Add a test case for the rcu reader being restarted by emptying the tree. Signed-off-by: Liam R. Howlett (Google) --- lib/test_maple_tree.c | 129 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index fb40e193a3cb7..894f5893e1be2 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3740,6 +3740,134 @@ static noinline void __init check_range64_in_rcu(struct maple_tree *mt) rcu_barrier(); } +/* + * A reader that restarts after its leaf died may find a tree without nodes: + * emptied, or emptied and then given a single entry at 0. Each case starts + * from a tree with nodes, built by check_seq(). The stores run while the + * reader holds rcu_read_lock, so they use GFP_ATOMIC. + */ +static noinline void __init check_restart_no_node(struct maple_tree *mt) +{ + void *ptr = xa_mk_value(1234); + void *entry; + MA_STATE(mas, mt, 0, 0); + + MT_BUG_ON(mt, !mtree_empty(mt)); + mt_set_non_kernel(99999); + + /* find: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* next: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_next(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 1); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* prev: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_prev(&mas, 0); + MT_BUG_ON(mt, entry != ptr); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the entry at 0 is below the minimum */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + mt_set_non_kernel(0); +} + static DEFINE_MTREE(tree); static int __init maple_tree_seed(void) { @@ -4031,6 +4159,7 @@ static int __init maple_tree_seed(void) check_range64_in_rcu(&tree); + check_restart_no_node(&tree); #if defined(BENCH) skip: -- 2.47.3