[PATCH] radix tree: fix kmemleak false positive in radix_tree_shrink()

[PATCH] radix tree: fix kmemleak false positive in radix_tree_shrink()

[Jared Kangas]

Kmemleak periodically produces a false positive report that resembles
the following:

unreferenced object 0xffff00000db613b8 (size 576):
  comm "systemd", pid 1, jiffies 4294987015
  hex dump (first 32 bytes):
    00 22 01 00 00 00 00 00 28 1c d5 c5 00 00 ff ff  ."......(.......
    10 e4 6c c0 00 00 ff ff d0 13 b6 0d 00 00 ff ff  ..l.............
  backtrace (crc 520d6e1c):
    kmemleak_alloc+0xb4/0xc4
    kmem_cache_alloc+0x288/0x2b0
    radix_tree_node_alloc.constprop.0+0x214/0x364
    idr_get_free+0x3d0/0x690
    idr_alloc_u32+0x120/0x280
    idr_alloc_cyclic+0xe8/0x1b4
    __kernfs_new_node+0x118/0x5a0
    kernfs_create_dir_ns+0x8c/0x1fc
    cgroup_create+0x1cc/0x8a0
    cgroup_mkdir+0x13c/0x90c
    kernfs_iop_mkdir+0x108/0x184
    vfs_mkdir+0x3c8/0x5f0
    do_mkdirat+0x218/0x290
    __arm64_sys_mkdirat+0xe0/0x140
    invoke_syscall.constprop.0+0x74/0x1e4
    do_el0_svc+0xd0/0x1dc

This is a transient leak that can be traced to radix_tree_shrink(): when
root->xa_head is set, kmemleak may have already started traversing the
radix tree. If this has happened, but kmemleak fails to scan the new
xa_head before it moves, kmemleak will see it as a leak until the radix
tree is scanned again.

Mark the new xa_head as a transient leak to prevent this false positive
report.

Signed-off-by: Jared Kangas <jkangas@redhat.com>
---
 lib/radix-tree.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 976b9bd02a1b5..79b3702a0cb54 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -509,6 +509,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
 			root_tag_clear(root, IDR_FREE);
 
+		/*
+		 * Kmemleak might report a false positive if it traverses the
+		 * tree while we're shrinking it, since the reference moves
+		 * from node->slots[0] to root->xa_head.
+		 */
+		if (radix_tree_is_internal_node(child))
+			kmemleak_transient_leak(entry_to_node(child));
+
 		/*
 		 * We have a dilemma here. The node's slot[0] must not be
 		 * NULLed in case there are concurrent lookups expecting to
-- 
2.49.0

Re: [PATCH] radix tree: fix kmemleak false positive in radix_tree_shrink()

[Andrew Morton]

On Wed, 14 May 2025 11:01:37 -0700 Jared Kangas <jkangas@redhat.com> wrote:

> Kmemleak periodically produces a false positive report that resembles
> the following:
> 
> unreferenced object 0xffff00000db613b8 (size 576):
>   comm "systemd", pid 1, jiffies 4294987015
>   hex dump (first 32 bytes):
>     00 22 01 00 00 00 00 00 28 1c d5 c5 00 00 ff ff  ."......(.......
>     10 e4 6c c0 00 00 ff ff d0 13 b6 0d 00 00 ff ff  ..l.............
>   backtrace (crc 520d6e1c):
>     kmemleak_alloc+0xb4/0xc4
>     kmem_cache_alloc+0x288/0x2b0
>     radix_tree_node_alloc.constprop.0+0x214/0x364
>     idr_get_free+0x3d0/0x690
>     idr_alloc_u32+0x120/0x280
>     idr_alloc_cyclic+0xe8/0x1b4
>     __kernfs_new_node+0x118/0x5a0
>     kernfs_create_dir_ns+0x8c/0x1fc
>     cgroup_create+0x1cc/0x8a0
>     cgroup_mkdir+0x13c/0x90c
>     kernfs_iop_mkdir+0x108/0x184
>     vfs_mkdir+0x3c8/0x5f0
>     do_mkdirat+0x218/0x290
>     __arm64_sys_mkdirat+0xe0/0x140
>     invoke_syscall.constprop.0+0x74/0x1e4
>     do_el0_svc+0xd0/0x1dc
> 
> This is a transient leak that can be traced to radix_tree_shrink(): when
> root->xa_head is set, kmemleak may have already started traversing the
> radix tree. If this has happened, but kmemleak fails to scan the new
> xa_head before it moves, kmemleak will see it as a leak until the radix
> tree is scanned again.
> 
> Mark the new xa_head as a transient leak to prevent this false positive
> report.
> 
> ...
>
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -509,6 +509,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
>  		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
>  			root_tag_clear(root, IDR_FREE);
>  
> +		/*
> +		 * Kmemleak might report a false positive if it traverses the
> +		 * tree while we're shrinking it, since the reference moves
> +		 * from node->slots[0] to root->xa_head.
> +		 */
> +		if (radix_tree_is_internal_node(child))
> +			kmemleak_transient_leak(entry_to_node(child));
> +

There is only one other caller of kmemleak_transient_leak().  Makes me
think that perhaps a more fundamental fix is needed.

So I'll queue it for testing for now, but I won't proceed further until
some further examination has occured.  Thanks.

Re: [PATCH] radix tree: fix kmemleak false positive in radix_tree_shrink()

[Jared Kangas]

Hi Andrew,

On Wed, May 14, 2025 at 03:16:05PM -0700, Andrew Morton wrote:
> On Wed, 14 May 2025 11:01:37 -0700 Jared Kangas <jkangas@redhat.com> wrote:
> 
> > Kmemleak periodically produces a false positive report that resembles
> > the following:
> > 
> > unreferenced object 0xffff00000db613b8 (size 576):
> >   comm "systemd", pid 1, jiffies 4294987015
> >   hex dump (first 32 bytes):
> >     00 22 01 00 00 00 00 00 28 1c d5 c5 00 00 ff ff  ."......(.......
> >     10 e4 6c c0 00 00 ff ff d0 13 b6 0d 00 00 ff ff  ..l.............
> >   backtrace (crc 520d6e1c):
> >     kmemleak_alloc+0xb4/0xc4
> >     kmem_cache_alloc+0x288/0x2b0
> >     radix_tree_node_alloc.constprop.0+0x214/0x364
> >     idr_get_free+0x3d0/0x690
> >     idr_alloc_u32+0x120/0x280
> >     idr_alloc_cyclic+0xe8/0x1b4
> >     __kernfs_new_node+0x118/0x5a0
> >     kernfs_create_dir_ns+0x8c/0x1fc
> >     cgroup_create+0x1cc/0x8a0
> >     cgroup_mkdir+0x13c/0x90c
> >     kernfs_iop_mkdir+0x108/0x184
> >     vfs_mkdir+0x3c8/0x5f0
> >     do_mkdirat+0x218/0x290
> >     __arm64_sys_mkdirat+0xe0/0x140
> >     invoke_syscall.constprop.0+0x74/0x1e4
> >     do_el0_svc+0xd0/0x1dc
> > 
> > This is a transient leak that can be traced to radix_tree_shrink(): when
> > root->xa_head is set, kmemleak may have already started traversing the
> > radix tree. If this has happened, but kmemleak fails to scan the new
> > xa_head before it moves, kmemleak will see it as a leak until the radix
> > tree is scanned again.
> > 
> > Mark the new xa_head as a transient leak to prevent this false positive
> > report.
> > 
> > ...
> >
> > --- a/lib/radix-tree.c
> > +++ b/lib/radix-tree.c
> > @@ -509,6 +509,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
> >  		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
> >  			root_tag_clear(root, IDR_FREE);
> >  
> > +		/*
> > +		 * Kmemleak might report a false positive if it traverses the
> > +		 * tree while we're shrinking it, since the reference moves
> > +		 * from node->slots[0] to root->xa_head.
> > +		 */
> > +		if (radix_tree_is_internal_node(child))
> > +			kmemleak_transient_leak(entry_to_node(child));
> > +
> 
> There is only one other caller of kmemleak_transient_leak().  Makes me
> think that perhaps a more fundamental fix is needed.
> 
> So I'll queue it for testing for now, but I won't proceed further until
> some further examination has occured.  Thanks.
> 

This patch actually breaks xarray and vma userland test compilation in
the same way Lorenzo pointed out in [1], and probably should be dropped
as well. If it sounds reasonable for v2, I can group this in with the
patch from [1] and the test compilation fix to keep the discussion in
one place. (In hindsight I should have sent them in the same series to
begin with.)

Sorry for the inconvenience caused by my oversight here.

[1]: https://lore.kernel.org/all/053ad5f9-3eee-486e-ac29-3104517b674a@lucifer.local/

Re: [PATCH] radix tree: fix kmemleak false positive in radix_tree_shrink()

[Catalin Marinas]

On Wed, May 14, 2025 at 03:16:05PM -0700, Andrew Morton wrote:
> On Wed, 14 May 2025 11:01:37 -0700 Jared Kangas <jkangas@redhat.com> wrote:
> > Mark the new xa_head as a transient leak to prevent this false positive
> > report.
> > 
> > ...
> >
> > --- a/lib/radix-tree.c
> > +++ b/lib/radix-tree.c
> > @@ -509,6 +509,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
> >  		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
> >  			root_tag_clear(root, IDR_FREE);
> >  
> > +		/*
> > +		 * Kmemleak might report a false positive if it traverses the
> > +		 * tree while we're shrinking it, since the reference moves
> > +		 * from node->slots[0] to root->xa_head.
> > +		 */
> > +		if (radix_tree_is_internal_node(child))
> > +			kmemleak_transient_leak(entry_to_node(child));
> > +
> 
> There is only one other caller of kmemleak_transient_leak().  Makes me
> think that perhaps a more fundamental fix is needed.

The other user is iova_depot_pop() where a struct iova_magazine object
is temporarily unreachable. But you have a point, we could try to change
the heuristics a bit to reduce such false positives. The only way to
guarantee is to use stop_machine() during scanning but that can take
minutes, so not really feasible.

We do have some heuristics as the checksum calculation that works well
for doubly-linked lists. However, when the reference to an object is
moved from one location to another while the object itself is not
updated, this won't be caught.

That said, the current logic updates the checksum when it was found
unreferenced (potential leak). If the object was referenced in
subsequent scans, the checksum remains intact, so minutes later it may
be seen again as a transient leak. Something like below should reduce
the transient leak reports (though not eliminate):

diff --git a/mm/kmemleak.c b/mm/kmemleak.c
index c12cef3eeb32..b1460c64f4b1 100644
--- a/mm/kmemleak.c
+++ b/mm/kmemleak.c
@@ -1408,6 +1408,12 @@ static void update_refs(struct kmemleak_object *object)
 		/* put_object() called when removing from gray_list */
 		WARN_ON(!get_object(object));
 		list_add_tail(&object->gray_list, &gray_list);
+		/*
+		 * Reset the checksum; the object must be unchanged between
+		 * two consecutive scans where it was unreferenced
+		 * (color_white()) in order to be reported as a leak.
+		 */
+		object->checksum = 0;
 	}
 }
 

-- 
Catalin