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 4FDECC6FD19 for ; Fri, 10 Mar 2023 18:53:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 95B758E0003; Fri, 10 Mar 2023 13:53:23 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 90ACB8E0001; Fri, 10 Mar 2023 13:53:23 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7D2BF8E0003; Fri, 10 Mar 2023 13:53:23 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 6E1AA8E0001 for ; Fri, 10 Mar 2023 13:53:23 -0500 (EST) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 2A4FF8035E for ; Fri, 10 Mar 2023 18:53:23 +0000 (UTC) X-FDA: 80553886686.12.141B4BF Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf09.hostedemail.com (Postfix) with ESMTP id 51C6C140012 for ; Fri, 10 Mar 2023 18:53:20 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjRRfFxf; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678474401; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=MT2yApvZ05ViO2Ujgfyy8OwtpBDoNA1MoVGcEzXFvq8=; b=oIjKHy2FefnMAG34kUCUOuiYTEHDs3thA58puYRm2EZOSLEIJXk230j0f0UdYcldrexbHi +vGCvc3pfZV3K2HVzWNWgSGjU/mZQDmvNHefMd/ZY+501Db5IyosTqKe5Ae2f/iop0i477 OxsFd1TrSEPPnvgr3vQFG+vC9yvfRao= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjRRfFxf; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678474401; a=rsa-sha256; cv=none; b=KA5RoNB77VeFjwze6tdgTyXr5aizyFbys5vw2+7qbLuxogzOpz8k+H55gS6ajtbkFASwYl xNrNRbKEY8LB3bMEws8W+FklufhZBuM72SqFuUj4rXTmQV1e1nRLkt7m2S3jMrEzXsEVmp UlXrzAvMhd20d2LVuyAd9GpafQaeRRM= Received: by mail-pl1-f173.google.com with SMTP id a9so6612119plh.11 for ; Fri, 10 Mar 2023 10:53:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678474399; h=content-transfer-encoding:in-reply-to:from:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=MT2yApvZ05ViO2Ujgfyy8OwtpBDoNA1MoVGcEzXFvq8=; b=AjRRfFxfnM9DHay0pkQxIkp37uekmHK71/nKoOHAkn3POQJDK5MSEvon3PBijUSCnk RjzE1Q7Mm5SB7uweAngWOtxSR9GBhWZECWs0EVtmjVR4kdR/MhvnNNYYISnV32GbxYtr m2mThagspaT34bR34pR+FNWEVynHk6qSefOdLoeCZGDyYbPU9+vER/TMroh3lnLtpG9P IFJ2xbh511ryRszkRvAuSPd4u5nVsdjOWH3ErVohUySVuzFC+ymgbyIe12lT1+W579al l/x0Szjv2n7AVyNzoMoxqblMa+ks+xt5KQu4Kn9T8fehpGbuP37mCRF/3mHL4TYGxE0P toxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678474399; h=content-transfer-encoding:in-reply-to:from:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=MT2yApvZ05ViO2Ujgfyy8OwtpBDoNA1MoVGcEzXFvq8=; b=5rHSzeE09IVhsNc0XVfGt0b8Gg9sj7/nfVHhYYGK79Jj8Jc/Oo86cD3yV+tu20gisW oYJHrvQVckcMIlOImtFoO+0DwcazifUBZ4b3lrhGZWyUeWHEofgVI1My5aYTw24sknLm kTcWF2FnL0JOEOl11UdRh0u0FSGu2zYEVsLvM1HyB6F9j+RV74OG9Jwl6Byik8eVBjX1 mxMtbqGQ1Ano4+Ke0s0W4RNHHs0ksSzoZrq7x6xdZ6G3PLbeUwfeH2aYvZNSsEc/krix B7yYj6V2ECb1Izu1JS0cYeN6gSmxdGIS6lJzIqd/l13HAOIyBR7S6rq3N8ufpm8VAZfJ 512A== X-Gm-Message-State: AO0yUKXf5OV2pxv6hhplFzZvV9UB4zeeSTuftKnk8aMNdbXYKn0JPFRz lpSrGYjX+H+riCi+yoamURsXHQ== X-Google-Smtp-Source: AK7set+3WFxKSxNoJcqhbZ55LB27r3MrFan52xLzSmHwFrMMtBSUpqHxoiMSO1GeuiuUu8+XlwGdtA== X-Received: by 2002:a17:903:32ca:b0:19c:e937:6d04 with SMTP id i10-20020a17090332ca00b0019ce9376d04mr33916246plr.0.1678474398820; Fri, 10 Mar 2023 10:53:18 -0800 (PST) Received: from [10.200.11.19] ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id ko7-20020a17090307c700b0019309be03e7sm353307plb.66.2023.03.10.10.53.16 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 10 Mar 2023 10:53:18 -0800 (PST) Message-ID: <9f6ed89e-3456-28d1-0c27-0925b7238f97@bytedance.com> Date: Sat, 11 Mar 2023 02:53:13 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 Subject: Re: [PATCH 1/4] maple_tree: Fix get wrong data_end in mtree_lookup_walk() To: "Liam R. Howlett" , Peng Zhang , linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> <20230310140848.94485-2-zhangpeng.00@bytedance.com> <20230310175842.qkw54rj6zg7dkymd@revolver> From: Peng Zhang In-Reply-To: <20230310175842.qkw54rj6zg7dkymd@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 51C6C140012 X-Stat-Signature: na6y8xuz47fdjeifxwkii93ptja9761s X-HE-Tag: 1678474400-31447 X-HE-Meta: U2FsdGVkX18phG48rLZztWeqkHNkIB1Cb6aVxdISYevkMTI3aXk0Ykj0sxNF51f24W6BTWWVFUThwC9YGjn1TNGKvJNgvqO5vQ6WE8RQloOTBRbBZPcI6BPjyeKwNU4sr/I11fQJ3bhRfsGWYTzj22tCiU5iPWm5W7YF5KbyrUNJcTlc5FzjtQPsN7W+6fcYsErunCvQ+XUWHi4rO9wGShw0p1x4Ckthn2zIGeolKIjri2CwypCAJwIEbx3i6mkukiBWmdB1B08/kuFePHufgVDSrnFfwiUPoq/uERHoojIlbowPdUhkr/RmOd8CpW74Gqd67sYXZ0iotEWHqV6Q8idw/Lnc0EZob1CK0Hgs7C5z+AnEEcflKzxvKhheEaWP0tYD/4PbQJnaTnpGPVrkmJREu+hhbl+0blpF1EeiQMBi1+vzCbaiDCFvNMkLZ5OS3iD/Zw7YpumuxW4T/3HZ0FiVn6GPgzJicHOzI+dtH0UFTEo8/VyAXMnya54SyBMsS8bC9QSP/3kPRm6Z68r8XmHf2M7iZEzXxjSz+3DJgj1gv+TgYwD/YDGhu47F3mAXhEzB7atDQ7ZC6eLEF/hK4jvvG5szfPp3d04wdqQFcC3McsH6JSmKjgNVLBAlhJnNsumyXj7qILGt8ubYYqAESeM4/qIaibVzMBBVFZ2my3R9Z3CH7AzpfEtrUEBfAhnznI4EzvplXafD/eDBGdWCfH53flLos7yl9qazNFncE3MybP2YPPsDWwOXmSNW26/HtVI4yTPtDYtqQUAlyEKeTmxceU1TZCn6Se9//LmL7+4bBBmLJXfikg5EUJE7b43gxAIQTfer54VyHabQb5IyaX6W1jNDfdySilR90fWfxelFjJNcgrVzhEw4B8mUFIHILiAI6iyyBPVD23/ysoNYoNoHMc7Z6AyCWIi0TfqY1k91JqJmkFiacwZckoHIAE7xOwkhVq0Rk4umPNPsjJ6 DuHB9gP3 89f+wklwlWprNwUvmsvh7OzvEogIhMe0zDLMaZ2ZD0Ezdcr6GiTT1W45+vaEGgetNIVwR2OdvDzlc5f6O4VgIJ21GrdHj7b+lK8u1eA5XSUIM/O09TwzQo4K1LYgc/tL1lyJoP2aPLtbkhGA1Vjmpv8y4tDp+Klss/rjbYCUHNguTGn5hGnWD8kzK2UDN6ySKsjJ1iHwF6J702HtvQ+MbmhZPKbj6t3zhWmiGu2k8eyZnTWvcIi+GSwC3MAmyTVMoTjmjF+LQ0QOqui/+z0ydDDdAWiWALofLl/2EBvhaAz0r0Db40cJQV59rrz/yYzF4LcWUxdOcRYAYedrwLHQc6fr1P1tbetNjdo5/FIuOfRH9bPR4T/Kv30ctxAkyCTaSz0AujukNh3HSu2fnnRV/m3Em5xgc+bqVk+ihzImMtArcDLLVvQPzAscqwxKPdyBY9oOK3KhG84nmWk19NSqpZcYZMR0S3M5rRA5y 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: 在 2023/3/11 01:58, Liam R. Howlett 写道: > * Peng Zhang [230310 09:09]: >> if (likely(offset > end)) >> max = pivots[offset]; >> >> The above code should be changed to if (likely(offset < end)), which is >> correct. This affects the correctness of ma_data_end(). > No. The way it is written is correct. If we are not at the last slot, > then we take the pivot as the max for the next level of the tree. If we > are at the last slot, then the max is already the correct value. As you said, If we are not at the last slot, we take the pivot as the max 
for the next level of the tree. At this time, “offset < end” is satisfied,
 but in the original code, when offset > end, take the pivot as the max. 
Please *think again*, it is wrong. The code may have been written incorrectly by mistake, not what you said it was written. >> Now it seems >> that the final result will not be wrong, but it is best to change it. > Why is it best to change it? > >> This patch does not change the code as above, because it simplifies the >> code by the way. >> >> Signed-off-by: Peng Zhang >> --- >> lib/maple_tree.c | 15 +++++---------- >> 1 file changed, 5 insertions(+), 10 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 646297cae5d1..b3164266cfde 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) >> end = ma_data_end(node, type, pivots, max); >> if (unlikely(ma_dead_node(node))) >> goto dead_node; >> - >> - if (pivots[offset] >= mas->index) >> - goto next; >> - >> do { >> - offset++; >> - } while ((offset < end) && (pivots[offset] < mas->index)); >> - >> - if (likely(offset > end)) >> - max = pivots[offset]; >> + if (pivots[offset] >= mas->index) { >> + max = pivots[offset]; > You can overflow the pivots array here because offset can actually be > larger than the array. I am surprised this passes the maple tree test > program, but with a full node and walking to the end, it will address > the pivots array out of bounds. > > I wrote it the way I did to minimize the instructions in the loop by > avoiding the overflow check. It is not possible overflow pivots array, because only when "while (++offset < end)" is satisfied, we enter the loop body. So if we access pivots[offset], “offset < end” must be satisfied. Maybe you need to read the code to know, instead of looking at the diff. The modified code looks like this:         do {             if (pivots[offset] >= mas->index) {                 max = pivots[offset];                 break;             }         } while (++offset < end); >> + break; >> + } >> + } while (++offset < end); >> >> -next: >> slots = ma_slots(node, type); >> next = mt_slot(mas->tree, slots, offset); >> if (unlikely(ma_dead_node(node))) >> -- >> 2.20.1 >>