add ian dowse's dirhash code from freebsd.

by building a hash table for large directories, lookups and deletions
become about constant time.  this is an excellent improvement for dirs with
10k or more files.
some more cleanup to come, but the code works.
enabled with option UFS_DIRHASH
testing brad millert otto

8 files changed, 1359 insertions, 10 deletions

diff --git a/sys/ufs/ufs/dir.h b/sys/ufs/ufs/dir.h
index 64015df51f0..0b7560cacd8 100644
--- a/sys/ufs/ufs/dir.h
+++ b/sys/ufs/ufs/dir.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dir.h,v 1.8 2003/06/02 23:28:23 millert Exp $	*/
+/*	$OpenBSD: dir.h,v 1.9 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: dir.h,v 1.8 1996/03/09 19:42:41 scottr Exp $	*/
 
 /*
@@ -109,6 +109,9 @@ struct	direct {
  * without the d_name field, plus enough space for the name with a terminating
  * null byte (dp->d_namlen+1), rounded up to a 4 byte boundary.
  */
+#define DIRECTSIZ(namlen)						\
+	(((int)&((struct direct *)0)->d_name +				\
+	  ((namlen)+1)*sizeof(((struct direct *)0)->d_name[0]) + 3) & ~3)
 #if (BYTE_ORDER == LITTLE_ENDIAN)
 #define DIRSIZ(oldfmt, dp) \
     ((oldfmt) ? \
diff --git a/sys/ufs/ufs/dirhash.h b/sys/ufs/ufs/dirhash.h
new file mode 100644
index 00000000000..ac922601de3
--- /dev/null
+++ b/sys/ufs/ufs/dirhash.h
@@ -0,0 +1,129 @@
+/*
+ * Copyright (c) 2001 Ian Dowse.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.4 2003/01/01 18:48:59 schweikh Exp $
+ */
+
+#ifndef _UFS_UFS_DIRHASH_H_
+#define _UFS_UFS_DIRHASH_H_
+
+#include <sys/rwlock.h>
+
+/*
+ * For fast operations on large directories, we maintain a hash
+ * that maps the file name to the offset of the directory entry within
+ * the directory file.
+ *
+ * The hashing uses a dumb spillover to the next free slot on
+ * collisions, so we must keep the utilisation low to avoid
+ * long linear searches. Deleted entries that are not the last
+ * in a chain must be marked DIRHASH_DEL.
+ *
+ * We also maintain information about free space in each block
+ * to speed up creations.
+ */
+#define DIRHASH_EMPTY	(-1)	/* entry unused */
+#define DIRHASH_DEL	(-2)	/* deleted entry; may be part of chain */
+
+#define DIRALIGN	4
+#define DH_NFSTATS	(DIRECTSIZ(MAXNAMLEN + 1) / DIRALIGN)
+				 /* max DIRALIGN words in a directory entry */
+
+/*
+ * Dirhash uses a score mechanism to achieve a hybrid between a
+ * least-recently-used and a least-often-used algorithm for entry
+ * recycling. The score is incremented when a directory is used, and
+ * decremented when the directory is a candidate for recycling. When
+ * the score reaches zero, the hash is recycled. Hashes are linked
+ * together on a TAILQ list, and hashes with higher scores filter
+ * towards the tail (most recently used) end of the list.
+ *
+ * New hash entries are given an inital score of DH_SCOREINIT and are
+ * placed at the most-recently-used end of the list. This helps a lot
+ * in the worst-case case scenario where every directory access is
+ * to a directory that is not hashed (i.e. the working set of hash
+ * candidates is much larger than the configured memry limit). In this
+ * case it limits the number of hash builds to 1/DH_SCOREINIT of the
+ * number of accesses.
+ */
+#define DH_SCOREINIT	8	/* initial dh_score when dirhash built */
+#define DH_SCOREMAX	64	/* max dh_score value */
+
+/*
+ * The main hash table has 2 levels. It is an array of pointers to
+ * blocks of DH_NBLKOFF offsets.
+ */
+#define DH_BLKOFFSHIFT	8
+#define DH_NBLKOFF	(1 << DH_BLKOFFSHIFT)
+#define DH_BLKOFFMASK	(DH_NBLKOFF - 1)
+
+#define DH_ENTRY(dh, slot) \
+    ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])
+
+struct dirhash {
+	struct rwlock dh_mtx;	/* protects all fields except dh_list */
+
+	doff_t	**dh_hash;	/* the hash array (2-level) */
+	int	dh_narrays;	/* number of entries in dh_hash */
+	int	dh_hlen;	/* total slots in the 2-level hash array */
+	int	dh_hused;	/* entries in use */
+
+	/* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
+	u_int8_t *dh_blkfree;	/* free DIRALIGN words in each dir block */
+	int	dh_nblk;	/* size of dh_blkfree array */
+	int	dh_dirblks;	/* number of DIRBLKSIZ blocks in dir */
+	int	dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */
+
+	int	dh_seqopt;	/* sequential access optimisation enabled */
+	doff_t	dh_seqoff;	/* sequential access optimisation offset */
+
+	int	dh_score;	/* access count for this dirhash */
+
+	int	dh_onlist;	/* true if on the ufsdirhash_list chain */
+
+	/* Protected by ufsdirhash_mtx. */
+	TAILQ_ENTRY(dirhash) dh_list;	/* chain of all dirhashes */
+};
+
+
+/*
+ * Dirhash functions.
+ */
+void	ufsdirhash_init(void);
+void	ufsdirhash_uninit(void);
+int	ufsdirhash_build(struct inode *);
+doff_t	ufsdirhash_findfree(struct inode *, int, int *);
+doff_t	ufsdirhash_enduseful(struct inode *);
+int	ufsdirhash_lookup(struct inode *, char *, int, doff_t *, struct buf **,
+	    doff_t *);
+void	ufsdirhash_newblk(struct inode *, doff_t);
+void	ufsdirhash_add(struct inode *, struct direct *, doff_t);
+void	ufsdirhash_remove(struct inode *, struct direct *, doff_t);
+void	ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
+void	ufsdirhash_dirtrunc(struct inode *, doff_t);
+void	ufsdirhash_free(struct inode *);
+
+void	ufsdirhash_checkblock(struct inode *, char *, doff_t);
+
+#endif /* !_UFS_UFS_DIRHASH_H_ */
diff --git a/sys/ufs/ufs/inode.h b/sys/ufs/ufs/inode.h
index e8a3f2b9bb9..fe24891b277 100644
--- a/sys/ufs/ufs/inode.h
+++ b/sys/ufs/ufs/inode.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: inode.h,v 1.23 2003/08/25 23:26:55 tedu Exp $	*/
+/*	$OpenBSD: inode.h,v 1.24 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: inode.h,v 1.8 1995/06/15 23:22:50 cgd Exp $	*/
 
 /*
@@ -100,9 +100,11 @@ struct inode {
 	union {
 		/* Other extensions could go here... */
 		struct ext2fs_inode_ext   e2fs;
+		struct dirhash *dirhash;
 	} inode_ext;
 #define i_e2fs_last_lblk inode_ext.e2fs.ext2fs_last_lblk
 #define i_e2fs_last_blk inode_ext.e2fs.ext2fs_last_blk
+#define	i_dirhash	inode_ext.dirhash
 
 	/*
 	 * The on-disk dinode itself.
@@ -172,6 +174,7 @@ struct inode_vtbl {
 #define	i_ffs_shortlink		i_din1.di_shortlink
 #define	i_ffs_size		i_din1.di_size
 #define	i_ffs_uid		i_din1.di_uid
+#define i_size			i_din1.di_size
 
 #ifndef _KERNEL
 /*
diff --git a/sys/ufs/ufs/ufs_dirhash.c b/sys/ufs/ufs/ufs_dirhash.c
new file mode 100644
index 00000000000..8ee377e7872
--- /dev/null
+++ b/sys/ufs/ufs/ufs_dirhash.c
@@ -0,0 +1,1095 @@
+/*
+ * Copyright (c) 2001, 2002 Ian Dowse.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * This implements a hash-based lookup scheme for UFS directories.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/lock.h>
+#include <sys/rwlock.h>
+#include <sys/malloc.h>
+#include <sys/pool.h>
+#include <sys/proc.h>
+#include <sys/buf.h>
+#include <sys/vnode.h>
+#include <sys/mount.h>
+#include <sys/sysctl.h>
+#include <sys/hash.h>
+
+#include <ufs/ufs/quota.h>
+#include <ufs/ufs/inode.h>
+#include <ufs/ufs/dir.h>
+#include <ufs/ufs/dirhash.h>
+#include <ufs/ufs/extattr.h>
+#include <ufs/ufs/ufsmount.h>
+#include <ufs/ufs/ufs_extern.h>
+
+#define WRAPINCR(val, limit)	(((val) + 1 == (limit)) ? 0 : ((val) + 1))
+#define WRAPDECR(val, limit)	(((val) == 0) ? ((limit) - 1) : ((val) - 1))
+#define OFSFMT(vp)		((vp)->v_mount->mnt_maxsymlinklen <= 0)
+#define BLKFREE2IDX(n)		((n) > DH_NFSTATS ? DH_NFSTATS : (n))
+
+int ufs_mindirhashsize = DIRBLKSIZ * 5;
+int ufs_dirhashmaxmem = 2 * 1024 * 1024;
+int ufs_dirhashmem;
+int ufs_dirhashcheck = 0;
+
+
+int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen);
+void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff);
+void ufsdirhash_delslot(struct dirhash *dh, int slot);
+int ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen,
+   doff_t offset);
+doff_t ufsdirhash_getprev(struct direct *dp, doff_t offset);
+int ufsdirhash_recycle(int wanted);
+
+/* Dirhash list; recently-used entries are near the tail. */
+TAILQ_HEAD(, dirhash) ufsdirhash_list;
+
+#ifdef __FreeBSD__
+static uma_zone_t	ufsdirhash_zone;
+#define		DIRHASH_ALLOC()	uma_zalloc(ufsdirhash_zone, M_WAITOK)
+#define		DIRHASH_FREE(v)	uma_zfree(ufsdirhash_zone, v)
+
+/* Protects: ufsdirhash_list, `dh_list' field, ufs_dirhashmem. */
+static struct mtx	ufsdirhash_mtx;
+#define		LOCK(l)		mtx_lock(l)
+#define		UNLOCK(l)	mtx_unlock(l)
+#else
+struct pool		ufsdirhash_pool;
+#define		DIRHASH_ALLOC()	pool_get(&ufsdirhash_pool, PR_WAITOK)
+#define		DIRHASH_FREE(v)	pool_put(&ufsdirhash_pool, v)
+
+struct rwlock		ufsdirhash_mtx;
+#define		LOCK(l)		rw_enter_write(l, curproc)
+#define		UNLOCK(l)	rw_exit_write(l)
+#define		mtx_assert(l, f)	/* nothing */
+
+#define DIRHASH_ASSERT(e, m)	KASSERT((e))
+#endif
+
+/*
+ * Locking order:
+ *	ufsdirhash_mtx
+ *	dh_mtx
+ *
+ * The dh_mtx mutex should be acquired either via the inode lock, or via
+ * ufsdirhash_mtx. Only the owner of the inode may free the associated
+ * dirhash, but anything can steal its memory and set dh_hash to NULL.
+ */
+
+/*
+ * Attempt to build up a hash table for the directory contents in
+ * inode 'ip'. Returns 0 on success, or -1 of the operation failed.
+ */
+int
+ufsdirhash_build(struct inode *ip)
+{
+	struct dirhash *dh;
+	struct buf *bp = NULL;
+	struct direct *ep;
+	struct vnode *vp;
+	doff_t bmask, pos;
+	int dirblocks, i, j, memreqd, nblocks, narrays, nslots, slot;
+
+	/* Check if we can/should use dirhash. */
+	if (ip->i_dirhash == NULL) {
+		if (ip->i_size < ufs_mindirhashsize || OFSFMT(ip->i_vnode))
+			return (-1);
+	} else {
+		/* Hash exists, but sysctls could have changed. */
+		if (ip->i_size < ufs_mindirhashsize ||
+		    ufs_dirhashmem > ufs_dirhashmaxmem) {
+			ufsdirhash_free(ip);
+			return (-1);
+		}
+		/* Check if hash exists and is intact (note: unlocked read). */
+		if (ip->i_dirhash->dh_hash != NULL)
+			return (0);
+		/* Free the old, recycled hash and build a new one. */
+		ufsdirhash_free(ip);
+	}
+
+	/* Don't hash removed directories. */
+	if (ip->i_effnlink == 0)
+		return (-1);
+
+	vp = ip->i_vnode;
+	/* Allocate 50% more entries than this dir size could ever need. */
+	DIRHASH_ASSERT(ip->i_size >= DIRBLKSIZ, ("ufsdirhash_build size"));
+	nslots = ip->i_size / DIRECTSIZ(1);
+	nslots = (nslots * 3 + 1) / 2;
+	narrays = howmany(nslots, DH_NBLKOFF);
+	nslots = narrays * DH_NBLKOFF;
+	dirblocks = howmany(ip->i_size, DIRBLKSIZ);
+	nblocks = (dirblocks * 3 + 1) / 2;
+
+	memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
+	    narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
+	    nblocks * sizeof(*dh->dh_blkfree);
+	LOCK(&ufsdirhash_mtx);
+	if (memreqd + ufs_dirhashmem > ufs_dirhashmaxmem) {
+		UNLOCK(&ufsdirhash_mtx);
+		if (memreqd > ufs_dirhashmaxmem / 2)
+			return (-1);
+
+		/* Try to free some space. */
+		if (ufsdirhash_recycle(memreqd) != 0)
+			return (-1);
+		/* Enough was freed, and ufsdirhash_mtx has been locked. */
+	}
+	ufs_dirhashmem += memreqd;
+	UNLOCK(&ufsdirhash_mtx);
+
+	/*
+	 * Use non-blocking mallocs so that we will revert to a linear
+	 * lookup on failure rather than potentially blocking forever.
+	 */
+	MALLOC(dh, struct dirhash *, sizeof *dh, M_DIRHASH, M_NOWAIT);
+	if (dh == NULL) {
+		LOCK(&ufsdirhash_mtx);
+		ufs_dirhashmem -= memreqd;
+		UNLOCK(&ufsdirhash_mtx);
+		return (-1);
+	}
+	memset(dh, 0, sizeof *dh);
+	MALLOC(dh->dh_hash, doff_t **, narrays * sizeof(dh->dh_hash[0]),
+	    M_DIRHASH, M_NOWAIT);
+	memset(dh->dh_hash, 0, narrays * sizeof(dh->dh_hash[0]));
+	MALLOC(dh->dh_blkfree, u_int8_t *, nblocks * sizeof(dh->dh_blkfree[0]),
+	    M_DIRHASH, M_NOWAIT);
+	if (dh->dh_hash == NULL || dh->dh_blkfree == NULL)
+		goto fail;
+	for (i = 0; i < narrays; i++) {
+		if ((dh->dh_hash[i] = DIRHASH_ALLOC()) == NULL)
+			goto fail;
+		for (j = 0; j < DH_NBLKOFF; j++)
+			dh->dh_hash[i][j] = DIRHASH_EMPTY;
+	}
+
+	/* Initialise the hash table and block statistics. */
+#ifdef __FreeBSD__
+	mtx_init(&dh->dh_mtx, "dirhash", NULL, MTX_DEF);
+#else
+	rw_init(&dh->dh_mtx);
+#endif
+	dh->dh_narrays = narrays;
+	dh->dh_hlen = nslots;
+	dh->dh_nblk = nblocks;
+	dh->dh_dirblks = dirblocks;
+	for (i = 0; i < dirblocks; i++)
+		dh->dh_blkfree[i] = DIRBLKSIZ / DIRALIGN;
+	for (i = 0; i < DH_NFSTATS; i++)
+		dh->dh_firstfree[i] = -1;
+	dh->dh_firstfree[DH_NFSTATS] = 0;
+	dh->dh_seqopt = 0;
+	dh->dh_seqoff = 0;
+	dh->dh_score = DH_SCOREINIT;
+	ip->i_dirhash = dh;
+
+	bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
+	pos = 0;
+	while (pos < ip->i_size) {
+		/* If necessary, get the next directory block. */
+		if ((pos & bmask) == 0) {
+			if (bp != NULL)
+				brelse(bp);
+			if (UFS_BUFATOFF(ip, (off_t)pos, NULL, &bp) != 0)
+				goto fail;
+		}
+
+		/* Add this entry to the hash. */
+		ep = (struct direct *)((char *)bp->b_data + (pos & bmask));
+		if (ep->d_reclen == 0 || ep->d_reclen >
+		    DIRBLKSIZ - (pos & (DIRBLKSIZ - 1))) {
+			/* Corrupted directory. */
+			brelse(bp);
+			goto fail;
+		}
+		if (ep->d_ino != 0) {
+			/* Add the entry (simplified ufsdirhash_add). */
+			slot = ufsdirhash_hash(dh, ep->d_name, ep->d_namlen);
+			while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
+				slot = WRAPINCR(slot, dh->dh_hlen);
+			dh->dh_hused++;
+			DH_ENTRY(dh, slot) = pos;
+			ufsdirhash_adjfree(dh, pos, -DIRSIZ(0, ep));
+		}
+		pos += ep->d_reclen;
+	}
+
+	if (bp != NULL)
+		brelse(bp);
+	LOCK(&ufsdirhash_mtx);
+	TAILQ_INSERT_TAIL(&ufsdirhash_list, dh, dh_list);
+	dh->dh_onlist = 1;
+	UNLOCK(&ufsdirhash_mtx);
+	return (0);
+
+fail:
+	if (dh->dh_hash != NULL) {
+		for (i = 0; i < narrays; i++)
+			if (dh->dh_hash[i] != NULL)
+				DIRHASH_FREE(dh->dh_hash[i]);
+		FREE(dh->dh_hash, M_DIRHASH);
+	}
+	if (dh->dh_blkfree != NULL)
+		FREE(dh->dh_blkfree, M_DIRHASH);
+	FREE(dh, M_DIRHASH);
+	ip->i_dirhash = NULL;
+	LOCK(&ufsdirhash_mtx);
+	ufs_dirhashmem -= memreqd;
+	UNLOCK(&ufsdirhash_mtx);
+	return (-1);
+}
+
+/*
+ * Free any hash table associated with inode 'ip'.
+ */
+void
+ufsdirhash_free(struct inode *ip)
+{
+	struct dirhash *dh;
+	int i, mem;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&ufsdirhash_mtx);
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_onlist)
+		TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
+	UNLOCK(&dh->dh_mtx);
+	UNLOCK(&ufsdirhash_mtx);
+
+	/* The dirhash pointed to by 'dh' is exclusively ours now. */
+
+	mem = sizeof(*dh);
+	if (dh->dh_hash != NULL) {
+		for (i = 0; i < dh->dh_narrays; i++)
+			DIRHASH_FREE(dh->dh_hash[i]);
+		FREE(dh->dh_hash, M_DIRHASH);
+		FREE(dh->dh_blkfree, M_DIRHASH);
+		mem += dh->dh_narrays * sizeof(*dh->dh_hash) +
+		    dh->dh_narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
+		    dh->dh_nblk * sizeof(*dh->dh_blkfree);
+	}
+#ifdef __FreeBSD__
+	mtx_destroy(&dh->dh_mtx);
+#endif
+	FREE(dh, M_DIRHASH);
+	ip->i_dirhash = NULL;
+
+	LOCK(&ufsdirhash_mtx);
+	ufs_dirhashmem -= mem;
+	UNLOCK(&ufsdirhash_mtx);
+}
+
+/*
+ * Find the offset of the specified name within the given inode.
+ * Returns 0 on success, ENOENT if the entry does not exist, or
+ * EJUSTRETURN if the caller should revert to a linear search.
+ *
+ * If successful, the directory offset is stored in *offp, and a
+ * pointer to a struct buf containing the entry is stored in *bpp. If
+ * prevoffp is non-NULL, the offset of the previous entry within
+ * the DIRBLKSIZ-sized block is stored in *prevoffp (if the entry
+ * is the first in a block, the start of the block is used).
+ */
+int
+ufsdirhash_lookup(struct inode *ip, char *name, int namelen, doff_t *offp,
+    struct buf **bpp, doff_t *prevoffp)
+{
+	struct dirhash *dh, *dh_next;
+	struct direct *dp;
+	struct vnode *vp;
+	struct buf *bp;
+	doff_t blkoff, bmask, offset, prevoff;
+	int i, slot;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return (EJUSTRETURN);
+	/*
+	 * Move this dirhash towards the end of the list if it has a
+	 * score higher than the next entry, and acquire the dh_mtx.
+	 * Optimise the case where it's already the last by performing
+	 * an unlocked read of the TAILQ_NEXT pointer.
+	 *
+	 * In both cases, end up holding just dh_mtx.
+	 */
+	if (TAILQ_NEXT(dh, dh_list) != NULL) {
+		LOCK(&ufsdirhash_mtx);
+		LOCK(&dh->dh_mtx);
+		/*
+		 * If the new score will be greater than that of the next
+		 * entry, then move this entry past it. With both mutexes
+		 * held, dh_next won't go away, but its dh_score could
+		 * change; that's not important since it is just a hint.
+		 */
+		if (dh->dh_hash != NULL &&
+		    (dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
+		    dh->dh_score >= dh_next->dh_score) {
+			DIRHASH_ASSERT(dh->dh_onlist, ("dirhash: not on list"));
+			TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
+			TAILQ_INSERT_AFTER(&ufsdirhash_list, dh_next, dh,
+			    dh_list);
+		}
+		UNLOCK(&ufsdirhash_mtx);
+	} else {
+		/* Already the last, though that could change as we wait. */
+		LOCK(&dh->dh_mtx);
+	}
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return (EJUSTRETURN);
+	}
+
+	/* Update the score. */
+	if (dh->dh_score < DH_SCOREMAX)
+		dh->dh_score++;
+
+	vp = ip->i_vnode;
+	bmask = VFSTOUFS(vp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
+	blkoff = -1;
+	bp = NULL;
+restart:
+	slot = ufsdirhash_hash(dh, name, namelen);
+
+	if (dh->dh_seqopt) {
+		/*
+		 * Sequential access optimisation. dh_seqoff contains the
+		 * offset of the directory entry immediately following
+		 * the last entry that was looked up. Check if this offset
+		 * appears in the hash chain for the name we are looking for.
+		 */
+		for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
+		    i = WRAPINCR(i, dh->dh_hlen))
+			if (offset == dh->dh_seqoff)
+				break;
+		if (offset == dh->dh_seqoff) {
+			/*
+			 * We found an entry with the expected offset. This
+			 * is probably the entry we want, but if not, the
+			 * code below will turn off seqoff and retry.
+			 */
+			slot = i;
+		} else
+			dh->dh_seqopt = 0;
+	}
+
+	for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
+	    slot = WRAPINCR(slot, dh->dh_hlen)) {
+		if (offset == DIRHASH_DEL)
+			continue;
+		UNLOCK(&dh->dh_mtx);
+
+		if (offset < 0 || offset >= ip->i_size)
+			panic("ufsdirhash_lookup: bad offset in hash array");
+		if ((offset & ~bmask) != blkoff) {
+			if (bp != NULL)
+				brelse(bp);
+			blkoff = offset & ~bmask;
+			if (UFS_BUFATOFF(ip, (off_t)blkoff, NULL, &bp) != 0)
+				return (EJUSTRETURN);
+		}
+		dp = (struct direct *)(bp->b_data + (offset & bmask));
+		if (dp->d_reclen == 0 || dp->d_reclen >
+		    DIRBLKSIZ - (offset & (DIRBLKSIZ - 1))) {
+			/* Corrupted directory. */
+			brelse(bp);
+			return (EJUSTRETURN);
+		}
+		if (dp->d_namlen == namelen &&
+		    bcmp(dp->d_name, name, namelen) == 0) {
+			/* Found. Get the prev offset if needed. */
+			if (prevoffp != NULL) {
+				if (offset & (DIRBLKSIZ - 1)) {
+					prevoff = ufsdirhash_getprev(dp,
+					    offset);
+					if (prevoff == -1) {
+						brelse(bp);
+						return (EJUSTRETURN);
+					}
+				} else
+					prevoff = offset;
+				*prevoffp = prevoff;
+			}
+
+			/* Check for sequential access, and update offset. */
+			if (dh->dh_seqopt == 0 && dh->dh_seqoff == offset)
+				dh->dh_seqopt = 1;
+			dh->dh_seqoff = offset + DIRSIZ(0, dp);
+
+			*bpp = bp;
+			*offp = offset;
+			return (0);
+		}
+
+		LOCK(&dh->dh_mtx);
+		if (dh->dh_hash == NULL) {
+			UNLOCK(&dh->dh_mtx);
+			if (bp != NULL)
+				brelse(bp);
+			ufsdirhash_free(ip);
+			return (EJUSTRETURN);
+		}
+		/*
+		 * When the name doesn't match in the seqopt case, go back
+		 * and search normally.
+		 */
+		if (dh->dh_seqopt) {
+			dh->dh_seqopt = 0;
+			goto restart;
+		}
+	}
+	UNLOCK(&dh->dh_mtx);
+	if (bp != NULL)
+		brelse(bp);
+	return (ENOENT);
+}
+
+/*
+ * Find a directory block with room for 'slotneeded' bytes. Returns
+ * the offset of the directory entry that begins the free space.
+ * This will either be the offset of an existing entry that has free
+ * space at the end, or the offset of an entry with d_ino == 0 at
+ * the start of a DIRBLKSIZ block.
+ *
+ * To use the space, the caller may need to compact existing entries in
+ * the directory. The total number of bytes in all of the entries involved
+ * in the compaction is stored in *slotsize. In other words, all of
+ * the entries that must be compacted are exactly contained in the
+ * region beginning at the returned offset and spanning *slotsize bytes.
+ *
+ * Returns -1 if no space was found, indicating that the directory
+ * must be extended.
+ */
+doff_t
+ufsdirhash_findfree(struct inode *ip, int slotneeded, int *slotsize)
+{
+	struct direct *dp;
+	struct dirhash *dh;
+	struct buf *bp;
+	doff_t pos, slotstart;
+	int dirblock, error, freebytes, i;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return (-1);
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return (-1);
+	}
+
+	/* Find a directory block with the desired free space. */
+	dirblock = -1;
+	for (i = howmany(slotneeded, DIRALIGN); i <= DH_NFSTATS; i++)
+		if ((dirblock = dh->dh_firstfree[i]) != -1)
+			break;
+	if (dirblock == -1) {
+		UNLOCK(&dh->dh_mtx);
+		return (-1);
+	}
+
+	DIRHASH_ASSERT(dirblock < dh->dh_nblk &&
+	    dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN),
+	    ("ufsdirhash_findfree: bad stats"));
+	UNLOCK(&dh->dh_mtx);
+	pos = dirblock * DIRBLKSIZ;
+	error = UFS_BUFATOFF(ip, (off_t)pos, (char **)&dp, &bp);
+	if (error)
+		return (-1);
+
+	/* Find the first entry with free space. */
+	for (i = 0; i < DIRBLKSIZ; ) {
+		if (dp->d_reclen == 0) {
+			brelse(bp);
+			return (-1);
+		}
+		if (dp->d_ino == 0 || dp->d_reclen > DIRSIZ(0, dp))
+			break;
+		i += dp->d_reclen;
+		dp = (struct direct *)((char *)dp + dp->d_reclen);
+	}
+	if (i > DIRBLKSIZ) {
+		brelse(bp);
+		return (-1);
+	}
+	slotstart = pos + i;
+
+	/* Find the range of entries needed to get enough space */
+	freebytes = 0;
+	while (i < DIRBLKSIZ && freebytes < slotneeded) {
+		freebytes += dp->d_reclen;
+		if (dp->d_ino != 0)
+			freebytes -= DIRSIZ(0, dp);
+		if (dp->d_reclen == 0) {
+			brelse(bp);
+			return (-1);
+		}
+		i += dp->d_reclen;
+		dp = (struct direct *)((char *)dp + dp->d_reclen);
+	}
+	if (i > DIRBLKSIZ) {
+		brelse(bp);
+		return (-1);
+	}
+	if (freebytes < slotneeded)
+		panic("ufsdirhash_findfree: free mismatch");
+	brelse(bp);
+	*slotsize = pos + i - slotstart;
+	return (slotstart);
+}
+
+/*
+ * Return the start of the unused space at the end of a directory, or
+ * -1 if there are no trailing unused blocks.
+ */
+doff_t
+ufsdirhash_enduseful(struct inode *ip)
+{
+
+	struct dirhash *dh;
+	int i;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return (-1);
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return (-1);
+	}
+
+	if (dh->dh_blkfree[dh->dh_dirblks - 1] != DIRBLKSIZ / DIRALIGN) {
+		UNLOCK(&dh->dh_mtx);
+		return (-1);
+	}
+
+	for (i = dh->dh_dirblks - 1; i >= 0; i--)
+		if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
+			break;
+	UNLOCK(&dh->dh_mtx);
+	return ((doff_t)(i + 1) * DIRBLKSIZ);
+}
+
+/*
+ * Insert information into the hash about a new directory entry. dirp
+ * points to a struct direct containing the entry, and offset specifies
+ * the offset of this entry.
+ */
+void
+ufsdirhash_add(struct inode *ip, struct direct *dirp, doff_t offset)
+{
+	struct dirhash *dh;
+	int slot;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	DIRHASH_ASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
+	    ("ufsdirhash_add: bad offset"));
+	/*
+	 * Normal hash usage is < 66%. If the usage gets too high then
+	 * remove the hash entirely and let it be rebuilt later.
+	 */
+	if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	/* Find a free hash slot (empty or deleted), and add the entry. */
+	slot = ufsdirhash_hash(dh, dirp->d_name, dirp->d_namlen);
+	while (DH_ENTRY(dh, slot) >= 0)
+		slot = WRAPINCR(slot, dh->dh_hlen);
+	if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
+		dh->dh_hused++;
+	DH_ENTRY(dh, slot) = offset;
+
+	/* Update the per-block summary info. */
+	ufsdirhash_adjfree(dh, offset, -DIRSIZ(0, dirp));
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Remove the specified directory entry from the hash. The entry to remove
+ * is defined by the name in `dirp', which must exist at the specified
+ * `offset' within the directory.
+ */
+void
+ufsdirhash_remove(struct inode *ip, struct direct *dirp, doff_t offset)
+{
+	struct dirhash *dh;
+	int slot;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	DIRHASH_ASSERT(offset < dh->dh_dirblks * DIRBLKSIZ,
+	    ("ufsdirhash_remove: bad offset"));
+	/* Find the entry */
+	slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, offset);
+
+	/* Remove the hash entry. */
+	ufsdirhash_delslot(dh, slot);
+
+	/* Update the per-block summary info. */
+	ufsdirhash_adjfree(dh, offset, DIRSIZ(0, dirp));
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Change the offset associated with a directory entry in the hash. Used
+ * when compacting directory blocks.
+ */
+void
+ufsdirhash_move(struct inode *ip, struct direct *dirp, doff_t oldoff,
+    doff_t newoff)
+{
+	struct dirhash *dh;
+	int slot;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	DIRHASH_ASSERT(oldoff < dh->dh_dirblks * DIRBLKSIZ &&
+	    newoff < dh->dh_dirblks * DIRBLKSIZ,
+	    ("ufsdirhash_move: bad offset"));
+	/* Find the entry, and update the offset. */
+	slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, oldoff);
+	DH_ENTRY(dh, slot) = newoff;
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Inform dirhash that the directory has grown by one block that
+ * begins at offset (i.e. the new length is offset + DIRBLKSIZ).
+ */
+void
+ufsdirhash_newblk(struct inode *ip, doff_t offset)
+{
+	struct dirhash *dh;
+	int block;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	DIRHASH_ASSERT(offset == dh->dh_dirblks * DIRBLKSIZ,
+	    ("ufsdirhash_newblk: bad offset"));
+	block = offset / DIRBLKSIZ;
+	if (block >= dh->dh_nblk) {
+		/* Out of space; must rebuild. */
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+	dh->dh_dirblks = block + 1;
+
+	/* Account for the new free block. */
+	dh->dh_blkfree[block] = DIRBLKSIZ / DIRALIGN;
+	if (dh->dh_firstfree[DH_NFSTATS] == -1)
+		dh->dh_firstfree[DH_NFSTATS] = block;
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Inform dirhash that the directory is being truncated.
+ */
+void
+ufsdirhash_dirtrunc(struct inode *ip, doff_t offset)
+{
+	struct dirhash *dh;
+	int block, i;
+
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	DIRHASH_ASSERT(offset <= dh->dh_dirblks * DIRBLKSIZ,
+	    ("ufsdirhash_dirtrunc: bad offset"));
+	block = howmany(offset, DIRBLKSIZ);
+	/*
+	 * If the directory shrinks to less than 1/8 of dh_nblk blocks
+	 * (about 20% of its original size due to the 50% extra added in
+	 * ufsdirhash_build) then free it, and let the caller rebuild
+	 * if necessary.
+	 */
+	if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	/*
+	 * Remove any `first free' information pertaining to the
+	 * truncated blocks. All blocks we're removing should be
+	 * completely unused.
+	 */
+	if (dh->dh_firstfree[DH_NFSTATS] >= block)
+		dh->dh_firstfree[DH_NFSTATS] = -1;
+	for (i = block; i < dh->dh_dirblks; i++)
+		if (dh->dh_blkfree[i] != DIRBLKSIZ / DIRALIGN)
+			panic("ufsdirhash_dirtrunc: blocks in use");
+	for (i = 0; i < DH_NFSTATS; i++)
+		if (dh->dh_firstfree[i] >= block)
+			panic("ufsdirhash_dirtrunc: first free corrupt");
+	dh->dh_dirblks = block;
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Debugging function to check that the dirhash information about
+ * a directory block matches its actual contents. Panics if a mismatch
+ * is detected.
+ *
+ * On entry, `buf' should point to the start of an in-core
+ * DIRBLKSIZ-sized directory block, and `offset' should contain the
+ * offset from the start of the directory of that block.
+ */
+void
+ufsdirhash_checkblock(struct inode *ip, char *buf, doff_t offset)
+{
+	struct dirhash *dh;
+	struct direct *dp;
+	int block, ffslot, i, nfree;
+
+	if (!ufs_dirhashcheck)
+		return;
+	if ((dh = ip->i_dirhash) == NULL)
+		return;
+	LOCK(&dh->dh_mtx);
+	if (dh->dh_hash == NULL) {
+		UNLOCK(&dh->dh_mtx);
+		ufsdirhash_free(ip);
+		return;
+	}
+
+	block = offset / DIRBLKSIZ;
+	if ((offset & (DIRBLKSIZ - 1)) != 0 || block >= dh->dh_dirblks)
+		panic("ufsdirhash_checkblock: bad offset");
+
+	nfree = 0;
+	for (i = 0; i < DIRBLKSIZ; i += dp->d_reclen) {
+		dp = (struct direct *)(buf + i);
+		if (dp->d_reclen == 0 || i + dp->d_reclen > DIRBLKSIZ)
+			panic("ufsdirhash_checkblock: bad dir");
+
+		if (dp->d_ino == 0) {
+#if 0
+			/*
+			 * XXX entries with d_ino == 0 should only occur
+			 * at the start of a DIRBLKSIZ block. However the
+			 * ufs code is tolerant of such entries at other
+			 * offsets, and fsck does not fix them.
+			 */
+			if (i != 0)
+				panic("ufsdirhash_checkblock: bad dir inode");
+#endif
+			nfree += dp->d_reclen;
+			continue;
+		}
+
+		/* Check that the entry	exists (will panic if it doesn't). */
+		ufsdirhash_findslot(dh, dp->d_name, dp->d_namlen, offset + i);
+
+		nfree += dp->d_reclen - DIRSIZ(0, dp);
+	}
+	if (i != DIRBLKSIZ)
+		panic("ufsdirhash_checkblock: bad dir end");
+
+	if (dh->dh_blkfree[block] * DIRALIGN != nfree)
+		panic("ufsdirhash_checkblock: bad free count");
+
+	ffslot = BLKFREE2IDX(nfree / DIRALIGN);
+	for (i = 0; i <= DH_NFSTATS; i++)
+		if (dh->dh_firstfree[i] == block && i != ffslot)
+			panic("ufsdirhash_checkblock: bad first-free");
+	if (dh->dh_firstfree[ffslot] == -1)
+		panic("ufsdirhash_checkblock: missing first-free entry");
+	UNLOCK(&dh->dh_mtx);
+}
+
+/*
+ * Hash the specified filename into a dirhash slot.
+ */
+int
+ufsdirhash_hash(struct dirhash *dh, char *name, int namelen)
+{
+	u_int32_t hash;
+
+	/*
+	 * We hash the name and then some other bit of data that is
+	 * invariant over the dirhash's lifetime. Otherwise names
+	 * differing only in the last byte are placed close to one
+	 * another in the table, which is bad for linear probing.
+	 */
+	hash = hash32_buf(name, namelen, HASHINIT);
+	hash = hash32_buf(&dh, sizeof(dh), hash);
+	return (hash % dh->dh_hlen);
+}
+
+/*
+ * Adjust the number of free bytes in the block containing `offset'
+ * by the value specified by `diff'.
+ *
+ * The caller must ensure we have exclusive access to `dh'; normally
+ * that means that dh_mtx should be held, but this is also called
+ * from ufsdirhash_build() where exclusive access can be assumed.
+ */
+void
+ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff)
+{
+	int block, i, nfidx, ofidx;
+
+	/* Update the per-block summary info. */
+	block = offset / DIRBLKSIZ;
+	DIRHASH_ASSERT(block < dh->dh_nblk && block < dh->dh_dirblks,
+	     ("dirhash bad offset"));
+	ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
+	dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
+	nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
+
+	/* Update the `first free' list if necessary. */
+	if (ofidx != nfidx) {
+		/* If removing, scan forward for the next block. */
+		if (dh->dh_firstfree[ofidx] == block) {
+			for (i = block + 1; i < dh->dh_dirblks; i++)
+				if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
+					break;
+			dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
+		}
+
+		/* Make this the new `first free' if necessary */
+		if (dh->dh_firstfree[nfidx] > block ||
+		    dh->dh_firstfree[nfidx] == -1)
+			dh->dh_firstfree[nfidx] = block;
+	}
+}
+
+/*
+ * Find the specified name which should have the specified offset.
+ * Returns a slot number, and panics on failure.
+ *
+ * `dh' must be locked on entry and remains so on return.
+ */
+int
+ufsdirhash_findslot(struct dirhash *dh, char *name, int namelen, doff_t offset)
+{
+	int slot;
+
+	mtx_assert(&dh->dh_mtx, MA_OWNED);
+
+	/* Find the entry. */
+	DIRHASH_ASSERT(dh->dh_hused < dh->dh_hlen, ("dirhash find full"));
+	slot = ufsdirhash_hash(dh, name, namelen);
+	while (DH_ENTRY(dh, slot) != offset &&
+	    DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
+		slot = WRAPINCR(slot, dh->dh_hlen);
+	if (DH_ENTRY(dh, slot) != offset)
+		panic("ufsdirhash_findslot: '%.*s' not found", namelen, name);
+
+	return (slot);
+}
+
+/*
+ * Remove the entry corresponding to the specified slot from the hash array.
+ *
+ * `dh' must be locked on entry and remains so on return.
+ */
+void
+ufsdirhash_delslot(struct dirhash *dh, int slot)
+{
+	int i;
+
+	mtx_assert(&dh->dh_mtx, MA_OWNED);
+
+	/* Mark the entry as deleted. */
+	DH_ENTRY(dh, slot) = DIRHASH_DEL;
+
+	/* If this is the end of a chain of DIRHASH_DEL slots, remove them. */
+	for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
+		i = WRAPINCR(i, dh->dh_hlen);
+	if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
+		i = WRAPDECR(i, dh->dh_hlen);
+		while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
+			DH_ENTRY(dh, i) = DIRHASH_EMPTY;
+			dh->dh_hused--;
+			i = WRAPDECR(i, dh->dh_hlen);
+		}
+		DIRHASH_ASSERT(dh->dh_hused >= 0, ("ufsdirhash_delslot neg hlen"));
+	}
+}
+
+/*
+ * Given a directory entry and its offset, find the offset of the
+ * previous entry in the same DIRBLKSIZ-sized block. Returns an
+ * offset, or -1 if there is no previous entry in the block or some
+ * other problem occurred.
+ */
+doff_t
+ufsdirhash_getprev(struct direct *dirp, doff_t offset)
+{
+	struct direct *dp;
+	char *blkbuf;
+	doff_t blkoff, prevoff;
+	int entrypos, i;
+
+	blkoff = offset & ~(DIRBLKSIZ - 1);	/* offset of start of block */
+	entrypos = offset & (DIRBLKSIZ - 1);	/* entry relative to block */
+	blkbuf = (char *)dirp - entrypos;
+	prevoff = blkoff;
+
+	/* If `offset' is the start of a block, there is no previous entry. */
+	if (entrypos == 0)
+		return (-1);
+
+	/* Scan from the start of the block until we get to the entry. */
+	for (i = 0; i < entrypos; i += dp->d_reclen) {
+		dp = (struct direct *)(blkbuf + i);
+		if (dp->d_reclen == 0 || i + dp->d_reclen > entrypos)
+			return (-1);	/* Corrupted directory. */
+		prevoff = blkoff + i;
+	}
+	return (prevoff);
+}
+
+/*
+ * Try to free up `wanted' bytes by stealing memory from existing
+ * dirhashes. Returns zero with ufsdirhash_mtx locked if successful.
+ */
+int
+ufsdirhash_recycle(int wanted)
+{
+	struct dirhash *dh;
+	doff_t **hash;
+	u_int8_t *blkfree;
+	int i, mem, narrays;
+
+	LOCK(&ufsdirhash_mtx);
+	while (wanted + ufs_dirhashmem > ufs_dirhashmaxmem) {
+		/* Find a dirhash, and lock it. */
+		if ((dh = TAILQ_FIRST(&ufsdirhash_list)) == NULL) {
+			UNLOCK(&ufsdirhash_mtx);
+			return (-1);
+		}
+		LOCK(&dh->dh_mtx);
+		DIRHASH_ASSERT(dh->dh_hash != NULL, ("dirhash: NULL hash on list"));
+
+		/* Decrement the score; only recycle if it becomes zero. */
+		if (--dh->dh_score > 0) {
+			UNLOCK(&dh->dh_mtx);
+			UNLOCK(&ufsdirhash_mtx);
+			return (-1);
+		}
+
+		/* Remove it from the list and detach its memory. */
+		TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
+		dh->dh_onlist = 0;
+		hash = dh->dh_hash;
+		dh->dh_hash = NULL;
+		blkfree = dh->dh_blkfree;
+		dh->dh_blkfree = NULL;
+		narrays = dh->dh_narrays;
+		mem = narrays * sizeof(*dh->dh_hash) +
+		    narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
+		    dh->dh_nblk * sizeof(*dh->dh_blkfree);
+
+		/* Unlock everything, free the detached memory. */
+		UNLOCK(&dh->dh_mtx);
+		UNLOCK(&ufsdirhash_mtx);
+		for (i = 0; i < narrays; i++)
+			DIRHASH_FREE(hash[i]);
+		FREE(hash, M_DIRHASH);
+		FREE(blkfree, M_DIRHASH);
+
+		/* Account for the returned memory, and repeat if necessary. */
+		LOCK(&ufsdirhash_mtx);
+		ufs_dirhashmem -= mem;
+	}
+	/* Success; return with ufsdirhash_mtx locked. */
+	return (0);
+}
+
+
+void
+ufsdirhash_init()
+{
+#ifdef __FreeBSD__
+	ufsdirhash_zone = uma_zcreate("DIRHASH", DH_NBLKOFF * sizeof(doff_t),
+	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
+	mtx_init(&ufsdirhash_mtx, "dirhash list", NULL, MTX_DEF);
+#else
+	pool_init(&ufsdirhash_pool, DH_NBLKOFF * sizeof(doff_t), 0, 0, 0,
+	    "dirhash", &pool_allocator_nointr);
+	rw_init(&ufsdirhash_mtx);
+#endif
+	TAILQ_INIT(&ufsdirhash_list);
+}
+
+void
+ufsdirhash_uninit()
+{
+	DIRHASH_ASSERT(TAILQ_EMPTY(&ufsdirhash_list), ("ufsdirhash_uninit"));
+#ifdef __FreeBSD__
+	uma_zdestroy(ufsdirhash_zone);
+	mtx_destroy(&ufsdirhash_mtx);
+#else
+	pool_destroy(&ufsdirhash_pool);
+#endif
+}
diff --git a/sys/ufs/ufs/ufs_inode.c b/sys/ufs/ufs/ufs_inode.c
index 0415e2c03a9..6dc9cb11614 100644
--- a/sys/ufs/ufs/ufs_inode.c
+++ b/sys/ufs/ufs/ufs_inode.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ufs_inode.c,v 1.19 2003/06/02 23:28:23 millert Exp $	*/
+/*	$OpenBSD: ufs_inode.c,v 1.20 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: ufs_inode.c,v 1.7 1996/05/11 18:27:52 mycroft Exp $	*/
 
 /*
@@ -51,6 +51,10 @@
 #include <ufs/ufs/inode.h>
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ufs/ufs_extern.h>
+#ifdef UFS_DIRHASH
+#include <ufs/ufs/dir.h>
+#include <ufs/ufs/dirhash.h>
+#endif
 
 u_long	nextgennumber;		/* Next generation number to assign. */
 
@@ -145,6 +149,10 @@ ufs_reclaim(vp, p)
 		vrele(ip->i_devvp);
 		ip->i_devvp = 0;
 	}
+#ifdef UFS_DIRHASH
+	if (ip->i_dirhash != NULL)
+		ufsdirhash_free(ip);
+#endif
 	ufs_quota_delete(ip);
 	return (0);
 }
diff --git a/sys/ufs/ufs/ufs_lookup.c b/sys/ufs/ufs/ufs_lookup.c
index 3595fc22c41..ea0619097ed 100644
--- a/sys/ufs/ufs/ufs_lookup.c
+++ b/sys/ufs/ufs/ufs_lookup.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ufs_lookup.c,v 1.22 2003/06/02 23:28:23 millert Exp $	*/
+/*	$OpenBSD: ufs_lookup.c,v 1.23 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: ufs_lookup.c,v 1.7 1996/02/09 22:36:06 christos Exp $	*/
 
 /*
@@ -53,6 +53,9 @@
 #include <ufs/ufs/quota.h>
 #include <ufs/ufs/inode.h>
 #include <ufs/ufs/dir.h>
+#ifdef UFS_DIRHASH
+#include <ufs/ufs/dirhash.h>
+#endif
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ufs/ufs_extern.h>
 
@@ -195,6 +198,47 @@ ufs_lookup(v)
 	 * of simplicity.
 	 */
 	bmask = VFSTOUFS(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
+
+#ifdef UFS_DIRHASH
+	/*
+	 * Use dirhash for fast operations on large directories. The logic
+	 * to determine whether to hash the directory is contained within
+	 * ufsdirhash_build(); a zero return means that it decided to hash
+	 * this directory and it successfully built up the hash table.
+	 */
+	if (ufsdirhash_build(dp) == 0) {
+		/* Look for a free slot if needed. */
+		enduseful = dp->i_size;
+		if (slotstatus != FOUND) {
+			slotoffset = ufsdirhash_findfree(dp, slotneeded,
+			    &slotsize);
+			if (slotoffset >= 0) {
+				slotstatus = COMPACT;
+				enduseful = ufsdirhash_enduseful(dp);
+				if (enduseful < 0)
+					enduseful = dp->i_size;
+			}
+		}
+		/* Look up the component. */
+		numdirpasses = 1;
+		entryoffsetinblock = 0; /* silence compiler warning */
+		switch (ufsdirhash_lookup(dp, cnp->cn_nameptr, cnp->cn_namelen,
+		    &dp->i_offset, &bp, nameiop == DELETE ? &prevoff : NULL)) {
+		case 0:
+			ep = (struct direct *)((char *)bp->b_data +
+			    (dp->i_offset & bmask));
+			goto foundentry;
+		case ENOENT:
+#define roundup2(x, y)	(((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
+			dp->i_offset = roundup2(dp->i_size, DIRBLKSIZ);
+			goto notfound;
+		default:
+			/* Something failed; just do a linear search. */
+			break;
+		}
+	}
+#endif /* UFS_DIRHASH */
+
 	if (nameiop != LOOKUP || dp->i_diroff == 0 ||
 	    dp->i_diroff >= dp->i_ffs_size) {
 		entryoffsetinblock = 0;
@@ -298,6 +342,9 @@ searchloop:
 			if (namlen == cnp->cn_namelen &&
 			    !bcmp(cnp->cn_nameptr, ep->d_name,
 				(unsigned)namlen)) {
+#ifdef UFS_DIRHASH
+foundentry:
+#endif
 				/*
 				 * Save directory entry's inode number and
 				 * reclen in ndp->ni_ufs area, and release
@@ -739,6 +786,16 @@ ufs_direnter(dvp, tvp, dirp, cnp, newdirbp)
 		blkoff = dp->i_offset &
 		    (VFSTOUFS(dvp->v_mount)->um_mountp->mnt_stat.f_iosize - 1);
 		bcopy((caddr_t)dirp, (caddr_t)bp->b_data + blkoff,newentrysize);
+
+#ifdef UFS_DIRHASH
+		if (dp->i_dirhash != NULL) {
+			ufsdirhash_newblk(dp, dp->i_offset);
+			ufsdirhash_add(dp, dirp, dp->i_offset);
+			ufsdirhash_checkblock(dp, (char *)bp->b_data + blkoff,
+			dp->i_offset);
+		}
+#endif
+
 		if (DOINGSOFTDEP(dvp)) {
 			/*
 			 * Ensure that the entire newly allocated block is a
@@ -813,6 +870,12 @@ ufs_direnter(dvp, tvp, dirp, cnp, newdirbp)
 		dsize = DIRSIZ(FSFMT(dvp), nep);
 		spacefree += nep->d_reclen - dsize;
 		loc += nep->d_reclen;
+#ifdef UFS_DIRHASH
+		if (dp->i_dirhash != NULL)
+			ufsdirhash_move(dp, nep,
+			    dp->i_offset + ((char *)nep - dirbuf),
+			    dp->i_offset + ((char *)ep - dirbuf));
+#endif
  		if (DOINGSOFTDEP(dvp))
  			softdep_change_directoryentry_offset(dp, dirbuf,
  			    (caddr_t)nep, (caddr_t)ep, dsize); 
@@ -836,7 +899,19 @@ ufs_direnter(dvp, tvp, dirp, cnp, newdirbp)
 		ep->d_reclen = dsize;
 		ep = (struct direct *)((char *)ep + dsize);
 	}
+
+#ifdef UFS_DIRHASH
+	if (dp->i_dirhash != NULL && (ep->d_ino == 0 ||
+	    dirp->d_reclen == spacefree))
+		ufsdirhash_add(dp, dirp, dp->i_offset + ((char *)ep - dirbuf));
+#endif
 	bcopy((caddr_t)dirp, (caddr_t)ep, (u_int)newentrysize);
+#ifdef UFS_DIRHASH
+	if (dp->i_dirhash != NULL)
+		ufsdirhash_checkblock(dp, dirbuf -
+		    (dp->i_offset & (DIRBLKSIZ - 1)),
+		    dp->i_offset & ~(DIRBLKSIZ - 1));
+#endif
 
   	if (DOINGSOFTDEP(dvp)) {
   		softdep_setup_directory_add(bp, dp,
@@ -856,8 +931,13 @@ ufs_direnter(dvp, tvp, dirp, cnp, newdirbp)
  	 */
 
 	if (error == 0 && dp->i_endoff && dp->i_endoff < dp->i_ffs_size) {
-	        if (tvp != NULL)
+		if (tvp != NULL)
 			VOP_UNLOCK(tvp, 0, p);
+#ifdef UFS_DIRHASH
+		if (dp->i_dirhash != NULL)
+			ufsdirhash_dirtrunc(dp, dp->i_endoff);
+#endif
+
 
 		error = UFS_TRUNCATE(dp, (off_t)dp->i_endoff, IO_SYNC, cr);
 
@@ -906,9 +986,18 @@ ufs_dirremove(dvp, ip, flags, isrmdir)
 		goto out;
 	}
 
- 	if ((error = UFS_BUFATOFF(dp,
- 	    (off_t)(dp->i_offset - dp->i_count), (char **)&ep, &bp)) != 0)
- 		return (error);
+	if ((error = UFS_BUFATOFF(dp,
+	    (off_t)(dp->i_offset - dp->i_count), (char **)&ep, &bp)) != 0)
+		return (error);
+#ifdef UFS_DIRHASH
+	/*
+	 * Remove the dirhash entry. This is complicated by the fact
+	 * that `ep' is the previous entry when dp->i_count != 0.
+	 */
+	if (dp->i_dirhash != NULL)
+		ufsdirhash_remove(dp, (dp->i_count == 0) ? ep :
+		(struct direct *)((char *)ep + ep->d_reclen), dp->i_offset);
+#endif
 
 	if (dp->i_count == 0) {
 		/*
@@ -921,6 +1010,12 @@ ufs_dirremove(dvp, ip, flags, isrmdir)
  		 */
  		ep->d_reclen += dp->i_reclen;
 	}
+#ifdef UFS_DIRHASH
+	if (dp->i_dirhash != NULL)
+		ufsdirhash_checkblock(dp, (char *)ep -
+		    ((dp->i_offset - dp->i_count) & (DIRBLKSIZ - 1)),
+		    dp->i_offset & ~(DIRBLKSIZ - 1));
+#endif
 out:
  	if (DOINGSOFTDEP(dvp)) {
 		if (ip) {
diff --git a/sys/ufs/ufs/ufs_vfsops.c b/sys/ufs/ufs/ufs_vfsops.c
index 9c0e6db5a6a..6996edcd761 100644
--- a/sys/ufs/ufs/ufs_vfsops.c
+++ b/sys/ufs/ufs/ufs_vfsops.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ufs_vfsops.c,v 1.10 2003/06/02 23:28:23 millert Exp $	*/
+/*	$OpenBSD: ufs_vfsops.c,v 1.11 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: ufs_vfsops.c,v 1.4 1996/02/09 22:36:12 christos Exp $	*/
 
 /*
@@ -52,6 +52,10 @@
 #include <ufs/ufs/inode.h>
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ufs/ufs_extern.h>
+#ifdef UFS_DIRHASH
+#include <ufs/ufs/dir.h>
+#include <ufs/ufs/dirhash.h>
+#endif
 
 /*
  * Make a filesystem operational.
@@ -125,6 +129,9 @@ ufs_init(vfsp)
 	done = 1;
 	ufs_ihashinit();
 	ufs_quota_init();
+#ifdef UFS_DIRHASH
+	ufsdirhash_init();
+#endif
 
 	return (0);
 }
diff --git a/sys/ufs/ufs/ufs_vnops.c b/sys/ufs/ufs/ufs_vnops.c
index 4169076450e..c350bdc1dd4 100644
--- a/sys/ufs/ufs/ufs_vnops.c
+++ b/sys/ufs/ufs/ufs_vnops.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ufs_vnops.c,v 1.53 2003/12/17 02:43:25 tedu Exp $	*/
+/*	$OpenBSD: ufs_vnops.c,v 1.54 2003/12/28 17:20:16 tedu Exp $	*/
 /*	$NetBSD: ufs_vnops.c,v 1.18 1996/05/11 18:28:04 mycroft Exp $	*/
 
 /*
@@ -66,6 +66,9 @@
 #include <ufs/ufs/dir.h>
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ufs/ufs_extern.h>
+#ifdef UFS_DIRHASH
+#include <ufs/ufs/dirhash.h>
+#endif
 #include <ufs/ext2fs/ext2fs_extern.h>
 
 static int ufs_chmod(struct vnode *, int, struct ucred *, struct proc *);
@@ -1483,6 +1486,12 @@ ufs_rmdir(v)
 		error = UFS_TRUNCATE(ip, (off_t)0, ioflag, cnp->cn_cred);
 	}
 	cache_purge(vp);
+#ifdef UFS_DIRHASH
+	/* Kill any active hash; i_effnlink == 0, so it will not come back. */
+	if (ip->i_dirhash != NULL)
+		ufsdirhash_free(ip);
+#endif
+
 out:
 	VN_KNOTE(vp, NOTE_DELETE);
         vput(dvp);