Re: [RFC] non-resident page management

[Pekka Enberg <penberg@cs.helsinki.fi>]

Hi,

On 4/23/05, Rik van Riel <riel@redhat.com> wrote:
> Note that this code could use an actual hash function.

How about this? It computes hash for the two longs and combines them by
addition and multiplication as suggested by [Bloch01].

Signed-off-by: Pekka Enberg <penberg@cs.helsinki.fi>
---

 include/linux/hash.h |   13 ++++++++++++-
 mm/nonresident.c     |   11 ++++++++---
 2 files changed, 20 insertions(+), 4 deletions(-)

Index: 2.6/include/linux/hash.h
===================================================================
--- 2.6.orig/include/linux/hash.h	2004-12-24 23:35:39.000000000 +0200
+++ 2.6/include/linux/hash.h	2005-04-23 13:57:46.000000000 +0300
@@ -23,7 +23,7 @@
 #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_long_mul(unsigned long val)
 {
 	unsigned long hash = val;
 
@@ -46,6 +46,17 @@
 	/* On some cpus multiply is faster, on others gcc will do shifts */
 	hash *= GOLDEN_RATIO_PRIME;
 #endif
+	return hash;
+}
+
+static inline unsigned long hash_ptr_mul(void *ptr)
+{
+	return hash_long_mul((unsigned long)ptr);
+}
+
+static inline unsigned long hash_long(unsigned long val, unsigned int bits)
+{
+	unsigned long hash = hash_long_mul(val);
 
 	/* High bits are more random, so use them. */
 	return hash >> (BITS_PER_LONG - bits);
Index: 2.6/mm/nonresident.c
===================================================================
--- 2.6.orig/mm/nonresident.c	2005-04-23 13:46:24.000000000 +0300
+++ 2.6/mm/nonresident.c	2005-04-23 14:18:20.000000000 +0300
@@ -21,7 +21,7 @@
 #include <linux/cache.h>
 #include <linux/spinlock.h>
 #include <linux/bootmem.h>
-#include <linux/jhash.h>
+#include <linux/hash.h>
 // #include <linux/nonresident.h>
 
 static unsigned long nr_buckets;
@@ -51,11 +51,16 @@
 /* The non-resident page hash table. */
 static struct nr_bucket * nr_hashtable;
 
-/* Wanted: a real hash function for 2 longs. */
 struct nr_bucket * nr_hash(void * mapping, unsigned long offset_and_gen)
 {
+	unsigned long hash;
 	unsigned long bucket;
-	bucket = ((unsigned long)mapping + offset_and_gen) % nr_buckets;
+
+	hash = 17;
+	hash = 37 * hash + hash_ptr_mul(mapping);
+	hash = 37 * hash + hash_long_mul(offset_and_gen);
+	bucket = hash % nr_buckets;
+
 	return nr_hashtable + bucket;
 }
 


-
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/