From adfade108b2a334be15cafb0e4075bef969397ec Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 1 Sep 2020 15:30:05 -0400 Subject: [PATCH] maple_tree: Fix spanning_rebalance across many nodes with a new root. When spanning many nodes and creating a new root at a different level, the spanning rebalance was not correctly installing the root node. Also, rework test framework to test the above scenario correctly and add a test (set41) to do so. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 46 ++++-- lib/test_maple_tree.c | 364 ++++++++++++++++++++++++++++++++++++++---- 2 files changed, 359 insertions(+), 51 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6abfabaf6848..bee04744585e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1914,7 +1914,9 @@ static inline bool mast_cousin_rebalance_right(struct maple_subtree_state *mast) { struct maple_enode *old_l = mast->orig_l->node; struct maple_enode *old_r = mast->orig_r->node; + MA_STATE(tmp, mast->orig_r->tree, mast->orig_r->index, mast->orig_r->last); + mas_dup_state(&tmp, mast->orig_r); mas_set_offset(mast->orig_r, mte_parent_slot(mast->orig_r->node)); mas_next_node(mast->orig_r, ULONG_MAX); @@ -1922,13 +1924,14 @@ static inline bool mast_cousin_rebalance_right(struct maple_subtree_state *mast) mast_rebalance_next(mast, old_r); return true; } + mas_dup_state(mast->orig_r, mast->orig_l); mas_dup_state(mast->r, mast->l); mas_prev_node(mast->orig_l, 0); if (mas_is_none(mast->orig_l)) { // This is going to be a new root with the contents of mast->bn mas_dup_state(mast->orig_l, mast->orig_r); - mast->bn->b_end--; + mas_dup_state(mast->orig_r, &tmp); return false; } @@ -2163,15 +2166,11 @@ static inline void mas_wmb_replace(struct ma_state *mas, mas_update_gap(mas); } -static inline bool mast_new_root(struct maple_subtree_state *mast, +static inline void mast_new_root(struct maple_subtree_state *mast, struct ma_state *mas) { - if (!mas_is_root_limits(mast->l)) - return false; - mas_mn(mast->l)->parent = ma_parent_ptr(((unsigned long)mas->tree | MA_ROOT_PARENT)); - mas->depth = mast->orig_l->depth; if (!mte_is_root(mast->orig_l->node)) { do { mast_ascend_free(mast); @@ -2183,8 +2182,6 @@ static inline bool mast_new_root(struct maple_subtree_state *mast, } mat_add(mast->free, mast->orig_l->node); - mas_dup_state(mast->orig_l, mast->l); - return true; } static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, @@ -2254,6 +2251,13 @@ static inline bool mast_sufficient(struct maple_subtree_state *mast) return false; } +static inline bool mast_overflow(struct maple_subtree_state *mast) +{ + if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) + return true; + + return false; +} static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) { @@ -2318,7 +2322,8 @@ static inline int mas_spanning_rebalance(struct ma_state *mas, mast->bn->type = mte_node_type(left); mast->orig_l->depth++; - if (mast_new_root(mast, mas)) + // Root already stored in l->node. + if (mas_is_root_limits(mast->l)) goto new_root; mast_ascend_free(mast); @@ -2336,13 +2341,20 @@ static inline int mas_spanning_rebalance(struct ma_state *mas, if (mast_sufficient(mast)) continue; - if (mas_is_root_limits(mast->orig_l)) // new root without a node. + if (mast_overflow(mast)) + continue; + + // May be a new root stored in mast->bn + if (mas_is_root_limits(mast->orig_l)) break; + // Try to get enough data for the next iteration. if (!mast_sibling_rebalance_right(mast)) if (!mast_cousin_rebalance_right(mast)) break; + + // rebalancing from other nodes may require another loop. if (!count) count++; } @@ -2357,19 +2369,17 @@ static inline int mas_spanning_rebalance(struct ma_state *mas, if (right) mte_set_parent(right, l_mas.node, ++slot); - if (mas_is_root_limits(mast->orig_l)) { - mas_mn(&l_mas)->parent = - ma_parent_ptr(((unsigned long)mas->tree | MA_ROOT_PARENT)); - } else { +new_root: + if (mas_is_root_limits(mast->l)) + mast_new_root(mast, mas); + else mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; - } if (!mte_dead_node(mast->orig_l->node)) mat_add(&free, mast->orig_l->node); mas_dup_state(mast->orig_l, &l_mas); mas->depth = mast->orig_l->depth; -new_root: mte_set_node_dead(mas->node); // Set up mas for insertion. mas_dup_state(mas, mast->orig_l); @@ -3557,8 +3567,10 @@ retry: if (mas_next_nentry(mas, limit, range_start)) break; - if (*range_start > limit) + if (*range_start > limit) { + mas->node = MAS_NONE; return NULL; + } next_node: p_slot = mte_parent_slot(mas->node); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 9d7e4e95b6d3..75efc261c05d 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -927,38 +927,16 @@ int mas_ce2_over_cnt(struct ma_state *mas_start, struct ma_state *mas_end, void *e_entry, unsigned long e_max, unsigned long *set, int i, bool null_entry) { - unsigned char cnt = 0; + int cnt = 0; unsigned long retry = 0; - MA_STATE(null_mas, mas_start->tree, mas_start->index - 1, - mas_end->index - 1); // check start - if (s_entry && (s_min == mas_start->index)) { - cnt++; - if (null_entry && !mas_load(&null_mas)) { - printk("null at %lu\n", null_mas.last); - cnt++; - } - } - - // check end - if (e_entry && (e_max == mas_end->last)) { + if (s_entry && (s_min == mas_start->index)) cnt++; - if (null_entry) { - null_mas.index = mas_end->last + 1; - null_mas.last = mas_end->last + 1; - mas_reset(&null_mas); - if (!mas_load(&null_mas)) { - printk("null at %lu\n", null_mas.last); - cnt++; - } - } - } // count slots - s_entry = mas_next(mas_start, set[i+2]); - while (!mas_is_none(mas_start) && - (mas_start->last != e_max)) { + s_entry = mas_next(mas_start, mas_end->last); + while (!mas_is_none(mas_start)) { BUG_ON(retry > 50); // stop infinite retry on testing. if (xa_is_zero(s_entry)) { retry++; @@ -969,8 +947,11 @@ int mas_ce2_over_cnt(struct ma_state *mas_start, struct ma_state *mas_end, s_entry = mas_next(mas_start, set[i+2]); } + // check end + if (e_entry && (e_max > mas_end->last)) + cnt--; - return cnt - 1; + return cnt; } static noinline void check_erase2_testset(struct maple_tree *mt, unsigned long *set, unsigned long size) @@ -1002,19 +983,16 @@ static noinline void check_erase2_testset(struct maple_tree *mt, switch (set[i]) { case SNULL: - if ((s_min == set[i+1]) && (s_max == set[i+2])) + if ((s_min == set[i+1]) && (s_max == set[i+2])) { entry_cnt--; - else if ((s_min != set[i+1]) && (s_max != set[i+2])) + } else if ((s_min != set[i+1]) && (s_max != set[i+2])) { entry_cnt++; - else if ((s_min == mas_start.index) - && (e_max == mas_end.last)) { + } else if (mas_start.node != mas_end.node) { entry_cnt -= mas_ce2_over_cnt(&mas_start, &mas_end, s_entry, s_min, e_entry, e_max, set, i, true); - // Since NULLs are combined, the prev and next - // slots need to be checked for NULL. } @@ -1041,7 +1019,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, mas_ce2_over_cnt(&mas_start, &mas_end, s_entry, s_min, e_entry, e_max, set, i, - false); + false) - 1; } erase_check_store_range(mt, set, i + 1, value); @@ -30878,6 +30856,316 @@ ERASE, 140320289300480, 140320289304575, ERASE, 140320289304576, 140320297693183, ERASE, 140320163409920, 140320163414015, }; + unsigned long set41[] = { +STORE, 140737488347136, 140737488351231, +STORE, 140728157171712, 140737488351231, +SNULL, 140728157175807, 140737488351231, +STORE, 140728157171712, 140728157175807, +STORE, 140728157040640, 140728157175807, +STORE, 94376106364928, 94376108613631, +SNULL, 94376106487807, 94376108613631, +STORE, 94376106364928, 94376106487807, +STORE, 94376106487808, 94376108613631, +SNULL, 94376106487808, 94376108613631, +STORE, 94376108584960, 94376108593151, +STORE, 94376108593152, 94376108613631, +STORE, 140113496432640, 140113498685439, +SNULL, 140113496575999, 140113498685439, +STORE, 140113496432640, 140113496575999, +STORE, 140113496576000, 140113498685439, +SNULL, 140113496576000, 140113498685439, +STORE, 140113498673152, 140113498681343, +STORE, 140113498681344, 140113498685439, +STORE, 140728157609984, 140728157618175, +STORE, 140728157593600, 140728157609983, +STORE, 140113498636288, 140113498673151, +STORE, 140113498628096, 140113498636287, +STORE, 140113492635648, 140113496432639, +SNULL, 140113492635648, 140113494294527, +STORE, 140113494294528, 140113496432639, +STORE, 140113492635648, 140113494294527, +SNULL, 140113496391679, 140113496432639, +STORE, 140113494294528, 140113496391679, +STORE, 140113496391680, 140113496432639, +SNULL, 140113496391680, 140113496416255, +STORE, 140113496416256, 140113496432639, +STORE, 140113496391680, 140113496416255, +SNULL, 140113496391680, 140113496416255, +STORE, 140113496391680, 140113496416255, +SNULL, 140113496416256, 140113496432639, +STORE, 140113496416256, 140113496432639, +SNULL, 140113496408063, 140113496416255, +STORE, 140113496391680, 140113496408063, +STORE, 140113496408064, 140113496416255, +SNULL, 94376108589055, 94376108593151, +STORE, 94376108584960, 94376108589055, +STORE, 94376108589056, 94376108593151, +SNULL, 140113498677247, 140113498681343, +STORE, 140113498673152, 140113498677247, +STORE, 140113498677248, 140113498681343, +SNULL, 140113498636288, 140113498673151, +STORE, 94376135090176, 94376135094271, +STORE, 94376135090176, 94376135098367, +STORE, 94376139288576, 94376139292671, +STORE, 94376143482880, 94376143486975, +STORE, 94376147677184, 94376147681279, +STORE, 94376151871488, 94376151875583, +STORE, 94376156065792, 94376156069887, +STORE, 94376160260096, 94376160264191, +STORE, 94376164454400, 94376164458495, +STORE, 94376168648704, 94376168652799, +STORE, 94376172843008, 94376172847103, +STORE, 94376177037312, 94376177041407, +STORE, 94376181231616, 94376181235711, +STORE, 94376185425920, 94376185430015, +STORE, 94376189620224, 94376189624319, +STORE, 94376193814528, 94376193818623, +STORE, 94376198008832, 94376198012927, +STORE, 94376202203136, 94376202207231, +STORE, 94376206397440, 94376206401535, +STORE, 94376210591744, 94376210595839, +STORE, 94376214786048, 94376214790143, +STORE, 94376218980352, 94376218984447, +STORE, 94376223174656, 94376223178751, +STORE, 94376227368960, 94376227373055, +STORE, 94376231563264, 94376231567359, +STORE, 94376235757568, 94376235761663, +STORE, 94376239951872, 94376239955967, +STORE, 94376244146176, 94376244150271, +STORE, 94376248340480, 94376248344575, +STORE, 94376252534784, 94376252538879, +STORE, 94376256729088, 94376256733183, +STORE, 94376260923392, 94376260927487, +STORE, 94376265117696, 94376265121791, +STORE, 94376269312000, 94376269316095, +STORE, 94376273506304, 94376273510399, +STORE, 94376277700608, 94376277704703, +STORE, 94376281894912, 94376281899007, +STORE, 94376286089216, 94376286093311, +STORE, 94376290283520, 94376290287615, +STORE, 94376294477824, 94376294481919, +STORE, 94376298672128, 94376298676223, +STORE, 94376302866432, 94376302870527, +STORE, 94376307060736, 94376307064831, +STORE, 94376311255040, 94376311259135, +STORE, 94376315449344, 94376315453439, +STORE, 94376319643648, 94376319647743, +STORE, 94376323837952, 94376323842047, +STORE, 94376328032256, 94376328036351, +STORE, 94376332226560, 94376332230655, +STORE, 94376336420864, 94376336424959, +STORE, 94376340615168, 94376340619263, +STORE, 94376344809472, 94376344813567, +STORE, 94376349003776, 94376349007871, +STORE, 94376353198080, 94376353202175, +STORE, 94376357392384, 94376357396479, +STORE, 94376361586688, 94376361590783, +STORE, 94376365780992, 94376365785087, +STORE, 94376369975296, 94376369979391, +STORE, 94376374169600, 94376374173695, +STORE, 94376378363904, 94376378367999, +STORE, 94376382558208, 94376382562303, +STORE, 94376386752512, 94376386756607, +STORE, 94376390946816, 94376390950911, +STORE, 94376395141120, 94376395145215, +STORE, 94376399335424, 94376399339519, +STORE, 94376403529728, 94376403533823, +STORE, 94376407724032, 94376407728127, +STORE, 94376411918336, 94376411922431, +STORE, 94376416112640, 94376416116735, +STORE, 94376420306944, 94376420311039, +STORE, 94376424501248, 94376424505343, +STORE, 94376428695552, 94376428699647, +STORE, 94376432889856, 94376432893951, +STORE, 94376437084160, 94376437088255, +STORE, 94376441278464, 94376441282559, +STORE, 94376445472768, 94376445476863, +STORE, 94376449667072, 94376449671167, +STORE, 94376453861376, 94376453865471, +STORE, 94376458055680, 94376458059775, +STORE, 94376462249984, 94376462254079, +STORE, 94376466444288, 94376466448383, +STORE, 94376470638592, 94376470642687, +STORE, 94376474832896, 94376474836991, +STORE, 94376479027200, 94376479031295, +STORE, 94376483221504, 94376483225599, +STORE, 94376487415808, 94376487419903, +STORE, 94376491610112, 94376491614207, +STORE, 94376495804416, 94376495808511, +STORE, 94376499998720, 94376500002815, +STORE, 94376504193024, 94376504197119, +STORE, 94376508387328, 94376508391423, +STORE, 94376512581632, 94376512585727, +STORE, 94376516775936, 94376516780031, +STORE, 94376520970240, 94376520974335, +STORE, 94376525164544, 94376525168639, +STORE, 94376529358848, 94376529362943, +STORE, 94376533553152, 94376533557247, +STORE, 94376537747456, 94376537751551, +STORE, 94376541941760, 94376541945855, +STORE, 94376546136064, 94376546140159, +STORE, 94376550330368, 94376550334463, +STORE, 94376554524672, 94376554528767, +STORE, 94376558718976, 94376558723071, +STORE, 94376562913280, 94376562917375, +STORE, 94376567107584, 94376567111679, +STORE, 94376571301888, 94376571305983, +STORE, 94376575496192, 94376575500287, +STORE, 94376579690496, 94376579694591, +STORE, 94376583884800, 94376583888895, +STORE, 94376588079104, 94376588083199, +STORE, 94376592273408, 94376592277503, +STORE, 94376596467712, 94376596471807, +STORE, 94376600662016, 94376600666111, +STORE, 94376604856320, 94376604860415, +STORE, 94376609050624, 94376609054719, +STORE, 94376613244928, 94376613249023, +STORE, 94376617439232, 94376617443327, +STORE, 94376621633536, 94376621637631, +STORE, 94376625827840, 94376625831935, +STORE, 94376630022144, 94376630026239, +STORE, 94376634216448, 94376634220543, +STORE, 94376638410752, 94376638414847, +STORE, 94376642605056, 94376642609151, +STORE, 94376646799360, 94376646803455, +STORE, 94376650993664, 94376650997759, +STORE, 94376655187968, 94376655192063, +STORE, 94376659382272, 94376659386367, +STORE, 94376663576576, 94376663580671, +STORE, 94376667770880, 94376667774975, +STORE, 94376671965184, 94376671969279, +STORE, 94376676159488, 94376676163583, +STORE, 94376680353792, 94376680357887, +STORE, 94376684548096, 94376684552191, +STORE, 94376688742400, 94376688746495, +STORE, 94376692936704, 94376692940799, +STORE, 94376697131008, 94376697135103, +STORE, 94376701325312, 94376701329407, +STORE, 94376705519616, 94376705523711, +STORE, 94376709713920, 94376709718015, +STORE, 94376713908224, 94376713912319, +STORE, 94376718102528, 94376718106623, +STORE, 94376722296832, 94376722300927, +STORE, 94376726491136, 94376726495231, +STORE, 94376730685440, 94376730689535, +STORE, 94376734879744, 94376734883839, +STORE, 94376739074048, 94376739078143, +STORE, 94376743268352, 94376743272447, +STORE, 94376747462656, 94376747466751, +STORE, 94376751656960, 94376751661055, +STORE, 94376755851264, 94376755855359, +STORE, 94376760045568, 94376760049663, +STORE, 94376764239872, 94376764243967, +STORE, 94376768434176, 94376768438271, +STORE, 94376772628480, 94376772632575, +STORE, 94376776822784, 94376776826879, +STORE, 94376781017088, 94376781021183, +STORE, 94376785211392, 94376785215487, +STORE, 94376789405696, 94376789409791, +STORE, 94376793600000, 94376793604095, +STORE, 94376797794304, 94376797798399, +STORE, 94376801988608, 94376801992703, +STORE, 94376806182912, 94376806187007, +STORE, 94376810377216, 94376810381311, +STORE, 94376814571520, 94376814575615, +STORE, 94376818765824, 94376818769919, +STORE, 94376822960128, 94376822964223, +STORE, 94376827154432, 94376827158527, +STORE, 94376831348736, 94376831352831, +STORE, 94376835543040, 94376835547135, +STORE, 94376839737344, 94376839741439, +STORE, 94376843931648, 94376843935743, +STORE, 94376848125952, 94376848130047, +STORE, 94376852320256, 94376852324351, +STORE, 94376856514560, 94376856518655, +STORE, 94376860708864, 94376860712959, +STORE, 94376864903168, 94376864907263, +STORE, 94376869097472, 94376869101567, +STORE, 94376873291776, 94376873295871, +STORE, 94376877486080, 94376877490175, +STORE, 94376881680384, 94376881684479, +STORE, 94376885874688, 94376885878783, +STORE, 94376890068992, 94376890073087, +STORE, 94376894263296, 94376894267391, +STORE, 94376898457600, 94376898461695, +STORE, 94376902651904, 94376902655999, +STORE, 94376906846208, 94376906850303, +STORE, 94376911040512, 94376911044607, +STORE, 94376915234816, 94376915238911, +STORE, 94376919429120, 94376919433215, +STORE, 94376923623424, 94376923627519, +STORE, 94376927817728, 94376927821823, +STORE, 94376932012032, 94376932016127, +STORE, 94376936206336, 94376936210431, +STORE, 94376940400640, 94376940404735, +STORE, 94376944594944, 94376944599039, +STORE, 94376948789248, 94376948793343, +STORE, 94376952983552, 94376952987647, +STORE, 94376957177856, 94376957181951, +STORE, 94376961372160, 94376961376255, +STORE, 94376965566464, 94376965570559, +STORE, 94376969760768, 94376969764863, +STORE, 94376973955072, 94376973959167, +STORE, 94376978149376, 94376978153471, +STORE, 94376982343680, 94376982347775, +STORE, 94376986537984, 94376986542079, +STORE, 94376990732288, 94376990736383, +STORE, 94376994926592, 94376994930687, +STORE, 94376999120896, 94376999124991, +STORE, 94377003315200, 94377003319295, +STORE, 94377007509504, 94377007513599, +STORE, 94377011703808, 94377011707903, +STORE, 94377015898112, 94377015902207, +STORE, 94377020092416, 94377020096511, +STORE, 94377024286720, 94377024290815, +STORE, 94377028481024, 94377028485119, +STORE, 94377032675328, 94377032679423, +STORE, 94377036869632, 94377036873727, +STORE, 94377041063936, 94377041068031, +STORE, 94377045258240, 94377045262335, +STORE, 94377049452544, 94377049456639, +STORE, 94377053646848, 94377053650943, +STORE, 94377057841152, 94377057845247, +STORE, 94377062035456, 94377062039551, +STORE, 94377066229760, 94377066233855, +STORE, 94377070424064, 94377070428159, +STORE, 94377074618368, 94377074622463, +STORE, 94377078812672, 94377078816767, +STORE, 94377083006976, 94377083011071, +STORE, 94377087201280, 94377087205375, +STORE, 94377091395584, 94377091399679, +STORE, 94377095589888, 94377095593983, +STORE, 94377099784192, 94377099788287, +STORE, 94377103978496, 94377103982591, +STORE, 94377108172800, 94377108176895, +STORE, 94377112367104, 94377112371199, +STORE, 94377116561408, 94377116565503, +STORE, 94377120755712, 94377120759807, +STORE, 94377124950016, 94377124954111, +STORE, 94377129144320, 94377129148415, +STORE, 94377133338624, 94377133342719, +STORE, 94377137532928, 94377137537023, +STORE, 94377141727232, 94377141731327, +STORE, 94377145921536, 94377145925631, +STORE, 94377150115840, 94377150119935, +STORE, 94377154310144, 94377154314239, +STORE, 94377158504448, 94377158508543, +STORE, 94377162698752, 94377162702847, +STORE, 94377166893056, 94377166897151, +STORE, 94377171087360, 94377171091455, +STORE, 94377175281664, 94377175285759, +STORE, 94377179475968, 94377179480063, +STORE, 94377183670272, 94377183674367, +STORE, 94377187864576, 94377187868671, +STORE, 94377192058880, 94377192062975, +STORE, 94377196253184, 94377196257279, +STORE, 94377200447488, 94377200451583, +STORE, 94377204641792, 94377204645887, +SNULL, 94376135094271, 94376135098367, +STORE, 94376135090176, 94376135094271, +STORE, 94376135094272, 94376135098367, +SNULL, 94376135094272, 94377208836095, + }; int cnt = 0; void *ptr = NULL; @@ -31248,6 +31536,13 @@ ERASE, 140320163409920, 140320163414015, rcu_barrier(); mt_validate(mt); mtree_destroy(mt); + + mas_reset(&mas); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set41, ARRAY_SIZE(set41)); + rcu_barrier(); + mt_validate(mt); + mtree_destroy(mt); } static noinline void check_alloc_rev_range(struct maple_tree *mt) @@ -32427,6 +32722,7 @@ static int maple_tree_seed(void) mtree_init(&tree, MAPLE_ALLOC_RANGE); check_prev_entry(&tree); + mtree_init(&tree, 0); check_erase2_sets(&tree); mtree_destroy(&tree); -- 2.50.1