From nobody Sat Jul 25 15:51:37 2026 Received: from mail-yx1-f52.google.com (mail-yx1-f52.google.com [74.125.224.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 77C78382361 for ; Thu, 16 Jul 2026 12:22:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.224.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1784204538; cv=none; b=Tl7wkqsDrjDTzk55hBvaRG+3csPoXNC0nq3wbzYX9iC3RJS8icuhsNJg56TM8PmQQN/Ab+mMcvk1i4h3ii1TOJQXoYWuyyO0xOIB6be9pN2z1DHgIJFhMb0rWhNysmrFfDQlK6DaL2FeIem9KZ2IhDltRdKQ+UpO87mipWo88ug= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1784204538; c=relaxed/simple; bh=K5QxdT34Z7Nlk1hcP7I3l1HpUUvFoq0wrN2yLWnXptQ=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=VIE9DT1FbwHqGIUTWaj9mZtn7RkABWbq/ZHnE0O/z2pFMhwPPf+ZCl/2uppVJsHnvYLLMibOx6jKN05Pkq5E3VLeOAC91huH1aXtqXmd8+TvJBdzG63dDFtQzWG0VaOJycooFtckJThDYL5jF7OiywaHz3KT8atMwztC/EAnQ8U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lDd7Af4l; arc=none smtp.client-ip=74.125.224.52 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lDd7Af4l" Received: by mail-yx1-f52.google.com with SMTP id 956f58d0204a3-668296d0ff3so731412d50.0 for ; Thu, 16 Jul 2026 05:22:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1784204535; x=1784809335; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to:content-type; bh=rpGdWJFpIUEvAvYjxewkkqgZyu1hAM+6SDZkgbpU9xg=; b=lDd7Af4lnEgtW4Fzul9Z7dkRPwy2yxtgTBhdNUfFX84f1u2p/3KJC0L21Aq7xWRFZP 9Nv9/B8BkX7ApEB6mher8O4tK6BHyU8DWGQF8BCE8CkoOWdzBkU/L24pkX/hy4llvCmj yONdxPpHop5xz/H3lOo+mc5mLyzXFw6fOodqZDhpZynqbI2VsJKm1V0aNv4+MXQoSg6P a9vAmYq2umBblHjIcJeVYLaYFAphrnY/MpK/EWq3DzIoerAm/DrER2a55AGDM7tC63/+ ZRBw4hRTCOAvbCGkiZFHaJL2u6gwJvbo2vB8w8mrqRRCbS2OFN2MN10cr7V7QoO6u+qX U/Kg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1784204535; x=1784809335; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to:content-type; bh=rpGdWJFpIUEvAvYjxewkkqgZyu1hAM+6SDZkgbpU9xg=; b=YYxUiwBFo2XJwxcjFRqHO1pL70CznD4c5e9oVS/dV14PkroC7LlYWbVp3hnTAIMhEr GS3vOjfXShHvsuG8swP73h+vbpUJlwX/2z/5SVkSKi+cswbT1a4OllrAIDo+1Fx+nTqA uE/MOj+uK7ToYFEWwClCuQRrf/QiSZkznUdhSWFvRVWKXGrUFFN2UhnqxxEyIQrtiexP 30mYKCvDhiMxCIa3dCTheROq+8kApTeVYQnrH5VeNWyygzsjHu0NqigojI21RMaD37ZW N6zCKYNSx8MMVy82IGYazqOzW8oFCDcbKp/Zihe+NHzkRAIltFQGaumTYS8Szqn5wzhh K4nQ== X-Forwarded-Encrypted: i=1; AHgh+Rq6h/wwjVZvGlJw0fw6U83mZStDtYdfIK0iRTUZ68nj2+/M2VGILWgotpMkylEiQPa+1Xkn4A+oAEmfxf0=@vger.kernel.org X-Gm-Message-State: AOJu0YyQS4mHbzomIEU260xpGN4l3UsxYAkfVaMuxF+acuRO3ETYqo7r eoGhhPgditwS/ER1eI/qY49nGI5V+4DibvO/L4h1TeAf7KaszdreNNsx X-Gm-Gg: AfdE7ckxqG8bHGwW+F7tiw9npkCTEX6q+5C3PcwoAn04VEeVXGQsRH342Yz/E2Y8yJ7 IUkAOdt5QDN/XXR0rAvjmKHOH+OB7f4fhkL9w4pifVD54OuGeIieyiFxSvURZk5Cx4TudbwSodI HlWRKO9GLpoPLxCpt7TG+ZETcRMUff4qW/C99wG9TzhVkJ+uTPNYE66b7dDN+cCDXG+mbYwxJrZ tDE1JuU9CNmYivKkau3RnLzVNY++rqXHEf/gIqV5YrBugEV4ZIUWw3zyzHf3NZyOObufu4LGruZ iwUaek7L8O+XUZpWtGjLlgWr+h1hFgM0C7pENgU2c5jFxqNZaBY9tZZ/zyogkXgP9f1XTFRmb0x dWPJcLwYfoOXJCO4oK2jUzNgsqwK8fwjpLatGoxBEQlinzzirV2V63jM8vh67v3do5xTotY8NfB G4Zv8ogykLPHVFvIzjWewDIghCWX1ne+DfErgLwA== X-Received: by 2002:a05:690e:4312:b0:664:ef34:4b with SMTP id 956f58d0204a3-6681347ed35mr4069141d50.76.1784204535115; Thu, 16 Jul 2026 05:22:15 -0700 (PDT) Received: from fedora ([2804:30c:1f53:aa00:1495:7d0a:c9fe:c63a]) by smtp.gmail.com with ESMTPSA id 956f58d0204a3-6681fc49cf2sm3165524d50.9.2026.07.16.05.22.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 16 Jul 2026 05:22:14 -0700 (PDT) From: Pedro Demarchi Gomes To: Andrew Morton , David Hildenbrand , Xu Xin , Chengming Zhou Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Pedro Demarchi Gomes Subject: [RFC PATCH] mm/ksm: use checksum to speed up page comparison Date: Thu, 16 Jul 2026 09:20:39 -0300 Message-ID: <20260716122039.679173-1-pedrodemargomes@gmail.com> X-Mailer: git-send-email 2.54.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 =3D 8ULL * 1024*1024*1024; unsigned long long int numpages =3D size/PAGESZ; char *pages =3D mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP= _ANONYMOUS, -1, 0); // Generate #numpages pages with different contents for (unsigned long long i =3D 0; i < numpages; i++) { *((unsigned long long *) &pages[i*PAGESZ]) =3D i; } if (madvise(pages, size, MADV_MERGEABLE) !=3D 0) { perror("madvise MADV_MERGEABLE failed"); return 1; } printf("Wait...\n"); getchar(); return 0; } bench2.c: int main() { size_t size =3D 8ULL * 1024*1024*1024; unsigned long long int numpages =3D size/PAGESZ; char *pages =3D mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP= _ANONYMOUS, -1, 0); // Generate #numpages pages with different contents for (unsigned long long i =3D 0; i < numpages/2; i++) { *((unsigned long long *) &pages[i*PAGESZ]) =3D i; *((unsigned long long *) &pages[(numpages-i-1)*PAGESZ]) =3D i; } if (madvise(pages, size, MADV_MERGEABLE) !=3D 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 =3D nsecs; } tracepoint:ksm:ksm_stop_scan { $elapsed =3D 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 s= can 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 --- 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 =3D jiffies; chain->rmap_hlist_len =3D STABLE_NODE_CHAIN; + chain->checksum =3D dup->checksum; #if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA) chain->nid =3D NUMA_NO_NODE; /* debug */ #endif @@ -1816,6 +1821,18 @@ static __always_inline struct folio *chain(struct ks= m_stable_node **s_n_d, return __stable_node_chain(s_n_d, s_n, root, false); } =20 +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 foun= d, * -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 ch= ecksum) { int nid; struct rb_root *root; @@ -1869,7 +1886,8 @@ static struct folio *stable_tree_search(struct page *= page) goto again; } =20 - ret =3D memcmp_pages(page, &tree_folio->page); + ret =3D ksm_memcmp_pages(page, checksum, &tree_folio->page, + stable_node->checksum); folio_put(tree_folio); =20 parent =3D *new; @@ -1946,6 +1964,7 @@ static struct folio *stable_tree_search(struct page *= page) DO_NUMA(page_node->nid =3D nid); rb_link_node(&page_node->node, parent, new); rb_insert_color(&page_node->node, root); + page_node->checksum =3D 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 =3D 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 =3D nid); stable_node_chain_add_dup(page_node, stable_node); + page_node->checksum =3D 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 !=3D &migrate_nodes); list_del(&page_node->list); + page_node->checksum =3D checksum; DO_NUMA(page_node->nid =3D nid); stable_node_chain_add_dup(page_node, stable_node); goto out; @@ -2048,10 +2070,12 @@ static struct ksm_stable_node *stable_tree_insert(s= truct folio *kfolio) struct rb_node *parent; struct ksm_stable_node *stable_node, *stable_node_dup; bool need_chain =3D false; + unsigned int checksum; =20 kpfn =3D folio_pfn(kfolio); nid =3D get_kpfn_nid(kpfn); root =3D root_stable_tree + nid; + checksum =3D calc_checksum(&kfolio->page); again: parent =3D NULL; new =3D &root->rb_node; @@ -2076,7 +2100,9 @@ static struct ksm_stable_node *stable_tree_insert(str= uct folio *kfolio) goto again; } =20 - ret =3D memcmp_pages(&kfolio->page, &tree_folio->page); + ret =3D ksm_memcmp_pages(&kfolio->page, checksum, + &tree_folio->page, + stable_node->checksum); folio_put(tree_folio); =20 parent =3D *new; @@ -2116,6 +2142,7 @@ static struct ksm_stable_node *stable_tree_insert(str= uct folio *kfolio) =20 folio_set_stable_node(kfolio, stable_node_dup); =20 + stable_node_dup->checksum =3D checksum; return stable_node_dup; } =20 @@ -2150,43 +2177,52 @@ struct ksm_rmap_item *unstable_tree_search_insert(s= truct ksm_rmap_item *rmap_ite while (*new) { struct ksm_rmap_item *tree_rmap_item; struct page *tree_page; - int ret; =20 cond_resched(); tree_rmap_item =3D rb_entry(*new, struct ksm_rmap_item, node); - tree_page =3D get_mergeable_page(tree_rmap_item); - if (!tree_page) - return NULL; - - /* - * Don't substitute a ksm page for a forked page. - */ - if (page =3D=3D tree_page) { - put_page(tree_page); - return NULL; - } - - ret =3D memcmp_pages(page, tree_page); =20 parent =3D *new; - if (ret < 0) { - put_page(tree_page); + if (rmap_item->oldchecksum < tree_rmap_item->oldchecksum) { new =3D &parent->rb_left; - } else if (ret > 0) { - put_page(tree_page); + } else if (rmap_item->oldchecksum > + tree_rmap_item->oldchecksum) { new =3D &parent->rb_right; - } else if (!ksm_merge_across_nodes && - page_to_nid(tree_page) !=3D nid) { + } else { + int ret; + + tree_page =3D 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 =3D tree_page; - return tree_rmap_item; + if (page =3D=3D tree_page) { + put_page(tree_page); + return NULL; + } + + ret =3D memcmp_pages(page, tree_page); + + if (ret < 0) { + put_page(tree_page); + new =3D &parent->rb_left; + } else if (ret > 0) { + put_page(tree_page); + new =3D &parent->rb_right; + } else if (!ksm_merge_across_nodes && + page_to_nid(tree_page) !=3D 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 =3D tree_page; + return tree_rmap_item; + } } } =20 @@ -2271,6 +2307,14 @@ static void cmp_and_merge_page(struct page *page, st= ruct ksm_rmap_item *rmap_ite if (stable_node->head !=3D &migrate_nodes && rmap_item->head =3D=3D 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 =3D=3D &migrate_nodes) + checksum =3D calc_checksum(page); + else + checksum =3D 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, s= truct 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 =3D stable_tree_search(page); + kfolio =3D stable_tree_search(page, checksum); if (kfolio =3D=3D folio && rmap_item->head =3D=3D stable_node) { folio_put(kfolio); return; } =20 remove_rmap_item_from_tree(rmap_item); + rmap_item->oldchecksum =3D checksum; =20 if (kfolio) { if (kfolio =3D=3D ERR_PTR(-EBUSY)) --=20 2.54.0