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