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
10 #include <afsconfig.h>
11 #include "afs/param.h"
14 #include "afs/sysincludes.h" /*Standard vendor system headers */
15 #include "afsincludes.h" /*AFS-based standard headers */
18 #include "afs/afs_stats.h"
19 #include "afs/afs_osidnlc.h"
22 * also cache failed lookups.
23 * look into interactions of dnlc and readdir.
24 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
25 * the actual name itself.
26 * precompute a key and stuff for \sys, and combine the HandleAtName function with
27 * this, since we're looking at the name anyway.
30 struct afs_lock afs_xdnlc;
31 extern struct afs_lock afs_xvcache;
33 dnlcstats_t dnlcstats;
36 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
37 struct nc *ncfreelist = NULL;
38 static struct nc nameCache[NCSIZE];
39 struct nc *nameHash[NHSIZE];
40 /* Hash table invariants:
41 * 1. If nameHash[i] is NULL, list is empty
42 * 2. A single element in a hash bucket has itself as prev and next.
45 typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
46 ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
47 osi_dnlc_purgevpT, osi_dnlc_purgeT
57 struct dt dnlctracetable[256];
60 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
62 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
64 #if defined(AFS_FBSD80_ENV) && !defined(UKERNEL)
65 #define ma_critical_enter critical_enter
66 #define ma_critical_exit critical_exit
68 #define ma_critical_enter() {}
69 #define ma_critical_exit() {}
75 static unsigned int nameptr = 0; /* next bucket to pull something from */
81 ncfreelist = tnc->next;
85 for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
86 if (nameptr >= NHSIZE)
88 if (nameHash[nameptr])
92 TRACE(ScavengeEntryT, nameptr);
93 tnc = nameHash[nameptr];
94 if (!tnc) /* May want to consider changing this to return 0 */
95 osi_Panic("null tnc in GetMeAnEntry");
97 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
98 nameHash[nameptr] = NULL;
102 tnc = tnc->prev; /* grab oldest one in this bucket */
103 /* remove it from list */
104 tnc->next->prev = tnc->prev;
105 tnc->prev->next = tnc->next;
111 InsertEntry(struct nc *tnc)
114 key = tnc->key & (NHSIZE - 1);
116 TRACE(InsertEntryT, key);
117 if (!nameHash[key]) {
119 tnc->next = tnc->prev = tnc;
121 tnc->next = nameHash[key];
122 tnc->prev = tnc->next->prev;
123 tnc->next->prev = tnc;
124 tnc->prev->next = tnc;
131 osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
135 unsigned int key, skey;
142 TRACE(osi_dnlc_enterT, 0);
143 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
144 if (ts - aname >= AFSNCNAMESIZE) {
147 skey = key & (NHSIZE - 1);
151 ObtainWriteLock(&afs_xdnlc, 222);
153 /* Only cache entries from the latest version of the directory */
154 if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
155 ReleaseWriteLock(&afs_xdnlc);
160 * Make sure each directory entry gets cached no more than once.
162 for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
163 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
164 /* duplicate entry */
166 } else if (tnc->next == nameHash[skey]) { /* end of list */
169 } else if (safety > NCSIZE) {
170 afs_warn("DNLC cycle");
172 ReleaseWriteLock(&afs_xdnlc);
179 tnc = GetMeAnEntry();
184 memcpy((char *)tnc->name, aname, ts - aname + 1); /* include the NULL */
191 ReleaseWriteLock(&afs_xdnlc);
198 osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
202 unsigned int key, skey;
204 struct nc *tnc, *tnc1 = 0;
206 #ifdef AFS_DARWIN80_ENV
217 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
218 if (ts - aname >= AFSNCNAMESIZE) {
222 skey = key & (NHSIZE - 1);
224 TRACE(osi_dnlc_lookupT, skey);
227 ObtainReadLock(&afs_xvcache);
228 ObtainReadLock(&afs_xdnlc);
230 for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
231 tnc = tnc->next, safety++) {
232 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
233 && (!strcmp((char *)tnc->name, aname))) {
237 } else if (tnc->next == nameHash[skey]) { /* end of list */
239 } else if (safety > NCSIZE) {
240 afs_warn("DNLC cycle");
242 ReleaseReadLock(&afs_xdnlc);
243 ReleaseReadLock(&afs_xvcache);
250 LRUme = 0; /* (tnc != nameHash[skey]); */
251 ReleaseReadLock(&afs_xdnlc);
254 ReleaseReadLock(&afs_xvcache);
257 if ((tvc->f.states & CVInit)
258 #ifdef AFS_DARWIN80_ENV
259 ||(tvc->f.states & CDeadVnode)
263 ReleaseReadLock(&afs_xvcache);
265 osi_dnlc_remove(adp, aname, tvc);
270 VN_HOLD((vnode_t *) tvc);
272 #ifdef AFS_DARWIN80_ENV
274 if (vnode_get(tvp)) {
275 ReleaseReadLock(&afs_xvcache);
277 osi_dnlc_remove(adp, aname, tvc);
281 if (vnode_ref(tvp)) {
282 ReleaseReadLock(&afs_xvcache);
287 osi_dnlc_remove(adp, aname, tvc);
292 #ifdef AFS_FBSD50_ENV
293 /* can't sleep in a critical section */
299 #endif /* AFS_FBSD80_ENV */
302 ReleaseReadLock(&afs_xvcache);
306 * XX If LRUme ever is non-zero change the if statement around because
307 * aix's cc with optimizer on won't necessarily check things in order XX
309 if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
310 /* don't block to do this */
311 /* tnc might have been moved during race condition, */
312 /* but it's always in a legit hash chain when a lock is granted,
313 * or else it's on the freelist so prev == NULL,
314 * so at worst this is redundant */
315 /* Now that we've got it held, and a lock on the dnlc, we
316 * should check to be sure that there was no race, and
317 * bail out if there was. */
319 /* special case for only two elements on list - relative ordering
321 if (tnc->prev != tnc->next) {
322 /* remove from old location */
323 tnc->prev->next = tnc->next;
324 tnc->next->prev = tnc->prev;
325 /* insert into new location */
326 tnc->next = nameHash[skey];
327 tnc->prev = tnc->next->prev;
328 tnc->next->prev = tnc;
329 tnc->prev->next = tnc;
331 nameHash[skey] = tnc;
333 ReleaseWriteLock(&afs_xdnlc);
344 RemoveEntry(struct nc *tnc, unsigned int key)
346 if (!tnc->prev) /* things on freelist always have null prev ptrs */
347 osi_Panic("bogus free list");
349 TRACE(RemoveEntryT, key);
350 if (tnc == tnc->next) { /* only one in list */
351 nameHash[key] = NULL;
353 if (tnc == nameHash[key])
354 nameHash[key] = tnc->next;
355 tnc->prev->next = tnc->next;
356 tnc->next->prev = tnc->prev;
359 tnc->prev = NULL; /* everything not in hash table has 0 prev */
360 tnc->key = 0; /* just for safety's sake */
365 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
367 unsigned int key, skey;
374 TRACE(osi_dnlc_removeT, skey);
375 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
376 if (ts - aname >= AFSNCNAMESIZE) {
379 skey = key & (NHSIZE - 1);
380 TRACE(osi_dnlc_removeT, skey);
382 ObtainReadLock(&afs_xdnlc);
384 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
385 if ((tnc->dirp == adp) && (tnc->key == key)
386 && (!strcmp((char *)tnc->name, aname))) {
387 tnc->dirp = NULL; /* now it won't match anything */
389 } else if (tnc->next == nameHash[skey]) { /* end of list */
394 ReleaseReadLock(&afs_xdnlc);
399 /* there is a little race condition here, but it's relatively
400 * harmless. At worst, I wind up removing a mapping that I just
402 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
403 return 0; /* no big deal, tnc will get recycled eventually */
405 RemoveEntry(tnc, skey);
406 tnc->next = ncfreelist;
408 ReleaseWriteLock(&afs_xdnlc);
414 * Remove anything pertaining to this directory. I can invalidate
415 * things without the lock, since I am just looking through the array,
416 * but to move things off the lists or into the freelist, I need the
419 * \param adp vcache entry for the directory to be purged.
423 osi_dnlc_purgedp(struct vcache *adp)
428 #ifdef AFS_DARWIN_ENV
429 if (!(adp->f.states & (CVInit | CVFlushed
430 #ifdef AFS_DARWIN80_ENV
434 cache_purge(AFSTOV(adp));
441 TRACE(osi_dnlc_purgedpT, 0);
442 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
444 for (i = 0; i < NCSIZE; i++) {
445 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
446 nameCache[i].dirp = nameCache[i].vp = NULL;
447 if (writelocked && nameCache[i].prev) {
448 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
449 nameCache[i].next = ncfreelist;
450 ncfreelist = &nameCache[i];
455 ReleaseWriteLock(&afs_xdnlc);
461 * Remove anything pertaining to this file
463 * \param File vcache entry.
467 osi_dnlc_purgevp(struct vcache *avc)
472 #ifdef AFS_DARWIN_ENV
473 if (!(avc->f.states & (CVInit | CVFlushed
474 #ifdef AFS_DARWIN80_ENV
478 cache_purge(AFSTOV(avc));
485 TRACE(osi_dnlc_purgevpT, 0);
486 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
488 for (i = 0; i < NCSIZE; i++) {
489 if ((nameCache[i].vp == avc)) {
490 nameCache[i].dirp = nameCache[i].vp = NULL;
491 /* can't simply break; because of hard links -- might be two */
492 /* different entries with same vnode */
493 if (writelocked && nameCache[i].prev) {
494 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
495 nameCache[i].next = ncfreelist;
496 ncfreelist = &nameCache[i];
501 ReleaseWriteLock(&afs_xdnlc);
506 /* remove everything */
513 TRACE(osi_dnlc_purgeT, 0);
514 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) { /* couldn't get lock */
515 for (i = 0; i < NCSIZE; i++)
516 nameCache[i].dirp = nameCache[i].vp = NULL;
517 } else { /* did get the lock */
519 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
520 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
521 for (i = 0; i < NCSIZE; i++) {
522 nameCache[i].next = ncfreelist;
523 ncfreelist = &nameCache[i];
525 ReleaseWriteLock(&afs_xdnlc);
531 /* remove everything referencing a specific volume */
533 osi_dnlc_purgevol(struct VenusFid *fidp)
536 dnlcstats.purgevols++;
547 Lock_Init(&afs_xdnlc);
548 memset(&dnlcstats, 0, sizeof(dnlcstats));
549 memset(dnlctracetable, 0, sizeof(dnlctracetable));
551 ObtainWriteLock(&afs_xdnlc, 223);
553 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
554 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
555 for (i = 0; i < NCSIZE; i++) {
556 nameCache[i].next = ncfreelist;
557 ncfreelist = &nameCache[i];
559 ReleaseWriteLock(&afs_xdnlc);
565 osi_dnlc_shutdown(void)