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
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);
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
dirhash_put(struct dirhash * dirh)227 dirhash_put(struct dirhash *dirh)
228 {
229
230 mutex_enter(&dirhashmutex);
231 dirh->refcnt--;
232 mutex_exit(&dirhashmutex);
233 }
234
235
236 void
dirhash_enter(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size,int new_p)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
dirhash_enter_freed(struct dirhash * dirh,uint64_t offset,uint32_t entry_size)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
dirhash_remove(struct dirhash * dirh,struct dirent * dirent,uint64_t offset,uint32_t entry_size)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
dirhash_lookup(struct dirhash * dirh,const char * d_name,int d_namlen,struct dirhash_entry ** result)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
dirhash_lookup_freed(struct dirhash * dirh,uint32_t min_entrysize,struct dirhash_entry ** result)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
dirhash_dir_isempty(struct dirhash * dirh)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