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
diff -Nru linux-2.4.19-pre1/fs/inode.c linux-patched/fs/inode.c
--- linux-2.4.19-pre1/fs/inode.c Fri Dec 21 12:41:55 2001
+++ linux-patched/fs/inode.c Mon Feb 25 20:28:27 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-alpha/param.h linux-patched/include/asm-alpha/param.h
--- linux-2.4.19-pre1/include/asm-alpha/param.h Wed Nov 8 02:37:31 2000
+++ linux-patched/include/asm-alpha/param.h Mon Feb 25 20:44:35 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-arm/param.h linux-patched/include/asm-arm/param.h
--- linux-2.4.19-pre1/include/asm-arm/param.h Thu Oct 11 12:04:57 2001
+++ linux-patched/include/asm-arm/param.h Mon Feb 25 20:43:13 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-cris/param.h linux-patched/include/asm-cris/param.h
--- linux-2.4.19-pre1/include/asm-cris/param.h Thu Feb 8 19:32:44 2001
+++ linux-patched/include/asm-cris/param.h Mon Feb 25 20:43:27 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-i386/param.h linux-patched/include/asm-i386/param.h
--- linux-2.4.19-pre1/include/asm-i386/param.h Fri Oct 27 14:04:43 2000
+++ linux-patched/include/asm-i386/param.h Mon Feb 25 20:28:27 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-ia64/param.h linux-patched/include/asm-ia64/param.h
--- linux-2.4.19-pre1/include/asm-ia64/param.h Thu Apr 5 15:51:47 2001
+++ linux-patched/include/asm-ia64/param.h Mon Feb 25 20:45:09 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-m68k/param.h linux-patched/include/asm-m68k/param.h
--- linux-2.4.19-pre1/include/asm-m68k/param.h Thu Jan 4 16:00:55 2001
+++ linux-patched/include/asm-m68k/param.h Mon Feb 25 20:43:45 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-mips/param.h linux-patched/include/asm-mips/param.h
--- linux-2.4.19-pre1/include/asm-mips/param.h Mon Jul 2 16:56:40 2001
+++ linux-patched/include/asm-mips/param.h Mon Feb 25 20:45:35 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-mips64/param.h linux-patched/include/asm-mips64/param.h
--- linux-2.4.19-pre1/include/asm-mips64/param.h Wed Nov 29 00:42:04 2000
+++ linux-patched/include/asm-mips64/param.h Mon Feb 25 20:46:10 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-parisc/param.h linux-patched/include/asm-parisc/param.h
--- linux-2.4.19-pre1/include/asm-parisc/param.h Tue Dec 5 15:29:39 2000
+++ linux-patched/include/asm-parisc/param.h Mon Feb 25 20:49:01 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-ppc/param.h linux-patched/include/asm-ppc/param.h
--- linux-2.4.19-pre1/include/asm-ppc/param.h Tue Aug 28 09:58:33 2001
+++ linux-patched/include/asm-ppc/param.h Mon Feb 25 20:42:59 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-s390/param.h linux-patched/include/asm-s390/param.h
--- linux-2.4.19-pre1/include/asm-s390/param.h Tue Feb 13 17:13:44 2001
+++ linux-patched/include/asm-s390/param.h Mon Feb 25 20:47:06 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-s390x/param.h linux-patched/include/asm-s390x/param.h
--- linux-2.4.19-pre1/include/asm-s390x/param.h Thu Oct 11 12:43:38 2001
+++ linux-patched/include/asm-s390x/param.h Mon Feb 25 20:47:18 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sh/param.h linux-patched/include/asm-sh/param.h
--- linux-2.4.19-pre1/include/asm-sh/param.h Thu Jan 4 16:19:13 2001
+++ linux-patched/include/asm-sh/param.h Mon Feb 25 20:47:41 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sparc/param.h linux-patched/include/asm-sparc/param.h
--- linux-2.4.19-pre1/include/asm-sparc/param.h Mon Oct 30 17:34:12 2000
+++ linux-patched/include/asm-sparc/param.h Mon Feb 25 20:48:26 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/asm-sparc64/param.h linux-patched/include/asm-sparc64/param.h
--- linux-2.4.19-pre1/include/asm-sparc64/param.h Mon Oct 30 17:34:12 2000
+++ linux-patched/include/asm-sparc64/param.h Mon Feb 25 20:48:47 2002
@@ -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
diff -Nru linux-2.4.19-pre1/include/linux/pagemap.h linux-patched/include/linux/pagemap.h
--- linux-2.4.19-pre1/include/linux/pagemap.h Mon Feb 25 14:38:13 2002
+++ linux-patched/include/linux/pagemap.h Mon Feb 25 20:28:27 2002
@@ -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))
diff -Nru linux-2.4.19-pre1/include/linux/sched.h linux-patched/include/linux/sched.h
--- linux-2.4.19-pre1/include/linux/sched.h Fri Dec 21 12:42:03 2001
+++ linux-patched/include/linux/sched.h Mon Feb 25 20:30:42 2002
@@ -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)
{
diff -Nru linux-2.4.19-pre1/kernel/user.c linux-patched/kernel/user.c
--- linux-2.4.19-pre1/kernel/user.c Wed Nov 29 01:43:39 2000
+++ linux-patched/kernel/user.c Mon Feb 25 20:28:27 2002
@@ -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;
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/