[PATCH 0/5] KSM updates v2

[PATCH 0/5] KSM updates v2

[Andrea Arcangeli]

Hello,

This practically the same as the previous submit but without the first
patch which luckily turned out to be a noop. Some commit message have
been improved on the way.

Dropping the first patch would generate rejects on the later patches
so this is a clean submit against v4.3.

The cond_resched() for the rmap walks is not only for KSM but it's
primarily a KSM improvement as KSM generates much heavier rmap walks
than the other rmap mechanisms would, so I'm submitting it in KSM
context.

All patches in this submit have been acked by Hugh already, thanks for
the help!

Andrea Arcangeli (5):
  mm: add cond_resched() to the rmap walks
  ksm: don't fail stable tree lookups if walking over stale stable_nodes
  ksm: use the helper method to do the hlist_empty check
  ksm: use find_mergeable_vma in try_to_merge_with_ksm_page
  ksm: unstable_tree_search_insert error checking cleanup

 mm/ksm.c  | 49 +++++++++++++++++++++++++++++++++++--------------
 mm/rmap.c |  4 ++++
 2 files changed, 39 insertions(+), 14 deletions(-)

--
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 1/5] mm: add cond_resched() to the rmap walks

[Andrea Arcangeli]

The rmap walk must reach every possible mapping of the page, so if a
page is heavily shared (no matter if it's KSM, anon, pagecache) there
will be tons of entries to walk through. All optimizations with
prio_tree, anon_vma chains, interval tree, helps to find the right
virtual mapping faster, but if there are lots of virtual mappings, all
mapping must still be walked through.

The biggest cost is for the IPIs, but regardless of the IPIs, it's
generally safer to keep these cond_resched() in all cases, as even if
we massively reduce the number of IPIs, the number of entries to walk
IPI-less may still be large and no entry can be possibly skipped in
the page migration case.

Acked-by: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
 mm/ksm.c  | 2 ++
 mm/rmap.c | 4 ++++
 2 files changed, 6 insertions(+)

diff --git a/mm/ksm.c b/mm/ksm.c
index 7ee101e..e87dec7 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -1914,9 +1914,11 @@ again:
 		struct anon_vma_chain *vmac;
 		struct vm_area_struct *vma;
 
+		cond_resched();
 		anon_vma_lock_read(anon_vma);
 		anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,
 					       0, ULONG_MAX) {
+			cond_resched();
 			vma = vmac->vma;
 			if (rmap_item->address < vma->vm_start ||
 			    rmap_item->address >= vma->vm_end)
diff --git a/mm/rmap.c b/mm/rmap.c
index f5b5c1f..b949778 100644
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -1607,6 +1607,8 @@ static int rmap_walk_anon(struct page *page, struct rmap_walk_control *rwc)
 		struct vm_area_struct *vma = avc->vma;
 		unsigned long address = vma_address(page, vma);
 
+		cond_resched();
+
 		if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
 			continue;
 
@@ -1656,6 +1658,8 @@ static int rmap_walk_file(struct page *page, struct rmap_walk_control *rwc)
 	vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
 		unsigned long address = vma_address(page, vma);
 
+		cond_resched();
+
 		if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
 			continue;
 

--
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 2/5] ksm: don't fail stable tree lookups if walking over stale stable_nodes

[Andrea Arcangeli]

The stable_nodes can become stale at any time if the underlying pages
gets freed. The stable_node gets collected and removed from the stable
rbtree if that is detected during the rbtree lookups.

Don't fail the lookup if running into stale stable_nodes, just restart
the lookup after collecting the stale stable_nodes. Otherwise the CPU
spent in the preparation stage is wasted and the lookup must be
repeated at the next loop potentially failing a second time in a
second stale stable_node.

If we don't prune aggressively we delay the merging of the unstable
node candidates and at the same time we delay the freeing of the stale
stable_nodes. Keeping stale stable_nodes around wastes memory and it
can't provide any benefit.

Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: Hugh Dickins <hughd@google.com>
---
 mm/ksm.c | 32 +++++++++++++++++++++++++++-----
 1 file changed, 27 insertions(+), 5 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index e87dec7..9f182f9 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -1177,8 +1177,18 @@ again:
 		cond_resched();
 		stable_node = rb_entry(*new, struct stable_node, node);
 		tree_page = get_ksm_page(stable_node, false);
-		if (!tree_page)
-			return NULL;
+		if (!tree_page) {
+			/*
+			 * If we walked over a stale stable_node,
+			 * get_ksm_page() will call rb_erase() and it
+			 * may rebalance the tree from under us. So
+			 * restart the search from scratch. Returning
+			 * NULL would be safe too, but we'd generate
+			 * false negative insertions just because some
+			 * stable_node was stale.
+			 */
+			goto again;
+		}
 
 		ret = memcmp_pages(page, tree_page);
 		put_page(tree_page);
@@ -1254,12 +1264,14 @@ static struct stable_node *stable_tree_insert(struct page *kpage)
 	unsigned long kpfn;
 	struct rb_root *root;
 	struct rb_node **new;
-	struct rb_node *parent = NULL;
+	struct rb_node *parent;
 	struct stable_node *stable_node;
 
 	kpfn = page_to_pfn(kpage);
 	nid = get_kpfn_nid(kpfn);
 	root = root_stable_tree + nid;
+again:
+	parent = NULL;
 	new = &root->rb_node;
 
 	while (*new) {
@@ -1269,8 +1281,18 @@ static struct stable_node *stable_tree_insert(struct page *kpage)
 		cond_resched();
 		stable_node = rb_entry(*new, struct stable_node, node);
 		tree_page = get_ksm_page(stable_node, false);
-		if (!tree_page)
-			return NULL;
+		if (!tree_page) {
+			/*
+			 * If we walked over a stale stable_node,
+			 * get_ksm_page() will call rb_erase() and it
+			 * may rebalance the tree from under us. So
+			 * restart the search from scratch. Returning
+			 * NULL would be safe too, but we'd generate
+			 * false negative insertions just because some
+			 * stable_node was stale.
+			 */
+			goto again;
+		}
 
 		ret = memcmp_pages(kpage, tree_page);
 		put_page(tree_page);

--
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 3/5] ksm: use the helper method to do the hlist_empty check

[Andrea Arcangeli]

This just uses the helper function to cleanup the assumption on the
hlist_node internals.

Acked-by: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
 mm/ksm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 9f182f9..d4ee159 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -625,7 +625,7 @@ static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
 		unlock_page(page);
 		put_page(page);
 
-		if (stable_node->hlist.first)
+		if (!hlist_empty(&stable_node->hlist))
 			ksm_pages_sharing--;
 		else
 			ksm_pages_shared--;

--
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 4/5] ksm: use find_mergeable_vma in try_to_merge_with_ksm_page

[Andrea Arcangeli]

Doing the VM_MERGEABLE check after the page == kpage check won't
provide any meaningful benefit. The !vma->anon_vma check of
find_mergeable_vma is the only superfluous bit in using
find_mergeable_vma because the !PageAnon check of
try_to_merge_one_page() implicitly checks for that, but it still looks
cleaner to share the same find_mergeable_vma().

Acked-by: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
 mm/ksm.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index d4ee159..0183083 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -1021,8 +1021,6 @@ static int try_to_merge_one_page(struct vm_area_struct *vma,
 	if (page == kpage)			/* ksm page forked */
 		return 0;
 
-	if (!(vma->vm_flags & VM_MERGEABLE))
-		goto out;
 	if (PageTransCompound(page) && page_trans_compound_anon_split(page))
 		goto out;
 	BUG_ON(PageTransCompound(page));
@@ -1087,10 +1085,8 @@ static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item,
 	int err = -EFAULT;
 
 	down_read(&mm->mmap_sem);
-	if (ksm_test_exit(mm))
-		goto out;
-	vma = find_vma(mm, rmap_item->address);
-	if (!vma || vma->vm_start > rmap_item->address)
+	vma = find_mergeable_vma(mm, rmap_item->address);
+	if (!vma)
 		goto out;
 
 	err = try_to_merge_one_page(vma, page, kpage);

--
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 5/5] ksm: unstable_tree_search_insert error checking cleanup

[Andrea Arcangeli]

get_mergeable_page() can only return NULL (also in case of errors) or
the pinned mergeable page. It can't return an error different than
NULL. This optimizes away the unnecessary error check.

Add a return after the "out:" label in the callee to make it more
readable.

Acked-by: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
 mm/ksm.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 0183083..b5cd647 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -475,7 +475,8 @@ static struct page *get_mergeable_page(struct rmap_item *rmap_item)
 		flush_dcache_page(page);
 	} else {
 		put_page(page);
-out:		page = NULL;
+out:
+		page = NULL;
 	}
 	up_read(&mm->mmap_sem);
 	return page;
@@ -1358,7 +1359,7 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item,
 		cond_resched();
 		tree_rmap_item = rb_entry(*new, struct rmap_item, node);
 		tree_page = get_mergeable_page(tree_rmap_item);
-		if (IS_ERR_OR_NULL(tree_page))
+		if (!tree_page)
 			return NULL;
 
 		/*

--
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 1/5] mm: add cond_resched() to the rmap walks

[Davidlohr Bueso]

On Mon, 02 Nov 2015, Andrea Arcangeli wrote:

>The rmap walk must reach every possible mapping of the page, so if a
>page is heavily shared (no matter if it's KSM, anon, pagecache) there
>will be tons of entries to walk through. All optimizations with
>prio_tree, anon_vma chains, interval tree, helps to find the right
>virtual mapping faster, but if there are lots of virtual mappings, all
>mapping must still be walked through.
>
>The biggest cost is for the IPIs, but regardless of the IPIs, it's
>generally safer to keep these cond_resched() in all cases, as even if
>we massively reduce the number of IPIs, the number of entries to walk
>IPI-less may still be large and no entry can be possibly skipped in
>the page migration case.
>
>Acked-by: Hugh Dickins <hughd@google.com>
>Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>

Acked-by: Davidlohr Bueso <dbueso@suse.de>

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