From: Thomas Gleixner <tglx@linutronix.de>
To: LKML <linux-kernel@vger.kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@kernel.org>,
Linus Torvalds <torvalds@linux-foundation.org>,
Andrew Morton <akpm@linux-foundation.org>,
Sebastian Andrzej Siewior <bigeasy@linutronix.de>,
Darren Hart <darren@dvhart.com>,
Michael Kerrisk <mtk.manpages@googlemail.com>,
Davidlohr Bueso <dave@stgolabs.net>, Chris Mason <clm@fb.com>,
"Carlos O'Donell" <carlos@redhat.com>,
Torvald Riegel <triegel@redhat.com>,
Eric Dumazet <edumazet@google.com>
Subject: [patch 2/7] lib/hashmod: Add modulo based hash mechanism
Date: Thu, 28 Apr 2016 16:42:08 -0000 [thread overview]
Message-ID: <20160428163525.495514517@linutronix.de> (raw)
In-Reply-To: 20160428161742.363543816@linutronix.de
[-- Attachment #1: lib-hashmod-Add-modulo-based-hash-mechanism.patch --]
[-- Type: text/plain, Size: 3515 bytes --]
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@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;
+}
next prev parent reply other threads:[~2016-04-28 16:43 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-04-28 16:42 [patch 0/7] futex: Add support for process private hashing Thomas Gleixner
2016-04-28 16:42 ` [patch 1/7] futex: Add some more function commentry Thomas Gleixner
2016-04-28 16:42 ` Thomas Gleixner [this message]
2016-04-28 18:32 ` [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds
2016-04-28 23:26 ` Thomas Gleixner
2016-04-29 2:25 ` Linus Torvalds
2016-04-30 13:02 ` Thomas Gleixner
2016-04-30 16:45 ` Eric Dumazet
2016-04-30 17:12 ` Linus Torvalds
2016-04-30 17:37 ` Eric Dumazet
2016-06-12 12:18 ` Sandy Harris
2016-04-29 21:10 ` Linus Torvalds
2016-04-29 23:51 ` Linus Torvalds
2016-04-30 1:34 ` Rik van Riel
2016-05-02 9:39 ` Torvald Riegel
2016-04-30 15:22 ` Thomas Gleixner
2016-04-28 16:42 ` [patch 3/7] futex: Hash private futexes per process Thomas Gleixner
2016-04-28 16:42 ` [patch 4/7] futex: Add op for hash preallocation Thomas Gleixner
2016-04-28 16:42 ` [patch 5/7] futex: Add sysctl knobs for process private hash Thomas Gleixner
2016-04-28 16:42 ` [patch 6/7] perf/bench/futex-hash: Support NUMA Thomas Gleixner
2016-04-28 16:42 ` [patch 7/7] perf/bench/futex-hash: Support preallocate hash table Thomas Gleixner
2016-04-29 2:57 [patch 2/7] lib/hashmod: Add modulo based hash mechanism George Spelvin
2016-04-29 3:16 ` Linus Torvalds
2016-04-29 4:12 ` George Spelvin
2016-04-29 23:31 ` George Spelvin
2016-04-30 0:05 ` Linus Torvalds
2016-04-30 0:32 ` George Spelvin
2016-04-30 1:12 ` Linus Torvalds
2016-04-30 3:04 ` George Spelvin
[not found] <CA+55aFxBWfAHQNAdBbdVr+z8ror4GVteyce3D3=vwDWxhu5KqQ@mail.gmail.com>
2016-04-30 20:52 ` George Spelvin
2016-05-01 8:35 ` Thomas Gleixner
2016-05-01 9:43 ` George Spelvin
2016-05-01 16:51 ` Linus Torvalds
2016-05-14 3:54 ` George Spelvin
2016-05-14 18:35 ` Linus Torvalds
2016-05-02 7:11 ` Thomas Gleixner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160428163525.495514517@linutronix.de \
--to=tglx@linutronix.de \
--cc=akpm@linux-foundation.org \
--cc=bigeasy@linutronix.de \
--cc=carlos@redhat.com \
--cc=clm@fb.com \
--cc=darren@dvhart.com \
--cc=dave@stgolabs.net \
--cc=edumazet@google.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=mtk.manpages@googlemail.com \
--cc=peterz@infradead.org \
--cc=torvalds@linux-foundation.org \
--cc=triegel@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).