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

["David Hildenbrand (Arm)" <david@kernel.org>]

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?

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

-- 
Cheers,

David