| Message ID | 20160330140636.GD11035@twins.programming.kicks-ass.net (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Wed, Mar 30, 2016 at 4:06 PM, 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. > Is this patch in combination with the previous one? - Sedat - > --- > 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) > { -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Mar 30, 2016 at 4:06 PM, 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) > { Will you push that also to peterz/queue.git#locking/urgent? - Sedat - P.S.: "lockdep: print chain_key collision information" in your above tree differs from the upstream one. [1] http://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/log/?h=locking/urgent -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Apr 04, 2016 at 05:31:40PM +0200, Sedat Dilek wrote: > > +/* 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); > > +} > Will you push that also to peterz/queue.git#locking/urgent? Only after I've had a play and observed it making any difference; Dmitry supposedly has a reproducer, but I've not yet had a moment to try. > - Sedat - > > P.S.: "lockdep: print chain_key collision information" in your above > tree differs from the upstream one. I'll drop mine, I just hadn't moved to the very latestestest tip. -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 4/4/16, Peter Zijlstra <peterz@infradead.org> wrote: > On Mon, Apr 04, 2016 at 05:31:40PM +0200, Sedat Dilek wrote: >> > +/* 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); >> > +} > >> Will you push that also to peterz/queue.git#locking/urgent? > > Only after I've had a play and observed it making any difference; Dmitry > supposedly has a reproducer, but I've not yet had a moment to try. > Hi Peter, any news on that stuff? How can someone test this? How did Dmitry reproduce? Regards, - Sedat - -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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) {
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(-) -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html