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

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

1 files changed, 32 insertions, 36 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);