From patchwork Fri Jun 21 07:54:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chengming Zhou X-Patchwork-Id: 13706967 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id AAAF6C2BA1A for ; Fri, 21 Jun 2024 07:55:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A8C418D0143; Fri, 21 Jun 2024 03:55:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A18F78D0138; Fri, 21 Jun 2024 03:55:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 780888D0143; Fri, 21 Jun 2024 03:55:19 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 4DC728D0138 for ; Fri, 21 Jun 2024 03:55:19 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id E153080AEB for ; Fri, 21 Jun 2024 07:55:18 +0000 (UTC) X-FDA: 82254135516.20.5152834 Received: from out-188.mta0.migadu.com (out-188.mta0.migadu.com [91.218.175.188]) by imf16.hostedemail.com (Postfix) with ESMTP id 8BF4018000E for ; Fri, 21 Jun 2024 07:55:16 +0000 (UTC) Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=TnGrkbwW; dmarc=pass (policy=none) header.from=linux.dev; spf=pass (imf16.hostedemail.com: domain of chengming.zhou@linux.dev designates 91.218.175.188 as permitted sender) smtp.mailfrom=chengming.zhou@linux.dev ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1718956509; a=rsa-sha256; cv=none; b=TCFexkeJghXh0JIHYZO3t1hPohpA4FjcWKJtsVli3Ok+l/ErzgZfsiMqNXSeHZgwoRVE6G GSMBX3d4L56vRpERR3vXotooXHx0G0aKdzQ1uCo+sWFUPy9rB37uxiK+DegtRdVRW0sVZa vqbFEIQR+6N5XHAw/YnLOjzOmJWz++U= ARC-Authentication-Results: i=1; imf16.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=TnGrkbwW; dmarc=pass (policy=none) header.from=linux.dev; spf=pass (imf16.hostedemail.com: domain of chengming.zhou@linux.dev designates 91.218.175.188 as permitted sender) smtp.mailfrom=chengming.zhou@linux.dev ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1718956509; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=aBTb4+v7Qjp9h/YfZziY90UbHgzMj5tgQ+gOTK4dIwk=; b=Azr8UUfsD0EM1m7dv7Yd7TyXdSYm/2y5k9yzn/haCevVr7b41ZEbhCP+Tsi/nlwsrcxdTu lnryUkHXcFB1NNV2Iwfo8QoUTh4VfzSCEXF5e5KLTjqeCIlukndxxckzQDy4E1Y2hPWKCO gTdY6+z9nb7UroHqAbHXXFCbKpNUPdk= X-Envelope-To: david@redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1718956515; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=aBTb4+v7Qjp9h/YfZziY90UbHgzMj5tgQ+gOTK4dIwk=; b=TnGrkbwW436/Yap5Ue4H98Atcpl4VB9QMsg8iPSTtY0CJAXvj4UHSLInQ2RlqUfxsKFoF0 y2NKHI+3D+4ZH7Ax3Q5YK+ZakWJ7xkP7qExCAAugC9UzcRh4vSq5ZVQGqDArJoWkafB66U VFv5AmeaGMnhhI7TBLLiPwkFjgCsiQ0= X-Envelope-To: linux-kernel@vger.kernel.org X-Envelope-To: akpm@linux-foundation.org X-Envelope-To: hughd@google.com X-Envelope-To: chengming.zhou@linux.dev X-Envelope-To: zhouchengming@bytedance.com X-Envelope-To: linux-mm@kvack.org X-Envelope-To: aarcange@redhat.com X-Envelope-To: shr@devkernel.io X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Chengming Zhou Date: Fri, 21 Jun 2024 15:54:31 +0800 Subject: [PATCH v2 3/3] mm/ksm: optimize the chain()/chain_prune() interfaces MIME-Version: 1.0 Message-Id: <20240621-b4-ksm-scan-optimize-v2-3-1c328aa9e30b@linux.dev> References: <20240621-b4-ksm-scan-optimize-v2-0-1c328aa9e30b@linux.dev> In-Reply-To: <20240621-b4-ksm-scan-optimize-v2-0-1c328aa9e30b@linux.dev> To: Andrew Morton , david@redhat.com, aarcange@redhat.com, hughd@google.com, shr@devkernel.io Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, zhouchengming@bytedance.com, Chengming Zhou X-Developer-Signature: v=1; a=ed25519-sha256; t=1718956503; l=9550; i=chengming.zhou@linux.dev; s=20240617; h=from:subject:message-id; bh=aNZtikh89uZPUxDF7c2Rld2Ly+4aFi7EXpdx4+SXheY=; b=bOdA9BYysMkUH2+JdBV45OcwVMOTbDIiKLccdbJ5jZ1yl2TbQ/Jxd6AGsGx7IIzzdL+Vo41Jy foNRzuyFJIABRcXbo9+eILkdIBTZgC116f0rFUtBWPJbukeeK2Go5wH X-Developer-Key: i=chengming.zhou@linux.dev; a=ed25519; pk=/XPhIutBo+zyUeQyf4Ni5JYk/PEIWxIeUQqy2DYjmhI= X-Migadu-Flow: FLOW_OUT X-Rspamd-Queue-Id: 8BF4018000E X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: e7d7xnzood11efw5direwq7bk6gq1s1f X-HE-Tag: 1718956516-977254 X-HE-Meta: U2FsdGVkX1+/MT59YpC4ywCqZwyzRL6d74gYQy4T58hn+Bn5WwEkCUlgB5mIdnezmkWH8trZpXiomQsz/2FqNkD72T79QW49Axytj7YC8AxFlmkNOVZtOwMtx01IxSs8cJPa+hFkHpJhPhN75jHEFg8ZZKxujxHwrptzBVZEi0EHfEjEOVuU1uJHQScWeBuRTQQItow4P2x5duOLSyjLSJHW21Pzhe3TTKOZNRhigyyO2yZeohXqlyvLTflpFasYVjS3riWToh30WgJlWifCVyetTw3iqEvvJn836JGSFim7so+aLGclNR41u6S6X+40Q7ge4aVBqfk1FdquPscgvY8nrWh1WczRR3dH+Ls6sE1SFZjylZ8EBlOgkiw0dIUYZgr1A+6iQ8bN5JuSdAnTeh1arYYH9+tCPbI1qE4yfVBXotEBqW0NesHzDNfwseZpVH3mUHCpeCWbb+OwMxpM3DIV2hoBHqPZm9C04z3o0DtH7v7qhf1vtnwANhoHPV5F7dWtTQ1kWALJNyov1Ky/GDvsQlg29vWxXjXY8zM/Zwk788lgeMp7cWA8Aps3L2BmSDzD6SzIxzXKI1tMJiXVlTbz7DYP4r/koZkeDgRbive9XDG+X/ZFRumM/s1HD4S9/kr3LTgx1QYs214NrPAtP6RpRQpAWIgl+eWuubwEpluDzKt1wuIWC+roKdsfVJhqENHWF+8uIxPGwK7H0p5jSE5NQ3gUuhtsqswXn1NzNXPIuDOoRuPY4KJKf2GOJDxPiGxhplnIo9tcQqQePbNgOUnKRW5acj9W4aCAvbUUPsDLTgE+AG+FZcRLDIQR8xnxRmFa69CWqElT5Pwv9BbQCwXkAV55pfqVQCVfyD0D8iVfNzoH5tuUKeOx2Ova1kkfna0cY0zsBWup0bOLQ4jOd+zy4glo+1CVsGOc8Y6vNgEcw26+adp2SbZk9BJqHVhkE9E0Ybtt0QHtt3cai35 6HS6B1om UQMZrDgdswf0uGkdZIcw7SN6pQxHFmq6MSXpKPE2kBhDQz3hEMe95I1KIqlFd8w9bn+Voj/yebTwXPVpz4GFTMARPLkc4DQL8TlSVeM4wrqg2oZAHqid5Wh5baYQQUXBpWYSW2n9ZF33lEceCIz7ao1tpsA57P4bC9mbxie1jDnylVag= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Now the implementation of stable_node_dup() causes chain()/chain_prune() interfaces and usages are overcomplicated. Why? stable_node_dup() only find and return a candidate stable_node for sharing, so the users have to recheck using stable_node_dup_any() if any non-candidate stable_node exist. And try to ksm_get_folio() from it again. Actually, stable_node_dup() can just return a best stable_node as it can, then the users can check if it's a candidate for sharing or not. The code is simplified too and fewer corner cases: such as stable_node and stable_node_dup can't be NULL if returned tree_folio is not NULL. Signed-off-by: Chengming Zhou --- mm/ksm.c | 152 ++++++++++++--------------------------------------------------- 1 file changed, 27 insertions(+), 125 deletions(-) diff --git a/mm/ksm.c b/mm/ksm.c index 2cf836fb1367..8a5d88472223 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -1663,7 +1663,6 @@ static struct folio *stable_node_dup(struct ksm_stable_node **_stable_node_dup, struct ksm_stable_node *dup, *found = NULL, *stable_node = *_stable_node; struct hlist_node *hlist_safe; struct folio *folio, *tree_folio = NULL; - int nr = 0; int found_rmap_hlist_len; if (!prune_stale_stable_nodes || @@ -1690,33 +1689,26 @@ static struct folio *stable_node_dup(struct ksm_stable_node **_stable_node_dup, folio = ksm_get_folio(dup, KSM_GET_FOLIO_NOLOCK); if (!folio) continue; - nr += 1; - if (is_page_sharing_candidate(dup)) { - if (!found || - dup->rmap_hlist_len > found_rmap_hlist_len) { - if (found) - folio_put(tree_folio); - found = dup; - found_rmap_hlist_len = found->rmap_hlist_len; - tree_folio = folio; - - /* skip put_page for found dup */ - if (!prune_stale_stable_nodes) - break; - continue; - } + /* Pick the best candidate if possible. */ + if (!found || (is_page_sharing_candidate(dup) && + (!is_page_sharing_candidate(found) || + dup->rmap_hlist_len > found_rmap_hlist_len))) { + if (found) + folio_put(tree_folio); + found = dup; + found_rmap_hlist_len = found->rmap_hlist_len; + tree_folio = folio; + /* skip put_page for found candidate */ + if (!prune_stale_stable_nodes && + is_page_sharing_candidate(found)) + break; + continue; } folio_put(folio); } if (found) { - /* - * nr is counting all dups in the chain only if - * prune_stale_stable_nodes is true, otherwise we may - * break the loop at nr == 1 even if there are - * multiple entries. - */ - if (prune_stale_stable_nodes && nr == 1) { + if (hlist_is_singular_node(&found->hlist_dup, &stable_node->hlist)) { /* * If there's not just one entry it would * corrupt memory, better BUG_ON. In KSM @@ -1768,25 +1760,15 @@ static struct folio *stable_node_dup(struct ksm_stable_node **_stable_node_dup, hlist_add_head(&found->hlist_dup, &stable_node->hlist); } + } else { + /* Its hlist must be empty if no one found. */ + free_stable_node_chain(stable_node, root); } *_stable_node_dup = found; return tree_folio; } -static struct ksm_stable_node *stable_node_dup_any(struct ksm_stable_node *stable_node, - struct rb_root *root) -{ - if (!is_stable_node_chain(stable_node)) - return stable_node; - if (hlist_empty(&stable_node->hlist)) { - free_stable_node_chain(stable_node, root); - return NULL; - } - return hlist_entry(stable_node->hlist.first, - typeof(*stable_node), hlist_dup); -} - /* * Like for ksm_get_folio, this function can free the *_stable_node and * *_stable_node_dup if the returned tree_page is NULL. @@ -1807,17 +1789,10 @@ static struct folio *__stable_node_chain(struct ksm_stable_node **_stable_node_d bool prune_stale_stable_nodes) { struct ksm_stable_node *stable_node = *_stable_node; + if (!is_stable_node_chain(stable_node)) { - if (is_page_sharing_candidate(stable_node)) { - *_stable_node_dup = stable_node; - return ksm_get_folio(stable_node, KSM_GET_FOLIO_NOLOCK); - } - /* - * _stable_node_dup set to NULL means the stable_node - * reached the ksm_max_page_sharing limit. - */ - *_stable_node_dup = NULL; - return NULL; + *_stable_node_dup = stable_node; + return ksm_get_folio(stable_node, KSM_GET_FOLIO_NOLOCK); } return stable_node_dup(_stable_node_dup, _stable_node, root, prune_stale_stable_nodes); @@ -1831,16 +1806,10 @@ static __always_inline struct folio *chain_prune(struct ksm_stable_node **s_n_d, } static __always_inline struct folio *chain(struct ksm_stable_node **s_n_d, - struct ksm_stable_node *s_n, + struct ksm_stable_node **s_n, struct rb_root *root) { - struct ksm_stable_node *old_stable_node = s_n; - struct folio *tree_folio; - - tree_folio = __stable_node_chain(s_n_d, &s_n, root, false); - /* not pruning dups so s_n cannot have changed */ - VM_BUG_ON(s_n != old_stable_node); - return tree_folio; + return __stable_node_chain(s_n_d, s_n, root, false); } /* @@ -1858,7 +1827,7 @@ static struct page *stable_tree_search(struct page *page) struct rb_root *root; struct rb_node **new; struct rb_node *parent; - struct ksm_stable_node *stable_node, *stable_node_dup, *stable_node_any; + struct ksm_stable_node *stable_node, *stable_node_dup; struct ksm_stable_node *page_node; struct folio *folio; @@ -1882,45 +1851,7 @@ static struct page *stable_tree_search(struct page *page) cond_resched(); stable_node = rb_entry(*new, struct ksm_stable_node, node); - stable_node_any = NULL; tree_folio = chain_prune(&stable_node_dup, &stable_node, root); - /* - * NOTE: stable_node may have been freed by - * chain_prune() if the returned stable_node_dup is - * not NULL. stable_node_dup may have been inserted in - * the rbtree instead as a regular stable_node (in - * order to collapse the stable_node chain if a single - * stable_node dup was found in it). In such case the - * stable_node is overwritten by the callee to point - * to the stable_node_dup that was collapsed in the - * stable rbtree and stable_node will be equal to - * stable_node_dup like if the chain never existed. - */ - if (!stable_node_dup) { - /* - * Either all stable_node dups were full in - * this stable_node chain, or this chain was - * empty and should be rb_erased. - */ - stable_node_any = stable_node_dup_any(stable_node, - root); - if (!stable_node_any) { - /* rb_erase just run */ - goto again; - } - /* - * Take any of the stable_node dups page of - * this stable_node chain to let the tree walk - * continue. All KSM pages belonging to the - * stable_node dups in a stable_node chain - * have the same content and they're - * write protected at all times. Any will work - * fine to continue the walk. - */ - tree_folio = ksm_get_folio(stable_node_any, - KSM_GET_FOLIO_NOLOCK); - } - VM_BUG_ON(!stable_node_dup ^ !!stable_node_any); if (!tree_folio) { /* * If we walked over a stale stable_node, @@ -1958,7 +1889,7 @@ static struct page *stable_tree_search(struct page *page) goto chain_append; } - if (!stable_node_dup) { + if (!is_page_sharing_candidate(stable_node_dup)) { /* * If the stable_node is a chain and * we got a payload match in memcmp @@ -2067,9 +1998,6 @@ static struct page *stable_tree_search(struct page *page) return &folio->page; chain_append: - /* stable_node_dup could be null if it reached the limit */ - if (!stable_node_dup) - stable_node_dup = stable_node_any; /* * If stable_node was a chain and chain_prune collapsed it, * stable_node has been updated to be the new regular @@ -2114,7 +2042,7 @@ static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio) struct rb_root *root; struct rb_node **new; struct rb_node *parent; - struct ksm_stable_node *stable_node, *stable_node_dup, *stable_node_any; + struct ksm_stable_node *stable_node, *stable_node_dup; bool need_chain = false; kpfn = folio_pfn(kfolio); @@ -2130,33 +2058,7 @@ static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio) cond_resched(); stable_node = rb_entry(*new, struct ksm_stable_node, node); - stable_node_any = NULL; - tree_folio = chain(&stable_node_dup, stable_node, root); - if (!stable_node_dup) { - /* - * Either all stable_node dups were full in - * this stable_node chain, or this chain was - * empty and should be rb_erased. - */ - stable_node_any = stable_node_dup_any(stable_node, - root); - if (!stable_node_any) { - /* rb_erase just run */ - goto again; - } - /* - * Take any of the stable_node dups page of - * this stable_node chain to let the tree walk - * continue. All KSM pages belonging to the - * stable_node dups in a stable_node chain - * have the same content and they're - * write protected at all times. Any will work - * fine to continue the walk. - */ - tree_folio = ksm_get_folio(stable_node_any, - KSM_GET_FOLIO_NOLOCK); - } - VM_BUG_ON(!stable_node_dup ^ !!stable_node_any); + tree_folio = chain(&stable_node_dup, &stable_node, root); if (!tree_folio) { /* * If we walked over a stale stable_node,