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 <afsconfig.h>
19 #include <afs/param.h>
30 #include <WINNT/afsreg.h>
32 osi_rwlock_t cm_dnlcLock;
34 static cm_dnlcstats_t dnlcstats; /* dnlc statistics */
35 static int cm_useDnlc = 1; /* yes, start using the dnlc */
36 static int cm_debugDnlc = 0; /* debug dnlc */
39 /* Hash table invariants:
40 * 1. If nameHash[i] is NULL, list is empty
41 * 2. A single element in a hash bucket has itself as prev and next.
44 /* Must be called with cm_dnlcLock write locked */
48 static unsigned int nameptr = 0; /* next bucket to pull something from */
52 if (cm_data.ncfreelist)
54 tnc = cm_data.ncfreelist;
55 cm_data.ncfreelist = tnc->next;
59 for (j=0; j<NHSIZE+2; j++, nameptr++)
61 if (nameptr >= NHSIZE)
63 if (cm_data.nameHash[nameptr])
67 tnc = cm_data.nameHash[nameptr];
70 osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
75 { /* only thing in list, don't screw around */
76 cm_data.nameHash[nameptr] = (cm_nc_t *) 0;
80 tnc = tnc->prev; /* grab oldest one in this bucket */
81 tnc->next->prev = tnc->prev;/* remove it from list */
82 tnc->prev->next = tnc->next;
88 InsertEntry(cm_nc_t *tnc)
91 key = tnc->key & (NHSIZE -1);
93 if (!cm_data.nameHash[key])
95 cm_data.nameHash[key] = tnc;
96 tnc->next = tnc->prev = tnc;
100 tnc->next = cm_data.nameHash[key];
101 tnc->prev = tnc->next->prev;
102 tnc->next->prev = tnc;
103 tnc->prev->next = tnc;
104 cm_data.nameHash[key] = tnc;
110 cm_dnlcEnter ( cm_scache_t *adp,
115 unsigned int key, skey, new=0;
116 normchar_t *ts = nname;
120 if (!cm_useDnlc || nname == NULL)
123 if (!cm_NormStrCmp(nname,_C(".")) || !cm_NormStrCmp(nname,_C("..")))
127 osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %S scache %x",
128 adp, osi_LogSaveStringW(afsd_logp,nname), avc);
130 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
131 if (ts - nname >= CM_AFSNCNAMESIZE)
133 skey = key & (NHSIZE -1);
135 InterlockedIncrement(&dnlcstats.enters);
136 lock_ObtainRead(&cm_dnlcLock);
138 for (tnc = cm_data.nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
139 if ((tnc->dirp == adp) && (!cm_NormStrCmp(tnc->name, nname)))
140 break; /* preexisting entry */
141 else if ( tnc->next == cm_data.nameHash[skey]) /* end of list */
146 else if (safety > NCSIZE)
148 InterlockedIncrement(&dnlcstats.cycles);
150 lock_ReleaseWrite(&cm_dnlcLock);
152 lock_ReleaseRead(&cm_dnlcLock);
155 osi_Log0(afsd_logp, "DNLC cycle");
162 if ( !writeLocked ) {
163 lock_ConvertRToW(&cm_dnlcLock);
167 new = 1; /* entry does not exist, we are creating a new entry*/
168 tnc = GetMeAnEntry();
175 memcpy (tnc->name, nname, (ts-nname+1)*sizeof(normchar_t)); /* include the NULL */
177 if ( new ) /* insert entry only if it is newly created */
182 lock_ReleaseWrite(&cm_dnlcLock);
184 lock_ReleaseRead(&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 normchar_t* nname = sp->nsearchNamep;
199 normchar_t *ts = nname;
200 cm_nc_t * tnc, * tnc_begin;
203 if (!cm_useDnlc || nname == NULL)
207 osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %S",
208 adp, osi_LogSaveStringW(afsd_logp,nname));
210 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
212 if (ts - nname >= CM_AFSNCNAMESIZE) {
213 InterlockedIncrement(&dnlcstats.lookups);
214 InterlockedIncrement(&dnlcstats.misses);
218 skey = key & (NHSIZE -1);
220 lock_ObtainRead(&cm_dnlcLock);
221 InterlockedIncrement(&dnlcstats.lookups);
224 tnc_begin = cm_data.nameHash[skey];
225 for ( tvc = (cm_scache_t *) NULL, tnc = tnc_begin, safety=0;
226 tnc; tnc = tnc->next, safety++ )
228 if (tnc->dirp == adp)
231 osi_Log1(afsd_logp,"Looking at [%S]",
232 osi_LogSaveStringW(afsd_logp,tnc->name));
234 if ( sp->caseFold ) /* case insensitive */
236 match = cm_NormStrCmpI(tnc->name, nname);
237 if ( !match ) /* something matches */
242 /* determine what type of match it is */
243 if ( !cm_NormStrCmp(tnc->name, nname))
249 osi_Log1(afsd_logp,"DNLC found exact match [%S]",
250 osi_LogSaveStringW(afsd_logp,tnc->name));
253 else if ( cm_NoneUpper(tnc->name))
255 else if ( cm_NoneLower(tnc->name))
259 /* Don't break here. We might find an exact match yet */
262 else /* case sensitive */
264 match = cm_NormStrCmp(tnc->name, nname);
265 if ( !match ) /* found a match */
274 if (tnc->next == cm_data.nameHash[skey])
278 else if (tnc->next == tnc_begin || safety > NCSIZE)
280 InterlockedIncrement(&dnlcstats.cycles);
281 lock_ReleaseRead(&cm_dnlcLock);
284 osi_Log0(afsd_logp, "DNLC cycle");
290 if(cm_debugDnlc && ts) {
291 osi_Log3(afsd_logp, "DNLC matched [%S] for [%W] with vnode[%ld]",
292 osi_LogSaveStringW(afsd_logp,ts),
293 osi_LogSaveStringW(afsd_logp,nname),
294 (long) tvc->fid.vnode);
298 InterlockedIncrement(&dnlcstats.misses);
302 sp->fid.vnode = tvc->fid.vnode;
303 sp->fid.unique = tvc->fid.unique;
305 lock_ReleaseRead(&cm_dnlcLock);
310 if ( cm_debugDnlc && tvc )
311 osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
318 RemoveEntry (cm_nc_t *tnc, unsigned int key)
320 if (!tnc->prev) /* things on freelist always have null prev ptrs */
322 osi_Log0(afsd_logp,"Bogus dnlc freelist");
323 return 1; /* error */
326 if (tnc == tnc->next) /* only one in list */
327 cm_data.nameHash[key] = (cm_nc_t *) 0;
330 if (tnc == cm_data.nameHash[key])
331 cm_data.nameHash[key] = tnc->next;
332 tnc->prev->next = tnc->next;
333 tnc->next->prev = tnc->prev;
336 memset(tnc, 0, sizeof(cm_nc_t));
337 tnc->magic = CM_DNLC_MAGIC;
338 return 0; /* success */
343 cm_dnlcRemove (cm_scache_t *adp, normchar_t *nname)
345 unsigned int key, skey, error=0;
346 int found= 0, safety;
347 normchar_t *ts = nname;
350 if (!cm_useDnlc || nname == NULL)
354 osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %S",
355 adp, osi_LogSaveStringW(afsd_logp,nname));
357 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
358 if (ts - nname >= CM_AFSNCNAMESIZE)
361 skey = key & (NHSIZE -1);
362 lock_ObtainWrite(&cm_dnlcLock);
363 InterlockedIncrement(&dnlcstats.removes);
365 for (tnc = cm_data.nameHash[skey], safety=0; tnc; safety++)
367 if ( (tnc->dirp == adp) && (tnc->key == key)
368 && !cm_NormStrCmp(tnc->name,nname) )
371 error = RemoveEntry(tnc, skey);
375 tnc->next = cm_data.ncfreelist; /* insert entry into freelist */
376 cm_data.ncfreelist = tnc;
377 found = 1; /* found at least one entry */
379 tnc = tmp; /* continue down the linked list */
381 else if (tnc->next == cm_data.nameHash[skey]) /* end of list */
385 if ( safety > NCSIZE )
387 InterlockedIncrement(&dnlcstats.cycles);
388 lock_ReleaseWrite(&cm_dnlcLock);
391 osi_Log0(afsd_logp, "DNLC cycle");
396 lock_ReleaseWrite(&cm_dnlcLock);
398 if (!found && !error && cm_debugDnlc)
399 osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
405 /* remove anything pertaining to this directory */
407 cm_dnlcPurgedp (cm_scache_t *adp)
416 osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
418 lock_ObtainWrite(&cm_dnlcLock);
419 InterlockedIncrement(&dnlcstats.purgeds);
421 for (i=0; i<NCSIZE && !err; i++)
423 if (cm_data.nameCache[i].dirp == adp )
425 if (cm_data.nameCache[i].prev) {
426 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
429 cm_data.nameCache[i].next = cm_data.ncfreelist;
430 cm_data.ncfreelist = &cm_data.nameCache[i];
433 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
437 lock_ReleaseWrite(&cm_dnlcLock);
442 /* remove anything pertaining to this file */
444 cm_dnlcPurgevp (cm_scache_t *avc)
453 osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
455 lock_ObtainWrite(&cm_dnlcLock);
456 InterlockedIncrement(&dnlcstats.purgevs);
458 for (i=0; i<NCSIZE && !err ; i++)
460 if (cm_data.nameCache[i].vp == avc)
462 if (cm_data.nameCache[i].prev) {
463 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
466 cm_data.nameCache[i].next = cm_data.ncfreelist;
467 cm_data.ncfreelist = &cm_data.nameCache[i];
470 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
474 lock_ReleaseWrite(&cm_dnlcLock);
479 /* remove everything */
480 void cm_dnlcPurge(void)
488 osi_Log0(afsd_logp, "cm_dnlcPurge");
490 lock_ObtainWrite(&cm_dnlcLock);
491 InterlockedIncrement(&dnlcstats.purges);
493 cm_data.ncfreelist = (cm_nc_t *) 0;
494 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
495 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
496 for (i=0; i<NCSIZE; i++)
498 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
499 cm_data.nameCache[i].next = cm_data.ncfreelist;
500 cm_data.ncfreelist = &cm_data.nameCache[i];
502 lock_ReleaseWrite(&cm_dnlcLock);
506 /* remove everything referencing a specific volume */
507 /* is this function ever called? */
509 cm_dnlcPurgeVol(AFSFid *fidp)
515 InterlockedIncrement(&dnlcstats.purgevols);
520 cm_dnlcValidate(void)
526 // are all nameCache entries marked with the magic bit?
527 for (i=0; i<NCSIZE; i++)
529 if (cm_data.nameCache[i].magic != CM_DNLC_MAGIC) {
530 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC", i);
531 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC\n", i);
534 if (cm_data.nameCache[i].next &&
535 cm_data.nameCache[i].next->magic != CM_DNLC_MAGIC) {
536 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC", i);
537 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC\n", i);
540 if (cm_data.nameCache[i].prev &&
541 cm_data.nameCache[i].prev->magic != CM_DNLC_MAGIC) {
542 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC", i);
543 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC\n", i);
546 if (cm_data.nameCache[i].dirp &&
547 cm_data.nameCache[i].dirp->magic != CM_SCACHE_MAGIC) {
548 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC", i);
549 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC\n", i);
552 if (cm_data.nameCache[i].vp &&
553 cm_data.nameCache[i].vp->magic != CM_SCACHE_MAGIC) {
554 afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC", i);
555 fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC\n", i);
560 // are the contents of the hash table intact?
561 for (i=0; i<NHSIZE;i++) {
562 for (ncp = cm_data.nameHash[i]; ncp ;
563 ncp = ncp->next != cm_data.nameHash[i] ? ncp->next : NULL) {
564 if (ncp->magic != CM_DNLC_MAGIC) {
565 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
566 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
569 if (ncp->prev && ncp->prev->magic != CM_DNLC_MAGIC) {
570 afsi_log("cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC");
571 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC\n");
574 if (ncp->dirp && ncp->dirp->magic != CM_SCACHE_MAGIC) {
575 afsi_log("cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC");
576 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC\n");
579 if (ncp->vp && ncp->vp->magic != CM_SCACHE_MAGIC) {
580 afsi_log("cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC");
581 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC\n");
587 // is the freelist stable?
588 if ( cm_data.ncfreelist ) {
589 for (ncp = cm_data.ncfreelist, i = 0; ncp && i < NCSIZE;
590 ncp = ncp->next != cm_data.ncfreelist ? ncp->next : NULL, i++) {
591 if (ncp->magic != CM_DNLC_MAGIC) {
592 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
593 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
597 afsi_log("cm_dnlcValidate failure: ncp->prev != NULL");
598 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev != NULL\n");
602 afsi_log("cm_dnlcValidate failure: ncp->key != 0");
603 fprintf(stderr, "cm_dnlcValidate failure: ncp->key != 0\n");
607 afsi_log("cm_dnlcValidate failure: ncp->dirp != NULL");
608 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp != NULL\n");
612 afsi_log("cm_dnlcValidate failure: ncp->vp != NULL");
613 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp != NULL\n");
618 if ( i == NCSIZE && ncp ) {
619 afsi_log("cm_dnlcValidate failure: dnlc freeList corrupted");
620 fprintf(stderr, "cm_dnlcValidate failure: dnlc freeList corrupted\n");
630 afsi_log("cm_dnlcValidate information: purging");
631 fprintf(stderr, "cm_dnlcValidate information: purging\n");
632 cm_data.ncfreelist = (cm_nc_t *) 0;
633 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
634 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
635 for (i=0; i<NCSIZE; i++)
637 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
638 cm_data.nameCache[i].next = cm_data.ncfreelist;
639 cm_data.ncfreelist = &cm_data.nameCache[i];
646 cm_dnlcInit(int newFile)
654 code = RegOpenKeyEx(HKEY_LOCAL_MACHINE, AFSREG_CLT_OPENAFS_SUBKEY,
655 0, KEY_QUERY_VALUE, &parmKey);
656 if (code == ERROR_SUCCESS) {
657 dummyLen = sizeof(DWORD);
658 code = RegQueryValueEx(parmKey, "UseDNLC", NULL, NULL,
659 (BYTE *) &dwValue, &dummyLen);
660 if (code == ERROR_SUCCESS)
661 cm_useDnlc = dwValue ? 1 : 0;
662 afsi_log("CM UseDNLC = %d", cm_useDnlc);
664 dummyLen = sizeof(DWORD);
665 code = RegQueryValueEx(parmKey, "DebugDNLC", NULL, NULL,
666 (BYTE *) &dwValue, &dummyLen);
667 if (code == ERROR_SUCCESS)
668 cm_debugDnlc = dwValue ? 1 : 0;
669 afsi_log("CM DebugDNLC = %d", cm_debugDnlc);
670 RegCloseKey (parmKey);
674 osi_Log0(afsd_logp,"cm_dnlcInit");
676 memset (&dnlcstats, 0, sizeof(dnlcstats));
678 lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock", LOCK_HIERARCHY_DNLC_GLOBAL);
680 lock_ObtainWrite(&cm_dnlcLock);
681 cm_data.ncfreelist = (cm_nc_t *) 0;
682 cm_data.nameCache = cm_data.dnlcBaseAddress;
683 memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
684 cm_data.nameHash = (cm_nc_t **) (cm_data.nameCache + NCSIZE);
685 memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
687 for (i=0; i<NCSIZE; i++)
689 cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
690 cm_data.nameCache[i].next = cm_data.ncfreelist;
691 cm_data.ncfreelist = &cm_data.nameCache[i];
693 lock_ReleaseWrite(&cm_dnlcLock);
698 cm_dnlcShutdown(void)
701 osi_Log0(afsd_logp,"cm_dnlcShutdown");