[RFC PATCH] mm/ksm: use checksum to speed up page comparison
From: Pedro Demarchi Gomes
Date: Thu Jul 16 2026 - 08:23:37 EST
Use page checksums as the primary ordering key when traversing the stable
and unstable trees and fall back to memcmp_pages() only when checksums
match.
Since struct ksm_stable_node does not have a checksum field, create one
in a union with migration list fields, so when we encounter a migration
page while scanning an address space we have to recalculate the page
checksum. This avoids increasing the size of struct ksm_stable_node,
which is maintained at 64 bytes, as show below.
pedro@fedora:~/tmp/linux$ pahole -C ksm_stable_node ./vmlinux
struct ksm_stable_node {
union {
struct {
struct rb_node node __attribute__((__aligned__(8))); /* 0 24 */
unsigned int checksum; /* 24 4 */
} __attribute__((__aligned__(8))) __attribute__((__aligned__(8))); /* 0 32 */
struct {
struct list_head * head; /* 0 8 */
struct {
struct hlist_node hlist_dup; /* 8 16 */
struct list_head list; /* 24 16 */
}; /* 8 32 */
}; /* 0 40 */
} __attribute__((__aligned__(8))); /* 0 40 */
struct hlist_head hlist; /* 40 8 */
union {
long unsigned int kpfn; /* 48 8 */
long unsigned int chain_prune_time; /* 48 8 */
}; /* 48 8 */
int rmap_hlist_len; /* 56 4 */
int nid; /* 60 4 */
/* size: 64, cachelines: 1, members: 5 */
/* forced alignments: 1 */
} __attribute__((__aligned__(8)));
To evaluate this change it was used two benchmarks, bench1.c and
bench2.c. The first one allocates 8G of pages with different content,
and the second one allocates 8G of pages where the first 4G are the same
as the last 4G. The two benchmarks and the system ksm configuration are
presented below.
bench1.c:
int main() {
size_t size = 8ULL * 1024*1024*1024;
unsigned long long int numpages = size/PAGESZ;
char *pages = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// Generate #numpages pages with different contents
for (unsigned long long i = 0; i < numpages; i++) {
*((unsigned long long *) &pages[i*PAGESZ]) = i;
}
if (madvise(pages, size, MADV_MERGEABLE) != 0) {
perror("madvise MADV_MERGEABLE failed");
return 1;
}
printf("Wait...\n");
getchar();
return 0;
}
bench2.c:
int main() {
size_t size = 8ULL * 1024*1024*1024;
unsigned long long int numpages = size/PAGESZ;
char *pages = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// Generate #numpages pages with different contents
for (unsigned long long i = 0; i < numpages/2; i++) {
*((unsigned long long *) &pages[i*PAGESZ]) = i;
*((unsigned long long *) &pages[(numpages-i-1)*PAGESZ]) = i;
}
if (madvise(pages, size, MADV_MERGEABLE) != 0) {
perror("madvise MADV_MERGEABLE failed");
return 1;
}
printf("Wait...\n");
getchar();
return 0;
}
Configuration:
echo never > /sys/kernel/mm/transparent_hugepage/enabled
echo 1 > /sys/kernel/mm/ksm/sleep_millisecs
echo 100000 > /sys/kernel/mm/ksm/pages_to_scan
echo 0 > /sys/kernel/mm/ksm/use_zero_pages
echo 1 > /sys/kernel/mm/ksm/smart_scan
echo 1 > /sys/kernel/mm/ksm/run
It was used the following bpftrace command to measure the scan time and
compare the numbers of the vanilla and patched version of the two
benchmarks:
bpftrace -e 'tracepoint:ksm:ksm_start_scan { @start_ns = nsecs; }
tracepoint:ksm:ksm_stop_scan {
$elapsed = nsecs - @start_ns;
printf("KSM scan finished in %llu ns\n", $elapsed);
delete(@start_ns);
}'
The number of scans and the sum of the scan times of bench1:
bench1: 58 scans
PATCHED 121847114611 ns
VANILLA 416445370473 ns
SPEED UP 3.4177
In bench2 ksm takes two scans to merge all 4G of memory. So comparing the scan
times of the first two scans:
bench2: 2 scans
PATCHED 58344341937 ns
VANILLA 84007052386 ns
SPEED UP 1.4398
This patch is based on commit
'd9031030ac19defb229537d22ad53e9bb4303ccc'.
Signed-off-by: Pedro Demarchi Gomes <pedrodemargomes@xxxxxxxxx>
---
mm/ksm.c | 112 ++++++++++++++++++++++++++++++++++++++-----------------
1 file changed, 78 insertions(+), 34 deletions(-)
diff --git a/mm/ksm.c b/mm/ksm.c
index 7d5b76478f0b..c79b0328d5ca 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -147,6 +147,7 @@ struct ksm_scan {
/**
* struct ksm_stable_node - node of the stable rbtree
* @node: rb node of this ksm page in the stable tree
+ * @checksum: checksum of this ksm page
* @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
* @hlist_dup: linked into the stable_node->hlist with a stable_node chain
* @list: linked into migrate_nodes, pending placement in the proper node tree
@@ -158,7 +159,10 @@ struct ksm_scan {
*/
struct ksm_stable_node {
union {
- struct rb_node node; /* when node of stable tree */
+ struct {
+ struct rb_node node; /* when node of stable tree */
+ unsigned int checksum;
+ };
struct { /* when listed for migration */
struct list_head *head;
struct {
@@ -847,6 +851,7 @@ static struct ksm_stable_node *alloc_stable_node_chain(struct ksm_stable_node *d
INIT_HLIST_HEAD(&chain->hlist);
chain->chain_prune_time = jiffies;
chain->rmap_hlist_len = STABLE_NODE_CHAIN;
+ chain->checksum = dup->checksum;
#if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA)
chain->nid = NUMA_NO_NODE; /* debug */
#endif
@@ -1816,6 +1821,18 @@ static __always_inline struct folio *chain(struct ksm_stable_node **s_n_d,
return __stable_node_chain(s_n_d, s_n, root, false);
}
+static __always_inline int ksm_memcmp_pages(struct page *page1,
+ unsigned int checksum1,
+ struct page *page2,
+ unsigned int checksum2)
+{
+ if (checksum1 < checksum2)
+ return -1;
+ if (checksum1 > checksum2)
+ return 1;
+ return memcmp_pages(page1, page2);
+}
+
/*
* stable_tree_search - search for page inside the stable tree
*
@@ -1825,7 +1842,7 @@ static __always_inline struct folio *chain(struct ksm_stable_node **s_n_d,
* This function returns the stable tree node of identical content if found,
* -EBUSY if the stable node's page is being migrated, NULL otherwise.
*/
-static struct folio *stable_tree_search(struct page *page)
+static struct folio *stable_tree_search(struct page *page, unsigned int checksum)
{
int nid;
struct rb_root *root;
@@ -1869,7 +1886,8 @@ static struct folio *stable_tree_search(struct page *page)
goto again;
}
- ret = memcmp_pages(page, &tree_folio->page);
+ ret = ksm_memcmp_pages(page, checksum, &tree_folio->page,
+ stable_node->checksum);
folio_put(tree_folio);
parent = *new;
@@ -1946,6 +1964,7 @@ static struct folio *stable_tree_search(struct page *page)
DO_NUMA(page_node->nid = nid);
rb_link_node(&page_node->node, parent, new);
rb_insert_color(&page_node->node, root);
+ page_node->checksum = checksum;
out:
if (is_page_sharing_candidate(page_node)) {
folio_get(folio);
@@ -1973,6 +1992,7 @@ static struct folio *stable_tree_search(struct page *page)
rb_replace_node(&stable_node_dup->node,
&page_node->node,
root);
+ page_node->checksum = checksum;
if (is_page_sharing_candidate(page_node))
folio_get(folio);
else
@@ -1989,6 +2009,7 @@ static struct folio *stable_tree_search(struct page *page)
list_del(&page_node->list);
DO_NUMA(page_node->nid = nid);
stable_node_chain_add_dup(page_node, stable_node);
+ page_node->checksum = checksum;
if (is_page_sharing_candidate(page_node))
folio_get(folio);
else
@@ -2027,6 +2048,7 @@ static struct folio *stable_tree_search(struct page *page)
VM_BUG_ON(!is_stable_node_dup(stable_node_dup));
VM_BUG_ON(page_node->head != &migrate_nodes);
list_del(&page_node->list);
+ page_node->checksum = checksum;
DO_NUMA(page_node->nid = nid);
stable_node_chain_add_dup(page_node, stable_node);
goto out;
@@ -2048,10 +2070,12 @@ static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio)
struct rb_node *parent;
struct ksm_stable_node *stable_node, *stable_node_dup;
bool need_chain = false;
+ unsigned int checksum;
kpfn = folio_pfn(kfolio);
nid = get_kpfn_nid(kpfn);
root = root_stable_tree + nid;
+ checksum = calc_checksum(&kfolio->page);
again:
parent = NULL;
new = &root->rb_node;
@@ -2076,7 +2100,9 @@ static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio)
goto again;
}
- ret = memcmp_pages(&kfolio->page, &tree_folio->page);
+ ret = ksm_memcmp_pages(&kfolio->page, checksum,
+ &tree_folio->page,
+ stable_node->checksum);
folio_put(tree_folio);
parent = *new;
@@ -2116,6 +2142,7 @@ static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio)
folio_set_stable_node(kfolio, stable_node_dup);
+ stable_node_dup->checksum = checksum;
return stable_node_dup;
}
@@ -2150,43 +2177,52 @@ struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_ite
while (*new) {
struct ksm_rmap_item *tree_rmap_item;
struct page *tree_page;
- int ret;
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;
-
- /*
- * Don't substitute a ksm page for a forked page.
- */
- if (page == tree_page) {
- put_page(tree_page);
- return NULL;
- }
-
- ret = memcmp_pages(page, tree_page);
parent = *new;
- if (ret < 0) {
- put_page(tree_page);
+ if (rmap_item->oldchecksum < tree_rmap_item->oldchecksum) {
new = &parent->rb_left;
- } else if (ret > 0) {
- put_page(tree_page);
+ } else if (rmap_item->oldchecksum >
+ tree_rmap_item->oldchecksum) {
new = &parent->rb_right;
- } else if (!ksm_merge_across_nodes &&
- page_to_nid(tree_page) != nid) {
+ } else {
+ int ret;
+
+ tree_page = get_mergeable_page(tree_rmap_item);
+ if (!tree_page)
+ return NULL;
+
/*
- * 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.
+ * Don't substitute a ksm page for a forked page.
*/
- put_page(tree_page);
- return NULL;
- } else {
- *tree_pagep = tree_page;
- return tree_rmap_item;
+ if (page == tree_page) {
+ put_page(tree_page);
+ return NULL;
+ }
+
+ ret = memcmp_pages(page, tree_page);
+
+ if (ret < 0) {
+ put_page(tree_page);
+ new = &parent->rb_left;
+ } 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;
+ }
}
}
@@ -2271,6 +2307,14 @@ static void cmp_and_merge_page(struct page *page, struct ksm_rmap_item *rmap_ite
if (stable_node->head != &migrate_nodes &&
rmap_item->head == stable_node)
return;
+ /*
+ * If stable_node is in migrate_nodes list its checksum field
+ * is not valid, so calculate it here
+ */
+ if (stable_node->head == &migrate_nodes)
+ checksum = calc_checksum(page);
+ else
+ checksum = stable_node->checksum;
/*
* If it's a KSM fork, allow it to go over the sharing limit
* without warnings.
@@ -2295,15 +2339,15 @@ static void cmp_and_merge_page(struct page *page, struct ksm_rmap_item *rmap_ite
if (!try_to_merge_with_zero_page(rmap_item, page))
return;
}
-
/* Start by searching for the folio in the stable tree */
- kfolio = stable_tree_search(page);
+ kfolio = stable_tree_search(page, checksum);
if (kfolio == folio && rmap_item->head == stable_node) {
folio_put(kfolio);
return;
}
remove_rmap_item_from_tree(rmap_item);
+ rmap_item->oldchecksum = checksum;
if (kfolio) {
if (kfolio == ERR_PTR(-EBUSY))
--
2.54.0