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: 57839 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp116708wrn; Wed, 15 Feb 2023 21:19:15 -0800 (PST) X-Google-Smtp-Source: AK7set+wEGd6DlEcubTcIlLN5KmxFLUB+cmUGJ6YczoYZzanSLgP3resgAxPp2NDwllWuBpW5rgd X-Received: by 2002:a17:90b:1b48:b0:230:7a31:b9ac with SMTP id nv8-20020a17090b1b4800b002307a31b9acmr5634093pjb.48.1676524754720; Wed, 15 Feb 2023 21:19:14 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1676524754; cv=none; d=google.com; s=arc-20160816; b=fRCALGH6z4EfBQpJKhHtYmKDaxxH/gLbwv/Y8ot+fC1fyPcEXnq0PP4S4KJ4zRCGci r5IIj/1By+tVpj2vCZWJN3WaVLmN+I/X3GszjqTu5UoWznKwNYB0BSNj40263NPZIfyR mwg7C9k0R0pEPp8/UwRHBJgEZWhMaWXpceVY4lsHpYZLFYZh0h6Gl5JnSac3xLmPNlSF 8FjAnqorDcM2YFrwABH++ZeXh0LAPU+pj3pXXo6aITPOyIdCjA17KBfeIyfAqS2c0sak DU8AXkwQedZBUoRGLH7pMz5pcaShvx6LWwrQrG9MbOsaTyzHPHZu6E0nEztlgz5irnjQ 1MUA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=eiC+Iexfup+RTroKLCxxsKt1sRroZAPvjqioHV2wMiw=; b=Lx7fDx4laA+WCpKXhTtWaSns58AWgtFSmn/GAtjnDiYVCusWwELQ00S2wjBbo52Z11 RLuMlSm1gPy5m9sCRzBxdlJ1tyIYBjt/Uv0Oqdr2N+kfkIrI9q05/GHZTQKdfj54VByt +YDGUQXfMetNlyKT7sCtq372uQD6oWn3VxjDkTY5+u40ck3EukLLhLsnlBtUmb3Df+Xu FXayd3/c4MnennIV3OTcVv6xldC7i4uKKfofHxz3wFY3H3gCC+NY1DqpZ8it2efyFfuu yiEqnrNSheM1knEHUzF+xCG6kVL0fJl9YaBL4DTsEuIfg5XRRpdJ024T3PxG6mCspFRX LOvQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=gSbKQNPX; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id u2-20020a17090add4200b00230c717f66esi3709974pjv.172.2023.02.15.21.19.02; Wed, 15 Feb 2023 21:19:14 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=gSbKQNPX; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229591AbjBPFSK (ORCPT + 99 others); Thu, 16 Feb 2023 00:18:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44620 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229528AbjBPFSC (ORCPT ); Thu, 16 Feb 2023 00:18:02 -0500 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B405A1BACE for ; Wed, 15 Feb 2023 21:18:00 -0800 (PST) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-52ee93d7863so8353547b3.18 for ; Wed, 15 Feb 2023 21:18:00 -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=HtBka/XnXeDgIdXq2ejdDwuy3vY3xy3ojb8+iyaKytdNa/2lc2izy2fcHN4lzJv2cg c4W+fmKeRC3bXmeGMgxQY/YAKJNx14LEamTrR7icC+gau94X/NyfyGl/HpNVxb4P4saE pO5j9VnaED+mDlRsAQTLOf5m5gamElsIps6q+u0DgIVdBtpa9wdGV77s/YrnqPis5ZnP nm+yHrcG5Nu0fXHs21Gd/qV/pMN7Puv1FzPP8KlZKntuKoXreDFpKN9RCMkyk6gq/fQs xxS/+lwvIEu5pGFdAlApZnNwjGveYSE+GnPkMi2FH7cM/sZdOA9dWuVxrH4te5ZnjaOv dEWQ== X-Gm-Message-State: AO0yUKV9jFICdSO6w4epQYDcm/Ljw362gHscDjCDDbBgZTxRL0MYtcOU PwUaHDALWeBoSP+dM8iXNwUrB47rO5U= 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-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1757963621334995961?= X-GMAIL-MSGID: =?utf-8?q?1757963621334995961?= 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; }