sys/kern/vfs_dirhash.c

   1 /* $NetBSD: vfs_dirhash.c,v 1.9 2008/12/28 17:11:26 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.9 2008/12/28 17:11:26 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  * 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
 169         dirhashsize -= dirh->size;
 170         dirh->size = 0;
 171 }
 172
 173
 174 void
 175 dirhash_purge(struct dirhash **dirhp)
 176 {
 177         struct dirhash *dirh = *dirhp;
 178
 179         if (dirh == NULL)
 180                 return;
 181
 182         /* purge its entries */
 183         dirhash_purge_entries(dirh);
 184
 185         /* recycle */
 186         mutex_enter(&dirhashmutex);
 187         TAILQ_REMOVE(&dirhash_queue, dirh, next);
 188         mutex_exit(&dirhashmutex);
 189
 190         pool_put(&dirhash_pool, dirh);
 191         *dirhp = NULL;
 192 }
 193
 194
 195 void
 196 dirhash_get(struct dirhash **dirhp)
 197 {
 198         struct dirhash *dirh;
 199         uint32_t hashline;
 200
 201         /* if no dirhash was given, allocate one */
 202         dirh = *dirhp;
 203         if (dirh == NULL) {
 204                 dirh = pool_get(&dirhash_pool, PR_WAITOK);
 205                 memset(dirh, 0, sizeof(struct dirhash));
 206                 for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
 207                         LIST_INIT(&dirh->entries[hashline]);
 208                 }
 209         }
 210
 211         /* implement LRU on the dirhash queue */
 212         mutex_enter(&dirhashmutex);
 213         if (*dirhp) {
 214                 /* remove from queue to be requeued */
 215                 TAILQ_REMOVE(&dirhash_queue, dirh, next);
 216         }
 217         dirh->refcnt++;
 218         TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next);
 219         mutex_exit(&dirhashmutex);
 220
 221         *dirhp = dirh;
 222 }
 223
 224
 225 void
 226 dirhash_put(struct dirhash *dirh)
 227 {
 228
 229         mutex_enter(&dirhashmutex);
 230         dirh->refcnt--;
 231         mutex_exit(&dirhashmutex);
 232 }
 233
 234
 235 void
 236 dirhash_enter(struct dirhash *dirh,
 237         struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new)
 238 {
 239         struct dirhash *del_dirh, *prev_dirh;
 240         struct dirhash_entry *dirh_e;
 241         uint32_t hashvalue, hashline;
 242         int entrysize;
 243
 244         /* make sure we have a dirhash to work on */
 245         KASSERT(dirh);
 246         KASSERT(dirh->refcnt > 0);
 247
 248         /* are we trying to re-enter an entry? */
 249         if (!new && (dirh->flags & DIRH_COMPLETE))
 250                 return;
 251
 252         /* calculate our hash */
 253         hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
 254         hashline  = hashvalue & DIRHASH_HASHMASK;
 255
 256         /* lookup and insert entry if not there yet */
 257         LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
 258                 /* check for hash collision */
 259                 if (dirh_e->hashvalue != hashvalue)
 260                         continue;
 261                 if (dirh_e->offset != offset)
 262                         continue;
 263                 /* got it already */
 264                 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
 265                 KASSERT(dirh_e->entry_size == entry_size);
 266                 return;
 267         }
 268
 269         DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n",
 270                 offset, entry_size, dirent->d_namlen,
 271                 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
 272
 273         /* check if entry is in free space list */
 274         LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
 275                 if (dirh_e->offset == offset) {
 276                         DPRINTF(("\tremoving free entry\n"));
 277                         LIST_REMOVE(dirh_e, next);
 278                         pool_put(&dirhash_entry_pool, dirh_e);
 279                         break;
 280                 }
 281         }
 282
 283         /* ensure we are not passing the dirhash limit */
 284         entrysize = sizeof(struct dirhash_entry);
 285         if (dirhashsize + entrysize > maxdirhashsize) {
 286                 /* we walk the dirhash_queue, so need to lock it */
 287                 mutex_enter(&dirhashmutex);
 288                 del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash);
 289                 KASSERT(del_dirh);
 290                 while (dirhashsize + entrysize > maxdirhashsize) {
 291                         /* no use trying to delete myself */
 292                         if (del_dirh == dirh)
 293                                 break;
 294                         prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next);
 295                         if (del_dirh->refcnt == 0)
 296                                 dirhash_purge_entries(del_dirh);
 297                         del_dirh = prev_dirh;
 298                 }
 299                 mutex_exit(&dirhashmutex);
 300         }
 301
 302         /* add to the hashline */
 303         dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK);
 304         memset(dirh_e, 0, sizeof(struct dirhash_entry));
 305
 306         dirh_e->hashvalue = hashvalue;
 307         dirh_e->offset    = offset;
 308         dirh_e->d_namlen  = dirent->d_namlen;
 309         dirh_e->entry_size  = entry_size;
 310
 311         dirh->size  += sizeof(struct dirhash_entry);
 312         dirhashsize += sizeof(struct dirhash_entry);
 313         LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next);
 314 }
 315
 316
 317 void
 318 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset,
 319         uint32_t entry_size)
 320 {
 321         struct dirhash_entry *dirh_e;
 322
 323         /* make sure we have a dirhash to work on */
 324         KASSERT(dirh);
 325         KASSERT(dirh->refcnt > 0);
 326
 327         /* check for double entry of free space */
 328         LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
 329                 KASSERT(dirh_e->offset != offset);
 330         }
 331
 332         DPRINTF(("dirhash enter FREED %"PRIu64", %d\n",
 333                 offset, entry_size));
 334         dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK);
 335         memset(dirh_e, 0, sizeof(struct dirhash_entry));
 336
 337         dirh_e->hashvalue = 0;          /* not relevant */
 338         dirh_e->offset    = offset;
 339         dirh_e->d_namlen  = 0;          /* not relevant */
 340         dirh_e->entry_size  = entry_size;
 341
 342         /* XXX it might be preferable to append them at the tail */
 343         LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
 344         dirh->size  += sizeof(struct dirhash_entry);
 345         dirhashsize += sizeof(struct dirhash_entry);
 346 }
 347
 348
 349 void
 350 dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
 351         uint64_t offset, uint32_t entry_size)
 352 {
 353         struct dirhash_entry *dirh_e;
 354         uint32_t hashvalue, hashline;
 355
 356         DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
 357                 offset, entry_size,
 358                 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
 359
 360         /* make sure we have a dirhash to work on */
 361         KASSERT(dirh);
 362         KASSERT(dirh->refcnt > 0);
 363
 364         /* calculate our hash */
 365         hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
 366         hashline  = hashvalue & DIRHASH_HASHMASK;
 367
 368         /* lookup entry */
 369         LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
 370                 /* check for hash collision */
 371                 if (dirh_e->hashvalue != hashvalue)
 372                         continue;
 373                 if (dirh_e->offset != offset)
 374                         continue;
 375
 376                 /* got it! */
 377                 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
 378                 KASSERT(dirh_e->entry_size == entry_size);
 379                 LIST_REMOVE(dirh_e, next);
 380                 dirh->size -= sizeof(struct dirhash_entry);
 381                 dirhashsize -= sizeof(struct dirhash_entry);
 382
 383                 dirhash_enter_freed(dirh, offset, entry_size);
 384                 return;
 385         }
 386
 387         /* not found! */
 388         panic("dirhash_remove couldn't find entry in hash table\n");
 389 }
 390
 391
 392 /*
 393  * BUGALERT: don't use result longer than needed, never past the node lock.
 394  * Call with NULL *result initially and it will return nonzero if again.
 395  */
 396 int
 397 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
 398         struct dirhash_entry **result)
 399 {
 400         struct dirhash_entry *dirh_e;
 401         uint32_t hashvalue, hashline;
 402
 403         /* make sure we have a dirhash to work on */
 404         KASSERT(dirh);
 405         KASSERT(dirh->refcnt > 0);
 406
 407         /* start where we were */
 408         if (*result) {
 409                 dirh_e = *result;
 410
 411                 /* retrieve information to avoid recalculation and advance */
 412                 hashvalue = dirh_e->hashvalue;
 413                 dirh_e = LIST_NEXT(*result, next);
 414         } else {
 415                 /* calculate our hash and lookup all entries in hashline */
 416                 hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
 417                 hashline  = hashvalue & DIRHASH_HASHMASK;
 418                 dirh_e = LIST_FIRST(&dirh->entries[hashline]);
 419         }
 420
 421         for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
 422                 /* check for hash collision */
 423                 if (dirh_e->hashvalue != hashvalue)
 424                         continue;
 425                 if (dirh_e->d_namlen != d_namlen)
 426                         continue;
 427                 /* might have an entry in the cache */
 428                 *result = dirh_e;
 429                 return 1;
 430         }
 431
 432         *result = NULL;
 433         return 0;
 434 }
 435
 436
 437 /*
 438  * BUGALERT: don't use result longer than needed, never past the node lock.
 439  * Call with NULL *result initially and it will return nonzero if again.
 440  */
 441
 442 int
 443 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
 444         struct dirhash_entry **result)
 445 {
 446         struct dirhash_entry *dirh_e;
 447
 448         /* make sure we have a dirhash to work on */
 449         KASSERT(dirh);
 450         KASSERT(dirh->refcnt > 0);
 451
 452         /* start where we were */
 453         if (*result) {
 454                 dirh_e = LIST_NEXT(*result, next);
 455         } else {
 456                 /* lookup all entries that match */
 457                 dirh_e = LIST_FIRST(&dirh->free_entries);
 458         }
 459
 460         for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
 461                 /* check for minimum size */
 462                 if (dirh_e->entry_size < min_entrysize)
 463                         continue;
 464                 /* might be a candidate */
 465                 *result = dirh_e;
 466                 return 1;
 467         }
 468
 469         *result = NULL;
 470         return 0;
 471 }