From patchwork Mon Jan 9 20:52:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13094311 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 9A49DC6379F for ; Mon, 9 Jan 2023 20:55:27 +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=UqbgGdZqEvr/KdkDnCBvswvryo7SX0OTGMQuuh3yljE=; b=lFwfb7/qkLZiXaW6Oy27nXU6ca NOAef3jW5qxGgwp9dNOdOMPV4vWjSA+594qJgf3ERkWDpyr0PXLH/rKvxjYR5wXp/komqaZ+QOyU6 DFTipLBfK2AefLLhNNOumIbuhDpTqq1zGk1hFTPQ+gWuP7q8gYav/BJhJVX5WsYnc1+aH6nOXOGmP 8Vd8GN2CEE7uXqJ//WdXQX4P+OY0dSTisTqSRE8ewmJ/z3YNXhfH2FKkd3o6UGuO1NpxC3/y18nRp R2tpkXGwwIjsEFUn01q6KQUHyIFjOKxdzrVkxMF1VBtMiK0sziLe3hXQZy8sOALEyvFp3Z+6AATQR 5O1AY+2Q==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1pEz9i-003zwA-7W; Mon, 09 Jan 2023 20:54:06 +0000 Received: from mail-pj1-x1049.google.com ([2607:f8b0:4864:20::1049]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1pEz9P-003zkl-DX for linux-arm-kernel@lists.infradead.org; Mon, 09 Jan 2023 20:53:49 +0000 Received: by mail-pj1-x1049.google.com with SMTP id 31-20020a17090a0fa200b00226e43409c2so3541595pjz.9 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=qoUX2SRa97lcfilpZxl+EMStXxA6t5/VqNUgmNByko3I84+C/X7KcUcBvpSdeelF4b bUMTnlmdEp83ev3Z6tQ7vJ9J0qy/cDm1Mzpr1UgIjBc3+Kw2CTJndKcpG+rPdEgh9IKT BIXNw7uBh4IPMHT75NoNMRmAKiFXiGrst4cva5Q/PMMr51gVdgfzcCjjWeqbP9URs42Y kyUWfur7L4auv22MAJ5WkscjapUP3LqOrClU4lBCJweYcJ1Cb+BfPj46gBXg/gMuyidE fs4XBHbn7YDw+R5dvWRQvjKDXOtAgIhVEFCVwrDrzUBkhza3BbmWfZJbM4GByu8AcMXt mbPA== X-Gm-Message-State: AFqh2krb273w48KxXYrXSrYn+jytNrYbURNkak1voBXn6iuduyDWWFmd Jo150fRs4ftZ0Wu4dS+015wHz0uTOlc= X-Google-Smtp-Source: AMrXdXsx8jOEqF8lBOHYbim74eUIuqk/BpJXbormK1OrkMgDb8c5pT4kOfmHApmrR7R22KnvvmwfjroHm1I= 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 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20230109_125347_524626_1BE5DC16 X-CRM114-Status: GOOD ( 11.84 ) 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 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; }