From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Peng Zhang <zhangpeng.00@bytedance.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 14:50:23 -0400 [thread overview]
Message-ID: <20230504185023.4osqa3spndsawvl4@revolver> (raw)
In-Reply-To: <915edff9-1753-2a0b-327f-ba11e6c5a7b1@bytedance.com>
* Peng Zhang <zhangpeng.00@bytedance.com> [230503 23:33]:
>
>
> 在 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?
Yes, thank you.
> > + * └─ 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 18:51 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
2023-05-04 18:50 ` Liam R. Howlett [this message]
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=20230504185023.4osqa3spndsawvl4@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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.