Use a generic implementation of the Fowler/Noll/Vo hash (FNV hash).

Make the name cache hash as well as the nfsnode hash use it.

As a special tweak, create an unsigned version of register_t.  This allows
us to use a special tweak for the 64 bit versions that significantly
speeds up the i386 version (ie: int64 XOR int64 is slower than int64
XOR int32).

The code layout is a little strange for the string function, but I was
able to get between 5 to 10% improvement over the original version I
started with. The layout affects gcc code generation choices and this way
was fastest on x86 and alpha.

Note that 'CPUTYPE=p3' etc makes a fair difference to this.  It is
around 45% faster with -march=pentiumpro on a p6 cpu.

14 files changed, 86 insertions, 78 deletions

diff --git a/sys/alpha/include/types.h b/sys/alpha/include/types.h
index 087c175..8ca3c6b 100644
--- a/sys/alpha/include/types.h
+++ b/sys/alpha/include/types.h
@@ -56,8 +56,8 @@ typedef	long		vm_ooffset_t;
 typedef	unsigned long	vm_pindex_t;
 typedef	unsigned long	vm_size_t;
 
-
 typedef __int64_t		register_t;
+typedef __uint64_t		u_register_t;
 
 #ifdef _KERNEL
 typedef	long		intfptr_t;
diff --git a/sys/i386/include/types.h b/sys/i386/include/types.h
index 91428c6..7063a04 100644
--- a/sys/i386/include/types.h
+++ b/sys/i386/include/types.h
@@ -53,7 +53,7 @@ typedef	unsigned int	vm_pindex_t;
 typedef	unsigned int	vm_size_t;
 
 typedef	__int32_t	register_t;
-
+typedef	__uint32_t	u_register_t;
 
 #ifdef _KERNEL
 typedef	int		intfptr_t;
diff --git a/sys/ia64/include/types.h b/sys/ia64/include/types.h
index ccb7793..f8235a2 100644
--- a/sys/ia64/include/types.h
+++ b/sys/ia64/include/types.h
@@ -56,8 +56,8 @@ typedef	long		vm_ooffset_t;
 typedef	unsigned long	vm_pindex_t;
 typedef	unsigned long	vm_size_t;
 
-
 typedef __int64_t		register_t;
+typedef __uint64_t		u_register_t;
 
 #ifdef _KERNEL
 typedef	long		intfptr_t;
diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c
index 6657523..3f92c8f 100644
--- a/sys/kern/vfs_cache.c
+++ b/sys/kern/vfs_cache.c
@@ -48,6 +48,7 @@
 #include <sys/sysproto.h>
 #include <sys/proc.h>
 #include <sys/filedesc.h>
+#include <sys/fnv_hash.h>
 
 /*
  * This structure describes the elements in the cache of recent
@@ -180,9 +181,7 @@ cache_lookup(dvp, vpp, cnp)
 	struct componentname *cnp;
 {
 	struct namecache *ncp;
-	u_long hash;
-	u_char *cp;
-	int len;
+	u_int32_t hash;
 
 	if (!doingcache) {
 		cnp->cn_flags &= ~MAKEENTRY;
@@ -209,10 +208,7 @@ cache_lookup(dvp, vpp, cnp)
 		}
 	}
 
-	hash = 0;
-	len = cnp->cn_namelen;
-	for (cp = cnp->cn_nameptr; len; len--, cp++)
-		hash += *cp;
+	hash = fnv32_hashbuf(cnp->cn_nameptr, cnp->cn_namelen);
 	LIST_FOREACH(ncp, (NCHHASH(dvp, hash)), nc_hash) {
 		numchecks++;
 		if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen &&
@@ -279,8 +275,7 @@ cache_enter(dvp, vp, cnp)
 {
 	struct namecache *ncp;
 	struct nchashhead *ncpp;
-	u_long hash;
-	u_char *cp, *dp;
+	u_int32_t hash;
 	int len;
 
 	if (!doingcache)
@@ -323,10 +318,8 @@ cache_enter(dvp, vp, cnp)
 	ncp->nc_vp = vp;
 	ncp->nc_dvp = dvp;
 	len = ncp->nc_nlen = cnp->cn_namelen;
-	hash = 0;
-	dp = ncp->nc_name;
-	for (cp = cnp->cn_nameptr; len; len--, cp++, dp++)
-		hash += (*dp = *cp);
+	hash = fnv32_hashbuf(cnp->cn_nameptr, len);
+	bcopy(cnp->cn_nameptr, ncp->nc_name, len);
 	ncpp = NCHHASH(dvp, hash);
 	LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
 	if (LIST_EMPTY(&dvp->v_cache_src))
diff --git a/sys/nfs/nfs.h b/sys/nfs/nfs.h
index 6423e5a..259ec20 100644
--- a/sys/nfs/nfs.h
+++ b/sys/nfs/nfs.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/nfs/nfs_node.c b/sys/nfs/nfs_node.c
index 365d7f2..450729d 100644
--- a/sys/nfs/nfs_node.c
+++ b/sys/nfs/nfs_node.c
@@ -44,6 +44,7 @@
 #include <sys/namei.h>
 #include <sys/vnode.h>
 #include <sys/malloc.h>
+#include <sys/fnv_hash.h>
 
 #include <vm/vm_zone.h>
 
@@ -72,33 +73,6 @@ nfs_nhinit()
 }
 
 /*
- * Compute an entry in the NFS hash table structure
- *
- * Hash based on: http://www.isthe.com/chongo/tech/comp/fnv/
- * by Glenn Fowler, Phong Vo and Landon Curt Noll
- * aka the "Fowler / Noll / Vo Hash" (FNV)
- */
-#define FNV_32_PRIME ((u_int32_t) 0x01000193UL)
-#define FNV1_32_INIT ((u_int32_t) 33554467UL)
-u_long
-nfs_hash(fhp, fhsize)
-	nfsfh_t *fhp;
-	int fhsize;
-{
-	u_char *fhpp;
-	u_int32_t hval;
-	int i;
-
-	fhpp = &fhp->fh_bytes[0];
-	hval = FNV1_32_INIT;
-	for (i = 0; i < fhsize; i++) {
-		hval *= FNV_32_PRIME;
-		hval ^= (u_int32_t)*fhpp++;
-	}
-	return (hval);
-}
-
-/*
  * Look up a vnode/nfsnode by file handle.
  * Callers must check for mount points!!
  * In all cases, a pointer to a
@@ -133,7 +107,7 @@ nfs_nget(mntp, fhp, fhsize, npp)
 		rsflags = 0;
 
 retry:
-	nhpp = NFSNOHASH(nfs_hash(fhp, fhsize));
+	nhpp = NFSNOHASH(fnv32_hashbuf(fhp->fh_bytes, fhsize));
 loop:
 	for (np = nhpp->lh_first; np != 0; np = np->n_hash.le_next) {
 		if (mntp != NFSTOV(np)->v_mount || np->n_fhsize != fhsize ||
diff --git a/sys/nfsclient/nfs.h b/sys/nfsclient/nfs.h
index 6423e5a..259ec20 100644
--- a/sys/nfsclient/nfs.h
+++ b/sys/nfsclient/nfs.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/nfsclient/nfs_node.c b/sys/nfsclient/nfs_node.c
index 365d7f2..450729d 100644
--- a/sys/nfsclient/nfs_node.c
+++ b/sys/nfsclient/nfs_node.c
@@ -44,6 +44,7 @@
 #include <sys/namei.h>
 #include <sys/vnode.h>
 #include <sys/malloc.h>
+#include <sys/fnv_hash.h>
 
 #include <vm/vm_zone.h>
 
@@ -72,33 +73,6 @@ nfs_nhinit()
 }
 
 /*
- * Compute an entry in the NFS hash table structure
- *
- * Hash based on: http://www.isthe.com/chongo/tech/comp/fnv/
- * by Glenn Fowler, Phong Vo and Landon Curt Noll
- * aka the "Fowler / Noll / Vo Hash" (FNV)
- */
-#define FNV_32_PRIME ((u_int32_t) 0x01000193UL)
-#define FNV1_32_INIT ((u_int32_t) 33554467UL)
-u_long
-nfs_hash(fhp, fhsize)
-	nfsfh_t *fhp;
-	int fhsize;
-{
-	u_char *fhpp;
-	u_int32_t hval;
-	int i;
-
-	fhpp = &fhp->fh_bytes[0];
-	hval = FNV1_32_INIT;
-	for (i = 0; i < fhsize; i++) {
-		hval *= FNV_32_PRIME;
-		hval ^= (u_int32_t)*fhpp++;
-	}
-	return (hval);
-}
-
-/*
  * Look up a vnode/nfsnode by file handle.
  * Callers must check for mount points!!
  * In all cases, a pointer to a
@@ -133,7 +107,7 @@ nfs_nget(mntp, fhp, fhsize, npp)
 		rsflags = 0;
 
 retry:
-	nhpp = NFSNOHASH(nfs_hash(fhp, fhsize));
+	nhpp = NFSNOHASH(fnv32_hashbuf(fhp->fh_bytes, fhsize));
 loop:
 	for (np = nhpp->lh_first; np != 0; np = np->n_hash.le_next) {
 		if (mntp != NFSTOV(np)->v_mount || np->n_fhsize != fhsize ||
diff --git a/sys/nfsclient/nfsargs.h b/sys/nfsclient/nfsargs.h
index 6423e5a..259ec20 100644
--- a/sys/nfsclient/nfsargs.h
+++ b/sys/nfsclient/nfsargs.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/nfsclient/nfsstats.h b/sys/nfsclient/nfsstats.h
index 6423e5a..259ec20 100644
--- a/sys/nfsclient/nfsstats.h
+++ b/sys/nfsclient/nfsstats.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/nfsserver/nfs.h b/sys/nfsserver/nfs.h
index 6423e5a..259ec20 100644
--- a/sys/nfsserver/nfs.h
+++ b/sys/nfsserver/nfs.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/nfsserver/nfsrvstats.h b/sys/nfsserver/nfsrvstats.h
index 6423e5a..259ec20 100644
--- a/sys/nfsserver/nfsrvstats.h
+++ b/sys/nfsserver/nfsrvstats.h
@@ -633,7 +633,6 @@ int	nfs_savenickauth __P((struct nfsmount *, struct ucred *, int,
 int	nfs_adv __P((struct mbuf **, caddr_t *, int, int));
 void	nfs_nhinit __P((void));
 void	nfs_timer __P((void*));
-u_long	nfs_hash __P((nfsfh_t *, int));
 int	nfsrv_dorec __P((struct nfssvc_sock *, struct nfsd *, 
 			 struct nfsrv_descript **));
 int	nfsrv_getcache __P((struct nfsrv_descript *, struct nfssvc_sock *,
diff --git a/sys/powerpc/include/types.h b/sys/powerpc/include/types.h
index 50514ac..4231ab0 100644
--- a/sys/powerpc/include/types.h
+++ b/sys/powerpc/include/types.h
@@ -55,6 +55,7 @@ typedef	unsigned int	vm_pindex_t;
 typedef	unsigned int	vm_size_t;
 
 typedef __int32_t	register_t;
+typedef __uint32_t	u_register_t;
 
 #ifdef _KERNEL
 typedef	int		intfptr_t;
diff --git a/sys/sys/fnv_hash.h b/sys/sys/fnv_hash.h
new file mode 100644
index 0000000..50d2003
--- /dev/null
+++ b/sys/sys/fnv_hash.h
@@ -0,0 +1,72 @@
+/*
+ * Fowler / Noll / Vo Hash (FNV Hash)
+ * http://www.isthe.com/chongo/tech/comp/fnv/
+ *
+ * This is an implementation of the algorithms posted above.
+ * This file is placed in the public domain by Peter Wemm.
+ *
+ * $FreeBSD$
+ */
+
+#define FNV_32_PRIME ((u_int32_t) 0x01000193UL)
+#define FNV1_32_INIT ((u_int32_t) 33554467UL)
+
+#define FNV_64_PRIME ((u_int64_t) 0x100000001b3ULL)
+#define FNV1_64_INIT ((u_int64_t) 0xcbf29ce484222325ULL)
+
+static __inline u_int32_t
+fnv32_hashbuf(const void *buf, size_t len)
+{
+	const u_int8_t *s = (const u_int8_t *)buf;
+	u_int32_t hval;
+
+	hval = FNV1_32_INIT;
+	while (len-- != 0) {
+		hval *= FNV_32_PRIME;
+		hval ^= *s++;
+	}
+	return hval;
+}
+
+static __inline u_int32_t
+fnv32_hashstr(const char *str)
+{
+	const u_int8_t *s = (const u_int8_t *)str;
+	u_int32_t hval, c;
+
+	hval = FNV1_32_INIT;
+	while ((c = *s++) != 0) {
+		hval *= FNV_32_PRIME;
+		hval ^= c;
+	}
+	return hval;
+}
+
+static __inline u_int64_t
+fnv64_hashbuf(const void *buf, size_t len)
+{
+	const u_int8_t *s = (const u_int8_t *)buf;
+	u_int64_t hval;
+
+	hval = FNV1_64_INIT;
+	while (len-- != 0) {
+		hval *= FNV_64_PRIME;
+		hval ^= *s++;
+	}
+	return hval;
+}
+
+static __inline u_int64_t
+fnv64_hashstr(const char *str)
+{
+	const u_int8_t *s = (const u_int8_t *)str;
+	u_int64_t hval;
+	u_register_t c;		 /* 32 bit on i386, 64 bit on alpha,ia64 */
+
+	hval = FNV1_64_INIT;
+	while ((c = *s++) != 0) {
+		hval *= FNV_64_PRIME;
+		hval ^= c;
+	}
+	return hval;
+}