80eb8575a923447b59651b8779bd43175648a96b
[openafs.git] / src / WINNT / afsd / cm_dnlc.c
1 /*
2  * Copyright 2000, International Business Machines Corporation and others.
3  * All Rights Reserved.
4  * 
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
8  */
9
10 /*
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. 
15 **
16 */
17
18 #include <afs/param.h>
19 #include <afs/stds.h>
20
21 #include <windows.h>
22 #include <winsock2.h>
23 #include <string.h>
24 #include <stdlib.h>
25 #include <osi.h>
26 #include "afsd.h"
27
28 osi_rwlock_t cm_dnlcLock;
29
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 */
33
34
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.
38  */
39
40 /* Must be called with cm_dnlcLock write locked */
41 static cm_nc_t * 
42 GetMeAnEntry() 
43 {
44     static unsigned int nameptr = 0; /* next bucket to pull something from */
45     cm_nc_t *tnc;
46     int j;
47   
48     if (cm_data.ncfreelist) 
49     {
50         tnc = cm_data.ncfreelist;
51         cm_data.ncfreelist = tnc->next;
52         return tnc;
53     }
54
55     for (j=0; j<NHSIZE+2; j++, nameptr++) 
56     {
57         if (nameptr >= NHSIZE) 
58             nameptr =0;
59         if (cm_data.nameHash[nameptr])
60             break;
61     }
62
63     tnc = cm_data.nameHash[nameptr];
64     if (!tnc)   
65     {
66         osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
67         return 0;
68     }
69
70     if (tnc->prev == tnc) 
71     {                   /* only thing in list, don't screw around */
72         cm_data.nameHash[nameptr] = (cm_nc_t *) 0;
73         return (tnc);
74     }
75
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;
79
80     return (tnc);
81 }
82
83 static void 
84 InsertEntry(cm_nc_t *tnc)
85 {
86     unsigned int key; 
87     key = tnc->key & (NHSIZE -1);
88
89     if (!cm_data.nameHash[key]) 
90     {
91         cm_data.nameHash[key] = tnc;
92         tnc->next = tnc->prev = tnc;
93     }
94     else 
95     {
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;
101     }
102 }
103
104
105 void 
106 cm_dnlcEnter ( cm_scache_t *adp,
107                char        *aname,
108                cm_scache_t *avc )
109 {
110     cm_nc_t *tnc;
111     unsigned int key, skey, new=0;
112     char *ts = aname;
113     int safety;
114
115     if (!cm_useDnlc)
116         return ;
117   
118     if ( cm_debugDnlc ) 
119         osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %s scache %x", 
120             adp, osi_LogSaveString(afsd_logp,aname), avc);
121
122     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
123     if (ts - aname >= CM_AFSNCNAMESIZE) 
124         return ;
125     skey = key & (NHSIZE -1);
126
127     lock_ObtainWrite(&cm_dnlcLock);
128     dnlcstats.enters++;
129   
130     for (tnc = cm_data.nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
131         if ((tnc->dirp == adp) && (!strcmp(tnc->name, aname)))
132             break;                              /* preexisting entry */
133         else if ( tnc->next == cm_data.nameHash[skey])  /* end of list */
134         {
135             tnc = NULL;
136             break;
137         }
138         else if (safety > NCSIZE) 
139         {
140             dnlcstats.cycles++;
141             lock_ReleaseWrite(&cm_dnlcLock);
142
143             if ( cm_debugDnlc )
144                 osi_Log0(afsd_logp, "DNLC cycle");
145             cm_dnlcPurge();
146             return;
147         }
148         
149     if ( !tnc )
150     {
151         new = 1;        /* entry does not exist, we are creating a new entry*/
152         tnc = GetMeAnEntry();
153     }
154     if ( tnc )
155     { 
156         tnc->dirp = adp;
157         tnc->vp = avc;
158         tnc->key = key;
159         memcpy (tnc->name, aname, ts-aname+1); /* include the NULL */
160
161         if ( new )      /* insert entry only if it is newly created */ 
162                 InsertEntry(tnc);
163
164     }
165     lock_ReleaseWrite(&cm_dnlcLock);
166
167     if ( !tnc)
168         cm_dnlcPurge();
169 }
170
171 /*
172 * if the scache entry is found, return it held
173 */
174 cm_scache_t *
175 cm_dnlcLookup (cm_scache_t *adp, cm_lookupSearch_t* sp)
176 {
177     cm_scache_t * tvc;
178     unsigned int key, skey;
179     char* aname = sp->searchNamep;
180     char *ts = aname;
181     cm_nc_t * tnc, * tnc_begin;
182     int safety, match;
183   
184     if (!cm_useDnlc)
185         return 0;
186     if ( cm_debugDnlc ) 
187         osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %s", 
188                 adp, osi_LogSaveString(afsd_logp,aname));
189
190     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
191     if (ts - aname >= CM_AFSNCNAMESIZE) 
192         return 0;
193
194     skey = key & (NHSIZE -1);
195
196     lock_ObtainRead(&cm_dnlcLock);
197     dnlcstats.lookups++;             /* Is a dnlcread lock sufficient? */
198
199     ts = 0;
200     tnc_begin = cm_data.nameHash[skey];
201     for ( tvc = (cm_scache_t *) 0, tnc = tnc_begin, safety=0; 
202           tnc; tnc = tnc->next, safety++ ) 
203     {
204         if (tnc->dirp == adp) 
205         {
206         if( cm_debugDnlc ) 
207             osi_Log1(afsd_logp,"Looking at [%s]",
208                      osi_LogSaveString(afsd_logp,tnc->name));
209
210             if ( sp->caseFold )         /* case insensitive */
211             {
212             match = cm_stricmp(tnc->name, aname);
213             if ( !match )       /* something matches */
214             {
215                 tvc = tnc->vp;
216                 ts = tnc->name;
217
218                 /* determine what type of match it is */
219                 if ( !strcmp(tnc->name, aname))
220                 {       
221                     /* exact match. */
222                     sp->ExactFound = 1;
223
224                     if( cm_debugDnlc )
225                         osi_Log1(afsd_logp,"DNLC found exact match [%s]",
226                                  osi_LogSaveString(afsd_logp,tnc->name));
227                     break;
228                 }
229                 else if ( cm_NoneUpper(tnc->name))
230                     sp->LCfound = 1;
231                 else if ( cm_NoneLower(tnc->name))
232                     sp->UCfound = 1;
233                 else    
234                     sp->NCfound = 1;
235                 /* Don't break here. We might find an exact match yet */
236             }
237             }
238             else                        /* case sensitive */
239             {
240             match = strcmp(tnc->name, aname);
241             if ( !match ) /* found a match */
242             {
243                 sp->ExactFound = 1;
244                 tvc = tnc->vp; 
245                 ts = tnc->name;
246                 break;
247             }
248             }
249         }
250         if (tnc->next == cm_data.nameHash[skey]) 
251     {                   /* end of list */
252             break;
253         }
254         else if (tnc->next == tnc_begin || safety > NCSIZE) 
255         {
256             dnlcstats.cycles++;
257             lock_ReleaseRead(&cm_dnlcLock);
258
259             if ( cm_debugDnlc ) 
260                 osi_Log0(afsd_logp, "DNLC cycle"); 
261             cm_dnlcPurge();
262             return(0);
263         }
264     }
265
266     if(cm_debugDnlc && ts) {
267         osi_Log3(afsd_logp, "DNLC matched [%s] for [%s] with vnode[%ld]",
268                  osi_LogSaveString(afsd_logp,ts),
269                  osi_LogSaveString(afsd_logp,aname),
270                  (long) tvc->fid.vnode);
271     }
272
273     if (!tvc) 
274         dnlcstats.misses++;     /* Is a dnlcread lock sufficient? */
275     else 
276     {
277         sp->found = 1;
278         sp->fid.vnode  = tvc->fid.vnode; 
279         sp->fid.unique = tvc->fid.unique;       
280     }
281     lock_ReleaseRead(&cm_dnlcLock);
282
283     if (tvc)
284         cm_HoldSCache(tvc);
285
286     if ( cm_debugDnlc && tvc ) 
287         osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
288     
289     return tvc;
290 }
291
292
293 static int
294 RemoveEntry (cm_nc_t *tnc, unsigned int key)
295 {
296     if (!tnc->prev) /* things on freelist always have null prev ptrs */
297     {
298         osi_Log0(afsd_logp,"Bogus dnlc freelist");
299         return 1;   /* error */
300     }
301
302     if (tnc == tnc->next)  /* only one in list */
303         cm_data.nameHash[key] = (cm_nc_t *) 0;
304     else 
305     {
306         if (tnc == cm_data.nameHash[key])
307             cm_data.nameHash[key]  = tnc->next;
308         tnc->prev->next = tnc->next;
309         tnc->next->prev = tnc->prev;
310     }
311
312     memset(tnc, 0, sizeof(cm_nc_t));
313     tnc->magic = CM_DNLC_MAGIC;
314     return 0;     /* success */
315 }
316
317
318 void 
319 cm_dnlcRemove (cm_scache_t *adp, char *aname)
320 {
321     unsigned int key, skey, error=0;
322     int found= 0, safety;
323     char *ts = aname;
324     cm_nc_t *tnc, *tmp;
325   
326     if (!cm_useDnlc)
327         return ;
328
329     if ( cm_debugDnlc )
330         osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s", 
331                 adp, osi_LogSaveString(afsd_logp,aname));
332
333     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
334     if (ts - aname >= CM_AFSNCNAMESIZE) 
335         return ;
336
337     skey = key & (NHSIZE -1);
338     lock_ObtainWrite(&cm_dnlcLock);
339     dnlcstats.removes++;
340
341     for (tnc = cm_data.nameHash[skey], safety=0; tnc; safety++) 
342     {
343         if ( (tnc->dirp == adp) && (tnc->key == key) 
344                         && !strcmp(tnc->name,aname) )
345         {
346             tmp = tnc->next;
347             error = RemoveEntry(tnc, skey);
348             if ( error )
349                 break;
350
351             tnc->next = cm_data.ncfreelist; /* insert entry into freelist */
352             cm_data.ncfreelist = tnc;
353             found = 1;          /* found at least one entry */
354
355             tnc = tmp;          /* continue down the linked list */
356         }
357         else if (tnc->next == cm_data.nameHash[skey]) /* end of list */
358             break;
359         else
360             tnc = tnc->next;
361         if ( safety > NCSIZE )
362         {
363             dnlcstats.cycles++;
364             lock_ReleaseWrite(&cm_dnlcLock);
365
366             if ( cm_debugDnlc ) 
367                 osi_Log0(afsd_logp, "DNLC cycle"); 
368             cm_dnlcPurge();
369             return;
370         }
371     }
372     lock_ReleaseWrite(&cm_dnlcLock);
373
374     if (!found && !error && cm_debugDnlc)
375         osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
376
377     if ( error )
378         cm_dnlcPurge();
379 }
380
381 /* remove anything pertaining to this directory */
382 void 
383 cm_dnlcPurgedp (cm_scache_t *adp)
384 {
385     int i;
386     int err=0;
387
388     if (!cm_useDnlc)
389         return ;
390
391     if ( cm_debugDnlc )
392         osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
393
394     lock_ObtainWrite(&cm_dnlcLock);
395     dnlcstats.purgeds++;
396
397     for (i=0; i<NCSIZE && !err; i++) 
398     {
399         if (cm_data.nameCache[i].dirp == adp ) 
400         {
401             if (cm_data.nameCache[i].prev) {
402                 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
403                 if (!err)
404                 {
405                     cm_data.nameCache[i].next = cm_data.ncfreelist;
406                     cm_data.ncfreelist = &cm_data.nameCache[i];
407                 }
408             } else {
409                 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
410             }
411         }
412     }
413     lock_ReleaseWrite(&cm_dnlcLock);
414     if ( err )
415         cm_dnlcPurge();
416 }
417
418 /* remove anything pertaining to this file */
419 void 
420 cm_dnlcPurgevp (cm_scache_t *avc)
421 {
422     int i;
423     int err=0;
424
425     if (!cm_useDnlc)
426         return ;
427
428     if ( cm_debugDnlc )
429         osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
430
431     lock_ObtainWrite(&cm_dnlcLock);
432     dnlcstats.purgevs++;
433
434     for (i=0; i<NCSIZE && !err ; i++) 
435     {
436         if (cm_data.nameCache[i].vp == avc) 
437         {
438             if (cm_data.nameCache[i].prev) {
439                 err = RemoveEntry(&cm_data.nameCache[i], cm_data.nameCache[i].key & (NHSIZE-1));
440                 if (!err)
441                 {
442                     cm_data.nameCache[i].next = cm_data.ncfreelist;
443                     cm_data.ncfreelist = &cm_data.nameCache[i];
444                 }
445             } else {
446                 cm_data.nameCache[i].dirp = cm_data.nameCache[i].vp = (cm_scache_t *) 0;
447             }
448         }
449     }
450     lock_ReleaseWrite(&cm_dnlcLock);
451     if ( err )
452         cm_dnlcPurge();
453 }
454
455 /* remove everything */
456 void cm_dnlcPurge(void)
457 {
458     int i;
459
460     if (!cm_useDnlc)
461         return ;
462
463     if ( cm_debugDnlc )
464         osi_Log0(afsd_logp, "cm_dnlcPurge");
465
466     lock_ObtainWrite(&cm_dnlcLock);
467     dnlcstats.purges++;
468     
469     cm_data.ncfreelist = (cm_nc_t *) 0;
470     memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
471     memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
472     for (i=0; i<NCSIZE; i++)
473     {
474         cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
475         cm_data.nameCache[i].next = cm_data.ncfreelist;
476         cm_data.ncfreelist = &cm_data.nameCache[i];
477     }
478     lock_ReleaseWrite(&cm_dnlcLock);
479    
480 }
481
482 /* remove everything referencing a specific volume */
483 /* is this function ever called? */
484 void
485 cm_dnlcPurgeVol(AFSFid *fidp)
486 {
487
488     if (!cm_useDnlc)
489         return ;
490
491     dnlcstats.purgevols++;
492     cm_dnlcPurge();
493 }
494
495 long
496 cm_dnlcValidate(void)
497 {
498     int i, purged = 0;
499     cm_nc_t * ncp;
500
501   retry:
502     // are all nameCache entries marked with the magic bit?
503     for (i=0; i<NCSIZE; i++)
504     {
505         if (cm_data.nameCache[i].magic != CM_DNLC_MAGIC) {
506             afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC", i);
507             fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].magic != CM_DNLC_MAGIC\n", i);
508             goto purge;
509         }
510         if (cm_data.nameCache[i].next &&
511             cm_data.nameCache[i].next->magic != CM_DNLC_MAGIC) {
512             afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC", i);
513             fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].next->magic != CM_DNLC_MAGIC\n", i);
514             goto purge;
515         }
516         if (cm_data.nameCache[i].prev &&
517             cm_data.nameCache[i].prev->magic != CM_DNLC_MAGIC) {
518             afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC", i);
519             fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].prev->magic != CM_DNLC_MAGIC\n", i);
520             goto purge;
521         }
522         if (cm_data.nameCache[i].dirp &&
523             cm_data.nameCache[i].dirp->magic != CM_SCACHE_MAGIC) {
524             afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC", i);
525             fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].dirp->magic != CM_SCACHE_MAGIC\n", i);
526             goto purge;
527         }
528         if (cm_data.nameCache[i].vp &&
529             cm_data.nameCache[i].vp->magic != CM_SCACHE_MAGIC) {
530             afsi_log("cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC", i);
531             fprintf(stderr, "cm_dnlcValidate failure: cm_data.nameCache[%d].vp->magic != CM_SCACHE_MAGIC\n", i);
532             goto purge;
533         }
534     }
535
536     // are the contents of the hash table intact?
537     for (i=0; i<NHSIZE;i++) {
538         for (ncp = cm_data.nameHash[i]; ncp ; 
539              ncp = ncp->next != cm_data.nameHash[i] ? ncp->next : NULL) {
540             if (ncp->magic != CM_DNLC_MAGIC) {
541                 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
542                 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
543                 goto purge;
544             }
545             if (ncp->prev && ncp->prev->magic != CM_DNLC_MAGIC) {
546                 afsi_log("cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC");
547                 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev->magic != CM_DNLC_MAGIC\n");
548                 goto purge;
549             }
550             if (ncp->dirp && ncp->dirp->magic != CM_SCACHE_MAGIC) {
551                 afsi_log("cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC");
552                 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp->magic != CM_DNLC_MAGIC\n");
553                 goto purge;
554             }
555             if (ncp->vp && ncp->vp->magic != CM_SCACHE_MAGIC) {
556                 afsi_log("cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC");
557                 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp->magic != CM_DNLC_MAGIC\n");
558                 goto purge;
559             }
560         }
561     }
562
563     // is the freelist stable?
564     if ( cm_data.ncfreelist ) {
565         for (ncp = cm_data.ncfreelist, i = 0; ncp && i < NCSIZE; 
566              ncp = ncp->next != cm_data.ncfreelist ? ncp->next : NULL, i++) {
567             if (ncp->magic != CM_DNLC_MAGIC) {
568                 afsi_log("cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC");
569                 fprintf(stderr, "cm_dnlcValidate failure: ncp->magic != CM_DNLC_MAGIC\n");
570                 goto purge;
571             }
572             if (ncp->prev) {
573                 afsi_log("cm_dnlcValidate failure: ncp->prev != NULL");
574                 fprintf(stderr, "cm_dnlcValidate failure: ncp->prev != NULL\n");
575                 goto purge;
576             }
577             if (ncp->key) {
578                 afsi_log("cm_dnlcValidate failure: ncp->key != 0");
579                 fprintf(stderr, "cm_dnlcValidate failure: ncp->key != 0\n");
580                 goto purge;
581             }
582             if (ncp->dirp) {
583                 afsi_log("cm_dnlcValidate failure: ncp->dirp != NULL");
584                 fprintf(stderr, "cm_dnlcValidate failure: ncp->dirp != NULL\n");
585                goto purge;
586             }
587             if (ncp->vp) {
588                 afsi_log("cm_dnlcValidate failure: ncp->vp != NULL");
589                 fprintf(stderr, "cm_dnlcValidate failure: ncp->vp != NULL\n");
590                 goto purge;
591             }
592         }
593
594         if ( i == NCSIZE && ncp ) {
595             afsi_log("cm_dnlcValidate failure: dnlc freeList corrupted");
596             fprintf(stderr, "cm_dnlcValidate failure: dnlc freeList corrupted\n");
597             goto purge;
598         }
599     }
600     return 0;
601
602   purge:
603     if ( purged )
604         return -1;
605
606     afsi_log("cm_dnlcValidate information: purging");
607     fprintf(stderr, "cm_dnlcValidate information: purging\n");
608     cm_data.ncfreelist = (cm_nc_t *) 0;
609     memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
610     memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
611     for (i=0; i<NCSIZE; i++)
612     {
613         cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
614         cm_data.nameCache[i].next = cm_data.ncfreelist;
615         cm_data.ncfreelist = &cm_data.nameCache[i];
616     }
617     purged = 1;
618     goto retry;
619 }
620
621 void 
622 cm_dnlcInit(int newFile)
623 {
624     int i;
625
626     if (!cm_useDnlc)
627         return ;
628
629     if ( cm_debugDnlc )
630         osi_Log0(afsd_logp,"cm_dnlcInit");
631
632     memset (&dnlcstats, 0, sizeof(dnlcstats));
633
634     lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
635     if ( newFile ) {
636         lock_ObtainWrite(&cm_dnlcLock);
637         cm_data.ncfreelist = (cm_nc_t *) 0;
638         cm_data.nameCache = cm_data.dnlcBaseAddress;
639         memset (cm_data.nameCache, 0, sizeof(cm_nc_t) * NCSIZE);
640         cm_data.nameHash = (cm_nc_t **) (cm_data.nameCache + NCSIZE);
641         memset (cm_data.nameHash, 0, sizeof(cm_nc_t *) * NHSIZE);
642     
643         for (i=0; i<NCSIZE; i++)
644         {
645             cm_data.nameCache[i].magic = CM_DNLC_MAGIC;
646             cm_data.nameCache[i].next = cm_data.ncfreelist;
647             cm_data.ncfreelist = &cm_data.nameCache[i];
648         }
649         lock_ReleaseWrite(&cm_dnlcLock);
650     }
651 }
652
653 long 
654 cm_dnlcShutdown(void)
655 {
656     if ( cm_debugDnlc )
657         osi_Log0(afsd_logp,"cm_dnlcShutdown");
658
659     return 0;
660 }