vfs_dirhash.c revision 1.1.2.3
1 1.1.2.2 mjf /* $NetBSD: vfs_dirhash.c,v 1.1.2.3 2009/01/17 13:29:20 mjf Exp $ */ 2 1.1.2.2 mjf 3 1.1.2.2 mjf /* 4 1.1.2.2 mjf * Copyright (c) 2008 Reinoud Zandijk 5 1.1.2.2 mjf * All rights reserved. 6 1.1.2.2 mjf * 7 1.1.2.2 mjf * Redistribution and use in source and binary forms, with or without 8 1.1.2.2 mjf * modification, are permitted provided that the following conditions 9 1.1.2.2 mjf * are met: 10 1.1.2.2 mjf * 1. Redistributions of source code must retain the above copyright 11 1.1.2.2 mjf * notice, this list of conditions and the following disclaimer. 12 1.1.2.2 mjf * 2. Redistributions in binary form must reproduce the above copyright 13 1.1.2.2 mjf * notice, this list of conditions and the following disclaimer in the 14 1.1.2.2 mjf * documentation and/or other materials provided with the distribution. 15 1.1.2.2 mjf * 16 1.1.2.2 mjf * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 1.1.2.2 mjf * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 1.1.2.2 mjf * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 1.1.2.2 mjf * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 1.1.2.2 mjf * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 1.1.2.2 mjf * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 1.1.2.2 mjf * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 1.1.2.2 mjf * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 1.1.2.2 mjf * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 1.1.2.2 mjf * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 1.1.2.2 mjf * 27 1.1.2.2 mjf */ 28 1.1.2.2 mjf 29 1.1.2.2 mjf 30 1.1.2.2 mjf #include <sys/cdefs.h> 31 1.1.2.2 mjf __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.1.2.3 2009/01/17 13:29:20 mjf Exp $"); 32 1.1.2.2 mjf 33 1.1.2.2 mjf /* CLEAN UP! */ 34 1.1.2.2 mjf #include <sys/param.h> 35 1.1.2.2 mjf #include <sys/kernel.h> 36 1.1.2.2 mjf #include <sys/buf.h> 37 1.1.2.2 mjf #include <sys/dirent.h> 38 1.1.2.3 mjf #include <sys/hash.h> 39 1.1.2.3 mjf #include <sys/mutex.h> 40 1.1.2.3 mjf #include <sys/pool.h> 41 1.1.2.3 mjf #include <sys/queue.h> 42 1.1.2.3 mjf #include <sys/vnode.h> 43 1.1.2.3 mjf #include <sys/sysctl.h> 44 1.1.2.2 mjf 45 1.1.2.2 mjf #include <sys/dirhash.h> 46 1.1.2.2 mjf 47 1.1.2.3 mjf #if 1 48 1.1.2.3 mjf # define DPRINTF(a) ; 49 1.1.2.3 mjf #else 50 1.1.2.3 mjf # define DPRINTF(a) printf a; 51 1.1.2.3 mjf #endif 52 1.1.2.3 mjf 53 1.1.2.3 mjf /* 54 1.1.2.3 mjf * The locking protocol of the dirhash structures is fairly simple: 55 1.1.2.3 mjf * 56 1.1.2.3 mjf * The global dirhash_queue is protected by the dirhashmutex. This lock is 57 1.1.2.3 mjf * internal only and is FS/mountpoint/vnode independent. On exit of the 58 1.1.2.3 mjf * exported functions this mutex is not helt. 59 1.1.2.3 mjf * 60 1.1.2.3 mjf * The dirhash structure is considered part of the vnode/inode/udf_node 61 1.1.2.3 mjf * structure and will thus use the lock that protects that vnode/inode. 62 1.1.2.3 mjf * 63 1.1.2.3 mjf * The dirhash entries are considered part of the dirhash structure and thus 64 1.1.2.3 mjf * are on the same lock. 65 1.1.2.3 mjf */ 66 1.1.2.2 mjf 67 1.1.2.2 mjf static struct sysctllog *sysctl_log; 68 1.1.2.3 mjf static struct pool dirhash_pool; 69 1.1.2.3 mjf static struct pool dirhash_entry_pool; 70 1.1.2.2 mjf 71 1.1.2.3 mjf static kmutex_t dirhashmutex; 72 1.1.2.3 mjf static uint32_t maxdirhashsize = DIRHASH_SIZE; 73 1.1.2.3 mjf static uint32_t dirhashsize = 0; 74 1.1.2.3 mjf static TAILQ_HEAD(_dirhash, dirhash) dirhash_queue; 75 1.1.2.2 mjf 76 1.1.2.2 mjf 77 1.1.2.2 mjf void 78 1.1.2.2 mjf dirhash_init(void) 79 1.1.2.2 mjf { 80 1.1.2.3 mjf const struct sysctlnode *rnode, *cnode; 81 1.1.2.3 mjf size_t sz; 82 1.1.2.2 mjf uint32_t max_entries; 83 1.1.2.2 mjf 84 1.1.2.2 mjf /* initialise dirhash queue */ 85 1.1.2.2 mjf TAILQ_INIT(&dirhash_queue); 86 1.1.2.2 mjf 87 1.1.2.2 mjf /* init dirhash pools */ 88 1.1.2.3 mjf sz = sizeof(struct dirhash); 89 1.1.2.3 mjf pool_init(&dirhash_pool, sz, 0, 0, 0, 90 1.1.2.3 mjf "dirhpl", NULL, IPL_NONE); 91 1.1.2.3 mjf 92 1.1.2.3 mjf sz = sizeof(struct dirhash_entry); 93 1.1.2.3 mjf pool_init(&dirhash_entry_pool, sz, 0, 0, 0, 94 1.1.2.3 mjf "dirhepl", NULL, IPL_NONE); 95 1.1.2.2 mjf 96 1.1.2.2 mjf mutex_init(&dirhashmutex, MUTEX_DEFAULT, IPL_NONE); 97 1.1.2.3 mjf max_entries = maxdirhashsize / sz; 98 1.1.2.2 mjf pool_sethiwat(&dirhash_entry_pool, max_entries); 99 1.1.2.2 mjf dirhashsize = 0; 100 1.1.2.2 mjf 101 1.1.2.2 mjf /* create sysctl knobs and dials */ 102 1.1.2.2 mjf sysctl_log = NULL; 103 1.1.2.3 mjf sysctl_createv(&sysctl_log, 0, NULL, &rnode, 104 1.1.2.2 mjf CTLFLAG_PERMANENT, 105 1.1.2.3 mjf CTLTYPE_NODE, "dirhash", NULL, 106 1.1.2.2 mjf NULL, 0, NULL, 0, 107 1.1.2.3 mjf CTL_VFS, VFS_GENERIC, CTL_CREATE, CTL_EOL); 108 1.1.2.3 mjf sysctl_createv(&sysctl_log, 0, &rnode, &cnode, 109 1.1.2.2 mjf CTLFLAG_PERMANENT, 110 1.1.2.3 mjf CTLTYPE_INT, "memused", 111 1.1.2.3 mjf SYSCTL_DESCR("current dirhash memory usage"), 112 1.1.2.2 mjf NULL, 0, &dirhashsize, 0, 113 1.1.2.3 mjf CTL_CREATE, CTL_EOL); 114 1.1.2.3 mjf sysctl_createv(&sysctl_log, 0, &rnode, &cnode, 115 1.1.2.2 mjf CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 116 1.1.2.3 mjf CTLTYPE_INT, "maxmem", 117 1.1.2.3 mjf SYSCTL_DESCR("maximum dirhash memory usage"), 118 1.1.2.2 mjf NULL, 0, &maxdirhashsize, 0, 119 1.1.2.3 mjf CTL_CREATE, CTL_EOL); 120 1.1.2.2 mjf } 121 1.1.2.2 mjf 122 1.1.2.2 mjf 123 1.1.2.2 mjf #if 0 124 1.1.2.2 mjf void 125 1.1.2.2 mjf dirhash_finish(void) 126 1.1.2.2 mjf { 127 1.1.2.2 mjf pool_destroy(&dirhash_pool); 128 1.1.2.2 mjf pool_destroy(&dirhash_entry_pool); 129 1.1.2.2 mjf 130 1.1.2.2 mjf mutex_destroy(&dirhashmutex); 131 1.1.2.2 mjf 132 1.1.2.2 mjf /* sysctl_teardown(&sysctl_log); */ 133 1.1.2.2 mjf } 134 1.1.2.2 mjf #endif 135 1.1.2.2 mjf 136 1.1.2.2 mjf 137 1.1.2.2 mjf /* 138 1.1.2.2 mjf * generic dirhash implementation 139 1.1.2.2 mjf */ 140 1.1.2.2 mjf 141 1.1.2.2 mjf void 142 1.1.2.2 mjf dirhash_purge_entries(struct dirhash *dirh) 143 1.1.2.2 mjf { 144 1.1.2.2 mjf struct dirhash_entry *dirh_e; 145 1.1.2.2 mjf uint32_t hashline; 146 1.1.2.2 mjf 147 1.1.2.2 mjf if (dirh == NULL) 148 1.1.2.2 mjf return; 149 1.1.2.2 mjf 150 1.1.2.2 mjf if (dirh->size == 0) 151 1.1.2.2 mjf return; 152 1.1.2.2 mjf 153 1.1.2.2 mjf for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 154 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->entries[hashline]); 155 1.1.2.2 mjf while (dirh_e) { 156 1.1.2.2 mjf LIST_REMOVE(dirh_e, next); 157 1.1.2.2 mjf pool_put(&dirhash_entry_pool, dirh_e); 158 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->entries[hashline]); 159 1.1.2.2 mjf } 160 1.1.2.2 mjf } 161 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->free_entries); 162 1.1.2.2 mjf 163 1.1.2.2 mjf while (dirh_e) { 164 1.1.2.2 mjf LIST_REMOVE(dirh_e, next); 165 1.1.2.2 mjf pool_put(&dirhash_entry_pool, dirh_e); 166 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->entries[hashline]); 167 1.1.2.2 mjf } 168 1.1.2.2 mjf 169 1.1.2.2 mjf dirh->flags &= ~DIRH_COMPLETE; 170 1.1.2.2 mjf dirh->flags |= DIRH_PURGED; 171 1.1.2.2 mjf 172 1.1.2.2 mjf dirhashsize -= dirh->size; 173 1.1.2.2 mjf dirh->size = 0; 174 1.1.2.2 mjf } 175 1.1.2.2 mjf 176 1.1.2.2 mjf 177 1.1.2.2 mjf void 178 1.1.2.2 mjf dirhash_purge(struct dirhash **dirhp) 179 1.1.2.2 mjf { 180 1.1.2.2 mjf struct dirhash *dirh = *dirhp; 181 1.1.2.2 mjf 182 1.1.2.2 mjf if (dirh == NULL) 183 1.1.2.2 mjf return; 184 1.1.2.2 mjf 185 1.1.2.3 mjf /* purge its entries */ 186 1.1.2.2 mjf dirhash_purge_entries(dirh); 187 1.1.2.3 mjf 188 1.1.2.3 mjf /* recycle */ 189 1.1.2.3 mjf mutex_enter(&dirhashmutex); 190 1.1.2.2 mjf TAILQ_REMOVE(&dirhash_queue, dirh, next); 191 1.1.2.3 mjf mutex_exit(&dirhashmutex); 192 1.1.2.2 mjf 193 1.1.2.3 mjf pool_put(&dirhash_pool, dirh); 194 1.1.2.2 mjf *dirhp = NULL; 195 1.1.2.2 mjf } 196 1.1.2.2 mjf 197 1.1.2.2 mjf 198 1.1.2.2 mjf void 199 1.1.2.2 mjf dirhash_get(struct dirhash **dirhp) 200 1.1.2.2 mjf { 201 1.1.2.2 mjf struct dirhash *dirh; 202 1.1.2.2 mjf uint32_t hashline; 203 1.1.2.2 mjf 204 1.1.2.3 mjf /* if no dirhash was given, allocate one */ 205 1.1.2.2 mjf dirh = *dirhp; 206 1.1.2.3 mjf if (dirh == NULL) { 207 1.1.2.2 mjf dirh = pool_get(&dirhash_pool, PR_WAITOK); 208 1.1.2.2 mjf memset(dirh, 0, sizeof(struct dirhash)); 209 1.1.2.3 mjf for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) { 210 1.1.2.2 mjf LIST_INIT(&dirh->entries[hashline]); 211 1.1.2.3 mjf } 212 1.1.2.2 mjf } 213 1.1.2.2 mjf 214 1.1.2.3 mjf /* implement LRU on the dirhash queue */ 215 1.1.2.3 mjf mutex_enter(&dirhashmutex); 216 1.1.2.3 mjf if (*dirhp) { 217 1.1.2.3 mjf /* remove from queue to be requeued */ 218 1.1.2.3 mjf TAILQ_REMOVE(&dirhash_queue, dirh, next); 219 1.1.2.3 mjf } 220 1.1.2.2 mjf dirh->refcnt++; 221 1.1.2.2 mjf TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next); 222 1.1.2.2 mjf mutex_exit(&dirhashmutex); 223 1.1.2.3 mjf 224 1.1.2.3 mjf *dirhp = dirh; 225 1.1.2.2 mjf } 226 1.1.2.2 mjf 227 1.1.2.2 mjf 228 1.1.2.2 mjf void 229 1.1.2.2 mjf dirhash_put(struct dirhash *dirh) 230 1.1.2.2 mjf { 231 1.1.2.2 mjf 232 1.1.2.2 mjf mutex_enter(&dirhashmutex); 233 1.1.2.2 mjf dirh->refcnt--; 234 1.1.2.2 mjf mutex_exit(&dirhashmutex); 235 1.1.2.2 mjf } 236 1.1.2.2 mjf 237 1.1.2.2 mjf 238 1.1.2.2 mjf void 239 1.1.2.2 mjf dirhash_enter(struct dirhash *dirh, 240 1.1.2.2 mjf struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new) 241 1.1.2.2 mjf { 242 1.1.2.2 mjf struct dirhash *del_dirh, *prev_dirh; 243 1.1.2.2 mjf struct dirhash_entry *dirh_e; 244 1.1.2.2 mjf uint32_t hashvalue, hashline; 245 1.1.2.2 mjf int entrysize; 246 1.1.2.2 mjf 247 1.1.2.2 mjf /* make sure we have a dirhash to work on */ 248 1.1.2.2 mjf KASSERT(dirh); 249 1.1.2.2 mjf KASSERT(dirh->refcnt > 0); 250 1.1.2.2 mjf 251 1.1.2.2 mjf /* are we trying to re-enter an entry? */ 252 1.1.2.2 mjf if (!new && (dirh->flags & DIRH_COMPLETE)) 253 1.1.2.2 mjf return; 254 1.1.2.2 mjf 255 1.1.2.2 mjf /* calculate our hash */ 256 1.1.2.3 mjf hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT); 257 1.1.2.2 mjf hashline = hashvalue & DIRHASH_HASHMASK; 258 1.1.2.2 mjf 259 1.1.2.2 mjf /* lookup and insert entry if not there yet */ 260 1.1.2.2 mjf LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 261 1.1.2.2 mjf /* check for hash collision */ 262 1.1.2.2 mjf if (dirh_e->hashvalue != hashvalue) 263 1.1.2.2 mjf continue; 264 1.1.2.2 mjf if (dirh_e->offset != offset) 265 1.1.2.2 mjf continue; 266 1.1.2.2 mjf /* got it already */ 267 1.1.2.2 mjf KASSERT(dirh_e->d_namlen == dirent->d_namlen); 268 1.1.2.2 mjf KASSERT(dirh_e->entry_size == entry_size); 269 1.1.2.2 mjf return; 270 1.1.2.2 mjf } 271 1.1.2.2 mjf 272 1.1.2.2 mjf DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n", 273 1.1.2.2 mjf offset, entry_size, dirent->d_namlen, 274 1.1.2.2 mjf dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 275 1.1.2.2 mjf 276 1.1.2.2 mjf /* check if entry is in free space list */ 277 1.1.2.2 mjf LIST_FOREACH(dirh_e, &dirh->free_entries, next) { 278 1.1.2.2 mjf if (dirh_e->offset == offset) { 279 1.1.2.2 mjf DPRINTF(("\tremoving free entry\n")); 280 1.1.2.2 mjf LIST_REMOVE(dirh_e, next); 281 1.1.2.3 mjf pool_put(&dirhash_entry_pool, dirh_e); 282 1.1.2.2 mjf break; 283 1.1.2.2 mjf } 284 1.1.2.2 mjf } 285 1.1.2.2 mjf 286 1.1.2.2 mjf /* ensure we are not passing the dirhash limit */ 287 1.1.2.2 mjf entrysize = sizeof(struct dirhash_entry); 288 1.1.2.2 mjf if (dirhashsize + entrysize > maxdirhashsize) { 289 1.1.2.3 mjf /* we walk the dirhash_queue, so need to lock it */ 290 1.1.2.3 mjf mutex_enter(&dirhashmutex); 291 1.1.2.2 mjf del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash); 292 1.1.2.2 mjf KASSERT(del_dirh); 293 1.1.2.2 mjf while (dirhashsize + entrysize > maxdirhashsize) { 294 1.1.2.2 mjf /* no use trying to delete myself */ 295 1.1.2.2 mjf if (del_dirh == dirh) 296 1.1.2.2 mjf break; 297 1.1.2.2 mjf prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next); 298 1.1.2.2 mjf if (del_dirh->refcnt == 0) 299 1.1.2.2 mjf dirhash_purge_entries(del_dirh); 300 1.1.2.2 mjf del_dirh = prev_dirh; 301 1.1.2.2 mjf } 302 1.1.2.3 mjf mutex_exit(&dirhashmutex); 303 1.1.2.2 mjf } 304 1.1.2.2 mjf 305 1.1.2.2 mjf /* add to the hashline */ 306 1.1.2.2 mjf dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); 307 1.1.2.2 mjf memset(dirh_e, 0, sizeof(struct dirhash_entry)); 308 1.1.2.2 mjf 309 1.1.2.2 mjf dirh_e->hashvalue = hashvalue; 310 1.1.2.2 mjf dirh_e->offset = offset; 311 1.1.2.2 mjf dirh_e->d_namlen = dirent->d_namlen; 312 1.1.2.2 mjf dirh_e->entry_size = entry_size; 313 1.1.2.2 mjf 314 1.1.2.2 mjf dirh->size += sizeof(struct dirhash_entry); 315 1.1.2.2 mjf dirhashsize += sizeof(struct dirhash_entry); 316 1.1.2.2 mjf LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next); 317 1.1.2.2 mjf } 318 1.1.2.2 mjf 319 1.1.2.2 mjf 320 1.1.2.2 mjf void 321 1.1.2.2 mjf dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, 322 1.1.2.2 mjf uint32_t entry_size) 323 1.1.2.2 mjf { 324 1.1.2.2 mjf struct dirhash_entry *dirh_e; 325 1.1.2.2 mjf 326 1.1.2.2 mjf /* make sure we have a dirhash to work on */ 327 1.1.2.2 mjf KASSERT(dirh); 328 1.1.2.2 mjf KASSERT(dirh->refcnt > 0); 329 1.1.2.2 mjf 330 1.1.2.2 mjf /* check for double entry of free space */ 331 1.1.2.3 mjf LIST_FOREACH(dirh_e, &dirh->free_entries, next) { 332 1.1.2.2 mjf KASSERT(dirh_e->offset != offset); 333 1.1.2.3 mjf } 334 1.1.2.2 mjf 335 1.1.2.2 mjf DPRINTF(("dirhash enter FREED %"PRIu64", %d\n", 336 1.1.2.2 mjf offset, entry_size)); 337 1.1.2.2 mjf dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK); 338 1.1.2.2 mjf memset(dirh_e, 0, sizeof(struct dirhash_entry)); 339 1.1.2.2 mjf 340 1.1.2.2 mjf dirh_e->hashvalue = 0; /* not relevant */ 341 1.1.2.2 mjf dirh_e->offset = offset; 342 1.1.2.2 mjf dirh_e->d_namlen = 0; /* not relevant */ 343 1.1.2.2 mjf dirh_e->entry_size = entry_size; 344 1.1.2.2 mjf 345 1.1.2.2 mjf /* XXX it might be preferable to append them at the tail */ 346 1.1.2.2 mjf LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next); 347 1.1.2.2 mjf dirh->size += sizeof(struct dirhash_entry); 348 1.1.2.2 mjf dirhashsize += sizeof(struct dirhash_entry); 349 1.1.2.2 mjf } 350 1.1.2.2 mjf 351 1.1.2.2 mjf 352 1.1.2.2 mjf void 353 1.1.2.2 mjf dirhash_remove(struct dirhash *dirh, struct dirent *dirent, 354 1.1.2.2 mjf uint64_t offset, uint32_t entry_size) 355 1.1.2.2 mjf { 356 1.1.2.2 mjf struct dirhash_entry *dirh_e; 357 1.1.2.2 mjf uint32_t hashvalue, hashline; 358 1.1.2.2 mjf 359 1.1.2.2 mjf DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n", 360 1.1.2.2 mjf offset, entry_size, 361 1.1.2.2 mjf dirent->d_namlen, dirent->d_namlen, dirent->d_name)); 362 1.1.2.2 mjf 363 1.1.2.2 mjf /* make sure we have a dirhash to work on */ 364 1.1.2.2 mjf KASSERT(dirh); 365 1.1.2.2 mjf KASSERT(dirh->refcnt > 0); 366 1.1.2.2 mjf 367 1.1.2.2 mjf /* calculate our hash */ 368 1.1.2.3 mjf hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT); 369 1.1.2.2 mjf hashline = hashvalue & DIRHASH_HASHMASK; 370 1.1.2.2 mjf 371 1.1.2.2 mjf /* lookup entry */ 372 1.1.2.2 mjf LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) { 373 1.1.2.2 mjf /* check for hash collision */ 374 1.1.2.2 mjf if (dirh_e->hashvalue != hashvalue) 375 1.1.2.2 mjf continue; 376 1.1.2.2 mjf if (dirh_e->offset != offset) 377 1.1.2.2 mjf continue; 378 1.1.2.2 mjf 379 1.1.2.2 mjf /* got it! */ 380 1.1.2.2 mjf KASSERT(dirh_e->d_namlen == dirent->d_namlen); 381 1.1.2.2 mjf KASSERT(dirh_e->entry_size == entry_size); 382 1.1.2.2 mjf LIST_REMOVE(dirh_e, next); 383 1.1.2.3 mjf dirh->size -= sizeof(struct dirhash_entry); 384 1.1.2.2 mjf dirhashsize -= sizeof(struct dirhash_entry); 385 1.1.2.2 mjf 386 1.1.2.2 mjf dirhash_enter_freed(dirh, offset, entry_size); 387 1.1.2.2 mjf return; 388 1.1.2.2 mjf } 389 1.1.2.2 mjf 390 1.1.2.2 mjf /* not found! */ 391 1.1.2.2 mjf panic("dirhash_remove couldn't find entry in hash table\n"); 392 1.1.2.2 mjf } 393 1.1.2.2 mjf 394 1.1.2.2 mjf 395 1.1.2.3 mjf /* 396 1.1.2.3 mjf * BUGALERT: don't use result longer than needed, never past the node lock. 397 1.1.2.3 mjf * Call with NULL *result initially and it will return nonzero if again. 398 1.1.2.3 mjf */ 399 1.1.2.2 mjf int 400 1.1.2.2 mjf dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen, 401 1.1.2.2 mjf struct dirhash_entry **result) 402 1.1.2.2 mjf { 403 1.1.2.2 mjf struct dirhash_entry *dirh_e; 404 1.1.2.2 mjf uint32_t hashvalue, hashline; 405 1.1.2.2 mjf 406 1.1.2.2 mjf /* make sure we have a dirhash to work on */ 407 1.1.2.2 mjf KASSERT(dirh); 408 1.1.2.2 mjf KASSERT(dirh->refcnt > 0); 409 1.1.2.2 mjf 410 1.1.2.2 mjf /* start where we were */ 411 1.1.2.2 mjf if (*result) { 412 1.1.2.2 mjf dirh_e = *result; 413 1.1.2.2 mjf 414 1.1.2.2 mjf /* retrieve information to avoid recalculation and advance */ 415 1.1.2.2 mjf hashvalue = dirh_e->hashvalue; 416 1.1.2.2 mjf dirh_e = LIST_NEXT(*result, next); 417 1.1.2.2 mjf } else { 418 1.1.2.2 mjf /* calculate our hash and lookup all entries in hashline */ 419 1.1.2.3 mjf hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT); 420 1.1.2.2 mjf hashline = hashvalue & DIRHASH_HASHMASK; 421 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->entries[hashline]); 422 1.1.2.2 mjf } 423 1.1.2.2 mjf 424 1.1.2.2 mjf for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 425 1.1.2.2 mjf /* check for hash collision */ 426 1.1.2.2 mjf if (dirh_e->hashvalue != hashvalue) 427 1.1.2.2 mjf continue; 428 1.1.2.2 mjf if (dirh_e->d_namlen != d_namlen) 429 1.1.2.2 mjf continue; 430 1.1.2.2 mjf /* might have an entry in the cache */ 431 1.1.2.2 mjf *result = dirh_e; 432 1.1.2.2 mjf return 1; 433 1.1.2.2 mjf } 434 1.1.2.2 mjf 435 1.1.2.2 mjf *result = NULL; 436 1.1.2.2 mjf return 0; 437 1.1.2.2 mjf } 438 1.1.2.2 mjf 439 1.1.2.2 mjf 440 1.1.2.3 mjf /* 441 1.1.2.3 mjf * BUGALERT: don't use result longer than needed, never past the node lock. 442 1.1.2.3 mjf * Call with NULL *result initially and it will return nonzero if again. 443 1.1.2.3 mjf */ 444 1.1.2.3 mjf 445 1.1.2.2 mjf int 446 1.1.2.2 mjf dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize, 447 1.1.2.2 mjf struct dirhash_entry **result) 448 1.1.2.2 mjf { 449 1.1.2.2 mjf struct dirhash_entry *dirh_e; 450 1.1.2.2 mjf 451 1.1.2.2 mjf /* make sure we have a dirhash to work on */ 452 1.1.2.2 mjf KASSERT(dirh); 453 1.1.2.2 mjf KASSERT(dirh->refcnt > 0); 454 1.1.2.2 mjf 455 1.1.2.2 mjf /* start where we were */ 456 1.1.2.2 mjf if (*result) { 457 1.1.2.2 mjf dirh_e = LIST_NEXT(*result, next); 458 1.1.2.2 mjf } else { 459 1.1.2.2 mjf /* lookup all entries that match */ 460 1.1.2.2 mjf dirh_e = LIST_FIRST(&dirh->free_entries); 461 1.1.2.2 mjf } 462 1.1.2.2 mjf 463 1.1.2.2 mjf for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) { 464 1.1.2.2 mjf /* check for minimum size */ 465 1.1.2.2 mjf if (dirh_e->entry_size < min_entrysize) 466 1.1.2.2 mjf continue; 467 1.1.2.2 mjf /* might be a candidate */ 468 1.1.2.2 mjf *result = dirh_e; 469 1.1.2.2 mjf return 1; 470 1.1.2.2 mjf } 471 1.1.2.2 mjf 472 1.1.2.2 mjf *result = NULL; 473 1.1.2.2 mjf return 0; 474 1.1.2.2 mjf } 475
Indexes created Tue Sep 30 10:09:55 GMT 2025