Date: Tue, 18 Nov 2003 10:13:12 -0800 From: Ken Marx <kmarx@vicor.com> To: Don Lewis <truckman@FreeBSD.org> Cc: mckusick@beastie.mckusick.com Subject: Re: 4.8 ffs_dirpref problem Message-ID: <3FBA6138.3000500@vicor.com> In-Reply-To: <200311180347.hAI3lmeF089505@gw.catspoiler.org> References: <200311180347.hAI3lmeF089505@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Don Lewis wrote:
> 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;
>
>
Most excellent. I'll try and get you some info by end of today.
Thanks!
k
--
Ken Marx, kmarx@vicor-nb.com
Clearly we must down size and set up weekly meetings on the object, etc.
- http://www.bigshed.com/cgi-bin/speak.cgi
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3FBA6138.3000500>