[PATCH v1 0/3] ida: fix the allocation failure paths of ida_alloc_range()

[PATCH v1 0/3] ida: fix the allocation failure paths of ida_alloc_range()

[Nickolai Zeldovich]

These three patches fix what ida_alloc_range() does when its xas_store()
fails for want of a node, found while formally verifying the function
against the kernel binary, where its resource accounting could not be
established against the code as it is.

Patch 1: the bit set in a new bitmap before the failed store is not
cleared again, so a retry can store an ID that nobody owns (exact-ID
callers then get -ENOSPC for a free ID, and the chunk's bitmap can never
be freed).  Patch 2: the bitmap of the failed store is leaked, on the
-ENOMEM return and on a successful retry.  Patch 3: the node
preallocated by xas_nomem() is leaked on the "nospc:" exit and on the
-ENOMEM return at "alloc:".  These need an allocation failure under
memory pressure and, for two of them, a concurrent allocation on the
same IDA; they affect every ida_alloc_*() user, so they are tagged for
stable.

Patches 1 and 3 add tests to tools/testing/radix-tree/idr-test.c which
use the node cache callback of the user-space harness to run a second
allocation in the window where xas_nomem() has dropped the lock; they
fail without their fix.  The leaks of patch 2 cannot be reached in the
harness (it cannot fail a GFP_KERNEL node allocation or let a
GFP_NOWAIT kmalloc() succeed) and were reproduced with a user-space
copy of the function with fault injection at its four allocation sites.
The complete lib/test_ida.c suite and idr-test pass at XA_CHUNK_SHIFT 3
and 6, and in x86_64 and RISC-V defconfig kernels with CONFIG_TEST_IDA=y
booted under QEMU; lib/idr.o builds without warnings with W=1 and C=1
(sparse) on both architectures.

Nickolai Zeldovich (3):
  ida: clear the bit of a bitmap that ida_alloc_range() failed to store
  ida: free the bitmaps that ida_alloc_range() fails to store
  ida: free the preallocated node on the ida_alloc_range() failure paths

 lib/idr.c                           | 16 ++++--
 tools/testing/radix-tree/idr-test.c | 77 +++++++++++++++++++++++++++++
 tools/testing/radix-tree/test.h     |  4 ++
 3 files changed, 94 insertions(+), 3 deletions(-)


base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0

[PATCH v1 1/3] ida: clear the bit of a bitmap that ida_alloc_range() failed to store

[Nickolai Zeldovich]

ida_alloc_range() sets the requested bit in a new bitmap before it calls
xas_store().  When the store fails because xas_alloc() could not get a
node with GFP_NOWAIT, nothing is stored, but the bit stays set.  If the
bitmap is the one preallocated at the "alloc:" label, the retry after
xas_nomem() reuses it.  The lock was dropped in between, and if another
allocation stored a value entry for that chunk meanwhile, the retry
converts the value entry into the bitmap by writing word 0 only, so a
stale bit at position 64 or above survives into the stored bitmap.

The result is an ID which is marked as allocated but which nobody owns.
The retrying caller gets the next free ID instead of the one it asked
for, an exact-ID caller (ida_alloc_range(ida, id, id, gfp)) gets -ENOSPC
for an ID that nobody holds, and the bitmap of that chunk never becomes
empty, so ida_free() can never free it.

Clear the bit again when the store fails; it was never visible.

This was found while formally verifying ida_alloc_range() against the
kernel binary.  Add ida_check_retry_stale() to the
tools/testing/radix-tree harness: it runs a second allocation from the
node cache callback, which fires in the window where xas_nomem() has
dropped the lock.  Without the fix the caller gets ID 1101 instead of
1100 and the IDA is not empty after both IDs have been freed.

Fixes: f32f004cddf8 ("ida: Convert to XArray")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
 lib/idr.c                           |  2 ++
 tools/testing/radix-tree/idr-test.c | 53 +++++++++++++++++++++++++++++
 tools/testing/radix-tree/test.h     |  4 +++
 3 files changed, 59 insertions(+)

diff --git a/lib/idr.c b/lib/idr.c
index 69bee5369670..f298660f5c80 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -450,6 +450,8 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 			__set_bit(bit, bitmap->bitmap);
 		}
 		xas_store(&xas, bitmap);
+		if (xas_error(&xas) && !xa_is_value(bitmap))
+			__clear_bit(bit, bitmap->bitmap);
 	}
 out:
 	xas_unlock_irqrestore(&xas, flags);
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 945144e98507..f1e0be0e09ec 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -470,6 +470,58 @@ void ida_check_nomem(void)
 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 }
 
+/*
+ * Run a second allocation on the same IDA while ida_alloc_range() has
+ * dropped the lock in xas_nomem() to allocate a node.  In userspace every
+ * GFP_NOWAIT allocation fails, so an allocation in a chunk which has no
+ * node yet fails its first store and retries; the node cache callback runs
+ * before xas_nomem() allocates, with the lock dropped.
+ */
+static struct ida *window_ida;
+static unsigned int window_min;
+static int window_id;
+
+static void ida_window_alloc(void *unused)
+{
+	kmem_cache_set_callback(radix_tree_node_cachep, NULL);
+	kmem_cache_set_non_kernel(radix_tree_node_cachep, 1);
+	window_id = ida_alloc_min(window_ida, window_min, GFP_KERNEL);
+	kmem_cache_set_non_kernel(radix_tree_node_cachep, 0);
+}
+
+static int ida_alloc_window(struct ida *ida, unsigned int min,
+			    unsigned int max, unsigned int other)
+{
+	int id;
+
+	window_ida = ida;
+	window_min = other;
+	window_id = -1;
+	kmem_cache_set_callback(radix_tree_node_cachep, ida_window_alloc);
+	id = ida_alloc_range(ida, min, max, GFP_KERNEL);
+	kmem_cache_set_callback(radix_tree_node_cachep, NULL);
+	IDA_BUG_ON(ida, window_id != other);
+
+	return id;
+}
+
+/*
+ * A bit set in a bitmap whose store failed must not be stored by the retry
+ * once another allocation has put a value entry in that chunk.
+ */
+void ida_check_retry_stale(void)
+{
+	DEFINE_IDA(ida);
+	unsigned int min = IDA_BITMAP_BITS + BITS_PER_LONG + 12;
+	int id;
+
+	id = ida_alloc_window(&ida, min, ~0, IDA_BITMAP_BITS + 5);
+	IDA_BUG_ON(&ida, id != min);
+	ida_free(&ida, IDA_BITMAP_BITS + 5);
+	ida_free(&ida, id);
+	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
+}
+
 /*
  * Check handling of conversions between exceptional entries and full bitmaps.
  */
@@ -541,6 +593,7 @@ void user_ida_checks(void)
 	radix_tree_cpu_dead(1);
 
 	ida_check_nomem();
+	ida_check_retry_stale();
 	ida_check_conv_user();
 	ida_check_random();
 	ida_alloc_free_test();
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 7ef7067e942c..8ca50a58e138 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -48,6 +48,10 @@ void tree_verify_min_height(struct radix_tree_root *root, int maxindex);
 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
 
 extern int nr_allocated;
+extern struct kmem_cache *radix_tree_node_cachep;
+void kmem_cache_set_callback(struct kmem_cache *cachep,
+			     void (*callback)(void *));
+void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val);
 
 /* Normally private parts of lib/radix-tree.c */
 struct radix_tree_node *entry_to_node(void *ptr);
-- 
2.53.0

[PATCH v1 2/3] ida: free the bitmaps that ida_alloc_range() fails to store

[Nickolai Zeldovich]

When xas_store() in ida_alloc_range() fails with -ENOMEM, nothing has
been stored, but the function loses the bitmap it was about to store:

 - A bitmap allocated with GFP_NOWAIT under the lock is neither the
   preallocation "alloc" nor stored.  If xas_nomem() fails as well, the
   function returns -ENOMEM and leaks it.  If xas_nomem() succeeds, the
   retry overwrites the only pointer to it and allocates a second one,
   so the call succeeds and still leaks the first bitmap.

 - A preallocated bitmap whose store failed is not freed on the -ENOMEM
   return, because the exit path takes "bitmap == alloc" to mean that
   the preallocation was stored.

 - The value-to-bitmap conversion resets word 0 when its store fails
   and then loses the bitmap in the same two ways.

Each occurrence leaks a 128-byte struct ida_bitmap.  It takes a
GFP_NOWAIT radix_tree_node allocation failing right after a GFP_NOWAIT
kmalloc-128 allocation succeeded, which is what memory pressure looks
like to any ida_alloc_*() caller, such as create_worker() allocating
from worker_ida, get_anon_bdev() or the misc device minors.

Hand a bitmap whose store failed to "alloc", so that the retry reuses it
and the normal exit owns it, and free "alloc" on the error return
whether or not it is the bitmap of the failed store.

This was found while formally verifying ida_alloc_range() against the
kernel binary.  The tools/testing/radix-tree harness cannot fail a
GFP_KERNEL node allocation or let a GFP_NOWAIT kmalloc() succeed, so it
cannot reach these paths; a user-space copy of the function with fault
injection at its four allocation sites leaks one bitmap on each of the
three paths before this change and none after it, with the same return
values.

Fixes: f32f004cddf8 ("ida: Convert to XArray")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
 lib/idr.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index f298660f5c80..86c572e60f75 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -424,6 +424,7 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 		xas_store(&xas, bitmap);
 		if (xas_error(&xas)) {
 			bitmap->bitmap[0] = 0;
+			alloc = bitmap;
 			goto out;
 		}
 	}
@@ -450,8 +451,10 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 			__set_bit(bit, bitmap->bitmap);
 		}
 		xas_store(&xas, bitmap);
-		if (xas_error(&xas) && !xa_is_value(bitmap))
+		if (xas_error(&xas) && !xa_is_value(bitmap)) {
 			__clear_bit(bit, bitmap->bitmap);
+			alloc = bitmap;
+		}
 	}
 out:
 	xas_unlock_irqrestore(&xas, flags);
@@ -460,10 +463,12 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 		bit = min % IDA_BITMAP_BITS;
 		goto retry;
 	}
-	if (bitmap != alloc)
+	if (xas_error(&xas)) {
 		kfree(alloc);
-	if (xas_error(&xas))
 		return xas_error(&xas);
+	}
+	if (bitmap != alloc)
+		kfree(alloc);
 	return xas.xa_index * IDA_BITMAP_BITS + bit;
 alloc:
 	xas_unlock_irqrestore(&xas, flags);
-- 
2.53.0

[PATCH v1 3/3] ida: free the preallocated node on the ida_alloc_range() failure paths

[Nickolai Zeldovich]

When xas_store() in ida_alloc_range() fails for want of a node,
xas_nomem() allocates one into xas.xa_alloc and the function retries.
The retry either consumes that node in xas_store() or, if it reaches
"out:" without needing it, returns it through xas_nomem(), which calls
xas_destroy() when the state is not -ENOMEM.  Two exits do neither:

 - "nospc:", when the retry finds no free ID in [min, max] any more.
   The failed round stored nothing, so this means that another
   allocation took the IDs while the lock was dropped in xas_nomem();
   exact-ID callers, ida_alloc_range(ida, id, id, gfp), are the usual
   way to get there.

 - The -ENOMEM return at "alloc:", when the retry needs a bitmap and
   both the GFP_NOWAIT and the gfp allocation of it fail.

Each occurrence leaks a struct xa_node (576 bytes) from the
radix_tree_node cache.

Call xas_destroy() on both exits.  It is called with the lock dropped,
as xas_nomem() itself does, and it is a no-op when nothing was
preallocated.

This was found while formally verifying ida_alloc_range() against the
kernel binary.  Add ida_check_retry_nospc() to the
tools/testing/radix-tree harness: an exact-ID allocation whose first
store fails loses its ID to an allocation made in the window where
xas_nomem() has dropped the lock, for an ID in a value entry and for one
in a bitmap.  Without the fix the harness counts one node still
allocated after the IDA has been emptied.

Fixes: f32f004cddf8 ("ida: Convert to XArray")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
 lib/idr.c                           |  5 ++++-
 tools/testing/radix-tree/idr-test.c | 24 ++++++++++++++++++++++++
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/lib/idr.c b/lib/idr.c
index 86c572e60f75..468a9b7adb14 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -473,13 +473,16 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 alloc:
 	xas_unlock_irqrestore(&xas, flags);
 	alloc = kzalloc_obj(*bitmap, gfp);
-	if (!alloc)
+	if (!alloc) {
+		xas_destroy(&xas);
 		return -ENOMEM;
+	}
 	xas_set(&xas, min / IDA_BITMAP_BITS);
 	bit = min % IDA_BITMAP_BITS;
 	goto retry;
 nospc:
 	xas_unlock_irqrestore(&xas, flags);
+	xas_destroy(&xas);
 	kfree(alloc);
 	return -ENOSPC;
 }
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index f1e0be0e09ec..4b862f2080cf 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -522,6 +522,29 @@ void ida_check_retry_stale(void)
 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 }
 
+/*
+ * The node preallocated by xas_nomem() must be freed when the retry finds
+ * that another allocation took the only ID in range, whether that ID lives
+ * in a value entry or in a bitmap.
+ */
+void ida_check_retry_nospc(void)
+{
+	DEFINE_IDA(ida);
+	unsigned int ids[] = { IDA_BITMAP_BITS + 5, IDA_BITMAP_BITS + 63 };
+	int allocated, i, id;
+
+	rcu_barrier();
+	allocated = nr_allocated;
+	for (i = 0; i < ARRAY_SIZE(ids); i++) {
+		id = ida_alloc_window(&ida, ids[i], ids[i], ids[i]);
+		IDA_BUG_ON(&ida, id != -ENOSPC);
+		ida_free(&ida, ids[i]);
+		IDA_BUG_ON(&ida, !ida_is_empty(&ida));
+		rcu_barrier();
+		IDA_BUG_ON(&ida, nr_allocated != allocated);
+	}
+}
+
 /*
  * Check handling of conversions between exceptional entries and full bitmaps.
  */
@@ -594,6 +617,7 @@ void user_ida_checks(void)
 
 	ida_check_nomem();
 	ida_check_retry_stale();
+	ida_check_retry_nospc();
 	ida_check_conv_user();
 	ida_check_random();
 	ida_alloc_free_test();
-- 
2.53.0

Re: [PATCH v1 0/3] ida: fix the allocation failure paths of ida_alloc_range()

[Andrew Morton]

On Mon, 12 Oct 2026 20:27:00 -0400 Nickolai Zeldovich <nickolai@csail.mit.edu> wrote:

> These three patches fix what ida_alloc_range() does when its xas_store()
> fails for want of a node, found while formally verifying the function
> against the kernel binary, where its resource accounting could not be
> established against the code as it is.

Please teach your LLM about the first 32 lines of
Documentation/process/stable-kernel-rules.rst.  Seriously.

Please also tell it that when fixing a bug, it should fully describe
the userspace-visible runtime effects of that bug, especially when
proposing a -stable backport.

Thanks.