Merge branch 'hash' of git://ftp.sciencehorizons.net/linux
authorLinus Torvalds <torvalds@linux-foundation.org>
Sat, 28 May 2016 23:15:25 +0000 (16:15 -0700)
committerLinus Torvalds <torvalds@linux-foundation.org>
Sat, 28 May 2016 23:15:25 +0000 (16:15 -0700)
Pull string hash improvements from George Spelvin:
 "This series does several related things:

   - Makes the dcache hash (fs/namei.c) useful for general kernel use.

     (Thanks to Bruce for noticing the zero-length corner case)

   - Converts the string hashes in <linux/sunrpc/svcauth.h> to use the
     above.

   - Avoids 64-bit multiplies in hash_64() on 32-bit platforms.  Two
     32-bit multiplies will do well enough.

   - Rids the world of the bad hash multipliers in hash_32.

     This finishes the job started in commit 689de1d6ca95 ("Minimal
     fix-up of bad hashing behavior of hash_64()")

     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.

   - Overhauls the dcache hash mixing.

     The patch in commit 0fed3ac866ea ("namei: Improve hash mixing if
     CONFIG_DCACHE_WORD_ACCESS") 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!)

   - Modify the hash_name() loop to skip the initial HASH_MIX().  This
     would let us salt the hash if we ever wanted to.

   - 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

   - 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"

  Special thanks to 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"

* 'hash' of git://ftp.sciencehorizons.net/linux:
  h8300: Add <asm/hash.h>
  microblaze: Add <asm/hash.h>
  m68k: Add <asm/hash.h>
  <linux/hash.h>: Add support for architecture-specific functions
  fs/namei.c: Improve dcache hash function
  Eliminate bad hash multipliers from hash_32() and  hash_64()
  Change hash_64() return value to 32 bits
  <linux/sunrpc/svcauth.h>: Define hash_str() in terms of hashlen_string()
  fs/namei.c: Add hashlen_string() function
  Pull out string hash to <linux/stringhash.h>

1  2 
arch/Kconfig
arch/h8300/Kconfig
arch/m68k/Kconfig.cpu
arch/microblaze/Kconfig
fs/dcache.c
fs/namei.c
include/linux/dcache.h
lib/Kconfig.debug
lib/Makefile

diff --cc arch/Kconfig
Simple merge
index aa232de2d4bc854a7c25b73a538dc7bcf7df755e,6c583dbbc1196948b15d01e84c0ae213586caffa..3ae852507e57952332c1b260520a631d3ec37c69
@@@ -20,7 -20,7 +20,8 @@@ config H830
        select HAVE_KERNEL_GZIP
        select HAVE_KERNEL_LZO
        select HAVE_ARCH_KGDB
+       select HAVE_ARCH_HASH
 +      select CPU_NO_EFFICIENT_FFS
  
  config RWSEM_GENERIC_SPINLOCK
        def_bool y
index 8ace920ca24aaf1d491db0f7038a60e2bbc58237,bf3de464cf3c5eda2f78d2a1fdc0adb21f75e4bc..967260f2eb1cce36e6295c36d791b5a141dd667e
@@@ -40,7 -40,7 +40,8 @@@ config M6800
        select CPU_HAS_NO_MULDIV64
        select CPU_HAS_NO_UNALIGNED
        select GENERIC_CSUM
 +      select CPU_NO_EFFICIENT_FFS
+       select HAVE_ARCH_HASH
        help
          The Freescale (was Motorola) 68000 CPU is the first generation of
          the well known M68K family of processors. The CPU core as well as
Simple merge
diff --cc fs/dcache.c
Simple merge
diff --cc fs/namei.c
Simple merge
Simple merge
Simple merge
diff --cc lib/Makefile
Simple merge