Skip to contentSkip to conversation

mm: NUMA replicated pagecache (rewrite) for 2.6.20

PATCH New Nick Piggin 1 participant 2 messages Feb 16, 2007

Subsystems (7)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 mm: NUMA replicated pagecache (rewrite) for 2.6.20

Page-based NUMA pagecache replication.

This is a scheme for page replication replicates read-only pagecache pages opportunistically, at pagecache lookup time (at points where we know the page is being looked up for read only).

The page will be replicated if it resides on a different node to what the requesting CPU is on. Also, the original page must meet some conditions:
it must be clean, uptodate, not under writeback, and not have an elevated refcount or filesystem private data. However it is allowed to be mapped into pagetables.

Replication is done at the pagecache level, where a replicated pagecache (inode,offset) key will have its radix-tree entry specially tagged, and its radix-tree page will be replaced with a descriptor. Most importantly, this descriptor has another radix-tree which is keyed by node.

Writes into pagetables are caught by having a filemap_mkwrite function, which collapses the replication before proceeding. After collapsing the replication, all process page tables are unmapped, so that any processes mapping discarded pages will refault in the correct one.

/proc/vmstat has nr_repl_pages, which is the number of _additional_ pages replicated, beyond the first.

Status:
Completely reworked and optimised. This is actually a reasonable design and implementation.

- Data structures and conceptual state machine remain basically identical, however implementation is changed so much that I don't think it will be worth posting the incremental diff.

- Fastpath (ie. look up a page, without replicating or collapsing it) performance is basically unchanged now.
- Slowpath (replicating, unreplicating) still has some small locking inefficiencies (eg. we could use a rwlock downgrade). However I don't want to get fancy there, because with the lockless pagecache it should naturally become ideal.
- This is achieved by using a bit in the radix-tree entry pointer to tell us whether a given offset is a page or a pcache_desc. One good point about this is that it can give us completely lockless lookups for both replicated and unreplicated case with lockless pagecache.
- Also, gang lookup functions no longer perform a wild sweep looking for replicated pages to collapse, but precisely collapse those that are needed.
- Proper error handling implemented. We never get into a situation where setting up a replication could result in a failure where we're unable to restore the unreplicated state.
- Use __GFP_THISNODE | __GFP_NORETRY to allocate slave pages (thanks Lee)
- Made CONFIG_urable.
- Moved into its own file, with 6 hooks used by the core mm. Still not quite as nice as I would like (eg. get_unreplicated_page & variants), but it's getting closer. It might be cleaner to simply completely reimplement those few changed lookup functions if CONFIG_REPLICATION.
- Locking is generally much nicer, but again not perfect.
- Some commenting.
- Fixes several races (thanks Lee).
- No longer uses ->page_mkwrite, but hooks into mm/memory.c. This means all filesystems should now work.
- Unconditionally wrprotects ptes when cleaning a file page, and the page fault unreplicating hook locks then dirties the page, which should actually be a real attempt at getting the locking right this time. I still need to think more about this.

Todo:
- A PG_replicated bit will optimise reclaim and remove the last requirement for PAGECACHE_TAG_REPLICATED and radix_tree_tag_get! I didn't think this could be done so optimally without any changes to the radix tree! Sweet. This is implemented and will be included in the next version (I want to give it further testing).
- Again, no NUMA testing. However my per-CPU test patch is much closer to the NUMA code this time, so it's more likely to work.
- Would like to be able to control replication via userspace, and maybe even internally to the kernel.
- Ideally, reclaim might reclaim replicated pages preferentially, however I aim to be _minimally_ intrusive, and this conflicts with that.
- Would like to replicate PagePrivate, but filesystem may dirty page via buffers. Could replicate regular file pagecache, I think.
- Would be nice to promote a slave to master when reclaiming the master. This This should be quite easy: must transfer relevant flags, and only promote if !PagePrivate (which reclaim itself takes care of).
- More correctness testing.
- Eventually, have to look at playing nicely with migration.

 include/linux/fs.h         |    1 
 include/linux/mm.h         |    6 
 include/linux/mm_types.h   |    8 
 include/linux/mmzone.h     |    1 
 include/linux/radix-tree.h |    4 
 init/main.c                |    1 
 lib/radix-tree.c           |    2 
 mm/Kconfig                 |   11 +
 mm/Makefile                |    1 
 mm/filemap.c               |  132 ++++++-------
 mm/internal.h              |   59 ++++++
 mm/replication.c           |  435 +++++++++++++++++++++++++++++++++++++++++++++
 mm/vmscan.c                |    8 
 mm/vmstat.c                |    1 
 14 files changed, 594 insertions(+), 76 deletions(-)
include/linux/mm_types.h +8 -0
Index: linux-2.6/include/linux/mm_types.h
===================================================================
@@ -5,6 +5,8 @@
 #include <linux/threads.h>
 #include <linux/list.h>
 #include <linux/spinlock.h>
+#include <linux/radix-tree.h>
+#include <linux/nodemask.h>
 
 struct address_space;
 
@@ -64,4 +66,10 @@ struct page {
 #endif /* WANT_PAGE_VIRTUAL */
 };
 
+struct pcache_desc {
+	struct page *master;
+	nodemask_t nodes_present;
+	struct radix_tree_root page_tree;
+};
+
 #endif /* _LINUX_MM_TYPES_H */
include/linux/fs.h +1 -0
Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -490,6 +490,7 @@ struct block_device {
  */
 #define PAGECACHE_TAG_DIRTY	0
 #define PAGECACHE_TAG_WRITEBACK	1
+#define PAGECACHE_TAG_REPLICATED 2
 
 int mapping_tagged(struct address_space *mapping, int tag);
 
include/linux/radix-tree.h +4 -0
Index: linux-2.6/include/linux/radix-tree.h
===================================================================
@@ -52,7 +52,11 @@ static inline int radix_tree_is_direct_p
 
 /*** radix-tree API starts here ***/
 
+#ifdef CONFIG_REPLICATION
+#define RADIX_TREE_MAX_TAGS 3
+#else
 #define RADIX_TREE_MAX_TAGS 2
+#endif
 
 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
 struct radix_tree_root {
mm/filemap.c +32 -73

216 lines not on this page · raw message

mm/internal.h +66 -0

76 lines not on this page · raw message

mm/vmscan.c +7 -1
Index: linux-2.6/mm/vmscan.c
===================================================================
@@ -390,6 +390,7 @@ int remove_mapping(struct address_space 
 	BUG_ON(!PageLocked(page));
 	BUG_ON(mapping != page_mapping(page));
 
+again:
 	write_lock_irq(&mapping->tree_lock);
 	/*
 	 * The non racy check for a busy page.
@@ -431,7 +432,12 @@ int remove_mapping(struct address_space 
 		return 1;
 	}
 
-	__remove_from_page_cache(page);
+	/* XXX: could optimise with a page bit */
+	if (pcache_replicated(mapping, page->index)) {
+		if (reclaim_replicated_page(mapping, page))
+			goto again;
+	} else
+		__remove_from_page_cache(page);
 	write_unlock_irq(&mapping->tree_lock);
 	__put_page(page);
 	return 1;
include/linux/mm.h +6 -0
Index: linux-2.6/include/linux/mm.h
===================================================================
@@ -1005,6 +1005,12 @@ extern void show_mem(void);
 extern void si_meminfo(struct sysinfo * val);
 extern void si_meminfo_node(struct sysinfo *val, int nid);
 
+#ifdef CONFIG_REPLICATION
+extern void replication_init(void);
+#else
+static inline void replication_init(void) {}
+#endif
+
 #ifdef CONFIG_NUMA
 extern void setup_per_cpu_pageset(void);
 #else
init/main.c +1 -0
Index: linux-2.6/init/main.c
===================================================================
@@ -583,6 +583,7 @@ asmlinkage void __init start_kernel(void
 	kmem_cache_init();
 	setup_per_cpu_pageset();
 	numa_policy_init();
+	replication_init();
 	if (late_time_init)
 		late_time_init();
 	calibrate_delay();
include/linux/mmzone.h +3 -0
Index: linux-2.6/include/linux/mmzone.h
===================================================================
@@ -51,6 +51,9 @@ enum zone_stat_item {
 	NR_FILE_MAPPED,	/* pagecache pages mapped into pagetables.
 			   only modified from process context */
 	NR_FILE_PAGES,
+#ifdef CONFIG_REPLICATION
+	NR_REPL_PAGES,
+#endif
 	NR_SLAB_RECLAIMABLE,
 	NR_SLAB_UNRECLAIMABLE,
 	NR_PAGETABLE,	/* used for pagetables */
mm/vmstat.c +3 -0
Index: linux-2.6/mm/vmstat.c
===================================================================
@@ -457,6 +457,9 @@ static const char * const vmstat_text[] 
 	"nr_anon_pages",
 	"nr_mapped",
 	"nr_file_pages",
+#ifdef CONFIG_REPL
+	"nr_repl_pages",
+#endif
 	"nr_slab_reclaimable",
 	"nr_slab_unreclaimable",
 	"nr_page_table_pages",
lib/radix-tree.c +0 -2
Index: linux-2.6/lib/radix-tree.c
===================================================================
@@ -534,7 +534,6 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_tag_clear);
 
-#ifndef __KERNEL__	/* Only the test harness uses this at present */
 /**
  * radix_tree_tag_get - get a tag on a radix tree node
  * @root:		radix tree root
@@ -596,7 +595,6 @@ int radix_tree_tag_get(struct radix_tree
 	}
 }
 EXPORT_SYMBOL(radix_tree_tag_get);
-#endif
 
 static unsigned int
 __lookup(struct radix_tree_node *slot, void **results, unsigned long index,
mm/Kconfig +11 -0
Index: linux-2.6/mm/Kconfig
===================================================================
@@ -152,6 +152,17 @@ config MIGRATION
 	  example on NUMA systems to put pages nearer to the processors accessing
 	  the page.
 
+#
+# support for NUMA pagecache replication
+#
+config REPLICATION
+	bool "Pagecache replication"
+	def_bool n
+	depends on NUMA
+	help
+	  Enables NUMA pagecache page replication
+
+
 config RESOURCES_64BIT
 	bool "64 bit Memory and IO resources (EXPERIMENTAL)" if (!64BIT && EXPERIMENTAL)
 	default 64BIT
mm/Makefile +1 -0
Index: linux-2.6/mm/Makefile
===================================================================
@@ -29,3 +29,4 @@ obj-$(CONFIG_MEMORY_HOTPLUG) += memory_h
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o
 obj-$(CONFIG_SMP) += allocpercpu.o
+obj-$(CONFIG_REPLICATION) += replication.o
mm/replication.c new file +472 -0

472 lines not on this page · raw message

mm/memory.c +5 -2
Index: linux-2.6/mm/memory.c
===================================================================
@@ -60,6 +60,8 @@
 #include <linux/swapops.h>
 #include <linux/elf.h>
 
+#include "internal.h"
+
 #ifndef CONFIG_NEED_MULTIPLE_NODES
 /* use the per-pgdat data instead for discontigmem - mbligh */
 unsigned long max_mapnr;
@@ -1528,11 +1530,10 @@ static int do_wp_page(struct mm_struct *
 			page_cache_get(old_page);
 			pte_unmap_unlock(page_table, ptl);
 
+			old_page = get_unreplicated_page_fault(old_page);
 			if (vma->vm_ops->page_mkwrite(vma, old_page) < 0)
 				goto unwritable_page;
 
-			page_cache_release(old_page);
-
 			/*
 			 * Since we dropped the lock we need to revalidate
 			 * the PTE as someone else may have changed it.  If
@@ -1541,9 +1542,11 @@ static int do_wp_page(struct mm_struct *
 			 */
 			page_table = pte_offset_map_lock(mm, pmd, address,
 							 &ptl);
+			page_cache_release(old_page);
 			if (!pte_same(*page_table, orig_pte))
 				goto unlock;
 		}
+
 		dirty_page = old_page;
 		get_page(dirty_page);
 		reuse = 1;
mm/page-writeback.c +5 -0
Index: linux-2.6/mm/page-writeback.c
===================================================================
@@ -857,7 +857,12 @@ int clear_page_dirty_for_io(struct page 
 {
 	struct address_space *mapping = page_mapping(page);
 
+	BUG_ON(!PageLocked(page));
+#ifndef CONFIG_REPLICATION
 	if (mapping && mapping_cap_account_dirty(mapping)) {
+#else
+	if (mapping) {
+#endif
 		/*
 		 * Yes, Virginia, this is indeed insane.
 		 *

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

#1 lore raw

PATCH 1/1 mm: per-CPU replicated pagecache (for testing)

Trial the replicated pagecache on non-NUMA machines by doing per-CPU replication. Actually there is a slight change in one algorithm because there is no such thing as page_to_cpuid.

To minimise the code change, this just pretends smp_processor_id returns a node id. Technically this will blow up if you have more CPUs than MAX_NUMNODES.

 mm/replication.c |   29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)
mm/replication.c +15 -14
Index: linux-2.6/mm/replication.c
===================================================================
@@ -98,9 +98,6 @@ static int should_replicate_pcache(struc
 	if (unlikely(PageSwapCache(page)))
 		return 0;
 
-	if (nid == page_to_nid(page))
-		return 0;
-
 	if (page_count(page) != 2 + page_mapcount(page))
 		return 0;
 	smp_rmb();
@@ -133,7 +130,7 @@ static int try_to_replicate_pcache(struc
 	if (!pcd)
 		goto out;
 
-	page_node = page_to_nid(page);
+	page_node = smp_processor_id();
 	pcd->master = page;
 	node_set(page_node, pcd->nodes_present);
 	if (radix_tree_insert(&pcd->page_tree, page_node, page))
@@ -143,7 +140,7 @@ static int try_to_replicate_pcache(struc
 
 	/* The non-racy check */
 	if (unlikely(!should_replicate_pcache(page, mapping, offset,
-							numa_node_id())))
+							smp_processor_id())))
 		goto out_lock;
 
 	pslot = radix_tree_lookup_slot(&mapping->page_tree, offset);
@@ -269,13 +266,18 @@ failed:
 static void __remove_replicated_page(struct pcache_desc *pcd, struct page *page,
 			struct address_space *mapping, unsigned long offset)
 {
-	int nid = page_to_nid(page);
+	int nid;
 	BUG_ON(page == pcd->master);
-	/* XXX: page->mapping = NULL; ? */
-	BUG_ON(!node_isset(nid, pcd->nodes_present));
-	BUG_ON(radix_tree_delete(&pcd->page_tree, nid) != page);
-	node_clear(nid, pcd->nodes_present);
-	__dec_zone_page_state(page, NR_REPL_PAGES);
+	for_each_node_mask(nid, pcd->nodes_present) {
+		/* XXX: page->mapping = NULL; ? */
+		if (radix_tree_lookup(&pcd->page_tree, nid) != page)
+			continue;
+		BUG_ON(radix_tree_delete(&pcd->page_tree, nid) != page);
+		node_clear(nid, pcd->nodes_present);
+		__dec_zone_page_state(page, NR_REPL_PAGES);
+		return;
+	}
+	BUG();
 }
 
 /*
@@ -309,8 +311,7 @@ static struct page *try_to_create_replic
 {
 	struct page *repl_page;
 
-	repl_page = alloc_pages_node(nid, mapping_gfp_mask(mapping) |
-					  __GFP_THISNODE | __GFP_NORETRY, 0);
+	repl_page = page_cache_alloc(mapping);
 	if (!repl_page)
 		return page; /* failed alloc, just return the master */
 
@@ -343,7 +344,7 @@ struct page * find_get_page_readonly(str
 
 retry:
 	read_lock_irq(&mapping->tree_lock);
-	nid = numa_node_id();
+	nid = smp_processor_id();
 	page = radix_tree_lookup(&mapping->page_tree, offset);
 	if (is_pcache_desc(page)) {
 		struct pcache_desc *pcd;

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