From: Yi Liu <yi.l.liu@intel.com>
To: alex.williamson@redhat.com
Cc: jgg@nvidia.com, yi.l.liu@intel.com, kevin.tian@intel.com,
eric.auger@redhat.com, kvm@vger.kernel.org,
chao.p.peng@linux.intel.com, zhenzhong.duan@intel.com,
willy@infradead.org, zhangfei.gao@linaro.org,
vasant.hegde@amd.com
Subject: [PATCH v9 1/5] ida: Add ida_find_first_range()
Date: Fri, 21 Mar 2025 11:01:39 -0700 [thread overview]
Message-ID: <20250321180143.8468-2-yi.l.liu@intel.com> (raw)
In-Reply-To: <20250321180143.8468-1-yi.l.liu@intel.com>
There is no helpers for user to check if a given ID is allocated or not,
neither a helper to loop all the allocated IDs in an IDA and do something
for cleanup. With the two needs, a helper to get the lowest allocated ID
of a range and two variants based on it.
Caller can check if a given ID is allocated or not by:
bool ida_exists(struct ida *ida, unsigned int id)
Caller can iterate all allocated IDs by:
int id;
while ((id = ida_find_first(&pasid_ida)) >= 0) {
//anything to do with the allocated ID
ida_free(pasid_ida, pasid);
}
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Suggested-by: Jason Gunthorpe <jgg@nvidia.com>
Reviewed-by: Jason Gunthorpe <jgg@nvidia.com>
Reviewed-by: Kevin Tian <kevin.tian@intel.com>
Acked-by: Matthew Wilcox (Oracle) <willy@infradead.org>
Signed-off-by: Yi Liu <yi.l.liu@intel.com>
---
include/linux/idr.h | 11 +++++++
lib/idr.c | 67 +++++++++++++++++++++++++++++++++++++++++++
lib/test_ida.c | 70 +++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 148 insertions(+)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index da5f5fa4a3a6..718f9b1b91af 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -257,6 +257,7 @@ struct ida {
int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
void ida_free(struct ida *, unsigned int id);
void ida_destroy(struct ida *ida);
+int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max);
/**
* ida_alloc() - Allocate an unused ID.
@@ -328,4 +329,14 @@ static inline bool ida_is_empty(const struct ida *ida)
{
return xa_empty(&ida->xa);
}
+
+static inline bool ida_exists(struct ida *ida, unsigned int id)
+{
+ return ida_find_first_range(ida, id, id) == id;
+}
+
+static inline int ida_find_first(struct ida *ida)
+{
+ return ida_find_first_range(ida, 0, ~0);
+}
#endif /* __IDR_H__ */
diff --git a/lib/idr.c b/lib/idr.c
index da36054c3ca0..e2adc457abb4 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -476,6 +476,73 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
}
EXPORT_SYMBOL(ida_alloc_range);
+/**
+ * ida_find_first_range - Get the lowest used ID.
+ * @ida: IDA handle.
+ * @min: Lowest ID to get.
+ * @max: Highest ID to get.
+ *
+ * Get the lowest used ID between @min and @max, inclusive. The returned
+ * ID will not exceed %INT_MAX, even if @max is larger.
+ *
+ * Context: Any context. Takes and releases the xa_lock.
+ * Return: The lowest used ID, or errno if no used ID is found.
+ */
+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 flags;
+ void *entry;
+ int ret;
+
+ if ((int)min < 0)
+ return -EINVAL;
+ if ((int)max < 0)
+ max = 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);
+
+ xa_unlock_irqrestore(&ida->xa, flags);
+
+ if (bit == size ||
+ index * IDA_BITMAP_BITS + bit > max)
+ return -ENOENT;
+
+ return index * IDA_BITMAP_BITS + bit;
+
+err_unlock:
+ xa_unlock_irqrestore(&ida->xa, flags);
+ return ret;
+}
+EXPORT_SYMBOL(ida_find_first_range);
+
/**
* ida_free() - Release an allocated ID.
* @ida: IDA handle.
diff --git a/lib/test_ida.c b/lib/test_ida.c
index c80155a1956d..63078f8dc13f 100644
--- a/lib/test_ida.c
+++ b/lib/test_ida.c
@@ -189,6 +189,75 @@ static void ida_check_bad_free(struct ida *ida)
IDA_BUG_ON(ida, !ida_is_empty(ida));
}
+/*
+ * Check ida_find_first_range() and varriants.
+ */
+static void ida_check_find_first(struct ida *ida)
+{
+ /* IDA is empty; all of the below should be not exist */
+ IDA_BUG_ON(ida, ida_exists(ida, 0));
+ IDA_BUG_ON(ida, ida_exists(ida, 3));
+ IDA_BUG_ON(ida, ida_exists(ida, 63));
+ IDA_BUG_ON(ida, ida_exists(ida, 1023));
+ IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
+
+ /* IDA contains a single value entry */
+ IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);
+ IDA_BUG_ON(ida, ida_exists(ida, 0));
+ IDA_BUG_ON(ida, !ida_exists(ida, 3));
+ IDA_BUG_ON(ida, ida_exists(ida, 63));
+ IDA_BUG_ON(ida, ida_exists(ida, 1023));
+ IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
+
+ IDA_BUG_ON(ida, ida_alloc_min(ida, 63, GFP_KERNEL) != 63);
+ IDA_BUG_ON(ida, ida_exists(ida, 0));
+ IDA_BUG_ON(ida, !ida_exists(ida, 3));
+ IDA_BUG_ON(ida, !ida_exists(ida, 63));
+ IDA_BUG_ON(ida, ida_exists(ida, 1023));
+ IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
+
+ /* IDA contains a single bitmap */
+ IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);
+ IDA_BUG_ON(ida, ida_exists(ida, 0));
+ IDA_BUG_ON(ida, !ida_exists(ida, 3));
+ IDA_BUG_ON(ida, !ida_exists(ida, 63));
+ IDA_BUG_ON(ida, !ida_exists(ida, 1023));
+ IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
+
+ /* IDA contains a tree */
+ IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);
+ IDA_BUG_ON(ida, ida_exists(ida, 0));
+ IDA_BUG_ON(ida, !ida_exists(ida, 3));
+ IDA_BUG_ON(ida, !ida_exists(ida, 63));
+ IDA_BUG_ON(ida, !ida_exists(ida, 1023));
+ IDA_BUG_ON(ida, !ida_exists(ida, (1 << 20) - 1));
+
+ /* Now try to find first */
+ IDA_BUG_ON(ida, ida_find_first(ida) != 3);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, -1, 2) != -EINVAL);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 2) != -ENOENT); // no used ID
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 3) != 3);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 1, 3) != 3);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 3, 3) != 3);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 2, 4) != 3);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 3) != -ENOENT); // min > max, fail
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 60) != -ENOENT); // no used ID
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 64) != 63);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 63, 63) != 63);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 64, 1026) != 1023);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, 1023) != 1023);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, (1 << 20) - 1) != 1023);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, 1024, (1 << 20) - 1) != (1 << 20) - 1);
+ IDA_BUG_ON(ida, ida_find_first_range(ida, (1 << 20), INT_MAX) != -ENOENT);
+
+ ida_free(ida, 3);
+ ida_free(ida, 63);
+ ida_free(ida, 1023);
+ ida_free(ida, (1 << 20) - 1);
+
+ IDA_BUG_ON(ida, !ida_is_empty(ida));
+}
+
static DEFINE_IDA(ida);
static int ida_checks(void)
@@ -202,6 +271,7 @@ static int ida_checks(void)
ida_check_max(&ida);
ida_check_conv(&ida);
ida_check_bad_free(&ida);
+ ida_check_find_first(&ida);
printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
return (tests_run != tests_passed) ? 0 : -EINVAL;
--
2.34.1
next prev parent reply other threads:[~2025-03-21 18:01 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-03-21 18:01 [PATCH v9 0/5] vfio-pci support pasid attach/detach Yi Liu
2025-03-21 18:01 ` Yi Liu [this message]
2025-03-21 18:01 ` [PATCH v9 2/5] vfio-iommufd: Support pasid [at|de]tach for physical VFIO devices Yi Liu
2025-03-21 18:01 ` [PATCH v9 3/5] vfio: VFIO_DEVICE_[AT|DE]TACH_IOMMUFD_PT support pasid Yi Liu
2025-03-21 18:01 ` [PATCH v9 4/5] iommufd: Extend IOMMU_GET_HW_INFO to report PASID capability Yi Liu
2025-03-21 18:01 ` [PATCH v9 5/5] iommufd/selftest: Add coverage for reporting max_pasid_log2 via IOMMU_HW_INFO Yi Liu
2025-03-21 20:29 ` Nicolin Chen
2025-03-25 13:25 ` [PATCH v9 0/5] vfio-pci support pasid attach/detach Jason Gunthorpe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250321180143.8468-2-yi.l.liu@intel.com \
--to=yi.l.liu@intel.com \
--cc=alex.williamson@redhat.com \
--cc=chao.p.peng@linux.intel.com \
--cc=eric.auger@redhat.com \
--cc=jgg@nvidia.com \
--cc=kevin.tian@intel.com \
--cc=kvm@vger.kernel.org \
--cc=vasant.hegde@amd.com \
--cc=willy@infradead.org \
--cc=zhangfei.gao@linaro.org \
--cc=zhenzhong.duan@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.