Unix CM: Purge needless brackets
[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     unsigned int key, skey;
194     char *ts = aname;
195     struct nc *tnc;
196     int safety;
197 #ifdef AFS_DARWIN80_ENV
198     vnode_t tvp;
199 #endif
200
201     if (!afs_usednlc)
202       return 0;
203
204     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
205     if (ts - aname >= AFSNCNAMESIZE)
206       return 0;
207     skey = key & (NHSIZE - 1);
208
209     TRACE(osi_dnlc_lookupT, skey);
210     dnlcstats.lookups++;
211
212     ObtainReadLock(&afs_xvcache);
213     ObtainReadLock(&afs_xdnlc);
214
215     for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
216          tnc = tnc->next, safety++) {
217         if ( /* (tnc->key == key)  && */ (tnc->dirp == adp)
218             && (!strcmp((char *)tnc->name, aname))) {
219             tvc = tnc->vp;
220             break;
221         } else if (tnc->next == nameHash[skey]) {       /* end of list */
222             break;
223         } else if (safety > NCSIZE) {
224             afs_warn("DNLC cycle");
225             dnlcstats.cycles++;
226             ReleaseReadLock(&afs_xdnlc);
227             ReleaseReadLock(&afs_xvcache);
228             osi_dnlc_purge();
229             return (0);
230         }
231     }
232
233     ReleaseReadLock(&afs_xdnlc);
234
235     if (!tvc) {
236         ReleaseReadLock(&afs_xvcache);
237         dnlcstats.misses++;
238     } else {
239         if ((tvc->f.states & CVInit)
240 #ifdef  AFS_DARWIN80_ENV
241             ||(tvc->f.states & CDeadVnode)
242 #endif
243             )
244         {
245             ReleaseReadLock(&afs_xvcache);
246             dnlcstats.misses++;
247             osi_dnlc_remove(adp, aname, tvc);
248             return 0;
249         }
250 #if defined(AFS_DARWIN80_ENV)
251         tvp = AFSTOV(tvc);
252         if (vnode_get(tvp)) {
253             ReleaseReadLock(&afs_xvcache);
254             dnlcstats.misses++;
255             osi_dnlc_remove(adp, aname, tvc);
256             return 0;
257         }
258         if (vnode_ref(tvp)) {
259             ReleaseReadLock(&afs_xvcache);
260             AFS_GUNLOCK();
261             vnode_put(tvp);
262             AFS_GLOCK();
263             dnlcstats.misses++;
264             osi_dnlc_remove(adp, aname, tvc);
265             return 0;
266         }
267 #else
268         osi_vnhold(tvc, 0);
269 #endif
270         ReleaseReadLock(&afs_xvcache);
271
272     }
273
274     return tvc;
275 }
276
277
278 static void
279 RemoveEntry(struct nc *tnc, unsigned int key)
280 {
281     if (!tnc->prev)             /* things on freelist always have null prev ptrs */
282         osi_Panic("bogus free list");
283
284     TRACE(RemoveEntryT, key);
285     if (tnc == tnc->next) {     /* only one in list */
286         nameHash[key] = NULL;
287     } else {
288         if (tnc == nameHash[key])
289             nameHash[key] = tnc->next;
290         tnc->prev->next = tnc->next;
291         tnc->next->prev = tnc->prev;
292     }
293
294     tnc->prev = NULL;           /* everything not in hash table has 0 prev */
295     tnc->key = 0;               /* just for safety's sake */
296 }
297
298
299 int
300 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
301 {
302     unsigned int key, skey;
303     char *ts = aname;
304     struct nc *tnc;
305
306     if (!afs_usednlc)
307         return 0;
308
309     TRACE(osi_dnlc_removeT, skey);
310     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
311     if (ts - aname >= AFSNCNAMESIZE) {
312         return 0;
313     }
314     skey = key & (NHSIZE - 1);
315     TRACE(osi_dnlc_removeT, skey);
316     dnlcstats.removes++;
317     ObtainReadLock(&afs_xdnlc);
318
319     for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
320         if ((tnc->dirp == adp) && (tnc->key == key)
321             && (!strcmp((char *)tnc->name, aname))) {
322             tnc->dirp = NULL;   /* now it won't match anything */
323             break;
324         } else if (tnc->next == nameHash[skey]) {       /* end of list */
325             tnc = NULL;
326             break;
327         }
328     }
329     ReleaseReadLock(&afs_xdnlc);
330
331     if (!tnc)
332         return 0;
333
334     /* there is a little race condition here, but it's relatively
335      * harmless.  At worst, I wind up removing a mapping that I just
336      * created. */
337     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
338         return 0;               /* no big deal, tnc will get recycled eventually */
339     }
340     RemoveEntry(tnc, skey);
341     tnc->next = ncfreelist;
342     ncfreelist = tnc;
343     ReleaseWriteLock(&afs_xdnlc);
344
345     return 0;
346 }
347
348 /*!
349  * Remove anything pertaining to this directory.  I can invalidate
350  * things without the lock, since I am just looking through the array,
351  * but to move things off the lists or into the freelist, I need the
352  * write lock
353  *
354  * \param adp vcache entry for the directory to be purged.
355  * \return 0
356  */
357 int
358 osi_dnlc_purgedp(struct vcache *adp)
359 {
360     int i;
361     int writelocked;
362
363 #ifdef AFS_DARWIN_ENV
364     if (!(adp->f.states & (CVInit | CVFlushed
365 #ifdef AFS_DARWIN80_ENV
366                         | CDeadVnode
367 #endif
368         )) && AFSTOV(adp))
369     cache_purge(AFSTOV(adp));
370 #endif
371
372     if (!afs_usednlc)
373         return 0;
374
375     dnlcstats.purgeds++;
376     TRACE(osi_dnlc_purgedpT, 0);
377     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
378
379     for (i = 0; i < NCSIZE; i++) {
380         if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
381             nameCache[i].dirp = nameCache[i].vp = NULL;
382             if (writelocked && nameCache[i].prev) {
383                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
384                 nameCache[i].next = ncfreelist;
385                 ncfreelist = &nameCache[i];
386             }
387         }
388     }
389     if (writelocked)
390         ReleaseWriteLock(&afs_xdnlc);
391
392     return 0;
393 }
394
395 /*!
396  * Remove anything pertaining to this file
397  *
398  * \param File vcache entry.
399  * \return 0
400  */
401 int
402 osi_dnlc_purgevp(struct vcache *avc)
403 {
404     int i;
405     int writelocked;
406
407 #ifdef AFS_DARWIN_ENV
408     if (!(avc->f.states & (CVInit | CVFlushed
409 #ifdef AFS_DARWIN80_ENV
410                         | CDeadVnode
411 #endif
412         )) && AFSTOV(avc))
413     cache_purge(AFSTOV(avc));
414 #endif
415
416     if (!afs_usednlc)
417         return 0;
418
419     dnlcstats.purgevs++;
420     TRACE(osi_dnlc_purgevpT, 0);
421     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
422
423     for (i = 0; i < NCSIZE; i++) {
424         if (nameCache[i].vp == avc) {
425             nameCache[i].dirp = nameCache[i].vp = NULL;
426             /* can't simply break; because of hard links -- might be two */
427             /* different entries with same vnode */
428             if (writelocked && nameCache[i].prev) {
429                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
430                 nameCache[i].next = ncfreelist;
431                 ncfreelist = &nameCache[i];
432             }
433         }
434     }
435     if (writelocked)
436         ReleaseWriteLock(&afs_xdnlc);
437
438     return 0;
439 }
440
441 /* remove everything */
442 int
443 osi_dnlc_purge(void)
444 {
445     int i;
446
447     dnlcstats.purges++;
448     TRACE(osi_dnlc_purgeT, 0);
449     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) {      /* couldn't get lock */
450         for (i = 0; i < NCSIZE; i++)
451             nameCache[i].dirp = nameCache[i].vp = NULL;
452     } else {                    /* did get the lock */
453         ncfreelist = NULL;
454         memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
455         memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
456         for (i = 0; i < NCSIZE; i++) {
457             nameCache[i].next = ncfreelist;
458             ncfreelist = &nameCache[i];
459         }
460         ReleaseWriteLock(&afs_xdnlc);
461     }
462
463     return 0;
464 }
465
466 /* remove everything referencing a specific volume */
467 int
468 osi_dnlc_purgevol(struct VenusFid *fidp)
469 {
470
471     dnlcstats.purgevols++;
472     osi_dnlc_purge();
473
474     return 0;
475 }
476
477 int
478 osi_dnlc_init(void)
479 {
480     int i;
481
482     Lock_Init(&afs_xdnlc);
483     memset(&dnlcstats, 0, sizeof(dnlcstats));
484     memset(dnlctracetable, 0, sizeof(dnlctracetable));
485     dnlct = 0;
486     ObtainWriteLock(&afs_xdnlc, 223);
487     ncfreelist = NULL;
488     memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
489     memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
490     for (i = 0; i < NCSIZE; i++) {
491         nameCache[i].next = ncfreelist;
492         ncfreelist = &nameCache[i];
493     }
494     ReleaseWriteLock(&afs_xdnlc);
495
496     return 0;
497 }
498
499 int
500 osi_dnlc_shutdown(void)
501 {
502     return 0;
503 }