[PATCH v2] xen/lib: introduce generic find next bit operations

[Oleksii Kurochko <oleksii.kurochko@xxxxxxxxx>]

find-next-bit.c is common for Arm64, PPC and RISCV64,
so it is moved to xen/lib.

PPC has been transitioned to generic functions from find-next-bit.c
since it now shares the same implementation as the PPC-specific code.

The MISRA exclude list has been updated to verify
lib/find-next-bit.c instead of Arm's find_next_bit.c,
as Arm's find_next_bit.c has been relocated to xen/lib/.

Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in
Xen and being removed from the Linux kernel [1], it could theoretically
prove useful for Xen. This is because the Linux kernel transitioned
Arm to the generic version of find_first_bit() and
find_first_zero_bit() due to improvements [1] in both performance
and .text size.
It would be prudent to investigate whether [1] is applicable to Xen
as well and, if so, implement the necessary changes in a separate patch.

[1] 
https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@xxxxxxxxx/

Suggested-by: Jan Beulich <jbeulich@xxxxxxxx>
Signed-off-by: Oleksii Kurochko <oleksii.kurochko@xxxxxxxxx>
---
 docs/misra/exclude-list.json                  |   8 +-
 xen/arch/arm/arm64/lib/Makefile               |   2 +-
 xen/arch/arm/include/asm/arm64/bitops.h       |  46 +------
 xen/arch/ppc/include/asm/bitops.h             | 115 ------------------
 xen/include/xen/bitops.h                      |  48 ++++++++
 xen/lib/Makefile                              |   1 +
 .../find_next_bit.c => lib/find-next-bit.c}   |   0
 7 files changed, 55 insertions(+), 165 deletions(-)
 rename xen/{arch/arm/arm64/lib/find_next_bit.c => lib/find-next-bit.c} (100%)

diff --git a/docs/misra/exclude-list.json b/docs/misra/exclude-list.json
index 7971d0e70f..b28174d0eb 100644
--- a/docs/misra/exclude-list.json
+++ b/docs/misra/exclude-list.json
@@ -13,10 +13,6 @@
             "rel_path": "arch/arm/arm64/insn.c",
             "comment": "Imported on Linux, ignore for now"
         },
-        {
-            "rel_path": "arch/arm/arm64/lib/find_next_bit.c",
-            "comment": "Imported from Linux, ignore for now"
-        },
         {
             "rel_path": "arch/x86/acpi/boot.c",
             "comment": "Imported from Linux, ignore for now"
@@ -221,6 +217,10 @@
             "rel_path": "include/xen/decompress.h",
             "comment": "Imported from Linux, ignore for now"
         },
+        {
+            "rel_path": "lib/find-next-bit.c",
+            "comment": "Imported from Linux, ignore for now"
+        },
         {
             "rel_path": "lib/list-sort.c",
             "comment": "Imported from Linux, ignore for now"
diff --git a/xen/arch/arm/arm64/lib/Makefile b/xen/arch/arm/arm64/lib/Makefile
index 1b9c7a95e6..66cfac435a 100644
--- a/xen/arch/arm/arm64/lib/Makefile
+++ b/xen/arch/arm/arm64/lib/Makefile
@@ -1,4 +1,4 @@
 obj-y += memcpy.o memcmp.o memmove.o memset.o memchr.o
 obj-y += clear_page.o
-obj-y += bitops.o find_next_bit.o
+obj-y += bitops.o
 obj-y += strchr.o strcmp.o strlen.o strncmp.o strnlen.o strrchr.o
diff --git a/xen/arch/arm/include/asm/arm64/bitops.h 
b/xen/arch/arm/include/asm/arm64/bitops.h
index d85a49bca4..0efde29068 100644
--- a/xen/arch/arm/include/asm/arm64/bitops.h
+++ b/xen/arch/arm/include/asm/arm64/bitops.h
@@ -36,57 +36,13 @@ static inline int flsl(unsigned long x)
 
 /* Based on linux/include/asm-generic/bitops/find.h */
 
-#ifndef find_next_bit
-/**
- * find_next_bit - find the next set bit in a memory region
- * @addr: The address to base the search on
- * @offset: The bitnumber to start searching at
- * @size: The bitmap size in bits
- */
-extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
-               size, unsigned long offset);
-#endif
-
-#ifndef find_next_zero_bit
-/**
- * find_next_zero_bit - find the next cleared bit in a memory region
- * @addr: The address to base the search on
- * @offset: The bitnumber to start searching at
- * @size: The bitmap size in bits
- */
-extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned
-               long size, unsigned long offset);
-#endif
-
-#ifdef CONFIG_GENERIC_FIND_FIRST_BIT
-
-/**
- * find_first_bit - find the first set bit in a memory region
- * @addr: The address to start the search at
- * @size: The maximum size to search
- *
- * Returns the bit number of the first set bit.
- */
-extern unsigned long find_first_bit(const unsigned long *addr,
-                                   unsigned long size);
-
-/**
- * find_first_zero_bit - find the first cleared bit in a memory region
- * @addr: The address to start the search at
- * @size: The maximum size to search
- *
- * Returns the bit number of the first cleared bit.
- */
-extern unsigned long find_first_zero_bit(const unsigned long *addr,
-                                        unsigned long size);
-#else /* CONFIG_GENERIC_FIND_FIRST_BIT */
+#ifndef CONFIG_GENERIC_FIND_FIRST_BIT
 
 #define find_first_bit(addr, size) find_next_bit((addr), (size), 0)
 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
 
 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
-
 #endif /* _ARM_ARM64_BITOPS_H */
 /*
  * Local variables:
diff --git a/xen/arch/ppc/include/asm/bitops.h 
b/xen/arch/ppc/include/asm/bitops.h
index 5e7f36c21d..5820b9ce7b 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -217,119 +217,4 @@ static always_inline unsigned long __ffs(unsigned long 
word)
  */
 #define find_first_set_bit(x) (ffsl(x) - 1)
 
-/*
- * Find the first set bit in a memory region.
- */
-static inline unsigned long find_first_bit(const unsigned long *addr,
-                                           unsigned long size)
-{
-    const unsigned long *p = addr;
-    unsigned long result = 0;
-    unsigned long tmp;
-
-    while ( size & ~(BITS_PER_LONG - 1) )
-    {
-        if ( (tmp = *(p++)) )
-            goto found;
-        result += BITS_PER_LONG;
-        size -= BITS_PER_LONG;
-    }
-    if ( !size )
-        return result;
-
-    tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
-    if ( tmp == 0UL )         /* Are any bits set? */
-        return result + size; /* Nope. */
- found:
-    return result + __ffs(tmp);
-}
-
-static inline unsigned long find_next_bit(const unsigned long *addr,
-                                          unsigned long size,
-                                          unsigned long offset)
-{
-    const unsigned long *p = addr + BITOP_WORD(offset);
-    unsigned long result = offset & ~(BITS_PER_LONG - 1);
-    unsigned long tmp;
-
-    if ( offset >= size )
-        return size;
-    size -= result;
-    offset %= BITS_PER_LONG;
-    if ( offset )
-    {
-        tmp = *(p++);
-        tmp &= (~0UL << offset);
-        if ( size < BITS_PER_LONG )
-            goto found_first;
-        if ( tmp )
-            goto found_middle;
-        size -= BITS_PER_LONG;
-        result += BITS_PER_LONG;
-    }
-    while ( size & ~(BITS_PER_LONG - 1) )
-    {
-        if ( (tmp = *(p++)) )
-            goto found_middle;
-        result += BITS_PER_LONG;
-        size -= BITS_PER_LONG;
-    }
-    if ( !size )
-        return result;
-    tmp = *p;
-
- found_first:
-    tmp &= (~0UL >> (BITS_PER_LONG - size));
-    if ( tmp == 0UL )         /* Are any bits set? */
-        return result + size; /* Nope. */
- found_middle:
-    return result + __ffs(tmp);
-}
-
-/*
- * This implementation of find_{first,next}_zero_bit was stolen from
- * Linus' asm-alpha/bitops.h.
- */
-static inline unsigned long find_next_zero_bit(const unsigned long *addr,
-                                               unsigned long size,
-                                               unsigned long offset)
-{
-    const unsigned long *p = addr + BITOP_WORD(offset);
-    unsigned long result = offset & ~(BITS_PER_LONG - 1);
-    unsigned long tmp;
-
-    if ( offset >= size )
-        return size;
-    size -= result;
-    offset %= BITS_PER_LONG;
-    if ( offset )
-    {
-        tmp = *(p++);
-        tmp |= ~0UL >> (BITS_PER_LONG - offset);
-        if ( size < BITS_PER_LONG )
-            goto found_first;
-        if ( ~tmp )
-            goto found_middle;
-        size -= BITS_PER_LONG;
-        result += BITS_PER_LONG;
-    }
-    while ( size & ~(BITS_PER_LONG - 1) )
-    {
-        if ( ~(tmp = *(p++)) )
-            goto found_middle;
-        result += BITS_PER_LONG;
-        size -= BITS_PER_LONG;
-    }
-    if ( !size )
-        return result;
-    tmp = *p;
-
- found_first:
-    tmp |= ~0UL << size;
-    if ( tmp == ~0UL )        /* Are any bits zero? */
-        return result + size; /* Nope. */
- found_middle:
-    return result + ffz(tmp);
-}
-
 #endif /* _ASM_PPC_BITOPS_H */
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index 2cb7892bcc..e3c5a4ccf3 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -105,6 +105,54 @@ static inline int generic_flsl(unsigned long x)
  */
 #include <asm/bitops.h>
 
+#ifndef find_next_bit
+/**
+ * find_next_bit - find the next set bit in a memory region
+ * @addr: The address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ */
+extern unsigned long find_next_bit(const unsigned long *addr,
+                                   unsigned long size,
+                                   unsigned long offset);
+#endif
+
+#ifndef find_next_zero_bit
+/**
+ * find_next_zero_bit - find the next cleared bit in a memory region
+ * @addr: The address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ */
+extern unsigned long find_next_zero_bit(const unsigned long *addr,
+                                        unsigned long size,
+                                        unsigned long offset);
+#endif
+
+#ifndef find_first_bit
+/**
+ * find_first_bit - find the first set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum size to search
+ *
+ * Returns the bit number of the first set bit.
+ */
+extern unsigned long find_first_bit(const unsigned long *addr,
+                                    unsigned long size);
+#endif
+
+#ifndef find_first_zero_bit
+/**
+ * find_first_zero_bit - find the first cleared bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum size to search
+ *
+ * Returns the bit number of the first cleared bit.
+ */
+extern unsigned long find_first_zero_bit(const unsigned long *addr,
+                                         unsigned long size);
+#endif
+
 #if BITS_PER_LONG == 64
 # define fls64 flsl
 # define ffs64 ffsl
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index 2d9ebb945f..e63798e1d4 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -3,6 +3,7 @@ obj-$(CONFIG_X86) += x86/
 lib-y += bsearch.o
 lib-y += ctors.o
 lib-y += ctype.o
+lib-y += find-next-bit.o
 lib-y += list-sort.o
 lib-y += memchr.o
 lib-y += memchr_inv.o
diff --git a/xen/arch/arm/arm64/lib/find_next_bit.c b/xen/lib/find-next-bit.c
similarity index 100%
rename from xen/arch/arm/arm64/lib/find_next_bit.c
rename to xen/lib/find-next-bit.c
-- 
2.43.0