dentry cache order 7 is broken

From: dean gaudet (dean-list-linux-kernel@arctic.org)
Date: Thu Feb 08 2001 - 02:15:30 EST


this looks to be a problem going back all the way to at least 2.2.

if you've got 512Mb of RAM you end up with a dentry cache of order 7 --
65536 entries.

this results in a D_HASHBITS of 16. if you look at d_hash it contains
this code:

        hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);

D_HASHBITS*2 = 32, which on an x86 results in a shift of 0. (ia32 is
defined to mask a variable shift down to the low 5 bits and use the low 5
bits.)

this results in a hash with very little perturbance at all, since the 1st
and 3rd terms of the xor are equal and cancel... and the resulting
performance is pretty abysmal. i'm getting hash chains with well over 100
entries in them just doing a find on the kernel source tree.

if i hard code to order 8 then i get nice well distributed hash chains, 5
entries max.

also, for order > 7, was the real intention to use a shift of
(order*2)&31?

-dean

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/



This archive was generated by hypermail 2b29 : Thu Feb 15 2001 - 21:00:10 EST