Submssions for 2.4.19-pre [Fibonacci Hashing (William Lee Irwin)] [Discuss :) ]
Subsystems (3)
This is the second of several mails containing patches to be included in 2.4.19. Some are worthy of dicussion prior to inclusion and have been marked as such. The majority of these patches were found on lkml; the remaining ones have URLs listed.
This one was given to me by WLI himself; I have a feeling that ftp://ftp.XX.kernel.org/pub/linux/kernel/people/wli might have it in pieces, or /pub/linux/kernel/people/mjc/testing/mjc4p2.tar.bz2 also has it.
This version at least will compile on all arches that 2.4.19-pre1 will, and a note is given for arches where the sparse golden ratio prime given is definately not the optimal (non-32bit arches). I will try to help wli find a better prime for 64bit soon. Testing on other arches is, of course, appreciated.
------
Michael Cohen
OhDarn.net
fs/inode.c +6 -5
@@ -901,12 +901,13 @@static inline unsigned long hash (struct super_block *sb,unsigned long i_ino) { -unsigned long tmp = i_ino + ((unsigned long ) sb /L1_CACHE_BYTES ); - tmp = tmp + (tmp >>I_HASHBITS ); -return tmp &I_HASHMASK ; +unsigned long hash; + hash = i_ino + (unsigned long ) sb; + hash *=SPARSE_GOLDEN_RATIO_PRIME ; + hash >>=BITS_PER_LONG -I_HASHBITS ; + hash &=I_HASHMASK ; +return hash; } - -/* Yeah, I know about quadratic hash. Maybe, later. */ /** * iunique - get a unique inode number
include/asm-alpha/param.h +7 -0
@@ -15,6 +15,13 @@# endif #endif +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 8192#ifndef NGROUPS
include/asm-arm/param.h +4 -0
@@ -20,6 +20,10 @@#define hz_to_std (a) (a)#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +#ifndef NGROUPS #define NGROUPS 32#endif
include/asm-cris/param.h +5 -0
@@ -5,6 +5,11 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 8192#ifndef NGROUPS
include/asm-i386/param.h +4 -0
@@ -5,6 +5,10 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-ia64/param.h +6 -0
@@ -20,6 +20,12 @@# define HZ 1024#endif +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +#define EXEC_PAGESIZE 65536#ifndef NGROUPS
include/asm-m68k/param.h +5 -0
@@ -5,6 +5,11 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 8192#ifndef NGROUPS
include/asm-mips/param.h +5 -0
@@ -52,6 +52,11 @@#endif /* defined(__KERNEL__) */ #endif /* defined(HZ) */ +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-mips64/param.h +7 -0
@@ -17,6 +17,13 @@#endif #endif +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. +*/ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-parisc/param.h +7 -0
@@ -5,6 +5,13 @@#define HZ 100#endif +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-ppc/param.h +4 -0
@@ -8,6 +8,10 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-s390/param.h +5 -0
@@ -13,6 +13,11 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-s390x/param.h +7 -0
@@ -16,6 +16,13 @@#endif #endif +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-sh/param.h +5 -0
@@ -5,6 +5,11 @@#define HZ 100#endif +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 4096#ifndef NGROUPS
include/asm-sparc/param.h +5 -1
@@ -6,7 +6,11 @@#define HZ 100#endif -#define EXEC_PAGESIZE 8192/* Thanks for sun4's we carry baggage... */ +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + +#define EXEC_PAGESIZE 8192/* Thanks to sun4's we carry baggage... */ #ifndef NGROUPS #define NGROUPS 32
include/asm-sparc64/param.h +8 -1
@@ -6,7 +6,14 @@#define HZ 100#endif -#define EXEC_PAGESIZE 8192/* Thanks for sun4's we carry baggage... */ +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif + + +#define EXEC_PAGESIZE 8192/* Thanks to sun4's we carry baggage... */ #ifndef NGROUPS #define NGROUPS 32
include/linux/pagemap.h +6 -5
@@ -61,11 +61,12 @@*/ static inline unsigned long _page_hashfn (struct address_space * mapping,unsigned long index) { -#define i (((unsigned long) mapping)/(sizeof(struct inode) & ~ (sizeof(struct inode) - 1))) -#define s (x) ((x)+((x)>>PAGE_HASH_BITS)) -return s (i+index) & (PAGE_HASH_SIZE -1 ); -#undef i -#undef s +unsigned long hash; + hash = (unsigned long ) mapping + index; + hash *=SPARSE_GOLDEN_RATIO_PRIME ; + hash >>=BITS_PER_LONG -PAGE_HASH_BITS ; + hash &=PAGE_HASH_SIZE -1 ; +return hash; }#define page_hash (mapping,index) (page_hash_table+_page_hashfn(mapping,index))
include/linux/sched.h +13 -2
@@ -518,11 +518,22 @@extern struct mm_struct init_mm;extern struct task_struct *init_tasks[NR_CPUS ]; +/* +* A pid hash function using a prime near golden +* ratio to the machine word size (32 bits). The +* results of this are unknown. +* +* Added shift to extract high-order bits of computed +* hash function. +* -- wli +*/ +/* PID hashing. (shouldnt this be dynamic?) */ #define PIDHASH_SZ (4096 >> 2) +#define PIDHASH_BITS 10extern struct task_struct *pidhash[PIDHASH_SZ ]; - -#define pid_hashfn (x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1)) +#define pid_hashfn (x) \ + (((2654435761UL*(x)) >> (BITS_PER_LONG-PIDHASH_BITS)) & (PIDHASH_SZ-1))static inline void hash_pid (struct task_struct *p) {
kernel/user.c +8 -1
@@ -19,7 +19,14 @@#define UIDHASH_BITS 8#define UIDHASH_SZ (1 << UIDHASH_BITS)#define UIDHASH_MASK (UIDHASH_SZ - 1) -#define __uidhashfn (uid) (((uid >> UIDHASH_BITS) ^ uid) & UIDHASH_MASK) + +/* +* hash function borrowed from Chuck Lever's paper +* The effects of this replacement have not been measured. +* -- wli +*/ +#define __uidhashfn (uid) \ + (((2654435761UL*(uid)) >> (BITS_PER_LONG-UIDHASH_BITS)) & UIDHASH_MASK)#define uidhashentry (uid) (uidhash_table + __uidhashfn(uid))static kmem_cache_t *uid_cachep;
Quoted 1 line · Michael Cohen
This one was given to me by WLI himself;
Are you sure these are the latest bit-sparse primes ?
include/asm-alpha/param.h
Quoted 12 lines
+++
linux-patched/include/asm-alpha/param.hMon Feb 25 20:44:35 2002include/asm-alpha/param.h +9
-0+/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +++ linux-patched/include/asm-arm/param.h Mon Feb 25 20:43:13 2002 +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif
Yuck, the fact that you're defining the exact same constant in many .h files is ugly. Could you move this to one place ?
(maybe linux/hash.h like Rusty is doing for 2.5?)
include/linux/pagemap.h line 69
Quoted 6 lines
include/linux/pagemap.h +6
-0+unsigned long hash; + hash = (unsigned long ) mapping + index; + hash *=SPARSE_GOLDEN_RATIO_PRIME ; + hash >>=BITS_PER_LONG -PAGE_HASH_BITS ; + hash &=PAGE_HASH_SIZE -1 ; +return hash;
For 64-bit systems you'll want:
1) a 64-bit golden ratio prime
2) expanding the bit ops by hand because gcc doesn't do it for you
These last 2 points are easy, you can just copy the stuff from the struct page patch I sent earlier.
cheers,
Rik
Signature · 4 lines
"Linux holds advantages over the single-vendor commercial OS"
-- Microsoft's "Competing with Linux" document
http://www.surriel.com/ http://distro.conectiva.com/Quoted 5 lines · On Mon, 25 Feb 2002 23:04:58 -0300 (BRT) Rik van Riel <[email protected]>…
Quoted 1 line · Michael Cohen
This one was given to me by WLI himself;
Are you sure these are the latest bit-sparse primes ?
WLI has yet to update me, and I've yet to see anything new from him in this area. I could be mistaken.
Quoted 16 lines
include/asm-alpha/param.h
Quoted 12 lines
+++
linux-patched/include/asm-alpha/param.hMon Feb 25 20:44:35 2002include/asm-alpha/param.h +9
-0+/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */ + +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif +++ linux-patched/include/asm-arm/param.h Mon Feb 25 20:43:13 2002 +#ifndef SPARSE_GOLDEN_RATIO_PRIME +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL +#endif Yuck, the fact that you're defining the exact same constant in many .h files is ugly. Could you move this to one place ?
Quoted 1 line
(maybe
linux/hash.hlike Rusty is doing for 2.5?)
Possible. Take a look at HZ though. It's an arch-specific parameter similar to HZ (different for some arches, but not all) and it looks like it belongs in params.h for that reason.
Quoted 9 lines
include/linux/pagemap.h line 69
Quoted 6 lines
include/linux/pagemap.h +6
-0+unsigned long hash; + hash = (unsigned long ) mapping + index; + hash *=SPARSE_GOLDEN_RATIO_PRIME ; + hash >>=BITS_PER_LONG -PAGE_HASH_BITS ; + hash &=PAGE_HASH_SIZE -1 ; +return hash;For 64-bit systems you'll want:
Quoted 5 lines
1) a 64-bit golden ratio prime
2) expanding the bit ops by hand because gcc doesn't do it for you
These last 2 points are easy, you can just copy the stuff from the struct page patch I sent earlier.
Great, thanks :)
Quoted 8 lines
cheers,
Rik
Signature · 4 lines
"Linux holds advantages over the single-vendor commercial OS" -- Microsoft's "Competing with Linux" document http://www.surriel.com/ http://distro.conectiva.com/
Quoted 1 line · Michael Cohen
Quoted 1 line
Quoted 1 line
This one was given to me by WLI himself;
Quoted 1 line · On Mon, 25 Feb 2002 23:04:58 -0300 (BRT) Rik van Riel <[email protected]>…
Quoted 1 line
Are you sure these are the latest bit-sparse primes ?
Quoted 2 lines · Michael Cohen
WLI has yet to update me, and I've yet to see anything new from him in this area. I could be mistaken.
They aren't the latest, though I have seen these in particular do well for the inode cache.
Cheers,
Bill