Null expansion bug
Subsystems (3)
cover Null expansion bug
Andrew,
Please apply these two fixes to v9 of the maple tree.
The first should be applied to [01/69] "Maple Tree: add new data structure" to fix the bug.
The second should be applied to [07/69] "lib/test_maple_tree: add testing for maple tree" to test for the bug in the future.
Thanks,
Liam
*** BLURB HERE ***
Liam R. Howlett (2):
maple_tree: Fix expanding null off the end of the data.
test_maple_tree: Add null expansion tests
lib/maple_tree.c | 8 ++----- lib/test_maple_tree.c | 55 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+), 6 deletions(-)
Signature · 1 line
2.35.1
PATCH 1/2 maple_tree: Fix expanding null off the end of the data.
When expanding a write of null to another null, the metadata for the end of the node may be off by one. Fix this issue by setting the write end pivot (wr_mas->end_piv) in mas_wr_extend_null(). Also use the saved value for the end pivot during node stores instead of looking up the same entry again.
There is also unnecessary code in mas_wr_extend_null() that can be dropped.
--- lib/maple_tree.c | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
lib/maple_tree.c +2 -6
@@ -3981,8 +3981,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) new_end++; }else { -if (mas_safe_pivot (mas, wr_mas->pivots, wr_mas->offset_end, - wr_mas->type) == mas->last) +if (wr_mas->end_piv == mas->last) wr_mas->offset_end++; new_end -= wr_mas->offset_end - offset -1 ;
@@ -4146,10 +4145,7 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) mas->last = mas->max; else mas->last = wr_mas->pivots[wr_mas->offset_end]; - }else if ((mas->last > wr_mas->end_piv) && - !wr_mas->slots[wr_mas->offset_end]) { - mas->last = wr_mas->end_piv; - wr_mas->offset_end++; + wr_mas->end_piv = mas->last; }if (!wr_mas->content) {
Signature · 1 line
2.35.1
PATCH 2/2 test_maple_tree: Add null expansion tests
In reply to Liam Howlett--- lib/test_maple_tree.c | 55 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+)
lib/test_maple_tree.c +55 -0
@@ -35537,6 +35537,57 @@ static noinline void check_root_expand(struct maple_tree *mt)mas_unlock (&mas); } +static noinline void check_null_expand(struct maple_tree *mt) +{ +unsigned long i, max =100 ; +unsigned char data_end; +MA_STATE (mas, mt,959 ,959 ); + +for (i =0 ; i <= max; i++) +mtree_test_store_range (mt, i *10 , i *10 +5 , &i); +/* Test expanding null at start. */ +mas_walk (&mas); + data_end =mas_data_end (&mas); +mas_set_range (&mas,959 ,963 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt,mtree_load (mt,963 ) !=NULL ); +MT_BUG_ON (mt, data_end !=mas_data_end (&mas)); + +/* Test expanding null at end. */ +mas_set (&mas,880 ); +mas_walk (&mas); + data_end =mas_data_end (&mas); +mas_set_range (&mas,884 ,887 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt,mtree_load (mt,884 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,889 ) !=NULL ); +MT_BUG_ON (mt, data_end !=mas_data_end (&mas)); + +/* Test expanding null at start and end. */ +mas_set (&mas,890 ); +mas_walk (&mas); + data_end =mas_data_end (&mas); +mas_set_range (&mas,900 ,905 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt,mtree_load (mt,899 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,900 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,905 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,906 ) !=NULL ); +MT_BUG_ON (mt, data_end -2 !=mas_data_end (&mas)); + +/* Test expanding null across multiple slots. */ +mas_set (&mas,800 ); +mas_walk (&mas); + data_end =mas_data_end (&mas); +mas_set_range (&mas,810 ,825 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt,mtree_load (mt,809 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,810 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,825 ) !=NULL ); +MT_BUG_ON (mt,mtree_load (mt,826 ) !=NULL ); +MT_BUG_ON (mt, data_end -4 !=mas_data_end (&mas)); +} + static noinline void check_gap_combining(struct maple_tree *mt) {struct maple_enode *mn1, *mn2;
@@ -37627,6 +37678,10 @@ static int maple_tree_seed(void)check_new_node (&tree);mtree_destroy (&tree); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_null_expand (&tree); +mtree_destroy (&tree); +mt_init_flags (&tree,0 );check_dfs_preorder (&tree);mtree_destroy (&tree);
Signature · 1 line
2.35.1