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"
15 #include "../afs/sysincludes.h" /*Standard vendor system headers*/
16 #include "../afs/afsincludes.h" /*AFS-based standard headers*/
18 #include "../afs/lock.h"
19 #include "../afs/afs_stats.h"
20 #include "../afs/afs_osidnlc.h"
23 * also cache failed lookups.
24 * look into interactions of dnlc and readdir.
25 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
26 * the actual name itself.
27 * precompute a key and stuff for @sys, and combine the HandleAtName function with
28 * this, since we're looking at the name anyway.
31 struct afs_lock afs_xdnlc;
32 extern struct afs_lock afs_xvcache;
34 dnlcstats_t dnlcstats;
37 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
38 struct nc *ncfreelist = (struct nc *)0;
39 static struct nc nameCache[NCSIZE];
40 struct nc *nameHash[NHSIZE];
41 /* Hash table invariants:
42 * 1. If nameHash[i] is NULL, list is empty
43 * 2. A single element in a hash bucket has itself as prev and next.
46 typedef enum {osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT, ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT, osi_dnlc_purgevpT, osi_dnlc_purgeT } traceevt;
55 struct dt dnlctracetable[256];
58 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
60 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
62 static struct nc * GetMeAnEntry() {
63 static unsigned int nameptr = 0; /* next bucket to pull something from */
69 ncfreelist = tnc->next;
73 for (j=0; j<NHSIZE+2; j++, nameptr++) {
74 if (nameptr >= NHSIZE)
76 if (nameHash[nameptr])
80 TRACE(ScavengeEntryT, nameptr);
81 tnc = nameHash[nameptr];
82 if (!tnc) /* May want to consider changing this to return 0 */
83 osi_Panic("null tnc in GetMeAnEntry");
85 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
86 nameHash[nameptr] = (struct nc *) 0;
90 tnc = tnc->prev; /* grab oldest one in this bucket */
91 /* remove it from list */
92 tnc->next->prev = tnc->prev;
93 tnc->prev->next = tnc->next;
98 static void InsertEntry(tnc)
102 key = tnc->key & (NHSIZE -1);
104 TRACE(InsertEntryT, key);
107 tnc->next = tnc->prev = tnc;
110 tnc->next = nameHash[key];
111 tnc->prev = tnc->next->prev;
112 tnc->next->prev = tnc;
113 tnc->prev->next = tnc;
119 int osi_dnlc_enter ( adp, aname, avc, avno )
126 unsigned int key, skey;
133 TRACE(osi_dnlc_enterT, 0);
134 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
135 if (ts - aname >= AFSNCNAMESIZE) {
138 skey = key & (NHSIZE -1);
142 ObtainWriteLock(&afs_xdnlc,222);
144 /* Only cache entries from the latest version of the directory */
145 if (!(adp->states & CStatd) || !hsame(*avno, adp->m.DataVersion)) {
146 ReleaseWriteLock(&afs_xdnlc);
151 * Make sure each directory entry gets cached no more than once.
153 for (tnc = nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ ) {
154 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
155 /* duplicate entry */
158 else if (tnc->next == nameHash[skey]) { /* end of list */
162 else if (safety >NCSIZE) {
163 afs_warn("DNLC cycle");
165 ReleaseWriteLock(&afs_xdnlc);
172 tnc = GetMeAnEntry();
177 memcpy((char *)tnc->name, aname, ts-aname+1); /* include the NULL */
184 ReleaseWriteLock(&afs_xdnlc);
191 osi_dnlc_lookup ( adp, aname, locktype )
198 unsigned int key, skey;
200 struct nc * tnc, *tnc1=0;
206 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
207 if (ts - aname >= AFSNCNAMESIZE) {
210 skey = key & (NHSIZE -1);
212 TRACE(osi_dnlc_lookupT, skey);
215 ObtainReadLock(&afs_xvcache);
216 ObtainReadLock(&afs_xdnlc);
218 for ( tvc = (struct vcache *) 0, tnc = nameHash[skey], safety=0;
219 tnc; tnc = tnc->next, safety++ ) {
220 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
221 && (!strcmp((char *)tnc->name, aname))) {
226 else if (tnc->next == nameHash[skey]) { /* end of list */
229 else if (safety >NCSIZE) {
230 afs_warn("DNLC cycle");
232 ReleaseReadLock(&afs_xdnlc);
233 ReleaseReadLock(&afs_xvcache);
239 LRUme = 0; /* (tnc != nameHash[skey]); */
240 ReleaseReadLock(&afs_xdnlc);
243 ReleaseReadLock(&afs_xvcache);
248 VN_HOLD((vnode_t *)tvc);
252 ReleaseReadLock(&afs_xvcache);
256 * XX If LRUme ever is non-zero change the if statement around because
257 * aix's cc with optimizer on won't necessarily check things in order XX
259 if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
260 /* don't block to do this */
261 /* tnc might have been moved during race condition, */
262 /* but it's always in a legit hash chain when a lock is granted,
263 * or else it's on the freelist so prev == NULL,
264 * so at worst this is redundant */
265 /* Now that we've got it held, and a lock on the dnlc, we
266 * should check to be sure that there was no race, and
267 * bail out if there was. */
269 /* special case for only two elements on list - relative ordering
271 if (tnc->prev != tnc->next) {
272 /* remove from old location */
273 tnc->prev->next = tnc->next;
274 tnc->next->prev = tnc->prev;
275 /* insert into new location */
276 tnc->next = nameHash[skey];
277 tnc->prev = tnc->next->prev;
278 tnc->next->prev = tnc;
279 tnc->prev->next = tnc;
281 nameHash[skey] = tnc;
283 ReleaseWriteLock(&afs_xdnlc);
293 RemoveEntry (tnc, key)
297 if (!tnc->prev) /* things on freelist always have null prev ptrs */
298 osi_Panic("bogus free list");
300 TRACE(RemoveEntryT, key);
301 if (tnc == tnc->next) { /* only one in list */
302 nameHash[key] = (struct nc *) 0;
305 if (tnc == nameHash[key])
306 nameHash[key] = tnc->next;
307 tnc->prev->next = tnc->next;
308 tnc->next->prev = tnc->prev;
311 tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
312 tnc->key = 0; /* just for safety's sake */
317 osi_dnlc_remove ( adp, aname, avc )
322 unsigned int key, skey;
329 TRACE( osi_dnlc_removeT, skey);
330 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
331 if (ts - aname >= AFSNCNAMESIZE) {
334 skey = key & (NHSIZE -1);
335 TRACE( osi_dnlc_removeT, skey);
337 ObtainReadLock(&afs_xdnlc);
339 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
340 if ((tnc->dirp == adp) && (tnc->key == key)
341 && (!strcmp((char *)tnc->name, aname))) {
342 tnc->dirp = (struct vcache *) 0; /* now it won't match anything */
345 else if (tnc->next == nameHash[skey]) { /* end of list */
346 tnc = (struct nc *) 0;
350 ReleaseReadLock(&afs_xdnlc);
355 /* there is a little race condition here, but it's relatively
356 * harmless. At worst, I wind up removing a mapping that I just
358 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,1)) {
359 return 0; /* no big deal, tnc will get recycled eventually */
361 RemoveEntry(tnc, skey);
362 tnc->next = ncfreelist;
364 ReleaseWriteLock(&afs_xdnlc);
369 /* remove anything pertaining to this directory. I can invalidate
370 * things without the lock, since I am just looking through the array,
371 * but to move things off the lists or into the freelist, I need the
374 osi_dnlc_purgedp (adp)
384 TRACE( osi_dnlc_purgedpT, 0);
385 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,2));
387 for (i=0; i<NCSIZE; i++) {
388 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
389 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
390 if (writelocked && nameCache[i].prev) {
391 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
392 nameCache[i].next = ncfreelist;
393 ncfreelist = &nameCache[i];
398 ReleaseWriteLock(&afs_xdnlc);
403 /* remove anything pertaining to this file */
405 osi_dnlc_purgevp ( avc )
415 TRACE( osi_dnlc_purgevpT, 0);
416 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,3));
418 for (i=0; i<NCSIZE; i++) {
419 if ((nameCache[i].vp == avc)) {
420 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
421 /* can't simply break; because of hard links -- might be two */
422 /* different entries with same vnode */
423 if (writelocked && nameCache[i].prev) {
424 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
425 nameCache[i].next = ncfreelist;
426 ncfreelist = &nameCache[i];
431 ReleaseWriteLock(&afs_xdnlc);
436 /* remove everything */
442 TRACE( osi_dnlc_purgeT, 0);
443 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,4)) { /* couldn't get lock */
444 for (i=0; i<NCSIZE; i++)
445 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
447 else { /* did get the lock */
448 ncfreelist = (struct nc *) 0;
449 memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
450 memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
451 for (i=0; i<NCSIZE; i++) {
452 nameCache[i].next = ncfreelist;
453 ncfreelist = &nameCache[i];
455 ReleaseWriteLock(&afs_xdnlc);
461 /* remove everything referencing a specific volume */
463 osi_dnlc_purgevol( fidp )
464 struct VenusFid *fidp;
467 dnlcstats.purgevols++;
477 Lock_Init(&afs_xdnlc);
478 memset((char *)&dnlcstats, 0, sizeof(dnlcstats));
479 memset((char *)dnlctracetable, 0, sizeof(dnlctracetable));
481 ObtainWriteLock(&afs_xdnlc,223);
482 ncfreelist = (struct nc *) 0;
483 memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
484 memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
485 for (i=0; i<NCSIZE; i++) {
486 nameCache[i].next = ncfreelist;
487 ncfreelist = &nameCache[i];
489 ReleaseWriteLock(&afs_xdnlc);
494 int osi_dnlc_shutdown()