linux-mm.kvack.org archive mirror
 help / color / mirror / Atom feed
* Re: [RFC] non-resident page management
@ 2005-04-23 11:25 Pekka Enberg
  2005-04-23 11:31 ` Rik van Riel
  2005-04-23 17:13 ` Rik van Riel
  0 siblings, 2 replies; 5+ messages in thread
From: Pekka Enberg @ 2005-04-23 11:25 UTC (permalink / raw)
  To: riel; +Cc: linux-mm, linux-kernel

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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

^ permalink raw reply	[flat|nested] 5+ messages in thread
* [RFC] non-resident page management
@ 2005-04-22 21:26 Rik van Riel
  0 siblings, 0 replies; 5+ messages in thread
From: Rik van Riel @ 2005-04-22 21:26 UTC (permalink / raw)
  To: linux-mm; +Cc: linux-kernel

Basic infrastructure to track non-resident pages. This code is
needed to support advanced page replacement algorithms like
CLOCK-Pro or CART.

Note that this code could use an actual hash function.

Links to the actual replacement algorithms can be found on:

http://wiki.linux-mm.org/wiki/AdvancedPageReplacement

Signed-off-by: Rik van Riel <riel@redhat.com>

--- linux-2.6.11/include/linux/nonresident.h.nonres	2005-04-22 17:19:20.000000000 -0400
+++ linux-2.6.11/include/linux/nonresident.h	2005-04-22 17:20:31.000000000 -0400
@@ -0,0 +1,11 @@
+/*
+ * include/linux/nonresident.h
+ * (C) 2004,2005 Red Hat, Inc
+ * Written by Rik van Riel <riel@redhat.com>
+ * Released under the GPL, see the file COPYING for details.
+ *
+ * Keeps track of whether a non-resident page was recently evicted
+ * and should be immediately promoted to the active list.
+ */
+extern int recently_evicted(void *, unsigned long, short);
+extern int remember_page(void *, unsigned long, short);
--- linux-2.6.11/mm/nonresident.c.nonres	2005-04-22 17:19:13.000000000 -0400
+++ linux-2.6.11/mm/nonresident.c	2005-04-22 17:21:12.000000000 -0400
@@ -0,0 +1,130 @@
+/*
+ * mm/nonresident.c
+ * (C) 2004,2005 Red Hat, Inc
+ * Written by Rik van Riel <riel@redhat.com>
+ * Released under the GPL, see the file COPYING for details.
+ *
+ * Keeps track of whether a non-resident page was recently evicted
+ * and should be immediately promoted to the active list. This also
+ * helps automatically tune the inactive target.
+ *
+ * The pageout code stores a recently evicted page in this cache
+ * by calling remember_page(mapping/mm, offset/vaddr, generation)
+ * and can look it up in the cache by calling recently_evicted()
+ * with the same arguments.
+ *
+ * Note that there is no way to invalidate pages after eg. truncate
+ * or exit, we let the pages fall out of the non-resident set through
+ * normal replacement.
+ */
+#include <linux/mm.h>
+#include <linux/cache.h>
+#include <linux/spinlock.h>
+#include <linux/bootmem.h>
+#include <linux/jhash.h>
+// #include <linux/nonresident.h>
+
+static unsigned long nr_buckets;
+
+/*
+ * We fold the object generation number into the offset field, since
+ * that one has the most "free" bits on a 32 bit system.
+ */
+#define NR_GEN_SHIFT		(BITS_PER_LONG * 7 / 8)
+#define NR_OFFSET_MASK		((1 << NR_GEN_SHIFT) - 1)
+#define make_nr_oag(x,y)	(((x) & NR_OFFSET_MASK) + ((y) << NR_GEN_SHIFT))
+
+struct nr_page {
+	void * mapping;
+	unsigned long offset_and_gen;
+};
+
+/* Number of non-resident pages per hash bucket */
+#define NUM_NR ((L1_CACHE_BYTES - sizeof(spinlock_t))/sizeof(struct nr_page))
+
+struct nr_bucket
+{
+	spinlock_t lock;
+	struct nr_page pages[NUM_NR];
+} ____cacheline_aligned;
+
+/* 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 bucket;
+	bucket = ((unsigned long)mapping + offset_and_gen) % nr_buckets;
+	return nr_hashtable + bucket;
+}
+
+static int nr_same(struct nr_page * first, struct nr_page * second)
+{
+	/* Chances are this nr_page belongs to a different mapping ... */
+	if (first->mapping != second->mapping)
+		return 0;
+
+	/* ... but if it matches the mapping, it's probably the same page. */
+	if (likely(first->offset_and_gen == second->offset_and_gen))
+		return 1;
+
+	return 0;
+}
+
+int recently_evicted(void * mapping, unsigned long offset, short gen)
+{
+	unsigned long offset_and_gen = make_nr_oag(offset, gen);
+	struct nr_bucket * nr_bucket = nr_hash(mapping, offset_and_gen);
+	struct nr_page wanted;
+	int state = -1;
+	int i;
+
+	wanted.offset_and_gen = offset_and_gen;
+	wanted.mapping = mapping;
+
+	spin_lock(&nr_bucket->lock);
+	for (i = 0; i < NUM_NR; i++) {
+		struct nr_page * found = &nr_bucket->pages[i];
+		if (nr_same(found, &wanted)) {
+			found->mapping = 0;
+			state = 1;
+		}
+	}
+	spin_unlock(&nr_bucket->lock);
+
+	return state;
+}
+
+int remember_page(void * mapping, unsigned long offset, short gen)
+{
+	unsigned long offset_and_gen = make_nr_oag(offset, gen);
+	struct nr_bucket * nr_bucket = nr_hash(mapping, offset_and_gen);
+	struct nr_page * victim;
+	int recycled = 0;
+	int i;
+
+	spin_lock(&nr_bucket->lock);
+	for (i = 0; i < NUM_NR; i++) {
+		victim = &nr_bucket->pages[i];
+		if (victim->mapping == 0)
+			goto assign;
+	}
+
+	/* Randomly recycle an nr_page. */
+	i = (offset ^ jiffies) % NUM_NR;
+	victim = &nr_bucket->pages[i];
+	recycled = 1;
+
+assign:
+	victim->mapping = mapping;
+	victim->offset_and_gen = offset_and_gen;
+	spin_unlock(&nr_bucket->lock);
+	return recycled;
+}
+
+void __init init_nonresident(unsigned long mempages)
+{
+	nr_buckets = mempages / NUM_NR;
+	nr_hashtable = alloc_bootmem(nr_buckets * sizeof(struct nr_bucket));
+}
--- linux-2.6.11/mm/Makefile.nonres	2005-04-22 17:19:49.000000000 -0400
+++ linux-2.6.11/mm/Makefile	2005-04-22 11:25:36.000000000 -0400
@@ -12,7 +12,8 @@ obj-y			:= bootmem.o filemap.o mempool.o
 			   readahead.o slab.o swap.o truncate.o vmscan.o \
 			   prio_tree.o $(mmu-y)
 
-obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o
+obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o \
+			   nonresident.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
 obj-$(CONFIG_SHMEM) += shmem.o
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2005-04-23 18:55 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-04-23 11:25 [RFC] non-resident page management Pekka Enberg
2005-04-23 11:31 ` Rik van Riel
2005-04-23 17:13 ` Rik van Riel
2005-04-23 18:55   ` Rik van Riel
  -- strict thread matches above, loose matches on Subject: below --
2005-04-22 21:26 Rik van Riel

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox