summaryrefslogtreecommitdiff
path: root/tools/testing/radix-tree/maple.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/testing/radix-tree/maple.c')
-rw-r--r--tools/testing/radix-tree/maple.c314
1 files changed, 302 insertions, 12 deletions
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 5c1b18e3ed21..d967e76a3c06 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -2,7 +2,7 @@
/*
* maple_tree.c: Userspace testing for maple tree test-suite
* Copyright (c) 2018-2022 Oracle Corporation
- * Author: Liam R. Howlett <Liam.Howlett@Oracle.com>
+ * Author: Liam R. Howlett <liam@infradead.org>
*
* Any tests that require internal knowledge of the tree or threads and other
* difficult to handle in kernel tests.
@@ -38,6 +38,7 @@ struct rcu_test_struct2 {
unsigned long index[RCU_RANGE_COUNT];
unsigned long last[RCU_RANGE_COUNT];
+ pthread_mutex_t dump;
};
struct rcu_test_struct3 {
@@ -33997,8 +33998,25 @@ static void *rcu_reader_fwd(void *ptr)
}
}
- RCU_MT_BUG_ON(test, mas.index != r_start);
- RCU_MT_BUG_ON(test, mas.last != r_end);
+ if (mas.index != r_start) {
+ if (pthread_mutex_trylock(&test->dump) != 0) {
+ rcu_read_unlock();
+ goto quit;
+ }
+ printk("start is wrong: %lx (%lu) vs expected %lx (%lu)\n",
+ mas.index, mas.index, r_start, r_start);
+ RCU_MT_BUG_ON(test, mas.index != r_start);
+ }
+
+ if (mas.last != r_end) {
+ if (pthread_mutex_trylock(&test->dump) != 0) {
+ rcu_read_unlock();
+ goto quit;
+ }
+ printk("last is wrong: %lx (%lu) vs expected %lx (%lu)\n",
+ mas.last, mas.last, r_end, r_end);
+ RCU_MT_BUG_ON(test, mas.last != r_end);
+ }
if (i == reader->flip) {
alt = xa_mk_value(index + i + RCU_RANGE_COUNT);
@@ -34014,7 +34032,8 @@ static void *rcu_reader_fwd(void *ptr)
else if (entry == alt)
toggled = true;
else {
- printk("!!%lu-%lu -> %p not %p or %p\n", mas.index, mas.last, entry, expected, alt);
+ printk("!!%lu-%lu -> %p not %p or %p\n",
+ mas.index, mas.last, entry, expected, alt);
RCU_MT_BUG_ON(test, 1);
}
@@ -34047,9 +34066,11 @@ static void *rcu_reader_fwd(void *ptr)
usleep(test->pause);
}
+quit:
rcu_unregister_thread();
return NULL;
}
+
/* RCU reader in decreasing index */
static void *rcu_reader_rev(void *ptr)
{
@@ -34119,13 +34140,17 @@ static void *rcu_reader_rev(void *ptr)
line = __LINE__;
if (mas.index != r_start) {
+ if (pthread_mutex_trylock(&test->dump) != 0) {
+ rcu_read_unlock();
+ goto quit;
+ }
+
alt = xa_mk_value(index + i * 2 + 1 +
RCU_RANGE_COUNT);
mt_dump(test->mt, mt_dump_dec);
- printk("Error: %lu-%lu %p != %lu-%lu %p %p line %d i %d\n",
- mas.index, mas.last, entry,
- r_start, r_end, expected, alt,
- line, i);
+ printk("Error: %p %lu-%lu %p != %lu-%lu %p %p line %d i %d\n",
+ mas.node, mas.index, mas.last, entry,
+ r_start, r_end, expected, alt, line, i);
}
RCU_MT_BUG_ON(test, mas.index != r_start);
RCU_MT_BUG_ON(test, mas.last != r_end);
@@ -34180,6 +34205,7 @@ static void *rcu_reader_rev(void *ptr)
usleep(test->pause);
}
+quit:
rcu_unregister_thread();
return NULL;
}
@@ -34329,6 +34355,7 @@ static void rcu_stress(struct maple_tree *mt, bool forward)
test.seen_modified = 0;
test.thread_count = 0;
test.start = test.stop = false;
+ pthread_mutex_init(&test.dump, NULL);
seed = time(NULL);
srand(seed);
for (i = 0; i < RCU_RANGE_COUNT; i++) {
@@ -34414,6 +34441,7 @@ struct rcu_test_struct {
unsigned long removed; /* The index of the removed entry */
unsigned long added; /* The index of the removed entry */
unsigned long toggle; /* The index of the removed entry */
+ pthread_mutex_t dump;
};
static inline
@@ -34506,7 +34534,9 @@ static void *rcu_loop(void *ptr)
/* Out of the interesting range */
if (mas.index < test->index || mas.index > test->last) {
if (entry != expected) {
- printk("%lx - %lx = %p not %p\n",
+ if (pthread_mutex_trylock(&test->dump) != 0)
+ break;
+ printk("\nERROR: %lx - %lx = %p not %p\n",
mas.index, mas.last, entry, expected);
}
MT_BUG_ON(test->mt, entry != expected);
@@ -34854,6 +34884,7 @@ static noinline void __init check_rcu_threaded(struct maple_tree *mt)
vals.range_end = ULONG_MAX;
vals.seen_entry2 = 0;
vals.seen_entry3 = 0;
+ pthread_mutex_init(&vals.dump, NULL);
run_check_rcu(mt, &vals);
mtree_destroy(mt);
@@ -35203,7 +35234,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
mt_set_non_kernel(1);
/* Spanning store */
mas_set_range(&mas, 1, 100);
- MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
+ MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) == 0);
allocated = mas_allocated(&mas);
height = mas_mt_height(&mas);
MT_BUG_ON(mt, allocated != 0);
@@ -35226,7 +35257,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
MT_BUG_ON(mt, mas_allocated(&mas) != 0);
mas_set_range(&mas, 0, 200);
mt_set_non_kernel(1);
- MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
+ MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) == 0);
allocated = mas_allocated(&mas);
height = mas_mt_height(&mas);
MT_BUG_ON(mt, allocated != 0);
@@ -35250,6 +35281,8 @@ static noinline void __init check_spanning_write(struct maple_tree *mt)
{
unsigned long i, max = 5000;
MA_STATE(mas, mt, 1200, 2380);
+ struct maple_enode *enode;
+ struct maple_node *pnode;
for (i = 0; i <= max; i++)
mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
@@ -35373,7 +35406,18 @@ static noinline void __init check_spanning_write(struct maple_tree *mt)
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
for (i = 0; i <= max; i++)
mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
+
mtree_lock(mt);
+ if (MAPLE_32BIT) {
+ i = 47811;
+ do {
+ mas_set(&mas, i);
+ mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
+ i++;
+ mas_ascend(&mas);
+ } while (mas_data_end(&mas) < mt_slot_count(mas.node) - 1);
+ }
+
mas_set(&mas, 47606);
mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
mas_set(&mas, 47607);
@@ -35410,6 +35454,128 @@ static noinline void __init check_spanning_write(struct maple_tree *mt)
mas_set_range(&mas, 76, 875);
mas_store_gfp(&mas, NULL, GFP_KERNEL);
mtree_unlock(mt);
+ mtree_destroy(mt);
+
+ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+ for (i = 0; i <= max; i++)
+ mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
+
+ if (MAPLE_32BIT)
+ i = 49750; /* 0xC25B */
+ else
+ i = 49835; /* 0xC2AB */
+
+ mtree_lock(mt);
+ /* Store a null across a boundary that ends in a null */
+ mas_set(&mas, i); /* 0xC2AB */
+ MT_BUG_ON(mt, mas_walk(&mas) == NULL);
+ MT_BUG_ON(mt, mas.end != mas.offset);
+ MT_BUG_ON(mt, mas_next_range(&mas, ULONG_MAX) != NULL);
+ mas_set_range(&mas, i, mas.last - 1);
+ mas_store_gfp(&mas, NULL, GFP_KERNEL);
+ mt_validate(mt);
+
+ /* Store a null across a boundary that starts and ends in a null */
+ mas_set(&mas, 49849);
+ MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+ MT_BUG_ON(mt, mas.index != 49846);
+ mas_set(&mas, 49876);
+ MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+ MT_BUG_ON(mt, mas.last != 49879);
+ mas_set_range(&mas, 49849, 49876);
+ mas_store_gfp(&mas, NULL, GFP_KERNEL);
+ /* Results in 49846-49879: (nil) */
+ MT_BUG_ON(mt, mas.index != 49846);
+ MT_BUG_ON(mt, mas.last != 49879);
+ mt_validate(mt);
+
+ /* Store a null across a boundary that starts and ends next to nulls */
+ mas_set(&mas, 49800);
+ MT_BUG_ON(mt, mas_walk(&mas) == NULL);
+ MT_BUG_ON(mt, mas.index != 49800);
+ mas_set(&mas, 49815);
+ MT_BUG_ON(mt, mas_walk(&mas) == NULL);
+ MT_BUG_ON(mt, mas.last != 49815);
+ mas_set_range(&mas, 49800, 49815);
+ mas_store_gfp(&mas, NULL, GFP_KERNEL);
+ /* Results in 49846-49879: (nil) */
+ MT_BUG_ON(mt, mas.index != 49796);
+ MT_BUG_ON(mt, mas.last != 49819);
+ mt_validate(mt);
+
+ /* Store a value across a boundary that starts and ends in a null */
+ mas_set(&mas, 49907);
+ MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+ MT_BUG_ON(mt, mas.index != 49906);
+ mas_set(&mas, 49928);
+ MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+ MT_BUG_ON(mt, mas.last != 49929);
+ mas_set_range(&mas, 49907, 49928);
+ mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
+ MT_BUG_ON(mt, mas.index != 49907);
+ MT_BUG_ON(mt, mas.last != 49928);
+ mt_validate(mt);
+
+ /* Store a value across a node boundary that causes a 3 way split */
+
+ if (MAPLE_32BIT)
+ i = 49430; /* 0xc116 */
+ else
+ i = 49670; /* 0xC206 */
+
+ mas_set(&mas, i);
+ MT_BUG_ON(mt, mas_walk(&mas) == NULL);
+ MT_BUG_ON(mt, mas.index != i);
+ MT_BUG_ON(mt, mas.end != mt_slot_count(mas.node) - 1);
+ enode = mas.node;
+ MT_BUG_ON(mt, mas_next_range(&mas, ULONG_MAX) != NULL);
+ MT_BUG_ON(mt, mas.index != i + 6);
+ MT_BUG_ON(mt, mas.end != mt_slot_count(mas.node) - 1);
+ MT_BUG_ON(mt, enode == mas.node);
+ mas_set_range(&mas, i + 2, i + 7);
+ mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
+ MT_BUG_ON(mt, mas.index != i + 2);
+ MT_BUG_ON(mt, mas.last != i + 7);
+ mt_validate(mt);
+
+ /* 2 levels of basically the same testing */
+
+ if (MAPLE_32BIT) {
+ /* 32bit needs a bit more work to fill the nodes.
+ * The two parent nodes need to be filled (they have one space
+ * vacant) without causing a split at the store locations (or
+ * the siblings).
+ */
+ i = 44426;
+ mas_set(&mas, i);
+ mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
+ i = 45126;
+ mas_set(&mas, i);
+ mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
+ i = 44790;
+ } else {
+ /* 48950 - 48955 => ptr, 48956 - 48959 => NULL */
+ i = 48950;
+
+ }
+ mas_set(&mas, i);
+ MT_BUG_ON(mt, mas_walk(&mas) == NULL);
+ MT_BUG_ON(mt, mas.index != i);
+ MT_BUG_ON(mt, mas.end != mt_slot_count(mas.node) - 1);
+ enode = mas.node;
+ pnode = mte_parent(enode);
+ MT_BUG_ON(mt, mas_next_range(&mas, ULONG_MAX) != NULL);
+ MT_BUG_ON(mt, mas.index != i + 6);
+ MT_BUG_ON(mt, mas.end != mt_slot_count(mas.node) - 1);
+ MT_BUG_ON(mt, enode == mas.node);
+ MT_BUG_ON(mt, pnode == mte_parent(mas.node));
+ mas_set_range(&mas, i + 2, i + 8);
+ mas_store_gfp(&mas, NULL, GFP_KERNEL);
+ mt_validate(mt);
+
+ mtree_unlock(mt);
+ mtree_destroy(mt);
+ rcu_barrier();
}
/* End of spanning write testing */
@@ -35733,6 +35899,127 @@ unlock:
return ret;
}
+static noinline void __init check_erase_rebalance(struct maple_tree *mt)
+{
+ unsigned long val;
+ void *enode;
+ int ret;
+
+ MA_STATE(mas, mt, 0, 0);
+
+ /*
+ * During removal of big node, the rebalance started going too high,
+ * which resulted in too many nodes trying to be used.
+ *
+ * Create a rebalance which results in an exactly full parent (0-9) that
+ * does not need to be rebalanced. This required two full levels,
+ * followed by an insufficient level which will be rebalanced into two
+ * nodes, finally leaves that need to be rebalanced into one node.
+ *
+ * The bugs tree:
+ * root 4 Label R
+ * /\ /\
+ * 9 X F
+ * /\ /\ /
+ * 9 X E
+ * /\ /\ /\
+ * 4 8 C D
+ * /\ /\
+ * 6 9 A B
+ * ^ becomes 5 with the write.
+ *
+ * Below, the reconstruction leaves the root with 2 entries, the setup
+ * uses the letter labels above.
+ */
+
+ ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, 4);
+ MT_BUG_ON(mt, ret);
+
+ /* Cheap expansion to 5 levels */
+ mtree_store(mt, ULONG_MAX, xa_mk_value(0), GFP_KERNEL);
+ /* rcu is used to ensure node use */
+ mt_set_in_rcu(mt);
+ mas_lock(&mas);
+
+ /* Node A had 6 entries */
+ mas_walk(&mas);
+ MAS_BUG_ON(&mas, mas_data_end(&mas) < 6);
+ while (mas_data_end(&mas) > 6) {
+ mas_erase(&mas);
+ mas_next(&mas, ULONG_MAX);
+ }
+
+ /* Move to Node B */
+ enode = (void*) mas.node;
+ while (mas.node == enode)
+ mas_next(&mas, ULONG_MAX);
+
+ /* Node B had 9 entries */
+ MAS_BUG_ON(&mas, mas_data_end(&mas) < 9);
+ while (mas_data_end(&mas) > 9) {
+ mas_erase(&mas);
+ mas_next(&mas, ULONG_MAX);
+ }
+
+ /* Move to Node C */
+ mas_ascend(&mas);
+ val = mas.max;
+ /* Adjust entries to be 4 */
+ while (mas_data_end(&mas) > 4) {
+ mas_set(&mas, val);
+ mas_erase(&mas);
+ mas_prev(&mas, 0);
+ val = mas.index;
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node D */
+ mas_ascend(&mas);
+ mas.offset = 1;
+ mas_descend(&mas);
+ val = mas.max;
+ /* Adjust entries to be 8 */
+ while (mas_data_end(&mas) < 8) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node E */
+ mas_ascend(&mas);
+ val = mas.max;
+ MAS_BUG_ON(&mas, mas_data_end(&mas) > 9);
+ /* Adjust Node E to 9 entries */
+ while (mas_data_end(&mas) < 9) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ }
+
+ /* Move to Node F */
+ mas_ascend(&mas);
+ val = mas.max;
+ MAS_BUG_ON(&mas, mas_data_end(&mas) > 9);
+ /* Adjust Node F to 9 entries */
+ while (mas_data_end(&mas) < 9) {
+ mas_set(&mas, val--);
+ mas_store_gfp(&mas, &mas, GFP_KERNEL);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ mas_ascend(&mas);
+ }
+
+ /* Test is set up, walk to first entry */
+ mas_set(&mas, 0);
+ mas_next(&mas, ULONG_MAX);
+ /* overwrite the entry to cause a rebalance, which was 1 too few */
+ mas_set_range(&mas, 0, mas.last);
+ mas_preallocate(&mas, NULL, GFP_KERNEL);
+ mas_store_prealloc(&mas, NULL);
+ mas_unlock(&mas);
+}
+
static noinline void __init check_mtree_dup(struct maple_tree *mt)
{
DEFINE_MTREE(new);
@@ -36029,7 +36316,6 @@ static inline int check_vma_modification(struct maple_tree *mt)
return 0;
}
-
void farmer_tests(void)
{
struct maple_node *node;
@@ -36095,6 +36381,10 @@ void farmer_tests(void)
check_mtree_dup(&tree);
mtree_destroy(&tree);
+ mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+ check_erase_rebalance(&tree);
+ mtree_destroy(&tree);
+
/* RCU testing */
mt_init_flags(&tree, 0);
check_erase_testset(&tree);
generated by cgit v1.2.3 (git 2.0.4) at 2026-09-25 01:23:17 +0000