[PATCH v1] radix-tree: fix memory leak of intermediate nodes on insert failure

[PATCH v1] radix-tree: fix memory leak of intermediate nodes on insert failure

[Jiayuan Chen]

From: Jiayuan Chen <jiayuan.chen@shopee.com>

__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: syzbot+006987d1be3586e13555@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/all/000000000000bfba3a060bf4ffcf@google.com/T/
Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Signed-off-by: Jiayuan Chen <jiayuan.chen@shopee.com>
---
 lib/radix-tree.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 976b9bd02a1b..2bdf2be71b95 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -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++;
-- 
2.43.0