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

[Nickolai Zeldovich <nickolai@csail.mit.edu>]

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