[xen staging] xen/bitops: Introduce for_each_set_bit()

[patchbot@xxxxxxx]

commit ed26376f20bffc8b542e2434a2643a1d788012d5
Author:     Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
AuthorDate: Wed Jun 19 15:46:47 2024 +0100
Commit:     Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CommitDate: Fri Aug 23 21:50:57 2024 +0100

    xen/bitops: Introduce for_each_set_bit()
    
    The prior version (renamed to bitmap_for_each()) was inefficeint when used
    over a scalar, but this is the more common usage even before accounting for
    the many opencoded forms.
    
    Introduce a new version which operates on scalars only and does so without
    spilling them to memory.  This in turn requires the addition of a 
type-generic
    form of ffs().
    
    Add testing for the new construct alongside the ffs/fls testing.
    
    Signed-off-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
    Reviewed-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/bitops.c      | 29 +++++++++++++++++++++++++++++
 xen/include/xen/bitops.h | 24 ++++++++++++++++++++++++
 2 files changed, 53 insertions(+)

diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index 94a8983af9..9e532f0d87 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -84,8 +84,37 @@ static void __init test_fls(void)
     CHECK(fls64, 0x8000000000000001ULL, 64);
 }
 
+static void __init test_for_each_set_bit(void)
+{
+    unsigned int  ui,  ui_res = 0;
+    unsigned long ul,  ul_res = 0;
+    uint64_t      ull, ull_res = 0;
+
+    ui = HIDE(0x80008001U);
+    for_each_set_bit ( i, ui )
+        ui_res |= 1U << i;
+
+    if ( ui != ui_res )
+        panic("for_each_set_bit(uint) expected %#x, got %#x\n", ui, ui_res);
+
+    ul = HIDE(1UL << (BITS_PER_LONG - 1) | 1);
+    for_each_set_bit ( i, ul )
+        ul_res |= 1UL << i;
+
+    if ( ul != ul_res )
+        panic("for_each_set_bit(ulong) expected %#lx, got %#lx\n", ul, ul_res);
+
+    ull = HIDE(0x8000000180000001ULL);
+    for_each_set_bit ( i, ull )
+        ull_res |= 1ULL << i;
+
+    if ( ull != ull_res )
+        panic("for_each_set_bit(uint64) expected %#"PRIx64", got 
%#"PRIx64"\n", ull, ull_res);
+}
+
 static void __init __constructor test_bitops(void)
 {
     test_ffs();
     test_fls();
+    test_for_each_set_bit();
 }
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index fbbab96c97..1cd43e464d 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -236,6 +236,16 @@ static always_inline __pure unsigned int ffs64(uint64_t x)
         return !x || (uint32_t)x ? ffs(x) : ffs(x >> 32) + 32;
 }
 
+/*
+ * A type-generic ffs() which picks the appropriate ffs{,l,64}() based on it's
+ * argument.
+ */
+#define ffs_g(x)                                        \
+    (sizeof(x) <= sizeof(int)      ? ffs(x) :           \
+     sizeof(x) <= sizeof(long)     ? ffsl(x) :          \
+     sizeof(x) <= sizeof(uint64_t) ? ffs64(x) :         \
+     ({ BUILD_ERROR("ffs_g() Bad input type"); 0; }))
+
 static always_inline __pure unsigned int fls(unsigned int x)
 {
     if ( __builtin_constant_p(x) )
@@ -272,6 +282,20 @@ static always_inline __pure unsigned int fls64(uint64_t x)
     }
 }
 
+/*
+ * for_each_set_bit() - Iterate over all set bits in a scalar value.
+ *
+ * @iter An iterator name.  Scoped is within the loop only.
+ * @val  A scalar value to iterate over.
+ *
+ * A copy of @val is taken internally.
+ */
+#define for_each_set_bit(iter, val)                     \
+    for ( typeof(val) __v = (val); __v; )               \
+        for ( unsigned int (iter);                      \
+              __v && ((iter) = ffs_g(__v) - 1, true);   \
+              __v &= __v - 1 )
+
 /* --------------------- Please tidy below here --------------------- */
 
 #ifndef find_next_bit
--
generated by git-patchbot for /home/xen/git/xen.git#staging