From patchwork Fri Jan 27 19:40:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13119245 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 CD975C38142 for ; Fri, 27 Jan 2023 19:41:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 487A66B007B; Fri, 27 Jan 2023 14:41:36 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 410626B007E; Fri, 27 Jan 2023 14:41:36 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 214AD6B0080; Fri, 27 Jan 2023 14:41:36 -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 1281E6B007B for ; Fri, 27 Jan 2023 14:41:36 -0500 (EST) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id DCFFCAB7D5 for ; Fri, 27 Jan 2023 19:41:35 +0000 (UTC) X-FDA: 80401598550.23.0591CF3 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) by imf23.hostedemail.com (Postfix) with ESMTP id 98834140011 for ; Fri, 27 Jan 2023 19:41:26 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=S2HR++yb; spf=pass (imf23.hostedemail.com: domain of 34SjUYwYKCKgacZMVJOWWOTM.KWUTQVcf-UUSdIKS.WZO@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=34SjUYwYKCKgacZMVJOWWOTM.KWUTQVcf-UUSdIKS.WZO@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=1674848486; 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=FUzzHzCQcxOurh9YuvudjXpNdZx02NIZtoLw3Jde/PE=; b=WTOeRPgNok1VoTsYIr7sAPAwpPM65nDiw6+K6bil18gBu2abILzRDNGF36Ec0ehd97FrgA NsRMR5HxWUNsVpnI1BRGczhPuLMHaVTIny7T4MZCHnNDMP/I8rjLvDMh9pNw9EZr7Rp9cg p6HCV6haSwsS7liQCdvzgFDb51Sn2b8= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=S2HR++yb; spf=pass (imf23.hostedemail.com: domain of 34SjUYwYKCKgacZMVJOWWOTM.KWUTQVcf-UUSdIKS.WZO@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=34SjUYwYKCKgacZMVJOWWOTM.KWUTQVcf-UUSdIKS.WZO@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1674848486; a=rsa-sha256; cv=none; b=F7UWF4hglFs2pE6LFUmTCzyIOlWzGIBkriX2SJP/7F49qqWR6ZMQGztpTDZPLe+JIgZ2qv iZZBLghUV0J6c1AMPPhLXynQLAhrdzgiyNSIMpPo+Jp9S2MXHjZX+/dCBipBY7UujadzaZ 1FyLSxLeqmlAYMSU2i23AmJ73GUKUrk= Received: by mail-yb1-f202.google.com with SMTP id r8-20020a252b08000000b007b989d5e105so6375702ybr.11 for ; Fri, 27 Jan 2023 11:41:26 -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=FUzzHzCQcxOurh9YuvudjXpNdZx02NIZtoLw3Jde/PE=; b=S2HR++ybc/ns4vYecXBlgBA5lh7rKCR5RBxCn2d6nLoproYmP4Y/TuK8A2ykL1TZCy PQi2lsVKc//h5m3TPGFUZRCScYCxf/iBRsPO4Le2L6kyLee01De7/gBctPL5x+AFYdbM +GjlXUavIluJZluW6t/CA9goOPJfDGVnM+Mgt+aMp9WxpRPbD/Tewkr6wZubL9JQbZ/Q D22ZQZJELsrUxamrbo349CKHJL642zBXbi0BO/uzmOjlGEGSeG1j/mwEO9F4yWD/yh+R Z4EUx0fbMYpLh0Co5d8CYSkewP6ymMJoH7lGt/nPXvwtHvtN4R6vwQVewCoOaVtJA9nQ 6Lhw== 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=FUzzHzCQcxOurh9YuvudjXpNdZx02NIZtoLw3Jde/PE=; b=B+WnXAGNwMTLuKhhcSmWqEeyP7pDREdy1C/D0L+ShPJMiu7YsSPL6/TLtOIVfPn465 zo48ITBJzfeG5GKTbuBsHjL4GT52OhqWUjyjiEjj3TXZu2uBgZWJJX7b+biRm1Q7XfPT /x/5sgbwxLfe+ONFLAA97kEzoMXOgPGWD/F/I84Neg89C+pIgBYYteiwuF1wqEqZtSqh 5g9faLgghfZr+Ez9OrEr2rhsAyBN0sm79grjxfA83+8XS/W1Yhrgtlis0tgfGnDQPvuT osnVXY8Q9lc/RWyMFcgZkyuxmlsEXKvzh9a/LiSN4Ix+4RbQiHsv5j77EAU5gZQar2LR 9h9Q== X-Gm-Message-State: AO0yUKXzh3TbFAEfDgoJkWgZWaJMyP512W+Ws7FjdVdORQ5Z2Ygpz5QL /IOXe8RH+Evi4BAtwgFokfDTTFb+W7Y= X-Google-Smtp-Source: AK7set8Zoaf7xb4TZLOBvvU/fOAKWYAOQ/jwdJrqulf4473/2u2hKvPvmXN7ahB+v/eEMKhFLKA99DnsrP0= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:4e19:be9:c5d0:8483]) (user=surenb job=sendgmr) by 2002:a81:7e4b:0:b0:506:4f19:740c with SMTP id p11-20020a817e4b000000b005064f19740cmr1518489ywn.383.1674848481189; Fri, 27 Jan 2023 11:41:21 -0800 (PST) Date: Fri, 27 Jan 2023 11:40:40 -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-4-surenb@google.com> Subject: [PATCH v2 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, 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-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 98834140011 X-Stat-Signature: tesnnfdah8gys9kxo799tzmc6wahykjw X-Rspam-User: X-HE-Tag: 1674848486-389842 X-HE-Meta: U2FsdGVkX18U6fdSWUBtUaEaMkEuomZvLOiO40FyN6i7N52QwtKwIbeXijhjSPypDEjV5FsCnzeORv1kmOYCo4OnhHBJa5WxkqC4WZmxh9GA6xvJvZnnJy8FpUsM7aAT+ZIhEweeXZGrYct3A6GtEBNajF3dnz8wFMfEHaWk72NXtK7FpyeX9B9LQonn2+mw8LsSdK4mHCMOT7N+n3ataG4CobUCZlobrwkRit9K3Xb+niNPjmkg0aLgTJmNR8ZWTwg21m96WnIwZ74J4ch+lxy+X5VfH0DbNcyAASt/USEx8qOCiHLEaxCDPDrIoQcmIg8USMNrsazloDj33ExgwSZ2O232lOmVLHgSI337YkcFtG6srnSKFBNn4Dr37IFBJwjRxkVAU5x1Mi+jAX2aMxx83fW88ZdwL7gduD1MGdIcNuikuKpZvJGTf720jN/bjYp3qHIMbuoXZ8FqYvi0M5kjyZGYXT36Vfh2+ZJeZI+gYe7fpp74zGfsAHS8UX0k7gYMMJvJrBQNr7IPg4pAOXKWdqjMmwnxu/UQzbSWlesLEvpRei4NmfOg+FSjSol4eHbzAOs+rB17OU1egr7Mm3eB6j9MyYDyzIzN8bhZZgVsftrhCJKQbAKNukho2coYiWH6lhAzRZDVMyWAOcxCg8xazrBJqRaWc/D8VWDtusYftBJbgym58TW0RHGBrSA4chXNx4GlRJnJgJrp3ZIjdwbnRL+LA5nSgBpeNm8VBs1Z8pHTZhO+irOCwiJQ+64gaqmF7iXiv8E+JnOLBpPxW21toJ5Mh48R0UiHx4BAtr6CfE3l/CBi32GvvZOoHI83YojXgWqDZ5ticFql+Zt9khKnPG+9+i9ZV7pwznORWgwUvFKAjJllSIPC2O7IA7sbkJ0j5gQYqZ9G8POhIFbB0cfpZl3cw4aj5e1jwFw2qXy1kZdq8x9/DWxM/i0UQ8878sTZhK2v8N/UZ2EZ4bS X52wvbuW Zuj3gGggANW6u+fK6Ct3Hb7kaMR4Ezrb3SOIMF9VufR/k4t22D0DAcq8sTlXBfT8IoRf7s/oRIxmMET384Yo3TN7XeRtoBINpmhshtiOm2Fv5ORtK8C+4JNRzAHCrTOfJ9Tvvm+nR50cQIaJeGQ7+jXbzfeiHhkQ7ZIJ8F/m+Z2og3gqOBzB/cE2ZtB6oFst000zFdHEXSiCpTqfsHUZJOJ6KM7whrRf4mhKO7lhFNgarZmDoKzCEGYz7X4ne/8/nm630O11SH/Si/cFdGmfDHnc0AW2bDyLfUvx8ouCAVs+k0DDT7jr56RwDo2k82FGemEwf0JMg/5nxsk1bTIpCNWMHjtapEzY8Ey0YeCuyCScAFjWl0zP1+UzNKz90cC9wcqc6e4gJl0D5wUS9edKF1//9yEtQKvowB5VRF1AOMzjGF63uRJcEHCUWwzgxPKWQ2yg/jXwJGe1aVocXVCu7iOlojkFdtYnFMaNvIPuNS1e7EC6KbCtFB+7k4BHJMXRshh5FAHRH9ckZ5hPw4x3Cvfhkl4i2HmlWuBdUHOVHgGqmtmMu8eCHICzH4ZaCT23s/D/KuGZMFe57uMP2INO276xOg0YsbFQ8XU7RJj5J5SrzKwin0N3/QNCzm6gDxm/oHzgWm+dEO4NilUGga7abDzcCB6DH1booAZXolYOikliFjAX2aj6lULFAtDmGxHf8wXXdMJr4wF15bXPzrV+WC7cLDdWLUE5FaTo/rmDhRlTS53CMTU+3rPWJTxbTB1te6/8HyY9a0vSC5ns= 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 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 482e17a460cb..73917dd2c608 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -895,6 +895,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 @@ -5448,20 +5486,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); @@ -5480,14 +5520,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)); @@ -5551,11 +5590,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; @@ -5575,13 +5617,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 { @@ -5589,7 +5636,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; @@ -5613,7 +5661,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); @@ -5623,6 +5672,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); } /*