Skip to contentSkip to conversation

VM: Implements the swap-out page-clustering technique

PATCH In review Hamid R. Jahanjou 8 participants 18 messages Sep 4, 2008 – Sep 24, 2008 1 message not in the archive

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

PATCH 1/1 VM: Implements the swap-out page-clustering technique

From: Hamid R. Jahanjou

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

---

include/linux/pageout_clustering.h +12 -0
diff -uprN -X linux-2.6.26.1-vanilla/Documentation/dontdiff linux-2.6.26.1-vanilla/include/linux/pageout_clustering.h linux-2.6.26.1HJ/include/linux/pageout_clustering.h
@@ -0,0 +1,12 @@
+#ifndef PAGEOUT_CLUSTERING_H_
+#define PAGEOUT_CLUSTERING_H_
+
+#include<linux/list.h>
+#define INITIAL_CLUSTER_SCAN_RANGE 4 
+#define HALF_PAGEOUT_CLUSTER_SIZE 8      /* default number of pages to be clustered 
+					  * on either side of a given page */
+
+int try_to_cluster(struct page *, struct list_head *, 
+		   struct list_head *, int, int);
+
+#endif 
include/linux/rmap.h +6 -0
diff -uprN -X linux-2.6.26.1-vanilla/Documentation/dontdiff linux-2.6.26.1-vanilla/include/linux/rmap.h linux-2.6.26.1HJ/include/linux/rmap.h
@@ -102,6 +102,12 @@ pte_t *page_check_address(struct page *,
 unsigned long page_address_in_vma(struct page *, struct vm_area_struct *);
 
 /*
+ * Used by pageout clustering 
+ */
+struct anon_vma *page_lock_anon_vma(struct page *);
+void page_unlock_anon_vma(struct anon_vma *);
+
+/*
  * Cleans the PTEs of shared mappings.
  * (and since clean PTEs should also be readonly, write protects them too)
  *
mm/Makefile +3 -3
diff -uprN -X linux-2.6.26.1-vanilla/Documentation/dontdiff linux-2.6.26.1-vanilla/mm/Makefile linux-2.6.26.1HJ/mm/Makefile
@@ -9,9 +9,9 @@ mmu-$(CONFIG_MMU)	:= fremap.o highmem.o 
 
 obj-y			:= bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \
 			   maccess.o page_alloc.o page-writeback.o pdflush.o \
-			   readahead.o swap.o truncate.o vmscan.o \
-			   prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
-			   page_isolation.o $(mmu-y)
+			   readahead.o swap.o truncate.o pageout_clustering.o \
+			   vmscan.o prio_tree.o util.o mmzone.o vmstat.o \
+                           backing-dev.o page_isolation.o $(mmu-y)
 
 obj-$(CONFIG_PROC_PAGE_MONITOR) += pagewalk.o
 obj-$(CONFIG_BOUNCE)	+= bounce.o
mm/pageout_clustering.c +278 -0

278 lines not on this page · raw message

mm/rmap.c +2 -2
diff -uprN -X linux-2.6.26.1-vanilla/Documentation/dontdiff linux-2.6.26.1-vanilla/mm/rmap.c linux-2.6.26.1HJ/mm/rmap.c
@@ -156,7 +156,7 @@ void __init anon_vma_init(void)
  * Getting a lock on a stable anon_vma from a page off the LRU is
  * tricky: page_lock_anon_vma rely on RCU to guard against the races.
  */
-static struct anon_vma *page_lock_anon_vma(struct page *page)
+struct anon_vma *page_lock_anon_vma(struct page *page)
 {
 	struct anon_vma *anon_vma;
 	unsigned long anon_mapping;
@@ -176,7 +176,7 @@ out:
 	return NULL;
 }
 
-static void page_unlock_anon_vma(struct anon_vma *anon_vma)
+void page_unlock_anon_vma(struct anon_vma *anon_vma)
 {
 	spin_unlock(&anon_vma->lock);
 	rcu_read_unlock();
mm/vmscan.c +10 -51

85 lines not on this page · raw message

#1 lore raw
Quoted 11 lines · On Thu, 04 Sep 2008 15:34:30 +0330 "Hamid R. Jahanjou"…

From: Hamid R. Jahanjou

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

Quoted 2 lines

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

It would be good to get some idea of what testing you have done with this patch.

Signature · 1 line
All rights reversed.
maintainer
#2 lore raw
In reply to Hamid R. Jahanjou
Quoted 8 lines · On Thu, 04 Sep 2008 15:34:30 +0330 "Hamid R. Jahanjou"…

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

I tried that once. The code all worked as-designed but didn't seem to improve performance much across a spread of workloads.

Quoted 2 lines

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

Benchmarks are essential, please. Good ones.

The whole point of the patch is to improve performance. If we don't know whether it improves performance, we cannot proceed in any way.

Secondly, please don't just dump a pile of new code in our laps and expect us to pick through it and work out what it does and how it does it. Please at least provide a carefully-written english-language description of the design and implementation.

Thirdly, I'd suggest that this code be converted into vaguely standard kernel coding style sooner rather than later. Convert it to use eight-column hard tabs then check it with scripts/checkpatch.pl, thanks.

#3 lore raw
Quoted 4 lines · Andrew Morton

I tried that once. The code all worked as-designed but didn't seem to improve performance much across a spread of workloads.

Benchmarks are essential, please. Good ones.

Do you recommend any specific benchmarks for memory-related projects ? Which
one did you use for your own implementation ?

Thank You

maintainer
#4 lore raw
Quoted 9 lines · On Fri, 05 Sep 2008 11:15:07 +0330 "Hamid R. Jahanjou"…
Quoted 4 lines · Andrew Morton

I tried that once. The code all worked as-designed but didn't seem to improve performance much across a spread of workloads.

Benchmarks are essential, please. Good ones.

Do you recommend any specific benchmarks for memory-related projects ? Which
one did you use for your own implementation ?

Pretty much any and all benchmarks, when there's not enough memory (boot with mem=). Kernel compiles, database benchmarks, you name it. Basically anything which has a measurable execution time is relevant.

Designing and running these things is a lot of work and thought. And it's an integral part of the development process, because some things are going to get slower and others will show large inter-run variations and then one needs to get in there and find explanations and hopefully fixes.

For example, start with small and simple microbenchmarks: run two processes which concurrently allocate 1*mem, then modify it all linearly, then read it all linearly. Build up from there. Do not dive into complex benchmarks on day 1, because you'll have no hope of explaining the results which they produce.

Beware that behaviour on SMP can be very different from behaviour on uniprocessor because of the relatively large duration of a timeslice. Both must be tested.

#5 lore raw
In reply to Hamid R. Jahanjou
Quoted 11 lines · Hamid R. Jahanjou

From: Hamid R. Jahanjou

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

Quoted 2 lines

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

Just some general comments:

First I think virtual swap clustering is a great idea in theory and long overdue. Hopefully the numbers will agree.

In general the code would be much nicer if you didn't pass around all that much in a structure (which is just a fancy way to have a function with lots of arguments) Perhaps try to restructure it a bit to make this smaller? Ideally clustering_info should disappear or at least get much smaller.

Then continue_search seems to be only set to one value so it can be eliminated? Perhaps there is more like this.

I didn't quite understand the "adjust the value of our search by the allocation order". The allocation order should be normally 0. I think having a tunable for the cluster sizes would be a good idea. At some point they might be even device dependent (e.g. on a flash device you would like to have them roughly erase block sized)

-Andi

Signature · 1 line
[email protected]
#6 lore raw
Quoted 20 lines · Andi Kleen
Quoted 11 lines · Hamid R. Jahanjou

From: Hamid R. Jahanjou

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

Quoted 3 lines

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

Just some general comments:

Quoted 9 lines

First I think virtual swap clustering is a great idea in theory and long overdue. Hopefully the numbers will agree.

In general the code would be much nicer if you didn't pass around all that much in a structure (which is just a fancy way to have a function with lots of arguments) Perhaps try to restructure it a bit to make this smaller? Ideally clustering_info should disappear or at least get much smaller.

Thanks for the review and the comments.
Do you consider the clustering_info struct to hurt the readability of the code or there is some other technical reasons ?

Quoted 6 lines

I didn't quite understand the "adjust the value of our search by the allocation order". The allocation order should be normally 0. I think having a tunable for the cluster sizes would be a good idea. At some point they might be even device dependent (e.g. on a flash device you would like to have them roughly erase block sized)

The allocation order value is initially passed to the try_to_free_pages() in __alloc_pages_internal() and its value can be well more than zero. The clustering code adjusts the cluster size to the value of the allocation order (in a non-linear fashion of course). In this sense the cluster size is
not determined at compile time, but the parameters affecting it are. Perhaps the term "statically-tunable" is appropriate here.

Signature · 2 lines
Hamid R. Jahanjou
([email protected]) 
#7 lore raw
Quoted 10 lines · Hamid R. Jahanjou
Quoted 6 lines

In general the code would be much nicer if you didn't pass around all that much in a structure (which is just a fancy way to have a function with lots of arguments) Perhaps try to restructure it a bit to make this smaller? Ideally clustering_info should disappear or at least get much smaller.

Thanks for the review and the comments.
Do you consider the clustering_info struct to hurt the readability of the code or there is some other technical reasons ?

It's a fancy way to have a function with lots of arguments and having lots of arguments is typically a sign for a poor code structure, with functions not being properly separated.

I know the standard scanner does it too, but it's also somewhat poor there and especially there's no excuse for doing it in much simpler code/

Quoted 9 lines
Quoted 7 lines

I didn't quite understand the "adjust the value of our search by the allocation order". The allocation order should be normally 0. I think having a tunable for the cluster sizes would be a good idea. At some point they might be even device dependent (e.g. on a flash device you would like to have them roughly erase block sized)

The allocation order value is initially passed to the try_to_free_pages()

Yes, but that has nothing to do in how much you should swap cluster.

AFAIK the main motivation for swap clustering is to avoid the extreme seekiness that happens during swap in (that is the main reason why swap on Linux often takes so long). And also to use the IO device well. IO devices today typically have a "minimum useful unit of IO" which is much larger than a page. Typically it's at least a MB, sometimes even more e.g. on flash or on some RAID controllers.

Making it even larger is good to avoid seeks on read which are very costly on spinning disks.

Also for user application swapping the order will be near always 0 (except for large page users, but that's really a exotic corner case today) And clustering for one page doesn't make much sense.

So I don't think you should care about that order, but make it a tunable and experiment what the best values are on different IO devices and then possibly later make it dependent on the device.

-Andi

Signature · 1 line
[email protected]
#8 lore raw
Quoted 8 lines · On Fri, 5 Sep 2008 21:45:01 +0200 Andi Kleen <[email protected]> wrote:

Yes, but that has nothing to do in how much you should swap cluster.

AFAIK the main motivation for swap clustering is to avoid the extreme seekiness that happens during swap in (that is the main reason why swap on Linux often takes so long). And also to use the IO device well. IO devices today typically have a "minimum useful unit of IO" which is much larger than a page. Typically it's at least a MB, sometimes even more e.g. on flash or on some RAID controllers.

That is indeed the reason.

Basically, the swap IO size should be large enough that swap throughput is not incredibly slow when swapping in lots of related data in a process.

On the other hand, you do want to avoid evicting data that the process is still using, just because you are swapping out a not recently referenced page on a nearby virtual address.

I suspect that the swap IO cluster could contain nearby and virtually contiguous pages that are (1) not recently referenced and (2) on the inactive list.

Of course, my guess may be wrong - this needs testing :)

Signature · 1 line
All rights reversed.
#9 lore raw

Rik van Riel wrote:
[cut]

Quoted 2 lines

On the other hand, you do want to avoid evicting data that the process is still using, just because you are swapping out a not recently referenced page on a nearby virtual address.

How about writing the nearby pages to swap anyway and mark the still in-use pages as SwapCache.

#10 lore raw
Quoted 9 lines · On Sun, 07 Sep 2008 18:28:30 -0600 Zan Lynx <[email protected]> wrote:

Rik van Riel wrote:
[cut]

Quoted 4 lines

On the other hand, you do want to avoid evicting data that the process is still using, just because you are swapping out a not recently referenced page on a nearby virtual address.

How about writing the nearby pages to swap anyway and mark the still in-use pages as SwapCache.

That is what will happen pretty much automatically.

Another thing the swap out page clustering code could do is move pages that were recently referenced back to the active list, so the VM will not have to scan those pages again.

Signature · 1 line
All rights reversed.
#11 lore raw
Quoted 11 lines · Rik van Riel
Quoted 8 lines · On Sun, 07 Sep 2008 18:28:30 -0600 Zan Lynx <[email protected]> wrote:

Rik van Riel wrote:
[cut]

Quoted 5 lines

On the other hand, you do want to avoid evicting data that the process is still using, just because you are swapping out a not recently referenced page on a nearby virtual address.

Quoted 6 lines
Quoted 3 lines

How about writing the nearby pages to swap anyway and mark the still in-use pages as SwapCache.

That is what will happen pretty much automatically.

I agree. As you said, we have two conflicting requirements here: on the one hand one likes to swap as many pages as to satisfy the backing storage "proper block IO size," on the other hand, one should not make a process lose too many pages. The code needs tuning really, I'm going to rewrite it making it more flexible according to the suggestion given on the mailing list.

Quoted 6 lines

Another thing the swap out page clustering code could do is move pages that were recently referenced back to the active list, so the VM will not have to scan those pages again.

I think this is a very good idea, actually the code does this already.

Thanks.

#12 lore raw
Quoted 4 lines · Hamid R. Jahanjou

I agree. As you said, we have two conflicting requirements here: on the one hand one likes to swap as many pages as to satisfy the backing storage "proper block IO size," on the other hand, one should not make a process lose too many pages.

I'd much rather that one process lose a lot of pages than many processes lose a few. When a system is swap thrashing, each process has some of its active working set tossed to swap, which means *any* application you try to switch to is then sluggish. If it were only one application, then only that one takes the penalty hit when the user switches focus and context.

#13 lore raw
Quoted 7 lines · On Wed, 10 Sep 2008 10:08:07 -0700 "Ray Lee" <[email protected]> wrote:
Quoted 4 lines · Hamid R. Jahanjou

I agree. As you said, we have two conflicting requirements here: on the one hand one likes to swap as many pages as to satisfy the backing storage "proper block IO size," on the other hand, one should not make a process lose too many pages.

Quoted 6 lines

I'd much rather that one process lose a lot of pages than many processes lose a few. When a system is swap thrashing, each process has some of its active working set tossed to swap, which means *any* application you try to switch to is then sluggish. If it were only one application, then only that one takes the penalty hit when the user switches focus and context.

Better still, with proper IO clustering that one process can get its pages back into memory quite quickly.

Paging of anonymous pages is limited by disk seeks, so minimizing those is a top goal.

Signature · 1 line
All rights reversed.
#14 lore raw
In reply to Hamid R. Jahanjou
Quoted 17 lines · Hamid R. Jahanjou

From: Hamid R. Jahanjou

Implements the idea of swap-out page clustering from *BSD for Linux. Each time a candidate page is to be swapped out, virtually-nearby pages are scanned to find eligible pages to be swapped out too as a cluster. This technique increases the likelihood of bringing in related data on a page fault and decreases swap space fragmentation in the long run. Currently, Linux searches only physically-nearby pages which is not optimal since, over time, physically- adjacent pages may become unrelated.

The code can be statically tuned. No benchmarks. I'm not sure whether the added complexity is acceptable.

[snip a lot of code here]

mm/pageout_clustering.c line 126

Quoted 6 lines
mm/pageout_clustering.c +6 -0
+
+	for(vm_address = cursor_vma->vm_start; 
+	    vm_address < cursor_vma->vm_end && ci->nr_collected < ci->cluster_size; 
+	    vm_address += PAGE_SIZE)
+	{
+	    cursor_page = virt_to_page(vm_address);

I do not think that the virt_to_page() can work well on userland virtual address space. And the linear searching for whole address space of a vma is not good idea too, really.

Quoted 4 lines
mm/pageout_clustering.c +2 -0
+	    if (!page_allowed_in_cluster(cursor_page, ci))
+		continue;
#15 lore raw

2008/9/8, Li Yu <[email protected]>:

Quoted 6 lines

And the linear searching for whole address space of a vma is not good idea too, really.

mm/pageout_clustering.c line 128

Quoted 3 lines
mm/pageout_clustering.c +2 -0
+	    if (!page_allowed_in_cluster(cursor_page, ci))
+		continue;

Thank you for the review and comments. You are right in that searching the whole process address space is not a good idea. The idea is to make the scan range flexible, thus normally, assuming that the code has been well-tuned, only a very limited number of VMA's are scanned.

In general, i think that the cluster size and the scan range should be tuned depending on the backing storage characteristics and the low-on-memory severity. Like any VM code, this one needs tuning.

BTW, the code could be implemented much more elegantly if the VMA's were connected using a doubly-linked list. I wonder if there are enought other codes with the same situation to justify making it doubly-linked.

A message that is not in the archive (sent off-list or not yet received): [email protected]

#17 lore raw
Quoted 39 lines · Li Yu
Quoted 16 lines · hamidreza jahanjou

2008/9/8, Li Yu <[email protected]>:

Quoted 8 lines

And the linear searching for whole address space of a vma is not good idea too, really.

mm/pageout_clustering.c line 128

Quoted 4 lines
mm/pageout_clustering.c +2 -0
+	    if (!page_allowed_in_cluster(cursor_page, ci))
+		continue;

Thank you for the review and comments. You are right in that searching the whole process address space is not a good idea. The idea is to make the scan range flexible, thus normally, assuming that the code has been well-tuned, only a very limited number of VMA's are scanned.

Quoted 9 lines

In general, i think that the cluster size and the scan range should be tuned depending on the backing storage characteristics and the low-on-memory severity. Like any VM code, this one needs tuning.

BTW, the code could be implemented much more elegantly if the VMA's were connected using a doubly-linked list. I wonder if there are enought other codes with the same situation to justify making it doubly-linked.

You are welcome!

I think that scanning one vma each task is enough.

The goal of swapoutclustering is to reduce disk heads movement while swapping in, it is based on space/time locality. I think that different vmas implied different using pattern, which also means they have different in program locality. Therefore, I think scanning multi vmas per task is not a good idea.

Maybe, we need a page cache searching like for anonymous mapping instead of *linear* searching in each vma.

I also have an uncompleted implementation for this feature ^_^

Good luck.

#18 lore raw
In reply to Hamid R. Jahanjou

Em Thu, 04 Sep 2008 15:34:30 +0330
"Hamid R. Jahanjou" <[email protected]> escreveu:

| From: Hamid R. Jahanjou
| 
| Implements the idea of swap-out page clustering from *BSD for
| Linux. Each time a candidate page is to be swapped out,
| virtually-nearby pages are scanned to find eligible pages to be
| swapped out too as a cluster. This technique increases the likelihood of
| bringing in related data on a page fault and decreases swap space
| fragmentation in the long run. Currently, Linux searches only
| physically-nearby pages which is not optimal since, over time, physically-
| adjacent pages may become unrelated.
| 
| The code can be statically tuned. No benchmarks. I'm not sure whether
| the added complexity is acceptable.

Sorry for this (very) late response, but I ran some very simple tests
this week and thought you might be interested in the results.

The test machine has 512MB of RAM. For the tests I booted with 64MB
and setup a 512MB swap file.

For the first test I let an allyesconfig kernel building for several
hours with six jobs (make -j6). I did not have any problems, so considering that your code was used I think it is stable enough.

In the second test I have built an allnoconfig kernel with and without
your patches, still with six jobs. Results:

	2.6.27-rc7-vanilla   44:12 minutes
	2.6.27-rc7-pgc       52:09 minutes

(pgc means page-clustering patches).

For both builds I did not change any swap paramenter and I could
observe that about 80MB of swap were used most of the time.

But please, note that these tests were quite far from being 'scientific'
eg. I should have built the kernel more times and should have tried other setups...

I will wait for the next version of the patches to run more serious
tests.

Signature · 1 line
Luiz Fernando N. Capitulino