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