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) {
