Skip to contentSkip to conversation

radix-tree: fix memory leak of intermediate nodes on insert failure

PATCH In review Jiayuan Chen 2 participants 2 messages Feb 25

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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.

Reported-by [email protected]
Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")
---
 lib/radix-tree.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)
lib/radix-tree.c +21 -1
index 976b9bd02a1b..2bdf2be71b95 100644
@@ -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
#1 lore raw
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 with rcu_assign_pointer() and free the orphaned nodes via call_rcu() to maintain RCU safety for concurrent readers.

I'm not interested in fixing this. Migrate qrtr to use XArray.