From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754503AbcC3OGn (ORCPT ); Wed, 30 Mar 2016 10:06:43 -0400 Received: from casper.infradead.org ([85.118.1.10]:48569 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754418AbcC3OGk (ORCPT ); Wed, 30 Mar 2016 10:06:40 -0400 Date: Wed, 30 Mar 2016 16:06:36 +0200 From: Peter Zijlstra To: Ingo Molnar Cc: Alfredo Alvarez Fernandez , Linus Torvalds , Sedat Dilek , "Theodore Ts'o" , linux-fsdevel , LKML Subject: Re: [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260 Message-ID: <20160330140636.GD11035@twins.programming.kicks-ass.net> References: <20160327204810.GW6356@twins.programming.kicks-ass.net> <20160329084701.GA9393@gmail.com> <20160330093659.GS3408@twins.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20160330093659.GS3408@twins.programming.kicks-ass.net> User-Agent: Mutt/1.5.21 (2012-12-30) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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) {