Change bufhash from the old grotty hash table to red-black trees hanging

off the vnode.
ok art@, oga@, miod@

2 files changed, 48 insertions, 37 deletions

diff --git a/sys/kern/vfs_bio.c b/sys/kern/vfs_bio.c
index 5be42faeac0..6706e7262a9 100644
--- a/sys/kern/vfs_bio.c
+++ b/sys/kern/vfs_bio.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: vfs_bio.c,v 1.112 2009/04/22 13:12:26 art Exp $	*/
+/*	$OpenBSD: vfs_bio.c,v 1.113 2009/06/03 04:30:57 beck Exp $	*/
 /*	$NetBSD: vfs_bio.c,v 1.44 1996/06/11 11:15:36 pk Exp $	*/
 
 /*-
@@ -62,20 +62,6 @@
 #include <miscfs/specfs/specdev.h>
 
 /*
- * Definitions for the buffer hash lists.
- */
-#define	BUFHASH(dvp, lbn)	\
-	(&bufhashtbl[((long)(dvp) / sizeof(*(dvp)) + (int)(lbn)) & bufhash])
-LIST_HEAD(bufhashhdr, buf) *bufhashtbl, invalhash;
-u_long	bufhash;
-
-/*
- * Insq/Remq for the buffer hash lists.
- */
-#define	binshash(bp, dp)	LIST_INSERT_HEAD(dp, bp, b_hash)
-#define	bremhash(bp)		LIST_REMOVE(bp, b_hash)
-
-/*
  * Definitions for the buffer free lists.
  */
 #define	BQUEUES		2		/* number of free buffer queues */
@@ -182,7 +168,6 @@ buf_put(struct buf *bp)
 		panic("buf_put: b_dep is not empty");
 #endif
 
-	bremhash(bp);
 	LIST_REMOVE(bp, b_list);
 	bcstats.numbufs--;
 
@@ -237,7 +222,6 @@ bufinit(void)
  	 */
 	buf_mem_init(bufkvm);
 
-	bufhashtbl = hashinit(bufpages / 4, M_CACHE, M_WAITOK, &bufhash);
 	hidirtypages = (bufpages / 4) * 3;
 	lodirtypages = bufpages / 2;
 
@@ -676,10 +660,12 @@ brelse(struct buf *bp)
 			CLR(bp->b_flags, B_DELWRI);
 		}
 
-		if (bp->b_vp)
+		if (bp->b_vp) {
+			RB_REMOVE(buf_rb_bufs, &bp->b_vp->v_bufs_tree,
+			    bp);
 			brelvp(bp);
-		bremhash(bp);
-		binshash(bp, &invalhash);
+		}
+		bp->b_vp = NULL;
 
 		/*
 		 * If the buffer has no associated data, place it back in the
@@ -697,6 +683,9 @@ brelse(struct buf *bp)
 				CLR(bp->b_flags, B_WANTED);
 				wakeup(bp);
 			}
+			if (bp->b_vp != NULL)
+				RB_REMOVE(buf_rb_bufs,
+				    &bp->b_vp->v_bufs_tree, bp);
 			buf_put(bp);
 			splx(s);
 			return;
@@ -758,15 +747,14 @@ struct buf *
 incore(struct vnode *vp, daddr64_t blkno)
 {
 	struct buf *bp;
-
-	/* Search hash chain */
-	LIST_FOREACH(bp, BUFHASH(vp, blkno), b_hash) {
-		if (bp->b_lblkno == blkno && bp->b_vp == vp &&
-		    !ISSET(bp->b_flags, B_INVAL))
-			return (bp);
-	}
-
-	return (NULL);
+	struct buf b;
+
+	/* Search buf lookup tree */
+	b.b_lblkno = blkno;
+	bp = RB_FIND(buf_rb_bufs, &vp->v_bufs_tree, &b);
+	if (bp && !ISSET(bp->b_flags, B_INVAL))
+		return(bp);
+	return(NULL);
 }
 
 /*
@@ -781,6 +769,7 @@ struct buf *
 getblk(struct vnode *vp, daddr64_t blkno, int size, int slpflag, int slptimeo)
 {
 	struct buf *bp;
+	struct buf b;
 	int s, error;
 
 	/*
@@ -794,9 +783,9 @@ getblk(struct vnode *vp, daddr64_t blkno, int size, int slpflag, int slptimeo)
 	 * the block until the write is finished.
 	 */
 start:
-	LIST_FOREACH(bp, BUFHASH(vp, blkno), b_hash) {
-		if (bp->b_lblkno != blkno || bp->b_vp != vp)
-			continue;
+	b.b_lblkno = blkno;
+	bp = RB_FIND(buf_rb_bufs, &vp->v_bufs_tree, &b);
+	if (bp != NULL) {
 
 		s = splbio();
 		if (ISSET(bp->b_flags, B_BUSY)) {
@@ -868,8 +857,11 @@ buf_get(struct vnode *vp, daddr64_t blkno, size_t size)
 			while (bcstats.numcleanpages > locleanpages) {
 				bp = TAILQ_FIRST(&bufqueues[BQ_CLEAN]);
 				bremfree(bp);
-				if (bp->b_vp)
+				if (bp->b_vp) {
+					RB_REMOVE(buf_rb_bufs,
+					    &bp->b_vp->v_bufs_tree, bp);
 					brelvp(bp);
+				}
 				buf_put(bp);
 			}
 		}
@@ -884,8 +876,11 @@ buf_get(struct vnode *vp, daddr64_t blkno, size_t size)
 			int i = freemax;
 			while ((bp = TAILQ_FIRST(&bufqueues[BQ_CLEAN])) && i--) {
 				bremfree(bp);
-				if (bp->b_vp)
+				if (bp->b_vp) {
+					RB_REMOVE(buf_rb_bufs,
+					    &bp->b_vp->v_bufs_tree, bp);
 					brelvp(bp);
+				}
 				buf_put(bp);
 			}
 			if (freemax == i) {
@@ -929,11 +924,12 @@ buf_get(struct vnode *vp, daddr64_t blkno, size_t size)
 
 		bp->b_blkno = bp->b_lblkno = blkno;
 		bgetvp(vp, bp);
-		binshash(bp, BUFHASH(vp, blkno));
+		if (RB_INSERT(buf_rb_bufs, &vp->v_bufs_tree, bp))
+			panic("buf_get: dup lblk vp %p bp %p", vp, bp);
 	} else {
 		bp->b_vnbufs.le_next = NOLIST;
 		SET(bp->b_flags, B_INVAL);
-		binshash(bp, &invalhash);
+		bp->b_vp = NULL;
 	}
 
 	LIST_INSERT_HEAD(&bufhead, bp, b_list);
diff --git a/sys/kern/vfs_subr.c b/sys/kern/vfs_subr.c
index ce7eeedae86..069cd7ce121 100644
--- a/sys/kern/vfs_subr.c
+++ b/sys/kern/vfs_subr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: vfs_subr.c,v 1.175 2008/11/10 11:53:16 pedro Exp $	*/
+/*	$OpenBSD: vfs_subr.c,v 1.176 2009/06/03 04:30:57 beck Exp $	*/
 /*	$NetBSD: vfs_subr.c,v 1.53 1996/04/22 01:39:13 christos Exp $	*/
 
 /*
@@ -59,6 +59,7 @@
 #include <sys/mbuf.h>
 #include <sys/syscallargs.h>
 #include <sys/pool.h>
+#include <sys/tree.h>
 
 #include <uvm/uvm_extern.h>
 #include <sys/sysctl.h>
@@ -115,6 +116,19 @@ void printlockedvnodes(void);
 
 struct pool vnode_pool;
 
+static int rb_buf_compare(struct buf *b1, struct buf *b2);
+RB_GENERATE(buf_rb_bufs, buf, b_rbbufs, rb_buf_compare);
+
+static int
+rb_buf_compare(struct buf *b1, struct buf *b2)
+{
+	if (b1->b_lblkno < b2->b_lblkno)
+		return(-1);
+	if (b1->b_lblkno > b2->b_lblkno)
+		return(1);
+	return(0);
+}
+
 /*
  * Initialize the vnode management data structures.
  */
@@ -345,6 +359,7 @@ getnewvnode(enum vtagtype tag, struct mount *mp, int (**vops)(void *),
 	    ((TAILQ_FIRST(listhd = &vnode_hold_list) == NULL) || toggle))) {
 		splx(s);
 		vp = pool_get(&vnode_pool, PR_WAITOK | PR_ZERO);
+		RB_INIT(&vp->v_bufs_tree);
 		numvnodes++;
 	} else {
 		for (vp = TAILQ_FIRST(listhd); vp != NULLVP;