From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: akpm@linux-foundation.org, linux-mm@kvack.org,
linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org
Subject: Re: [PATCH v2 3/8] maple_tree: make mas_validate_gaps() to check metadata
Date: Tue, 11 Jul 2023 21:21:41 -0400 [thread overview]
Message-ID: <20230712012141.2ccxgy2xymsvq76n@revolver> (raw)
In-Reply-To: <20230711035444.526-4-zhangpeng.00@bytedance.com>
* Peng Zhang <zhangpeng.00@bytedance.com> [230710 23:55]:
> 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 <zhangpeng.00@bytedance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
> 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)
> --
> 2.20.1
>
next prev parent reply other threads:[~2023-07-12 1:22 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-11 3:54 [PATCH v2 0/8] Improve the validation for maple tree and some cleanup Peng Zhang
2023-07-11 3:54 ` [PATCH v2 1/8] maple_tree: set the node limit when creating a new root node Peng Zhang
2023-07-11 3:54 ` [PATCH v2 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Peng Zhang
2023-07-11 3:54 ` [PATCH v2 3/8] maple_tree: make mas_validate_gaps() to check metadata Peng Zhang
2023-07-12 1:21 ` Liam R. Howlett [this message]
2023-07-11 3:54 ` [PATCH v2 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Peng Zhang
2023-07-11 3:54 ` [PATCH v2 5/8] maple_tree: make mas_validate_limits() check root node and node limit Peng Zhang
2023-07-12 1:24 ` Liam R. Howlett
2023-07-11 3:54 ` [PATCH v2 6/8] maple_tree: update mt_validate() Peng Zhang
2023-07-12 1:22 ` Liam R. Howlett
2023-07-11 3:54 ` [PATCH v2 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Peng Zhang
2023-07-11 3:54 ` [PATCH v2 8/8] maple_tree: drop mas_first_entry() Peng Zhang
2023-07-11 10:10 ` [PATCH v2 0/8] Improve the validation for maple tree and some cleanup Geert Uytterhoeven
2023-07-12 1:27 ` Liam R. Howlett
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230712012141.2ccxgy2xymsvq76n@revolver \
--to=liam.howlett@oracle.com \
--cc=akpm@linux-foundation.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=maple-tree@lists.infradead.org \
--cc=zhangpeng.00@bytedance.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox