Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753228AbcD1Qnp (ORCPT ); Thu, 28 Apr 2016 12:43:45 -0400 Received: from www.linutronix.de ([62.245.132.108]:58900 "EHLO Galois.linutronix.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752666AbcD1Qnn (ORCPT ); Thu, 28 Apr 2016 12:43:43 -0400 Message-Id: <20160428163525.495514517@linutronix.de> User-Agent: quilt/0.63-1 Date: Thu, 28 Apr 2016 16:42:08 -0000 From: Thomas Gleixner To: LKML Cc: Peter Zijlstra , Ingo Molnar , Linus Torvalds , Andrew Morton , Sebastian Andrzej Siewior , Darren Hart , Michael Kerrisk , Davidlohr Bueso , Chris Mason , "Carlos O'Donell" , Torvald Riegel , Eric Dumazet Subject: [patch 2/7] lib/hashmod: Add modulo based hash mechanism References: <20160428161742.363543816@linutronix.de> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Disposition: inline; filename=lib-hashmod-Add-modulo-based-hash-mechanism.patch X-Linutronix-Spam-Score: -1.0 X-Linutronix-Spam-Level: - X-Linutronix-Spam-Status: No , -1.0 points, 5.0 required, ALL_TRUSTED=-1,SHORTCIRCUIT=-0.0001,URIBL_BLOCKED=0.001 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3516 Lines: 123 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 --- 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 +#include +#include +#include + +#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; +}