vfs_dirhash.c revision 1.12
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
Indexes created Mon Sep 22 21:09:42 GMT 2025