From patchwork Fri Mar 10 14:08:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 67411 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp894532wrd; Fri, 10 Mar 2023 06:12:07 -0800 (PST) X-Google-Smtp-Source: AK7set9MiQnz5BoGUwXYVfxzpPokNxrM1Ni/rCmQxJ58t665zyv81eO3uDYoi05FMZQ6D+YTPMys X-Received: by 2002:a62:844e:0:b0:5a8:aabf:46f4 with SMTP id k75-20020a62844e000000b005a8aabf46f4mr23577368pfd.8.1678457527068; Fri, 10 Mar 2023 06:12:07 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678457527; cv=none; d=google.com; s=arc-20160816; b=HsmbKSouW0Rud9lUbP76EXrwyXvEreeo/DglI9X3q/VKFjf1HN9+v5ACj6r9x8GmYe GWGCOtJgVcJv9436No9hPYawPlbUgF6S2I4/GodM1eFc9LWcyilcRBVsI4IxO5jxQPr1 XEyICa9VpxxurGJ4Mhenz4Q1YfxzA2kvzg//fLaPz7fN/34F5uf417ajMELd2mAgxdUz UXbdApau6/tjY79Qns7LDOX8C0u0qiAfmckA+XqkEVuyaLgpSqyGcpWFQA5eIfradm/k 7yny5m7ezywiCAW3BcqSbG4TPu8ajME6MUxM1n8c1N+h1rt3eGqwdFRlYxg+GMu/dVYy B/9Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=YjLkk2c7qkyw5y4hjkb7TF+50UyVGFsleuClk20l+mY=; b=KKyD+JdbR3vGwIY/uIpSMUckcjyHsINQ8d6kh3tLcBHmcOk9ch/N8kCq5pujkek1+j 04BcX+E1dWVsi42HMDe2mnY2zvwd4eyrCctjxRSMcbZ+tWAdME1Mp0yBvL4Ox/zepzKD bYxzYCzBMAesrYQplIPBFvOsT3EH/BaRA+zCunFajC0ziUuDdO+r+wMkdspol0EYeTcI I+gfrKjyTMm94dd85R+Ye/eINySDls9we39GgO1+FBOkn0UEM8886Ydy1oAnq02WDfod 8PmryPc5hZ2GcZZSwfLoTMKf64ib1xna8VX5JykLePOh+cjhfoDcXUADuWiHuSapgE6U Vnzw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=WphEF2ox; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id y15-20020aa79aef000000b0058d6a27d641si1944862pfp.234.2023.03.10.06.11.53; Fri, 10 Mar 2023 06:12:07 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=WphEF2ox; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231926AbjCJOLE (ORCPT + 99 others); Fri, 10 Mar 2023 09:11:04 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34414 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231877AbjCJOKa (ORCPT ); Fri, 10 Mar 2023 09:10:30 -0500 Received: from mail-pl1-x631.google.com (mail-pl1-x631.google.com [IPv6:2607:f8b0:4864:20::631]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2FE581AB for ; Fri, 10 Mar 2023 06:09:37 -0800 (PST) Received: by mail-pl1-x631.google.com with SMTP id a2so5664614plm.4 for ; Fri, 10 Mar 2023 06:09:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678457376; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=YjLkk2c7qkyw5y4hjkb7TF+50UyVGFsleuClk20l+mY=; b=WphEF2oxgLVej3eE274fGsflhyHMgJ2dTa8s8OAIbv9LOvuOXfdF5Wd1/NaUe575sO jjgnHjjrsT0jG6nkB6+v3mF6Cr3KhiaHv6c32jK1u5+vbv0c5CRt2ZF0+PVT6Cbh4HTH MbTFqJrcrn9Gkh6LznsP0LnemRqAd0jDgk17BUrm8jORI2Z6HACdab9cSSXcHLhfmvI1 xh1BNcKau3ckNIcS2HIQZc9DrtBF1jIOIXioVCYTSReGIrRus1A7fySebJgKB4nf68ku I+9kznE7YYXqfpkGLKgIi/gzoqg00fpJ4qB1FyA7HcnqhHZOJqUFQ8om/zSdXIm75gBT DotA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678457376; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=YjLkk2c7qkyw5y4hjkb7TF+50UyVGFsleuClk20l+mY=; b=nSr0OCIP9Hyu+VIBPdPI+mEEYbd21oIcvQPmuyyBFVitz1hV9GdvS+RppG4S+UJs4P fRcDskc+TI8T62XYmjkS4CfnZnBowSYgiq62X2cstLmrIxZuaVEi6WEChTO+c1YkUe+H UhZ8rl7HPrLrEI31au5tuuwvRNnms6LM58YyyOqkqKK5LZAIBh3pX2dytNNHH8JnGkHS Ud5HCJcA/7PV7Tebm4V9eQ5A3ObxwEy376jNRdLB7aRCk7NqfCwV2wLY9gIz8Fa7EQhT yKN7096kJDscrs7OSaS/4gV1Iu9coprrrLLckWpewytKK6MvL7FidQP67Ja5lsxhBbDx awmw== X-Gm-Message-State: AO0yUKWQPwylwrb73PvhZIandh6GBfI5EHuU6Akn04pmSFHm6s4luJ2W Puygk7lE7PbDqZNwjK4VJm3ahQ== X-Received: by 2002:a17:90b:4a4c:b0:237:9cc7:28a4 with SMTP id lb12-20020a17090b4a4c00b002379cc728a4mr27301326pjb.14.1678457376680; Fri, 10 Mar 2023 06:09:36 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id fu11-20020a17090ad18b00b002375c356b0csm6753pjb.19.2023.03.10.06.09.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 10 Mar 2023 06:09:36 -0800 (PST) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 1/4] maple_tree: Fix get wrong data_end in mtree_lookup_walk() Date: Fri, 10 Mar 2023 22:08:44 +0800 Message-Id: <20230310140848.94485-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230310140848.94485-1-zhangpeng.00@bytedance.com> References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759990279644336636?= X-GMAIL-MSGID: =?utf-8?q?1759990279644336636?= 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(). Now it seems that the final result will not be wrong, but it is 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 Reviewed-by: Liam R. Howlett --- 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]; + break; + } + } while (++offset < end); -next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) From patchwork Fri Mar 10 14:08:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 67463 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp947727wrd; Fri, 10 Mar 2023 07:52:17 -0800 (PST) X-Google-Smtp-Source: AK7set+fPJzsENxdu1oQ2cqK1sY+AQCv+oUKrHjxZK0BAnpnfywkNNzyHIdvXL0wetyK2WfldAOx X-Received: by 2002:a17:902:b786:b0:19d:ab83:ec70 with SMTP id e6-20020a170902b78600b0019dab83ec70mr20663816pls.45.1678463537344; Fri, 10 Mar 2023 07:52:17 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678463537; cv=none; d=google.com; s=arc-20160816; b=zWrEB6uRTeppSqw32xIqJs1MN8EtKUWxcjkyBOEmPpRSAx3NvJeIeahVyER+PxWM2Y qFOeZgJmJG81wnS3dnwD8AlSM1gCRPiBeweYNmPmMpg6XCWY4GIs/fuem4RXSJq2CLGW b8YfK0c38B3T3BRMU9xx4GT9CDtKkJC85T/0IoCWj9O2j2kMHnYoTAZ1NXzLvrVyNPwp ic7+Go0Vb1MvwOVUqcpb7ftlOD3q4iMxJxGhbKGEWZA1oQTUEULu/8kGyLE39SuvHVeS GvlB5tSGRTj4DInFuVGDpge8aVm9fOMq+AMKxOTsu/dClogty+yRzXKWO9/rIIl3AoSH SSzA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=f7DPt8nqxS2DR8+B+9WtRvCdWF3m9pKFBEKjw2IVbrY=; b=MSTzXBUrZt4p7hha+pmkc2apxL24nfeGn7HWFwmhyAohU1vRx6hP6lfhHljd8ID9qE rbry+hRWy/U8abgdaKvcPo7uoCi21yb7514oi0jEJlpl5fzp5mkj99xXfkugD1GCZPC2 iVl4Z/OXKy6CxmMk0+hVPgdOF6NNiOlOw60Vv31Q0cYrM2fVPs9w2vHCW5WMbWP5eUdu aVyC+T2bZ9t5HLlZ4SZvXHsY8pIhMoaz5UOVCl9srWLr3I7YcyWiTbIlaT+gMdtuw5E2 asm/C79oVRg2Et7KF1jplHQOvcExk/bUGADeASUWpHYiHA5GHFVpPy2qtx7XZ0ULxLZQ LM5Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Vt7HmeQi; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id c2-20020a170902848200b001926cc639ecsi198564plo.487.2023.03.10.07.52.05; Fri, 10 Mar 2023 07:52:17 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Vt7HmeQi; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231771AbjCJOKj (ORCPT + 99 others); Fri, 10 Mar 2023 09:10:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34510 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231733AbjCJOKM (ORCPT ); Fri, 10 Mar 2023 09:10:12 -0500 Received: from mail-pl1-x62f.google.com (mail-pl1-x62f.google.com [IPv6:2607:f8b0:4864:20::62f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2E57D136C9 for ; Fri, 10 Mar 2023 06:09:40 -0800 (PST) Received: by mail-pl1-x62f.google.com with SMTP id y11so5685893plg.1 for ; Fri, 10 Mar 2023 06:09:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678457379; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=f7DPt8nqxS2DR8+B+9WtRvCdWF3m9pKFBEKjw2IVbrY=; b=Vt7HmeQi/0l9PcitJbwAwTNB69hO/ue7yLU7cQTTmP4tGVuY+aE3gFyEMp8I6M+gd9 0vRhsPgpGy9FkvxG682ngJXJVQ8h7Q+tFj6pxUci1n4a90DrWTeC+BFdbqiLiR1QES06 8Zh5WuLrsn2iRx4YmU07ySYLIt08ka0rV7cMvePtiLF2pelRlbmHOFUpl1w4eow+HBzM 1NSEFkEOZT3RNO0m7kXJqqJiUWLffAlSDZDnSXEMmqRGz4ZspmHHeTzNUzH/X/BrtwDi vCxlaVIW0PhyKotrrKPuxWcz0ee1nfXSCt0hEtD0rmaCWbI22gsK/jKBS2RXZ0mSAr6Y Ikqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678457379; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=f7DPt8nqxS2DR8+B+9WtRvCdWF3m9pKFBEKjw2IVbrY=; b=Vx3HGjECv2DuG1LaETBWTWhoVHa1Hc1It+JCh3tJeTFIjG7P5u9mtMkn4FKw6P6Dpu zRqxtxVdlcqkIorH/5VdauxiK76fc/N8JOEeYDxy1Mumul5SvpBhHoOAvtTygzO2tcgT 7Jn60yWRLpYak3SZ+358WFBi+ITHHD0YoG/CS/NIcVdb7Q4hPpAzJNhDfwgRTDEWAS4s DU6UQjHzAI7adsrhFLq90XDm898q3nPYOIE7wZRKqxk6PxVY3pJ6pwzpRhv05UIzR8aC pC5up7gjbhVywnFWfnQ5YwjQGfWkbTRzvVLPrrLc5rcvlzK3rsTuXCrgEYQ5yKE3l149 oItQ== X-Gm-Message-State: AO0yUKXsU0T93pawUVqooJyKL5KWbqf1cXvm6v/a9mFoI9VW1BaGL3uF FAWi92M7fQmUoaZUJXtJkFfo1g== X-Received: by 2002:a17:90b:4f42:b0:236:76cb:99d2 with SMTP id pj2-20020a17090b4f4200b0023676cb99d2mr27006601pjb.8.1678457379677; Fri, 10 Mar 2023 06:09:39 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id fu11-20020a17090ad18b00b002375c356b0csm6753pjb.19.2023.03.10.06.09.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 10 Mar 2023 06:09:39 -0800 (PST) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 2/4] maple_tree: Simplify mas_wr_node_walk() Date: Fri, 10 Mar 2023 22:08:45 +0800 Message-Id: <20230310140848.94485-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230310140848.94485-1-zhangpeng.00@bytedance.com> References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759996582445240166?= X-GMAIL-MSGID: =?utf-8?q?1759996582445240166?= Simplify code of mas_wr_node_walk() without changing functionality, and improve readability. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 34 +++++----------------------------- 1 file changed, 5 insertions(+), 29 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b3164266cfde..4d15202a0692 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2251,9 +2251,7 @@ static inline struct maple_enode *mte_node_or_none(struct maple_enode *enode) static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - unsigned char count; - unsigned char offset; - unsigned long index, min, max; + unsigned char count, offset; if (unlikely(ma_is_dense(wr_mas->type))) { wr_mas->r_max = wr_mas->r_min = mas->index; @@ -2266,34 +2264,12 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) count = wr_mas->node_end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, mas->max); offset = mas->offset; - min = mas_safe_min(mas, wr_mas->pivots, offset); - if (unlikely(offset == count)) - goto max; - - max = wr_mas->pivots[offset]; - index = mas->index; - if (unlikely(index <= max)) - goto done; - - if (unlikely(!max && offset)) - goto max; - min = max + 1; - while (++offset < count) { - max = wr_mas->pivots[offset]; - if (index <= max) - goto done; - else if (unlikely(!max)) - break; - - min = max + 1; - } + while (offset < count && mas->index > wr_mas->pivots[offset]) + offset++; -max: - max = mas->max; -done: - wr_mas->r_max = max; - wr_mas->r_min = min; + wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; + wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); wr_mas->offset_end = mas->offset = offset; } From patchwork Fri Mar 10 14:08:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 67432 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp941673wrd; Fri, 10 Mar 2023 07:39:38 -0800 (PST) X-Google-Smtp-Source: AK7set8HKSBs3LdX21WxNXJ/04fCTxc9Bp2iX8wfE0pDgNE23+FSlbZw0XS3w5RoE/A6jPt7PsE6 X-Received: by 2002:a17:902:ec8a:b0:19c:f2d5:5830 with SMTP id x10-20020a170902ec8a00b0019cf2d55830mr32113889plg.44.1678462777872; Fri, 10 Mar 2023 07:39:37 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678462777; cv=none; d=google.com; s=arc-20160816; b=XAsX5owSh0ziEhS4u9V/WeXXYeV78cUL3yUeJUfPV2E/bNjAmuToHCk6Tj7W7JEOdj 1JF/gwXO+WAuQ/Q6VJZv3rQCOWI1fSD5FuUKRpxF5YSgotHgKuOe42atO1ouyjmOlHRO EFVRSCZAVBaA24+QRmsuLusHFP3o9ROExxER15l+aucYDUniAXGu+qp7/XqfK71f26fx hjV/el6PTqrFBe0T9HLT9CCtrCgehVpJb0EasgR+xQnGc8RnSlid5wze+2r+77lk/PyF WZsY7yhQPgS9suHlJcyzGESVuPaMK4EkDchKpghxqPv/miRzBzevaz70SY3FP067n8p9 OPkA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=YhjLemRp0ybGNAE6kUWmSVSvbxk5Whphru93CDPfy31RrwR3wSrLfW5aSPt7Ss8AMG JYqT5EEurxYNnfj0ddUnfjqh+5UZOFhGxSirP+HG6RwhhFSKNcm+Bh+fWbBsmKEm0+Po Z3CZG2fvgUlphAVmCPst1AwDTdwE7ORrjeIz3ZY+l3pCtAQiqgl6xx6s28aJW+MO+Fs3 2sqtAYVQLzvOy6jzL1bLkPCQ4piZRkKn7cZshJE5jK+NsccZiIjuhLJZSUj4yHI1LbM4 P6aj1zzYKtFeDu+l621AcREf9SNBTI2C/Qxm/J3oew70cfUiZoies1fR+u4fbXhZF2gf cyGg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=R7ouu0Wk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id g2-20020a1709026b4200b0019a95ab6b66si254141plt.33.2023.03.10.07.39.22; Fri, 10 Mar 2023 07:39:37 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=R7ouu0Wk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231938AbjCJOLR (ORCPT + 99 others); Fri, 10 Mar 2023 09:11:17 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34594 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231784AbjCJOKi (ORCPT ); Fri, 10 Mar 2023 09:10:38 -0500 Received: from mail-pl1-x62e.google.com (mail-pl1-x62e.google.com [IPv6:2607:f8b0:4864:20::62e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1F5795FE1 for ; Fri, 10 Mar 2023 06:09:43 -0800 (PST) Received: by mail-pl1-x62e.google.com with SMTP id i10so5645504plr.9 for ; Fri, 10 Mar 2023 06:09:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678457382; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=R7ouu0Wktvvy/0biANU6/CsFYdvyqaelWm1/tm2k3z1xn1E58V6YQdhsRRE48Ukl0D xouTlAcz47ET0Gx71OmdRdZ1QQB46Fe9vBCaiXaGfk/dAdNoNJMwJmdyFhZ7pV/S7KcT qq/41cVbpI0VXpk7WAC/xbEO208+6SIYdhxXL+q7/v3/pnmJ5yey3oRrE45ykNAf9O+h 86/msFcANeTG0J4YQf4v66JfUdAcaAPu7V0w346WgpHPq+5Ozy9K7ywU+iLrHj5ieiIP /YBouzChgTtzGJRoD3jWioB/xzQHKJGT8lMCdNM7tcG+wvmYMAxcNNKEWgFrBZeD2ZvQ Cx/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678457382; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=zMrA0KjZhywy9hJsjrPFZAPPusTMnhRrPsYpWJWpG2XW2QTOW4p6xVSu6SUVQqhxzL jc5mQifbArTBTlXhLGYSJsYwpPRkhcW+tAbbCTh/UpsvgK3KMLaGviVZrubRwwq0vKvM DL6VE+6IiSFGTnPFaHmsQnWVzndB9/5KrFiEKVGvyI5PJ1+PzB0hhRwAMltLYlN5tas1 yNumFPQ0QbtQusO+Kd/Yp8U6P6t8p0tpTBITOWUmESWf2XOXgJP8PlFOWjdcAozhNMP5 7wjD5qZTCZwfqy5AUATcEpnNERSkASTaa9hbfnJh9BvnQWBREdL8DQ1PVTk7G78sUMNy nhRA== X-Gm-Message-State: AO0yUKUfgVNpBqgywap+I/9/f3Ihe6iyLyDaVd4RHESXBcNW5W2AQXWG mpaavTzcCkzpmsY/dW7GO3zoew== X-Received: by 2002:a17:90b:33c4:b0:234:bf0:86bc with SMTP id lk4-20020a17090b33c400b002340bf086bcmr25736949pjb.31.1678457382536; Fri, 10 Mar 2023 06:09:42 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id fu11-20020a17090ad18b00b002375c356b0csm6753pjb.19.2023.03.10.06.09.40 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 10 Mar 2023 06:09:42 -0800 (PST) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU mode Date: Fri, 10 Mar 2023 22:08:46 +0800 Message-Id: <20230310140848.94485-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230310140848.94485-1-zhangpeng.00@bytedance.com> References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759995785564292896?= X-GMAIL-MSGID: =?utf-8?q?1759995785564292896?= There is a concurrency bug that may cause the wrong value to be loaded when a CPU is modifying the maple tree. CPU1: mtree_insert_range() mas_insert() mas_store_root() ... mas_root_expand() ... rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); ma_set_meta(node, maple_leaf_64, 0, slot); <---IP CPU2: mtree_load() mtree_lookup_walk() ma_data_end(); When CPU1 is about to execute the instruction pointed to by IP, the ma_data_end() executed by CPU2 may return the wrong end position, which will cause the value loaded by mtree_load() to be wrong. An example of triggering the bug: Add mdelay(100) between rcu_assign_pointer() and ma_set_meta() in mas_root_expand(). static DEFINE_MTREE(tree); int work(void *p) { unsigned long val; for (int i = 0 ; i< 30; ++i) { val = (unsigned long)mtree_load(&tree, 8); mdelay(5); pr_info("%lu",val); } return 0; } mt_init_flags(&tree, MT_FLAGS_USE_RCU); mtree_insert(&tree, 0, (void*)12345, GFP_KERNEL); run_thread(work) mtree_insert(&tree, 1, (void*)56789, GFP_KERNEL); In RCU mode, mtree_load() should always return the value before or after the data structure is modified, and in this example mtree_load(&tree, 8) may return 56789 which is not expected, it should always return NULL. Fix it by put ma_set_meta() before rcu_assign_pointer(). Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4d15202a0692..de43ff19da72 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3635,10 +3635,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) slot++; mas->depth = 1; mas_set_height(mas); - + ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - ma_set_meta(node, maple_leaf_64, 0, slot); return slot; } From patchwork Fri Mar 10 14:08:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 67477 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp950349wrd; Fri, 10 Mar 2023 07:58:09 -0800 (PST) X-Google-Smtp-Source: AK7set8RAY5slqBJkHjYc3K/WD0uoK9B7XPE+9wpau3VQu/8n/VQHkOX2oOWmKPiICryFgxGKrnq X-Received: by 2002:a17:903:247:b0:19c:f232:4604 with SMTP id j7-20020a170903024700b0019cf2324604mr31732594plh.10.1678463889205; Fri, 10 Mar 2023 07:58:09 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678463889; cv=none; d=google.com; s=arc-20160816; b=q1Rxw1KR6nk6HJLLoRtMZQnvzcGi1HtQpPmdShugCVJjORZcywvtlQtUc7AqTRFSYm kTg+Hf6mfTNiAuBa/xlx4BzBCxlbOtsCfGp2F8NG+tVjQJ4UBo7jnOeh9dv+NYmnty0E sXPeLt//wWWfkKBm1wNVznvSS53WC08VEt9VaWk4t7NTEYEibkpnjQFhcjt43bGdGMkn F0sqjndDaDUbNINZ1K7D8N00PhLo/CrAd13IduJxsfe3Bs23WN6W/OUQySlW8Asc8Dvn NyYtbaeqPGg1PnHTK8L1hQmSKMh0hZcIhbVO2OtffjLPef4K2Y/H9KaJMhT7SzMNhh5T EhAg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=u6SczCfFTY/KJFxBt0YFVietITxxXbodBIi134Qsi0M=; b=Dhh0Wkt0biUtqszACM/m94ieWdPdekPddKnqItYee8o4+sTjs40H6phY5sMszRdCax NeSSnsv0APJPxJvBVCskekbiZVuicFqTtB1WrS9Bql3LcpahoJY35kq2NDfu6EOfFs2Y AFN+2MNXgW0HSaMcwdPRCz/Jl3YKZYKGDgawk6/kX5RxIir4+bvol9sIDcEg9v/7Mhdr /s5CIz2TEVimb2fiFiDJdoeQ0TVYiZ1H1m2EvRcYJAP3FpLHo2Ps7U3KJeAY8bSbAUql i0LZ2aU55a5Jfzt12h3YprwNtkMWhYyX7mWHjHxwXtorYNZY/XcD7GIPx2yfqR8VJRxf k4kw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=asKUtiJY; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id q20-20020a63cc54000000b004f1b6a7d559si122580pgi.467.2023.03.10.07.57.54; Fri, 10 Mar 2023 07:58:09 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=asKUtiJY; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231906AbjCJOLW (ORCPT + 99 others); Fri, 10 Mar 2023 09:11:22 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33726 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231898AbjCJOKl (ORCPT ); Fri, 10 Mar 2023 09:10:41 -0500 Received: from mail-pj1-x102d.google.com (mail-pj1-x102d.google.com [IPv6:2607:f8b0:4864:20::102d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 251B810E252 for ; Fri, 10 Mar 2023 06:09:46 -0800 (PST) Received: by mail-pj1-x102d.google.com with SMTP id h11-20020a17090a2ecb00b00237c740335cso5269743pjs.3 for ; Fri, 10 Mar 2023 06:09:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678457385; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=u6SczCfFTY/KJFxBt0YFVietITxxXbodBIi134Qsi0M=; b=asKUtiJYwQqgvMbN60l/bVTcYy2W5TZi9AcVU4FhwMRejoM8MKEoTejGDXrB4L5qRb apETIhrKGJqUxZte8/van/OhvRDQPA6LTjZdPQYxQy56FIXwSfYtblPmPlJaMseRJfCk /yfIf/MqQYjQt0TQom3v4HX7d9OQO9QM0TLMhqyOmcyJNEW9vYdHhWIAHfGXKlMTIJG8 33aFH4rBUKRtz1XBQmXjUCY1FGm6mtprh9lqOS/mAuq0AE1VUTJcJYRCp14hiDaJ4m1/ bHLS+N/9p6xMEGCJSRATQivnN79niKr7Z/zt+6bOH/T7hEOAme9agNB41jtnTSqcXhxy msag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678457385; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=u6SczCfFTY/KJFxBt0YFVietITxxXbodBIi134Qsi0M=; b=smjr0QLuNerKvAV+l83qSYwDPUkZ3sYVOTDZ03aGuOQ0Gz4AKQ/GFoNj6c58fVwETz UGAlsM6vOiICfm59vpf4kwhcUZiCrODnetq/Nf44awi+edd/mggG7zsgCjMKhCgzOYT0 iMS0UsCBV/M/VC+xYgVC5LiSw0HhAiuEn7QjkbGVNu/DdJAD2bdle9b7O+ICQm4RY+SY +as7+au2B8PNmFLtL7F9vpaA/xSUmCc1mfRVr3O9+IVdpp0jfP9vcjReq1tgh341wo4n GCq8zQmxTxAVH8psWHr4TWHUUBjSqNwMktQSEdBXwfnkAlO+x8PPbj9fvUm13ncejSnQ C3oQ== X-Gm-Message-State: AO0yUKUQOQ7eXfHR5gEx3gM3r9wto3Tj79DIAxmHJiv/x4DGudXECY3I WFvtnm+PCHX2tTZ3GvJ0GvZy2Q== X-Received: by 2002:a17:90b:2353:b0:233:cea2:dac6 with SMTP id ms19-20020a17090b235300b00233cea2dac6mr26150338pjb.47.1678457385677; Fri, 10 Mar 2023 06:09:45 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id fu11-20020a17090ad18b00b002375c356b0csm6753pjb.19.2023.03.10.06.09.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 10 Mar 2023 06:09:45 -0800 (PST) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 4/4] maple_tree: Simplify the code of mas_mab_cp() Date: Fri, 10 Mar 2023 22:08:47 +0800 Message-Id: <20230310140848.94485-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230310140848.94485-1-zhangpeng.00@bytedance.com> References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759996950970700687?= X-GMAIL-MSGID: =?utf-8?q?1759996950970700687?= Simplify the code of mas_mab_cp(), and improve readability. No change in functionality. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 24 +++++------------------- 1 file changed, 5 insertions(+), 19 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index de43ff19da72..688b062728a2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1914,32 +1914,18 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, void __rcu **slots; unsigned long *pivots, *gaps; int i = mas_start, j = mab_start; - unsigned char piv_end; node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); - if (!i) { - b_node->pivot[j] = pivots[i++]; - if (unlikely(i > mas_end)) - goto complete; - j++; - } - piv_end = min(mas_end, mt_pivots[mt]); - for (; i < piv_end; i++, j++) { - b_node->pivot[j] = pivots[i]; - if (unlikely(!b_node->pivot[j])) + for (; i < min(mas_end, mt_pivots[mt]); i++, j++) { + if (unlikely(!pivots[i] && i) || + unlikely(mas->max == pivots[i])) break; - - if (unlikely(mas->max == b_node->pivot[j])) - goto complete; + b_node->pivot[j] = pivots[i]; } - - if (likely(i <= mas_end)) - b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); - -complete: + b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); b_node->b_end = ++j; j -= mab_start; slots = ma_slots(node, mt);