From c6fbcba17a6c0cbb1a59f1af36926e7e4933833e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 13 Dec 2019 16:13:55 -0500 Subject: [PATCH] maple_tree: Fix empty pivot when appending to a perfect fit. When appending data to the end of a node which fits perfectly in the range, it may be that the pivot is 0 but the implied pivot is mas->max. This would result in a walk operation not finding the value. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 2 + lib/test_maple_tree.c | 138 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 139 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a0b62b76082c..484d123e532a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2052,6 +2052,8 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, if (mas->index == min && mas->last == max) { mte_set_rcu_slot(mas->node, slot, entry); + if (slot < slot_cnt) + mte_set_pivot(mas->node, slot, mas->last); ret = 1; goto complete; } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 592624439b58..7b59c4b71c96 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1016,7 +1016,139 @@ STORE, 47646523273216, 47646523277312, STORE, 47646523277312, 47646523445248, ERASE, 47646523277312, 47646523445248, STORE, 47646523277312, 47646523400192, + }; + unsigned long set5[] = { +STORE, 140737488347136, 140737488351232, +STORE, 140726874062848, 140737488351232, +ERASE, 140726874062848, 140737488351232, +STORE, 140726874062848, 140726874066944, +STORE, 94248892870656, 94248893042688, +ERASE, 94248892870656, 94248893042688, +STORE, 94248892870656, 94248892887040, +STORE, 94248892887040, 94248893042688, +ERASE, 94248892887040, 94248893042688, +STORE, 94248892887040, 94248892989440, +STORE, 94248892989440, 94248893030400, +STORE, 94248893030400, 94248893042688, +STORE, 47884786266112, 47884786438144, +ERASE, 47884786266112, 47884786438144, +STORE, 47884786266112, 47884786270208, +STORE, 47884786270208, 47884786438144, +ERASE, 47884786270208, 47884786438144, +STORE, 47884786270208, 47884786393088, +STORE, 47884786393088, 47884786425856, +STORE, 47884786425856, 47884786434048, +STORE, 47884786434048, 47884786438144, +STORE, 140726874513408, 140726874517504, +STORE, 140726874501120, 140726874513408, +STORE, 47884786438144, 47884786446336, +STORE, 47884786446336, 47884786454528, +STORE, 47884786454528, 47884786618368, +ERASE, 47884786454528, 47884786618368, +STORE, 47884786454528, 47884786466816, +STORE, 47884786466816, 47884786618368, +STORE, 47884786565120, 47884786618368, +STORE, 47884786466816, 47884786565120, +ERASE, 47884786466816, 47884786565120, +STORE, 47884786466816, 47884786565120, +STORE, 47884786610176, 47884786618368, +STORE, 47884786565120, 47884786610176, +ERASE, 47884786565120, 47884786610176, +STORE, 47884786565120, 47884786618368, +ERASE, 47884786565120, 47884786618368, +STORE, 47884786565120, 47884786610176, +STORE, 47884786610176, 47884786618368, +ERASE, 47884786610176, 47884786618368, +STORE, 47884786610176, 47884786618368, +STORE, 47884786618368, 47884789669888, +STORE, 47884787163136, 47884789669888, +STORE, 47884786618368, 47884787163136, +ERASE, 47884787163136, 47884789669888, +STORE, 47884787163136, 47884789448704, +STORE, 47884789448704, 47884789669888, +STORE, 47884788858880, 47884789448704, +STORE, 47884787163136, 47884788858880, +ERASE, 47884787163136, 47884788858880, +STORE, 47884787163136, 47884788858880, +STORE, 47884789444608, 47884789448704, +STORE, 47884788858880, 47884789444608, +ERASE, 47884788858880, 47884789444608, +STORE, 47884788858880, 47884789444608, +STORE, 47884789653504, 47884789669888, +STORE, 47884789448704, 47884789653504, +ERASE, 47884789448704, 47884789653504, +STORE, 47884789448704, 47884789653504, +ERASE, 47884789653504, 47884789669888, +STORE, 47884789653504, 47884789669888, +STORE, 47884789669888, 47884791508992, +STORE, 47884789809152, 47884791508992, +STORE, 47884789669888, 47884789809152, +ERASE, 47884789809152, 47884791508992, +STORE, 47884789809152, 47884791468032, +STORE, 47884791468032, 47884791508992, +STORE, 47884791152640, 47884791468032, +STORE, 47884789809152, 47884791152640, +ERASE, 47884789809152, 47884791152640, +STORE, 47884789809152, 47884791152640, +STORE, 47884791463936, 47884791468032, +STORE, 47884791152640, 47884791463936, +ERASE, 47884791152640, 47884791463936, +STORE, 47884791152640, 47884791463936, +STORE, 47884791492608, 47884791508992, +STORE, 47884791468032, 47884791492608, +ERASE, 47884791468032, 47884791492608, +STORE, 47884791468032, 47884791492608, +ERASE, 47884791492608, 47884791508992, +STORE, 47884791492608, 47884791508992, +STORE, 47884791508992, 47884791644160, +ERASE, 47884791508992, 47884791644160, +STORE, 47884791508992, 47884791533568, +STORE, 47884791533568, 47884791644160, +STORE, 47884791595008, 47884791644160, +STORE, 47884791533568, 47884791595008, +ERASE, 47884791533568, 47884791595008, +STORE, 47884791533568, 47884791595008, +STORE, 47884791619584, 47884791644160, +STORE, 47884791595008, 47884791619584, +ERASE, 47884791595008, 47884791619584, +STORE, 47884791595008, 47884791644160, +ERASE, 47884791595008, 47884791644160, +STORE, 47884791595008, 47884791619584, +STORE, 47884791619584, 47884791644160, +STORE, 47884791627776, 47884791644160, +STORE, 47884791619584, 47884791627776, +ERASE, 47884791619584, 47884791627776, +STORE, 47884791619584, 47884791627776, +ERASE, 47884791627776, 47884791644160, +STORE, 47884791627776, 47884791644160, +STORE, 47884791644160, 47884791664640, +ERASE, 47884791644160, 47884791664640, +STORE, 47884791644160, 47884791648256, +STORE, 47884791648256, 47884791664640, +STORE, 47884791652352, 47884791664640, +STORE, 47884791648256, 47884791652352, +ERASE, 47884791648256, 47884791652352, +STORE, 47884791648256, 47884791652352, +STORE, 47884791656448, 47884791664640, +STORE, 47884791652352, 47884791656448, +ERASE, 47884791652352, 47884791656448, +STORE, 47884791652352, 47884791664640, +ERASE, 47884791652352, 47884791664640, +STORE, 47884791652352, 47884791656448, +STORE, 47884791656448, 47884791664640, +ERASE, 47884791656448, 47884791664640, +STORE, 47884791656448, 47884791664640, +STORE, 47884791664640, 47884791672832, +ERASE, 47884791468032, 47884791492608, +STORE, 47884791468032, 47884791484416, +STORE, 47884791484416, 47884791492608, +ERASE, 47884791656448, 47884791664640, +STORE, 47884791656448, 47884791660544, +STORE, 47884791660544, 47884791664640, +ERASE, 47884791619584, 47884791627776, +STORE, 47884791619584, 47884791623680, +STORE, 47884791623680, 47884791627776, }; @@ -1043,8 +1175,12 @@ STORE, 47646523277312, 47646523400192, if (mas_retry(&mas, entry)) continue; } - rcu_read_unlock(); mtree_destroy(mt); + + mtree_init(mt, 0); + check_erase2_testset(mt, set5, ARRAY_SIZE(set5)); + mtree_destroy(mt); + rcu_read_unlock(); } static noinline void check_alloc_rev_range(struct maple_tree *mt) { -- 2.50.1