From patchwork Mon May 15 13:17:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241442 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 6DDE2C77B75 for ; Mon, 15 May 2023 13:18:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 013C2280007; Mon, 15 May 2023 09:18:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F0723280001; Mon, 15 May 2023 09:18:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DCEB9280007; Mon, 15 May 2023 09:18:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id C6092280001 for ; Mon, 15 May 2023 09:18:48 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 76ACA8104B for ; Mon, 15 May 2023 13:18:48 +0000 (UTC) X-FDA: 80792544336.01.FA952BC Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) by imf12.hostedemail.com (Postfix) with ESMTP id 33E0940013 for ; Mon, 15 May 2023 13:18:45 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=IeSw9vO+; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 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=1684156726; 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=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=A+af5uFi/PbqcFHl1xK4zLaZP/oMsg0BOArLvoUAU53OPrQrW65FMMzr7XvIxwZR9o6d0T vyJS8VgPUiN1ecoQR0yuMhujjfebFJ7RFFPh7MPdkb5Qmwz82o9IZPX0qpJbaj67vk1uHZ FONaz6qo1LtSU/CyVLMoCVDWewo7qhg= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=IeSw9vO+; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156726; a=rsa-sha256; cv=none; b=wrN27Tlayd9TyM4StGnlRfa9RJ5sp/tJCNxNyeMW1fVp8DzRxk84fche+OUkJ/b9ZsPANz F3JEyq23IVedr+/yzUVAP2xDg38fQ1FuiQvBp2nN7rce0a1316q9c0Qb46ReLHZALX+vlt eQbnpCHmJFcMjwJQ8yuL+zbZ77AK+T8= Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-24e0c29733fso11445467a91.2 for ; Mon, 15 May 2023 06:18:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156725; x=1686748725; 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=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=IeSw9vO+5tUCyqhG3uAeGFw3l+kw0p1+xquqjvHnxWcTDJpp+QiZkleh9ZA4o1vRFP LFFQ9RUFpkMznTFDy38B1W2fNinp8wPwPa1vtTRBHgSp5UQx6f2PLig0LbQE8kmt6nO2 QHifAX+73dgUs5UZCtQTdz+QmY/BG7O+cWyKNZ2SpAwB1jo34DRBYtzAt9oEuDSXwuyH FZBXRiFYlwH9i0Q+eZJosITIX0uZu/Fe1ibGzExVWrN66H/hxtWiiRn3gHzxcuvN2BUN iAM0kqw3LiFeiTNOMvkWinAY0QaMmwaZK+eQhVvcwmAFnAs1R0wdpBUmHRoT/A04NjMv 2I5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156725; x=1686748725; 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=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=jkkaZokUFmTkUueHbQncRDekWPxg2NC24X62DhSi0jv0pQ4bXLanuFz+JvBrOtxtxr liYm3PahSubYdjgmyCxu6aSmoDe6KcV0egT4SeGMBLc9dhdfBvM2rpxsOPFKCu/ylPXG 9s8yfZ8zqJqQS5coITkBKPDQTRQqPHL37O553GN8g+M751shBwuuej+35wiyP8v7VJfu X8Z9ffy3gZCu9iRgeJWxI6Nh90w5uOVbc2Y7laWAtD2e5tAg2HEROBH3d+pG6SI42NTy C8ml8cnLKL/n7GomsL75vGYxSlTPplwcEQXoeQLknLDRlRpcUGVv5hvDSDdWmyaLvXbg dygQ== X-Gm-Message-State: AC+VfDzEBvjGxMtZ0qQDLC89ex4n+WmOMZq+PIKAnQ7REIKUZUImIOB7 NWvCWNQjU39aAhiP3X8t01g4wA== X-Google-Smtp-Source: ACHHUZ7AvLcqhLLRsd3AKclUfZSzUVQ/4fh1rVvWJLa4GbZzqy5/Ip9c+kJ3AEJMnFSgRXXWzKoXXg== X-Received: by 2002:a17:90a:1fca:b0:250:d293:5d9d with SMTP id z10-20020a17090a1fca00b00250d2935d9dmr18534359pjz.43.1684156724763; Mon, 15 May 2023 06:18:44 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.42 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:44 -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 07/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately Date: Mon, 15 May 2023 21:17:54 +0800 Message-Id: <20230515131757.60035-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: b3g6jn3diu5w1sc6pe78f3bpimhn75px X-Rspam-User: X-Rspamd-Queue-Id: 33E0940013 X-Rspamd-Server: rspam07 X-HE-Tag: 1684156725-190068 X-HE-Meta: U2FsdGVkX18zGRz00Ow4l0IJ8OCNBC/6dASFECe9OdgGSC+F1IKI2QYQBYde5kiEnIWstRM9SfDHC/J+UUHRAQe/D/WMfsA4rHqaASlr5/jeb2ARjlAfg8KXWldo+H9g30C3IHH/55KAyWPyqEnS/gxFXweaMmS/QoSsCHV0SLcJmf/SD7243k/IZnBxTHeOEMx+QcP2Da1E9vlcy7QFyDaGEtCDIDYw0a0ApnTQ8cwlo4vJjdzOWqqn3ClJgoAVEFSTPU923gNWwKc7A7thlxmnAaIiNKycDHrE8sjP8TmNPtEOUD7Ch7NYaUy9jrfvsN5tlFcPj3XMQn/F4skm3y5nz9WPboXsRy1QXp8M0n3RwoOwEbevIX48xPnnib62FR8j+sIcS/DoSgIhujnQB28M9TJhvz5rJnekOeqlpCeQxUKUag9/cxwSWkA57/peLrn7ooxIzCSXFTcpuiTZLApCvfwd7HJJfFcb0rc5LEOR1WyF9cQJbaDVgkweWyjLF5MzDdQrO7x+ZgWDwBh09Xm0/Q14iqwSZ5YZjjSKLbNm3/hMBJyf3Wr+KrDQL28sEORIIkg0fsCdTCprWPD3PzfuT8R+1zEGmUCGJArMQoY9uPYp+G7e02gEtBdbNdihpAylaXH/ro/CX0PvrA4Hh/3vWMt9d4MoPuWVpfosZsVeNLQVlGtzym1nOjlgmsZogU27TG1L/+OzK0ausWN3Q08PpmY5mMHTRIKT0MhRlUVx0zKTS81/lB5XJeumayoiN8aqa2dHK1ALPjVumFMM1idiKUqeP57YfzW4IsbV4lgUcaJMzqGA2VMdQoFIjmUGw6rZYy5ivlnYLPXKJmUYSVktkI0Aq8Il/TyznTEnQQKWEo3G+9jq9xxdzdx7/0Ydpnz3Ane7sXwEok/nJpj6upTGePuCQUjKnHeuwgq1HkpURnQOQLTpf8RxLmHMNpaun7aDwtDAiXTnc29PXX3 fzr1Kqa0 GCAjm/F0Vio9KIHaZF0QQfc+m4A75CdC9mxXzsONNiQ0L6S9+esp1ZAKs1IgKyyFHn4kreFdzomFtxO4Ge5G8vXf4gED79E/+J3FqoaqdWkpmlW0/4ym17MWFdajnNa9pZkhklxkwoIfLSWge06v67aPB/Od9CXRxB+RpbCggAA0FlB1wuacoyzGNrKato5P1JFLYstBf9NiEm4p0f4D0kNL3ltQlaHHPxaMgZVumQ3t5QIhNaQ/bOvQClrl/CLXx6A/T3CP967mc3fJucrqFDxr3JnX7paav6rXEn6z2pWA0KGodJGhS/tmo716eZdn6Pe7MNRnUR7uBtiQcJunUnoft5s8ewCrgSatVTKGgm++0uXWKbeFTAIcYhLZ+aCorTorU96lJPGcNUxazmMJGxs3fEynkmC63T7+X51/xOYm+bhGoMxyPMl1LHuIAL3hVivvRpGSxTW9CbuA= 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: 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 --- lib/maple_tree.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ce695adc670ec..20082ef8c396c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4301,6 +4301,20 @@ static inline bool mas_wr_replace(struct ma_wr_state *wr_mas) return false; } +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; @@ -4356,25 +4370,22 @@ 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; /* Attempt to direct replace */ if (mas_wr_replace(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);