From patchwork Mon Feb 27 17:36:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 62016 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp2551583wrd; Mon, 27 Feb 2023 09:38:09 -0800 (PST) X-Google-Smtp-Source: AK7set8MLd6PnrgDc+qe4j1hX3eL2jwgPgw/ifi1/4jObIKfkGOomySvPSJtnm4EZSGqUF+1pZmr X-Received: by 2002:a17:907:9543:b0:8b2:c2fc:178e with SMTP id ex3-20020a170907954300b008b2c2fc178emr27206358ejc.74.1677519488898; Mon, 27 Feb 2023 09:38:08 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677519488; cv=none; d=google.com; s=arc-20160816; b=ch8mAlUHtoHtH8agqXZ329YvP1gWFGa0Utz25PE1VktQemdIXoW5oOoU+4GtM6RQb6 cIpa4zJ4Gxy47sjB7zrdIslUWxyN7MbE1J6heg9ovmyDvt18CTqwp6nnG2LGBGCVhpG4 DoXGs90FUAY9ZmsA4+lMGYsGaZ2kHVdFqC7/g3G+XSkhFK6aXo5wFlrcleh4WvZ6uK9M EFdaJvj3JNFs6GJZ3h6QVIOf3AXIZzhzQaeYzeQqlfUxMzIgW+kb0kwGRqQ+YrLu9zDr NpxrDg1bwKfu2aRMb0hcvQdVL2GqUJxdvnz3JueLhJH4h/6kT7DgJwE1BlkPKnRtl+yn ThhQ== 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=9oOfd5ioBGFgnDThXBfBlaouYrbK90Ol7CTAINZYLi8=; b=QL3VbwGqDZmRYdpJNN34JfbJj89VBIQ5qv22ndyVlNRbu9nR9/xD9Kms+acgxv9Vbm wHOShuzmL7C15Qw6scnMkR9C8rrWhEYZaD6546/8HKwY+BiX4CRKQOo8u9Rv76g6QeaF 2AB/h6EoRn3B1N1Q65P/yL9iTxX9/9DR2arypdeQ/v41Af0/wQTjFK1tfxv0rhyklwg4 bHA+oJzGxaBjkwLey19ShHE5D4g1/4v1SnMIFGN4sPqIwwPy/y9bPZ4bjIYn7GTgxeE8 GPwdh5guwuehNABY3XMMofCmE6hWEEyWtzKfUZ+WH0GeZy9PYaAXzJjdWYPMCu8fIsVS 8QOQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=J1npsbv1; 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 tj6-20020a170907c24600b008d6a0a6ba66si8696740ejc.800.2023.02.27.09.37.46; Mon, 27 Feb 2023 09:38:08 -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=J1npsbv1; 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 S229800AbjB0Rgq (ORCPT + 99 others); Mon, 27 Feb 2023 12:36:46 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47670 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229697AbjB0Rgm (ORCPT ); Mon, 27 Feb 2023 12:36:42 -0500 Received: from mail-pj1-x104a.google.com (mail-pj1-x104a.google.com [IPv6:2607:f8b0:4864:20::104a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C39BD2365D for ; Mon, 27 Feb 2023 09:36:40 -0800 (PST) Received: by mail-pj1-x104a.google.com with SMTP id gm13-20020a17090b100d00b0023704a72ca5so1893480pjb.4 for ; Mon, 27 Feb 2023 09:36:40 -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=9oOfd5ioBGFgnDThXBfBlaouYrbK90Ol7CTAINZYLi8=; b=J1npsbv1gUS6Xx9BiEsQjP7XeeP4aS0zilvFmnv/Rz+GOr5UTDVWeJrWl0j62csJqw pABdpewltkyMDTz5x9er0/tmyJAZh7x/KhM7c8duF9xadmsMayPg+H71fGIGq8oPKWOj MgbVwv2JgaJHWGglF3BAvt4DqnEv/mXmkg9toQmUgHu4O8sWHghp6pe4qMmBQxfPPa9Z PixCDkJQkwa7ilKkjAeCuQR96NDmtVqp0ZmLhbk++NpcJ1RgmTRpPPKm+6LBvLnGJc6j 5RqWVbaNSaafI5Uk5daP/3bMtRsXgSv4TZmCrUrgFU7+20OuWfc4Q8qOQnmnQqR2Eexd RlJg== 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=9oOfd5ioBGFgnDThXBfBlaouYrbK90Ol7CTAINZYLi8=; b=vJnuLVWIJcAIdQR5ZFEEr9WnH8crOzURd4qFomdsbACNOqzYqPO9OvSeQGfuhy1VyL NKWQq4BEMaBF4/yfmHOQbzY/svfbDTq23QXp52GMxFwi/dOg+BWzHqmFUkEagOn7xnTw i/q9htYxPFiYd4p8RrXg0zvqMUXMuNCFMPCiebfGKuiPOk2y4GVw4nQt2Ea4mHhvnwAm WJ0ub/WjTMo9g25YIuLOUNrd/MK54CdV/0VSXuVRAnqIUtu0BPevn/HkDF5r6lPfv0c5 mHlLf0orYJ4kvYsMnB6N+uDQcQHMsB1nGRhrE9SYIdUUaoEiUAx/jVbjR9OiK9zx73Y6 mOig== X-Gm-Message-State: AO0yUKWJas+boM9xjpuLfrFWkVZtL3BLYa/ZstZsH92uDtb3nB/tgIVz VSIBkXUVwQ0EwO2rFmwMgxuZ5ulMfi4= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:e1f6:21d1:eead:3897]) (user=surenb job=sendgmr) by 2002:a17:90b:17c9:b0:237:ae7c:1595 with SMTP id me9-20020a17090b17c900b00237ae7c1595mr187914pjb.2.1677519399986; Mon, 27 Feb 2023 09:36:39 -0800 (PST) Date: Mon, 27 Feb 2023 09:36:00 -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-2-surenb@google.com> Subject: [PATCH v4 01/33] 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-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?1759006675612070284?= X-GMAIL-MSGID: =?utf-8?q?1759006675612070284?= 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;