non-resident page management

RFC Pekka Enberg 2 participants 4 messages Apr 23, 2005 Memory management

lore

Share & tools

lore

Pekka Enberg

author

2005-04-23 11:25 UTC #0 lore raw

Hi,

Quoted 1 line · Rik van Riel

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 <[email protected]>

---

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

include/linux/hash.h +12 -1

Index: 2.6/include/linux/hash.h
===================================================================
@@ -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);

mm/nonresident.c +8 -3

Index: 2.6/mm/nonresident.c
===================================================================
@@ -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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Rik van Riel

2005-04-23 11:31 UTC #1 lore raw

Quoted 5 lines · Pekka Enberg

Quoted 1 line · Rik van Riel
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].

I've thought about it, but ...

include/linux/hash.h line 24

Quoted 3 lines

include/linux/hash.h +0 -0

@@ -23,7 +23,7 @@
 #error Define GOLDEN_RATIO_PRIME for your wordsize.
 #endif

... include/linux/hash.c appears to only work right for 32 bit words, not 64 bit ones ...

Signature · 8 lines

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Rik van Riel

2005-04-23 17:13 UTC #2 lore raw

In reply to Pekka Enberg

Quoted 4 lines · Pekka Enberg

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 <[email protected]>

Looks good to me, here's a new version of the patch.

The next part of my cunning plan is to get rid of the object generation number, and use a cryptographic hash of (offset, mapping->host->i_ino, mapping->host->i_sb). That way there's only a small chance of false positives - assuming a perfect hash, one false positive every 256MB of data, or 2^16 pages.

Unless there are filesystems that immediately reassign the same inode number when creating a file after one got deleted - not sure about that...

Anyway, here is the current code:

Signed-off-by Rik van Riel <[email protected]>

 include/linux/hash.h        |   13 +++-
 include/linux/nonresident.h |   12 +++
 mm/Makefile                 |    3 
 mm/nonresident.c            |  137 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 163 insertions(+), 2 deletions(-)

include/linux/nonresident.h renamed from include/linux/nonresident.h.nonres +12 -0

@@ -0,0 +1,12 @@
+/*
+ * include/linux/nonresident.h
+ * (C) 2004,2005 Red Hat, Inc
+ * Written by Rik van Riel <[email protected]>
+ * 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, unsigned long);
+extern int remember_page(void *, unsigned long, unsigned long);
+void init_nonresident(unsigned long);

include/linux/hash.h renamed from include/linux/hash.h.nonres +12 -1

@@ -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 @@ static inline unsigned long hash_long(un
 	/* 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);

mm/nonresident.c renamed from mm/nonresident.c.nonres +137 -0

137 lines not on this page · raw message

mm/Makefile renamed from mm/Makefile.nonres +2 -1

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

Rik van Riel

2005-04-23 18:55 UTC #3 lore raw

Quoted 2 lines · Rik van Riel

The next part of my cunning plan is to get rid of the object generation number,

Here's the change, incremental to the previous patch. This should simplify things for the caller and work with both the swap cache and filesystem backed inodes - assuming filesystems are smart about recycling inode numbers, otherwise I may need to use another field too ...

Signed-off-by Rik van Riel <[email protected]>

include/linux/nonresident.h renamed from include/linux/nonresident.h.nr2 +2 -2

@@ -7,6 +7,6 @@
  * 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, unsigned long);
-extern int remember_page(void *, unsigned long, unsigned long);
+extern int recently_evicted(void *, unsigned long);
+extern int remember_page(void *, unsigned long);
 void init_nonresident(unsigned long);

mm/nonresident.c renamed from mm/nonresident.c.nr2 +22 ~~-18~~

@@ -26,14 +26,6 @@
 
 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;

@@ -51,19 +43,31 @@ struct nr_bucket
 /* The non-resident page hash table. */
 static struct nr_bucket * nr_hashtable;
 
-struct nr_bucket * nr_hash(void * mapping, unsigned long offset_and_gen)
+struct nr_bucket * nr_hash(void * mapping, unsigned long offset)
 {
 	unsigned long bucket;
 	unsigned long hash;
 
-	hash = 17;
-	hash = 37 * hash + hash_ptr_mul(mapping);
-	hash = 37 * hash + hash_long_mul(offset_and_gen);
+	hash = hash_ptr_mul(mapping);
+	hash = 37 * hash + hash_long_mul(offset);
 	bucket = hash % nr_buckets;
 
 	return nr_hashtable + bucket;
 }
 
+static unsigned long nr_cookie(struct address_space * mapping, unsigned long offset)
+{
+	unsigned long cookie = offset;
+
+	if (mapping->host) {
+		cookie = hash_mul_long(offset);
+		cookie = 37 * cookie + hash_ptr_mul(mapping->host->i_ino);
+		cookie = 37 * cookie + hash_ptr_mul(mapping->host->i_sb);
+	}
+
+	return cookie;
+}
+
 static int nr_same(struct nr_page * first, struct nr_page * second)
 {
 	/* Chances are this nr_page belongs to a different mapping ... */

@@ -77,10 +81,10 @@ static int nr_same(struct nr_page * firs
 	return 0;
 }
 
-int recently_evicted(void * mapping, unsigned long offset, unsigned long gen)
+int recently_evicted(struct address_space * mapping, unsigned long offset)
 {
-	unsigned long offset_and_gen = make_nr_oag(offset, gen);
-	struct nr_bucket * nr_bucket = nr_hash(mapping, offset_and_gen);
+	unsigned long offset_and_gen = nr_cookie(mapping, offset);
+	struct nr_bucket * nr_bucket = nr_hash(mapping, offset);
 	struct nr_page wanted;
 	int state = -1;
 	int i;

@@ -102,10 +106,10 @@ int recently_evicted(void * mapping, uns
 	return state;
 }
 
-int remember_page(void * mapping, unsigned long offset, unsigned long gen)
+int remember_page(struct address_space * mapping, unsigned long offset)
 {
-	unsigned long offset_and_gen = make_nr_oag(offset, gen);
-	struct nr_bucket * nr_bucket = nr_hash(mapping, offset_and_gen);
+	unsigned long offset_and_gen = nr_cookie(mapping, offset);
+	struct nr_bucket * nr_bucket = nr_hash(mapping, offset);
 	struct nr_page * victim;
 	int recycled = 0;
 	int i;