From patchwork Mon Feb 27 17:36:02 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 62018 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp2551707wrd; Mon, 27 Feb 2023 09:38:23 -0800 (PST) X-Google-Smtp-Source: AK7set/fYaQ/YCm7InI8cJJXOnCB1sCwsyRMCKdfjiv+AHfQKhsLx3gzjLbB1Qstyl3wE/dBLX2t X-Received: by 2002:a17:907:8d17:b0:8f0:4a90:a764 with SMTP id tc23-20020a1709078d1700b008f04a90a764mr9112556ejc.23.1677519503216; Mon, 27 Feb 2023 09:38:23 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677519503; cv=none; d=google.com; s=arc-20160816; b=uDJvES1Zpnb9DsA9hawowJz5ykXEJxBjacilDyw8wzNWPWt+qAKZQUa0LoST1/Mxe6 d8bVqO+4Exp2gaa2ln0+Kh6ryWWKAsPBdasQlbjasaX82YLubjXnAq/Iv2j5CD39nIKV kd1i75KS3TMJmZ7Awi5jqvBveRleZS5Sl4AKoONUnh5zHcAs14gInOgwqprHTg7VQ/H8 W3YP0F5+eYFbKz9yp32r2Ngh9PCRH8GN4MMo5mIujDz7y8cd/HD2zL7j60r3LdNYs81J oEEWu3cQO/agKYLDtt+rctnIBkVWFvc89pttl00bRfGCVhGr51EQlPP9xY7ekr9MCPIL c1DA== 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=orUi5wHnC++aji9CdkMMFCsYDd1RwNIxCQdLrt+cFY0=; b=PRLiPAgrfrbsGvM3g+cNNsVhdtseOAm6IUVXpxxQjZLUJ5UnkGgCTAbMauRGBYJd49 coUSSFKK7Cmtxi24CeIaLLrLGxNfwD6OPwdTiLKSMK+8weWOj1hJU6w4ovRp5HCHKrHS gx/uBKF1DBMGKnipxVLd382SOp16Y7wgqKZbKApe6HPlWd5MLcyom+wmWeoB4Y5QlKlZ VsMZXOgtfVQz7e364MHh7/LOb8wMiz5x58YV31JaE4XKQZ8odwKPGME0w3W/toYCI82x I76Xl+jSiEl38UPE34U/G5dMFh3wZXjUA7y5CbhXSrxoRdTS31wMCsfcvXxbcStVbQpx LENw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=Am83ro2Y; 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 k2-20020a05640212c200b004ad02c77d40si9488505edx.29.2023.02.27.09.37.59; Mon, 27 Feb 2023 09:38:23 -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=Am83ro2Y; 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 S229888AbjB0Rg4 (ORCPT + 99 others); Mon, 27 Feb 2023 12:36:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47822 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229834AbjB0Rgq (ORCPT ); Mon, 27 Feb 2023 12:36:46 -0500 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 46E482387C for ; Mon, 27 Feb 2023 09:36:45 -0800 (PST) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-536bbaa701aso152697007b3.3 for ; Mon, 27 Feb 2023 09:36:45 -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=orUi5wHnC++aji9CdkMMFCsYDd1RwNIxCQdLrt+cFY0=; b=Am83ro2YmRzZ4VgyIBhDoTNrPllqfw/5UTqTUL7yZCncC06+SMYT4eArFva+POwT7g 6A/0/pFhHTsDxJdieAltqSAe6HtiFFVlFItush+XbcRSxs2FetQjqrV9RzDHQ5xUXxy+ EFVFqHW9b/Vfsu1fjnNuXuTzPWG0kNjoL02ASewZm4aTLFi207WQmvOLdMhmY0rXGsBi NgW5j6vPb4Yb97AotYvdQXAzm4p61g/PV5t8r9ru9nwtbYld830L0Sd8TDb9hbnZaf2S Co5g3ZCxIRR9yw3YwCJpCKA97OC2cOIFxPWxIRbJAgeIMHg6EAO/atx61gUeYr5Wxasb jnNw== 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=orUi5wHnC++aji9CdkMMFCsYDd1RwNIxCQdLrt+cFY0=; b=Gp25PwCkWSdtZ3MmfQPvLFRd/xvSGm3paVqVBEYmqueOwVR0cfE04xPUutU3Y10G3u rgpA7nIj/oGXVjT+A8C4Ps2gfCnFJIwkH/+7ALKrYqA0papt/VpvF8rVVCC+O+TfnQTw Yc4kED8XKNJiFh3zRKhMvDCpokpwa8qPn0wkDqR5kQ5ZUF8dy2L3EbEU/kDAQlxf91Dv 9nWDHhWNmjbjeq8FPoLSxaszh0uyP5NXyr63i12J38I0wojoOFZ97vF5xbPmmjYBlwh5 Xx9Yype9tOHu+f+/zqt2uTqd45KwORDNooJMGXU5nown88fsnCxn/NSCWYFsbOTwkpZa mZ5Q== X-Gm-Message-State: AO0yUKUrNpeGH+FJjxOEjbJlO3NoAF8PGf8eE1lbgBNQrBRNwmS1S1bF MzDg9D1VAG5KzK6VcVy+nFyBUZzY4T8= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:e1f6:21d1:eead:3897]) (user=surenb job=sendgmr) by 2002:a5b:ecb:0:b0:a03:da3f:3e68 with SMTP id a11-20020a5b0ecb000000b00a03da3f3e68mr9395474ybs.12.1677519404853; Mon, 27 Feb 2023 09:36:44 -0800 (PST) Date: Mon, 27 Feb 2023 09:36:02 -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-4-surenb@google.com> Subject: [PATCH v4 03/33] maple_tree: Fix freeing of nodes in rcu mode 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?1759006690631708459?= X-GMAIL-MSGID: =?utf-8?q?1759006690631708459?= From: Liam Howlett The walk to destroy the nodes was not always setting the node type and would result in a destroy method potentially using the values as nodes. Avoid this by setting the correct node types. This is necessary for the 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 | 73 ++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 62 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 089cd76ec379..44d6ce30b28e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -902,6 +902,44 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, meta->end = end; } +/* + * mas_clear_meta() - clear the metadata information of a node, if it exists + * @mas: The maple state + * @mn: The maple node + * @mt: The maple node type + * @offset: The offset of the highest sub-gap in this node. + * @end: The end of the data in this node. + */ +static inline void mas_clear_meta(struct ma_state *mas, struct maple_node *mn, + enum maple_type mt) +{ + struct maple_metadata *meta; + unsigned long *pivots; + void __rcu **slots; + void *next; + + switch (mt) { + case maple_range_64: + pivots = mn->mr64.pivot; + if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) { + slots = mn->mr64.slot; + next = mas_slot_locked(mas, slots, + MAPLE_RANGE64_SLOTS - 1); + if (unlikely((mte_to_node(next) && mte_node_type(next)))) + return; /* The last slot is a node, no metadata */ + } + fallthrough; + case maple_arange_64: + meta = ma_meta(mn, mt); + break; + default: + return; + } + + meta->gap = 0; + meta->end = 0; +} + /* * ma_meta_end() - Get the data end of a node from the metadata * @mn: The maple node @@ -5455,20 +5493,22 @@ static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min, * mas_dead_leaves() - Mark all leaves of a node as dead. * @mas: The maple state * @slots: Pointer to the slot array + * @type: The maple node type * * Must hold the write lock. * * Return: The number of leaves marked as dead. */ static inline -unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots) +unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots, + enum maple_type mt) { struct maple_node *node; enum maple_type type; void *entry; int offset; - for (offset = 0; offset < mt_slot_count(mas->node); offset++) { + for (offset = 0; offset < mt_slots[mt]; offset++) { entry = mas_slot_locked(mas, slots, offset); type = mte_node_type(entry); node = mte_to_node(entry); @@ -5487,14 +5527,13 @@ unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots) static void __rcu **mas_dead_walk(struct ma_state *mas, unsigned char offset) { - struct maple_node *node, *next; + struct maple_node *next; void __rcu **slots = NULL; next = mas_mn(mas); do { - mas->node = ma_enode_ptr(next); - node = mas_mn(mas); - slots = ma_slots(node, node->type); + mas->node = mt_mk_node(next, next->type); + slots = ma_slots(next, next->type); next = mas_slot_locked(mas, slots, offset); offset = 0; } while (!ma_is_leaf(next->type)); @@ -5558,11 +5597,14 @@ static inline void __rcu **mas_destroy_descend(struct ma_state *mas, node = mas_mn(mas); slots = ma_slots(node, mte_node_type(mas->node)); next = mas_slot_locked(mas, slots, 0); - if ((mte_dead_node(next))) + if ((mte_dead_node(next))) { + mte_to_node(next)->type = mte_node_type(next); next = mas_slot_locked(mas, slots, 1); + } mte_set_node_dead(mas->node); node->type = mte_node_type(mas->node); + mas_clear_meta(mas, node, node->type); node->piv_parent = prev; node->parent_slot = offset; offset = 0; @@ -5582,13 +5624,18 @@ static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, MA_STATE(mas, &mt, 0, 0); - if (mte_is_leaf(enode)) + mas.node = enode; + if (mte_is_leaf(enode)) { + node->type = mte_node_type(enode); goto free_leaf; + } + ma_flags &= ~MT_FLAGS_LOCK_MASK; mt_init_flags(&mt, ma_flags); mas_lock(&mas); - mas.node = start = enode; + mte_to_node(enode)->ma_flags = ma_flags; + start = enode; slots = mas_destroy_descend(&mas, start, 0); node = mas_mn(&mas); do { @@ -5596,7 +5643,8 @@ static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, unsigned char offset; struct maple_enode *parent, *tmp; - node->slot_len = mas_dead_leaves(&mas, slots); + node->type = mte_node_type(mas.node); + node->slot_len = mas_dead_leaves(&mas, slots, node->type); if (free) mt_free_bulk(node->slot_len, slots); offset = node->parent_slot + 1; @@ -5620,7 +5668,8 @@ static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, } while (start != mas.node); node = mas_mn(&mas); - node->slot_len = mas_dead_leaves(&mas, slots); + node->type = mte_node_type(mas.node); + node->slot_len = mas_dead_leaves(&mas, slots, node->type); if (free) mt_free_bulk(node->slot_len, slots); @@ -5630,6 +5679,8 @@ static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, free_leaf: if (free) mt_free_rcu(&node->rcu); + else + mas_clear_meta(&mas, node, node->type); } /*