Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1392494

Re: [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Mon, May 2, 2016 at 3:22 AM, George Spelvin <linux@horizon.com> wrote:
> hash_64() was using a low-bit-weight multiplier, which resulted in
> very bad mixing of the high bits of the input.  In particular,
> page-aligned pointers (low 12 bits not used) were a disaster,

So I did just a minimal for fro 4.6 (and back-porting), which took
just the constants and made _only_ the 64-bit architevture case use
this improved constant for hash_64.

In other words, people who use "hash_long()" or use "hash_64()" on
64-bit architectures will get the improvements, but if you use
hash_64() on a 32-bit architecture you'll conteinue to see the old
behavior.

Quite frankly, looking at some of the explicit hash_64() users, they
seem to be a big dubious anyway. And it won't make things *worse* for
them.

So that simple "just use multiplication unconditionally on 64-bit, and
use the better constant" should fix the actual _practical_ problems
that we've seen. And it shouldn't have any negative consequences,
since as you say, 64-bit architectures universally do have a
multiplier.

The bigger changes will have to be for 4.7 by now, I think.

                     Linus

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-04-30 23:00 +0200
  Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-01 10:40 +0200
    Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-05-01 11:50 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-01 19:00 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-02 09:20 +0200
        [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
          [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
            Re: [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 22:10 +0200
          [RFC PATCH 3/2] (Rant) Fix various hash abuses "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
          [RFC PATCH 4/2] namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS "George Spelvin" <linux@horizon.com> - 2016-05-02 12:40 +0200
          Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32  bits Peter Zijlstra <peterz@infradead.org> - 2016-05-02 15:30 +0200
            Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 21:10 +0200
          Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 18:30 +0200
            Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 22:30 +0200
              Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:20 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:50 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-03 04:00 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-03 05:10 +0200

csiph-web