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 2848FD5D69F for ; Fri, 8 Nov 2024 03:02:31 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 785376B0098; Thu, 7 Nov 2024 22:02:30 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 735666B00B1; Thu, 7 Nov 2024 22:02:30 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5D6936B00B4; Thu, 7 Nov 2024 22:02:30 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 3F0E96B0098 for ; Thu, 7 Nov 2024 22:02:30 -0500 (EST) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id BEFA9A079A for ; Fri, 8 Nov 2024 03:02:29 +0000 (UTC) X-FDA: 82761427140.20.1EC8A92 Received: from mail-ej1-f41.google.com (mail-ej1-f41.google.com [209.85.218.41]) by imf08.hostedemail.com (Postfix) with ESMTP id A850816001C for ; Fri, 8 Nov 2024 03:02:03 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Rru3vxKV; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731034777; a=rsa-sha256; cv=none; b=dvYCrbbf6JqujUaPVlKJRLxa4gd8AJgSXidXjHt485egYu+Zv0WiYW+wgIQW/KGuNsz3ii T7lDIAzaXNvCqaulT1/2nZDhxrT/sIge+Gv/l1ZAIpdpNjhe0UYGUgs6bHD8Rj1CnzE8CN gf2nAH1Rf+NVJFlj7NAzDqxgwtiQXGc= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Rru3vxKV; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 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=1731034777; 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=rdh7nPhnc19EnCRZOnMzZGUuEMd54SxRLG9f/bwRGLs=; b=UsGY4JdO75Zu8tzip7PtcRByYq6pISvY8XmvS5nY3cjHTlCJii2Rn/0oK5/sLWwicBGOx5 FuwjTfvlSpuMdYxEaG00wqmRjXbs2ukdv7O6xn+BTxQfFhP0/KEvQ/ATI2RlAMObDCerY/ f9CxUAbck9qMbP22RrdElomD67xbfNg= Received: by mail-ej1-f41.google.com with SMTP id a640c23a62f3a-a9ed7d8d4e0so240984966b.1 for ; Thu, 07 Nov 2024 19:02:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731034946; x=1731639746; 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=rdh7nPhnc19EnCRZOnMzZGUuEMd54SxRLG9f/bwRGLs=; b=Rru3vxKV69IiVY4wV+qzMmxWMC6sm94fqHW5eshtYoLRVaqi69nms3NPVCJ/NuPeUM 1W74rGvPm/RHSndSdw/q4xdq89bx2ZX436abGCdpDBUCZLiEDOcyXEPr0ldNjtnfGKVE 4I+ly5zQT7wc/iARh3zzHBj92p8B5SKbS7iGsqTU/LVwtqy1GjJIfjC3mqinYPzzeJWM 8ZlL52jbm7M/oCIHKhM5tjl7AKppDSnmvJYHaf3fCAGMs+Y3Fctk1m7L6GcpG3bj5AQw 9AEQ0I9PpBsWVeIUO6uPa0paCb7SEFOet18Wp01fqbMtFXQh0LTE6C8PdrrjcxOHx6KV KF9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731034946; x=1731639746; 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=rdh7nPhnc19EnCRZOnMzZGUuEMd54SxRLG9f/bwRGLs=; b=LpgJ3XvJZKHUJVZY09guz607kSyXs0ESivnjL/G2lKJ5gi6Mn15B6ccvD3GilF7uad 2llKim1BhUKf6DooUChrNY7PdtyvlDdu88UiG7sOS5iUP49ntHN5Z9qvA3kXNkT3v6QE eTMLP7gaO4PxikWc8QnWjErxXw7xBO0rTkT5lpVaYi39s8onvj2tWGCXQ5GOAfAWNqHo 3xvJFPe7ftTIdorL/NjbcwMxjaDjvTizy3lyB+2AfotjeUiC23Q0yak41kK6KFVaJS7E GsDzhtCQ4ArjlirbbaydKzUhJuNroaJ5OTQAjXtn7z6TLNOlXrl0HEy32T1Kw7Js1XcM Yzcg== X-Forwarded-Encrypted: i=1; AJvYcCXnan7RDNCvp0tuPOg/I1R4jOEgYyIGq0ytWs5Qhs+OhLa9e8qxKtd+qCVXZc5yhS4Tdu7qqPb+rg==@kvack.org X-Gm-Message-State: AOJu0YyYxHDy1MFe71BRgpBjYvDtnsC9a8qkaRRJiYt7j1j32ZNlz1FM plO3croUM7Zo0GH31Ivsw8u/an8CR2amawhayx8O1LtYkem6WHgp X-Google-Smtp-Source: AGHT+IFsDcbruzh6KPhasmGUyjd3j7y3nXoir5O/inYRoCGxgS9T/5BuzB7fvhGqaAozS3mLUUmPgg== X-Received: by 2002:a17:907:94ca:b0:a99:2ab0:d973 with SMTP id a640c23a62f3a-a9ef001b427mr97345866b.55.1731034946032; Thu, 07 Nov 2024 19:02:26 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9ee0a48585sm175297866b.45.2024.11.07.19.02.23 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 07 Nov 2024 19:02:24 -0800 (PST) Date: Fri, 8 Nov 2024 03:02:22 +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: <20241108030222.s553xkovtb5wsrb3@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: 9tqqbaiinzb6oykcfjjoytzamaig7n9o X-Rspamd-Queue-Id: A850816001C X-Rspamd-Server: rspam08 X-Rspam-User: X-HE-Tag: 1731034923-960331 X-HE-Meta: U2FsdGVkX1/D1QSkcWsROh4EKkCwstwjcpAxtieTL5+kYcHM691vzilCANTIGElvy7FD/yd0+vcU0mJHcIjAAGSrINfRmNjTNt6BUsjhx8FIJEhqhXl1rf5Fsd7lX62oM8Q5NPSg3c5y2Ma1ncXuKxtY+LDwqP38v+ONFvwPxPVojgP/EZgE+FZ+SPJ0QA7rviYHlAKcTIV5Hc7F+wZFqgmYTRjqLIDzRHf1eFmI6maDtbAwQ+bF64knlLEIotJ79c4aoTp5YOk7kpu7/zyde7wXicY5qgn4H5pUniibzwtf/gDUeik8n9kdnYyWiMpm5lp6re8DBMEAzQGDIzbOpt5H9Zd2oIarrYS44/v5nj0K03W5WG6LzESdu6RfWyFSrGkgFUoq7sN7xpUYb0K52FHaaRAVl5uZcaXywaCbM6zNwmLiwDud+tCKmQyWpICZImCa1g8stChaQ3SIo/BBjXUqUdKm9r9Dl1TFgh+FBDpeI9dbkvEBu8rbkdjrSGVXbZIijrIljG97awWX7NOuX8utwWGq7UfFxou//e7WHZuox44yVb+dHD4crzpRqltp70jpQJ6tOLDoE0nxIK+9rhbvd4pDWHyDjIYoSl27zzPWKH3WUsGC4FkP7jPHDq1i3VQUEWU5UIqAn8b5vVHqhH4rs5otJIr2YS1CFZwstjEcC8fjF5Zf6Zg2He3CSGk8glKEd54RyCFVvO9AX0RIDyqCO9NJbj3tRwxU7+qpB8brFeZLh8JNB0TUqWFQiNMZIGc3G59e7mnURbKFT8Uz7wGSjetIhbwhJivpUMkKv/ShHkk6CS8aQogWqe1E4hxzHkHhaZfRjNHygtKFT4JJzgYAanhdYZ0m/rg2ZaHd1S5eJtSlcK/EUieOlLYteusPvd0dRIkga7AXOFLoYBgUUTsjfVGZxrlHZFrzETeLKkAONfNpOhktzegQBYv6N/IqNl1pOD1LQYLzybJLEY6 I5IDsP4i G1wj7SHDRUZ8pyFL7bXFF6DEzCagsMBXDTyBmhD1K6+VGLEwOSxYC9gAKcWftbVmD+4KOtF+diF8oPgVmdfCsH+/1DrT6ncEJ4p9K2p6L4EVgTJ+wWhwKpMmjq/ZtC0dOhBc4YDLmm1nk96jBvdQ7WFFvAdFbhPaQMxFFrTeo7yGEYSD6/+40D72CV1PlbXff0eI/wsFAXfKOdAV+E1DIQhStxPxXHuHHtAC8do0B9Di4l65vJT/LEw2abflPyxm48Ou3Q29QlMGW6hN8gg8AbzlquPziyvsU3+Mo2aMp4pA1/lnoQ0I6AcT0v6axC1uk0TJG4E3j2YANbUycceQmeJo82P/m16oJcFsSU9JkFSZFdz5SvWuxHzZZM8gGvDxGXM89T5PADDZkAO6OhGA3Oo9KymT44/3lvD2xY0pYk9wuMF+dcmLtnk8EgdRfkSrrgY0uSVx8o0o7R8W11Q+quRhDOrA+/oSiO20iswSuvWDErvHAlHX1XOC4oQiEjtfDLU/eKIFT3th1ryMFqBuyc1E/iIrdpfEyh1wiintvSSANFatkdeStaSVMcoYsh9JEiQR4LfT0HLb/Dc9ewhK6YN6yb0pjBxM+HsyoxjJH5z7WPJlQXA8Dqf6jkQwWeaUiAKA0hWm8WHjBRF2uFGv0RMRrNsu0YuvSI7UfjuJnp4iHREZ9kSoDCRN07DZcu5fkOHlZykD7wt+1Ezb8mAeXHX5pwQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000070, 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. > >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. > This looks good to me. And it looks we won't face jitter problem after this. I need to take a through look. >> >> > >> > 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