[src/trunk]: src/sys - Implement

[lukem <lukem%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/20b671ae4346
branches:  trunk
changeset: 518934:20b671ae4346
user:      lukem <lukem%NetBSD.org@localhost>
date:      Sat Dec 08 04:09:59 2001 +0000

description:
- Implement
        uint32_t namei_hash(const char *p, const char **ep)
  which determines the equivalent MI hash32_str() hash for p.
  If *ep != NULL, calculate the hash to the character before ep.
  If *ep == NULL, calculate the has to the first / or NUL found, and
  point *ep to that location.
- Use namei_hash() to calculate cn_hash in lookup() and relookup().
  Hash distribution goes from 35-40% to 55-70%, with similar profiled
  time spent in cache_lookup() and cache_enter() on my P3-600.
- Use namei_hash() to calculate cn_hash in nfs_readdirplusrpc(),
  insetad of homegrown code (that differed from that in lookup() !)
  namei_hash() has better spread and is faster than previous code
  (which used a non-constant multiplication).

diffstat:

 sys/kern/vfs_lookup.c |  44 ++++++++++++++++++++++++++++++++++++--------
 sys/nfs/nfs_vnops.c   |  15 ++++++++-------
 sys/sys/namei.h       |   3 ++-
 3 files changed, 46 insertions(+), 16 deletions(-)

diffs (158 lines):

diff -r 54f5e71fb583 -r 20b671ae4346 sys/kern/vfs_lookup.c
--- a/sys/kern/vfs_lookup.c     Sat Dec 08 04:09:56 2001 +0000
+++ b/sys/kern/vfs_lookup.c     Sat Dec 08 04:09:59 2001 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: vfs_lookup.c,v 1.38 2001/11/12 15:25:39 lukem Exp $    */
+/*     $NetBSD: vfs_lookup.c,v 1.39 2001/12/08 04:09:59 lukem Exp $    */
 
 /*
  * Copyright (c) 1982, 1986, 1989, 1993
@@ -41,7 +41,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: vfs_lookup.c,v 1.38 2001/11/12 15:25:39 lukem Exp $");
+__KERNEL_RCSID(0, "$NetBSD: vfs_lookup.c,v 1.39 2001/12/08 04:09:59 lukem Exp $");
 
 #include "opt_ktrace.h"
 
@@ -53,8 +53,9 @@
 #include <sys/vnode.h>
 #include <sys/mount.h>
 #include <sys/errno.h>
+#include <sys/filedesc.h>
+#include <sys/hash.h>
 #include <sys/malloc.h>
-#include <sys/filedesc.h>
 #include <sys/proc.h>
 
 #ifdef KTRACE
@@ -236,6 +237,34 @@
 }
 
 /*
+ * Determine the namei hash (for cn_hash) for name.
+ * If *ep != NULL, hash from name to ep-1.
+ * If *ep == NULL, hash from name until the first NUL or '/', and
+ * return the location of this termination character in *ep.
+ *
+ * This function returns an equivalent hash to the MI hash32_strn().
+ * The latter isn't used because in the *ep == NULL case, determining
+ * the length of the string to the first NUL or `/' and then calling
+ * hash32_strn() involves unnecessary double-handling of the data.
+ */
+uint32_t
+namei_hash(const char *name, const char **ep)
+{
+       uint32_t        hash;
+
+       hash = HASH32_STR_INIT;
+       if (*ep != NULL) {
+               for (; name < *ep; name++)
+                       hash = hash * 33 + *(uint8_t *)name;
+       } else {
+               for (; *name != '\0' && *name != '/'; name++)
+                       hash = hash * 33 + *(uint8_t *)name;
+               *ep = name;
+       }
+       return (hash + (hash >> 5));
+}
+
+/*
  * Search a pathname.
  * This is a very central and rather complicated routine.
  *
@@ -349,9 +378,8 @@
         * responsibility for freeing the pathname buffer.
         */
        cnp->cn_consume = 0;
-       cnp->cn_hash = 0;
-       for (cp = cnp->cn_nameptr; *cp != '\0' && *cp != '/'; cp++)
-               cnp->cn_hash += (unsigned char)*cp;
+       cp = NULL;
+       cnp->cn_hash = namei_hash(cnp->cn_nameptr, &cp);
        cnp->cn_namelen = cp - cnp->cn_nameptr;
        if (cnp->cn_namelen > NAME_MAX) {
                error = ENAMETOOLONG;
@@ -638,8 +666,8 @@
         * responsibility for freeing the pathname buffer.
         */
 #ifdef NAMEI_DIAGNOSTIC
-       for (newhash = 0, cp = cnp->cn_nameptr; *cp != 0 && *cp != '/'; cp++)
-               newhash += (unsigned char)*cp;
+       cp = NULL;
+       newhash = namei_hash(cnp->cn_nameptr, &cp);
        if (newhash != cnp->cn_hash)
                panic("relookup: bad hash");
        if (cnp->cn_namelen != cp - cnp->cn_nameptr)
diff -r 54f5e71fb583 -r 20b671ae4346 sys/nfs/nfs_vnops.c
--- a/sys/nfs/nfs_vnops.c       Sat Dec 08 04:09:56 2001 +0000
+++ b/sys/nfs/nfs_vnops.c       Sat Dec 08 04:09:59 2001 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: nfs_vnops.c,v 1.146 2001/12/04 18:38:09 christos Exp $ */
+/*     $NetBSD: nfs_vnops.c,v 1.147 2001/12/08 04:10:00 lukem Exp $    */
 
 /*
  * Copyright (c) 1989, 1993
@@ -43,7 +43,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: nfs_vnops.c,v 1.146 2001/12/04 18:38:09 christos Exp $");
+__KERNEL_RCSID(0, "$NetBSD: nfs_vnops.c,v 1.147 2001/12/08 04:10:00 lukem Exp $");
 
 #include "opt_nfs.h"
 #include "opt_uvmhist.h"
@@ -62,6 +62,7 @@
 #include <sys/vnode.h>
 #include <sys/dirent.h>
 #include <sys/fcntl.h>
+#include <sys/hash.h>
 #include <sys/lockf.h>
 #include <sys/stat.h>
 #include <sys/unistd.h>
@@ -2377,7 +2378,6 @@
        struct componentname *cnp = &ndp->ni_cnd;
        struct nfsmount *nmp = VFSTONFS(vp->v_mount);
        struct nfsnode *dnp = VTONFS(vp), *np;
-       const unsigned char *hcp;
        nfsfh_t *fhp;
        u_quad_t fileno;
        int error = 0, tlen, more_dirs = 1, blksiz = 0, doit, bigenough = 1, i;
@@ -2522,14 +2522,15 @@
                                        newvp = NFSTOV(np);
                                }
                                if (!error) {
+                                   const char *cp;
+
                                    nfs_loadattrcache(&newvp, &fattr, 0);
                                    dp->d_type =
                                        IFTODT(VTTOIF(np->n_vattr->va_type));
                                    ndp->ni_vp = newvp;
-                                   cnp->cn_hash = 0;
-                                   for (hcp = cnp->cn_nameptr, i = 1; i <= len;
-                                       i++, hcp++)
-                                       cnp->cn_hash += *hcp * i;
+                                   cp = cnp->cn_nameptr + cnp->cn_namelen;
+                                   cnp->cn_hash =
+                                       namei_hash(cnp->cn_nameptr, &cp);
                                    if (cnp->cn_namelen <= NCHNAMLEN)
                                        cache_enter(ndp->ni_dvp, ndp->ni_vp,
                                                    cnp);
diff -r 54f5e71fb583 -r 20b671ae4346 sys/sys/namei.h
--- a/sys/sys/namei.h   Sat Dec 08 04:09:56 2001 +0000
+++ b/sys/sys/namei.h   Sat Dec 08 04:09:59 2001 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: namei.h,v 1.24 2001/12/06 04:02:22 lukem Exp $ */
+/*     $NetBSD: namei.h,v 1.25 2001/12/08 04:10:00 lukem Exp $ */
 
 /*
  * Copyright (c) 1985, 1989, 1991, 1993
@@ -184,6 +184,7 @@
 #define        PNBUF_PUT(pnb)  pool_cache_put(&pnbuf_cache, (pnb))
 
 int    namei __P((struct nameidata *ndp));
+uint32_t namei_hash __P((const char *, const char **));
 int    lookup __P((struct nameidata *ndp));
 int    relookup __P((struct vnode *dvp, struct vnode **vpp,
                      struct componentname *cnp));