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>
27 #include <WINNT/afsreg.h>
29 osi_rwlock_t cm_dnlcLock;
31 static cm_dnlcstats_t dnlcstats; /* dnlc statistics */
32 static int cm_useDnlc = 1; /* yes, start using the dnlc */
33 static int cm_debugDnlc = 0; /* debug dnlc */
36 /* Hash table invariants:
37 * 1. If nameHash[i] is NULL, list is empty
38 * 2. A single element in a hash bucket has itself as prev and next.
41 /* Must be called with cm_dnlcLock write locked */
45 static unsigned int nameptr = 0; /* next bucket to pull something from */
49 if (cm_data.ncfreelist)
51 tnc = cm_data.ncfreelist;
52 cm_data.ncfreelist = tnc->next;
56 for (j=0; j<NHSIZE+2; j++, nameptr++)
58 if (nameptr >= NHSIZE)
60 if (cm_data.nameHash[nameptr])
64 tnc = cm_data.nameHash[nameptr];
67 osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
72 { /* only thing in list, don't screw around */
73 cm_data.nameHash[nameptr] = (cm_nc_t *) 0;
77 tnc = tnc->prev; /* grab oldest one in this bucket */
78 tnc->next->prev = tnc->prev;/* remove it from list */
79 tnc->prev->next = tnc->next;
85 InsertEntry(cm_nc_t *tnc)
88 key = tnc->key & (NHSIZE -1);
90 if (!cm_data.nameHash[key])
92 cm_data.nameHash[key] = tnc;
93 tnc->next = tnc->prev = tnc;
97 tnc->next = cm_data.nameHash[key];
98 tnc->prev = tnc->next->prev;
99 tnc->next->prev = tnc;
100 tnc->prev->next = tnc;
101 cm_data.nameHash[key] = tnc;
107 cm_dnlcEnter ( cm_scache_t *adp,
112 unsigned int key, skey, new=0;
113 normchar_t *ts = nname;
120 if (!cm_NormStrCmp(nname,_C(".")) || !cm_NormStrCmp(nname,_C("..")))
124 osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %S scache %x",
125 adp, osi_LogSaveStringW(afsd_logp,nname), avc);
127 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
128 if (ts - nname >= CM_AFSNCNAMESIZE)
130 skey = key & (NHSIZE -1);
132 InterlockedIncrement(&dnlcstats.enters);
133 lock_ObtainRead(&cm_dnlcLock);
135 for (tnc = cm_data.nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
136 if ((tnc->dirp == adp) && (!cm_NormStrCmp(tnc->name, nname)))
137 break; /* preexisting entry */
138 else if ( tnc->next == cm_data.nameHash[skey]) /* end of list */
143 else if (safety > NCSIZE)
145 InterlockedIncrement(&dnlcstats.cycles);
147 lock_ReleaseWrite(&cm_dnlcLock);
149 lock_ReleaseRead(&cm_dnlcLock);
152 osi_Log0(afsd_logp, "DNLC cycle");
159 if ( !writeLocked ) {
160 lock_ConvertRToW(&cm_dnlcLock);
164 new = 1; /* entry does not exist, we are creating a new entry*/
165 tnc = GetMeAnEntry();
172 memcpy (tnc->name, nname, (ts-nname+1)*sizeof(normchar_t)); /* include the NULL */
174 if ( new ) /* insert entry only if it is newly created */
179 lock_ReleaseWrite(&cm_dnlcLock);
181 lock_ReleaseRead(&cm_dnlcLock);
188 * if the scache entry is found, return it held
191 cm_dnlcLookup (cm_scache_t *adp, cm_lookupSearch_t* sp)
194 unsigned int key, skey;
195 normchar_t* nname = sp->nsearchNamep;
196 normchar_t *ts = nname;
197 cm_nc_t * tnc, * tnc_begin;
204 osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %S",
205 adp, osi_LogSaveStringW(afsd_logp,nname));
207 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
209 if (ts - nname >= CM_AFSNCNAMESIZE) {
210 InterlockedIncrement(&dnlcstats.lookups);
211 InterlockedIncrement(&dnlcstats.misses);
215 skey = key & (NHSIZE -1);
217 lock_ObtainRead(&cm_dnlcLock);
218 InterlockedIncrement(&dnlcstats.lookups);
221 tnc_begin = cm_data.nameHash[skey];
222 for ( tvc = (cm_scache_t *) NULL, tnc = tnc_begin, safety=0;
223 tnc; tnc = tnc->next, safety++ )
225 if (tnc->dirp == adp)
228 osi_Log1(afsd_logp,"Looking at [%S]",
229 osi_LogSaveStringW(afsd_logp,tnc->name));
231 if ( sp->caseFold ) /* case insensitive */
233 match = cm_NormStrCmpI(tnc->name, nname);
234 if ( !match ) /* something matches */
239 /* determine what type of match it is */
240 if ( !cm_NormStrCmp(tnc->name, nname))
246 osi_Log1(afsd_logp,"DNLC found exact match [%S]",
247 osi_LogSaveStringW(afsd_logp,tnc->name));
250 else if ( cm_NoneUpper(tnc->name))
252 else if ( cm_NoneLower(tnc->name))
256 /* Don't break here. We might find an exact match yet */
259 else /* case sensitive */
261 match = cm_NormStrCmp(tnc->name, nname);
262 if ( !match ) /* found a match */
271 if (tnc->next == cm_data.nameHash[skey])
275 else if (tnc->next == tnc_begin || safety > NCSIZE)
277 InterlockedIncrement(&dnlcstats.cycles);
278 lock_ReleaseRead(&cm_dnlcLock);
281 osi_Log0(afsd_logp, "DNLC cycle");
287 if(cm_debugDnlc && ts) {
288 osi_Log3(afsd_logp, "DNLC matched [%S] for [%W] with vnode[%ld]",
289 osi_LogSaveStringW(afsd_logp,ts),
290 osi_LogSaveStringW(afsd_logp,nname),
291 (long) tvc->fid.vnode);
295 InterlockedIncrement(&dnlcstats.misses);
299 sp->fid.vnode = tvc->fid.vnode;
300 sp->fid.unique = tvc->fid.unique;
302 lock_ReleaseRead(&cm_dnlcLock);
307 if ( cm_debugDnlc && tvc )
308 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
315 RemoveEntry (cm_nc_t *tnc, unsigned int key)
317 if (!tnc->prev) /* things on freelist always have null prev ptrs */
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, normchar_t *nname)
342 unsigned int key, skey, error=0;
343 int found= 0, safety;
344 normchar_t *ts = nname;
351 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %S",
352 adp, osi_LogSaveStringW(afsd_logp,nname));
354 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
355 if (ts - nname >= CM_AFSNCNAMESIZE)
358 skey = key & (NHSIZE -1);
359 lock_ObtainWrite(&cm_dnlcLock);
360 InterlockedIncrement(&dnlcstats.removes);
362 for (tnc = cm_data.nameHash[skey], safety=0; tnc; safety++)
364 if ( (tnc->dirp == adp) && (tnc->key == key)
365 && !cm_NormStrCmp(tnc->name,nname) )
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 )
384 InterlockedIncrement(&dnlcstats.cycles);
385 lock_ReleaseWrite(&cm_dnlcLock);
388 osi_Log0(afsd_logp, "DNLC cycle");
393 lock_ReleaseWrite(&cm_dnlcLock);
395 if (!found && !error && cm_debugDnlc)
396 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
402 /* remove anything pertaining to this directory */
404 cm_dnlcPurgedp (cm_scache_t *adp)
413 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
415 lock_ObtainWrite(&cm_dnlcLock);
416 InterlockedIncrement(&dnlcstats.purgeds);
418 for (i=0; i<NCSIZE && !err; i++)
420 if (cm_data.nameCache[i].dirp == adp )
422 if (cm_data.nameCache[i].prev) {
423 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
426 cm_data.nameCache[i].next = cm_data.ncfreelist;
427 cm_data.ncfreelist = &cm_data.nameCache[i];
430 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
434 lock_ReleaseWrite(&cm_dnlcLock);
439 /* remove anything pertaining to this file */
441 cm_dnlcPurgevp (cm_scache_t *avc)
450 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
452 lock_ObtainWrite(&cm_dnlcLock);
453 InterlockedIncrement(&dnlcstats.purgevs);
455 for (i=0; i<NCSIZE && !err ; i++)
457 if (cm_data.nameCache[i].vp == avc)
459 if (cm_data.nameCache[i].prev) {
460 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
463 cm_data.nameCache[i].next = cm_data.ncfreelist;
464 cm_data.ncfreelist = &cm_data.nameCache[i];
467 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
471 lock_ReleaseWrite(&cm_dnlcLock);
476 /* remove everything */
477 void cm_dnlcPurge(void)
485 osi_Log0(afsd_logp, "cm_dnlcPurge");
487 lock_ObtainWrite(&cm_dnlcLock);
488 InterlockedIncrement(&dnlcstats.purges);
490 cm_data.ncfreelist = (cm_nc_t *) 0;
491 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
492 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
493 for (i=0; i<NCSIZE; i++)
495 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
496 cm_data.nameCache[i].next = cm_data.ncfreelist;
497 cm_data.ncfreelist = &cm_data.nameCache[i];
499 lock_ReleaseWrite(&cm_dnlcLock);
503 /* remove everything referencing a specific volume */
504 /* is this function ever called? */
506 cm_dnlcPurgeVol(AFSFid *fidp)
512 InterlockedIncrement(&dnlcstats.purgevols);
517 cm_dnlcValidate(void)
523 // are all nameCache entries marked with the magic bit?
524 for (i=0; i<NCSIZE; i++)
526 if (cm_data.nameCache[i].magic != CM_DNLC_MAGIC) {
527 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC", i);
528 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC\n", i);
531 if (cm_data.nameCache[i].next &&
532 cm_data.nameCache[i].next->magic != CM_DNLC_MAGIC) {
533 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC", i);
534 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC\n", i);
537 if (cm_data.nameCache[i].prev &&
538 cm_data.nameCache[i].prev->magic != CM_DNLC_MAGIC) {
539 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC", i);
540 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC\n", i);
543 if (cm_data.nameCache[i].dirp &&
544 cm_data.nameCache[i].dirp->magic != CM_SCACHE_MAGIC) {
545 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC", i);
546 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC\n", i);
549 if (cm_data.nameCache[i].vp &&
550 cm_data.nameCache[i].vp->magic != CM_SCACHE_MAGIC) {
551 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC", i);
552 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC\n", i);
557 // are the contents of the hash table intact?
558 for (i=0; i<NHSIZE;i++) {
559 for (ncp = cm_data.nameHash[i]; ncp ;
560 ncp = ncp->next != cm_data.nameHash[i] ? ncp->next : NULL) {
561 if (ncp->magic != CM_DNLC_MAGIC) {
562 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
563 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
566 if (ncp->prev && ncp->prev->magic != CM_DNLC_MAGIC) {
567 afsi_log("cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC");
568 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC\n");
571 if (ncp->dirp && ncp->dirp->magic != CM_SCACHE_MAGIC) {
572 afsi_log("cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC");
573 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC\n");
576 if (ncp->vp && ncp->vp->magic != CM_SCACHE_MAGIC) {
577 afsi_log("cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC");
578 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC\n");
584 // is the freelist stable?
585 if ( cm_data.ncfreelist ) {
586 for (ncp = cm_data.ncfreelist, i = 0; ncp && i < NCSIZE;
587 ncp = ncp->next != cm_data.ncfreelist ? ncp->next : NULL, i++) {
588 if (ncp->magic != CM_DNLC_MAGIC) {
589 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
590 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
594 afsi_log("cm_dnlcValidate failure: ncp->prev != NULL");
595 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev != NULL\n");
599 afsi_log("cm_dnlcValidate failure: ncp->key != 0");
600 fprintf(stderr, "cm_dnlcValidate failure: ncp->key != 0\n");
604 afsi_log("cm_dnlcValidate failure: ncp->dirp != NULL");
605 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp != NULL\n");
609 afsi_log("cm_dnlcValidate failure: ncp->vp != NULL");
610 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp != NULL\n");
615 if ( i == NCSIZE && ncp ) {
616 afsi_log("cm_dnlcValidate failure: dnlc freeList corrupted");
617 fprintf(stderr, "cm_dnlcValidate failure: dnlc freeList corrupted\n");
627 afsi_log("cm_dnlcValidate information: purging");
628 fprintf(stderr, "cm_dnlcValidate information: purging\n");
629 cm_data.ncfreelist = (cm_nc_t *) 0;
630 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
631 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
632 for (i=0; i<NCSIZE; i++)
634 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
635 cm_data.nameCache[i].next = cm_data.ncfreelist;
636 cm_data.ncfreelist = &cm_data.nameCache[i];
643 cm_dnlcInit(int newFile)
651 code = RegOpenKeyEx(HKEY_LOCAL_MACHINE, AFSREG_CLT_OPENAFS_SUBKEY,
652 0, KEY_QUERY_VALUE, &parmKey);
653 if (code == ERROR_SUCCESS) {
654 dummyLen = sizeof(DWORD);
655 code = RegQueryValueEx(parmKey, "UseDNLC", NULL, NULL,
656 (BYTE *) &dwValue, &dummyLen);
657 if (code == ERROR_SUCCESS)
658 cm_useDnlc = dwValue ? 1 : 0;
659 afsi_log("CM UseDNLC = %d", cm_useDnlc);
661 dummyLen = sizeof(DWORD);
662 code = RegQueryValueEx(parmKey, "DebugDNLC", NULL, NULL,
663 (BYTE *) &dwValue, &dummyLen);
664 if (code == ERROR_SUCCESS)
665 cm_debugDnlc = dwValue ? 1 : 0;
666 afsi_log("CM DebugDNLC = %d", cm_debugDnlc);
667 RegCloseKey (parmKey);
671 osi_Log0(afsd_logp,"cm_dnlcInit");
673 memset (&dnlcstats, 0, sizeof(dnlcstats));
675 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
677 lock_ObtainWrite(&cm_dnlcLock);
678 cm_data.ncfreelist = (cm_nc_t *) 0;
679 cm_data.nameCache = cm_data.dnlcBaseAddress;
680 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
681 cm_data.nameHash = (cm_nc_t **) (cm_data.nameCache + NCSIZE);
682 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
684 for (i=0; i<NCSIZE; i++)
686 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
687 cm_data.nameCache[i].next = cm_data.ncfreelist;
688 cm_data.ncfreelist = &cm_data.nameCache[i];
690 lock_ReleaseWrite(&cm_dnlcLock);
695 cm_dnlcShutdown(void)
698 osi_Log0(afsd_logp,"cm_dnlcShutdown");