From patchwork Sun Oct 20 02:46:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842955 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 CAD5DD3C927 for ; Sun, 20 Oct 2024 02:46:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4AC8F6B0089; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 45D8D6B008C; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 286F66B0092; Sat, 19 Oct 2024 22:46:46 -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 065D56B0089 for ; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 38150120349 for ; Sun, 20 Oct 2024 02:46:33 +0000 (UTC) X-FDA: 82692442350.26.93CE1AA Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf05.hostedemail.com (Postfix) with ESMTP id 29DD5100005 for ; Sun, 20 Oct 2024 02:46:18 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=g38MJfAp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729392283; a=rsa-sha256; cv=none; b=6hKHKHodtMW9jxMpcLj+f1y2R5tmsw3CFnkf1DQjoCuNZIYUPSufvkTEnemJ1G1Hefj8mQ yK0Z4Ghhfa6+lMXtTMwFWfOrboRWkeA/Qz14uxDPelzLhKiDIre/Xt3rtQ6BFQAlhaSCYZ n5/7NcRtmJRrdkDc0VPeehZhlYR7j9M= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=g38MJfAp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1729392283; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=w2Czo2WLSEk7CaIld7JKmGh5vIqrIFIPXvnO7KiDvTViD4jJdmvtdIePWmi5nidfUBe7pF 3sz021NBHBLTIvaPDiUFm7aWmgGtU1wYaCwA53IXBZe4jkFurDYuFahN0uYt45oft9awd6 1btHc+miFOq3ibPD4CvzqqPY24IDjLk= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5c9693dc739so4319201a12.3 for ; Sat, 19 Oct 2024 19:46:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729392402; x=1729997202; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=g38MJfApkTUxMV60aV0R3l3x/sABz/hY7zRr98uEGPm/oiZpGv0E1fqC/u/KCecPKc qsagwLMhy1dX4vIooRZ1uw59ywvGzn5ldCj+Zjh0VZTJw4tlo6PAR0ekcMwXT9NnDrtt 0dpYIQdfca+qqsKlkPEGxnrRr0uPINosrZxeuiN/AbJe7JpFPiq0tVqx8eM+SOrr6BL0 0WrSnW273AaQMVmWE6o7RPxrBAvjw0LxoCD4wn81Jys2QipmxLfiOTT2o1+I8PCM2/2h NZAhTfTFUqKVxrc4HSYPif0Vvau1zxxqCpARBEBHrQ2VOP403iolEAPWDgRcilHTfw/s 0Rrg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729392402; x=1729997202; h=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=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=Rl8ZKuexhPOSi5Olcez+DNjk1EzY7cezds027TdSU6t5fSJbkyKASfm19Fnk9q0aTm XrtvdYniOQpCtdNIhJn45rh/dFOjRipqPLxFkX3H25leOxBctzwNlbZK+G5jfu2ncY8W PQ7LiLhPSRWi6dqHped0sx6ZYcUJzwGoxk4+uirHPD3sZnbIJzBeiWvY+qqpMcB84wua gLJJZJX2YuiBExVTef0yOz6cAadX98XFRfukVCyIR0QhQH51x/T01xNvCew0bAqChy7X MGPO8DPNURzPDq0o1R2CVP2F+WGw4UQzr72UmNrMZxVCgyZbEvJ3IvMTFrsQ/wJdB0N5 ZLuw== X-Forwarded-Encrypted: i=1; AJvYcCUJ4rH7A10YoAS5IZKsrNd5dHX/1qTUpQpCu5dLWXUP6JSvSShF7JahXD/lx9RVhQSqKTuuXWEoGg==@kvack.org X-Gm-Message-State: AOJu0YyyjlihVOAGIHiRR0MW1lZ48syUcBiW2E6k+P4Xb3bWWUxwC/8g xMeRpv2M3zXMXJBfvYmo/nJiH1ZoibrOdo3CxAAj4dRK8BAgdp30 X-Google-Smtp-Source: AGHT+IG9TU6YFWoe8nI1KvqfcEts+0UB9XrQ+D3X09pG1eButUKOg+cLAxSGLd/JbnJTIbIDRMcy9A== X-Received: by 2002:a05:6402:13d6:b0:5c9:218d:7071 with SMTP id 4fb4d7f45d1cf-5ca0ac71049mr6497448a12.20.1729392402408; Sat, 19 Oct 2024 19:46:42 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cb66a6d798sm433292a12.50.2024.10.19.19.46.39 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 19:46:40 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH 3/4] maple_tree: use the correct min to calculate split Date: Sun, 20 Oct 2024 02:46:27 +0000 Message-Id: <20241020024628.22469-4-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241020024628.22469-1-richard.weiyang@gmail.com> References: <20241020024628.22469-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 29DD5100005 X-Stat-Signature: zmxi3e3z7amrzzasse6p3mt8b4s664j6 X-Rspam-User: X-HE-Tag: 1729392378-520325 X-HE-Meta: U2FsdGVkX1/aErq6S322vozNdkuEOA8nF2y6HXQXTEYY1p9dIrln49PXnqvM5cL5yxe4HP1GypxZlaxabLwgjoyZJq9F7KE6+hoLcUc29P8z0ovkgB+RlcYWzizoNTR8pH5MYETjfHUJh8zZbrJbgGDmpWlqTWDQkhojNLjLuJlrk4kmxB/rjCcEHoFJAKvatbHFTBptsvghAYOQhwnhrBlgM3iIiaRQKtcKhcvKJAF95qEqxgDqx+Kyaru9DQf6TvRLeTM5wVHLBLQzBau8U7awrJNbA6tMa6dz50jJafAHiR9QcIpnIGhof3krz62D3KnLfsd7cMyT5LWq+A36+hIVRS5Mw9yR7k7Wzv9Td7e2hLN1u3qXClaOQ2iCEM9pCFxDwF5LsB5fE/9JJZueDhK9OX+xKEf1U/IzO0UZVmCCWsaZSmPCkvGeYE8Cjhsj85P/kSHPS9v3ERbv4cTZAQGf/sA8unN6MfK9Jr6CtHOUSKdesNv2ArtWj2zcZYr1SjhTpyyAx/WU5D85NccwT0RSN0RlG3U9DAI75qVB2SvWlBpVpUFm7Ez7v+Vhw1G27Q+esWEu4GSE30TbMITxtnDR5VbmVHmts4oDaNQS6FZBHkHEHt6fUQ2Fk+U7dTD46BRA1SBAIJAiD8gtPPu6Cko+cq6q+Qy4iZoD+mvsmWvIpS3D+Hf4dPVxX43ARC8ybwbOZmhyRDJYRDnePZ5YU/XmX1RU2MRlLDLeidudSWpvAEI684b44yEhjtDNV0dBRs8KCbdiM9ufdAT749axCxfVoltOgT5acEu4NHWMIu//CtFt1AQXT3wn0ThR9GVSIfzb9puyK/XQVAgy8LjtXFtg2f+k7NIEknhroASUw4pIXJ7Q6YaGeWH8UN2qBAJqjk5ASD8z8JuPcSYxXxR//Ik6w5oYBGqLZnoVFuT74n9+aziN/5bkZxN9FkIPnTWpE0SEeNqv+D18otu2Lck bdzzX2nX FjN051JUe2kQ9AWmVZ3gK1iJRYeHvJ3fr4/7sUqwd0jcn5M40/obGTo8thfrZ0tq/jnbTYXOf0ce6MtE8DJFcaUIMFEcYRHr9tMKvdeVSv9OPxiI35vrddpyhHCoMZXB+kc+sWakONKEtGIe5BYU57Dcqt+XoE6zHCV1Y+hZU9es9kydif7/E7EyRGwcYuxzUKgCaefE64kYaf35l69f8pH0CW2aaeKPGTUXhNp5bkhx/mbUCti5+Zut49rHGk92ovm2EfBO25aYbd2pE7NhXGQoxRcxuxLH0ZJpPyD3mFCS0mm1XdxtV/b2Lc3icZuUST01aySBnjOUdDGhr2kTbY1CCmOMfktXjvrn1WTsvpBMab/ADgerhF04Asvz1UwhP69NAFfAS7TFymbAMuW6re+IbxFhpWM9KOrHVxqlcipL19rkErqlBiGKMmdyk7/P0e+gCIvGymVfRiouaVmSJVXupCkmvzLuJjCXe2KvdA6MmiPWB8DGuInWSrV27Oekg9XoH 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: The check in mab_calc_split() is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min. First we may encounter a pivot[split] smaller than min. For example: mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min). Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect. Since we are now calculating the split of mas->node, we should use the mas->min instead of prev_l_mas.min. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 894dc5e9436e..c2d4b188646c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) if (mas_push_data(mas, height, &mast, false)) break; - split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min); + split = mab_calc_split(mas, b_node, &mid_split, mas->min); mast_split_data(&mast, mas, split); /* * Usually correct, mab_mas_cp in the above call overwrites