Messages in this thread Patch in this message | | | Date | Wed, 30 Mar 2016 16:06:36 +0200 | From | Peter Zijlstra <> | Subject | Re: [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260 |
| |
On Wed, Mar 30, 2016 at 11:36:59AM +0200, Peter Zijlstra wrote: > Furthermore, our hash function has definite room for improvement.
After a bit of reading, using a 'strong' PRNG as base for a hash function seems generally suggested.
--- kernel/locking/lockdep.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 53ab2f85d77e..0f7dba4144d6 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -308,10 +308,21 @@ static struct hlist_head chainhash_table[CHAINHASH_SIZE]; * It's a 64-bit hash, because it's important for the keys to be * unique. */ -#define iterate_chain_key(key1, key2) \ - (((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \ - ((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \ - (key2)) + +/* https://en.wikipedia.org/wiki/Xorshift#xorshift.2A */ +#define UINT64_C(x) x##ULL +static inline u64 xorshift64star(u64 x) +{ + x ^= x >> 12; // a + x ^= x << 25; // b + x ^= x >> 27; // c + return x * UINT64_C(2685821657736338717); +} + +static inline u64 iterate_chain_key(u64 hash, u64 class_idx) +{ + return xorshift64star(hash ^ class_idx); +} void lockdep_off(void) {
| |