From patchwork Thu Feb 16 05:17:17 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13142495 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 1F91DC6379F for ; Thu, 16 Feb 2023 05:18:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 346D26B0078; Thu, 16 Feb 2023 00:18:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 318EE6B007B; Thu, 16 Feb 2023 00:18:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2070F6B007D; Thu, 16 Feb 2023 00:18:02 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 0E0CA6B0078 for ; Thu, 16 Feb 2023 00:18:02 -0500 (EST) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id D4FF81603AF for ; Thu, 16 Feb 2023 05:18:01 +0000 (UTC) X-FDA: 80471998362.10.41E0EBA Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) by imf24.hostedemail.com (Postfix) with ESMTP id 2F862180013 for ; Thu, 16 Feb 2023 05:18:00 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=gSbKQNPX; spf=pass (imf24.hostedemail.com: domain of 3hrztYwYKCNsPROBK8DLLDIB.9LJIFKRU-JJHS79H.LOD@flex--surenb.bounces.google.com designates 209.85.128.201 as permitted sender) smtp.mailfrom=3hrztYwYKCNsPROBK8DLLDIB.9LJIFKRU-JJHS79H.LOD@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=1676524680; 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=eiC+Iexfup+RTroKLCxxsKt1sRroZAPvjqioHV2wMiw=; b=zl+M+WYUz9izmxbpF8C+n0REjJVUIq8xILwNHnwyqiSVYU9q4ymzyhEPPNE1YyGVnSrvfH GHfcZZ6hbr9ruCJntvKSwtOwUb/ghl9c6jWOvLIeFBe6lZ9W2fruwOYerYUqRvMU9NA47a 5EHCGmiSyeGiaZa0GZ/VoIbJeKyNwqE= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=gSbKQNPX; spf=pass (imf24.hostedemail.com: domain of 3hrztYwYKCNsPROBK8DLLDIB.9LJIFKRU-JJHS79H.LOD@flex--surenb.bounces.google.com designates 209.85.128.201 as permitted sender) smtp.mailfrom=3hrztYwYKCNsPROBK8DLLDIB.9LJIFKRU-JJHS79H.LOD@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1676524680; a=rsa-sha256; cv=none; b=yxDApfKA0cPBKvyPjiMAebxMSsiKXXvH4vGJVTs4gwTFiAwij+bQQMEBKLob2suQoXulmR aO4Lu7Mt5bJzLoUmjfbXI4IT1GXajhQxIgV1E8iAKgp1nykquUk6dwYo1pYcv7zW9ln/TY TcPf15huTzXrnPyIPNIuwzlXpkrnD/k= Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-52ecbe73389so9085177b3.0 for ; Wed, 15 Feb 2023 21:17:59 -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=eiC+Iexfup+RTroKLCxxsKt1sRroZAPvjqioHV2wMiw=; b=gSbKQNPX+j8W3tzxYZsRNAblkFTxWANtMyo2LSqGNkakVHWziV6JTyqlohrqDf6nLO 7F5N7WpIKnXsbFPEflJy25rhat2iqZIJRLZvV94iATncucILtc8zFlPzaxOQpEoApKoJ RWEtB6lTCeOcIkp8qbIxk4V683W1L3zeK3vTsHv9Yla4n9gJP1xuJQs99Ms5w5HF3olN Kli7prX+XczaCsAJ+8hVggWwSYtxp34C+A6/4yuDSchSQcAT4VW0lygmuaxa708qKR/5 zV/LK3WvWxvtgplCG5tRDu/7iPKMsNWXdzFiEgVvRQ3tE0ZzhzdCi73gDraIVPZ+cD1H 1RBQ== 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=eiC+Iexfup+RTroKLCxxsKt1sRroZAPvjqioHV2wMiw=; b=qYlGsU+q9CPHyYCzZjx0K5qLr4ST8a2Unu6fApKBZSG987M+FM2P/tRCbnGJgjeb8D 7HS7iMGIF2cHjEK4Dku6lnvT4zfcqLMjV/ID5bnYL0B1fd8vsAZu78qDfrAJ7ptkyi1J tYo5dcDZbbEow1s+5ABJ0TYZF693WOx/6cEGgumXqBqDLleyDr5YsVLcTDRcV7i+YefJ K6p1/Yt+0yiygRAh9ndWvhZBjMVQ668v79PqlJQk3FBXw+EFxiOC9VjHx6zHBsTtGK+b rtNEW0Wy1VF2FUBiBato4KjfoFDsVozinVXcAsUnWbnXfJclAWYM4emC6E2rywAOrdw5 FcpA== X-Gm-Message-State: AO0yUKW8PZXNVC1j8Isr+C7bDPyRJ/+rBUS1OS61MfSf0mSomoB1eiNZ AjSBgcUQaDYXlgAIm1/34sszYkj9F0s= X-Google-Smtp-Source: AK7set+h9VKChaGyyozNEu9Udu5uv7zPqiNZXg8WkDwG0C713PEP5x3O9LtVk8xkCPSk1ZyxP2XheyHDpnY= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:f781:d5ed:1806:6ebb]) (user=surenb job=sendgmr) by 2002:a05:6902:10f:b0:855:fa17:4f5f with SMTP id o15-20020a056902010f00b00855fa174f5fmr78ybh.1.1676524678798; Wed, 15 Feb 2023 21:17:58 -0800 (PST) Date: Wed, 15 Feb 2023 21:17:17 -0800 In-Reply-To: <20230216051750.3125598-1-surenb@google.com> Mime-Version: 1.0 References: <20230216051750.3125598-1-surenb@google.com> X-Mailer: git-send-email 2.39.1.581.gbfd45094c4-goog Message-ID: <20230216051750.3125598-3-surenb@google.com> Subject: [PATCH v3 02/35] 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: rspam07 X-Rspamd-Queue-Id: 2F862180013 X-Rspam-User: X-Stat-Signature: swnc9wse95isadipzqf8ag3dwsy9566h X-HE-Tag: 1676524680-804685 X-HE-Meta: U2FsdGVkX1+bLoUt2cNMUgdqiQMKJ2s8mJsjunkEWhtf2MpKR0JIfxzhanH7dipAvep0gMaEaTykgNLFvawj5EIHgIE+EOzxN40NlVatoETqBkaC5udmd37TOrQXbew9RRhJvmLaC2XYEM9ATN6bObrI4d76m7dJMcaDIkZ5rdQBzhGwPexTXc3H/1x2lsN/iJ7/u9+cQvpLaui9lrNORUIlbbJYyb61WMd/t16Vgu+KDYwL+ieo254/rnrb7ntFqdDr2N/4J7+cOaf4arXnlln96iWG/XCmDuo3ZosMMvIWgCzaIxy4m6G8Eq8GJKrvPawbMPef/jgtvDZEmTfIbccgelJJogOQl2S3tF6tBTVrrEyfxyA9lRqAVJQQ5GGAiSjbREShWVwGU6m8DtI7NK87IRENuvJr2QKZpDMQhYRyax1F2E1033OnBPqctTUcJtL6hIKJYizRovERsnGqiWveVKZCqETu0SjsUSFJG/MfKxoX1wvuPRf7Y1AOhfEoqJKwzpoMjypxr81Mn7mXhiqAU6kKn91gzqJHFb7BmkZQKEqyad8ca65oyrLk7m0e8tgRd05/WEbKjKH4mxBu7TcVHRvVM2frwG0rVckG0gJ15au7rrlD2gKOz3t40+QF7PckAsFSOqE+SgDnl9G4l80GAFUX5Cy/ih59VEKQR/Wu9u3M6Rbg37/1zZ8yN9O1MsjSM1Hmp+70syD6V8M7iqv6c1MlJRXDQDxzeA0fJdZ8LbY2CuueLVolyYlkco7SWJ2WKvrcDXzHwlqvsLuQ6Snble+05owDfeUS4fz4RsHVz6QG+sECN6L4/UBd+kJ6x3ezncKb9SfgxT00QWPN7Rl0Bg1ftl60Dpm2tcsqSNwdOm0NMdKv5vHE2kK4FHOccEwFxRtetgNNyMI7y+pby+8OyYFtrAQQiKRIOfvFUh7pkN5D539Z9xgk+zopm4JuZTKnw6aMl+ZGXfPChoq MPTgL0e5 W62QkcWcOB9Q08tLlPru1VZ/tdRY8Z9PlVSn8MWFXTjH65/uGtuUTcD8X/XDAh9WXkgQdcbJTcpzoYobbgb2cTy/EWjKL3jNAzz6mIcqjHmNgsQSfml9RusZAONPQBP4HS/MDGlbL+O+obZhkZyLDriIeJf8gcHHxgKf9ym5h3lfgNxE00VNoI8AIu67eTE55N7oaK4AMwC6JgGrWjY3cVGeIc0y9duVLvFPqeIVrLPRFD/IZyP7fCKJhLvXdlVLrbV6+XFA2qO8wGgUX9wGXDfUq+yc+cx2gnIr3/KXjXNyY4seiOa15+bKBMtEsfLn2QHCla8y4mmMyBgO0QzFqFQ0Y1rLbkT1HkvSDOpKtsifCY9OHxkzRXlUuANoL/E8D38iS1Km1+LsI/lpeXVN9Wn23vOy7zasimTwnycTs8bGzkdEwTkcEEx9RyV7Co3UcIwiCWBbfqi7vAicsM0LCPffJb6Bx/mjgikA1SH2po1XHcrz9/gfQdaznqRQa19Rim9WhteMFIdrPlDJlEZOtNWO7uH0LMn+uNdBeVkQC+1XZ1WZU095yOTf0ou+vmemnqrsqqvYwAdxPG+SrDnpW3eP5zk8Iqgq0lQFJ0LnKAMARzDZSfIUOV6j7DtEWwWgulIUZ0MyUnVo+hMTNxD0gkbdZ11LpRaCR+A/JHeaFXVvAcd8ju7GsovYR1FI+ndA4k33W 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; }