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