* [RFC PATCH] mm/ksm: use checksum to speed up page comparison
@ 2026-07-16 12:20 Pedro Demarchi Gomes
2026-07-29 9:38 ` David Hildenbrand (Arm)
0 siblings, 1 reply; 2+ messages in thread
From: Pedro Demarchi Gomes @ 2026-07-16 12:20 UTC (permalink / raw)
To: Andrew Morton, David Hildenbrand, Xu Xin, Chengming Zhou
Cc: linux-mm, linux-kernel, Pedro Demarchi Gomes
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@gmail.com>
---
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
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [RFC PATCH] mm/ksm: use checksum to speed up page comparison
2026-07-16 12:20 [RFC PATCH] mm/ksm: use checksum to speed up page comparison Pedro Demarchi Gomes
@ 2026-07-29 9:38 ` David Hildenbrand (Arm)
0 siblings, 0 replies; 2+ messages in thread
From: David Hildenbrand (Arm) @ 2026-07-29 9:38 UTC (permalink / raw)
To: Pedro Demarchi Gomes, Andrew Morton, Xu Xin, Chengming Zhou
Cc: linux-mm, linux-kernel
On 7/16/26 14:20, Pedro Demarchi Gomes wrote:
> 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;
> }
>
Hi!
> 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
Given that the default is 100, and sleep_millisecs is 200 ... and it is known
that frequent scanning is harmful for performance, what is the real world impact
in common setups?
IOW, do we even notice / care?
--
Cheers,
David
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2026-07-29 9:38 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-07-16 12:20 [RFC PATCH] mm/ksm: use checksum to speed up page comparison Pedro Demarchi Gomes
2026-07-29 9:38 ` David Hildenbrand (Arm)
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox