1 /* $NetBSD: ufs_dirhash.c,v 1.37 2014/12/20 00:28:05 christos Exp $ */
2
3 /*
4 * Copyright (c) 2001, 2002 Ian Dowse. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 *
27 * $FreeBSD: src/sys/ufs/ufs/ufs_dirhash.c,v 1.3.2.8 2004/12/08 11:54:13 dwmalone Exp $
28 */
29
30 #include <sys/cdefs.h>
31 __KERNEL_RCSID(0, "$NetBSD: ufs_dirhash.c,v 1.37 2014/12/20 00:28:05 christos Exp $");
32
33 /*
34 * This implements a hash-based lookup scheme for UFS directories.
35 */
36
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/kernel.h>
40 #include <sys/kmem.h>
41 #include <sys/types.h>
42 #include <sys/hash.h>
43 #include <sys/proc.h>
44 #include <sys/buf.h>
45 #include <sys/vnode.h>
46 #include <sys/mount.h>
47 #include <sys/pool.h>
48 #include <sys/sysctl.h>
49 #include <sys/atomic.h>
50
51 #include <ufs/ufs/inode.h>
52 #include <ufs/ufs/dir.h>
53 #include <ufs/ufs/dirhash.h>
54 #include <ufs/ufs/ufsmount.h>
55 #include <ufs/ufs/ufs_bswap.h>
56 #include <ufs/ufs/ufs_extern.h>
57
58 #define WRAPINCR(val, limit) (((val) + 1 == (limit)) ? 0 : ((val) + 1))
59 #define WRAPDECR(val, limit) (((val) == 0) ? ((limit) - 1) : ((val) - 1))
60 #define OFSFMT(ip) ((ip)->i_ump->um_maxsymlinklen <= 0)
61 #define BLKFREE2IDX(n) ((n) > DH_NFSTATS ? DH_NFSTATS : (n))
62
63 static u_int ufs_dirhashminblks = 5;
64 static u_int ufs_dirhashmaxmem = 2 * 1024 * 1024;
65 static u_int ufs_dirhashmem;
66 static u_int ufs_dirhashcheck = 0;
67
68 static int ufsdirhash_hash(struct dirhash *dh, const char *name, int namelen);
69 static void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff,
70 int dirblksiz);
71 static void ufsdirhash_delslot(struct dirhash *dh, int slot);
72 static int ufsdirhash_findslot(struct dirhash *dh, const char *name,
73 int namelen, doff_t offset);
74 static doff_t ufsdirhash_getprev(struct direct *dp, doff_t offset,
75 int dirblksiz);
76 static int ufsdirhash_recycle(int wanted);
77
78 static pool_cache_t ufsdirhashblk_cache;
79 static pool_cache_t ufsdirhash_cache;
80
81 #define DIRHASHLIST_LOCK() mutex_enter(&ufsdirhash_lock)
82 #define DIRHASHLIST_UNLOCK() mutex_exit(&ufsdirhash_lock)
83 #define DIRHASH_LOCK(dh) mutex_enter(&(dh)->dh_lock)
84 #define DIRHASH_UNLOCK(dh) mutex_exit(&(dh)->dh_lock)
85 #define DIRHASH_BLKALLOC() \
86 pool_cache_get(ufsdirhashblk_cache, PR_NOWAIT)
87 #define DIRHASH_BLKFREE(ptr) \
88 pool_cache_put(ufsdirhashblk_cache, ptr)
89
90 /* Dirhash list; recently-used entries are near the tail. */
91 static TAILQ_HEAD(, dirhash) ufsdirhash_list;
92
93 /* Protects: ufsdirhash_list, `dh_list' field, ufs_dirhashmem. */
94 static kmutex_t ufsdirhash_lock;
95
96 static struct sysctllog *ufsdirhash_sysctl_log;
97
98 /*
99 * Locking order:
100 * ufsdirhash_lock
101 * dh_lock
102 *
103 * The dh_lock mutex should be acquired either via the inode lock, or via
104 * ufsdirhash_lock. Only the owner of the inode may free the associated
105 * dirhash, but anything can steal its memory and set dh_hash to NULL.
106 */
107
108 /*
109 * Attempt to build up a hash table for the directory contents in
110 * inode 'ip'. Returns 0 on success, or -1 of the operation failed.
111 */
112 int
ufsdirhash_build(struct inode * ip)113 ufsdirhash_build(struct inode *ip)
114 {
115 struct dirhash *dh;
116 struct buf *bp = NULL;
117 struct direct *ep;
118 struct vnode *vp;
119 doff_t bmask, pos;
120 int dirblocks, i, j, memreqd, nblocks, narrays, nslots, slot;
121 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
122 int dirblksiz = ip->i_ump->um_dirblksiz;
123
124 /* Check if we can/should use dirhash. */
125 if (ip->i_dirhash == NULL) {
126 if (ip->i_size < (ufs_dirhashminblks * dirblksiz) || OFSFMT(ip))
127 return (-1);
128 } else {
129 /* Hash exists, but sysctls could have changed. */
130 if (ip->i_size < (ufs_dirhashminblks * dirblksiz) ||
131 ufs_dirhashmem > ufs_dirhashmaxmem) {
132 ufsdirhash_free(ip);
133 return (-1);
134 }
135 /* Check if hash exists and is intact (note: unlocked read). */
136 if (ip->i_dirhash->dh_hash != NULL)
137 return (0);
138 /* Free the old, recycled hash and build a new one. */
139 ufsdirhash_free(ip);
140 }
141
142 /* Don't hash removed directories. */
143 if (ip->i_nlink == 0)
144 return (-1);
145
146 vp = ip->i_vnode;
147 /* Allocate 50% more entries than this dir size could ever need. */
148 KASSERT(ip->i_size >= dirblksiz);
149 nslots = ip->i_size / UFS_DIRECTSIZ(1);
150 nslots = (nslots * 3 + 1) / 2;
151 narrays = howmany(nslots, DH_NBLKOFF);
152 nslots = narrays * DH_NBLKOFF;
153 dirblocks = howmany(ip->i_size, dirblksiz);
154 nblocks = (dirblocks * 3 + 1) / 2;
155
156 memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
157 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
158 nblocks * sizeof(*dh->dh_blkfree);
159
160 while (atomic_add_int_nv(&ufs_dirhashmem, memreqd) >
161 ufs_dirhashmaxmem) {
162 atomic_add_int(&ufs_dirhashmem, -memreqd);
163 if (memreqd > ufs_dirhashmaxmem / 2)
164 return (-1);
165 /* Try to free some space. */
166 if (ufsdirhash_recycle(memreqd) != 0)
167 return (-1);
168 else
169 DIRHASHLIST_UNLOCK();
170 }
171
172 /*
173 * Use non-blocking mallocs so that we will revert to a linear
174 * lookup on failure rather than potentially blocking forever.
175 */
176 dh = pool_cache_get(ufsdirhash_cache, PR_NOWAIT);
177 if (dh == NULL) {
178 atomic_add_int(&ufs_dirhashmem, -memreqd);
179 return (-1);
180 }
181 memset(dh, 0, sizeof(*dh));
182 mutex_init(&dh->dh_lock, MUTEX_DEFAULT, IPL_NONE);
183 DIRHASH_LOCK(dh);
184 dh->dh_hashsz = narrays * sizeof(dh->dh_hash[0]);
185 dh->dh_hash = kmem_zalloc(dh->dh_hashsz, KM_NOSLEEP);
186 dh->dh_blkfreesz = nblocks * sizeof(dh->dh_blkfree[0]);
187 dh->dh_blkfree = kmem_zalloc(dh->dh_blkfreesz, KM_NOSLEEP);
188 if (dh->dh_hash == NULL || dh->dh_blkfree == NULL)
189 goto fail;
190 for (i = 0; i < narrays; i++) {
191 if ((dh->dh_hash[i] = DIRHASH_BLKALLOC()) == NULL)
192 goto fail;
193 for (j = 0; j < DH_NBLKOFF; j++)
194 dh->dh_hash[i][j] = DIRHASH_EMPTY;
195 }
196
197 /* Initialise the hash table and block statistics. */
198 dh->dh_narrays = narrays;
199 dh->dh_hlen = nslots;
200 dh->dh_nblk = nblocks;
201 dh->dh_dirblks = dirblocks;
202 for (i = 0; i < dirblocks; i++)
203 dh->dh_blkfree[i] = dirblksiz / DIRALIGN;
204 for (i = 0; i < DH_NFSTATS; i++)
205 dh->dh_firstfree[i] = -1;
206 dh->dh_firstfree[DH_NFSTATS] = 0;
207 dh->dh_seqopt = 0;
208 dh->dh_seqoff = 0;
209 dh->dh_score = DH_SCOREINIT;
210 ip->i_dirhash = dh;
211
212 bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
213 pos = 0;
214 while (pos < ip->i_size) {
215 if ((curcpu()->ci_schedstate.spc_flags & SPCF_SHOULDYIELD)
216 != 0) {
217 preempt();
218 }
219 /* If necessary, get the next directory block. */
220 if ((pos & bmask) == 0) {
221 if (bp != NULL)
222 brelse(bp, 0);
223 if (ufs_blkatoff(vp, (off_t)pos, NULL, &bp, false) != 0)
224 goto fail;
225 }
226
227 /* Add this entry to the hash. */
228 ep = (struct direct *)((char *)bp->b_data + (pos & bmask));
229 if (ep->d_reclen == 0 || ep->d_reclen >
230 dirblksiz - (pos & (dirblksiz - 1))) {
231 /* Corrupted directory. */
232 brelse(bp, 0);
233 goto fail;
234 }
235 if (ep->d_ino != 0) {
236 /* Add the entry (simplified ufsdirhash_add). */
237 slot = ufsdirhash_hash(dh, ep->d_name, ep->d_namlen);
238 while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
239 slot = WRAPINCR(slot, dh->dh_hlen);
240 dh->dh_hused++;
241 DH_ENTRY(dh, slot) = pos;
242 ufsdirhash_adjfree(dh, pos, -UFS_DIRSIZ(0, ep, needswap),
243 dirblksiz);
244 }
245 pos += ep->d_reclen;
246 }
247
248 if (bp != NULL)
249 brelse(bp, 0);
250 DIRHASHLIST_LOCK();
251 TAILQ_INSERT_TAIL(&ufsdirhash_list, dh, dh_list);
252 dh->dh_onlist = 1;
253 DIRHASH_UNLOCK(dh);
254 DIRHASHLIST_UNLOCK();
255 return (0);
256
257 fail:
258 ip->i_dirhash = NULL;
259 DIRHASH_UNLOCK(dh);
260 if (dh->dh_hash != NULL) {
261 for (i = 0; i < narrays; i++)
262 if (dh->dh_hash[i] != NULL)
263 DIRHASH_BLKFREE(dh->dh_hash[i]);
264 kmem_free(dh->dh_hash, dh->dh_hashsz);
265 }
266 if (dh->dh_blkfree != NULL)
267 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
268 mutex_destroy(&dh->dh_lock);
269 pool_cache_put(ufsdirhash_cache, dh);
270 atomic_add_int(&ufs_dirhashmem, -memreqd);
271 return (-1);
272 }
273
274 /*
275 * Free any hash table associated with inode 'ip'.
276 */
277 void
ufsdirhash_free(struct inode * ip)278 ufsdirhash_free(struct inode *ip)
279 {
280 struct dirhash *dh;
281 int i, mem;
282
283 if ((dh = ip->i_dirhash) == NULL)
284 return;
285
286 ip->i_dirhash = NULL;
287
288 if (dh->dh_onlist) {
289 DIRHASHLIST_LOCK();
290 if (dh->dh_onlist)
291 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
292 DIRHASHLIST_UNLOCK();
293 }
294
295 /* The dirhash pointed to by 'dh' is exclusively ours now. */
296 mem = sizeof(*dh);
297 if (dh->dh_hash != NULL) {
298 for (i = 0; i < dh->dh_narrays; i++)
299 DIRHASH_BLKFREE(dh->dh_hash[i]);
300 kmem_free(dh->dh_hash, dh->dh_hashsz);
301 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
302 mem += dh->dh_hashsz;
303 mem += dh->dh_narrays * DH_NBLKOFF * sizeof(**dh->dh_hash);
304 mem += dh->dh_nblk * sizeof(*dh->dh_blkfree);
305 }
306 mutex_destroy(&dh->dh_lock);
307 pool_cache_put(ufsdirhash_cache, dh);
308
309 atomic_add_int(&ufs_dirhashmem, -mem);
310 }
311
312 /*
313 * Find the offset of the specified name within the given inode.
314 * Returns 0 on success, ENOENT if the entry does not exist, or
315 * EJUSTRETURN if the caller should revert to a linear search.
316 *
317 * If successful, the directory offset is stored in *offp, and a
318 * pointer to a struct buf containing the entry is stored in *bpp. If
319 * prevoffp is non-NULL, the offset of the previous entry within
320 * the UFS_DIRBLKSIZ-sized block is stored in *prevoffp (if the entry
321 * is the first in a block, the start of the block is used).
322 */
323 int
ufsdirhash_lookup(struct inode * ip,const char * name,int namelen,doff_t * offp,struct buf ** bpp,doff_t * prevoffp)324 ufsdirhash_lookup(struct inode *ip, const char *name, int namelen, doff_t *offp,
325 struct buf **bpp, doff_t *prevoffp)
326 {
327 struct dirhash *dh, *dh_next;
328 struct direct *dp;
329 struct vnode *vp;
330 struct buf *bp;
331 doff_t blkoff, bmask, offset, prevoff;
332 int i, slot;
333 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
334 int dirblksiz = ip->i_ump->um_dirblksiz;
335
336 if ((dh = ip->i_dirhash) == NULL)
337 return (EJUSTRETURN);
338
339 /*
340 * Move this dirhash towards the end of the list if it has a
341 * score higher than the next entry, and acquire the dh_lock.
342 * Optimise the case where it's already the last by performing
343 * an unlocked read of the TAILQ_NEXT pointer.
344 *
345 * In both cases, end up holding just dh_lock.
346 */
347 if (TAILQ_NEXT(dh, dh_list) != NULL) {
348 DIRHASHLIST_LOCK();
349 DIRHASH_LOCK(dh);
350 /*
351 * If the new score will be greater than that of the next
352 * entry, then move this entry past it. With both mutexes
353 * held, dh_next won't go away, but its dh_score could
354 * change; that's not important since it is just a hint.
355 */
356 if (dh->dh_hash != NULL &&
357 (dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
358 dh->dh_score >= dh_next->dh_score) {
359 KASSERT(dh->dh_onlist);
360 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
361 TAILQ_INSERT_AFTER(&ufsdirhash_list, dh_next, dh,
362 dh_list);
363 }
364 DIRHASHLIST_UNLOCK();
365 } else {
366 /* Already the last, though that could change as we wait. */
367 DIRHASH_LOCK(dh);
368 }
369 if (dh->dh_hash == NULL) {
370 DIRHASH_UNLOCK(dh);
371 ufsdirhash_free(ip);
372 return (EJUSTRETURN);
373 }
374
375 /* Update the score. */
376 if (dh->dh_score < DH_SCOREMAX)
377 dh->dh_score++;
378
379 vp = ip->i_vnode;
380 bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
381 blkoff = -1;
382 bp = NULL;
383 restart:
384 slot = ufsdirhash_hash(dh, name, namelen);
385
386 if (dh->dh_seqopt) {
387 /*
388 * Sequential access optimisation. dh_seqoff contains the
389 * offset of the directory entry immediately following
390 * the last entry that was looked up. Check if this offset
391 * appears in the hash chain for the name we are looking for.
392 */
393 for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
394 i = WRAPINCR(i, dh->dh_hlen))
395 if (offset == dh->dh_seqoff)
396 break;
397 if (offset == dh->dh_seqoff) {
398 /*
399 * We found an entry with the expected offset. This
400 * is probably the entry we want, but if not, the
401 * code below will turn off seqoff and retry.
402 */
403 slot = i;
404 } else
405 dh->dh_seqopt = 0;
406 }
407
408 for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
409 slot = WRAPINCR(slot, dh->dh_hlen)) {
410 if (offset == DIRHASH_DEL)
411 continue;
412
413 if (offset < 0 || offset >= ip->i_size)
414 panic("ufsdirhash_lookup: bad offset in hash array");
415 if ((offset & ~bmask) != blkoff) {
416 if (bp != NULL)
417 brelse(bp, 0);
418 blkoff = offset & ~bmask;
419 if (ufs_blkatoff(vp, (off_t)blkoff,
420 NULL, &bp, false) != 0) {
421 DIRHASH_UNLOCK(dh);
422 return (EJUSTRETURN);
423 }
424 }
425 dp = (struct direct *)((char *)bp->b_data + (offset & bmask));
426 if (dp->d_reclen == 0 || dp->d_reclen >
427 dirblksiz - (offset & (dirblksiz - 1))) {
428 /* Corrupted directory. */
429 DIRHASH_UNLOCK(dh);
430 brelse(bp, 0);
431 return (EJUSTRETURN);
432 }
433 if (dp->d_namlen == namelen &&
434 memcmp(dp->d_name, name, namelen) == 0) {
435 /* Found. Get the prev offset if needed. */
436 if (prevoffp != NULL) {
437 if (offset & (dirblksiz - 1)) {
438 prevoff = ufsdirhash_getprev(dp,
439 offset, dirblksiz);
440 if (prevoff == -1) {
441 brelse(bp, 0);
442 return (EJUSTRETURN);
443 }
444 } else
445 prevoff = offset;
446 *prevoffp = prevoff;
447 }
448
449 /* Check for sequential access, and update offset. */
450 if (dh->dh_seqopt == 0 && dh->dh_seqoff == offset)
451 dh->dh_seqopt = 1;
452 dh->dh_seqoff = offset + UFS_DIRSIZ(0, dp, needswap);
453 DIRHASH_UNLOCK(dh);
454
455 *bpp = bp;
456 *offp = offset;
457 return (0);
458 }
459
460 if (dh->dh_hash == NULL) {
461 DIRHASH_UNLOCK(dh);
462 if (bp != NULL)
463 brelse(bp, 0);
464 ufsdirhash_free(ip);
465 return (EJUSTRETURN);
466 }
467 /*
468 * When the name doesn't match in the seqopt case, go back
469 * and search normally.
470 */
471 if (dh->dh_seqopt) {
472 dh->dh_seqopt = 0;
473 goto restart;
474 }
475 }
476 DIRHASH_UNLOCK(dh);
477 if (bp != NULL)
478 brelse(bp, 0);
479 return (ENOENT);
480 }
481
482 /*
483 * Find a directory block with room for 'slotneeded' bytes. Returns
484 * the offset of the directory entry that begins the free space.
485 * This will either be the offset of an existing entry that has free
486 * space at the end, or the offset of an entry with d_ino == 0 at
487 * the start of a UFS_DIRBLKSIZ block.
488 *
489 * To use the space, the caller may need to compact existing entries in
490 * the directory. The total number of bytes in all of the entries involved
491 * in the compaction is stored in *slotsize. In other words, all of
492 * the entries that must be compacted are exactly contained in the
493 * region beginning at the returned offset and spanning *slotsize bytes.
494 *
495 * Returns -1 if no space was found, indicating that the directory
496 * must be extended.
497 */
498 doff_t
ufsdirhash_findfree(struct inode * ip,int slotneeded,int * slotsize)499 ufsdirhash_findfree(struct inode *ip, int slotneeded, int *slotsize)
500 {
501 struct direct *dp;
502 struct dirhash *dh;
503 struct buf *bp;
504 doff_t pos, slotstart;
505 int dirblock, error, freebytes, i;
506 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
507 int dirblksiz = ip->i_ump->um_dirblksiz;
508
509 if ((dh = ip->i_dirhash) == NULL)
510 return (-1);
511
512 DIRHASH_LOCK(dh);
513 if (dh->dh_hash == NULL) {
514 DIRHASH_UNLOCK(dh);
515 ufsdirhash_free(ip);
516 return (-1);
517 }
518
519 /* Find a directory block with the desired free space. */
520 dirblock = -1;
521 for (i = howmany(slotneeded, DIRALIGN); i <= DH_NFSTATS; i++)
522 if ((dirblock = dh->dh_firstfree[i]) != -1)
523 break;
524 if (dirblock == -1) {
525 DIRHASH_UNLOCK(dh);
526 return (-1);
527 }
528
529 KASSERT(dirblock < dh->dh_nblk &&
530 dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN));
531 pos = dirblock * dirblksiz;
532 error = ufs_blkatoff(ip->i_vnode, (off_t)pos, (void *)&dp, &bp, false);
533 if (error) {
534 DIRHASH_UNLOCK(dh);
535 return (-1);
536 }
537 /* Find the first entry with free space. */
538 for (i = 0; i < dirblksiz; ) {
539 if (dp->d_reclen == 0) {
540 DIRHASH_UNLOCK(dh);
541 brelse(bp, 0);
542 return (-1);
543 }
544 if (dp->d_ino == 0 || dp->d_reclen > UFS_DIRSIZ(0, dp, needswap))
545 break;
546 i += dp->d_reclen;
547 dp = (struct direct *)((char *)dp + dp->d_reclen);
548 }
549 if (i > dirblksiz) {
550 DIRHASH_UNLOCK(dh);
551 brelse(bp, 0);
552 return (-1);
553 }
554 slotstart = pos + i;
555
556 /* Find the range of entries needed to get enough space */
557 freebytes = 0;
558 while (i < dirblksiz && freebytes < slotneeded) {
559 freebytes += dp->d_reclen;
560 if (dp->d_ino != 0)
561 freebytes -= UFS_DIRSIZ(0, dp, needswap);
562 if (dp->d_reclen == 0) {
563 DIRHASH_UNLOCK(dh);
564 brelse(bp, 0);
565 return (-1);
566 }
567 i += dp->d_reclen;
568 dp = (struct direct *)((char *)dp + dp->d_reclen);
569 }
570 if (i > dirblksiz) {
571 DIRHASH_UNLOCK(dh);
572 brelse(bp, 0);
573 return (-1);
574 }
575 if (freebytes < slotneeded)
576 panic("ufsdirhash_findfree: free mismatch");
577 DIRHASH_UNLOCK(dh);
578 brelse(bp, 0);
579 *slotsize = pos + i - slotstart;
580 return (slotstart);
581 }
582
583 /*
584 * Return the start of the unused space at the end of a directory, or
585 * -1 if there are no trailing unused blocks.
586 */
587 doff_t
ufsdirhash_enduseful(struct inode * ip)588 ufsdirhash_enduseful(struct inode *ip)
589 {
590 struct dirhash *dh;
591 int i;
592 int dirblksiz = ip->i_ump->um_dirblksiz;
593
594 if ((dh = ip->i_dirhash) == NULL)
595 return (-1);
596
597 DIRHASH_LOCK(dh);
598 if (dh->dh_hash == NULL) {
599 DIRHASH_UNLOCK(dh);
600 ufsdirhash_free(ip);
601 return (-1);
602 }
603
604 if (dh->dh_blkfree[dh->dh_dirblks - 1] != dirblksiz / DIRALIGN) {
605 DIRHASH_UNLOCK(dh);
606 return (-1);
607 }
608
609 for (i = dh->dh_dirblks - 1; i >= 0; i--)
610 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
611 break;
612 DIRHASH_UNLOCK(dh);
613 return ((doff_t)(i + 1) * dirblksiz);
614 }
615
616 /*
617 * Insert information into the hash about a new directory entry. dirp
618 * points to a struct direct containing the entry, and offset specifies
619 * the offset of this entry.
620 */
621 void
ufsdirhash_add(struct inode * ip,struct direct * dirp,doff_t offset)622 ufsdirhash_add(struct inode *ip, struct direct *dirp, doff_t offset)
623 {
624 struct dirhash *dh;
625 int slot;
626 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
627 int dirblksiz = ip->i_ump->um_dirblksiz;
628
629 if ((dh = ip->i_dirhash) == NULL)
630 return;
631
632 DIRHASH_LOCK(dh);
633 if (dh->dh_hash == NULL) {
634 DIRHASH_UNLOCK(dh);
635 ufsdirhash_free(ip);
636 return;
637 }
638
639 KASSERT(offset < dh->dh_dirblks * dirblksiz);
640 /*
641 * Normal hash usage is < 66%. If the usage gets too high then
642 * remove the hash entirely and let it be rebuilt later.
643 */
644 if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
645 DIRHASH_UNLOCK(dh);
646 ufsdirhash_free(ip);
647 return;
648 }
649
650 /* Find a free hash slot (empty or deleted), and add the entry. */
651 slot = ufsdirhash_hash(dh, dirp->d_name, dirp->d_namlen);
652 while (DH_ENTRY(dh, slot) >= 0)
653 slot = WRAPINCR(slot, dh->dh_hlen);
654 if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
655 dh->dh_hused++;
656 DH_ENTRY(dh, slot) = offset;
657
658 /* Update the per-block summary info. */
659 ufsdirhash_adjfree(dh, offset, -UFS_DIRSIZ(0, dirp, needswap), dirblksiz);
660 DIRHASH_UNLOCK(dh);
661 }
662
663 /*
664 * Remove the specified directory entry from the hash. The entry to remove
665 * is defined by the name in `dirp', which must exist at the specified
666 * `offset' within the directory.
667 */
668 void
ufsdirhash_remove(struct inode * ip,struct direct * dirp,doff_t offset)669 ufsdirhash_remove(struct inode *ip, struct direct *dirp, doff_t offset)
670 {
671 struct dirhash *dh;
672 int slot;
673 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
674 int dirblksiz = ip->i_ump->um_dirblksiz;
675
676 if ((dh = ip->i_dirhash) == NULL)
677 return;
678
679 DIRHASH_LOCK(dh);
680 if (dh->dh_hash == NULL) {
681 DIRHASH_UNLOCK(dh);
682 ufsdirhash_free(ip);
683 return;
684 }
685
686 KASSERT(offset < dh->dh_dirblks * dirblksiz);
687 /* Find the entry */
688 slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, offset);
689
690 /* Remove the hash entry. */
691 ufsdirhash_delslot(dh, slot);
692
693 /* Update the per-block summary info. */
694 ufsdirhash_adjfree(dh, offset, UFS_DIRSIZ(0, dirp, needswap), dirblksiz);
695 DIRHASH_UNLOCK(dh);
696 }
697
698 /*
699 * Change the offset associated with a directory entry in the hash. Used
700 * when compacting directory blocks.
701 */
702 void
ufsdirhash_move(struct inode * ip,struct direct * dirp,doff_t oldoff,doff_t newoff)703 ufsdirhash_move(struct inode *ip, struct direct *dirp, doff_t oldoff,
704 doff_t newoff)
705 {
706 struct dirhash *dh;
707 int slot;
708
709 if ((dh = ip->i_dirhash) == NULL)
710 return;
711 DIRHASH_LOCK(dh);
712 if (dh->dh_hash == NULL) {
713 DIRHASH_UNLOCK(dh);
714 ufsdirhash_free(ip);
715 return;
716 }
717
718 KASSERT(oldoff < dh->dh_dirblks * ip->i_ump->um_dirblksiz &&
719 newoff < dh->dh_dirblks * ip->i_ump->um_dirblksiz);
720 /* Find the entry, and update the offset. */
721 slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, oldoff);
722 DH_ENTRY(dh, slot) = newoff;
723 DIRHASH_UNLOCK(dh);
724 }
725
726 /*
727 * Inform dirhash that the directory has grown by one block that
728 * begins at offset (i.e. the new length is offset + UFS_DIRBLKSIZ).
729 */
730 void
ufsdirhash_newblk(struct inode * ip,doff_t offset)731 ufsdirhash_newblk(struct inode *ip, doff_t offset)
732 {
733 struct dirhash *dh;
734 int block;
735 int dirblksiz = ip->i_ump->um_dirblksiz;
736
737 if ((dh = ip->i_dirhash) == NULL)
738 return;
739 DIRHASH_LOCK(dh);
740 if (dh->dh_hash == NULL) {
741 DIRHASH_UNLOCK(dh);
742 ufsdirhash_free(ip);
743 return;
744 }
745
746 KASSERT(offset == dh->dh_dirblks * dirblksiz);
747 block = offset / dirblksiz;
748 if (block >= dh->dh_nblk) {
749 /* Out of space; must rebuild. */
750 DIRHASH_UNLOCK(dh);
751 ufsdirhash_free(ip);
752 return;
753 }
754 dh->dh_dirblks = block + 1;
755
756 /* Account for the new free block. */
757 dh->dh_blkfree[block] = dirblksiz / DIRALIGN;
758 if (dh->dh_firstfree[DH_NFSTATS] == -1)
759 dh->dh_firstfree[DH_NFSTATS] = block;
760 DIRHASH_UNLOCK(dh);
761 }
762
763 /*
764 * Inform dirhash that the directory is being truncated.
765 */
766 void
ufsdirhash_dirtrunc(struct inode * ip,doff_t offset)767 ufsdirhash_dirtrunc(struct inode *ip, doff_t offset)
768 {
769 struct dirhash *dh;
770 int block, i;
771 int dirblksiz = ip->i_ump->um_dirblksiz;
772
773 if ((dh = ip->i_dirhash) == NULL)
774 return;
775
776 DIRHASH_LOCK(dh);
777 if (dh->dh_hash == NULL) {
778 DIRHASH_UNLOCK(dh);
779 ufsdirhash_free(ip);
780 return;
781 }
782
783 KASSERT(offset <= dh->dh_dirblks * dirblksiz);
784 block = howmany(offset, dirblksiz);
785 /*
786 * If the directory shrinks to less than 1/8 of dh_nblk blocks
787 * (about 20% of its original size due to the 50% extra added in
788 * ufsdirhash_build) then free it, and let the caller rebuild
789 * if necessary.
790 */
791 if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
792 DIRHASH_UNLOCK(dh);
793 ufsdirhash_free(ip);
794 return;
795 }
796
797 /*
798 * Remove any `first free' information pertaining to the
799 * truncated blocks. All blocks we're removing should be
800 * completely unused.
801 */
802 if (dh->dh_firstfree[DH_NFSTATS] >= block)
803 dh->dh_firstfree[DH_NFSTATS] = -1;
804 for (i = block; i < dh->dh_dirblks; i++)
805 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
806 panic("ufsdirhash_dirtrunc: blocks in use");
807 for (i = 0; i < DH_NFSTATS; i++)
808 if (dh->dh_firstfree[i] >= block)
809 panic("ufsdirhash_dirtrunc: first free corrupt");
810 dh->dh_dirblks = block;
811 DIRHASH_UNLOCK(dh);
812 }
813
814 /*
815 * Debugging function to check that the dirhash information about
816 * a directory block matches its actual contents. Panics if a mismatch
817 * is detected.
818 *
819 * On entry, `sbuf' should point to the start of an in-core
820 * DIRBLKSIZ-sized directory block, and `offset' should contain the
821 * offset from the start of the directory of that block.
822 */
823 void
ufsdirhash_checkblock(struct inode * ip,char * sbuf,doff_t offset)824 ufsdirhash_checkblock(struct inode *ip, char *sbuf, doff_t offset)
825 {
826 struct dirhash *dh;
827 struct direct *dp;
828 int block, ffslot, i, nfree;
829 const int needswap = UFS_MPNEEDSWAP(ip->i_ump);
830 int dirblksiz = ip->i_ump->um_dirblksiz;
831
832 if (!ufs_dirhashcheck)
833 return;
834 if ((dh = ip->i_dirhash) == NULL)
835 return;
836
837 DIRHASH_LOCK(dh);
838 if (dh->dh_hash == NULL) {
839 DIRHASH_UNLOCK(dh);
840 ufsdirhash_free(ip);
841 return;
842 }
843
844 block = offset / dirblksiz;
845 if ((offset & (dirblksiz - 1)) != 0 || block >= dh->dh_dirblks)
846 panic("ufsdirhash_checkblock: bad offset");
847
848 nfree = 0;
849 for (i = 0; i < dirblksiz; i += dp->d_reclen) {
850 dp = (struct direct *)(sbuf + i);
851 if (dp->d_reclen == 0 || i + dp->d_reclen > dirblksiz)
852 panic("ufsdirhash_checkblock: bad dir");
853
854 if (dp->d_ino == 0) {
855 #if 0
856 /*
857 * XXX entries with d_ino == 0 should only occur
858 * at the start of a DIRBLKSIZ block. However the
859 * ufs code is tolerant of such entries at other
860 * offsets, and fsck does not fix them.
861 */
862 if (i != 0)
863 panic("ufsdirhash_checkblock: bad dir inode");
864 #endif
865 nfree += dp->d_reclen;
866 continue;
867 }
868
869 /* Check that the entry exists (will panic if it doesn't). */
870 ufsdirhash_findslot(dh, dp->d_name, dp->d_namlen, offset + i);
871
872 nfree += dp->d_reclen - UFS_DIRSIZ(0, dp, needswap);
873 }
874 if (i != dirblksiz)
875 panic("ufsdirhash_checkblock: bad dir end");
876
877 if (dh->dh_blkfree[block] * DIRALIGN != nfree)
878 panic("ufsdirhash_checkblock: bad free count");
879
880 ffslot = BLKFREE2IDX(nfree / DIRALIGN);
881 for (i = 0; i <= DH_NFSTATS; i++)
882 if (dh->dh_firstfree[i] == block && i != ffslot)
883 panic("ufsdirhash_checkblock: bad first-free");
884 if (dh->dh_firstfree[ffslot] == -1)
885 panic("ufsdirhash_checkblock: missing first-free entry");
886 DIRHASH_UNLOCK(dh);
887 }
888
889 /*
890 * Hash the specified filename into a dirhash slot.
891 */
892 static int
ufsdirhash_hash(struct dirhash * dh,const char * name,int namelen)893 ufsdirhash_hash(struct dirhash *dh, const char *name, int namelen)
894 {
895 u_int32_t hash;
896
897 /*
898 * We hash the name and then some other bit of data that is
899 * invariant over the dirhash's lifetime. Otherwise names
900 * differing only in the last byte are placed close to one
901 * another in the table, which is bad for linear probing.
902 */
903 hash = hash32_buf(name, namelen, HASH32_BUF_INIT);
904 hash = hash32_buf(&dh, sizeof(dh), hash);
905 return (hash % dh->dh_hlen);
906 }
907
908 /*
909 * Adjust the number of free bytes in the block containing `offset'
910 * by the value specified by `diff'.
911 *
912 * The caller must ensure we have exclusive access to `dh'; normally
913 * that means that dh_lock should be held, but this is also called
914 * from ufsdirhash_build() where exclusive access can be assumed.
915 */
916 static void
ufsdirhash_adjfree(struct dirhash * dh,doff_t offset,int diff,int dirblksiz)917 ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff, int dirblksiz)
918 {
919 int block, i, nfidx, ofidx;
920
921 KASSERT(mutex_owned(&dh->dh_lock));
922
923 /* Update the per-block summary info. */
924 block = offset / dirblksiz;
925 KASSERT(block < dh->dh_nblk && block < dh->dh_dirblks);
926 ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
927 dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
928 nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
929
930 /* Update the `first free' list if necessary. */
931 if (ofidx != nfidx) {
932 /* If removing, scan forward for the next block. */
933 if (dh->dh_firstfree[ofidx] == block) {
934 for (i = block + 1; i < dh->dh_dirblks; i++)
935 if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
936 break;
937 dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
938 }
939
940 /* Make this the new `first free' if necessary */
941 if (dh->dh_firstfree[nfidx] > block ||
942 dh->dh_firstfree[nfidx] == -1)
943 dh->dh_firstfree[nfidx] = block;
944 }
945 }
946
947 /*
948 * Find the specified name which should have the specified offset.
949 * Returns a slot number, and panics on failure.
950 *
951 * `dh' must be locked on entry and remains so on return.
952 */
953 static int
ufsdirhash_findslot(struct dirhash * dh,const char * name,int namelen,doff_t offset)954 ufsdirhash_findslot(struct dirhash *dh, const char *name, int namelen,
955 doff_t offset)
956 {
957 int slot;
958
959 KASSERT(mutex_owned(&dh->dh_lock));
960
961 /* Find the entry. */
962 KASSERT(dh->dh_hused < dh->dh_hlen);
963 slot = ufsdirhash_hash(dh, name, namelen);
964 while (DH_ENTRY(dh, slot) != offset &&
965 DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
966 slot = WRAPINCR(slot, dh->dh_hlen);
967 if (DH_ENTRY(dh, slot) != offset)
968 panic("ufsdirhash_findslot: '%.*s' not found", namelen, name);
969
970 return (slot);
971 }
972
973 /*
974 * Remove the entry corresponding to the specified slot from the hash array.
975 *
976 * `dh' must be locked on entry and remains so on return.
977 */
978 static void
ufsdirhash_delslot(struct dirhash * dh,int slot)979 ufsdirhash_delslot(struct dirhash *dh, int slot)
980 {
981 int i;
982
983 KASSERT(mutex_owned(&dh->dh_lock));
984
985 /* Mark the entry as deleted. */
986 DH_ENTRY(dh, slot) = DIRHASH_DEL;
987
988 /* If this is the end of a chain of DIRHASH_DEL slots, remove them. */
989 for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
990 i = WRAPINCR(i, dh->dh_hlen);
991 if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
992 i = WRAPDECR(i, dh->dh_hlen);
993 while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
994 DH_ENTRY(dh, i) = DIRHASH_EMPTY;
995 dh->dh_hused--;
996 i = WRAPDECR(i, dh->dh_hlen);
997 }
998 KASSERT(dh->dh_hused >= 0);
999 }
1000 }
1001
1002 /*
1003 * Given a directory entry and its offset, find the offset of the
1004 * previous entry in the same UFS_DIRBLKSIZ-sized block. Returns an
1005 * offset, or -1 if there is no previous entry in the block or some
1006 * other problem occurred.
1007 */
1008 static doff_t
ufsdirhash_getprev(struct direct * dirp,doff_t offset,int dirblksiz)1009 ufsdirhash_getprev(struct direct *dirp, doff_t offset, int dirblksiz)
1010 {
1011 struct direct *dp;
1012 char *blkbuf;
1013 doff_t blkoff, prevoff;
1014 int entrypos, i;
1015
1016 blkoff = offset & ~(dirblksiz - 1); /* offset of start of block */
1017 entrypos = offset & (dirblksiz - 1); /* entry relative to block */
1018 blkbuf = (char *)dirp - entrypos;
1019 prevoff = blkoff;
1020
1021 /* If `offset' is the start of a block, there is no previous entry. */
1022 if (entrypos == 0)
1023 return (-1);
1024
1025 /* Scan from the start of the block until we get to the entry. */
1026 for (i = 0; i < entrypos; i += dp->d_reclen) {
1027 dp = (struct direct *)(blkbuf + i);
1028 if (dp->d_reclen == 0 || i + dp->d_reclen > entrypos)
1029 return (-1); /* Corrupted directory. */
1030 prevoff = blkoff + i;
1031 }
1032 return (prevoff);
1033 }
1034
1035 /*
1036 * Try to free up `wanted' bytes by stealing memory from existing
1037 * dirhashes. Returns zero with list locked if successful.
1038 */
1039 static int
ufsdirhash_recycle(int wanted)1040 ufsdirhash_recycle(int wanted)
1041 {
1042 struct dirhash *dh;
1043 doff_t **hash;
1044 u_int8_t *blkfree;
1045 int i, mem, narrays;
1046 size_t hashsz, blkfreesz;
1047
1048 DIRHASHLIST_LOCK();
1049 while (wanted + ufs_dirhashmem > ufs_dirhashmaxmem) {
1050 /* Find a dirhash, and lock it. */
1051 if ((dh = TAILQ_FIRST(&ufsdirhash_list)) == NULL) {
1052 DIRHASHLIST_UNLOCK();
1053 return (-1);
1054 }
1055 DIRHASH_LOCK(dh);
1056 KASSERT(dh->dh_hash != NULL);
1057
1058 /* Decrement the score; only recycle if it becomes zero. */
1059 if (--dh->dh_score > 0) {
1060 DIRHASH_UNLOCK(dh);
1061 DIRHASHLIST_UNLOCK();
1062 return (-1);
1063 }
1064
1065 /* Remove it from the list and detach its memory. */
1066 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
1067 dh->dh_onlist = 0;
1068 hash = dh->dh_hash;
1069 hashsz = dh->dh_hashsz;
1070 dh->dh_hash = NULL;
1071 blkfree = dh->dh_blkfree;
1072 blkfreesz = dh->dh_blkfreesz;
1073 dh->dh_blkfree = NULL;
1074 narrays = dh->dh_narrays;
1075 mem = narrays * sizeof(*dh->dh_hash) +
1076 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
1077 dh->dh_nblk * sizeof(*dh->dh_blkfree);
1078
1079 /* Unlock everything, free the detached memory. */
1080 DIRHASH_UNLOCK(dh);
1081 DIRHASHLIST_UNLOCK();
1082
1083 for (i = 0; i < narrays; i++)
1084 DIRHASH_BLKFREE(hash[i]);
1085 kmem_free(hash, hashsz);
1086 kmem_free(blkfree, blkfreesz);
1087
1088 /* Account for the returned memory, and repeat if necessary. */
1089 DIRHASHLIST_LOCK();
1090 atomic_add_int(&ufs_dirhashmem, -mem);
1091 }
1092 /* Success. */
1093 return (0);
1094 }
1095
1096 static void
ufsdirhash_sysctl_init(void)1097 ufsdirhash_sysctl_init(void)
1098 {
1099 const struct sysctlnode *rnode, *cnode;
1100
1101 sysctl_createv(&ufsdirhash_sysctl_log, 0, NULL, &rnode,
1102 CTLFLAG_PERMANENT,
1103 CTLTYPE_NODE, "ufs",
1104 SYSCTL_DESCR("ufs"),
1105 NULL, 0, NULL, 0,
1106 CTL_VFS, CTL_CREATE, CTL_EOL);
1107
1108 sysctl_createv(&ufsdirhash_sysctl_log, 0, &rnode, &rnode,
1109 CTLFLAG_PERMANENT,
1110 CTLTYPE_NODE, "dirhash",
1111 SYSCTL_DESCR("dirhash"),
1112 NULL, 0, NULL, 0,
1113 CTL_CREATE, CTL_EOL);
1114
1115 sysctl_createv(&ufsdirhash_sysctl_log, 0, &rnode, &cnode,
1116 CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
1117 CTLTYPE_INT, "minblocks",
1118 SYSCTL_DESCR("minimum hashed directory size in blocks"),
1119 NULL, 0, &ufs_dirhashminblks, 0,
1120 CTL_CREATE, CTL_EOL);
1121
1122 sysctl_createv(&ufsdirhash_sysctl_log, 0, &rnode, &cnode,
1123 CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
1124 CTLTYPE_INT, "maxmem",
1125 SYSCTL_DESCR("maximum dirhash memory usage"),
1126 NULL, 0, &ufs_dirhashmaxmem, 0,
1127 CTL_CREATE, CTL_EOL);
1128
1129 sysctl_createv(&ufsdirhash_sysctl_log, 0, &rnode, &cnode,
1130 CTLFLAG_PERMANENT|CTLFLAG_READONLY,
1131 CTLTYPE_INT, "memused",
1132 SYSCTL_DESCR("current dirhash memory usage"),
1133 NULL, 0, &ufs_dirhashmem, 0,
1134 CTL_CREATE, CTL_EOL);
1135
1136 sysctl_createv(&ufsdirhash_sysctl_log, 0, &rnode, &cnode,
1137 CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
1138 CTLTYPE_INT, "docheck",
1139 SYSCTL_DESCR("enable extra sanity checks"),
1140 NULL, 0, &ufs_dirhashcheck, 0,
1141 CTL_CREATE, CTL_EOL);
1142 }
1143
1144 void
ufsdirhash_init(void)1145 ufsdirhash_init(void)
1146 {
1147
1148 mutex_init(&ufsdirhash_lock, MUTEX_DEFAULT, IPL_NONE);
1149 ufsdirhashblk_cache = pool_cache_init(DH_NBLKOFF * sizeof(daddr_t), 0,
1150 0, 0, "dirhashblk", NULL, IPL_NONE, NULL, NULL, NULL);
1151 ufsdirhash_cache = pool_cache_init(sizeof(struct dirhash), 0,
1152 0, 0, "dirhash", NULL, IPL_NONE, NULL, NULL, NULL);
1153 TAILQ_INIT(&ufsdirhash_list);
1154 ufsdirhash_sysctl_init();
1155 }
1156
1157 void
ufsdirhash_done(void)1158 ufsdirhash_done(void)
1159 {
1160
1161 KASSERT(TAILQ_EMPTY(&ufsdirhash_list));
1162 pool_cache_destroy(ufsdirhashblk_cache);
1163 pool_cache_destroy(ufsdirhash_cache);
1164 mutex_destroy(&ufsdirhash_lock);
1165 sysctl_teardown(&ufsdirhash_sysctl_log);
1166 }
1167