Use an RB tree instead of a hashtable for fh/node lookups.

Idea from NetBSD.

OK blambert@

7 files changed, 61 insertions, 65 deletions

diff --git a/sys/nfs/nfs.h b/sys/nfs/nfs.h
index 187112bf705..e6f0f924cb9 100644
--- a/sys/nfs/nfs.h
+++ b/sys/nfs/nfs.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfs.h,v 1.46 2009/08/10 09:38:44 thib Exp $	*/
+/*	$OpenBSD: nfs.h,v 1.47 2009/08/10 10:59:11 thib Exp $	*/
 /*	$NetBSD: nfs.h,v 1.10.4.1 1996/05/27 11:23:56 fvdl Exp $	*/
 
 /*
@@ -263,9 +263,6 @@ enum nfs_rto_timers {
 
 #define NFS_INITRTT	(NFS_HZ << 3)
 
-#define	NFSNOHASH(fhsum) \
-	(&nfsnodehashtbl[(fhsum) & nfsnodehash])
-
 /*
  * Network address hash list element
  */
diff --git a/sys/nfs/nfs_node.c b/sys/nfs/nfs_node.c
index 4557d6f21fe..2c9d0a55ba0 100644
--- a/sys/nfs/nfs_node.c
+++ b/sys/nfs/nfs_node.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfs_node.c,v 1.45 2009/07/20 16:49:40 thib Exp $	*/
+/*	$OpenBSD: nfs_node.c,v 1.46 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfs_node.c,v 1.16 1996/02/18 11:53:42 fvdl Exp $	*/
 
 /*
@@ -45,7 +45,6 @@
 #include <sys/kernel.h>
 #include <sys/malloc.h>
 #include <sys/pool.h>
-#include <sys/hash.h>
 #include <sys/rwlock.h>
 #include <sys/queue.h>
 
@@ -56,28 +55,23 @@
 #include <nfs/nfsmount.h>
 #include <nfs/nfs_var.h>
 
-LIST_HEAD(nfsnodehashhead, nfsnode) *nfsnodehashtbl;
-u_long nfsnodehash;
-struct rwlock nfs_hashlock = RWLOCK_INITIALIZER("nfshshlk");
-
 struct pool nfs_node_pool;
-
 extern int prtactive;
 
-#define	nfs_hash(x,y)	hash32_buf((x), (y), HASHINIT)
+struct rwlock nfs_hashlock = RWLOCK_INITIALIZER("nfshshlk");
 
-/*
- * Initialize hash links for nfsnodes
- * and build nfsnode free list.
- */
-void
-nfs_nhinit()
+/* filehandle to node lookup. */
+static __inline int
+nfsnode_cmp(const struct nfsnode *a, const struct nfsnode *b)
 {
-	nfsnodehashtbl = hashinit(desiredvnodes, M_NFSNODE, M_WAITOK, &nfsnodehash);
-	pool_init(&nfs_node_pool, sizeof(struct nfsnode), 0, 0, 0, "nfsnodepl",
-	    &pool_allocator_nointr);
+	if (a->n_fhsize != b->n_fhsize)
+		return (a->n_fhsize - b->n_fhsize);
+	return (memcmp(a->n_fhp, b->n_fhp, a->n_fhsize));
 }
 
+RB_PROTOTYPE(nfs_nodetree, nfsnode, n_entry, nfsnode_cmp);
+RB_GENERATE(nfs_nodetree, nfsnode, n_entry, nfsnode_cmp);
+
 /*
  * Look up a vnode/nfsnode by file handle.
  * Callers must check for mount points!!
@@ -85,41 +79,40 @@ nfs_nhinit()
  * nfsnode structure is returned.
  */
 int
-nfs_nget(mntp, fhp, fhsize, npp)
-	struct mount *mntp;
-	nfsfh_t *fhp;
-	int fhsize;
-	struct nfsnode **npp;
+nfs_nget(struct mount *mnt, nfsfh_t *fh, int fhsize, struct nfsnode **npp)
 {
-	struct nfsmount *nmp;
-	struct proc *p = curproc;	/* XXX */
-	struct nfsnode *np;
-	struct nfsnodehashhead *nhpp;
-	struct vnode *vp;
-	extern int (**nfsv2_vnodeop_p)(void *);
-	struct vnode *nvp;
-	int error;
+	extern int (**nfsv2_vnodeop_p)(void *);		/* XXX */
+	struct nfsmount		*nmp;
+	struct nfsnode		*np, find;
+	struct vnode		*vp, *nvp;
+	struct proc		*p = curproc;		/* XXX */
+	int			 error;
+
+	nmp = VFSTONFS(mnt);
 
-	nhpp = NFSNOHASH(nfs_hash(fhp, fhsize));
 loop:
-	LIST_FOREACH(np, nhpp, n_hash) {
-		if (mntp != NFSTOV(np)->v_mount || np->n_fhsize != fhsize ||
-		    bcmp((caddr_t)fhp, (caddr_t)np->n_fhp, fhsize))
-			continue;
+	/* XXXTHIB: locking. */
+	find.n_fhp = fh;
+	find.n_fhsize = fhsize;
+	np = RB_FIND(nfs_nodetree, &nmp->nm_ntree, &find);
+	if (np != NULL) {
 		vp = NFSTOV(np);
 		if (vget(vp, LK_EXCLUSIVE, p))
 			goto loop;
 		*npp = np;
-		return(0);
+		return (0);
 	}
+
 	if (rw_enter(&nfs_hashlock, RW_WRITE|RW_SLEEPFAIL))
 		goto loop;
-	error = getnewvnode(VT_NFS, mntp, nfsv2_vnodeop_p, &nvp);
+
+	error = getnewvnode(VT_NFS, mnt, nfsv2_vnodeop_p, &nvp);
 	if (error) {
-		*npp = 0;
+		*npp = NULL;
 		rw_exit(&nfs_hashlock);
 		return (error);
 	}
+
 	vp = nvp;
 	np = pool_get(&nfs_node_pool, PR_WAITOK | PR_ZERO);
 	vp->v_data = np;
@@ -131,21 +124,20 @@ loop:
 	 * Are we getting the root? If so, make sure the vnode flags
 	 * are correct 
 	 */
-	nmp = VFSTONFS(mntp);
-	if ((fhsize == nmp->nm_fhsize) &&
-	    !bcmp(fhp, nmp->nm_fh, fhsize)) {
+	if ((fhsize == nmp->nm_fhsize) && !bcmp(fh, nmp->nm_fh, fhsize)) {
 		if (vp->v_type == VNON)
 			vp->v_type = VDIR;
 		vp->v_flag |= VROOT;
 	}
-	
-	LIST_INSERT_HEAD(nhpp, np, n_hash);
+
 	np->n_fhp = &np->n_fh;
-	bcopy((caddr_t)fhp, (caddr_t)np->n_fhp, fhsize);
+	bcopy(fh, np->n_fhp, fhsize);
 	np->n_fhsize = fhsize;
+	RB_INSERT(nfs_nodetree, &nmp->nm_ntree, np);
 	np->n_accstamp = -1;
 	rw_exit(&nfs_hashlock);
 	*npp = np;
+
 	return (0);
 }
 
@@ -190,27 +182,28 @@ nfs_inactive(v)
  * Reclaim an nfsnode so that it can be used for other purposes.
  */
 int
-nfs_reclaim(v)
-	void *v;
+nfs_reclaim(void *v)
 {
-	struct vop_reclaim_args *ap = v;
-	struct vnode *vp = ap->a_vp;
-	struct nfsnode *np = VTONFS(vp);
+	struct vop_reclaim_args	*ap = v;
+	struct vnode		*vp = ap->a_vp;
+	struct nfsmount		*nmp = VFSTONFS(vp->v_mount);
+	struct nfsnode		*np = VTONFS(vp);
 
 #ifdef DIAGNOSTIC
 	if (prtactive && vp->v_usecount != 0)
 		vprint("nfs_reclaim: pushing active", vp);
 #endif
 
-	if (np->n_hash.le_prev != NULL)
-		LIST_REMOVE(np, n_hash);
+	RB_REMOVE(nfs_nodetree, &nmp->nm_ntree, np);
 
 	if (np->n_rcred)
 		crfree(np->n_rcred);
 	if (np->n_wcred)
 		crfree(np->n_wcred);
+
 	cache_purge(vp);
 	pool_put(&nfs_node_pool, vp->v_data);
 	vp->v_data = NULL;
+
 	return (0);
 }
diff --git a/sys/nfs/nfs_subs.c b/sys/nfs/nfs_subs.c
index 4446cf1e3c6..fc035d41569 100644
--- a/sys/nfs/nfs_subs.c
+++ b/sys/nfs/nfs_subs.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfs_subs.c,v 1.100 2009/08/10 09:38:44 thib Exp $	*/
+/*	$OpenBSD: nfs_subs.c,v 1.101 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfs_subs.c,v 1.27.4.3 1996/07/08 20:34:24 jtc Exp $	*/
 
 /*
@@ -931,11 +931,14 @@ nfs_init()
 
 #ifdef NFSCLIENT
 int
-nfs_vfs_init(vfsp)
-	struct vfsconf *vfsp;
+nfs_vfs_init(struct vfsconf *vfsp)
 {
+	extern struct pool nfs_node_pool;
+
 	TAILQ_INIT(&nfs_bufq);
-	nfs_nhinit();			/* Init the nfsnode table */
+
+	pool_init(&nfs_node_pool, sizeof(struct nfsnode), 0, 0, 0,
+	    "nfsnodepl", NULL);
 
 	return (0);
 }
diff --git a/sys/nfs/nfs_var.h b/sys/nfs/nfs_var.h
index 3b050439731..582b310133c 100644
--- a/sys/nfs/nfs_var.h
+++ b/sys/nfs/nfs_var.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfs_var.h,v 1.53 2009/08/10 09:38:44 thib Exp $	*/
+/*	$OpenBSD: nfs_var.h,v 1.54 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfs_var.h,v 1.3 1996/02/18 11:53:54 fvdl Exp $	*/
 
 /*
@@ -56,7 +56,6 @@ int nfs_doio(struct buf *, struct proc *);
 int nfs_boot_init(struct nfs_diskless *, struct proc *);
 
 /* nfs_node.c */
-void nfs_nhinit(void);
 int nfs_nget(struct mount *, nfsfh_t *, int, struct nfsnode **);
 int nfs_inactive(void *);
 int nfs_reclaim(void *);
diff --git a/sys/nfs/nfs_vfsops.c b/sys/nfs/nfs_vfsops.c
index 145b179cf94..b3fa864500c 100644
--- a/sys/nfs/nfs_vfsops.c
+++ b/sys/nfs/nfs_vfsops.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfs_vfsops.c,v 1.86 2009/08/04 17:12:39 thib Exp $	*/
+/*	$OpenBSD: nfs_vfsops.c,v 1.87 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfs_vfsops.c,v 1.46.4.1 1996/05/25 22:40:35 fvdl Exp $	*/
 
 /*
@@ -698,6 +698,8 @@ mountnfs(argp, mp, nam, pth, hst)
 	nmp->nm_nam = nam;
 	nfs_decode_args(nmp, argp, &mp->mnt_stat.mount_info.nfs_args);
 
+	RB_INIT(&nmp->nm_ntree);
+
 	/* Set up the sockets and per-host congestion */
 	nmp->nm_sotype = argp->sotype;
 	nmp->nm_soproto = argp->proto;
diff --git a/sys/nfs/nfsmount.h b/sys/nfs/nfsmount.h
index 709fda51c6f..f080e810bc3 100644
--- a/sys/nfs/nfsmount.h
+++ b/sys/nfs/nfsmount.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfsmount.h,v 1.20 2009/06/03 00:12:34 thib Exp $	*/
+/*	$OpenBSD: nfsmount.h,v 1.21 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfsmount.h,v 1.10 1996/02/18 11:54:03 fvdl Exp $	*/
 
 /*
@@ -45,6 +45,8 @@
  * Holds NFS specific information for mount.
  */
 struct	nfsmount {
+	RB_HEAD(nfs_nodetree, nfsnode)
+		nm_ntree;		/* filehandle/node tree */
 	int	nm_flag;		/* Flags for soft/hard... */
 	struct	mount *nm_mountp;	/* Vfs structure for this filesystem */
 	int	nm_numgrps;		/* Max. size of groupslist */
diff --git a/sys/nfs/nfsnode.h b/sys/nfs/nfsnode.h
index 2dab79a0542..ce8edebb97c 100644
--- a/sys/nfs/nfsnode.h
+++ b/sys/nfs/nfsnode.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nfsnode.h,v 1.33 2009/01/24 23:30:42 thib Exp $	*/
+/*	$OpenBSD: nfsnode.h,v 1.34 2009/08/10 10:59:12 thib Exp $	*/
 /*	$NetBSD: nfsnode.h,v 1.16 1996/02/18 11:54:04 fvdl Exp $	*/
 
 /*
@@ -70,7 +70,7 @@ struct sillyrename {
  *     be well aligned and, therefore, tightly packed.
  */
 struct nfsnode {
-	LIST_ENTRY(nfsnode)	n_hash;		/* Hash chain */
+	RB_ENTRY(nfsnode)	n_entry;	/* filehandle/node tree. */
 	u_quad_t		n_size;		/* Current size of file */
 	struct vattr		n_vattr;	/* Vnode attribute cache */
 	time_t			n_attrstamp;	/* Attr. cache timestamp */