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 ** This implements the directory to name cache lookup.
12 ** Given a directory scache and a name, the dnlc returns the
13 ** vcache corresponding to the name. The vcache entries that
14 ** exist in the dnlc are not refcounted.
18 #include <afs/param.h>
30 osi_rwlock_t cm_dnlcLock;
32 cm_dnlcstats_t dnlcstats; /* dnlc statistics */
33 int cm_useDnlc = 1; /* yes, start using the dnlc */
34 int cm_debugDnlc = 0; /* debug dnlc */
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.
41 struct nc *ncfreelist = (struct nc *)0;
42 static struct nc nameCache[NCSIZE];
43 struct nc* nameHash[NHSIZE];
47 #define dnlcNotify(x,debug){ \
52 hh = RegisterEventSource(NULL, AFS_DAEMON_EVENT_NAME); \
53 ReportEvent(hh,EVENTLOG_ERROR_TYPE,0,__LINE__, \
54 NULL, 1, 0, ptbuf, NULL); \
55 DeregisterEventSource(hh); \
59 #define dnlcNotify(x,debug)
66 static unsigned int nameptr = 0; /* next bucket to pull something from */
73 ncfreelist = tnc->next;
77 for (j=0; j<NHSIZE+2; j++, nameptr++)
79 if (nameptr >= NHSIZE)
81 if (nameHash[nameptr])
85 tnc = nameHash[nameptr];
88 dnlcNotify("null tnc in GetMeAnEntry",1);
89 osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
94 { /* only thing in list, don't screw around */
95 nameHash[nameptr] = (struct nc *) 0;
99 tnc = tnc->prev; /* grab oldest one in this bucket */
100 tnc->next->prev = tnc->prev;/* remove it from list */
101 tnc->prev->next = tnc->next;
111 key = tnc->key & (NHSIZE -1);
116 tnc->next = tnc->prev = tnc;
120 tnc->next = nameHash[key];
121 tnc->prev = tnc->next->prev;
122 tnc->next->prev = tnc;
123 tnc->prev->next = tnc;
130 cm_dnlcEnter ( adp, aname, avc )
136 unsigned int key, skey, new=0;
144 osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %s scache %x",
145 adp, osi_LogSaveString(afsd_logp,aname), avc);
147 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
148 if (ts - aname >= CM_AFSNCNAMESIZE)
150 skey = key & (NHSIZE -1);
152 lock_ObtainWrite(&cm_dnlcLock);
155 for (tnc = nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
156 if ((tnc->dirp == adp) && (!cm_stricmp(tnc->name, aname)))
157 break; /* preexisting entry */
158 else if ( tnc->next == nameHash[skey]) /* end of list */
163 else if ( safety >NCSIZE)
166 lock_ReleaseWrite(&cm_dnlcLock);
168 dnlcNotify("DNLC cycle",1);
170 osi_Log0(afsd_logp, "DNLC cycle");
177 new = 1; /* entry does not exist, we are creating a new entry*/
178 tnc = GetMeAnEntry();
185 memcpy (tnc->name, aname, ts-aname+1); /* include the NULL */
187 if ( new ) /* insert entry only if it is newly created */
191 lock_ReleaseWrite(&cm_dnlcLock);
198 * if the scache entry is found, return it held
201 cm_dnlcLookup ( adp, sp)
203 cm_lookupSearch_t* sp;
206 unsigned int key, skey;
207 char* aname = sp->searchNamep;
215 osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %s",
216 adp, osi_LogSaveString(afsd_logp,aname));
218 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
219 if (ts - aname >= CM_AFSNCNAMESIZE)
222 skey = key & (NHSIZE -1);
224 lock_ObtainRead(&cm_dnlcLock);
225 dnlcstats.lookups++; /* Is a dnlcread lock sufficient? */
227 for ( tvc = (cm_scache_t *) 0, tnc = nameHash[skey], safety=0;
228 tnc; tnc = tnc->next, safety++ )
230 if (tnc->dirp == adp)
232 if ( sp->caseFold ) /* case insensitive */
234 match = cm_stricmp(tnc->name, aname);
235 if ( !match ) /* something matches */
237 /* determine what type of match it is */
238 if ( !strcmp(tnc->name, aname))
240 /* exact match, do nothing */
242 else if ( cm_NoneUpper(tnc->name))
244 else if ( cm_NoneLower(tnc->name))
246 else sp->NCfound = 1;
251 else /* case sensitive */
253 match = strcmp(tnc->name, aname);
254 if ( !match ) /* found a match */
261 if (tnc->next == nameHash[skey])
265 else if (safety >NCSIZE)
268 lock_ReleaseRead(&cm_dnlcLock);
270 dnlcNotify("DNLC cycle",1);
272 osi_Log0(afsd_logp, "DNLC cycle");
279 dnlcstats.misses++; /* Is a dnlcread lock sufficient? */
283 sp->fid.vnode = tvc->fid.vnode;
284 sp->fid.unique = tvc->fid.unique;
286 lock_ReleaseRead(&cm_dnlcLock);
289 lock_ObtainWrite(&cm_scacheLock);
290 tvc->refCount++; /* scache entry held */
291 lock_ReleaseWrite(&cm_scacheLock);
294 if ( cm_debugDnlc && tvc )
295 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
302 RemoveEntry (tnc, key)
306 if (!tnc->prev) /* things on freelist always have null prev ptrs */
308 dnlcNotify("Bogus dnlc freelist", 1);
309 osi_Log0(afsd_logp,"Bogus dnlc freelist");
310 return 1; /* error */
313 if (tnc == tnc->next) /* only one in list */
314 nameHash[key] = (struct nc *) 0;
317 if (tnc == nameHash[key])
318 nameHash[key] = tnc->next;
319 tnc->prev->next = tnc->next;
320 tnc->next->prev = tnc->prev;
323 tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
324 tnc->key = 0; /* just for safety's sake */
325 return 0; /* success */
330 cm_dnlcRemove ( adp, aname)
334 unsigned int key, skey, error=0;
335 int found= 0, safety;
337 struct nc *tnc, *tmp;
343 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
344 adp, osi_LogSaveString(afsd_logp,aname));
346 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
347 if (ts - aname >= CM_AFSNCNAMESIZE)
350 skey = key & (NHSIZE -1);
351 lock_ObtainWrite(&cm_dnlcLock);
354 for (tnc = nameHash[skey], safety=0; tnc; safety++)
356 if ( (tnc->dirp == adp) && (tnc->key == key)
357 && !cm_stricmp(tnc->name,aname) )
359 tnc->dirp = (cm_scache_t *) 0; /* now it won't match anything */
361 error = RemoveEntry(tnc, skey);
365 tnc->next = ncfreelist; /* insert entry into freelist */
367 found = 1; /* found atleast one entry */
369 tnc = tmp; /* continue down the linked list */
371 else if (tnc->next == nameHash[skey]) /* end of list */
375 if ( safety > NCSIZE )
378 lock_ReleaseWrite(&cm_dnlcLock);
380 dnlcNotify("DNLC cycle",1);
382 osi_Log0(afsd_logp, "DNLC cycle");
387 lock_ReleaseWrite(&cm_dnlcLock);
389 if (!found && !error && cm_debugDnlc)
390 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
396 /* remove anything pertaining to this directory */
408 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
410 lock_ObtainWrite(&cm_dnlcLock);
413 for (i=0; i<NCSIZE && !err; i++)
415 if (nameCache[i].dirp == adp )
417 nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
418 if (nameCache[i].prev && !err)
420 err = RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
421 nameCache[i].next = ncfreelist;
422 ncfreelist = &nameCache[i];
426 lock_ReleaseWrite(&cm_dnlcLock);
431 /* remove anything pertaining to this file */
433 cm_dnlcPurgevp ( avc )
443 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
445 lock_ObtainWrite(&cm_dnlcLock);
448 for (i=0; i<NCSIZE && !err ; i++)
450 if (nameCache[i].vp == avc)
452 nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
453 /* can't simply break; because of hard links -- might be two */
454 /* different entries with same vnode */
455 if (!err && nameCache[i].prev)
457 err=RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
458 nameCache[i].next = ncfreelist;
459 ncfreelist = &nameCache[i];
463 lock_ReleaseWrite(&cm_dnlcLock);
468 /* remove everything */
469 void cm_dnlcPurge(void)
477 osi_Log0(afsd_logp, "cm_dnlcPurge");
479 lock_ObtainWrite(&cm_dnlcLock);
482 ncfreelist = (struct nc *) 0;
483 memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
484 memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
485 for (i=0; i<NCSIZE; i++)
487 nameCache[i].next = ncfreelist;
488 ncfreelist = &nameCache[i];
490 lock_ReleaseWrite(&cm_dnlcLock);
494 /* remove everything referencing a specific volume */
496 cm_dnlcPurgeVol( fidp )
503 dnlcstats.purgevols++;
515 osi_Log0(afsd_logp,"cm_dnlcInit");
517 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
518 memset (&dnlcstats, 0, sizeof(dnlcstats));
519 lock_ObtainWrite(&cm_dnlcLock);
520 ncfreelist = (struct nc *) 0;
521 memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
522 memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
523 for (i=0; i<NCSIZE; i++)
525 nameCache[i].next = ncfreelist;
526 ncfreelist = &nameCache[i];
528 lock_ReleaseWrite(&cm_dnlcLock);
532 cm_dnlcShutdown(void)
535 osi_Log0(afsd_logp,"cm_dnlcShutdown");