From patchwork Fri Jan 27 19:40:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13119351 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 bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id E0793C54EAA for ; Fri, 27 Jan 2023 20:09:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:Message-ID: References:Mime-Version:In-Reply-To:Date:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=UQb3IYPLVQUwnlIJLhll6pUBv/BDThTtDW9VWA0c+Xw=; b=fz1RKLtWCIeyqEoD3hZWXZdKt4 d3o2bUdnYWZoAOlzrhtmWA2Y7C/GKIcuUmNVz8ta1pBQq7raynFyvTFRerIxugnGrbcr05DSv8wa3 F0tyOAIMgfp6hwu++OGvAQVh4FDgs2SBAMkhyvn3mKNzYntEb3WcfaI5X+cBMSrQY+p1T/X+V+aIQ S8RXvvQ9okY1QrciWuU1VNtYGuiCNqYGqjWvctxG639ajYSjsH7LMxc5TvfCO4usuyKrMCIwEXM4q XuJ4FMhzgRPPx8TItQ0vPw7i1u74mvt6fUmBZ+F/htTV78oUxJ9dqetj/+X5G45/W8At/QppTkaEh 8IcHjipQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1pLV19-00GJDS-6E; Fri, 27 Jan 2023 20:08:12 +0000 Received: from desiato.infradead.org ([2001:8b0:10b:1:d65d:64ff:fe57:4e05]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1pLUx4-00GHQr-HY for linux-arm-kernel@bombadil.infradead.org; Fri, 27 Jan 2023 20:03:58 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=desiato.20200630; h=Content-Type:Cc:To:From:Subject: Message-ID:References:Mime-Version:In-Reply-To:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=6D7AVbhEFxAo5EKdbJ2HQfTq9cKDp9C6gMDUsIDn2rU=; b=mLCTEPekuf1l+NqF0eb3VVUJ1N NIcz54E41/iUKDIw7Q7UmCaBYFqcrY6AXTb9l+h0HRAewasY6q5wgO00/EJJOQwW7sh/1YC474eRL vc5hk6Ql1Y1tryZ36laPPKwYxZ6K61ovXkEJ4Chocrxm496S01CHCHjTRUKJGF23m071nRE1Rgetv Qb2gSaDJeHnb864FTWJrMJN974GXwpG/6CNACx6Rr1BRv68rvLZdCjzZHMnJ91JHu+czd3l/ZQutB PlNdfgZbZ7SNfpfH5bPttwf3aeysry64yD2n2L29vGc98Ir8db/EXNcvgqxso5I4TvTQr1C7vjRow beqMbnxw==; Received: from mail-pj1-x104a.google.com ([2607:f8b0:4864:20::104a]) by desiato.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1pLUan-002xhb-0C for linux-arm-kernel@lists.infradead.org; Fri, 27 Jan 2023 19:40:59 +0000 Received: by mail-pj1-x104a.google.com with SMTP id gn18-20020a17090ac79200b0022bef1f49c9so4968052pjb.0 for ; Fri, 27 Jan 2023 11:41:20 -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=6D7AVbhEFxAo5EKdbJ2HQfTq9cKDp9C6gMDUsIDn2rU=; b=ij3G6594G9QMVIcaC7y7IotZlrRGSd461+VUEA/BMKS/DqdJRnleVk5IzJ5gil69bZ nXwMrZpHBfopZhY+dBOM8TntT+xgyMzx0lhn0c4XjFlDdq8hUc51rQLAJayIjAlxU0Vs tSDUCQts0+fWuoHVHrLcPeZOnjtBdS6uOzMiFPrkU4AVT++YMj0+eDXitszbX73gjVet Uj7on6Z68KT42I30IFAHZ8MnQyKVo+KH97KXkIJWbVMmYdISzeeP/HtVHdR/3Pzjnpiz r0YfwFvkG3mRoMMu6hvaQ0O0QqVpO+Mcl7G8itnKrK/kLoHBd5Ey6CcVhBTBp6nBJTd/ 24fw== 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=6D7AVbhEFxAo5EKdbJ2HQfTq9cKDp9C6gMDUsIDn2rU=; b=NM0/32xcbb9qpb5/ZtqVGx0F6z7zO0AEURf1n4V8PE5lAmnCt1Q0EYjfLvpdoQGHBK e8HSKZlNk/n7EjrJtKJNgi74Dbxp33scP7MQtUOAH9imEGyApHV2Je8TbcnaBlDxLI9u AuJILS/EHJJio55aEuZSEw65K9lzdvlkjc14Cpd14ANL583HIG1vEyjp+qd/mmKCRYd/ s6eW/4QhUbolINwridL0tejt9B2m7txP20mGLbV1frCMidZhPmdZIWkyTpJdRlgyRFKK sQg1+NIoDYWCJ9tVx/hKVyk0QYeyej12YbuF9Rr9/mMDRccQIm5ozwI76xfmtkNH5mGy yILA== X-Gm-Message-State: AO0yUKU1xf2t6wdYs8DQI606i6l0zEQ6uh4vBDkzPSYmPDMU4pBJQkhl uQXPS2OFZf3lsRn3561YePdPpqEw8q4= X-Google-Smtp-Source: AK7set+8nPPCBQ/ToCHxQhHQnspD+CZKcqljSV2Aj5HMLvXZA8Wu8rpp2+AujJr6dncfulY9izqabQa2p3o= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:4e19:be9:c5d0:8483]) (user=surenb job=sendgmr) by 2002:a05:6a00:1990:b0:593:909f:ed45 with SMTP id d16-20020a056a00199000b00593909fed45mr72889pfl.0.1674848478930; Fri, 27 Jan 2023 11:41:18 -0800 (PST) Date: Fri, 27 Jan 2023 11:40:39 -0800 In-Reply-To: <20230127194110.533103-1-surenb@google.com> Mime-Version: 1.0 References: <20230127194110.533103-1-surenb@google.com> X-Mailer: git-send-email 2.39.1.456.gfc5497dd1b-goog Message-ID: <20230127194110.533103-3-surenb@google.com> Subject: [PATCH v2 02/33] 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, paulmck@kernel.org, mingo@redhat.com, will@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, rppt@kernel.org, jannh@google.com, shakeelb@google.com, tatashin@google.com, edumazet@google.com, gthelen@google.com, gurua@google.com, arjunroy@google.com, soheil@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 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20230127_194057_163160_A46A23BC X-CRM114-Status: GOOD ( 11.62 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.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 e5eeecd14eee..482e17a460cb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1353,12 +1353,16 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->max = ULONG_MAX; mas->depth = 0; +retry: root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { mas->depth = 1; mas->node = mte_safe_root(root); mas->offset = 0; + if (mte_dead_node(mas->node)) + goto retry; + return NULL; }