From patchwork Mon May 22 05:06:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13249771 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 12ACBC77B73 for ; Mon, 22 May 2023 05:07:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9D6CA90000C; Mon, 22 May 2023 01:07:39 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 98409900002; Mon, 22 May 2023 01:07:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 84BF790000C; Mon, 22 May 2023 01:07:39 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 76290900002 for ; Mon, 22 May 2023 01:07:39 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 41AAE8044E for ; Mon, 22 May 2023 05:07:39 +0000 (UTC) X-FDA: 80816708238.15.B1779BB Received: from mail-pg1-f171.google.com (mail-pg1-f171.google.com [209.85.215.171]) by imf01.hostedemail.com (Postfix) with ESMTP id 6999740006 for ; Mon, 22 May 2023 05:07:37 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=jgMP8vdB; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf01.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684732057; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=gZz+uQjmpOdIMxeiaJgwUz4BoyhUknFLXJa8Z3V7HsI=; b=b807Ked13KXsxrcr7V2MFBDaO56YaWA1hBPGTfJM9fc/9CNdoNVoZIW4/IYTSxQZ5P6HIo U0DrBKKPSULdO9+7S7fNfrQYET7+C//98HMwIho6cu1sL7XVbIWRsu+qGCTXOp4rj2sIDL GEwbkHQHqlOvDN+AT8GYJSOKtMXvz+E= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=jgMP8vdB; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf01.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684732057; a=rsa-sha256; cv=none; b=rilqJt3ZBoylxapt+SpY+Jqxscl8eMLU6t4P/jsDytoNW1+KPaJ6vW5vgp0iUEhihCQok8 QAUaoWH7mpuT+22QNFet/9hKw1f8KJOGelZa3n5pD3fTKfDBVY+6eL5Qa5CoMrjgPuJwSd cy8Yj0MOe14aPtDWqLjVhzM/eJDv9mA= Received: by mail-pg1-f171.google.com with SMTP id 41be03b00d2f7-517ab9a4a13so4978077a12.1 for ; Sun, 21 May 2023 22:07:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684732056; x=1687324056; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=gZz+uQjmpOdIMxeiaJgwUz4BoyhUknFLXJa8Z3V7HsI=; b=jgMP8vdBmcOPewxDkJjBZQcf60lixgiNyhCEEOeGGUIpPNqCfsdnSzzeIL2MICM/0R dmJuRkdPDnNnSfKA/dr8EkxfvxBIxP3R4j2iiulIlRGcVDmX8Lct+JSE/lMFq5EGDBJD MKnUiIMoKHSCObK01IPby8K5It8XOEKZYIVlGoZ/mgPiqAD4vHLsmTpUhZE3oIODEi3b gvn0IAyhVkAuotI9HrMW1aiOaWcC/Lor8mMrbNnXu6jNXIDwgJtEi3y5StnbZsqWkZvM nF9BxiVrMtuDUA0UL2yAdW5NJdF+KXKc+Ue8A0yBVtprddy7h6bpFr1gPiOXTD9l0MZY 9rFw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684732056; x=1687324056; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=gZz+uQjmpOdIMxeiaJgwUz4BoyhUknFLXJa8Z3V7HsI=; b=YxKQnTEXnoIGbysXqK/PUUwVAn0v26zp9AbDGj8iuZOei4GmRQhozAYbpsdg67aOPB s2WSZhTlyPqITrIN2Urpkn54OR/moy0rgkeniURpyXslQ5LicKDq05t6YY92oMG8M2H+ YWQz3icUhDGjbxbNGYNqFch0VAEP1unluqrs6O2JN6kmrExPfb38OKcL5P42nUdW+vGc cto+khir7cXCOBG269Tred3Q3/OItPt7V8/oJ2FKqgRCvzJOKp6VuderdNYQz370WwPr jea0ST6z2WndiXWMehGyEJhg1xeF/opBBZL/AiqmeRMZ7yZC0P7selbtPJU0N9mbsCPB kKdA== X-Gm-Message-State: AC+VfDwrLfzFKz9ITQtYCRoAP7fY3RQT7kFIUFgNADJUxioZuv8pPIJ1 pFcQSOEK1UQOrDLgOYUMQVQOWw== X-Google-Smtp-Source: ACHHUZ7kqirc8A3D4h9wAwED0RDK5kYc00X56oQezZL6FCZscI345O1qs97um4cy07jU4YV8E3R45A== X-Received: by 2002:a05:6a20:440b:b0:10b:e88f:598f with SMTP id ce11-20020a056a20440b00b0010be88f598fmr916141pzb.51.1684732056314; Sun, 21 May 2023 22:07:36 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id t10-20020a62ea0a000000b0063b5776b073sm3247519pfh.117.2023.05.21.22.07.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 21 May 2023 22:07:36 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v3 06/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately Date: Mon, 22 May 2023 13:06:52 +0800 Message-Id: <20230522050656.96215-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230522050656.96215-1-zhangpeng.00@bytedance.com> References: <20230522050656.96215-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: jmi9qsjywib4werjku8uy7uhgdiwob83 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 6999740006 X-HE-Tag: 1684732057-204487 X-HE-Meta: U2FsdGVkX19s3V7YvaTSS5MkX9pYJh67uvexlsiZJHLR3sH3KEY4QKVVmUwwokeDHPfB/xrzPViiBRNf7724MfX7ylz38YGl3RrU0LudmHY2fTuYvx4f6RLfeoQAvFXlNxieWC2FSXTS2XLMJSOM07Y+zokm36J119j8Hn/hO61cSt2DOwbrRb0Iik7zdMl/UFKi692CRlqsT02vHZItX+nsGsJFE43+cKg1+jwzobJIqqbjoscLgUSRzkYqDXwsfl+ElRT9EZf0idlB7Sd1e68AFdIn24TPdkmi17dGnfY9yxPTWDoX64D+eQx8VQVVlAxdGwVyYy+Lu6ndAUMTlnnVWW+a4kt4LT3ATQGxk8jBmV7IS4o0C8c96Jp2fCDhx2WwjppR+mmnaoR+eD1oAdtLwUf8uj6WUCB39IF33/VdtWN33bwh+RTbyzwpxOQvEtoUzHfBDWMLEl7gwGilt+TQoq50Pfy6uWL51dW3CHZp7IkAamcHAuX/JW98gbZOO4TJmvV80Ypp9AHA8GNkEQhM65bPQuTDzku95gG00SusAdRDw+nmaiwSLKovfFnqK8t+j0mHfCsXsq2pOB9rSXMRxETpyuh2Sni0pEZlbb7m1xP7LXSrzWaPTaWahyirhVKqvnQaNAllXmBy6cWye+1Qjm9QmVD5Ud0hNR8WhhvX0aGZVBZuaRlrZjIOHRWV7dOjRNdFtyTqk2zlpPluHSMzeqUrX6eveYQWEgv04Y2smVf6fe70K4U36/uFtDPc+4SdhEWRRIFZfttd9cZQ8nzLzzxipBP+rhciWl1rCk3NTgx4BWWs5sHPpq3zTH8SSsbT/yE2osZWEjcQbbPhSiD1PrQnWvxwXIxQu7IyUWJkUrwZr6d47o4Jflu0pDNIAOeMLQrGTCuIfYxcnAZfKchrQEEYCY8t+t1gBBalBBHknH0o9ZHzOccD9l/UXdrOzYoSAq/qgBbvtYF2X28 3CnkUtRc gT2Z8eqXkyTQ0PIdM00eHeiQEQTCbrLC7hOb25ySh7u8YEFDX00782oiRXjPN6ZFsRkgtXNDP5ijmP2R1+ue/hK838tsxBU9EqR5lTl7F8CB4BwKXzm8+xr8/MYO43C5VBpTVlOD87fLSGGG00gRrHGbStcUuk+zNGY6N24nICZEvNzGj5jbKLShs/AKHpQ9sFLVakuPCvOUWf9dAFPjBl7GueNpreAlpoI9OhgDAzGMpiFdvQbmDj2oZXKxK72ozvoKzP9wXFtmnC+buEnzVsSMhaEH1JMcOCw5WY1ubrydat6G4vggSXzROpD0DXY5kGIF44XUUHOgNmcXdpjn6eTxoTkRrpKnikinh0wPdrbvoqLExTnMkBJ+V+f/CdIgBcnSURv+T5uRWiBSBa4rFYO4SIMp3LaKyuJ16iw+b2Hn56Jk1sGhSH1UHeHRY6lHbmU6NZW9MucUgj3Q= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000655, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: The previous new_end calculation is inaccurate, because it assumes that two new pivots must be added (this is inaccurate), and sometimes it will miss the fast path and enter the slow path. Add mas_wr_new_end() to accurately calculate new_end to make the conditions for entering the fast path more accurate. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 34 +++++++++++++++++++++++----------- 1 file changed, 23 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 562507979a4b..0550a07355d7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4297,6 +4297,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) } } +static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + unsigned char new_end = wr_mas->node_end + 2; + + new_end -= wr_mas->offset_end - mas->offset; + if (wr_mas->r_min == mas->index) + new_end--; + + if (wr_mas->end_piv == mas->last) + new_end--; + + return new_end; +} + static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end = wr_mas->node_end; @@ -4352,9 +4367,8 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas) static inline void mas_wr_modify(struct ma_wr_state *wr_mas) { - unsigned char node_slots; - unsigned char node_size; struct ma_state *mas = wr_mas->mas; + unsigned char new_end; /* Direct replacement */ if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) { @@ -4364,17 +4378,15 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) return; } - /* Attempt to append */ - node_slots = mt_slots[wr_mas->type]; - node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2; - if (mas->max == ULONG_MAX) - node_size++; - - /* slot and node store will not fit, go to the slow path */ - if (unlikely(node_size >= node_slots)) + /* + * new_end exceeds the size of the maple node and cannot enter the fast + * path. + */ + new_end = mas_wr_new_end(wr_mas); + if (new_end >= mt_slots[wr_mas->type]) goto slow_path; - if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) && + if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) && (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) { if (!wr_mas->content || !wr_mas->entry) mas_update_gap(mas);