Root Cause Analysis

1. Functions, Structs, and Files Involved

• lib/radix-tree.c: __radix_tree_create(), delete_node()
• include/linux/radix-tree.h / include/linux/xarray.h: struct radix_tree_node (defined as struct xa_node), radix_tree_for_each_slot()
• drivers/infiniband/core/uverbs_uapi.c: uverbs_alloc_api(), uverbs_destroy_api(), uapi_remove_range(), uapi_add_elm()
• drivers/infiniband/core/uverbs_main.c: ib_uverbs_create_uapi(), ib_uverbs_release_dev()

2. Technical Mechanism and Triggering Path

1. Intermediate Node Allocation in __radix_tree_create(): When adding an entry to a radix tree (radix_tree_insert() -> __radix_tree_create()), the function walks down the levels of the tree (while (shift > 0)):

   while (shift > 0) {
       shift -= RADIX_TREE_MAP_SHIFT;
       if (child == NULL) {
           child = radix_tree_node_alloc(gfp, node, root, shift, offset, 0, 0);
           if (!child)
               return -ENOMEM;
           rcu_assign_pointer(*slot, node_to_entry(child));
           if (node)
               node->count++;
       } else if (!radix_tree_is_internal_node(child))
           break;
   
       node = entry_to_node(child);
       offset = radix_tree_descend(node, &child, index);
       slot = &node->slots[offset];
   }
   

   At each missing level in the path towards the leaf, an intermediate radix_tree_node is allocated with count = 0 and linked into its parent's slot (*slot), and the parent's count is incremented.

2. Failure Handling on -ENOMEM: If a tree requires multiple intermediate levels (e.g. shift = 12, then shift = 6, then shift = 0):

   • At shift = 12, intermediate node Object 1 (0xffff88810d78f488, shift = 12, parent = NULL) is allocated.
   • At shift = 6, intermediate node Object 2 (0xffff88810d792920, shift = 6, offset = 9, count = 0, parent = Object 1) is allocated and linked into Object 1->slots[9], incrementing Object 1->count to 1.
   • On the subsequent level (shift = 0), radix_tree_node_alloc() fails with -ENOMEM (in the reproducer, induced via /proc/thread-self/fail-nth = 270).
   • __radix_tree_create() immediately returns -ENOMEM at line 627 without unwinding the tree or calling delete_node() on the partially created path.

3. Inability to Clean Up Empty Intermediate Nodes:

   • Because radix_tree_insert() returns -ENOMEM, uapi_merge_def() fails, and error recovery invokes uverbs_destroy_api():

     void uverbs_destroy_api(struct uverbs_api *uapi)
     {
         if (!uapi)
             return;
         uapi_remove_range(uapi, 0, U32_MAX);
         kfree(uapi->write_methods);
         kfree(uapi);
     }
     

   • uapi_remove_range() cleans up the tree using radix_tree_for_each_slot():

     static void uapi_remove_range(struct uverbs_api *uapi, u32 start, u32 last)
     {
         struct radix_tree_iter iter;
         void __rcu **slot;
     
         radix_tree_for_each_slot (slot, &uapi->radix, &iter, start) {
             if (iter.index > last)
                 return;
             kfree(rcu_dereference_protected(*slot, true));
             radix_tree_iter_delete(&uapi->radix, &iter, slot);
         }
     }
     

   • radix_tree_for_each_slot() traverses only non-empty leaf slots. Because Object 2 contains only empty slots (count == 0), the iterator never visits Object 2.
   • As valid entries elsewhere in the tree are deleted, delete_node() and radix_tree_shrink() shrink the tree down to Object 1 (shift = 12). However, Object 1->count is still 1 (referencing Object 2), so delete_node() cannot delete Object 1, nor can radix_tree_shrink() collapse it (as offset != 0).
   • Finally, kfree(uapi) frees struct uverbs_api (which embeds uapi->radix at address 0xffff888111f3e540, visible in the xa_node::array pointer field of both nodes' hex dumps). This cuts all remaining references to Object 1 and Object 2, producing the reported kmemleak splat.