Two minor changes to dirhash, which result in some marginal benchmark

improvements.

1) If deleting an entry results in a chain of deleted slots ending in an
   empty slot, then we can be a bit more aggressive about marking slots as
   empty.

2) The last stage of the FNV hash is to xor the last byte of data
   into the hash. This means that filenames which differ only in
   the last byte will be placed close to one another in the hash
   table, which forms longer chains. To work around this common
   case, we also hash in the address of the dirhash structure.

     news/cancel = news/articles/control/cancel for a tradspool inn server
     squid2 = squid level 2 directory (dirs called 00->FF)
     squid3 = squid level 3 directory (files called 00001F00->00001FFF)

                             mean #probes for
                  home dir  mh inbox  news/cancel  tmp    squid2  squid3
old   successful  1.02      3.19      4.07         1.10    7.85   2.06
new   successful  1.04      1.32      1.27         1.04    1.93   1.17

old unsuccessful  1.08      4.50      5.37         1.17   10.76   2.69
new unsuccessful  1.08      1.73      1.64         1.17    2.89   1.37

Reviewed by:	iedowse
MFC after:	2 weeks

1 files changed, 15 insertions, 3 deletions

diff --git a/sys/ufs/ufs/ufs_dirhash.c b/sys/ufs/ufs/ufs_dirhash.c
index 9409165..be9d600 100644
--- a/sys/ufs/ufs/ufs_dirhash.c
+++ b/sys/ufs/ufs/ufs_dirhash.c
@@ -56,6 +56,7 @@
 #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))
 
@@ -862,7 +863,17 @@ ufsdirhash_checkblock(struct inode *ip, char *buf, doff_t offset)
 static int
 ufsdirhash_hash(struct dirhash *dh, char *name, int namelen)
 {
-	return (fnv_32_buf(name, namelen, FNV1_32_INIT) % dh->dh_hlen);
+	u_int32_t hash;
+
+	/*
+	 * We hash the name and then some ofther bit of data which is
+	 * invarient 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 = fnv_32_buf(name, namelen, FNV1_32_INIT);
+	hash = fnv_32_buf(dh, sizeof(dh), hash);
+	return (hash % dh->dh_hlen);
 }
 
 /*
@@ -947,10 +958,11 @@ ufsdirhash_delslot(struct dirhash *dh, int slot)
 	for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
 		i = WRAPINCR(i, dh->dh_hlen);
 	if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
-		for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; ) {
+		i = WRAPDECR(i, dh->dh_hlen);
+		while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
 			DH_ENTRY(dh, i) = DIRHASH_EMPTY;
 			dh->dh_hused--;
-			i = WRAPINCR(i, dh->dh_hlen);
+			i = WRAPDECR(i, dh->dh_hlen);
 		}
 		KASSERT(dh->dh_hused >= 0, ("ufsdirhash_delslot neg hlen"));
 	}