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 26851D597C1 for ; Wed, 13 Nov 2024 01:15:50 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6F5526B00B6; Tue, 12 Nov 2024 20:15:49 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 6A5486B00B7; Tue, 12 Nov 2024 20:15:49 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 545936B00B8; Tue, 12 Nov 2024 20:15:49 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 33F2D6B00B6 for ; Tue, 12 Nov 2024 20:15:49 -0500 (EST) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id A9895A0795 for ; Wed, 13 Nov 2024 01:15:48 +0000 (UTC) X-FDA: 82779303516.30.C08495D Received: from mail-wr1-f48.google.com (mail-wr1-f48.google.com [209.85.221.48]) by imf21.hostedemail.com (Postfix) with ESMTP id 8283E1C000E for ; Wed, 13 Nov 2024 01:14:26 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=kMoSSa57; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731460373; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=iADwcgNhFbmTf/XdDsDLQX9L1rafBGkyeAKw1Il+kiQ=; b=HgVMef2hRbBt+PZCX+MwSSmzYjyIaYRXGFRBcbSrMhAomwYvhZv6DlJNwWKzcAJTrrW+wX JAq4ruLokn8CSyYnQHfeYpkffYT0QElUgpVw+peznIgxC4GVIZkeDNKmdSM5IISq8Ju2B0 utDKCI1c0OtRQhj8jldgosbFFS8TlZQ= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=kMoSSa57; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731460373; a=rsa-sha256; cv=none; b=8Vefjawu4s3fbOxp+k01LlKEGhRMnUFg25dcJczJQD2jiMjlCIPpNUkaaYSkcxccRf2RcM kMJx2dIEx0uWQ+vitxMnjEjILwTMKCjTq6kyu95ylpbjYxl1RO4fepeGuAB2EWmI9ttujI tsC6DsUeTNrnxh/GNuanZoQ8KJxb5XI= Received: by mail-wr1-f48.google.com with SMTP id ffacd0b85a97d-37d4b0943c7so3942189f8f.1 for ; Tue, 12 Nov 2024 17:15:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731460545; x=1732065345; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=iADwcgNhFbmTf/XdDsDLQX9L1rafBGkyeAKw1Il+kiQ=; b=kMoSSa575nKUOBAG1evnvcUDUHtKeo65V59M1ZfhMlqYtNIquUqN/B8Ydeb3DrMCE5 YlqVLiGtJy6iuqNv2kt1teyTvNYe7+IVNYqLquZZT+NywVk1eCxKzC/2OHeuhW0Fowt+ ukYjueF/SnnVMhUc84zxWaOFIUS5CbQp+Witglt7CMUOovmLcH3AMPfi44Agt5k4sIUi XNtRJslwv0MPRmgDqtV6hINIrFr58Jci8mhr5Kaqvodb/tOlPHQ1kfa+qaBTqGjC7Iw4 sV1LhjiiEoOlSciViEcZglby9NbSslZqTXYToRsXoq4pNtHyPmObVDPWqD6slGax7yi8 5ymg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731460545; x=1732065345; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=iADwcgNhFbmTf/XdDsDLQX9L1rafBGkyeAKw1Il+kiQ=; b=P/jNDChWNz5X/CBszKZXjMyoczhK70UvySuoedhkb6PgagSVNLM5X2eqOoi+Kog5lq NST3ruc5IWir19aRZT7F0TDYNqTfHBPhdjl+fn4EppOjCErjzCGoKEW/WBlBqICD8rLR rMvP2jjTtxAcmI+WOVLFgcflpwWHW85wKhZqb+Ql9yufrf1VrK8JnzQQa97ubtT0wbUb PX9UkapUPsjI4CWecHciO/xRBPKt1+CJ77iQE0uTHHr0w2c96dhKP28x5HjKrj4AoqZn xCK5+MIiH0rRtqV5gRenm1Zh1jfEXQh3M+g0CpsIanTd/8EkR/MLQ5vQJDCl8KNHXRJR +R8A== X-Forwarded-Encrypted: i=1; AJvYcCWRyqUODmLpyejzbMMCsWHFMKjFBWaK5a61Ybozk6AxpNQCXhfK3qPnvqxDxXG+pI+nA6v09VjROg==@kvack.org X-Gm-Message-State: AOJu0YySpR4bgJf9l++g/o5Gok6CgSI9kS1XOfN479HlnI1N2TQxqKSE Df96bdC3sjr8DbUKAqDjUS/htii/EL+LEmrTt5nl3I7MKelyw/Qz X-Google-Smtp-Source: AGHT+IH6DJ7fe4qf+jzbui3RbC7ya9XRl6dXheVDREjs4MgHSyJM2HDvANunFw/AAuFE7fnieM5HZA== X-Received: by 2002:a05:6000:210e:b0:382:424:94fc with SMTP id ffacd0b85a97d-382042495c9mr5858544f8f.44.1731460544970; Tue, 12 Nov 2024 17:15:44 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9ee0a43967sm780865466b.44.2024.11.12.17.15.42 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 12 Nov 2024 17:15:43 -0800 (PST) Date: Wed, 13 Nov 2024 01:15:42 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH v2 1/2] maple_tree: simplify split calculation Message-ID: <20241113011542.lw5zzude7oo63rr7@master> Reply-To: Wei Yang References: <20241109134410.31792-1-richard.weiyang@gmail.com> <20241109134410.31792-2-richard.weiyang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 8283E1C000E X-Stat-Signature: k43j5u5pmqfj1fgrwfme8p11zwhhbap4 X-Rspam-User: X-HE-Tag: 1731460466-237261 X-HE-Meta: U2FsdGVkX181IHECY3b0DfBApw6Cbpcl+X4hABjOuNbn7X9pw71JTiBfJoYqLr7dG9YqAXBIXDNs71UtrRHK3IoBrjhSX4sOnp02NUbKIJb+OVpXYW70TBFdgtrDOH6nNyiBd3AHTa1rMoutKFEOllxsF3FXOjpPmBuxbZcGYglnaCqX7b+D+MWB3i/RAaqb5G6ViZdAZltuiEZdlN5Ph8sJk5mAq1xiN39QH88QaweVKzNdGj23umg7dwofszAcPk7ZCAfgqS5bV6yYsczAIlwChggBSA+/XUKti4Nh84Ts3QPWAlJd2wrG+sTTUYm5Gup8iRewTLmJm+0WYxIQ6jZ7Zf7yxvnCBl72xb6wvawLmh9t6osQkdJQVIUU0Tpul8+VVwF6a65gfHEY0HNN1LlVpWn+eRLSnMXspBTRA9XDJzciyHn9uwI+33OszAPKgx4H6So3zS5/W+4bOwFp0TFXkbIyMWvLAiXmOKJMBdBFL9UgzFjt2XMtgzYGEaB9tbYBgvHkBO28uE9ai00XStp3ptr7Lit7ZgXbaAfnJ4BgGBesApSXy/2XPzxTs7G7IO/ierBf/pJZltaFNnnoRAFmJ0b6iDz/oS8xzquYfwMfiiy7/Snad8JPFOhs6n3fZGw0g8BkTXci5qkjg4Bmp9U63hSrzvuWAnVUpZsDuC6YJa0zI5JmeMrGIHiKUW4jsT8bYvsoEOFJ5YdmMRVAmXjSOIJDH7r2MIpwhFfq7JkxCw8peB7A3S9OCDFmyLHh5eqNUS4uGb5xV2uTtApojfDOqvQ9wVKyS5E7Dqozd+oRGsb0RHoHIaAhPoh45Cd2FJLDRwfmQSQtzj4ZLcBZCPJz+4+aylO69WLiq3etv7LLVapvXKCCyjmd+cLGTR9PIyd8cwD3+6+WY2bOrLZl9jdm56LPXuboKk/JfOTtbHadvH3zS56AByJKlvWyNZNB+XIqPsXoQaWv3rD4NA8 rvkMZlfy DFVZi/Ia9XaMLaXtGCm9mtI/MDZZAUqQ6s5uQtPhp7tPDB7/ZNPOEj22aDafu6Ok+E5B5isDoSbO+uMgvjQdWmnAZg05PpIznZGhHxFGNY26CLwAbDbCfP8XK+eiybHhmNsq35s/vQFaNlv+kaB303Tr+vTgmZuWDSRtJaAAp7QCbM2sdfOUKIMyBbc+RMK1WhLZuNe4os9bQZuqgCLvK+DvOVAboLVrF39sPtpArR4v4gMQ4PEW+XQXU9m/40k9O+7MXro0WFqIlpwP6jb3u6hh+Prn0gEribeMqgDQjTPnb8wkiCmGOCFB6pRYljrIHiXyx2k0//BiU4k1hAJ1z3PHLXQHOhZaD+KCX/ODUU4Lk6R7TCeU61I634nnCqV4Y5bnkpm3Io7O0CdslMBSN34DtfIw0eeq5kfOiO2QtsvZBNS0Q2r2FI0/Gjk3eeHQCUcWvmXKu19W+PqtH4usTTggGV+sGgHO+nIJwM6WVVSZzap0DNdlqCZFnP6hxXv5UnHrBHp0ptj8Bn8AkhP3bdXLyRYrHYF1rnNc/FwtOGpROVDTLN/WLqbthSShB7FSyhI7qkEBhmwd3PHZ0ncKRAMR/CiUXiww4c76ISBmLsku4XIdvNi2CJj9OpPkTLX8wQpfIWxGH3XwNPgUf1Y/y10WwQ4tJf3JnYfHbXcG2DQke1ElIzH/epWLghnIO0dt8whQNYdWf2B2DHowMayqPzXJGOQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.009284, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Tue, Nov 12, 2024 at 09:46:20AM -0500, Liam R. Howlett wrote: >* Wei Yang [241109 08:45]: >> 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. > >This comment is difficult to understand. > >Maybe something like: >The current calculation for splitting nodes tries to enforce a minimum >span on the leaf nodes. This code is complex and never worked correctly >to begin with, due to the min value being passed as 0 for all leaves. > >The calculation should just split the data as equally as possible >between the new nodes. Note that b_end will be one more than the data, >so the left side is still favoured in the calculation. > >The current code may also lead to a deficient node by not leaving enough >data for the right side of the split. This issue is also addressed with >the split calculation change. > Thanks, this looks much better :-) >> >> Signed-off-by: Wei Yang > >Fixes: ? >Cc: stable ? > Will add this. BTW, as this is a fix, do you think the test case in patch 2 of v1 is still necessary? >> 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 >> -- >> 2.34.1 >> -- Wei Yang Help you, Help me