From patchwork Tue Mar 14 12:42:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 69607 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp1734005wrd; Tue, 14 Mar 2023 05:44:41 -0700 (PDT) X-Google-Smtp-Source: AK7set/KrBqkxdGExloUPFZ8+cq+U/WCmn9m6AMW+CJsI8EwKXZC07IxFwtzJ6sxf/uLFvsJSsiG X-Received: by 2002:aa7:9f96:0:b0:625:5e9e:17d5 with SMTP id z22-20020aa79f96000000b006255e9e17d5mr1859106pfr.9.1678797881363; Tue, 14 Mar 2023 05:44:41 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1678797881; cv=none; d=google.com; s=arc-20160816; b=HPjlMkB6tU6pG5/UhZJN8eM0RJ9J7VaSde/6W+YF8hl/qLud8ZYoxsYa2JomSntXar 0XE4ho8inKOhr+6ORaIbJHETteKy7nFphla83pB2VI9L3eVoJ6tQLKCHIYt5erUk9VH8 x1hrvkCXUZAPwAURdL0DJskm68vI5esWr0cSBW1MlJWrlaMqaCC+E+a25NdDk7Tl0BM/ a9MYPHrJEJFw/lzZWF0GwrBHWP/K+DsiX/zYGtSJ5oax2z9oj4ATGOo92GX0xVy17sG1 mqWP4BAUf3dlC73yRuRcp3BLJZv/9QR3aK4T7zL40gRE4IGad6ZPmZLnj8v/qffq0hNR 7aFA== 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=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=l24T4w3lRiKDxyAsq1say9m2R67XtrwYFbzk8dPp7TEGhFkHLdBg7JjjwdJgjXw0Dh jcAQofwD9YhKs19hFG/D2P1XVgP//8Avdlk6+rz7PmB6MZVdS3kiwvTU0CVSWlOtD/Y3 E/yiqCuN/wV+JJ+irukfhrZE7oEEyc9fmatf7MOI61/AM+Y7+DvZIqZyvDK0YL8dPjSp X22/027OA6VJFX8eFuyv0Zjrig3ACjump3lkYOTaSlgiYCyz+bgjdK0JIbBbrmx/2GWl CHl/4/AWgocvo1rDSLMK3QecGWgyGbkSmB2rGsmEpYIjIamJKfpWa87UN7X5c6nWc/eE undg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Q0EWqbll; 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 v66-20020a626145000000b005a8da0b042bsi2037788pfb.378.2023.03.14.05.44.28; Tue, 14 Mar 2023 05:44:41 -0700 (PDT) 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=Q0EWqbll; 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 S231645AbjCNMn3 (ORCPT + 99 others); Tue, 14 Mar 2023 08:43:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59020 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231629AbjCNMnE (ORCPT ); Tue, 14 Mar 2023 08:43:04 -0400 Received: from mail-pj1-x1034.google.com (mail-pj1-x1034.google.com [IPv6:2607:f8b0:4864:20::1034]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 87879A189C for ; Tue, 14 Mar 2023 05:42:19 -0700 (PDT) Received: by mail-pj1-x1034.google.com with SMTP id cn6so2661857pjb.2 for ; Tue, 14 Mar 2023 05:42:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797738; 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=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=Q0EWqbllJxrbZyB/Dz9VLiyjmY6OKzQ9ODkPXCtv1PHZFxEXHWUGy9j8P3QCubHPW6 laPUIMP5ae5R8SQ31VbcE0PP2Qxc0ZRZeq9ial6QzAMDElJuHuLPmKq8qz8iadur2NK2 Qc6llIatsVC/fIYVCuEaCkKpavYWo5xV0MCwYao4CrA7z5VX0new9FRvp3QEbxYXkyiI SLS6EiaBUB2md6d10HaQRcz8rW8OxSMc7iQFehdRbjLPyp5kXZppj44STkAZGKtyjsmc olYO/uynIoSxt0B+X/x9asOLPNhgHb9CaVT7qrMmAGPN7MuDUu025M1syzM8Q6iWO8yG UYOw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797738; 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=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=C4ql3GXnIg8h0FzsI4z6zAv6a3hDFjLx/jEGfcpURks8dxGJPaeiSLnacmH0MtOdVP hgygV1PbOTw0CRrlr3xi0GzqiqUEn/edWZMbGHyyX/q77FNsO7Vv3A5VFarau9nMuYaz l002ro7RzuF2ZXQUtFrxho1B1WvxKsSuoZT1N2BwR3TXuJyxw+IM4rRZB7fabZGWAV3q sHmP+AGK7M+0LtNKbn7bNoA6baYwpMqmkQ+iPq1b+aWWn62BDtfogccL6RikgM+fEA+u bvThKQJi1y8TQrxh4acwdqkxg1QQpZQiMSI/2YA2rjjhuNuTip6aA1ZeH/0QdqNeTQmr wo1A== X-Gm-Message-State: AO0yUKWmNVr5uKJ1vZ2RzM9WkY1yDd4Cv+stJcQ9CZ4IGxd6dpT6eejY OJ8MCyjdmnvB3Bf6kGB7oF5hXQ== X-Received: by 2002:a05:6a20:bc97:b0:d5:74f:37a1 with SMTP id fx23-20020a056a20bc9700b000d5074f37a1mr3510720pzb.27.1678797738697; Tue, 14 Mar 2023 05:42:18 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.16 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:18 -0700 (PDT) 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 v2 1/3] maple_tree: Fix get wrong data_end in mtree_lookup_walk() Date: Tue, 14 Mar 2023 20:42:01 +0800 Message-Id: <20230314124203.91572-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-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?1760347167127203504?= X-GMAIL-MSGID: =?utf-8?q?1760347167127203504?= 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. Fixes: 54a611b60590 ("Maple Tree: add new data structure") 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 Tue Mar 14 12:42:02 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 69608 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp1739478wrd; Tue, 14 Mar 2023 05:56:20 -0700 (PDT) X-Google-Smtp-Source: AK7set/jEuz0/YU7MLinM2PIMyi6X0vH9ONFV1BnwNRx53csNEtt5Cw/vJPvQdkhCEewFFujc6xF X-Received: by 2002:a62:1dd0:0:b0:622:891a:7e0a with SMTP id d199-20020a621dd0000000b00622891a7e0amr8080618pfd.15.1678798580546; Tue, 14 Mar 2023 05:56:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1678798580; cv=none; d=google.com; s=arc-20160816; b=DhsOzDEggvMj45RYYHEdWLgmVdsi89TPX5t80qyK1U/1quAwD7QpHdORy+CAIlBzFj 5nCDR7xoZpY6WOtyxM88YNJ49WruMzw4tU051y0mYk/8P/LDn3Pc987uuDcsIkUSCOgR yLnoc4fvwBIEkknxqkvUGvgJJf8dwys4WA7a1FnmjTPFjyHNesF1xwXiADTkc8nQw91c Ka1f1LQMamppyuDqLfVak63nrP40HMTExA36Jggjq64RZPlb9RVh9vZh3C4du7Q0bTn3 tBfWDIhFpuIicJ4TrX2NZHqpiLu583E1DC7TFmmluMASf8MQxU5qEjMcwCNiQ0MoAYWE rZiw== 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=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=a87xGucPbUy2L/tINF9JQFarTdM3aZV0cV74vM9y1GENfstmxiI3g3sUlQ3BjFa6wd CUpUTpRRP/UcxIaGkSHjSizsGkv6thVSAcDdiDnNB+NcTeYi0AQ2uPup8u8MTByqBbo6 JmlbjFG3FWH+g9GwwCCE7Ef6ba4e+YZ1b5ud0xeYvoh974bJeNnco59DtF3xU0RGfopz Yoa+BJY2X+4LmzPukP5tAl5kYt2fdSyeYhwaaHgU3COX2ocPpmy6LlMt1bJiLFXCsj8C d9yYIq5fFJu5ZU4u6iK2A9PA0LFclRHNNp2m15R3hoVjRwQ/pTz6l2no5cLwRw+2v2FK oZow== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=ix7uri1I; 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 b19-20020aa79513000000b005925e6b584bsi2154576pfp.201.2023.03.14.05.56.06; Tue, 14 Mar 2023 05:56:20 -0700 (PDT) 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=ix7uri1I; 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 S231277AbjCNMnb (ORCPT + 99 others); Tue, 14 Mar 2023 08:43:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57810 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231264AbjCNMnK (ORCPT ); Tue, 14 Mar 2023 08:43:10 -0400 Received: from mail-pj1-x102b.google.com (mail-pj1-x102b.google.com [IPv6:2607:f8b0:4864:20::102b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 365FCB479 for ; Tue, 14 Mar 2023 05:42:26 -0700 (PDT) Received: by mail-pj1-x102b.google.com with SMTP id cn6so2661994pjb.2 for ; Tue, 14 Mar 2023 05:42:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797741; 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=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=ix7uri1ILEEPiyasmKqakK5ccU2YG24dfCqDDUm43gJDsFxSpoQlzQG6Qa5vAndQXl jMsc70HggeW+6NgiokrIJmXArEGC7yYYQFla6ShFJyEAu682f+SnE7+XfbcrU66ksx4k 4kFZv0Dv44qxaNHR7T52669L7YDxYZP8MT6K0pu3uVwc9FzRsE26xZIDVpEpoMyw28YW MOOhI9tAbzpkS1N0dmHOI8A3Mjy9YteguHhhITQL9vclsticEYAqAYzAg9nbqA/MOwqh 1X/UnNuLY7zn0mc1PHipCaOAx3+hJALDo3nOjHAZK3iZrjkSJ7K3Sx5kaOdlPd/iXTXb 3Yww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797741; 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=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=NQQFZJeRa7aKRpKXdQdv/GDJv4FxS3WpfYbzr5UPXAVXsaB9YNwo8wVP7TLAL+kQx/ JXukAicTNBAA9e4xExlwTa0/DUiUBCau6iiDONuVjUibm4hsa6B3YSMtCNwNiiWElNMk +Ja4ontLhKrG5Xgr3ezJ5LYyhZsUTkcVheGstXF9FLbOXPgtfGaK0hF03ZqdLQ+GL2+I MH1a9KKLpd0MOirUih7DIgGlUbq3dMxgnSnkc5P7BqcKGQkJANh8CQpv0jshYmeBgcwZ 5xi+pu90DqvidgmyayEW6gDG/wSOGwv7DWksmHzwzAwjMFFbsrkxXST+gbi+8AienMhL s88g== X-Gm-Message-State: AO0yUKXRvHR8v4txIfphtyx+ZYwtVPzFBtgszS9zISslQslreksWIfxQ JdxqJRWafmH0HTwjGRKVheB/76iRS5A/WmmEqvQ= X-Received: by 2002:a05:6a20:1bdd:b0:cd:87ef:3f21 with SMTP id cv29-20020a056a201bdd00b000cd87ef3f21mr36837359pzb.8.1678797741688; Tue, 14 Mar 2023 05:42:21 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:21 -0700 (PDT) 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 v2 2/3] maple_tree: Simplify mas_wr_node_walk() Date: Tue, 14 Mar 2023 20:42:02 +0800 Message-Id: <20230314124203.91572-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-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?1760347900591436682?= X-GMAIL-MSGID: =?utf-8?q?1760347900591436682?= Simplify code of mas_wr_node_walk() without changing functionality, and improve readability. Remove some special judgments. Instead of dynamically recording the min and max in the loop, get the final min and max directly at the end. 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 Tue Mar 14 12:42:03 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 69609 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp1746057wrd; Tue, 14 Mar 2023 06:07:17 -0700 (PDT) X-Google-Smtp-Source: AK7set9lI8LQ3iixz8lXv3C76CH9WEPdFljEvvaZdRe7z/cG06ZPHpOl794ZCUyqEnB0RSMhSpWt X-Received: by 2002:a17:902:e80f:b0:1a0:5349:7779 with SMTP id u15-20020a170902e80f00b001a053497779mr6063828plg.5.1678799236918; Tue, 14 Mar 2023 06:07:16 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1678799236; cv=none; d=google.com; s=arc-20160816; b=juE4xS/2kym/DHxWpoNwx3xZAPIh6/3ARcBr6uingLMJLx5aznGA5wNBaLzExdbXjJ YSWGTbDlgaapLs+lUj1VkZvfFIBfDSFh5cNA6bf0AuLGyYnDqqrQVEv00p6G9nuCoSYu 1jDyW53ZAofZQh+9O07wRSmB59fUVkGMNefJEu2OnwoblT7c3z4jY3lT5f79TAw09UmL UbawNdlFo4cQTgO/Is2faMySUkkYBwmfSV1UwBpp6Tz+eCrX0kFouAIBZQaFxrBq6ji+ PRpfwG189L9Aywq6g4R3N1pV2R60X1lsWUfBJhpsRVNV/Qv2BTmq0KHRWjox+J53ibqb ho2g== 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=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=Ucyh2w4s0Lm8DqAad09En1jXblHD9P7IjwlNg+kYxPymnnlP7ZAcW/aSkzQRGUpUqV Hv9cIezU4U+eanojUkjZVco8F+CECIEqVvp7RfmezOiwP2oOTBv+HaIlEeJMd6x6mMSp /IYqx+LA060xoYW+Kn3pxfT67JDdvtxcE+ymoSdHpiFWfWKEqBhg91Tyi8yKyGbvOVjj H/ajJizSPWsYB2uFomIt1cTP2Z28uIgie9dpb4hRFKA3/gKUndkg4a76KEatqPSbtuqn RvR04TbpSRCk7kgKTGWlfhAfkdvn/SYVAViiUK85aCB0byNSu5N5FBKE66t/RaPA4Txz GbLA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=ioJxPaNM; 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 lk14-20020a17090308ce00b0019ab107bd01si2374783plb.110.2023.03.14.06.07.01; Tue, 14 Mar 2023 06:07:16 -0700 (PDT) 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=ioJxPaNM; 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 S230207AbjCNMnN (ORCPT + 99 others); Tue, 14 Mar 2023 08:43:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55410 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231387AbjCNMmu (ORCPT ); Tue, 14 Mar 2023 08:42:50 -0400 Received: from mail-pf1-x433.google.com (mail-pf1-x433.google.com [IPv6:2607:f8b0:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 87F6D97FE9 for ; Tue, 14 Mar 2023 05:42:27 -0700 (PDT) Received: by mail-pf1-x433.google.com with SMTP id ce7so9608064pfb.9 for ; Tue, 14 Mar 2023 05:42:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797744; 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=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=ioJxPaNMnP30bTwv1b4MqjbilZtnlKQ9m1hdLXAwZsIGL9l6MV5d4U/YSj+W/3nvNV Ku35QSwZHVI0wCWwz1lxNOn2pyfHnoDzp9HWWmr5MpAlXnIvsHuvDcKqSDSPIsFT7W8R wVHRLuCkrLHPYsENx47uJPNzAhK/PTrJYPmq8hYbjB5uLb9bEk6NqHk5MjthH0X2TVV4 z5m81EIIf6x/uQXAB65ULJPGnSZx4SFKOioo7XNeZuBlpDoHpyfZqtpJ/vrQssKbNQsq nVNT5PABOsTqgFPrvIW3eSDPG7ApKweSPxEkSgE0b3UVV92ZUOizfBMzoJcKaTLRqJjE DDXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797744; 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=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=YlS2jwTMM7GNkRhSQikiy7r+PtxojPi14WSV1PTe52W6wz+VmqUkYQInCxCLMDXtic CCAknwdFRuS65QcVwN9LXf4n5djTAA/2d9gy8MUmplIocDh6a4FGifmsR2lfdUyNJq53 yMyKNFS1UQj7hFkOVygtl33HKuB22wtlEK0ALqDXd2iqTSpj4S2wFB8n99pDzRG+VAlJ eKwF3r1Dq3Ol94vrivqIFn3Ar32hRwtqP7tbhn+EsqFvbeSVLxWRsxx84btKErEJPJyf gtsnyRfxuKEE2z0/4T5m+ONaVx/YiFRLKFbwx2DV+d6rJTc9XGHkTv58pD2JGm4sXHc4 qdqw== X-Gm-Message-State: AO0yUKWgFdCQuAlDkvodazisZhYK/nYEpHP5JjWynhfT4oy5Unl9tJq7 ry+9qga8FniA2cVDL73MbWE3Zg== X-Received: by 2002:a62:1756:0:b0:625:13f3:9409 with SMTP id 83-20020a621756000000b0062513f39409mr3941069pfx.26.1678797744687; Tue, 14 Mar 2023 05:42:24 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.22 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:24 -0700 (PDT) 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 v2 3/3] maple_tree: Fix a potential concurrency bug in RCU mode Date: Tue, 14 Mar 2023 20:42:03 +0800 Message-Id: <20230314124203.91572-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-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?1760348588570590506?= X-GMAIL-MSGID: =?utf-8?q?1760348588570590506?= 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(). Fixes: 54a611b60590 ("Maple Tree: add new data structure") 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; }