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