Received: by 2002:a05:6358:16cc:b0:ea:6187:17c9 with SMTP id r12csp6800064rwl; Mon, 9 Jan 2023 13:15:28 -0800 (PST) X-Google-Smtp-Source: AMrXdXuuHmRSjAltYWsLdKandLTB7WLmZ/5GlknRMLrOQcj8EHh9tUYg6qZ5tsvRb6PowP1m5h16 X-Received: by 2002:a05:6a20:a59c:b0:a2:17a6:3e86 with SMTP id bc28-20020a056a20a59c00b000a217a63e86mr80179007pzb.55.1673298928131; Mon, 09 Jan 2023 13:15:28 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673298928; cv=none; d=google.com; s=arc-20160816; b=YUEozRlqUysm8iqurOO+SrGAwSgpfV93qQJysq5TNOk0i/T/EOBtJ/yolMs+3xS/3D VBFnapewkvYeI+I5xuZq7QlelsRwyT8THz/J5g7f4ITYh4OLPVgkdIaq5zL8g82UK6W/ k8242f2Xy7HqCLvpNLuan3HozFgm7HgHg9pMql0W28QKOgPbDeNEnkAmVQr+7TayTJh2 9NKXCqiwFj0QcoY6o/t6iewYeD4G75StdpIXrJ63pYAKpYYMkuqLAC/Ui2RLtqliwLvk NnjZvGQGVkO46LIn5vu819mLudjtgLOPDf/MDwikuYxY6wAdZiaMzAKwYXZqh//eamEP 44YQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=GU7SFbwLvAPdD9ofPJY8ZC3AFrLWlaqOvHr/TBsM1Ak=; b=Ql0y/dTlkmIrHwrWnKsBeZwaueOsmHp/snmhs2tP36oLlAnuO6r94fKAPXjS8vQfsZ 8FVnudW5+/dq2Qst+3si/LO0g9V2EeL5KQVqxI8s0BIopLpzP00jp+TU/PbHafBbZ3AP n774pK6YNdBillogomUHWc8jQBOa3nOlbXE/PD7H4umltY5OPTVlCMn16KcISc8qxw+h e/sQBL/+sJzW+a0UEI0NN6CP3GlNEXAy0DyxY1CTkd+cA4D0yhorFcgx2a4xHiuGulgr e+c98ILxlZCouUF354dofp8g3KWfE+9e1xhDN9z0SJCGattkRh712V3hgOnBmUKiXnZw h+Dw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=cDmwrsTn; 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=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id w186-20020a6382c3000000b004b51cdfb176si855932pgd.253.2023.01.09.13.15.16; Mon, 09 Jan 2023 13:15:28 -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=@google.com header.s=20210112 header.b=cDmwrsTn; 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=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237072AbjAIUx4 (ORCPT + 53 others); Mon, 9 Jan 2023 15:53:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59886 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234961AbjAIUxr (ORCPT ); Mon, 9 Jan 2023 15:53:47 -0500 Received: from mail-pj1-x104a.google.com (mail-pj1-x104a.google.com [IPv6:2607:f8b0:4864:20::104a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5ECF2755E7 for ; Mon, 9 Jan 2023 12:53:46 -0800 (PST) Received: by mail-pj1-x104a.google.com with SMTP id h6-20020a17090aa88600b00223fccff2efso7863654pjq.6 for ; Mon, 09 Jan 2023 12:53:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=GU7SFbwLvAPdD9ofPJY8ZC3AFrLWlaqOvHr/TBsM1Ak=; b=cDmwrsTnYnxMRe2M80E4L23YmooQix5wB2D0eUb+oN2Hp3bbyg7HFQB/PgVNLoHyKT pK0aWtF4CTk14CmlPxG5u4iqhHXIU+wNQHLdGD94tpFP5D5/s9ok9CC5dVKy7ZTVeaNC t3/Bp5EGifXzniBaXl20JHyzpYwXEFHr6vzZDBUr27QQthKbHcJnIlWiGRlMM6UQg0ND gIbAYHo5+gFS5Z1JXyH/8Q0hICWyuNm77sn6kp0Bt2Cy3fEKAr803t0EnzzgxBkOELQu v2Q/SfqHP/lVu/l9N+v6WarwdrrXQ25UydUZpK32X5OyRK1NLw7E4rGZtvAQp6+5paD/ Xoog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=GU7SFbwLvAPdD9ofPJY8ZC3AFrLWlaqOvHr/TBsM1Ak=; b=Jc3+iwdrxu2zn6bEtogwfbBauBNTV2ljdQzckmZE30klt1Qf/28EZKtFcSxDoHF0lE Xwao4WKUu6iFEcghBzs00II2UpU8dzsE20OV85fUjR8p2UeVMG3rlBfGFFwZPrt/vLUx he03aAM1ooW2+yAmHlyRhlMSMebDIAtZlVg0oweNqVdp+fsWYri+Y3lHMm3d3RFyZbvU 3PWAgbhyKpDjftYKcTrMPXJwU/VHPoqSeaNBGV/SwK69IcwtK0FXoCE7X9SxeHSeLhH5 XsGcoT3NB37TIpuW9sUaUTQi1+Wyzgqz85q0wWNFWrOw97o+opyGcUNNgu/5TCCe/qir zmMg== X-Gm-Message-State: AFqh2kogAM7KQMnTsDbILHy4yU/+JJk/8yMRJ5Jl6rbhRXd+kqvcalJ+ UhB8SYOKF6TtJmplFbbhsy7Tg6j3Wc8= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:9393:6f7a:d410:55ca]) (user=surenb job=sendgmr) by 2002:a17:902:c209:b0:177:faf5:58c5 with SMTP id 9-20020a170902c20900b00177faf558c5mr4095626pll.166.1673297625715; Mon, 09 Jan 2023 12:53:45 -0800 (PST) Date: Mon, 9 Jan 2023 12:52:57 -0800 In-Reply-To: <20230109205336.3665937-1-surenb@google.com> Mime-Version: 1.0 References: <20230109205336.3665937-1-surenb@google.com> X-Mailer: git-send-email 2.39.0.314.g84b9a713c41-goog Message-ID: <20230109205336.3665937-3-surenb@google.com> Subject: [PATCH 02/41] maple_tree: Detect dead nodes in mas_start() From: Suren Baghdasaryan To: akpm@linux-foundation.org Cc: michel@lespinasse.org, jglisse@google.com, mhocko@suse.com, vbabka@suse.cz, hannes@cmpxchg.org, mgorman@techsingularity.net, dave@stgolabs.net, willy@infradead.org, liam.howlett@oracle.com, peterz@infradead.org, ldufour@linux.ibm.com, laurent.dufour@fr.ibm.com, paulmck@kernel.org, luto@kernel.org, songliubraving@fb.com, peterx@redhat.com, david@redhat.com, dhowells@redhat.com, hughd@google.com, bigeasy@linutronix.de, kent.overstreet@linux.dev, punit.agrawal@bytedance.com, lstoakes@gmail.com, peterjung1337@gmail.com, rientjes@google.com, axelrasmussen@google.com, joelaf@google.com, minchan@google.com, jannh@google.com, shakeelb@google.com, tatashin@google.com, edumazet@google.com, gthelen@google.com, gurua@google.com, arjunroy@google.com, soheil@google.com, hughlynch@google.com, leewalsh@google.com, posk@google.com, linux-mm@kvack.org, linux-arm-kernel@lists.infradead.org, linuxppc-dev@lists.ozlabs.org, x86@kernel.org, linux-kernel@vger.kernel.org, kernel-team@android.com, surenb@google.com, Liam Howlett Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,USER_IN_DEF_DKIM_WL 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 From: Liam Howlett When initially starting a search, the root node may already be in the process of being replaced in RCU mode. Detect and restart the walk if this is the case. This is necessary for RCU mode of the maple tree. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Liam Howlett Signed-off-by: Suren Baghdasaryan --- lib/maple_tree.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ff9f04e0150d..a748938ad2e9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1359,11 +1359,15 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->depth = 0; mas->offset = 0; +retry: root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { mas->depth = 1; mas->node = mte_safe_root(root); + if (mte_dead_node(mas->node)) + goto retry; + return NULL; } -- 2.39.0