Home | History | Annotate | Line # | Download | only in coda
coda_namecache.c revision 1.29
      1  1.29    andvar /*	$NetBSD: coda_namecache.c,v 1.29 2024/02/09 22:08:34 andvar Exp $	*/
      2   1.2       rvb 
      3   1.1       rvb /*
      4  1.14     perry  *
      5   1.2       rvb  *             Coda: an Experimental Distributed File System
      6   1.2       rvb  *                              Release 3.1
      7  1.14     perry  *
      8   1.2       rvb  *           Copyright (c) 1987-1998 Carnegie Mellon University
      9   1.2       rvb  *                          All Rights Reserved
     10  1.14     perry  *
     11   1.2       rvb  * Permission  to  use, copy, modify and distribute this software and its
     12   1.2       rvb  * documentation is hereby granted,  provided  that  both  the  copyright
     13   1.2       rvb  * notice  and  this  permission  notice  appear  in  all  copies  of the
     14   1.2       rvb  * software, derivative works or  modified  versions,  and  any  portions
     15   1.2       rvb  * thereof, and that both notices appear in supporting documentation, and
     16   1.2       rvb  * that credit is given to Carnegie Mellon University  in  all  documents
     17   1.2       rvb  * and publicity pertaining to direct or indirect use of this code or its
     18   1.2       rvb  * derivatives.
     19  1.14     perry  *
     20   1.2       rvb  * CODA IS AN EXPERIMENTAL SOFTWARE SYSTEM AND IS  KNOWN  TO  HAVE  BUGS,
     21   1.2       rvb  * SOME  OF  WHICH MAY HAVE SERIOUS CONSEQUENCES.  CARNEGIE MELLON ALLOWS
     22   1.2       rvb  * FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.   CARNEGIE  MELLON
     23   1.2       rvb  * DISCLAIMS  ANY  LIABILITY  OF  ANY  KIND  FOR  ANY  DAMAGES WHATSOEVER
     24   1.2       rvb  * RESULTING DIRECTLY OR INDIRECTLY FROM THE USE OF THIS SOFTWARE  OR  OF
     25   1.2       rvb  * ANY DERIVATIVE WORK.
     26  1.14     perry  *
     27   1.2       rvb  * Carnegie  Mellon  encourages  users  of  this  software  to return any
     28   1.2       rvb  * improvements or extensions that  they  make,  and  to  grant  Carnegie
     29   1.2       rvb  * Mellon the rights to redistribute these changes without encumbrance.
     30  1.14     perry  *
     31  1.14     perry  * 	@(#) coda/coda_namecache.c,v 1.1.1.1 1998/08/29 21:26:45 rvb Exp $
     32   1.2       rvb  */
     33   1.1       rvb 
     34  1.14     perry /*
     35   1.1       rvb  * Mach Operating System
     36   1.1       rvb  * Copyright (c) 1990 Carnegie-Mellon University
     37   1.1       rvb  * Copyright (c) 1989 Carnegie-Mellon University
     38   1.1       rvb  * All rights reserved.  The CMU software License Agreement specifies
     39   1.1       rvb  * the terms and conditions for use and redistribution.
     40   1.1       rvb  */
     41   1.1       rvb 
     42   1.1       rvb /*
     43   1.1       rvb  * This code was written for the Coda file system at Carnegie Mellon University.
     44   1.1       rvb  * Contributers include David Steere, James Kistler, and M. Satyanarayanan.
     45   1.1       rvb  */
     46   1.1       rvb 
     47   1.1       rvb /*
     48   1.3       rvb  * This module contains the routines to implement the CODA name cache. The
     49  1.14     perry  * purpose of this cache is to reduce the cost of translating pathnames
     50   1.1       rvb  * into Vice FIDs. Each entry in the cache contains the name of the file,
     51   1.1       rvb  * the vnode (FID) of the parent directory, and the cred structure of the
     52   1.1       rvb  * user accessing the file.
     53   1.1       rvb  *
     54   1.1       rvb  * The first time a file is accessed, it is looked up by the local Venus
     55   1.1       rvb  * which first insures that the user has access to the file. In addition
     56   1.1       rvb  * we are guaranteed that Venus will invalidate any name cache entries in
     57   1.1       rvb  * case the user no longer should be able to access the file. For these
     58   1.1       rvb  * reasons we do not need to keep access list information as well as a
     59   1.1       rvb  * cred structure for each entry.
     60   1.1       rvb  *
     61   1.1       rvb  * The table can be accessed through the routines cnc_init(), cnc_enter(),
     62   1.1       rvb  * cnc_lookup(), cnc_rmfidcred(), cnc_rmfid(), cnc_rmcred(), and cnc_purge().
     63   1.1       rvb  * There are several other routines which aid in the implementation of the
     64   1.1       rvb  * hash table.
     65   1.1       rvb  */
     66   1.1       rvb 
     67   1.1       rvb /*
     68   1.1       rvb  * NOTES: rvb@cs
     69   1.1       rvb  * 1.	The name cache holds a reference to every vnode in it.  Hence files can not be
     70   1.1       rvb  *	 closed or made inactive until they are released.
     71   1.3       rvb  * 2.	coda_nc_name(cp) was added to get a name for a cnode pointer for debugging.
     72   1.3       rvb  * 3.	coda_nc_find() has debug code to detect when entries are stored with different
     73   1.1       rvb  *	 credentials.  We don't understand yet, if/how entries are NOT EQ but still
     74   1.1       rvb  *	 EQUAL
     75   1.1       rvb  * 4.	I wonder if this name cache could be replace by the vnode name cache.
     76   1.1       rvb  *	The latter has no zapping functions, so probably not.
     77   1.1       rvb  */
     78  1.11     lukem 
     79  1.11     lukem #include <sys/cdefs.h>
     80  1.29    andvar __KERNEL_RCSID(0, "$NetBSD: coda_namecache.c,v 1.29 2024/02/09 22:08:34 andvar Exp $");
     81   1.1       rvb 
     82   1.1       rvb #include <sys/param.h>
     83   1.1       rvb #include <sys/errno.h>
     84   1.1       rvb #include <sys/malloc.h>
     85   1.1       rvb #include <sys/select.h>
     86  1.18      elad #include <sys/kauth.h>
     87   1.1       rvb 
     88   1.4       rvb #include <coda/coda.h>
     89   1.4       rvb #include <coda/cnode.h>
     90   1.4       rvb #include <coda/coda_namecache.h>
     91  1.25  christos #include <coda/coda_subr.h>
     92   1.5       rvb 
     93  1.14     perry /*
     94   1.1       rvb  * Declaration of the name cache data structure.
     95   1.1       rvb  */
     96   1.1       rvb 
     97   1.3       rvb int 	coda_nc_use = 1;			 /* Indicate use of CODA Name Cache */
     98   1.1       rvb 
     99   1.3       rvb int	coda_nc_size = CODA_NC_CACHESIZE;	 /* size of the cache */
    100   1.3       rvb int	coda_nc_hashsize = CODA_NC_HASHSIZE; /* size of the primary hash */
    101   1.1       rvb 
    102   1.3       rvb struct 	coda_cache *coda_nc_heap;	/* pointer to the cache entries */
    103   1.3       rvb struct	coda_hash  *coda_nc_hash;	/* hash table of cfscache pointers */
    104   1.3       rvb struct	coda_lru   coda_nc_lru;		/* head of lru chain */
    105   1.1       rvb 
    106   1.3       rvb struct coda_nc_statistics coda_nc_stat;	/* Keep various stats */
    107   1.1       rvb 
    108  1.14     perry /*
    109   1.1       rvb  * for testing purposes
    110   1.1       rvb  */
    111   1.3       rvb int coda_nc_debug = 0;
    112   1.1       rvb 
    113   1.1       rvb /*
    114   1.3       rvb  * Entry points for the CODA Name Cache
    115   1.1       rvb  */
    116   1.3       rvb static struct coda_cache *
    117   1.3       rvb coda_nc_find(struct cnode *dcp, const char *name, int namelen,
    118  1.18      elad 	kauth_cred_t cred, int hash);
    119   1.1       rvb static void
    120   1.3       rvb coda_nc_remove(struct coda_cache *cncp, enum dc_status dcstat);
    121   1.1       rvb 
    122  1.14     perry /*
    123   1.1       rvb  * Initialize the cache, the LRU structure and the Hash structure(s)
    124   1.1       rvb  */
    125   1.1       rvb 
    126   1.3       rvb #define TOTAL_CACHE_SIZE 	(sizeof(struct coda_cache) * coda_nc_size)
    127   1.3       rvb #define TOTAL_HASH_SIZE 	(sizeof(struct coda_hash)  * coda_nc_hashsize)
    128   1.1       rvb 
    129   1.3       rvb int coda_nc_initialized = 0;      /* Initially the cache has not been initialized */
    130   1.1       rvb 
    131   1.1       rvb void
    132   1.3       rvb coda_nc_init(void)
    133   1.1       rvb {
    134   1.1       rvb     int i;
    135   1.1       rvb 
    136   1.1       rvb     /* zero the statistics structure */
    137  1.14     perry 
    138  1.10   thorpej     memset(&coda_nc_stat, 0, (sizeof(struct coda_nc_statistics)));
    139   1.1       rvb 
    140   1.7       rvb #ifdef	CODA_VERBOSE
    141   1.3       rvb     printf("CODA NAME CACHE: CACHE %d, HASH TBL %d\n", CODA_NC_CACHESIZE, CODA_NC_HASHSIZE);
    142   1.5       rvb #endif
    143   1.3       rvb     CODA_ALLOC(coda_nc_heap, struct coda_cache *, TOTAL_CACHE_SIZE);
    144   1.3       rvb     CODA_ALLOC(coda_nc_hash, struct coda_hash *, TOTAL_HASH_SIZE);
    145  1.14     perry 
    146  1.22    plunky     memset(coda_nc_heap, 0, TOTAL_CACHE_SIZE);
    147  1.22    plunky     memset(coda_nc_hash, 0, TOTAL_HASH_SIZE);
    148  1.14     perry 
    149  1.22    plunky     TAILQ_INIT(&coda_nc_lru.head);
    150  1.14     perry 
    151   1.3       rvb     for (i=0; i < coda_nc_size; i++) {	/* initialize the heap */
    152  1.22    plunky 	TAILQ_INSERT_HEAD(&coda_nc_lru.head, &coda_nc_heap[i], lru);
    153   1.1       rvb     }
    154  1.14     perry 
    155   1.3       rvb     for (i=0; i < coda_nc_hashsize; i++) {	/* initialize the hashtable */
    156  1.22    plunky 	LIST_INIT(&coda_nc_hash[i].head);
    157   1.1       rvb     }
    158  1.14     perry 
    159   1.3       rvb     coda_nc_initialized++;
    160   1.1       rvb }
    161   1.1       rvb 
    162   1.1       rvb /*
    163  1.28    andvar  * Auxiliary routines -- shouldn't be entry points
    164   1.1       rvb  */
    165   1.1       rvb 
    166   1.3       rvb static struct coda_cache *
    167  1.16   xtraeme coda_nc_find(struct cnode *dcp, const char *name, int namelen,
    168  1.18      elad 	kauth_cred_t cred, int hash)
    169   1.1       rvb {
    170  1.14     perry 	/*
    171   1.1       rvb 	 * hash to find the appropriate bucket, look through the chain
    172  1.14     perry 	 * for the right entry (especially right cred, unless cred == 0)
    173   1.1       rvb 	 */
    174   1.3       rvb 	struct coda_cache *cncp;
    175   1.1       rvb 	int count = 1;
    176   1.1       rvb 
    177  1.14     perry 	CODA_NC_DEBUG(CODA_NC_FIND,
    178  1.13  drochner 		myprintf(("coda_nc_find(dcp %p, name %s, len %d, cred %p, hash %d\n",
    179  1.13  drochner 			dcp, name, namelen, cred, hash));)
    180   1.1       rvb 
    181  1.22    plunky 	LIST_FOREACH(cncp, &coda_nc_hash[hash].head, hash)
    182   1.1       rvb 	{
    183   1.1       rvb 
    184   1.3       rvb 	    if ((CODA_NAMEMATCH(cncp, name, namelen, dcp)) &&
    185  1.14     perry 		((cred == 0) || (cncp->cred == cred)))
    186  1.14     perry 	    {
    187   1.1       rvb 		/* compare cr_uid instead */
    188   1.3       rvb 		coda_nc_stat.Search_len += count;
    189   1.1       rvb 		return(cncp);
    190   1.1       rvb 	    }
    191   1.1       rvb #ifdef	DEBUG
    192   1.3       rvb 	    else if (CODA_NAMEMATCH(cncp, name, namelen, dcp)) {
    193   1.3       rvb 	    	printf("coda_nc_find: name %s, new cred = %p, cred = %p\n",
    194   1.1       rvb 			name, cred, cncp->cred);
    195   1.1       rvb 		printf("nref %d, nuid %d, ngid %d // oref %d, ocred %d, ogid %d\n",
    196  1.18      elad 			kauth_cred_getrefcnt(cred),
    197  1.18      elad 			kauth_cred_geteuid(cred),
    198  1.18      elad 			kauth_cred_getegid(cred),
    199  1.18      elad 			kauth_cred_getrefcnt(cncp->cred),
    200  1.18      elad 			kauth_cred_geteuid(cncp->cred),
    201  1.18      elad 			kauth_cred_getegid(cncp->cred));
    202  1.25  christos 		coda_print_cred(cred);
    203  1.25  christos 		coda_print_cred(cncp->cred);
    204   1.1       rvb 	    }
    205   1.1       rvb #endif
    206  1.22    plunky 	    count++;
    207   1.1       rvb 	}
    208   1.1       rvb 
    209   1.3       rvb 	return((struct coda_cache *)0);
    210   1.1       rvb }
    211   1.1       rvb 
    212   1.1       rvb /*
    213   1.1       rvb  * Enter a new (dir cnode, name) pair into the cache, updating the
    214   1.1       rvb  * LRU and Hash as needed.
    215   1.1       rvb  */
    216   1.1       rvb void
    217  1.16   xtraeme coda_nc_enter(struct cnode *dcp, const char *name, int namelen,
    218  1.18      elad 	kauth_cred_t cred, struct cnode *cp)
    219   1.1       rvb {
    220   1.3       rvb     struct coda_cache *cncp;
    221   1.1       rvb     int hash;
    222  1.14     perry 
    223   1.3       rvb     if (coda_nc_use == 0)			/* Cache is off */
    224   1.1       rvb 	return;
    225  1.14     perry 
    226  1.14     perry     CODA_NC_DEBUG(CODA_NC_ENTER,
    227   1.1       rvb 		myprintf(("Enter: dcp %p cp %p name %s cred %p \n",
    228   1.1       rvb 		       dcp, cp, name, cred)); )
    229  1.14     perry 
    230   1.3       rvb     if (namelen > CODA_NC_NAMELEN) {
    231  1.14     perry 	CODA_NC_DEBUG(CODA_NC_ENTER,
    232   1.1       rvb 		    myprintf(("long name enter %s\n",name));)
    233   1.3       rvb 	    coda_nc_stat.long_name_enters++;	/* record stats */
    234   1.1       rvb 	return;
    235   1.1       rvb     }
    236  1.14     perry 
    237   1.3       rvb     hash = CODA_NC_HASH(name, namelen, dcp);
    238   1.3       rvb     cncp = coda_nc_find(dcp, name, namelen, cred, hash);
    239  1.14     perry     if (cncp != (struct coda_cache *) 0) {
    240   1.3       rvb 	coda_nc_stat.dbl_enters++;		/* duplicate entry */
    241   1.1       rvb 	return;
    242   1.1       rvb     }
    243  1.14     perry 
    244   1.3       rvb     coda_nc_stat.enters++;		/* record the enters statistic */
    245  1.14     perry 
    246   1.1       rvb     /* Grab the next element in the lru chain */
    247  1.22    plunky     cncp = TAILQ_FIRST(&coda_nc_lru.head);
    248  1.22    plunky     TAILQ_REMOVE(&coda_nc_lru.head, cncp, lru);
    249  1.14     perry 
    250   1.3       rvb     if (CODA_NC_VALID(cncp)) {
    251   1.1       rvb 	/* Seems really ugly, but we have to decrement the appropriate
    252   1.1       rvb 	   hash bucket length here, so we have to find the hash bucket
    253   1.1       rvb 	   */
    254   1.3       rvb 	coda_nc_hash[CODA_NC_HASH(cncp->name, cncp->namelen, cncp->dcp)].length--;
    255  1.14     perry 
    256   1.3       rvb 	coda_nc_stat.lru_rm++;	/* zapped a valid entry */
    257  1.22    plunky 	LIST_REMOVE(cncp, hash);
    258  1.14     perry 	vrele(CTOV(cncp->dcp));
    259   1.1       rvb 	vrele(CTOV(cncp->cp));
    260  1.18      elad 	kauth_cred_free(cncp->cred);
    261   1.1       rvb     }
    262  1.14     perry 
    263   1.1       rvb     /*
    264   1.1       rvb      * Put a hold on the current vnodes and fill in the cache entry.
    265   1.1       rvb      */
    266   1.1       rvb     vref(CTOV(cp));
    267   1.1       rvb     vref(CTOV(dcp));
    268  1.18      elad     kauth_cred_hold(cred);
    269   1.1       rvb     cncp->dcp = dcp;
    270   1.1       rvb     cncp->cp = cp;
    271   1.1       rvb     cncp->namelen = namelen;
    272   1.1       rvb     cncp->cred = cred;
    273  1.14     perry 
    274  1.24   tsutsui     memcpy(cncp->name, name, (unsigned)namelen);
    275  1.14     perry 
    276   1.1       rvb     /* Insert into the lru and hash chains. */
    277  1.22    plunky     TAILQ_INSERT_TAIL(&coda_nc_lru.head, cncp, lru);
    278  1.22    plunky     LIST_INSERT_HEAD(&coda_nc_hash[hash].head, cncp, hash);
    279   1.3       rvb     coda_nc_hash[hash].length++;                      /* Used for tuning */
    280  1.14     perry 
    281   1.3       rvb     CODA_NC_DEBUG(CODA_NC_PRINTCODA_NC, print_coda_nc(); )
    282   1.1       rvb }
    283   1.1       rvb 
    284   1.1       rvb /*
    285  1.26       snj  * Find the (dir cnode, name) pair in the cache, if its cred
    286   1.1       rvb  * matches the input, return it, otherwise return 0
    287   1.1       rvb  */
    288   1.1       rvb struct cnode *
    289  1.16   xtraeme coda_nc_lookup(struct cnode *dcp, const char *name, int namelen,
    290  1.18      elad 	kauth_cred_t cred)
    291   1.1       rvb {
    292   1.1       rvb 	int hash;
    293   1.3       rvb 	struct coda_cache *cncp;
    294   1.1       rvb 
    295   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    296   1.1       rvb 		return((struct cnode *) 0);
    297   1.1       rvb 
    298   1.3       rvb 	if (namelen > CODA_NC_NAMELEN) {
    299  1.14     perry 	        CODA_NC_DEBUG(CODA_NC_LOOKUP,
    300   1.1       rvb 			    myprintf(("long name lookup %s\n",name));)
    301   1.3       rvb 		coda_nc_stat.long_name_lookups++;		/* record stats */
    302   1.1       rvb 		return((struct cnode *) 0);
    303   1.1       rvb 	}
    304   1.1       rvb 
    305   1.1       rvb 	/* Use the hash function to locate the starting point,
    306   1.1       rvb 	   then the search routine to go down the list looking for
    307   1.1       rvb 	   the correct cred.
    308   1.1       rvb  	 */
    309   1.1       rvb 
    310   1.3       rvb 	hash = CODA_NC_HASH(name, namelen, dcp);
    311   1.3       rvb 	cncp = coda_nc_find(dcp, name, namelen, cred, hash);
    312   1.3       rvb 	if (cncp == (struct coda_cache *) 0) {
    313   1.3       rvb 		coda_nc_stat.misses++;			/* record miss */
    314   1.1       rvb 		return((struct cnode *) 0);
    315   1.1       rvb 	}
    316   1.1       rvb 
    317   1.3       rvb 	coda_nc_stat.hits++;
    318   1.1       rvb 
    319   1.1       rvb 	/* put this entry at the end of the LRU */
    320  1.22    plunky 	TAILQ_REMOVE(&coda_nc_lru.head, cncp, lru);
    321  1.22    plunky 	TAILQ_INSERT_TAIL(&coda_nc_lru.head, cncp, lru);
    322   1.1       rvb 
    323   1.1       rvb 	/* move it to the front of the hash chain */
    324   1.1       rvb 	/* don't need to change the hash bucket length */
    325  1.22    plunky 	LIST_REMOVE(cncp, hash);
    326  1.22    plunky 	LIST_INSERT_HEAD(&coda_nc_hash[hash].head, cncp, hash);
    327   1.1       rvb 
    328  1.14     perry 	CODA_NC_DEBUG(CODA_NC_LOOKUP,
    329   1.1       rvb 		printf("lookup: dcp %p, name %s, cred %p = cp %p\n",
    330   1.1       rvb 			dcp, name, cred, cncp->cp); )
    331   1.1       rvb 
    332   1.1       rvb 	return(cncp->cp);
    333   1.1       rvb }
    334   1.1       rvb 
    335   1.1       rvb static void
    336  1.16   xtraeme coda_nc_remove(struct coda_cache *cncp, enum dc_status dcstat)
    337   1.1       rvb {
    338  1.14     perry 	/*
    339   1.1       rvb 	 * remove an entry -- vrele(cncp->dcp, cp), crfree(cred),
    340  1.26       snj 	 * remove it from its hash chain, and
    341   1.1       rvb 	 * place it at the head of the lru list.
    342   1.1       rvb 	 */
    343   1.3       rvb         CODA_NC_DEBUG(CODA_NC_REMOVE,
    344  1.13  drochner 		    myprintf(("coda_nc_remove %s from parent %s\n",
    345  1.13  drochner 			      cncp->name, coda_f2s(&cncp->dcp->c_fid))); )
    346  1.14     perry 
    347   1.1       rvb 
    348  1.22    plunky 	LIST_REMOVE(cncp, hash);
    349  1.22    plunky 	memset(&cncp->hash, 0, sizeof(cncp->hash));
    350   1.1       rvb 
    351  1.27        ad 	if ((dcstat == IS_DOWNCALL) && (vrefcnt(CTOV(cncp->dcp)) == 1)) {
    352   1.1       rvb 		cncp->dcp->c_flags |= C_PURGING;
    353   1.1       rvb 	}
    354  1.14     perry 	vrele(CTOV(cncp->dcp));
    355   1.1       rvb 
    356  1.27        ad 	if ((dcstat == IS_DOWNCALL) && (vrefcnt(CTOV(cncp->cp)) == 1)) {
    357   1.1       rvb 		cncp->cp->c_flags |= C_PURGING;
    358   1.1       rvb 	}
    359  1.14     perry 	vrele(CTOV(cncp->cp));
    360   1.1       rvb 
    361  1.18      elad 	kauth_cred_free(cncp->cred);
    362  1.10   thorpej 	memset(DATA_PART(cncp), 0, DATA_SIZE);
    363   1.1       rvb 
    364  1.22    plunky 	/* move the null entry to the front for reuse */
    365  1.22    plunky 	TAILQ_REMOVE(&coda_nc_lru.head, cncp, lru);
    366  1.22    plunky 	TAILQ_INSERT_HEAD(&coda_nc_lru.head, cncp, lru);
    367   1.1       rvb }
    368   1.1       rvb 
    369   1.1       rvb /*
    370   1.1       rvb  * Remove all entries with a parent which has the input fid.
    371   1.1       rvb  */
    372   1.1       rvb void
    373  1.16   xtraeme coda_nc_zapParentfid(CodaFid *fid, enum dc_status dcstat)
    374   1.1       rvb {
    375   1.1       rvb 	/* To get to a specific fid, we might either have another hashing
    376   1.1       rvb 	   function or do a sequential search through the cache for the
    377   1.1       rvb 	   appropriate entries. The later may be acceptable since I don't
    378  1.12       wiz 	   think callbacks or whatever Case 1 covers are frequent occurrences.
    379   1.1       rvb 	 */
    380   1.3       rvb 	struct coda_cache *cncp, *ncncp;
    381   1.1       rvb 	int i;
    382   1.1       rvb 
    383   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    384   1.1       rvb 		return;
    385   1.1       rvb 
    386  1.14     perry 	CODA_NC_DEBUG(CODA_NC_ZAPPFID,
    387  1.13  drochner 		myprintf(("ZapParent: fid %s\n", coda_f2s(fid))); )
    388   1.1       rvb 
    389   1.3       rvb 	coda_nc_stat.zapPfids++;
    390   1.1       rvb 
    391   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++) {
    392   1.1       rvb 
    393   1.1       rvb 		/*
    394   1.1       rvb 		 * Need to save the hash_next pointer in case we remove the
    395   1.1       rvb 		 * entry. remove causes hash_next to point to itself.
    396   1.1       rvb 		 */
    397   1.1       rvb 
    398  1.22    plunky 		ncncp = LIST_FIRST(&coda_nc_hash[i].head);
    399  1.22    plunky 		while ((cncp = ncncp) != NULL) {
    400  1.22    plunky 			ncncp = LIST_NEXT(cncp, hash);
    401  1.22    plunky 
    402  1.13  drochner 			if (coda_fid_eq(&(cncp->dcp->c_fid), fid)) {
    403   1.3       rvb 			        coda_nc_hash[i].length--;      /* Used for tuning */
    404  1.14     perry 				coda_nc_remove(cncp, dcstat);
    405   1.1       rvb 			}
    406   1.1       rvb 		}
    407   1.1       rvb 	}
    408   1.1       rvb }
    409   1.1       rvb 
    410   1.1       rvb /*
    411   1.1       rvb  * Remove all entries which have the same fid as the input
    412   1.1       rvb  */
    413   1.1       rvb void
    414  1.16   xtraeme coda_nc_zapfid(CodaFid *fid, enum dc_status dcstat)
    415   1.1       rvb {
    416   1.1       rvb 	/* See comment for zapParentfid. This routine will be used
    417  1.14     perry 	   if attributes are being cached.
    418   1.1       rvb 	 */
    419   1.3       rvb 	struct coda_cache *cncp, *ncncp;
    420   1.1       rvb 	int i;
    421   1.1       rvb 
    422   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    423   1.1       rvb 		return;
    424   1.1       rvb 
    425  1.14     perry 	CODA_NC_DEBUG(CODA_NC_ZAPFID,
    426  1.13  drochner 		myprintf(("Zapfid: fid %s\n", coda_f2s(fid))); )
    427   1.1       rvb 
    428   1.3       rvb 	coda_nc_stat.zapFids++;
    429   1.1       rvb 
    430   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++) {
    431  1.22    plunky 
    432  1.22    plunky 		ncncp = LIST_FIRST(&coda_nc_hash[i].head);
    433  1.22    plunky 		while ((cncp = ncncp) != NULL) {
    434  1.22    plunky 			ncncp = LIST_NEXT(cncp, hash);
    435  1.22    plunky 
    436  1.13  drochner 			if (coda_fid_eq(&cncp->cp->c_fid, fid)) {
    437   1.3       rvb 			        coda_nc_hash[i].length--;     /* Used for tuning */
    438  1.14     perry 				coda_nc_remove(cncp, dcstat);
    439   1.1       rvb 			}
    440   1.1       rvb 		}
    441   1.1       rvb 	}
    442   1.1       rvb }
    443   1.1       rvb 
    444  1.14     perry /*
    445   1.1       rvb  * Remove all entries which match the fid and the cred
    446   1.1       rvb  */
    447   1.1       rvb void
    448  1.19  christos coda_nc_zapvnode(CodaFid *fid, kauth_cred_t cred,
    449  1.20  christos     enum dc_status dcstat)
    450   1.1       rvb {
    451   1.1       rvb 	/* See comment for zapfid. I don't think that one would ever
    452   1.1       rvb 	   want to zap a file with a specific cred from the kernel.
    453   1.1       rvb 	   We'll leave this one unimplemented.
    454   1.1       rvb 	 */
    455   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    456   1.1       rvb 		return;
    457   1.1       rvb 
    458  1.14     perry 	CODA_NC_DEBUG(CODA_NC_ZAPVNODE,
    459  1.13  drochner 		myprintf(("Zapvnode: fid %s cred %p\n",
    460  1.13  drochner 			  coda_f2s(fid), cred)); )
    461   1.1       rvb }
    462   1.1       rvb 
    463   1.1       rvb /*
    464   1.1       rvb  * Remove all entries which have the (dir vnode, name) pair
    465   1.1       rvb  */
    466   1.1       rvb void
    467  1.16   xtraeme coda_nc_zapfile(struct cnode *dcp, const char *name, int namelen)
    468   1.1       rvb {
    469   1.1       rvb 	/* use the hash function to locate the file, then zap all
    470   1.1       rvb  	   entries of it regardless of the cred.
    471   1.1       rvb 	 */
    472   1.3       rvb 	struct coda_cache *cncp;
    473   1.1       rvb 	int hash;
    474   1.1       rvb 
    475   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    476   1.1       rvb 		return;
    477   1.1       rvb 
    478  1.14     perry 	CODA_NC_DEBUG(CODA_NC_ZAPFILE,
    479   1.1       rvb 		myprintf(("Zapfile: dcp %p name %s \n",
    480   1.1       rvb 			  dcp, name)); )
    481   1.1       rvb 
    482   1.3       rvb 	if (namelen > CODA_NC_NAMELEN) {
    483   1.3       rvb 		coda_nc_stat.long_remove++;		/* record stats */
    484   1.1       rvb 		return;
    485   1.1       rvb 	}
    486   1.1       rvb 
    487   1.3       rvb 	coda_nc_stat.zapFile++;
    488   1.1       rvb 
    489   1.3       rvb 	hash = CODA_NC_HASH(name, namelen, dcp);
    490   1.3       rvb 	cncp = coda_nc_find(dcp, name, namelen, 0, hash);
    491   1.1       rvb 
    492   1.1       rvb 	while (cncp) {
    493   1.3       rvb 	  coda_nc_hash[hash].length--;                 /* Used for tuning */
    494   1.1       rvb /* 1.3 */
    495   1.3       rvb 	  coda_nc_remove(cncp, NOT_DOWNCALL);
    496   1.3       rvb 	  cncp = coda_nc_find(dcp, name, namelen, 0, hash);
    497   1.1       rvb 	}
    498   1.1       rvb }
    499   1.1       rvb 
    500  1.14     perry /*
    501   1.1       rvb  * Remove all the entries for a particular user. Used when tokens expire.
    502   1.1       rvb  * A user is determined by his/her effective user id (id_uid).
    503   1.1       rvb  */
    504   1.1       rvb void
    505  1.16   xtraeme coda_nc_purge_user(uid_t uid, enum dc_status dcstat)
    506   1.1       rvb {
    507  1.14     perry 	/*
    508   1.1       rvb 	 * I think the best approach is to go through the entire cache
    509   1.1       rvb 	 * via HASH or whatever and zap all entries which match the
    510   1.1       rvb 	 * input cred. Or just flush the whole cache.  It might be
    511   1.1       rvb 	 * best to go through on basis of LRU since cache will almost
    512  1.14     perry 	 * always be full and LRU is more straightforward.
    513   1.1       rvb 	 */
    514   1.1       rvb 
    515   1.3       rvb 	struct coda_cache *cncp, *ncncp;
    516   1.1       rvb 	int hash;
    517   1.1       rvb 
    518   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    519   1.1       rvb 		return;
    520   1.1       rvb 
    521  1.14     perry 	CODA_NC_DEBUG(CODA_NC_PURGEUSER,
    522   1.8       rvb 		myprintf(("ZapDude: uid %x\n", uid)); )
    523   1.3       rvb 	coda_nc_stat.zapUsers++;
    524   1.1       rvb 
    525  1.22    plunky 	ncncp = TAILQ_FIRST(&coda_nc_lru.head);
    526  1.22    plunky 	while ((cncp = ncncp) != NULL) {
    527  1.22    plunky 		ncncp = TAILQ_NEXT(cncp, lru);
    528   1.1       rvb 
    529   1.3       rvb 		if ((CODA_NC_VALID(cncp)) &&
    530  1.18      elad 		   (kauth_cred_geteuid(cncp->cred) == uid)) {
    531   1.1       rvb 		        /* Seems really ugly, but we have to decrement the appropriate
    532   1.1       rvb 			   hash bucket length here, so we have to find the hash bucket
    533   1.1       rvb 			   */
    534   1.3       rvb 		        hash = CODA_NC_HASH(cncp->name, cncp->namelen, cncp->dcp);
    535   1.3       rvb 			coda_nc_hash[hash].length--;     /* For performance tuning */
    536   1.1       rvb 
    537  1.14     perry 			coda_nc_remove(cncp, dcstat);
    538   1.1       rvb 		}
    539   1.1       rvb 	}
    540   1.1       rvb }
    541   1.1       rvb 
    542   1.1       rvb /*
    543   1.1       rvb  * Flush the entire name cache. In response to a flush of the Venus cache.
    544   1.1       rvb  */
    545   1.1       rvb void
    546  1.16   xtraeme coda_nc_flush(enum dc_status dcstat)
    547   1.1       rvb {
    548   1.1       rvb 	/* One option is to deallocate the current name cache and
    549   1.1       rvb 	   call init to start again. Or just deallocate, then rebuild.
    550  1.14     perry 	   Or again, we could just go through the array and zero the
    551  1.14     perry 	   appropriate fields.
    552   1.1       rvb 	 */
    553  1.14     perry 
    554  1.14     perry 	/*
    555   1.1       rvb 	 * Go through the whole lru chain and kill everything as we go.
    556   1.1       rvb 	 * I don't use remove since that would rebuild the lru chain
    557  1.29    andvar 	 * as it went and that seemed unnecessary.
    558   1.1       rvb 	 */
    559   1.3       rvb 	struct coda_cache *cncp;
    560   1.1       rvb 	int i;
    561   1.1       rvb 
    562   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    563   1.1       rvb 		return;
    564   1.1       rvb 
    565   1.3       rvb 	coda_nc_stat.Flushes++;
    566   1.1       rvb 
    567  1.22    plunky 	TAILQ_FOREACH(cncp, &coda_nc_lru.head, lru) {
    568  1.22    plunky 		if (CODA_NC_VALID(cncp)) {	/* only zero valid nodes */
    569  1.22    plunky 			LIST_REMOVE(cncp, hash);
    570  1.22    plunky 			memset(&cncp->hash, 0, sizeof(cncp->hash));
    571   1.1       rvb 
    572  1.14     perry 			if ((dcstat == IS_DOWNCALL)
    573  1.27        ad 			    && (vrefcnt(CTOV(cncp->dcp)) == 1))
    574   1.1       rvb 			{
    575   1.1       rvb 				cncp->dcp->c_flags |= C_PURGING;
    576   1.1       rvb 			}
    577  1.14     perry 			vrele(CTOV(cncp->dcp));
    578   1.1       rvb 
    579  1.21        ad 			if (CTOV(cncp->cp)->v_iflag & VI_TEXT) {
    580   1.3       rvb 			    if (coda_vmflush(cncp->cp))
    581  1.14     perry 				CODADEBUG(CODA_FLUSH,
    582  1.13  drochner 					myprintf(("coda_nc_flush: %s busy\n",
    583  1.13  drochner 						coda_f2s(&cncp->cp->c_fid))); )
    584   1.1       rvb 			}
    585   1.1       rvb 
    586  1.14     perry 			if ((dcstat == IS_DOWNCALL)
    587  1.27        ad 			    && (vrefcnt(CTOV(cncp->cp)) == 1))
    588   1.1       rvb 			{
    589   1.1       rvb 				cncp->cp->c_flags |= C_PURGING;
    590   1.1       rvb 			}
    591  1.14     perry 			vrele(CTOV(cncp->cp));
    592   1.1       rvb 
    593  1.18      elad 			kauth_cred_free(cncp->cred);
    594  1.10   thorpej 			memset(DATA_PART(cncp), 0, DATA_SIZE);
    595   1.1       rvb 		}
    596   1.1       rvb 	}
    597   1.1       rvb 
    598   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++)
    599   1.3       rvb 	  coda_nc_hash[i].length = 0;
    600   1.1       rvb }
    601   1.1       rvb 
    602   1.1       rvb /*
    603   1.1       rvb  * Debugging routines
    604   1.1       rvb  */
    605   1.1       rvb 
    606  1.14     perry /*
    607   1.1       rvb  * This routine should print out all the hash chains to the console.
    608   1.1       rvb  */
    609   1.1       rvb void
    610   1.3       rvb print_coda_nc(void)
    611   1.1       rvb {
    612   1.1       rvb 	int hash;
    613   1.3       rvb 	struct coda_cache *cncp;
    614   1.1       rvb 
    615   1.3       rvb 	for (hash = 0; hash < coda_nc_hashsize; hash++) {
    616   1.1       rvb 		myprintf(("\nhash %d\n",hash));
    617   1.1       rvb 
    618  1.22    plunky 		LIST_FOREACH(cncp, &coda_nc_hash[hash].head, hash) {
    619   1.1       rvb 			myprintf(("cp %p dcp %p cred %p name %s\n",
    620   1.1       rvb 				  cncp->cp, cncp->dcp,
    621   1.1       rvb 				  cncp->cred, cncp->name));
    622   1.1       rvb 		     }
    623   1.1       rvb 	}
    624   1.1       rvb }
    625   1.1       rvb 
    626   1.1       rvb void
    627   1.3       rvb coda_nc_gather_stats(void)
    628   1.1       rvb {
    629  1.15  christos     int i, xmax = 0, sum = 0, temp, zeros = 0, ave, n;
    630   1.1       rvb 
    631   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++) {
    632   1.3       rvb 	  if (coda_nc_hash[i].length) {
    633   1.3       rvb 	    sum += coda_nc_hash[i].length;
    634   1.1       rvb 	  } else {
    635   1.1       rvb 	    zeros++;
    636   1.1       rvb 	  }
    637   1.1       rvb 
    638  1.15  christos 	  if (coda_nc_hash[i].length > xmax)
    639  1.15  christos 	    xmax = coda_nc_hash[i].length;
    640   1.1       rvb 	}
    641   1.1       rvb 
    642   1.1       rvb 	/*
    643  1.14     perry 	 * When computing the Arithmetic mean, only count slots which
    644   1.1       rvb 	 * are not empty in the distribution.
    645   1.1       rvb 	 */
    646   1.3       rvb         coda_nc_stat.Sum_bucket_len = sum;
    647   1.3       rvb         coda_nc_stat.Num_zero_len = zeros;
    648  1.15  christos         coda_nc_stat.Max_bucket_len = xmax;
    649   1.1       rvb 
    650  1.14     perry 	if ((n = coda_nc_hashsize - zeros) > 0)
    651   1.1       rvb 	  ave = sum / n;
    652   1.1       rvb 	else
    653   1.1       rvb 	  ave = 0;
    654   1.1       rvb 
    655   1.1       rvb 	sum = 0;
    656   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++) {
    657   1.3       rvb 	  if (coda_nc_hash[i].length) {
    658   1.3       rvb 	    temp = coda_nc_hash[i].length - ave;
    659   1.1       rvb 	    sum += temp * temp;
    660   1.1       rvb 	  }
    661   1.1       rvb 	}
    662   1.3       rvb         coda_nc_stat.Sum2_bucket_len = sum;
    663   1.1       rvb }
    664   1.1       rvb 
    665   1.1       rvb /*
    666   1.1       rvb  * The purpose of this routine is to allow the hash and cache sizes to be
    667   1.1       rvb  * changed dynamically. This should only be used in controlled environments,
    668   1.1       rvb  * it makes no effort to lock other users from accessing the cache while it
    669   1.1       rvb  * is in an improper state (except by turning the cache off).
    670   1.1       rvb  */
    671   1.1       rvb int
    672  1.16   xtraeme coda_nc_resize(int hashsize, int heapsize, enum dc_status dcstat)
    673   1.1       rvb {
    674   1.1       rvb     if ((hashsize % 2) || (heapsize % 2)) { /* Illegal hash or cache sizes */
    675   1.1       rvb 	return(EINVAL);
    676  1.14     perry     }
    677  1.14     perry 
    678   1.3       rvb     coda_nc_use = 0;                       /* Turn the cache off */
    679  1.14     perry 
    680   1.3       rvb     coda_nc_flush(dcstat);                 /* free any cnodes in the cache */
    681  1.14     perry 
    682   1.1       rvb     /* WARNING: free must happen *before* size is reset */
    683   1.3       rvb     CODA_FREE(coda_nc_heap,TOTAL_CACHE_SIZE);
    684   1.3       rvb     CODA_FREE(coda_nc_hash,TOTAL_HASH_SIZE);
    685  1.14     perry 
    686   1.3       rvb     coda_nc_hashsize = hashsize;
    687   1.3       rvb     coda_nc_size = heapsize;
    688  1.14     perry 
    689   1.3       rvb     coda_nc_init();                        /* Set up a cache with the new size */
    690  1.14     perry 
    691   1.3       rvb     coda_nc_use = 1;                       /* Turn the cache back on */
    692   1.1       rvb     return(0);
    693   1.1       rvb }
    694   1.1       rvb 
    695   1.3       rvb char coda_nc_name_buf[CODA_MAXNAMLEN+1];
    696   1.1       rvb 
    697   1.1       rvb void
    698   1.3       rvb coda_nc_name(struct cnode *cp)
    699   1.1       rvb {
    700  1.22    plunky 	struct coda_cache *cncp;
    701   1.1       rvb 	int i;
    702   1.1       rvb 
    703   1.3       rvb 	if (coda_nc_use == 0)			/* Cache is off */
    704   1.1       rvb 		return;
    705   1.1       rvb 
    706   1.3       rvb 	for (i = 0; i < coda_nc_hashsize; i++) {
    707  1.22    plunky 
    708  1.22    plunky 		LIST_FOREACH(cncp, &coda_nc_hash[i].head, hash) {
    709   1.1       rvb 			if (cncp->cp == cp) {
    710  1.24   tsutsui 				memcpy(coda_nc_name_buf, cncp->name, cncp->namelen);
    711   1.3       rvb 				coda_nc_name_buf[cncp->namelen] = 0;
    712   1.1       rvb 				printf(" is %s (%p,%p)@%p",
    713   1.3       rvb 					coda_nc_name_buf, cncp->cp, cncp->dcp, cncp);
    714   1.1       rvb 			}
    715   1.1       rvb 
    716   1.1       rvb 		}
    717   1.1       rvb 	}
    718   1.1       rvb }
    719