vfs_dirhash.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /* $NetBSD: vfs_dirhash.c,v 1.15 2022/09/28 09:57:13 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.15 2022/09/28 09:57:13 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 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 /*
  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         dirh->num_files = 0;
  169 
  170         dirhashsize -= dirh->size;
  171         dirh->size = 0;
  172 }
  173 
  174 
  175 void
  176 dirhash_purge(struct dirhash **dirhp)
  177 {
  178         struct dirhash *dirh = *dirhp;
  179 
  180         if (dirh == NULL)
  181                 return;
  182 
  183         /* purge its entries */
  184         dirhash_purge_entries(dirh);
  185 
  186         /* recycle */
  187         mutex_enter(&dirhashmutex);
  188         TAILQ_REMOVE(&dirhash_queue, dirh, next);
  189         mutex_exit(&dirhashmutex);
  190 
  191         pool_put(&dirhash_pool, dirh);
  192         *dirhp = NULL;
  193 }
  194 
  195 
  196 void
  197 dirhash_get(struct dirhash **dirhp)
  198 {
  199         struct dirhash *dirh;
  200         uint32_t hashline;
  201 
  202         /* if no dirhash was given, allocate one */
  203         dirh = *dirhp;
  204         if (dirh == NULL) {
  205                 dirh = pool_get(&dirhash_pool, PR_WAITOK | PR_ZERO);
  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_p)
  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_p && (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 | PR_ZERO);
  304 
  305         dirh_e->hashvalue = hashvalue;
  306         dirh_e->offset    = offset;
  307         dirh_e->d_namlen  = dirent->d_namlen;
  308         dirh_e->entry_size  = entry_size;
  309 
  310         dirh->size  += sizeof(struct dirhash_entry);
  311         dirh->num_files++;
  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 | PR_ZERO);
  335 
  336         dirh_e->hashvalue = 0;          /* not relevant */
  337         dirh_e->offset    = offset;
  338         dirh_e->d_namlen  = 0;          /* not relevant */
  339         dirh_e->entry_size  = entry_size;
  340 
  341         /* XXX it might be preferable to append them at the tail */
  342         LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
  343         dirh->size  += sizeof(struct dirhash_entry);
  344         dirhashsize += sizeof(struct dirhash_entry);
  345 }
  346 
  347 
  348 void
  349 dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
  350         uint64_t offset, uint32_t entry_size)
  351 {
  352         struct dirhash_entry *dirh_e;
  353         uint32_t hashvalue, hashline;
  354 
  355         DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
  356                 offset, entry_size, 
  357                 dirent->d_namlen, dirent->d_namlen, dirent->d_name));
  358 
  359         /* make sure we have a dirhash to work on */
  360         KASSERT(dirh);
  361         KASSERT(dirh->refcnt > 0);
  362 
  363         /* calculate our hash */
  364         hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
  365         hashline  = hashvalue & DIRHASH_HASHMASK;
  366 
  367         /* lookup entry */
  368         LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
  369                 /* check for hash collision */
  370                 if (dirh_e->hashvalue != hashvalue)
  371                         continue;
  372                 if (dirh_e->offset != offset)
  373                         continue;
  374 
  375                 /* got it! */
  376                 KASSERT(dirh_e->d_namlen == dirent->d_namlen);
  377                 KASSERT(dirh_e->entry_size == entry_size);
  378                 LIST_REMOVE(dirh_e, next);
  379                 dirh->size -= sizeof(struct dirhash_entry);
  380                 KASSERT(dirh->num_files > 0);
  381                 dirh->num_files--;
  382                 dirhashsize -= sizeof(struct dirhash_entry);
  383 
  384                 dirhash_enter_freed(dirh, offset, entry_size);
  385                 return;
  386         }
  387 
  388         /* not found! */
  389         panic("dirhash_remove couldn't find entry in hash table\n");
  390 }
  391 
  392 
  393 /*
  394  * BUGALERT: don't use result longer than needed, never past the node lock.
  395  * Call with NULL *result initially and it will return nonzero if again.
  396  */
  397 int
  398 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
  399         struct dirhash_entry **result)
  400 {
  401         struct dirhash_entry *dirh_e;
  402         uint32_t hashvalue, hashline;
  403 
  404         /* make sure we have a dirhash to work on */
  405         KASSERT(dirh);
  406         KASSERT(dirh->refcnt > 0);
  407 
  408         /* start where we were */
  409         if (*result) {
  410                 dirh_e = *result;
  411 
  412                 /* retrieve information to avoid recalculation and advance */
  413                 hashvalue = dirh_e->hashvalue;
  414                 dirh_e = LIST_NEXT(*result, next);
  415         } else {
  416                 /* calculate our hash and lookup all entries in hashline */
  417                 hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
  418                 hashline  = hashvalue & DIRHASH_HASHMASK;
  419                 dirh_e = LIST_FIRST(&dirh->entries[hashline]);
  420         }
  421 
  422         for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
  423                 /* check for hash collision */
  424                 if (dirh_e->hashvalue != hashvalue)
  425                         continue;
  426                 if (dirh_e->d_namlen != d_namlen)
  427                         continue;
  428                 /* might have an entry in the cache */
  429                 *result = dirh_e;
  430                 return 1;
  431         }
  432 
  433         *result = NULL;
  434         return 0;
  435 }
  436 
  437 
  438 /*
  439  * BUGALERT: don't use result longer than needed, never past the node lock.
  440  * Call with NULL *result initially and it will return nonzero if again.
  441  */
  442 
  443 int
  444 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
  445         struct dirhash_entry **result)
  446 {
  447         struct dirhash_entry *dirh_e;
  448 
  449         /* make sure we have a dirhash to work on */
  450         KASSERT(dirh);
  451         KASSERT(dirh->refcnt > 0);
  452 
  453         /* start where we were */
  454         if (*result) {
  455                 dirh_e = LIST_NEXT(*result, next);
  456         } else {
  457                 /* lookup all entries that match */
  458                 dirh_e = LIST_FIRST(&dirh->free_entries);
  459         }
  460 
  461         for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
  462                 /* check for minimum size */
  463                 if (dirh_e->entry_size < min_entrysize)
  464                         continue;
  465                 /* might be a candidate */
  466                 *result = dirh_e;
  467                 return 1;
  468         }
  469 
  470         *result = NULL;
  471         return 0;
  472 }
  473 
  474 
  475 bool
  476 dirhash_dir_isempty(struct dirhash *dirh)
  477 {
  478 #ifdef DEBUG
  479         struct dirhash_entry *dirh_e;
  480         int hashline, num;
  481 
  482         num = 0;
  483         for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
  484                 LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
  485                         num++;
  486                 }
  487         }
  488 
  489         if (dirh->num_files != num) {
  490                 printf("dirhash_dir_isempy: dirhash_counter failed: "
  491                         "dirh->num_files = %d, counted %d\n",
  492                         dirh->num_files, num);
  493                 assert(dirh->num_files == num);
  494         }
  495 #endif
  496         /* assert the directory hash info is valid */
  497         KASSERT(dirh->flags & DIRH_COMPLETE);
  498 
  499         /* the directory is empty when only '..' lifes in it or is absent */
  500         return (dirh->num_files <= 1);
  501 }
  502
Cache object: 569d61e4918a5c550307d68c921f0713
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/kern/vfs_dirhash.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/vfs_dirhash.c
