[PATCH 0/2] mm/ksm: optimize unstable_tree_search_insert()

[PATCH 0/2] mm/ksm: optimize unstable_tree_search_insert()

[Chengming Zhou]

We use unstable_tree_search_insert() to find matched page or insert our
rmap_item into the unstable tree if no matched found.

Now it may return NULL too early in which cases we can do better:

1. get_mergeable_page() return NULL: which means tree_rmap_item is stale.
2. tree_page is migrated to another node and !ksm_merge_across_nodes.

In both cases, we can just remove the staled or migrated one out of the
unstable tree, so our rmap_item can be inserted successfully. The code
flow becomes clearer and may increase the merge possibility too.

Thanks for review and comments!

Signed-off-by: Chengming Zhou <chengming.zhou@linux.dev>
---
Chengming Zhou (2):
      mm/ksm: re-search unstable tree when tree_rmap_item is stale
      mm/ksm: flush out migrated rmap_item to insert our rmap_item

 mm/ksm.c | 31 +++++++++++++++++++------------
 1 file changed, 19 insertions(+), 12 deletions(-)
---
base-commit: fb0f40125feec3de7ef4524600ac83946207117e
change-id: 20240508-b4-ksm-unstable-insert-0329446317e1

Best regards,
-- 
Chengming Zhou <chengming.zhou@linux.dev>

[PATCH 1/2] mm/ksm: re-search unstable tree when tree_rmap_item is stale

[Chengming Zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

Now unstable_tree_search_insert() will return NULL if encounter a stale
tree_rmap_item, in which case get_mergeable_page() return NULL.

More reasonable handling is to remove stale rmap_item out of unstable
tree and re-search from root. That stale rmap_item will be reclaimed
when next time of scan.

So we can insert our rmap_item successfully instead of returning NULL.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 mm/ksm.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index e1034bf1c937..66219983eb3a 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -2196,12 +2196,14 @@ struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_ite
 {
 	struct rb_node **new;
 	struct rb_root *root;
-	struct rb_node *parent = NULL;
+	struct rb_node *parent;
 	int nid;
 
 	nid = get_kpfn_nid(page_to_pfn(page));
 	root = root_unstable_tree + nid;
+again:
 	new = &root->rb_node;
+	parent = NULL;
 
 	while (*new) {
 		struct ksm_rmap_item *tree_rmap_item;
@@ -2211,8 +2213,10 @@ struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_ite
 		cond_resched();
 		tree_rmap_item = rb_entry(*new, struct ksm_rmap_item, node);
 		tree_page = get_mergeable_page(tree_rmap_item);
-		if (!tree_page)
-			return NULL;
+		if (!tree_page) {
+			remove_rmap_item_from_tree(tree_rmap_item);
+			goto again;
+		}
 
 		/*
 		 * Don't substitute a ksm page for a forked page.

-- 
2.45.0

[PATCH 2/2] mm/ksm: flush out migrated rmap_item to insert our rmap_item

[Chengming Zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

If tree_page has been migrated to another NUMA node and across_nodes
disabled, flush it out immediately and it will be put in the right
unstable tree when next time.

The good point is that we can retry to insert our rmap_item successfully
to increase the merge possibility, and we don't need to bother to
memcmp_pages() in this case.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 mm/ksm.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 66219983eb3a..b840fb55e1f4 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -2226,6 +2226,18 @@ struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_ite
 			return NULL;
 		}
 
+		/*
+		 * If tree_page has been migrated to another NUMA node and
+		 * across_nodes disabled, flush it out here and it will be
+		 * put in the right unstable tree next time. So we can retry
+		 * to insert our rmap_item successfully.
+		 */
+		if (!ksm_merge_across_nodes &&
+		    page_to_nid(tree_page) != nid) {
+			remove_rmap_item_from_tree(tree_rmap_item);
+			goto again;
+		}
+
 		ret = memcmp_pages(page, tree_page);
 
 		parent = *new;
@@ -2235,15 +2247,6 @@ struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_ite
 		} else if (ret > 0) {
 			put_page(tree_page);
 			new = &parent->rb_right;
-		} else if (!ksm_merge_across_nodes &&
-			   page_to_nid(tree_page) != nid) {
-			/*
-			 * If tree_page has been migrated to another NUMA node,
-			 * it will be flushed out and put in the right unstable
-			 * tree next time: only merge with it when across_nodes.
-			 */
-			put_page(tree_page);
-			return NULL;
 		} else {
 			*tree_pagep = tree_page;
 			return tree_rmap_item;

-- 
2.45.0