2 * Copyright 2000, International Business Machines Corporation and others.
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
11 * OSI Directory Name Lookup Cache
13 * Keep a local cache of lookup results to avoid needing to examine the disk
14 * cache, for frequently accessed names.
17 #include <afsconfig.h>
18 #include "afs/param.h"
21 #include "afs/sysincludes.h" /*Standard vendor system headers */
22 #include "afsincludes.h" /*AFS-based standard headers */
25 #include "afs/afs_stats.h"
26 #include "afs/afs_osidnlc.h"
29 * also cache failed lookups.
30 * look into interactions of dnlc and readdir.
31 * cache larger names, perhaps by using a better,longer key (SHA) and discarding
32 * the actual name itself.
33 * precompute a key and stuff for \sys, and combine the HandleAtName function with
34 * this, since we're looking at the name anyway.
37 struct afs_lock afs_xdnlc
;
38 extern struct afs_lock afs_xvcache
;
40 dnlcstats_t dnlcstats
;
43 #define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
44 struct nc
*ncfreelist
= NULL
;
45 static struct nc nameCache
[NCSIZE
];
46 struct nc
*nameHash
[NHSIZE
];
47 /* Hash table invariants:
48 * 1. If nameHash[i] is NULL, list is empty
49 * 2. A single element in a hash bucket has itself as prev and next.
52 typedef enum { osi_dnlc_enterT
, InsertEntryT
, osi_dnlc_lookupT
,
53 ScavengeEntryT
, osi_dnlc_removeT
, RemoveEntryT
, osi_dnlc_purgedpT
,
54 osi_dnlc_purgevpT
, osi_dnlc_purgeT
64 struct dt dnlctracetable
[256];
67 #define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
69 #define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173; hval += *ts; }
74 static unsigned int nameptr
= 0; /* next bucket to pull something from */
80 ncfreelist
= tnc
->next
;
84 for (j
= 0; j
< NHSIZE
+ 2; j
++, nameptr
++) {
85 if (nameptr
>= NHSIZE
)
87 if (nameHash
[nameptr
])
91 if (nameptr
>= NHSIZE
)
94 TRACE(ScavengeEntryT
, nameptr
);
95 tnc
= nameHash
[nameptr
];
96 if (!tnc
) /* May want to consider changing this to return 0 */
97 osi_Panic("null tnc in GetMeAnEntry");
99 if (tnc
->prev
== tnc
) { /* only thing in list, don't screw around */
100 nameHash
[nameptr
] = NULL
;
104 tnc
= tnc
->prev
; /* grab oldest one in this bucket */
105 /* remove it from list */
106 tnc
->next
->prev
= tnc
->prev
;
107 tnc
->prev
->next
= tnc
->next
;
113 InsertEntry(struct nc
*tnc
)
116 key
= tnc
->key
& (NHSIZE
- 1);
118 TRACE(InsertEntryT
, key
);
119 if (!nameHash
[key
]) {
121 tnc
->next
= tnc
->prev
= tnc
;
123 tnc
->next
= nameHash
[key
];
124 tnc
->prev
= tnc
->next
->prev
;
125 tnc
->next
->prev
= tnc
;
126 tnc
->prev
->next
= tnc
;
133 osi_dnlc_enter(struct vcache
*adp
, char *aname
, struct vcache
*avc
,
137 unsigned int key
, skey
;
144 TRACE(osi_dnlc_enterT
, 0);
145 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
146 if (ts
- aname
>= AFSNCNAMESIZE
) {
149 skey
= key
& (NHSIZE
- 1);
153 ObtainWriteLock(&afs_xdnlc
, 222);
155 /* Only cache entries from the latest version of the directory */
156 if (!(adp
->f
.states
& CStatd
) || !hsame(*avno
, adp
->f
.m
.DataVersion
)) {
157 ReleaseWriteLock(&afs_xdnlc
);
162 * Make sure each directory entry gets cached no more than once.
164 for (tnc
= nameHash
[skey
], safety
= 0; tnc
; tnc
= tnc
->next
, safety
++) {
165 if ((tnc
->dirp
== adp
) && (!strcmp((char *)tnc
->name
, aname
))) {
166 /* duplicate entry */
168 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
171 } else if (safety
> NCSIZE
) {
172 afs_warn("DNLC cycle");
174 ReleaseWriteLock(&afs_xdnlc
);
181 tnc
= GetMeAnEntry();
186 memcpy((char *)tnc
->name
, aname
, ts
- aname
+ 1); /* include the NULL */
193 ReleaseWriteLock(&afs_xdnlc
);
200 osi_dnlc_lookup(struct vcache
*adp
, char *aname
, int locktype
)
203 unsigned int key
, skey
;
207 #ifdef AFS_DARWIN80_ENV
214 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
215 if (ts
- aname
>= AFSNCNAMESIZE
)
217 skey
= key
& (NHSIZE
- 1);
219 TRACE(osi_dnlc_lookupT
, skey
);
222 ObtainReadLock(&afs_xvcache
);
223 ObtainReadLock(&afs_xdnlc
);
225 for (tvc
= NULL
, tnc
= nameHash
[skey
], safety
= 0; tnc
;
226 tnc
= tnc
->next
, safety
++) {
227 if ( /* (tnc->key == key) && */ (tnc
->dirp
== adp
)
228 && (!strcmp((char *)tnc
->name
, aname
))) {
231 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
233 } else if (safety
> NCSIZE
) {
234 afs_warn("DNLC cycle");
236 ReleaseReadLock(&afs_xdnlc
);
237 ReleaseReadLock(&afs_xvcache
);
243 ReleaseReadLock(&afs_xdnlc
);
246 ReleaseReadLock(&afs_xvcache
);
249 if ((tvc
->f
.states
& CVInit
)
250 #ifdef AFS_DARWIN80_ENV
251 ||(tvc
->f
.states
& CDeadVnode
)
255 ReleaseReadLock(&afs_xvcache
);
257 osi_dnlc_remove(adp
, aname
, tvc
);
260 #if defined(AFS_DARWIN80_ENV)
262 if (vnode_get(tvp
)) {
263 ReleaseReadLock(&afs_xvcache
);
265 osi_dnlc_remove(adp
, aname
, tvc
);
268 if (vnode_ref(tvp
)) {
269 ReleaseReadLock(&afs_xvcache
);
274 osi_dnlc_remove(adp
, aname
, tvc
);
280 ReleaseReadLock(&afs_xvcache
);
289 RemoveEntry(struct nc
*tnc
, unsigned int key
)
291 if (!tnc
->prev
) /* things on freelist always have null prev ptrs */
292 osi_Panic("bogus free list");
294 TRACE(RemoveEntryT
, key
);
295 if (tnc
== tnc
->next
) { /* only one in list */
296 nameHash
[key
] = NULL
;
298 if (tnc
== nameHash
[key
])
299 nameHash
[key
] = tnc
->next
;
300 tnc
->prev
->next
= tnc
->next
;
301 tnc
->next
->prev
= tnc
->prev
;
304 tnc
->prev
= NULL
; /* everything not in hash table has 0 prev */
305 tnc
->key
= 0; /* just for safety's sake */
310 osi_dnlc_remove(struct vcache
*adp
, char *aname
, struct vcache
*avc
)
312 unsigned int key
, skey
;
319 TRACE(osi_dnlc_removeT
, skey
);
320 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
321 if (ts
- aname
>= AFSNCNAMESIZE
) {
324 skey
= key
& (NHSIZE
- 1);
325 TRACE(osi_dnlc_removeT
, skey
);
327 ObtainReadLock(&afs_xdnlc
);
329 for (tnc
= nameHash
[skey
]; tnc
; tnc
= tnc
->next
) {
330 if ((tnc
->dirp
== adp
) && (tnc
->key
== key
)
331 && (!strcmp((char *)tnc
->name
, aname
))) {
332 tnc
->dirp
= NULL
; /* now it won't match anything */
334 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
339 ReleaseReadLock(&afs_xdnlc
);
344 /* there is a little race condition here, but it's relatively
345 * harmless. At worst, I wind up removing a mapping that I just
347 if (EWOULDBLOCK
== NBObtainWriteLock(&afs_xdnlc
, 1)) {
348 return 0; /* no big deal, tnc will get recycled eventually */
350 RemoveEntry(tnc
, skey
);
351 tnc
->next
= ncfreelist
;
353 ReleaseWriteLock(&afs_xdnlc
);
359 * Remove anything pertaining to this directory. I can invalidate
360 * things without the lock, since I am just looking through the array,
361 * but to move things off the lists or into the freelist, I need the
364 * \param adp vcache entry for the directory to be purged.
368 osi_dnlc_purgedp(struct vcache
*adp
)
373 #ifdef AFS_DARWIN_ENV
374 if (!(adp
->f
.states
& (CVInit
| CVFlushed
375 #ifdef AFS_DARWIN80_ENV
379 cache_purge(AFSTOV(adp
));
386 TRACE(osi_dnlc_purgedpT
, 0);
387 writelocked
= (0 == NBObtainWriteLock(&afs_xdnlc
, 2));
389 for (i
= 0; i
< NCSIZE
; i
++) {
390 if ((nameCache
[i
].dirp
== adp
) || (nameCache
[i
].vp
== adp
)) {
391 nameCache
[i
].dirp
= nameCache
[i
].vp
= NULL
;
392 if (writelocked
&& nameCache
[i
].prev
) {
393 RemoveEntry(&nameCache
[i
], nameCache
[i
].key
& (NHSIZE
- 1));
394 nameCache
[i
].next
= ncfreelist
;
395 ncfreelist
= &nameCache
[i
];
400 ReleaseWriteLock(&afs_xdnlc
);
406 * Remove anything pertaining to this file
408 * \param File vcache entry.
412 osi_dnlc_purgevp(struct vcache
*avc
)
417 #ifdef AFS_DARWIN_ENV
418 if (!(avc
->f
.states
& (CVInit
| CVFlushed
419 #ifdef AFS_DARWIN80_ENV
423 cache_purge(AFSTOV(avc
));
430 TRACE(osi_dnlc_purgevpT
, 0);
431 writelocked
= (0 == NBObtainWriteLock(&afs_xdnlc
, 3));
433 for (i
= 0; i
< NCSIZE
; i
++) {
434 if (nameCache
[i
].vp
== avc
) {
435 nameCache
[i
].dirp
= nameCache
[i
].vp
= NULL
;
436 /* can't simply break; because of hard links -- might be two */
437 /* different entries with same vnode */
438 if (writelocked
&& nameCache
[i
].prev
) {
439 RemoveEntry(&nameCache
[i
], nameCache
[i
].key
& (NHSIZE
- 1));
440 nameCache
[i
].next
= ncfreelist
;
441 ncfreelist
= &nameCache
[i
];
446 ReleaseWriteLock(&afs_xdnlc
);
451 /* remove everything */
458 TRACE(osi_dnlc_purgeT
, 0);
459 if (EWOULDBLOCK
== NBObtainWriteLock(&afs_xdnlc
, 4)) { /* couldn't get lock */
460 for (i
= 0; i
< NCSIZE
; i
++)
461 nameCache
[i
].dirp
= nameCache
[i
].vp
= NULL
;
462 } else { /* did get the lock */
464 memset(nameCache
, 0, sizeof(struct nc
) * NCSIZE
);
465 memset(nameHash
, 0, sizeof(struct nc
*) * NHSIZE
);
466 for (i
= 0; i
< NCSIZE
; i
++) {
467 nameCache
[i
].next
= ncfreelist
;
468 ncfreelist
= &nameCache
[i
];
470 ReleaseWriteLock(&afs_xdnlc
);
476 /* remove everything referencing a specific volume */
478 osi_dnlc_purgevol(struct VenusFid
*fidp
)
481 dnlcstats
.purgevols
++;
492 Lock_Init(&afs_xdnlc
);
493 memset(&dnlcstats
, 0, sizeof(dnlcstats
));
494 memset(dnlctracetable
, 0, sizeof(dnlctracetable
));
496 ObtainWriteLock(&afs_xdnlc
, 223);
498 memset(nameCache
, 0, sizeof(struct nc
) * NCSIZE
);
499 memset(nameHash
, 0, sizeof(struct nc
*) * NHSIZE
);
500 for (i
= 0; i
< NCSIZE
; i
++) {
501 nameCache
[i
].next
= ncfreelist
;
502 ncfreelist
= &nameCache
[i
];
504 ReleaseWriteLock(&afs_xdnlc
);
510 osi_dnlc_shutdown(void)