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: 13119249 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 E1517C38142 for ; Fri, 27 Jan 2023 19:41:42 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 76E096B0082; Fri, 27 Jan 2023 14:41:42 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 744136B0083; Fri, 27 Jan 2023 14:41:42 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5E5476B0085; Fri, 27 Jan 2023 14:41:42 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 493DF6B0082 for ; Fri, 27 Jan 2023 14:41:42 -0500 (EST) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 279798075B for ; Fri, 27 Jan 2023 19:41:42 +0000 (UTC) X-FDA: 80401598844.29.A94C370 Received: from mail-pj1-f74.google.com (mail-pj1-f74.google.com [209.85.216.74]) by imf08.hostedemail.com (Postfix) with ESMTP id 65C5016001F for ; Fri, 27 Jan 2023 19:41:32 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=ij3G6594; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf08.hostedemail.com: domain of 33ijUYwYKCKUXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com designates 209.85.216.74 as permitted sender) smtp.mailfrom=33ijUYwYKCKUXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1674848492; 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=6D7AVbhEFxAo5EKdbJ2HQfTq9cKDp9C6gMDUsIDn2rU=; b=CRhlGRdcqB02SFnz/mxamiiOQqV7kZAgrTKnc/ygRgL2KciusDhf4XhA/HI3WoODzaPrtV LW8y7rvI++R0/jMVZN1MgVbF8wFtBtkVcxFz0cZBF+l6rj9HMOh4qDB2Ts9keru/TRrHwt x6GhMnkhyBATAw5/v0TWawWJLyay7WQ= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=ij3G6594; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf08.hostedemail.com: domain of 33ijUYwYKCKUXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com designates 209.85.216.74 as permitted sender) smtp.mailfrom=33ijUYwYKCKUXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1674848492; a=rsa-sha256; cv=none; b=fjoImR3L+EIrUh/LdgpLpmUPO0Uf9q4kiE+RXqwwID/401RMfHJVsVnioje+cD5Nwb+UT8 s3lbHJzpi9AB/2e2lE0eSXtQTGZvfofkGisJxowYJeSSu5Hk1G52Ufadnzno1PAGvkhGwr kgfTsRm4y7tJzMR3BcKK+pkKEZVOt2w= Received: by mail-pj1-f74.google.com with SMTP id gn18-20020a17090ac79200b0022bef1f49c9so4968053pjb.0 for ; Fri, 27 Jan 2023 11:41:32 -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=RGS8k/JzlBawOwYcIbOPUHAuSzxy+x1VmdH2cxuRQc0IpHGG0HG87OuGsSX9eBvVUM tskW1Q2ZF/oGDQh2HBwYMd7h+Y2ZmV8vlY/ZCOZxTBEZbqxvc4IcVijy3D+itByrW0Su h6pR4eKAsWrNJSkBXQm/RkgI5P/iSu1vUn1a+UQqJt2BvuUZzahU7Q7qr1wP6pkCqCuJ OBTGMwmUTw+uqJS0UK4ceWOYXPSU0LB6RKalaKUMD2oRy/jHKTKnDLFeLk2rnsWsREmZ 01J+/KUFLXhQo0NK85EwXZTTuhPmrfi/79INxPDgxj2hF6EA9NWIN8U5YCAIXbik3jTg Ynjw== X-Gm-Message-State: AO0yUKXDQ8wKVbO+exwGcrDs3SBLra96hbU2n+j3om4oIAVSrqpDt7bb Vmucu0DYSKE8i1xFIpC7LEyedyw7+Ks= 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-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 65C5016001F X-Stat-Signature: ei1j8uhse7n95sdozxnwkzgsc4zmszrz X-HE-Tag: 1674848492-74319 X-HE-Meta: U2FsdGVkX1+oXg8ElVYqmHM8K73jgmNfB7edvplSgMcUgu2bDRhpFNfhxLoH1fihV4tVvgQAPk1xSw44/iRxxWOWyDVAnSyHxIIP6kDlwf3rv23mMzvMZXOeJsLQrvLq529iW/gofc0oYvFxHjEA0MRnyWz+162R0u2hPiBFq51LOiaf6wM+5cs6fwpAi0xs/4z36sxknRN+1gTuTiR8sJTjewESL0atAbV8czeFjdVM5CfcXfXg87VhLqXdDMW5WecVsUdthGK9otOmmpYjXml5kPnGpyb/E/xpdcSK/k4MWCJiJIJomtEjuD64o0iTtqLeAnucXagzn7Fdq9ZOlVLK+gheDlhvCDa57WNOpWnrDU2XmnDbsb8/YVkx11CQRawSOoO9qgqbU01A7Jq8K7fw0VJZKTipXgXipeznlkNOyQOQiCdIdrVq5f8C9JNmSuAdMwqP+3ujnVbAOAhKuclF7rcNOaxCncI8qIvW+2NlMel3DCgxOQ2W0VJQPTJibMMbdi8tsV5M9QkMyX4dbfOHb3oazeWru5DcgtBLQWtuyp25Kmifzz/3Te3UXd2QjrWLKVzX9Bgman9wgf3k16103FWKG/sqT53hLcFce9wNTXNU0OtBfkq0b/4eYfCAlrGviFTBhBguQ88pXrFoZtlYo1lO61/07kM2UxQSf+D2XU/s8rC/+Z0iyuvYoN3goUSFeCJu1dnrBHrz7tEsSRksfOunu1IjXPdxKG6iyrPj1cdSURS7ZXDVHWDV9TL6x9YN2Rk4qBnl6BbgUa9hZ1Icmu5EvlNUgUZ6xnboa29jFHftUAoazVIcOKuBN5uY68Sm8tLcRuKOL8w/K/zVdz+3mWBLzmiUjSauK/rebFqYudKJ4z/N4dIunL+KpQkArbGTTkDhkjb4nCwpP1MnL9gFJ4h3z6B8OkJA5xIPB4ciY6w8E1NJy12FGJhzrrw7n/Sl9yz/6mXRqp+SG7b aXndxrIx ia8N9qqiZQO6vhxllXkMqBh3N3os03co+fonxGCqw0lI9WKdCXzIFiuBxVp6JPZ0QlEGJYFiolX8WaM2HLQm1chzK8MOnSpasM8807DlXShgzoEb9bFoKlzFPnBcSzQIgZRu+bENXDSAcuQBLnvBIz8ExKwEqHWTJ08MOx4e4+9lDTWaZPTSy8ylhD+oXhyWaOQogeggtrY0CnrZiTE/ekksokf/vXGS9vhQzNWeeJ/KSDVbUd1K/qHOHXO7NeceSMG0jY1eMd2+Kgeq2WhAAAC4aA82gmEvxsFC2uZMO9iOIgiOT3G5RTw31V01rCZdjL31V9f2nZAdqec27thFyAnU/Alep9ZCC3aP0ydhfeABTEVXTR3y6eMedC+9SNEzor2lbbkYx3q2q85K0WXTmPOac/bPArHvg8djZaoiJQ0lcXkmUkIhuO9poABgulH0xoE2LFBDRWBoaJvyfcCpEdR86jjIvuDR8ooIfWxyB360r3tLF4GFl9tKKT+5AaAyCvLmdbqUBUHRMVHAz1gJMsqh4SxaO8gFtiXTADb8aEHCgkTCe4ZkrpZgAQvQllcWRCfMe0uK4NaxJYQr95qNmIqndUL8NTUNZWCoxwDsgcKUUyvCZwGjgejXLjMZeT1nMlZGip0K4+toCE7XJNPZOIe+pwuCTkJfpb30FsURba6doSQ8QdThsUpmY90b5dLoIMPOSSW9pkQ5BKDJ7GAPfXC/XLnModYJAmr0xuFiyr4DkYQzcvZVtwmaeHMe2saNVEp4ldMfnI0IMMSg= 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 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; }