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: 13094268 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 80963C5479D for ; Mon, 9 Jan 2023 20:53:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1A9458E0006; Mon, 9 Jan 2023 15:53:49 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 132AD8E0001; Mon, 9 Jan 2023 15:53:49 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F3D058E0006; Mon, 9 Jan 2023 15:53:48 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id E60228E0001 for ; Mon, 9 Jan 2023 15:53:48 -0500 (EST) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id B12AC120BD5 for ; Mon, 9 Jan 2023 20:53:48 +0000 (UTC) X-FDA: 80336462136.22.B74E207 Received: from mail-pl1-f201.google.com (mail-pl1-f201.google.com [209.85.214.201]) by imf12.hostedemail.com (Postfix) with ESMTP id F2EB94000E for ; Mon, 9 Jan 2023 20:53:46 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=cDmwrsTn; spf=pass (imf12.hostedemail.com: domain of 32X68YwYKCOwgifSbPUccUZS.QcaZWbil-aaYjOQY.cfU@flex--surenb.bounces.google.com designates 209.85.214.201 as permitted sender) smtp.mailfrom=32X68YwYKCOwgifSbPUccUZS.QcaZWbil-aaYjOQY.cfU@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673297627; a=rsa-sha256; cv=none; b=LZh0yNrmp3jLt3/Bb/n+A/tfvMZ7JOs0R/uQEN7asgF23xWSrQWZiFz0R1YniKYQoPp5wM zcmfEZrOUHXYsZjGmRL7ULE3Ihd44Nr2NvcFxZAEM4UPZx1zfa4HuOBXnAAtTai3vBxrWr OA38UAOLoS/PwZTOzfkfmkZ+g0UXWeM= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=cDmwrsTn; spf=pass (imf12.hostedemail.com: domain of 32X68YwYKCOwgifSbPUccUZS.QcaZWbil-aaYjOQY.cfU@flex--surenb.bounces.google.com designates 209.85.214.201 as permitted sender) smtp.mailfrom=32X68YwYKCOwgifSbPUccUZS.QcaZWbil-aaYjOQY.cfU@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=1673297627; 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=GU7SFbwLvAPdD9ofPJY8ZC3AFrLWlaqOvHr/TBsM1Ak=; b=H8rFJi51AgRruzSpe1fTDQpO208KygKZe2XJd7nus0n8TaRM60BtGAKni6KgKwxWSztKjW k7Vv66n3jcj0aztuljGyyHBCfS1JPVD/tsaW5vublLEhKTTx6BPSJF4qLJL/htnpTGngLX M6G/uqlApa1SsuF11Piopv1MWY5kqMo= Received: by mail-pl1-f201.google.com with SMTP id l15-20020a170903244f00b001927c3a0055so6949251pls.6 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=OlFGqmQRVY+yp3uIrZdjSjJCu+FgJAlgrhqy0Q88zAZ7LJKhigSFiKR8V4Qs137yRF Cc9zUIMq2+SQ9/qqzgS2S/EPGnHZV+zoZInsnqwO1jvou7ocCdHggXE9TFUxcRRfYHRJ oji81DfiwCXEqVxFL12kF62o5JaV+jQXe9RqqGCeNI3QaxYRmVizb+U7Wa6yrrjuLwoh Q93qqGHIo9yu/TOM2EribUlrrXsSqA6oCu7SSMTR23TWccJPDtsQC9PEsHMe675zePrT QDjZKU9zr+HxrsaXQT04Gde8qui/MSzn+5p4WYRVkfOCrjjiHB2ca/65jTKn+4gonUbO PgMw== X-Gm-Message-State: AFqh2krwZBprQP0O2oDaI9dhW+waYuzRS2CtXlDDFe7CNwvO/E2V0qA4 2nRDFeBc6rB9C/K/p180sHDOjqmsH3c= 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-Rspam-User: X-Rspamd-Queue-Id: F2EB94000E X-Rspamd-Server: rspam01 X-Stat-Signature: o1jewnsugkk8aiaopakemhc59eu9gknw X-HE-Tag: 1673297626-789174 X-HE-Meta: U2FsdGVkX195cVYtq0WK05o4MtQw6v7CiaKRu7CgTsBXZHUCa4pPITNnKUZWqPPXDScvVHnfVNL4QCtHWXiNuQWRXn0iJ5nfJDKP/isShsdSkkAU23zWXf/tcFAZygNLJaQqKwpCC0QcqgXrT87F3AAg7ahevRpj3Z7vPsSzC4zw+4MxvDjL4//C4g6pTX1eCUUQgHgnPRQHk0DMfvSkjbKuTiNiRfsgxgiUCgoUsIzJqSs0Fds4NCvXcvqD/UyIOzN0q4za6uftLI6WhNf9xDhZWjOKl9T3HuFoZwm+uOxMQjJB9wi8HhH8xSl0HqBMGZy+JIljZrp9N8kN+M9YHIe45fKLkyrUZ6AbCFpufeD2axDeCOLyr0ZJ1ffIn1CGD15ZRmMO50828cFLuIyq1Iq1VRX9C39JrP2Oze7ApQTsO8rps+Ed1oa/a3h9sCjR3qYXGsTvJXR3eflwnRXoVxyonforQbYL2J4RCf4ihMrCry4XPCIErSdfXl0j+TtVWsGFUBaM4iAN81UQieONYHotj8woP4mKR/5MtVL6/UvQDw0gAQIcyWNNPxwvTmWBbyKMmVNhHKNuFLHTSH0h4WNt/qkb5xlooerOUxXUa2B0PhpGoIMaQoW80ON5njWOhW8LQJIH+MutDQoNN/zMwHFDo/KRqzalHmJSWyiizbXdfZbqpvc54SBwMfv5p9DUG8Lo0eYWHghNJ9bkBSikn+HSbkajhU1GjduxgZ28TXl/IhRhC3+VgZcarKQRm8muiK08ECOi2yKN9r375xBIZfGWqksMZWUQa8Uoc5Vye7NA8Z1qJIdiHcG22udkm2YUnMZ9w6bAmbwBi3kC1wdL7hWQFgyCZfts6T3FISylP/qxIxmhBfq2frIv1pb4Zir7xjXEtWLl8uhShJU1yUyEYdVDk9Y5BId5EkO5100ayfndOX06xeMkbm+IYg9uVmnHQAHZjjaUJ1WcG542vVZ QBBW7dzI kykR7u9oy6MVGytAlg+oOYDleciuItDKSnogMw4x0P+hje3DQZ1PffBIWWl4RjT0iWw3Z+BGDacqqH0Fb1lz4uxmsuI8bbtNicWoLxoVycv/w0jTBBixznPZbTDyEiVPCnA/WU7Vmky6x92FQE8kLg6ZSOjHFs53giYCzjWTK9Pqij/t+CEMPYXKdOEbogVhnUmwiThofNrkmG020qe6NRV7SLIg2wpWUMV1oYcdbfSNYC7X/Lon93JKdO/+EuHFghSlw+ZgdWPLD/+d0JEiXYmhrgEE8BsAgVS13kzIYa3aboZNbpAtSuwCZIgYdGk7IE+9B5POTivOrncrG8N+pHiFyQfjx/5GYhIurznOWNEfuE8aT82Bn7SZzSPBs6nFQWeBKYEeR0toeHWOZP7Mcd+flv9NQF4HOVZsH X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, 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 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; }