From 8225bb0a62b193d35d00b54375b3b342d1255d5b Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 14 Feb 2020 11:36:50 -0500 Subject: [PATCH] maple_tree: Fix mas_rev_awalk to check if the entry is empty. When checking of an entry is empty, ensure delete is considered empty. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 6 ++--- lib/test_maple_tree.c | 55 ++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 55 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index afc3d9673ae2..7b9a5e0de0ae 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3589,7 +3589,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) /* check if this slot is full */ entry = _mte_get_rcu_slot(mas->node, i, type); - if (entry) + if (entry && !mt_is_deleted(entry)) goto next_slot; this_gap = max - min + 1; @@ -3665,12 +3665,12 @@ next: next = _mte_get_rcu_slot(mas->node, i, type); mas->min = min; mas->max = max; - if (next) { + if (!mt_is_empty(next)) { mas->node = next; i = mas_data_end(mas, mte_node_type(next), &max, &coalesce); } else { - found = true; // this is a non-leaf hole. + goto ascend; } } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 22cdcb771e28..7700a317d2c7 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -899,8 +899,8 @@ static noinline void check_erase2_testset(struct maple_tree *mt, set[i+1], set[i+2]-1); #endif - s_entry = mas_range_load(&mas_start, &s_min, &s_max); - e_entry = mas_range_load(&mas_end, &e_min, &e_max); + s_entry = mas_range_load(&mas_start, &s_min, &s_max, false); + e_entry = mas_range_load(&mas_end, &e_min, &e_max, false); switch(set[i]) { case STORE: @@ -9392,6 +9392,35 @@ STORE, 140732658565120, 140732658569215, STORE, 140732658552832, 140732658565119, }; + unsigned long set12[] = { // contains 12 values. +STORE, 140737488347136, 140737488351231, +STORE, 140732658499584, 140737488351231, +ERASE, 140732658499584, 140732658499584, +STORE, 140732658499584, 140732658503679, +STORE, 94029856579584, 94029856751615, +ERASE, 94029856579584, 94029856579584, +STORE, 94029856579584, 94029856595967, +STORE, 94029856595968, 94029856751615, +ERASE, 94029856595968, 94029856595968, +STORE, 94029856595968, 94029856698367, +STORE, 94029856698368, 94029856739327, +STORE, 94029856739328, 94029856751615, +STORE, 140014592573440, 140014592745471, +ERASE, 140014592573440, 140014592573440, +STORE, 140014592573440, 140014592577535, +STORE, 140014592577536, 140014592745471, +ERASE, 140014592577536, 140014592577536, +STORE, 140014592577536, 140014592700415, +STORE, 140014592700416, 140014592733183, +STORE, 140014592733184, 140014592741375, +STORE, 140014592741376, 140014592745471, +STORE, 140732658565120, 140732658569215, +STORE, 140732658552832, 140732658565119, +STORE, 140014592741375, 140014592741375, // contrived +STORE, 140014592733184, 140014592741376, // creates first entry retry. + }; + + int cnt = 0; mt_set_non_kernel(3); check_erase2_testset(mt, set, ARRAY_SIZE(set)); @@ -9458,6 +9487,26 @@ STORE, 140732658552832, 140732658565119, mas_get_unmapped_area_rev(&mas, 12288, 140014592737280, 0x2000); MT_BUG_ON(mt, mas.index != 140014592565248); mtree_destroy(mt); + + mas_reset(&mas); + mas.tree = mt; + cnt = 0; + mas.index = 0; + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set12, ARRAY_SIZE(set12)); + rcu_barrier(); + mt_dump(mt); + mas_for_each(&mas, entry, ULONG_MAX) { + if (mas_retry(&mas, entry)) { + printk("retry\n\n\n"); + continue; + } + BUG_ON(cnt > 12); + cnt++; + printk("%d %lu-%lu %p\n", cnt, mas.index, mas.last, entry); + } + exit(0); + mtree_destroy(mt); } static noinline void check_alloc_rev_range(struct maple_tree *mt) @@ -9931,7 +9980,6 @@ static int maple_tree_seed(void) /* Clear out the tree */ mtree_destroy(&tree); - mtree_init(&tree, 0); check_erase_testset(&tree); mtree_destroy(&tree); @@ -10007,6 +10055,7 @@ static int maple_tree_seed(void) mtree_init(&tree, 0); check_prev_entry(&tree); + mtree_init(&tree, 0); check_erase2_sets(&tree); mtree_destroy(&tree); -- 2.50.1