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
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 */
18 #include "afs/afs_stats.h"
19 #include "afs/afs_osidnlc.h"
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
;
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
57 struct dt dnlctracetable
[256];
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; }
67 static unsigned int nameptr
= 0; /* next bucket to pull something from */
73 ncfreelist
= tnc
->next
;
77 for (j
= 0; j
< NHSIZE
+ 2; j
++, nameptr
++) {
78 if (nameptr
>= NHSIZE
)
80 if (nameHash
[nameptr
])
84 if (nameptr
>= NHSIZE
)
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
;
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
;
106 InsertEntry(struct nc
*tnc
)
109 key
= tnc
->key
& (NHSIZE
- 1);
111 TRACE(InsertEntryT
, key
);
112 if (!nameHash
[key
]) {
114 tnc
->next
= tnc
->prev
= tnc
;
116 tnc
->next
= nameHash
[key
];
117 tnc
->prev
= tnc
->next
->prev
;
118 tnc
->next
->prev
= tnc
;
119 tnc
->prev
->next
= tnc
;
126 osi_dnlc_enter(struct vcache
*adp
, char *aname
, struct vcache
*avc
,
130 unsigned int key
, skey
;
137 TRACE(osi_dnlc_enterT
, 0);
138 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
139 if (ts
- aname
>= AFSNCNAMESIZE
) {
142 skey
= key
& (NHSIZE
- 1);
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
);
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 */
161 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
164 } else if (safety
> NCSIZE
) {
165 afs_warn("DNLC cycle");
167 ReleaseWriteLock(&afs_xdnlc
);
174 tnc
= GetMeAnEntry();
179 memcpy((char *)tnc
->name
, aname
, ts
- aname
+ 1); /* include the NULL */
186 ReleaseWriteLock(&afs_xdnlc
);
193 osi_dnlc_lookup(struct vcache
*adp
, char *aname
, int locktype
)
196 unsigned int key
, skey
;
200 #ifdef AFS_DARWIN80_ENV
207 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
208 if (ts
- aname
>= AFSNCNAMESIZE
)
210 skey
= key
& (NHSIZE
- 1);
212 TRACE(osi_dnlc_lookupT
, skey
);
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
))) {
224 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
226 } else if (safety
> NCSIZE
) {
227 afs_warn("DNLC cycle");
229 ReleaseReadLock(&afs_xdnlc
);
230 ReleaseReadLock(&afs_xvcache
);
236 ReleaseReadLock(&afs_xdnlc
);
239 ReleaseReadLock(&afs_xvcache
);
242 if ((tvc
->f
.states
& CVInit
)
243 #ifdef AFS_DARWIN80_ENV
244 ||(tvc
->f
.states
& CDeadVnode
)
248 ReleaseReadLock(&afs_xvcache
);
250 osi_dnlc_remove(adp
, aname
, tvc
);
253 #if defined(AFS_DARWIN80_ENV)
255 if (vnode_get(tvp
)) {
256 ReleaseReadLock(&afs_xvcache
);
258 osi_dnlc_remove(adp
, aname
, tvc
);
261 if (vnode_ref(tvp
)) {
262 ReleaseReadLock(&afs_xvcache
);
267 osi_dnlc_remove(adp
, aname
, tvc
);
273 ReleaseReadLock(&afs_xvcache
);
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
;
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
;
312 TRACE(osi_dnlc_removeT
, skey
);
313 dnlcHash(ts
, key
); /* leaves ts pointing at the NULL */
314 if (ts
- aname
>= AFSNCNAMESIZE
) {
317 skey
= key
& (NHSIZE
- 1);
318 TRACE(osi_dnlc_removeT
, skey
);
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 */
327 } else if (tnc
->next
== nameHash
[skey
]) { /* end of list */
332 ReleaseReadLock(&afs_xdnlc
);
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
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
;
346 ReleaseWriteLock(&afs_xdnlc
);
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
357 * \param adp vcache entry for the directory to be purged.
361 osi_dnlc_purgedp(struct vcache
*adp
)
366 #ifdef AFS_DARWIN_ENV
367 if (!(adp
->f
.states
& (CVInit
| CVFlushed
368 #ifdef AFS_DARWIN80_ENV
372 cache_purge(AFSTOV(adp
));
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
];
393 ReleaseWriteLock(&afs_xdnlc
);
399 * Remove anything pertaining to this file
401 * \param File vcache entry.
405 osi_dnlc_purgevp(struct vcache
*avc
)
410 #ifdef AFS_DARWIN_ENV
411 if (!(avc
->f
.states
& (CVInit
| CVFlushed
412 #ifdef AFS_DARWIN80_ENV
416 cache_purge(AFSTOV(avc
));
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
];
439 ReleaseWriteLock(&afs_xdnlc
);
444 /* remove everything */
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 */
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
);
469 /* remove everything referencing a specific volume */
471 osi_dnlc_purgevol(struct VenusFid
*fidp
)
474 dnlcstats
.purgevols
++;
485 Lock_Init(&afs_xdnlc
);
486 memset(&dnlcstats
, 0, sizeof(dnlcstats
));
487 memset(dnlctracetable
, 0, sizeof(dnlctracetable
));
489 ObtainWriteLock(&afs_xdnlc
, 223);
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
);
503 osi_dnlc_shutdown(void)