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 static cm_dnlcstats_t dnlcstats; /* dnlc statistics */
33 static int cm_useDnlc = 1; /* yes, start using the dnlc */
34 static 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.
42 #define dnlcNotify(x,debug){ \
47 hh = RegisterEventSource(NULL, AFS_DAEMON_EVENT_NAME); \
48 ReportEvent(hh,EVENTLOG_ERROR_TYPE,0,__LINE__, \
49 NULL, 1, 0, ptbuf, NULL); \
50 DeregisterEventSource(hh); \
54 #define dnlcNotify(x,debug)
57 /* Must be called with cm_dnlcLock write locked */
61 static unsigned int nameptr = 0; /* next bucket to pull something from */
65 if (cm_data.ncfreelist)
67 tnc = cm_data.ncfreelist;
68 cm_data.ncfreelist = tnc->next;
72 for (j=0; j<NHSIZE+2; j++, nameptr++)
74 if (nameptr >= NHSIZE)
76 if (cm_data.nameHash[nameptr])
80 tnc = cm_data.nameHash[nameptr];
83 dnlcNotify("null tnc in GetMeAnEntry",1);
84 osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
89 { /* only thing in list, don't screw around */
90 cm_data.nameHash[nameptr] = (cm_nc_t *) 0;
94 tnc = tnc->prev; /* grab oldest one in this bucket */
95 tnc->next->prev = tnc->prev;/* remove it from list */
96 tnc->prev->next = tnc->next;
102 InsertEntry(cm_nc_t *tnc)
105 key = tnc->key & (NHSIZE -1);
107 if (!cm_data.nameHash[key])
109 cm_data.nameHash[key] = tnc;
110 tnc->next = tnc->prev = tnc;
114 tnc->next = cm_data.nameHash[key];
115 tnc->prev = tnc->next->prev;
116 tnc->next->prev = tnc;
117 tnc->prev->next = tnc;
118 cm_data.nameHash[key] = tnc;
124 cm_dnlcEnter ( cm_scache_t *adp,
129 unsigned int key, skey, new=0;
137 osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %s scache %x",
138 adp, osi_LogSaveString(afsd_logp,aname), avc);
140 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
141 if (ts - aname >= CM_AFSNCNAMESIZE)
143 skey = key & (NHSIZE -1);
145 lock_ObtainWrite(&cm_dnlcLock);
148 for (tnc = cm_data.nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
149 if ((tnc->dirp == adp) && (!strcmp(tnc->name, aname)))
150 break; /* preexisting entry */
151 else if ( tnc->next == cm_data.nameHash[skey]) /* end of list */
156 else if (safety > NCSIZE)
159 lock_ReleaseWrite(&cm_dnlcLock);
161 dnlcNotify("DNLC cycle",1);
163 osi_Log0(afsd_logp, "DNLC cycle");
170 new = 1; /* entry does not exist, we are creating a new entry*/
171 tnc = GetMeAnEntry();
178 memcpy (tnc->name, aname, ts-aname+1); /* include the NULL */
180 if ( new ) /* insert entry only if it is newly created */
184 lock_ReleaseWrite(&cm_dnlcLock);
191 * if the scache entry is found, return it held
194 cm_dnlcLookup (cm_scache_t *adp, cm_lookupSearch_t* sp)
197 unsigned int key, skey;
198 char* aname = sp->searchNamep;
200 cm_nc_t * tnc, * tnc_begin;
206 osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %s",
207 adp, osi_LogSaveString(afsd_logp,aname));
209 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
210 if (ts - aname >= CM_AFSNCNAMESIZE)
213 skey = key & (NHSIZE -1);
215 lock_ObtainRead(&cm_dnlcLock);
216 dnlcstats.lookups++; /* Is a dnlcread lock sufficient? */
219 tnc_begin = cm_data.nameHash[skey];
220 for ( tvc = (cm_scache_t *) 0, tnc = tnc_begin, safety=0;
221 tnc; tnc = tnc->next, safety++ )
223 if (tnc->dirp == adp)
226 osi_Log1(afsd_logp,"Looking at [%s]",
227 osi_LogSaveString(afsd_logp,tnc->name));
229 if ( sp->caseFold ) /* case insensitive */
231 match = cm_stricmp(tnc->name, aname);
232 if ( !match ) /* something matches */
237 /* determine what type of match it is */
238 if ( !strcmp(tnc->name, aname))
244 osi_Log1(afsd_logp,"DNLC found exact match [%s]",
245 osi_LogSaveString(afsd_logp,tnc->name));
248 else if ( cm_NoneUpper(tnc->name))
250 else if ( cm_NoneLower(tnc->name))
254 /* Don't break here. We might find an exact match yet */
257 else /* case sensitive */
259 match = strcmp(tnc->name, aname);
260 if ( !match ) /* found a match */
269 if (tnc->next == cm_data.nameHash[skey])
273 else if (tnc->next == tnc_begin || safety > NCSIZE)
276 lock_ReleaseRead(&cm_dnlcLock);
278 dnlcNotify("DNLC cycle",1);
280 osi_Log0(afsd_logp, "DNLC cycle");
286 if(cm_debugDnlc && ts) {
287 osi_Log3(afsd_logp, "DNLC matched [%s] for [%s] with vnode[%ld]",
288 osi_LogSaveString(afsd_logp,ts),
289 osi_LogSaveString(afsd_logp,aname),
290 (long) tvc->fid.vnode);
294 dnlcstats.misses++; /* Is a dnlcread lock sufficient? */
298 sp->fid.vnode = tvc->fid.vnode;
299 sp->fid.unique = tvc->fid.unique;
301 lock_ReleaseRead(&cm_dnlcLock);
306 if ( cm_debugDnlc && tvc )
307 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
314 RemoveEntry (cm_nc_t *tnc, unsigned int key)
316 if (!tnc->prev) /* things on freelist always have null prev ptrs */
318 dnlcNotify("Bogus dnlc freelist", 1);
319 osi_Log0(afsd_logp,"Bogus dnlc freelist");
320 return 1; /* error */
323 if (tnc == tnc->next) /* only one in list */
324 cm_data.nameHash[key] = (cm_nc_t *) 0;
327 if (tnc == cm_data.nameHash[key])
328 cm_data.nameHash[key] = tnc->next;
329 tnc->prev->next = tnc->next;
330 tnc->next->prev = tnc->prev;
333 memset(tnc, 0, sizeof(cm_nc_t));
334 tnc->magic = CM_DNLC_MAGIC;
335 return 0; /* success */
340 cm_dnlcRemove (cm_scache_t *adp, char *aname)
342 unsigned int key, skey, error=0;
343 int found= 0, safety;
351 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
352 adp, osi_LogSaveString(afsd_logp,aname));
354 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
355 if (ts - aname >= CM_AFSNCNAMESIZE)
358 skey = key & (NHSIZE -1);
359 lock_ObtainWrite(&cm_dnlcLock);
362 for (tnc = cm_data.nameHash[skey], safety=0; tnc; safety++)
364 if ( (tnc->dirp == adp) && (tnc->key == key)
365 && !strcmp(tnc->name,aname) )
368 error = RemoveEntry(tnc, skey);
372 tnc->next = cm_data.ncfreelist; /* insert entry into freelist */
373 cm_data.ncfreelist = tnc;
374 found = 1; /* found at least one entry */
376 tnc = tmp; /* continue down the linked list */
378 else if (tnc->next == cm_data.nameHash[skey]) /* end of list */
382 if ( safety > NCSIZE )
385 lock_ReleaseWrite(&cm_dnlcLock);
387 dnlcNotify("DNLC cycle",1);
389 osi_Log0(afsd_logp, "DNLC cycle");
394 lock_ReleaseWrite(&cm_dnlcLock);
396 if (!found && !error && cm_debugDnlc)
397 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
403 /* remove anything pertaining to this directory */
405 cm_dnlcPurgedp (cm_scache_t *adp)
414 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
416 lock_ObtainWrite(&cm_dnlcLock);
419 for (i=0; i<NCSIZE && !err; i++)
421 if (cm_data.nameCache[i].dirp == adp )
423 if (cm_data.nameCache[i].prev) {
424 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
427 cm_data.nameCache[i].next = cm_data.ncfreelist;
428 cm_data.ncfreelist = &cm_data.nameCache[i];
431 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
435 lock_ReleaseWrite(&cm_dnlcLock);
440 /* remove anything pertaining to this file */
442 cm_dnlcPurgevp (cm_scache_t *avc)
451 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
453 lock_ObtainWrite(&cm_dnlcLock);
456 for (i=0; i<NCSIZE && !err ; i++)
458 if (cm_data.nameCache[i].vp == avc)
460 if (cm_data.nameCache[i].prev) {
461 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
464 cm_data.nameCache[i].next = cm_data.ncfreelist;
465 cm_data.ncfreelist = &cm_data.nameCache[i];
468 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
472 lock_ReleaseWrite(&cm_dnlcLock);
477 /* remove everything */
478 void cm_dnlcPurge(void)
486 osi_Log0(afsd_logp, "cm_dnlcPurge");
488 lock_ObtainWrite(&cm_dnlcLock);
491 cm_data.ncfreelist = (cm_nc_t *) 0;
492 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
493 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
494 for (i=0; i<NCSIZE; i++)
496 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
497 cm_data.nameCache[i].next = cm_data.ncfreelist;
498 cm_data.ncfreelist = &cm_data.nameCache[i];
500 lock_ReleaseWrite(&cm_dnlcLock);
504 /* remove everything referencing a specific volume */
505 /* is this function ever called? */
507 cm_dnlcPurgeVol(AFSFid *fidp)
513 dnlcstats.purgevols++;
518 cm_dnlcValidate(void)
524 // are all nameCache entries marked with the magic bit?
525 for (i=0; i<NCSIZE; i++)
527 if (cm_data.nameCache[i].magic != CM_DNLC_MAGIC) {
528 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC", i);
529 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC\n", i);
532 if (cm_data.nameCache[i].next &&
533 cm_data.nameCache[i].next->magic != CM_DNLC_MAGIC) {
534 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC", i);
535 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC\n", i);
538 if (cm_data.nameCache[i].prev &&
539 cm_data.nameCache[i].prev->magic != CM_DNLC_MAGIC) {
540 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC", i);
541 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC\n", i);
544 if (cm_data.nameCache[i].dirp &&
545 cm_data.nameCache[i].dirp->magic != CM_SCACHE_MAGIC) {
546 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC", i);
547 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC\n", i);
550 if (cm_data.nameCache[i].vp &&
551 cm_data.nameCache[i].vp->magic != CM_SCACHE_MAGIC) {
552 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC", i);
553 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC\n", i);
558 // are the contents of the hash table intact?
559 for (i=0; i<NHSIZE;i++) {
560 for (ncp = cm_data.nameHash[i]; ncp ;
561 ncp = ncp->next != cm_data.nameHash[i] ? ncp->next : NULL) {
562 if (ncp->magic != CM_DNLC_MAGIC) {
563 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
564 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
567 if (ncp->prev && ncp->prev->magic != CM_DNLC_MAGIC) {
568 afsi_log("cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC");
569 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC\n");
572 if (ncp->dirp && ncp->dirp->magic != CM_SCACHE_MAGIC) {
573 afsi_log("cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC");
574 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC\n");
577 if (ncp->vp && ncp->vp->magic != CM_SCACHE_MAGIC) {
578 afsi_log("cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC");
579 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC\n");
585 // is the freelist stable?
586 if ( cm_data.ncfreelist ) {
587 for (ncp = cm_data.ncfreelist, i = 0; ncp && i < NCSIZE;
588 ncp = ncp->next != cm_data.ncfreelist ? ncp->next : NULL, i++) {
589 if (ncp->magic != CM_DNLC_MAGIC) {
590 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
591 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
595 afsi_log("cm_dnlcValidate failure: ncp->prev != NULL");
596 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev != NULL\n");
600 afsi_log("cm_dnlcValidate failure: ncp->key != 0");
601 fprintf(stderr, "cm_dnlcValidate failure: ncp->key != 0\n");
605 afsi_log("cm_dnlcValidate failure: ncp->dirp != NULL");
606 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp != NULL\n");
610 afsi_log("cm_dnlcValidate failure: ncp->vp != NULL");
611 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp != NULL\n");
616 if ( i == NCSIZE && ncp ) {
617 afsi_log("cm_dnlcValidate failure: dnlc freeList corrupted");
618 fprintf(stderr, "cm_dnlcValidate failure: dnlc freeList corrupted\n");
628 afsi_log("cm_dnlcValidate information: purging");
629 fprintf(stderr, "cm_dnlcValidate information: purging\n");
630 cm_data.ncfreelist = (cm_nc_t *) 0;
631 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
632 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
633 for (i=0; i<NCSIZE; i++)
635 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
636 cm_data.nameCache[i].next = cm_data.ncfreelist;
637 cm_data.ncfreelist = &cm_data.nameCache[i];
644 cm_dnlcInit(int newFile)
652 osi_Log0(afsd_logp,"cm_dnlcInit");
654 memset (&dnlcstats, 0, sizeof(dnlcstats));
656 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
658 lock_ObtainWrite(&cm_dnlcLock);
659 cm_data.ncfreelist = (cm_nc_t *) 0;
660 cm_data.nameCache = cm_data.dnlcBaseAddress;
661 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
662 cm_data.nameHash = (cm_nc_t **) (cm_data.nameCache + NCSIZE);
663 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
665 for (i=0; i<NCSIZE; i++)
667 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
668 cm_data.nameCache[i].next = cm_data.ncfreelist;
669 cm_data.ncfreelist = &cm_data.nameCache[i];
671 lock_ReleaseWrite(&cm_dnlcLock);
676 cm_dnlcShutdown(void)
679 osi_Log0(afsd_logp,"cm_dnlcShutdown");