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

[Peter Zijlstra]

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