Re: [RFC PATCH] mm/ksm: use checksum to speed up page comparison

[Pedro Demarchi Gomes <pedrodemargomes@gmail.com>]

On Thu, Jul 30, 2026 at 04:47:14PM +0200, David Hildenbrand (Arm) wrote:
> On 7/30/26 16:22, Pedro Demarchi Gomes wrote:
> > On Wed, Jul 29, 2026 at 11:38:38AM +0200, David Hildenbrand (Arm) wrote:
> >> 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!
> >>
> > 
> > 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?
> >>
> > 
> > As described in the KSM admin guide [1], the default values for pages_to_scan
> > and sleep_millisecs are intended for demonstration purposes rather than
> > production use.
> 
> Well, I argue that
> 
> 	echo 1 >  /sys/kernel/mm/ksm/sleep_millisecs
> 	echo 100000 >  /sys/kernel/mm/ksm/pages_to_scan
> 
> is not for production use either?
> 

Yes, this configuration was used only for a quick benchmark to test the RFC
idea.

> > 
> > At LPC 2023, Stefan Roesch described the use of KSM in a production workload at
> > Meta [2] and presented optimizations such as Smart Scan and Advisor Mode, both
> > of which have since been merged to reduce KSM's scanning overhead.
> > 
> > This RFC proposes a complementary optimization. KSM already computes a checksum
> > for every scanned page to identify frequently changing pages and avoid
> > unnecessary stable and unstable tree lookups. Reusing that checksum as an index
> > into those trees can further reduce lookup costs, lowering CPU usage without
> > changing KSM's behavior.
> 
> Yes, but the change is not completely trivial, so we better make sure that the
> change is actually worth it in practice.
>

Ok. I am CCing Stefan Roesch to get his opinion on this.
Thanks!

> -- 
> Cheers,
> 
> David
>