maple_tree: Fix mt_destroy_walk() on root leaf node
Subsystems (5)
PATCH 1/2 maple_tree: Fix mt_destroy_walk() on root leaf node
From: Wei Yang <[email protected]>
On destroy, we should set each node dead. But current code miss this when the maple tree has only the root node.
The reason is mt_destroy_walk() leverage mte_destroy_descend() to set node dead, but this is skipped since the only root node is a leaf.
Fixes this by setting the node dead if it is a leaf.
--- lib/maple_tree.c | 1 + 1 file changed, 1 insertion(+)
lib/maple_tree.c +1 -0
@@ -5319,6 +5319,7 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,struct maple_enode *start;if (mte_is_leaf (enode)) { +mte_set_node_dead (enode); node->type =mte_node_type (enode); goto free_leaf; }
Signature · 1 line
2.47.2
PATCH 2/2 maple_tree: assert retrieving new value on a tree containing just a leaf node
From: Wei Yang <[email protected]>
Original code may not get the new value after overwriting the whole range on a maple tree containing just a leaf node. The reason is we didn't set the only root node dead during destroy.
Add a test case to ensure the new value is returned when overwriting a tree containing just a leaf node.
--- tools/testing/radix-tree/maple.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)
tools/testing/radix-tree/maple.c +26 -0
@@ -35257,6 +35257,32 @@ static noinline void __init check_rcu_simulated(struct maple_tree *mt)MT_BUG_ON (mt,mas_prev (&mas_reader,0 ) !=xa_mk_value (val));rcu_read_unlock (); +/* Clear out tree & create one with only root node */ +mtree_destroy (mt); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE |MT_FLAGS_USE_RCU ); +mas_pause (&mas_writer); +mas_lock (&mas_writer); +for (i =0 ; i <=5 ; i++) { + mas_writer.index = i *10 ; + mas_writer.last = i *10 +5 ; +mas_store_gfp (&mas_writer,xa_mk_value (i),GFP_KERNEL ); + } +mas_unlock (&mas_writer); + target =10 ; + val =20 ; +mas_set (&mas_reader, target); +rcu_read_lock (); +MT_BUG_ON (mt,mas_walk (&mas_reader) !=xa_mk_value (target/10 )); +MT_BUG_ON (mt,mte_is_leaf (mas_reader.node) != true); + +/* Overwrite the whole range */ +mas_lock (&mas_writer); +mas_set_range (&mas_writer,0 ,ULONG_MAX ); +mas_store_gfp (&mas_writer,xa_mk_value (val),GFP_KERNEL ); +mas_unlock (&mas_writer); +MT_BUG_ON (mt,mas_walk (&mas_reader) !=xa_mk_value (val)); +rcu_read_unlock (); +rcu_unregister_thread (); }
Signature · 1 line
2.47.2
Quoted 25 lines · Liam R. Howlett
From: Wei Yang <[email protected]>
On destroy, we should set each node dead. But current code miss this when the maple tree has only the root node.
The reason is
mt_destroy_walk()leveragemte_destroy_descend()to set node dead, but this is skipped since the only root node is a leaf.Fixes this by setting the node dead if it is a leaf.
Fixes 54a611b60590 ("Maple Tree: add new data structure")Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>Cc <[email protected]>Signed-off-by Liam R. Howlett <[email protected]>--- lib/maple_tree.c | 1 + 1 file changed, 1 insertion(+)lib/maple_tree.c +0
-0
lib/maple_tree.c static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, · line 5325
Quoted 7 lines
lib/maple_tree.c +1
-0@@ -5319,6 +5319,7 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,struct maple_enode *start;if (mte_is_leaf (enode)) { +mte_set_node_dead (enode); node->type =mte_node_type (enode); goto free_leaf; }
FWIW I have been reading the maple tree code and this looks good to me.