cvs commit: src/sys/kern vfs_bio.c

Don Lewis truckman at FreeBSD.org
Wed Dec 3 20:30:02 PST 2003


On  3 Dec, Nate Lawson wrote:
> On Wed, 3 Dec 2003, Don Lewis wrote:
>>   Modified files:        (Branch: RELENG_4)
>>     sys/kern             vfs_bio.c
>>   Log:
>>   The existing hash algorithm in bufhash() does not distribute entries
>>   very well across buckets, especially in the case of cylinder group blocks
>>   which are located at a sequence of locations that are a multiple of a large
>>   power of two apart.  In the case of large file systems, one or possibly
>>   a few of the hash chains can get excessively long.  Replace the existing
>>   hash algorithm with a variation on the Fibonacci hash.
>>
>>   Tested by:      Ken Marx <kmarx at vicor.com>
>>
>>   Revision    Changes    Path
>>   1.242.2.22  +37 -2     src/sys/kern/vfs_bio.c
> 
> This is excellent.  MTC?  (Merge To Current)  :)

Nope, -CURRENT uses a splay tree instead of a hash table here.

> Also, whitespace nit:
> 
>> +	 * 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.
>> +	 *

Grumble ... actually two.  Fix committed.


More information about the cvs-src mailing list