On 2024/9/12 23:11, Matthew Wilcox wrote:
On Thu, Sep 12, 2024 at 06:17:26AM -0700, Yi Liu 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 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@xxxxxxxxxxxxx>
Suggested-by: Jason Gunthorpe <jgg@xxxxxxxxxx>
Signed-off-by: Yi Liu <yi.l.liu@xxxxxxxxx>
---
include/linux/idr.h | 11 ++++++++
lib/idr.c | 67 +++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 78 insertions(+)
No test cases for the test suite? ;-(
let me add something like the below. :)
diff --git a/lib/test_ida.c b/lib/test_ida.c
index c80155a1956d..d89554ff5719 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 +270,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;
--
Regards,
Yi Liu
