From mboxrd@z Thu Jan 1 00:00:00 1970 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 3AFA3C25B74 for ; Fri, 24 May 2024 08:57:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BEAB16B0098; Fri, 24 May 2024 04:57:47 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B978F6B0099; Fri, 24 May 2024 04:57:47 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9F4F66B009A; Fri, 24 May 2024 04:57:47 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 7ECDD6B0098 for ; Fri, 24 May 2024 04:57:47 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 309A21C0F4E for ; Fri, 24 May 2024 08:57:47 +0000 (UTC) X-FDA: 82152686574.12.6E46A59 Received: from out-188.mta1.migadu.com (out-188.mta1.migadu.com [95.215.58.188]) by imf15.hostedemail.com (Postfix) with ESMTP id A61DCA000D for ; Fri, 24 May 2024 08:57:44 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=nsleZO40; spf=pass (imf15.hostedemail.com: domain of chengming.zhou@linux.dev designates 95.215.58.188 as permitted sender) smtp.mailfrom=chengming.zhou@linux.dev; dmarc=pass (policy=none) header.from=linux.dev ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1716541065; a=rsa-sha256; cv=none; b=MOIlugWePEe+3f1qJHnPFegfrRtPt+NSIzOkuoEtj7c2Hzk//L2L9rlH+flCkGmr/FMlzX D6zggCxLAfQnxUXtE5bUdfMSQwbV2DR2wAt2rxXzi6fc9sBaDlDEXuHVCv1LEPClIB8NXR B+9IF8JcCDQvKDF3fQbV6ZN/J8bGuGI= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=nsleZO40; spf=pass (imf15.hostedemail.com: domain of chengming.zhou@linux.dev designates 95.215.58.188 as permitted sender) smtp.mailfrom=chengming.zhou@linux.dev; dmarc=pass (policy=none) header.from=linux.dev ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1716541065; 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=9kGF9w1QUnOSltohj+L0P/TzAsAcBq0IIlZW6mywScQ=; b=1ZeiWACtjVqLQCxcxBQrL76FdyhS7U87bLKXNFnoDwGP+hLLLQZaR5p1tozVmYWSqBCkQV 3p9MragOz47TUqKrzeMUaavQkkzcK/gkjEbNbO+ojxB04VriaRBpQnC4R2UG6rRMOmJmGH FAuksjvO9rIX9lb0Bbbz7E+Mm3z3YUQ= X-Envelope-To: linux-mm@kvack.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1716541063; 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=9kGF9w1QUnOSltohj+L0P/TzAsAcBq0IIlZW6mywScQ=; b=nsleZO401TgVx5KF9wb+ceO8era7Jem4f+cMSs9YNzbTHmueEL9+9Y9c8sTtLrNEBtJsGh TVWPzIMkfKyekJKQrQz94vOH7zwFzGNrq1TfyoiswZIpfmVgHm/fUh5BoRL9zHDQe9LJkH BgwGtPqzyKjQ5I8hRzTnr0ocAj0w5Xo= X-Envelope-To: hughd@google.com X-Envelope-To: chengming.zhou@linux.dev X-Envelope-To: zhouchengming@bytedance.com X-Envelope-To: shr@devkernel.io X-Envelope-To: david@redhat.com X-Envelope-To: akpm@linux-foundation.org X-Envelope-To: aarcange@redhat.com X-Envelope-To: linux-kernel@vger.kernel.org X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Chengming Zhou Date: Fri, 24 May 2024 16:56:52 +0800 Subject: [PATCH 3/4] mm/ksm: optimize the chain()/chain_prune() interfaces MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Message-Id: <20240524-b4-ksm-scan-optimize-v1-3-053b31bd7ab4@linux.dev> References: <20240524-b4-ksm-scan-optimize-v1-0-053b31bd7ab4@linux.dev> In-Reply-To: <20240524-b4-ksm-scan-optimize-v1-0-053b31bd7ab4@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=1716541051; l=9550; i=chengming.zhou@linux.dev; s=20240508; h=from:subject:message-id; bh=B3mWul1z83IaYeQ2cUT6DdRB2E/1FafRRpZB8x99BtA=; b=nzbFXMDobe1UukjngEHFuUwYFMRq/StBqzcrTRZ6CxoVvEgcltAoBkvGjF5A0L2B94mAqC+tM 3OkiFr8H+y1DAWKpNEe8YR0LIoUUYoc9WUzqfX4EpwozFF5S//xFomx X-Developer-Key: i=chengming.zhou@linux.dev; a=ed25519; pk=kx40VUetZeR6MuiqrM7kPCcGakk1md0Az5qHwb6gBdU= X-Migadu-Flow: FLOW_OUT X-Rspamd-Queue-Id: A61DCA000D X-Rspam-User: X-Rspamd-Server: rspam12 X-Stat-Signature: xk9h8g5bqtncp6f95kjsxrtqgfty8kza X-HE-Tag: 1716541064-595632 X-HE-Meta: U2FsdGVkX19RtR2xFz2as52M6liYbOAByqboT70xP1HiiUmcKiYCXn9PYWtaLpB0jzAv/tckBtb+emSV+EdcNkhAzcBmp0JMrG50rjfD2U5bc+dc+YkSh0WtPV3VxcQZgWXiDYyz+49UrqOEwqbx6+XFisrTluclkPBqo07gZuTqQazfdbi5bVoyx98+lPQojujQZ0qFIlgHoLms9XyIGFoE7bopRo4fHq5hzyP8Onb1i+UFEftwt4BxmQh2XAWoIrZC6i1oDtHwKacSKL/gzWMOp8IA4zUve/f/NS9koyOwGQy350vXc5NQWiLVlq+i4iynFB2QN7Qs93RtaHBHWLBMkN5l+PwF7jCDLvp01dUYVSjfHnRINPi86mIHzutMF/uvJPTsM8aO/j9kHTZEaKKUNz4/V+h7HKCGmIRIPLxuvrIB73pWBxnN/yAODKsBYuR1a6U+4s9TnH/LLc0nhcukHGDTLZYP3Qzhg7ACAHg48uq6WDvF4Hrb+lvSG30Hn5u9MVQNLIc3tPDNViKPcBuIfB1w6/14em9THpXOowzMX509ePFWfa5azy4LQpkm+cR1iyVU24Ku3+JMKcTpBlWN1HAvzrXdyRvwBLTkjI3BZUVkbII59u5qM2oW8rMmeo7aGp3xRMau6w1nAU+C5yIWkXSbnb8f+orIvtdSf/JtpJObPu+xHtWzlU/5PerPUq2xRMdlwP0/1BayhcmuKFRoEtLZtakCvIo056MS+z9xj5xwgCFeQik6kd70dt0K7y5y9ONQkTczZ1TEudMpWXdgqFG8RP/AnLgPnJQ6uBQOcsr062Y3PFqW1ZpAr8i6u5SCu/fv2x1Lkl0pJamolV/plEUF4Vp3j3IEhfjPMLpj7a7wG/YcPxCoAMPcTwqXtgs7aTy+JYV4nBDQqgEyMo+gxjOgqKx/wKvb5VVco2Y6CUuHMQpAbTWZuj0MpH8pKLxYwZJwvQyvah3BDPH lH+6k5mz 53XPdN3QdqoDpjUknEVHmK8lAFl3gl7iT6E6i8Ygxlm8uQpomqGio7Lviz67GbNYWs55YZPDSJ3XshNidy8KEihFk9ArPO/zZfteaxzldSwL2RqtsyS5Ken+lbmlvc5zI9f3pkTDmOqzyknE= 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 2424081f386e..f923699452ed 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -1660,7 +1660,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 || @@ -1687,33 +1686,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 @@ -1765,25 +1757,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. @@ -1804,17 +1786,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); @@ -1828,16 +1803,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); } /* @@ -1855,7 +1824,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; @@ -1879,45 +1848,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, @@ -1955,7 +1886,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 @@ -2064,9 +1995,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 @@ -2111,7 +2039,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); @@ -2127,33 +2055,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, -- 2.45.1