[PATCH 33/34] maple_tree: Add testing for mas_{prev,next}_range()
From: Liam R. Howlett
Date: Tue Apr 25 2023 - 12:30:21 EST
Add the testing for the new functions to iterate per range.
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
---
lib/test_maple_tree.c | 148 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 148 insertions(+)
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 7b2d19ad5934d..adbf59542951b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3356,6 +3356,150 @@ static noinline void __init check_state_handling(struct maple_tree *mt)
mas_unlock(&mas);
}
+static noinline void __init check_slot_iterators(struct maple_tree *mt)
+{
+ MA_STATE(mas, mt, 0, 0);
+ unsigned long i, index = 40;
+ unsigned char offset = 0;
+ void *test;
+
+ mt_set_non_kernel(99999);
+
+ mas_lock(&mas);
+ for (i = 0; i <= index; i++) {
+ unsigned long end = 5;
+ if (i > 20 && i < 35)
+ end = 9;
+ mas_set_range(&mas, i*10, i*10 + end);
+ mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
+ }
+
+ i = 21;
+ mas_set(&mas, i*10);
+ MAS_BUG_ON(&mas, mas_walk(&mas) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas_prev_range(&mas, 0) != NULL);
+ MAS_BUG_ON(&mas, mas.index != 206);
+ MAS_BUG_ON(&mas, mas.last != 209);
+
+ i--;
+ MAS_BUG_ON(&mas, mas_prev_range(&mas, 0) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.index != 200);
+ MAS_BUG_ON(&mas, mas.last != 205);
+
+ i = 25;
+ mas_set(&mas, i*10);
+ MAS_BUG_ON(&mas, mas_walk(&mas) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.offset != 0);
+
+ /* Previous range is in another node */
+ i--;
+ MAS_BUG_ON(&mas, mas_prev_range(&mas, 0) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.index != 240);
+ MAS_BUG_ON(&mas, mas.last != 249);
+
+ /* Shift back with mas_next */
+ i++;
+ MAS_BUG_ON(&mas, mas_next_range(&mas, ULONG_MAX) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.index != 250);
+ MAS_BUG_ON(&mas, mas.last != 259);
+
+ i = 33;
+ mas_set(&mas, i*10);
+ MAS_BUG_ON(&mas, mas_walk(&mas) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.index != 330);
+ MAS_BUG_ON(&mas, mas.last != 339);
+
+ /* Next range is in another node */
+ i++;
+ MAS_BUG_ON(&mas, mas_next_range(&mas, ULONG_MAX) != xa_mk_value(i));
+ MAS_BUG_ON(&mas, mas.offset != 0);
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+
+ /* Next out of range */
+ i++;
+ MAS_BUG_ON(&mas, mas_next_range(&mas, i*10 - 1) != NULL);
+ /* maple state does not move */
+ MAS_BUG_ON(&mas, mas.offset != 0);
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+
+ /* Prev out of range */
+ i--;
+ MAS_BUG_ON(&mas, mas_prev_range(&mas, i*10 + 1) != NULL);
+ /* maple state does not move */
+ MAS_BUG_ON(&mas, mas.offset != 0);
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+
+ mas_set(&mas, 210);
+ for (i = 210; i<= 350; i += 10) {
+ void *entry = mas_find_range(&mas, ULONG_MAX);
+
+ MAS_BUG_ON(&mas, entry != xa_mk_value(i/10));
+ }
+
+ mas_set(&mas, 0);
+ mas_contiguous(&mas, test, ULONG_MAX) {
+ MAS_BUG_ON(&mas, test != xa_mk_value(0));
+ MAS_BUG_ON(&mas, mas.index != 0);
+ MAS_BUG_ON(&mas, mas.last != 5);
+ }
+ MAS_BUG_ON(&mas, test != NULL);
+ MAS_BUG_ON(&mas, mas.index != 6);
+ MAS_BUG_ON(&mas, mas.last != 9);
+
+ mas_set(&mas, 6);
+ mas_contiguous(&mas, test, ULONG_MAX) {
+ MAS_BUG_ON(&mas, test != xa_mk_value(1));
+ MAS_BUG_ON(&mas, mas.index != 10);
+ MAS_BUG_ON(&mas, mas.last != 15);
+ }
+ MAS_BUG_ON(&mas, test != NULL);
+ MAS_BUG_ON(&mas, mas.index != 16);
+ MAS_BUG_ON(&mas, mas.last != 19);
+
+ i = 210;
+ mas_set(&mas, i);
+ mas_contiguous(&mas, test, 340) {
+ MAS_BUG_ON(&mas, test != xa_mk_value(i/10));
+ MAS_BUG_ON(&mas, mas.index != i);
+ MAS_BUG_ON(&mas, mas.last != i+9);
+ i+=10;
+ offset = mas.offset;
+ }
+ /* Hit the limit, iterator is at the limit. */
+ MAS_BUG_ON(&mas, offset != mas.offset);
+ MAS_BUG_ON(&mas, test != NULL);
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+ test = mas_find_range(&mas, ULONG_MAX);
+ MAS_BUG_ON(&mas, test != xa_mk_value(35));
+ MAS_BUG_ON(&mas, mas.index != 350);
+ MAS_BUG_ON(&mas, mas.last != 355);
+
+
+ test = mas_find_range_rev(&mas, 0);
+ MAS_BUG_ON(&mas, test != xa_mk_value(34));
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+ mas_set(&mas, 345);
+ test = mas_find_range_rev(&mas, 0);
+ MAS_BUG_ON(&mas, test != xa_mk_value(34));
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+
+ offset = mas.offset;
+ test = mas_find_range_rev(&mas, 340);
+ MAS_BUG_ON(&mas, offset != mas.offset);
+ MAS_BUG_ON(&mas, test != NULL);
+ MAS_BUG_ON(&mas, mas.index != 340);
+ MAS_BUG_ON(&mas, mas.last != 349);
+
+ mas_unlock(&mas);
+ mt_set_non_kernel(0);
+}
+
static DEFINE_MTREE(tree);
static int __init maple_tree_seed(void)
{
@@ -3621,6 +3765,10 @@ static int __init maple_tree_seed(void)
check_state_handling(&tree);
mtree_destroy(&tree);
+ mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+ check_slot_iterators(&tree);
+ mtree_destroy(&tree);
+
#if defined(BENCH)
skip:
#endif
--
2.39.2