From mboxrd@z Thu Jan 1 00:00:00 1970 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 39B27C77B6E for ; Wed, 12 Apr 2023 08:12:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C9C2A900004; Wed, 12 Apr 2023 04:12:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C270F900003; Wed, 12 Apr 2023 04:12:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AA065900004; Wed, 12 Apr 2023 04:12:18 -0400 (EDT) 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 8BD03900003 for ; Wed, 12 Apr 2023 04:12:18 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 518D380F88 for ; Wed, 12 Apr 2023 08:12:18 +0000 (UTC) X-FDA: 80672021556.03.CF52271 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf30.hostedemail.com (Postfix) with ESMTP id 8FA8C8000F for ; Wed, 12 Apr 2023 08:12:16 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=linuxfoundation.org header.s=korg header.b=x18wvqxT; dmarc=pass (policy=none) header.from=linuxfoundation.org; spf=pass (imf30.hostedemail.com: domain of gregkh@linuxfoundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=gregkh@linuxfoundation.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1681287136; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:dkim-signature; bh=5ZjTfKPkRTK9XABSnSJsI1KRTN/rMJQ4a8DSD+046j8=; b=1nVftqabLPkY8WGH6x9p7UmEW2I+TuWMf4HIRmw8k3y6Eo9f/oZZ/7j7tmcubTUOwgyHor 5/IwFHkjdip4/srx/5h8SRTLob6c6dh+oUzvf8M/mfDyq2nAZw/a/X19tFv7JyzvLZtAc1 53eO4JmoDk4gTeJ+j3LVIq0NhEjOm/A= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=linuxfoundation.org header.s=korg header.b=x18wvqxT; dmarc=pass (policy=none) header.from=linuxfoundation.org; spf=pass (imf30.hostedemail.com: domain of gregkh@linuxfoundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=gregkh@linuxfoundation.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1681287136; a=rsa-sha256; cv=none; b=WPEBBW5IDovD3NO1nnBEWYu0wZW7CUkNHCoBcVZxVyDotD/d6g/vzPmqSS7uDaVb7LI0gJ iw0sA4R/nrT8Vvk1ZfbY+sFTKxhuQurP08ynAEa8vpBq3dGcgD9U5vuNbqo/VMPnIEgXNx G/iGmRP99UwqWQBY0d2B33Elz1jev6Y= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id D129A62F4F; Wed, 12 Apr 2023 08:12:15 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id E88CCC433D2; Wed, 12 Apr 2023 08:12:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linuxfoundation.org; s=korg; t=1681287135; bh=s1qVeFW8e+LoEzQ640IL2Z7jjT1VLwT+uVwRK2DZeOk=; h=Subject:To:Cc:From:Date:In-Reply-To:From; b=x18wvqxT386ThLZ4SKUrz6IbWAvRYuwPluDm+aD99NMSrOD34FsDgCUT83Q7QJKAL yMw/C7ctOTeb6LAhfS/R6Vfc7/ywcgF4eZVX6/R8mI6aCkgzI06aXDJKQSZyIzGq7n RtpT2GFshAE0DSVXjHZ79Ia7LWClYNxQopcKX7eA= Subject: Patch "maple_tree: be more cautious about dead nodes" has been added to the 6.2-stable tree To: Liam.Howlett@Oracle.com,Liam.Howlett@oracle.com,gregkh@linuxfoundation.org,linux-mm@kvack.org,maple-tree@lists.infradead.org Cc: From: Date: Wed, 12 Apr 2023 10:12:07 +0200 In-Reply-To: <20230411151055.2910579-8-Liam.Howlett@oracle.com> Message-ID: <2023041207-heaving-recede-5bc1@gregkh> MIME-Version: 1.0 Content-Type: text/plain; charset=ANSI_X3.4-1968 Content-Transfer-Encoding: 8bit X-stable: commit X-Patchwork-Hint: ignore X-Rspamd-Queue-Id: 8FA8C8000F X-Rspamd-Server: rspam09 X-Rspam-User: X-Stat-Signature: jsi18h71pr64ugx4uori1he1jnpxnkai X-HE-Tag: 1681287136-617111 X-HE-Meta: U2FsdGVkX180tlr6BTGRWNLXzh7hHkknVhIPvmhy8XBt/ETmNG6i7l2xLLij6PJMF41Hv9gAwMCZAgZEym9pjlXkWGY2hk6bMx/3PQWcSjDWcjByFoVrzFtZhE1eL1CF1C5mmfP1qxudtb3zrroaSrBEtDtb14h7wJkoMvbeupSaFrQndrt5aGKl6v8XdFz4KPo7gjjdHV+g4XSfdumbOGo8z30OulyT84dbXD36nRageaDUJrvlzrBUDZrqsHIHokHtZnXpgkrT7TLs8W81tIbeLnwurmccESdNgR8boQXDdK9aQM/r/q0vchhCb8ZkLYJ6uVkq1JbS/cjj+mg/f314Ta8CbtdNerS1vkSFnRLjHMRz7JY2xAkMMJAGPOiWlfdMwPCsMOUZ6V6TeoSBJ+9LK+4MtlT0gk79PtuFyGNCWKkEhc6uuaRwVU/TFz0SGXEU1WkvxuCVt+78BB+6RZnXrGwSBT/YRZgGQbUQX1g0Yd3z1+Kb00eAB1FLuhFJFUZuqMCoa/EMGHwhN9ZhoJ0Ik4EYELKw32qPzQq7uIHjWHG9/ZsBUwVpemVE+YF8qPv1/EPfK/1NL4KATCLNswU0RtsPR25Y8nGhSMnFTcHqmB5iEAoJVzSmCGfZwPg6OlQy36/1hy5Zdmzje4Mob0hrp/zuJhEQLNI/vJ/4H2Op6MPMNOrusa8WY1U4+b/Tfnfmzkfybe42rBLBiCCMduPYgVj6hvOwLw9O5njmiLbJIfcsn9p7w3F1wH8NYtl5XrptmUGB4aRJ/1/RrfW9/Z5g88N4IYWviUR9BXOvrmq1vJb1v7quZBgm527Oa7dw3KXWAdqXS4zKARRaYDnuHhSJbHCqXVpq1jc8Sau2jOG5mfuZ7G1fqcWz8UkOW83OOxEp+DmyNJtff2JBbLwnDbUS3QTSpOeQS6ynvBW/6G5EUcVsAg//sNInshXjb4H3pNUjlr/1F+svQ4fDRAB SRx8YoaN /XjnCXboixeMRuQ2C0DNuL3Gm4SAOYdYJ8PtsK8GPCrP8jfPnCd8ePOZwxYLk3KbdnEAdNzO9U1LeUjWA9uDx74DqlWaFoAWjqbNRANA3CUNqye5BHARSDqc9uZCuZbgy5xSbcyUsQBjziX7dQVcITX2Z6EAjoqX0uKhyXdHYW774eyUta/jvQ4GZo3zktMUZn0Ed4UQMSOwnrqAqz0Oy271oAMGVML/HBY4AFtWAK8NGY9cpWjQQfXXFhtWLuYWyC+1P/DsX0iMwu84be5gQo4nnpkDYzXx3pkwC9TvIBomUVfz1XSkCwHlYZxAquD8YNoImla4jmUEMfeEkLwXONbAydg/KeKe7gX7ij9JHCtBT70GXw52zZjCykCNbQCEKytFF8cpqc+ifHvjiyCXvXvmow5CWRTa8LpXScg1c72Nc4IsIGpipEb/vcneUAvWTFJg9b5vhes5nj4/MtNaRV9tJJEQb4/4LTQBaL6EyHbCCegUg+tsekyHt9+lN+7cfHANuLAKM8ffVqRRnVB48t4tPPaKsrTUO67QCx2xvDxxXbVGw3I+VnsibmLO7hs3IQUrwdQI/J7WoXWRKrnwXhpva6Ig2ylXa9C/PPOqBc5pzaKiSyvXZUxivav8NWsX3IIgA+fXIx/PGSSaTxtyWjIkFZ+ccsUMqX+kS03wWBH+vVYaKJHoYlGm1ivXNb+aDQTW0j2rs3SIPTpH6/mSexS+HKA== 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: This is a note to let you know that I've just added the patch titled maple_tree: be more cautious about dead nodes to the 6.2-stable tree which can be found at: http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary The filename of the patch is: maple_tree-be-more-cautious-about-dead-nodes.patch and it can be found in the queue-6.2 subdirectory. If you, or anyone else, feels it should not be added to the stable tree, please let know about it. >From stable-owner@vger.kernel.org Tue Apr 11 17:13:00 2023 From: "Liam R. Howlett" Date: Tue, 11 Apr 2023 11:10:48 -0400 Subject: maple_tree: be more cautious about dead nodes To: Greg Kroah-Hartman , stable@vger.kernel.org Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Liam R. Howlett" , Stable@vger.kernel.org, Liam Howlett Message-ID: <20230411151055.2910579-8-Liam.Howlett@oracle.com> From: "Liam R. Howlett" commit 39d0bd86c499ecd6abae42a9b7112056c5560691 upstream. ma_pivots() and ma_data_end() may be called with a dead node. Ensure to that the node isn't dead before using the returned values. This is necessary for RCU mode of the maple tree. Link: https://lkml.kernel.org/r/20230227173632.3292573-1-surenb@google.com Link: https://lkml.kernel.org/r/20230227173632.3292573-2-surenb@google.com Fixes: 54a611b60590 ("Maple Tree: add new data structure") Cc: Signed-off-by: Liam Howlett Signed-off-by: Greg Kroah-Hartman --- lib/maple_tree.c | 52 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 43 insertions(+), 9 deletions(-) --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -539,6 +539,7 @@ static inline bool ma_dead_node(const st return (parent == node); } + /* * mte_dead_node() - check if the @enode is dead. * @enode: The encoded maple node @@ -620,6 +621,8 @@ static inline unsigned int mas_alloc_req * @node - the maple node * @type - the node type * + * In the event of a dead node, this array may be %NULL + * * Return: A pointer to the maple node pivots */ static inline unsigned long *ma_pivots(struct maple_node *node, @@ -1091,8 +1094,11 @@ static int mas_ascend(struct ma_state *m a_type = mas_parent_enum(mas, p_enode); a_node = mte_parent(p_enode); a_slot = mte_parent_slot(p_enode); - pivots = ma_pivots(a_node, a_type); a_enode = mt_mk_node(a_node, a_type); + pivots = ma_pivots(a_node, a_type); + + if (unlikely(ma_dead_node(a_node))) + return 1; if (!set_min && a_slot) { set_min = true; @@ -1398,6 +1404,9 @@ static inline unsigned char ma_data_end( { unsigned char offset; + if (!pivots) + return 0; + if (type == maple_arange_64) return ma_meta_end(node, type); @@ -1433,6 +1442,9 @@ static inline unsigned char mas_data_end return ma_meta_end(node, type); pivots = ma_pivots(node, type); + if (unlikely(ma_dead_node(node))) + return 0; + offset = mt_pivots[type] - 1; if (likely(!pivots[offset])) return ma_meta_end(node, type); @@ -4498,6 +4510,9 @@ static inline int mas_prev_node(struct m node = mas_mn(mas); slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); + if (unlikely(ma_dead_node(node))) + return 1; + mas->max = pivots[offset]; if (offset) mas->min = pivots[offset - 1] + 1; @@ -4519,6 +4534,9 @@ static inline int mas_prev_node(struct m slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); offset = ma_data_end(node, mt, pivots, mas->max); + if (unlikely(ma_dead_node(node))) + return 1; + if (offset) mas->min = pivots[offset - 1] + 1; @@ -4567,6 +4585,7 @@ static inline int mas_next_node(struct m struct maple_enode *enode; int level = 0; unsigned char offset; + unsigned char node_end; enum maple_type mt; void __rcu **slots; @@ -4590,7 +4609,11 @@ static inline int mas_next_node(struct m node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); - } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max))); + node_end = ma_data_end(node, mt, pivots, mas->max); + if (unlikely(ma_dead_node(node))) + return 1; + + } while (unlikely(offset == node_end)); slots = ma_slots(node, mt); pivot = mas_safe_pivot(mas, pivots, ++offset, mt); @@ -4606,6 +4629,9 @@ static inline int mas_next_node(struct m mt = mte_node_type(mas->node); slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); + if (unlikely(ma_dead_node(node))) + return 1; + offset = 0; pivot = pivots[0]; } @@ -4652,11 +4678,14 @@ static inline void *mas_next_nentry(stru return NULL; } - pivots = ma_pivots(node, type); slots = ma_slots(node, type); - mas->index = mas_safe_min(mas, pivots, mas->offset); + pivots = ma_pivots(node, type); count = ma_data_end(node, type, pivots, mas->max); - if (ma_dead_node(node)) + if (unlikely(ma_dead_node(node))) + return NULL; + + mas->index = mas_safe_min(mas, pivots, mas->offset); + if (unlikely(ma_dead_node(node))) return NULL; if (mas->index > max) @@ -4814,6 +4843,11 @@ retry: slots = ma_slots(mn, mt); pivots = ma_pivots(mn, mt); + if (unlikely(ma_dead_node(mn))) { + mas_rewalk(mas, index); + goto retry; + } + if (offset == mt_pivots[mt]) pivot = mas->max; else @@ -6616,11 +6650,11 @@ static inline void *mas_first_entry(stru while (likely(!ma_is_leaf(mt))) { MT_BUG_ON(mas->tree, mte_dead_node(mas->node)); slots = ma_slots(mn, mt); - pivots = ma_pivots(mn, mt); - max = pivots[0]; entry = mas_slot(mas, slots, 0); + pivots = ma_pivots(mn, mt); if (unlikely(ma_dead_node(mn))) return NULL; + max = pivots[0]; mas->node = entry; mn = mas_mn(mas); mt = mte_node_type(mas->node); @@ -6640,13 +6674,13 @@ static inline void *mas_first_entry(stru if (likely(entry)) return entry; - pivots = ma_pivots(mn, mt); - mas->index = pivots[0] + 1; mas->offset = 1; entry = mas_slot(mas, slots, 1); + pivots = ma_pivots(mn, mt); if (unlikely(ma_dead_node(mn))) return NULL; + mas->index = pivots[0] + 1; if (mas->index > limit) goto none; Patches currently in stable-queue which might be from stable-owner@vger.kernel.org are queue-6.2/maple_tree-fix-potential-rcu-issue.patch queue-6.2/maple_tree-add-smp_rmb-to-dead-node-detection.patch queue-6.2/maple_tree-add-rcu-lock-checking-to-rcu-callback-functions.patch queue-6.2/maple_tree-fix-handle-of-invalidated-state-in-mas_wr_store_setup.patch queue-6.2/maple_tree-reduce-user-error-potential.patch queue-6.2/maple_tree-fix-mas_prev-and-mas_find-state-handling.patch queue-6.2/maple_tree-remove-gfp_zero-from-kmem_cache_alloc-and-kmem_cache_alloc_bulk.patch queue-6.2/maple_tree-be-more-cautious-about-dead-nodes.patch queue-6.2/mm-enable-maple-tree-rcu-mode-by-default.patch queue-6.2/maple_tree-detect-dead-nodes-in-mas_start.patch queue-6.2/maple_tree-fix-freeing-of-nodes-in-rcu-mode.patch queue-6.2/maple_tree-remove-extra-smp_wmb-from-mas_dead_leaves.patch queue-6.2/maple_tree-refine-ma_state-init-from-mas_start.patch