[PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

Patch uses two bits to detect if page is scanned, one bit for odd cycle
and other for even cycle. This adds one more bit in page flags and
overloads existing bit (PG_owner_priv_1).
Changes are based of 3.4.79 kernel, since I have used that for verification.
Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
Suggestion(s) are welcome for alternative solution in order to avoid one more
bit in page flags.

Pradeep Sawlani (1):
  ksm: check and skip page, if it is already scanned

 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

-- 
1.7.9.5

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

Patch uses two bits to detect if page is scanned, one bit for odd cycle
and other for even cycle. This adds one more bit in page flags and
overloads existing bit (PG_owner_priv_1).
Changes are based of 3.4.79 kernel, since I have used that for verification.
Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
Suggestion(s) are welcome for alternative solution in order to avoid one more
bit in page flags.

Pradeep Sawlani (1):
  ksm: check and skip page, if it is already scanned

 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

-- 
1.7.9.5

[PATCH RFC 1/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

On system like Android where most of the process are forked
from parent w/o execve, KSM can scan same page multiple times
in one scan cycle. There is no advantage in scanning same page
multiple times for merging. During testing with Android, it was
observed around 60% pages are skipped for each scan cycle.

Change-Id: I0cf01802f0b4d61fcab92558beb9e1c660dc9a77
Link: http://lkml.kernel.org/r/CAMrOTPgBtANS_ryRjan0-dTL97U7eRvtf3dCsss=Kn+Uk89fuA@mail.gmail.com
Signed-off-by: Pradeep Sawlani <sawlani@amazon.com>
---
 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
index 4dabf0f..af4462f 100644
--- a/include/linux/page-flags.h
+++ b/include/linux/page-flags.h
@@ -108,8 +108,15 @@ enum pageflags {
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
 	PG_compound_lock,
 #endif
+#ifdef CONFIG_KSM_CHECK_PAGE
+	PG_ksm_scan0,		/* page has been scanned by even KSM cycle */
+#endif
 	__NR_PAGEFLAGS,
 
+#ifdef CONFIG_KSM_CHECK_PAGE
+	/* page has been scanned by odd KSM cycle */
+	PG_ksm_scan1 = PG_owner_priv_1,
+#endif
 	/* Filesystems */
 	PG_checked = PG_owner_priv_1,
 
@@ -209,6 +216,10 @@ PAGEFLAG(Reserved, reserved) __CLEARPAGEFLAG(Reserved, reserved)
 PAGEFLAG(SwapBacked, swapbacked) __CLEARPAGEFLAG(SwapBacked, swapbacked)
 
 __PAGEFLAG(SlobFree, slob_free)
+#ifdef CONFIG_KSM_CHECK_PAGE
+CLEARPAGEFLAG(KsmScan0, ksm_scan0) TESTSETFLAG(KsmScan0, ksm_scan0)
+CLEARPAGEFLAG(KsmScan1, ksm_scan1) TESTSETFLAG(KsmScan1, ksm_scan1)
+#endif
 
 /*
  * Private page markings that may be used by the filesystem that owns the page
diff --git a/mm/Kconfig b/mm/Kconfig
index 3922002..984f67c 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -246,6 +246,16 @@ config KSM
 	  until a program has madvised that an area is MADV_MERGEABLE, and
 	  root has set /sys/kernel/mm/ksm/run to 1 (if CONFIG_SYSFS is set).
 
+config KSM_CHECK_PAGE
+	bool "Check page before scanning"
+	depends on KSM
+	default n
+	help
+	  If enabled, this will check and skip if page is already scanned in
+	  same KSM scan cycle.
+	  This is useful in situation where you have parent and
+	  child process marking same area for KSM scanning.
+
 config DEFAULT_MMAP_MIN_ADDR
         int "Low address space to protect from user allocation"
 	depends on MMU
diff --git a/mm/ksm.c b/mm/ksm.c
index 47c8853..2edb9cb 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -558,7 +558,9 @@ static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
 		 * than left over from before.
 		 */
 		age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
+#ifndef CONFIG_KSM_CHECK_PAGE
 		BUG_ON(age > 1);
+#endif
 		if (!age)
 			rb_erase(&rmap_item->node, &root_unstable_tree);
 
@@ -1407,6 +1409,31 @@ next_mm:
 	return NULL;
 }
 
+static inline int is_page_scanned(struct page *page)
+{
+#ifdef CONFIG_KSM_CHECK_PAGE
+	/* page is already marked as ksm, so this will be simple merge */
+	if (PageKsm(page))
+		return 0;
+
+	if (ksm_scan.seqnr & 0x1) {
+		/* odd cycle */
+		/* clear even cycle bit */
+		ClearPageKsmScan0(page);
+		/* get old value and mark it scanned */
+		return TestSetPageKsmScan1(page);
+	} else {
+		/* even cycle */
+		/* clear odd cycle bit */
+		ClearPageKsmScan1(page);
+		/* get old value and mark it scanned */
+		return TestSetPageKsmScan0(page);
+	}
+#else
+	return 0;
+#endif
+}
+
 /**
  * ksm_do_scan  - the ksm scanner main worker function.
  * @scan_npages - number of pages we want to scan before we return.
@@ -1421,8 +1448,10 @@ static void ksm_do_scan(unsigned int scan_npages)
 		rmap_item = scan_get_next_rmap_item(&page);
 		if (!rmap_item)
 			return;
-		if (!PageKsm(page) || !in_stable_tree(rmap_item))
-			cmp_and_merge_page(page, rmap_item);
+		if (!PageKsm(page) || !in_stable_tree(rmap_item)) {
+			if (!is_page_scanned(page))
+				cmp_and_merge_page(page, rmap_item);
+		}
 		put_page(page);
 	}
 }
-- 
1.7.9.5

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH RFC 1/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

On system like Android where most of the process are forked
from parent w/o execve, KSM can scan same page multiple times
in one scan cycle. There is no advantage in scanning same page
multiple times for merging. During testing with Android, it was
observed around 60% pages are skipped for each scan cycle.

Change-Id: I0cf01802f0b4d61fcab92558beb9e1c660dc9a77
Link: http://lkml.kernel.org/r/CAMrOTPgBtANS_ryRjan0-dTL97U7eRvtf3dCsss=Kn+Uk89fuA@mail.gmail.com
Signed-off-by: Pradeep Sawlani <sawlani@amazon.com>
---
 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
index 4dabf0f..af4462f 100644
--- a/include/linux/page-flags.h
+++ b/include/linux/page-flags.h
@@ -108,8 +108,15 @@ enum pageflags {
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
 	PG_compound_lock,
 #endif
+#ifdef CONFIG_KSM_CHECK_PAGE
+	PG_ksm_scan0,		/* page has been scanned by even KSM cycle */
+#endif
 	__NR_PAGEFLAGS,
 
+#ifdef CONFIG_KSM_CHECK_PAGE
+	/* page has been scanned by odd KSM cycle */
+	PG_ksm_scan1 = PG_owner_priv_1,
+#endif
 	/* Filesystems */
 	PG_checked = PG_owner_priv_1,
 
@@ -209,6 +216,10 @@ PAGEFLAG(Reserved, reserved) __CLEARPAGEFLAG(Reserved, reserved)
 PAGEFLAG(SwapBacked, swapbacked) __CLEARPAGEFLAG(SwapBacked, swapbacked)
 
 __PAGEFLAG(SlobFree, slob_free)
+#ifdef CONFIG_KSM_CHECK_PAGE
+CLEARPAGEFLAG(KsmScan0, ksm_scan0) TESTSETFLAG(KsmScan0, ksm_scan0)
+CLEARPAGEFLAG(KsmScan1, ksm_scan1) TESTSETFLAG(KsmScan1, ksm_scan1)
+#endif
 
 /*
  * Private page markings that may be used by the filesystem that owns the page
diff --git a/mm/Kconfig b/mm/Kconfig
index 3922002..984f67c 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -246,6 +246,16 @@ config KSM
 	  until a program has madvised that an area is MADV_MERGEABLE, and
 	  root has set /sys/kernel/mm/ksm/run to 1 (if CONFIG_SYSFS is set).
 
+config KSM_CHECK_PAGE
+	bool "Check page before scanning"
+	depends on KSM
+	default n
+	help
+	  If enabled, this will check and skip if page is already scanned in
+	  same KSM scan cycle.
+	  This is useful in situation where you have parent and
+	  child process marking same area for KSM scanning.
+
 config DEFAULT_MMAP_MIN_ADDR
         int "Low address space to protect from user allocation"
 	depends on MMU
diff --git a/mm/ksm.c b/mm/ksm.c
index 47c8853..2edb9cb 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -558,7 +558,9 @@ static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
 		 * than left over from before.
 		 */
 		age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
+#ifndef CONFIG_KSM_CHECK_PAGE
 		BUG_ON(age > 1);
+#endif
 		if (!age)
 			rb_erase(&rmap_item->node, &root_unstable_tree);
 
@@ -1407,6 +1409,31 @@ next_mm:
 	return NULL;
 }
 
+static inline int is_page_scanned(struct page *page)
+{
+#ifdef CONFIG_KSM_CHECK_PAGE
+	/* page is already marked as ksm, so this will be simple merge */
+	if (PageKsm(page))
+		return 0;
+
+	if (ksm_scan.seqnr & 0x1) {
+		/* odd cycle */
+		/* clear even cycle bit */
+		ClearPageKsmScan0(page);
+		/* get old value and mark it scanned */
+		return TestSetPageKsmScan1(page);
+	} else {
+		/* even cycle */
+		/* clear odd cycle bit */
+		ClearPageKsmScan1(page);
+		/* get old value and mark it scanned */
+		return TestSetPageKsmScan0(page);
+	}
+#else
+	return 0;
+#endif
+}
+
 /**
  * ksm_do_scan  - the ksm scanner main worker function.
  * @scan_npages - number of pages we want to scan before we return.
@@ -1421,8 +1448,10 @@ static void ksm_do_scan(unsigned int scan_npages)
 		rmap_item = scan_get_next_rmap_item(&page);
 		if (!rmap_item)
 			return;
-		if (!PageKsm(page) || !in_stable_tree(rmap_item))
-			cmp_and_merge_page(page, rmap_item);
+		if (!PageKsm(page) || !in_stable_tree(rmap_item)) {
+			if (!is_page_scanned(page))
+				cmp_and_merge_page(page, rmap_item);
+		}
 		put_page(page);
 	}
 }
-- 
1.7.9.5

Re: [PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Dave Hansen]

On 03/03/2014 06:48 PM, Pradeep Sawlani wrote:
> Patch uses two bits to detect if page is scanned, one bit for odd cycle
> and other for even cycle. This adds one more bit in page flags and
> overloads existing bit (PG_owner_priv_1).
> Changes are based of 3.4.79 kernel, since I have used that for verification.
> Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
> Suggestion(s) are welcome for alternative solution in order to avoid one more
> bit in page flags.

Allocate a big bitmap (depends on how many pages you are scanning).
Hash the page's pfn and index in to the bitmap.  If the bit is set,
don't scan the page.  If not set, then set it.  Vary the hash for each
scanning pass to reduce the same collision happening repeatedly.  Clear
the bitmap before each scan.

You'll get plenty of collisions, especially for a small table, but who
cares?

The other option is to bloat anon_vma instead, and only do one scan for
each anon_vma that shares the same root.  That's a bit more invasive though.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Dave Hansen]

On 03/03/2014 06:48 PM, Pradeep Sawlani wrote:
> Patch uses two bits to detect if page is scanned, one bit for odd cycle
> and other for even cycle. This adds one more bit in page flags and
> overloads existing bit (PG_owner_priv_1).
> Changes are based of 3.4.79 kernel, since I have used that for verification.
> Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
> Suggestion(s) are welcome for alternative solution in order to avoid one more
> bit in page flags.

Allocate a big bitmap (depends on how many pages you are scanning).
Hash the page's pfn and index in to the bitmap.  If the bit is set,
don't scan the page.  If not set, then set it.  Vary the hash for each
scanning pass to reduce the same collision happening repeatedly.  Clear
the bitmap before each scan.

You'll get plenty of collisions, especially for a small table, but who
cares?

The other option is to bloat anon_vma instead, and only do one scan for
each anon_vma that shares the same root.  That's a bit more invasive though.

[PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

Patch uses two bits to detect if page is scanned, one bit for odd cycle
and other for even cycle. This adds one more bit in page flags and
overloads existing bit (PG_owner_priv_1).
Changes are based of 3.4.79 kernel, since I have used that for verification.
Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
Suggestion(s) are welcome for alternative solution in order to avoid one more
bit in page flags.

Pradeep Sawlani (1):
  ksm: check and skip page, if it is already scanned

 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

-- 
1.7.9.5

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH RFC 0/1] ksm: check and skip page, if it is already scanned

[Pradeep Sawlani]

From: Pradeep Sawlani <sawlani@amazon.com>

Patch uses two bits to detect if page is scanned, one bit for odd cycle
and other for even cycle. This adds one more bit in page flags and
overloads existing bit (PG_owner_priv_1).
Changes are based of 3.4.79 kernel, since I have used that for verification.
Detail discussion can be found at https://lkml.org/lkml/2014/2/13/624
Suggestion(s) are welcome for alternative solution in order to avoid one more
bit in page flags.

Pradeep Sawlani (1):
  ksm: check and skip page, if it is already scanned

 include/linux/page-flags.h |   11 +++++++++++
 mm/Kconfig                 |   10 ++++++++++
 mm/ksm.c                   |   33 +++++++++++++++++++++++++++++++--
 3 files changed, 52 insertions(+), 2 deletions(-)

-- 
1.7.9.5