Skip to contentSkip to conversation

vm - swap_prefetch-11

PATCH In review Con Kolivas 2 participants 3 messages Sep 23, 2005 – Sep 27, 2005

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

PATCH 1/1 vm - swap_prefetch-11

More optimisations, much much less locking costs, limits on when to prefetch and bugfixes.

Thanks to all testers!

Incrementals are available
http://ck.kolivas.org/patches/swap-prefetch/

Cheers,
Con

This patch implements swap prefetching when the vm is relatively idle and there is free ram available. The code is based on some early work by Thomas Schlichter.

This stores a list of swapped entries in a list ordered most recently used and a radix tree. It generates a low priority kernel thread running at nice 19 to do the prefetching at a later stage.

Once pages have been added to the swapped list, a timer is started, testing for conditions suitable to prefetch swap pages every 5 seconds. Suitable conditions are defined as lack of swapping out or in any pages, and no watermark tests failing. Significant amounts of dirtied ram also prevent prefetching. It then checks that we have spare ram looking for at least 3* pages_high free per zone and if it succeeds that will prefetch pages from swap. The pages are prefetched in 128kb groups every 1 second until the vm is busy for the tests above, the watermarks fail to detect adequate free ram or the list is emptied. The pages are copied to swap cache and kept on backing store. This allows pressure on either physical ram or swap to readily find free pages without further I/O.

In testing on modern pc hardware this results in wall-clock time activation of the firefox browser to speed up 5 fold after a worst case complete swap-out of the browser on an static web page.

 include/linux/fs.h   |    2
 include/linux/swap.h |   32 +++
 init/Kconfig         |   21 ++
 mm/Makefile          |    1
 mm/page_alloc.c      |   14 +
 mm/swap.c            |    3
 mm/swap_prefetch.c   |  411 +++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/swap_state.c      |   12 +
 mm/vmscan.c          |    5
 9 files changed, 496 insertions(+), 5 deletions(-)
include/linux/fs.h +2 -0
Index: linux-2.6.13-sp/include/linux/fs.h
===================================================================
@@ -340,6 +340,8 @@ struct address_space {
 	struct inode		*host;		/* owner: inode, block_device */
 	struct radix_tree_root	page_tree;	/* radix tree of all pages */
 	rwlock_t		tree_lock;	/* and rwlock protecting it */
+	struct radix_tree_root	swap_tree;	/* radix tree of swapped pages */
+	struct list_head	swapped_pages;	/* list of swapped pages */
 	unsigned int		i_mmap_writable;/* count VM_SHARED mappings */
 	struct prio_tree_root	i_mmap;		/* tree of private and shared mappings */
 	struct list_head	i_mmap_nonlinear;/*list VM_NONLINEAR mappings */
include/linux/swap.h +32 -0
Index: linux-2.6.13-sp/include/linux/swap.h
===================================================================
@@ -185,6 +185,37 @@ extern int shmem_unuse(swp_entry_t entry
 
 extern void swap_unplug_io_fn(struct backing_dev_info *, struct page *);
 
+#ifdef CONFIG_SWAP_PREFETCH
+/* only used by prefetch externally */
+/*	mm/swap_prefetch.c */
+extern void prepare_prefetch(void);
+extern void add_to_swapped_list(unsigned long index);
+extern void remove_from_swapped_list(unsigned long index);
+extern void delay_prefetch(void);
+/* linux/mm/page_alloc.c */
+extern struct page *
+buffered_rmqueue(struct zone *zone, int order, unsigned int __nocast gfp_flags);
+extern void zone_statistics(struct zonelist *zonelist, struct zone *z);
+
+#else	/* CONFIG_SWAP_PREFETCH */
+static inline void add_to_swapped_list(unsigned long index)
+{
+}
+
+static inline void prepare_prefetch(void)
+{
+}
+
+static inline void remove_from_swapped_list(unsigned long index)
+{
+}
+
+static inline void delay_prefetch(void)
+{
+}
+
+#endif	/* CONFIG_SWAP_PREFETCH */
+
 #ifdef CONFIG_SWAP
 /* linux/mm/page_io.c */
 extern int swap_readpage(struct file *, struct page *);
@@ -206,6 +237,7 @@ extern void free_pages_and_swap_cache(st
 extern struct page * lookup_swap_cache(swp_entry_t);
 extern struct page * read_swap_cache_async(swp_entry_t, struct vm_area_struct *vma,
 					   unsigned long addr);
+extern int add_to_swap_cache(struct page *page, swp_entry_t entry);
 /* linux/mm/swapfile.c */
 extern long total_swap_pages;
 extern unsigned int nr_swapfiles;
init/Kconfig +21 -0
Index: linux-2.6.13-sp/init/Kconfig
===================================================================
@@ -87,6 +87,27 @@ config SWAP
 	  used to provide more virtual memory than the actual RAM present
 	  in your computer.  If unsure say Y.
 
+config SWAP_PREFETCH
+	bool "Support for prefetching swapped memory"
+	depends on SWAP && EXPERIMENTAL
+	default n
+	---help---
+	  This option will allow the kernel to prefetch swapped memory pages
+	  when idle. The pages will be kept on both swap and in swap_cache
+	  thus avoiding the need for further I/O if either ram or swap space
+	  is required.
+	  
+	  What this will do on workstations is slowly bring back applications
+	  that have swapped out after memory intensive workloads back into
+	  physical ram if you have free ram at a later stage and the machine
+	  is relatively idle. This means that when you come back to your
+	  computer after leaving it idle for a while, applications will come
+	  to life faster. Note that your swap usage will appear to increase
+	  but these are cached pages, can be dropped freely by the vm, and it
+	  should stabilise around 50% swap usage.
+	  
+	  Desktop users will most likely want to say Y.
+
 config SYSVIPC
 	bool "System V IPC"
 	depends on MMU
mm/Makefile +1 -0
Index: linux-2.6.13-sp/mm/Makefile
===================================================================
@@ -13,6 +13,7 @@ obj-y			:= bootmem.o filemap.o mempool.o
 			   prio_tree.o $(mmu-y)
 
 obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o
+obj-$(CONFIG_SWAP_PREFETCH) += swap_prefetch.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
 obj-$(CONFIG_SPARSEMEM)	+= sparse.o
mm/page_alloc.c +10 -4
Index: linux-2.6.13-sp/mm/page_alloc.c
===================================================================
@@ -607,7 +607,7 @@ void drain_local_pages(void)
 }
 #endif /* CONFIG_PM */
 
-static void zone_statistics(struct zonelist *zonelist, struct zone *z)
+void zone_statistics(struct zonelist *zonelist, struct zone *z)
 {
 #ifdef CONFIG_NUMA
 	unsigned long flags;
@@ -684,7 +684,7 @@ static inline void prep_zero_page(struct
  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
  * or two.
  */
-static struct page *
+struct page *
 buffered_rmqueue(struct zone *zone, int order, unsigned int __nocast gfp_flags)
 {
 	unsigned long flags;
@@ -745,7 +745,7 @@ int zone_watermark_ok(struct zone *z, in
 		min -= min / 4;
 
 	if (free_pages <= min + z->lowmem_reserve[classzone_idx])
-		return 0;
+		goto out_failed;
 	for (o = 0; o < order; o++) {
 		/* At the next order, this order's pages become unavailable */
 		free_pages -= z->free_area[o].nr_free << o;
@@ -754,9 +754,15 @@ int zone_watermark_ok(struct zone *z, in
 		min >>= 1;
 
 		if (free_pages <= min)
-			return 0;
+			goto out_failed;
 	}
+
 	return 1;
+out_failed:
+	/* Swap prefetching is delayed if any watermark is low */
+	delay_prefetch();
+
+	return 0;	
 }
 
 static inline int
mm/swap.c +3 -0
Index: linux-2.6.13-sp/mm/swap.c
===================================================================
@@ -481,5 +481,8 @@ void __init swap_setup(void)
 	 * Right now other parts of the system means that we
 	 * _really_ don't want to cluster much more
 	 */
+
+	prepare_prefetch();
+
 	hotcpu_notifier(cpu_swap_callback, 0);
 }
mm/swap_prefetch.c +411 -0

411 lines not on this page · raw message

mm/swap_state.c +11 -1
Index: linux-2.6.13-sp/mm/swap_state.c
===================================================================
@@ -36,6 +36,8 @@ static struct backing_dev_info swap_back
 struct address_space swapper_space = {
 	.page_tree	= RADIX_TREE_INIT(GFP_ATOMIC|__GFP_NOWARN),
 	.tree_lock	= RW_LOCK_UNLOCKED,
+	.swap_tree	= RADIX_TREE_INIT(GFP_ATOMIC),
+	.swapped_pages	= LIST_HEAD_INIT(swapper_space.swapped_pages),
 	.a_ops		= &swap_aops,
 	.i_mmap_nonlinear = LIST_HEAD_INIT(swapper_space.i_mmap_nonlinear),
 	.backing_dev_info = &swap_backing_dev_info,
@@ -80,6 +82,7 @@ static int __add_to_swap_cache(struct pa
 		error = radix_tree_insert(&swapper_space.page_tree,
 						entry.val, page);
 		if (!error) {
+			remove_from_swapped_list(entry.val);
 			page_cache_get(page);
 			SetPageLocked(page);
 			SetPageSwapCache(page);
@@ -93,11 +96,12 @@ static int __add_to_swap_cache(struct pa
 	return error;
 }
 
-static int add_to_swap_cache(struct page *page, swp_entry_t entry)
+int add_to_swap_cache(struct page *page, swp_entry_t entry)
 {
 	int error;
 
 	if (!swap_duplicate(entry)) {
+		remove_from_swapped_list(entry.val);
 		INC_CACHE_INFO(noent_race);
 		return -ENOENT;
 	}
@@ -145,6 +149,9 @@ int add_to_swap(struct page * page)
 	swp_entry_t entry;
 	int err;
 
+	/* Swap prefetching is delayed if we're swapping pages */
+	delay_prefetch();
+
 	if (!PageLocked(page))
 		BUG();
 
@@ -325,6 +332,9 @@ struct page *read_swap_cache_async(swp_e
 	struct page *found_page, *new_page = NULL;
 	int err;
 
+	/* Swap prefetching is delayed if we're already reading from swap */
+	delay_prefetch();
+
 	do {
 		/*
 		 * First check the swap cache.  Since this is normally
mm/vmscan.c +5 -0
Index: linux-2.6.13-sp/mm/vmscan.c
===================================================================
@@ -519,6 +519,7 @@ static int shrink_list(struct list_head 
 #ifdef CONFIG_SWAP
 		if (PageSwapCache(page)) {
 			swp_entry_t swap = { .val = page->private };
+			add_to_swapped_list(swap.val);
 			__delete_from_swap_cache(page);
 			write_unlock_irq(&mapping->tree_lock);
 			swap_free(swap);
@@ -929,6 +930,8 @@ int try_to_free_pages(struct zone **zone
 	unsigned long lru_pages = 0;
 	int i;
 
+	delay_prefetch();
+
 	sc.gfp_mask = gfp_mask;
 	sc.may_writepage = 0;
 	sc.may_swap = 1;
@@ -1275,6 +1278,8 @@ int shrink_all_memory(int nr_pages)
 		.reclaimed_slab = 0,
 	};
 
+	delay_prefetch();
+
 	current->reclaim_state = &reclaim_state;
 	for_each_pgdat(pgdat) {
 		int freed;
#1 lore raw

Hi, Con,

Quoted 2 lines

This patch implements swap prefetching when the vm is relatively idle and there is free ram available.

I'm having a look at it now (better late than never...), and a couple of questions come to mind...

The more general of the two is: would it make sense to somehow merge your swapped_entry data structure with Rik's page-remembering scheme for CLOCK-PRO? Assumed that both are someday destined for inclusion, it seems it would make sense to add just one "remember info about swapped pages" data structure, rather than two.

Second question:

include/linux/fs.h struct address_space { · line 344

Quoted 7 lines

+++ linux-2.6.13-sp/include/linux/fs.h 2005-09-23 16:57:03.000000000 +1000

include/linux/fs.h +2 -0
@@ -340,6 +340,8 @@ struct address_space {
 	struct inode		*host;		/* owner: inode, block_device */
 	struct radix_tree_root	page_tree;	/* radix tree of all pages */
 	rwlock_t		tree_lock;	/* and rwlock protecting it */
+	struct radix_tree_root	swap_tree;	/* radix tree of swapped pages */
+	struct list_head	swapped_pages;	/* list of swapped pages */

It looks like you are adding these fields to every address_space structure in the system - and there can be a fair number of those. But further down, when it comes time to remember a swapped page:

mm/swap_prefetch.c line 97

Quoted 4 lines
mm/swap_prefetch.c +4 -0
+void add_to_swapped_list(unsigned long index)
+{
+	struct swapped_entry_t *entry;
+	struct address_space *mapping = &swapper_space;

You're only actually remembering pages associated with a single address space.

Do you anticipate adding prefetching from other address spaces as well? If not, it might be worth putting these structures somewhere else to avoid bloating the address_space structure.

...or am I missing something again...?

Thanks,

jon

#2 lore raw
Quoted 7 lines · Jonathan Corbet

Hi, Con,

Quoted 2 lines

This patch implements swap prefetching when the vm is relatively idle and there is free ram available.

I'm having a look at it now (better late than never...), and a couple of questions come to mind...

Hey thanks for looking. It can be quite hard for people to find time to review patches and I appreciate the effort.

Quoted 5 lines

The more general of the two is: would it make sense to somehow merge your swapped_entry data structure with Rik's page-remembering scheme for CLOCK-PRO? Assumed that both are someday destined for inclusion, it seems it would make sense to add just one "remember info about swapped pages" data structure, rather than two.

Indeed it would. I was hoping the time frame for inclusion of swap prefetching would be much shorter than clock pro given the relatively intrusive nature of clock pro. It would make sense to update the accounting to that of clock pro if/when clock pro was pushed. One of the features of the current accounting is it is extremely cheap and slightly sloppy on purpose since there is no point to being perfectly accurate and incur the extra overhead. Once that overhead is considered worthwhile for clock pro algorithms we can just use that data.

Quoted 6 lines

Second question:
It looks like you are adding these fields to every address_space structure in the system - and there can be a fair number of those. But

further down, when it comes time to remember a swapped page:

Quoted 8 lines

You're only actually remembering pages associated with a single address space.

Do you anticipate adding prefetching from other address spaces as well? If not, it might be worth putting these structures somewhere else to avoid bloating the address_space structure.

...or am I missing something again...?

Nope you're definitely not missing something. As you're well aware code ends up often being far from the original attempt. It's the legacy of the code evolution and it was something I would hopefully have thought about myself without being prompted by someone else. I'll have to get onto that with the next version.

Just as a data point there is still a workload that is inappopriately causing out-of-memory conditions when it shouldn't and only once I nail all known issues from the -ck users will I push it to -mm.

Thanks again

Cheers,
Con