Remove incorrect critical section use in dnlc_lookup
[openafs.git] / src / afs / afs_osidnlc.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 #include <afsconfig.h>
11 #include "afs/param.h"
12
13
14 #include "afs/sysincludes.h"    /*Standard vendor system headers */
15 #include "afsincludes.h"        /*AFS-based standard headers */
16 #include "afs/afs.h"
17 #include "afs/lock.h"
18 #include "afs/afs_stats.h"
19 #include "afs/afs_osidnlc.h"
20
21 /* Things to do:
22  *    also cache failed lookups.
23  *    look into interactions of dnlc and readdir.
24  *    cache larger names, perhaps by using a better,longer key (SHA) and discarding
25  *    the actual name itself.
26  *    precompute a key and stuff for \sys, and combine the HandleAtName function with
27  *    this, since we're looking at the name anyway.  
28  */
29
30 struct afs_lock afs_xdnlc;
31 extern struct afs_lock afs_xvcache;
32
33 dnlcstats_t dnlcstats;
34
35 #define NCSIZE 300
36 #define NHSIZE 256              /* must be power of 2. == NHASHENT in dir package */
37 struct nc *ncfreelist = NULL;
38 static struct nc nameCache[NCSIZE];
39 struct nc *nameHash[NHSIZE];
40 /* Hash table invariants:
41  *     1.  If nameHash[i] is NULL, list is empty
42  *     2.  A single element in a hash bucket has itself as prev and next.
43  */
44
45 typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
46     ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
47     osi_dnlc_purgevpT, osi_dnlc_purgeT
48 } traceevt;
49
50 int afs_usednlc = 1;
51
52 struct dt {
53     traceevt event;
54     unsigned char slot;
55 };
56
57 struct dt dnlctracetable[256];
58 int dnlct;
59
60 #define TRACE(e,s)              /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
61
62 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173;  hval  += *ts;   }
63
64 static struct nc *
65 GetMeAnEntry(void)
66 {
67     static unsigned int nameptr = 0;    /* next bucket to pull something from */
68     struct nc *tnc;
69     int j;
70
71     if (ncfreelist) {
72         tnc = ncfreelist;
73         ncfreelist = tnc->next;
74         return tnc;
75     }
76
77     for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
78         if (nameptr >= NHSIZE)
79             nameptr = 0;
80         if (nameHash[nameptr])
81             break;
82     }
83
84     TRACE(ScavengeEntryT, nameptr);
85     tnc = nameHash[nameptr];
86     if (!tnc)                   /* May want to consider changing this to return 0 */
87         osi_Panic("null tnc in GetMeAnEntry");
88
89     if (tnc->prev == tnc) {     /* only thing in list, don't screw around */
90         nameHash[nameptr] = NULL;
91         return (tnc);
92     }
93
94     tnc = tnc->prev;            /* grab oldest one in this bucket */
95     /* remove it from list */
96     tnc->next->prev = tnc->prev;
97     tnc->prev->next = tnc->next;
98
99     return (tnc);
100 }
101
102 static void
103 InsertEntry(struct nc *tnc)
104 {
105     unsigned int key;
106     key = tnc->key & (NHSIZE - 1);
107
108     TRACE(InsertEntryT, key);
109     if (!nameHash[key]) {
110         nameHash[key] = tnc;
111         tnc->next = tnc->prev = tnc;
112     } else {
113         tnc->next = nameHash[key];
114         tnc->prev = tnc->next->prev;
115         tnc->next->prev = tnc;
116         tnc->prev->next = tnc;
117         nameHash[key] = tnc;
118     }
119 }
120
121
122 int
123 osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
124                afs_hyper_t * avno)
125 {
126     struct nc *tnc;
127     unsigned int key, skey;
128     char *ts = aname;
129     int safety;
130
131     if (!afs_usednlc)
132         return 0;
133
134     TRACE(osi_dnlc_enterT, 0);
135     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
136     if (ts - aname >= AFSNCNAMESIZE) {
137         return 0;
138     }
139     skey = key & (NHSIZE - 1);
140     dnlcstats.enters++;
141
142   retry:
143     ObtainWriteLock(&afs_xdnlc, 222);
144
145     /* Only cache entries from the latest version of the directory */
146     if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
147         ReleaseWriteLock(&afs_xdnlc);
148         return 0;
149     }
150
151     /*
152      * Make sure each directory entry gets cached no more than once.
153      */
154     for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
155         if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
156             /* duplicate entry */
157             break;
158         } else if (tnc->next == nameHash[skey]) {       /* end of list */
159             tnc = NULL;
160             break;
161         } else if (safety > NCSIZE) {
162             afs_warn("DNLC cycle");
163             dnlcstats.cycles++;
164             ReleaseWriteLock(&afs_xdnlc);
165             osi_dnlc_purge();
166             goto retry;
167         }
168     }
169
170     if (tnc == NULL) {
171         tnc = GetMeAnEntry();
172
173         tnc->dirp = adp;
174         tnc->vp = avc;
175         tnc->key = key;
176         memcpy((char *)tnc->name, aname, ts - aname + 1);       /* include the NULL */
177
178         InsertEntry(tnc);
179     } else {
180         /* duplicate */
181         tnc->vp = avc;
182     }
183     ReleaseWriteLock(&afs_xdnlc);
184
185     return 0;
186 }
187
188
189 struct vcache *
190 osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
191 {
192     struct vcache *tvc;
193     int LRUme;
194     unsigned int key, skey;
195     char *ts = aname;
196     struct nc *tnc, *tnc1 = 0;
197     int safety;
198 #ifdef AFS_DARWIN80_ENV
199     vnode_t tvp;
200 #endif
201
202     if (!afs_usednlc)
203       return 0;
204
205     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
206     if (ts - aname >= AFSNCNAMESIZE)
207       return 0;
208     skey = key & (NHSIZE - 1);
209
210     TRACE(osi_dnlc_lookupT, skey);
211     dnlcstats.lookups++;
212
213     ObtainReadLock(&afs_xvcache);
214     ObtainReadLock(&afs_xdnlc);
215
216     for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
217          tnc = tnc->next, safety++) {
218         if ( /* (tnc->key == key)  && */ (tnc->dirp == adp)
219             && (!strcmp((char *)tnc->name, aname))) {
220             tvc = tnc->vp;
221             tnc1 = tnc;
222             break;
223         } else if (tnc->next == nameHash[skey]) {       /* end of list */
224             break;
225         } else if (safety > NCSIZE) {
226             afs_warn("DNLC cycle");
227             dnlcstats.cycles++;
228             ReleaseReadLock(&afs_xdnlc);
229             ReleaseReadLock(&afs_xvcache);
230             osi_dnlc_purge();
231             return (0);
232         }
233     }
234
235     LRUme = 0;                  /* (tnc != nameHash[skey]); */
236     ReleaseReadLock(&afs_xdnlc);
237
238     if (!tvc) {
239         ReleaseReadLock(&afs_xvcache);
240         dnlcstats.misses++;
241     } else {
242         if ((tvc->f.states & CVInit)
243 #ifdef  AFS_DARWIN80_ENV
244             ||(tvc->f.states & CDeadVnode)
245 #endif
246             )      
247         {
248             ReleaseReadLock(&afs_xvcache);
249             dnlcstats.misses++;
250             osi_dnlc_remove(adp, aname, tvc);
251             return 0;
252         }
253 #if defined(AFS_DARWIN80_ENV)
254         tvp = AFSTOV(tvc);
255         if (vnode_get(tvp)) {
256             ReleaseReadLock(&afs_xvcache);
257             dnlcstats.misses++;
258             osi_dnlc_remove(adp, aname, tvc);
259             return 0;
260         }
261         if (vnode_ref(tvp)) {
262             ReleaseReadLock(&afs_xvcache);
263             AFS_GUNLOCK();
264             vnode_put(tvp);
265             AFS_GLOCK();
266             dnlcstats.misses++;
267             osi_dnlc_remove(adp, aname, tvc);
268             return 0;
269         }
270         osi_vnhold(tvc, 0);
271         ReleaseReadLock(&afs_xvcache);
272
273 #ifdef  notdef
274         /* 
275          * XX If LRUme ever is non-zero change the if statement around because
276          * aix's cc with optimizer on won't necessarily check things in order XX
277          */
278         if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
279             /* don't block to do this */
280             /* tnc might have been moved during race condition, */
281             /* but it's always in a legit hash chain when a lock is granted, 
282              * or else it's on the freelist so prev == NULL, 
283              * so at worst this is redundant */
284             /* Now that we've got it held, and a lock on the dnlc, we 
285              * should check to be sure that there was no race, and 
286              * bail out if there was. */
287             if (tnc->prev) {
288                 /* special case for only two elements on list - relative ordering
289                  * doesn't change */
290                 if (tnc->prev != tnc->next) {
291                     /* remove from old location */
292                     tnc->prev->next = tnc->next;
293                     tnc->next->prev = tnc->prev;
294                     /* insert into new location */
295                     tnc->next = nameHash[skey];
296                     tnc->prev = tnc->next->prev;
297                     tnc->next->prev = tnc;
298                     tnc->prev->next = tnc;
299                 }
300                 nameHash[skey] = tnc;
301             }
302             ReleaseWriteLock(&afs_xdnlc);
303         }
304 #endif
305     }
306
307     return tvc;
308 }
309
310
311 static void
312 RemoveEntry(struct nc *tnc, unsigned int key)
313 {
314     if (!tnc->prev)             /* things on freelist always have null prev ptrs */
315         osi_Panic("bogus free list");
316
317     TRACE(RemoveEntryT, key);
318     if (tnc == tnc->next) {     /* only one in list */
319         nameHash[key] = NULL;
320     } else {
321         if (tnc == nameHash[key])
322             nameHash[key] = tnc->next;
323         tnc->prev->next = tnc->next;
324         tnc->next->prev = tnc->prev;
325     }
326
327     tnc->prev = NULL;           /* everything not in hash table has 0 prev */
328     tnc->key = 0;               /* just for safety's sake */
329 }
330
331
332 int
333 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
334 {
335     unsigned int key, skey;
336     char *ts = aname;
337     struct nc *tnc;
338
339     if (!afs_usednlc)
340         return 0;
341
342     TRACE(osi_dnlc_removeT, skey);
343     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
344     if (ts - aname >= AFSNCNAMESIZE) {
345         return 0;
346     }
347     skey = key & (NHSIZE - 1);
348     TRACE(osi_dnlc_removeT, skey);
349     dnlcstats.removes++;
350     ObtainReadLock(&afs_xdnlc);
351
352     for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
353         if ((tnc->dirp == adp) && (tnc->key == key)
354             && (!strcmp((char *)tnc->name, aname))) {
355             tnc->dirp = NULL;   /* now it won't match anything */
356             break;
357         } else if (tnc->next == nameHash[skey]) {       /* end of list */
358             tnc = NULL;
359             break;
360         }
361     }
362     ReleaseReadLock(&afs_xdnlc);
363
364     if (!tnc)
365         return 0;
366
367     /* there is a little race condition here, but it's relatively
368      * harmless.  At worst, I wind up removing a mapping that I just
369      * created. */
370     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
371         return 0;               /* no big deal, tnc will get recycled eventually */
372     }
373     RemoveEntry(tnc, skey);
374     tnc->next = ncfreelist;
375     ncfreelist = tnc;
376     ReleaseWriteLock(&afs_xdnlc);
377
378     return 0;
379 }
380
381 /*! 
382  * Remove anything pertaining to this directory.  I can invalidate
383  * things without the lock, since I am just looking through the array,
384  * but to move things off the lists or into the freelist, I need the
385  * write lock 
386  *
387  * \param adp vcache entry for the directory to be purged.
388  * \return 0
389  */
390 int
391 osi_dnlc_purgedp(struct vcache *adp)
392 {
393     int i;
394     int writelocked;
395
396 #ifdef AFS_DARWIN_ENV
397     if (!(adp->f.states & (CVInit | CVFlushed
398 #ifdef AFS_DARWIN80_ENV
399                         | CDeadVnode
400 #endif
401         )) && AFSTOV(adp))
402     cache_purge(AFSTOV(adp));
403 #endif
404
405     if (!afs_usednlc)
406         return 0;
407
408     dnlcstats.purgeds++;
409     TRACE(osi_dnlc_purgedpT, 0);
410     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
411
412     for (i = 0; i < NCSIZE; i++) {
413         if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
414             nameCache[i].dirp = nameCache[i].vp = NULL;
415             if (writelocked && nameCache[i].prev) {
416                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
417                 nameCache[i].next = ncfreelist;
418                 ncfreelist = &nameCache[i];
419             }
420         }
421     }
422     if (writelocked)
423         ReleaseWriteLock(&afs_xdnlc);
424
425     return 0;
426 }
427
428 /*! 
429  * Remove anything pertaining to this file 
430  *
431  * \param File vcache entry.
432  * \return 0
433  */
434 int
435 osi_dnlc_purgevp(struct vcache *avc)
436 {
437     int i;
438     int writelocked;
439
440 #ifdef AFS_DARWIN_ENV
441     if (!(avc->f.states & (CVInit | CVFlushed
442 #ifdef AFS_DARWIN80_ENV
443                         | CDeadVnode
444 #endif
445         )) && AFSTOV(avc))
446     cache_purge(AFSTOV(avc));
447 #endif
448
449     if (!afs_usednlc)
450         return 0;
451
452     dnlcstats.purgevs++;
453     TRACE(osi_dnlc_purgevpT, 0);
454     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
455
456     for (i = 0; i < NCSIZE; i++) {
457         if ((nameCache[i].vp == avc)) {
458             nameCache[i].dirp = nameCache[i].vp = NULL;
459             /* can't simply break; because of hard links -- might be two */
460             /* different entries with same vnode */
461             if (writelocked && nameCache[i].prev) {
462                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
463                 nameCache[i].next = ncfreelist;
464                 ncfreelist = &nameCache[i];
465             }
466         }
467     }
468     if (writelocked)
469         ReleaseWriteLock(&afs_xdnlc);
470
471     return 0;
472 }
473
474 /* remove everything */
475 int
476 osi_dnlc_purge(void)
477 {
478     int i;
479
480     dnlcstats.purges++;
481     TRACE(osi_dnlc_purgeT, 0);
482     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) {      /* couldn't get lock */
483         for (i = 0; i < NCSIZE; i++)
484             nameCache[i].dirp = nameCache[i].vp = NULL;
485     } else {                    /* did get the lock */
486         ncfreelist = NULL;
487         memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
488         memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
489         for (i = 0; i < NCSIZE; i++) {
490             nameCache[i].next = ncfreelist;
491             ncfreelist = &nameCache[i];
492         }
493         ReleaseWriteLock(&afs_xdnlc);
494     }
495
496     return 0;
497 }
498
499 /* remove everything referencing a specific volume */
500 int
501 osi_dnlc_purgevol(struct VenusFid *fidp)
502 {
503
504     dnlcstats.purgevols++;
505     osi_dnlc_purge();
506
507     return 0;
508 }
509
510 int
511 osi_dnlc_init(void)
512 {
513     int i;
514
515     Lock_Init(&afs_xdnlc);
516     memset(&dnlcstats, 0, sizeof(dnlcstats));
517     memset(dnlctracetable, 0, sizeof(dnlctracetable));
518     dnlct = 0;
519     ObtainWriteLock(&afs_xdnlc, 223);
520     ncfreelist = NULL;
521     memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
522     memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
523     for (i = 0; i < NCSIZE; i++) {
524         nameCache[i].next = ncfreelist;
525         ncfreelist = &nameCache[i];
526     }
527     ReleaseWriteLock(&afs_xdnlc);
528
529     return 0;
530 }
531
532 int
533 osi_dnlc_shutdown(void)
534 {
535     return 0;
536 }