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 "../afs/param.h" /*Should be always first*/
11 #include "../afs/sysincludes.h" /*Standard vendor system headers*/
12 #include "../afs/afsincludes.h" /*AFS-based standard headers*/
14 #include "../afs/lock.h"
15 #include "../afs/afs_stats.h"
16 #include "../afs/afs_osidnlc.h"
19 * also cache failed lookups.
20 * look into interactions of dnlc and readdir.
21 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
22 * the actual name itself.
23 * precompute a key and stuff for @sys, and combine the HandleAtName function with
24 * this, since we're looking at the name anyway.
27 struct afs_lock afs_xdnlc;
28 extern struct afs_lock afs_xvcache;
30 dnlcstats_t dnlcstats;
33 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
34 struct nc *ncfreelist = (struct nc *)0;
35 static struct nc nameCache[NCSIZE];
36 struct nc *nameHash[NHSIZE];
37 /* Hash table invariants:
38 * 1. If nameHash[i] is NULL, list is empty
39 * 2. A single element in a hash bucket has itself as prev and next.
42 typedef enum {osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT, ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT, osi_dnlc_purgevpT, osi_dnlc_purgeT } traceevt;
51 struct dt dnlctracetable[256];
54 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
56 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
58 static struct nc * GetMeAnEntry() {
59 static unsigned int nameptr = 0; /* next bucket to pull something from */
65 ncfreelist = tnc->next;
69 for (j=0; j<NHSIZE+2; j++, nameptr++) {
70 if (nameptr >= NHSIZE)
72 if (nameHash[nameptr])
76 TRACE(ScavengeEntryT, nameptr);
77 tnc = nameHash[nameptr];
78 if (!tnc) /* May want to consider changing this to return 0 */
79 osi_Panic("null tnc in GetMeAnEntry");
81 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
82 nameHash[nameptr] = (struct nc *) 0;
86 tnc = tnc->prev; /* grab oldest one in this bucket */
87 /* remove it from list */
88 tnc->next->prev = tnc->prev;
89 tnc->prev->next = tnc->next;
94 static void InsertEntry(tnc)
98 key = tnc->key & (NHSIZE -1);
100 TRACE(InsertEntryT, key);
103 tnc->next = tnc->prev = tnc;
106 tnc->next = nameHash[key];
107 tnc->prev = tnc->next->prev;
108 tnc->next->prev = tnc;
109 tnc->prev->next = tnc;
115 int osi_dnlc_enter ( adp, aname, avc, avno )
122 unsigned int key, skey;
129 TRACE(osi_dnlc_enterT, 0);
130 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
131 if (ts - aname >= AFSNCNAMESIZE) {
134 skey = key & (NHSIZE -1);
138 ObtainWriteLock(&afs_xdnlc,222);
140 /* Only cache entries from the latest version of the directory */
141 if (!(adp->states & CStatd) || !hsame(*avno, adp->m.DataVersion)) {
142 ReleaseWriteLock(&afs_xdnlc);
147 * Make sure each directory entry gets cached no more than once.
149 for (tnc = nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ ) {
150 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
151 /* duplicate entry */
154 else if (tnc->next == nameHash[skey]) { /* end of list */
158 else if (safety >NCSIZE) {
159 afs_warn("DNLC cycle");
161 ReleaseWriteLock(&afs_xdnlc);
168 tnc = GetMeAnEntry();
173 bcopy (aname, (char *)tnc->name, ts-aname+1); /* include the NULL */
180 ReleaseWriteLock(&afs_xdnlc);
187 osi_dnlc_lookup ( adp, aname, locktype )
194 unsigned int key, skey;
196 struct nc * tnc, *tnc1=0;
202 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
203 if (ts - aname >= AFSNCNAMESIZE) {
206 skey = key & (NHSIZE -1);
208 TRACE(osi_dnlc_lookupT, skey);
211 ObtainReadLock(&afs_xvcache);
212 ObtainReadLock(&afs_xdnlc);
214 for ( tvc = (struct vcache *) 0, tnc = nameHash[skey], safety=0;
215 tnc; tnc = tnc->next, safety++ ) {
216 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
217 && (!strcmp((char *)tnc->name, aname))) {
222 else if (tnc->next == nameHash[skey]) { /* end of list */
225 else if (safety >NCSIZE) {
226 afs_warn("DNLC cycle");
228 ReleaseReadLock(&afs_xdnlc);
229 ReleaseReadLock(&afs_xvcache);
235 LRUme = 0; /* (tnc != nameHash[skey]); */
236 ReleaseReadLock(&afs_xdnlc);
239 ReleaseReadLock(&afs_xvcache);
244 VN_HOLD((vnode_t *)tvc);
248 ReleaseReadLock(&afs_xvcache);
252 * XX If LRUme ever is non-zero change the if statement around because
253 * aix's cc with optimizer on won't necessarily check things in order XX
255 if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
256 /* don't block to do this */
257 /* tnc might have been moved during race condition, */
258 /* but it's always in a legit hash chain when a lock is granted,
259 * or else it's on the freelist so prev == NULL,
260 * so at worst this is redundant */
261 /* Now that we've got it held, and a lock on the dnlc, we
262 * should check to be sure that there was no race, and
263 * bail out if there was. */
265 /* special case for only two elements on list - relative ordering
267 if (tnc->prev != tnc->next) {
268 /* remove from old location */
269 tnc->prev->next = tnc->next;
270 tnc->next->prev = tnc->prev;
271 /* insert into new location */
272 tnc->next = nameHash[skey];
273 tnc->prev = tnc->next->prev;
274 tnc->next->prev = tnc;
275 tnc->prev->next = tnc;
277 nameHash[skey] = tnc;
279 ReleaseWriteLock(&afs_xdnlc);
289 RemoveEntry (tnc, key)
293 if (!tnc->prev) /* things on freelist always have null prev ptrs */
294 osi_Panic("bogus free list");
296 TRACE(RemoveEntryT, key);
297 if (tnc == tnc->next) { /* only one in list */
298 nameHash[key] = (struct nc *) 0;
301 if (tnc == nameHash[key])
302 nameHash[key] = tnc->next;
303 tnc->prev->next = tnc->next;
304 tnc->next->prev = tnc->prev;
307 tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
308 tnc->key = 0; /* just for safety's sake */
313 osi_dnlc_remove ( adp, aname, avc )
318 unsigned int key, skey;
325 TRACE( osi_dnlc_removeT, skey);
326 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
327 if (ts - aname >= AFSNCNAMESIZE) {
330 skey = key & (NHSIZE -1);
331 TRACE( osi_dnlc_removeT, skey);
333 ObtainReadLock(&afs_xdnlc);
335 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
336 if ((tnc->dirp == adp) && (tnc->key == key)
337 && (!strcmp((char *)tnc->name, aname))) {
338 tnc->dirp = (struct vcache *) 0; /* now it won't match anything */
341 else if (tnc->next == nameHash[skey]) { /* end of list */
342 tnc = (struct nc *) 0;
346 ReleaseReadLock(&afs_xdnlc);
351 /* there is a little race condition here, but it's relatively
352 * harmless. At worst, I wind up removing a mapping that I just
354 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,1)) {
355 return 0; /* no big deal, tnc will get recycled eventually */
357 RemoveEntry(tnc, skey);
358 tnc->next = ncfreelist;
360 ReleaseWriteLock(&afs_xdnlc);
365 /* remove anything pertaining to this directory. I can invalidate
366 * things without the lock, since I am just looking through the array,
367 * but to move things off the lists or into the freelist, I need the
370 osi_dnlc_purgedp (adp)
380 TRACE( osi_dnlc_purgedpT, 0);
381 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,2));
383 for (i=0; i<NCSIZE; i++) {
384 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
385 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
386 if (writelocked && nameCache[i].prev) {
387 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
388 nameCache[i].next = ncfreelist;
389 ncfreelist = &nameCache[i];
394 ReleaseWriteLock(&afs_xdnlc);
399 /* remove anything pertaining to this file */
401 osi_dnlc_purgevp ( avc )
411 TRACE( osi_dnlc_purgevpT, 0);
412 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,3));
414 for (i=0; i<NCSIZE; i++) {
415 if ((nameCache[i].vp == avc)) {
416 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
417 /* can't simply break; because of hard links -- might be two */
418 /* different entries with same vnode */
419 if (writelocked && nameCache[i].prev) {
420 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
421 nameCache[i].next = ncfreelist;
422 ncfreelist = &nameCache[i];
427 ReleaseWriteLock(&afs_xdnlc);
432 /* remove everything */
438 TRACE( osi_dnlc_purgeT, 0);
439 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,4)) { /* couldn't get lock */
440 for (i=0; i<NCSIZE; i++)
441 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
443 else { /* did get the lock */
444 ncfreelist = (struct nc *) 0;
445 bzero ((char *)nameCache, sizeof(struct nc) * NCSIZE);
446 bzero ((char *)nameHash, sizeof(struct nc *) * NHSIZE);
447 for (i=0; i<NCSIZE; i++) {
448 nameCache[i].next = ncfreelist;
449 ncfreelist = &nameCache[i];
451 ReleaseWriteLock(&afs_xdnlc);
457 /* remove everything referencing a specific volume */
459 osi_dnlc_purgevol( fidp )
460 struct VenusFid *fidp;
463 dnlcstats.purgevols++;
473 Lock_Init(&afs_xdnlc);
474 bzero ((char *)&dnlcstats, sizeof(dnlcstats));
475 bzero ((char *)dnlctracetable, sizeof(dnlctracetable));
477 ObtainWriteLock(&afs_xdnlc,223);
478 ncfreelist = (struct nc *) 0;
479 bzero ((char *)nameCache, sizeof(struct nc) * NCSIZE);
480 bzero ((char *)nameHash, sizeof(struct nc *) * NHSIZE);
481 for (i=0; i<NCSIZE; i++) {
482 nameCache[i].next = ncfreelist;
483 ncfreelist = &nameCache[i];
485 ReleaseWriteLock(&afs_xdnlc);
490 int osi_dnlc_shutdown()