From 266cea85ee85a1343c8d97993dc1f12fadb5db16 Mon Sep 17 00:00:00 2001 From: peter Date: Tue, 20 Mar 2001 02:10:18 +0000 Subject: Use the same API as the example code. Allow the initial hash value to be passed in, as the examples do. Incrementally hash in the dvp->v_id (using the official api) rather than add it. This seems to help power-of-two predictable filename trees where the filenames repeat on a power-of-two cycle and the directory trees have power-of-two components in it. The simple add then mask was causing things like 12000+ entry collision chains while most other entries have between 0 and 3 entries each. This way seems to improve things. --- sys/kern/vfs_cache.c | 14 ++++++++------ sys/nfs/nfs_node.c | 2 +- sys/nfsclient/nfs_node.c | 2 +- sys/sys/fnv_hash.h | 36 ++++++++++++++++-------------------- 4 files changed, 26 insertions(+), 28 deletions(-) diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c index 3f92c8f..3459917 100644 --- a/sys/kern/vfs_cache.c +++ b/sys/kern/vfs_cache.c @@ -86,8 +86,8 @@ struct namecache { /* * Structures associated with name cacheing. */ -#define NCHHASH(dvp, hash) \ - (&nchashtbl[((dvp)->v_id + (hash)) & nchash]) +#define NCHHASH(hash) \ + (&nchashtbl[(hash) & nchash]) static LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */ static TAILQ_HEAD(, namecache) ncneg; /* Hash Table */ static u_long nchash; /* size of hash table */ @@ -208,8 +208,9 @@ cache_lookup(dvp, vpp, cnp) } } - hash = fnv32_hashbuf(cnp->cn_nameptr, cnp->cn_namelen); - LIST_FOREACH(ncp, (NCHHASH(dvp, hash)), nc_hash) { + hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT); + hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash); + LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) { numchecks++; if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen && !bcmp(ncp->nc_name, cnp->cn_nameptr, ncp->nc_nlen)) @@ -318,9 +319,10 @@ cache_enter(dvp, vp, cnp) ncp->nc_vp = vp; ncp->nc_dvp = dvp; len = ncp->nc_nlen = cnp->cn_namelen; - hash = fnv32_hashbuf(cnp->cn_nameptr, len); + hash = fnv_32_buf(cnp->cn_nameptr, len, FNV1_32_INIT); bcopy(cnp->cn_nameptr, ncp->nc_name, len); - ncpp = NCHHASH(dvp, hash); + hash = fnv_32_buf(&dvp->v_id, sizeof(dvp->v_id), hash); + ncpp = NCHHASH(hash); LIST_INSERT_HEAD(ncpp, ncp, nc_hash); if (LIST_EMPTY(&dvp->v_cache_src)) vhold(dvp); diff --git a/sys/nfs/nfs_node.c b/sys/nfs/nfs_node.c index 450729d..a82ad11 100644 --- a/sys/nfs/nfs_node.c +++ b/sys/nfs/nfs_node.c @@ -107,7 +107,7 @@ nfs_nget(mntp, fhp, fhsize, npp) rsflags = 0; retry: - nhpp = NFSNOHASH(fnv32_hashbuf(fhp->fh_bytes, fhsize)); + nhpp = NFSNOHASH(fnv_32_buf(fhp->fh_bytes, fhsize, FNV1_32_INIT)); 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_node.c b/sys/nfsclient/nfs_node.c index 450729d..a82ad11 100644 --- a/sys/nfsclient/nfs_node.c +++ b/sys/nfsclient/nfs_node.c @@ -107,7 +107,7 @@ nfs_nget(mntp, fhp, fhsize, npp) rsflags = 0; retry: - nhpp = NFSNOHASH(fnv32_hashbuf(fhp->fh_bytes, fhsize)); + nhpp = NFSNOHASH(fnv_32_buf(fhp->fh_bytes, fhsize, FNV1_32_INIT)); 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/sys/fnv_hash.h b/sys/sys/fnv_hash.h index 50d2003..24254cf 100644 --- a/sys/sys/fnv_hash.h +++ b/sys/sys/fnv_hash.h @@ -8,19 +8,20 @@ * $FreeBSD$ */ -#define FNV_32_PRIME ((u_int32_t) 0x01000193UL) -#define FNV1_32_INIT ((u_int32_t) 33554467UL) +typedef u_int32_t Fnv32_t; +typedef u_int64_t Fnv64_t; -#define FNV_64_PRIME ((u_int64_t) 0x100000001b3ULL) -#define FNV1_64_INIT ((u_int64_t) 0xcbf29ce484222325ULL) +#define FNV1_32_INIT ((Fnv32_t) 33554467UL) +#define FNV1_64_INIT ((Fnv64_t) 0xcbf29ce484222325ULL) -static __inline u_int32_t -fnv32_hashbuf(const void *buf, size_t len) +#define FNV_32_PRIME ((Fnv32_t) 0x01000193UL) +#define FNV_64_PRIME ((Fnv64_t) 0x100000001b3ULL) + +static __inline Fnv32_t +fnv_32_buf(const void *buf, size_t len, Fnv32_t hval) { 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++; @@ -28,13 +29,12 @@ fnv32_hashbuf(const void *buf, size_t len) return hval; } -static __inline u_int32_t -fnv32_hashstr(const char *str) +static __inline Fnv32_t +fnv_32_str(const char *str, Fnv32_t hval) { const u_int8_t *s = (const u_int8_t *)str; - u_int32_t hval, c; + Fnv32_t c; - hval = FNV1_32_INIT; while ((c = *s++) != 0) { hval *= FNV_32_PRIME; hval ^= c; @@ -42,13 +42,11 @@ fnv32_hashstr(const char *str) return hval; } -static __inline u_int64_t -fnv64_hashbuf(const void *buf, size_t len) +static __inline Fnv64_t +fnv_64_buf(const void *buf, size_t len, Fnv64_t hval) { 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++; @@ -56,14 +54,12 @@ fnv64_hashbuf(const void *buf, size_t len) return hval; } -static __inline u_int64_t -fnv64_hashstr(const char *str) +static __inline Fnv64_t +fnv_64_str(const char *str, Fnv64_t hval) { 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; -- cgit v1.1