Re: [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260

Peter Zijlstra
2016-03-30T14:06:43Z

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