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 <t...@linutronix.de>
---
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;
+}
