Skip to contentSkip to conversation

Submssions for 2.4.19-pre [Fibonacci Hashing (William Lee Irwin)] [Discuss :) ]

PATCH Michael Cohen 3 participants 4 messages Feb 26, 2002

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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
diff -Nru linux-2.4.19-pre1/fs/inode.c linux-patched/fs/inode.c
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-alpha/param.h linux-patched/include/asm-alpha/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-arm/param.h linux-patched/include/asm-arm/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-cris/param.h linux-patched/include/asm-cris/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-i386/param.h linux-patched/include/asm-i386/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-ia64/param.h linux-patched/include/asm-ia64/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-m68k/param.h linux-patched/include/asm-m68k/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-mips/param.h linux-patched/include/asm-mips/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-mips64/param.h linux-patched/include/asm-mips64/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-parisc/param.h linux-patched/include/asm-parisc/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-ppc/param.h linux-patched/include/asm-ppc/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-s390/param.h linux-patched/include/asm-s390/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-s390x/param.h linux-patched/include/asm-s390x/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sh/param.h linux-patched/include/asm-sh/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sparc/param.h linux-patched/include/asm-sparc/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sparc64/param.h linux-patched/include/asm-sparc64/param.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/linux/pagemap.h linux-patched/include/linux/pagemap.h
@@ -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
diff -Nru linux-2.4.19-pre1/include/linux/sched.h linux-patched/include/linux/sched.h
@@ -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 10
 extern 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
diff -Nru linux-2.4.19-pre1/kernel/user.c linux-patched/kernel/user.c
@@ -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;
#1 lore raw
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.h Mon Feb 25 20:44:35 2002

include/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/
#2 lore raw
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.h Mon Feb 25 20:44:35 2002

include/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.h like 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/
#3 lore raw
In reply to Michael Cohen
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