Merge 1.8.0~pre4 packaging into master
[pkg-k5-afs_openafs.git] / src / afs / afs_osidnlc.c
blob9d267e4c07f4ac36c4df1248c00411b7dd651ed1
1 /*
2 * Copyright 2000, International Business Machines Corporation and others.
3 * All Rights Reserved.
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 */
10 #include <afsconfig.h>
11 #include "afs/param.h"
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"
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.
30 struct afs_lock afs_xdnlc;
31 extern struct afs_lock afs_xvcache;
33 dnlcstats_t dnlcstats;
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.
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;
50 int afs_usednlc = 1;
52 struct dt {
53 traceevt event;
54 unsigned char slot;
57 struct dt dnlctracetable[256];
58 int dnlct;
60 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
62 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
64 static struct nc *
65 GetMeAnEntry(void)
67 static unsigned int nameptr = 0; /* next bucket to pull something from */
68 struct nc *tnc;
69 int j;
71 if (ncfreelist) {
72 tnc = ncfreelist;
73 ncfreelist = tnc->next;
74 return tnc;
77 for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
78 if (nameptr >= NHSIZE)
79 nameptr = 0;
80 if (nameHash[nameptr])
81 break;
84 if (nameptr >= NHSIZE)
85 nameptr = 0;
87 TRACE(ScavengeEntryT, nameptr);
88 tnc = nameHash[nameptr];
89 if (!tnc) /* May want to consider changing this to return 0 */
90 osi_Panic("null tnc in GetMeAnEntry");
92 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
93 nameHash[nameptr] = NULL;
94 return (tnc);
97 tnc = tnc->prev; /* grab oldest one in this bucket */
98 /* remove it from list */
99 tnc->next->prev = tnc->prev;
100 tnc->prev->next = tnc->next;
102 return (tnc);
105 static void
106 InsertEntry(struct nc *tnc)
108 unsigned int key;
109 key = tnc->key & (NHSIZE - 1);
111 TRACE(InsertEntryT, key);
112 if (!nameHash[key]) {
113 nameHash[key] = tnc;
114 tnc->next = tnc->prev = tnc;
115 } else {
116 tnc->next = nameHash[key];
117 tnc->prev = tnc->next->prev;
118 tnc->next->prev = tnc;
119 tnc->prev->next = tnc;
120 nameHash[key] = tnc;
126 osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
127 afs_hyper_t * avno)
129 struct nc *tnc;
130 unsigned int key, skey;
131 char *ts = aname;
132 int safety;
134 if (!afs_usednlc)
135 return 0;
137 TRACE(osi_dnlc_enterT, 0);
138 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
139 if (ts - aname >= AFSNCNAMESIZE) {
140 return 0;
142 skey = key & (NHSIZE - 1);
143 dnlcstats.enters++;
145 retry:
146 ObtainWriteLock(&afs_xdnlc, 222);
148 /* Only cache entries from the latest version of the directory */
149 if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
150 ReleaseWriteLock(&afs_xdnlc);
151 return 0;
155 * Make sure each directory entry gets cached no more than once.
157 for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
158 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
159 /* duplicate entry */
160 break;
161 } else if (tnc->next == nameHash[skey]) { /* end of list */
162 tnc = NULL;
163 break;
164 } else if (safety > NCSIZE) {
165 afs_warn("DNLC cycle");
166 dnlcstats.cycles++;
167 ReleaseWriteLock(&afs_xdnlc);
168 osi_dnlc_purge();
169 goto retry;
173 if (tnc == NULL) {
174 tnc = GetMeAnEntry();
176 tnc->dirp = adp;
177 tnc->vp = avc;
178 tnc->key = key;
179 memcpy((char *)tnc->name, aname, ts - aname + 1); /* include the NULL */
181 InsertEntry(tnc);
182 } else {
183 /* duplicate */
184 tnc->vp = avc;
186 ReleaseWriteLock(&afs_xdnlc);
188 return 0;
192 struct vcache *
193 osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
195 struct vcache *tvc;
196 unsigned int key, skey;
197 char *ts = aname;
198 struct nc *tnc;
199 int safety;
200 #ifdef AFS_DARWIN80_ENV
201 vnode_t tvp;
202 #endif
204 if (!afs_usednlc)
205 return 0;
207 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
208 if (ts - aname >= AFSNCNAMESIZE)
209 return 0;
210 skey = key & (NHSIZE - 1);
212 TRACE(osi_dnlc_lookupT, skey);
213 dnlcstats.lookups++;
215 ObtainReadLock(&afs_xvcache);
216 ObtainReadLock(&afs_xdnlc);
218 for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
219 tnc = tnc->next, safety++) {
220 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
221 && (!strcmp((char *)tnc->name, aname))) {
222 tvc = tnc->vp;
223 break;
224 } else if (tnc->next == nameHash[skey]) { /* end of list */
225 break;
226 } else if (safety > NCSIZE) {
227 afs_warn("DNLC cycle");
228 dnlcstats.cycles++;
229 ReleaseReadLock(&afs_xdnlc);
230 ReleaseReadLock(&afs_xvcache);
231 osi_dnlc_purge();
232 return (0);
236 ReleaseReadLock(&afs_xdnlc);
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
248 ReleaseReadLock(&afs_xvcache);
249 dnlcstats.misses++;
250 osi_dnlc_remove(adp, aname, tvc);
251 return 0;
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;
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;
270 #else
271 osi_vnhold(tvc, 0);
272 #endif
273 ReleaseReadLock(&afs_xvcache);
277 return tvc;
281 static void
282 RemoveEntry(struct nc *tnc, unsigned int key)
284 if (!tnc->prev) /* things on freelist always have null prev ptrs */
285 osi_Panic("bogus free list");
287 TRACE(RemoveEntryT, key);
288 if (tnc == tnc->next) { /* only one in list */
289 nameHash[key] = NULL;
290 } else {
291 if (tnc == nameHash[key])
292 nameHash[key] = tnc->next;
293 tnc->prev->next = tnc->next;
294 tnc->next->prev = tnc->prev;
297 tnc->prev = NULL; /* everything not in hash table has 0 prev */
298 tnc->key = 0; /* just for safety's sake */
303 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
305 unsigned int key, skey;
306 char *ts = aname;
307 struct nc *tnc;
309 if (!afs_usednlc)
310 return 0;
312 TRACE(osi_dnlc_removeT, skey);
313 dnlcHash(ts, key); /* leaves ts pointing at the NULL */
314 if (ts - aname >= AFSNCNAMESIZE) {
315 return 0;
317 skey = key & (NHSIZE - 1);
318 TRACE(osi_dnlc_removeT, skey);
319 dnlcstats.removes++;
320 ObtainReadLock(&afs_xdnlc);
322 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
323 if ((tnc->dirp == adp) && (tnc->key == key)
324 && (!strcmp((char *)tnc->name, aname))) {
325 tnc->dirp = NULL; /* now it won't match anything */
326 break;
327 } else if (tnc->next == nameHash[skey]) { /* end of list */
328 tnc = NULL;
329 break;
332 ReleaseReadLock(&afs_xdnlc);
334 if (!tnc)
335 return 0;
337 /* there is a little race condition here, but it's relatively
338 * harmless. At worst, I wind up removing a mapping that I just
339 * created. */
340 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
341 return 0; /* no big deal, tnc will get recycled eventually */
343 RemoveEntry(tnc, skey);
344 tnc->next = ncfreelist;
345 ncfreelist = tnc;
346 ReleaseWriteLock(&afs_xdnlc);
348 return 0;
352 * Remove anything pertaining to this directory. I can invalidate
353 * things without the lock, since I am just looking through the array,
354 * but to move things off the lists or into the freelist, I need the
355 * write lock
357 * \param adp vcache entry for the directory to be purged.
358 * \return 0
361 osi_dnlc_purgedp(struct vcache *adp)
363 int i;
364 int writelocked;
366 #ifdef AFS_DARWIN_ENV
367 if (!(adp->f.states & (CVInit | CVFlushed
368 #ifdef AFS_DARWIN80_ENV
369 | CDeadVnode
370 #endif
371 )) && AFSTOV(adp))
372 cache_purge(AFSTOV(adp));
373 #endif
375 if (!afs_usednlc)
376 return 0;
378 dnlcstats.purgeds++;
379 TRACE(osi_dnlc_purgedpT, 0);
380 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
382 for (i = 0; i < NCSIZE; i++) {
383 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
384 nameCache[i].dirp = nameCache[i].vp = NULL;
385 if (writelocked && nameCache[i].prev) {
386 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
387 nameCache[i].next = ncfreelist;
388 ncfreelist = &nameCache[i];
392 if (writelocked)
393 ReleaseWriteLock(&afs_xdnlc);
395 return 0;
399 * Remove anything pertaining to this file
401 * \param File vcache entry.
402 * \return 0
405 osi_dnlc_purgevp(struct vcache *avc)
407 int i;
408 int writelocked;
410 #ifdef AFS_DARWIN_ENV
411 if (!(avc->f.states & (CVInit | CVFlushed
412 #ifdef AFS_DARWIN80_ENV
413 | CDeadVnode
414 #endif
415 )) && AFSTOV(avc))
416 cache_purge(AFSTOV(avc));
417 #endif
419 if (!afs_usednlc)
420 return 0;
422 dnlcstats.purgevs++;
423 TRACE(osi_dnlc_purgevpT, 0);
424 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
426 for (i = 0; i < NCSIZE; i++) {
427 if (nameCache[i].vp == avc) {
428 nameCache[i].dirp = nameCache[i].vp = NULL;
429 /* can't simply break; because of hard links -- might be two */
430 /* different entries with same vnode */
431 if (writelocked && nameCache[i].prev) {
432 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
433 nameCache[i].next = ncfreelist;
434 ncfreelist = &nameCache[i];
438 if (writelocked)
439 ReleaseWriteLock(&afs_xdnlc);
441 return 0;
444 /* remove everything */
446 osi_dnlc_purge(void)
448 int i;
450 dnlcstats.purges++;
451 TRACE(osi_dnlc_purgeT, 0);
452 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) { /* couldn't get lock */
453 for (i = 0; i < NCSIZE; i++)
454 nameCache[i].dirp = nameCache[i].vp = NULL;
455 } else { /* did get the lock */
456 ncfreelist = NULL;
457 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
458 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
459 for (i = 0; i < NCSIZE; i++) {
460 nameCache[i].next = ncfreelist;
461 ncfreelist = &nameCache[i];
463 ReleaseWriteLock(&afs_xdnlc);
466 return 0;
469 /* remove everything referencing a specific volume */
471 osi_dnlc_purgevol(struct VenusFid *fidp)
474 dnlcstats.purgevols++;
475 osi_dnlc_purge();
477 return 0;
481 osi_dnlc_init(void)
483 int i;
485 Lock_Init(&afs_xdnlc);
486 memset(&dnlcstats, 0, sizeof(dnlcstats));
487 memset(dnlctracetable, 0, sizeof(dnlctracetable));
488 dnlct = 0;
489 ObtainWriteLock(&afs_xdnlc, 223);
490 ncfreelist = NULL;
491 memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
492 memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
493 for (i = 0; i < NCSIZE; i++) {
494 nameCache[i].next = ncfreelist;
495 ncfreelist = &nameCache[i];
497 ReleaseWriteLock(&afs_xdnlc);
499 return 0;
503 osi_dnlc_shutdown(void)
505 return 0;