2 * Copyright 2000, International Business Machines Corporation and others.
5 * This software has been released under the terms of the IBM Public
6 * License. For details, see the LICENSE file in the top-level source
7 * directory or online at http://www.openafs.org/dl/license10.html
11 * OSI Directory Name Lookup Cache
13 * Keep a local cache of lookup results to avoid needing to examine the disk
14 * cache, for frequently accessed names.
17 #include <afsconfig.h>
18 #include "afs/param.h"
21 #include "afs/sysincludes.h" /*Standard vendor system headers */
22 #include "afsincludes.h" /*AFS-based standard headers */
25 #include "afs/afs_stats.h"
26 #include "afs/afs_osidnlc.h"
29 * also cache failed lookups.
30 * look into interactions of dnlc and readdir.
31 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
32 * the actual name itself.
33 * precompute a key and stuff for \sys, and combine the HandleAtName function with
34 * this, since we're looking at the name anyway.
37 struct afs_lock afs_xdnlc;
38 extern struct afs_lock afs_xvcache;
40 dnlcstats_t dnlcstats;
43 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
44 struct nc *ncfreelist = NULL;
45 static struct nc nameCache[NCSIZE];
46 struct nc *nameHash[NHSIZE];
47 /* Hash table invariants:
48 * 1. If nameHash[i] is NULL, list is empty
49 * 2. A single element in a hash bucket has itself as prev and next.
52 typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
53 ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
54 osi_dnlc_purgevpT, osi_dnlc_purgeT
64 struct dt dnlctracetable[256];
67 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
69 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
74 static unsigned int nameptr = 0; /* next bucket to pull something from */
80 ncfreelist = tnc->next;
84 for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
85 if (nameptr >= NHSIZE)
87 if (nameHash[nameptr])
91 if (nameptr >= NHSIZE)
94 TRACE(ScavengeEntryT, nameptr);
95 tnc = nameHash[nameptr];
96 if (!tnc) /* May want to consider changing this to return 0 */
97 osi_Panic("null tnc in GetMeAnEntry");
99 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
100 nameHash[nameptr] = NULL;
104 tnc = tnc->prev; /* grab oldest one in this bucket */
105 /* remove it from list */
106 tnc->next->prev = tnc->prev;
107 tnc->prev->next = tnc->next;
113 InsertEntry(struct nc *tnc)
116 key = tnc->key & (NHSIZE - 1);
118 TRACE(InsertEntryT, key);
119 if (!nameHash[key]) {
121 tnc->next = tnc->prev = tnc;
123 tnc->next = nameHash[key];
124 tnc->prev = tnc->next->prev;
125 tnc->next->prev = tnc;
126 tnc->prev->next = tnc;
133 osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
137 unsigned int key, skey;
144 TRACE(osi_dnlc_enterT, 0);
145 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
146 if (ts - aname >= AFSNCNAMESIZE) {
149 skey = key & (NHSIZE - 1);
153 ObtainWriteLock(&afs_xdnlc, 222);
155 /* Only cache entries from the latest version of the directory */
156 if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
157 ReleaseWriteLock(&afs_xdnlc);
162 * Make sure each directory entry gets cached no more than once.
164 for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
165 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
166 /* duplicate entry */
168 } else if (tnc->next == nameHash[skey]) { /* end of list */
171 } else if (safety > NCSIZE) {
172 afs_warn("DNLC cycle");
174 ReleaseWriteLock(&afs_xdnlc);
181 tnc = GetMeAnEntry();
186 memcpy((char *)tnc->name, aname, ts - aname + 1); /* include the NULL */
193 ReleaseWriteLock(&afs_xdnlc);
200 osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
203 unsigned int key, skey;
207 #ifdef AFS_DARWIN80_ENV
214 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
215 if (ts - aname >= AFSNCNAMESIZE)
217 skey = key & (NHSIZE - 1);
219 TRACE(osi_dnlc_lookupT, skey);
222 ObtainReadLock(&afs_xvcache);
223 ObtainReadLock(&afs_xdnlc);
225 for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
226 tnc = tnc->next, safety++) {
227 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
228 && (!strcmp((char *)tnc->name, aname))) {
231 } else if (tnc->next == nameHash[skey]) { /* end of list */
233 } else if (safety > NCSIZE) {
234 afs_warn("DNLC cycle");
236 ReleaseReadLock(&afs_xdnlc);
237 ReleaseReadLock(&afs_xvcache);
243 ReleaseReadLock(&afs_xdnlc);
246 ReleaseReadLock(&afs_xvcache);
249 if ((tvc->f.states & CVInit)
250 #ifdef AFS_DARWIN80_ENV
251 ||(tvc->f.states & CDeadVnode)
255 ReleaseReadLock(&afs_xvcache);
257 osi_dnlc_remove(adp, aname, tvc);
260 #if defined(AFS_DARWIN80_ENV)
262 if (vnode_get(tvp)) {
263 ReleaseReadLock(&afs_xvcache);
265 osi_dnlc_remove(adp, aname, tvc);
268 if (vnode_ref(tvp)) {
269 ReleaseReadLock(&afs_xvcache);
274 osi_dnlc_remove(adp, aname, tvc);
280 ReleaseReadLock(&afs_xvcache);
289 RemoveEntry(struct nc *tnc, unsigned int key)
291 if (!tnc->prev) /* things on freelist always have null prev ptrs */
292 osi_Panic("bogus free list");
294 TRACE(RemoveEntryT, key);
295 if (tnc == tnc->next) { /* only one in list */
296 nameHash[key] = NULL;
298 if (tnc == nameHash[key])
299 nameHash[key] = tnc->next;
300 tnc->prev->next = tnc->next;
301 tnc->next->prev = tnc->prev;
304 tnc->prev = NULL; /* everything not in hash table has 0 prev */
305 tnc->key = 0; /* just for safety's sake */
310 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
312 unsigned int key, skey;
319 TRACE(osi_dnlc_removeT, skey);
320 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
321 if (ts - aname >= AFSNCNAMESIZE) {
324 skey = key & (NHSIZE - 1);
325 TRACE(osi_dnlc_removeT, skey);
327 ObtainReadLock(&afs_xdnlc);
329 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
330 if ((tnc->dirp == adp) && (tnc->key == key)
331 && (!strcmp((char *)tnc->name, aname))) {
332 tnc->dirp = NULL; /* now it won't match anything */
334 } else if (tnc->next == nameHash[skey]) { /* end of list */
339 ReleaseReadLock(&afs_xdnlc);
344 /* there is a little race condition here, but it's relatively
345 * harmless. At worst, I wind up removing a mapping that I just
347 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
348 return 0; /* no big deal, tnc will get recycled eventually */
350 RemoveEntry(tnc, skey);
351 tnc->next = ncfreelist;
353 ReleaseWriteLock(&afs_xdnlc);
359 * Remove anything pertaining to this directory. I can invalidate
360 * things without the lock, since I am just looking through the array,
361 * but to move things off the lists or into the freelist, I need the
364 * \param adp vcache entry for the directory to be purged.
368 osi_dnlc_purgedp(struct vcache *adp)
373 #ifdef AFS_DARWIN_ENV
374 if (!(adp->f.states & (CVInit | CVFlushed
375 #ifdef AFS_DARWIN80_ENV
379 cache_purge(AFSTOV(adp));
386 TRACE(osi_dnlc_purgedpT, 0);
387 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
389 for (i = 0; i < NCSIZE; i++) {
390 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
391 nameCache[i].dirp = nameCache[i].vp = NULL;
392 if (writelocked && nameCache[i].prev) {
393 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
394 nameCache[i].next = ncfreelist;
395 ncfreelist = &nameCache[i];
400 ReleaseWriteLock(&afs_xdnlc);
406 * Remove anything pertaining to this file
408 * \param File vcache entry.
412 osi_dnlc_purgevp(struct vcache *avc)
417 #ifdef AFS_DARWIN_ENV
418 if (!(avc->f.states & (CVInit | CVFlushed
419 #ifdef AFS_DARWIN80_ENV
423 cache_purge(AFSTOV(avc));
430 TRACE(osi_dnlc_purgevpT, 0);
431 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
433 for (i = 0; i < NCSIZE; i++) {
434 if (nameCache[i].vp == avc) {
435 nameCache[i].dirp = nameCache[i].vp = NULL;
436 /* can't simply break; because of hard links -- might be two */
437 /* different entries with same vnode */
438 if (writelocked && nameCache[i].prev) {
439 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
440 nameCache[i].next = ncfreelist;
441 ncfreelist = &nameCache[i];
446 ReleaseWriteLock(&afs_xdnlc);
451 /* remove everything */
458 TRACE(osi_dnlc_purgeT, 0);
459 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) { /* couldn't get lock */
460 for (i = 0; i < NCSIZE; i++)
461 nameCache[i].dirp = nameCache[i].vp = NULL;
462 } else { /* did get the lock */
464 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
465 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
466 for (i = 0; i < NCSIZE; i++) {
467 nameCache[i].next = ncfreelist;
468 ncfreelist = &nameCache[i];
470 ReleaseWriteLock(&afs_xdnlc);
476 /* remove everything referencing a specific volume */
478 osi_dnlc_purgevol(struct VenusFid *fidp)
481 dnlcstats.purgevols++;
492 Lock_Init(&afs_xdnlc);
493 memset(&dnlcstats, 0, sizeof(dnlcstats));
494 memset(dnlctracetable, 0, sizeof(dnlctracetable));
496 ObtainWriteLock(&afs_xdnlc, 223);
498 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
499 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
500 for (i = 0; i < NCSIZE; i++) {
501 nameCache[i].next = ncfreelist;
502 ncfreelist = &nameCache[i];
504 ReleaseWriteLock(&afs_xdnlc);
510 osi_dnlc_shutdown(void)