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>
28 osi_rwlock_t cm_dnlcLock;
30 static cm_dnlcstats_t dnlcstats; /* dnlc statistics */
31 static int cm_useDnlc = 1; /* yes, start using the dnlc */
32 static int cm_debugDnlc = 0; /* debug dnlc */
35 /* Hash table invariants:
36 * 1. If nameHash[i] is NULL, list is empty
37 * 2. A single element in a hash bucket has itself as prev and next.
40 /* Must be called with cm_dnlcLock write locked */
44 static unsigned int nameptr = 0; /* next bucket to pull something from */
48 if (cm_data.ncfreelist)
50 tnc = cm_data.ncfreelist;
51 cm_data.ncfreelist = tnc->next;
55 for (j=0; j<NHSIZE+2; j++, nameptr++)
57 if (nameptr >= NHSIZE)
59 if (cm_data.nameHash[nameptr])
63 tnc = cm_data.nameHash[nameptr];
66 osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
71 { /* only thing in list, don't screw around */
72 cm_data.nameHash[nameptr] = (cm_nc_t *) 0;
76 tnc = tnc->prev; /* grab oldest one in this bucket */
77 tnc->next->prev = tnc->prev;/* remove it from list */
78 tnc->prev->next = tnc->next;
84 InsertEntry(cm_nc_t *tnc)
87 key = tnc->key & (NHSIZE -1);
89 if (!cm_data.nameHash[key])
91 cm_data.nameHash[key] = tnc;
92 tnc->next = tnc->prev = tnc;
96 tnc->next = cm_data.nameHash[key];
97 tnc->prev = tnc->next->prev;
98 tnc->next->prev = tnc;
99 tnc->prev->next = tnc;
100 cm_data.nameHash[key] = tnc;
106 cm_dnlcEnter ( cm_scache_t *adp,
111 unsigned int key, skey, new=0;
118 if (!strcmp(aname,".") || !strcmp(aname,".."))
122 osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %s scache %x",
123 adp, osi_LogSaveString(afsd_logp,aname), avc);
125 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
126 if (ts - aname >= CM_AFSNCNAMESIZE)
128 skey = key & (NHSIZE -1);
130 lock_ObtainWrite(&cm_dnlcLock);
133 for (tnc = cm_data.nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
134 if ((tnc->dirp == adp) && (!strcmp(tnc->name, aname)))
135 break; /* preexisting entry */
136 else if ( tnc->next == cm_data.nameHash[skey]) /* end of list */
141 else if (safety > NCSIZE)
144 lock_ReleaseWrite(&cm_dnlcLock);
147 osi_Log0(afsd_logp, "DNLC cycle");
154 new = 1; /* entry does not exist, we are creating a new entry*/
155 tnc = GetMeAnEntry();
162 memcpy (tnc->name, aname, ts-aname+1); /* include the NULL */
164 if ( new ) /* insert entry only if it is newly created */
168 lock_ReleaseWrite(&cm_dnlcLock);
175 * if the scache entry is found, return it held
178 cm_dnlcLookup (cm_scache_t *adp, cm_lookupSearch_t* sp)
181 unsigned int key, skey;
182 char* aname = sp->searchNamep;
184 cm_nc_t * tnc, * tnc_begin;
190 osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %s",
191 adp, osi_LogSaveString(afsd_logp,aname));
193 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
194 if (ts - aname >= CM_AFSNCNAMESIZE)
197 skey = key & (NHSIZE -1);
199 lock_ObtainRead(&cm_dnlcLock);
200 dnlcstats.lookups++; /* Is a dnlcread lock sufficient? */
203 tnc_begin = cm_data.nameHash[skey];
204 for ( tvc = (cm_scache_t *) 0, tnc = tnc_begin, safety=0;
205 tnc; tnc = tnc->next, safety++ )
207 if (tnc->dirp == adp)
210 osi_Log1(afsd_logp,"Looking at [%s]",
211 osi_LogSaveString(afsd_logp,tnc->name));
213 if ( sp->caseFold ) /* case insensitive */
215 match = cm_stricmp(tnc->name, aname);
216 if ( !match ) /* something matches */
221 /* determine what type of match it is */
222 if ( !strcmp(tnc->name, aname))
228 osi_Log1(afsd_logp,"DNLC found exact match [%s]",
229 osi_LogSaveString(afsd_logp,tnc->name));
232 else if ( cm_NoneUpper(tnc->name))
234 else if ( cm_NoneLower(tnc->name))
238 /* Don't break here. We might find an exact match yet */
241 else /* case sensitive */
243 match = strcmp(tnc->name, aname);
244 if ( !match ) /* found a match */
253 if (tnc->next == cm_data.nameHash[skey])
257 else if (tnc->next == tnc_begin || safety > NCSIZE)
260 lock_ReleaseRead(&cm_dnlcLock);
263 osi_Log0(afsd_logp, "DNLC cycle");
269 if(cm_debugDnlc && ts) {
270 osi_Log3(afsd_logp, "DNLC matched [%s] for [%s] with vnode[%ld]",
271 osi_LogSaveString(afsd_logp,ts),
272 osi_LogSaveString(afsd_logp,aname),
273 (long) tvc->fid.vnode);
277 dnlcstats.misses++; /* Is a dnlcread lock sufficient? */
281 sp->fid.vnode = tvc->fid.vnode;
282 sp->fid.unique = tvc->fid.unique;
284 lock_ReleaseRead(&cm_dnlcLock);
289 if ( cm_debugDnlc && tvc )
290 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
297 RemoveEntry (cm_nc_t *tnc, unsigned int key)
299 if (!tnc->prev) /* things on freelist always have null prev ptrs */
301 osi_Log0(afsd_logp,"Bogus dnlc freelist");
302 return 1; /* error */
305 if (tnc == tnc->next) /* only one in list */
306 cm_data.nameHash[key] = (cm_nc_t *) 0;
309 if (tnc == cm_data.nameHash[key])
310 cm_data.nameHash[key] = tnc->next;
311 tnc->prev->next = tnc->next;
312 tnc->next->prev = tnc->prev;
315 memset(tnc, 0, sizeof(cm_nc_t));
316 tnc->magic = CM_DNLC_MAGIC;
317 return 0; /* success */
322 cm_dnlcRemove (cm_scache_t *adp, char *aname)
324 unsigned int key, skey, error=0;
325 int found= 0, safety;
333 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
334 adp, osi_LogSaveString(afsd_logp,aname));
336 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
337 if (ts - aname >= CM_AFSNCNAMESIZE)
340 skey = key & (NHSIZE -1);
341 lock_ObtainWrite(&cm_dnlcLock);
344 for (tnc = cm_data.nameHash[skey], safety=0; tnc; safety++)
346 if ( (tnc->dirp == adp) && (tnc->key == key)
347 && !strcmp(tnc->name,aname) )
350 error = RemoveEntry(tnc, skey);
354 tnc->next = cm_data.ncfreelist; /* insert entry into freelist */
355 cm_data.ncfreelist = tnc;
356 found = 1; /* found at least one entry */
358 tnc = tmp; /* continue down the linked list */
360 else if (tnc->next == cm_data.nameHash[skey]) /* end of list */
364 if ( safety > NCSIZE )
367 lock_ReleaseWrite(&cm_dnlcLock);
370 osi_Log0(afsd_logp, "DNLC cycle");
375 lock_ReleaseWrite(&cm_dnlcLock);
377 if (!found && !error && cm_debugDnlc)
378 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
384 /* remove anything pertaining to this directory */
386 cm_dnlcPurgedp (cm_scache_t *adp)
395 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
397 lock_ObtainWrite(&cm_dnlcLock);
400 for (i=0; i<NCSIZE && !err; i++)
402 if (cm_data.nameCache[i].dirp == adp )
404 if (cm_data.nameCache[i].prev) {
405 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
408 cm_data.nameCache[i].next = cm_data.ncfreelist;
409 cm_data.ncfreelist = &cm_data.nameCache[i];
412 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
416 lock_ReleaseWrite(&cm_dnlcLock);
421 /* remove anything pertaining to this file */
423 cm_dnlcPurgevp (cm_scache_t *avc)
432 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
434 lock_ObtainWrite(&cm_dnlcLock);
437 for (i=0; i<NCSIZE && !err ; i++)
439 if (cm_data.nameCache[i].vp == avc)
441 if (cm_data.nameCache[i].prev) {
442 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
445 cm_data.nameCache[i].next = cm_data.ncfreelist;
446 cm_data.ncfreelist = &cm_data.nameCache[i];
449 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
453 lock_ReleaseWrite(&cm_dnlcLock);
458 /* remove everything */
459 void cm_dnlcPurge(void)
467 osi_Log0(afsd_logp, "cm_dnlcPurge");
469 lock_ObtainWrite(&cm_dnlcLock);
472 cm_data.ncfreelist = (cm_nc_t *) 0;
473 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
474 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
475 for (i=0; i<NCSIZE; i++)
477 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
478 cm_data.nameCache[i].next = cm_data.ncfreelist;
479 cm_data.ncfreelist = &cm_data.nameCache[i];
481 lock_ReleaseWrite(&cm_dnlcLock);
485 /* remove everything referencing a specific volume */
486 /* is this function ever called? */
488 cm_dnlcPurgeVol(AFSFid *fidp)
494 dnlcstats.purgevols++;
499 cm_dnlcValidate(void)
505 // are all nameCache entries marked with the magic bit?
506 for (i=0; i<NCSIZE; i++)
508 if (cm_data.nameCache[i].magic != CM_DNLC_MAGIC) {
509 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC", i);
510 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC\n", i);
513 if (cm_data.nameCache[i].next &&
514 cm_data.nameCache[i].next->magic != CM_DNLC_MAGIC) {
515 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC", i);
516 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC\n", i);
519 if (cm_data.nameCache[i].prev &&
520 cm_data.nameCache[i].prev->magic != CM_DNLC_MAGIC) {
521 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC", i);
522 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC\n", i);
525 if (cm_data.nameCache[i].dirp &&
526 cm_data.nameCache[i].dirp->magic != CM_SCACHE_MAGIC) {
527 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC", i);
528 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC\n", i);
531 if (cm_data.nameCache[i].vp &&
532 cm_data.nameCache[i].vp->magic != CM_SCACHE_MAGIC) {
533 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC", i);
534 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC\n", i);
539 // are the contents of the hash table intact?
540 for (i=0; i<NHSIZE;i++) {
541 for (ncp = cm_data.nameHash[i]; ncp ;
542 ncp = ncp->next != cm_data.nameHash[i] ? ncp->next : NULL) {
543 if (ncp->magic != CM_DNLC_MAGIC) {
544 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
545 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
548 if (ncp->prev && ncp->prev->magic != CM_DNLC_MAGIC) {
549 afsi_log("cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC");
550 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC\n");
553 if (ncp->dirp && ncp->dirp->magic != CM_SCACHE_MAGIC) {
554 afsi_log("cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC");
555 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC\n");
558 if (ncp->vp && ncp->vp->magic != CM_SCACHE_MAGIC) {
559 afsi_log("cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC");
560 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC\n");
566 // is the freelist stable?
567 if ( cm_data.ncfreelist ) {
568 for (ncp = cm_data.ncfreelist, i = 0; ncp && i < NCSIZE;
569 ncp = ncp->next != cm_data.ncfreelist ? ncp->next : NULL, i++) {
570 if (ncp->magic != CM_DNLC_MAGIC) {
571 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
572 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
576 afsi_log("cm_dnlcValidate failure: ncp->prev != NULL");
577 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev != NULL\n");
581 afsi_log("cm_dnlcValidate failure: ncp->key != 0");
582 fprintf(stderr, "cm_dnlcValidate failure: ncp->key != 0\n");
586 afsi_log("cm_dnlcValidate failure: ncp->dirp != NULL");
587 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp != NULL\n");
591 afsi_log("cm_dnlcValidate failure: ncp->vp != NULL");
592 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp != NULL\n");
597 if ( i == NCSIZE && ncp ) {
598 afsi_log("cm_dnlcValidate failure: dnlc freeList corrupted");
599 fprintf(stderr, "cm_dnlcValidate failure: dnlc freeList corrupted\n");
609 afsi_log("cm_dnlcValidate information: purging");
610 fprintf(stderr, "cm_dnlcValidate information: purging\n");
611 cm_data.ncfreelist = (cm_nc_t *) 0;
612 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
613 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
614 for (i=0; i<NCSIZE; i++)
616 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
617 cm_data.nameCache[i].next = cm_data.ncfreelist;
618 cm_data.ncfreelist = &cm_data.nameCache[i];
625 cm_dnlcInit(int newFile)
633 osi_Log0(afsd_logp,"cm_dnlcInit");
635 memset (&dnlcstats, 0, sizeof(dnlcstats));
637 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
639 lock_ObtainWrite(&cm_dnlcLock);
640 cm_data.ncfreelist = (cm_nc_t *) 0;
641 cm_data.nameCache = cm_data.dnlcBaseAddress;
642 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
643 cm_data.nameHash = (cm_nc_t **) (cm_data.nameCache + NCSIZE);
644 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
646 for (i=0; i<NCSIZE; i++)
648 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
649 cm_data.nameCache[i].next = cm_data.ncfreelist;
650 cm_data.ncfreelist = &cm_data.nameCache[i];
652 lock_ReleaseWrite(&cm_dnlcLock);
657 cm_dnlcShutdown(void)
660 osi_Log0(afsd_logp,"cm_dnlcShutdown");