mm - implement swap prefetching

PATCH In review Con Kolivas 3 participants 7 messages Oct 10, 2005 – Oct 15, 2005

Subsystems (7)

Memory management Documentation Page allocator MGLRU +3 more subsystems

lore

Share & tools

lore

Con Kolivas

author

2005-10-10 14:23 UTC #0 lore raw

PATCH 1/1 mm - implement swap prefetching

Andrew could you please consider this for -mm

Small changes to the style after suggestions from Pekka Enberg (thanks), and changed the default size of prefetch to gently increase with size of ram. Functionally this is the same code as vm-swap_prefetch-15 and I believe ready for a wider audience.

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 and changes in free ram representing disk writes or reads 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.

The amount prefetched in each group is configurable via the tunable in /proc/sys/vm/swap_prefetch. This is set to a value based on memory size. When laptop_mode is enabled it prefetches in ten times larger blocks to minimise the time spent reading.

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.

Signed-off-by Con Kolivas <[email protected]>

 Documentation/sysctl/vm.txt |   12 +
 include/linux/swap.h        |   33 +++
 include/linux/sysctl.h      |    1
 init/Kconfig                |   21 +
 kernel/sysctl.c             |   12 +
 mm/Makefile                 |    1
 mm/page_alloc.c             |   14 -
 mm/swap.c                   |    3
 mm/swap_prefetch.c          |  467 ++++++++++++++++++++++++++++++++++++++++++++
 mm/swap_state.c             |   10
 mm/vmscan.c                 |    5
 11 files changed, 574 insertions(+), 5 deletions(-)

Documentation/sysctl/vm.txt +12 -0

Index: linux-2.6.14-rc3/Documentation/sysctl/vm.txt
===================================================================
@@ -26,6 +26,7 @@ Currently, these files are in /proc/sys/
 - min_free_kbytes
 - laptop_mode
 - block_dump
+- swap_prefetch
 
 ==============================================================

@@ -102,3 +103,14 @@ This is used to force the Linux VM to ke
 of kilobytes free.  The VM uses this number to compute a pages_min
 value for each lowmem zone in the system.  Each lowmem zone gets 
 a number of reserved free pages based proportionally on its size.
+
+==============================================================
+
+swap_prefetch
+
+This is the amount of data prefetched per prefetching interval when
+swap prefetching is compiled in. The value means multiples of 128K,
+except when laptop_mode is enabled and then it is ten times larger.
+Setting it to 0 disables prefetching entirely.
+
+The default value is dependant on ramsize.

include/linux/swap.h +33 -0

Index: linux-2.6.14-rc3/include/linux/swap.h
===================================================================
@@ -183,6 +183,38 @@ 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);
+extern int swap_prefetch;
+
+#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 *);

@@ -204,6 +236,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;

include/linux/sysctl.h +1 -0

Index: linux-2.6.14-rc3/include/linux/sysctl.h
===================================================================
@@ -180,6 +180,7 @@ enum
 	VM_VFS_CACHE_PRESSURE=26, /* dcache/icache reclaim pressure */
 	VM_LEGACY_VA_LAYOUT=27, /* legacy/compatibility virtual address space layout */
 	VM_SWAP_TOKEN_TIMEOUT=28, /* default time for token time out */
+	VM_SWAP_PREFETCH=29,	/* int: amount to swap prefetch */
 };

init/Kconfig +21 -0

Index: linux-2.6.14-rc3/init/Kconfig
===================================================================
@@ -103,6 +103,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
+	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

kernel/sysctl.c +12 -0

Index: linux-2.6.14-rc3/kernel/sysctl.c
===================================================================
@@ -848,6 +848,18 @@ static ctl_table vm_table[] = {
 		.proc_handler	= &proc_dointvec_jiffies,
 		.strategy	= &sysctl_jiffies,
 	},
+#ifdef CONFIG_SWAP_PREFETCH
+	{
+		.ctl_name	= VM_SWAP_PREFETCH,
+		.procname	= "swap_prefetch",
+		.data		= &swap_prefetch,
+		.maxlen		= sizeof(swap_prefetch),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+	},
+#endif
 #endif
 	{ .ctl_name = 0 }
 };

mm/Makefile +1 -0

Index: linux-2.6.14-rc3/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.14-rc3/mm/page_alloc.c
===================================================================
@@ -608,7 +608,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;

@@ -685,7 +685,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;

@@ -746,7 +746,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;

@@ -755,9 +755,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.14-rc3/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 +467 -0

467 lines not on this page · raw message

mm/swap_state.c +9 -1

Index: linux-2.6.14-rc3/mm/swap_state.c
===================================================================
@@ -80,6 +80,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 +94,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;
 	}

@@ -146,6 +148,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();

@@ -321,6 +326,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.14-rc3/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);

@@ -931,6 +932,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;

@@ -1277,6 +1280,8 @@ int shrink_all_memory(int nr_pages)
 		.reclaimed_slab = 0,
 	};
 
+	delay_prefetch();
+
 	current->reclaim_state = &reclaim_state;
 	for_each_pgdat(pgdat) {
 		int freed;

Jesper Juhl

2005-10-10 14:35 UTC #1 lore raw

Quoted 7 lines · Con Kolivas

Andrew could you please consider this for -mm
Small changes to the style after suggestions from Pekka Enberg (thanks), and changed the default size of prefetch to gently increase with size of ram. Functionally this is the same code as vm-swap_prefetch-15 and I believe ready for a wider audience.

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

How about a little note about the impact for server users as well? You recommend that desktop users enable this, but you don't give any recommendation for servers.

--
Jesper Juhl <[email protected]>
Don't top-post http://www.catb.org/~esr/jargon/html/T/top-post.html
Plain text mails only, please http://www.expita.com/nomime.html

Con Kolivas

author

2005-10-10 14:40 UTC #2 lore raw

Quoted 19 lines · Jesper Juhl

Quoted 6 lines · Con Kolivas
Andrew could you please consider this for -mm
Small changes to the style after suggestions from Pekka Enberg (thanks), and changed the default size of prefetch to gently increase with size of ram. Functionally this is the same code as vm-swap_prefetch-15 and I believe ready for a wider audience.
init/Kconfig +10 -0
+	  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.

Quoted 3 lines

How about a little note about the impact for server users as well? You recommend that desktop users enable this, but you don't give any recommendation for servers.

Your guess is as good as mine. I can easily demonstrate a benefit when using it with desktop workloads but a server? It's not expensive to run but I don't really know if it's advantageous either. If I had to take a guess, a server that had multiple user logins running applications would benefit, but database, web servers etc I doubt would benefit.

Cheers,
Con

Con Kolivas

author

2005-10-11 06:48 UTC #3 lore raw

In reply to Con Kolivas

Quoted 6 lines · Con Kolivas

Andrew could you please consider this for -mm
Small changes to the style after suggestions from Pekka Enberg (thanks), and changed the default size of prefetch to gently increase with size of ram. Functionally this is the same code as vm-swap_prefetch-15 and I believe ready for a wider audience.

Here's a respin for 2.6.14-rc4

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.

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.

Signed-off-by Con Kolivas <[email protected]>

 Documentation/sysctl/vm.txt |   12 +
 include/linux/swap.h        |   33 +++
 include/linux/sysctl.h      |    1
 init/Kconfig                |   21 +
 kernel/sysctl.c             |   12 +
 mm/Makefile                 |    1
 mm/page_alloc.c             |   14 -
 mm/swap.c                   |    3
 mm/swap_prefetch.c          |  467 ++++++++++++++++++++++++++++++++++++++++++++
 mm/swap_state.c             |   10
 mm/vmscan.c                 |    5
 11 files changed, 574 insertions(+), 5 deletions(-)

Documentation/sysctl/vm.txt +12 -0

Index: linux-2.6.14-rc4/Documentation/sysctl/vm.txt
===================================================================
@@ -26,6 +26,7 @@ Currently, these files are in /proc/sys/
 - min_free_kbytes
 - laptop_mode
 - block_dump
+- swap_prefetch
 
 ==============================================================

@@ -102,3 +103,14 @@ This is used to force the Linux VM to ke
 of kilobytes free.  The VM uses this number to compute a pages_min
 value for each lowmem zone in the system.  Each lowmem zone gets 
 a number of reserved free pages based proportionally on its size.
+
+==============================================================
+
+swap_prefetch
+
+This is the amount of data prefetched per prefetching interval when
+swap prefetching is compiled in. The value means multiples of 128K,
+except when laptop_mode is enabled and then it is ten times larger.
+Setting it to 0 disables prefetching entirely.
+
+The default value is dependant on ramsize.

include/linux/swap.h +33 -0

Index: linux-2.6.14-rc4/include/linux/swap.h
===================================================================
@@ -183,6 +183,38 @@ 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, gfp_t gfp_flags);
+extern void zone_statistics(struct zonelist *zonelist, struct zone *z);
+extern int swap_prefetch;
+
+#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 *);

@@ -204,6 +236,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;

include/linux/sysctl.h +1 -0

Index: linux-2.6.14-rc4/include/linux/sysctl.h
===================================================================
@@ -180,6 +180,7 @@ enum
 	VM_VFS_CACHE_PRESSURE=26, /* dcache/icache reclaim pressure */
 	VM_LEGACY_VA_LAYOUT=27, /* legacy/compatibility virtual address space layout */
 	VM_SWAP_TOKEN_TIMEOUT=28, /* default time for token time out */
+	VM_SWAP_PREFETCH=29,	/* int: amount to swap prefetch */
 };

init/Kconfig +21 -0

Index: linux-2.6.14-rc4/init/Kconfig
===================================================================
@@ -103,6 +103,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
+	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

kernel/sysctl.c +12 -0

Index: linux-2.6.14-rc4/kernel/sysctl.c
===================================================================
@@ -848,6 +848,18 @@ static ctl_table vm_table[] = {
 		.proc_handler	= &proc_dointvec_jiffies,
 		.strategy	= &sysctl_jiffies,
 	},
+#ifdef CONFIG_SWAP_PREFETCH
+	{
+		.ctl_name	= VM_SWAP_PREFETCH,
+		.procname	= "swap_prefetch",
+		.data		= &swap_prefetch,
+		.maxlen		= sizeof(swap_prefetch),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+	},
+#endif
 #endif
 	{ .ctl_name = 0 }
 };

mm/Makefile +1 -0

Index: linux-2.6.14-rc4/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.14-rc4/mm/page_alloc.c
===================================================================
@@ -608,7 +608,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;

@@ -685,7 +685,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, gfp_t gfp_flags)
 {
 	unsigned long flags;

@@ -746,7 +746,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;

@@ -755,9 +755,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.14-rc4/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 +467 -0

467 lines not on this page · raw message

mm/swap_state.c +9 -1

Index: linux-2.6.14-rc4/mm/swap_state.c
===================================================================
@@ -80,6 +80,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 +94,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;
 	}

@@ -146,6 +148,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();

@@ -321,6 +326,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.14-rc4/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);

@@ -931,6 +932,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;

@@ -1277,6 +1280,8 @@ int shrink_all_memory(int nr_pages)
 		.reclaimed_slab = 0,
 	};
 
+	delay_prefetch();
+
 	current->reclaim_state = &reclaim_state;
 	for_each_pgdat(pgdat) {
 		int freed;

Andrew Morton

2005-10-12 05:34 UTC #4 lore raw

Quoted 39 lines · Con Kolivas

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

mm/swap_prefetch.c +35 -0

+/*
+ * Find the zone with the most free pages, recheck the watermarks and
+ * then directly allocate the ram. We don't want prefetch to use
+ * __alloc_pages and go calling on reclaim.
+ */
+static struct page *prefetch_get_page(void)
+{
+	struct zone *zone = NULL, *z;
+	struct page *page = NULL;
+	long most_free = 0;
+
+	for_each_zone(z) {
+		long free;
+
+		if (z->present_pages == 0)
+			continue;
+
+		free = z->free_pages;
+
+		/* We don't prefetch into DMA */
+		if (zone_idx(z) == ZONE_DMA)
+			continue;
+
+		/* Select the zone with the most free ram */
+		if (free > most_free) {
+			most_free = free;
+			zone = z;
+		}
+	}
+
+	if (zone == NULL)
+		goto out;
+
+	page = buffered_rmqueue(zone, 0, GFP_HIGHUSER);
+	if (likely(page)) {

mm/swap_prefetch.c line 218

Quoted 10 lines

mm/swap_prefetch.c +10 -0

+		struct zonelist *zonelist;
+
+		zonelist = NODE_DATA(numa_node_id())->node_zonelists +
+		(GFP_HIGHUSER & GFP_ZONEMASK);
+
+		zone_statistics(zonelist, zone);
+	}
+out:
+	return page;
+}

Why use the "zone with most free pages"? Generally it would be better to use up ZONE_HIGHMEM first: ZONE_NORMAL is valuable.

Quoted 39 lines

mm/swap_prefetch.c +39 -0

+/*
+ * We want to be absolutely certain it's ok to start prefetching.
+ */
+static int prefetch_suitable(void)
+{
+	struct page_state ps;
+	unsigned long pending_writes, limit;
+	struct zone *z;
+	int ret = 0;
+
+	/* Purposefully racy and might return false positive which is ok */
+	if (__test_and_clear_bit(0, &swapped.busy))
+		goto out;
+
+	temp_free = 0;
+	/*
+	 * Have some hysteresis between where page reclaiming and prefetching
+	 * will occur to prevent ping-ponging between them.
+	 */
+	for_each_zone(z) {
+		unsigned long free;
+
+		if (z->present_pages == 0)
+			continue;
+		free = z->free_pages;
+		if (z->pages_high * 3 > free)
+			goto out;
+		temp_free += free;
+	}
+
+	/*
+	 * We check to see that pages are not being allocated elsewhere
+	 * at any significant rate implying any degree of memory pressure
+	 * (eg during file reads)
+	 */
+	if (last_free) {
+		if (temp_free + SWAP_CLUSTER_MAX + prefetch_pages() <
+			last_free) {
+				last_free = temp_free;

mm/swap_prefetch.c line 329

Quoted 10 lines

mm/swap_prefetch.c +10 -0

+				goto out;
+		}
+	} else
+		last_free = temp_free;
+
+	get_page_state(&ps);
+
+	/* We shouldn't prefetch when we are doing writeback */
+	if (ps.nr_writeback)
+		goto out;

Yeah, this really needs to become per-disk-queue-aware.

mm/swap_prefetch.c line 334

Quoted 4 lines

mm/swap_prefetch.c +4 -0

+	/* Delay prefetching if we have significant amounts of dirty data */
+	pending_writes = ps.nr_dirty + ps.nr_unstable;
+	if (pending_writes > SWAP_CLUSTER_MAX)
+		goto out;

Surely this is too aggressive. There are almost always a few tens of dirty pages floating about, especially when atime updates are enabled. I'd suggest that you stick a printk in here - I expect you'll find that this test triggers a lot - too much.

mm/swap_prefetch.c line 348

Quoted 13 lines

mm/swap_prefetch.c +13 -0

+	/* >2/3 of the ram is mapped, we need some free for pagecache */
+	limit = ps.nr_mapped + ps.nr_slab + pending_writes;
+	if (limit > mapped_limit)
+		goto out;
+
+	/*
+	 * Add swapcache to limit as well, but check this last since it needs
+	 * locking
+	 */
+	if (unlikely(!read_trylock(&swapper_space.tree_lock)))
+		goto out;
+	limit += total_swapcache_pages;
+	read_unlock(&swapper_space.tree_lock);

I'd just not bother with the locking at all here.

mm/swap_prefetch.c line 410

Quoted 5 lines

mm/swap_prefetch.c +5 -0

+static int kprefetchd(void *data)
+{
+	DEFINE_WAIT(wait);
+
+	daemonize("kprefetchd");

kthread(), please.

Quoted 45 lines

mm/swap_prefetch.c +45 -0

+	set_user_nice(current, 19);
+	/* Set ioprio to lowest if supported by i/o scheduler */
+	sys_ioprio_set(IOPRIO_WHO_PROCESS, 0, IOPRIO_CLASS_IDLE);
+
+	for ( ; ; ) {
+		enum trickle_return prefetched;
+
+		try_to_freeze();
+		prepare_to_wait(&kprefetchd_wait, &wait, TASK_INTERRUPTIBLE);
+		schedule();
+		finish_wait(&kprefetchd_wait, &wait);
+
+		/* FAILED implies no entries left - the timer is not reset */
+		prefetched = trickle_swap();
+		switch (prefetched) {
+		case SUCCESS:
+			last_free = temp_free;
+			reset_prefetch_timer();
+			break;
+		case DELAY:
+			last_free = 0;
+			delay_prefetch_timer();
+			break;
+		case FAILED:
+			last_free = 0;
+			break;
+		}
+	}
+	return 0;
+}
+
+/*
+ * Wake up kprefetchd. It will reset the timer itself appropriately so no
+ * need to do it here
+ */
+static void prefetch_wakeup(unsigned long data)
+{
+	if (waitqueue_active(&kprefetchd_wait))
+		wake_up_interruptible(&kprefetchd_wait);
+}
+
+static int __init kprefetchd_init(void)
+{
+	/*
+	 * Prepare the prefetch timer. It is inactive until entries are placed

mm/swap_prefetch.c line 465

Quoted 10 lines

mm/swap_prefetch.c +10 -0

+	 * on the swapped_list
+	 */
+	init_timer(&prefetch_timer);
+	prefetch_timer.data = 0;
+	prefetch_timer.function = prefetch_wakeup;
+
+	kernel_thread(kprefetchd, NULL, CLONE_KERNEL);
+
+	return 0;
+}

Might be able to use a boring old wake_up_process() here rather than a waitqueue.

Is the timer actually needed? Could just do schedule_timeout() in kprefetchd()?

Con Kolivas

author

2005-10-12 12:00 UTC #5 lore raw

Quoted 7 lines · Andrew Morton

mm/swap_prefetch.c line 199
Quoted 3 lines · Con Kolivas
mm/swap_prefetch.c +3 -0
+		/* Select the zone with the most free ram */
+		if (free > most_free) {
+			most_free = free;
Why use the "zone with most free pages"? Generally it would be better to use up ZONE_HIGHMEM first: ZONE_NORMAL is valuable.

Ok. Sounds fair.

Quoted 5 lines

mm/swap_prefetch.c line 329
Quoted 3 lines
mm/swap_prefetch.c +3 -0
+	/* We shouldn't prefetch when we are doing writeback */
+	if (ps.nr_writeback)
+		goto out;
Yeah, this really needs to become per-disk-queue-aware.

I looked but it started looking like I was going to over-engineer.

Quoted 9 lines

mm/swap_prefetch.c line 334
Quoted 4 lines
mm/swap_prefetch.c +4 -0
+	/* Delay prefetching if we have significant amounts of dirty data */
+	pending_writes = ps.nr_dirty + ps.nr_unstable;
+	if (pending_writes > SWAP_CLUSTER_MAX)
+		goto out;
Surely this is too aggressive. There are almost always a few tens of dirty pages floating about, especially when atime updates are enabled. I'd suggest that you stick a printk in here - I expect you'll find that this test triggers a lot - too much.

Actually I was quite aware of how frequently this hits. What I found in practice was that the amount of dirty ram was an extraordinarily good marker of whether the system was globally idle / low stressed or not. It did not seem to stop prefetching from occurring in the real world on the machines I tried it on.

Quoted 6 lines

mm/swap_prefetch.c line 348
Quoted 4 lines
mm/swap_prefetch.c +4 -0
+	if (unlikely(!read_trylock(&swapper_space.tree_lock)))
+		goto out;
+	limit += total_swapcache_pages;
+	read_unlock(&swapper_space.tree_lock);
I'd just not bother with the locking at all here.

Ok.

Quoted 3 lines

mm/swap_prefetch.c line 410
Quoted 1 line
mm/swap_prefetch.c +1 -0
+	daemonize("kprefetchd");
kthread(), please.

Check.

Quoted 12 lines

mm/swap_prefetch.c line 465
Quoted 8 lines
mm/swap_prefetch.c +8 -0
+	init_timer(&prefetch_timer);
+	prefetch_timer.data = 0;
+	prefetch_timer.function = prefetch_wakeup;
+
+	kernel_thread(kprefetchd, NULL, CLONE_KERNEL);
+
+	return 0;
+}
Might be able to use a boring old wake_up_process() here rather than a waitqueue.

Quoted 2 lines

Is the timer actually needed? Could just do schedule_timeout() in kprefetchd()?

I guess. The timer just made it easy to start and stop it completely before I turned prefetch into a daemon and it kinda stayed that way. It's not run that frequently and only does miniscule things in that context; is it of a significant advantage?

Thanks very much!

Cheers,
Con

Con Kolivas

author

2005-10-15 08:11 UTC #6 lore raw

In reply to Andrew Morton

[snip snip]

Quoted 5 lines · Andrew Morton

Why use the "zone with most free pages"? Generally it would be better to use up ZONE_HIGHMEM first: ZONE_NORMAL is valuable.
I'd just not bother with the locking at all here.

Quoted 7 lines

kthread(), please.
Might be able to use a boring old wake_up_process() here rather than a waitqueue.
Is the timer actually needed? Could just do schedule_timeout() in kprefetchd()?

Ok how's this look? On top of your patches.

Cheers,
Con

-Convert kprefetchd to kthread().
-Convert timers to schedule_timeouts -Prefer highmem whenever possible to prefetch into -Remove locking from reading total_swapcache_pages -Remove waitqueues

Signed-off-by Con Kolivas <[email protected]>

mm/swap_prefetch.c +41 ~~-67~~

Index: linux-2.6.14-rc4-ck1/mm/swap_prefetch.c
===================================================================
@@ -10,11 +10,12 @@
  * published by the Free Software Foundation.
  */
 
-#include <linux/swap.h>
 #include <linux/fs.h>
+#include <linux/swap.h>
+#include <linux/ioprio.h>
+#include <linux/kthread.h>
 #include <linux/pagemap.h>
 #include <linux/syscalls.h>
-#include <linux/ioprio.h>
 #include <linux/writeback.h>
 
 /* Time to delay prefetching if vm is busy or prefetching unsuccessful */

@@ -48,9 +49,7 @@ static struct swapped_root swapped = {
 	.count 		= 0,
 };
 
-static struct timer_list prefetch_timer;
-
-static DECLARE_WAIT_QUEUE_HEAD(kprefetchd_wait);
+static task_t *kprefetchd_task;
 
 static unsigned long mapped_limit;	/* Max mapped we will prefetch to */
 static unsigned long last_free = 0;	/* Last total free pages */

@@ -77,16 +76,6 @@ void __init prepare_prefetch(void)
 		swap_prefetch++;
 }
 
-static inline void delay_prefetch_timer(void)
-{
-	mod_timer(&prefetch_timer, jiffies + PREFETCH_DELAY);
-}
-
-static inline void reset_prefetch_timer(void)
-{
-	mod_timer(&prefetch_timer, jiffies + PREFETCH_INTERVAL);
-}
-
 /*
  * We check to see no part of the vm is busy. If it is this will interrupt
  * trickle_swap and wait another PREFETCH_DELAY. Purposefully racy.

@@ -130,11 +119,11 @@ void add_to_swapped_list(unsigned long i
 		error = radix_tree_insert(&swapped.swap_tree, index, entry);
 		if (likely(!error)) {
 			/*
-			 * If this is the first entry the timer needs to be
+			 * If this is the first entry, kprefetchd needs to be
 			 * (re)started
 			 */
 			if (list_empty(&swapped.list))
-				delay_prefetch_timer();
+				wake_up_process(kprefetchd_task);
 			list_add(&entry->swapped_list, &swapped.list);
 			swapped.count++;
 		}

@@ -168,6 +157,13 @@ void remove_from_swapped_list(unsigned l
 	spin_unlock_irqrestore(&swapped.lock, flags);
 }
 
+static inline int high_zone(struct zone *zone)
+{
+	if (zone == NULL)
+		return 0;
+	return is_highmem(zone);
+}
+
 /*
  * Find the zone with the most free pages, recheck the watermarks and
  * then directly allocate the ram. We don't want prefetch to use

@@ -185,16 +181,16 @@ static struct page *prefetch_get_page(vo
 		if (z->present_pages == 0)
 			continue;
 
-		free = z->free_pages;
-
 		/* We don't prefetch into DMA */
 		if (zone_idx(z) == ZONE_DMA)
 			continue;
 
-		/* Select the zone with the most free ram */
-		if (free > most_free) {
-			most_free = free;
-			zone = z;
+		free = z->free_pages;
+		/* Select the zone with the most free ram preferring high */
+		if ((free > most_free && (!high_zone(zone) || high_zone(z))) ||
+			(!high_zone(zone) && high_zone(z))) {
+				most_free = free;
+				zone = z;
 		}
 	}

@@ -330,19 +326,12 @@ static int prefetch_suitable(void)
 	if (pending_writes > SWAP_CLUSTER_MAX)
 		goto out;
 
-	/* >2/3 of the ram is mapped, we need some free for pagecache */
-	limit = ps.nr_mapped + ps.nr_slab + pending_writes;
-	if (limit > mapped_limit)
-		goto out;
-
 	/*
-	 * Add swapcache to limit as well, but check this last since it needs
-	 * locking
+	 * >2/3 of the ram is mapped or swapcache, we need some free for
+	 * pagecache
 	 */
-	if (unlikely(!read_trylock(&swapper_space.tree_lock)))
-		goto out;
-	limit += total_swapcache_pages;
-	read_unlock(&swapper_space.tree_lock);
+	limit = ps.nr_mapped + ps.nr_slab + pending_writes +
+		total_swapcache_pages;
 	if (limit > mapped_limit)
 		goto out;

@@ -400,68 +389,53 @@ out:
 	return ret;
 }
 
-static int kprefetchd(void *data)
+static int kprefetchd(void *__unused)
 {
-	DEFINE_WAIT(wait);
-
-	daemonize("kprefetchd");
 	set_user_nice(current, 19);
 	/* Set ioprio to lowest if supported by i/o scheduler */
 	sys_ioprio_set(IOPRIO_WHO_PROCESS, 0, IOPRIO_CLASS_IDLE);
 
-	for ( ; ; ) {
+	do {
 		enum trickle_return prefetched;
 
 		try_to_freeze();
-		prepare_to_wait(&kprefetchd_wait, &wait, TASK_INTERRUPTIBLE);
-		schedule();
-		finish_wait(&kprefetchd_wait, &wait);
 
 		/*
-		 * TRICKLE_FAILED implies no entries left - the timer is not
-		 * reset
+		 * TRICKLE_FAILED implies no entries left - we do not schedule
+		 * a wakeup, and further delay the next one.
 		 */
 		prefetched = trickle_swap();
 		switch (prefetched) {
 		case TRICKLE_SUCCESS:
 			last_free = temp_free;
-			reset_prefetch_timer();
+			schedule_timeout_interruptible(PREFETCH_INTERVAL);
 			break;
 		case TRICKLE_DELAY:
 			last_free = 0;
-			delay_prefetch_timer();
+			schedule_timeout_interruptible(PREFETCH_DELAY);
 			break;
 		case TRICKLE_FAILED:
 			last_free = 0;
+			schedule_timeout_interruptible(MAX_SCHEDULE_TIMEOUT);
+			schedule_timeout_interruptible(PREFETCH_DELAY);
 			break;
 		}
-	}
-	return 0;
-}
+	} while (!kthread_should_stop());
 
-/*
- * Wake up kprefetchd. It will reset the timer itself appropriately so no
- * need to do it here
- */
-static void prefetch_wakeup(unsigned long data)
-{
-	if (waitqueue_active(&kprefetchd_wait))
-		wake_up_interruptible(&kprefetchd_wait);
+	return 0;
 }
 
 static int __init kprefetchd_init(void)
 {
-	/*
-	 * Prepare the prefetch timer. It is inactive until entries are placed
-	 * on the swapped_list
-	 */
-	init_timer(&prefetch_timer);
-	prefetch_timer.data = 0;
-	prefetch_timer.function = prefetch_wakeup;
-
-	kernel_thread(kprefetchd, NULL, CLONE_KERNEL);
+	kprefetchd_task = kthread_run(kprefetchd, NULL, "kprefetchd");
 
 	return 0;
 }
 
-module_init(kprefetchd_init)
+static void __exit kprefetchd_exit(void)
+{
+	kthread_stop(kprefetchd_task);
+}
+
+module_init(kprefetchd_init);
+module_exit(kprefetchd_exit);