From patchwork Thu Feb 16 05:17:16 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13142493 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 4A83AC61DA4 for ; Thu, 16 Feb 2023 05:18:00 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A942E6B0073; Thu, 16 Feb 2023 00:17:59 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A43386B0074; Thu, 16 Feb 2023 00:17:59 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 90C226B007B; Thu, 16 Feb 2023 00:17:59 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 7EE3D6B0074 for ; Thu, 16 Feb 2023 00:17:59 -0500 (EST) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 4B05CA61D3 for ; Thu, 16 Feb 2023 05:17:59 +0000 (UTC) X-FDA: 80471998278.20.C8B5FB1 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) by imf04.hostedemail.com (Postfix) with ESMTP id 9041940010 for ; Thu, 16 Feb 2023 05:17:57 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=DtrBb0OE; spf=pass (imf04.hostedemail.com: domain of 3hLztYwYKCNkNPM9I6BJJBG9.7JHGDIPS-HHFQ57F.JMB@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3hLztYwYKCNkNPM9I6BJJBG9.7JHGDIPS-HHFQ57F.JMB@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=1676524677; 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=0nC1+Z5xJ7W1lTs/T0LqT1g+dKiQp9Lc6m1pbhrJE6M=; b=LpY43sL2FFzNwtYu6DKECnL/wK+EkjK8HAoLxgAJq/9NBZRcAtD9rigOZlCNpGXZocJZFW qI8LCF6oP6rmLsLtHq4xfvkPfIvgkBQSIJdnkZqNGwMBP6SGsvw9g4rOVApSFNWvgOJJnw P5Iok2qAEfkV5UyRbqC3WSU0KJKcVm4= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=DtrBb0OE; spf=pass (imf04.hostedemail.com: domain of 3hLztYwYKCNkNPM9I6BJJBG9.7JHGDIPS-HHFQ57F.JMB@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3hLztYwYKCNkNPM9I6BJJBG9.7JHGDIPS-HHFQ57F.JMB@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1676524677; a=rsa-sha256; cv=none; b=44PSeNx2wUN4q7mcqfCCaP/IDEEcGwjIdl4WWF9JZqZsp9VvJnLO77UMerNh80OcI3zr02 XxLiRzM/cz7WvC8xscWWqNOs0+J9XYdAK+mUKawthvvJGIMrwd8CSfZm5pxYjQAcyyyzJZ dDjHbtloS17kbazwk7u9AQdqpUgKETY= Received: by mail-yb1-f202.google.com with SMTP id a17-20020a256611000000b00889c54916f2so850946ybc.14 for ; Wed, 15 Feb 2023 21:17:57 -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=0nC1+Z5xJ7W1lTs/T0LqT1g+dKiQp9Lc6m1pbhrJE6M=; b=DtrBb0OEqSibZGKM+tGrekgia+czdJCmNvwxB9nTfvwGTIHXKlm6TS9Q1D5NfIR4hg c3apVnOjZnfZCRE1YFzTHLthbM0S/IVW1BccnLNsJf21OgviYfhBVHNRB8wtAupWJwTS 1TEYfIbKZCSoMpt+Js0TzB9iPZbPOfnvL//puIai0IRqYdE7nHNdWFvMQyJ5Dt5csXIh 43aWlLJbXNtNaZid0iRHPyqJRyFRPoBCCZ5nKLzs/n4kbMJKA8/P4QRR3m4y665oyagy kgaLTr7SQL3GQMCbK2ePGMttOB2X0C/PFJbSA9edFZkog1VQvtGlD+HG94g+afV+vkdw M8NA== 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=0nC1+Z5xJ7W1lTs/T0LqT1g+dKiQp9Lc6m1pbhrJE6M=; b=uho0ebqtJIJlAo9erJFDTeKffoFukQguDp46vd/l7yk2eKq3mWoT0m3eZL9XCu46iu 5ZJcqVyWPwiAmt3AinoKSFHwg0f6E/RTWZmnwzqIdlrGt9tK+ZxdesAsQHeBNmbFtBMf nJekS8MH00dPByOdB9mQVCdhOpPj06BlrjnceirYxmKIFoSwsMACi6i5RjKBlG0UJcU8 c0wGOPEiIdJOiMlyvZpaaWCeLNJFxYyHu1sW/aIYEoz2GTwgAt/cOKEEIfakbeBYr4NK duTlENtlW7g2Pv4GWCOrALL0rw6LgSfum+Dl1DtO68XRX8wp1goHvzclzu+qWhnEH8qQ zLUA== X-Gm-Message-State: AO0yUKUEQsQohg6FCLNOg7vuEC7xIqrVnq3bZYI8Y+5FTMmBqTioEwXV TY6syIx+gjjy2aLubFITl+br5dGwgwA= X-Google-Smtp-Source: AK7set+Y8Yn0V0huCQq66Ej7hgCVLxUYKYuorVk92zLqUUDZhSEdy+eB6kBj2xP313LsIxhb2Sq52k6rqsw= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:f781:d5ed:1806:6ebb]) (user=surenb job=sendgmr) by 2002:a0d:d88c:0:b0:533:86d8:a551 with SMTP id a134-20020a0dd88c000000b0053386d8a551mr60897ywe.11.1676524676787; Wed, 15 Feb 2023 21:17:56 -0800 (PST) Date: Wed, 15 Feb 2023 21:17:16 -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-2-surenb@google.com> Subject: [PATCH v3 01/35] maple_tree: Be more cautious about dead nodes 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-Rspam-User: X-Rspamd-Server: rspam03 X-Stat-Signature: tbd6eh6mnp5sqth9fpcehd9ze53fhqma X-Rspamd-Queue-Id: 9041940010 X-HE-Tag: 1676524677-806775 X-HE-Meta: U2FsdGVkX1/y1GIJBHd/keDgmUpy+ug8yCLapCXOQOm0YVXycR0qbM0HZpy8NAvHQjDjxGp3svPn804NKTGLj+WIbZooCcD3oYZwJ3bFo+rrA7D1kl5FSahqHCbvKTp9NSIXsf7PPDBls3twoLh8U5eGyq/Xy6K+gmKv1bvlTkEWNo3ytfGFasBC6cuFa7d6s301q4JegR0veBRUwenubM5XDPSNd+cip7Rg7z1llo6FgDLmK0oCU6QDYmzj78qDk3vH8t/SmIYC0nF87HA+kX5pIeQjPFFNhEvVpYOLcXM5Gk5ixSJGNzjEEX0q1UCW4Hkw4RARliXLF3CWEYZDuq1SSMW64Or533RTIBRpgTA48ko+7LxNh2B6hLE+mM4xgW4d6gF82mL4sM3zCqKfR8uHAk6oyqJKAInyoV2Ful8NU53qPYU90Teb0JzATRP2UHJwQDWU5pD5NeV3OkCzxMl0eLq/dyuf1l1w3QvY5pcRK5S1Z+ZQBfsb1E9EBN5DtlgOgav3KKHdi1LGgsvioKz+0d/rtU93TeZQeJ4nbR3yIBSSQMbddPB7N6Rb1KrzfoT19Zvk23nbkKvB19q7q2qS7DZmrJ7B6SZ1J2Pg7aXeE6r5txYB4GcoIKezNeeMq5TpShMkVB5fdqm8GWJCJ3UXTrXhU51bhIlyPtLE0y+PhM8seu/TakYm4dgmvRhIzsQCvJ79cHyjsePdHAjtd3RgWUPcd1fg6Jp8+DpTU108OW7hCt1HxASo+b1eYS/o2+0O5J8JDtSmWLme6ZDs8JLxmccTpRN3Ej6Uf20q/NOKBOjz/HF2vlt6GstuCjDw5cbVV4e2ewfuuNgn7AKWUwg3H7f1KfEJK96ca0FJEMu0eP9iMq4QyuhXjRvtMi8nlcC1q8zT50bb0GvGmsue9rQqOwEs/++wZkSqhuM/IwnDULgYkr6CWMBUHJMEVks7Ab5ABO0TED3dakE+VCv kxFdo3+h +kOaF4oZ5Q+R1Qc1WY3oh6tIrDhkDh0CcRvo8AS6jP/YAn59FTlXlvFeynzSY2QtchoWzfhLXZMs55n2E9/PXjgEybEmshjfheSOxIrEYaPL4tT7HOlUlIpgcW2c9of/JF//GNym+Zu1IT8Wj6VgM+FAVslfJMfAiR6HMSjDULqYYkVYojtZYh3NagNY0qjfS68OTfnxyQxK7Nv++owQVJmMg2PXf6Svb0R5NLISL2xBAmSeCnTDTXUl7Xx9rfxkVE7erK85QtiodYqjamulKUXGTLBSWWGyqbvW4Lu2HE5P4jnJO4MYQuAOZrDxp4j5x8gfOVAzk8EBj4GL4IKpoUDUW4htj3INPviQZuscGZDbtOKLf1LJkPLf2Iz4tEyUgqNsgUqHKEdzAth59DK3lX+yLNjmjVlKD4q9nXlZmqz3S9rOrxhSMhdy4OY5YT5kFxvJKwJsigscFoGNAcNzThsI7suJQ9cdu+sxLvCJJ/q6ZiW+g0bRC+j7pl6zroj2M2yrobh9PmbDwFa7fwVBlRVPTVWNd5aW80lA94/Dx4HzABUgk6SzT3WEQHkuXFRW5j+74n4KyEwV1N8QElC2ZQOipNWe8boYXGDwk 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 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. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Liam Howlett Signed-off-by: Suren Baghdasaryan --- lib/maple_tree.c | 52 +++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 43 insertions(+), 9 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 646297cae5d1..cc356b8369ad 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -544,6 +544,7 @@ static inline bool ma_dead_node(const struct maple_node *node) return (parent == node); } + /* * mte_dead_node() - check if the @enode is dead. * @enode: The encoded maple node @@ -625,6 +626,8 @@ static inline unsigned int mas_alloc_req(const struct ma_state *mas) * @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, @@ -1096,8 +1099,11 @@ static int mas_ascend(struct ma_state *mas) 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; @@ -1401,6 +1407,9 @@ static inline unsigned char ma_data_end(struct maple_node *node, { unsigned char offset; + if (!pivots) + return 0; + if (type == maple_arange_64) return ma_meta_end(node, type); @@ -1436,6 +1445,9 @@ static inline unsigned char mas_data_end(struct ma_state *mas) 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); @@ -4505,6 +4517,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) 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; @@ -4526,6 +4541,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) 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; @@ -4574,6 +4592,7 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, struct maple_enode *enode; int level = 0; unsigned char offset; + unsigned char node_end; enum maple_type mt; void __rcu **slots; @@ -4597,7 +4616,11 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, 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); @@ -4613,6 +4636,9 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, 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]; } @@ -4659,11 +4685,14 @@ static inline void *mas_next_nentry(struct ma_state *mas, 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) @@ -4817,6 +4846,11 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, 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 @@ -6631,11 +6665,11 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, 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); @@ -6655,13 +6689,13 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, 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;