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