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"
16 #include "afs/sysincludes.h" /*Standard vendor system headers */
17 #include "afsincludes.h" /*AFS-based standard headers */
20 #include "afs/afs_stats.h"
21 #include "afs/afs_osidnlc.h"
24 * also cache failed lookups.
25 * look into interactions of dnlc and readdir.
26 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
27 * the actual name itself.
28 * precompute a key and stuff for \sys, and combine the HandleAtName function with
29 * this, since we're looking at the name anyway.
32 struct afs_lock afs_xdnlc;
33 extern struct afs_lock afs_xvcache;
35 dnlcstats_t dnlcstats;
38 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
39 struct nc *ncfreelist = NULL;
40 static struct nc nameCache[NCSIZE];
41 struct nc *nameHash[NHSIZE];
42 /* Hash table invariants:
43 * 1. If nameHash[i] is NULL, list is empty
44 * 2. A single element in a hash bucket has itself as prev and next.
47 typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
48 ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
49 osi_dnlc_purgevpT, osi_dnlc_purgeT
59 struct dt dnlctracetable[256];
62 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
64 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
66 #if defined(AFS_FBSD80_ENV) && !defined(UKERNEL)
67 #define ma_critical_enter critical_enter
68 #define ma_critical_exit critical_exit
70 #define ma_critical_enter() {}
71 #define ma_critical_exit() {}
77 static unsigned int nameptr = 0; /* next bucket to pull something from */
83 ncfreelist = tnc->next;
87 for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
88 if (nameptr >= NHSIZE)
90 if (nameHash[nameptr])
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->states & CStatd) || !hsame(*avno, adp->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)
204 unsigned int key, skey;
206 struct nc *tnc, *tnc1 = 0;
208 #ifdef AFS_DARWIN80_ENV
219 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
220 if (ts - aname >= AFSNCNAMESIZE) {
224 skey = key & (NHSIZE - 1);
226 TRACE(osi_dnlc_lookupT, skey);
229 ObtainReadLock(&afs_xvcache);
230 ObtainReadLock(&afs_xdnlc);
232 for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
233 tnc = tnc->next, safety++) {
234 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
235 && (!strcmp((char *)tnc->name, aname))) {
239 } else if (tnc->next == nameHash[skey]) { /* end of list */
241 } else if (safety > NCSIZE) {
242 afs_warn("DNLC cycle");
244 ReleaseReadLock(&afs_xdnlc);
245 ReleaseReadLock(&afs_xvcache);
252 LRUme = 0; /* (tnc != nameHash[skey]); */
253 ReleaseReadLock(&afs_xdnlc);
256 ReleaseReadLock(&afs_xvcache);
259 if ((tvc->states & CVInit)
260 #ifdef AFS_DARWIN80_ENV
261 ||(tvc->states & CDeadVnode)
265 ReleaseReadLock(&afs_xvcache);
267 osi_dnlc_remove(adp, aname, tvc);
272 VN_HOLD((vnode_t *) tvc);
274 #ifdef AFS_DARWIN80_ENV
276 if (vnode_get(tvp)) {
277 ReleaseReadLock(&afs_xvcache);
279 osi_dnlc_remove(adp, aname, tvc);
283 if (vnode_ref(tvp)) {
284 ReleaseReadLock(&afs_xvcache);
289 osi_dnlc_remove(adp, aname, tvc);
294 #ifdef AFS_FBSD50_ENV
295 /* can't sleep in a critical section */
301 #endif /* AFS_FBSD80_ENV */
304 ReleaseReadLock(&afs_xvcache);
308 * XX If LRUme ever is non-zero change the if statement around because
309 * aix's cc with optimizer on won't necessarily check things in order XX
311 if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
312 /* don't block to do this */
313 /* tnc might have been moved during race condition, */
314 /* but it's always in a legit hash chain when a lock is granted,
315 * or else it's on the freelist so prev == NULL,
316 * so at worst this is redundant */
317 /* Now that we've got it held, and a lock on the dnlc, we
318 * should check to be sure that there was no race, and
319 * bail out if there was. */
321 /* special case for only two elements on list - relative ordering
323 if (tnc->prev != tnc->next) {
324 /* remove from old location */
325 tnc->prev->next = tnc->next;
326 tnc->next->prev = tnc->prev;
327 /* insert into new location */
328 tnc->next = nameHash[skey];
329 tnc->prev = tnc->next->prev;
330 tnc->next->prev = tnc;
331 tnc->prev->next = tnc;
333 nameHash[skey] = tnc;
335 ReleaseWriteLock(&afs_xdnlc);
346 RemoveEntry(struct nc *tnc, unsigned int key)
348 if (!tnc->prev) /* things on freelist always have null prev ptrs */
349 osi_Panic("bogus free list");
351 TRACE(RemoveEntryT, key);
352 if (tnc == tnc->next) { /* only one in list */
353 nameHash[key] = NULL;
355 if (tnc == nameHash[key])
356 nameHash[key] = tnc->next;
357 tnc->prev->next = tnc->next;
358 tnc->next->prev = tnc->prev;
361 tnc->prev = NULL; /* everything not in hash table has 0 prev */
362 tnc->key = 0; /* just for safety's sake */
367 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
369 unsigned int key, skey;
376 TRACE(osi_dnlc_removeT, skey);
377 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
378 if (ts - aname >= AFSNCNAMESIZE) {
381 skey = key & (NHSIZE - 1);
382 TRACE(osi_dnlc_removeT, skey);
384 ObtainReadLock(&afs_xdnlc);
386 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
387 if ((tnc->dirp == adp) && (tnc->key == key)
388 && (!strcmp((char *)tnc->name, aname))) {
389 tnc->dirp = NULL; /* now it won't match anything */
391 } else if (tnc->next == nameHash[skey]) { /* end of list */
396 ReleaseReadLock(&afs_xdnlc);
401 /* there is a little race condition here, but it's relatively
402 * harmless. At worst, I wind up removing a mapping that I just
404 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
405 return 0; /* no big deal, tnc will get recycled eventually */
407 RemoveEntry(tnc, skey);
408 tnc->next = ncfreelist;
410 ReleaseWriteLock(&afs_xdnlc);
416 * Remove anything pertaining to this directory. I can invalidate
417 * things without the lock, since I am just looking through the array,
418 * but to move things off the lists or into the freelist, I need the
421 * \param adp vcache entry for the directory to be purged.
425 osi_dnlc_purgedp(struct vcache *adp)
430 #ifdef AFS_DARWIN_ENV
431 if (!(adp->states & (CVInit | CVFlushed
432 #ifdef AFS_DARWIN80_ENV
436 cache_purge(AFSTOV(adp));
443 TRACE(osi_dnlc_purgedpT, 0);
444 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
446 for (i = 0; i < NCSIZE; i++) {
447 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
448 nameCache[i].dirp = nameCache[i].vp = NULL;
449 if (writelocked && nameCache[i].prev) {
450 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
451 nameCache[i].next = ncfreelist;
452 ncfreelist = &nameCache[i];
457 ReleaseWriteLock(&afs_xdnlc);
463 * Remove anything pertaining to this file
465 * \param File vcache entry.
469 osi_dnlc_purgevp(struct vcache *avc)
474 #ifdef AFS_DARWIN_ENV
475 if (!(avc->states & (CVInit | CVFlushed
476 #ifdef AFS_DARWIN80_ENV
480 cache_purge(AFSTOV(avc));
487 TRACE(osi_dnlc_purgevpT, 0);
488 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
490 for (i = 0; i < NCSIZE; i++) {
491 if ((nameCache[i].vp == avc)) {
492 nameCache[i].dirp = nameCache[i].vp = NULL;
493 /* can't simply break; because of hard links -- might be two */
494 /* different entries with same vnode */
495 if (writelocked && nameCache[i].prev) {
496 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
497 nameCache[i].next = ncfreelist;
498 ncfreelist = &nameCache[i];
503 ReleaseWriteLock(&afs_xdnlc);
508 /* remove everything */
515 TRACE(osi_dnlc_purgeT, 0);
516 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) { /* couldn't get lock */
517 for (i = 0; i < NCSIZE; i++)
518 nameCache[i].dirp = nameCache[i].vp = NULL;
519 } else { /* did get the lock */
521 memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
522 memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
523 for (i = 0; i < NCSIZE; i++) {
524 nameCache[i].next = ncfreelist;
525 ncfreelist = &nameCache[i];
527 ReleaseWriteLock(&afs_xdnlc);
533 /* remove everything referencing a specific volume */
535 osi_dnlc_purgevol(struct VenusFid *fidp)
538 dnlcstats.purgevols++;
549 Lock_Init(&afs_xdnlc);
550 memset((char *)&dnlcstats, 0, sizeof(dnlcstats));
551 memset((char *)dnlctracetable, 0, sizeof(dnlctracetable));
553 ObtainWriteLock(&afs_xdnlc, 223);
555 memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
556 memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
557 for (i = 0; i < NCSIZE; i++) {
558 nameCache[i].next = ncfreelist;
559 ncfreelist = &nameCache[i];
561 ReleaseWriteLock(&afs_xdnlc);
567 osi_dnlc_shutdown(void)