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 B1085D6409C for ; Sat, 9 Nov 2024 01:24:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 30E5E6B00B5; Fri, 8 Nov 2024 20:24:38 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 2BD0B6B00B6; Fri, 8 Nov 2024 20:24:38 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 185536B00BA; Fri, 8 Nov 2024 20:24:38 -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 EEE256B00B5 for ; Fri, 8 Nov 2024 20:24:37 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 36D471A1046 for ; Sat, 9 Nov 2024 01:24:37 +0000 (UTC) X-FDA: 82764811416.14.9EF0362 Received: from mail-lj1-f176.google.com (mail-lj1-f176.google.com [209.85.208.176]) by imf12.hostedemail.com (Postfix) with ESMTP id 48F8C4000B for ; Sat, 9 Nov 2024 01:24:18 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=R1UGiPxT; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.176 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731115303; a=rsa-sha256; cv=none; b=WeDoQ0RYuEOqjikReQVuKP7wv4vIUwWML6gRGMpd3DIvBG90hmT0DoRRiWWn/PRzpr12Q5 s24Wcl/J+7dpoT6ZtYAsMkMfoBQ8vTCiFqWKuiv2lRQEbUTCd3G3sh+bgb6n2/+7FdEH8t QPPv7ADvOKviKY4x0cIzd9G4RCbGM30= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=R1UGiPxT; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.176 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=1731115303; 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=sPrMy7Oc11eEPM2E+BNqUw0kn1q27QUPBaKsoCv/d58=; b=rD8o6y7ht/OZyJDtRhIddJvKHhDFYo9NXClOZRCMEODIWMdmKsjaso7QrhTjQouuiT2iy+ lVcYCIS88o2sTI0YhIxci1Tr+13gNC9188BaKfmPEgdl4AiTZeznRIeSJFQjL3lH+FOBuY htv8kQDNXhmm7MEAWIoIpKJ7PmFEnyg= Received: by mail-lj1-f176.google.com with SMTP id 38308e7fff4ca-2fb51e00c05so34445441fa.0 for ; Fri, 08 Nov 2024 17:24:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731115473; x=1731720273; 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=sPrMy7Oc11eEPM2E+BNqUw0kn1q27QUPBaKsoCv/d58=; b=R1UGiPxTIJwSBS44rc7sbmc3TsKFi/dOo4iLH09LpoAju/PgUb8+OwHKaTkrCve8RM AkrR6apcKHg0FPTwm0yKonJaMuilfwOk+R7mTm2Q+RKCaxgu/RagfQuelqR+A233UtdS rs1U3OFLDgDg7918Hx/T16yoqu2hbjDyuJXSj7PYqM6hDd7+YktwZSD1SgWkGFASpF92 26L0QULWf7d1eeIebUosXGSSzN9HzepPhSD4cOiGCWn5/8wOW0O/HBkzjeYx1Y8OaMaD AnQbhGyhKXCohzIyHCnhkSuSWMz+Ik3SN+Rg/LwAahbPOwHpxOclSt7YhwFFxMSvxyO5 2Xjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731115473; x=1731720273; 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=sPrMy7Oc11eEPM2E+BNqUw0kn1q27QUPBaKsoCv/d58=; b=IIeFyeu4TaqsPc76dq/fZh7SjlPsIkbRV8CjLOtDHo3sn8gNfJSGHSo9qYnenk4QeA qu6Yo1tMRt1+93LumWaJrvbW3M6nft7GyNp6fR7cvGG1ygPAMkIfjbiUzJkXub2Tx0cB UUpYeJ1YLiKGDjrfVtVzqrfPAQlof+WLr322feBWUGTaddPvEYMaJKiKJMnhgyojZcOU fUM9FD5HSEKgAYoI8Mvt1APH3RDhFYkCJz+LsnYST783A/jD7UhdTT1ggIHbKMSS+Y8z dUrSY4j89pIqLDB6EHPPyfay6FDAgHW40J5W1pl2R6Tc/bmns6rRofKtfLN5EguSVb3e qNFQ== X-Forwarded-Encrypted: i=1; AJvYcCVH88z7PnlDoPn/vFmkkOGB0ZL1R2i64Nn+OiOIEKHS6KeVEmiohEFNn2hF/XJXKd3DOaYU44Ebsg==@kvack.org X-Gm-Message-State: AOJu0YwGy/6HhU7VlZvCbrHWfhkLPUNgvz4YEn8iVV/Z/vVKeXgsfbMd F490W9ymOBIQat4ePeqO36i/TU3CYeRLuo0/ptX9d3ibqtl4UDVx X-Google-Smtp-Source: AGHT+IELj/i/+iTMOPcIMjAluk7I+JLKli5mAwdriUtEJyXyiAAcd2Nu6HdDBabNNs6MjGNlSzDmcA== X-Received: by 2002:a05:651c:554:b0:2fb:4f8e:efd with SMTP id 38308e7fff4ca-2ff2028a97amr43316791fa.32.1731115472996; Fri, 08 Nov 2024 17:24:32 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9ee0deee8asm298525566b.134.2024.11.08.17.24.29 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 08 Nov 2024 17:24:31 -0800 (PST) Date: Sat, 9 Nov 2024 01:24:29 +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 3/4] maple_tree: use the correct min to calculate split Message-ID: <20241109012429.x7rkol5qtr3ilab6@master> Reply-To: Wei Yang References: <20241020024628.22469-1-richard.weiyang@gmail.com> <20241020024628.22469-4-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-Stat-Signature: xg65c65ygdjtrf6aicnmsq1ti44yx4fc X-Rspamd-Queue-Id: 48F8C4000B X-Rspamd-Server: rspam08 X-Rspam-User: X-HE-Tag: 1731115458-741346 X-HE-Meta: U2FsdGVkX18cgPpNpKhIP5dbfEEk5kMi3SGM5AgYOjmuD94qMOZdKltw/RKLJr0kx5mt46auftgjMaHsqVWshevGsusziXRHU3D5O8ewaHOGxrneaKKBA2T8xpkfgwT0hO2bz+FLfaQfl46GZliYIOByaGUVBwlqEaPYM87L1RRXVzUJvSTzO1xdtIGZFAbjSDstuCxueVpu5HHf+3oQfHyI3wkrnPCgb/UhEMerGF6S49Ym4GoSwjCHmuHfMnNYKnCcvaWlmZrxG2CaNDoR535MkrcuQlNSFjO0JFYeqgyMf0jlqUiQcx0jPTpStIvI3uClDa1YdRCem2j11Le2lshL6qV/4465SqAFgARSqTeg2SDHk8dO7gYxdLytTtxNVAE0BPXu3px3wffAlB5UMVxLfb/rA2BxnGALOFRH3D+EouOQzqWd/ayetqQNuqY15SPCdEcrDK9BI7k8gSvwrWWZPjgW8GayaHqNdNmV8IOzT22Nd7Ws1oLV1HzdDfVXf4+mOyq2TZk6CEuC1Em1gSguYQGlkaG/s8J2FXoTvbJvCezR6SFDvJyOyPnFUaLzE83kvduRyUtWn9fQVJnIMn81W0IEoHDI/iesT2tszymo6xT0YzFT3UZ8h4Vg8zSMbj5i97RlR4lDH6y1fLq1fC1bpcMriiNokF6v7i5mVc7iP8xbt+il6Ftx8oypLiXPqmEUJtyfgEFMfZh1cdR/3qPdjNVNrRfEC/1UeUXwaeCgJXMKjWSeNhWuobam2KSPiyS7nVauJxPGjTtZAWDi4L5asidlurY/8Z9mu+Cwc4AFqBEZj40YFCbXqHPyaecsIVckMnyMeuOToSERvVOaqbrZzrHStbPYl1OkypEF/sbmFXHuS0gGPr8L2UzYe+JeCWYXAWNua1LHmPR3ZgFPpmg3m6tAZobNAfA4YAZBP0uUUVKeDwLqrpsSo9/uySA6p0sRgfvMlqMIxMhcdyn 0rEsq9Jj /jg4g9cPdf/6cowGxZ8L1OKUj+QSFsuxAB2zLZxvLuJk2b/IlbeZXI1wLzHursKY0ZKx+DBbpHRb6rx48kiPQgovYiqxlKaAqXywbLCpx8+f/RPi9m+8UbKSFfoCp4USEzseWLQIRHwOnPUx/tDvlqDzADC217qja96fCUEsO1v0n14DU5FuCb6o4O6k0kPptGkbv8fZKTQtTfdcLiBxJt0w7BE59x1ZOaJWGjf5S6oiEFWQk2DVzXAwUsO8l020lRh+ZiJTlO2ScsSGd47L3N0PQ8o8EXajS14l51i+qGNip1cHSzs4hDcB8DjiXFmNtcm3UO2QHOyi/ckQ4OSWgZjYK/mQXJ0WsImdsvbJpLLQ99eFEvNCZfub1CHVl4X6SZ+uk4pmP4NYBOVGzHqK49Q4SkbmJsbZJxAYsCdU3ZWWJ7aHxF3oAJzt0NZ8YUrQUfdm4T6A+BIoA7q/43UhocyzgiA6pC2Q+Ripz7aLNW8TLng4sn/zQLROmBTnLuR42B4kRozOoErV228Jxs57znu5+kU9W7smgtgv2UkHteC7fBnYChW7zZYlH2H/CqQw1r2pRknS7YtQukIYdQfPWSfKcPay7kSgMjeUuC/SgQ9ajE9HzPgL/z3D1c9lrOFSxXCz0FcWIrKCnR+YdkmVb4IsgSmmATQ5HBcP/I4XL8q16q6t+ziFMqAmfgxGtW17Wa/Bi4KrrmOjaDthNtt5g0jAisg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, 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, Oct 29, 2024 at 01:49:28PM -0400, Liam R. Howlett wrote: >* Liam R. Howlett [241020 18:00]: >> * Wei Yang [241019 22:46]: >> > 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). >> >> This is fine. >> >> There is an open work item to make it more accurate at higher levels, >> but it's not a problem as it is. >> >> Each level upwards needs a better 'minimum span', meaning that the node >> should have at least mas.min - mas.min + level * something. >> >> It works today for leaves, somewhat. >> >> > >> > 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. >> >> No, it is set to 0. Not initialized would cause random data loss. >> >> See MA_STATE() in the header. >> >> > >> > Since we are now calculating the split of mas->node, we should use the >> > mas->min instead of prev_l_mas.min. >> >> This sounds reasonable, but considering what this number is used for, I >> don't see how it is working as well as it is today. I will need to look >> deeper into this. > > >On examination of what is happening here, the only way this makes a >difference during the testcases is if we have a node with 16 entries, >we'll put 8 in the left today and 9 in the left after this change. > >This only matters if the range is less than the slot count, so the real >world implications of the change will be negligible, if anything. > Yes, maybe it only effect when there are all singleton. >I honestly think I'm trying to be too smart here, especially at the >leaves. We should just set mid_split = 0; in that complex statement and >drop the min argument all together. It hasn't made a difference besides >the number of instructions executed. > I have tried to remove those lines, so we got split = b_end / 2 and mid_split = 0. Tests all passed and kernel runs. (I guess in the real world, it behaves the same, since (bn->pivot[split] - min) is always bigger than 15.) Since we call mab_calc_split() when b_end >= slot_count == 16, it means we get split == 16/2 == 8. So the new left|right node has data 9|8, this is friendly to jitter problem. >> >> > >> > 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 >> > -- >> > 2.34.1 >> > -- Wei Yang Help you, Help me