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 2FA91D4335C for ; Fri, 8 Nov 2024 02:55:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id ADED76B00B5; Thu, 7 Nov 2024 21:55:50 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A980D6B00B6; Thu, 7 Nov 2024 21:55:50 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 92E046B00B7; Thu, 7 Nov 2024 21:55:50 -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 732D56B00B5 for ; Thu, 7 Nov 2024 21:55:50 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 0EABE808A5 for ; Fri, 8 Nov 2024 02:55:50 +0000 (UTC) X-FDA: 82761411222.19.E82FD2C Received: from mail-ej1-f45.google.com (mail-ej1-f45.google.com [209.85.218.45]) by imf08.hostedemail.com (Postfix) with ESMTP id E19BA160006 for ; Fri, 8 Nov 2024 02:55:23 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=eD0aBf6S; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.45 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731034488; a=rsa-sha256; cv=none; b=SbV1A/X748mBJ+yZ7lZsYwD87Kf5XrRrvQBQcMp1LlBa0HFQSTE7IwXAcdaWa8jc73lFFg fdpSg4aYJ62jhKh5O9pWiVc8gvBirgYU6L2YqG/UGiazvIg7UqxTWtlVXzHhHeAstH/toZ rx/HALkpNE60Vz+yueWFP2VAKSarrkI= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=eD0aBf6S; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.45 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=1731034488; 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=+P976JGVPjqah6BDsiyfavWI8QDBJwRkIlgzyYupEoI=; b=vhC91C7DoQMGnjA0zVxQFVS1IEnyakQHK1LT5IsvOi4p9znRRv1ou8HQ+CoPyDlwJXmbrO 9HoL/3Y9q11YBfRPrR4FbucZFq3tK/CBSc7Ci50hFrVYWl1pQWvHCaGVvQae2vSYo+WE3u mbJ3MtTjbQ/DpecjnFpmyyAlvkAJfCI= Received: by mail-ej1-f45.google.com with SMTP id a640c23a62f3a-a9a628b68a7so269738966b.2 for ; Thu, 07 Nov 2024 18:55:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731034546; x=1731639346; 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=+P976JGVPjqah6BDsiyfavWI8QDBJwRkIlgzyYupEoI=; b=eD0aBf6Sr/I/ULZdqrQooXPwI+J13g+0qTBNi57XUwT849QkSqetLveyMtpo7J0c1M 1jxRhOYi3eqAPOoZVT+B3nB2Q0fLVLbMuHqoB1UOpizK++lo7VdgW74B71nk+bkRgfJt SHDpgIfgX4DP6EJmp8U0ohLtE1IPX+gh2E6UUpjiDhDEMlh/4IRu1AwZ5y5SYdQfj30T Lxk1Tk2Utf0Efb+Oj5Ddri40bHxMyBEqPWFIAIPHeTLW0ECuvud1BsLQq54GTWqWteUC C/saSRjCB/Fxmri6buTswyt3gkdwUvD2lI4HzW0FqEsOKvTspHKMKMGtko84fwUfh5MB EtVg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731034546; x=1731639346; 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=+P976JGVPjqah6BDsiyfavWI8QDBJwRkIlgzyYupEoI=; b=AoNbcuKAViHZh0rLURwiojNF+bJZxHtjEpvbSdE9SnccuJn6RC4glh9mZ0SjIs2ppb xIi069A+vf5mNISrTXm/NWa46ZqnrEL3+yJ0BC7UtraHJT4AMZ5EHV8UL6kdBtby0upk tdxv1XpCsRvZxr+vjubzWioVjLbjscPTJFbZDEcxOrkNlLCMJ+e5b1qSv8p6O5nXwKri uFJHUmcP/MscRtkZ1SPPSIAYLCHTZkq9w8ZQrcr9xBMciBQeQbAXIet3rMMz+Iajfe9o xdJetMuvaKN7r4qaHiS+HVzw/1xXxYMtRSbYLGays2DD34a3fr+IljlsQPBsXfVwav6f uArQ== X-Forwarded-Encrypted: i=1; AJvYcCWS5i6WzsyQRNvmR2shGNRQk1SIrJPZPUFFKqFCu2wx2N866d/mYoHWgc61XmurguJ5HvPRcofZww==@kvack.org X-Gm-Message-State: AOJu0YwVFpoV6LZOaSfoTasvRZZV37RqWjyuk4UJoqUQDvK+/W8P8ZkM SQ2tlT05+o2To1oVbmdWYO4RTZNoEiugaz2C+9ac3c0uK0LwLV3/ X-Google-Smtp-Source: AGHT+IFEx/2un9oDtHGOzXRymwyBeL962XrynLOEA2BUHIsEWb5BWz9NNSgzaGoh+Bx+WQtStU+Hng== X-Received: by 2002:a17:906:f59a:b0:a99:33db:2035 with SMTP id a640c23a62f3a-a9eeff37f95mr78792666b.26.1731034546162; Thu, 07 Nov 2024 18:55:46 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9ee0abea92sm174154866b.85.2024.11.07.18.55.43 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 07 Nov 2024 18:55:44 -0800 (PST) Date: Fri, 8 Nov 2024 02:55: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 3/4] maple_tree: use the correct min to calculate split Message-ID: <20241108025542.whll2orsuj7aru43@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-Rspam-User: X-Rspamd-Queue-Id: E19BA160006 X-Rspamd-Server: rspam01 X-Stat-Signature: m6uqsz3hn8iecdyyaxbt7z77of6zwkuj X-HE-Tag: 1731034523-493908 X-HE-Meta: U2FsdGVkX1+RtK91dR1YI7GFzpBSkWDUsY/MkYPxGC2cyfw5XwbmbzKfcsWpHwZJKGLxYkeZSTI5+akIaD+VlJDdYIIZR1xyTFlwLaGZZ5OcmXvWO/HlvQlEJnXwS9jPkDZIrT8dr1ggn9ajWOvOhQydn58rd1MLYaatF4xw3Ti/uc5fwQbulnqdC8q2aIHw/oa2sJmROsJ3bHY3lNokO9VKPpXSXUnJscB08O5dOSoPhARVSEyQ/Jz65kCJPVVM3UwsccQk5PGdfVQcnvqs14C5J1qqCDeCiyiWw95Qrxpr2vSazD0lIEjccAMq0RepzR2QLyrnsP0XPYm7wKVZUQCTVVisvcK+yKjJ0b7MRIY6XVishMaoC2aO0txNger+f7rXs08IJIt1X+bMhxnV7vuFSniCeZW2p3JYwTJAgXCorNblwQebZZeqD+d9uQBuSzkGrNYfOpEAMpTyx+bQWmnijyGy8E7y65dIXOBKRZwNZx/u0Z12ljW9Eb5OiW2509fuOTV4ITWD6zAgKheiDy36pOOkYanmSgsEJOTaaWNFTunZhrFRJkaoj/9VjmoBIletuiyYjOGF/4CeU+PuDVH7DZ+1l03/DgtqApXXbuP/U1hescFTYaLTtui4se6r30solbaGSX8mYpxRe2vl5pWZG1Ws2TrLaWc8b9YxbJBZkpEzBRIa5f/PJx+cqA4ihszdjT3MIurONWutJx7uGPAYqowysTjqtdSi6+serU6Qi5KUkaq15Gnim/iOVTOYJ40NNSd4Ij321ZotR0VIQ7jm8/3LNEajrVcqP+KhfUFEJYsGppkhK6+jqh2jeqbuRJ9PDAmpxpUikHHRhZUS6lmV9DU8xeukuCpVpUfyitiXPvhVvzFy36DgIiR8PZpxc3Lwa91ngqiSS89NqZtmKtbM0t4iuVy7x6dAvMoYXhPtdgZSLLuYKYdQK72t79MhA3f4uAZ1EyjzjOmLdiy zcUQiQIT /PKlJra4JdNLECH4Eaw2IewyMO3LF4cUNOmFmd7lxj/s1RN+vit2BlZ4oM7Wvil9EI/HNiYzuOjhv2mGCdWs9nhehZmOUOHHWXDLNTFEParsiHHlvNhNDQE7J/cOyjPu5YCguUOTrQr2XsgVFg82x9yr8lKRs0DBF/2uqds2PKfF3tMaEqxjU50TqNH7n+wEi0d7gbvpd4s0+8UTeTvMZKiJDGcGEZyMWjMz1KArJ2VUitUTzRhwZO9AzdWlKh3d1pcGTaNSWRZcAzJT9O3Fm3c/An/WfZWOkDeNbWmbZqFmuMKFt2Nw4zcCOYq5Zn4fy2lewwVg7+7mmnWs/TjCcDCPI/HzgVOTNlwhSfMaPvcRi/ORq0XvgQRbI70sE7YNKQUBfvM/hxxQDcJo3h3mWwbFou2wKw6oOFi6a/Ng5RhPZQFtoroskVKp9qBkWqD4elZc9Gpv5Te3lkLjLXyBqdIIIMnbrY2PmWKWHEF0cRwj4l/zjtEQdy4dL8RSoOhooZP7Pwtqzc1T9uZH7xi35SiNmLpcUkqiGVjM6g23gj9Ajo2JM7YCtJpe0sJpmTc88SInr+i35DyTkRnJ2hseQU9fVX4S/sh9UVGNlnoRRtg/2Hlta2dEO9Eo6wqSJ5tjQZHBtzVRrWx7l06fb/Fpo6x2U58XTlhWBYDPkvY4riUNoFnTsoJYpayoRinPqRcMKmjAOQBssT2pqh52DDKvPJo2iJg== 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: On Sun, Oct 20, 2024 at 06:00:35PM -0400, Liam R. Howlett wrote: >* 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. Don't follow this. First, I guess it is mas.max - mas.min? Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought? > >It works today for leaves, somewhat. > To me it works by coincidence. The condition check is: (bn->pivot[split] - min) < (slot_count - 1) while slot_count is a constent, 16 for leaf node. And we always pass 0 as min, the condition for leaf is: bn->pivot[split] < 15 For the mmap world, per my understanding, we won't expect an address is smaller than 15. >> >> 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. > Right, I want to say not initialized to the value we want. Will be more careful next time. >> >> 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. > >> >> 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