Re: [RFC] non-resident page management

From: Pekka Enberg
Date: Sat Apr 23 2005 - 06:28:47 EST


Hi,

On 4/23/05, Rik van Riel <riel@xxxxxxxxxx> 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@xxxxxxxxxxxxxx>
---

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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/