From e0fe7f7124b88be1a6f4e1f21706133e107332a9 Mon Sep 17 00:00:00 2001 From: peter Date: Sat, 17 Mar 2001 05:43:01 +0000 Subject: Dramatically improve the **lame** nfs_hash(). This is based on the Fowler / Noll / Vo Hash (http://www.isthe.com/chongo/tech/comp/fnv/). This improves hash coverage a *massive* amount. We were seeing one set of machines that were using 0.84% of their 131072 entry nfsnode hash buckets with maximum chain lengths of up to ~500 entries. The machine was spending nearly 100% of its time in 'system'. A test with this has pushed the coverage from a few perCent up to 91% utilization with a max chain length of 11. Submitted by: David Filo --- sys/nfs/nfs_node.c | 24 ++++++++++++++++-------- sys/nfsclient/nfs_node.c | 24 ++++++++++++++++-------- 2 files changed, 32 insertions(+), 16 deletions(-) diff --git a/sys/nfs/nfs_node.c b/sys/nfs/nfs_node.c index 1ede795..365d7f2 100644 --- a/sys/nfs/nfs_node.c +++ b/sys/nfs/nfs_node.c @@ -73,21 +73,29 @@ 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) - register nfsfh_t *fhp; + nfsfh_t *fhp; int fhsize; { - register u_char *fhpp; - register u_long fhsum; - register int i; + u_char *fhpp; + u_int32_t hval; + int i; fhpp = &fhp->fh_bytes[0]; - fhsum = 0; - for (i = 0; i < fhsize; i++) - fhsum += *fhpp++; - return (fhsum); + hval = FNV1_32_INIT; + for (i = 0; i < fhsize; i++) { + hval *= FNV_32_PRIME; + hval ^= (u_int32_t)*fhpp++; + } + return (hval); } /* diff --git a/sys/nfsclient/nfs_node.c b/sys/nfsclient/nfs_node.c index 1ede795..365d7f2 100644 --- a/sys/nfsclient/nfs_node.c +++ b/sys/nfsclient/nfs_node.c @@ -73,21 +73,29 @@ 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) - register nfsfh_t *fhp; + nfsfh_t *fhp; int fhsize; { - register u_char *fhpp; - register u_long fhsum; - register int i; + u_char *fhpp; + u_int32_t hval; + int i; fhpp = &fhp->fh_bytes[0]; - fhsum = 0; - for (i = 0; i < fhsize; i++) - fhsum += *fhpp++; - return (fhsum); + hval = FNV1_32_INIT; + for (i = 0; i < fhsize; i++) { + hval *= FNV_32_PRIME; + hval ^= (u_int32_t)*fhpp++; + } + return (hval); } /* -- cgit v1.1