4.8 ffs_dirpref problem

[Don Lewis]

On 17 Nov, Ken Marx wrote:
> 
> 
> Don Lewis wrote:

>> Ok, I'll do the commit as soon as I can do some testing on my -STABLE
>> box.
>> 
> 
> Great. Please let us know when this happens. In fact,
> I kind of got lost which you were planning to commit.
> Can you point me to it, and I'll do one last overnight run.

I just committed version which sets minbfree to:
	max(1, avgbfree - avgbfree / 4)

You may want to continue to use the version that you are already running
which sets minbfree to avgbfree.  I'm not committing my more complex
version because it benchmarked worse for me than the version I
committed.

I'm pretty sure that we can do better than this, but it will require a
fair amount of tweaking and benchmarking, but for now this version
should work a lot better than the previous version of the code.

>> 
>>>I was able to run a couple more tests here, and *belive* that the
>>>fix to the hash table in vfs_bio.c will provide some relief
>>>for cg block searches when things do fall into the linear search case.
>> 
>> 
>> I'll see about cranking out patch to use a Fibonacci hash.  It'll
>> probably be a little while before I can find sufficient time, though.
>> 
> 
> Ditto the above: thanks/keep us posted. Our clients are
> anxious to have a 'final' kernel to run with. I think we'll
> just give them what you commit, and sneak the hash fix in with
> the security patch or some such. So, no rush, but do let me
> know if you think it might happen sooner than, say, 2 weeks
> so I can try and get it all in one release to them.

I had some time to crank out a patch.  Give this a try and compare it to
your hash patch.  It hasn't blown up my system, but I don't have any
benchmark data on it.  You can just do the test where you fill the
remaining space in the filesystem.  You won't need to do a newfs and
start from scratch.  It would be great if you could compare the hash
bucket sizes for the different versions of the hash.


Index: sys/kern/vfs_bio.c
===================================================================
RCS file: /home/ncvs/src/sys/kern/vfs_bio.c,v
retrieving revision 1.242.2.21
diff -u -r1.242.2.21 vfs_bio.c
--- sys/kern/vfs_bio.c	9 Aug 2003 16:21:19 -0000	1.242.2.21
+++ sys/kern/vfs_bio.c	18 Nov 2003 02:10:55 -0000
@@ -140,6 +140,7 @@
 	&bufreusecnt, 0, "");
 
 static int bufhashmask;
+static int bufhashshift;
 static LIST_HEAD(bufhashhdr, buf) *bufhashtbl, invalhash;
 struct bqueues bufqueues[BUFFER_QUEUES] = { { 0 } };
 char *buf_wmesg = BUF_WMESG;
@@ -160,7 +161,20 @@
 struct bufhashhdr *
 bufhash(struct vnode *vnp, daddr_t bn)
 {
-	return(&bufhashtbl[(((uintptr_t)(vnp) >> 7) + (int)bn) & bufhashmask]);
+	u_int64_t hashkey64;
+	int hashkey; 
+	
+	/*
+	 * Fibonacci hash, see Knuth's
+	 * _Art of Computer Programming, Volume 3 / Sorting and Searching_
+	 *
+         * We reduce the argument to 32 bits before doing the hash to
+	 * avoid the need for a slow 64x64 multiply on 32 bit platforms.
+	 */
+	hashkey64 = (u_int64_t)(uintptr_t)vnp + (u_int64_t)bn;
+	hashkey = (((u_int32_t)(hashkey64 + (hashkey64 >> 32)) * 2654435769u) >>
+	    bufhashshift) & bufhashmask;
+	return(&bufhashtbl[hashkey]);
 }
 
 /*
@@ -319,8 +333,9 @@
 bufhashinit(caddr_t vaddr)
 {
 	/* first, make a null hash table */
+	bufhashshift = 29;
 	for (bufhashmask = 8; bufhashmask < nbuf / 4; bufhashmask <<= 1)
-		;
+		bufhashshift--;
 	bufhashtbl = (void *)vaddr;
 	vaddr = vaddr + sizeof(*bufhashtbl) * bufhashmask;
 	--bufhashmask;