• Linus Torvalds's avatar
    Merge branch 'hash' of git://ftp.sciencehorizons.net/linux · 7e0fb73c
    Linus Torvalds authored
    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 689de1d6 ("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 0fed3ac8 ("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>
    7e0fb73c
Kconfig 19.2 KB