swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Signed-off-by Shaohua Li <[email protected]>

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

This patch depends on readahead-fault-retry-breaks-mmap-file-read-random-detection.patch

V1->V2:
1. Move the swap readahead accounting to separate functions as suggested by Riel.
2. Enable the logic only with CONFIG_SWAP enabled as suggested by Minchan.

Signed-off-by Shaohua Li<[email protected]>

---
  include/linux/mm_types.h |    3 +++
  mm/internal.h            |   44 ++++++++++++++++++++++++++++++++++++++++++++
  mm/memory.c              |    3 ++-
  mm/swap_state.c          |    8 ++++++++
  4 files changed, 57 insertions(+), 1 deletion(-)

Quoted 5 lines

include/linux/mm_types.h +0 -0

@@ -279,6 +279,9 @@ struct vm_area_struct {
 #ifdef CONFIG_NUMA
 	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */

include/linux/mm_types.h struct vm_area_struct { · line 284

Quoted 4 lines

include/linux/mm_types.h +3 -0

 #endif
+#ifdef CONFIG_SWAP
+	atomic_t swapra_miss;
+#endif

You can place this atomic on vma->anon_vma, it has perfect 4-byte hole right after field "refcount". vma->anon_vma already exists since this vma already contains anon pages.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

This patch depends on readahead-fault-retry-breaks-mmap-file-read-random-detection.patch

V2->V3:
move swapra_miss to 'struct anon_vma' as suggested by Konstantin.

V1->V2:
1. Move the swap readahead accounting to separate functions as suggested by Riel.
2. Enable the logic only with CONFIG_SWAP enabled as suggested by Minchan.

Signed-off-by Shaohua Li <[email protected]>

Quoted 5 lines · Konstantin Khlebnikov

Quoted 5 lines

include/linux/mm_types.h +0 -0

@@ -279,6 +279,9 @@ struct vm_area_struct {
 #ifdef CONFIG_NUMA
 	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */

Quoted 8 lines

include/linux/mm_types.h struct vm_area_struct { · line 284

Quoted 4 lines

include/linux/mm_types.h +3 -0

 #endif
+#ifdef CONFIG_SWAP
+	atomic_t swapra_miss;
+#endif

You can place this atomic on vma->anon_vma, it has perfect 4-byte hole right after field "refcount". vma->anon_vma already exists since this vma already contains anon pages.

makes sense. vma->anon_vma could be NUll (shmem), but in shmem case, vma could NULL too, so maybe just ignore it.

Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

This patch depends on readahead-fault-retry-breaks-mmap-file-read-random-detection.patch

V2->V3:
move swapra_miss to 'struct anon_vma' as suggested by Konstantin.

V1->V2:
1. Move the swap readahead accounting to separate functions as suggested by Riel.
2. Enable the logic only with CONFIG_SWAP enabled as suggested by Minchan.

Signed-off-by Shaohua Li <[email protected]>

---
 include/linux/rmap.h |    3 +++
 mm/internal.h        |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/memory.c          |    3 ++-
 mm/shmem.c           |    1 +
 mm/swap_state.c      |    6 ++++++
 5 files changed, 62 insertions(+), 1 deletion(-)

Index: linux/mm/swap_state.c
===================================================================

mm/swap_state.c +6 -0

@@ -20,6 +20,7 @@
 #include <linux/page_cgroup.h>
 
 #include <asm/pgtable.h>
+#include "internal.h"
 
 /*
  * swapper_space is a fiction, retained to simplify the path through

@@ -379,6 +380,10 @@ struct page *swapin_readahead(swp_entry_
 	unsigned long mask = (1UL << page_cluster) - 1;
 	struct blk_plug plug;
 
+	swap_cache_miss(vma);
+	if (swap_cache_skip_readahead(vma))
+		goto skip;
+
 	/* Read a page_cluster sized and aligned cluster around offset. */
 	start_offset = offset & ~mask;
 	end_offset = offset | mask;

@@ -397,5 +402,6 @@ struct page *swapin_readahead(swp_entry_
 	blk_finish_plug(&plug);
 
 	lru_add_drain();	/* Push any new pages onto the LRU now */
+skip:
 	return read_swap_cache_async(entry, gfp_mask, vma, addr);
 }

Index: linux/mm/memory.c
===================================================================

mm/memory.c +2 -1

@@ -2953,7 +2953,8 @@ static int do_swap_page(struct mm_struct
 		ret = VM_FAULT_HWPOISON;
 		delayacct_clear_flag(DELAYACCT_PF_SWAPIN);
 		goto out_release;
-	}
+	} else if (!(flags & FAULT_FLAG_TRIED))
+		swap_cache_hit(vma);
 
 	locked = lock_page_or_retry(page, mm, flags);
 

Index: linux/mm/internal.h
===================================================================

mm/internal.h +16 -0

@@ -12,6 +12,7 @@
 #define __MM_INTERNAL_H
 
 #include <linux/mm.h>
+#include <linux/rmap.h>
 
 void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
 		unsigned long floor, unsigned long ceiling);

@@ -356,3 +357,52 @@ extern unsigned long vm_mmap_pgoff(struc
         unsigned long, unsigned long);
 
 extern void set_pageblock_order(void);
+
+/*
+ * Unnecessary readahead harms performance. 1. for SSD, big size read is more
+ * expensive than small size read, so extra unnecessary read only has overhead.
+ * For harddisk, this overhead doesn't exist. 2. unnecessary readahead will
+ * allocate extra memroy, which further tights memory pressure, so more
+ * swapout/swapin.
+ * These adds a simple swap random access detection. In swap page fault, if
+ * page is found in swap cache, decrease an account of vma, otherwise we need
+ * do sync swapin and the account is increased. Optionally swapin will do
+ * readahead if the counter is below a threshold.
+ */
+#ifdef CONFIG_SWAP
+#define SWAPRA_MISS  (100)
+static inline void swap_cache_hit(struct vm_area_struct *vma)

mm/internal.h +24 -0

+		atomic_inc(&vma->anon_vma->swapra_miss);
+}
+
+static inline int swap_cache_skip_readahead(struct vm_area_struct *vma)
+{
+	if (!vma || !vma->anon_vma)
+		return 0;
+	return atomic_read(&vma->anon_vma->swapra_miss) > SWAPRA_MISS;
+}
+#else
+static inline void swap_cache_hit(struct vm_area_struct *vma)
+{
+}
+
+static inline void swap_cache_miss(struct vm_area_struct *vma)
+{
+}
+
+static inline int swap_cache_skip_readahead(struct vm_area_struct *vma)
+{
+	return 0;
+}
+
+#endif

Index: linux/include/linux/rmap.h
===================================================================

include/linux/rmap.h +3 -0

@@ -35,6 +35,9 @@ struct anon_vma {
 	 * anon_vma if they are the last user on release
 	 */
 	atomic_t refcount;
+#ifdef CONFIG_SWAP
+	atomic_t swapra_miss;
+#endif
 
 	/*
 	 * NOTE: the LSB of the head.next is set by

Index: linux/mm/shmem.c
===================================================================

*/
#define SWAPRA_SKIP_THRESHOLD 100
#define SWAPRA_MISS_MAX_COUNT (SWAPRA_SKIP_THRESHOLD * 10)

mm/shmem.c static struct page *shmem_swapin(swp_ent · line 936

Quoted 8 lines

===================================================================

mm/shmem.c +1 -0

@@ -933,6 +933,7 @@ static struct page *shmem_swapin(swp_ent
 	pvma.vm_pgoff = index + info->vfs_inode.i_ino;
 	pvma.vm_ops = NULL;
 	pvma.vm_policy = spol;
+	pvma.anon_vma = NULL;

So, shmem always do readahead blindly still?

Quoted 3 lines · Minchan Kim

*/
#define SWAPRA_SKIP_THRESHOLD 100
#define SWAPRA_MISS_MAX_COUNT (SWAPRA_SKIP_THRESHOLD * 10)

Ok, updated to use macro.

Quoted 10 lines

mm/shmem.c static struct page *shmem_swapin(swp_ent · line 936

Quoted 8 lines

===================================================================

mm/shmem.c +1 -0

@@ -933,6 +933,7 @@ static struct page *shmem_swapin(swp_ent
 	pvma.vm_pgoff = index + info->vfs_inode.i_ino;
 	pvma.vm_ops = NULL;
 	pvma.vm_policy = spol;
+	pvma.anon_vma = NULL;

So, shmem always do readahead blindly still?

yes, I had no idea how to prevent the ra for shmem so far. It could be a tmpfs file read, so no vma ever.

Thanks,
Shaohua

Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

This patch depends on readahead-fault-retry-breaks-mmap-file-read-random-detection.patch

V2->V3:
move swapra_miss to 'struct anon_vma' as suggested by Konstantin.

V1->V2:
1. Move the swap readahead accounting to separate functions as suggested by Riel.
2. Enable the logic only with CONFIG_SWAP enabled as suggested by Minchan.

Signed-off-by Shaohua Li <[email protected]>

Acked-by Rik van Riel <[email protected]>

---
 include/linux/rmap.h |    3 ++
 mm/internal.h        |   52 +++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/memory.c          |    3 +-
 mm/shmem.c           |    1 
 mm/swap_state.c      |    6 +++++
 5 files changed, 64 insertions(+), 1 deletion(-)

Index: linux/mm/swap_state.c
===================================================================

mm/swap_state.c +6 -0

@@ -20,6 +20,7 @@
 #include <linux/page_cgroup.h>
 
 #include <asm/pgtable.h>
+#include "internal.h"
 
 /*
  * swapper_space is a fiction, retained to simplify the path through

@@ -379,6 +380,10 @@ struct page *swapin_readahead(swp_entry_
 	unsigned long mask = (1UL << page_cluster) - 1;
 	struct blk_plug plug;
 
+	swap_cache_miss(vma);
+	if (swap_cache_skip_readahead(vma))
+		goto skip;
+
 	/* Read a page_cluster sized and aligned cluster around offset. */
 	start_offset = offset & ~mask;
 	end_offset = offset | mask;

@@ -397,5 +402,6 @@ struct page *swapin_readahead(swp_entry_
 	blk_finish_plug(&plug);
 
 	lru_add_drain();	/* Push any new pages onto the LRU now */
+skip:
 	return read_swap_cache_async(entry, gfp_mask, vma, addr);
 }

Index: linux/mm/memory.c
===================================================================

mm/memory.c +2 -1

@@ -2953,7 +2953,8 @@ static int do_swap_page(struct mm_struct
 		ret = VM_FAULT_HWPOISON;
 		delayacct_clear_flag(DELAYACCT_PF_SWAPIN);
 		goto out_release;
-	}
+	} else if (!(flags & FAULT_FLAG_TRIED))
+		swap_cache_hit(vma);
 
 	locked = lock_page_or_retry(page, mm, flags);
 

Index: linux/mm/internal.h
===================================================================

mm/internal.h +52 -0

@@ -12,6 +12,7 @@
 #define __MM_INTERNAL_H
 
 #include <linux/mm.h>
+#include <linux/rmap.h>
 
 void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
 		unsigned long floor, unsigned long ceiling);

@@ -356,3 +357,54 @@ extern unsigned long vm_mmap_pgoff(struc
         unsigned long, unsigned long);
 
 extern void set_pageblock_order(void);
+
+/*
+ * Unnecessary readahead harms performance. 1. for SSD, big size read is more
+ * expensive than small size read, so extra unnecessary read only has overhead.
+ * For harddisk, this overhead doesn't exist. 2. unnecessary readahead will
+ * allocate extra memroy, which further tights memory pressure, so more
+ * swapout/swapin.
+ * These adds a simple swap random access detection. In swap page fault, if
+ * page is found in swap cache, decrease an account of vma, otherwise we need
+ * do sync swapin and the account is increased. Optionally swapin will do
+ * readahead if the counter is below a threshold.
+ */
+#ifdef CONFIG_SWAP
+#define SWAPRA_MISS_THRESHOLD  (100)
+#define SWAPRA_MAX_MISS ((SWAPRA_MISS_THRESHOLD) * 10)
+static inline void swap_cache_hit(struct vm_area_struct *vma)
+{
+	if (vma && vma->anon_vma)
+		atomic_dec_if_positive(&vma->anon_vma->swapra_miss);
+}
+
+static inline void swap_cache_miss(struct vm_area_struct *vma)
+{
+	if (!vma || !vma->anon_vma)
+		return;
+	if (atomic_read(&vma->anon_vma->swapra_miss) < SWAPRA_MAX_MISS)
+		atomic_inc(&vma->anon_vma->swapra_miss);
+}
+
+static inline int swap_cache_skip_readahead(struct vm_area_struct *vma)
+{
+	if (!vma || !vma->anon_vma)
+		return 0;
+	return atomic_read(&vma->anon_vma->swapra_miss) >
+		SWAPRA_MISS_THRESHOLD;
+}
+#else
+static inline void swap_cache_hit(struct vm_area_struct *vma)
+{
+}
+
+static inline void swap_cache_miss(struct vm_area_struct *vma)
+{
+}
+
+static inline int swap_cache_skip_readahead(struct vm_area_struct *vma)
+{
+	return 0;
+}
+
+#endif

Index: linux/include/linux/rmap.h
===================================================================

Don't we need initialization?

mm/rmap.c +0 -0

index 0f3b7cd..c0f3221 100644

On Mon, Sep 03, 2012 at 05:32:45PM +0900, Minchan Kim wrote:
Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

Quoted 25 lines · Shaohua Li

On Mon, Sep 03, 2012 at 05:32:45PM +0900, Minchan Kim wrote:
Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has
no penality in harddisk, and if the readahead pages are garbage, they can be
reclaimed fastly. But for SSD, big size read is more expensive than small size
read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead
does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

Quoted 7 lines

For both harddisk and SSD, the randwrite swap workload run time is reduced
significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

Generally speaking swapin readahread isn't usable while system is under memory
pressure. Cache hit isn't very probable, because reclaimer allocates swap entries in page-LRU order.

But swapin readahead is very useful if system recovers from memory pressure,
it helps to read whole swap back to memory (a sort of desktop scenario).

So, I think we can simply disable swapin readahead while system is under memory
pressure. For example in time-based manner -- enable it only after grace period
after last swap_writepage().

Quoted 43 lines · Konstantin Khlebnikov

Quoted 25 lines · Shaohua Li

On Mon, Sep 03, 2012 at 05:32:45PM +0900, Minchan Kim wrote:
Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has
no penality in harddisk, and if the readahead pages are garbage, they can be
reclaimed fastly. But for SSD, big size read is more expensive than small size
read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead
does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

Quoted 7 lines

For both harddisk and SSD, the randwrite swap workload run time is reduced
significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

Generally speaking swapin readahread isn't usable while system is under memory
pressure. Cache hit isn't very probable, because reclaimer allocates swap entries in page-LRU order.

But swapin readahead is very useful if system recovers from memory pressure,
it helps to read whole swap back to memory (a sort of desktop scenario).

Quoted 5 lines

So, I think we can simply disable swapin readahead while system is under memory
pressure. For example in time-based manner -- enable it only after grace period
after last swap_writepage().

Determining "under memory pressure" is pretty hard to do.

However, Shaohua's patch provides an easy way to see whether swap readahead is helping (we are getting pages from the swap cache), or whether it is not (pages got evicted before someone faulted on them).

In short, Shaohua's patch not only does roughly what you want, it does it in a simple way.

It disables reahahead if it is ineffective in one particular VMA, but in recovering-case this does not important -- we really want to read whole swap back, no matter which VMA around pages belongs to. [BTW this case was mentioned in you patch which added skipping-over-holes]

And its metric is strange, looks like it just disables headahead for all VMAs
after hundred swapins and never enables it back. Why we cannot disable it from
the beginning and turn it on when needed? This ways is even more simple.

This patch adds simple tracker for swapin readahread effectiveness, and tunes readahead cluster depending on it. It manage internal state [0..1024] and scales readahead order between 0 and value from sysctl vm.page-cluster (3 by default). Swapout and readahead misses decreases state, swapin and ra hits increases it:

 Swapin          +1		[page fault, shmem, etc... ]
 Swapout         -10
 Readahead hit   +10
 Readahead miss  -1		[removing from swapcache unused readahead page]

If system is under serious memory pressure swapin readahead is useless, because pages in swap are highly fragmented and cache hit is mostly impossible. In this case swapin only leads to unnecessary memory allocations. But readahead helps to read all swapped pages back to memory if system recovers from memory pressure.

This patch inspired by patch from Shaohua Li
http://www.spinics.net/lists/linux-mm/msg41128.html
mine version uses system wide state rather than per-VMA counters.

Signed-off-by Konstantin Khlebnikov <[email protected]>

Shaohua, Konstantin,

Sorry that it takes me so long to to reply on these swapin readahead bounding threads, but I had to try some things out before jumping in, and only found time to experiment last week.

Quoted 15 lines · Konstantin Khlebnikov

This patch adds simple tracker for swapin readahread effectiveness, and tunes readahead cluster depending on it. It manage internal state [0..1024] and scales readahead order between 0 and value from sysctl vm.page-cluster (3 by default). Swapout and readahead misses decreases state, swapin and ra hits increases it:

  Swapin          +1           [page fault, shmem, etc... ]
  Swapout         -10
  Readahead hit   +10
  Readahead miss  -1           [removing from swapcache unused readahead page]

If system is under serious memory pressure swapin readahead is useless, because pages in swap are highly fragmented and cache hit is mostly impossible. In this case swapin only leads to unnecessary memory allocations. But readahead helps to read all swapped pages back to memory if system recovers from memory pressure.

Quoted 5 lines

This patch inspired by patch from Shaohua Li
http://www.spinics.net/lists/linux-mm/msg41128.html
mine version uses system wide state rather than per-VMA counters.

Signed-off-by Konstantin Khlebnikov<[email protected]>

While I appreciate the usefulness of the idea, I do have some issues with both implementations - Shaohua's currently in mmotm and next, and Konstantin's apparently overlooked.

Shaohua, things I don't care for in your patch,
but none of them thoroughly convincing killers:

1. As Konstantin mentioned (in other words), it dignifies the illusion that swap is somehow structured by vmas, rather than being a global pool allocated by accident of when pages fall to the bottom of lrus.

2. Following on from that, it's unable to extend its optimization to randomly accessed tmpfs files or shmem areas (and I don't want that horrid pseudo-vma stuff in shmem.c to be extended in any way to deal with this - I'd have replaced it years ago by alloc_page_mpol() if I had understood the since-acknowledged-broken mempolicy lifetimes).

3. Although putting swapra_miss into struct anon_vma was a neat memory- saving idea from Konstantin, anon_vmas are otherwise pretty much self- referential, never before holding any control information themselves:
I hesitate to extend them in this way.

4. I have not actually performed the test to prove it (tell me if I'm plain wrong), but experience with trying to modify it tells me that if your vma (worse, your anon_vma) is sometimes used for sequential access and sometimes for random (or part of it for sequential and part of it for random), then a burst of randomness will switch readahead off it forever.

Konstantin, given that, I wanted to speak up for your version. I admire the way you have confined it to swap_state.c (and without relying upon the FAULT_FLAG_TRIED patch), and make neat use of PageReadahead and lookup_swap_cache().

But when I compared it against vanilla or Shaohua's patch, okay it's comparable (a few percent slower?) than Shaohua's on random, and works on shmem where his fails - but it was 50% slower on sequential access (when testing on this laptop with Intel SSD: not quite the same as in the tests below, which I left your patch out of).

I thought that's probably due to some off-by-one or other trivial bug in the patch; but when I looked to correct it, I found that I just don't understand what your heuristics are up to, the +1s and -1s and +10s and -10s. Maybe it's an off-by-ten, I haven't a clue.

Perhaps, with a trivial bugfix, and comments added, yours will be great. But it drove me to steal some of your ideas, combining with a simple heuristic that even I can understand: patch below.

If I boot with mem=900M (and 1G swap: either on hard disk sda, or on Vertex II SSD sdb), and mmap anonymous 1000M (either MAP_PRIVATE, or MAP_SHARED for a shmem object), and either cycle sequentially round that making 5M touches (spaced a page apart), or make 5M random touches, then here are the times in centisecs that I see (but it's only elapsed that I've been worrying about).

3.6-rc7 swapping to hard disk:

     124 user    6154 system   73921 elapsed -rc7 sda seq
     102 user    8862 system  895392 elapsed -rc7 sda random
     130 user    6628 system   73601 elapsed -rc7 sda shmem seq
     194 user    8610 system 1058375 elapsed -rc7 sda shmem random

3.6-rc7 swapping to SSD:

     116 user    5898 system   24634 elapsed -rc7 sdb seq
      96 user    8166 system   43014 elapsed -rc7 sdb random
     110 user    6410 system   24959 elapsed -rc7 sdb shmem seq
     208 user    8024 system   45349 elapsed -rc7 sdb shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), HDD:

     116 user    6258 system   76210 elapsed shli sda seq
      80 user    7716 system  831243 elapsed shli sda random
     128 user    6640 system   73176 elapsed shli sda shmem seq
     212 user    8522 system 1053486 elapsed shli sda shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), SSD:

     126 user    5734 system   24198 elapsed shli sdb seq
      90 user    7356 system   26146 elapsed shli sdb random
     128 user    6396 system   24932 elapsed shli sdb shmem seq
     192 user    8006 system   45215 elapsed shli sdb shmem random

3.6-rc7 + my patch, swapping to hard disk:

     126 user    6252 system   75611 elapsed hugh sda seq
      70 user    8310 system  871569 elapsed hugh sda random
     130 user    6790 system   73855 elapsed hugh sda shmem seq
     148 user    7734 system  827935 elapsed hugh sda shmem random

3.6-rc7 + my patch, swapping to SSD:

     116 user    5996 system   24673 elapsed hugh sdb seq
      76 user    7568 system   28075 elapsed hugh sdb random
     132 user    6468 system   25052 elapsed hugh sdb shmem seq
     166 user    7220 system   28249 elapsed hugh sdb shmem random

Mine does look slightly slower than Shaohua's there (except, of course, on the shmem random): maybe it's just noise, maybe I have some edge condition to improve, don't know yet.

These tests are, of course, at the single process extreme; I've also tried my heavy swapping loads, but have not yet discerned a clear trend on all machines from those.

Shaohua, Konstantin, do you have any time to try my patch against whatever loads you were testing with, to see if it's a contender?

Thanks,
Hugh

  include/linux/page-flags.h |    4 +-
  mm/swap_state.c            |   51 ++++++++++++++++++++++++++++++++---
  2 files changed, 50 insertions(+), 5 deletions(-)

include/linux/page-flags.h 2012-09-28 22:02:00.008166986 -0700 renamed from include/linux/page-flags.h 2012-08-03 08:31:26.904842267 -0700 +2 -2

@@ -228,9 +228,9 @@ PAGEFLAG(OwnerPriv1, owner_priv_1) TESTC
  TESTPAGEFLAG(Writeback, writeback) TESTSCFLAG(Writeback, writeback)
  PAGEFLAG(MappedToDisk, mappedtodisk)
 
-/* PG_readahead is only used for file reads; PG_reclaim is only for writes */
+/* PG_readahead is only used for reads; PG_reclaim is only for writes */
  PAGEFLAG(Reclaim, reclaim) TESTCLEARFLAG(Reclaim, reclaim)
-PAGEFLAG(Readahead, reclaim)           /* Reminder to do async read-ahead */
+PAGEFLAG(Readahead, reclaim) TESTCLEARFLAG(Readahead, reclaim)
 
  #ifdef CONFIG_HIGHMEM
  /*

mm/swap_state.c 2012-09-28 23:32:59.752577966 -0700 renamed from mm/swap_state.c 2012-08-03 08:31:27.076842271 -0700 +46 -3

@@ -53,6 +53,8 @@ static struct {
         unsigned long find_total;
  } swap_cache_info;
 
+static atomic_t swapra_hits = ATOMIC_INIT(0);
+
  void show_swap_cache_info(void)
  {
         printk("%lu pages in swap cache\n", total_swapcache_pages);

@@ -265,8 +267,11 @@ struct page * lookup_swap_cache(swp_entr
 
         page = find_get_page(&swapper_space, entry.val);
 
-       if (page)
+       if (page) {
                 INC_CACHE_INFO(find_success);
+               if (TestClearPageReadahead(page))
+                       atomic_inc(&swapra_hits);
+       }
 
         INC_CACHE_INFO(find_total);
         return page;

@@ -351,6 +356,41 @@ struct page *read_swap_cache_async(swp_e
         return found_page;
  }
 
+unsigned long swapin_nr_pages(unsigned long offset)
+{
+       static unsigned long prev_offset;
+       static unsigned int swapin_pages = 8;
+       unsigned int used, half, pages, max_pages;
+
+       used = atomic_xchg(&swapra_hits, 0) + 1;
+       pages = ACCESS_ONCE(swapin_pages);
+       half = pages>>  1;
+
+       if (!half) {
+               /*
+                * We can have no readahead hits to judge by: but must not get
+                * stuck here forever, so check for an adjacent offset instead
+                * (and don't even bother to check if swap type is the same).
+                */
+               if (offset == prev_offset + 1 || offset == prev_offset - 1)
+                       pages<<= 1;
+               prev_offset = offset;
+       } else if (used<  half) {
+               /* Less than half were used?  Then halve the window size */
+               pages = half;
+       } else if (used>  half) {
+               /* More than half were used?  Then double the window size */
+               pages<<= 1;
+       }
+
+       max_pages = 1<<  ACCESS_ONCE(page_cluster);
+       if (pages>  max_pages)
+               pages = max_pages;
+       if (ACCESS_ONCE(swapin_pages) != pages)
+               swapin_pages = pages;
+       return pages;
+}
+
  /**
   * swapin_readahead - swap in pages in hope we need them soon
   * @entry: swap entry of this memory

@@ -374,11 +414,14 @@ struct page *swapin_readahead(swp_entry_
                         struct vm_area_struct *vma, unsigned long addr)
  {
         struct page *page;
-       unsigned long offset = swp_offset(entry);
+       unsigned long entry_offset = swp_offset(entry);
+       unsigned long offset = entry_offset;
         unsigned long start_offset, end_offset;
-       unsigned long mask = (1UL<<  page_cluster) - 1;
+       unsigned long mask;
         struct blk_plug plug;
 
+       mask = swapin_nr_pages(offset) - 1;
+
         /* Read a page_cluster sized and aligned cluster around offset. */
         start_offset = offset&  ~mask;
         end_offset = offset | mask;

Quoted 40 lines · Hugh Dickins

If I boot with mem=900M (and 1G swap: either on hard disk sda, or on Vertex II SSD sdb), and mmap anonymous 1000M (either MAP_PRIVATE, or MAP_SHARED for a shmem object), and either cycle sequentially round that making 5M touches (spaced a page apart), or make 5M random touches, then here are the times in centisecs that I see (but it's only elapsed that I've been worrying about).

3.6-rc7 swapping to hard disk:

     124 user    6154 system   73921 elapsed -rc7 sda seq
     102 user    8862 system  895392 elapsed -rc7 sda random
     130 user    6628 system   73601 elapsed -rc7 sda shmem seq
     194 user    8610 system 1058375 elapsed -rc7 sda shmem random

3.6-rc7 swapping to SSD:

     116 user    5898 system   24634 elapsed -rc7 sdb seq
      96 user    8166 system   43014 elapsed -rc7 sdb random
     110 user    6410 system   24959 elapsed -rc7 sdb shmem seq
     208 user    8024 system   45349 elapsed -rc7 sdb shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), HDD:

     116 user    6258 system   76210 elapsed shli sda seq
      80 user    7716 system  831243 elapsed shli sda random
     128 user    6640 system   73176 elapsed shli sda shmem seq
     212 user    8522 system 1053486 elapsed shli sda shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), SSD:

     126 user    5734 system   24198 elapsed shli sdb seq
      90 user    7356 system   26146 elapsed shli sdb random
     128 user    6396 system   24932 elapsed shli sdb shmem seq
     192 user    8006 system   45215 elapsed shli sdb shmem random

3.6-rc7 + my patch, swapping to hard disk:

     126 user    6252 system   75611 elapsed hugh sda seq
      70 user    8310 system  871569 elapsed hugh sda random
     130 user    6790 system   73855 elapsed hugh sda shmem seq
     148 user    7734 system  827935 elapsed hugh sda shmem random

Quoted 6 lines

3.6-rc7 + my patch, swapping to SSD:

     116 user    5996 system   24673 elapsed hugh sdb seq
      76 user    7568 system   28075 elapsed hugh sdb random
     132 user    6468 system   25052 elapsed hugh sdb shmem seq
     166 user    7220 system   28249 elapsed hugh sdb shmem random

Hmm, It would be nice to gather numbers without swapin readahead at all, just to see the the worst possible case for sequential read and the best for random.

I'll run some tests too, especially I want to see how it works for less synthetic workloads.

Quoted 48 lines · Konstantin Khlebnikov

Quoted 40 lines · Hugh Dickins

If I boot with mem=900M (and 1G swap: either on hard disk sda, or on Vertex II SSD sdb), and mmap anonymous 1000M (either MAP_PRIVATE, or MAP_SHARED for a shmem object), and either cycle sequentially round that making 5M touches (spaced a page apart), or make 5M random touches, then here are the times in centisecs that I see (but it's only elapsed that I've been worrying about).

3.6-rc7 swapping to hard disk:

      124 user    6154 system   73921 elapsed -rc7 sda seq
      102 user    8862 system  895392 elapsed -rc7 sda random
      130 user    6628 system   73601 elapsed -rc7 sda shmem seq
      194 user    8610 system 1058375 elapsed -rc7 sda shmem random

3.6-rc7 swapping to SSD:

      116 user    5898 system   24634 elapsed -rc7 sdb seq
       96 user    8166 system   43014 elapsed -rc7 sdb random
      110 user    6410 system   24959 elapsed -rc7 sdb shmem seq
      208 user    8024 system   45349 elapsed -rc7 sdb shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), HDD:

      116 user    6258 system   76210 elapsed shli sda seq
       80 user    7716 system  831243 elapsed shli sda random
      128 user    6640 system   73176 elapsed shli sda shmem seq
      212 user    8522 system 1053486 elapsed shli sda shmem random

3.6-rc7 + Shaohua's patch (and FAULT_FLAG_RETRY check in do_swap_page), SSD:

      126 user    5734 system   24198 elapsed shli sdb seq
       90 user    7356 system   26146 elapsed shli sdb random
      128 user    6396 system   24932 elapsed shli sdb shmem seq
      192 user    8006 system   45215 elapsed shli sdb shmem random

3.6-rc7 + my patch, swapping to hard disk:

      126 user    6252 system   75611 elapsed hugh sda seq
       70 user    8310 system  871569 elapsed hugh sda random
      130 user    6790 system   73855 elapsed hugh sda shmem seq
      148 user    7734 system  827935 elapsed hugh sda shmem random

Quoted 6 lines

3.6-rc7 + my patch, swapping to SSD:

      116 user    5996 system   24673 elapsed hugh sdb seq
       76 user    7568 system   28075 elapsed hugh sdb random
      132 user    6468 system   25052 elapsed hugh sdb shmem seq
      166 user    7220 system   28249 elapsed hugh sdb shmem random

Quoted 3 lines

Hmm, It would be nice to gather numbers without swapin readahead at all, just to see the the worst possible case for sequential read and the best for random.

Right, and also interesting to see what happens if we raise page_cluster (more of an option than it was, with your or my patch scaling it down). Run on the same machine under the same conditions:

3.6-rc7 + my patch, swapping to hard disk with page_cluster 0 (no readahead):

     136 user   34038 system  121542 elapsed hugh cluster0 sda seq
     102 user    7928 system  841680 elapsed hugh cluster0 sda random
     130 user   34770 system  118322 elapsed hugh cluster0 sda shmem seq
     160 user    7362 system  756489 elapsed hugh cluster0 sda shmem random

3.6-rc7 + my patch, swapping to SSD with page_cluster 0 (no readahead):

     138 user   32230 system   70018 elapsed hugh cluster0 sdb seq
      88 user    7296 system   25901 elapsed hugh cluster0 sdb random
     154 user   33150 system   69678 elapsed hugh cluster0 sdb shmem seq
     166 user    6936 system   24332 elapsed hugh cluster0 sdb shmem random

3.6-rc7 + my patch, swapping to hard disk with page_cluster 4 (default + 1):

     144 user    4262 system   77950 elapsed hugh cluster4 sda seq
      74 user    8268 system  863871 elapsed hugh cluster4 sda random
     140 user    4880 system   73534 elapsed hugh cluster4 sda shmem seq
     160 user    7788 system  834804 elapsed hugh cluster4 sda shmem random

3.6-rc7 + my patch, swapping to SSD with page_cluster 4 (default + 1):

     124 user    4242 system   21125 elapsed hugh cluster4 sdb seq
      72 user    7680 system   28686 elapsed hugh cluster4 sdb random
     122 user    4622 system   21387 elapsed hugh cluster4 sdb shmem seq
     172 user    7238 system   28226 elapsed hugh cluster4 sdb shmem random

I was at first surprised to see random significantly faster than sequential on SSD with readahead off, thinking they ought to come out the same. But no, that's a warning on the limitations of the test: with an mmap of 1000M on a machine with mem=900M, the page-by-page sequential is never going to rehit cache, whereas the random has a good chance of finding in memory.

Which I presume also accounts for the lower user times throughout for random - but then why not the same for shmem random?

I did start off measuring on the laptop with SSD, mmap 1000M mem=500M; but once I transferred to the desktop, I rediscovered just how slow swapping to hard disk can be, couldn't wait days, so made mem=900M.

Quoted 2 lines

I'll run some tests too, especially I want to see how it works for less synthetic workloads.

Thank you, that would be valuable. I expect there to be certain midway tests on which Shaohao's patch would show up as significantly faster, where his per-vma approach would beat the global approach; then the global to improve with growing contention between processes. But I didn't devise any such test, and hoped Shaohua might have one.

Hugh

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Numbers from your tests formatted into table for better readability

HDD Vanilla Shaohua RA=3 RA=0 RA=4
SEQ, ANON 73921 76210 75611 121542 77950
SEQ, SHMEM 73601 73176 73855 118322 73534
RND, ANON 895392 831243 871569 841680 863871
RND, SHMEM 1058375 1053486 827935 756489 834804

SDD Vanilla Shaohua RA=3 RA=0 RA=4
SEQ, ANON 24634 24198 24673 70018 21125
SEQ, SHMEM 24959 24932 25052 69678 21387
RND, ANON 43014 26146 28075 25901 28686
RND, SHMEM 45349 45215 28249 24332 28226

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Quoted 16 lines · Konstantin Khlebnikov

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

Quoted 4 lines

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Thanks for doing this, Konstantin, but I'm stuck for anything much to say! Shaohua and I are both about 4.5% bad for this particular test, but I'm more consistently bad - hurrah!

I suspect (not a convincing argument) that if the test were just slightly different (a little more or a little less memory, SSD instead of hard disk, diskcache instead of tmpfs), then it would come out differently.

Did you draw any conclusions from the numbers you found?

I haven't done any more on this in the last few days, except to verify that once an anon_vma is judged random with Shaohua's, then it appears to be condemned to no-readahead ever after.

That's probably something that a hack like I had in mine would fix, but that addition might change its balance further (and increase vma or anon_vma size) - not tried yet.

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Hugh

Quoted 14 lines

Numbers from your tests formatted into table for better readability

HDD Vanilla Shaohua RA=3 RA=0 RA=4
SEQ, ANON 73921 76210 75611 121542 77950
SEQ, SHMEM 73601 73176 73855 118322 73534
RND, ANON 895392 831243 871569 841680 863871
RND, SHMEM 1058375 1053486 827935 756489 834804

SDD Vanilla Shaohua RA=3 RA=0 RA=4
SEQ, ANON 24634 24198 24673 70018 21125
SEQ, SHMEM 24959 24932 25052 69678 21387
RND, ANON 43014 26146 28075 25901 28686
RND, SHMEM 45349 45215 28249 24332 28226

Quoted 16 lines · Konstantin Khlebnikov

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

Quoted 4 lines

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Thanks for doing this, Konstantin, but I'm stuck for anything much to say! Shaohua and I are both about 4.5% bad for this particular test, but I'm more consistently bad - hurrah!

I suspect (not a convincing argument) that if the test were just slightly different (a little more or a little less memory, SSD instead of hard disk, diskcache instead of tmpfs), then it would come out differently.

Did you draw any conclusions from the numbers you found?

I haven't done any more on this in the last few days, except to verify that once an anon_vma is judged random with Shaohua's, then it appears to be condemned to no-readahead ever after.

That's probably something that a hack like I had in mine would fix, but that addition might change its balance further (and increase vma or anon_vma size) - not tried yet.

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Quoted 37 lines · Hugh Dickins

Quoted 16 lines · Konstantin Khlebnikov

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

Quoted 4 lines

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Thanks for doing this, Konstantin, but I'm stuck for anything much to say! Shaohua and I are both about 4.5% bad for this particular test, but I'm more consistently bad - hurrah!

I suspect (not a convincing argument) that if the test were just slightly different (a little more or a little less memory, SSD instead of hard disk, diskcache instead of tmpfs), then it would come out differently.

Did you draw any conclusions from the numbers you found?

I haven't done any more on this in the last few days, except to verify that once an anon_vma is judged random with Shaohua's, then it appears to be condemned to no-readahead ever after.

Quoted 7 lines

That's probably something that a hack like I had in mine would fix, but that addition might change its balance further (and increase vma or anon_vma size) - not tried yet.

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Ok, I tested Hugh's patch. My test is a multithread random write workload. With Hugh's patch, 49:28.06elapsed
With mine, 43:23.39elapsed
There is 12% more time used with Hugh's patch.

In the stable state of this workload, SI:SO ratio should be roughly 1:1. With Hugh's patch, it's around 1.6:1, there is still unnecessary swapin.

I also tried a workload with seqential/random write mixed, Hugh's patch is 10% bad too.

Quoted 51 lines · Shaohua Li

Quoted 37 lines · Hugh Dickins

Quoted 16 lines · Konstantin Khlebnikov

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

Quoted 4 lines

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Thanks for doing this, Konstantin, but I'm stuck for anything much to say! Shaohua and I are both about 4.5% bad for this particular test, but I'm more consistently bad - hurrah!

I suspect (not a convincing argument) that if the test were just slightly different (a little more or a little less memory, SSD instead of hard disk, diskcache instead of tmpfs), then it would come out differently.

Did you draw any conclusions from the numbers you found?

I haven't done any more on this in the last few days, except to verify that once an anon_vma is judged random with Shaohua's, then it appears to be condemned to no-readahead ever after.

Quoted 7 lines

That's probably something that a hack like I had in mine would fix, but that addition might change its balance further (and increase vma or anon_vma size) - not tried yet.

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Ok, I tested Hugh's patch. My test is a multithread random write workload. With Hugh's patch, 49:28.06elapsed
With mine, 43:23.39elapsed
There is 12% more time used with Hugh's patch.

Quoted 5 lines

In the stable state of this workload, SI:SO ratio should be roughly 1:1. With Hugh's patch, it's around 1.6:1, there is still unnecessary swapin.

I also tried a workload with seqential/random write mixed, Hugh's patch is 10% bad too.

With below change, the si/so ratio is back to around 1:1 in my workload. Guess the run time of my test will be reduced too, though I didn't test yet.

I'm wondering how could a global counter based method detect readahead correctly. For example, if there are a sequential access thread and a random access thread, doesn't this method always make wrong decision?

Quoted 58 lines · Shaohua Li

Quoted 56 lines · Shaohua Li

Quoted 37 lines · Hugh Dickins

Quoted 16 lines · Konstantin Khlebnikov

Here results of my test. Workload isn't very realistic, but at least it
threaded: compiling linux-3.6 with defconfig in 16 threads on tmpfs, 512mb ram, dualcore cpu, ordinary hard disk. (test script in attachment)

average results for ten runs:

		RA=3	RA=0	RA=1	RA=2	RA=4	Hugh	Shaohua

real time 500 542 528 519 500 523 522
user time 738 737 735 737 739 737 739
sys time 93 93 91 92 96 92 93
pgmajfault 62918 110533 92454 78221 54342 86601 77229
pgpgin 2070372 795228 1034046 1471010 3177192 1154532 1599388
pgpgout 2597278 2022037 2110020 2350380 2802670 2286671 2526570
pswpin 462747 138873 202148 310969 739431 232710 341320
pswpout 646363 502599 524613 584731 697797 568784 628677

Quoted 4 lines

So, last two columns shows mostly equal results: +4.6% and +4.4% in comparison to vanilla kernel with RA=3, but your version shows more stable results (std-error 2.7% against 4.8%) (all this numbers in huge table in attachment)

Thanks for doing this, Konstantin, but I'm stuck for anything much to say! Shaohua and I are both about 4.5% bad for this particular test, but I'm more consistently bad - hurrah!

I suspect (not a convincing argument) that if the test were just slightly different (a little more or a little less memory, SSD instead of hard disk, diskcache instead of tmpfs), then it would come out differently.

Did you draw any conclusions from the numbers you found?

I haven't done any more on this in the last few days, except to verify that once an anon_vma is judged random with Shaohua's, then it appears to be condemned to no-readahead ever after.

Quoted 7 lines

That's probably something that a hack like I had in mine would fix, but that addition might change its balance further (and increase vma or anon_vma size) - not tried yet.

All I want to do right now, is suggest to Andrew that he hold Shaohua's patch back from 3.7 for the moment: I'll send a response to Sep 7th's mm-commits mail to suggest that - but no great disaster if he ignores me.

Ok, I tested Hugh's patch. My test is a multithread random write workload. With Hugh's patch, 49:28.06elapsed
With mine, 43:23.39elapsed
There is 12% more time used with Hugh's patch.

In the stable state of this workload, SI:SO ratio should be roughly 1:1. With Hugh's patch, it's around 1.6:1, there is still unnecessary swapin.

I also tried a workload with seqential/random write mixed, Hugh's patch is 10% bad too.

Review

Quoted 4 lines

With below change, the si/so ratio is back to around 1:1 in my workload. Guess the run time of my test will be reduced too, though I didn't test yet.

(quoted diff) +1 -1

-	used = atomic_xchg(&swapra_hits, 0) + 1;
+	used = atomic_xchg(&swapra_hits, 0);

Thank you for playing and trying that, I haven't found time to revisit it at all. I'll give that adjustment a go at my end. The "+ 1" was for the target page itself; but whatever works best, there's not much science to it.

Quoted 4 lines

I'm wondering how could a global counter based method detect readahead correctly. For example, if there are a sequential access thread and a random access thread, doesn't this method always make wrong decision?

But only in the simplest cases is the sequentiality of placement on swap well correlated with the sequentiality of placement in virtual memory. Once you have a sequential access thread and a random access thread swapping out at the same time, their pages will be interspersed.

I'm pretty sure that if you give it more thought than I am giving it at the moment, you can devise a test case which would go amazingly faster by your per-vma method than by keeping just this global state.

But I doubt such a test case would be so realistic as to deserve that extra sophistication. I do prefer to keep the heuristic as stupid and unpretentious as possible.

I have no strong point against the global state method. But I'd agree making the heuristic simple is preferred currently. I'm happy about the patch if the '+1' is removed.

Quoted 3 lines · Shaohua Li

I have no strong point against the global state method. But I'd agree making the heuristic simple is preferred currently. I'm happy about the patch if the '+1' is removed.

Without the +1, how will you figure out when to re-enable readahead?

Quoted 7 lines · Rik van Riel

Quoted 3 lines · Shaohua Li

I have no strong point against the global state method. But I'd agree making the heuristic simple is preferred currently. I'm happy about the patch if the '+1' is removed.

Without the +1, how will you figure out when to re-enable readahead?

Below code in swapin_nr_pages can recover it.

(quoted diff) +2 -0

+               if (offset == prev_offset + 1 || offset == prev_offset - 1)
+                       pages <<= 1;

Not perfect, but should work in some sort. This reminds me to think if pagereadahead flag is really required, hit in swap cache is a more reliable way to count readahead hit, and as Hugh mentioned, swap isn't vma bound.

Quoted 13 lines · Shaohua Li

Quoted 7 lines · Rik van Riel

Quoted 3 lines · Shaohua Li

I have no strong point against the global state method. But I'd agree making the heuristic simple is preferred currently. I'm happy about the patch if the '+1' is removed.

Without the +1, how will you figure out when to re-enable readahead?

Below code in swapin_nr_pages can recover it.

(quoted diff) +2 -0

+               if (offset == prev_offset + 1 || offset == prev_offset - 1)
+                       pages <<= 1;

Quoted 3 lines

Not perfect, but should work in some sort. This reminds me to think if pagereadahead flag is really required, hit in swap cache is a more reliable way to count readahead hit, and as Hugh mentioned, swap isn't vma bound.

Hugh,
ping! Any chance you can check this again?

Quoted 18 lines · Shaohua Li

Quoted 16 lines · Shaohua Li

Quoted 7 lines · Rik van Riel

Quoted 3 lines · Shaohua Li

I have no strong point against the global state method. But I'd agree making the heuristic simple is preferred currently. I'm happy about the patch if the '+1' is removed.

Without the +1, how will you figure out when to re-enable readahead?

Below code in swapin_nr_pages can recover it.

(quoted diff) +2 -0

+               if (offset == prev_offset + 1 || offset == prev_offset - 1)
+                       pages <<= 1;

Not perfect, but should work in some sort. This reminds me to think if pagereadahead flag is really required, hit in swap cache is a more reliable way to count readahead hit, and as Hugh mentioned, swap isn't vma bound.

Quoted 2 lines

Hugh,
ping! Any chance you can check this again?

I apologize, Shaohua, my slowness must be very frustrating for you, as it is for me too.

Thank you for pointing out how my first patch was reading two pages instead of one in the random case, explaining its disappointing performance there: odd how blind I was to that, despite taking stats.

I did experiment with removing the "+ 1" as you did, it worked well in the random SSD case, but degraded performance in (all? I forget) the other cases.

I failed to rescue the "algorithm" in that patch, and changed it a week ago for an even simpler one, that has worked well for me so far. When I sent you a quick private ack to your ping, I was puzzled by its "too good to be true" initial test results: once I looked into those, found my rearrangement of the test script had left out a swapoff, so the supposed harddisk tests were actually swapping to SSD.

I've finally got around to assembling the results and writing up some description, starting off from yours. I think I've gone as far as I can with this, and don't want to hold you up with further
delays: would it be okay if I simply hand this patch over to you now, to test and expand upon and add your Sign-off and send in to akpm to replace your original in mmotm - IF you are satisfied with it?

Quoted 7 lines · Minchan Kim

Don't we need initialization?

mm/rmap.c +0 -0

index 0f3b7cd..c0f3221 100644

mm/rmap.c static void anon_vma_ctor(void *data) · line 423

Quoted 8 lines

mm/rmap.c +3 -0

@@ -416,6 +416,9 @@ static void anon_vma_ctor(void *data)
 
        mutex_init(&anon_vma->mutex);
        atomic_set(&anon_vma->refcount, 0);
+#ifdef CONFIG_SWAP
+       atomic_set(&anon_vma->swapra_miss, 0);
+#endif
        INIT_LIST_HEAD(&anon_vma->head);
 }

Sorry about this silly problem. I'm wondering why I didn't notice it, maybe because only tested random swap after move swapra_miss to anon_vma.

Subject: swap: add a simple random read swapin detection

The swapin readahead does a blind readahead regardless if the swapin is sequential. This is ok for harddisk and random read, because read big size has no penality in harddisk, and if the readahead pages are garbage, they can be reclaimed fastly. But for SSD, big size read is more expensive than small size read. If readahead pages are garbage, such readahead only has overhead.

This patch addes a simple random read detection like what file mmap readahead does. If random read is detected, swapin readahead will be skipped. This improves a lot for a swap workload with random IO in a fast SSD.

I run anonymous mmap write micro benchmark, which will triger swapin/swapout.
runtime changes with path
randwrite harddisk -38.7%
seqwrite harddisk -1.1%
randwrite SSD -46.9%
seqwrite SSD +0.3%

For both harddisk and SSD, the randwrite swap workload run time is reduced significant. sequential write swap workload hasn't chanage.

Interesting is the randwrite harddisk test is improved too. This might be because swapin readahead need allocate extra memory, which further tights memory pressure, so more swapout/swapin.

This patch depends on readahead-fault-retry-breaks-mmap-file-read-random-detection.patch

V2->V3:
move swapra_miss to 'struct anon_vma' as suggested by Konstantin.

V1->V2:
1. Move the swap readahead accounting to separate functions as suggested by Riel.
2. Enable the logic only with CONFIG_SWAP enabled as suggested by Minchan.

Signed-off-by Shaohua Li <[email protected]>

Acked-by Rik van Riel <[email protected]>