3 * Coda: an Experimental Distributed File System
6 * Copyright (c) 1987-1998 Carnegie Mellon University
9 * Permission to use, copy, modify and distribute this software and its
10 * documentation is hereby granted, provided that both the copyright
11 * notice and this permission notice appear in all copies of the
12 * software, derivative works or modified versions, and any portions
13 * thereof, and that both notices appear in supporting documentation, and
14 * that credit is given to Carnegie Mellon University in all documents
15 * and publicity pertaining to direct or indirect use of this code or its
18 * CODA IS AN EXPERIMENTAL SOFTWARE SYSTEM AND IS KNOWN TO HAVE BUGS,
19 * SOME OF WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON ALLOWS
20 * FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION. CARNEGIE MELLON
21 * DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER
22 * RESULTING DIRECTLY OR INDIRECTLY FROM THE USE OF THIS SOFTWARE OR OF
23 * ANY DERIVATIVE WORK.
25 * Carnegie Mellon encourages users of this software to return any
26 * improvements or extensions that they make, and to grant Carnegie
27 * Mellon the rights to redistribute these changes without encumbrance.
29 * @(#) src/sys/coda/coda_namecache.c,v 1.1.1.1 1998/08/29 21:14:52 rvb Exp $
30 * $FreeBSD: src/sys/coda/coda_namecache.c,v 1.10 1999/08/28 00:40:53 peter Exp $
31 * $DragonFly: src/sys/vfs/coda/Attic/coda_namecache.c,v 1.6 2004/03/31 02:34:37 cpressey Exp $
36 * Mach Operating System
37 * Copyright (c) 1990 Carnegie-Mellon University
38 * Copyright (c) 1989 Carnegie-Mellon University
39 * All rights reserved. The CMU software License Agreement specifies
40 * the terms and conditions for use and redistribution.
44 * This code was written for the Coda file system at Carnegie Mellon University.
45 * Contributers include David Steere, James Kistler, and M. Satyanarayanan.
49 * This module contains the routines to implement the CODA name cache. The
50 * purpose of this cache is to reduce the cost of translating pathnames
51 * into Vice FIDs. Each entry in the cache contains the name of the file,
52 * the vnode (FID) of the parent directory, and the cred structure of the
53 * user accessing the file.
55 * The first time a file is accessed, it is looked up by the local Venus
56 * which first insures that the user has access to the file. In addition
57 * we are guaranteed that Venus will invalidate any name cache entries in
58 * case the user no longer should be able to access the file. For these
59 * reasons we do not need to keep access list information as well as a
60 * cred structure for each entry.
62 * The table can be accessed through the routines cnc_init(), cnc_enter(),
63 * cnc_lookup(), cnc_rmfidcred(), cnc_rmfid(), cnc_rmcred(), and cnc_purge().
64 * There are several other routines which aid in the implementation of the
70 * 1. The name cache holds a reference to every vnode in it. Hence files can not be
71 * closed or made inactive until they are released.
72 * 2. coda_nc_name(cp) was added to get a name for a cnode pointer for debugging.
73 * 3. coda_nc_find() has debug code to detect when entries are stored with different
74 * credentials. We don't understand yet, if/how entries are NOT EQ but still
76 * 4. I wonder if this name cache could be replace by the vnode name cache.
77 * The latter has no zapping functions, so probably not.
80 #include <sys/param.h>
81 #include <sys/errno.h>
82 #include <sys/malloc.h>
83 #include <sys/ucred.h>
84 #include <sys/select.h>
87 #include <sys/systm.h>
91 #include <vm/vm_object.h>
95 #include "coda_namecache.h"
98 #include "coda_vnops.h"
102 * Declaration of the name cache data structure.
105 int coda_nc_use = 1; /* Indicate use of CODA Name Cache */
106 int coda_nc_size = CODA_NC_CACHESIZE; /* size of the cache */
107 int coda_nc_hashsize = CODA_NC_HASHSIZE; /* size of the primary hash */
109 struct coda_cache *coda_nc_heap; /* pointer to the cache entries */
110 struct coda_hash *coda_nc_hash; /* hash table of coda_cache pointers */
111 struct coda_lru coda_nc_lru; /* head of lru chain */
113 struct coda_nc_statistics coda_nc_stat; /* Keep various stats */
116 * for testing purposes
118 int coda_nc_debug = 0;
121 * Entry points for the CODA Name Cache
123 static struct coda_cache *coda_nc_find(struct cnode *dcp, const char *name, int namelen,
124 struct ucred *cred, int hash);
125 static void coda_nc_remove(struct coda_cache *cncp, enum dc_status dcstat);
128 * Initialize the cache, the LRU structure and the Hash structure(s)
131 #define TOTAL_CACHE_SIZE (sizeof(struct coda_cache) * coda_nc_size)
132 #define TOTAL_HASH_SIZE (sizeof(struct coda_hash) * coda_nc_hashsize)
134 int coda_nc_initialized = 0; /* Initially the cache has not been initialized */
141 /* zero the statistics structure */
143 bzero(&coda_nc_stat, (sizeof(struct coda_nc_statistics)));
146 printf("CODA NAME CACHE: CACHE %d, HASH TBL %d\n", CODA_NC_CACHESIZE, CODA_NC_HASHSIZE);
148 CODA_ALLOC(coda_nc_heap, struct coda_cache *, TOTAL_CACHE_SIZE);
149 CODA_ALLOC(coda_nc_hash, struct coda_hash *, TOTAL_HASH_SIZE);
151 coda_nc_lru.lru_next =
152 coda_nc_lru.lru_prev = (struct coda_cache *)LRU_PART(&coda_nc_lru);
155 for (i=0; i < coda_nc_size; i++) { /* initialize the heap */
156 CODA_NC_LRUINS(&coda_nc_heap[i], &coda_nc_lru);
157 CODA_NC_HSHNUL(&coda_nc_heap[i]);
158 coda_nc_heap[i].cp = coda_nc_heap[i].dcp = (struct cnode *)0;
161 for (i=0; i < coda_nc_hashsize; i++) { /* initialize the hashtable */
162 CODA_NC_HSHNUL((struct coda_cache *)&coda_nc_hash[i]);
165 coda_nc_initialized++;
169 * Auxillary routines -- shouldn't be entry points
172 static struct coda_cache *
173 coda_nc_find(struct cnode *dcp, const char *name, int namelen,
174 struct ucred *cred, int hash)
177 * hash to find the appropriate bucket, look through the chain
178 * for the right entry (especially right cred, unless cred == 0)
180 struct coda_cache *cncp;
183 CODA_NC_DEBUG(CODA_NC_FIND,
184 myprintf(("coda_nc_find(dcp %p, name %s, len %d, cred %p, hash %d\n",
185 dcp, name, namelen, cred, hash));)
187 for (cncp = coda_nc_hash[hash].hash_next;
188 cncp != (struct coda_cache *)&coda_nc_hash[hash];
189 cncp = cncp->hash_next, count++)
192 if ((CODA_NAMEMATCH(cncp, name, namelen, dcp)) &&
193 ((cred == 0) || (cncp->cred == cred)))
195 /* compare cr_uid instead */
196 coda_nc_stat.Search_len += count;
200 else if (CODA_NAMEMATCH(cncp, name, namelen, dcp)) {
201 printf("coda_nc_find: name %s, new cred = %p, cred = %p\n",
202 name, cred, cncp->cred);
203 printf("nref %d, nuid %d, ngid %d // oref %d, ocred %d, ogid %d\n",
204 cred->cr_ref, cred->cr_uid, cred->cr_gid,
205 cncp->cred->cr_ref, cncp->cred->cr_uid, cncp->cred->cr_gid);
207 print_cred(cncp->cred);
212 return((struct coda_cache *)0);
216 * Enter a new (dir cnode, name) pair into the cache, updating the
217 * LRU and Hash as needed.
220 coda_nc_enter(struct cnode *dcp, const char *name, int namelen,
221 struct ucred *cred, struct cnode *cp)
223 struct coda_cache *cncp;
226 if (coda_nc_use == 0) /* Cache is off */
229 CODA_NC_DEBUG(CODA_NC_ENTER,
230 myprintf(("Enter: dcp %p cp %p name %s cred %p \n",
231 dcp, cp, name, cred)); )
233 if (namelen > CODA_NC_NAMELEN) {
234 CODA_NC_DEBUG(CODA_NC_ENTER,
235 myprintf(("long name enter %s\n",name));)
236 coda_nc_stat.long_name_enters++; /* record stats */
240 hash = CODA_NC_HASH(name, namelen, dcp);
241 cncp = coda_nc_find(dcp, name, namelen, cred, hash);
242 if (cncp != (struct coda_cache *) 0) {
243 coda_nc_stat.dbl_enters++; /* duplicate entry */
247 coda_nc_stat.enters++; /* record the enters statistic */
249 /* Grab the next element in the lru chain */
250 cncp = CODA_NC_LRUGET(coda_nc_lru);
252 CODA_NC_LRUREM(cncp); /* remove it from the lists */
254 if (CODA_NC_VALID(cncp)) {
255 /* Seems really ugly, but we have to decrement the appropriate
256 hash bucket length here, so we have to find the hash bucket
258 coda_nc_hash[CODA_NC_HASH(cncp->name, cncp->namelen, cncp->dcp)].length--;
260 coda_nc_stat.lru_rm++; /* zapped a valid entry */
261 CODA_NC_HSHREM(cncp);
262 vrele(CTOV(cncp->dcp));
263 vrele(CTOV(cncp->cp));
268 * Put a hold on the current vnodes and fill in the cache entry.
274 cncp->namelen = namelen;
275 cncp->cred = crhold(cred);
277 bcopy(name, cncp->name, (unsigned)namelen);
279 /* Insert into the lru and hash chains. */
281 CODA_NC_LRUINS(cncp, &coda_nc_lru);
282 CODA_NC_HSHINS(cncp, &coda_nc_hash[hash]);
283 coda_nc_hash[hash].length++; /* Used for tuning */
285 CODA_NC_DEBUG(CODA_NC_PRINTCODA_NC, print_coda_nc(); )
289 * Find the (dir cnode, name) pair in the cache, if it's cred
290 * matches the input, return it, otherwise return 0
293 coda_nc_lookup(struct cnode *dcp, const char *name, int namelen,
297 struct coda_cache *cncp;
299 if (coda_nc_use == 0) /* Cache is off */
300 return((struct cnode *) 0);
302 if (namelen > CODA_NC_NAMELEN) {
303 CODA_NC_DEBUG(CODA_NC_LOOKUP,
304 myprintf(("long name lookup %s\n",name));)
305 coda_nc_stat.long_name_lookups++; /* record stats */
306 return((struct cnode *) 0);
309 /* Use the hash function to locate the starting point,
310 then the search routine to go down the list looking for
314 hash = CODA_NC_HASH(name, namelen, dcp);
315 cncp = coda_nc_find(dcp, name, namelen, cred, hash);
316 if (cncp == (struct coda_cache *) 0) {
317 coda_nc_stat.misses++; /* record miss */
318 return((struct cnode *) 0);
323 /* put this entry at the end of the LRU */
324 CODA_NC_LRUREM(cncp);
325 CODA_NC_LRUINS(cncp, &coda_nc_lru);
327 /* move it to the front of the hash chain */
328 /* don't need to change the hash bucket length */
329 CODA_NC_HSHREM(cncp);
330 CODA_NC_HSHINS(cncp, &coda_nc_hash[hash]);
332 CODA_NC_DEBUG(CODA_NC_LOOKUP,
333 printf("lookup: dcp %p, name %s, cred %p = cp %p\n",
334 dcp, name, cred, cncp->cp); )
340 coda_nc_remove(struct coda_cache *cncp, enum dc_status dcstat)
343 * remove an entry -- vrele(cncp->dcp, cp), crfree(cred),
344 * remove it from it's hash chain, and
345 * place it at the head of the lru list.
347 CODA_NC_DEBUG(CODA_NC_REMOVE,
348 myprintf(("coda_nc_remove %s from parent %lx.%lx.%lx\n",
349 cncp->name, (cncp->dcp)->c_fid.Volume,
350 (cncp->dcp)->c_fid.Vnode, (cncp->dcp)->c_fid.Unique));)
352 CODA_NC_HSHREM(cncp);
354 CODA_NC_HSHNUL(cncp); /* have it be a null chain */
355 if ((dcstat == IS_DOWNCALL) && (CTOV(cncp->dcp)->v_usecount == 1)) {
356 cncp->dcp->c_flags |= C_PURGING;
358 vrele(CTOV(cncp->dcp));
360 if ((dcstat == IS_DOWNCALL) && (CTOV(cncp->cp)->v_usecount == 1)) {
361 cncp->cp->c_flags |= C_PURGING;
363 vrele(CTOV(cncp->cp));
366 bzero(DATA_PART(cncp),DATA_SIZE);
368 /* Put the null entry just after the least-recently-used entry */
369 /* LRU_TOP adjusts the pointer to point to the top of the structure. */
370 CODA_NC_LRUREM(cncp);
371 CODA_NC_LRUINS(cncp, LRU_TOP(coda_nc_lru.lru_prev));
375 * Remove all entries with a parent which has the input fid.
378 coda_nc_zapParentfid(ViceFid *fid, enum dc_status dcstat)
380 /* To get to a specific fid, we might either have another hashing
381 function or do a sequential search through the cache for the
382 appropriate entries. The later may be acceptable since I don't
383 think callbacks or whatever Case 1 covers are frequent occurences.
385 struct coda_cache *cncp, *ncncp;
388 if (coda_nc_use == 0) /* Cache is off */
391 CODA_NC_DEBUG(CODA_NC_ZAPPFID,
392 myprintf(("ZapParent: fid 0x%lx, 0x%lx, 0x%lx \n",
393 fid->Volume, fid->Vnode, fid->Unique)); )
395 coda_nc_stat.zapPfids++;
397 for (i = 0; i < coda_nc_hashsize; i++) {
400 * Need to save the hash_next pointer in case we remove the
401 * entry. remove causes hash_next to point to itself.
404 for (cncp = coda_nc_hash[i].hash_next;
405 cncp != (struct coda_cache *)&coda_nc_hash[i];
407 ncncp = cncp->hash_next;
408 if ((cncp->dcp->c_fid.Volume == fid->Volume) &&
409 (cncp->dcp->c_fid.Vnode == fid->Vnode) &&
410 (cncp->dcp->c_fid.Unique == fid->Unique)) {
411 coda_nc_hash[i].length--; /* Used for tuning */
412 coda_nc_remove(cncp, dcstat);
420 * Remove all entries which have the same fid as the input
423 coda_nc_zapfid(ViceFid *fid, enum dc_status dcstat)
425 /* See comment for zapParentfid. This routine will be used
426 if attributes are being cached.
428 struct coda_cache *cncp, *ncncp;
431 if (coda_nc_use == 0) /* Cache is off */
434 CODA_NC_DEBUG(CODA_NC_ZAPFID,
435 myprintf(("Zapfid: fid 0x%lx, 0x%lx, 0x%lx \n",
436 fid->Volume, fid->Vnode, fid->Unique)); )
438 coda_nc_stat.zapFids++;
440 for (i = 0; i < coda_nc_hashsize; i++) {
441 for (cncp = coda_nc_hash[i].hash_next;
442 cncp != (struct coda_cache *)&coda_nc_hash[i];
444 ncncp = cncp->hash_next;
445 if ((cncp->cp->c_fid.Volume == fid->Volume) &&
446 (cncp->cp->c_fid.Vnode == fid->Vnode) &&
447 (cncp->cp->c_fid.Unique == fid->Unique)) {
448 coda_nc_hash[i].length--; /* Used for tuning */
449 coda_nc_remove(cncp, dcstat);
456 * Remove all entries which match the fid and the cred
459 coda_nc_zapvnode(ViceFid *fid, struct ucred *cred, enum dc_status dcstat)
461 /* See comment for zapfid. I don't think that one would ever
462 want to zap a file with a specific cred from the kernel.
463 We'll leave this one unimplemented.
465 if (coda_nc_use == 0) /* Cache is off */
468 CODA_NC_DEBUG(CODA_NC_ZAPVNODE,
469 myprintf(("Zapvnode: fid 0x%lx, 0x%lx, 0x%lx cred %p\n",
470 fid->Volume, fid->Vnode, fid->Unique, cred)); )
475 * Remove all entries which have the (dir vnode, name) pair
478 coda_nc_zapfile(struct cnode *dcp, const char *name, int namelen)
480 /* use the hash function to locate the file, then zap all
481 entries of it regardless of the cred.
483 struct coda_cache *cncp;
486 if (coda_nc_use == 0) /* Cache is off */
489 CODA_NC_DEBUG(CODA_NC_ZAPFILE,
490 myprintf(("Zapfile: dcp %p name %s \n",
493 if (namelen > CODA_NC_NAMELEN) {
494 coda_nc_stat.long_remove++; /* record stats */
498 coda_nc_stat.zapFile++;
500 hash = CODA_NC_HASH(name, namelen, dcp);
501 cncp = coda_nc_find(dcp, name, namelen, 0, hash);
504 coda_nc_hash[hash].length--; /* Used for tuning */
506 coda_nc_remove(cncp, NOT_DOWNCALL);
507 cncp = coda_nc_find(dcp, name, namelen, 0, hash);
512 * Remove all the entries for a particular user. Used when tokens expire.
513 * A user is determined by his/her effective user id (id_uid).
516 coda_nc_purge_user(vuid_t uid, enum dc_status dcstat)
519 * I think the best approach is to go through the entire cache
520 * via HASH or whatever and zap all entries which match the
521 * input cred. Or just flush the whole cache. It might be
522 * best to go through on basis of LRU since cache will almost
523 * always be full and LRU is more straightforward.
526 struct coda_cache *cncp, *ncncp;
529 if (coda_nc_use == 0) /* Cache is off */
532 CODA_NC_DEBUG(CODA_NC_PURGEUSER,
533 myprintf(("ZapDude: uid %x\n", uid)); )
534 coda_nc_stat.zapUsers++;
536 for (cncp = CODA_NC_LRUGET(coda_nc_lru);
537 cncp != (struct coda_cache *)(&coda_nc_lru);
539 ncncp = CODA_NC_LRUGET(*cncp);
541 if ((CODA_NC_VALID(cncp)) &&
542 ((cncp->cred)->cr_uid == uid)) {
543 /* Seems really ugly, but we have to decrement the appropriate
544 hash bucket length here, so we have to find the hash bucket
546 hash = CODA_NC_HASH(cncp->name, cncp->namelen, cncp->dcp);
547 coda_nc_hash[hash].length--; /* For performance tuning */
549 coda_nc_remove(cncp, dcstat);
555 * Flush the entire name cache. In response to a flush of the Venus cache.
558 coda_nc_flush(enum dc_status dcstat)
560 /* One option is to deallocate the current name cache and
561 call init to start again. Or just deallocate, then rebuild.
562 Or again, we could just go through the array and zero the
567 * Go through the whole lru chain and kill everything as we go.
568 * I don't use remove since that would rebuild the lru chain
569 * as it went and that seemed unneccesary.
571 struct coda_cache *cncp;
574 if (coda_nc_use == 0) /* Cache is off */
577 coda_nc_stat.Flushes++;
579 for (cncp = CODA_NC_LRUGET(coda_nc_lru);
580 cncp != (struct coda_cache *)&coda_nc_lru;
581 cncp = CODA_NC_LRUGET(*cncp)) {
582 if (CODA_NC_VALID(cncp)) {
584 CODA_NC_HSHREM(cncp); /* only zero valid nodes */
585 CODA_NC_HSHNUL(cncp);
586 if ((dcstat == IS_DOWNCALL)
587 && (CTOV(cncp->dcp)->v_usecount == 1))
589 cncp->dcp->c_flags |= C_PURGING;
591 vrele(CTOV(cncp->dcp));
593 if (CTOV(cncp->cp)->v_flag & VTEXT) {
594 if (coda_vmflush(cncp->cp))
595 CODADEBUG(CODA_FLUSH,
596 myprintf(("coda_nc_flush: (%lx.%lx.%lx) busy\n", cncp->cp->c_fid.Volume, cncp->cp->c_fid.Vnode, cncp->cp->c_fid.Unique)); )
599 if ((dcstat == IS_DOWNCALL)
600 && (CTOV(cncp->cp)->v_usecount == 1))
602 cncp->cp->c_flags |= C_PURGING;
604 vrele(CTOV(cncp->cp));
607 bzero(DATA_PART(cncp),DATA_SIZE);
611 for (i = 0; i < coda_nc_hashsize; i++)
612 coda_nc_hash[i].length = 0;
620 * This routine should print out all the hash chains to the console.
626 struct coda_cache *cncp;
628 for (hash = 0; hash < coda_nc_hashsize; hash++) {
629 myprintf(("\nhash %d\n",hash));
631 for (cncp = coda_nc_hash[hash].hash_next;
632 cncp != (struct coda_cache *)&coda_nc_hash[hash];
633 cncp = cncp->hash_next) {
634 myprintf(("cp %p dcp %p cred %p name %s\n",
636 cncp->cred, cncp->name));
642 coda_nc_gather_stats(void)
644 int i, max = 0, sum = 0, temp, zeros = 0, ave, n;
646 for (i = 0; i < coda_nc_hashsize; i++) {
647 if (coda_nc_hash[i].length) {
648 sum += coda_nc_hash[i].length;
653 if (coda_nc_hash[i].length > max)
654 max = coda_nc_hash[i].length;
658 * When computing the Arithmetic mean, only count slots which
659 * are not empty in the distribution.
661 coda_nc_stat.Sum_bucket_len = sum;
662 coda_nc_stat.Num_zero_len = zeros;
663 coda_nc_stat.Max_bucket_len = max;
665 if ((n = coda_nc_hashsize - zeros) > 0)
671 for (i = 0; i < coda_nc_hashsize; i++) {
672 if (coda_nc_hash[i].length) {
673 temp = coda_nc_hash[i].length - ave;
677 coda_nc_stat.Sum2_bucket_len = sum;
681 * The purpose of this routine is to allow the hash and cache sizes to be
682 * changed dynamically. This should only be used in controlled environments,
683 * it makes no effort to lock other users from accessing the cache while it
684 * is in an improper state (except by turning the cache off).
687 coda_nc_resize(int hashsize, int heapsize, enum dc_status dcstat)
689 if ((hashsize % 2) || (heapsize % 2)) { /* Illegal hash or cache sizes */
693 coda_nc_use = 0; /* Turn the cache off */
695 coda_nc_flush(dcstat); /* free any cnodes in the cache */
697 /* WARNING: free must happen *before* size is reset */
698 CODA_FREE(coda_nc_heap,TOTAL_CACHE_SIZE);
699 CODA_FREE(coda_nc_hash,TOTAL_HASH_SIZE);
701 coda_nc_hashsize = hashsize;
702 coda_nc_size = heapsize;
704 coda_nc_init(); /* Set up a cache with the new size */
706 coda_nc_use = 1; /* Turn the cache back on */
711 char coda_nc_name_buf[CODA_MAXNAMLEN+1];
714 coda_nc_name(struct cnode *cp)
716 struct coda_cache *cncp, *ncncp;
719 if (coda_nc_use == 0) /* Cache is off */
722 for (i = 0; i < coda_nc_hashsize; i++) {
723 for (cncp = coda_nc_hash[i].hash_next;
724 cncp != (struct coda_cache *)&coda_nc_hash[i];
726 ncncp = cncp->hash_next;
727 if (cncp->cp == cp) {
728 bcopy(cncp->name, coda_nc_name_buf, cncp->namelen);
729 coda_nc_name_buf[cncp->namelen] = 0;
730 printf(" is %s (%p,%p)@%p",
731 coda_nc_name_buf, cncp->cp, cncp->dcp, cncp);