1 /* $NetBSD: vfs_dirhash.c,v 1.16 2024/12/07 02:11:42 riastradh Exp $ */
2
3 /*
4 * Copyright (c) 2008 Reinoud Zandijk
5 * 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 ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 */
28
29 #include <sys/cdefs.h>
30 __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.16 2024/12/07 02:11:42 riastradh Exp $");
31
32 /* CLEAN UP! */
33 #include <sys/param.h>
34 #include <sys/types.h>
35
36 #include <sys/buf.h>
37 #include <sys/dirent.h>
38 #include <sys/dirhash.h>
39 #include <sys/hash.h>
40 #include <sys/kernel.h>
41 #include <sys/mutex.h>
42 #include <sys/pool.h>
43 #include <sys/queue.h>
44 #include <sys/sysctl.h>
45 #include <sys/vnode.h>
46
47 #if 1
48 # define DPRINTF(a) __nothing
49 #else
50 # define DPRINTF(a) printf a
51 #endif
52
53 /*
54 * The locking protocol of the dirhash structures is fairly simple:
55 *
56 * The global dirhash_queue is protected by the dirhashmutex. This lock is
57 * internal only and is FS/mountpoint/vnode independent. On exit of the
58 * exported functions this mutex is not held.
59 *
60 * The dirhash structure is considered part of the vnode/inode structure and
61 * will thus use the lock that protects that vnode/inode.
62 *
63 * The dirhash entries are considered part of the dirhash structure and thus
64 * are on the same lock.
65 */
66
67 static struct sysctllog *sysctl_log;
68 static struct pool dirhash_pool;
69 static struct pool dirhash_entry_pool;
70
71 static kmutex_t dirhashmutex;
72 static uint32_t maxdirhashsize = DIRHASH_SIZE;
73 static uint32_t dirhashsize = 0;
74 static TAILQ_HEAD(_dirhash, dirhash) dirhash_queue;
75
76
77 void
dirhash_init(void)78 dirhash_init(void)
79 {
80 const struct sysctlnode *rnode, *cnode;
81 size_t sz;
82 uint32_t max_entries;
83
84 /* initialise dirhash queue */
85 TAILQ_INIT(&dirhash_queue);
86
87 /* init dirhash pools */
88 sz = sizeof(struct dirhash);
89 pool_init(&dirhash_pool, sz, 0, 0, 0,
90 "dirhpl", NULL, IPL_NONE);
91
92 sz = sizeof(struct dirhash_entry);
93 pool_init(&dirhash_entry_pool, sz, 0, 0, 0,
94 "dirhepl", NULL, IPL_NONE);
95
96 mutex_init(&dirhashmutex, MUTEX_DEFAULT, IPL_NONE);
97 max_entries = maxdirhashsize / sz;
98 pool_sethiwat(&dirhash_entry_pool, max_entries);
99 dirhashsize = 0;
100
101 /* create sysctl knobs and dials */
102 sysctl_log = NULL;
103 sysctl_createv(&sysctl_log, 0, NULL, &rnode,
104 CTLFLAG_PERMANENT,
105 CTLTYPE_NODE, "dirhash", NULL,
106 NULL, 0, NULL, 0,
107 CTL_VFS, VFS_GENERIC, CTL_CREATE, CTL_EOL);
108 sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
109 CTLFLAG_PERMANENT,
110 CTLTYPE_INT, "memused",
111 SYSCTL_DESCR("current dirhash memory usage"),
112 NULL, 0, &dirhashsize, 0,
113 CTL_CREATE, CTL_EOL);
114 sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
115 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
116 CTLTYPE_INT, "maxmem",
117 SYSCTL_DESCR("maximum dirhash memory usage"),
118 NULL, 0, &maxdirhashsize, 0,
119 CTL_CREATE, CTL_EOL);
120 }
121
122
123 #if 0
124 void
125 dirhash_finish(void)
126 {
127 pool_destroy(&dirhash_pool);
128 pool_destroy(&dirhash_entry_pool);
129
130 mutex_destroy(&dirhashmutex);
131
132 /* sysctl_teardown(&sysctl_log); */
133 }
134 #endif
135
136 /*
137 * generic dirhash implementation
138 */
139
140 void
dirhash_purge_entries(struct dirhash * dirh)141 dirhash_purge_entries(struct dirhash *dirh)
142 {
143 struct dirhash_entry *dirh_e;
144 uint32_t hashline;
145
146 if (dirh == NULL)
147 return;
148
149 if (dirh->size == 0)
150 return;
151
152 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
153 while ((dirh_e = LIST_FIRST(&dirh->entries[hashline]))
154 != NULL) {
155 LIST_REMOVE(dirh_e, next);
156 pool_put(&dirhash_entry_pool, dirh_e);
157 }
158 }
159
160 while ((dirh_e = LIST_FIRST(&dirh->free_entries)) != NULL) {
161 LIST_REMOVE(dirh_e, next);
162 pool_put(&dirhash_entry_pool, dirh_e);
163 }
164
165 dirh->flags &= ~DIRH_COMPLETE;
166 dirh->flags |= DIRH_PURGED;
167 dirh->num_files = 0;
168
169 dirhashsize -= dirh->size;
170 dirh->size = 0;
171 }
172
173 void
dirhash_purge(struct dirhash ** dirhp)174 dirhash_purge(struct dirhash **dirhp)
175 {
176 struct dirhash *dirh = *dirhp;
177
178 if (dirh == NULL)
179 return;
180
181 /* purge its entries */
182 dirhash_purge_entries(dirh);
183
184 /* recycle */
185 mutex_enter(&dirhashmutex);
186 TAILQ_REMOVE(&dirhash_queue, dirh, next);
187 mutex_exit(&dirhashmutex);
188
189 pool_put(&dirhash_pool, dirh);
190 *dirhp = NULL;
191 }
192
193 void
dirhash_get(struct dirhash ** dirhp)194 dirhash_get(struct dirhash **dirhp)
195 {
196 struct dirhash *dirh;
197 uint32_t hashline;
198
199 /* if no dirhash was given, allocate one */
200 dirh = *dirhp;
201 if (dirh == NULL) {
202 dirh = pool_get(&dirhash_pool, PR_WAITOK | PR_ZERO);
203 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
204 LIST_INIT(&dirh->entries[hashline]);
205 }
206 }
207
208 /* implement LRU on the dirhash queue */
209 mutex_enter(&dirhashmutex);
210 if (*dirhp) {
211 /* remove from queue to be requeued */
212 TAILQ_REMOVE(&dirhash_queue, dirh, next);
213 }
214 dirh->refcnt++;
215 TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next);
216 mutex_exit(&dirhashmutex);
217
218 *dirhp = dirh;
219 }
220
221 void
dirhash_put(struct dirhash * dirh)222 dirhash_put(struct dirhash *dirh)
223 {
224
225 mutex_enter(&dirhashmutex);
226 dirh->refcnt--;
227 mutex_exit(&dirhashmutex);
228 }
229
230 void
dirhash_enter(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size,int new_p)231 dirhash_enter(struct dirhash *dirh,
232 struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new_p)
233 {
234 struct dirhash *del_dirh, *prev_dirh;
235 struct dirhash_entry *dirh_e;
236 uint32_t hashvalue, hashline;
237 int entrysize;
238
239 /* make sure we have a dirhash to work on */
240 KASSERT(dirh);
241 KASSERT(dirh->refcnt > 0);
242
243 /* are we trying to re-enter an entry? */
244 if (!new_p && (dirh->flags & DIRH_COMPLETE))
245 return;
246
247 /* calculate our hash */
248 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen,
249 HASH32_STR_INIT);
250 hashline = hashvalue & DIRHASH_HASHMASK;
251
252 /* lookup and insert entry if not there yet */
253 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
254 /* check for hash collision */
255 if (dirh_e->hashvalue != hashvalue)
256 continue;
257 if (dirh_e->offset != offset)
258 continue;
259 /* got it already */
260 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
261 KASSERT(dirh_e->entry_size == entry_size);
262 return;
263 }
264
265 DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n",
266 offset, entry_size, dirent->d_namlen,
267 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
268
269 /* check if entry is in free space list */
270 LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
271 if (dirh_e->offset == offset) {
272 DPRINTF(("\tremoving free entry\n"));
273 LIST_REMOVE(dirh_e, next);
274 pool_put(&dirhash_entry_pool, dirh_e);
275 break;
276 }
277 }
278
279 /* ensure we are not passing the dirhash limit */
280 entrysize = sizeof(struct dirhash_entry);
281 if (dirhashsize + entrysize > maxdirhashsize) {
282 /* we walk the dirhash_queue, so need to lock it */
283 mutex_enter(&dirhashmutex);
284 del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash);
285 KASSERT(del_dirh);
286 while (dirhashsize + entrysize > maxdirhashsize) {
287 /* no use trying to delete myself */
288 if (del_dirh == dirh)
289 break;
290 prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next);
291 if (del_dirh->refcnt == 0)
292 dirhash_purge_entries(del_dirh);
293 del_dirh = prev_dirh;
294 }
295 mutex_exit(&dirhashmutex);
296 }
297
298 /* add to the hashline */
299 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);
300
301 dirh_e->hashvalue = hashvalue;
302 dirh_e->offset = offset;
303 dirh_e->d_namlen = dirent->d_namlen;
304 dirh_e->entry_size = entry_size;
305
306 dirh->size += sizeof(struct dirhash_entry);
307 dirh->num_files++;
308 dirhashsize += sizeof(struct dirhash_entry);
309 LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next);
310 }
311
312 void
dirhash_enter_freed(struct dirhash * dirh,uint64_t offset,uint32_t entry_size)313 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, uint32_t entry_size)
314 {
315 struct dirhash_entry *dirh_e;
316
317 /* make sure we have a dirhash to work on */
318 KASSERT(dirh);
319 KASSERT(dirh->refcnt > 0);
320
321 /* check for double entry of free space */
322 LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
323 KASSERT(dirh_e->offset != offset);
324 }
325
326 DPRINTF(("dirhash enter FREED %"PRIu64", %d\n",
327 offset, entry_size));
328 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);
329
330 dirh_e->hashvalue = 0; /* not relevant */
331 dirh_e->offset = offset;
332 dirh_e->d_namlen = 0; /* not relevant */
333 dirh_e->entry_size = entry_size;
334
335 /* XXX it might be preferable to append them at the tail */
336 LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
337 dirh->size += sizeof(struct dirhash_entry);
338 dirhashsize += sizeof(struct dirhash_entry);
339 }
340
341 void
dirhash_remove(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size)342 dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
343 uint64_t offset, uint32_t entry_size)
344 {
345 struct dirhash_entry *dirh_e;
346 uint32_t hashvalue, hashline;
347
348 DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
349 offset, entry_size,
350 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
351
352 /* make sure we have a dirhash to work on */
353 KASSERT(dirh);
354 KASSERT(dirh->refcnt > 0);
355
356 /* calculate our hash */
357 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen,
358 HASH32_STR_INIT);
359 hashline = hashvalue & DIRHASH_HASHMASK;
360
361 /* lookup entry */
362 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
363 /* check for hash collision */
364 if (dirh_e->hashvalue != hashvalue)
365 continue;
366 if (dirh_e->offset != offset)
367 continue;
368
369 /* got it! */
370 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
371 KASSERT(dirh_e->entry_size == entry_size);
372 LIST_REMOVE(dirh_e, next);
373 dirh->size -= sizeof(struct dirhash_entry);
374 KASSERT(dirh->num_files > 0);
375 dirh->num_files--;
376 dirhashsize -= sizeof(struct dirhash_entry);
377
378 dirhash_enter_freed(dirh, offset, entry_size);
379 return;
380 }
381
382 /* not found! */
383 panic("dirhash_remove couldn't find entry in hash table\n");
384 }
385
386 /*
387 * BUGALERT: don't use result longer than needed, never past the node lock.
388 * Call with NULL *result initially and it will return nonzero if again.
389 */
390 int
dirhash_lookup(struct dirhash * dirh,const char * d_name,int d_namlen,struct dirhash_entry ** result)391 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
392 struct dirhash_entry **result)
393 {
394 struct dirhash_entry *dirh_e;
395 uint32_t hashvalue, hashline;
396
397 /* make sure we have a dirhash to work on */
398 KASSERT(dirh);
399 KASSERT(dirh->refcnt > 0);
400
401 /* start where we were */
402 if (*result) {
403 dirh_e = *result;
404
405 /* retrieve information to avoid recalculation and advance */
406 hashvalue = dirh_e->hashvalue;
407 dirh_e = LIST_NEXT(*result, next);
408 } else {
409 /* calculate our hash and lookup all entries in hashline */
410 hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
411 hashline = hashvalue & DIRHASH_HASHMASK;
412 dirh_e = LIST_FIRST(&dirh->entries[hashline]);
413 }
414
415 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
416 /* check for hash collision */
417 if (dirh_e->hashvalue != hashvalue)
418 continue;
419 if (dirh_e->d_namlen != d_namlen)
420 continue;
421 /* might have an entry in the cache */
422 *result = dirh_e;
423 return 1;
424 }
425
426 *result = NULL;
427 return 0;
428 }
429
430 /*
431 * BUGALERT: don't use result longer than needed, never past the node lock.
432 * Call with NULL *result initially and it will return nonzero if again.
433 */
434 int
dirhash_lookup_freed(struct dirhash * dirh,uint32_t min_entrysize,struct dirhash_entry ** result)435 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
436 struct dirhash_entry **result)
437 {
438 struct dirhash_entry *dirh_e;
439
440 /* make sure we have a dirhash to work on */
441 KASSERT(dirh);
442 KASSERT(dirh->refcnt > 0);
443
444 /* start where we were */
445 if (*result) {
446 dirh_e = LIST_NEXT(*result, next);
447 } else {
448 /* lookup all entries that match */
449 dirh_e = LIST_FIRST(&dirh->free_entries);
450 }
451
452 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
453 /* check for minimum size */
454 if (dirh_e->entry_size < min_entrysize)
455 continue;
456 /* might be a candidate */
457 *result = dirh_e;
458 return 1;
459 }
460
461 *result = NULL;
462 return 0;
463 }
464
465 bool
dirhash_dir_isempty(struct dirhash * dirh)466 dirhash_dir_isempty(struct dirhash *dirh)
467 {
468 #ifdef DEBUG
469 struct dirhash_entry *dirh_e;
470 int hashline, num;
471
472 num = 0;
473 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
474 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
475 num++;
476 }
477 }
478
479 if (dirh->num_files != num) {
480 printf("dirhash_dir_isempy: dirhash_counter failed: "
481 "dirh->num_files = %d, counted %d\n",
482 dirh->num_files, num);
483 assert(dirh->num_files == num);
484 }
485 #endif
486 /* assert the directory hash info is valid */
487 KASSERT(dirh->flags & DIRH_COMPLETE);
488
489 /* the directory is empty when only '..' lifes in it or is absent */
490 return (dirh->num_files <= 1);
491 }
492