[PATCH] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries

[PATCH] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries

[Josh Law]

From: Josh Law <objecting@objecting.org>

ida_find_first_range() only examines the first XArray entry returned by
xa_find(). If that entry does not contain a set bit at or above the
requested offset, the function returns -ENOENT without searching
subsequent entries, even though later chunks may contain allocated IDs
within the requested range.

For example, a DRM driver using IDA to manage connector IDs may allocate
IDs across multiple 1024-bit IDA chunks. If early IDs are freed and the
driver calls ida_find_first_range() with a min that falls into a
sparsely populated first chunk, valid IDs in higher chunks are silently
missed. This can cause the driver to incorrectly conclude no connectors
exist in the queried range, leading to stale connector state or failed
hotplug detection.

Fix this by looping over xa_find()/xa_find_after() to continue searching
subsequent entries when the current one has no matching bit.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/idr.c | 55 ++++++++++++++++++++++++-------------------------------
 1 file changed, 24 insertions(+), 31 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 69bee5369670..1649f41016e7 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -495,10 +495,9 @@ int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max)
 	unsigned long index = min / IDA_BITMAP_BITS;
 	unsigned int offset = min % IDA_BITMAP_BITS;
 	unsigned long *addr, size, bit;
-	unsigned long tmp = 0;
+	unsigned long tmp;
 	unsigned long flags;
 	void *entry;
-	int ret;
 
 	if ((int)min < 0)
 		return -EINVAL;
@@ -508,40 +507,34 @@ int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max)
 	xa_lock_irqsave(&ida->xa, flags);
 
 	entry = xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT);
-	if (!entry) {
-		ret = -ENOENT;
-		goto err_unlock;
-	}
-
-	if (index > min / IDA_BITMAP_BITS)
-		offset = 0;
-	if (index * IDA_BITMAP_BITS + offset > max) {
-		ret = -ENOENT;
-		goto err_unlock;
-	}
-
-	if (xa_is_value(entry)) {
-		tmp = xa_to_value(entry);
-		addr = &tmp;
-		size = BITS_PER_XA_VALUE;
-	} else {
-		addr = ((struct ida_bitmap *)entry)->bitmap;
-		size = IDA_BITMAP_BITS;
-	}
-
-	bit = find_next_bit(addr, size, offset);
+	while (entry) {
+		if (index > min / IDA_BITMAP_BITS)
+			offset = 0;
+		if (index * IDA_BITMAP_BITS + offset > max)
+			break;
 
-	xa_unlock_irqrestore(&ida->xa, flags);
+		if (xa_is_value(entry)) {
+			tmp = xa_to_value(entry);
+			addr = &tmp;
+			size = BITS_PER_XA_VALUE;
+		} else {
+			addr = ((struct ida_bitmap *)entry)->bitmap;
+			size = IDA_BITMAP_BITS;
+		}
 
-	if (bit == size ||
-	    index * IDA_BITMAP_BITS + bit > max)
-		return -ENOENT;
+		bit = find_next_bit(addr, size, offset);
+		if (bit < size &&
+		    index * IDA_BITMAP_BITS + bit <= max) {
+			xa_unlock_irqrestore(&ida->xa, flags);
+			return index * IDA_BITMAP_BITS + bit;
+		}
 
-	return index * IDA_BITMAP_BITS + bit;
+		entry = xa_find_after(&ida->xa, &index,
+				      max / IDA_BITMAP_BITS, XA_PRESENT);
+	}
 
-err_unlock:
 	xa_unlock_irqrestore(&ida->xa, flags);
-	return ret;
+	return -ENOENT;
 }
 EXPORT_SYMBOL(ida_find_first_range);
 
-- 
2.43.0

Re: [PATCH] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries

[Matthew Wilcox]

On Fri, Mar 06, 2026 at 08:03:19PM +0000, Josh Law wrote:
> ida_find_first_range() only examines the first XArray entry returned by
> xa_find(). If that entry does not contain a set bit at or above the
> requested offset, the function returns -ENOENT without searching
> subsequent entries, even though later chunks may contain allocated IDs
> within the requested range.

Can I trouble you to add a test to lib/test_ida.c to demonstrate the
problem (and that it's fixed, and that it doesn't come back)?

Also this needs a Fixes: line.  I suggest 7fe6b987166b is the commit
it's fixing.  Add Jason and Yi Liu as well as the author and committer
of that patch.

Re: [PATCH] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries

[Josh Law]

6 Mar 2026 20:15:29 Matthew Wilcox <willy@infradead.org>:

> On Fri, Mar 06, 2026 at 08:03:19PM +0000, Josh Law wrote:
>> ida_find_first_range() only examines the first XArray entry returned by
>> xa_find(). If that entry does not contain a set bit at or above the
>> requested offset, the function returns -ENOENT without searching
>> subsequent entries, even though later chunks may contain allocated IDs
>> within the requested range.
>
> Can I trouble you to add a test to lib/test_ida.c to demonstrate the
> problem (and that it's fixed, and that it doesn't come back)?
>
> Also this needs a Fixes: line.  I suggest 7fe6b987166b is the commit
> it's fixing.  Add Jason and Yi Liu as well as the author and committer
> of that patch.

Okay, you mind if I put the modifications to test_ida.c on the same commit? Or would you like it on another commit

V/R


Josh law

Re: [PATCH] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries

[Matthew Wilcox]

On Fri, Mar 06, 2026 at 08:25:42PM +0000, Josh Law wrote:
> 6 Mar 2026 20:15:29 Matthew Wilcox <willy@infradead.org>:
> 
> > On Fri, Mar 06, 2026 at 08:03:19PM +0000, Josh Law wrote:
> >> ida_find_first_range() only examines the first XArray entry returned by
> >> xa_find(). If that entry does not contain a set bit at or above the
> >> requested offset, the function returns -ENOENT without searching
> >> subsequent entries, even though later chunks may contain allocated IDs
> >> within the requested range.
> >
> > Can I trouble you to add a test to lib/test_ida.c to demonstrate the
> > problem (and that it's fixed, and that it doesn't come back)?
> >
> > Also this needs a Fixes: line.  I suggest 7fe6b987166b is the commit
> > it's fixing.  Add Jason and Yi Liu as well as the author and committer
> > of that patch.
> 
> Okay, you mind if I put the modifications to test_ida.c on the same commit? Or would you like it on another commit

I like it as part of the same commit (as 7fe6b987166b did), but honestly
I'm just happy to get improvements to the test suite no matter how they
come.