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