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;
209 struct nc * tnc, * tnc_begin;
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 tnc_begin = nameHash[skey];
228 for ( tvc = (cm_scache_t *) 0, tnc = tnc_begin, safety=0;
229 tnc; tnc = tnc->next, safety++ )
231 if (tnc->dirp == adp)
233 if ( sp->caseFold ) /* case insensitive */
235 match = cm_stricmp(tnc->name, aname);
236 if ( !match ) /* something matches */
238 /* determine what type of match it is */
239 if ( !strcmp(tnc->name, aname))
241 /* exact match, do nothing */
243 else if ( cm_NoneUpper(tnc->name))
245 else if ( cm_NoneLower(tnc->name))
247 else sp->NCfound = 1;
252 else /* case sensitive */
254 match = strcmp(tnc->name, aname);
255 if ( !match ) /* found a match */
262 if (tnc->next == nameHash[skey])
266 else if (tnc->next == tnc_begin || safety >NCSIZE)
269 lock_ReleaseRead(&cm_dnlcLock);
271 dnlcNotify("DNLC cycle",1);
273 osi_Log0(afsd_logp, "DNLC cycle");
280 dnlcstats.misses++; /* Is a dnlcread lock sufficient? */
284 sp->fid.vnode = tvc->fid.vnode;
285 sp->fid.unique = tvc->fid.unique;
287 lock_ReleaseRead(&cm_dnlcLock);
290 lock_ObtainWrite(&cm_scacheLock);
291 tvc->refCount++; /* scache entry held */
292 lock_ReleaseWrite(&cm_scacheLock);
295 if ( cm_debugDnlc && tvc )
296 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
303 RemoveEntry (tnc, key)
307 if (!tnc->prev) /* things on freelist always have null prev ptrs */
309 dnlcNotify("Bogus dnlc freelist", 1);
310 osi_Log0(afsd_logp,"Bogus dnlc freelist");
311 return 1; /* error */
314 if (tnc == tnc->next) /* only one in list */
315 nameHash[key] = (struct nc *) 0;
318 if (tnc == nameHash[key])
319 nameHash[key] = tnc->next;
320 tnc->prev->next = tnc->next;
321 tnc->next->prev = tnc->prev;
324 tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
325 tnc->key = 0; /* just for safety's sake */
326 return 0; /* success */
331 cm_dnlcRemove ( adp, aname)
335 unsigned int key, skey, error=0;
336 int found= 0, safety;
338 struct nc *tnc, *tmp;
344 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
345 adp, osi_LogSaveString(afsd_logp,aname));
347 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
348 if (ts - aname >= CM_AFSNCNAMESIZE)
351 skey = key & (NHSIZE -1);
352 lock_ObtainWrite(&cm_dnlcLock);
355 for (tnc = nameHash[skey], safety=0; tnc; safety++)
357 if ( (tnc->dirp == adp) && (tnc->key == key)
358 && !cm_stricmp(tnc->name,aname) )
360 tnc->dirp = (cm_scache_t *) 0; /* now it won't match anything */
362 error = RemoveEntry(tnc, skey);
366 tnc->next = ncfreelist; /* insert entry into freelist */
368 found = 1; /* found atleast one entry */
370 tnc = tmp; /* continue down the linked list */
372 else if (tnc->next == nameHash[skey]) /* end of list */
376 if ( safety > NCSIZE )
379 lock_ReleaseWrite(&cm_dnlcLock);
381 dnlcNotify("DNLC cycle",1);
383 osi_Log0(afsd_logp, "DNLC cycle");
388 lock_ReleaseWrite(&cm_dnlcLock);
390 if (!found && !error && cm_debugDnlc)
391 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
397 /* remove anything pertaining to this directory */
409 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
411 lock_ObtainWrite(&cm_dnlcLock);
414 for (i=0; i<NCSIZE && !err; i++)
416 if (nameCache[i].dirp == adp )
418 nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
419 if (nameCache[i].prev && !err)
421 err = RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
422 nameCache[i].next = ncfreelist;
423 ncfreelist = &nameCache[i];
427 lock_ReleaseWrite(&cm_dnlcLock);
432 /* remove anything pertaining to this file */
434 cm_dnlcPurgevp ( avc )
444 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
446 lock_ObtainWrite(&cm_dnlcLock);
449 for (i=0; i<NCSIZE && !err ; i++)
451 if (nameCache[i].vp == avc)
453 nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
454 /* can't simply break; because of hard links -- might be two */
455 /* different entries with same vnode */
456 if (!err && nameCache[i].prev)
458 err=RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
459 nameCache[i].next = ncfreelist;
460 ncfreelist = &nameCache[i];
464 lock_ReleaseWrite(&cm_dnlcLock);
469 /* remove everything */
470 void cm_dnlcPurge(void)
478 osi_Log0(afsd_logp, "cm_dnlcPurge");
480 lock_ObtainWrite(&cm_dnlcLock);
483 ncfreelist = (struct nc *) 0;
484 memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
485 memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
486 for (i=0; i<NCSIZE; i++)
488 nameCache[i].next = ncfreelist;
489 ncfreelist = &nameCache[i];
491 lock_ReleaseWrite(&cm_dnlcLock);
495 /* remove everything referencing a specific volume */
497 cm_dnlcPurgeVol( fidp )
504 dnlcstats.purgevols++;
516 osi_Log0(afsd_logp,"cm_dnlcInit");
518 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
519 memset (&dnlcstats, 0, sizeof(dnlcstats));
520 lock_ObtainWrite(&cm_dnlcLock);
521 ncfreelist = (struct nc *) 0;
522 memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
523 memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
524 for (i=0; i<NCSIZE; i++)
526 nameCache[i].next = ncfreelist;
527 ncfreelist = &nameCache[i];
529 lock_ReleaseWrite(&cm_dnlcLock);
533 cm_dnlcShutdown(void)
536 osi_Log0(afsd_logp,"cm_dnlcShutdown");