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