From ea34c334b0485fd04ce9d753d2f44af97ae187fc Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 25 Feb 2020 11:18:51 -0500 Subject: [PATCH] maple_tree: Fix off by one on mas_prev when going to previous node. mas_prev_nentry decrements the slot prior to checking for an entry, so don't decrement the slot in mas_prev loop on new nodes. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 2 +- lib/test_maple_tree.c | 12 ++++++++++-- 2 files changed, 11 insertions(+), 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a58caac4defa..12838071355a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3207,7 +3207,7 @@ static inline void* _mas_prev(struct ma_state *mas, unsigned long limit) break; mas_prev_node(mas, limit); - mas_set_slot(mas, mt_slot_count(mas->node) - 1); + mas_set_slot(mas, mt_slot_count(mas->node)); } if (mas_is_none(mas)) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0477191b93c5..7e86303c403f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -11671,10 +11671,18 @@ static noinline void check_next_entry(struct maple_tree *mt) static noinline void check_prev_entry(struct maple_tree *mt) { - MT_BUG_ON(mt, !mtree_empty(mt)); + unsigned long index = 16; + void *value; + MA_STATE(mas, mt, index, index); + MT_BUG_ON(mt, !mtree_empty(mt)); check_seq(mt, 30, false); + rcu_read_lock(); + value = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, value != xa_mk_value(index)); + value = mas_prev(&mas, 0); + MT_BUG_ON(mt, value != xa_mk_value(index - 1)); rcu_read_unlock(); mtree_destroy(mt); @@ -11834,7 +11842,7 @@ static int maple_tree_seed(void) mtree_destroy(&tree); - mtree_init(&tree, 0); + mtree_init(&tree, MAPLE_ALLOC_RANGE); check_prev_entry(&tree); mtree_init(&tree, 0); -- 2.50.1