1 /* $NetBSD: vfs_dirhash.c,v 1.15 2022/09/28 09:57:13 reinoud 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
30 #include <sys/cdefs.h>
31 __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.15 2022/09/28 09:57:13 reinoud Exp $");
32
33 /* CLEAN UP! */
34 #include <sys/param.h>
35 #include <sys/kernel.h>
36 #include <sys/buf.h>
37 #include <sys/dirent.h>
38 #include <sys/hash.h>
39 #include <sys/mutex.h>
40 #include <sys/pool.h>
41 #include <sys/queue.h>
42 #include <sys/vnode.h>
43 #include <sys/sysctl.h>
44
45 #include <sys/dirhash.h>
46
47 #if 1
48 # define DPRINTF(a) ;
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 /*
138 * generic dirhash implementation
139 */
140
141 void
dirhash_purge_entries(struct dirhash * dirh)142 dirhash_purge_entries(struct dirhash *dirh)
143 {
144 struct dirhash_entry *dirh_e;
145 uint32_t hashline;
146
147 if (dirh == NULL)
148 return;
149
150 if (dirh->size == 0)
151 return;
152
153 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
154 while ((dirh_e =
155 LIST_FIRST(&dirh->entries[hashline])) != NULL) {
156 LIST_REMOVE(dirh_e, next);
157 pool_put(&dirhash_entry_pool, dirh_e);
158 }
159 }
160
161 while ((dirh_e = LIST_FIRST(&dirh->free_entries)) != NULL) {
162 LIST_REMOVE(dirh_e, next);
163 pool_put(&dirhash_entry_pool, dirh_e);
164 }
165
166 dirh->flags &= ~DIRH_COMPLETE;
167 dirh->flags |= DIRH_PURGED;
168 dirh->num_files = 0;
169
170 dirhashsize -= dirh->size;
171 dirh->size = 0;
172 }
173
174
175 void
dirhash_purge(struct dirhash ** dirhp)176 dirhash_purge(struct dirhash **dirhp)
177 {
178 struct dirhash *dirh = *dirhp;
179
180 if (dirh == NULL)
181 return;
182
183 /* purge its entries */
184 dirhash_purge_entries(dirh);
185
186 /* recycle */
187 mutex_enter(&dirhashmutex);
188 TAILQ_REMOVE(&dirhash_queue, dirh, next);
189 mutex_exit(&dirhashmutex);
190
191 pool_put(&dirhash_pool, dirh);
192 *dirhp = NULL;
193 }
194
195
196 void
dirhash_get(struct dirhash ** dirhp)197 dirhash_get(struct dirhash **dirhp)
198 {
199 struct dirhash *dirh;
200 uint32_t hashline;
201
202 /* if no dirhash was given, allocate one */
203 dirh = *dirhp;
204 if (dirh == NULL) {
205 dirh = pool_get(&dirhash_pool, PR_WAITOK | PR_ZERO);
206 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
207 LIST_INIT(&dirh->entries[hashline]);
208 }
209 }
210
211 /* implement LRU on the dirhash queue */
212 mutex_enter(&dirhashmutex);
213 if (*dirhp) {
214 /* remove from queue to be requeued */
215 TAILQ_REMOVE(&dirhash_queue, dirh, next);
216 }
217 dirh->refcnt++;
218 TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next);
219 mutex_exit(&dirhashmutex);
220
221 *dirhp = dirh;
222 }
223
224
225 void
dirhash_put(struct dirhash * dirh)226 dirhash_put(struct dirhash *dirh)
227 {
228
229 mutex_enter(&dirhashmutex);
230 dirh->refcnt--;
231 mutex_exit(&dirhashmutex);
232 }
233
234
235 void
dirhash_enter(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size,int new_p)236 dirhash_enter(struct dirhash *dirh,
237 struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new_p)
238 {
239 struct dirhash *del_dirh, *prev_dirh;
240 struct dirhash_entry *dirh_e;
241 uint32_t hashvalue, hashline;
242 int entrysize;
243
244 /* make sure we have a dirhash to work on */
245 KASSERT(dirh);
246 KASSERT(dirh->refcnt > 0);
247
248 /* are we trying to re-enter an entry? */
249 if (!new_p && (dirh->flags & DIRH_COMPLETE))
250 return;
251
252 /* calculate our hash */
253 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
254 hashline = hashvalue & DIRHASH_HASHMASK;
255
256 /* lookup and insert entry if not there yet */
257 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
258 /* check for hash collision */
259 if (dirh_e->hashvalue != hashvalue)
260 continue;
261 if (dirh_e->offset != offset)
262 continue;
263 /* got it already */
264 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
265 KASSERT(dirh_e->entry_size == entry_size);
266 return;
267 }
268
269 DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n",
270 offset, entry_size, dirent->d_namlen,
271 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
272
273 /* check if entry is in free space list */
274 LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
275 if (dirh_e->offset == offset) {
276 DPRINTF(("\tremoving free entry\n"));
277 LIST_REMOVE(dirh_e, next);
278 pool_put(&dirhash_entry_pool, dirh_e);
279 break;
280 }
281 }
282
283 /* ensure we are not passing the dirhash limit */
284 entrysize = sizeof(struct dirhash_entry);
285 if (dirhashsize + entrysize > maxdirhashsize) {
286 /* we walk the dirhash_queue, so need to lock it */
287 mutex_enter(&dirhashmutex);
288 del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash);
289 KASSERT(del_dirh);
290 while (dirhashsize + entrysize > maxdirhashsize) {
291 /* no use trying to delete myself */
292 if (del_dirh == dirh)
293 break;
294 prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next);
295 if (del_dirh->refcnt == 0)
296 dirhash_purge_entries(del_dirh);
297 del_dirh = prev_dirh;
298 }
299 mutex_exit(&dirhashmutex);
300 }
301
302 /* add to the hashline */
303 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);
304
305 dirh_e->hashvalue = hashvalue;
306 dirh_e->offset = offset;
307 dirh_e->d_namlen = dirent->d_namlen;
308 dirh_e->entry_size = entry_size;
309
310 dirh->size += sizeof(struct dirhash_entry);
311 dirh->num_files++;
312 dirhashsize += sizeof(struct dirhash_entry);
313 LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next);
314 }
315
316
317 void
dirhash_enter_freed(struct dirhash * dirh,uint64_t offset,uint32_t entry_size)318 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset,
319 uint32_t entry_size)
320 {
321 struct dirhash_entry *dirh_e;
322
323 /* make sure we have a dirhash to work on */
324 KASSERT(dirh);
325 KASSERT(dirh->refcnt > 0);
326
327 /* check for double entry of free space */
328 LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
329 KASSERT(dirh_e->offset != offset);
330 }
331
332 DPRINTF(("dirhash enter FREED %"PRIu64", %d\n",
333 offset, entry_size));
334 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);
335
336 dirh_e->hashvalue = 0; /* not relevant */
337 dirh_e->offset = offset;
338 dirh_e->d_namlen = 0; /* not relevant */
339 dirh_e->entry_size = entry_size;
340
341 /* XXX it might be preferable to append them at the tail */
342 LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
343 dirh->size += sizeof(struct dirhash_entry);
344 dirhashsize += sizeof(struct dirhash_entry);
345 }
346
347
348 void
dirhash_remove(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size)349 dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
350 uint64_t offset, uint32_t entry_size)
351 {
352 struct dirhash_entry *dirh_e;
353 uint32_t hashvalue, hashline;
354
355 DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
356 offset, entry_size,
357 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
358
359 /* make sure we have a dirhash to work on */
360 KASSERT(dirh);
361 KASSERT(dirh->refcnt > 0);
362
363 /* calculate our hash */
364 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
365 hashline = hashvalue & DIRHASH_HASHMASK;
366
367 /* lookup entry */
368 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
369 /* check for hash collision */
370 if (dirh_e->hashvalue != hashvalue)
371 continue;
372 if (dirh_e->offset != offset)
373 continue;
374
375 /* got it! */
376 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
377 KASSERT(dirh_e->entry_size == entry_size);
378 LIST_REMOVE(dirh_e, next);
379 dirh->size -= sizeof(struct dirhash_entry);
380 KASSERT(dirh->num_files > 0);
381 dirh->num_files--;
382 dirhashsize -= sizeof(struct dirhash_entry);
383
384 dirhash_enter_freed(dirh, offset, entry_size);
385 return;
386 }
387
388 /* not found! */
389 panic("dirhash_remove couldn't find entry in hash table\n");
390 }
391
392
393 /*
394 * BUGALERT: don't use result longer than needed, never past the node lock.
395 * Call with NULL *result initially and it will return nonzero if again.
396 */
397 int
dirhash_lookup(struct dirhash * dirh,const char * d_name,int d_namlen,struct dirhash_entry ** result)398 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
399 struct dirhash_entry **result)
400 {
401 struct dirhash_entry *dirh_e;
402 uint32_t hashvalue, hashline;
403
404 /* make sure we have a dirhash to work on */
405 KASSERT(dirh);
406 KASSERT(dirh->refcnt > 0);
407
408 /* start where we were */
409 if (*result) {
410 dirh_e = *result;
411
412 /* retrieve information to avoid recalculation and advance */
413 hashvalue = dirh_e->hashvalue;
414 dirh_e = LIST_NEXT(*result, next);
415 } else {
416 /* calculate our hash and lookup all entries in hashline */
417 hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
418 hashline = hashvalue & DIRHASH_HASHMASK;
419 dirh_e = LIST_FIRST(&dirh->entries[hashline]);
420 }
421
422 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
423 /* check for hash collision */
424 if (dirh_e->hashvalue != hashvalue)
425 continue;
426 if (dirh_e->d_namlen != d_namlen)
427 continue;
428 /* might have an entry in the cache */
429 *result = dirh_e;
430 return 1;
431 }
432
433 *result = NULL;
434 return 0;
435 }
436
437
438 /*
439 * BUGALERT: don't use result longer than needed, never past the node lock.
440 * Call with NULL *result initially and it will return nonzero if again.
441 */
442
443 int
dirhash_lookup_freed(struct dirhash * dirh,uint32_t min_entrysize,struct dirhash_entry ** result)444 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
445 struct dirhash_entry **result)
446 {
447 struct dirhash_entry *dirh_e;
448
449 /* make sure we have a dirhash to work on */
450 KASSERT(dirh);
451 KASSERT(dirh->refcnt > 0);
452
453 /* start where we were */
454 if (*result) {
455 dirh_e = LIST_NEXT(*result, next);
456 } else {
457 /* lookup all entries that match */
458 dirh_e = LIST_FIRST(&dirh->free_entries);
459 }
460
461 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
462 /* check for minimum size */
463 if (dirh_e->entry_size < min_entrysize)
464 continue;
465 /* might be a candidate */
466 *result = dirh_e;
467 return 1;
468 }
469
470 *result = NULL;
471 return 0;
472 }
473
474
475 bool
dirhash_dir_isempty(struct dirhash * dirh)476 dirhash_dir_isempty(struct dirhash *dirh)
477 {
478 #ifdef DEBUG
479 struct dirhash_entry *dirh_e;
480 int hashline, num;
481
482 num = 0;
483 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
484 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
485 num++;
486 }
487 }
488
489 if (dirh->num_files != num) {
490 printf("dirhash_dir_isempy: dirhash_counter failed: "
491 "dirh->num_files = %d, counted %d\n",
492 dirh->num_files, num);
493 assert(dirh->num_files == num);
494 }
495 #endif
496 /* assert the directory hash info is valid */
497 KASSERT(dirh->flags & DIRH_COMPLETE);
498
499 /* the directory is empty when only '..' lifes in it or is absent */
500 return (dirh->num_files <= 1);
501 }
502
503