From patchwork Tue Jul 11 03:54:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308094 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 EACC0C001B0 for ; Tue, 11 Jul 2023 03:55:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 83B0A8E0005; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7EB518E0002; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 665178E0005; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) 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 586BC8E0002 for ; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 380CCAFD81 for ; Tue, 11 Jul 2023 03:55:10 +0000 (UTC) X-FDA: 80997965580.10.87FDCE0 Received: from mail-oo1-f46.google.com (mail-oo1-f46.google.com [209.85.161.46]) by imf09.hostedemail.com (Postfix) with ESMTP id 68BD214000C for ; Tue, 11 Jul 2023 03:55:08 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="ba93/Clp"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.46 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1689047708; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=3Sf1yS5B6eneELaNlZqL5FMfT0vCM5ltJ3mVgEmAAb+UxSN48hCD78LepUy2eB6KZke8Ra AK0TUSnzxeb0s1GSo9es0Alehrd4d2Ho/RPI44AaSfZFQeNs3Ky/peACgMUJsjNYfUS34p womKtShjYH+GQvH3rMDBGJ2qnJHmXdw= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="ba93/Clp"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.46 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047708; a=rsa-sha256; cv=none; b=O64bdy5Q8r3bWrNYp8uHjadIa05pu8t4Vs4LH2jMhTzeJu/ovRHrUDZpp1m6J45U4v/RGR tpOqZllhtwSWkD1wPMLU6qN4kZNeSe/m7g5tGy4gHG5bzDiLo4cw12SzJIFadHuc7ORQlH GRapjQ5+Alsbzz8Ln2sFSGKEjKXYFUY= Received: by mail-oo1-f46.google.com with SMTP id 006d021491bc7-55e1ae72dceso3772972eaf.3 for ; Mon, 10 Jul 2023 20:55:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047707; x=1691639707; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=ba93/ClplBNkeT536iWxDiRxrvDKLuk5KzbRIGlkNS/wjSUDSw0YG2fdY+wocAKY5f QIcaK5gsT/UKH1/j1gmInqnQydQtLdFwMoEaVF8Y0JynNst6O2va9pZ58iQ78jbDHz4R ndraKp96OKm6JzDpx9nPiOKqPRN6160Rbdcb2ka3yKuAnldcB1vGQArUyhhiXyJmqeu2 DFn5VI06R0dhs/J0QOYB+u8lmCI5Mtr0NqjaEOG+OIxk4KMQHM16azCfVmq9ldF6/EYQ M/n4PHfRcWMdYBEYL/VcaBdPlvczwae5dmhcz/2jNwPFqIr4m2+KUs+sIdqrqveJOrb2 UMtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047707; x=1691639707; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=ZUFJ2+V9nXYWosI0TAQAHUlkAZS+g5ljkEyVCeDJHdASYf5Wvi7+TzKw/brB7mDheM UtgRrI1hywNXHav3rWzqn/BKBUs3GCjKt7neViQfvJ2vWnitj4JjXIxCXnUFXLd/cypX n7HRrpjqUvQk2H9B9tmE5Gp7uEXozW0IOw57EkA2HfoYGUzhY5PlHSVpuKQ3jv6Bb+k8 dMppHDRdO/Ma+DOgcTGfiGVb6W0N5PaWhFVo1nn9LbHLDTK2HN0MvsklqHEtm9l3srHW v81zoOa1hsR+j/+G2nbhreldwoZEghLOgrnRE5J34Vu8K8JA0igsmzTRgD3qCHvSYHt9 j5bQ== X-Gm-Message-State: ABy/qLYWcQMPMjYPeBdyN66CtzimYLcELtNi05o1ZNl0jwpDL3EPK7GK H9U51BKZfUAYgQOQiCitV7uEIg== X-Google-Smtp-Source: APBJJlFQdZ5ouen7AkuwOFPVNmD1rUP/WKxjeZ5E1cKkHpCB9W7ANQJv0/FGjEcF/RHwquL0uQTEFg== X-Received: by 2002:a05:6358:c0f:b0:135:4dcf:9a2a with SMTP id f15-20020a0563580c0f00b001354dcf9a2amr10478949rwj.7.1689047707525; Mon, 10 Jul 2023 20:55:07 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.05 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:07 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Tue, 11 Jul 2023 11:54:39 +0800 Message-Id: <20230711035444.526-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 68BD214000C X-Rspam-User: X-Stat-Signature: 8tsu6fbuig33g6ipqe15xjtjxh8w36xr X-Rspamd-Server: rspam01 X-HE-Tag: 1689047708-45670 X-HE-Meta: U2FsdGVkX19kzXP2gXiwl/KEQgi8iequnG22tBq3bxtyMrEwTUgFYeHXtzjgogFz85ZDrJWc/dJ94QEzWRu4I6QPVKh4muK3CGt4mIm3I3DzhEyTrn4PWXUQc37KWR7Q/jnH1/WvkBHGUEBj5etofUXtt4BKZl41sIlokTvoP0bQ+myKPXwgq7YknFVUVGTczNXVVnomEvST+4WgkG8l5S0QcDqJ+CPS4FXlqO158ZJSKKyoGK++XGlVKv1fswxkzsL1RT+F0IrSv9Az5cvkJObK2C/FxuOwKZqFMBs4Pv9PMy/Fyt244x6HthJc8ecH09evSCnehOI0QmsQ88n7FXuf/+R1OU9YKFcejZavTLKqGlhXQe71Ow7JdSGz/gZpbxzNs+pi2F7JLzD4SbviWJKbRt+VfbkkrIaM3M+i6nGaT3RMVSUzh2111r9dKHLjEmOIZNEuwYBSL3M/kYewVO/2FyhV5CmeAAxJYGKIu/cFx5FBeRfC4YPwO8nz5vEOD47jYIDHzPE+N6bKVausMPeCdrvqXLhh5RQk/eEAHM5Inxj9OXcO3aYwNf2TZmOaxHCaGgPa7sjom7mFVw8U2eEGXImoIhl7FITkZ0R9NEW41NzlleWV826cDF57QA3rssd7zzD2qU9fjFbSJyO7i1G1HnKBo0Hg8rTomCLglzUOwSIwUymgKXbWD/Kc7XboVwSJ/q6+X+rcy6gxzwt76pabeOJ+HKfUJLZ/14bfBWnwBc+A+M1DTXXc2T00jqDQGS5OvpMmBeRszJ0Vb6sOXeMxTZmL00qXWjSgcJfm+SoHY5cFBCBwEWLi68eM8UR+VQf7jYK82aCou692Fch/bN4wuIT9VsXxvhKsWVNDt2hYKXyXYN4UdPUSos6rnjzuVPopgOZMGBYdHGfUQBSwM/bJ0ODNHFDRTqiEa78zrG7NF098kXT7YMBMSyUEWx2hXzPajgcJQlRhhGJM4Je AjRAi+dE I8AfSbOQUcVljoe2ueSNjfI8kz7k/zTa7acZ2JRfV38S/IKWTgxI/W5EJI8iNXfBsAbRgLJGiSYubLYYc+Zsohs95jQ8k15kAqjYlxvOyx7nRCaSSlR2LFfjI+ucHZJGn5L/1smzSzY35zc4KhUDJtZ76bk5Np6qRkVqilpLpWDek7Dfgm7AnAcu4jB8s3d+AnA+dmlhEzqZMyyeGoRTh8EljwW8of7pL8R8ZmAeMrw+4dMuIJdSmoVzRU4a79g/NaknM7NTOsLfZN874eVQFwzB6w0aHgi1H1fTsXi5yXrSOAmTvIlb/dktgwwh96se8JWrSQoZdc57GgpMDc29NP6wmHqk7XJcTgR8AFpECtcJQoN1E8c5RB/G+Fn7rFuOKQOmey8GLMW6EFhbBsKVRCKRml5eQa342f07hS/onX0tPnmAxdA84s50BLuGGTXEwRQMZ+jnSpUHsY0Q= 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: Make mas_validate_gaps() check whether the offset in the metadata points to the largest gap. By the way, simplify this function. Add the verification that gaps beyond the node limit are zero. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 78 ++++++++++++++++++++++++++---------------------- 1 file changed, 42 insertions(+), 36 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8982146338..a5776fab1875 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); static void mas_validate_gaps(struct ma_state *mas) { struct maple_enode *mte = mas->node; - struct maple_node *p_mn; + struct maple_node *p_mn, *node = mte_to_node(mte); + enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; - unsigned char p_slot; + unsigned char p_slot, offset; unsigned long *gaps = NULL; - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); - int i; + unsigned long *pivots = ma_pivots(node, mt); + unsigned int i; - if (ma_is_dense(mte_node_type(mte))) { + if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) @@ -7004,52 +7005,59 @@ static void mas_validate_gaps(struct ma_state *mas) goto counted; } - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); + gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); + p_end = mas_logical_pivot(mas, pivots, i, mt); if (!gaps) { - if (mas_get_slot(mas, i)) { - gap = 0; - goto not_empty; - } - - gap += p_end - p_start + 1; + if (!mas_get_slot(mas, i)) + gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i); gap = gaps[i]; - if (!entry) { - if (gap != p_end - p_start + 1) { - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", - mas_mn(mas), i, - mas_get_slot(mas, i), gap, - p_end, p_start); - mt_dump(mas->tree, mt_dump_hex); - - MT_BUG_ON(mas->tree, - gap != p_end - p_start + 1); - } - } else { - if (gap > p_end - p_start + 1) { - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", - mas_mn(mas), i, gap, p_end, p_start, - p_end - p_start + 1); - MT_BUG_ON(mas->tree, - gap > p_end - p_start + 1); - } + MT_BUG_ON(mas->tree, !entry); + + if (gap > p_end - p_start + 1) { + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", + mas_mn(mas), i, gap, p_end, p_start, + p_end - p_start + 1); + MT_BUG_ON(mas->tree, gap > p_end - p_start + 1); } } if (gap > max_gap) max_gap = gap; -not_empty: + p_start = p_end + 1; if (p_end >= mas->max) break; } counted: + if (mt == maple_arange_64) { + offset = ma_meta_gap(node, mt); + if (offset > i) { + pr_err("gap offset %p[%u] is invalid\n", node, offset); + MT_BUG_ON(mas->tree, 1); + } + + if (gaps[offset] != max_gap) { + pr_err("gap %p[%u] is not the largest gap %lu\n", + node, offset, max_gap); + MT_BUG_ON(mas->tree, 1); + } + + MT_BUG_ON(mas->tree, !gaps); + for (i++ ; i < mt_slot_count(mte); i++) { + if (gaps[i] != 0) { + pr_err("gap %p[%u] beyond node limit != 0\n", + node, i); + MT_BUG_ON(mas->tree, 1); + } + } + } + if (mte_is_root(mte)) return; @@ -7059,10 +7067,8 @@ static void mas_validate_gaps(struct ma_state *mas) if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); + MT_BUG_ON(mas->tree, 1); } - - MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas)