From: Peng Zhang <zhangpeng.00@bytedance.com>
To: "Liam R. Howlett" <Liam.Howlett@oracle.com>
Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org,
maple-tree@lists.infradead.org,
Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [PATCH 26/34] maple_tree: Update testing code for mas_{next,prev,walk}
Date: Thu, 4 May 2023 11:33:12 +0800 [thread overview]
Message-ID: <915edff9-1753-2a0b-327f-ba11e6c5a7b1@bytedance.com> (raw)
In-Reply-To: <20230425140955.3834476-27-Liam.Howlett@oracle.com>
在 2023/4/25 22:09, Liam R. Howlett 写道:
> Now that the functions have changed the limits, update the testing of
> the maple tree to test these new settings.
>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
> lib/test_maple_tree.c | 641 +++++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 635 insertions(+), 6 deletions(-)
>
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index ae08d34d1d3c4..345eef526d8b0 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -1290,6 +1290,7 @@ static noinline void __init check_root_expand(struct maple_tree *mt)
> mas_lock(&mas);
> mas_set(&mas, 3);
> ptr = mas_walk(&mas);
> + MAS_BUG_ON(&mas, mas.index != 0);
> MT_BUG_ON(mt, ptr != NULL);
> MT_BUG_ON(mt, mas.index != 0);
> MT_BUG_ON(mt, mas.last != ULONG_MAX);
> @@ -1300,7 +1301,7 @@ static noinline void __init check_root_expand(struct maple_tree *mt)
>
> mas_set(&mas, 0);
> ptr = mas_walk(&mas);
> - MT_BUG_ON(mt, ptr != NULL);
> + MAS_BUG_ON(&mas, ptr != NULL);
>
> mas_set(&mas, 1);
> ptr = mas_walk(&mas);
> @@ -1359,7 +1360,7 @@ static noinline void __init check_root_expand(struct maple_tree *mt)
> mas_store_gfp(&mas, ptr, GFP_KERNEL);
> ptr = mas_next(&mas, ULONG_MAX);
> MT_BUG_ON(mt, ptr != NULL);
> - MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
> + MAS_BUG_ON(&mas, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
>
> mas_set(&mas, 1);
> ptr = mas_prev(&mas, 0);
> @@ -1768,12 +1769,12 @@ static noinline void __init check_iteration(struct maple_tree *mt)
> mas.index = 760;
> mas.last = 765;
> mas_store(&mas, val);
> - mas_next(&mas, ULONG_MAX);
> }
> i++;
> }
> /* Make sure the next find returns the one after 765, 766-769 */
> val = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, val != xa_mk_value(76));
> MT_BUG_ON(mt, val != xa_mk_value(76));
> mas_unlock(&mas);
> mas_destroy(&mas);
> @@ -1979,7 +1980,7 @@ static noinline void __init next_prev_test(struct maple_tree *mt)
>
> val = mas_next(&mas, ULONG_MAX);
> MT_BUG_ON(mt, val != NULL);
> - MT_BUG_ON(mt, mas.index != ULONG_MAX);
> + MT_BUG_ON(mt, mas.index != 0x7d6);
> MT_BUG_ON(mt, mas.last != ULONG_MAX);
>
> val = mas_prev(&mas, 0);
> @@ -2003,7 +2004,8 @@ static noinline void __init next_prev_test(struct maple_tree *mt)
> val = mas_prev(&mas, 0);
> MT_BUG_ON(mt, val != NULL);
> MT_BUG_ON(mt, mas.index != 0);
> - MT_BUG_ON(mt, mas.last != 0);
> + MT_BUG_ON(mt, mas.last != 5);
> + MT_BUG_ON(mt, mas.node != MAS_NONE);
>
> mas.index = 0;
> mas.last = 5;
> @@ -2015,7 +2017,7 @@ static noinline void __init next_prev_test(struct maple_tree *mt)
> val = mas_prev(&mas, 0);
> MT_BUG_ON(mt, val != NULL);
> MT_BUG_ON(mt, mas.index != 0);
> - MT_BUG_ON(mt, mas.last != 0);
> + MT_BUG_ON(mt, mas.last != 9);
> mas_unlock(&mas);
>
> mtree_destroy(mt);
> @@ -2718,6 +2720,629 @@ static noinline void __init check_empty_area_fill(struct maple_tree *mt)
> mt_set_non_kernel(0);
> }
>
> +/*
> + * Check MAS_START, MAS_PAUSE, active (implied), and MAS_NONE transitions.
> + *
> + * The table below shows the single entry tree (0-0 pointer) and normal tree
> + * with nodes.
> + *
> + * Function ENTRY Start Result index & last
> + * ┬ ┬ ┬ ┬ ┬
> + * │ │ │ │ └─ the final range
> + * │ │ │ └─ The node value after execution
> + * │ │ └─ The node value before execution
> + * │ └─ If the entry exists of does not exists (DNE)
of->or?
> + * └─ The function name
> + *
> + * Function ENTRY Start Result index & last
> + * mas_next()
> + * - after last
> + * Single entry tree at 0-0
> + * ------------------------
> + * DNE MAS_START MAS_NONE 1 - oo
> + * DNE MAS_PAUSE MAS_NONE 1 - oo
> + * DNE MAS_ROOT MAS_NONE 1 - oo
> + * when index = 0
> + * DNE MAS_NONE MAS_ROOT 0
> + * when index > 0
> + * DNE MAS_NONE MAS_NONE 1 - oo
> + *
> + * Normal tree
> + * -----------
> + * exists MAS_START active range
> + * DNE MAS_START active set to last range
> + * exists MAS_PAUSE active range
> + * DNE MAS_PAUSE active set to last range
> + * exists MAS_NONE active range
> + * exists active active range
> + * DNE active active set to last range
> + *
> + * Function ENTRY Start Result index & last
> + * mas_prev()
> + * - before index
> + * Single entry tree at 0-0
> + * ------------------------
> + * if index > 0
> + * exists MAS_START MAS_ROOT 0
> + * exists MAS_PAUSE MAS_ROOT 0
> + * exists MAS_NONE MAS_ROOT 0
> + *
> + * if index == 0
> + * DNE MAS_START MAS_NONE 0
> + * DNE MAS_PAUSE MAS_NONE 0
> + * DNE MAS_NONE MAS_NONE 0
> + * DNE MAS_ROOT MAS_NONE 0
> + *
> + * Normal tree
> + * -----------
> + * exists MAS_START active range
> + * DNE MAS_START active set to min
> + * exists MAS_PAUSE active range
> + * DNE MAS_PAUSE active set to min
> + * exists MAS_NONE active range
> + * DNE MAS_NONE MAS_NONE set to min
> + * any MAS_ROOT MAS_NONE 0
> + * exists active active range
> + * DNE active active last range
> + *
> + * Function ENTRY Start Result index & last
> + * mas_find()
> + * - at index or next
> + * Single entry tree at 0-0
> + * ------------------------
> + * if index > 0
> + * DNE MAS_START MAS_NONE 0
> + * DNE MAS_PAUSE MAS_NONE 0
> + * DNE MAS_ROOT MAS_NONE 0
> + * DNE MAS_NONE MAS_NONE 0
> + * if index == 0
> + * exists MAS_START MAS_ROOT 0
> + * exists MAS_PAUSE MAS_ROOT 0
> + * exists MAS_NONE MAS_ROOT 0
> + *
> + * Normal tree
> + * -----------
> + * exists MAS_START active range
> + * DNE MAS_START active set to max
> + * exists MAS_PAUSE active range
> + * DNE MAS_PAUSE active set to max
> + * exists MAS_NONE active range
> + * exists active active range
> + * DNE active active last range (max < last)
> + *
> + * Function ENTRY Start Result index & last
> + * mas_find_rev()
> + * - at index or before
> + * Single entry tree at 0-0
> + * ------------------------
> + * if index > 0
> + * exists MAS_START MAS_ROOT 0
> + * exists MAS_PAUSE MAS_ROOT 0
> + * exists MAS_NONE MAS_ROOT 0
> + * if index == 0
> + * DNE MAS_START MAS_NONE 0
> + * DNE MAS_PAUSE MAS_NONE 0
> + * DNE MAS_NONE MAS_NONE 0
> + * DNE MAS_ROOT MAS_NONE 0
> + *
> + * Normal tree
> + * -----------
> + * exists MAS_START active range
> + * DNE MAS_START active set to min
> + * exists MAS_PAUSE active range
> + * DNE MAS_PAUSE active set to min
> + * exists MAS_NONE active range
> + * exists active active range
> + * DNE active active last range (min > index)
> + *
> + * Function ENTRY Start Result index & last
> + * mas_walk()
> + * - Look up index
> + * Single entry tree at 0-0
> + * ------------------------
> + * if index > 0
> + * DNE MAS_START MAS_ROOT 1 - oo
> + * DNE MAS_PAUSE MAS_ROOT 1 - oo
> + * DNE MAS_NONE MAS_ROOT 1 - oo
> + * DNE MAS_ROOT MAS_ROOT 1 - oo
> + * if index == 0
> + * exists MAS_START MAS_ROOT 0
> + * exists MAS_PAUSE MAS_ROOT 0
> + * exists MAS_NONE MAS_ROOT 0
> + * exists MAS_ROOT MAS_ROOT 0
> + *
> + * Normal tree
> + * -----------
> + * exists MAS_START active range
> + * DNE MAS_START active range of NULL
> + * exists MAS_PAUSE active range
> + * DNE MAS_PAUSE active range of NULL
> + * exists MAS_NONE active range
> + * DNE MAS_NONE active range of NULL
> + * exists active active range
> + * DNE active active range of NULL
> + */
> +
> +#define mas_active(x) (((x).node != MAS_ROOT) && \
> + ((x).node != MAS_START) && \
> + ((x).node != MAS_PAUSE) && \
> + ((x).node != MAS_NONE))
> +static noinline void __init check_state_handling(struct maple_tree *mt)
> +{
> + MA_STATE(mas, mt, 0, 0);
> + void *entry, *ptr = (void *) 0x1234500;
> + void *ptr2 = &ptr;
> + void *ptr3 = &ptr2;
> +
> + /* Check MAS_ROOT First */
> + mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
> +
> + mas_lock(&mas);
> + /* prev: Start -> none */
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* prev: Start -> root */
> + mas_set(&mas, 10);
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* prev: pause -> root */
> + mas_set(&mas, 10);
> + mas_pause(&mas);
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* next: start -> none */
> + mas_set(&mas, 0);
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* next: start -> none */
> + mas_set(&mas, 10);
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find: start -> root */
> + mas_set(&mas, 0);
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* find: root -> none */
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find: none -> none */
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find: start -> none */
> + mas_set(&mas, 10);
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find_rev: none -> root */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* find_rev: start -> root */
> + mas_set(&mas, 0);
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* find_rev: root -> none */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find_rev: none -> none */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* find_rev: start -> root */
> + mas_set(&mas, 10);
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* walk: start -> none */
> + mas_set(&mas, 10);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* walk: pause -> none*/
> + mas_set(&mas, 10);
> + mas_pause(&mas);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* walk: none -> none */
> + mas.index = mas.last = 10;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* walk: none -> none */
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* walk: start -> root */
> + mas_set(&mas, 0);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* walk: pause -> root */
> + mas_set(&mas, 0);
> + mas_pause(&mas);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* walk: none -> root */
> + mas.node = MAS_NONE;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* walk: root -> root */
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + /* walk: root -> none */
> + mas_set(&mas, 10);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 1);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, mas.node != MAS_NONE);
> +
> + /* walk: none -> root */
> + mas.index = mas.last = 0;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0);
> + MAS_BUG_ON(&mas, mas.node != MAS_ROOT);
> +
> + mas_unlock(&mas);
> +
> + /* Check when there is an actual node */
> + mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
> + mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
> + mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
> + mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
> +
> + mas_lock(&mas);
> +
> + /* next: start ->active */
> + mas_set(&mas, 0);
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next: pause ->active */
> + mas_set(&mas, 0);
> + mas_pause(&mas);
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next: none ->active */
> + mas.index = mas.last = 0;
> + mas.offset = 0;
> + mas.node = MAS_NONE;
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next:active ->active */
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr2);
> + MAS_BUG_ON(&mas, mas.index != 0x2000);
> + MAS_BUG_ON(&mas, mas.last != 0x2500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next:active -> active out of range*/
> + entry = mas_next(&mas, 0x2999);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x2501);
> + MAS_BUG_ON(&mas, mas.last != 0x2fff);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* Continue after out of range*/
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr3);
> + MAS_BUG_ON(&mas, mas.index != 0x3000);
> + MAS_BUG_ON(&mas, mas.last != 0x3500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next:active -> active out of range*/
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x3501);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* next: none -> active, skip value at location */
> + mas_set(&mas, 0);
> + entry = mas_next(&mas, ULONG_MAX);
> + mas.node = MAS_NONE;
> + mas.offset = 0;
> + entry = mas_next(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr2);
> + MAS_BUG_ON(&mas, mas.index != 0x2000);
> + MAS_BUG_ON(&mas, mas.last != 0x2500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* prev:active ->active */
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* prev:active -> active out of range*/
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0x0FFF);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* prev: pause ->active */
> + mas_set(&mas, 0x3600);
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr3);
> + mas_pause(&mas);
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr2);
> + MAS_BUG_ON(&mas, mas.index != 0x2000);
> + MAS_BUG_ON(&mas, mas.last != 0x2500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* prev:active -> active out of range*/
> + entry = mas_prev(&mas, 0x1600);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x1501);
> + MAS_BUG_ON(&mas, mas.last != 0x1FFF);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* prev: active ->active, continue*/
> + entry = mas_prev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find: start ->active */
> + mas_set(&mas, 0);
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find: pause ->active */
> + mas_set(&mas, 0);
> + mas_pause(&mas);
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find: start ->active on value */;
> + mas_set(&mas, 1200);
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find:active ->active */
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != ptr2);
> + MAS_BUG_ON(&mas, mas.index != 0x2000);
> + MAS_BUG_ON(&mas, mas.last != 0x2500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> +
> + /* find:active -> active (NULL)*/
> + entry = mas_find(&mas, 0x2700);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x2501);
> + MAS_BUG_ON(&mas, mas.last != 0x2FFF);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find: none ->active */
> + entry = mas_find(&mas, 0x5000);
> + MAS_BUG_ON(&mas, entry != ptr3);
> + MAS_BUG_ON(&mas, mas.index != 0x3000);
> + MAS_BUG_ON(&mas, mas.last != 0x3500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find:active -> active (NULL) end*/
> + entry = mas_find(&mas, ULONG_MAX);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x3501);
> + MAS_BUG_ON(&mas, mas.last != ULONG_MAX);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find_rev: active (END) ->active */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr3);
> + MAS_BUG_ON(&mas, mas.index != 0x3000);
> + MAS_BUG_ON(&mas, mas.last != 0x3500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find_rev:active ->active */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr2);
> + MAS_BUG_ON(&mas, mas.index != 0x2000);
> + MAS_BUG_ON(&mas, mas.last != 0x2500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find_rev: pause ->active */
> + mas_pause(&mas);
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find_rev:active -> active */
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0);
> + MAS_BUG_ON(&mas, mas.last != 0x0FFF);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* find_rev: start ->active */
> + mas_set(&mas, 0x1200);
> + entry = mas_find_rev(&mas, 0);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk start ->active */
> + mas_set(&mas, 0x1200);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk start ->active */
> + mas_set(&mas, 0x1600);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x1501);
> + MAS_BUG_ON(&mas, mas.last != 0x1fff);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk pause ->active */
> + mas_set(&mas, 0x1200);
> + mas_pause(&mas);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk pause -> active */
> + mas_set(&mas, 0x1600);
> + mas_pause(&mas);
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x1501);
> + MAS_BUG_ON(&mas, mas.last != 0x1fff);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk none -> active */
> + mas_set(&mas, 0x1200);
> + mas.node = MAS_NONE;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk none -> active */
> + mas_set(&mas, 0x1600);
> + mas.node = MAS_NONE;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x1501);
> + MAS_BUG_ON(&mas, mas.last != 0x1fff);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk active -> active */
> + mas.index = 0x1200;
> + mas.last = 0x1200;
> + mas.offset = 0;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != ptr);
> + MAS_BUG_ON(&mas, mas.index != 0x1000);
> + MAS_BUG_ON(&mas, mas.last != 0x1500);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + /* mas_walk active -> active */
> + mas.index = 0x1600;
> + mas.last = 0x1600;
> + entry = mas_walk(&mas);
> + MAS_BUG_ON(&mas, entry != NULL);
> + MAS_BUG_ON(&mas, mas.index != 0x1501);
> + MAS_BUG_ON(&mas, mas.last != 0x1fff);
> + MAS_BUG_ON(&mas, !mas_active(mas));
> +
> + mas_unlock(&mas);
> +}
> +
> static DEFINE_MTREE(tree);
> static int __init maple_tree_seed(void)
> {
> @@ -2979,6 +3604,10 @@ static int __init maple_tree_seed(void)
> mtree_destroy(&tree);
>
>
> + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
> + check_state_handling(&tree);
> + mtree_destroy(&tree);
> +
> #if defined(BENCH)
> skip:
> #endif
next prev parent reply other threads:[~2023-05-04 3:33 UTC|newest]
Thread overview: 65+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-25 14:09 [PATCH 00/34] Maple tree mas_{next,prev}_range() and cleanup Liam R. Howlett
2023-04-25 14:09 ` [PATCH 01/34] maple_tree: Fix static analyser cppcheck issue Liam R. Howlett
2023-04-26 4:06 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 02/34] maple_tree: Clean up mas_parent_enum() Liam R. Howlett
2023-04-25 16:13 ` Wei Yang
2023-04-26 4:14 ` Peng Zhang
2023-04-26 21:07 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 03/34] maple_tree: Avoid unnecessary ascending Liam R. Howlett
2023-04-26 5:27 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 04/34] maple_tree: Clean up mas_dfs_postorder() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 05/34] maple_tree: Add format option to mt_dump() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 06/34] maple_tree: Add debug BUG_ON and WARN_ON variants Liam R. Howlett
2023-04-25 14:09 ` [PATCH 07/34] maple_tree: Convert BUG_ON() to MT_BUG_ON() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 08/34] maple_tree: Change RCU checks to WARN_ON() instead of BUG_ON() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 09/34] maple_tree: Convert debug code to use MT_WARN_ON() and MAS_WARN_ON() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 10/34] maple_tree: Use MAS_BUG_ON() when setting a leaf node as a parent Liam R. Howlett
2023-04-28 10:08 ` Petr Tesařík
2023-05-03 19:31 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 11/34] maple_tree: Use MAS_BUG_ON() in mas_set_height() Liam R. Howlett
2023-04-28 10:10 ` Petr Tesařík
2023-05-03 19:33 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 12/34] maple_tree: Use MAS_BUG_ON() from mas_topiary_range() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 13/34] maple_tree: Use MAS_WR_BUG_ON() in mas_store_prealloc() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 14/34] maple_tree: Use MAS_BUG_ON() prior to calling mas_meta_gap() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 15/34] maple_tree: Return error on mte_pivots() out of range Liam R. Howlett
2023-04-26 9:55 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 16/34] maple_tree: Make test code work without debug enabled Liam R. Howlett
2023-04-26 3:23 ` kernel test robot
2023-04-25 14:09 ` [PATCH 17/34] mm: Update validate_mm() to use vma iterator Liam R. Howlett
2023-04-25 14:09 ` [PATCH 18/34] mm: Update vma_iter_store() to use MAS_WARN_ON() Liam R. Howlett
2023-04-27 1:07 ` Sergey Senozhatsky
2023-04-27 1:17 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 19/34] maple_tree: Add __init and __exit to test module Liam R. Howlett
2023-04-25 14:09 ` [PATCH 20/34] maple_tree: Remove unnecessary check from mas_destroy() Liam R. Howlett
2023-04-26 9:59 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 21/34] maple_tree: mas_start() reset depth on dead node Liam R. Howlett
2023-04-28 2:45 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 22/34] mm/mmap: Change do_vmi_align_munmap() for maple tree iterator changes Liam R. Howlett
2023-04-25 14:09 ` [PATCH 23/34] maple_tree: Try harder to keep active node after mas_next() Liam R. Howlett
2023-05-04 2:44 ` kernel test robot
2023-04-25 14:09 ` [PATCH 24/34] maple_tree: Try harder to keep active node with mas_prev() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 25/34] maple_tree: Clear up index and last setting in single entry tree Liam R. Howlett
2023-04-27 11:19 ` Peng Zhang
2023-04-27 17:25 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 26/34] maple_tree: Update testing code for mas_{next,prev,walk} Liam R. Howlett
2023-05-04 3:33 ` Peng Zhang [this message]
2023-05-04 18:50 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface Liam R. Howlett
2023-04-26 1:21 ` kernel test robot
2023-04-26 13:16 ` kernel test robot
2023-04-28 6:48 ` Peng Zhang
2023-05-03 19:31 ` Liam R. Howlett
2023-04-28 8:39 ` kernel test robot
2023-04-25 14:09 ` [PATCH 28/34] maple_tree: Revise limit checks in mas_empty_area{_rev}() Liam R. Howlett
2023-04-28 7:06 ` Peng Zhang
2023-04-25 14:09 ` [PATCH 29/34] maple_tree: Introduce mas_prev_slot() interface Liam R. Howlett
2023-04-28 8:27 ` Peng Zhang
2023-05-03 19:29 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 30/34] maple_tree: Fix comments for mas_next_entry() and mas_prev_entry() Liam R. Howlett
2023-04-25 14:09 ` [PATCH 31/34] maple_tree: Add mas_next_range() and mas_find_range() interfaces Liam R. Howlett
2023-04-25 14:09 ` [PATCH 32/34] maple_tree: Add mas_prev_range() and mas_find_range_rev interface Liam R. Howlett
2023-04-25 14:09 ` [PATCH 33/34] maple_tree: Add testing for mas_{prev,next}_range() Liam R. Howlett
2023-04-26 1:41 ` kernel test robot
2023-05-05 17:11 ` Liam R. Howlett
2023-04-25 14:09 ` [PATCH 34/34] mm: Add vma_iter_{next,prev}_range() to vma iterator 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=915edff9-1753-2a0b-327f-ba11e6c5a7b1@bytedance.com \
--to=zhangpeng.00@bytedance.com \
--cc=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 \
/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