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