1 #include "../afs/param.h" /*Should be always first*/
2 #include "../afs/sysincludes.h" /*Standard vendor system headers*/
3 #include "../afs/afsincludes.h" /*AFS-based standard headers*/
5 #include "../afs/lock.h"
6 #include "../afs/afs_stats.h"
7 #include "../afs/afs_osidnlc.h"
10 * also cache failed lookups.
11 * look into interactions of dnlc and readdir.
12 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
13 * the actual name itself.
14 * precompute a key and stuff for @sys, and combine the HandleAtName function with
15 * this, since we're looking at the name anyway.
18 struct afs_lock afs_xdnlc;
19 extern struct afs_lock afs_xvcache;
21 dnlcstats_t dnlcstats;
24 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
25 struct nc *ncfreelist = (struct nc *)0;
26 static struct nc nameCache[NCSIZE];
27 struct nc *nameHash[NHSIZE];
28 /* Hash table invariants:
29 * 1. If nameHash[i] is NULL, list is empty
30 * 2. A single element in a hash bucket has itself as prev and next.
33 typedef enum {osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT, ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT, osi_dnlc_purgevpT, osi_dnlc_purgeT } traceevt;
42 struct dt dnlctracetable[256];
45 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
47 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
49 static struct nc * GetMeAnEntry() {
50 static unsigned int nameptr = 0; /* next bucket to pull something from */
56 ncfreelist = tnc->next;
60 for (j=0; j<NHSIZE+2; j++, nameptr++) {
61 if (nameptr >= NHSIZE)
63 if (nameHash[nameptr])
67 TRACE(ScavengeEntryT, nameptr);
68 tnc = nameHash[nameptr];
69 if (!tnc) /* May want to consider changing this to return 0 */
70 osi_Panic("null tnc in GetMeAnEntry");
72 if (tnc->prev == tnc) { /* only thing in list, don't screw around */
73 nameHash[nameptr] = (struct nc *) 0;
77 tnc = tnc->prev; /* grab oldest one in this bucket */
78 /* remove it from list */
79 tnc->next->prev = tnc->prev;
80 tnc->prev->next = tnc->next;
85 static void InsertEntry(tnc)
89 key = tnc->key & (NHSIZE -1);
91 TRACE(InsertEntryT, key);
94 tnc->next = tnc->prev = tnc;
97 tnc->next = nameHash[key];
98 tnc->prev = tnc->next->prev;
99 tnc->next->prev = tnc;
100 tnc->prev->next = tnc;
106 int osi_dnlc_enter ( adp, aname, avc, avno )
113 unsigned int key, skey;
120 TRACE(osi_dnlc_enterT, 0);
121 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
122 if (ts - aname >= AFSNCNAMESIZE) {
125 skey = key & (NHSIZE -1);
129 ObtainWriteLock(&afs_xdnlc,222);
131 /* Only cache entries from the latest version of the directory */
132 if (!(adp->states & CStatd) || !hsame(*avno, adp->m.DataVersion)) {
133 ReleaseWriteLock(&afs_xdnlc);
138 * Make sure each directory entry gets cached no more than once.
140 for (tnc = nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ ) {
141 if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
142 /* duplicate entry */
145 else if (tnc->next == nameHash[skey]) { /* end of list */
149 else if (safety >NCSIZE) {
150 afs_warn("DNLC cycle");
152 ReleaseWriteLock(&afs_xdnlc);
159 tnc = GetMeAnEntry();
164 bcopy (aname, (char *)tnc->name, ts-aname+1); /* include the NULL */
171 ReleaseWriteLock(&afs_xdnlc);
178 osi_dnlc_lookup ( adp, aname, locktype )
185 unsigned int key, skey;
187 struct nc * tnc, *tnc1=0;
193 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
194 if (ts - aname >= AFSNCNAMESIZE) {
197 skey = key & (NHSIZE -1);
199 TRACE(osi_dnlc_lookupT, skey);
202 ObtainReadLock(&afs_xvcache);
203 ObtainReadLock(&afs_xdnlc);
205 for ( tvc = (struct vcache *) 0, tnc = nameHash[skey], safety=0;
206 tnc; tnc = tnc->next, safety++ ) {
207 if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
208 && (!strcmp((char *)tnc->name, aname))) {
213 else if (tnc->next == nameHash[skey]) { /* end of list */
216 else if (safety >NCSIZE) {
217 afs_warn("DNLC cycle");
219 ReleaseReadLock(&afs_xdnlc);
220 ReleaseReadLock(&afs_xvcache);
226 LRUme = 0; /* (tnc != nameHash[skey]); */
227 ReleaseReadLock(&afs_xdnlc);
230 ReleaseReadLock(&afs_xvcache);
235 VN_HOLD((vnode_t *)tvc);
239 ReleaseReadLock(&afs_xvcache);
243 * XX If LRUme ever is non-zero change the if statement around because
244 * aix's cc with optimizer on won't necessarily check things in order XX
246 if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
247 /* don't block to do this */
248 /* tnc might have been moved during race condition, */
249 /* but it's always in a legit hash chain when a lock is granted,
250 * or else it's on the freelist so prev == NULL,
251 * so at worst this is redundant */
252 /* Now that we've got it held, and a lock on the dnlc, we
253 * should check to be sure that there was no race, and
254 * bail out if there was. */
256 /* special case for only two elements on list - relative ordering
258 if (tnc->prev != tnc->next) {
259 /* remove from old location */
260 tnc->prev->next = tnc->next;
261 tnc->next->prev = tnc->prev;
262 /* insert into new location */
263 tnc->next = nameHash[skey];
264 tnc->prev = tnc->next->prev;
265 tnc->next->prev = tnc;
266 tnc->prev->next = tnc;
268 nameHash[skey] = tnc;
270 ReleaseWriteLock(&afs_xdnlc);
280 RemoveEntry (tnc, 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] = (struct nc *) 0;
292 if (tnc == nameHash[key])
293 nameHash[key] = tnc->next;
294 tnc->prev->next = tnc->next;
295 tnc->next->prev = tnc->prev;
298 tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
299 tnc->key = 0; /* just for safety's sake */
304 osi_dnlc_remove ( adp, aname, avc )
309 unsigned int key, skey;
316 TRACE( osi_dnlc_removeT, skey);
317 dnlcHash( ts, key ); /* leaves ts pointing at the NULL */
318 if (ts - aname >= AFSNCNAMESIZE) {
321 skey = key & (NHSIZE -1);
322 TRACE( osi_dnlc_removeT, skey);
324 ObtainReadLock(&afs_xdnlc);
326 for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
327 if ((tnc->dirp == adp) && (tnc->key == key)
328 && (!strcmp((char *)tnc->name, aname))) {
329 tnc->dirp = (struct vcache *) 0; /* now it won't match anything */
332 else if (tnc->next == nameHash[skey]) { /* end of list */
333 tnc = (struct nc *) 0;
337 ReleaseReadLock(&afs_xdnlc);
342 /* there is a little race condition here, but it's relatively
343 * harmless. At worst, I wind up removing a mapping that I just
345 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,1)) {
346 return 0; /* no big deal, tnc will get recycled eventually */
348 RemoveEntry(tnc, skey);
349 tnc->next = ncfreelist;
351 ReleaseWriteLock(&afs_xdnlc);
356 /* remove anything pertaining to this directory. I can invalidate
357 * things without the lock, since I am just looking through the array,
358 * but to move things off the lists or into the freelist, I need the
361 osi_dnlc_purgedp (adp)
371 TRACE( osi_dnlc_purgedpT, 0);
372 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,2));
374 for (i=0; i<NCSIZE; i++) {
375 if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
376 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
377 if (writelocked && nameCache[i].prev) {
378 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
379 nameCache[i].next = ncfreelist;
380 ncfreelist = &nameCache[i];
385 ReleaseWriteLock(&afs_xdnlc);
390 /* remove anything pertaining to this file */
392 osi_dnlc_purgevp ( avc )
402 TRACE( osi_dnlc_purgevpT, 0);
403 writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,3));
405 for (i=0; i<NCSIZE; i++) {
406 if ((nameCache[i].vp == avc)) {
407 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
408 /* can't simply break; because of hard links -- might be two */
409 /* different entries with same vnode */
410 if (writelocked && nameCache[i].prev) {
411 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
412 nameCache[i].next = ncfreelist;
413 ncfreelist = &nameCache[i];
418 ReleaseWriteLock(&afs_xdnlc);
423 /* remove everything */
429 TRACE( osi_dnlc_purgeT, 0);
430 if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,4)) { /* couldn't get lock */
431 for (i=0; i<NCSIZE; i++)
432 nameCache[i].dirp = nameCache[i].vp = (struct vcache *) 0;
434 else { /* did get the lock */
435 ncfreelist = (struct nc *) 0;
436 bzero ((char *)nameCache, sizeof(struct nc) * NCSIZE);
437 bzero ((char *)nameHash, sizeof(struct nc *) * NHSIZE);
438 for (i=0; i<NCSIZE; i++) {
439 nameCache[i].next = ncfreelist;
440 ncfreelist = &nameCache[i];
442 ReleaseWriteLock(&afs_xdnlc);
448 /* remove everything referencing a specific volume */
450 osi_dnlc_purgevol( fidp )
451 struct VenusFid *fidp;
454 dnlcstats.purgevols++;
464 Lock_Init(&afs_xdnlc);
465 bzero ((char *)&dnlcstats, sizeof(dnlcstats));
466 bzero ((char *)dnlctracetable, sizeof(dnlctracetable));
468 ObtainWriteLock(&afs_xdnlc,223);
469 ncfreelist = (struct nc *) 0;
470 bzero ((char *)nameCache, sizeof(struct nc) * NCSIZE);
471 bzero ((char *)nameHash, sizeof(struct nc *) * NHSIZE);
472 for (i=0; i<NCSIZE; i++) {
473 nameCache[i].next = ncfreelist;
474 ncfreelist = &nameCache[i];
476 ReleaseWriteLock(&afs_xdnlc);
481 int osi_dnlc_shutdown()