[PATCH 4/6] xen/bitops: Introduce for_each_set_bit()

[Andrew Cooper <andrew.cooper3@xxxxxxxxxx>]

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>
---
CC: Jan Beulich <JBeulich@xxxxxxxx>
CC: Roger Pau Monné <roger.pau@xxxxxxxxxx>
CC: Stefano Stabellini <sstabellini@xxxxxxxxxx>
CC: Julien Grall <julien@xxxxxxx>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@xxxxxxxx>
CC: Bertrand Marquis <bertrand.marquis@xxxxxxx>
CC: Michal Orzel <michal.orzel@xxxxxxx>
CC: Oleksii Kurochko <oleksii.kurochko@xxxxxxxxx>

The naming of ffs_g() is taken from the new compiler builtins which are using
a g suffix to mean type-generic.
---
 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 94a8983af99c..9e532f0d87aa 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 24de0835b7ab..84ffcb8d57bc 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -56,6 +56,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) )
@@ -92,6 +102,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
-- 
2.39.2