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

Groups > linux.kernel > #1397568

[PATCH 3.19.y-ckt 37/54] Minimal fix-up of bad hashing behavior of hash_64()

Show all headers | View raw

3.19.8-ckt21 -stable review patch.  If anyone has any objections, please let me know.

---8<------------------------------------------------------------

From: Linus Torvalds <torvalds@linux-foundation.org>

commit 689de1d6ca95b3b5bd8ee446863bf81a4883ea25 upstream.

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: George Spelvin <linux@horizon.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Kamal Mostafa <kamal@canonical.com>
---
 include/linux/hash.h | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)

diff --git a/include/linux/hash.h b/include/linux/hash.h
index 1afde47..79c52fa 100644
--- a/include/linux/hash.h
+++ b/include/linux/hash.h
@@ -32,12 +32,28 @@
 #error Wordsize not 32 or 64
 #endif
 
+/*
+ * The above primes are actively bad for hashing, since they are
+ * too sparse. The 32-bit one is mostly ok, the 64-bit one causes
+ * real problems. Besides, the "prime" part is pointless for the
+ * multiplicative hash.
+ *
+ * Although a random odd number will do, it turns out that the golden
+ * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
+ * properties.
+ *
+ * These are the negative, (1 - phi) = (phi^2) = (3 - sqrt(5))/2.
+ * (See Knuth vol 3, section 6.4, exercise 9.)
+ */
+#define GOLDEN_RATIO_32 0x61C88647
+#define GOLDEN_RATIO_64 0x61C8864680B583EBull
+
 static __always_inline u64 hash_64(u64 val, unsigned int bits)
 {
 	u64 hash = val;
 
-#if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64
-	hash = hash * GOLDEN_RATIO_PRIME_64;
+#if BITS_PER_LONG == 64
+	hash = hash * GOLDEN_RATIO_64;
 #else
 	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 	u64 n = hash;
-- 
2.7.4

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

Thread

[3.19.y-ckt stable] Linux 3.19.8-ckt21 stable review Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 42/54] x86/sysfb_efi: Fix valid BAR address range check Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 53/54] cxgbi: fix uninitialized flowi6 Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 14/54] mm: split ET_DYN ASLR from mmap ASLR Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 51/54] batman-adv: Reduce refcnt of removed router when updating route Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 18/54] ASoC: dapm: Make sure we have a card when displaying component widgets Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 11/54] s390: standardize mmap_rnd() usage Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 04/54] arm: factor out mmap ASLR into mmap_rnd Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 52/54] batman-adv: Fix broadcast/ogm queue limit on a removed interface Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 31/54] ARM: SoCFPGA: Fix secondary CPU startup in thumb2 kernel Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 48/54] jme: Do not enable NIC WoL functions on S0 Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 54/54] net/mlx4_en: fix spurious timestamping callbacks Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 12/54] mm: expose arch_mmap_rnd when available Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:10 +0200
  [PATCH 3.19.y-ckt 20/54] i2c: cpm: Fix build break due to incompatible pointer types Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 21/54] i2c: exynos5: Fix possible ABBA deadlock by keeping I2C clock prepared Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 37/54] Minimal fix-up of bad hashing behavior of hash_64() Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 36/54] powerpc: Fix bad inline asm constraint in create_zero_mask() Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 32/54] IB/security: Restrict use of the write() interface Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 24/54] USB: serial: cp210x: add Straizona Focusers device ids Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 09/54] s390: avoid z13 cache aliasing Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 34/54] mm: vmscan: reclaim highmem zone if buffer_heads is over limit Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 28/54] cxl: Keep IRQ mappings on context teardown Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 26/54] workqueue: fix ghost PENDING flag while doing MQ IO Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 27/54] drm/dp/mst: Get validated port ref in drm_dp_update_payload_part1() Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 29/54] drm/i915: Fix system resume if PCI device remained enabled Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 08/54] powerpc: standardize mmap_rnd() usage Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 40/54] MAINTAINERS: Remove asterisk from EFI directory names Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 41/54] ACPICA: Dispatcher: Update thread ID for recursive method calls Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 47/54] parisc: fix a bug when syscall number of tracee is __NR_Linux_syscalls Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 25/54] ALSA: hda - Add dock support for ThinkPad X260 Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 23/54] USB: serial: cp210x: add ID for Link ECU Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 13/54] s390: redefine randomize_et_dyn for ELF_ET_DYN_BASE Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 30/54] drm/i915/ddi: Fix eDP VDD handling during booting and suspend/resume Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 35/54] EDAC: i7core, sb_edac: Don't return NOTIFY_BAD from mce_decoder callback Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 06/54] arm64: standardize mmap_rnd() usage Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 43/54] fs/pnode.c: treat zero mnt_group_id-s as unequal Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 44/54] propogate_mnt: Handle the first propogated copy being a slave Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 33/54] mm/huge_memory: replace VM_NO_THP VM_BUG_ON with actual VMA check Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 10/54] s390/mm: align 64-bit PIE binaries to 4GB Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 17/54] ASoC: rt5640: Correct the digital interface data select Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 46/54] x86/tsc: Read all ratio bits from MSR_PLATFORM_INFO Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 39/54] drm/radeon: make sure vertical front porch is at least 1 Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 19/54] iio: ak8975: Fix NULL pointer exception on early interrupt Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:20 +0200
  [PATCH 3.19.y-ckt 07/54] mips: extract logic for mmap_rnd() Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:30 +0200
  [PATCH 3.19.y-ckt 01/54] [3.19-stable-only] Revert "powerpc: Update TM user feature bits in scan_features()" Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:30 +0200
    Re: [PATCH 3.19.y-ckt 01/54] [3.19-stable-only] Revert "powerpc:  Update TM user feature bits in scan_features()" Michael Ellerman <mpe@ellerman.id.au> - 2016-05-10 03:50 +0200
  [PATCH 3.19.y-ckt 02/54] [3.19-stable-only] fix backport "KVM: s390: avoid memory overwrites on emergency signal injection" Kamal Mostafa <kamal@canonical.com> - 2016-05-10 02:30 +0200

csiph-web