vfs_dirhash.c revision 1.4
1 /* $NetBSD: vfs_dirhash.c,v 1.4 2008/10/30 17:19:18 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 #ifndef lint 32 __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.4 2008/10/30 17:19:18 reinoud Exp $"); 33 #endif /* not lint */ 34 35 #if 1 36 # define DPRINTF(a) ; 37 #else 38 # define DPRINTF(a) printf(a); 39 #endif 40 41 /* CLEAN UP! */ 42 #include <sys/sysctl.h> 43 #include <sys/param.h> 44 #include <sys/systm.h> 45 #include <sys/sysctl.h> 46 #include <sys/namei.h> 47 #include <sys/proc.h> 48 #include <sys/kernel.h> 49 #include <sys/vnode.h> 50 #include <sys/mount.h> 51 #include <sys/buf.h> 52 #include <sys/file.h> 53 #include <sys/device.h> 54 #include <sys/disklabel.h> 55 #include <sys/ioctl.h> 56 #include <sys/malloc.h> 57 #include <sys/dirent.h> 58 #include <sys/stat.h> 59 #include <sys/conf.h> 60 #include <sys/kauth.h> 61 #include <dev/clock_subr.h> 62 63 #include <sys/dirhash.h> 64 65 66 static struct sysctllog *sysctl_log; 67 struct pool dirhash_pool; 68 struct pool dirhash_entry_pool; 69 70 static kmutex_t dirhashmutex; 71 static uint32_t maxdirhashsize = DIRHASH_SIZE; 72 static uint32_t dirhashsize = 0; 73 static TAILQ_HEAD(_dirhash, dirhash) dirhash_queue; 74 75 76 void 77 dirhash_init(void) 78 { 79 const struct sysctlnode *rnode, *cnode; 80 size_t size; 81 uint32_t max_entries; 82 83 /* initialise dirhash queue */ 84 TAILQ_INIT(&dirhash_queue); 85 86 /* init dirhash pools */ 87 size = sizeof(struct dirhash); 88 pool_init(&dirhash_pool, size, 0, 0, 0, 89 "dirhash_pool", NULL, IPL_NONE); 90 91 size = sizeof(struct dirhash_entry); 92 pool_init(&dirhash_entry_pool, size, 0, 0, 0, 93 "dirhash_entry_pool", NULL, IPL_NONE); 94 95 mutex_init(&dirhashmutex, MUTEX_DEFAULT, IPL_NONE); 96 max_entries = maxdirhashsize / size; 97 pool_sethiwat(&dirhash_entry_pool, max_entries); 98 dirhashsize = 0; 99 100 /* create sysctl knobs and dials */ 101 sysctl_log = NULL; 102 sysctl_createv(&sysctl_log, 0, NULL, &rnode, 103 CTLFLAG_PERMANENT, 104 CTLTYPE_NODE, "dirhash", NULL, 105 NULL, 0, NULL, 0, 106 CTL_VFS, VFS_GENERIC, CTL_CREATE, CTL_EOL); 107 sysctl_createv(&sysctl_log, 0, &rnode, &cnode, 108 CTLFLAG_PERMANENT, 109 CTLTYPE_INT, "memused", 110 SYSCTL_DESCR("current dirhash memory usage"), 111 NULL, 0, &dirhashsize, 0, 112 CTL_CREATE, CTL_EOL); 113 sysctl_createv(&sysctl_log, 0, &rnode, &cnode, 114 CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 115 CTLTYPE_INT, "maxmem", 116 SYSCTL_DESCR("maximum dirhash memory usage"), 117 NULL, 0, &maxdirhashsize, 0, 118 CTL_CREATE, CTL_EOL); 119 } 120 121 122 #if 0 123 void 124 dirhash_finish(void) 125 { 126 pool_destroy(&dirhash_pool); 127 pool_destroy(&dirhash_entry_pool); 128 129 mutex_destroy(&dirhashmutex); 130 131 /* sysctl_teardown(&sysctl_log); */ 132 } 133 #endif 134 135 136 /* 137 * generic dirhash implementation 138 */ 139 140 static uint32_t 141 dirhash_hash(const char *str, int namelen) 142 { 143 uint32_t hash = 5381; 144 int i, c; 145 146 for (i = 0; i < namelen; i++) { 147 c = *str++; 148 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 149 } 150 return hash; 151 } 152 153 154 void 155 dirhash_purge_entries(struct dirhash *dirh) 156 { 157 struct dirhash_entry *dirh_e; 158 uint32_t hashline; 159 160 if (dirh == NULL) 161 return; 162 163 if (dirh->size == 0) 164 return; 165 166 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 167 dirh_e = LIST_FIRST(&dirh->entries[hashline]); 168 while (dirh_e) { 169 LIST_REMOVE(dirh_e, next); 170 pool_put(&dirhash_entry_pool, dirh_e); 171 dirh_e = LIST_FIRST(&dirh->entries[hashline]); 172 } 173 } 174 dirh_e = LIST_FIRST(&dirh->free_entries); 175 176 while (dirh_e) { 177 LIST_REMOVE(dirh_e, next); 178 pool_put(&dirhash_entry_pool, dirh_e); 179 dirh_e = LIST_FIRST(&dirh->entries[hashline]); 180 } 181 182 dirh->flags &= ~DIRH_COMPLETE; 183 dirh->flags |= DIRH_PURGED; 184 185 dirhashsize -= dirh->size; 186 dirh->size = 0; 187 } 188 189 190 void 191 dirhash_purge(struct dirhash **dirhp) 192 { 193 struct dirhash *dirh = *dirhp; 194 195 if (dirh == NULL) 196 return; 197 198 mutex_enter(&dirhashmutex); 199 200 dirhash_purge_entries(dirh); 201 TAILQ_REMOVE(&dirhash_queue, dirh, next); 202 pool_put(&dirhash_pool, dirh); 203 204 *dirhp = NULL; 205 206 mutex_exit(&dirhashmutex); 207 } 208 209 210 void 211 dirhash_get(struct dirhash **dirhp) 212 { 213 struct dirhash *dirh; 214 uint32_t hashline; 215 216 mutex_enter(&dirhashmutex); 217 218 dirh = *dirhp; 219 if (*dirhp == NULL) { 220 dirh = pool_get(&dirhash_pool, PR_WAITOK); 221 *dirhp = dirh; 222 memset(dirh, 0, sizeof(struct dirhash)); 223 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) 224 LIST_INIT(&dirh->entries[hashline]); 225 dirh->size = 0; 226 dirh->refcnt = 0; 227 dirh->flags = 0; 228 } else { 229 TAILQ_REMOVE(&dirhash_queue, dirh, next); 230 } 231 232 dirh->refcnt++; 233 TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next); 234 235 mutex_exit(&dirhashmutex); 236 } 237 238 239 void 240 dirhash_put(struct dirhash *dirh) 241 { 242 243 mutex_enter(&dirhashmutex); 244 dirh->refcnt--; 245 mutex_exit(&dirhashmutex); 246 } 247 248 249 void 250 dirhash_enter(struct dirhash *dirh, 251 struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new) 252 { 253 struct dirhash *del_dirh, *prev_dirh; 254 struct dirhash_entry *dirh_e; 255 uint32_t hashvalue, hashline; 256 int entrysize; 257 258 /* make sure we have a dirhash to work on */ 259 KASSERT(dirh); 260 KASSERT(dirh->refcnt > 0); 261 262 /* are we trying to re-enter an entry? */ 263 if (!new && (dirh->flags & DIRH_COMPLETE)) 264 return; 265 266 /* calculate our hash */ 267 hashvalue = dirhash_hash(dirent->d_name, dirent->d_namlen); 268 hashline = hashvalue & DIRHASH_HASHMASK; 269 270 /* lookup and insert entry if not there yet */ 271 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 272 /* check for hash collision */ 273 if (dirh_e->hashvalue != hashvalue) 274 continue; 275 if (dirh_e->offset != offset) 276 continue; 277 /* got it already */ 278 KASSERT(dirh_e->d_namlen == dirent->d_namlen); 279 KASSERT(dirh_e->entry_size == entry_size); 280 return; 281 } 282 283 DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n", 284 offset, entry_size, dirent->d_namlen, 285 dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 286 287 /* check if entry is in free space list */ 288 LIST_FOREACH(dirh_e, &dirh->free_entries, next) { 289 if (dirh_e->offset == offset) { 290 DPRINTF(("\tremoving free entry\n")); 291 LIST_REMOVE(dirh_e, next); 292 break; 293 } 294 } 295 296 /* ensure we are not passing the dirhash limit */ 297 entrysize = sizeof(struct dirhash_entry); 298 if (dirhashsize + entrysize > maxdirhashsize) { 299 del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash); 300 KASSERT(del_dirh); 301 while (dirhashsize + entrysize > maxdirhashsize) { 302 /* no use trying to delete myself */ 303 if (del_dirh == dirh) 304 break; 305 prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next); 306 if (del_dirh->refcnt == 0) 307 dirhash_purge_entries(del_dirh); 308 del_dirh = prev_dirh; 309 } 310 } 311 312 /* add to the hashline */ 313 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); 314 memset(dirh_e, 0, sizeof(struct dirhash_entry)); 315 316 dirh_e->hashvalue = hashvalue; 317 dirh_e->offset = offset; 318 dirh_e->d_namlen = dirent->d_namlen; 319 dirh_e->entry_size = entry_size; 320 321 dirh->size += sizeof(struct dirhash_entry); 322 dirhashsize += sizeof(struct dirhash_entry); 323 LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next); 324 } 325 326 327 void 328 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, 329 uint32_t entry_size) 330 { 331 struct dirhash_entry *dirh_e; 332 333 /* make sure we have a dirhash to work on */ 334 KASSERT(dirh); 335 KASSERT(dirh->refcnt > 0); 336 337 #ifdef DEBUG 338 /* check for double entry of free space */ 339 LIST_FOREACH(dirh_e, &dirh->free_entries, next) 340 KASSERT(dirh_e->offset != offset); 341 #endif 342 343 DPRINTF(("dirhash enter FREED %"PRIu64", %d\n", 344 offset, entry_size)); 345 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); 346 memset(dirh_e, 0, sizeof(struct dirhash_entry)); 347 348 dirh_e->hashvalue = 0; /* not relevant */ 349 dirh_e->offset = offset; 350 dirh_e->d_namlen = 0; /* not relevant */ 351 dirh_e->entry_size = entry_size; 352 353 /* XXX it might be preferable to append them at the tail */ 354 LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next); 355 dirh->size += sizeof(struct dirhash_entry); 356 dirhashsize += sizeof(struct dirhash_entry); 357 } 358 359 360 void 361 dirhash_remove(struct dirhash *dirh, struct dirent *dirent, 362 uint64_t offset, uint32_t entry_size) 363 { 364 struct dirhash_entry *dirh_e; 365 uint32_t hashvalue, hashline; 366 367 DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n", 368 offset, entry_size, 369 dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 370 371 /* make sure we have a dirhash to work on */ 372 KASSERT(dirh); 373 KASSERT(dirh->refcnt > 0); 374 375 /* calculate our hash */ 376 hashvalue = dirhash_hash(dirent->d_name, dirent->d_namlen); 377 hashline = hashvalue & DIRHASH_HASHMASK; 378 379 /* lookup entry */ 380 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 381 /* check for hash collision */ 382 if (dirh_e->hashvalue != hashvalue) 383 continue; 384 if (dirh_e->offset != offset) 385 continue; 386 387 /* got it! */ 388 KASSERT(dirh_e->d_namlen == dirent->d_namlen); 389 KASSERT(dirh_e->entry_size == entry_size); 390 LIST_REMOVE(dirh_e, next); 391 dirh->size -= sizeof(struct dirhash_entry); 392 dirhashsize -= sizeof(struct dirhash_entry); 393 394 dirhash_enter_freed(dirh, offset, entry_size); 395 return; 396 } 397 398 /* not found! */ 399 panic("dirhash_remove couldn't find entry in hash table\n"); 400 } 401 402 403 /* BUGALERT: don't use result longer than needed, never past the node lock */ 404 /* call with NULL *result initially and it will return nonzero if again */ 405 int 406 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen, 407 struct dirhash_entry **result) 408 { 409 struct dirhash_entry *dirh_e; 410 uint32_t hashvalue, hashline; 411 412 /* vnode should be locked */ 413 //KASSERT(VOP_ISLOCKED(dirh->vnode)); 414 415 /* make sure we have a dirhash to work on */ 416 KASSERT(dirh); 417 KASSERT(dirh->refcnt > 0); 418 419 /* start where we were */ 420 if (*result) { 421 dirh_e = *result; 422 423 /* retrieve information to avoid recalculation and advance */ 424 hashvalue = dirh_e->hashvalue; 425 dirh_e = LIST_NEXT(*result, next); 426 } else { 427 /* calculate our hash and lookup all entries in hashline */ 428 hashvalue = dirhash_hash(d_name, d_namlen); 429 hashline = hashvalue & DIRHASH_HASHMASK; 430 dirh_e = LIST_FIRST(&dirh->entries[hashline]); 431 } 432 433 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 434 /* check for hash collision */ 435 if (dirh_e->hashvalue != hashvalue) 436 continue; 437 if (dirh_e->d_namlen != d_namlen) 438 continue; 439 /* might have an entry in the cache */ 440 *result = dirh_e; 441 return 1; 442 } 443 444 *result = NULL; 445 return 0; 446 } 447 448 449 /* BUGALERT: don't use result longer than needed, never past the node lock */ 450 /* call with NULL *result initially and it will return nonzero if again */ 451 int 452 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize, 453 struct dirhash_entry **result) 454 { 455 struct dirhash_entry *dirh_e; 456 457 //KASSERT(VOP_ISLOCKED(dirh->vnode)); 458 459 /* make sure we have a dirhash to work on */ 460 KASSERT(dirh); 461 KASSERT(dirh->refcnt > 0); 462 463 /* start where we were */ 464 if (*result) { 465 dirh_e = LIST_NEXT(*result, next); 466 } else { 467 /* lookup all entries that match */ 468 dirh_e = LIST_FIRST(&dirh->free_entries); 469 } 470 471 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 472 /* check for minimum size */ 473 if (dirh_e->entry_size < min_entrysize) 474 continue; 475 /* might be a candidate */ 476 *result = dirh_e; 477 return 1; 478 } 479 480 *result = NULL; 481 return 0; 482 } 483 484 485
Indexes created Tue Sep 30 07:10:03 GMT 2025