From 572fc40da7df8e51b6ef65559b2253d7607faff0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 21 Feb 2020 21:49:55 -0500 Subject: [PATCH] maple_tree: Fix finding the end of a node when the node ends in a NULL. Also fix the limit calculation on gaps when searches backwards goes into adjacent nodes during the search. Ignoring the end null may cause gaps to be skipped when searching backwards. Adjacent nodes caused the max limit to be reset to the parent but never set if the very next entry also had a potential gap that would work. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 7 ++- lib/test_maple_tree.c | 123 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 125 insertions(+), 5 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9eb4ccf0dd21..37b452600181 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1157,8 +1157,8 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, break; } (*coalesce) = (*coalesce) - counted_null + 1; - slot -= counted_null; - piv = _mas_get_safe_pivot(mas, slot, type); + piv = _mas_get_safe_pivot(mas, + slot - counted_null, type); } break; } @@ -3589,11 +3589,10 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) i = mas_get_slot(mas); min = mas->min; - max = mas->max; + max = _mas_get_safe_pivot(mas, i, type); switch (type) { case maple_leaf_64: - max = _mas_get_safe_pivot(mas, i, type); start = i; do { diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index ac73754cd3b5..6daa7a74ec99 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -10237,6 +10237,101 @@ STORE, 139921865613312, 139921865617407, STORE, 139921865547776, 139921865564159, }; + unsigned long set17[] = { +STORE, 94397057224704, 94397057646591, +STORE, 94397057650688, 94397057691647, +STORE, 94397057691648, 94397057695743, +STORE, 94397075271680, 94397075406847, +STORE, 139953169051648, 139953169063935, +STORE, 139953169063936, 139953171156991, +STORE, 139953171156992, 139953171161087, +STORE, 139953171161088, 139953171165183, +STORE, 139953171165184, 139953171632127, +STORE, 139953171632128, 139953173725183, +STORE, 139953173725184, 139953173729279, +STORE, 139953173729280, 139953173733375, +STORE, 139953173733376, 139953173749759, +STORE, 139953173749760, 139953175842815, +STORE, 139953175842816, 139953175846911, +STORE, 139953175846912, 139953175851007, +STORE, 139953175851008, 139953175867391, +STORE, 139953175867392, 139953177960447, +STORE, 139953177960448, 139953177964543, +STORE, 139953177964544, 139953177968639, +STORE, 139953177968640, 139953179627519, +STORE, 139953179627520, 139953181724671, +STORE, 139953181724672, 139953181741055, +STORE, 139953181741056, 139953181749247, +STORE, 139953181749248, 139953181765631, +STORE, 139953181765632, 139953181863935, +STORE, 139953181863936, 139953183956991, +STORE, 139953183956992, 139953183961087, +STORE, 139953183961088, 139953183965183, +STORE, 139953183965184, 139953183981567, +STORE, 139953183981568, 139953184010239, +STORE, 139953184010240, 139953186103295, +STORE, 139953186103296, 139953186107391, +STORE, 139953186107392, 139953186111487, +STORE, 139953186111488, 139953186263039, +STORE, 139953186263040, 139953188356095, +STORE, 139953188356096, 139953188360191, +STORE, 139953188360192, 139953188364287, +STORE, 139953188364288, 139953188372479, +STORE, 139953188372480, 139953188462591, +STORE, 139953188462592, 139953190555647, +STORE, 139953190555648, 139953190559743, +STORE, 139953190559744, 139953190563839, +STORE, 139953190563840, 139953190830079, +STORE, 139953190830080, 139953192923135, +STORE, 139953192923136, 139953192939519, +STORE, 139953192939520, 139953192943615, +STORE, 139953192943616, 139953192947711, +STORE, 139953192947712, 139953192976383, +STORE, 139953192976384, 139953195073535, +STORE, 139953195073536, 139953195077631, +STORE, 139953195077632, 139953195081727, +STORE, 139953195081728, 139953195225087, +STORE, 139953197281280, 139953197318143, +STORE, 139953197322240, 139953197326335, +STORE, 139953197326336, 139953197330431, +STORE, 139953197330432, 139953197334527, +STORE, 140720477511680, 140720477646847, +STORE, 140720478302208, 140720478314495, +STORE, 140720478314496, 140720478318591, + }; + unsigned long set18[] = { +STORE, 140737488347136, 140737488351231, +STORE, 140724953673728, 140737488351231, +SNULL, 140724953677823, 140737488351231, +STORE, 140724953673728, 140724953677823, +STORE, 140724953542656, 140724953677823, +STORE, 94675199266816, 94675199311871, +SNULL, 94675199303679, 94675199311871, +STORE, 94675199266816, 94675199303679, +STORE, 94675199303680, 94675199311871, +ERASE, 94675199303680, 94675199311871, +STORE, 94675199303680, 94675199311871, +STORE, 140222970605568, 140222972858367, +SNULL, 140222970748927, 140222972858367, +STORE, 140222970605568, 140222970748927, +STORE, 140222970748928, 140222972858367, +ERASE, 140222970748928, 140222972858367, +STORE, 140222972846080, 140222972854271, +STORE, 140222972854272, 140222972858367, +STORE, 140724954365952, 140724954370047, +STORE, 140724954353664, 140724954365951, +STORE, 140222972841984, 140222972846079, +STORE, 140222972833792, 140222972841983, +STORE, 140222968475648, 140222970605567, +SNULL, 140222968475648, 140222968504319, +STORE, 140222968504320, 140222970605567, +STORE, 140222968475648, 140222968504319, +SNULL, 140222970597375, 140222970605567, +STORE, 140222968504320, 140222970597375, +STORE, 140222970597376, 140222970605567, +ERASE, 140222970597376, 140222970605567, +STORE, 140222970597376, 140222970605567, + }; int cnt = 0; MA_STATE(mas, mt, 0, 0); @@ -10345,9 +10440,35 @@ STORE, 139921865547776, 139921865564159, check_erase2_testset(mt, set16, ARRAY_SIZE(set16)); rcu_barrier(); mas_get_unmapped_area_rev(&mas, 4096, 139921865637888, 0x6000); - printk("Found %lu\n", mas.index); MT_BUG_ON(mt, mas.index != 139921865523200); mtree_destroy(mt); + + /* set17 found a bug in walking backwards and not counting nulls at + * the end. This could cause a gap to be missed if the null had any + * size. + */ + mt_set_non_kernel(99); + mas_reset(&mas); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set17, ARRAY_SIZE(set17)); + rcu_barrier(); + mas_get_unmapped_area_rev(&mas, 4096, 139953197334528, 0x1000); + MT_BUG_ON(mt, mas.index != 139953197318144); + mtree_destroy(mt); + + /* set18 found a bug in walking backwards and not setting the max from + * the node, but using the parent node. This was only an issue if the + * next slot in the parent had what we needed. + */ + mt_set_non_kernel(99); + mas_reset(&mas); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set18, ARRAY_SIZE(set18)); + rcu_barrier(); + mas_get_unmapped_area_rev(&mas, 4096, 140222972858368, 2215936); + printk("Found %lu\n", mas.index); + MT_BUG_ON(mt, mas.index != 140222966259712); + mtree_destroy(mt); } static noinline void check_alloc_rev_range(struct maple_tree *mt) -- 2.50.1