[PATCH v3 00/10] String hash improvements

[George Spelvin]

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"
   multipliers.
   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
   maintainers.
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
   than full_name_hash.

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

-- 
2.8.1