[PATCH v3 00/10] String hash improvements
From: George Spelvin
Date: Sat May 28 2016 - 15:58:00 EST
Okay, Linus, it's still warm from the oven, but I think it's fully baked.
Special thanks to J. Bruce Fields for testing and finding bugs in v1.
(I learned some humbling lessons about "obviously correct" code.)
On the arch-specific front, the m68k assembly has been tested in
a standalone test harness, I've been in contact with the Microblaze
maintainers who mostly don't care, as the hardware multiplier is never
omitted in real-world applications, and I haven't heard anything from
the H8/300 world.
You can either drop them in and we can debug them during -rc, or
I can send them through the arch trees for 4.8.
This series does several related things:
1) Makes the dcache hash (fs/namei.c) useful for general kernel use.
(Thanks to Bruce for noticing the zero-length corner case.)
2) Converts the string hashes in <linux/sunrpc/svcauth.h> to use the above.
3) Avoids 64-bit multiplies in hash_64() on 32-bit platforms.
Two 32-bit multiplies will do well enough.
4) Rids the world of the bad hash multipliers in hash_32.
This finishes the job started in 689de1d6ca.
The vast majority of Linux architectures have hardware support
for 32x32-bit multiply and so derive no benefit from "simplified"
The few processors that do not (68000, h8/300 and some models of
Microblaze) have arch-specific implementations added. Those patches
are last in the series so they can go through the relevant arch
5) Overhauls the dcache hash mixing.
The patch in 2bf0b16954 was an off-the-cuff suggestion. Replaced with
a much more careful design that's simultaneously faster and better.
(My own invention, as there was noting suitable in the literature I
could find. Comments welcome!)
Things I thought about but can wait for now:
6) Modify the hash_name() loop to skip the initial HASH_MIX().
That would let us salt the hash if we ever wanted to.
7) Sort out partial_name_hash().
The hash function is declared as using a long state, even though
it's truncated to 32 bits at the end and the extra internal state
contributes nothing to the result. And some callers do odd things:
* fs/hfs/string.c only allocates 32 bits of state
* fs/hfsplus/unicode.c uses it to hash 16-bit unicode symbols not bytes
8) Modify bytemask_from_count to handle inputs of 1..sizeof(long)
rather than 0..sizeof(long)-1. This would simplify users other
George Spelvin (10):
Pull out string hash to <linux/stringhash.h>
fs/namei.c: Add hashlen_string() function
<linux/sunrpc/svcauth.h>: Define hash_str() in terms of hashlen_string()
Change hash_64() return value to 32 bits
Eliminate bad hash multipliers from hash_32() and hash_64()
fs/namei.c: Improve dcache hash function
<linux/hash.h>: Add support for architecture-specific functions
m68k: Add <asm/hash.h>
microblaze: Add <asm/hash.h>
h8300: Add <asm/hash.h>
arch/Kconfig | 8 ++
arch/h8300/Kconfig | 1 +
arch/h8300/include/asm/hash.h | 53 +++++++
arch/m68k/Kconfig.cpu | 1 +
arch/m68k/include/asm/hash.h | 59 ++++++++
arch/microblaze/Kconfig | 1 +
arch/microblaze/include/asm/hash.h | 81 +++++++++++
drivers/media/usb/dvb-usb-v2/af9015.c | 2 +
fs/dcache.c | 3 +-
fs/namei.c | 160 +++++++++++++++++-----
include/linux/dcache.h | 27 +---
include/linux/hash.h | 112 +++++++--------
include/linux/stringhash.h | 76 +++++++++++
include/linux/sunrpc/svcauth.h | 40 ++----
lib/Kconfig.debug | 11 ++
lib/Makefile | 1 +
lib/test_hash.c | 250 ++++++++++++++++++++++++++++++++++
17 files changed, 735 insertions(+), 151 deletions(-)
create mode 100644 arch/h8300/include/asm/hash.h
create mode 100644 arch/m68k/include/asm/hash.h
create mode 100644 arch/microblaze/include/asm/hash.h
create mode 100644 include/linux/stringhash.h
create mode 100644 lib/test_hash.c