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