From eaa95f615bea0f0624e9da7c52c1753843521691 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 2 Mar 2020 22:21:37 -0500 Subject: [PATCH] maple_tree: Fix overwritten slot in mas during __mas_add Overwriting the slot in the ma state caused issues later on. Restore the value and fix the code in mas_may_move_gap to also detect such scenarios. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 14 ++-- lib/test_maple_tree.c | 179 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 187 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3a2ad10b4e5c..96ccb175711b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1329,6 +1329,7 @@ static inline unsigned char _mas_append(struct ma_state *mas, this_piv = ma_get_pivot(smn, src_end, stype); } + // Not really src_data.. src_data = mas_get_rcu_slot(mas, dst_slot); if (!src_data) { if (!this_piv) @@ -2228,14 +2229,14 @@ static inline void mas_may_move_gap(struct ma_state *mas) if (entry && !xa_is_deleted(entry)) return; - if (curr.node == mas->node) { + if (curr.node == mas->node) mas_next(&next, ULONG_MAX); - if (mas_is_none(&next)) - return; - if (!mt_is_empty(mas_get_rcu_slot(&next, 0))) - return; - } + if (mas_is_none(&next)) + return; + + if (!mt_is_empty(mas_get_rcu_slot(&next, 0))) + return; while (end && (!entry || xa_is_deleted(entry))) entry = mas_get_rcu_slot(&curr, --end); @@ -2713,6 +2714,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, mas_set_slot(mas, slot); __mas_add(mas, entry, old_end, active, append); + mas_set_slot(mas, slot); complete: if (prev_enode != mas->node) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index a9f5ba3b57ac..3b4945c69f9c 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -10601,6 +10601,167 @@ STORE, 140656836775936, 140656836780031, STORE, 140656787476480, 140656791920639, ERASE, 140656774639616, 140656779083775, }; + unsigned long set20[] = { +STORE, 140737488347136, 140737488351231, +STORE, 140735952392192, 140737488351231, +SNULL, 140735952396287, 140737488351231, +STORE, 140735952392192, 140735952396287, +STORE, 140735952261120, 140735952396287, +STORE, 94849008947200, 94849009414143, +SNULL, 94849009364991, 94849009414143, +STORE, 94849008947200, 94849009364991, +STORE, 94849009364992, 94849009414143, +ERASE, 94849009364992, 94849009414143, +STORE, 94849009364992, 94849009414143, +STORE, 140590397943808, 140590400196607, +SNULL, 140590398087167, 140590400196607, +STORE, 140590397943808, 140590398087167, +STORE, 140590398087168, 140590400196607, +ERASE, 140590398087168, 140590400196607, +STORE, 140590400184320, 140590400192511, +STORE, 140590400192512, 140590400196607, +STORE, 140735952850944, 140735952855039, +STORE, 140735952838656, 140735952850943, +STORE, 140590400180224, 140590400184319, +STORE, 140590400172032, 140590400180223, +STORE, 140590395809792, 140590397943807, +SNULL, 140590395809792, 140590395838463, +STORE, 140590395838464, 140590397943807, +STORE, 140590395809792, 140590395838463, +SNULL, 140590397935615, 140590397943807, +STORE, 140590395838464, 140590397935615, +STORE, 140590397935616, 140590397943807, +ERASE, 140590397935616, 140590397943807, +STORE, 140590397935616, 140590397943807, +STORE, 140590393425920, 140590395809791, +SNULL, 140590393425920, 140590393692159, +STORE, 140590393692160, 140590395809791, +STORE, 140590393425920, 140590393692159, +SNULL, 140590395785215, 140590395809791, +STORE, 140590393692160, 140590395785215, +STORE, 140590395785216, 140590395809791, +SNULL, 140590395785216, 140590395805695, +STORE, 140590395805696, 140590395809791, +STORE, 140590395785216, 140590395805695, +ERASE, 140590395785216, 140590395805695, +STORE, 140590395785216, 140590395805695, +ERASE, 140590395805696, 140590395809791, +STORE, 140590395805696, 140590395809791, +STORE, 140590391234560, 140590393425919, +SNULL, 140590391234560, 140590391324671, +STORE, 140590391324672, 140590393425919, +STORE, 140590391234560, 140590391324671, +SNULL, 140590393417727, 140590393425919, +STORE, 140590391324672, 140590393417727, +STORE, 140590393417728, 140590393425919, +ERASE, 140590393417728, 140590393425919, +STORE, 140590393417728, 140590393425919, +STORE, 140590388973568, 140590391234559, +SNULL, 140590388973568, 140590389125119, +STORE, 140590389125120, 140590391234559, +STORE, 140590388973568, 140590389125119, +SNULL, 140590391218175, 140590391234559, +STORE, 140590389125120, 140590391218175, +STORE, 140590391218176, 140590391234559, +SNULL, 140590391218176, 140590391226367, +STORE, 140590391226368, 140590391234559, +STORE, 140590391218176, 140590391226367, +ERASE, 140590391218176, 140590391226367, +STORE, 140590391218176, 140590391226367, +ERASE, 140590391226368, 140590391234559, +STORE, 140590391226368, 140590391234559, +STORE, 140590386843648, 140590388973567, +SNULL, 140590386843648, 140590386872319, +STORE, 140590386872320, 140590388973567, +STORE, 140590386843648, 140590386872319, +SNULL, 140590388965375, 140590388973567, +STORE, 140590386872320, 140590388965375, +STORE, 140590388965376, 140590388973567, +ERASE, 140590388965376, 140590388973567, +STORE, 140590388965376, 140590388973567, +STORE, 140590384627712, 140590386843647, +SNULL, 140590384627712, 140590384726015, +STORE, 140590384726016, 140590386843647, +STORE, 140590384627712, 140590384726015, +SNULL, 140590386819071, 140590386843647, +STORE, 140590384726016, 140590386819071, +STORE, 140590386819072, 140590386843647, +SNULL, 140590386819072, 140590386827263, +STORE, 140590386827264, 140590386843647, +STORE, 140590386819072, 140590386827263, +ERASE, 140590386819072, 140590386827263, +STORE, 140590386819072, 140590386827263, +ERASE, 140590386827264, 140590386843647, +STORE, 140590386827264, 140590386843647, +STORE, 140590400163840, 140590400180223, +STORE, 140590380830720, 140590384627711, +SNULL, 140590380830720, 140590382489599, +STORE, 140590382489600, 140590384627711, +STORE, 140590380830720, 140590382489599, +SNULL, 140590384586751, 140590384627711, +STORE, 140590382489600, 140590384586751, +STORE, 140590384586752, 140590384627711, +SNULL, 140590384586752, 140590384611327, +STORE, 140590384611328, 140590384627711, +STORE, 140590384586752, 140590384611327, +ERASE, 140590384586752, 140590384611327, +STORE, 140590384586752, 140590384611327, +ERASE, 140590384611328, 140590384627711, +STORE, 140590384611328, 140590384627711, +STORE, 140590378713088, 140590380830719, +SNULL, 140590378713088, 140590378729471, +STORE, 140590378729472, 140590380830719, +STORE, 140590378713088, 140590378729471, +SNULL, 140590380822527, 140590380830719, +STORE, 140590378729472, 140590380822527, +STORE, 140590380822528, 140590380830719, +ERASE, 140590380822528, 140590380830719, +STORE, 140590380822528, 140590380830719, +STORE, 140590376595456, 140590378713087, +SNULL, 140590376595456, 140590376611839, +STORE, 140590376611840, 140590378713087, +STORE, 140590376595456, 140590376611839, +SNULL, 140590378704895, 140590378713087, +STORE, 140590376611840, 140590378704895, +STORE, 140590378704896, 140590378713087, +ERASE, 140590378704896, 140590378713087, +STORE, 140590378704896, 140590378713087, +STORE, 140590374027264, 140590376595455, +SNULL, 140590374027264, 140590374494207, +STORE, 140590374494208, 140590376595455, +STORE, 140590374027264, 140590374494207, +SNULL, 140590376587263, 140590376595455, +STORE, 140590374494208, 140590376587263, +STORE, 140590376587264, 140590376595455, +ERASE, 140590376587264, 140590376595455, +STORE, 140590376587264, 140590376595455, +STORE, 140590371913728, 140590374027263, +SNULL, 140590371913728, 140590371926015, +STORE, 140590371926016, 140590374027263, +STORE, 140590371913728, 140590371926015, +SNULL, 140590374019071, 140590374027263, +STORE, 140590371926016, 140590374019071, +STORE, 140590374019072, 140590374027263, +ERASE, 140590374019072, 140590374027263, +STORE, 140590374019072, 140590374027263, +STORE, 140590400155648, 140590400180223, +STORE, 140590400143360, 140590400180223, +SNULL, 140590384603135, 140590384611327, +STORE, 140590384586752, 140590384603135, +STORE, 140590384603136, 140590384611327, +SNULL, 140590374023167, 140590374027263, +STORE, 140590374019072, 140590374023167, +STORE, 140590374023168, 140590374027263, +SNULL, 140590386823167, 140590386827263, +STORE, 140590386819072, 140590386823167, +STORE, 140590386823168, 140590386827263, +SNULL, 140590376591359, 140590376595455, +/* +STORE, 140590376587264, 140590376591359, +STORE, 140590376591360, 140590376595455, +*/ + }; + int cnt = 0; MA_STATE(mas, mt, 0, 0); @@ -10756,6 +10917,16 @@ ERASE, 140656774639616, 140656779083775, entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != xa_mk_value(140656766251008)); mtree_destroy(mt); + + /* set20 found a bug in mas_may_move_gap due to the slot being + * overwritten during the __mas_add operation and setting it to zero. + */ + mt_set_non_kernel(99); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set20, ARRAY_SIZE(set20)); + rcu_barrier(); + check_load(mt, 94849009414144, NULL); + mtree_destroy(mt); } static noinline void check_alloc_rev_range(struct maple_tree *mt) @@ -11171,7 +11342,9 @@ static noinline void check_gap_combining(struct maple_tree *mt) check_seq(mt, 100, false); // create 100 singletons. mtree_test_erase(mt, 88); + check_load(mt, 88, NULL); mtree_test_erase(mt, 87); + check_load(mt, 87, NULL); rcu_read_lock(); entry = mas_find(&mas, ULONG_MAX); @@ -11190,7 +11363,9 @@ static noinline void check_gap_combining(struct maple_tree *mt) rcu_read_unlock(); mtree_test_erase(mt, 38); + check_load(mt, 38, NULL); mtree_test_erase(mt, 39); + check_load(mt, 39, NULL); mtree_test_erase(mt, 40); index = 37; @@ -11214,7 +11389,11 @@ static noinline void check_gap_combining(struct maple_tree *mt) rcu_read_unlock(); mtree_store(mt, 79, NULL, GFP_KERNEL); + check_load(mt, 79, NULL); + check_load(mt, 80, xa_mk_value(80)); mtree_store(mt, 80, NULL, GFP_KERNEL); + check_load(mt, 79, NULL); + check_load(mt, 80, NULL); mas_reset(&mas); rcu_read_lock(); -- 2.50.1