From nobody Thu Apr 9 15:44:02 2026 Received: from mail-qk1-f169.google.com (mail-qk1-f169.google.com [209.85.222.169]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 160AD33689D for ; Fri, 6 Mar 2026 20:30:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1772829051; cv=none; b=BGtWAkJPS4Y15r6q8GfWwQD28xl9LUNqhATbtKmF05scUgjhPS7KiFLYPQdR4rVmd1SUx6ZGI96hQRxycds+w1775vO3NLfpufIkp1dD61ozAXRodorhifQ+LEKAx+7LE6WZ32ZP0SED6Iw6tQcsquOysy9y/juqY6vM9ZfpNSs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1772829051; c=relaxed/simple; bh=YmC+F54J3lrxGj0/scpVc7eZoatE1MdmYUym4wBHbzI=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=TnC0DWCflGHAxpg2+9RDPOGMglPgCFu/TINXfSjISyNUR2AbMhc7EgiwpS6VMQUctpe+cgzntkubKzK9N74wIo1zJRu+RpVYaiaioKcEDYEZzqhi14467L9+0m7259jVML8XcNv4cVjx/bPobUV1p/XYSiqbPfNszG+CKE13D+8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Lf5sZqK9; arc=none smtp.client-ip=209.85.222.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Lf5sZqK9" Received: by mail-qk1-f169.google.com with SMTP id af79cd13be357-8cbc593a67aso912090685a.2 for ; Fri, 06 Mar 2026 12:30:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1772829049; x=1773433849; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=NAflFpld1ziWQP59fOhP77lxkMaSDWfKofqGmD46Gx4=; b=Lf5sZqK9/7m96dbDRoGxg/M7OgI/WMvK46CO/B4zeUuStcf8eh7OB8NCGvWaY4hw8N W4k8BImGhBswleV5SYBjYb7txk+0desJ3ZW6EHI1WwcywJszHZBad52q84NaSeVUlZ+0 T536NqXhulgS0npMPIBunsZHsjJBlfQtyN/whk5I1dsbulvd9zvP82dh2EiMRMQ7nhHJ Gd7AUbctS4zoz4GQzkoD0NaOiFCwDmAc5Zj+txX50pPYlGPpF5Kl5A1ay54EYptFuaVs 4GfbzEjN7Jk9gZqbFK6h4CKfbPffUt302N/RtX+G7YitZY5OgGhBaGj9uMUS9H6eQh44 pxcw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1772829049; x=1773433849; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=NAflFpld1ziWQP59fOhP77lxkMaSDWfKofqGmD46Gx4=; b=E3q/xmgDoxsXK9WmWDX9PkBfAMLsOJjD69vnlLSwIWdAcbiWxYjj6zeSJ1nXXGpI3X eq/JY+8oJcNd+91oWo/ITsv7zxeOGOyHktHJpJz+tNAM2AaXifgduIjurLrz/phZUDIJ FjCMX3UiLiTV3mECnRxDOPg6JFyxD2y/IlDlIlKqHj5Cvr9DDaX0V3Vr2hQjKEQtmaLj zjm5C9BszD4GwdOJ+wVFzP9bxfF0Gk+Vzbgwn/vEVwZTcocD6CFDP21AhqlKBk3jYPyQ shc8bAGVgQ+90RlyQig3hU/wzCHzIl+a432mzaAr45ExMZQpccAIZav/YR0FD5FEVo/6 5rHA== X-Forwarded-Encrypted: i=1; AJvYcCVe5dPZFJtE8Yjz+JyvjmEfbP3479AzLJ5REQA4bw2DJoqw0R1mBM/u9nQOquJSJT1dfzFlGfxbGRTweps=@vger.kernel.org X-Gm-Message-State: AOJu0YyZyLfx4gje77197dhLRUZshGFUdzVAXEZzzSnlhQpPVKnPNyMw WQKiPSMnCMKIXd0xGExHqeF4AQkRJC5n8TUmAmE3mZbeFI20N6FkxGG2 X-Gm-Gg: ATEYQzyhP7qm7+lATLzbd8Xda8r+V1IEHAAMo80dpzDuu5LgsHXLWvUSuQyX+BN38Jp xe229A1QaBSYPCBh9yiRFfAkAt3LtPwudoSp6SLSoVOMvapfYiUdlxesjlUxB1cjuunTW4S3jii 3kq8z532r7ZBz7+4aI2MkMXl5lEIpTuCY+2FtM9bNf32Fh+J+6iqiSetxxPyo8i5FebHZ9XFn57 My5VubJD0XvpjTs/NiHMVLN73x1qTJnohiZusHNaMMFpIH7x1XQzp73CigOnYZzIx7YIZtjp+X2 LdTR6nYs5MoHyA7ZPx0KI+jjBIMO03VbMQuWRaH4heb5nU50U6Go7wBDrPVC9vcwTLUDrLWmh+M j1DmCg/dn/gLH/uFWh/ot5bz8RHktno1lQroqEYuP5OmwDz7wP+piwqrFm9Km2lQ+eP1K4Ud+d6 YAyjtHcXB9M+jnS6YlZLeyxjPaToumD/fsABNgBs9fk0i7V8Iv3rZTer9FaCXQlhTyb8u1gx0Rh U7b X-Received: by 2002:a05:620a:468a:b0:8ca:2baa:76e with SMTP id af79cd13be357-8cd6d35b59amr471988985a.19.1772829048832; Fri, 06 Mar 2026 12:30:48 -0800 (PST) Received: from instance-20260207-1316.vcn12250046.oraclevcn.com ([150.136.248.187]) by smtp.gmail.com with ESMTPSA id af79cd13be357-8cd6f53b83esm183253785a.29.2026.03.06.12.30.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 06 Mar 2026 12:30:48 -0800 (PST) From: Josh Law X-Google-Original-From: Josh Law To: Matthew Wilcox , Andrew Morton Cc: Jason Gunthorpe , Kevin Tian , Yi Liu , linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Josh Law , Jason Gunthorpe Subject: [PATCH v2] lib/idr: fix ida_find_first_range() missing IDs across chunk boundaries Date: Fri, 6 Mar 2026 20:30:47 +0000 Message-ID: <20260306203047.2821852-1-objecting@objecting.org> X-Mailer: git-send-email 2.43.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Josh Law 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. Fixes: 7fe6b987166b ("ida: Add ida_find_first_range()") Cc: Yi Liu Cc: Jason Gunthorpe Cc: Jason Gunthorpe Signed-off-by: Josh Law --- lib/idr.c | 55 ++++++++++++++++++++++---------------------------- lib/test_ida.c | 14 +++++++++++++ 2 files changed, 38 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 =3D min / IDA_BITMAP_BITS; unsigned int offset =3D min % IDA_BITMAP_BITS; unsigned long *addr, size, bit; - unsigned long tmp =3D 0; + unsigned long tmp; unsigned long flags; void *entry; - int ret; =20 if ((int)min < 0) return -EINVAL; @@ -508,40 +507,34 @@ int ida_find_first_range(struct ida *ida, unsigned in= t min, unsigned int max) xa_lock_irqsave(&ida->xa, flags); =20 entry =3D xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT); - if (!entry) { - ret =3D -ENOENT; - goto err_unlock; - } - - if (index > min / IDA_BITMAP_BITS) - offset =3D 0; - if (index * IDA_BITMAP_BITS + offset > max) { - ret =3D -ENOENT; - goto err_unlock; - } - - if (xa_is_value(entry)) { - tmp =3D xa_to_value(entry); - addr =3D &tmp; - size =3D BITS_PER_XA_VALUE; - } else { - addr =3D ((struct ida_bitmap *)entry)->bitmap; - size =3D IDA_BITMAP_BITS; - } - - bit =3D find_next_bit(addr, size, offset); + while (entry) { + if (index > min / IDA_BITMAP_BITS) + offset =3D 0; + if (index * IDA_BITMAP_BITS + offset > max) + break; =20 - xa_unlock_irqrestore(&ida->xa, flags); + if (xa_is_value(entry)) { + tmp =3D xa_to_value(entry); + addr =3D &tmp; + size =3D BITS_PER_XA_VALUE; + } else { + addr =3D ((struct ida_bitmap *)entry)->bitmap; + size =3D IDA_BITMAP_BITS; + } =20 - if (bit =3D=3D size || - index * IDA_BITMAP_BITS + bit > max) - return -ENOENT; + bit =3D find_next_bit(addr, size, offset); + if (bit < size && + index * IDA_BITMAP_BITS + bit <=3D max) { + xa_unlock_irqrestore(&ida->xa, flags); + return index * IDA_BITMAP_BITS + bit; + } =20 - return index * IDA_BITMAP_BITS + bit; + entry =3D xa_find_after(&ida->xa, &index, + max / IDA_BITMAP_BITS, XA_PRESENT); + } =20 -err_unlock: xa_unlock_irqrestore(&ida->xa, flags); - return ret; + return -ENOENT; } EXPORT_SYMBOL(ida_find_first_range); =20 diff --git a/lib/test_ida.c b/lib/test_ida.c index 63078f8dc13f..d242549e16b6 100644 --- a/lib/test_ida.c +++ b/lib/test_ida.c @@ -256,6 +256,20 @@ static void ida_check_find_first(struct ida *ida) ida_free(ida, (1 << 20) - 1); =20 IDA_BUG_ON(ida, !ida_is_empty(ida)); + + /*=20 + * Test cross-chunk search. + * Allocate ID in chunk 0 and ID in chunk 1. + * Search for ID >=3D 1. min=3D1 maps to chunk 0. Chunk 0 has no IDs >=3D= 1. + * It should continue to chunk 1 and return 1024. + */ + IDA_BUG_ON(ida, ida_alloc_min(ida, 0, GFP_KERNEL) !=3D 0); + IDA_BUG_ON(ida, ida_alloc_min(ida, 1024, GFP_KERNEL) !=3D 1024); + IDA_BUG_ON(ida, ida_find_first_range(ida, 1, INT_MAX) !=3D 1024); + ida_free(ida, 0); + ida_free(ida, 1024); + + IDA_BUG_ON(ida, !ida_is_empty(ida)); } =20 static DEFINE_IDA(ida); --=20 2.43.0