From 670e711dd19510316ecaa1f30d78f16ba66492f6 Mon Sep 17 00:00:00 2001 From: peter Date: Sat, 17 Mar 2001 09:31:06 +0000 Subject: 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. --- sys/alpha/include/types.h | 2 +- sys/i386/include/types.h | 2 +- sys/ia64/include/types.h | 2 +- sys/kern/vfs_cache.c | 19 ++++-------- sys/nfs/nfs.h | 1 - sys/nfs/nfs_node.c | 30 ++----------------- sys/nfsclient/nfs.h | 1 - sys/nfsclient/nfs_node.c | 30 ++----------------- sys/nfsclient/nfsargs.h | 1 - sys/nfsclient/nfsstats.h | 1 - sys/nfsserver/nfs.h | 1 - sys/nfsserver/nfsrvstats.h | 1 - sys/powerpc/include/types.h | 1 + sys/sys/fnv_hash.h | 72 +++++++++++++++++++++++++++++++++++++++++++++ 14 files changed, 86 insertions(+), 78 deletions(-) create mode 100644 sys/sys/fnv_hash.h 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 #include #include +#include /* * 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 #include #include +#include #include @@ -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 #include #include +#include #include @@ -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; +} -- cgit v1.1