From patchwork Mon Feb 27 17:36:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13153965 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2931DC7EE23 for ; Mon, 27 Feb 2023 17:36:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B728F6B007D; Mon, 27 Feb 2023 12:36:45 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B229C6B007E; Mon, 27 Feb 2023 12:36:45 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9C35A6B0080; Mon, 27 Feb 2023 12:36:45 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 8DDD56B007D for ; Mon, 27 Feb 2023 12:36:45 -0500 (EST) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 35A8812039A for ; Mon, 27 Feb 2023 17:36:45 +0000 (UTC) X-FDA: 80513776770.15.4A81A39 Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) by imf04.hostedemail.com (Postfix) with ESMTP id 44BA140004 for ; Mon, 27 Feb 2023 17:36:43 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b="Rtawk/5q"; spf=pass (imf04.hostedemail.com: domain of 3Kur8YwYKCBkHJG3C05DD5A3.1DBA7CJM-BB9Kz19.DG5@flex--surenb.bounces.google.com designates 209.85.128.201 as permitted sender) smtp.mailfrom=3Kur8YwYKCBkHJG3C05DD5A3.1DBA7CJM-BB9Kz19.DG5@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1677519403; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=lArWv6/BKpLmlLXC6GszXodHEO09dxzXTjGiFRBLB5o=; b=3ve/8mTg8UTxhUBjp4TBAVBq+ZJvjkZSYFjQF9WU6U37gxhX7gre/PSQAehquVR61AOc3F 4o3BMjF3HYTOTenkqKj3625WfDAlMZP9cO64q+BxWPNsKeTWQ3wplHSYZ053AouR4OIfhp fULCVpZ2nBuYD3XfroPVdcBem4dAxzU= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b="Rtawk/5q"; spf=pass (imf04.hostedemail.com: domain of 3Kur8YwYKCBkHJG3C05DD5A3.1DBA7CJM-BB9Kz19.DG5@flex--surenb.bounces.google.com designates 209.85.128.201 as permitted sender) smtp.mailfrom=3Kur8YwYKCBkHJG3C05DD5A3.1DBA7CJM-BB9Kz19.DG5@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1677519403; a=rsa-sha256; cv=none; b=M+U6tCTBSSC8TDTBXEsi2bRKTqrh7qgd5fZZYgoregsDJzcpVi+/cGOwyGpcPMo/oQOqAL t93RCMQtyepMg9OqCCXB8Zcg3+LhOSz/0H/A9B1GzlHcqjIdnfNkpzEh6xxWDjx/PDme6J mnxeygqbkEhq/+xtkmmMbIy0O+vRmcI= Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-536a5a0b6e3so155576817b3.10 for ; Mon, 27 Feb 2023 09:36:42 -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=lArWv6/BKpLmlLXC6GszXodHEO09dxzXTjGiFRBLB5o=; b=Rtawk/5qB+wQAwcC1iD4VXuhoYDvFfWXoR8TLDjNU0mxzXG+OcIc5M1YDwWsJSdzc1 5ov0BA8i2CNkZg28B06fzU5xhMSs1uI1giDFkRO+7bYBZMhhkWnMlBAHldMBIWHj/nI6 Se6XX7qnInZ409hEUwR8XAgKIrmPJD89Fz59bDJnlZVSabti6XILWdKtE9EozNXeoXJo jeE4G4VS8SUdBqPqEoVdM/8Bov6AoMRWvMj0a5NQOXvkupkTbiI158Odu2A7RSMPsE77 crrvpWC4xPR29dzTvNq/UerrAnu3X0id5UHZqYhq5AWR42pdWVuHy+UOicXnyhpFqhVJ jDJg== 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=lArWv6/BKpLmlLXC6GszXodHEO09dxzXTjGiFRBLB5o=; b=vNP8p/0y+y3ysPjgvN9rERABo1cdz9RtNTg7hBz2aWz9zvcpZX2o4vTKdu59BWR20J JS1Qy659V6VU5j8OHW6v7Y4XFRpTJhEbaJcBJGURai0Y4mUxK4GlG28JgyDzbjDrVVLd oa/JZt0GQbUdS2sT0N2eALzQfBoCaby3xZhX/xJxRSlsQPimp9LHuKfYEfV68n65IhLA HR4dpV7bkYDfb4xWu5WVHZ946zEn1hItGIdI6zC5z9E5VVde0aHVOpDRtOSYuVOERrfh c6w+rWGioHYC5UUBtgOvIudHve2q16iSNcsg/+6/dEthCOqEShCMlVBcIqLQi75ohf7T 2N1w== X-Gm-Message-State: AO0yUKVJOzcykulzLh0S3M/90qY5TjJ6fncuIqZmVikzNm7XC3XXlHN3 95+Xb63oBvPn+qmWLSEFrODRNsWLs2I= X-Google-Smtp-Source: AK7set/6BFahylhHoQQLwR3PqP3k7QFJ6TbZ44w6th+v/3oGX1dR6WIuOL9QS1wjUZYjoh9QnZVdIWwPxxI= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:e1f6:21d1:eead:3897]) (user=surenb job=sendgmr) by 2002:a25:8890:0:b0:a0d:8150:be04 with SMTP id d16-20020a258890000000b00a0d8150be04mr7185754ybl.13.1677519402335; Mon, 27 Feb 2023 09:36:42 -0800 (PST) Date: Mon, 27 Feb 2023 09:36:01 -0800 In-Reply-To: <20230227173632.3292573-1-surenb@google.com> Mime-Version: 1.0 References: <20230227173632.3292573-1-surenb@google.com> X-Mailer: git-send-email 2.39.2.722.g9855ee24e9-goog Message-ID: <20230227173632.3292573-3-surenb@google.com> Subject: [PATCH v4 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, chriscli@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, michalechner92@googlemail.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, Liam Howlett , Suren Baghdasaryan X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 44BA140004 X-Stat-Signature: jnshk1irazsxsxn38fy8estgsapnhczi X-Rspam-User: X-HE-Tag: 1677519403-856423 X-HE-Meta: U2FsdGVkX18ND5ZXd+YuVt5BsNtMQJR+Uv9LlZf9fbiWvO/+0h8xITpggvqvHK0lTjFdjyWYz8UXivf+8sttEn8HD6++/dfKvm9tBgdRRXn9zaiBTwk36CYv06EImrAhoafp2na7JgrDRcD2E5rAemT7OnyL+nnTkzJGwc3Sh6gJSfpZy1uKlFFnmTVB3nLS+CExrhS162Gosukq4EGhI08TbTeuzLpcd7Ctr9yJV+0k4gIoQ6UMLM0HI1R9ax809bZALNBf+KfzhntxCNXf2ZAG/JpUkoHBZAWu2Nq5P2d4KbfPmfvZSvsBEqFtLOOgwyB26BRWHiq6+nmOH2xJcNf6i3TAXvzmDQk2Mpuwaioj9yD9Jjm7Daslo7fxbsqwBAuF6UUB+LlJpT9HhkLnlpLFpaQ16MIj+hdCBwC1oG5Iqm/3nE4RiuYLGWt/lMvLDFQdBG6y1HO4hbwiDsn7/O2kajcGkH3UJbmf05FbZ+xWKZ8uQyl6nYmggFFxFJs/g58zXUsSvEHScBGeTYQtWqV4SVehrgjiESKSJKi6Ks8TK71Op+HM/4s0oE7NEmCEUTBlYWiFSjKTBHoXXdFsCe6avp+x4wVCA2BZqoVnye0x3dOzT856oJkLf6CyFtrfAantOz9/KEi0eMWkWRSXW/ZqW9vrA6ta44JQh/MQORxdpwJWrVsSXx17C+7f6rMzt87OSh+JwHEIjqxrH3UMW6BzwEJ/sygXHlVAWxBL8btTZM88Ov3bW26K13v00+KQZCrfRaLvsK62FkDkBvuAf3KaXH8zyKhXL/6BLO5xabuzMoNGJECXh0K+/cA7d7Uw7AFgHIDzuVy6jXw02ePKTX38cAWwqzg3ksqSzlv4Nw5nidaPydA89AqeBJOppmLM7fWt82Ohxx0UIiGezUd9tTQTlWqjSg/QWvlMh/McQ80A0Lr4YvA0Sv/dDAz/HXgXpY/S4EntXNTklO1QHJ3 gd/+6bJI F6PlOO+XDHiaExIEsyVGp94ld+UG3OvLF/nbnOLTsczZv2vmy1KvQy8EZHkqPx9FQuEfv5t0osf/ItPN1jKKBrcNFc4SGG34LfgQevlsHSMfiPDT9MbaMMYlxD268L8PDaxH8zozrgxhzDKiByLvBuVhVGh3AuH9h01/xtlJtRWUvtdjRqmBfsrRZClKnV+ejwSXb+ttEIIkkwM/19cyCTUrTI8TJL34xvaVVMPdQO9FDWQ6A7cBZssZyQiwri3rYwJO21XCNGPNHJA7UgQ0Rqy94w6KKYek14kazXaujUdI9bIZcqi8P9yKfQwFZJAH4VH19jPVkj/nNZ+CycGsAQ557aa/TWNhO4ErwbvYb4PX8EAwxR+jT86bwsED8K6JUfk4mfL2YMu/0OsSrn8VP92ShmGQCl9zm/a8mFh/AB4/N5Nb8m/Dg/jSGnDFjrWOBA6/yBgTMVdSmAdDhEjVaqh9x/SyMgyFItFxIU0XFnStPOtsqwJ6zVPsoBL7KZQhA5fZQgDHjaDJTZeg6vI63x1TSidqcyrLxEiFryEjSBG4E0fqp2LZNntbbKvUIszmX9hcsSMA8F44pL1zm4Asg+cxw0GrVjBHAWpO+cSzfRT49EVuOA7zhO8TsEOzsDfEjKDOQXxcIDqfYv6wHgJqEvaJGvt4fjAE8lw8fSKyNS1cZXHDxAeSZqsgnEO8q/jRxIPsP X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 cc356b8369ad..089cd76ec379 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1360,12 +1360,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; }