ufs/ufs/ufs_dirhash.c

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
TAILQ_HEAD
ufsdirhash_free
ufsdirhash_lookup
ufsdirhash_findfree
ufsdirhash_enduseful
ufsdirhash_add
ufsdirhash_remove
ufsdirhash_move
ufsdirhash_newblk
ufsdirhash_dirtrunc
ufsdirhash_checkblock
ufsdirhash_hash
ufsdirhash_adjfree
ufsdirhash_findslot
ufsdirhash_delslot
ufsdirhash_getprev
ufsdirhash_recycle
ufsdirhash_init
ufsdirhash_uninit
    1 /* $OpenBSD: ufs_dirhash.c,v 1.15 2007/07/23 17:28:25 kettenis Exp $    */
    2 /*
    3  * Copyright (c) 2001, 2002 Ian Dowse.  All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer.
   10  * 2. Redistributions in binary form must reproduce the above copyright
   11  *    notice, this list of conditions and the following disclaimer in the
   12  *    documentation and/or other materials provided with the distribution.
   13  *
   14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24  * SUCH DAMAGE.
   25  */
   26 
   27 /*
   28  * This implements a hash-based lookup scheme for UFS directories.
   29  */
   30 
   31 #if 0
   32 __FBSDID("$FreeBSD: src/sys/ufs/ufs/ufs_dirhash.c,v 1.18 2004/02/15 21:39:35 dwmalone Exp $");
   33 #endif
   34 
   35 #include <sys/param.h>
   36 #include <sys/systm.h>
   37 #include <sys/kernel.h>
   38 #include <sys/lock.h>
   39 #include <sys/rwlock.h>
   40 #include <sys/malloc.h>
   41 #include <sys/pool.h>
   42 #include <sys/proc.h>
   43 #include <sys/buf.h>
   44 #include <sys/vnode.h>
   45 #include <sys/mount.h>
   46 #include <sys/sysctl.h>
   47 #include <sys/hash.h>
   48 
   49 #include <ufs/ufs/quota.h>
   50 #include <ufs/ufs/inode.h>
   51 #include <ufs/ufs/dir.h>
   52 #include <ufs/ufs/dirhash.h>
   53 #include <ufs/ufs/ufsmount.h>
   54 #include <ufs/ufs/ufs_extern.h>
   55 
   56 #define WRAPINCR(val, limit)    (((val) + 1 == (limit)) ? 0 : ((val) + 1))
   57 #define WRAPDECR(val, limit)    (((val) == 0) ? ((limit) - 1) : ((val) - 1))
   58 #define OFSFMT(vp)              ((vp)->v_mount->mnt_maxsymlinklen <= 0)
   59 #define BLKFREE2IDX(n)          ((n) > DH_NFSTATS ? DH_NFSTATS : (n))
   60 
   61 int ufs_mindirhashsize;
   62 int ufs_dirhashmaxmem;
   63 int ufs_dirhashmem;
   64 int ufs_dirhashcheck;
   65 
   66 
   67 int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen);
   68 void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff);
   69 void ufsdirhash_delslot(struct dirhash *dh, int slot);
   70 int ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen,
   71    doff_t offset);
   72 doff_t ufsdirhash_getprev(struct direct *dp, doff_t offset);
   73 int ufsdirhash_recycle(int wanted);
   74 
   75 struct pool             ufsdirhash_pool;
   76 
   77 #define DIRHASHLIST_LOCK()
   78 #define DIRHASHLIST_UNLOCK()
   79 #define DIRHASH_LOCK(dh)
   80 #define DIRHASH_UNLOCK(dh)
   81 #define DIRHASH_BLKALLOC()      pool_get(&ufsdirhash_pool, PR_NOWAIT)
   82 #define DIRHASH_BLKFREE(v)      pool_put(&ufsdirhash_pool, v)
   83 
   84 #define mtx_assert(l, f)        /* nothing */
   85 #define DIRHASH_ASSERT(e, m)    KASSERT((e))
   86 
   87 /* Dirhash list; recently-used entries are near the tail. */
   88 TAILQ_HEAD(, dirhash) ufsdirhash_list;
   89 
   90 /* Protects: ufsdirhash_list, `dh_list' field, ufs_dirhashmem. */
   91 
   92 /*
   93  * Locking order:
   94  *      ufsdirhash_mtx
   95  *      dh_mtx
   96  *
   97  * The dh_mtx mutex should be acquired either via the inode lock, or via
   98  * ufsdirhash_mtx. Only the owner of the inode may free the associated
   99  * dirhash, but anything can steal its memory and set dh_hash to NULL.
  100  */
  101 
  102 /*
  103  * Attempt to build up a hash table for the directory contents in
  104  * inode 'ip'. Returns 0 on success, or -1 of the operation failed.
  105  */
  106 int
  107 ufsdirhash_build(struct inode *ip)
  108 {
  109         struct dirhash *dh;
  110         struct buf *bp = NULL;
  111         struct direct *ep;
  112         struct vnode *vp;
  113         doff_t bmask, pos;
  114         int dirblocks, i, j, memreqd, nblocks, narrays, nslots, slot;
  115 
  116         /* Check if we can/should use dirhash. */
  117         if (ip->i_dirhash == NULL) {
  118                 if (DIP(ip, size) < ufs_mindirhashsize || OFSFMT(ip->i_vnode))
  119                         return (-1);
  120         } else {
  121                 /* Hash exists, but sysctls could have changed. */
  122                 if (DIP(ip, size) < ufs_mindirhashsize ||
  123                     ufs_dirhashmem > ufs_dirhashmaxmem) {
  124                         ufsdirhash_free(ip);
  125                         return (-1);
  126                 }
  127                 /* Check if hash exists and is intact (note: unlocked read). */
  128                 if (ip->i_dirhash->dh_hash != NULL)
  129                         return (0);
  130                 /* Free the old, recycled hash and build a new one. */
  131                 ufsdirhash_free(ip);
  132         }
  133 
  134         /* Don't hash removed directories. */
  135         if (ip->i_effnlink == 0)
  136                 return (-1);
  137 
  138         vp = ip->i_vnode;
  139         /* Allocate 50% more entries than this dir size could ever need. */
  140         DIRHASH_ASSERT(DIP(ip, size) >= DIRBLKSIZ, ("ufsdirhash_build size"));
  141         nslots = DIP(ip, size) / DIRECTSIZ(1);
  142         nslots = (nslots * 3 + 1) / 2;
  143         narrays = howmany(nslots, DH_NBLKOFF);
  144         nslots = narrays * DH_NBLKOFF;
  145         dirblocks = howmany(DIP(ip, size), DIRBLKSIZ);
  146         nblocks = (dirblocks * 3 + 1) / 2;
  147 
  148         memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
  149             narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
  150             nblocks * sizeof(*dh->dh_blkfree);
  151         DIRHASHLIST_LOCK();
  152         if (memreqd + ufs_dirhashmem > ufs_dirhashmaxmem) {
  153                 DIRHASHLIST_UNLOCK();
  154                 if (memreqd > ufs_dirhashmaxmem / 2)
  155                         return (-1);
  156 
  157                 /* Try to free some space. */
  158                 if (ufsdirhash_recycle(memreqd) != 0)
  159                         return (-1);
  160                 /* Enough was freed, and list has been locked. */
  161         }
  162         ufs_dirhashmem += memreqd;
  163         DIRHASHLIST_UNLOCK();
  164 
  165         /*
  166          * Use non-blocking mallocs so that we will revert to a linear
  167          * lookup on failure rather than potentially blocking forever.
  168          */
  169         MALLOC(dh, struct dirhash *, sizeof *dh, M_DIRHASH, M_NOWAIT);
  170         if (dh == NULL) {
  171                 DIRHASHLIST_LOCK();
  172                 ufs_dirhashmem -= memreqd;
  173                 DIRHASHLIST_UNLOCK();
  174                 return (-1);
  175         }
  176         memset(dh, 0, sizeof *dh);
  177         dh->dh_hash = malloc(narrays * sizeof(dh->dh_hash[0]),
  178             M_DIRHASH, M_NOWAIT);
  179         dh->dh_blkfree = malloc(nblocks * sizeof(dh->dh_blkfree[0]),
  180             M_DIRHASH, M_NOWAIT);
  181         if (dh->dh_hash == NULL || dh->dh_blkfree == NULL)
  182                 goto fail;
  183         memset(dh->dh_hash, 0, narrays * sizeof(dh->dh_hash[0]));
  184         for (i = 0; i < narrays; i++) {
  185                 if ((dh->dh_hash[i] = DIRHASH_BLKALLOC()) == NULL)
  186                         goto fail;
  187                 for (j = 0; j < DH_NBLKOFF; j++)
  188                         dh->dh_hash[i][j] = DIRHASH_EMPTY;
  189         }
  190 
  191         /* Initialise the hash table and block statistics. */
  192         dh->dh_narrays = narrays;
  193         dh->dh_hlen = nslots;
  194         dh->dh_nblk = nblocks;
  195         dh->dh_dirblks = dirblocks;
  196         for (i = 0; i < dirblocks; i++)
  197                 dh->dh_blkfree[i] = DIRBLKSIZ / DIRALIGN;
  198         for (i = 0; i < DH_NFSTATS; i++)
  199                 dh->dh_firstfree[i] = -1;
  200         dh->dh_firstfree[DH_NFSTATS] = 0;
  201         dh->dh_seqopt = 0;
  202         dh->dh_seqoff = 0;
  203         dh->dh_score = DH_SCOREINIT;
  204         ip->i_dirhash = dh;
  205 
  206         bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
  207         pos = 0;
  208         while (pos < DIP(ip, size)) {
  209                 /* If necessary, get the next directory block. */
  210                 if ((pos & bmask) == 0) {
  211                         if (bp != NULL)
  212                                 brelse(bp);
  213                         if (UFS_BUFATOFF(ip, (off_t)pos, NULL, &bp) != 0)
  214                                 goto fail;
  215                 }
  216 
  217                 /* Add this entry to the hash. */
  218                 ep = (struct direct *)((char *)bp->b_data + (pos & bmask));
  219                 if (ep->d_reclen == 0 || ep->d_reclen >
  220                     DIRBLKSIZ - (pos & (DIRBLKSIZ - 1))) {
  221                         /* Corrupted directory. */
  222                         brelse(bp);
  223                         goto fail;
  224                 }
  225                 if (ep->d_ino != 0) {
  226                         /* Add the entry (simplified ufsdirhash_add). */
  227                         slot = ufsdirhash_hash(dh, ep->d_name, ep->d_namlen);
  228                         while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
  229                                 slot = WRAPINCR(slot, dh->dh_hlen);
  230                         dh->dh_hused++;
  231                         DH_ENTRY(dh, slot) = pos;
  232                         ufsdirhash_adjfree(dh, pos, -DIRSIZ(0, ep));
  233                 }
  234                 pos += ep->d_reclen;
  235         }
  236 
  237         if (bp != NULL)
  238                 brelse(bp);
  239         DIRHASHLIST_LOCK();
  240         TAILQ_INSERT_TAIL(&ufsdirhash_list, dh, dh_list);
  241         dh->dh_onlist = 1;
  242         DIRHASHLIST_UNLOCK();
  243         return (0);
  244 
  245 fail:
  246         if (dh->dh_hash != NULL) {
  247                 for (i = 0; i < narrays; i++)
  248                         if (dh->dh_hash[i] != NULL)
  249                                 DIRHASH_BLKFREE(dh->dh_hash[i]);
  250                 free(dh->dh_hash, M_DIRHASH);
  251         }
  252         if (dh->dh_blkfree != NULL)
  253                 free(dh->dh_blkfree, M_DIRHASH);
  254         FREE(dh, M_DIRHASH);
  255         ip->i_dirhash = NULL;
  256         DIRHASHLIST_LOCK();
  257         ufs_dirhashmem -= memreqd;
  258         DIRHASHLIST_UNLOCK();
  259         return (-1);
  260 }
  261 
  262 /*
  263  * Free any hash table associated with inode 'ip'.
  264  */
  265 void
  266 ufsdirhash_free(struct inode *ip)
  267 {
  268         struct dirhash *dh;
  269         int i, mem;
  270 
  271         if ((dh = ip->i_dirhash) == NULL)
  272                 return;
  273         DIRHASHLIST_LOCK();
  274         DIRHASH_LOCK(dh);
  275         if (dh->dh_onlist)
  276                 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
  277         DIRHASH_UNLOCK(dh);
  278         DIRHASHLIST_UNLOCK();
  279 
  280         /* The dirhash pointed to by 'dh' is exclusively ours now. */
  281 
  282         mem = sizeof(*dh);
  283         if (dh->dh_hash != NULL) {
  284                 for (i = 0; i < dh->dh_narrays; i++)
  285                         DIRHASH_BLKFREE(dh->dh_hash[i]);
  286                 free(dh->dh_hash, M_DIRHASH);
  287                 free(dh->dh_blkfree, M_DIRHASH);
  288                 mem += dh->dh_narrays * sizeof(*dh->dh_hash) +
  289                     dh->dh_narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
  290                     dh->dh_nblk * sizeof(*dh->dh_blkfree);
  291         }
  292         FREE(dh, M_DIRHASH);
  293         ip->i_dirhash = NULL;
  294 
  295         DIRHASHLIST_LOCK();
  296         ufs_dirhashmem -= mem;
  297         DIRHASHLIST_UNLOCK();
  298 }
  299 
  300 /*
  301  * Find the offset of the specified name within the given inode.
  302  * Returns 0 on success, ENOENT if the entry does not exist, or
  303  * EJUSTRETURN if the caller should revert to a linear search.
  304  *
  305  * If successful, the directory offset is stored in *offp, and a
  306  * pointer to a struct buf containing the entry is stored in *bpp. If
  307  * prevoffp is non-NULL, the offset of the previous entry within
  308  * the DIRBLKSIZ-sized block is stored in *prevoffp (if the entry
  309  * is the first in a block, the start of the block is used).
  310  */
  311 int
  312 ufsdirhash_lookup(struct inode *ip, char *name, int namelen, doff_t *offp,
  313     struct buf **bpp, doff_t *prevoffp)
  314 {
  315         struct dirhash *dh, *dh_next;
  316         struct direct *dp;
  317         struct vnode *vp;
  318         struct buf *bp;
  319         doff_t blkoff, bmask, offset, prevoff;
  320         int i, slot;
  321 
  322         if ((dh = ip->i_dirhash) == NULL)
  323                 return (EJUSTRETURN);
  324         /*
  325          * Move this dirhash towards the end of the list if it has a
  326          * score higher than the next entry, and acquire the dh_mtx.
  327          * Optimise the case where it's already the last by performing
  328          * an unlocked read of the TAILQ_NEXT pointer.
  329          *
  330          * In both cases, end up holding just dh_mtx.
  331          */
  332         if (TAILQ_NEXT(dh, dh_list) != NULL) {
  333                 DIRHASHLIST_LOCK();
  334                 DIRHASH_LOCK(dh);
  335                 /*
  336                  * If the new score will be greater than that of the next
  337                  * entry, then move this entry past it. With both mutexes
  338                  * held, dh_next won't go away, but its dh_score could
  339                  * change; that's not important since it is just a hint.
  340                  */
  341                 if (dh->dh_hash != NULL &&
  342                     (dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
  343                     dh->dh_score >= dh_next->dh_score) {
  344                         DIRHASH_ASSERT(dh->dh_onlist, ("dirhash: not on list"));
  345                         TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
  346                         TAILQ_INSERT_AFTER(&ufsdirhash_list, dh_next, dh,
  347                             dh_list);
  348                 }
  349                 DIRHASHLIST_UNLOCK();
  350         } else {
  351                 /* Already the last, though that could change as we wait. */
  352                 DIRHASH_LOCK(dh);
  353         }
  354         if (dh->dh_hash == NULL) {
  355                 DIRHASH_UNLOCK(dh);
  356                 ufsdirhash_free(ip);
  357                 return (EJUSTRETURN);
  358         }
  359 
  360         /* Update the score. */
  361         if (dh->dh_score < DH_SCOREMAX)
  362                 dh->dh_score++;
  363 
  364         vp = ip->i_vnode;
  365         bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
  366         blkoff = -1;
  367         bp = NULL;
  368 restart:
  369         slot = ufsdirhash_hash(dh, name, namelen);
  370 
  371         if (dh->dh_seqopt) {
  372                 /*
  373                  * Sequential access optimisation. dh_seqoff contains the
  374                  * offset of the directory entry immediately following
  375                  * the last entry that was looked up. Check if this offset
  376                  * appears in the hash chain for the name we are looking for.
  377                  */
  378                 for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
  379                     i = WRAPINCR(i, dh->dh_hlen))
  380                         if (offset == dh->dh_seqoff)
  381                                 break;
  382                 if (offset == dh->dh_seqoff) {
  383                         /*
  384                          * We found an entry with the expected offset. This
  385                          * is probably the entry we want, but if not, the
  386                          * code below will turn off seqoff and retry.
  387                          */
  388                         slot = i;
  389                 } else
  390                         dh->dh_seqopt = 0;
  391         }
  392 
  393         for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
  394             slot = WRAPINCR(slot, dh->dh_hlen)) {
  395                 if (offset == DIRHASH_DEL)
  396                         continue;
  397                 DIRHASH_UNLOCK(dh);
  398 
  399                 if (offset < 0 || offset >= DIP(ip, size))
  400                         panic("ufsdirhash_lookup: bad offset in hash array");
  401                 if ((offset & ~bmask) != blkoff) {
  402                         if (bp != NULL)
  403                                 brelse(bp);
  404                         blkoff = offset & ~bmask;
  405                         if (UFS_BUFATOFF(ip, (off_t)blkoff, NULL, &bp) != 0)
  406                                 return (EJUSTRETURN);
  407                 }
  408                 dp = (struct direct *)(bp->b_data + (offset & bmask));
  409                 if (dp->d_reclen == 0 || dp->d_reclen >
  410                     DIRBLKSIZ - (offset & (DIRBLKSIZ - 1))) {
  411                         /* Corrupted directory. */
  412                         brelse(bp);
  413                         return (EJUSTRETURN);
  414                 }
  415                 if (dp->d_namlen == namelen &&
  416                     bcmp(dp->d_name, name, namelen) == 0) {
  417                         /* Found. Get the prev offset if needed. */
  418                         if (prevoffp != NULL) {
  419                                 if (offset & (DIRBLKSIZ - 1)) {
  420                                         prevoff = ufsdirhash_getprev(dp,
  421                                             offset);
  422                                         if (prevoff == -1) {
  423                                                 brelse(bp);
  424                                                 return (EJUSTRETURN);
  425                                         }
  426                                 } else
  427                                         prevoff = offset;
  428                                 *prevoffp = prevoff;
  429                         }
  430 
  431                         /* Check for sequential access, and update offset. */
  432                         if (dh->dh_seqopt == 0 && dh->dh_seqoff == offset)
  433                                 dh->dh_seqopt = 1;
  434                         dh->dh_seqoff = offset + DIRSIZ(0, dp);
  435 
  436                         *bpp = bp;
  437                         *offp = offset;
  438                         return (0);
  439                 }
  440 
  441                 DIRHASH_LOCK(dh);
  442                 if (dh->dh_hash == NULL) {
  443                         DIRHASH_UNLOCK(dh);
  444                         if (bp != NULL)
  445                                 brelse(bp);
  446                         ufsdirhash_free(ip);
  447                         return (EJUSTRETURN);
  448                 }
  449                 /*
  450                  * When the name doesn't match in the seqopt case, go back
  451                  * and search normally.
  452                  */
  453                 if (dh->dh_seqopt) {
  454                         dh->dh_seqopt = 0;
  455                         goto restart;
  456                 }
  457         }
  458         DIRHASH_UNLOCK(dh);
  459         if (bp != NULL)
  460                 brelse(bp);
  461         return (ENOENT);
  462 }
  463 
  464 /*
  465  * Find a directory block with room for 'slotneeded' bytes. Returns
  466  * the offset of the directory entry that begins the free space.
  467  * This will either be the offset of an existing entry that has free
  468  * space at the end, or the offset of an entry with d_ino == 0 at
  469  * the start of a DIRBLKSIZ block.
  470  *
  471  * To use the space, the caller may need to compact existing entries in
  472  * the directory. The total number of bytes in all of the entries involved
  473  * in the compaction is stored in *slotsize. In other words, all of
  474  * the entries that must be compacted are exactly contained in the
  475  * region beginning at the returned offset and spanning *slotsize bytes.
  476  *
  477  * Returns -1 if no space was found, indicating that the directory
  478  * must be extended.
  479  */
  480 doff_t
  481 ufsdirhash_findfree(struct inode *ip, int slotneeded, int *slotsize)
  482 {
  483         struct direct *dp;
  484         struct dirhash *dh;
  485         struct buf *bp;
  486         doff_t pos, slotstart;
  487         int dirblock, error, freebytes, i;
  488 
  489         if ((dh = ip->i_dirhash) == NULL)
  490                 return (-1);
  491         DIRHASH_LOCK(dh);
  492         if (dh->dh_hash == NULL) {
  493                 DIRHASH_UNLOCK(dh);
  494                 ufsdirhash_free(ip);
  495                 return (-1);
  496         }
  497 
  498         /* Find a directory block with the desired free space. */
  499         dirblock = -1;
  500         for (i = howmany(slotneeded, DIRALIGN); i <= DH_NFSTATS; i++)
  501                 if ((dirblock = dh->dh_firstfree[i]) != -1)
  502                         break;
  503         if (dirblock == -1) {
  504                 DIRHASH_UNLOCK(dh);
  505                 return (-1);
  506         }
  507 
  508         DIRHASH_ASSERT(dirblock < dh->dh_nblk &&
  509             dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN),
  510             ("ufsdirhash_findfree: bad stats"));
  511         DIRHASH_UNLOCK(dh);
  512         pos = dirblock * DIRBLKSIZ;
  513         error = UFS_BUFATOFF(ip, (off_t)pos, (char **)&dp, &bp);
  514         if (error)
  515                 return (-1);
  516 
  517         /* Find the first entry with free space. */
  518         for (i = 0; i < DIRBLKSIZ; ) {
  519                 if (dp->d_reclen == 0) {
  520                         brelse(bp);
  521                         return (-1);
  522                 }
  523                 if (dp->d_ino == 0 || dp->d_reclen > DIRSIZ(0, dp))
  524                         break;
  525                 i += dp->d_reclen;
  526                 dp = (struct direct *)((char *)dp + dp->d_reclen);
  527         }
  528         if (i > DIRBLKSIZ) {
  529                 brelse(bp);
  530                 return (-1);
  531         }
  532         slotstart = pos + i;
  533 
  534         /* Find the range of entries needed to get enough space */
  535         freebytes = 0;
  536         while (i < DIRBLKSIZ && freebytes < slotneeded) {
  537                 freebytes += dp->d_reclen;
  538                 if (dp->d_ino != 0)
  539                         freebytes -= DIRSIZ(0, dp);
  540                 if (dp->d_reclen == 0) {
  541                         brelse(bp);
  542                         return (-1);
  543                 }
  544                 i += dp->d_reclen;
  545                 dp = (struct direct *)((char *)dp + dp->d_reclen);
  546         }
  547         if (i > DIRBLKSIZ) {
  548                 brelse(bp);
  549                 return (-1);
  550         }
  551         if (freebytes < slotneeded)
  552                 panic("ufsdirhash_findfree: free mismatch");
  553         brelse(bp);
  554         *slotsize = pos + i - slotstart;
  555         return (slotstart);
  556 }
  557 
  558 /*
  559  * Return the start of the unused space at the end of a directory, or
  560  * -1 if there are no trailing unused blocks.
  561  */
  562 doff_t
  563 ufsdirhash_enduseful(struct inode *ip)
  564 {
  565 
  566         struct dirhash *dh;
  567         int i;
  568 
  569         if ((dh = ip->i_dirhash) == NULL)
  570                 return (-1);
  571         DIRHASH_LOCK(dh);
  572         if (dh->dh_hash == NULL) {
  573                 DIRHASH_UNLOCK(dh);
  574                 ufsdirhash_free(ip);
  575                 return (-1);
  576         }
  577 
  578         if (dh->dh_blkfree[dh->dh_dirblks - 1] != DIRBLKSIZ / DIRALIGN) {
  579                 DIRHASH_UNLOCK(dh);
  580                 return (-1);
  581         }
  582 
  583         for (i = dh->dh_dirblks - 1; i >= 0; i--)
  584                 if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
  585                         break;
  586         DIRHASH_UNLOCK(dh);
  587         return ((doff_t)(i + 1) * DIRBLKSIZ);
  588 }
  589 
  590 /*
  591  * Insert information into the hash about a new directory entry. dirp
  592  * points to a struct direct containing the entry, and offset specifies
  593  * the offset of this entry.
  594  */
  595 void
  596 ufsdirhash_add(struct inode *ip, struct direct *dirp, doff_t offset)
  597 {
  598         struct dirhash *dh;
  599         int slot;
  600 
  601         if ((dh = ip->i_dirhash) == NULL)
  602                 return;
  603         DIRHASH_LOCK(dh);
  604         if (dh->dh_hash == NULL) {
  605                 DIRHASH_UNLOCK(dh);
  606                 ufsdirhash_free(ip);
  607                 return;
  608         }
  609 
  610         DIRHASH_ASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
  611             ("ufsdirhash_add: bad offset"));
  612         /*
  613          * Normal hash usage is < 66%. If the usage gets too high then
  614          * remove the hash entirely and let it be rebuilt later.
  615          */
  616         if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
  617                 DIRHASH_UNLOCK(dh);
  618                 ufsdirhash_free(ip);
  619                 return;
  620         }
  621 
  622         /* Find a free hash slot (empty or deleted), and add the entry. */
  623         slot = ufsdirhash_hash(dh, dirp->d_name, dirp->d_namlen);
  624         while (DH_ENTRY(dh, slot) >= 0)
  625                 slot = WRAPINCR(slot, dh->dh_hlen);
  626         if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
  627                 dh->dh_hused++;
  628         DH_ENTRY(dh, slot) = offset;
  629 
  630         /* Update the per-block summary info. */
  631         ufsdirhash_adjfree(dh, offset, -DIRSIZ(0, dirp));
  632         DIRHASH_UNLOCK(dh);
  633 }
  634 
  635 /*
  636  * Remove the specified directory entry from the hash. The entry to remove
  637  * is defined by the name in `dirp', which must exist at the specified
  638  * `offset' within the directory.
  639  */
  640 void
  641 ufsdirhash_remove(struct inode *ip, struct direct *dirp, doff_t offset)
  642 {
  643         struct dirhash *dh;
  644         int slot;
  645 
  646         if ((dh = ip->i_dirhash) == NULL)
  647                 return;
  648         DIRHASH_LOCK(dh);
  649         if (dh->dh_hash == NULL) {
  650                 DIRHASH_UNLOCK(dh);
  651                 ufsdirhash_free(ip);
  652                 return;
  653         }
  654 
  655         DIRHASH_ASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
  656             ("ufsdirhash_remove: bad offset"));
  657         /* Find the entry */
  658         slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, offset);
  659 
  660         /* Remove the hash entry. */
  661         ufsdirhash_delslot(dh, slot);
  662 
  663         /* Update the per-block summary info. */
  664         ufsdirhash_adjfree(dh, offset, DIRSIZ(0, dirp));
  665         DIRHASH_UNLOCK(dh);
  666 }
  667 
  668 /*
  669  * Change the offset associated with a directory entry in the hash. Used
  670  * when compacting directory blocks.
  671  */
  672 void
  673 ufsdirhash_move(struct inode *ip, struct direct *dirp, doff_t oldoff,
  674     doff_t newoff)
  675 {
  676         struct dirhash *dh;
  677         int slot;
  678 
  679         if ((dh = ip->i_dirhash) == NULL)
  680                 return;
  681         DIRHASH_LOCK(dh);
  682         if (dh->dh_hash == NULL) {
  683                 DIRHASH_UNLOCK(dh);
  684                 ufsdirhash_free(ip);
  685                 return;
  686         }
  687 
  688         DIRHASH_ASSERT(oldoff < dh->dh_dirblks * DIRBLKSIZ &&
  689             newoff < dh->dh_dirblks * DIRBLKSIZ,
  690             ("ufsdirhash_move: bad offset"));
  691         /* Find the entry, and update the offset. */
  692         slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, oldoff);
  693         DH_ENTRY(dh, slot) = newoff;
  694         DIRHASH_UNLOCK(dh);
  695 }
  696 
  697 /*
  698  * Inform dirhash that the directory has grown by one block that
  699  * begins at offset (i.e. the new length is offset + DIRBLKSIZ).
  700  */
  701 void
  702 ufsdirhash_newblk(struct inode *ip, doff_t offset)
  703 {
  704         struct dirhash *dh;
  705         int block;
  706 
  707         if ((dh = ip->i_dirhash) == NULL)
  708                 return;
  709         DIRHASH_LOCK(dh);
  710         if (dh->dh_hash == NULL) {
  711                 DIRHASH_UNLOCK(dh);
  712                 ufsdirhash_free(ip);
  713                 return;
  714         }
  715 
  716         DIRHASH_ASSERT(offset == dh->dh_dirblks * DIRBLKSIZ,
  717             ("ufsdirhash_newblk: bad offset"));
  718         block = offset / DIRBLKSIZ;
  719         if (block >= dh->dh_nblk) {
  720                 /* Out of space; must rebuild. */
  721                 DIRHASH_UNLOCK(dh);
  722                 ufsdirhash_free(ip);
  723                 return;
  724         }
  725         dh->dh_dirblks = block + 1;
  726 
  727         /* Account for the new free block. */
  728         dh->dh_blkfree[block] = DIRBLKSIZ / DIRALIGN;
  729         if (dh->dh_firstfree[DH_NFSTATS] == -1)
  730                 dh->dh_firstfree[DH_NFSTATS] = block;
  731         DIRHASH_UNLOCK(dh);
  732 }
  733 
  734 /*
  735  * Inform dirhash that the directory is being truncated.
  736  */
  737 void
  738 ufsdirhash_dirtrunc(struct inode *ip, doff_t offset)
  739 {
  740         struct dirhash *dh;
  741         int block, i;
  742 
  743         if ((dh = ip->i_dirhash) == NULL)
  744                 return;
  745         DIRHASH_LOCK(dh);
  746         if (dh->dh_hash == NULL) {
  747                 DIRHASH_UNLOCK(dh);
  748                 ufsdirhash_free(ip);
  749                 return;
  750         }
  751 
  752         DIRHASH_ASSERT(offset <= dh->dh_dirblks * DIRBLKSIZ,
  753             ("ufsdirhash_dirtrunc: bad offset"));
  754         block = howmany(offset, DIRBLKSIZ);
  755         /*
  756          * If the directory shrinks to less than 1/8 of dh_nblk blocks
  757          * (about 20% of its original size due to the 50% extra added in
  758          * ufsdirhash_build) then free it, and let the caller rebuild
  759          * if necessary.
  760          */
  761         if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
  762                 DIRHASH_UNLOCK(dh);
  763                 ufsdirhash_free(ip);
  764                 return;
  765         }
  766 
  767         /*
  768          * Remove any `first free' information pertaining to the
  769          * truncated blocks. All blocks we're removing should be
  770          * completely unused.
  771          */
  772         if (dh->dh_firstfree[DH_NFSTATS] >= block)
  773                 dh->dh_firstfree[DH_NFSTATS] = -1;
  774         for (i = block; i < dh->dh_dirblks; i++)
  775                 if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
  776                         panic("ufsdirhash_dirtrunc: blocks in use");
  777         for (i = 0; i < DH_NFSTATS; i++)
  778                 if (dh->dh_firstfree[i] >= block)
  779                         panic("ufsdirhash_dirtrunc: first free corrupt");
  780         dh->dh_dirblks = block;
  781         DIRHASH_UNLOCK(dh);
  782 }
  783 
  784 /*
  785  * Debugging function to check that the dirhash information about
  786  * a directory block matches its actual contents. Panics if a mismatch
  787  * is detected.
  788  *
  789  * On entry, `buf' should point to the start of an in-core
  790  * DIRBLKSIZ-sized directory block, and `offset' should contain the
  791  * offset from the start of the directory of that block.
  792  */
  793 void
  794 ufsdirhash_checkblock(struct inode *ip, char *buf, doff_t offset)
  795 {
  796         struct dirhash *dh;
  797         struct direct *dp;
  798         int block, ffslot, i, nfree;
  799 
  800         if (!ufs_dirhashcheck)
  801                 return;
  802         if ((dh = ip->i_dirhash) == NULL)
  803                 return;
  804         DIRHASH_LOCK(dh);
  805         if (dh->dh_hash == NULL) {
  806                 DIRHASH_UNLOCK(dh);
  807                 ufsdirhash_free(ip);
  808                 return;
  809         }
  810 
  811         block = offset / DIRBLKSIZ;
  812         if ((offset & (DIRBLKSIZ - 1)) != 0 || block >= dh->dh_dirblks)
  813                 panic("ufsdirhash_checkblock: bad offset");
  814 
  815         nfree = 0;
  816         for (i = 0; i < DIRBLKSIZ; i += dp->d_reclen) {
  817                 dp = (struct direct *)(buf + i);
  818                 if (dp->d_reclen == 0 || i + dp->d_reclen > DIRBLKSIZ)
  819                         panic("ufsdirhash_checkblock: bad dir");
  820 
  821                 if (dp->d_ino == 0) {
  822 #if 0
  823                         /*
  824                          * XXX entries with d_ino == 0 should only occur
  825                          * at the start of a DIRBLKSIZ block. However the
  826                          * ufs code is tolerant of such entries at other
  827                          * offsets, and fsck does not fix them.
  828                          */
  829                         if (i != 0)
  830                                 panic("ufsdirhash_checkblock: bad dir inode");
  831 #endif
  832                         nfree += dp->d_reclen;
  833                         continue;
  834                 }
  835 
  836                 /* Check that the entry exists (will panic if it doesn't). */
  837                 ufsdirhash_findslot(dh, dp->d_name, dp->d_namlen, offset + i);
  838 
  839                 nfree += dp->d_reclen - DIRSIZ(0, dp);
  840         }
  841         if (i != DIRBLKSIZ)
  842                 panic("ufsdirhash_checkblock: bad dir end");
  843 
  844         if (dh->dh_blkfree[block] * DIRALIGN != nfree)
  845                 panic("ufsdirhash_checkblock: bad free count");
  846 
  847         ffslot = BLKFREE2IDX(nfree / DIRALIGN);
  848         for (i = 0; i <= DH_NFSTATS; i++)
  849                 if (dh->dh_firstfree[i] == block && i != ffslot)
  850                         panic("ufsdirhash_checkblock: bad first-free");
  851         if (dh->dh_firstfree[ffslot] == -1)
  852                 panic("ufsdirhash_checkblock: missing first-free entry");
  853         DIRHASH_UNLOCK(dh);
  854 }
  855 
  856 /*
  857  * Hash the specified filename into a dirhash slot.
  858  */
  859 int
  860 ufsdirhash_hash(struct dirhash *dh, char *name, int namelen)
  861 {
  862         u_int32_t hash;
  863 
  864         /*
  865          * We hash the name and then some other bit of data that is
  866          * invariant over the dirhash's lifetime. Otherwise names
  867          * differing only in the last byte are placed close to one
  868          * another in the table, which is bad for linear probing.
  869          */
  870         hash = hash32_buf(name, namelen, HASHINIT);
  871         hash = hash32_buf(&dh, sizeof(dh), hash);
  872         return (hash % dh->dh_hlen);
  873 }
  874 
  875 /*
  876  * Adjust the number of free bytes in the block containing `offset'
  877  * by the value specified by `diff'.
  878  *
  879  * The caller must ensure we have exclusive access to `dh'; normally
  880  * that means that dh_mtx should be held, but this is also called
  881  * from ufsdirhash_build() where exclusive access can be assumed.
  882  */
  883 void
  884 ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff)
  885 {
  886         int block, i, nfidx, ofidx;
  887 
  888         /* Update the per-block summary info. */
  889         block = offset / DIRBLKSIZ;
  890         DIRHASH_ASSERT(block < dh->dh_nblk && block < dh->dh_dirblks,
  891              ("dirhash bad offset"));
  892         ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
  893         dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
  894         nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
  895 
  896         /* Update the `first free' list if necessary. */
  897         if (ofidx != nfidx) {
  898                 /* If removing, scan forward for the next block. */
  899                 if (dh->dh_firstfree[ofidx] == block) {
  900                         for (i = block + 1; i < dh->dh_dirblks; i++)
  901                                 if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
  902                                         break;
  903                         dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
  904                 }
  905 
  906                 /* Make this the new `first free' if necessary */
  907                 if (dh->dh_firstfree[nfidx] > block ||
  908                     dh->dh_firstfree[nfidx] == -1)
  909                         dh->dh_firstfree[nfidx] = block;
  910         }
  911 }
  912 
  913 /*
  914  * Find the specified name which should have the specified offset.
  915  * Returns a slot number, and panics on failure.
  916  *
  917  * `dh' must be locked on entry and remains so on return.
  918  */
  919 int
  920 ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen, doff_t offset)
  921 {
  922         int slot;
  923 
  924         mtx_assert(&dh->dh_mtx, MA_OWNED);
  925 
  926         /* Find the entry. */
  927         DIRHASH_ASSERT(dh->dh_hused < dh->dh_hlen, ("dirhash find full"));
  928         slot = ufsdirhash_hash(dh, name, namelen);
  929         while (DH_ENTRY(dh, slot) != offset &&
  930             DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
  931                 slot = WRAPINCR(slot, dh->dh_hlen);
  932         if (DH_ENTRY(dh, slot) != offset)
  933                 panic("ufsdirhash_findslot: '%.*s' not found", namelen, name);
  934 
  935         return (slot);
  936 }
  937 
  938 /*
  939  * Remove the entry corresponding to the specified slot from the hash array.
  940  *
  941  * `dh' must be locked on entry and remains so on return.
  942  */
  943 void
  944 ufsdirhash_delslot(struct dirhash *dh, int slot)
  945 {
  946         int i;
  947 
  948         mtx_assert(&dh->dh_mtx, MA_OWNED);
  949 
  950         /* Mark the entry as deleted. */
  951         DH_ENTRY(dh, slot) = DIRHASH_DEL;
  952 
  953         /* If this is the end of a chain of DIRHASH_DEL slots, remove them. */
  954         for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
  955                 i = WRAPINCR(i, dh->dh_hlen);
  956         if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
  957                 i = WRAPDECR(i, dh->dh_hlen);
  958                 while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
  959                         DH_ENTRY(dh, i) = DIRHASH_EMPTY;
  960                         dh->dh_hused--;
  961                         i = WRAPDECR(i, dh->dh_hlen);
  962                 }
  963                 DIRHASH_ASSERT(dh->dh_hused >= 0, ("ufsdirhash_delslot neg hlen"));
  964         }
  965 }
  966 
  967 /*
  968  * Given a directory entry and its offset, find the offset of the
  969  * previous entry in the same DIRBLKSIZ-sized block. Returns an
  970  * offset, or -1 if there is no previous entry in the block or some
  971  * other problem occurred.
  972  */
  973 doff_t
  974 ufsdirhash_getprev(struct direct *dirp, doff_t offset)
  975 {
  976         struct direct *dp;
  977         char *blkbuf;
  978         doff_t blkoff, prevoff;
  979         int entrypos, i;
  980 
  981         blkoff = offset & ~(DIRBLKSIZ - 1);     /* offset of start of block */
  982         entrypos = offset & (DIRBLKSIZ - 1);    /* entry relative to block */
  983         blkbuf = (char *)dirp - entrypos;
  984         prevoff = blkoff;
  985 
  986         /* If `offset' is the start of a block, there is no previous entry. */
  987         if (entrypos == 0)
  988                 return (-1);
  989 
  990         /* Scan from the start of the block until we get to the entry. */
  991         for (i = 0; i < entrypos; i += dp->d_reclen) {
  992                 dp = (struct direct *)(blkbuf + i);
  993                 if (dp->d_reclen == 0 || i + dp->d_reclen > entrypos)
  994                         return (-1);    /* Corrupted directory. */
  995                 prevoff = blkoff + i;
  996         }
  997         return (prevoff);
  998 }
  999 
 1000 /*
 1001  * Try to free up `wanted' bytes by stealing memory from existing
 1002  * dirhashes. Returns zero with list locked if successful.
 1003  */
 1004 int
 1005 ufsdirhash_recycle(int wanted)
 1006 {
 1007         struct dirhash *dh;
 1008         doff_t **hash;
 1009         u_int8_t *blkfree;
 1010         int i, mem, narrays;
 1011 
 1012         DIRHASHLIST_LOCK();
 1013         while (wanted + ufs_dirhashmem > ufs_dirhashmaxmem) {
 1014                 /* Find a dirhash, and lock it. */
 1015                 if ((dh = TAILQ_FIRST(&ufsdirhash_list)) == NULL) {
 1016                         DIRHASHLIST_UNLOCK();
 1017                         return (-1);
 1018                 }
 1019                 DIRHASH_LOCK(dh);
 1020                 DIRHASH_ASSERT(dh->dh_hash != NULL, ("dirhash: NULL hash on list"));
 1021 
 1022                 /* Decrement the score; only recycle if it becomes zero. */
 1023                 if (--dh->dh_score > 0) {
 1024                         DIRHASH_UNLOCK(dh);
 1025                         DIRHASHLIST_UNLOCK();
 1026                         return (-1);
 1027                 }
 1028 
 1029                 /* Remove it from the list and detach its memory. */
 1030                 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
 1031                 dh->dh_onlist = 0;
 1032                 hash = dh->dh_hash;
 1033                 dh->dh_hash = NULL;
 1034                 blkfree = dh->dh_blkfree;
 1035                 dh->dh_blkfree = NULL;
 1036                 narrays = dh->dh_narrays;
 1037                 mem = narrays * sizeof(*dh->dh_hash) +
 1038                     narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
 1039                     dh->dh_nblk * sizeof(*dh->dh_blkfree);
 1040 
 1041                 /* Unlock everything, free the detached memory. */
 1042                 DIRHASH_UNLOCK(dh);
 1043                 DIRHASHLIST_UNLOCK();
 1044                 for (i = 0; i < narrays; i++)
 1045                         DIRHASH_BLKFREE(hash[i]);
 1046                 free(hash, M_DIRHASH);
 1047                 free(blkfree, M_DIRHASH);
 1048 
 1049                 /* Account for the returned memory, and repeat if necessary. */
 1050                 DIRHASHLIST_LOCK();
 1051                 ufs_dirhashmem -= mem;
 1052         }
 1053         /* Success; return with list locked. */
 1054         return (0);
 1055 }
 1056 
 1057 
 1058 void
 1059 ufsdirhash_init()
 1060 {
 1061         pool_init(&ufsdirhash_pool, DH_NBLKOFF * sizeof(doff_t), 0, 0, 0,
 1062             "dirhash", &pool_allocator_nointr);
 1063         pool_sethiwat(&ufsdirhash_pool, 512);
 1064         TAILQ_INIT(&ufsdirhash_list);
 1065 #if defined (__sparc__) && !defined (__sparc64__)
 1066         if (!CPU_ISSUN4OR4C)
 1067 #elif defined (__vax__)
 1068         if (0)
 1069 #endif
 1070                 ufs_dirhashmaxmem = 2 * 1024 * 1024;
 1071         ufs_mindirhashsize = 5 * DIRBLKSIZ;
 1072 }
 1073 
 1074 void
 1075 ufsdirhash_uninit()
 1076 {
 1077         DIRHASH_ASSERT(TAILQ_EMPTY(&ufsdirhash_list), ("ufsdirhash_uninit"));
 1078         pool_destroy(&ufsdirhash_pool);
 1079 }
/* [<][>][^][v][top][bottom][index][help] */
root/ufs/ufs/ufs_dirhash.c

DEFINITIONS
