From 6e9a237a6c8d07fa4104893c5f77fff7baf96fc5 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Sun, 15 Dec 2019 20:05:40 -0500 Subject: [PATCH] maple_tree: Fix mas_first_entry return value. This was returning the wrong pivot value which resulted in skipping tree entries in mas_for_each loops. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 7 +- lib/test_maple_tree.c | 151 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 153 insertions(+), 5 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 484d123e532a..5db92449cc2c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1456,11 +1456,8 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, // Get the leaf slot. mas_set_slot(mas, 0); mas_first_node(mas, limit); - if (!mas_get_slot(mas)) - return mas->min; - else - return mas_get_safe_pivot(mas, - mas_get_slot(mas) - 1); + return mas_get_safe_pivot(mas, + mas_get_slot(mas)); } mas_set_slot(mas, 0); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 7b59c4b71c96..49e49b89f455 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -876,6 +876,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, int check = 0; void *foo; unsigned long addr = 0; + MA_STATE(mas, mt, 0, 0); for (int i = 0; i < size; i += 3) { switch(set[i]) { @@ -903,6 +904,19 @@ static noinline void check_erase2_testset(struct maple_tree *mt, } MT_BUG_ON(mt, check != entry_cnt); + + check = 0; + mas_reset(&mas); + mas.index = 0; + mas_for_each(&mas, foo, ULONG_MAX) { + if (mas_retry(&mas, foo)) + continue; + check++; + if (check > entry_cnt) + break; + } + + MT_BUG_ON(mt, check != entry_cnt); } } @@ -1151,6 +1165,138 @@ STORE, 47884791619584, 47884791623680, STORE, 47884791623680, 47884791627776, }; + unsigned long set6[] = { +STORE, 140737488347136, 140737488351232, +STORE, 140722999021568, 140737488351232, +ERASE, 140722999021568, 140737488351232, +STORE, 140722999021568, 140722999025664, +STORE, 94901500268544, 94901500440576, +ERASE, 94901500268544, 94901500440576, +STORE, 94901500268544, 94901500284928, +STORE, 94901500284928, 94901500440576, +ERASE, 94901500284928, 94901500440576, +STORE, 94901500284928, 94901500387328, +STORE, 94901500387328, 94901500428288, +STORE, 94901500428288, 94901500440576, +STORE, 47430426660864, 47430426832896, +ERASE, 47430426660864, 47430426832896, +STORE, 47430426660864, 47430426664960, +STORE, 47430426664960, 47430426832896, +ERASE, 47430426664960, 47430426832896, +STORE, 47430426664960, 47430426787840, +STORE, 47430426787840, 47430426820608, +STORE, 47430426820608, 47430426828800, +STORE, 47430426828800, 47430426832896, +STORE, 140722999115776, 140722999119872, +STORE, 140722999103488, 140722999115776, +STORE, 47430426832896, 47430426841088, +STORE, 47430426841088, 47430426849280, +STORE, 47430426849280, 47430427013120, +ERASE, 47430426849280, 47430427013120, +STORE, 47430426849280, 47430426861568, +STORE, 47430426861568, 47430427013120, +STORE, 47430426959872, 47430427013120, +STORE, 47430426861568, 47430426959872, +ERASE, 47430426861568, 47430426959872, +STORE, 47430426861568, 47430426959872, +STORE, 47430427004928, 47430427013120, +STORE, 47430426959872, 47430427004928, +ERASE, 47430426959872, 47430427004928, +STORE, 47430426959872, 47430427013120, +ERASE, 47430426959872, 47430427013120, +STORE, 47430426959872, 47430427004928, +STORE, 47430427004928, 47430427013120, +ERASE, 47430427004928, 47430427013120, +STORE, 47430427004928, 47430427013120, +STORE, 47430427013120, 47430430064640, +STORE, 47430427557888, 47430430064640, +STORE, 47430427013120, 47430427557888, +ERASE, 47430427557888, 47430430064640, +STORE, 47430427557888, 47430429843456, +STORE, 47430429843456, 47430430064640, +STORE, 47430429253632, 47430429843456, +STORE, 47430427557888, 47430429253632, +ERASE, 47430427557888, 47430429253632, +STORE, 47430427557888, 47430429253632, +STORE, 47430429839360, 47430429843456, +STORE, 47430429253632, 47430429839360, +ERASE, 47430429253632, 47430429839360, +STORE, 47430429253632, 47430429839360, +STORE, 47430430048256, 47430430064640, +STORE, 47430429843456, 47430430048256, +ERASE, 47430429843456, 47430430048256, +STORE, 47430429843456, 47430430048256, +ERASE, 47430430048256, 47430430064640, +STORE, 47430430048256, 47430430064640, +STORE, 47430430064640, 47430431903744, +STORE, 47430430203904, 47430431903744, +STORE, 47430430064640, 47430430203904, +ERASE, 47430430203904, 47430431903744, +STORE, 47430430203904, 47430431862784, +STORE, 47430431862784, 47430431903744, +STORE, 47430431547392, 47430431862784, +STORE, 47430430203904, 47430431547392, +ERASE, 47430430203904, 47430431547392, +STORE, 47430430203904, 47430431547392, +STORE, 47430431858688, 47430431862784, +STORE, 47430431547392, 47430431858688, +ERASE, 47430431547392, 47430431858688, +STORE, 47430431547392, 47430431858688, +STORE, 47430431887360, 47430431903744, +STORE, 47430431862784, 47430431887360, +ERASE, 47430431862784, 47430431887360, +STORE, 47430431862784, 47430431887360, +ERASE, 47430431887360, 47430431903744, +STORE, 47430431887360, 47430431903744, +STORE, 47430431903744, 47430432038912, +ERASE, 47430431903744, 47430432038912, +STORE, 47430431903744, 47430431928320, +STORE, 47430431928320, 47430432038912, +STORE, 47430431989760, 47430432038912, +STORE, 47430431928320, 47430431989760, +ERASE, 47430431928320, 47430431989760, +STORE, 47430431928320, 47430431989760, +STORE, 47430432014336, 47430432038912, +STORE, 47430431989760, 47430432014336, +ERASE, 47430431989760, 47430432014336, +STORE, 47430431989760, 47430432038912, +ERASE, 47430431989760, 47430432038912, +STORE, 47430431989760, 47430432014336, +STORE, 47430432014336, 47430432038912, +STORE, 47430432022528, 47430432038912, +STORE, 47430432014336, 47430432022528, +ERASE, 47430432014336, 47430432022528, +STORE, 47430432014336, 47430432022528, +ERASE, 47430432022528, 47430432038912, +STORE, 47430432022528, 47430432038912, +STORE, 47430432038912, 47430432059392, +ERASE, 47430432038912, 47430432059392, +STORE, 47430432038912, 47430432043008, +STORE, 47430432043008, 47430432059392, +STORE, 47430432047104, 47430432059392, +STORE, 47430432043008, 47430432047104, +ERASE, 47430432043008, 47430432047104, +STORE, 47430432043008, 47430432047104, +STORE, 47430432051200, 47430432059392, +STORE, 47430432047104, 47430432051200, +ERASE, 47430432047104, 47430432051200, +STORE, 47430432047104, 47430432059392, +ERASE, 47430432047104, 47430432059392, +STORE, 47430432047104, 47430432051200, +STORE, 47430432051200, 47430432059392, +ERASE, 47430432051200, 47430432059392, +STORE, 47430432051200, 47430432059392, +STORE, 47430432059392, 47430432067584, +ERASE, 47430431862784, 47430431887360, +STORE, 47430431862784, 47430431879168, +STORE, 47430431879168, 47430431887360, +ERASE, 47430432051200, 47430432059392, +STORE, 47430432051200, 47430432055296, +STORE, 47430432055296, 47430432059392, +ERASE, 47430432014336, 47430432022528, +STORE, 47430432014336, 47430432018432, +STORE, 47430432018432, 47430432022528, + }; mt_set_non_kernel(3); check_erase2_testset(mt, set, ARRAY_SIZE(set)); @@ -1180,6 +1326,11 @@ STORE, 47884791623680, 47884791627776, mtree_init(mt, 0); check_erase2_testset(mt, set5, ARRAY_SIZE(set5)); mtree_destroy(mt); + + mtree_init(mt, 0); + check_erase2_testset(mt, set6, ARRAY_SIZE(set6)); + mtree_destroy(mt); + rcu_read_unlock(); } static noinline void check_alloc_rev_range(struct maple_tree *mt) -- 2.50.1