[PATCH v3 0/2] lib/idr: Fixes for infinite loop and memory leak

[PATCH v3 0/2] lib/idr: Fixes for infinite loop and memory leak

[Josh Law]

This series includes two fixes for the IDR and IDA APIs, along with
their corresponding test cases as requested by reviewers.

1. Fix an infinite loop condition in idr_get_next() that occurs when
   iterating over an ID > INT_MAX.
2. Fix a memory leak in ida_alloc_range() where an intermediate
   allocated bitmap is not freed if a subsequent XArray insertion fails.

Both fixes update tools/testing/radix-tree/idr-test.c to ensure the
error paths are covered by the test suite.

Changes since v2:
- Added `idr-test.c` updates to both commits to formally test the fix conditions.

Josh Law (2):
  lib/idr: fix infinite loop in idr_get_next()
  lib/idr: fix memory leak in ida_alloc_range() error path

 lib/idr.c                           |  4 +++-
 tools/testing/radix-tree/idr-test.c | 19 ++++++++++++++++++-
 2 files changed, 21 insertions(+), 2 deletions(-)

-- 
2.34.1

[PATCH v3 1/2] lib/idr: fix infinite loop in idr_get_next()

[Josh Law]

In idr_get_next(), if the returned id from idr_get_next_ul() is greater
than INT_MAX, the function issues a warning and returns NULL without
updating the *nextid pointer. This causes a soft lockup for any caller
iterating over an IDR (e.g. via idr_for_each_entry) because they will
receive NULL, fail to advance their index, and repeatedly query the same
state forever.

Fix this by setting *nextid to INT_MAX when the bounds check fails,
ensuring the caller's iteration will terminate.

Also update the idr_get_next() test case in the radix-tree test suite
to expect INT_MAX instead of 0 when hitting this condition.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/idr.c                           | 4 +++-
 tools/testing/radix-tree/idr-test.c | 2 +-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index f25bd2b9e9a4..07098eb4ddc3 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -268,8 +268,10 @@ void *idr_get_next(struct idr *idr, int *nextid)
 	unsigned long id = *nextid;
 	void *entry = idr_get_next_ul(idr, &id);
 
-	if (WARN_ON_ONCE(id > INT_MAX))
+	if (WARN_ON_ONCE(id > INT_MAX)) {
+		*nextid = INT_MAX;
 		return NULL;
+	}
 	*nextid = id;
 	return entry;
 }
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 945144e98507..bf6a0da6a50a 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -213,7 +213,7 @@ void idr_u32_test1(struct idr *idr, u32 handle)
 	ptr = idr_get_next(idr, &sid);
 	if (id > INT_MAX) {
 		BUG_ON(ptr != NULL);
-		BUG_ON(sid != 0);
+		BUG_ON(sid != INT_MAX);
 	} else {
 		BUG_ON(ptr != DUMMY_PTR);
 		BUG_ON(sid != id);
-- 
2.34.1

Re: [PATCH v3 1/2] lib/idr: fix infinite loop in idr_get_next()

[Andrew Morton]

On Thu, 12 Mar 2026 18:19:47 +0000 Josh Law <hlcj1234567@gmail.com> wrote:

> In idr_get_next(), if the returned id from idr_get_next_ul() is greater
> than INT_MAX, the function issues a warning and returns NULL without
> updating the *nextid pointer. This causes a soft lockup for any caller
> iterating over an IDR (e.g. via idr_for_each_entry) because they will
> receive NULL, fail to advance their index, and repeatedly query the same
> state forever.

This assumes that the idr_get_next() caller ignores the NULL return and
just keeps on looping.  Isn't that a caller bug and if so, do we need
to defend against it here?

Re: [PATCH v3 1/2] lib/idr: fix infinite loop in idr_get_next()

[Josh Law]

12 Mar 2026 20:55:15 Andrew Morton <akpm@linux-foundation.org>:

> On Thu, 12 Mar 2026 18:19:47 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
>
>> In idr_get_next(), if the returned id from idr_get_next_ul() is greater
>> than INT_MAX, the function issues a warning and returns NULL without
>> updating the *nextid pointer. This causes a soft lockup for any caller
>> iterating over an IDR (e.g. via idr_for_each_entry) because they will
>> receive NULL, fail to advance their index, and repeatedly query the same
>> state forever.
>
> This assumes that the idr_get_next() caller ignores the NULL return and
> just keeps on looping.  Isn't that a caller bug and if so, do we need
> to defend against it here?

The risk isn't just a single loop failure; it's that idr_get_next() breaks the 'forward-progress' guarantee of the iterator.
In macros like idr_for_each_entry_continue, if idr_get_next() returns NULL without advancing the pointer, the caller is left in a permanent trap. Any attempt to resume or retry the iteration results in an infinite loop of the same warning because the index is never incremented past the problematic ID.
Advancing the pointer ensures the infrastructure is robust against these 'soft lockups', even if the caller's error handling is imperfect..

Re: [PATCH v3 1/2] lib/idr: fix infinite loop in idr_get_next()

[Josh Law]

12 Mar 2026 20:57:48 Josh Law <hlcj1234567@gmail.com>:

> 12 Mar 2026 20:55:15 Andrew Morton <akpm@linux-foundation.org>:
>
>> On Thu, 12 Mar 2026 18:19:47 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
>>
>>> In idr_get_next(), if the returned id from idr_get_next_ul() is greater
>>> than INT_MAX, the function issues a warning and returns NULL without
>>> updating the *nextid pointer. This causes a soft lockup for any caller
>>> iterating over an IDR (e.g. via idr_for_each_entry) because they will
>>> receive NULL, fail to advance their index, and repeatedly query the same
>>> state forever.
>>
>> This assumes that the idr_get_next() caller ignores the NULL return and
>> just keeps on looping.  Isn't that a caller bug and if so, do we need
>> to defend against it here?
>
> The risk isn't just a single loop failure; it's that idr_get_next() breaks the 'forward-progress' guarantee of the iterator.
> In macros like idr_for_each_entry_continue, if idr_get_next() returns NULL without advancing the pointer, the caller is left in a permanent trap. Any attempt to resume or retry the iteration results in an infinite loop of the same warning because the index is never incremented past the problematic ID.
> Advancing the pointer ensures the infrastructure is robust against these 'soft lockups', even if the caller's error handling is imperfect..

This most definitely needs to be merged.


V/R

[PATCH v3 2/2] lib/idr: fix memory leak in ida_alloc_range() error path

[Josh Law]

In ida_alloc_range(), if the XArray operation encounters an error
(e.g., -ENOSPC) during allocation, the function exits early via
return xas_error(&xas). However, if an intermediate `alloc` bitmap
was allocated via kzalloc() earlier in the function but the XArray
insertion failed, the error path returns without freeing `alloc`.

Reorder the error handling to ensure `alloc` is properly freed when
an XArray error occurs.

Also add a test case in idr-test to ensure coverage of the error
path in the IDA allocation logic.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 tools/testing/radix-tree/idr-test.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index bf6a0da6a50a..f4c3a5ed4ce1 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -543,6 +543,7 @@ void user_ida_checks(void)
 	ida_check_nomem();
 	ida_check_conv_user();
 	ida_check_random();
+	ida_check_leak();
 	ida_alloc_free_test();
 
 	radix_tree_cpu_dead(1);
@@ -556,6 +557,22 @@ static void *ida_random_fn(void *arg)
 	return NULL;
 }
 
+/*
+ * Check that an XArray error does not leak the allocated bitmap.
+ */
+static void ida_check_leak(void)
+{
+	DEFINE_IDA(ida);
+
+	/* Allocate up to 128 to ensure we need a new bitmap */
+	ida_alloc_range(&ida, 0, 128, GFP_KERNEL);
+	
+	/* Force a failure by providing an invalid range */
+	ida_alloc_range(&ida, 0, 0, GFP_KERNEL);
+	
+	ida_destroy(&ida);
+}
+
 static void *ida_leak_fn(void *arg)
 {
 	struct ida *ida = arg;
-- 
2.34.1

Re: [PATCH v3 2/2] lib/idr: fix memory leak in ida_alloc_range() error path

[kernel test robot]

:::::: 
:::::: Manual check reason: "low confidence bisect report"
:::::: 

BCC: lkp@intel.com
CC: oe-kbuild-all@lists.linux.dev
In-Reply-To: <20260312181948.20020-3-objecting@objecting.org>
References: <20260312181948.20020-3-objecting@objecting.org>
TO: Josh Law <hlcj1234567@gmail.com>
TO: Matthew Wilcox <willy@infradead.org>
TO: Andrew Morton <akpm@linux-foundation.org>
CC: Linux Memory Management List <linux-mm@kvack.org>
CC: linux-fsdevel@vger.kernel.org
CC: linux-kernel@vger.kernel.org
CC: Josh Law <objecting@objecting.org>

Hi Josh,

kernel test robot noticed the following build errors:

[auto build test ERROR on akpm-mm/mm-nonmm-unstable]
[also build test ERROR on akpm-mm/mm-everything linus/master v7.0-rc3 next-20260312]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Josh-Law/lib-idr-fix-infinite-loop-in-idr_get_next/20260313-143607
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20260312181948.20020-3-objecting%40objecting.org
patch subject: [PATCH v3 2/2] lib/idr: fix memory leak in ida_alloc_range() error path
:::::: branch date: 74 minutes ago
:::::: commit date: 74 minutes ago
config: arm64-allnoconfig-bpf (https://download.01.org/0day-ci/archive/20260313/202603130809.cCY2uVmK-lkp@intel.com/config)
compiler: aarch64-linux-gnu-gcc (Debian 14.2.0-19) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260313/202603130809.cCY2uVmK-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/r/202603130809.cCY2uVmK-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   idr-test.c: In function 'user_ida_checks':
>> idr-test.c:546:9: error: implicit declaration of function 'ida_check_leak'; did you mean 'ida_check_leaf'? [-Wimplicit-function-declaration]
     546 |         ida_check_leak();
         |         ^~~~~~~~~~~~~~
         |         ida_check_leaf
   idr-test.c: At top level:
>> idr-test.c:563:13: warning: conflicting types for 'ida_check_leak'; have 'void(void)'
     563 | static void ida_check_leak(void)
         |             ^~~~~~~~~~~~~~
>> idr-test.c:563:13: error: static declaration of 'ida_check_leak' follows non-static declaration
   idr-test.c:546:9: note: previous implicit declaration of 'ida_check_leak' with type 'void(void)'
     546 |         ida_check_leak();
         |         ^~~~~~~~~~~~~~
>> idr-test.c:563:13: warning: 'ida_check_leak' defined but not used [-Wunused-function]
     563 | static void ida_check_leak(void)
         |             ^~~~~~~~~~~~~~

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki