1 | /* $NetBSD: vfs_dirhash.c,v 1.12 2014/09/05 05:57:21 matt 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.12 2014/09/05 05:57:21 matt 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 helt. |
59 | * |
60 | * The dirhash structure is considered part of the vnode/inode/udf_node |
61 | * structure and 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 |
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 |
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 |
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 |
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); |
206 | memset(dirh, 0, sizeof(struct dirhash)); |
207 | for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { |
208 | LIST_INIT(&dirh->entries[hashline]); |
209 | } |
210 | } |
211 | |
212 | /* implement LRU on the dirhash queue */ |
213 | mutex_enter(&dirhashmutex); |
214 | if (*dirhp) { |
215 | /* remove from queue to be requeued */ |
216 | TAILQ_REMOVE(&dirhash_queue, dirh, next); |
217 | } |
218 | dirh->refcnt++; |
219 | TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next); |
220 | mutex_exit(&dirhashmutex); |
221 | |
222 | *dirhp = dirh; |
223 | } |
224 | |
225 | |
226 | void |
227 | dirhash_put(struct dirhash *dirh) |
228 | { |
229 | |
230 | mutex_enter(&dirhashmutex); |
231 | dirh->refcnt--; |
232 | mutex_exit(&dirhashmutex); |
233 | } |
234 | |
235 | |
236 | void |
237 | dirhash_enter(struct dirhash *dirh, |
238 | struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new_p) |
239 | { |
240 | struct dirhash *del_dirh, *prev_dirh; |
241 | struct dirhash_entry *dirh_e; |
242 | uint32_t hashvalue, hashline; |
243 | int entrysize; |
244 | |
245 | /* make sure we have a dirhash to work on */ |
246 | KASSERT(dirh); |
247 | KASSERT(dirh->refcnt > 0); |
248 | |
249 | /* are we trying to re-enter an entry? */ |
250 | if (!new_p && (dirh->flags & DIRH_COMPLETE)) |
251 | return; |
252 | |
253 | /* calculate our hash */ |
254 | hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT); |
255 | hashline = hashvalue & DIRHASH_HASHMASK; |
256 | |
257 | /* lookup and insert entry if not there yet */ |
258 | LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { |
259 | /* check for hash collision */ |
260 | if (dirh_e->hashvalue != hashvalue) |
261 | continue; |
262 | if (dirh_e->offset != offset) |
263 | continue; |
264 | /* got it already */ |
265 | KASSERT(dirh_e->d_namlen == dirent->d_namlen); |
266 | KASSERT(dirh_e->entry_size == entry_size); |
267 | return; |
268 | } |
269 | |
270 | DPRINTF(("dirhash enter %" PRIu64", %d, %d for `%*.*s`\n" , |
271 | offset, entry_size, dirent->d_namlen, |
272 | dirent->d_namlen, dirent->d_namlen, dirent->d_name)); |
273 | |
274 | /* check if entry is in free space list */ |
275 | LIST_FOREACH(dirh_e, &dirh->free_entries, next) { |
276 | if (dirh_e->offset == offset) { |
277 | DPRINTF(("\tremoving free entry\n" )); |
278 | LIST_REMOVE(dirh_e, next); |
279 | pool_put(&dirhash_entry_pool, dirh_e); |
280 | break; |
281 | } |
282 | } |
283 | |
284 | /* ensure we are not passing the dirhash limit */ |
285 | entrysize = sizeof(struct dirhash_entry); |
286 | if (dirhashsize + entrysize > maxdirhashsize) { |
287 | /* we walk the dirhash_queue, so need to lock it */ |
288 | mutex_enter(&dirhashmutex); |
289 | del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash); |
290 | KASSERT(del_dirh); |
291 | while (dirhashsize + entrysize > maxdirhashsize) { |
292 | /* no use trying to delete myself */ |
293 | if (del_dirh == dirh) |
294 | break; |
295 | prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next); |
296 | if (del_dirh->refcnt == 0) |
297 | dirhash_purge_entries(del_dirh); |
298 | del_dirh = prev_dirh; |
299 | } |
300 | mutex_exit(&dirhashmutex); |
301 | } |
302 | |
303 | /* add to the hashline */ |
304 | dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); |
305 | memset(dirh_e, 0, sizeof(struct dirhash_entry)); |
306 | |
307 | dirh_e->hashvalue = hashvalue; |
308 | dirh_e->offset = offset; |
309 | dirh_e->d_namlen = dirent->d_namlen; |
310 | dirh_e->entry_size = entry_size; |
311 | |
312 | dirh->size += sizeof(struct dirhash_entry); |
313 | dirh->num_files++; |
314 | dirhashsize += sizeof(struct dirhash_entry); |
315 | LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next); |
316 | } |
317 | |
318 | |
319 | void |
320 | dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, |
321 | uint32_t entry_size) |
322 | { |
323 | struct dirhash_entry *dirh_e; |
324 | |
325 | /* make sure we have a dirhash to work on */ |
326 | KASSERT(dirh); |
327 | KASSERT(dirh->refcnt > 0); |
328 | |
329 | /* check for double entry of free space */ |
330 | LIST_FOREACH(dirh_e, &dirh->free_entries, next) { |
331 | KASSERT(dirh_e->offset != offset); |
332 | } |
333 | |
334 | DPRINTF(("dirhash enter FREED %" PRIu64", %d\n" , |
335 | offset, entry_size)); |
336 | dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); |
337 | memset(dirh_e, 0, sizeof(struct dirhash_entry)); |
338 | |
339 | dirh_e->hashvalue = 0; /* not relevant */ |
340 | dirh_e->offset = offset; |
341 | dirh_e->d_namlen = 0; /* not relevant */ |
342 | dirh_e->entry_size = entry_size; |
343 | |
344 | /* XXX it might be preferable to append them at the tail */ |
345 | LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next); |
346 | dirh->size += sizeof(struct dirhash_entry); |
347 | dirhashsize += sizeof(struct dirhash_entry); |
348 | } |
349 | |
350 | |
351 | void |
352 | dirhash_remove(struct dirhash *dirh, struct dirent *dirent, |
353 | uint64_t offset, uint32_t entry_size) |
354 | { |
355 | struct dirhash_entry *dirh_e; |
356 | uint32_t hashvalue, hashline; |
357 | |
358 | DPRINTF(("dirhash remove %" PRIu64", %d for `%*.*s`\n" , |
359 | offset, entry_size, |
360 | dirent->d_namlen, dirent->d_namlen, dirent->d_name)); |
361 | |
362 | /* make sure we have a dirhash to work on */ |
363 | KASSERT(dirh); |
364 | KASSERT(dirh->refcnt > 0); |
365 | |
366 | /* calculate our hash */ |
367 | hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT); |
368 | hashline = hashvalue & DIRHASH_HASHMASK; |
369 | |
370 | /* lookup entry */ |
371 | LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { |
372 | /* check for hash collision */ |
373 | if (dirh_e->hashvalue != hashvalue) |
374 | continue; |
375 | if (dirh_e->offset != offset) |
376 | continue; |
377 | |
378 | /* got it! */ |
379 | KASSERT(dirh_e->d_namlen == dirent->d_namlen); |
380 | KASSERT(dirh_e->entry_size == entry_size); |
381 | LIST_REMOVE(dirh_e, next); |
382 | dirh->size -= sizeof(struct dirhash_entry); |
383 | KASSERT(dirh->num_files > 0); |
384 | dirh->num_files--; |
385 | dirhashsize -= sizeof(struct dirhash_entry); |
386 | |
387 | dirhash_enter_freed(dirh, offset, entry_size); |
388 | return; |
389 | } |
390 | |
391 | /* not found! */ |
392 | panic("dirhash_remove couldn't find entry in hash table\n" ); |
393 | } |
394 | |
395 | |
396 | /* |
397 | * BUGALERT: don't use result longer than needed, never past the node lock. |
398 | * Call with NULL *result initially and it will return nonzero if again. |
399 | */ |
400 | int |
401 | dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen, |
402 | struct dirhash_entry **result) |
403 | { |
404 | struct dirhash_entry *dirh_e; |
405 | uint32_t hashvalue, hashline; |
406 | |
407 | /* make sure we have a dirhash to work on */ |
408 | KASSERT(dirh); |
409 | KASSERT(dirh->refcnt > 0); |
410 | |
411 | /* start where we were */ |
412 | if (*result) { |
413 | dirh_e = *result; |
414 | |
415 | /* retrieve information to avoid recalculation and advance */ |
416 | hashvalue = dirh_e->hashvalue; |
417 | dirh_e = LIST_NEXT(*result, next); |
418 | } else { |
419 | /* calculate our hash and lookup all entries in hashline */ |
420 | hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT); |
421 | hashline = hashvalue & DIRHASH_HASHMASK; |
422 | dirh_e = LIST_FIRST(&dirh->entries[hashline]); |
423 | } |
424 | |
425 | for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { |
426 | /* check for hash collision */ |
427 | if (dirh_e->hashvalue != hashvalue) |
428 | continue; |
429 | if (dirh_e->d_namlen != d_namlen) |
430 | continue; |
431 | /* might have an entry in the cache */ |
432 | *result = dirh_e; |
433 | return 1; |
434 | } |
435 | |
436 | *result = NULL; |
437 | return 0; |
438 | } |
439 | |
440 | |
441 | /* |
442 | * BUGALERT: don't use result longer than needed, never past the node lock. |
443 | * Call with NULL *result initially and it will return nonzero if again. |
444 | */ |
445 | |
446 | int |
447 | dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize, |
448 | struct dirhash_entry **result) |
449 | { |
450 | struct dirhash_entry *dirh_e; |
451 | |
452 | /* make sure we have a dirhash to work on */ |
453 | KASSERT(dirh); |
454 | KASSERT(dirh->refcnt > 0); |
455 | |
456 | /* start where we were */ |
457 | if (*result) { |
458 | dirh_e = LIST_NEXT(*result, next); |
459 | } else { |
460 | /* lookup all entries that match */ |
461 | dirh_e = LIST_FIRST(&dirh->free_entries); |
462 | } |
463 | |
464 | for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { |
465 | /* check for minimum size */ |
466 | if (dirh_e->entry_size < min_entrysize) |
467 | continue; |
468 | /* might be a candidate */ |
469 | *result = dirh_e; |
470 | return 1; |
471 | } |
472 | |
473 | *result = NULL; |
474 | return 0; |
475 | } |
476 | |
477 | |
478 | bool |
479 | dirhash_dir_isempty(struct dirhash *dirh) |
480 | { |
481 | #ifdef DEBUG |
482 | struct dirhash_entry *dirh_e; |
483 | int hashline, num; |
484 | |
485 | num = 0; |
486 | for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { |
487 | LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { |
488 | num++; |
489 | } |
490 | } |
491 | |
492 | if (dirh->num_files != num) { |
493 | printf("dirhash_dir_isempy: dirhash_counter failed: " |
494 | "dirh->num_files = %d, counted %d\n" , |
495 | dirh->num_files, num); |
496 | assert(dirh->num_files == num); |
497 | } |
498 | #endif |
499 | /* assert the directory hash info is valid */ |
500 | KASSERT(dirh->flags & DIRH_COMPLETE); |
501 | |
502 | /* the directory is empty when only '..' lifes in it or is absent */ |
503 | return (dirh->num_files <= 1); |
504 | } |
505 | |
506 | |