radix-tree: fix memory leak of intermediate nodes on insert failure
Subsystems (2)
PATCH 1/1 radix-tree: fix memory leak of intermediate nodes on insert failure
From: Jiayuan Chen <[email protected]>
__radix_tree_create() builds a path by allocating and immediately linking intermediate nodes into the tree one by one. If an allocation fails partway through, the already-linked nodes remain in the tree with no corresponding leaf entry. These nodes are never reclaimed because radix_tree_for_each_slot() only visits slots containing leaf values and there is no radix_tree_destroy() to walk all structural nodes.
The natural alternative—migrating callers to xarray and relying on xa_destroy()—does not cover global or long-lived trees whose lifetime is tied to the system. xa_destroy() is never called for such trees, so orphaned nodes would persist until reboot.
Fix this directly in __radix_tree_create() by tracking the first newly linked slot. On allocation failure, sever the partial path with rcu_assign_pointer() and free the orphaned nodes via call_rcu() to maintain RCU safety for concurrent readers.
--- lib/radix-tree.c | 22 +++++++++++++++++++++- 1 file changed, 21 insertions(+), 1 deletion(-)
lib/radix-tree.c +21 -1
@@ -600,6 +600,11 @@ static int __radix_tree_create(struct radix_tree_root *root, void __rcu ***slotp) {struct radix_tree_node *node =NULL , *child; +/* Track newly allocated nodes for rollback on failure */ +struct radix_tree_node *new_nodes[RADIX_TREE_MAX_PATH ]; +void __rcu **first_new_slot =NULL ; +struct radix_tree_node *first_new_parent =NULL ; +int new_count =0 , i;void __rcu **slot = (void __rcu **)&root->xa_head;unsigned long maxindex;unsigned int shift, offset =0 ;
@@ -623,8 +628,23 @@ static int __radix_tree_create(struct radix_tree_root *root,/* Have to add a child node. */ child =radix_tree_node_alloc (gfp, node, root, shift, offset,0 ,0 ); -if (!child) +if (!child) { +/* Rollback: sever and free all newly allocated nodes */ +if (first_new_slot) { +rcu_assign_pointer (*first_new_slot,NULL ); +if (first_new_parent) + first_new_parent->count--; +for (i =0 ; i < new_count; i++) +radix_tree_node_free (new_nodes[i]); + }return -ENOMEM ; + } +/* Record first new slot and parent for potential rollback */ +if (!first_new_slot) { + first_new_slot = slot; + first_new_parent = node; + } + new_nodes[new_count++] = child;rcu_assign_pointer (*slot,node_to_entry (child));if (node) node->count++;
Signature · 1 line
2.43.0
Quoted 4 lines · Jiayuan Chen
Fix this directly in
__radix_tree_create()by tracking the first newly linked slot. On allocation failure, sever the partial path withrcu_assign_pointer()and free the orphaned nodes viacall_rcu()to maintain RCU safety for concurrent readers.
I'm not interested in fixing this. Migrate qrtr to use XArray.