• 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
Name
Last commit
Last update
..
acpi Loading commit data...
asm-generic Loading commit data...
clocksource Loading commit data...
crypto Loading commit data...
drm Loading commit data...
dt-bindings Loading commit data...
keys Loading commit data...
kvm Loading commit data...
linux Loading commit data...
math-emu Loading commit data...
media Loading commit data...
memory Loading commit data...
misc Loading commit data...
net Loading commit data...
pcmcia Loading commit data...
ras Loading commit data...
rdma Loading commit data...
rxrpc Loading commit data...
scsi Loading commit data...
soc Loading commit data...
sound Loading commit data...
target Loading commit data...
trace Loading commit data...
uapi Loading commit data...
video Loading commit data...
xen Loading commit data...
Kbuild Loading commit data...