sys/ufs/ufs/ufs_dirhash.c

   1 /*-
   2  * Copyright (c) 2001, 2002 Ian Dowse.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 /*
  27  * This implements a hash-based lookup scheme for UFS directories.
  28  */
  29
  30 #include <sys/cdefs.h>
  31 __FBSDID("$FreeBSD$");
  32
  33 #include "opt_ufs.h"
  34
  35 #ifdef UFS_DIRHASH
  36
  37 #include <sys/param.h>
  38 #include <sys/systm.h>
  39 #include <sys/kernel.h>
  40 #include <sys/lock.h>
  41 #include <sys/mutex.h>
  42 #include <sys/malloc.h>
  43 #include <sys/fnv_hash.h>
  44 #include <sys/proc.h>
  45 #include <sys/bio.h>
  46 #include <sys/buf.h>
  47 #include <sys/vnode.h>
  48 #include <sys/mount.h>
  49 #include <sys/refcount.h>
  50 #include <sys/sysctl.h>
  51 #include <sys/sx.h>
  52 #include <sys/eventhandler.h>
  53 #include <sys/time.h>
  54 #include <vm/uma.h>
  55
  56 #include <ufs/ufs/quota.h>
  57 #include <ufs/ufs/inode.h>
  58 #include <ufs/ufs/dir.h>
  59 #include <ufs/ufs/dirhash.h>
  60 #include <ufs/ufs/extattr.h>
  61 #include <ufs/ufs/ufsmount.h>
  62 #include <ufs/ufs/ufs_extern.h>
  63
  64 #define WRAPINCR(val, limit)    (((val) + 1 == (limit)) ? 0 : ((val) + 1))
  65 #define WRAPDECR(val, limit)    (((val) == 0) ? ((limit) - 1) : ((val) - 1))
  66 #define OFSFMT(vp)              ((vp)->v_mount->mnt_maxsymlinklen <= 0)
  67 #define BLKFREE2IDX(n)          ((n) > DH_NFSTATS ? DH_NFSTATS : (n))
  68
  69 static MALLOC_DEFINE(M_DIRHASH, "ufs_dirhash", "UFS directory hash tables");
  70
  71 static int ufs_mindirhashsize = DIRBLKSIZ * 5;
  72 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_minsize, CTLFLAG_RW,
  73     &ufs_mindirhashsize,
  74     0, "minimum directory size in bytes for which to use hashed lookup");
  75 static int ufs_dirhashmaxmem = 2 * 1024 * 1024; /* NOTE: initial value. It is
  76                                                    tuned in ufsdirhash_init() */
  77 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_maxmem, CTLFLAG_RW, &ufs_dirhashmaxmem,
  78     0, "maximum allowed dirhash memory usage");
  79 static int ufs_dirhashmem;
  80 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_mem, CTLFLAG_RD, &ufs_dirhashmem,
  81     0, "current dirhash memory usage");
  82 static int ufs_dirhashcheck = 0;
  83 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_docheck, CTLFLAG_RW, &ufs_dirhashcheck,
  84     0, "enable extra sanity tests");
  85 static int ufs_dirhashlowmemcount = 0;
  86 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_lowmemcount, CTLFLAG_RD,
  87     &ufs_dirhashlowmemcount, 0, "number of times low memory hook called");
  88 static int ufs_dirhashreclaimage = 60;
  89 SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_reclaimage, CTLFLAG_RW,
  90     &ufs_dirhashreclaimage, 0,
  91     "max time in seconds of hash inactivity before deletion in low VM events");
  92
  93
  94 static int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen);
  95 static void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff);
  96 static void ufsdirhash_delslot(struct dirhash *dh, int slot);
  97 static int ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen,
  98            doff_t offset);
  99 static doff_t ufsdirhash_getprev(struct direct *dp, doff_t offset);
 100 static int ufsdirhash_recycle(int wanted);
 101 static void ufsdirhash_lowmem(void);
 102 static void ufsdirhash_free_locked(struct inode *ip);
 103
 104 static uma_zone_t       ufsdirhash_zone;
 105
 106 #define DIRHASHLIST_LOCK()              mtx_lock(&ufsdirhash_mtx)
 107 #define DIRHASHLIST_UNLOCK()            mtx_unlock(&ufsdirhash_mtx)
 108 #define DIRHASH_BLKALLOC_WAITOK()       uma_zalloc(ufsdirhash_zone, M_WAITOK)
 109 #define DIRHASH_BLKFREE(ptr)            uma_zfree(ufsdirhash_zone, (ptr))
 110 #define DIRHASH_ASSERT_LOCKED(dh)                                       \
 111     sx_assert(&(dh)->dh_lock, SA_LOCKED)
 112
 113 /* Dirhash list; recently-used entries are near the tail. */
 114 static TAILQ_HEAD(, dirhash) ufsdirhash_list;
 115
 116 /* Protects: ufsdirhash_list, `dh_list' field, ufs_dirhashmem. */
 117 static struct mtx       ufsdirhash_mtx;
 118
 119 /*
 120  * Locking:
 121  *
 122  * The relationship between inode and dirhash is protected either by an
 123  * exclusive vnode lock or the vnode interlock where a shared vnode lock
 124  * may be used.  The dirhash_mtx is acquired after the dirhash lock.  To
 125  * handle teardown races, code wishing to lock the dirhash for an inode
 126  * when using a shared vnode lock must obtain a private reference on the
 127  * dirhash while holding the vnode interlock.  They can drop it once they
 128  * have obtained the dirhash lock and verified that the dirhash wasn't
 129  * recycled while they waited for the dirhash lock.
 130  *
 131  * ufsdirhash_build() acquires a shared lock on the dirhash when it is
 132  * successful.  This lock is released after a call to ufsdirhash_lookup().
 133  *
 134  * Functions requiring exclusive access use ufsdirhash_acquire() which may
 135  * free a dirhash structure that was recycled by ufsdirhash_recycle().
 136  *
 137  * The dirhash lock may be held across io operations.
 138  *
 139  * WITNESS reports a lock order reversal between the "bufwait" lock
 140  * and the "dirhash" lock.  However, this specific reversal will not
 141  * cause a deadlock.  To get a deadlock, one would have to lock a
 142  * buffer followed by the dirhash while a second thread locked a
 143  * buffer while holding the dirhash lock.  The second order can happen
 144  * under a shared or exclusive vnode lock for the associated directory
 145  * in lookup().  The first order, however, can only happen under an
 146  * exclusive vnode lock (e.g. unlink(), rename(), etc.).  Thus, for
 147  * a thread to be doing a "bufwait" -> "dirhash" order, it has to hold
 148  * an exclusive vnode lock.  That exclusive vnode lock will prevent
 149  * any other threads from doing a "dirhash" -> "bufwait" order.
 150  */
 151
 152 static void
 153 ufsdirhash_hold(struct dirhash *dh)
 154 {
 155
 156         refcount_acquire(&dh->dh_refcount);
 157 }
 158
 159 static void
 160 ufsdirhash_drop(struct dirhash *dh)
 161 {
 162
 163         if (refcount_release(&dh->dh_refcount)) {
 164                 sx_destroy(&dh->dh_lock);
 165                 free(dh, M_DIRHASH);
 166         }
 167 }
 168
 169 /*
 170  * Release the lock on a dirhash.
 171  */
 172 static void
 173 ufsdirhash_release(struct dirhash *dh)
 174 {
 175
 176         sx_unlock(&dh->dh_lock);
 177 }
 178
 179 /*
 180  * Either acquire an existing hash locked shared or create a new hash and
 181  * return it exclusively locked.  May return NULL if the allocation fails.
 182  *
 183  * The vnode interlock is used to protect the i_dirhash pointer from
 184  * simultaneous access while only a shared vnode lock is held.
 185  */
 186 static struct dirhash *
 187 ufsdirhash_create(struct inode *ip)
 188 {
 189         struct dirhash *ndh;
 190         struct dirhash *dh;
 191         struct vnode *vp;
 192         bool excl;
 193
 194         ndh = dh = NULL;
 195         vp = ip->i_vnode;
 196         excl = false;
 197         for (;;) {
 198                 /* Racy check for i_dirhash to prefetch a dirhash structure. */
 199                 if (ip->i_dirhash == NULL && ndh == NULL) {
 200                         ndh = malloc(sizeof *dh, M_DIRHASH,
 201                             M_NOWAIT | M_ZERO);
 202                         if (ndh == NULL)
 203                                 return (NULL);
 204                         refcount_init(&ndh->dh_refcount, 1);
 205
 206                         /*
 207                          * The DUPOK is to prevent warnings from the
 208                          * sx_slock() a few lines down which is safe
 209                          * since the duplicate lock in that case is
 210                          * the one for this dirhash we are creating
 211                          * now which has no external references until
 212                          * after this function returns.
 213                          */
 214                         sx_init_flags(&ndh->dh_lock, "dirhash", SX_DUPOK);
 215                         sx_xlock(&ndh->dh_lock);
 216                 }
 217                 /*
 218                  * Check i_dirhash.  If it's NULL just try to use a
 219                  * preallocated structure.  If none exists loop and try again.
 220                  */
 221                 VI_LOCK(vp);
 222                 dh = ip->i_dirhash;
 223                 if (dh == NULL) {
 224                         ip->i_dirhash = ndh;
 225                         VI_UNLOCK(vp);
 226                         if (ndh == NULL)
 227                                 continue;
 228                         return (ndh);
 229                 }
 230                 ufsdirhash_hold(dh);
 231                 VI_UNLOCK(vp);
 232
 233                 /* Acquire a lock on existing hashes. */
 234                 if (excl)
 235                         sx_xlock(&dh->dh_lock);
 236                 else
 237                         sx_slock(&dh->dh_lock);
 238
 239                 /* The hash could've been recycled while we were waiting. */
 240                 VI_LOCK(vp);
 241                 if (ip->i_dirhash != dh) {
 242                         VI_UNLOCK(vp);
 243                         ufsdirhash_release(dh);
 244                         ufsdirhash_drop(dh);
 245                         continue;
 246                 }
 247                 VI_UNLOCK(vp);
 248                 ufsdirhash_drop(dh);
 249
 250                 /* If the hash is still valid we've succeeded. */
 251                 if (dh->dh_hash != NULL)
 252                         break;
 253                 /*
 254                  * If the hash is NULL it has been recycled.  Try to upgrade
 255                  * so we can recreate it.  If we fail the upgrade, drop our
 256                  * lock and try again.
 257                  */
 258                 if (excl || sx_try_upgrade(&dh->dh_lock))
 259                         break;
 260                 sx_sunlock(&dh->dh_lock);
 261                 excl = true;
 262         }
 263         /* Free the preallocated structure if it was not necessary. */
 264         if (ndh) {
 265                 ufsdirhash_release(ndh);
 266                 ufsdirhash_drop(ndh);
 267         }
 268         return (dh);
 269 }
 270
 271 /*
 272  * Acquire an exclusive lock on an existing hash.  Requires an exclusive
 273  * vnode lock to protect the i_dirhash pointer.  hashes that have been
 274  * recycled are reclaimed here and NULL is returned.
 275  */
 276 static struct dirhash *
 277 ufsdirhash_acquire(struct inode *ip)
 278 {
 279         struct dirhash *dh;
 280
 281         ASSERT_VOP_ELOCKED(ip->i_vnode, __FUNCTION__);
 282
 283         dh = ip->i_dirhash;
 284         if (dh == NULL)
 285                 return (NULL);
 286         sx_xlock(&dh->dh_lock);
 287         if (dh->dh_hash != NULL)
 288                 return (dh);
 289         ufsdirhash_free_locked(ip);
 290         return (NULL);
 291 }
 292
 293 /*
 294  * Acquire exclusively and free the hash pointed to by ip.  Works with a
 295  * shared or exclusive vnode lock.
 296  */
 297 void
 298 ufsdirhash_free(struct inode *ip)
 299 {
 300         struct dirhash *dh;
 301         struct vnode *vp;
 302
 303         vp = ip->i_vnode;
 304         for (;;) {
 305                 /* Grab a reference on this inode's dirhash if it has one. */
 306                 VI_LOCK(vp);
 307                 dh = ip->i_dirhash;
 308                 if (dh == NULL) {
 309                         VI_UNLOCK(vp);
 310                         return;
 311                 }
 312                 ufsdirhash_hold(dh);
 313                 VI_UNLOCK(vp);
 314
 315                 /* Exclusively lock the dirhash. */
 316                 sx_xlock(&dh->dh_lock);
 317
 318                 /* If this dirhash still belongs to this inode, then free it. */
 319                 VI_LOCK(vp);
 320                 if (ip->i_dirhash == dh) {
 321                         VI_UNLOCK(vp);
 322                         ufsdirhash_drop(dh);
 323                         break;
 324                 }
 325                 VI_UNLOCK(vp);
 326
 327                 /*
 328                  * This inode's dirhash has changed while we were
 329                  * waiting for the dirhash lock, so try again.
 330                  */
 331                 ufsdirhash_release(dh);
 332                 ufsdirhash_drop(dh);
 333         }
 334         ufsdirhash_free_locked(ip);
 335 }
 336
 337 /*
 338  * Attempt to build up a hash table for the directory contents in
 339  * inode 'ip'. Returns 0 on success, or -1 of the operation failed.
 340  */
 341 int
 342 ufsdirhash_build(struct inode *ip)
 343 {
 344         struct dirhash *dh;
 345         struct buf *bp = NULL;
 346         struct direct *ep;
 347         struct vnode *vp;
 348         doff_t bmask, pos;
 349         int dirblocks, i, j, memreqd, nblocks, narrays, nslots, slot;
 350
 351         /* Take care of a decreased sysctl value. */
 352         while (ufs_dirhashmem > ufs_dirhashmaxmem) {
 353                 if (ufsdirhash_recycle(0) != 0)
 354                         return (-1);
 355                 /* Recycled enough memory, so unlock the list. */
 356                 DIRHASHLIST_UNLOCK();
 357         }
 358
 359         /* Check if we can/should use dirhash. */
 360         if (ip->i_size < ufs_mindirhashsize || OFSFMT(ip->i_vnode) ||
 361             ip->i_effnlink == 0) {
 362                 if (ip->i_dirhash)
 363                         ufsdirhash_free(ip);
 364                 return (-1);
 365         }
 366         dh = ufsdirhash_create(ip);
 367         if (dh == NULL)
 368                 return (-1);
 369         if (dh->dh_hash != NULL)
 370                 return (0);
 371
 372         vp = ip->i_vnode;
 373         /* Allocate 50% more entries than this dir size could ever need. */
 374         KASSERT(ip->i_size >= DIRBLKSIZ, ("ufsdirhash_build size"));
 375         nslots = ip->i_size / DIRECTSIZ(1);
 376         nslots = (nslots * 3 + 1) / 2;
 377         narrays = howmany(nslots, DH_NBLKOFF);
 378         nslots = narrays * DH_NBLKOFF;
 379         dirblocks = howmany(ip->i_size, DIRBLKSIZ);
 380         nblocks = (dirblocks * 3 + 1) / 2;
 381         memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
 382             narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
 383             nblocks * sizeof(*dh->dh_blkfree);
 384         DIRHASHLIST_LOCK();
 385         if (memreqd + ufs_dirhashmem > ufs_dirhashmaxmem) {
 386                 DIRHASHLIST_UNLOCK();
 387                 if (memreqd > ufs_dirhashmaxmem / 2)
 388                         goto fail;
 389                 /* Try to free some space. */
 390                 if (ufsdirhash_recycle(memreqd) != 0)
 391                         goto fail;
 392                 /* Enough was freed, and list has been locked. */
 393         }
 394         ufs_dirhashmem += memreqd;
 395         DIRHASHLIST_UNLOCK();
 396
 397         /* Initialise the hash table and block statistics. */
 398         dh->dh_memreq = memreqd;
 399         dh->dh_narrays = narrays;
 400         dh->dh_hlen = nslots;
 401         dh->dh_nblk = nblocks;
 402         dh->dh_dirblks = dirblocks;
 403         for (i = 0; i < DH_NFSTATS; i++)
 404                 dh->dh_firstfree[i] = -1;
 405         dh->dh_firstfree[DH_NFSTATS] = 0;
 406         dh->dh_hused = 0;
 407         dh->dh_seqoff = -1;
 408         dh->dh_score = DH_SCOREINIT;
 409         dh->dh_lastused = time_second;
 410
 411         /*
 412          * Use non-blocking mallocs so that we will revert to a linear
 413          * lookup on failure rather than potentially blocking forever.
 414          */
 415         dh->dh_hash = malloc(narrays * sizeof(dh->dh_hash[0]),
 416             M_DIRHASH, M_NOWAIT | M_ZERO);
 417         if (dh->dh_hash == NULL)
 418                 goto fail;
 419         dh->dh_blkfree = malloc(nblocks * sizeof(dh->dh_blkfree[0]),
 420             M_DIRHASH, M_NOWAIT);
 421         if (dh->dh_blkfree == NULL)
 422                 goto fail;
 423         for (i = 0; i < narrays; i++) {
 424                 if ((dh->dh_hash[i] = DIRHASH_BLKALLOC_WAITOK()) == NULL)
 425                         goto fail;
 426                 for (j = 0; j < DH_NBLKOFF; j++)
 427                         dh->dh_hash[i][j] = DIRHASH_EMPTY;
 428         }
 429         for (i = 0; i < dirblocks; i++)
 430                 dh->dh_blkfree[i] = DIRBLKSIZ / DIRALIGN;
 431         bmask = vp->v_mount->mnt_stat.f_iosize - 1;
 432         pos = 0;
 433         while (pos < ip->i_size) {
 434                 /* If necessary, get the next directory block. */
 435                 if ((pos & bmask) == 0) {
 436                         if (bp != NULL)
 437                                 brelse(bp);
 438                         if (UFS_BLKATOFF(vp, (off_t)pos, NULL, &bp) != 0)
 439                                 goto fail;
 440                 }
 441
 442                 /* Add this entry to the hash. */
 443                 ep = (struct direct *)((char *)bp->b_data + (pos & bmask));
 444                 if (ep->d_reclen == 0 || ep->d_reclen >
 445                     DIRBLKSIZ - (pos & (DIRBLKSIZ - 1))) {
 446                         /* Corrupted directory. */
 447                         brelse(bp);
 448                         goto fail;
 449                 }
 450                 if (ep->d_ino != 0) {
 451                         /* Add the entry (simplified ufsdirhash_add). */
 452                         slot = ufsdirhash_hash(dh, ep->d_name, ep->d_namlen);
 453                         while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
 454                                 slot = WRAPINCR(slot, dh->dh_hlen);
 455                         dh->dh_hused++;
 456                         DH_ENTRY(dh, slot) = pos;
 457                         ufsdirhash_adjfree(dh, pos, -DIRSIZ(0, ep));
 458                 }
 459                 pos += ep->d_reclen;
 460         }
 461
 462         if (bp != NULL)
 463                 brelse(bp);
 464         DIRHASHLIST_LOCK();
 465         TAILQ_INSERT_TAIL(&ufsdirhash_list, dh, dh_list);
 466         dh->dh_onlist = 1;
 467         DIRHASHLIST_UNLOCK();
 468         sx_downgrade(&dh->dh_lock);
 469         return (0);
 470
 471 fail:
 472         ufsdirhash_free_locked(ip);
 473         return (-1);
 474 }
 475
 476 /*
 477  * Free any hash table associated with inode 'ip'.
 478  */
 479 static void
 480 ufsdirhash_free_locked(struct inode *ip)
 481 {
 482         struct dirhash *dh;
 483         struct vnode *vp;
 484         int i;
 485
 486         DIRHASH_ASSERT_LOCKED(ip->i_dirhash);
 487
 488         /*
 489          * Clear the pointer in the inode to prevent new threads from
 490          * finding the dead structure.
 491          */
 492         vp = ip->i_vnode;
 493         VI_LOCK(vp);
 494         dh = ip->i_dirhash;
 495         ip->i_dirhash = NULL;
 496         VI_UNLOCK(vp);
 497
 498         /*
 499          * Remove the hash from the list since we are going to free its
 500          * memory.
 501          */
 502         DIRHASHLIST_LOCK();
 503         if (dh->dh_onlist)
 504                 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
 505         ufs_dirhashmem -= dh->dh_memreq;
 506         DIRHASHLIST_UNLOCK();
 507
 508         /*
 509          * At this point, any waiters for the lock should hold their
 510          * own reference on the dirhash structure.  They will drop
 511          * that reference once they grab the vnode interlock and see
 512          * that ip->i_dirhash is NULL.
 513          */
 514         sx_xunlock(&dh->dh_lock);
 515
 516         /*
 517          * Handle partially recycled as well as fully constructed hashes.
 518          */
 519         if (dh->dh_hash != NULL) {
 520                 for (i = 0; i < dh->dh_narrays; i++)
 521                         if (dh->dh_hash[i] != NULL)
 522                                 DIRHASH_BLKFREE(dh->dh_hash[i]);
 523                 free(dh->dh_hash, M_DIRHASH);
 524                 if (dh->dh_blkfree != NULL)
 525                         free(dh->dh_blkfree, M_DIRHASH);
 526         }
 527
 528         /*
 529          * Drop the inode's reference to the data structure.
 530          */
 531         ufsdirhash_drop(dh);
 532 }
 533
 534 /*
 535  * Find the offset of the specified name within the given inode.
 536  * Returns 0 on success, ENOENT if the entry does not exist, or
 537  * EJUSTRETURN if the caller should revert to a linear search.
 538  *
 539  * If successful, the directory offset is stored in *offp, and a
 540  * pointer to a struct buf containing the entry is stored in *bpp. If
 541  * prevoffp is non-NULL, the offset of the previous entry within
 542  * the DIRBLKSIZ-sized block is stored in *prevoffp (if the entry
 543  * is the first in a block, the start of the block is used).
 544  *
 545  * Must be called with the hash locked.  Returns with the hash unlocked.
 546  */
 547 int
 548 ufsdirhash_lookup(struct inode *ip, char *name, int namelen, doff_t *offp,
 549     struct buf **bpp, doff_t *prevoffp)
 550 {
 551         struct dirhash *dh, *dh_next;
 552         struct direct *dp;
 553         struct vnode *vp;
 554         struct buf *bp;
 555         doff_t blkoff, bmask, offset, prevoff, seqoff;
 556         int i, slot;
 557         int error;
 558
 559         dh = ip->i_dirhash;
 560         KASSERT(dh != NULL && dh->dh_hash != NULL,
 561             ("ufsdirhash_lookup: Invalid dirhash %p\n", dh));
 562         DIRHASH_ASSERT_LOCKED(dh);
 563         /*
 564          * Move this dirhash towards the end of the list if it has a
 565          * score higher than the next entry, and acquire the dh_lock.
 566          */
 567         DIRHASHLIST_LOCK();
 568         if (TAILQ_NEXT(dh, dh_list) != NULL) {
 569                 /*
 570                  * If the new score will be greater than that of the next
 571                  * entry, then move this entry past it. With both mutexes
 572                  * held, dh_next won't go away, but its dh_score could
 573                  * change; that's not important since it is just a hint.
 574                  */
 575                 if ((dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
 576                     dh->dh_score >= dh_next->dh_score) {
 577                         KASSERT(dh->dh_onlist, ("dirhash: not on list"));
 578                         TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
 579                         TAILQ_INSERT_AFTER(&ufsdirhash_list, dh_next, dh,
 580                             dh_list);
 581                 }
 582         }
 583         /* Update the score. */
 584         if (dh->dh_score < DH_SCOREMAX)
 585                 dh->dh_score++;
 586
 587         /* Update last used time. */
 588         dh->dh_lastused = time_second;
 589         DIRHASHLIST_UNLOCK();
 590
 591         vp = ip->i_vnode;
 592         bmask = vp->v_mount->mnt_stat.f_iosize - 1;
 593         blkoff = -1;
 594         bp = NULL;
 595         seqoff = dh->dh_seqoff;
 596 restart:
 597         slot = ufsdirhash_hash(dh, name, namelen);
 598
 599         if (seqoff != -1) {
 600                 /*
 601                  * Sequential access optimisation. seqoff contains the
 602                  * offset of the directory entry immediately following
 603                  * the last entry that was looked up. Check if this offset
 604                  * appears in the hash chain for the name we are looking for.
 605                  */
 606                 for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
 607                     i = WRAPINCR(i, dh->dh_hlen))
 608                         if (offset == seqoff)
 609                                 break;
 610                 if (offset == seqoff) {
 611                         /*
 612                          * We found an entry with the expected offset. This
 613                          * is probably the entry we want, but if not, the
 614                          * code below will retry.
 615                          */
 616                         slot = i;
 617                 } else
 618                         seqoff = -1;
 619         }
 620
 621         for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
 622             slot = WRAPINCR(slot, dh->dh_hlen)) {
 623                 if (offset == DIRHASH_DEL)
 624                         continue;
 625                 if (offset < 0 || offset >= ip->i_size)
 626                         panic("ufsdirhash_lookup: bad offset in hash array");
 627                 if ((offset & ~bmask) != blkoff) {
 628                         if (bp != NULL)
 629                                 brelse(bp);
 630                         blkoff = offset & ~bmask;
 631                         if (UFS_BLKATOFF(vp, (off_t)blkoff, NULL, &bp) != 0) {
 632                                 error = EJUSTRETURN;
 633                                 goto fail;
 634                         }
 635                 }
 636                 KASSERT(bp != NULL, ("no buffer allocated"));
 637                 dp = (struct direct *)(bp->b_data + (offset & bmask));
 638                 if (dp->d_reclen == 0 || dp->d_reclen >
 639                     DIRBLKSIZ - (offset & (DIRBLKSIZ - 1))) {
 640                         /* Corrupted directory. */
 641                         error = EJUSTRETURN;
 642                         goto fail;
 643                 }
 644                 if (dp->d_namlen == namelen &&
 645                     bcmp(dp->d_name, name, namelen) == 0) {
 646                         /* Found. Get the prev offset if needed. */
 647                         if (prevoffp != NULL) {
 648                                 if (offset & (DIRBLKSIZ - 1)) {
 649                                         prevoff = ufsdirhash_getprev(dp,
 650                                             offset);
 651                                         if (prevoff == -1) {
 652                                                 error = EJUSTRETURN;
 653                                                 goto fail;
 654                                         }
 655                                 } else
 656                                         prevoff = offset;
 657                                 *prevoffp = prevoff;
 658                         }
 659
 660                         /* Update offset. */
 661                         dh->dh_seqoff = offset + DIRSIZ(0, dp);
 662                         *bpp = bp;
 663                         *offp = offset;
 664                         ufsdirhash_release(dh);
 665                         return (0);
 666                 }
 667
 668                 /*
 669                  * When the name doesn't match in the sequential
 670                  * optimization case, go back and search normally.
 671                  */
 672                 if (seqoff != -1) {
 673                         seqoff = -1;
 674                         goto restart;
 675                 }
 676         }
 677         error = ENOENT;
 678 fail:
 679         ufsdirhash_release(dh);
 680         if (bp != NULL)
 681                 brelse(bp);
 682         return (error);
 683 }
 684
 685 /*
 686  * Find a directory block with room for 'slotneeded' bytes. Returns
 687  * the offset of the directory entry that begins the free space.
 688  * This will either be the offset of an existing entry that has free
 689  * space at the end, or the offset of an entry with d_ino == 0 at
 690  * the start of a DIRBLKSIZ block.
 691  *
 692  * To use the space, the caller may need to compact existing entries in
 693  * the directory. The total number of bytes in all of the entries involved
 694  * in the compaction is stored in *slotsize. In other words, all of
 695  * the entries that must be compacted are exactly contained in the
 696  * region beginning at the returned offset and spanning *slotsize bytes.
 697  *
 698  * Returns -1 if no space was found, indicating that the directory
 699  * must be extended.
 700  */
 701 doff_t
 702 ufsdirhash_findfree(struct inode *ip, int slotneeded, int *slotsize)
 703 {
 704         struct direct *dp;
 705         struct dirhash *dh;
 706         struct buf *bp;
 707         doff_t pos, slotstart;
 708         int dirblock, error, freebytes, i;
 709
 710         dh = ip->i_dirhash;
 711         KASSERT(dh != NULL && dh->dh_hash != NULL,
 712             ("ufsdirhash_findfree: Invalid dirhash %p\n", dh));
 713         DIRHASH_ASSERT_LOCKED(dh);
 714
 715         /* Find a directory block with the desired free space. */
 716         dirblock = -1;
 717         for (i = howmany(slotneeded, DIRALIGN); i <= DH_NFSTATS; i++)
 718                 if ((dirblock = dh->dh_firstfree[i]) != -1)
 719                         break;
 720         if (dirblock == -1)
 721                 return (-1);
 722
 723         KASSERT(dirblock < dh->dh_nblk &&
 724             dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN),
 725             ("ufsdirhash_findfree: bad stats"));
 726         pos = dirblock * DIRBLKSIZ;
 727         error = UFS_BLKATOFF(ip->i_vnode, (off_t)pos, (char **)&dp, &bp);
 728         if (error)
 729                 return (-1);
 730
 731         /* Find the first entry with free space. */
 732         for (i = 0; i < DIRBLKSIZ; ) {
 733                 if (dp->d_reclen == 0) {
 734                         brelse(bp);
 735                         return (-1);
 736                 }
 737                 if (dp->d_ino == 0 || dp->d_reclen > DIRSIZ(0, dp))
 738                         break;
 739                 i += dp->d_reclen;
 740                 dp = (struct direct *)((char *)dp + dp->d_reclen);
 741         }
 742         if (i > DIRBLKSIZ) {
 743                 brelse(bp);
 744                 return (-1);
 745         }
 746         slotstart = pos + i;
 747
 748         /* Find the range of entries needed to get enough space */
 749         freebytes = 0;
 750         while (i < DIRBLKSIZ && freebytes < slotneeded) {
 751                 freebytes += dp->d_reclen;
 752                 if (dp->d_ino != 0)
 753                         freebytes -= DIRSIZ(0, dp);
 754                 if (dp->d_reclen == 0) {
 755                         brelse(bp);
 756                         return (-1);
 757                 }
 758                 i += dp->d_reclen;
 759                 dp = (struct direct *)((char *)dp + dp->d_reclen);
 760         }
 761         if (i > DIRBLKSIZ) {
 762                 brelse(bp);
 763                 return (-1);
 764         }
 765         if (freebytes < slotneeded)
 766                 panic("ufsdirhash_findfree: free mismatch");
 767         brelse(bp);
 768         *slotsize = pos + i - slotstart;
 769         return (slotstart);
 770 }
 771
 772 /*
 773  * Return the start of the unused space at the end of a directory, or
 774  * -1 if there are no trailing unused blocks.
 775  */
 776 doff_t
 777 ufsdirhash_enduseful(struct inode *ip)
 778 {
 779
 780         struct dirhash *dh;
 781         int i;
 782
 783         dh = ip->i_dirhash;
 784         DIRHASH_ASSERT_LOCKED(dh);
 785         KASSERT(dh != NULL && dh->dh_hash != NULL,
 786             ("ufsdirhash_enduseful: Invalid dirhash %p\n", dh));
 787
 788         if (dh->dh_blkfree[dh->dh_dirblks - 1] != DIRBLKSIZ / DIRALIGN)
 789                 return (-1);
 790
 791         for (i = dh->dh_dirblks - 1; i >= 0; i--)
 792                 if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
 793                         break;
 794
 795         return ((doff_t)(i + 1) * DIRBLKSIZ);
 796 }
 797
 798 /*
 799  * Insert information into the hash about a new directory entry. dirp
 800  * points to a struct direct containing the entry, and offset specifies
 801  * the offset of this entry.
 802  */
 803 void
 804 ufsdirhash_add(struct inode *ip, struct direct *dirp, doff_t offset)
 805 {
 806         struct dirhash *dh;
 807         int slot;
 808
 809         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 810                 return;
 811
 812         KASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
 813             ("ufsdirhash_add: bad offset"));
 814         /*
 815          * Normal hash usage is < 66%. If the usage gets too high then
 816          * remove the hash entirely and let it be rebuilt later.
 817          */
 818         if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
 819                 ufsdirhash_free_locked(ip);
 820                 return;
 821         }
 822
 823         /* Find a free hash slot (empty or deleted), and add the entry. */
 824         slot = ufsdirhash_hash(dh, dirp->d_name, dirp->d_namlen);
 825         while (DH_ENTRY(dh, slot) >= 0)
 826                 slot = WRAPINCR(slot, dh->dh_hlen);
 827         if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
 828                 dh->dh_hused++;
 829         DH_ENTRY(dh, slot) = offset;
 830
 831         /* Update last used time. */
 832         dh->dh_lastused = time_second;
 833
 834         /* Update the per-block summary info. */
 835         ufsdirhash_adjfree(dh, offset, -DIRSIZ(0, dirp));
 836         ufsdirhash_release(dh);
 837 }
 838
 839 /*
 840  * Remove the specified directory entry from the hash. The entry to remove
 841  * is defined by the name in `dirp', which must exist at the specified
 842  * `offset' within the directory.
 843  */
 844 void
 845 ufsdirhash_remove(struct inode *ip, struct direct *dirp, doff_t offset)
 846 {
 847         struct dirhash *dh;
 848         int slot;
 849
 850         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 851                 return;
 852
 853         KASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
 854             ("ufsdirhash_remove: bad offset"));
 855         /* Find the entry */
 856         slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, offset);
 857
 858         /* Remove the hash entry. */
 859         ufsdirhash_delslot(dh, slot);
 860
 861         /* Update the per-block summary info. */
 862         ufsdirhash_adjfree(dh, offset, DIRSIZ(0, dirp));
 863         ufsdirhash_release(dh);
 864 }
 865
 866 /*
 867  * Change the offset associated with a directory entry in the hash. Used
 868  * when compacting directory blocks.
 869  */
 870 void
 871 ufsdirhash_move(struct inode *ip, struct direct *dirp, doff_t oldoff,
 872     doff_t newoff)
 873 {
 874         struct dirhash *dh;
 875         int slot;
 876
 877         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 878                 return;
 879
 880         KASSERT(oldoff < dh->dh_dirblks * DIRBLKSIZ &&
 881             newoff < dh->dh_dirblks * DIRBLKSIZ,
 882             ("ufsdirhash_move: bad offset"));
 883         /* Find the entry, and update the offset. */
 884         slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, oldoff);
 885         DH_ENTRY(dh, slot) = newoff;
 886         ufsdirhash_release(dh);
 887 }
 888
 889 /*
 890  * Inform dirhash that the directory has grown by one block that
 891  * begins at offset (i.e. the new length is offset + DIRBLKSIZ).
 892  */
 893 void
 894 ufsdirhash_newblk(struct inode *ip, doff_t offset)
 895 {
 896         struct dirhash *dh;
 897         int block;
 898
 899         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 900                 return;
 901
 902         KASSERT(offset == dh->dh_dirblks * DIRBLKSIZ,
 903             ("ufsdirhash_newblk: bad offset"));
 904         block = offset / DIRBLKSIZ;
 905         if (block >= dh->dh_nblk) {
 906                 /* Out of space; must rebuild. */
 907                 ufsdirhash_free_locked(ip);
 908                 return;
 909         }
 910         dh->dh_dirblks = block + 1;
 911
 912         /* Account for the new free block. */
 913         dh->dh_blkfree[block] = DIRBLKSIZ / DIRALIGN;
 914         if (dh->dh_firstfree[DH_NFSTATS] == -1)
 915                 dh->dh_firstfree[DH_NFSTATS] = block;
 916         ufsdirhash_release(dh);
 917 }
 918
 919 /*
 920  * Inform dirhash that the directory is being truncated.
 921  */
 922 void
 923 ufsdirhash_dirtrunc(struct inode *ip, doff_t offset)
 924 {
 925         struct dirhash *dh;
 926         int block, i;
 927
 928         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 929                 return;
 930
 931         KASSERT(offset <= dh->dh_dirblks * DIRBLKSIZ,
 932             ("ufsdirhash_dirtrunc: bad offset"));
 933         block = howmany(offset, DIRBLKSIZ);
 934         /*
 935          * If the directory shrinks to less than 1/8 of dh_nblk blocks
 936          * (about 20% of its original size due to the 50% extra added in
 937          * ufsdirhash_build) then free it, and let the caller rebuild
 938          * if necessary.
 939          */
 940         if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
 941                 ufsdirhash_free_locked(ip);
 942                 return;
 943         }
 944
 945         /*
 946          * Remove any `first free' information pertaining to the
 947          * truncated blocks. All blocks we're removing should be
 948          * completely unused.
 949          */
 950         if (dh->dh_firstfree[DH_NFSTATS] >= block)
 951                 dh->dh_firstfree[DH_NFSTATS] = -1;
 952         for (i = block; i < dh->dh_dirblks; i++)
 953                 if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
 954                         panic("ufsdirhash_dirtrunc: blocks in use");
 955         for (i = 0; i < DH_NFSTATS; i++)
 956                 if (dh->dh_firstfree[i] >= block)
 957                         panic("ufsdirhash_dirtrunc: first free corrupt");
 958         dh->dh_dirblks = block;
 959         ufsdirhash_release(dh);
 960 }
 961
 962 /*
 963  * Debugging function to check that the dirhash information about
 964  * a directory block matches its actual contents. Panics if a mismatch
 965  * is detected.
 966  *
 967  * On entry, `buf' should point to the start of an in-core
 968  * DIRBLKSIZ-sized directory block, and `offset' should contain the
 969  * offset from the start of the directory of that block.
 970  */
 971 void
 972 ufsdirhash_checkblock(struct inode *ip, char *buf, doff_t offset)
 973 {
 974         struct dirhash *dh;
 975         struct direct *dp;
 976         int block, ffslot, i, nfree;
 977
 978         if (!ufs_dirhashcheck)
 979                 return;
 980         if ((dh = ufsdirhash_acquire(ip)) == NULL)
 981                 return;
 982
 983         block = offset / DIRBLKSIZ;
 984         if ((offset & (DIRBLKSIZ - 1)) != 0 || block >= dh->dh_dirblks)
 985                 panic("ufsdirhash_checkblock: bad offset");
 986
 987         nfree = 0;
 988         for (i = 0; i < DIRBLKSIZ; i += dp->d_reclen) {
 989                 dp = (struct direct *)(buf + i);
 990                 if (dp->d_reclen == 0 || i + dp->d_reclen > DIRBLKSIZ)
 991                         panic("ufsdirhash_checkblock: bad dir");
 992
 993                 if (dp->d_ino == 0) {
 994 #if 0
 995                         /*
 996                          * XXX entries with d_ino == 0 should only occur
 997                          * at the start of a DIRBLKSIZ block. However the
 998                          * ufs code is tolerant of such entries at other
 999                          * offsets, and fsck does not fix them.
1000                          */
1001                         if (i != 0)
1002                                 panic("ufsdirhash_checkblock: bad dir inode");
1003 #endif
1004                         nfree += dp->d_reclen;
1005                         continue;
1006                 }
1007
1008                 /* Check that the entry exists (will panic if it doesn't). */
1009                 ufsdirhash_findslot(dh, dp->d_name, dp->d_namlen, offset + i);
1010
1011                 nfree += dp->d_reclen - DIRSIZ(0, dp);
1012         }
1013         if (i != DIRBLKSIZ)
1014                 panic("ufsdirhash_checkblock: bad dir end");
1015
1016         if (dh->dh_blkfree[block] * DIRALIGN != nfree)
1017                 panic("ufsdirhash_checkblock: bad free count");
1018
1019         ffslot = BLKFREE2IDX(nfree / DIRALIGN);
1020         for (i = 0; i <= DH_NFSTATS; i++)
1021                 if (dh->dh_firstfree[i] == block && i != ffslot)
1022                         panic("ufsdirhash_checkblock: bad first-free");
1023         if (dh->dh_firstfree[ffslot] == -1)
1024                 panic("ufsdirhash_checkblock: missing first-free entry");
1025         ufsdirhash_release(dh);
1026 }
1027
1028 /*
1029  * Hash the specified filename into a dirhash slot.
1030  */
1031 static int
1032 ufsdirhash_hash(struct dirhash *dh, char *name, int namelen)
1033 {
1034         u_int32_t hash;
1035
1036         /*
1037          * We hash the name and then some other bit of data that is
1038          * invariant over the dirhash's lifetime. Otherwise names
1039          * differing only in the last byte are placed close to one
1040          * another in the table, which is bad for linear probing.
1041          */
1042         hash = fnv_32_buf(name, namelen, FNV1_32_INIT);
1043         hash = fnv_32_buf(&dh, sizeof(dh), hash);
1044         return (hash % dh->dh_hlen);
1045 }
1046
1047 /*
1048  * Adjust the number of free bytes in the block containing `offset'
1049  * by the value specified by `diff'.
1050  *
1051  * The caller must ensure we have exclusive access to `dh'; normally
1052  * that means that dh_lock should be held, but this is also called
1053  * from ufsdirhash_build() where exclusive access can be assumed.
1054  */
1055 static void
1056 ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff)
1057 {
1058         int block, i, nfidx, ofidx;
1059
1060         /* Update the per-block summary info. */
1061         block = offset / DIRBLKSIZ;
1062         KASSERT(block < dh->dh_nblk && block < dh->dh_dirblks,
1063              ("dirhash bad offset"));
1064         ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
1065         dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
1066         nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
1067
1068         /* Update the `first free' list if necessary. */
1069         if (ofidx != nfidx) {
1070                 /* If removing, scan forward for the next block. */
1071                 if (dh->dh_firstfree[ofidx] == block) {
1072                         for (i = block + 1; i < dh->dh_dirblks; i++)
1073                                 if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
1074                                         break;
1075                         dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
1076                 }
1077
1078                 /* Make this the new `first free' if necessary */
1079                 if (dh->dh_firstfree[nfidx] > block ||
1080                     dh->dh_firstfree[nfidx] == -1)
1081                         dh->dh_firstfree[nfidx] = block;
1082         }
1083 }
1084
1085 /*
1086  * Find the specified name which should have the specified offset.
1087  * Returns a slot number, and panics on failure.
1088  *
1089  * `dh' must be locked on entry and remains so on return.
1090  */
1091 static int
1092 ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen, doff_t offset)
1093 {
1094         int slot;
1095
1096         DIRHASH_ASSERT_LOCKED(dh);
1097
1098         /* Find the entry. */
1099         KASSERT(dh->dh_hused < dh->dh_hlen, ("dirhash find full"));
1100         slot = ufsdirhash_hash(dh, name, namelen);
1101         while (DH_ENTRY(dh, slot) != offset &&
1102             DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
1103                 slot = WRAPINCR(slot, dh->dh_hlen);
1104         if (DH_ENTRY(dh, slot) != offset)
1105                 panic("ufsdirhash_findslot: '%.*s' not found", namelen, name);
1106
1107         return (slot);
1108 }
1109
1110 /*
1111  * Remove the entry corresponding to the specified slot from the hash array.
1112  *
1113  * `dh' must be locked on entry and remains so on return.
1114  */
1115 static void
1116 ufsdirhash_delslot(struct dirhash *dh, int slot)
1117 {
1118         int i;
1119
1120         DIRHASH_ASSERT_LOCKED(dh);
1121
1122         /* Mark the entry as deleted. */
1123         DH_ENTRY(dh, slot) = DIRHASH_DEL;
1124
1125         /* If this is the end of a chain of DIRHASH_DEL slots, remove them. */
1126         for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
1127                 i = WRAPINCR(i, dh->dh_hlen);
1128         if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
1129                 i = WRAPDECR(i, dh->dh_hlen);
1130                 while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
1131                         DH_ENTRY(dh, i) = DIRHASH_EMPTY;
1132                         dh->dh_hused--;
1133                         i = WRAPDECR(i, dh->dh_hlen);
1134                 }
1135                 KASSERT(dh->dh_hused >= 0, ("ufsdirhash_delslot neg hlen"));
1136         }
1137 }
1138
1139 /*
1140  * Given a directory entry and its offset, find the offset of the
1141  * previous entry in the same DIRBLKSIZ-sized block. Returns an
1142  * offset, or -1 if there is no previous entry in the block or some
1143  * other problem occurred.
1144  */
1145 static doff_t
1146 ufsdirhash_getprev(struct direct *dirp, doff_t offset)
1147 {
1148         struct direct *dp;
1149         char *blkbuf;
1150         doff_t blkoff, prevoff;
1151         int entrypos, i;
1152
1153         blkoff = offset & ~(DIRBLKSIZ - 1);     /* offset of start of block */
1154         entrypos = offset & (DIRBLKSIZ - 1);    /* entry relative to block */
1155         blkbuf = (char *)dirp - entrypos;
1156         prevoff = blkoff;
1157
1158         /* If `offset' is the start of a block, there is no previous entry. */
1159         if (entrypos == 0)
1160                 return (-1);
1161
1162         /* Scan from the start of the block until we get to the entry. */
1163         for (i = 0; i < entrypos; i += dp->d_reclen) {
1164                 dp = (struct direct *)(blkbuf + i);
1165                 if (dp->d_reclen == 0 || i + dp->d_reclen > entrypos)
1166                         return (-1);    /* Corrupted directory. */
1167                 prevoff = blkoff + i;
1168         }
1169         return (prevoff);
1170 }
1171
1172 /*
1173  * Delete the given dirhash and reclaim its memory. Assumes that
1174  * ufsdirhash_list is locked, and leaves it locked. Also assumes
1175  * that dh is locked. Returns the amount of memory freed.
1176  */
1177 static int
1178 ufsdirhash_destroy(struct dirhash *dh)
1179 {
1180         doff_t **hash;
1181         u_int8_t *blkfree;
1182         int i, mem, narrays;
1183
1184         KASSERT(dh->dh_hash != NULL, ("dirhash: NULL hash on list"));
1185
1186         /* Remove it from the list and detach its memory. */
1187         TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
1188         dh->dh_onlist = 0;
1189         hash = dh->dh_hash;
1190         dh->dh_hash = NULL;
1191         blkfree = dh->dh_blkfree;
1192         dh->dh_blkfree = NULL;
1193         narrays = dh->dh_narrays;
1194         mem = dh->dh_memreq;
1195         dh->dh_memreq = 0;
1196
1197         /* Unlock dirhash and free the detached memory. */
1198         ufsdirhash_release(dh);
1199         for (i = 0; i < narrays; i++)
1200                 DIRHASH_BLKFREE(hash[i]);
1201         free(hash, M_DIRHASH);
1202         free(blkfree, M_DIRHASH);
1203
1204         /* Account for the returned memory. */
1205         ufs_dirhashmem -= mem;
1206
1207         return (mem);
1208 }
1209
1210 /*
1211  * Try to free up `wanted' bytes by stealing memory from existing
1212  * dirhashes. Returns zero with list locked if successful.
1213  */
1214 static int
1215 ufsdirhash_recycle(int wanted)
1216 {
1217         struct dirhash *dh;
1218
1219         DIRHASHLIST_LOCK();
1220         dh = TAILQ_FIRST(&ufsdirhash_list);
1221         while (wanted + ufs_dirhashmem > ufs_dirhashmaxmem) {
1222                 /* Decrement the score; only recycle if it becomes zero. */
1223                 if (dh == NULL || --dh->dh_score > 0) {
1224                         DIRHASHLIST_UNLOCK();
1225                         return (-1);
1226                 }
1227                 /*
1228                  * If we can't lock it it's in use and we don't want to
1229                  * recycle it anyway.
1230                  */
1231                 if (!sx_try_xlock(&dh->dh_lock)) {
1232                         dh = TAILQ_NEXT(dh, dh_list);
1233                         continue;
1234                 }
1235
1236                 ufsdirhash_destroy(dh);
1237
1238                 /* Repeat if necessary. */
1239                 dh = TAILQ_FIRST(&ufsdirhash_list);
1240         }
1241         /* Success; return with list locked. */
1242         return (0);
1243 }
1244
1245 /*
1246  * Callback that frees some dirhashes when the system is low on virtual memory.
1247  */
1248 static void
1249 ufsdirhash_lowmem()
1250 {
1251         struct dirhash *dh, *dh_temp;
1252         int memfreed = 0;
1253         /*
1254          * Will free a *minimum* of 10% of the dirhash, but possibly much
1255          * more (depending on dirhashreclaimage). System with large dirhashes
1256          * probably also need a much larger dirhashreclaimage.
1257          * XXX: this percentage may need to be adjusted.
1258          */
1259         int memwanted = ufs_dirhashmem / 10;
1260
1261         ufs_dirhashlowmemcount++;
1262
1263         DIRHASHLIST_LOCK();
1264         /*
1265          * Delete dirhashes not used for more than ufs_dirhashreclaimage
1266          * seconds. If we can't get a lock on the dirhash, it will be skipped.
1267          */
1268         TAILQ_FOREACH_SAFE(dh, &ufsdirhash_list, dh_list, dh_temp) {
1269                 if (!sx_try_xlock(&dh->dh_lock))
1270                         continue;
1271                 if (time_second - dh->dh_lastused > ufs_dirhashreclaimage)
1272                         memfreed += ufsdirhash_destroy(dh);
1273                 /* Unlock if we didn't delete the dirhash */
1274                 else
1275                         ufsdirhash_release(dh);
1276         }
1277
1278         /*
1279          * If not enough memory was freed, keep deleting hashes from the head
1280          * of the dirhash list. The ones closest to the head should be the
1281          * oldest.
1282          */
1283         if (memfreed < memwanted) {
1284                 TAILQ_FOREACH_SAFE(dh, &ufsdirhash_list, dh_list, dh_temp) {
1285                         if (!sx_try_xlock(&dh->dh_lock))
1286                                 continue;
1287                         memfreed += ufsdirhash_destroy(dh);
1288                         if (memfreed >= memwanted)
1289                                 break;
1290                 }
1291         }
1292         DIRHASHLIST_UNLOCK();
1293 }
1294
1295
1296 void
1297 ufsdirhash_init()
1298 {
1299         ufs_dirhashmaxmem = lmax(roundup(hibufspace / 64, PAGE_SIZE),
1300             2 * 1024 * 1024);
1301
1302         ufsdirhash_zone = uma_zcreate("DIRHASH", DH_NBLKOFF * sizeof(doff_t),
1303             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
1304         mtx_init(&ufsdirhash_mtx, "dirhash list", NULL, MTX_DEF);
1305         TAILQ_INIT(&ufsdirhash_list);
1306
1307         /* Register a callback function to handle low memory signals */
1308         EVENTHANDLER_REGISTER(vm_lowmem, ufsdirhash_lowmem, NULL,
1309             EVENTHANDLER_PRI_FIRST);
1310 }
1311
1312 void
1313 ufsdirhash_uninit()
1314 {
1315         KASSERT(TAILQ_EMPTY(&ufsdirhash_list), ("ufsdirhash_uninit"));
1316         uma_zdestroy(ufsdirhash_zone);
1317         mtx_destroy(&ufsdirhash_mtx);
1318 }
1319
1320 #endif /* UFS_DIRHASH */