linux-kernel - Re: [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160330140636.GD11035@twins.programming.kicks-ass.net>
Date:	Wed, 30 Mar 2016 16:06:36 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Ingo Molnar <mingo@...nel.org>
Cc:	Alfredo Alvarez Fernandez <alfredoalvarezfernandez@...il.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Sedat Dilek <sedat.dilek@...il.com>,
	Theodore Ts'o <tytso@....edu>,
	linux-fsdevel <linux-fsdevel@...r.kernel.org>,
	LKML <linux-kernel@...r.kernel.org>
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)
 {