Skip to contentSkip to conversation

vm: swap prefetch

RFC PATCH In review Con Kolivas 4 participants 7 messages Sep 1, 2005 – Sep 2, 2005

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

RFC PATCH 1/1 vm: swap prefetch

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

http://ck.kolivas.org/patches/swap-prefetch/

These add an exclusive_timer function, and the patch that does the swap prefetching. I'm posting this rollup to lkml to see what the interest is in this feature, and for people to test it if they desire. I'm planning on including it in the next -ck but wanted to gauge general user opinion for mainline. Note that swapped in pages are kept on backing store (swap), meaning no further I/O is required if the page needs to swap back out.

Cheers,
Con Kolivas

include/linux/fs.h +2 -0
Index: linux-2.6.13/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 +28 -0
Index: linux-2.6.13/include/linux/swap.h
===================================================================
@@ -206,6 +206,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;
@@ -247,6 +248,33 @@ static inline void put_swap_token(struct
 		__put_swap_token(mm);
 }
 
+#ifdef CONFIG_SWAP_PREFETCH
+/*	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 int trickle_swap(void);
+extern void delay_prefetch_timer(void);
+
+#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_timer(void)
+{
+}
+
+#endif	/* CONFIG_SWAP_PREFETCH */
+
 #else /* CONFIG_SWAP */
 
 #define total_swap_pages			0
include/linux/timer.h +1 -0
Index: linux-2.6.13/include/linux/timer.h
===================================================================
@@ -53,6 +53,7 @@ extern void add_timer_on(struct timer_li
 extern int del_timer(struct timer_list * timer);
 extern int __mod_timer(struct timer_list *timer, unsigned long expires);
 extern int mod_timer(struct timer_list *timer, unsigned long expires);
+extern int exclusive_timer(struct timer_list *timer, unsigned long expires);
 
 extern unsigned long next_timer_interrupt(void);
 
init/Kconfig +11 -0
Index: linux-2.6.13/init/Kconfig
===================================================================
@@ -87,6 +87,17 @@ 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 (EXPERIMENTAL)"
+	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. This is desirable on workstations.
+	  Desktop users will most likely want to say Y.
+
 config SYSVIPC
 	bool "System V IPC"
 	depends on MMU
kernel/timer.c +24 -0
Index: linux-2.6.13/kernel/timer.c
===================================================================
@@ -329,6 +329,30 @@ int mod_timer(struct timer_list *timer, 
 	return __mod_timer(timer, expires);
 }
 
+/***
+ * exclusive_timer - add a timer only if one doesn't already exist
+ * @timer: the timer to be modified
+ *
+ * This is a safe way to add a timer when multiple concurrent users are
+ * potentially setting a timer, and only one timer is desired.
+ *
+ * The function returns 1 if a timer was added.
+ */
+int exclusive_timer(struct timer_list *timer, unsigned long expires)
+{
+	BUG_ON(!timer->function);
+
+	check_timer(timer);
+	if (timer_pending(timer))
+		return 0;
+
+	/*
+	 * __mod_timer returns the opposite value, and this should always
+	 * return 1
+	 */
+	return (!__mod_timer(timer, expires));
+}
+
 EXPORT_SYMBOL(mod_timer);
 
 /***
mm/Makefile +1 -0
Index: linux-2.6.13/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/swap.c +3 -0
Index: linux-2.6.13/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 +198 -0

198 lines not on this page · raw message

mm/swap_state.c +5 -1
Index: linux-2.6.13/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;
 	}
mm/vmscan.c +7 -2
Index: linux-2.6.13/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);
@@ -1256,9 +1257,13 @@ void wakeup_kswapd(struct zone *zone, in
 		pgdat->kswapd_max_order = order;
 	if (!cpuset_zone_allowed(zone))
 		return;
-	if (!waitqueue_active(&zone->zone_pgdat->kswapd_wait))
+	if (!waitqueue_active(&pgdat->kswapd_wait))
 		return;
-	wake_up_interruptible(&zone->zone_pgdat->kswapd_wait);
+	
+	/* The prefetch timer is delayed while any kswapd is busy */
+	delay_prefetch_timer();
+
+	wake_up_interruptible(&pgdat->kswapd_wait);
 }
 
 #ifdef CONFIG_PM
#1 lore raw
Quoted 7 lines · Con Kolivas

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

Quoted 8 lines

http://ck.kolivas.org/patches/swap-prefetch/

These add an exclusive_timer function, and the patch that does the swap prefetching. I'm posting this rollup to lkml to see what the interest is in this feature, and for people to test it if they desire. I'm planning on including it in the next -ck but wanted to gauge general user opinion for mainline. Note that swapped in pages are kept on backing store (swap), meaning no further I/O is required if the page needs to swap back out.

I would definitely use this if available.

That said, I have often thought it might be good to have something like pre-writing swap, ie reverse what your patch does.

In other words it'd keep as much of swappable data on disk as possible, but without removing it from memory. So when it comes time to free up some memory, the data is already on disk so no performance penalty from writing it out.

Hopefully something worth thinking about.

-HK

#2 lore raw
Quoted 18 lines · Hans Kristian Rosbach
Quoted 9 lines · Con Kolivas

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

http://ck.kolivas.org/patches/swap-prefetch/

Quoted 7 lines

These add an exclusive_timer function, and the patch that does the swap prefetching. I'm posting this rollup to lkml to see what the interest is in this feature, and for people to test it if they desire. I'm planning on including it in the next -ck but wanted to gauge general user opinion for mainline. Note that swapped in pages are kept on backing store (swap), meaning no further I/O is required if the page needs to swap back out.

Quoted 1 line

I would definitely use this if available.

Great.

Quoted 9 lines

That said, I have often thought it might be good to have something like pre-writing swap, ie reverse what your patch does.

In other words it'd keep as much of swappable data on disk as possible, but without removing it from memory. So when it comes time to free up some memory, the data is already on disk so no performance penalty from writing it out.

Hopefully something worth thinking about.

Actually to some degree this patch does that, albeit only on things that are swapped out "naturally". Anything that is swapped out and is unnaturally swapped back in using prefetching is kept on swap, and you often find much more swap sitting around ready for freeing up ram whenever there is memory pressure again.

Cheers,
Con

#6 lore raw
In reply to Con Kolivas

Hi Con!

Am Donnerstag, 1. September 2005 15:46 schrieb Con Kolivas:

Quoted 7 lines

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

Quoted 8 lines

http://ck.kolivas.org/patches/swap-prefetch/

These add an exclusive_timer function, and the patch that does the swap prefetching. I'm posting this rollup to lkml to see what the interest is in this feature, and for people to test it if they desire. I'm planning on including it in the next -ck but wanted to gauge general user opinion for mainline. Note that swapped in pages are kept on backing store (swap), meaning no further I/O is required if the page needs to swap back out.

I am (and some of my friends are) still interested in this functionality, so I'm definitly going to test your improved patch, of course. By the way, I'm quite happy that you came up with this new version of swap-prefetching, because I didn't and still don't have the time to develop or maintain it more...

So thanks for your good work, and keep on helping Linux-Desktop-Users! :-)

Thomas

#3 lore raw
In reply to Con Kolivas
Quoted 10 lines · Con Kolivas
Quoted 8 lines · Hans Kristian Rosbach
Quoted 7 lines · Con Kolivas

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

Quoted 7 lines
Quoted 7 lines

That said, I have often thought it might be good to have something like pre-writing swap, ie reverse what your patch does.

In other words it'd keep as much of swappable data on disk as possible, but without removing it from memory. So when it comes time to free up some memory, the data is already on disk so no performance penalty from writing it out.

both ideas make all the sense to me. I'll give it a try, but in what way can we test this kind of enhancement? maybe write a small program that starts fills a good part of swap space and then, after 1min idle, 'watch free -m' should show free memory decreasing (not counting cache/buffers) with idle activity. decent?

about the Hans's proposal - it would increase power consumption, because of increased disk activity. about con's swap prefetch, I'm not so sure...

regards,
pedro venda.

Signature · 3 lines
Pedro João Lopes Venda
email: pjvenda < at > arrakis.dhis.org
http://arrakis.dhis.org
#4 lore raw
Quoted 19 lines · Pedro Venda
Quoted 10 lines · Con Kolivas
Quoted 9 lines · Hans Kristian Rosbach
Quoted 7 lines · Con Kolivas

Here is a working swap prefetching patch for 2.6.13. I have resuscitated and rewritten some early prefetch code Thomas Schlichter did in late 2.5 to create a configurable kernel thread that reads in swap from ram in reverse order it was written out. It does this once kswapd has been idle for a minute (implying no current vm stress). This patch attached below is a rollup of two patches the current versions of which are here:

Quoted 7 lines
Quoted 7 lines

That said, I have often thought it might be good to have something like pre-writing swap, ie reverse what your patch does.

In other words it'd keep as much of swappable data on disk as possible, but without removing it from memory. So when it comes time to free up some memory, the data is already on disk so no performance penalty from writing it out.

Quoted 5 lines

both ideas make all the sense to me. I'll give it a try, but in what way can we test this kind of enhancement? maybe write a small program that starts fills a good part of swap space and then, after 1min idle, 'watch free -m' should show free memory decreasing (not counting cache/buffers) with idle activity. decent?

Yes that about wraps up what it does. It would be even better used in a real world situation on a machine that has trouble "getting started" after an overnight updatedb run and has been idle for a while.

Quoted 2 lines

about the Hans's proposal - it would increase power consumption, because of increased disk activity. about con's swap prefetch, I'm not so sure...

Depends entirely on workload. Overall I think this increases power consumption because the disk does tiny little reads and keeps spinning until it has finished prefetching as much as it can. I was thinking it could be made configurable and to detect when laptop mode was enabled and so on... if it is thought that this is desirable of course.

Cheers,
Con

#5 lore raw
Quoted 3 lines · Con Kolivas

Yes that about wraps up what it does. It would be even better used in a real world situation on a machine that has trouble "getting started" after an overnight updatedb run and has been idle for a while.

thanks. your last comment about updatedb reminds me of my "server"'s kind of load :-p

Quoted 8 lines
Quoted 2 lines

about the Hans's proposal - it would increase power consumption, because of increased disk activity. about con's swap prefetch, I'm not so sure...

Depends entirely on workload. Overall I think this increases power consumption because the disk does tiny little reads and keeps spinning until it has finished prefetching as much as it can. I was thinking it could be made configurable and to detect when laptop mode was enabled and so on... if it is thought that this is desirable of course.

Not counting hard drive spin-down or even standby, I find no reason for increased power consumption on swap prefetch mechanism, except for page syncing (swap&mem) and perhaps upon process killing...

Question: Imagine some big app like firefox completely swapped. killing it implies swapping out the process memory entirely to free allocated pages?

- If it does, then your swap prefetch may not increase power consumption by a measurable margin, because some of that swapped information was prefetched.
- If it does not, than prefetched swapped pages could be useless if the applications dies.

I don't know enough about the kernel VM to answer this on my own.

regards,
pedro venda.

Signature · 3 lines
Pedro João Lopes Venda
email: pjvenda < at > arrakis.dhis.org
http://arrakis.dhis.org