| Message ID | 20230425140955.3834476-27-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Maple tree mas_{next,prev}_range() and cleanup | expand |
在 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
* 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
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) + * └─ 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
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(-)