From patchwork Sat Nov 9 13:44:09 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13869658 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 88BB2D5E36D for ; Sat, 9 Nov 2024 13:45:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C1F366B0089; Sat, 9 Nov 2024 08:45:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id BA8E86B008A; Sat, 9 Nov 2024 08:45:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9FBEF6B008C; Sat, 9 Nov 2024 08:45:02 -0500 (EST) 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 7EB136B0089 for ; Sat, 9 Nov 2024 08:45:02 -0500 (EST) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 0EBA181229 for ; Sat, 9 Nov 2024 13:45:02 +0000 (UTC) X-FDA: 82766675712.13.36FB38D Received: from mail-ed1-f51.google.com (mail-ed1-f51.google.com [209.85.208.51]) by imf11.hostedemail.com (Postfix) with ESMTP id 2900040010 for ; Sat, 9 Nov 2024 13:44:12 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=a8vdh9Oo; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.51 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731159839; a=rsa-sha256; cv=none; b=pFANbBEZ1L3JYb1gML3xTUNcaaKTcm4SZjI+aIb6ZMowu8ab6v3vtn4wrMDZprfugkBiqX PGfYEIWoy1MZYpBdm5u6vJlOnEpTtbmjt0ycS32pz4qhPPhFrFDMjLc1bgdp3QDxb7TbCd n4Bx6hhS+4ZfTt26snx/KlJnuP+T+x8= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=a8vdh9Oo; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.51 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=1731159839; 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=WTXqgKb7N2Y0Eb4fPJg00gjI98gr8YsKMOseVjgVDUY=; b=C1hRSCdP/jab1A/cgtXHOQb+tlWikDaz5lr1/87jd3h7cS0KCbFQ25Vy6GlJjXBLpH6rw1 uJMwdhrG8GWJM7QoyWxkPmj7RTN703fTnGDPpUOt/tfBUHLSFvNZeyZAGl6WwHNyiQmAAi wvYlbhx4+3UAqL4EoVNeQ9wOjuYbOCU= Received: by mail-ed1-f51.google.com with SMTP id 4fb4d7f45d1cf-5cec9609303so3430736a12.1 for ; Sat, 09 Nov 2024 05:44:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731159899; x=1731764699; 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=WTXqgKb7N2Y0Eb4fPJg00gjI98gr8YsKMOseVjgVDUY=; b=a8vdh9Oo0ZxPwORR8BMMsRB21Rk9eM9Hs3xfYhPNUKX9QKV+C3ZeLVTsGWnfiqR6va V0U6OXZcj70cePA7oYi9yUZ2wnfYGwt+15XGnOC4wtoXze1GX880Mci8KAyccUT30kgE ACwvLicx95TKXmbdGxyP2+6N1rNChcRGpLoGGTDLPJC//cX2LuPFJQVsPxgwepy1SlK7 sS7v1W7dNO2dRmkUJ8MVkFFa2yH0brS4Y5BN+PTK2JLGtWOWyN+aa/EUZRh7MpugTfvM xe78+HxsKovJQD2WeYdclHJDqizy7QVV/579mIfLQhwgGurUDC2e3s8EUQMBp1h6RHYB Ge7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731159899; x=1731764699; 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=WTXqgKb7N2Y0Eb4fPJg00gjI98gr8YsKMOseVjgVDUY=; b=dRrL25KMcHJRPrtShEGBigQI0ZV3dZ/VI1JYzFo4jLU3+PnM8UxI24IPF+5jtTN45q f1VS7xt6yFKkSPsTn+gOeeYc/gchC5nkh5aIXO45MlK4oJGXi29dZxMJ/csAQUiIjmam nxt6gJTvhcG9qQmuVJyB9DPlBMhjvzeUZy/Lh2mWgjDRhkHf78+cn/S8a5t5MgqnlauL hrPYoBpJ89GSoVC4e//aYx+3ebdQZhJn3q9FOYFJarjCfilvSFMhfIdLMn6aqq+waqOy BtQM0NH1tK1LRyKt4KMCzpl0X18MdjmjxNmBapzZfUXAK/GW66qXZOhOMDGyW9eRvNKn Bvyg== X-Forwarded-Encrypted: i=1; AJvYcCVuyj6XgzENh72Pse+4PGuIqSebEW/YRE2T6YO964kihkxad7cSxULnYJoA+ukz6MSZBso1Te82wA==@kvack.org X-Gm-Message-State: AOJu0YwQcdLAHedSVFXjzo4BMlhBvwBTiwEuBXDLOyiUX48u699OiFtF OfLOkZo+Y+wFC6O/v4XAADJ/SVCXABjjAQhWheKh6NpiNn3wju6dEfEN4g== X-Google-Smtp-Source: AGHT+IGrsLwOEhWjAzwD5QSeShq1zehXU1jwcU04tN8bYBHBtD4k2kLpftDTJXdjvDxIWjBM0cFN0A== X-Received: by 2002:a05:6402:1765:b0:5cb:7295:49b with SMTP id 4fb4d7f45d1cf-5cf0a460fcdmr4221308a12.34.1731159898591; Sat, 09 Nov 2024 05:44:58 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03c7cafasm2959658a12.84.2024.11.09.05.44.52 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 09 Nov 2024 05:44:54 -0800 (PST) From: Wei Yang To: Liam.Howlett@oracle.com, akpm@linux-foundation.org Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v2 1/2] maple_tree: simplify split calculation Date: Sat, 9 Nov 2024 13:44:09 +0000 Message-Id: <20241109134410.31792-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241109134410.31792-1-richard.weiyang@gmail.com> References: <20241109134410.31792-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Queue-Id: 2900040010 X-Rspamd-Server: rspam01 X-Stat-Signature: pz7kw9om5t4jfk6yrpg57b8xaz56wzo1 X-HE-Tag: 1731159852-415575 X-HE-Meta: U2FsdGVkX1+vG8II5vbDF1VVBKuhn+WKe6aYkoelyo9xoaVmNj22yGCiyBM0LOF9bLNsGYr934DL0KksN6UkTWAzh5/A1SkvljsVaEvtb5ZwYqRnToZXN/wyMGgoUUxpCwwfIgmrjXnJGmXrr74HvoloI/V1/9BRddD4cZ+wWaQuli3DbSwA7qjX0XaIKF9p9UO8fNgSKfdVQXzCHww33ISRKLrtWes/YKFEFnTgCBcY59eXYnbYLkQJAmKjXN1GxmtkIzUsC9Qsv8X+e5PqIc8AwDKS/FXsDtJS0pjo4s6pfFLYCIELHLcBnyXXM0Y7bRYEWspwQozuLfYIgLxSJ5N9wII6zJ9G9tsZHyn9CTzOx5S8L2oacX6VhzRxLblJxUXiLO8TMMGPbzrv1jm6F5FnOtM6imT7Hq1i5DBT0P1jGo1JzMkBHIIrDoI+UlR84wmEC/sU0803eH1lcFwK7WVW4+Ce14M0ebOhMfKAeIpkBaoZWYgsQXqbIumRg3FE6mF154RaEF+CG5ZR32wTP2CBr75lqEANQZjTyD670+HY+nKoYQnTHstlE2tHx1veVd/zRIRMhAqxRtN1XazEtKVUQzzmR0UZZSIdx97Tyrf95E0wnRNSQA1xnLIJSyen4jnLKZ6WNZ8Yh9DE6ewl360pwNMHru01VShL5qbZbscArq9szNW7JuQt37POxI0svxgulGPj4KH7crBlO8L5DSY6KSPtTF+d1GdZ7okcJzr6Kr74NlGd334BJ68DTHgDX9wyKQinA2vdnraDrZ5B6yRaaJO6SJ6A1HbJoL5r5a1VIBd8w65zKXa68LOSIcAJ3BETHEdMaLTSp1y++P4X5he10uWAnmZiuZKixvwuX6yb/SIO4loGmdijnwao1aEF5XjfCuvipxhJWCUkj1PagsueVvNlfchU9JdQI0A8m125uqWucZAa0docMzunDJw6Dp9AUUrUL48PxtD02F5 NVFjatWw nqxs2dMh6Xb8M0ZHZsq1ghTXK3xeB+9LoI7bVF1tFjGqW697jSWS5b3Qg3/DizxMb+hJstlbApZQizRm3DgRAI9A1ZTErvllGKLU8fwRfICUXp/jQI5naBETwOZipRkKxR2KkGeeumGyAPJjKBCrn5Z7v9H0enJrJzj2qW8jwXdKIE7eempfQ5M3X1vmgkQ72LAd/dX967qgJZfICDa3LxY9EFWbyW+4vtDsiaJNqNdlRY4PpDiNVzdHT4A1OzG90g650hZYLbKjBZJKyCbY+eC3qsr7yxdHCWl8n0cTGvg5fkxmzkumLz8HjWUSpM3nNRGqFe7SkD8Xr/+LgaB46RSlB0UlvoaYxWNTgNUOwxUy2JACRgLd+hmkrl+SLS8Wl+S5bgeee2GqPKiqZfm30q1SdSh/w3W0MVDOGDlilpnJq4G8A/zhQtRswAekd6GL5vRouVTTsKq/c9TYPHOJCAIlrWSkpErWo+EOGMXjYcFEHcd7/yYU1XFPcuklbG+6ly2BR X-Bogosity: Ham, tests=bogofilter, spamicity=0.000062, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: We have been too smart to calculate split value. The purpose of current calculation is to avoid having a range less than the slot count. But this seems to push too hard to suffer from jitter problem. Considering this only matters if the range is less than the slot count, so the real world implications of the calculation will be negligible. So we decide to simplify the calculation of split. Also current code may lead to deficient node, the condition to check should be (b_end - split - 1 > slot_min). After this change, this one is gone together. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- v2: instead of fixing deficient split, simplify the calculation --- lib/maple_tree.c | 23 ++++++----------------- 1 file changed, 6 insertions(+), 17 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d0ae808f3a14..4f2950a1c38d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1863,11 +1863,11 @@ static inline int mab_no_null_split(struct maple_big_node *b_node, * Return: The first split location. The middle split is set in @mid_split. */ static inline int mab_calc_split(struct ma_state *mas, - struct maple_big_node *bn, unsigned char *mid_split, unsigned long min) + struct maple_big_node *bn, unsigned char *mid_split) { unsigned char b_end = bn->b_end; int split = b_end / 2; /* Assume equal split. */ - unsigned char slot_min, slot_count = mt_slots[bn->type]; + unsigned char slot_count = mt_slots[bn->type]; /* * To support gap tracking, all NULL entries are kept together and a node cannot @@ -1900,18 +1900,7 @@ static inline int mab_calc_split(struct ma_state *mas, split = b_end / 3; *mid_split = split * 2; } else { - slot_min = mt_min_slots[bn->type]; - *mid_split = 0; - /* - * Avoid having a range less than the slot count unless it - * causes one node to be deficient. - * NOTE: mt_min_slots is 1 based, b_end and split are zero. - */ - while ((split < slot_count - 1) && - ((bn->pivot[split] - min) < slot_count - 1) && - (b_end - split > slot_min)) - split++; } /* Avoid ending a node on a NULL entry */ @@ -2377,7 +2366,7 @@ static inline struct maple_enode static inline unsigned char mas_mab_to_node(struct ma_state *mas, struct maple_big_node *b_node, struct maple_enode **left, struct maple_enode **right, struct maple_enode **middle, - unsigned char *mid_split, unsigned long min) + unsigned char *mid_split) { unsigned char split = 0; unsigned char slot_count = mt_slots[b_node->type]; @@ -2390,7 +2379,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, if (b_node->b_end < slot_count) { split = b_node->b_end; } else { - split = mab_calc_split(mas, b_node, mid_split, min); + split = mab_calc_split(mas, b_node, mid_split); *right = mas_new_ma_node(mas, b_node); } @@ -2877,7 +2866,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, mast->bn->b_end--; mast->bn->type = mte_node_type(mast->orig_l->node); split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, - &mid_split, mast->orig_l->min); + &mid_split); mast_set_split_parents(mast, left, middle, right, split, mid_split); mast_cp_to_nodes(mast, left, middle, right, split, mid_split); @@ -3365,7 +3354,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); mast_split_data(&mast, mas, split); /* * Usually correct, mab_mas_cp in the above call overwrites