Allow 32-bit and 64-bit hashes
PATCH 1/1 Allow 32-bit and 64-bit hashes
The sym2 driver would like to hash a u32 value, and it could just call hash_long() and rely on integer promotion on 64-bit machines, but that seems a little wasteful.
Following Arjan's suggestion, I split the existing hash_long into hash_u32 and hash_u64, and made hash_long an alias to the appropriate function.
include/linux/hash.h +22 -13
@@ -13,23 +13,36 @@* them can use shifts and additions instead of multiplications for * machines where multiplications are slow. */ -#if BITS_PER_LONG ==32 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e370001UL -#elif BITS_PER_LONG ==64 +#define GOLDEN_RATIO_PRIME_32 0x9e370001UL/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL +#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL + +#if BITS_PER_LONG ==32 +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32 +#define hash_long (val, bits) hash_u32(val, bits) +#elif BITS_PER_LONG ==64 +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 +#define hash_long (val, bits) hash_u64(val, bits)#else #error Define GOLDEN_RATIO_PRIME for your wordsize.#endif -static inline unsigned long hash_long (unsigned long val,unsigned int bits) +static inline unsigned long hash_u32 (u32 val,unsigned int bits) +{ +/* On some cpus multiply is faster, on others gcc will do shifts */ +unsigned int hash = val *GOLDEN_RATIO_PRIME_32 ; + +/* High bits are more random, so use them. */ +return hash >> (32 - bits); +} + +static inline unsigned long hash_u64 (u64 val,unsigned int bits) { -unsigned long hash = val; +u64 hash = val; -#if BITS_PER_LONG ==64 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ -unsigned long n = hash; +u64 n = hash; n <<=18 ; hash -= n; n <<=33 ;
@@ -42,13 +55,9 @@ static inline unsigned long hash_long(un hash += n; n <<=2 ; hash += n; -#else -/* On some cpus multiply is faster, on others gcc will do shifts */ - hash *=GOLDEN_RATIO_PRIME ; -#endif /* High bits are more random, so use them. */ -return hash >> (BITS_PER_LONG - bits); +return hash >> (64 - bits); }static inline unsigned long hash_ptr (void *ptr,unsigned int bits)
Quoted 4 lines · Matthew Wilcox
The sym2 driver would like to hash a u32 value, and it could just call
hash_long()and rely on integer promotion on 64-bit machines, but that seems a little wasteful.
Hmm. It would appear that the <linux/hash.h> file now needs <linux/types.h>, no?
I do think it's a good change otherwise.
Linus
Quoted 8 lines · Linus Torvalds
Quoted 4 lines · Matthew Wilcox
The sym2 driver would like to hash a u32 value, and it could just call
hash_long()and rely on integer promotion on 64-bit machines, but that seems a little wasteful.Hmm. It would appear that the <
linux/hash.h> file now needs <linux/types.h>, no?
You're right. It hasn't actually caused any problems, presumably due to linux/types.h being included absolutely everywhere already, but it's clearly the Right Thing To Do. Updated patch:
-----
Allow 32-bit and 64-bit hashes
The sym2 driver would like to hash a u32 value, and it could just call hash_long() and rely on integer promotion on 64-bit machines, but that seems a little wasteful.
Following Arjan's suggestion, I split the existing hash_long into hash_u32 and hash_u64, and made hash_long an alias to the appropriate function.
include/linux/hash.h +24 -13
@@ -3,6 +3,8 @@/* Fast hashing routine for a long. (C) 2002 William Lee Irwin III, IBM */ +#include <linux/types.h> +/* * Knuth recommends primes in approximately golden ratio to the maximum * integer representable by a machine word for multiplicative hashing.
@@ -13,23 +15,36 @@* them can use shifts and additions instead of multiplications for * machines where multiplications are slow. */ -#if BITS_PER_LONG ==32 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e370001UL -#elif BITS_PER_LONG ==64 +#define GOLDEN_RATIO_PRIME_32 0x9e370001UL/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL +#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL + +#if BITS_PER_LONG ==32 +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32 +#define hash_long (val, bits) hash_u32(val, bits) +#elif BITS_PER_LONG ==64 +#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 +#define hash_long (val, bits) hash_u64(val, bits)#else #error Define GOLDEN_RATIO_PRIME for your wordsize.#endif -static inline unsigned long hash_long (unsigned long val,unsigned int bits) +static inline unsigned long hash_u32 (u32 val,unsigned int bits) { -unsigned long hash = val; +/* On some cpus multiply is faster, on others gcc will do shifts */ +unsigned int hash = val *GOLDEN_RATIO_PRIME_32 ; + +/* High bits are more random, so use them. */ +return hash >> (32 - bits); +} + +static inline unsigned long hash_u64 (u64 val,unsigned int bits) +{ +u64 hash = val; -#if BITS_PER_LONG ==64 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ -unsigned long n = hash; +u64 n = hash; n <<=18 ; hash -= n; n <<=33 ;
@@ -42,13 +57,9 @@ static inline unsigned long hash_long(un hash += n; n <<=2 ; hash += n; -#else -/* On some cpus multiply is faster, on others gcc will do shifts */ - hash *=GOLDEN_RATIO_PRIME ; -#endif /* High bits are more random, so use them. */ -return hash >> (BITS_PER_LONG - bits); +return hash >> (64 - bits); }static inline unsigned long hash_ptr (void *ptr,unsigned int bits)
Quoted 4 lines · Matthew Wilcox
You're right. It hasn't actually caused any problems, presumably due to
linux/types.hbeing included absolutely everywhere already, but it's clearly the Right Thing To Do. Updated patch:
I'm still not happy.
The return value of "hash_u64()" had better be u64, not "unsigned long".
Same goes (to a smaller degree) for hash_u32().
I can trivially just edit the patch and fix these things, but with two bugs found by just inspection of the patch, I'm going to ask you to look it over one more time and re-send me a "guaranteed correct" version, ok?
Because I'm a very religious man, and my religion basically boils down to
"If somebody else can do it for me, they should. I'm lazy, and I like it
that way. Besides, next time maybe they'll double-check on their own".
Thanks. And please spread the Good Word.
Linus