From: Sedat Dilek <sedat.dilek@gmail.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@kernel.org>,
Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>,
Linus Torvalds <torvalds@linux-foundation.org>,
"Theodore Ts'o" <tytso@mit.edu>,
linux-fsdevel <linux-fsdevel@vger.kernel.org>,
LKML <linux-kernel@vger.kernel.org>
Subject: Re: [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260
Date: Fri, 3 Jun 2016 17:15:33 +0200 [thread overview]
Message-ID: <CA+icZUUgZvQnMwsnaKcos259nOQuDN2sU1EmRkZGGmtUsFh-AQ@mail.gmail.com> (raw)
In-Reply-To: <20160330140636.GD11035@twins.programming.kicks-ass.net>
On 3/30/16, Peter Zijlstra <peterz@infradead.org> wrote:
> 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)
> {
>
You dropped this implementation and the below is a different approach?
"locking/lockdep: Use __jhash_mix() for iterate_chain_key()"
- Sedat -
[1] http://git.kernel.org/cgit/linux/kernel/git/tip/tip.git/commit/?h=locking/core&id=724e66913097c2eba029b06dcd05c5a2be78d466
next prev parent reply other threads:[~2016-06-03 15:15 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-03-27 8:15 [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260 Sedat Dilek
2016-03-27 8:57 ` Sedat Dilek
2016-03-27 12:03 ` Linus Torvalds
2016-03-27 13:32 ` Boqun Feng
2016-03-27 18:23 ` Theodore Ts'o
2016-03-27 19:40 ` Sedat Dilek
[not found] ` <CA+55aFwoKRpgq8OCTxUaP+8gOg-mnN3nbruYgiK32a=C5U4TkQ@mail.gmail.com>
2016-03-27 20:24 ` Sedat Dilek
2016-03-27 20:48 ` Peter Zijlstra
2016-03-27 20:59 ` Sedat Dilek
2016-03-27 21:48 ` Sedat Dilek
2016-03-28 1:05 ` Boqun Feng
2016-03-28 6:33 ` Peter Zijlstra
2016-03-29 8:47 ` Ingo Molnar
2016-03-30 9:20 ` Sedat Dilek
2016-03-30 9:36 ` Sedat Dilek
2016-03-30 9:36 ` Peter Zijlstra
2016-03-30 9:49 ` Sedat Dilek
2016-03-30 10:33 ` Sedat Dilek
2016-03-30 12:43 ` Peter Zijlstra
2016-03-30 12:46 ` Sedat Dilek
2016-03-30 13:15 ` Peter Zijlstra
2016-03-30 9:50 ` Peter Zijlstra
2016-03-30 9:59 ` Boqun Feng
2016-03-30 10:36 ` Peter Zijlstra
2016-03-30 11:07 ` Sedat Dilek
2016-03-31 15:42 ` Peter Zijlstra
2016-03-31 15:52 ` Boqun Feng
2016-04-02 6:26 ` Sedat Dilek
2016-03-30 14:06 ` Peter Zijlstra
2016-03-30 15:21 ` Sedat Dilek
2016-03-30 17:03 ` [PATCH] lockdep: print chain_key collision information Alfredo Alvarez Fernandez
2016-03-30 17:19 ` Peter Zijlstra
2016-04-01 6:36 ` [tip:core/urgent] locking/lockdep: Print " tip-bot for Alfredo Alvarez Fernandez
2016-05-10 9:09 ` Peter Zijlstra
2016-04-04 15:31 ` [Linux-v4.6-rc1] ext4: WARNING: CPU: 2 PID: 2692 at kernel/locking/lockdep.c:2017 __lock_acquire+0x180e/0x2260 Sedat Dilek
2016-04-04 16:02 ` Peter Zijlstra
2016-05-09 11:37 ` Sedat Dilek
2016-06-03 15:15 ` Sedat Dilek [this message]
2016-04-23 12:54 ` [tip:locking/urgent] lockdep: Fix lock_chain::base size tip-bot for Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CA+icZUUgZvQnMwsnaKcos259nOQuDN2sU1EmRkZGGmtUsFh-AQ@mail.gmail.com \
--to=sedat.dilek@gmail.com \
--cc=alfredoalvarezfernandez@gmail.com \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).