linux-kernel - Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CA+55aFyncfSsV=bmqS4gHAiKg8GwQEnjB2Fpn0OPqozm5QsxmA@mail.gmail.com>
Date:	Sat, 30 Apr 2016 10:12:38 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	Thomas Gleixner <tglx@...utronix.de>,
	LKML <linux-kernel@...r.kernel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...nel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Sebastian Andrzej Siewior <bigeasy@...utronix.de>,
	Darren Hart <darren@...art.com>,
	Michael Kerrisk <mtk.manpages@...glemail.com>,
	Davidlohr Bueso <dave@...olabs.net>, Chris Mason <clm@...com>,
	"Carlos O'Donell" <carlos@...hat.com>,
	Torvald Riegel <triegel@...hat.com>,
	Eric Dumazet <edumazet@...gle.com>
Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

On Sat, Apr 30, 2016 at 9:45 AM, Eric Dumazet <eric.dumazet@...il.com> wrote:
>
> I use hash_32() in net/sched/sch_fq.c, for all packets sent by Google
> servers. (Note that I did _not_ use hash_ptr())
>
> That's gazillions of packets per second, and the current multiply worked
> just fine in term of hash spreading.

So hash_32() really is much better than hash_64(). I think we'll tweak
it a bit, but largely leave it alone.

The 64-bit case needs to be tweaked a _lot_.

For the 32-bit case, I like the one that George Spelvin suggested:

   #define GOLDEN_RATIO_32 0x61c88647      /* phi^2 = 1-phi */

because of his slow multiplier fallback version that we could also use:

  /* Returns x * GOLDEN_RATIO_32 without a hardware multiplier */
  unsigned hash_32(unsigned x)
  {
          unsigned y, z;
                                /* Path length */
          y = (x << 19) + x;      /* 1 shift + 1 add */
          z = (x << 9) + y;       /* 1 shift + 2 add */
          x = (x << 23) + z;      /* 1 shift + 3 add */
          z = (z << 8) + y;       /* 2 shift + 3 add */
          x = (x << 6) - x;       /* 2 shift + 4 add */
          return (z << 3) + x;    /* 3 shift + 4 add */
  }

and I don't think that we really need the several big constants with
the fancy "full cascade" function.

If you have a test-case for that sch_fq.c case, it might be a good
idea to test the above GOLDEN_RATIO_32 value, but quite frankly, I
don't see any way it would be materially different from the one we use
now. It does avoid that long series of zeroes in the low bits, but
that's actually not a huge problem for the 32-bit hash to begin with.
It's not nearly as long a series (or in the wrong bit positions) as
the 64-bit hash multiplier value had.

Also, I suspect that since you hash the kernel "struct sock" pointers,
you actually never get the kinds of really bad patterns that Thomas
had.

But maybe you use hash_32() on a pointer because you noticed that
hash_long() or hash_ptr() (which use hash_64 on 64-bit architectures,
and would have been more natural) gave worse performance?

Maybe you thought that it was the bigger multiply that caused the
performance problems? If you did performance work, I suspect it really
could have been that hash_64() did a bad job for you.

                 Linus