On 2024/4/17 00:03, Alex Williamson wrote:
On Fri, 12 Apr 2024 01:21:18 -0700
Yi Liu <yi.l.liu@xxxxxxxxx> wrote:
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 can help to achieve it.
Caller can check if a given ID is allocated or not by:
int id = 200, rc;
rc = ida_get_lowest(&ida, id, id);
if (rc == id)
//id 200 is used
else
//id 200 is not used
Caller can iterate all allocated IDs by:
int id = 0;
while (!ida_is_empty(&pasid_ida)) {
id = ida_get_lowest(pasid_ida, id, INT_MAX);
if (id < 0)
break;
//anything to do with the allocated ID
ida_free(pasid_ida, pasid);
}
Cc: Matthew Wilcox (Oracle) <willy@xxxxxxxxxxxxx>
Suggested-by: Jason Gunthorpe <jgg@xxxxxxxxxx>
Signed-off-by: Yi Liu <yi.l.liu@xxxxxxxxx>
---
include/linux/idr.h | 1 +
lib/idr.c | 67 +++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 68 insertions(+)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index da5f5fa4a3a6..1dae71d4a75d 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_get_lowest(struct ida *ida, unsigned int min, unsigned int max);
/**
* ida_alloc() - Allocate an unused ID.
diff --git a/lib/idr.c b/lib/idr.c
index da36054c3ca0..03e461242fe2 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_get_lowest - 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_get_lowest(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 flags;
+ void *entry;
+ int ret;
+
+ if (min >= INT_MAX)
+ return -EINVAL;
+ if (max >= INT_MAX)
+ max = INT_MAX;
+
Could these be made consistent with the test in ida_alloc_range(), ie:
if ((int)min < 0)
return -EINVAL;
if ((int)max < 0)
max = INT_MAX;
sure.
+ xa_lock_irqsave(&ida->xa, flags);
+
+ entry = xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT);
+ if (!entry) {
+ ret = -ENOTTY;
-ENOENT? Same for all below too.
I see.
+ goto err_unlock;
+ }
+
+ if (index > min / IDA_BITMAP_BITS)
+ offset = 0;
+ if (index * IDA_BITMAP_BITS + offset > max) {
+ ret = -ENOTTY;
+ goto err_unlock;
+ }
+
+ if (xa_is_value(entry)) {
+ unsigned long 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 -ENOTTY;
+
+ return index * IDA_BITMAP_BITS + bit;
+
+err_unlock:
+ xa_unlock_irqrestore(&ida->xa, flags);
+ return ret;
+}
+EXPORT_SYMBOL(ida_get_lowest);
The API is a bit awkward to me, I wonder if it might be helped with
some renaming and wrappers...
int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max);
ok.
bool ida_exists(struct ida *ida, unsigned int id)
{
return ida_find_first_range(ida, id, id) == id;
}
this does helps in next patch.
int ida_find_first(struct ida *ida)
{
return ida_find_first_range(ida, 0, ~0);
}
perhaps it can be added in future. This series has two usages. One is to
check if a given ID is allocated. This can be covered by your ida_exists().
Another usage is to loop each IDs, do detach and free. This can still use
the ida_find_first_range() like the example in the commit message. The
first loop starts from 0, and next would start from the last found ID.
This may be more efficient than starts from 0 in every loop.
_min and _max variations of the latter would align with existing
ida_alloc variants, but maybe no need to add them preemptively.
yes.
Possibly an ida_for_each() could be useful in the use case of
disassociating each id, but not required for the brute force iterative
method. Thanks,
yep. maybe we can start with the below code, no need for ida_for_each()
today.
int id = 0;
while (!ida_is_empty(&pasid_ida)) {
id = ida_find_first_range(pasid_ida, id, INT_MAX);
if (unlikely(WARN_ON(id < 0))
break;
iommufd_device_pasid_detach();
ida_free(pasid_ida, pasid);
}
+
/**
* ida_free() - Release an allocated ID.
* @ida: IDA handle.
--
Regards,
Yi Liu
