]> git.baikalelectronics.ru Git - kernel.git/commit
Minimal fix-up of bad hashing behavior of hash_64()
authorLinus Torvalds <torvalds@linux-foundation.org>
Mon, 2 May 2016 19:46:42 +0000 (12:46 -0700)
committerLinus Torvalds <torvalds@linux-foundation.org>
Mon, 2 May 2016 20:01:51 +0000 (13:01 -0700)
commit444f572ec770d9625a74e1ed10a87f95fa95493c
tree643d7ff65d5c5f1af59ae9cd5d09a5d453976010
parent9958c749947986013da1e2a75b1f568c7370aafd
Minimal fix-up of bad hashing behavior of hash_64()

This is a fairly minimal fixup to the horribly bad behavior of hash_64()
with certain input patterns.

In particular, because the multiplicative value used for the 64-bit hash
was intentionally bit-sparse (so that the multiply could be done with
shifts and adds on architectures without hardware multipliers), some
bits did not get spread out very much.  In particular, certain fairly
common bit ranges in the input (roughly bits 12-20: commonly with the
most information in them when you hash things like byte offsets in files
or memory that have block factors that mean that the low bits are often
zero) would not necessarily show up much in the result.

There's a bigger patch-series brewing to fix up things more completely,
but this is the fairly minimal fix for the 64-bit hashing problem.  It
simply picks a much better constant multiplier, spreading the bits out a
lot better.

NOTE! For 32-bit architectures, the bad old hash_64() remains the same
for now, since 64-bit multiplies are expensive.  The bigger hashing
cleanup will replace the 32-bit case with something better.

The new constants were picked by George Spelvin who wrote that bigger
cleanup series.  I just picked out the constants and part of the comment
from that series.

Cc: stable@vger.kernel.org
Cc: George Spelvin <linux@horizon.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
include/linux/hash.h