From patchwork Fri Jan 27 19:40:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13119243 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 F01C7C54EAA for ; Fri, 27 Jan 2023 19:41:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8CDC66B007D; Fri, 27 Jan 2023 14:41:24 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 87CFA6B007B; Fri, 27 Jan 2023 14:41:24 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 71E776B007D; Fri, 27 Jan 2023 14:41:24 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 61A096B0078 for ; Fri, 27 Jan 2023 14:41:24 -0500 (EST) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 3F390A0FC0 for ; Fri, 27 Jan 2023 19:41:24 +0000 (UTC) X-FDA: 80401598088.11.1CF7849 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) by imf25.hostedemail.com (Postfix) with ESMTP id 76C97A0023 for ; Fri, 27 Jan 2023 19:41:17 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=q++c4JbF; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf25.hostedemail.com: domain of 33CjUYwYKCKMVXUHQEJRRJOH.FRPOLQXa-PPNYDFN.RUJ@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=33CjUYwYKCKMVXUHQEJRRJOH.FRPOLQXa-PPNYDFN.RUJ@flex--surenb.bounces.google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1674848477; 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=SRJKiHKrq/SvrK23nJ6WvAwYz6ftOZ3c7xtMrR/Zkmo=; b=M+Uv3xJtiqZNNiJnySVOigo4aQngqJnOzIb2LlujnaUK7LrGaZDfa6T9byRFYUlK/kY+i5 OJ2OIzE8vrCryMgYMV/RmGUHl3taC7i0jjhSV8LDe7aC+Bm0IQbj55/GMaNJZGyOeP3Frw qKfU8rE9g/mBBFathPzz5c8IQbcXUB8= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=q++c4JbF; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf25.hostedemail.com: domain of 33CjUYwYKCKMVXUHQEJRRJOH.FRPOLQXa-PPNYDFN.RUJ@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=33CjUYwYKCKMVXUHQEJRRJOH.FRPOLQXa-PPNYDFN.RUJ@flex--surenb.bounces.google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1674848477; a=rsa-sha256; cv=none; b=4HpnhH4pcRgvYYmL/D82lQCFpBzRhEI4WXHlQeoWJyf9RK7RQIOmIIAu7icHiL/l75Ny7n FQCzKQ2qOGN/SqCZRJMc+J3kH8ZvkpClDG9KZBKBoTWzE6i7qlqtJo8YZWIruSKY0za/8r 2iiGrEzXIDDM6Jqxfs3W1eX/MuLmG3g= Received: by mail-yb1-f202.google.com with SMTP id p19-20020a25d813000000b0080b78270db5so6347135ybg.15 for ; Fri, 27 Jan 2023 11:41:17 -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=SRJKiHKrq/SvrK23nJ6WvAwYz6ftOZ3c7xtMrR/Zkmo=; b=q++c4JbFs1cULNmXHJ6C3DczcQ0hXzOKIr6+9Qx2yz39vZWA+rjLc18PKWJkWy6B+C UeBdui8K3sk0l0OIGcxNzLRt494xbxI7WVRAtP+VLTOL1/q+UNWJf0WDLHuQPthduco2 hKKj52t3wKu54Vbflyx5DWFngCga+0YCh2aWf3wXfSgRE76VHyLLWka1QvKlb5EEsVq+ yKsc5SnLc4E9cZlzwXYLALtVVR/qLY2NGEjlF8VIz3gJJ8VVrEVxdVCt2bqpvNVXSzLO bCSv1unz+7C8JA4tTmfPKXKgKgaiBEIUDtx7XKU+dM+xg3yKNZdzkdQzW0TW1MecPnG9 7xHA== 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=SRJKiHKrq/SvrK23nJ6WvAwYz6ftOZ3c7xtMrR/Zkmo=; b=tLu+7zWgEo6/BkyKS64h1IcQuQjaRni1jqUZ/ZMNnLuPP3+X7ikSlKb8ObUrlAh+XF eBe+qhf2ox0vA0Ht8GeDAYMlR4uNtWRmYW9IDJv1dVQWM4JZx1tirT57w3EdzOEpIZ4z +MP+SWFT1SqJhMprSMrF6DxOS2zUeHSkVaYFSM3a8TkUA5wAwi8oK0zV+RKbaJX5TFPz S4F67Ca356wx2u6ALkWkMrjj7bOy4057V36Jd0ozA7+xrd8IkDd//tcJT4iYlmCWiSGx QurKU8NODJXqszYOhkaZv9ZspiGgQOM8WHjW3affDBVst1ZkWdLRUDlp2tmHfRNkGRbc 0Z4w== X-Gm-Message-State: AFqh2kr1yayv+E7gdrZwSfDu1/CGcBX05UZZU1cSAVMXPBkuoxndNgYC IvwDpRGs5fXhchU1yoJgOoCwZaNlsQE= X-Google-Smtp-Source: AMrXdXvEqVwWOYAYjpqjq4VZxkQLftXilDeGRL6KyIgBgBs2rP6fdUqH1kwtp8PmmItyT8YCkU5DjbIMLFI= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:4e19:be9:c5d0:8483]) (user=surenb job=sendgmr) by 2002:a25:4e54:0:b0:7fe:6d35:1a28 with SMTP id c81-20020a254e54000000b007fe6d351a28mr4351236ybb.534.1674848476456; Fri, 27 Jan 2023 11:41:16 -0800 (PST) Date: Fri, 27 Jan 2023 11:40:38 -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-2-surenb@google.com> Subject: [PATCH v2 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, 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-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 76C97A0023 X-Stat-Signature: hf5wpagfwd45gow5awj7fwmnjpryqeih X-HE-Tag: 1674848477-674551 X-HE-Meta: U2FsdGVkX1+JNOx7J3euxuxadNSEq2NXdaXMWtHiWXHfrbwsrg9mzbcM8wD5h/ORkQ5n3uCxNHG31o2OuZcH4ttAoxtSWpxMRtqwDoh0SjAPmIdrEdc2fJqjPVsvchh3YYz62jZhrJKngMolXwhlkolOoTduSNf6lPG8zifxHpsVPUFi7Xo1gx7+s70ct6yXHEA6V7RG1cMxirRB2HmWUreLOhS5zuXFZRK+nlyIxrFikwmqLLC+F4gAJhRr04WN/CxfqMxPhDXFfPwLsISGY13a/weJsDAFFiSBc9VfhmihcV4FiBKimgvT2CCE+F7od0WUzHWPy2bqD5Bf34e9sR6xpsvlgqPil7ZGjpFiczDTZkaNzsNO+tLil9HKQDOkjWdhN32nq9Xs/hnycj+qRIakio0OXFujvSHEVXh7lXtcFWejnrw5QtxmZpO6uj1Dvt8wq62hOfKqzhaisl0SxiK8c7Wbp+EylVPnEkrXiw3DKWE0148oRPW6LdsopQqsNevQ9KHSJ+3A7W0zyfuDge6E8fTETlqWOaNHiApzEU5eBWEW4NZ0BcoQyC5QJZ4CpzdYXJ+ZRgTZQ4vDv9LbqN2iBBg8xnqTifGVcwufcZc2NiyDfUfijparyq8CYgjp8OsNQaqlhwkj6m2vrM31LD5idFHtg9GLzJKXbMmx6UF+8VIfbG0YKOx73OZPi5DxnMMwa91/KNqzZvpZpEb6eCYVbQ4xzmSFYqVrWpGmVVZ2M5/PX1GMVwSv6OPtcJxd03J6M4Cv51KR8wTkWKichw5aJEp3XXjFltLnsBKc0NTXd74d5vSgOnpaD4AhcbXgUIpQPZ4cG9GjMbqzIKHZdWXXxVWe6IZq9Bh8NELtjBI8v+UXBoRjINy6zL7h0i4rS6bsumdtOtihpHMqwvspmb2GNg3GzVitIBRvTOy5EkZm+z6VG9rm3QkUfSOeAa62CfimOZsdEcL3pqeKCWf RRu3p/d8 nxy2AyU8cWZNebpfB49NTxBLte+y+HmY9yGyDC/fHYDyB5a0+LsVYgBOwjKntoXFFXUfJZRt1zs2f0EKb1H/xE+gxxO27HTv2tcznGn9clDHY7ZWddbvYnznNPXCWe03nQ52QC07BKRS+Hy+EvCdJEixpYYT2wx1VCfMHCPBkwgyjIWOG/G3IS0B8ixk4KLnJpQy3LyF34tYU6UVSxTk7w+JhmRNNe7Kv8u7LZhHXvV1CVcARwuXUnFGCjyG790Ty/aVHHzf++bW6i1uEtR67F8JvO8QSBxLHQWEPvW5D72v0HFaWxIkLA3q480yzebzWOm0FpbIol8r8JX8mY0qybTxgsG0cTiDDuCb0621K4vVBsSP6XMJmWTXBe1WAamRPwS4WJBNIH9wMhxyQIUBlPQcxRrIdoosphfGHmWVu78qoRAwF4Ntu8SEkkxXAdG+lBMQcNbKu8uaen1nsEb1babpgkHoNDUi1MP3bEQGI1SXIt0mUjbDkX3cdIyJQHIajzSs1NVBfs4l4oH3zlraV2WBuLXT1KA1zSgPJ7WbKeV/MZmiEd/Jb2sUtcNRuTxfYsClFyxjrJZ3PGWHNi1oRbCdO0w9Y7QHuIdeaaKwEwg2vQNUgpshWnccHiyEhNeEgLilld6RLLyUK4iwPgsqQ0OvC0XR1r1q+JUMY0mr6+zgvbMxdN6z5b7JPl3fUp35U3tTeCnOKFklFofjrSeJhUhzCEQpoR5DIuCESd3x3YFbx/deoQUDNCh7SOzhy9GDNEVQRf0eV37JIu/m8sHuKoi+ukw== 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 5e9703189259..e5eeecd14eee 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -537,6 +537,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 @@ -618,6 +619,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, @@ -1089,8 +1092,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; @@ -1394,6 +1400,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); @@ -1429,6 +1438,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); @@ -4498,6 +4510,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; @@ -4519,6 +4534,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; @@ -4567,6 +4585,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; @@ -4590,7 +4609,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); @@ -4606,6 +4629,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]; } @@ -4652,11 +4678,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) @@ -4810,6 +4839,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 @@ -6624,11 +6658,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); @@ -6648,13 +6682,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;