Re: [PATCH v3 1/4] ida: Add ida_find_first_range()

[Yi Liu]

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) <wi...@infradead.org>
Suggested-by: Jason Gunthorpe <j...@nvidia.com>
Signed-off-by: Yi Liu <yi.l....@intel.com>
---
  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