[patch 2/7] lib/hashmod: Add modulo based hash mechanism

[Thomas Gleixner]

hash_long/hash_ptr() provide really bad hashing for small hash sizes and for
cases where the lower 12 bits (Page size aligned) of the hash value are 0.

A simple modulo(prime) based hash function has way better results
across a wide range of input values. The implementation uses invers
multiplication instead of a slow division.

A futex benchmark shows better results up to a factor 10 on small hashes.

Signed-off-by: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
---
 include/linux/hash.h |   28 ++++++++++++++++++++++++++++
 lib/Kconfig          |    3 +++
 lib/Makefile         |    1 +
 lib/hashmod.c        |   44 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 76 insertions(+)
 create mode 100644 lib/hashmod.c

--- a/include/linux/hash.h
+++ b/include/linux/hash.h
@@ -83,4 +83,32 @@ static inline u32 hash32_ptr(const void
 	return (u32)val;
 }
 
+struct hash_modulo {
+	unsigned int	pmul;
+	unsigned int	prime;
+	unsigned int	mask;
+};
+
+#ifdef CONFIG_HASH_MODULO
+
+int hash_modulo_params(unsigned int hash_bits, struct hash_modulo *hm);
+
+/**
+ * hash_mod - FIXME
+ */
+static inline unsigned int hash_mod(unsigned long addr, struct hash_modulo *hm)
+{
+	u32 a, m;
+
+	if (IS_ENABLED(CONFIG_64BIT)) {
+		a =  addr >> 32;
+		a ^= (unsigned int) addr;
+	} else {
+		a = addr;
+	}
+	m = ((u64)a * hm->pmul) >> 32;
+	return (a - m * hm->prime) & hm->mask;
+}
+#endif
+
 #endif /* _LINUX_HASH_H */
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -185,6 +185,9 @@ config CRC8
 	  when they need to do cyclic redundancy check according CRC8
 	  algorithm. Module will be called crc8.
 
+config HASH_MODULO
+       bool
+
 config AUDIT_GENERIC
 	bool
 	depends on AUDIT && !AUDIT_ARCH
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -97,6 +97,7 @@ obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
 obj-$(CONFIG_CRC8)	+= crc8.o
+obj-$(CONFIG_HASH_MODULO) += hashmod.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_842_COMPRESS) += 842/
--- /dev/null
+++ b/lib/hashmod.c
@@ -0,0 +1,44 @@
+/*
+ * Modulo based hash - Global helper functions
+ *
+ * (C) 2016 Linutronix GmbH, Thomas Gleixner
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public Licence version 2 as published by
+ * the Free Software Foundation;
+ */
+
+#include <linux/hash.h>
+#include <linux/errno,h>
+#include <linux/bug.h>
+#include <linux/kernel.h>
+
+#define hash_pmul(prime)	((unsigned int)((1ULL << 32) / prime))
+
+static const struct hash_modulo hash_modulo[] = {
+	{ .prime =    3, .pmul = hash_pmul(3),    .mask = 0x0003 },
+	{ .prime =    7, .pmul = hash_pmul(7),    .mask = 0x0007 },
+	{ .prime =   13, .pmul = hash_pmul(13),   .mask = 0x000f },
+	{ .prime =   31, .pmul = hash_pmul(31),   .mask = 0x001f },
+	{ .prime =   61, .pmul = hash_pmul(61),   .mask = 0x003f },
+	{ .prime =  127, .pmul = hash_pmul(127),  .mask = 0x007f },
+	{ .prime =  251, .pmul = hash_pmul(251),  .mask = 0x00ff },
+	{ .prime =  509, .pmul = hash_pmul(509),  .mask = 0x01ff },
+	{ .prime = 1021, .pmul = hash_pmul(1021), .mask = 0x03ff },
+	{ .prime = 2039, .pmul = hash_pmul(2039), .mask = 0x07ff },
+	{ .prime = 4093, .pmul = hash_pmul(4093), .mask = 0x0fff },
+};
+
+/**
+ * hash_modulo_params - FIXME
+ */
+int hash_modulo_params(unsigned int hash_bits, struct hash_modulo *hm)
+{
+	hash_bits -= 2;
+
+	if (hash_bits >= ARRAY_SIZE(hash_modulo))
+		return -EINVAL;
+
+	*hm = hash_modulo[hash_bits];
+	return 0;
+}