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 89CE1C77B6E for ; Wed, 12 Apr 2023 08:13:29 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 28965900002; Wed, 12 Apr 2023 04:13:29 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 23965280003; Wed, 12 Apr 2023 04:13:29 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 101A2900006; Wed, 12 Apr 2023 04:13:29 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 00CBF900002 for ; Wed, 12 Apr 2023 04:13:28 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id CA233AACD2 for ; Wed, 12 Apr 2023 08:13:28 +0000 (UTC) X-FDA: 80672024496.05.87DC664 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf24.hostedemail.com (Postfix) with ESMTP id 11565180018 for ; Wed, 12 Apr 2023 08:13:26 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=linuxfoundation.org header.s=korg header.b=O4WOSagX; spf=pass (imf24.hostedemail.com: domain of gregkh@linuxfoundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=gregkh@linuxfoundation.org; dmarc=pass (policy=none) header.from=linuxfoundation.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1681287207; 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=SD5cw9WTwLv/gtC1leavGLAfHjGbJFl6bf9GFTq1DZA=; b=v1K8oNo9piuPt1DIQOJLcT42TbLD5lYqON3N2qeB5sCbByn+W+cDdlujUgylwJlKlI7Syx N4/5uU69tfUvohqR2h4pbhH2upxBYVxTcJSsQeundaBXuSTRgRKdB32zdNEeoltQigZ581 4jyP2ybtod6Ju3jrPNztQb5xnUnqiWg= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=linuxfoundation.org header.s=korg header.b=O4WOSagX; spf=pass (imf24.hostedemail.com: domain of gregkh@linuxfoundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=gregkh@linuxfoundation.org; dmarc=pass (policy=none) header.from=linuxfoundation.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1681287207; a=rsa-sha256; cv=none; b=kFr1/8/d88N6EgnAPtmY2DCBffe1BSstLcYEmq9yNGNv5PNfuJXjWhyRlf5TwTgKCDq1/v W0rQD+TbzQdGoPIJ/e2QUMPKvS70Os4qZgmL9hqv5NdeXqqIxRjpl48kS1UMNnnSia7YV2 F6HU3NpevX4T11vJXMVSBYgkVK99xEc= 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 33FE362F55; Wed, 12 Apr 2023 08:13:26 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 4744DC4339B; Wed, 12 Apr 2023 08:13:25 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linuxfoundation.org; s=korg; t=1681287205; bh=f2MF9ixfRqoThmb5mzbpVRaeB7vbGtdF5GA8+Ny46gc=; h=Subject:To:Cc:From:Date:In-Reply-To:From; b=O4WOSagXya6doQfyFbjz5cm0CcVdbWws7o/SNliqlwbOTtCsfx4dYja0L/nqt+961 3EFVCTo3G24x0pWsUAVlD9gvmd2yClFK07urAZwVa6IesmTnGMolnd/g2QvjqhekGM tcYeA94dqkQrBOk4/o9uMc2Si17kLZs7y+4PjPw0= Subject: Patch "maple_tree: be more cautious about dead nodes" has been added to the 6.1-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:13:18 +0200 In-Reply-To: <20230411151055.2910579-8-Liam.Howlett@oracle.com> Message-ID: <2023041217-prepay-cobalt-7edf@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: 11565180018 X-Stat-Signature: qi6qtcytih1tc5x9gfn81x5wx4agj1a8 X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1681287206-172406 X-HE-Meta: U2FsdGVkX18PBGSD69Hz4Pxq8XlKKxXAWlw+8rBNrG8+vNLiNAsh4eR1AYlrQg4zcxmXw6COI4bqgSj5tsLwHzQfKP56WbcAdDQ2aWr3eVuu9RAzgVbIlSszf9J7phEb03P6cJ+GIW7n1JklKdq03YfcsooBlff6BoNeiEr4GtFNWrSoFn8lss3cZ4tpX4DnV7tjCQLQn0AY/QWpqAgoFhCm6fj2Q4WuOdUHAuv25iKEZIreS6ywg4s9ilEGu7bsxC0tUu+FnTlDH4K3+LE/0jh2TFfy8Emf13Q4bJUilK+uoyaQ4k/o3qlArAdVOk4qCJOK+XPVqnxazFlPk1xwLCevEsivJq7cga6rXlJ3nuxSKLA1qkn425hN74xWjV423I+2Pb1T6wRVV/v/jrL04ad7s92yICYWf9aw5r9wT5uwrWmLvty7QOz8uxviDLml56y2HUB59JTg/wGYo0zsLQ5yS3WvMhUFOFUck4QC7s1UycKJWYCEs+STLnQbxK0ipNZ7/uMYwX4YN8KVPtapdPI3vUg50+2OPpNnU3+xXTMiRl8I+0UKcwrM5//dgKK7WUJvTNStZGNpTKkpXHs7hX65vEiySqFpq6XQ1KE1Uw6n5ftkswB4iC5KsXNjC4tkp4gwDj6Lu7IES9kyAEWwGxaF/bA6qCRO5sifCn0zzO050uepDLPLnYGhva6jo21YZUady+be+SH/szioKe4J8oVIr8AM2/WTg+fNV9CACsQt9eXCL/8QhTPRDDmih3FvSMFz+nzeY6Uczt4JxNxFdeusaoWFGxZ5CdHDb3adggzSeSjDQFPmllzgttCkio8V51T5MQCQGwiV9i5zNiEmdsfSEyuv84kp5HcKQZQQWiOW49mitTurJGiDK194jRIAHKABkeauoYzLArujKIq6Hf7n9UZDfXpR7CyTwQ8Z8PctLkopJOIFDc+KiIKyP0vJ0/PGtu/oXIycVMotH0P vFlbGwFI icr1RYgegd18uOIhevQ4PeOa+D0Aqdtcz9Y6mur737dDRGTeTtij6EbaO3sUN+WozVvcbRzOpAtKdA71iYDulGLvrUbYSDk7aUHLxS96cDe7hQze7vYTjufs3bjHfPFmxetLxqYgZNqPBYD83MjZJ0G31YPG8B9czy7VfVQAPngF9m3UBc0vuxyi7EuzYNeDXAW0/kV8EZ0IVcKDeOEJTSsbkinBHcjH9awmhlQ4x9z+7oDIkCqS+S6WroCs0WvBfPvCsw7cofIh/rK8hA9U9osiAs+nyjLphW1ed1h9nYUGjIH3LmqwC/CouU5B6Ij9SIXygzO99z0szIVZRb+geLROiHI8E8ICXtiW2Fat9FHDHhlCqWSB76n4JnwhI5yzGXb8qTCXGoWfjQ3ecM1MHavFOp3lF02WYqpjbwuYBiJRFrVpDh/7jFYj+/I4jA8U3McLjkkmSVUYatEpQE/HoTCv1J76tsTlYr6KczOEcoYKIeYyeqeeQIjbFqrhYcZeiYLd+h8ZZAhpdywZCzoRF+p0squuKfZJJO4cwuyFuHi4gmmYgOs+AZmT9PVUgVi7RuIDe4oKiel09xnJoODIUdE0s8CUoDY13Mx3GWrKAqH96guMsqi+lKFYZ/LOuQQMn0wUn7xQX96WQHTBs7r+pC2tS32hBPnU4SVOvP13A20tiE3sPQgkurPZulqkOAOm5m93qTbrIXvimlwHLFLs0IlOOCw== 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.1-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.1 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 @@ -534,6 +534,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 @@ -615,6 +616,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, @@ -1086,8 +1089,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; @@ -1393,6 +1399,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); @@ -1428,6 +1437,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); @@ -4493,6 +4505,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; @@ -4514,6 +4529,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; @@ -4562,6 +4580,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; @@ -4585,7 +4604,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); @@ -4601,6 +4624,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]; } @@ -4647,11 +4673,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) @@ -4809,6 +4838,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 @@ -6611,11 +6645,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); @@ -6635,13 +6669,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.1/maple_tree-fix-potential-rcu-issue.patch queue-6.1/maple_tree-add-smp_rmb-to-dead-node-detection.patch queue-6.1/maple_tree-add-rcu-lock-checking-to-rcu-callback-functions.patch queue-6.1/maple_tree-fix-handle-of-invalidated-state-in-mas_wr_store_setup.patch queue-6.1/maple_tree-reduce-user-error-potential.patch queue-6.1/maple_tree-fix-mas_prev-and-mas_find-state-handling.patch queue-6.1/maple_tree-remove-gfp_zero-from-kmem_cache_alloc-and-kmem_cache_alloc_bulk.patch queue-6.1/maple_tree-be-more-cautious-about-dead-nodes.patch queue-6.1/mm-enable-maple-tree-rcu-mode-by-default.patch queue-6.1/maple_tree-detect-dead-nodes-in-mas_start.patch queue-6.1/maple_tree-fix-freeing-of-nodes-in-rcu-mode.patch queue-6.1/maple_tree-remove-extra-smp_wmb-from-mas_dead_leaves.patch queue-6.1/maple_tree-refine-ma_state-init-from-mas_start.patch