1 /* $NetBSD: vfs_dirhash.c,v 1.16 2024/12/07 02:11:42 riastradh 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 #include <sys/cdefs.h> 30 __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.16 2024/12/07 02:11:42 riastradh Exp $"); 31 32 /* CLEAN UP! */ 33 #include <sys/param.h> 34 #include <sys/types.h> 35 36 #include <sys/buf.h> 37 #include <sys/dirent.h> 38 #include <sys/dirhash.h> 39 #include <sys/hash.h> 40 #include <sys/kernel.h> 41 #include <sys/mutex.h> 42 #include <sys/pool.h> 43 #include <sys/queue.h> 44 #include <sys/sysctl.h> 45 #include <sys/vnode.h> 46 47 #if 1 48 # define DPRINTF(a) __nothing 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 held. 59 * 60 * The dirhash structure is considered part of the vnode/inode structure and 61 * 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 * generic dirhash implementation 138 */ 139 140 void 141 dirhash_purge_entries(struct dirhash *dirh) 142 { 143 struct dirhash_entry *dirh_e; 144 uint32_t hashline; 145 146 if (dirh == NULL) 147 return; 148 149 if (dirh->size == 0) 150 return; 151 152 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 153 while ((dirh_e = LIST_FIRST(&dirh->entries[hashline])) 154 != NULL) { 155 LIST_REMOVE(dirh_e, next); 156 pool_put(&dirhash_entry_pool, dirh_e); 157 } 158 } 159 160 while ((dirh_e = LIST_FIRST(&dirh->free_entries)) != NULL) { 161 LIST_REMOVE(dirh_e, next); 162 pool_put(&dirhash_entry_pool, dirh_e); 163 } 164 165 dirh->flags &= ~DIRH_COMPLETE; 166 dirh->flags |= DIRH_PURGED; 167 dirh->num_files = 0; 168 169 dirhashsize -= dirh->size; 170 dirh->size = 0; 171 } 172 173 void 174 dirhash_purge(struct dirhash **dirhp) 175 { 176 struct dirhash *dirh = *dirhp; 177 178 if (dirh == NULL) 179 return; 180 181 /* purge its entries */ 182 dirhash_purge_entries(dirh); 183 184 /* recycle */ 185 mutex_enter(&dirhashmutex); 186 TAILQ_REMOVE(&dirhash_queue, dirh, next); 187 mutex_exit(&dirhashmutex); 188 189 pool_put(&dirhash_pool, dirh); 190 *dirhp = NULL; 191 } 192 193 void 194 dirhash_get(struct dirhash **dirhp) 195 { 196 struct dirhash *dirh; 197 uint32_t hashline; 198 199 /* if no dirhash was given, allocate one */ 200 dirh = *dirhp; 201 if (dirh == NULL) { 202 dirh = pool_get(&dirhash_pool, PR_WAITOK | PR_ZERO); 203 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 204 LIST_INIT(&dirh->entries[hashline]); 205 } 206 } 207 208 /* implement LRU on the dirhash queue */ 209 mutex_enter(&dirhashmutex); 210 if (*dirhp) { 211 /* remove from queue to be requeued */ 212 TAILQ_REMOVE(&dirhash_queue, dirh, next); 213 } 214 dirh->refcnt++; 215 TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next); 216 mutex_exit(&dirhashmutex); 217 218 *dirhp = dirh; 219 } 220 221 void 222 dirhash_put(struct dirhash *dirh) 223 { 224 225 mutex_enter(&dirhashmutex); 226 dirh->refcnt--; 227 mutex_exit(&dirhashmutex); 228 } 229 230 void 231 dirhash_enter(struct dirhash *dirh, 232 struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new_p) 233 { 234 struct dirhash *del_dirh, *prev_dirh; 235 struct dirhash_entry *dirh_e; 236 uint32_t hashvalue, hashline; 237 int entrysize; 238 239 /* make sure we have a dirhash to work on */ 240 KASSERT(dirh); 241 KASSERT(dirh->refcnt > 0); 242 243 /* are we trying to re-enter an entry? */ 244 if (!new_p && (dirh->flags & DIRH_COMPLETE)) 245 return; 246 247 /* calculate our hash */ 248 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, 249 HASH32_STR_INIT); 250 hashline = hashvalue & DIRHASH_HASHMASK; 251 252 /* lookup and insert entry if not there yet */ 253 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 254 /* check for hash collision */ 255 if (dirh_e->hashvalue != hashvalue) 256 continue; 257 if (dirh_e->offset != offset) 258 continue; 259 /* got it already */ 260 KASSERT(dirh_e->d_namlen == dirent->d_namlen); 261 KASSERT(dirh_e->entry_size == entry_size); 262 return; 263 } 264 265 DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n", 266 offset, entry_size, dirent->d_namlen, 267 dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 268 269 /* check if entry is in free space list */ 270 LIST_FOREACH(dirh_e, &dirh->free_entries, next) { 271 if (dirh_e->offset == offset) { 272 DPRINTF(("\tremoving free entry\n")); 273 LIST_REMOVE(dirh_e, next); 274 pool_put(&dirhash_entry_pool, dirh_e); 275 break; 276 } 277 } 278 279 /* ensure we are not passing the dirhash limit */ 280 entrysize = sizeof(struct dirhash_entry); 281 if (dirhashsize + entrysize > maxdirhashsize) { 282 /* we walk the dirhash_queue, so need to lock it */ 283 mutex_enter(&dirhashmutex); 284 del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash); 285 KASSERT(del_dirh); 286 while (dirhashsize + entrysize > maxdirhashsize) { 287 /* no use trying to delete myself */ 288 if (del_dirh == dirh) 289 break; 290 prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next); 291 if (del_dirh->refcnt == 0) 292 dirhash_purge_entries(del_dirh); 293 del_dirh = prev_dirh; 294 } 295 mutex_exit(&dirhashmutex); 296 } 297 298 /* add to the hashline */ 299 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO); 300 301 dirh_e->hashvalue = hashvalue; 302 dirh_e->offset = offset; 303 dirh_e->d_namlen = dirent->d_namlen; 304 dirh_e->entry_size = entry_size; 305 306 dirh->size += sizeof(struct dirhash_entry); 307 dirh->num_files++; 308 dirhashsize += sizeof(struct dirhash_entry); 309 LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next); 310 } 311 312 void 313 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, uint32_t entry_size) 314 { 315 struct dirhash_entry *dirh_e; 316 317 /* make sure we have a dirhash to work on */ 318 KASSERT(dirh); 319 KASSERT(dirh->refcnt > 0); 320 321 /* check for double entry of free space */ 322 LIST_FOREACH(dirh_e, &dirh->free_entries, next) { 323 KASSERT(dirh_e->offset != offset); 324 } 325 326 DPRINTF(("dirhash enter FREED %"PRIu64", %d\n", 327 offset, entry_size)); 328 dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO); 329 330 dirh_e->hashvalue = 0; /* not relevant */ 331 dirh_e->offset = offset; 332 dirh_e->d_namlen = 0; /* not relevant */ 333 dirh_e->entry_size = entry_size; 334 335 /* XXX it might be preferable to append them at the tail */ 336 LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next); 337 dirh->size += sizeof(struct dirhash_entry); 338 dirhashsize += sizeof(struct dirhash_entry); 339 } 340 341 void 342 dirhash_remove(struct dirhash *dirh, struct dirent *dirent, 343 uint64_t offset, uint32_t entry_size) 344 { 345 struct dirhash_entry *dirh_e; 346 uint32_t hashvalue, hashline; 347 348 DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n", 349 offset, entry_size, 350 dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 351 352 /* make sure we have a dirhash to work on */ 353 KASSERT(dirh); 354 KASSERT(dirh->refcnt > 0); 355 356 /* calculate our hash */ 357 hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, 358 HASH32_STR_INIT); 359 hashline = hashvalue & DIRHASH_HASHMASK; 360 361 /* lookup entry */ 362 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 363 /* check for hash collision */ 364 if (dirh_e->hashvalue != hashvalue) 365 continue; 366 if (dirh_e->offset != offset) 367 continue; 368 369 /* got it! */ 370 KASSERT(dirh_e->d_namlen == dirent->d_namlen); 371 KASSERT(dirh_e->entry_size == entry_size); 372 LIST_REMOVE(dirh_e, next); 373 dirh->size -= sizeof(struct dirhash_entry); 374 KASSERT(dirh->num_files > 0); 375 dirh->num_files--; 376 dirhashsize -= sizeof(struct dirhash_entry); 377 378 dirhash_enter_freed(dirh, offset, entry_size); 379 return; 380 } 381 382 /* not found! */ 383 panic("dirhash_remove couldn't find entry in hash table\n"); 384 } 385 386 /* 387 * BUGALERT: don't use result longer than needed, never past the node lock. 388 * Call with NULL *result initially and it will return nonzero if again. 389 */ 390 int 391 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen, 392 struct dirhash_entry **result) 393 { 394 struct dirhash_entry *dirh_e; 395 uint32_t hashvalue, hashline; 396 397 /* make sure we have a dirhash to work on */ 398 KASSERT(dirh); 399 KASSERT(dirh->refcnt > 0); 400 401 /* start where we were */ 402 if (*result) { 403 dirh_e = *result; 404 405 /* retrieve information to avoid recalculation and advance */ 406 hashvalue = dirh_e->hashvalue; 407 dirh_e = LIST_NEXT(*result, next); 408 } else { 409 /* calculate our hash and lookup all entries in hashline */ 410 hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT); 411 hashline = hashvalue & DIRHASH_HASHMASK; 412 dirh_e = LIST_FIRST(&dirh->entries[hashline]); 413 } 414 415 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 416 /* check for hash collision */ 417 if (dirh_e->hashvalue != hashvalue) 418 continue; 419 if (dirh_e->d_namlen != d_namlen) 420 continue; 421 /* might have an entry in the cache */ 422 *result = dirh_e; 423 return 1; 424 } 425 426 *result = NULL; 427 return 0; 428 } 429 430 /* 431 * BUGALERT: don't use result longer than needed, never past the node lock. 432 * Call with NULL *result initially and it will return nonzero if again. 433 */ 434 int 435 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize, 436 struct dirhash_entry **result) 437 { 438 struct dirhash_entry *dirh_e; 439 440 /* make sure we have a dirhash to work on */ 441 KASSERT(dirh); 442 KASSERT(dirh->refcnt > 0); 443 444 /* start where we were */ 445 if (*result) { 446 dirh_e = LIST_NEXT(*result, next); 447 } else { 448 /* lookup all entries that match */ 449 dirh_e = LIST_FIRST(&dirh->free_entries); 450 } 451 452 for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 453 /* check for minimum size */ 454 if (dirh_e->entry_size < min_entrysize) 455 continue; 456 /* might be a candidate */ 457 *result = dirh_e; 458 return 1; 459 } 460 461 *result = NULL; 462 return 0; 463 } 464 465 bool 466 dirhash_dir_isempty(struct dirhash *dirh) 467 { 468 #ifdef DEBUG 469 struct dirhash_entry *dirh_e; 470 int hashline, num; 471 472 num = 0; 473 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 474 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 475 num++; 476 } 477 } 478 479 if (dirh->num_files != num) { 480 printf("dirhash_dir_isempy: dirhash_counter failed: " 481 "dirh->num_files = %d, counted %d\n", 482 dirh->num_files, num); 483 assert(dirh->num_files == num); 484 } 485 #endif 486 /* assert the directory hash info is valid */ 487 KASSERT(dirh->flags & DIRH_COMPLETE); 488 489 /* the directory is empty when only '..' lifes in it or is absent */ 490 return (dirh->num_files <= 1); 491 } 492