[PATCH v2 for-4.19 00/13] xen/bitops: Untangle ffs()/fls() infrastructure

[PATCH v2 for-4.19 00/13] xen/bitops: Untangle ffs()/fls() infrastructure

[Andrew Cooper]

bitops.h is a mess.  It has grown organtically over many years, and forces
unreasonable repsonsibilities out into the per-arch stubs.

Start cleaning it up with ffs() and friends.  Across the board, this adds:

 * Functioning bitops without arch-specific asm
 * An option for arches to provide more optimal code generation
 * Compile-time constant folding
 * Testing at both compile time and during init that the basic operations
   behave according to spec.

and the only reason this series isn't a net reduction in code alone is the
because of the new unit testing.

This form is superior in many ways, including getting RISC-V support for free.

v2:
 * Many changes.  See patches for details
 * Include the fls() side of the infrastructure too.

Testing:
  https://gitlab.com/xen-project/people/andyhhp/xen/-/pipelines/1304664544
  https://cirrus-ci.com/github/andyhhp/xen/

Series-wide net bloat-o-meter:

  x86:   up/down: 51/-247 (-196)
  ARM64: up/down: 40/-400 (-360)

and PPC64 reproduced in full, just to demonstrate how absurd it was to have
generic_f?s() as static inlines...

  add/remove: 1/0 grow/shrink: 1/11 up/down: 228/-4832 (-4604)
  Function                                     old     new   delta
  init_constructors                              -     220    +220
  start_xen                                     92     100      +8
  alloc_heap_pages                            1980    1744    -236
  xenheap_max_mfn                              360     120    -240
  free_heap_pages                              784     536    -248
  find_next_zero_bit                           564     276    -288
  find_next_bit                                548     260    -288
  find_first_zero_bit                          444     148    -296
  find_first_bit                               444     132    -312
  xmem_pool_free                              1776    1440    -336
  __do_softirq                                 604     252    -352
  init_heap_pages                             2328    1416    -912
  xmem_pool_alloc                             2920    1596   -1324


Andrew Cooper (12):
  ppc/boot: Run constructors on boot
  xen/bitops: Cleanup ahead of rearrangements
  ARM/bitops: Change find_first_set_bit() to be a define
  xen/page_alloc: Coerce min(flsl(), foo) expressions to being unsigned
  xen/bitops: Implement generic_f?sl() in lib/
  xen/bitops: Implement ffs() in common logic
  x86/bitops: Improve arch_ffs() in the general case
  xen/bitops: Implement ffsl() in common logic
  xen/bitops: Replace find_first_set_bit() with ffsl() - 1
  xen/bitops: Delete find_first_set_bit()
  xen/bitops: Clean up ffs64()/fls64() definitions
  xen/bitops: Rearrange the top of xen/bitops.h

Oleksii Kurochko (1):
  xen/bitops: Implement fls()/flsl() in common logic

 xen/arch/arm/include/asm/arm32/bitops.h      |   2 -
 xen/arch/arm/include/asm/arm64/bitops.h      |  12 --
 xen/arch/arm/include/asm/bitops.h            |  35 +---
 xen/arch/ppc/include/asm/bitops.h            |  17 +-
 xen/arch/ppc/setup.c                         |   2 +
 xen/arch/x86/guest/xen/xen.c                 |   4 +-
 xen/arch/x86/hvm/dom0_build.c                |   2 +-
 xen/arch/x86/hvm/hpet.c                      |   8 +-
 xen/arch/x86/include/asm/bitops.h            | 114 +++++++------
 xen/arch/x86/include/asm/pt-contig-markers.h |   2 +-
 xen/arch/x86/mm.c                            |   2 +-
 xen/arch/x86/mm/p2m-pod.c                    |   4 +-
 xen/common/Makefile                          |   1 +
 xen/common/bitops.c                          |  89 +++++++++++
 xen/common/page_alloc.c                      |   6 +-
 xen/common/softirq.c                         |   2 +-
 xen/drivers/passthrough/amd/iommu_map.c      |   2 +-
 xen/drivers/passthrough/iommu.c              |   4 +-
 xen/drivers/passthrough/x86/iommu.c          |   4 +-
 xen/include/xen/bitops.h                     | 159 ++++++++-----------
 xen/include/xen/boot-check.h                 |  60 +++++++
 xen/include/xen/compiler.h                   |   3 +-
 xen/lib/Makefile                             |   2 +
 xen/lib/generic-ffsl.c                       |  65 ++++++++
 xen/lib/generic-flsl.c                       |  68 ++++++++
 25 files changed, 444 insertions(+), 225 deletions(-)
 create mode 100644 xen/common/bitops.c
 create mode 100644 xen/include/xen/boot-check.h
 create mode 100644 xen/lib/generic-ffsl.c
 create mode 100644 xen/lib/generic-flsl.c

-- 
2.30.2

[PATCH v2 01/13] ppc/boot: Run constructors on boot

[Andrew Cooper]

PPC collects constructors, but doesn't run them yet.  Do so.

They'll shortly be used to confirm correct behaviour of the bitops primitives.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

CI: https://gitlab.com/xen-project/people/andyhhp/xen/-/jobs/6931084695

v2:
 * New

RISC-V collects them too, but can't call init_constructors() until lib/ctors.c
is included in the build.

Constructors is the only way to get these tests working on PPC/RISC-V as
neither suvivie boot with initcalls() active.  Then again, initcalls() are
just a not-invented-here constructor, and we'd probably do well to move them
over..
---
 xen/arch/ppc/setup.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/xen/arch/ppc/setup.c b/xen/arch/ppc/setup.c
index 101bdd8bb648..7fe06aa4bfb0 100644
--- a/xen/arch/ppc/setup.c
+++ b/xen/arch/ppc/setup.c
@@ -39,6 +39,8 @@ void __init noreturn start_xen(unsigned long r3, unsigned long r4,
 
     setup_initial_pagetables();
 
+    init_constructors();
+
     early_printk("Hello, ppc64le!\n");
 
     for ( ; ; )
-- 
2.30.2

[PATCH v2 02/13] xen/bitops: Cleanup ahead of rearrangements

[Andrew Cooper]

 * Rename __attribute_pure__ to just __pure before it gains users.
 * Introduce __constructor which is going to be used in lib/, and is
   unconditionally cf_check.
 * Identify the areas of xen/bitops.h which are a mess.
 * Introduce xen/boot-check.h as helpers for compile and boot time testing.
   This provides a statement of the ABI, and a confirmation that arch-specific
   implementations behave as expected.

Sadly Clang 7 and older isn't happy with the compile time checks.  Skip them,
and just rely on the runtime checks.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Break macros out into a header as they're going to be used elsewhere too
 * Use panic() rather than BUG_ON() to be more helpful when something fails
 * Brackets in HIDE()
 * Alignment adjustments
 * Skip COMPILE_CHECK() for Clang < 8
---
 xen/include/xen/bitops.h     | 13 ++++++--
 xen/include/xen/boot-check.h | 60 ++++++++++++++++++++++++++++++++++++
 xen/include/xen/compiler.h   |  3 +-
 3 files changed, 72 insertions(+), 4 deletions(-)
 create mode 100644 xen/include/xen/boot-check.h

diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index e3c5a4ccf321..9b40f20381a2 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -1,5 +1,7 @@
-#ifndef _LINUX_BITOPS_H
-#define _LINUX_BITOPS_H
+#ifndef XEN_BITOPS_H
+#define XEN_BITOPS_H
+
+#include <xen/compiler.h>
 #include <xen/types.h>
 
 /*
@@ -103,8 +105,13 @@ static inline int generic_flsl(unsigned long x)
  * Include this here because some architectures need generic_ffs/fls in
  * scope
  */
+
+/* --------------------- Please tidy above here --------------------- */
+
 #include <asm/bitops.h>
 
+/* --------------------- Please tidy below here --------------------- */
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
@@ -294,4 +301,4 @@ static inline __u32 ror32(__u32 word, unsigned int shift)
 
 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
 
-#endif
+#endif /* XEN_BITOPS_H */
diff --git a/xen/include/xen/boot-check.h b/xen/include/xen/boot-check.h
new file mode 100644
index 000000000000..250f9a40d3b0
--- /dev/null
+++ b/xen/include/xen/boot-check.h
@@ -0,0 +1,60 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+/*
+ * Helpers for boot-time checks of basic logic, including confirming that
+ * examples which should be calculated by the compiler are.
+ */
+#ifndef XEN_BOOT_CHECK_H
+#define XEN_BOOT_CHECK_H
+
+#include <xen/lib.h>
+
+/* Hide a value from the optimiser. */
+#define HIDE(x)                                                         \
+    ({ typeof(x) _x = (x); asm volatile ( "" : "+r" (_x) ); _x; })
+
+/*
+ * Check that fn(val) can be calcuated by the compiler, and that it gives the
+ * expected answer.
+ *
+ * Clang < 8 can't fold constants through static inlines, causing this to
+ * fail.  Simply skip it for incredibly old compilers.
+ */
+#if !CONFIG_CC_IS_CLANG || CONFIG_CLANG_VERSION >= 80000
+#define COMPILE_CHECK(fn, val, res)                                     \
+    do {                                                                \
+        typeof(fn(val)) real = fn(val);                                 \
+                                                                        \
+        if ( !__builtin_constant_p(real) )                              \
+            asm ( ".error \"'" STR(fn(val)) "' not compile-time constant\"" ); \
+        else if ( real != res )                                         \
+            asm ( ".error \"Compile time check '" STR(fn(val) == res) "' failed\"" ); \
+    } while ( 0 )
+#else
+#define COMPILE_CHECK(fn, val, res)
+#endif
+
+/*
+ * Check that Xen's runtime logic for fn(val) gives the expected answer.  This
+ * requires using HIDE() to prevent the optimiser from collapsing the logic
+ * into a constant.
+ */
+#define RUNTIME_CHECK(fn, val, res)                     \
+    do {                                                \
+        typeof(fn(val)) real = fn(HIDE(val));           \
+                                                        \
+        if ( real != res )                              \
+            panic("%s: %s(%s) expected %u, got %u\n",   \
+                  __func__, #fn, #val, real, res);      \
+    } while ( 0 )
+
+/*
+ * Perform compiletime and runtime checks for fn(val) == res.
+ */
+#define CHECK(fn, val, res)                     \
+    do {                                        \
+        COMPILE_CHECK(fn, val, res);            \
+        RUNTIME_CHECK(fn, val, res);            \
+    } while ( 0 )
+
+#endif /* XEN_BOOT_CHECK_H */
diff --git a/xen/include/xen/compiler.h b/xen/include/xen/compiler.h
index 179ff23e62c5..444bf80142c7 100644
--- a/xen/include/xen/compiler.h
+++ b/xen/include/xen/compiler.h
@@ -86,7 +86,8 @@
 #define inline inline __init
 #endif
 
-#define __attribute_pure__  __attribute__((__pure__))
+#define __constructor       __attribute__((__constructor__)) cf_check
+#define __pure              __attribute__((__pure__))
 #define __attribute_const__ __attribute__((__const__))
 #define __transparent__     __attribute__((__transparent_union__))
 
-- 
2.30.2

[PATCH v2 03/13] ARM/bitops: Change find_first_set_bit() to be a define

[Andrew Cooper]

This is in order to maintain bisectability through the subsequent changes, as
the order of definitions is altered.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New
---
 xen/arch/arm/include/asm/bitops.h | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index ab030b6cb032..199252201291 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -167,10 +167,7 @@ static inline int fls(unsigned int x)
  * Returns the bit-number of the first set bit (first bit being 0).
  * The input must *not* be zero.
  */
-static inline unsigned int find_first_set_bit(unsigned long word)
-{
-        return ffsl(word) - 1;
-}
+#define find_first_set_bit(w) (ffsl(w) - 1)
 
 /**
  * hweightN - returns the hamming weight of a N-bit word
-- 
2.30.2

[PATCH v2 04/13] xen/page_alloc: Coerce min(flsl(), foo) expressions to being unsigned

[Andrew Cooper]

This is in order to maintain bisectability through the subsequent changes,
where flsl() changes sign-ness non-atomically by architecture.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New
---
 xen/common/page_alloc.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/xen/common/page_alloc.c b/xen/common/page_alloc.c
index 7c1bdfc046bf..8d3342e95236 100644
--- a/xen/common/page_alloc.c
+++ b/xen/common/page_alloc.c
@@ -1842,7 +1842,7 @@ static void _init_heap_pages(const struct page_info *pg,
          * Note that the value of ffsl() and flsl() starts from 1 so we need
          * to decrement it by 1.
          */
-        unsigned int inc_order = min(MAX_ORDER, flsl(e - s) - 1);
+        unsigned int inc_order = min(MAX_ORDER + 0U, flsl(e - s) - 1U);
 
         if ( s )
             inc_order = min(inc_order, ffsl(s) - 1U);
@@ -2266,7 +2266,7 @@ void __init xenheap_max_mfn(unsigned long mfn)
     ASSERT(!first_node_initialised);
     ASSERT(!xenheap_bits);
     BUILD_BUG_ON((PADDR_BITS - PAGE_SHIFT) >= BITS_PER_LONG);
-    xenheap_bits = min(flsl(mfn + 1) - 1 + PAGE_SHIFT, PADDR_BITS);
+    xenheap_bits = min(flsl(mfn + 1) - 1U + PAGE_SHIFT, PADDR_BITS + 0U);
     printk(XENLOG_INFO "Xen heap: %u bits\n", xenheap_bits);
 }
 
-- 
2.30.2

[PATCH v2 05/13] xen/bitops: Implement generic_f?sl() in lib/

[Andrew Cooper]

generic_f?s() being static inline is the cause of lots of the complexity
between the common and arch-specific bitops.h

They appear to be static inline for constant-folding reasons (ARM uses them
for this), but there are better ways to achieve the same effect.

It is presumptuous that an unrolled binary search is the right algorithm to
use on all microarchitectures.  Indeed, it's not for the eventual users, but
that can be addressed at a later point.

It is also nonsense to implement the int form as the base primitive and
construct the long form from 2x int in 64-bit builds, when it's just one extra
step to operate at the native register width.

Therefore, implement generic_f?sl() in lib/.  They're not actually needed in
x86/ARM/PPC by the end of the cleanup (i.e. the functions will be dropped by
the linker), and they're only expected be needed by RISC-V on hardware which
lacks the Zbb extension.

Implement generic_fls() in terms of generic_flsl() for now, but this will be
cleaned up in due course.

Provide basic runtime testing using __constructor inside the lib/ file.  This
is important, as it means testing runs if and only if generic_f?sl() are used
elsewhere in Xen.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New

I suspect we want to swap CONFIG_DEBUG for CONFIG_BOOT_UNIT_TESTS in due
course.  These ought to be able to be used in a release build too.
---
 xen/arch/arm/include/asm/bitops.h |  2 +-
 xen/arch/ppc/include/asm/bitops.h |  2 +-
 xen/include/xen/bitops.h          | 89 ++-----------------------------
 xen/lib/Makefile                  |  2 +
 xen/lib/generic-ffsl.c            | 65 ++++++++++++++++++++++
 xen/lib/generic-flsl.c            | 68 +++++++++++++++++++++++
 6 files changed, 142 insertions(+), 86 deletions(-)
 create mode 100644 xen/lib/generic-ffsl.c
 create mode 100644 xen/lib/generic-flsl.c

diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index 199252201291..ec1cf7b9b323 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -150,7 +150,7 @@ static inline int fls(unsigned int x)
         int ret;
 
         if (__builtin_constant_p(x))
-               return generic_fls(x);
+               return generic_flsl(x);
 
         asm("clz\t%"__OP32"0, %"__OP32"1" : "=r" (ret) : "r" (x));
         return 32 - ret;
diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
index bea655796d64..ab692d01717b 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -172,7 +172,7 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
 }
 
 #define flsl(x) generic_flsl(x)
-#define fls(x) generic_fls(x)
+#define fls(x) generic_flsl(x)
 #define ffs(x) ({ unsigned int t_ = (x); fls(t_ & -t_); })
 #define ffsl(x) ({ unsigned long t_ = (x); flsl(t_ & -t_); })
 
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index 9b40f20381a2..cd405df96180 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -15,91 +15,12 @@
     (((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LLONG - 1 - (h))))
 
 /*
- * ffs: find first bit set. This is defined the same way as
- * the libc and compiler builtin ffs routines, therefore
- * differs in spirit from the above ffz (man ffs).
- */
-
-static inline int generic_ffs(unsigned int x)
-{
-    int r = 1;
-
-    if (!x)
-        return 0;
-    if (!(x & 0xffff)) {
-        x >>= 16;
-        r += 16;
-    }
-    if (!(x & 0xff)) {
-        x >>= 8;
-        r += 8;
-    }
-    if (!(x & 0xf)) {
-        x >>= 4;
-        r += 4;
-    }
-    if (!(x & 3)) {
-        x >>= 2;
-        r += 2;
-    }
-    if (!(x & 1)) {
-        x >>= 1;
-        r += 1;
-    }
-    return r;
-}
-
-/*
- * fls: find last bit set.
+ * Find First/Last Set bit.
+ *
+ * Bits are labelled from 1.  Returns 0 if given 0.
  */
-
-static inline int generic_fls(unsigned int x)
-{
-    int r = 32;
-
-    if (!x)
-        return 0;
-    if (!(x & 0xffff0000u)) {
-        x <<= 16;
-        r -= 16;
-    }
-    if (!(x & 0xff000000u)) {
-        x <<= 8;
-        r -= 8;
-    }
-    if (!(x & 0xf0000000u)) {
-        x <<= 4;
-        r -= 4;
-    }
-    if (!(x & 0xc0000000u)) {
-        x <<= 2;
-        r -= 2;
-    }
-    if (!(x & 0x80000000u)) {
-        x <<= 1;
-        r -= 1;
-    }
-    return r;
-}
-
-#if BITS_PER_LONG == 64
-
-static inline int generic_ffsl(unsigned long x)
-{
-    return !x || (u32)x ? generic_ffs(x) : generic_ffs(x >> 32) + 32;
-}
-
-static inline int generic_flsl(unsigned long x)
-{
-    u32 h = x >> 32;
-
-    return h ? generic_fls(h) + 32 : generic_fls(x);
-}
-
-#else
-# define generic_ffsl generic_ffs
-# define generic_flsl generic_fls
-#endif
+unsigned int __pure generic_ffsl(unsigned long x);
+unsigned int __pure generic_flsl(unsigned long x);
 
 /*
  * Include this here because some architectures need generic_ffs/fls in
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index e63798e1d452..a48541596470 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -4,6 +4,8 @@ lib-y += bsearch.o
 lib-y += ctors.o
 lib-y += ctype.o
 lib-y += find-next-bit.o
+lib-y += generic-ffsl.o
+lib-y += generic-flsl.o
 lib-y += list-sort.o
 lib-y += memchr.o
 lib-y += memchr_inv.o
diff --git a/xen/lib/generic-ffsl.c b/xen/lib/generic-ffsl.c
new file mode 100644
index 000000000000..804cbd752efe
--- /dev/null
+++ b/xen/lib/generic-ffsl.c
@@ -0,0 +1,65 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#include <xen/bitops.h>
+#include <xen/boot-check.h>
+#include <xen/init.h>
+
+unsigned int generic_ffsl(unsigned long x)
+{
+    unsigned int r = 1;
+
+    if ( !x )
+        return 0;
+
+#if BITS_PER_LONG > 32
+    if ( !(x & 0xffffffffU) )
+    {
+        x >>= 32;
+        r += 32;
+    }
+#endif
+    if ( !(x & 0xffff) )
+    {
+        x >>= 16;
+        r += 16;
+    }
+    if ( !(x & 0xff) )
+    {
+        x >>= 8;
+        r += 8;
+    }
+    if ( !(x & 0xf) )
+    {
+        x >>= 4;
+        r += 4;
+    }
+    if ( !(x & 3) )
+    {
+        x >>= 2;
+        r += 2;
+    }
+    if ( !(x & 1) )
+    {
+        x >>= 1;
+        r += 1;
+    }
+
+    return r;
+}
+
+#ifdef CONFIG_DEBUG
+static void __init __constructor test_generic_ffsl(void)
+{
+    RUNTIME_CHECK(generic_ffsl, 0, 0);
+    RUNTIME_CHECK(generic_ffsl, 1, 1);
+    RUNTIME_CHECK(generic_ffsl, 3, 1);
+    RUNTIME_CHECK(generic_ffsl, 7, 1);
+    RUNTIME_CHECK(generic_ffsl, 6, 2);
+
+    RUNTIME_CHECK(generic_ffsl, 1UL << (BITS_PER_LONG - 1), BITS_PER_LONG);
+#if BITS_PER_LONG > 32
+    RUNTIME_CHECK(generic_ffsl, 1UL << 32, 33);
+    RUNTIME_CHECK(generic_ffsl, 1UL << 63, 64);
+#endif
+}
+#endif /* CONFIG_DEBUG */
diff --git a/xen/lib/generic-flsl.c b/xen/lib/generic-flsl.c
new file mode 100644
index 000000000000..e4543aeaf100
--- /dev/null
+++ b/xen/lib/generic-flsl.c
@@ -0,0 +1,68 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#include <xen/bitops.h>
+#include <xen/boot-check.h>
+#include <xen/init.h>
+
+/* Mask of type UL with the upper x bits set. */
+#define UPPER_MASK(x) (~0UL << (BITS_PER_LONG - (x)))
+
+unsigned int generic_flsl(unsigned long x)
+{
+    unsigned int r = BITS_PER_LONG;
+
+    if ( !x )
+        return 0;
+
+#if BITS_PER_LONG > 32
+    if ( !(x & UPPER_MASK(32)) )
+    {
+        x <<= 32;
+        r -= 32;
+    }
+#endif
+    if ( !(x & UPPER_MASK(16)) )
+    {
+        x <<= 16;
+        r -= 16;
+    }
+    if ( !(x & UPPER_MASK(8)) )
+    {
+        x <<= 8;
+        r -= 8;
+    }
+    if ( !(x & UPPER_MASK(4)) )
+    {
+        x <<= 4;
+        r -= 4;
+    }
+    if ( !(x & UPPER_MASK(2)) )
+    {
+        x <<= 2;
+        r -= 2;
+    }
+    if ( !(x & UPPER_MASK(1)) )
+    {
+        x <<= 1;
+        r -= 1;
+    }
+
+    return r;
+}
+
+#ifdef CONFIG_DEBUG
+static void __init __constructor test_generic_flsl(void)
+{
+    RUNTIME_CHECK(generic_flsl, 0, 0);
+    RUNTIME_CHECK(generic_flsl, 1, 1);
+    RUNTIME_CHECK(generic_flsl, 3, 2);
+    RUNTIME_CHECK(generic_flsl, 7, 3);
+    RUNTIME_CHECK(generic_flsl, 6, 3);
+
+    RUNTIME_CHECK(generic_flsl, 1 | (1UL << (BITS_PER_LONG - 1)), BITS_PER_LONG);
+#if BITS_PER_LONG > 32
+    RUNTIME_CHECK(generic_flsl, 1 | (1UL << 32), 33);
+    RUNTIME_CHECK(generic_flsl, 1 | (1UL << 63), 64);
+#endif
+}
+#endif /* CONFIG_DEBUG */
-- 
2.30.2

[PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Andrew Cooper]

Perform constant-folding unconditionally, rather than having it implemented
inconsistency between architectures.

Confirm the expected behaviour with compile time and boot time tests.

For non-constant inputs, use arch_ffs() if provided but fall back to
generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin that
works in all configurations.

For x86, rename ffs() to arch_ffs() and adjust the prototype.

For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to
generic_fls().  Drop the definition entirely.  ARM too benefits in the general
case by using __builtin_ctz(), but less dramatically because it using
optimised asm().

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Fall back to generic, not builtin.
 * Extend the testing with multi-bit values.
 * Use always_inline for x86
 * Defer x86 optimisation to a later change
---
 xen/arch/arm/include/asm/bitops.h |  2 +-
 xen/arch/ppc/include/asm/bitops.h |  2 +-
 xen/arch/x86/include/asm/bitops.h |  3 ++-
 xen/common/Makefile               |  1 +
 xen/common/bitops.c               | 19 +++++++++++++++++++
 xen/include/xen/bitops.h          | 17 +++++++++++++++++
 6 files changed, 41 insertions(+), 3 deletions(-)
 create mode 100644 xen/common/bitops.c

diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index ec1cf7b9b323..a88ec2612e16 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -157,7 +157,7 @@ static inline int fls(unsigned int x)
 }
 
 
-#define ffs(x) ({ unsigned int __t = (x); fls(ISOLATE_LSB(__t)); })
+#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
 #define ffsl(x) ({ unsigned long __t = (x); flsl(ISOLATE_LSB(__t)); })
 
 /**
diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
index ab692d01717b..5c36a6cc0ce3 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -173,7 +173,7 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
 
 #define flsl(x) generic_flsl(x)
 #define fls(x) generic_flsl(x)
-#define ffs(x) ({ unsigned int t_ = (x); fls(t_ & -t_); })
+#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
 #define ffsl(x) ({ unsigned long t_ = (x); flsl(t_ & -t_); })
 
 /**
diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
index 5a71afbc89d5..122767fc0d10 100644
--- a/xen/arch/x86/include/asm/bitops.h
+++ b/xen/arch/x86/include/asm/bitops.h
@@ -430,7 +430,7 @@ static inline int ffsl(unsigned long x)
     return (int)r+1;
 }
 
-static inline int ffs(unsigned int x)
+static always_inline unsigned int arch_ffs(unsigned int x)
 {
     int r;
 
@@ -440,6 +440,7 @@ static inline int ffs(unsigned int x)
           "1:" : "=r" (r) : "rm" (x));
     return r + 1;
 }
+#define arch_ffs arch_ffs
 
 /**
  * fls - find last bit set
diff --git a/xen/common/Makefile b/xen/common/Makefile
index d512cad5243f..21a4fb4c7166 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -1,5 +1,6 @@
 obj-$(CONFIG_ARGO) += argo.o
 obj-y += bitmap.o
+obj-bin-$(CONFIG_DEBUG) += bitops.init.o
 obj-$(CONFIG_GENERIC_BUG_FRAME) += bug.o
 obj-$(CONFIG_HYPFS_CONFIG) += config_data.o
 obj-$(CONFIG_CORE_PARKING) += core_parking.o
diff --git a/xen/common/bitops.c b/xen/common/bitops.c
new file mode 100644
index 000000000000..8c161b8ea7fa
--- /dev/null
+++ b/xen/common/bitops.c
@@ -0,0 +1,19 @@
+#include <xen/bitops.h>
+#include <xen/boot-check.h>
+#include <xen/init.h>
+
+static void __init test_ffs(void)
+{
+    /* unsigned int ffs(unsigned int) */
+    CHECK(ffs, 0, 0);
+    CHECK(ffs, 1, 1);
+    CHECK(ffs, 3, 1);
+    CHECK(ffs, 7, 1);
+    CHECK(ffs, 6, 2);
+    CHECK(ffs, 0x80000000U, 32);
+}
+
+static void __init __constructor test_bitops(void)
+{
+    test_ffs();
+}
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index cd405df96180..f7e90a2893a5 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -31,6 +31,23 @@ unsigned int __pure generic_flsl(unsigned long x);
 
 #include <asm/bitops.h>
 
+/*
+ * Find First/Last Set bit (all forms).
+ *
+ * Bits are labelled from 1.  Returns 0 if given 0.
+ */
+static always_inline __pure unsigned int ffs(unsigned int x)
+{
+    if ( __builtin_constant_p(x) )
+        return __builtin_ffs(x);
+
+#ifdef arch_ffs
+    return arch_ffs(x);
+#else
+    return generic_ffsl(x);
+#endif
+}
+
 /* --------------------- Please tidy below here --------------------- */
 
 #ifndef find_next_bit
-- 
2.30.2

[PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Andrew Cooper]

The asm in arch_ffs() is safe but inefficient.

CMOV would be an improvement over a conditional branch, but for 64bit CPUs
both Intel and AMD have provided enough details about the behaviour for a zero
input.  It is safe to pre-load the destination register with -1 and drop the
conditional logic.

However, it is common to find ffs() in a context where the optimiser knows
that x in nonzero even if it the value isn't known precisely, and in that case
it's safe to drop the preload of -1 too.

There are only a handful of uses of ffs() in the x86 build, and all of them
improve as a result of this:

  add/remove: 0/0 grow/shrink: 0/2 up/down: 0/-31 (-31)
  Function                                     old     new   delta
  mask_write                                   114     107      -7
  xmem_pool_alloc                             1063    1039     -24

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New.
 * Use __builtin_constant_p(x > 0) to optimise better.
---
 xen/arch/x86/include/asm/bitops.h | 26 +++++++++++++++++++++-----
 1 file changed, 21 insertions(+), 5 deletions(-)

diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
index 122767fc0d10..1d7aea6065ef 100644
--- a/xen/arch/x86/include/asm/bitops.h
+++ b/xen/arch/x86/include/asm/bitops.h
@@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
 
 static always_inline unsigned int arch_ffs(unsigned int x)
 {
-    int r;
+    unsigned int r;
+
+    if ( __builtin_constant_p(x > 0) && x > 0 )
+    {
+        /* Safe, when the compiler knows that x is nonzero. */
+        asm ( "bsf %[val], %[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x) );
+    }
+    else
+    {
+        /*
+         * The AMD manual states that BSF won't modify the destination
+         * register if x=0.  The Intel manual states that the result is
+         * undefined, but the architects have said that the register is
+         * written back with it's old value (zero extended as normal).
+         */
+        asm ( "bsf %[val], %[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x), "[res]" (-1) );
+    }
 
-    asm ( "bsf %1,%0\n\t"
-          "jnz 1f\n\t"
-          "mov $-1,%0\n"
-          "1:" : "=r" (r) : "rm" (x));
     return r + 1;
 }
 #define arch_ffs arch_ffs
-- 
2.30.2

[PATCH v2 08/13] xen/bitops: Implement ffsl() in common logic

[Andrew Cooper]

Just like ffs() in the previous changes.  Express the upper bound of the
testing in terms of BITS_PER_LONG as it varies between architectures.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Swap to #if BITS_PER_LONG > 32 to avoid a compile error on arm32
 * Changes to mirror ffs() v2.
---
 xen/arch/arm/include/asm/bitops.h |  2 +-
 xen/arch/ppc/include/asm/bitops.h |  2 +-
 xen/arch/x86/include/asm/bitops.h | 35 ++++++++++++++++---------------
 xen/common/bitops.c               | 13 ++++++++++++
 xen/include/xen/bitops.h          | 12 +++++++++++
 5 files changed, 45 insertions(+), 19 deletions(-)

diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index a88ec2612e16..ba39802c9de3 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -158,7 +158,7 @@ static inline int fls(unsigned int x)
 
 
 #define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
-#define ffsl(x) ({ unsigned long __t = (x); flsl(ISOLATE_LSB(__t)); })
+#define arch_ffsl(x) ((x) ? 1 + __builtin_ctzl(x) : 0)
 
 /**
  * find_first_set_bit - find the first set bit in @word
diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
index 5c36a6cc0ce3..ce0f6436f727 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -174,7 +174,7 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
 #define flsl(x) generic_flsl(x)
 #define fls(x) generic_flsl(x)
 #define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
-#define ffsl(x) ({ unsigned long t_ = (x); flsl(t_ & -t_); })
+#define arch_ffsl(x) ((x) ? 1 + __builtin_ctzl(x) : 0)
 
 /**
  * hweightN - returns the hamming weight of a N-bit word
diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
index 1d7aea6065ef..51d3c0f40473 100644
--- a/xen/arch/x86/include/asm/bitops.h
+++ b/xen/arch/x86/include/asm/bitops.h
@@ -413,23 +413,6 @@ static inline unsigned int find_first_set_bit(unsigned long word)
     return (unsigned int)word;
 }
 
-/**
- * ffs - find first bit set
- * @x: the word to search
- *
- * This is defined the same way as the libc and compiler builtin ffs routines.
- */
-static inline int ffsl(unsigned long x)
-{
-    long r;
-
-    asm ( "bsf %1,%0\n\t"
-          "jnz 1f\n\t"
-          "mov $-1,%0\n"
-          "1:" : "=r" (r) : "rm" (x));
-    return (int)r+1;
-}
-
 static always_inline unsigned int arch_ffs(unsigned int x)
 {
     unsigned int r;
@@ -458,6 +441,24 @@ static always_inline unsigned int arch_ffs(unsigned int x)
 }
 #define arch_ffs arch_ffs
 
+static always_inline unsigned int arch_ffsl(unsigned long x)
+{
+    unsigned int r;
+
+    /* See arch_ffs() for safety discussions. */
+    if ( __builtin_constant_p(x > 0) && x > 0 )
+        asm ( "bsf %[val], %q[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x) );
+    else
+        asm ( "bsf %[val], %q[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x), "[res]" (-1) );
+
+    return r + 1;
+}
+#define arch_ffsl arch_ffsl
+
 /**
  * fls - find last bit set
  * @x: the word to search
diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index 8c161b8ea7fa..b3813f818198 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -11,6 +11,19 @@ static void __init test_ffs(void)
     CHECK(ffs, 7, 1);
     CHECK(ffs, 6, 2);
     CHECK(ffs, 0x80000000U, 32);
+
+    /* unsigned int ffsl(unsigned long) */
+    CHECK(ffsl, 0, 0);
+    CHECK(ffsl, 1, 1);
+    CHECK(ffsl, 3, 1);
+    CHECK(ffsl, 7, 1);
+    CHECK(ffsl, 6, 2);
+
+    CHECK(ffsl, 1UL << (BITS_PER_LONG - 1), BITS_PER_LONG);
+#if BITS_PER_LONG > 32
+    CHECK(ffsl, 1UL << 32, 33);
+    CHECK(ffsl, 1UL << 63, 64);
+#endif
 }
 
 static void __init __constructor test_bitops(void)
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index f7e90a2893a5..88cf27a88bcf 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -48,6 +48,18 @@ static always_inline __pure unsigned int ffs(unsigned int x)
 #endif
 }
 
+static always_inline __pure unsigned int ffsl(unsigned long x)
+{
+    if ( __builtin_constant_p(x) )
+        return __builtin_ffsl(x);
+
+#ifdef arch_ffs
+    return arch_ffsl(x);
+#else
+    return generic_ffsl(x);
+#endif
+}
+
 /* --------------------- Please tidy below here --------------------- */
 
 #ifndef find_next_bit
-- 
2.30.2

[PATCH v2 09/13] xen/bitops: Replace find_first_set_bit() with ffsl() - 1

[Andrew Cooper]

find_first_set_bit() is a Xen-ism which has undefined behaviour with a 0
input.  The latter is well defined with an input of 0, and is a found outside
of Xen too.

_init_heap_pages() is the one special case here, comparing the LSB of two
different addresses.  The -1 cancels off both sides of the expression.

No functional change.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Reorder from later in the series to keep ARM bisectable

In an x86 build, we get the following delta:

  add/remove: 0/0 grow/shrink: 2/4 up/down: 39/-52 (-13)
  Function                                     old     new   delta
  hpet_write                                  2183    2206     +23
  init_heap_pages                             1222    1238     +16
  dom0_construct_pvh                          3959    3958      -1
  mapping_order                                139     126     -13
  guest_physmap_mark_populate_on_demand       1301    1285     -16
  vcpumask_to_pcpumask                         525     503     -22

so the optimiser improvements for ffsl() really do speak for themselves.

I'm surprised by the increase in hpet_write(), but looking at the code, it
very clearly wants the same treatment as:

  commit 188fa82305e72b725473db9146e20cc9abf7bff3
  Author: Andrew Cooper <andrew.cooper3@citrix.com>
  Date:   Fri Mar 15 11:31:33 2024

      xen/vpci: Improve code generation in mask_write()

which I'm confident will end up as a net improvement.
---
 xen/arch/x86/guest/xen/xen.c                 | 4 ++--
 xen/arch/x86/hvm/dom0_build.c                | 2 +-
 xen/arch/x86/hvm/hpet.c                      | 8 ++++----
 xen/arch/x86/include/asm/pt-contig-markers.h | 2 +-
 xen/arch/x86/mm.c                            | 2 +-
 xen/arch/x86/mm/p2m-pod.c                    | 4 ++--
 xen/common/page_alloc.c                      | 2 +-
 xen/common/softirq.c                         | 2 +-
 xen/drivers/passthrough/amd/iommu_map.c      | 2 +-
 xen/drivers/passthrough/iommu.c              | 4 ++--
 xen/drivers/passthrough/x86/iommu.c          | 4 ++--
 11 files changed, 18 insertions(+), 18 deletions(-)

diff --git a/xen/arch/x86/guest/xen/xen.c b/xen/arch/x86/guest/xen/xen.c
index d9768cc9527d..7484b3f73ad3 100644
--- a/xen/arch/x86/guest/xen/xen.c
+++ b/xen/arch/x86/guest/xen/xen.c
@@ -168,14 +168,14 @@ static void cf_check xen_evtchn_upcall(void)
 
     while ( pending )
     {
-        unsigned int l1 = find_first_set_bit(pending);
+        unsigned int l1 = ffsl(pending) - 1;
         unsigned long evtchn = xchg(&XEN_shared_info->evtchn_pending[l1], 0);
 
         __clear_bit(l1, &pending);
         evtchn &= ~XEN_shared_info->evtchn_mask[l1];
         while ( evtchn )
         {
-            unsigned int port = find_first_set_bit(evtchn);
+            unsigned int port = ffsl(evtchn) - 1;
 
             __clear_bit(port, &evtchn);
             port += l1 * BITS_PER_LONG;
diff --git a/xen/arch/x86/hvm/dom0_build.c b/xen/arch/x86/hvm/dom0_build.c
index b0cb96c3bc76..68c08bbe94f7 100644
--- a/xen/arch/x86/hvm/dom0_build.c
+++ b/xen/arch/x86/hvm/dom0_build.c
@@ -139,7 +139,7 @@ static int __init pvh_populate_memory_range(struct domain *d,
         order = get_order_from_pages(end - start + 1);
         order = min(order ? order - 1 : 0, max_order);
         /* The order allocated and populated must be aligned to the address. */
-        order = min(order, start ? find_first_set_bit(start) : MAX_ORDER);
+        order = min(order, start ? ffsl(start) - 1 : MAX_ORDER);
         page = alloc_domheap_pages(d, order, dom0_memflags | MEMF_no_scrub);
         if ( page == NULL )
         {
diff --git a/xen/arch/x86/hvm/hpet.c b/xen/arch/x86/hvm/hpet.c
index 12b00b770257..37e765e97df9 100644
--- a/xen/arch/x86/hvm/hpet.c
+++ b/xen/arch/x86/hvm/hpet.c
@@ -335,7 +335,7 @@ static void timer_sanitize_int_route(HPETState *h, unsigned int tn)
      * enabled pick the first irq.
      */
     timer_config(h, tn) |=
-        MASK_INSR(find_first_set_bit(timer_int_route_cap(h, tn)),
+        MASK_INSR(ffsl(timer_int_route_cap(h, tn)) - 1,
                   HPET_TN_ROUTE);
 }
 
@@ -409,7 +409,7 @@ static int cf_check hpet_write(
         {
             bool active;
 
-            i = find_first_set_bit(new_val);
+            i = ffsl(new_val) - 1;
             if ( i >= HPET_TIMER_NUM )
                 break;
             __clear_bit(i, &new_val);
@@ -535,14 +535,14 @@ static int cf_check hpet_write(
     /* stop/start timers whos state was changed by this write. */
     while (stop_timers)
     {
-        i = find_first_set_bit(stop_timers);
+        i = ffsl(stop_timers) - 1;
         __clear_bit(i, &stop_timers);
         hpet_stop_timer(h, i, guest_time);
     }
 
     while (start_timers)
     {
-        i = find_first_set_bit(start_timers);
+        i = ffsl(start_timers) - 1;
         __clear_bit(i, &start_timers);
         hpet_set_timer(h, i, guest_time);
     }
diff --git a/xen/arch/x86/include/asm/pt-contig-markers.h b/xen/arch/x86/include/asm/pt-contig-markers.h
index b3c1fe803534..e8c8157d605f 100644
--- a/xen/arch/x86/include/asm/pt-contig-markers.h
+++ b/xen/arch/x86/include/asm/pt-contig-markers.h
@@ -60,7 +60,7 @@ static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx,
     /* Step 1: Reduce markers in lower numbered entries. */
     while ( i )
     {
-        b = find_first_set_bit(i);
+        b = ffsl(i) - 1;
         i &= ~(1U << b);
         if ( GET_MARKER(pt[i]) <= b )
             break;
diff --git a/xen/arch/x86/mm.c b/xen/arch/x86/mm.c
index d968bbbc7315..2a84bdae670b 100644
--- a/xen/arch/x86/mm.c
+++ b/xen/arch/x86/mm.c
@@ -3424,7 +3424,7 @@ static int vcpumask_to_pcpumask(
         {
             unsigned int cpu;
 
-            vcpu_id = find_first_set_bit(vmask);
+            vcpu_id = ffsl(vmask) - 1;
             vmask &= ~(1UL << vcpu_id);
             vcpu_id += vcpu_bias;
             if ( (vcpu_id >= d->max_vcpus) )
diff --git a/xen/arch/x86/mm/p2m-pod.c b/xen/arch/x86/mm/p2m-pod.c
index 1c727c78c833..bd84fe9e27ee 100644
--- a/xen/arch/x86/mm/p2m-pod.c
+++ b/xen/arch/x86/mm/p2m-pod.c
@@ -684,7 +684,7 @@ unsigned long
 p2m_pod_decrease_reservation(struct domain *d, gfn_t gfn, unsigned int order)
 {
     unsigned long left = 1UL << order, ret = 0;
-    unsigned int chunk_order = find_first_set_bit(gfn_x(gfn) | left);
+    unsigned int chunk_order = ffsl(gfn_x(gfn) | left) - 1;
 
     do {
         ret += decrease_reservation(d, gfn, chunk_order);
@@ -1393,7 +1393,7 @@ guest_physmap_mark_populate_on_demand(struct domain *d, unsigned long gfn,
                                       unsigned int order)
 {
     unsigned long left = 1UL << order;
-    unsigned int chunk_order = find_first_set_bit(gfn | left);
+    unsigned int chunk_order = ffsl(gfn | left) - 1;
     int rc;
 
     if ( !paging_mode_translate(d) )
diff --git a/xen/common/page_alloc.c b/xen/common/page_alloc.c
index 8d3342e95236..054b7edb3989 100644
--- a/xen/common/page_alloc.c
+++ b/xen/common/page_alloc.c
@@ -1819,7 +1819,7 @@ static void _init_heap_pages(const struct page_info *pg,
     if ( unlikely(!avail[nid]) )
     {
         bool use_tail = IS_ALIGNED(s, 1UL << MAX_ORDER) &&
-                        (find_first_set_bit(e) <= find_first_set_bit(s));
+                        (ffsl(e) <= ffsl(s));
         unsigned long n;
 
         n = init_node_heap(nid, s, nr_pages, &use_tail);
diff --git a/xen/common/softirq.c b/xen/common/softirq.c
index 321d26902d37..bee4a82009c3 100644
--- a/xen/common/softirq.c
+++ b/xen/common/softirq.c
@@ -48,7 +48,7 @@ static void __do_softirq(unsigned long ignore_mask)
              || cpu_is_offline(cpu) )
             break;
 
-        i = find_first_set_bit(pending);
+        i = ffsl(pending) - 1;
         clear_bit(i, &softirq_pending(cpu));
         (*softirq_handlers[i])();
     }
diff --git a/xen/drivers/passthrough/amd/iommu_map.c b/xen/drivers/passthrough/amd/iommu_map.c
index e0f4fe736a8d..f1061bfc798c 100644
--- a/xen/drivers/passthrough/amd/iommu_map.c
+++ b/xen/drivers/passthrough/amd/iommu_map.c
@@ -137,7 +137,7 @@ static void set_iommu_ptes_present(unsigned long pt_mfn,
         ASSERT(!pde->u);
 
         if ( pde > table )
-            ASSERT(pde->ign0 == find_first_set_bit(pde - table));
+            ASSERT(pde->ign0 == ffsl(pde - table) - 1);
         else
             ASSERT(pde->ign0 == CONTIG_LEVEL_SHIFT);
 
diff --git a/xen/drivers/passthrough/iommu.c b/xen/drivers/passthrough/iommu.c
index ba18136c461c..50bfd62553ae 100644
--- a/xen/drivers/passthrough/iommu.c
+++ b/xen/drivers/passthrough/iommu.c
@@ -305,7 +305,7 @@ static unsigned int mapping_order(const struct domain_iommu *hd,
 {
     unsigned long res = dfn_x(dfn) | mfn_x(mfn);
     unsigned long sizes = hd->platform_ops->page_sizes;
-    unsigned int bit = find_first_set_bit(sizes), order = 0;
+    unsigned int bit = ffsl(sizes) - 1, order = 0;
 
     ASSERT(bit == PAGE_SHIFT);
 
@@ -313,7 +313,7 @@ static unsigned int mapping_order(const struct domain_iommu *hd,
     {
         unsigned long mask;
 
-        bit = find_first_set_bit(sizes);
+        bit = ffsl(sizes) - 1;
         mask = (1UL << bit) - 1;
         if ( nr <= mask || (res & mask) )
             break;
diff --git a/xen/drivers/passthrough/x86/iommu.c b/xen/drivers/passthrough/x86/iommu.c
index 304a2f5480c7..cc0062b02712 100644
--- a/xen/drivers/passthrough/x86/iommu.c
+++ b/xen/drivers/passthrough/x86/iommu.c
@@ -641,7 +641,7 @@ struct page_info *iommu_alloc_pgtable(struct domain_iommu *hd,
     if ( contig_mask )
     {
         /* See pt-contig-markers.h for a description of the marker scheme. */
-        unsigned int i, shift = find_first_set_bit(contig_mask);
+        unsigned int i, shift = ffsl(contig_mask) - 1;
 
         ASSERT((CONTIG_LEVEL_SHIFT & (contig_mask >> shift)) == CONTIG_LEVEL_SHIFT);
 
@@ -652,7 +652,7 @@ struct page_info *iommu_alloc_pgtable(struct domain_iommu *hd,
 
         for ( i = 4; i < PAGE_SIZE / sizeof(*p); i += 4 )
         {
-            p[i + 0] = (find_first_set_bit(i) + 0ULL) << shift;
+            p[i + 0] = (ffsl(i) - 1ULL) << shift;
             p[i + 1] = 0;
             p[i + 2] = 1ULL << shift;
             p[i + 3] = 0;
-- 
2.30.2

[PATCH v2 10/13] xen/bitops: Delete find_first_set_bit()

[Andrew Cooper]

No more users.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Reorder from later in the series to keep ARM bisectable
---
 xen/arch/arm/include/asm/bitops.h |  9 ---------
 xen/arch/ppc/include/asm/bitops.h |  9 ---------
 xen/arch/x86/include/asm/bitops.h | 12 ------------
 3 files changed, 30 deletions(-)

diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index ba39802c9de3..d30ba44598e3 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -160,15 +160,6 @@ static inline int fls(unsigned int x)
 #define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
 #define arch_ffsl(x) ((x) ? 1 + __builtin_ctzl(x) : 0)
 
-/**
- * find_first_set_bit - find the first set bit in @word
- * @word: the word to search
- *
- * Returns the bit-number of the first set bit (first bit being 0).
- * The input must *not* be zero.
- */
-#define find_first_set_bit(w) (ffsl(w) - 1)
-
 /**
  * hweightN - returns the hamming weight of a N-bit word
  * @x: the word to weigh
diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
index ce0f6436f727..761361291e6f 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -187,13 +187,4 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
 #define hweight16(x) __builtin_popcount((uint16_t)(x))
 #define hweight8(x)  __builtin_popcount((uint8_t)(x))
 
-/**
- * find_first_set_bit - find the first set bit in @word
- * @word: the word to search
- *
- * Returns the bit-number of the first set bit (first bit being 0).
- * The input must *not* be zero.
- */
-#define find_first_set_bit(x) (ffsl(x) - 1)
-
 #endif /* _ASM_PPC_BITOPS_H */
diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
index 51d3c0f40473..830e488f33a0 100644
--- a/xen/arch/x86/include/asm/bitops.h
+++ b/xen/arch/x86/include/asm/bitops.h
@@ -401,18 +401,6 @@ static always_inline unsigned int __scanbit(unsigned long val, unsigned int max)
     r__;                                                                    \
 })
 
-/**
- * find_first_set_bit - find the first set bit in @word
- * @word: the word to search
- * 
- * Returns the bit-number of the first set bit. The input must *not* be zero.
- */
-static inline unsigned int find_first_set_bit(unsigned long word)
-{
-    asm ( "rep; bsf %1,%0" : "=r" (word) : "rm" (word) );
-    return (unsigned int)word;
-}
-
 static always_inline unsigned int arch_ffs(unsigned int x)
 {
     unsigned int r;
-- 
2.30.2

[PATCH v2 11/13] xen/bitops: Implement fls()/flsl() in common logic

[Andrew Cooper]

From: Oleksii Kurochko <oleksii.kurochko@gmail.com>

This is most easily done together because of how arm32 is currently
structured, but it does just mirror the existing ffs()/ffsl() work.

Introduce compile and boot time testing.

Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New, incorperated from Oleksii's RISC-V series and adjusted.

for x86:

  add/remove: 0/0 grow/shrink: 3/17 up/down: 28/-153 (-125)
  Function                                     old     new   delta
  pci_enable_msi                              1033    1049     +16
  vlapic_lowest_prio                           330     338      +8
  kexec_early_calculations                      53      57      +4
  pci_restore_msi_state                       1159    1157      -2
  arch_hwdom_irqs                               61      59      -2
  control_read                                 132     129      -3
  pci_enable_msi.cold                          121     117      -4
  arch_get_dma_bitsize                         173     169      -4
  xmem_pool_alloc                             1039    1032      -7
  xenheap_max_mfn                               49      42      -7
  mba_sanitize_thrtl                            83      76      -7
  xstate_init                                  807     799      -8
  offline_page                                 965     957      -8
  apicid_to_socket                             160     152      -8
  vlapic_find_highest_vector                    61      48     -13
  xmem_pool_free                               983     967     -16
  iommu_alloc                                  935     919     -16
  free_heap_pages                             1512    1496     -16
  detect_ht                                    318     302     -16
  alloc_heap_pages                            1569    1553     -16

showing that the optimiser can now do a better job in most cases.
---
 xen/arch/arm/include/asm/arm32/bitops.h |  2 --
 xen/arch/arm/include/asm/arm64/bitops.h | 12 -------
 xen/arch/arm/include/asm/bitops.h       | 19 ++--------
 xen/arch/ppc/include/asm/bitops.h       |  4 +--
 xen/arch/x86/include/asm/bitops.h       | 46 +++++++++++++++----------
 xen/common/bitops.c                     | 25 ++++++++++++++
 xen/include/xen/bitops.h                | 24 +++++++++++++
 7 files changed, 80 insertions(+), 52 deletions(-)

diff --git a/xen/arch/arm/include/asm/arm32/bitops.h b/xen/arch/arm/include/asm/arm32/bitops.h
index d0309d47c188..0d7bb12d5c19 100644
--- a/xen/arch/arm/include/asm/arm32/bitops.h
+++ b/xen/arch/arm/include/asm/arm32/bitops.h
@@ -1,8 +1,6 @@
 #ifndef _ARM_ARM32_BITOPS_H
 #define _ARM_ARM32_BITOPS_H
 
-#define flsl fls
-
 /*
  * Little endian assembly bitops.  nr = 0 -> byte 0 bit 0.
  */
diff --git a/xen/arch/arm/include/asm/arm64/bitops.h b/xen/arch/arm/include/asm/arm64/bitops.h
index 906d84e5f295..a6135838dcfa 100644
--- a/xen/arch/arm/include/asm/arm64/bitops.h
+++ b/xen/arch/arm/include/asm/arm64/bitops.h
@@ -1,18 +1,6 @@
 #ifndef _ARM_ARM64_BITOPS_H
 #define _ARM_ARM64_BITOPS_H
 
-static inline int flsl(unsigned long x)
-{
-        uint64_t ret;
-
-        if (__builtin_constant_p(x))
-               return generic_flsl(x);
-
-        asm("clz\t%0, %1" : "=r" (ret) : "r" (x));
-
-        return BITS_PER_LONG - ret;
-}
-
 /* Based on linux/include/asm-generic/bitops/find.h */
 
 #ifndef CONFIG_GENERIC_FIND_FIRST_BIT
diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
index d30ba44598e3..8f4bdc09d128 100644
--- a/xen/arch/arm/include/asm/bitops.h
+++ b/xen/arch/arm/include/asm/bitops.h
@@ -140,25 +140,10 @@ static inline int test_bit(int nr, const volatile void *addr)
         return 1UL & (p[BITOP_WORD(nr)] >> (nr & (BITOP_BITS_PER_WORD-1)));
 }
 
-/*
- * On ARMv5 and above those functions can be implemented around
- * the clz instruction for much better code efficiency.
- */
-
-static inline int fls(unsigned int x)
-{
-        int ret;
-
-        if (__builtin_constant_p(x))
-               return generic_flsl(x);
-
-        asm("clz\t%"__OP32"0, %"__OP32"1" : "=r" (ret) : "r" (x));
-        return 32 - ret;
-}
-
-
 #define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
 #define arch_ffsl(x) ((x) ? 1 + __builtin_ctzl(x) : 0)
+#define arch_fls(x)  ((x) ? 32 - __builtin_clz(x) : 0)
+#define arch_flsl(x) ((x) ? BITS_PER_LONG - __builtin_clzl(x) : 0)
 
 /**
  * hweightN - returns the hamming weight of a N-bit word
diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
index 761361291e6f..8119b5ace877 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -171,10 +171,10 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
     return (old & mask) != 0;
 }
 
-#define flsl(x) generic_flsl(x)
-#define fls(x) generic_flsl(x)
 #define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
 #define arch_ffsl(x) ((x) ? 1 + __builtin_ctzl(x) : 0)
+#define arch_fls(x)  ((x) ? 32 - __builtin_clz(x) : 0)
+#define arch_flsl(x) ((x) ? BITS_PER_LONG - __builtin_clzl(x) : 0)
 
 /**
  * hweightN - returns the hamming weight of a N-bit word
diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
index 830e488f33a0..fc9fe73ad5ba 100644
--- a/xen/arch/x86/include/asm/bitops.h
+++ b/xen/arch/x86/include/asm/bitops.h
@@ -447,33 +447,41 @@ static always_inline unsigned int arch_ffsl(unsigned long x)
 }
 #define arch_ffsl arch_ffsl
 
-/**
- * fls - find last bit set
- * @x: the word to search
- *
- * This is defined the same way as ffs.
- */
-static inline int flsl(unsigned long x)
+static always_inline unsigned int arch_fls(unsigned int x)
 {
-    long r;
+    unsigned int r;
+
+    /* See arch_ffs() for safety discussions. */
+    if ( __builtin_constant_p(x > 0) && x > 0 )
+        asm ( "bsr %[val], %[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x) );
+    else
+        asm ( "bsr %[val], %[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x), "[res]" (-1) );
 
-    asm ( "bsr %1,%0\n\t"
-          "jnz 1f\n\t"
-          "mov $-1,%0\n"
-          "1:" : "=r" (r) : "rm" (x));
-    return (int)r+1;
+    return r + 1;
 }
+#define arch_fls arch_fls
 
-static inline int fls(unsigned int x)
+static always_inline unsigned int arch_flsl(unsigned long x)
 {
-    int r;
+    unsigned int r;
+
+    /* See arch_ffs() for safety discussions. */
+    if ( __builtin_constant_p(x > 0) && x > 0 )
+        asm ( "bsr %[val], %q[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x) );
+    else
+        asm ( "bsr %[val], %q[res]"
+              : [res] "=r" (r)
+              : [val] "rm" (x), "[res]" (-1) );
 
-    asm ( "bsr %1,%0\n\t"
-          "jnz 1f\n\t"
-          "mov $-1,%0\n"
-          "1:" : "=r" (r) : "rm" (x));
     return r + 1;
 }
+#define arch_flsl arch_flsl
 
 /**
  * hweightN - returns the hamming weight of a N-bit word
diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index b3813f818198..b4845d9e84d1 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -26,7 +26,32 @@ static void __init test_ffs(void)
 #endif
 }
 
+static void __init test_fls(void)
+{
+    /* unsigned int fls(unsigned int) */
+    CHECK(fls, 0, 0);
+    CHECK(fls, 1, 1);
+    CHECK(fls, 3, 2);
+    CHECK(fls, 7, 3);
+    CHECK(fls, 6, 3);
+    CHECK(fls, 0x80000000U, 32);
+
+    /* unsigned int flsl(unsigned long) */
+    CHECK(flsl, 0, 0);
+    CHECK(flsl, 1, 1);
+    CHECK(flsl, 3, 2);
+    CHECK(flsl, 7, 3);
+    CHECK(flsl, 6, 3);
+
+    CHECK(flsl, 1 | (1UL << (BITS_PER_LONG - 1)), BITS_PER_LONG);
+#if BITS_PER_LONG > 32
+    CHECK(flsl, 1 | (1UL << 32), 33);
+    CHECK(flsl, 1 | (1UL << 63), 64);
+#endif
+}
+
 static void __init __constructor test_bitops(void)
 {
     test_ffs();
+    test_fls();
 }
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index 88cf27a88bcf..e7df6377372d 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -60,6 +60,30 @@ static always_inline __pure unsigned int ffsl(unsigned long x)
 #endif
 }
 
+static always_inline __pure unsigned int fls(unsigned int x)
+{
+    if ( __builtin_constant_p(x) )
+        return x ? 32 - __builtin_clz(x) : 0;
+
+#ifdef arch_fls
+    return arch_fls(x);
+#else
+    return generic_flsl(x);
+#endif
+}
+
+static always_inline __pure unsigned int flsl(unsigned long x)
+{
+    if ( __builtin_constant_p(x) )
+        return x ? BITS_PER_LONG - __builtin_clzl(x) : 0;
+
+#ifdef arch_fls
+    return arch_flsl(x);
+#else
+    return generic_flsl(x);
+#endif
+}
+
 /* --------------------- Please tidy below here --------------------- */
 
 #ifndef find_next_bit
-- 
2.30.2

[PATCH v2 12/13] xen/bitops: Clean up ffs64()/fls64() definitions

[Andrew Cooper]

Implement ffs64() and fls64() as plain static inlines, dropping the ifdefary
and intermediate generic_f?s64() forms.

Add tests for all interesting bit positions at 32bit boundaries.

No functional change.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * Use ULL rather than a uint64_t cast.
 * Extend to fls64() too.
---
 xen/common/bitops.c      | 32 ++++++++++++++++++++++++++++++
 xen/include/xen/bitops.h | 42 +++++++++++++++++++---------------------
 2 files changed, 52 insertions(+), 22 deletions(-)

diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index b4845d9e84d1..5482e5a1218d 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -24,6 +24,22 @@ static void __init test_ffs(void)
     CHECK(ffsl, 1UL << 32, 33);
     CHECK(ffsl, 1UL << 63, 64);
 #endif
+
+    /*
+     * unsigned int ffs64(uint64_t)
+     *
+     * 32-bit builds of Xen have to split this into two adjacent operations,
+     * so test all interesting bit positions across the divide.
+     */
+    CHECK(ffs64, 0, 0);
+    CHECK(ffs64, 1, 1);
+    CHECK(ffs64, 3, 1);
+    CHECK(ffs64, 7, 1);
+    CHECK(ffs64, 6, 2);
+
+    CHECK(ffs64, 0x8000000080000000ULL, 32);
+    CHECK(ffs64, 0x8000000100000000ULL, 33);
+    CHECK(ffs64, 0x8000000000000000ULL, 64);
 }
 
 static void __init test_fls(void)
@@ -48,6 +64,22 @@ static void __init test_fls(void)
     CHECK(flsl, 1 | (1UL << 32), 33);
     CHECK(flsl, 1 | (1UL << 63), 64);
 #endif
+
+    /*
+     * unsigned int ffl64(uint64_t)
+     *
+     * 32-bit builds of Xen have to split this into two adjacent operations,
+     * so test all interesting bit positions across the divide.
+     */
+    CHECK(fls64, 0, 0);
+    CHECK(fls64, 1, 1);
+    CHECK(fls64, 3, 2);
+    CHECK(fls64, 7, 3);
+    CHECK(fls64, 6, 3);
+
+    CHECK(fls64, 0x0000000080000001ULL, 32);
+    CHECK(fls64, 0x0000000100000001ULL, 33);
+    CHECK(fls64, 0x8000000000000001ULL, 64);
 }
 
 static void __init __constructor test_bitops(void)
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index e7df6377372d..c5518d2c8552 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -60,6 +60,14 @@ static always_inline __pure unsigned int ffsl(unsigned long x)
 #endif
 }
 
+static always_inline __pure unsigned int ffs64(uint64_t x)
+{
+    if ( BITS_PER_LONG == 64 )
+        return ffsl(x);
+    else
+        return !x || (uint32_t)x ? ffs(x) : ffs(x >> 32) + 32;
+}
+
 static always_inline __pure unsigned int fls(unsigned int x)
 {
     if ( __builtin_constant_p(x) )
@@ -84,6 +92,18 @@ static always_inline __pure unsigned int flsl(unsigned long x)
 #endif
 }
 
+static always_inline __pure unsigned int fls64(uint64_t x)
+{
+    if ( BITS_PER_LONG == 64 )
+        return flsl(x);
+    else
+    {
+        uint32_t h = x >> 32;
+
+        return h ? fls(h) + 32 : fls(x);
+    }
+}
+
 /* --------------------- Please tidy below here --------------------- */
 
 #ifndef find_next_bit
@@ -134,28 +154,6 @@ 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
-#else
-# ifndef ffs64
-static inline int generic_ffs64(__u64 x)
-{
-    return !x || (__u32)x ? ffs(x) : ffs(x >> 32) + 32;
-}
-#  define ffs64 generic_ffs64
-# endif
-# ifndef fls64
-static inline int generic_fls64(__u64 x)
-{
-    __u32 h = x >> 32;
-
-    return h ? fls(h) + 32 : fls(x);
-}
-#  define fls64 generic_fls64
-# endif
-#endif
-
 static inline int get_bitmask_order(unsigned int count)
 {
     int order;
-- 
2.30.2

[PATCH v2 13/13] xen/bitops: Rearrange the top of xen/bitops.h

[Andrew Cooper]

The #include <asm/bitops.h> can move to the top of the file now now that
generic_f?s() have been untangled.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2:
 * New
---
 xen/include/xen/bitops.h | 18 +++---------------
 1 file changed, 3 insertions(+), 15 deletions(-)

diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index c5518d2c8552..6a5e28730a25 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -4,6 +4,8 @@
 #include <xen/compiler.h>
 #include <xen/types.h>
 
+#include <asm/bitops.h>
+
 /*
  * Create a contiguous bitmask starting at bit position @l and ending at
  * position @h. For example GENMASK(30, 21) gives us 0x7fe00000ul.
@@ -15,27 +17,13 @@
     (((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LLONG - 1 - (h))))
 
 /*
- * Find First/Last Set bit.
+ * Find First/Last Set bit (all forms).
  *
  * Bits are labelled from 1.  Returns 0 if given 0.
  */
 unsigned int __pure generic_ffsl(unsigned long x);
 unsigned int __pure generic_flsl(unsigned long x);
 
-/*
- * Include this here because some architectures need generic_ffs/fls in
- * scope
- */
-
-/* --------------------- Please tidy above here --------------------- */
-
-#include <asm/bitops.h>
-
-/*
- * Find First/Last Set bit (all forms).
- *
- * Bits are labelled from 1.  Returns 0 if given 0.
- */
 static always_inline __pure unsigned int ffs(unsigned int x)
 {
     if ( __builtin_constant_p(x) )
-- 
2.30.2

Re: [PATCH v2 04/13] xen/page_alloc: Coerce min(flsl(), foo) expressions to being unsigned

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> This is in order to maintain bisectability through the subsequent changes,
> where flsl() changes sign-ness non-atomically by architecture.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCH v2 02/13] xen/bitops: Cleanup ahead of rearrangements

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
>  * Rename __attribute_pure__ to just __pure before it gains users.
>  * Introduce __constructor which is going to be used in lib/, and is
>    unconditionally cf_check.
>  * Identify the areas of xen/bitops.h which are a mess.
>  * Introduce xen/boot-check.h as helpers for compile and boot time testing.
>    This provides a statement of the ABI, and a confirmation that arch-specific
>    implementations behave as expected.
> 
> Sadly Clang 7 and older isn't happy with the compile time checks.  Skip them,
> and just rely on the runtime checks.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

Further remarks, though:

> ---
>  xen/include/xen/bitops.h     | 13 ++++++--
>  xen/include/xen/boot-check.h | 60 ++++++++++++++++++++++++++++++++++++
>  xen/include/xen/compiler.h   |  3 +-
>  3 files changed, 72 insertions(+), 4 deletions(-)
>  create mode 100644 xen/include/xen/boot-check.h

The bulk of the changes isn't about bitops; it's just that you're intending
to first use it for testing there. The subject prefix therefore is somewhat
misleading.

> --- /dev/null
> +++ b/xen/include/xen/boot-check.h
> @@ -0,0 +1,60 @@
> +/* SPDX-License-Identifier: GPL-2.0-or-later */
> +
> +/*
> + * Helpers for boot-time checks of basic logic, including confirming that
> + * examples which should be calculated by the compiler are.
> + */
> +#ifndef XEN_BOOT_CHECK_H
> +#define XEN_BOOT_CHECK_H
> +
> +#include <xen/lib.h>
> +
> +/* Hide a value from the optimiser. */
> +#define HIDE(x)                                                         \
> +    ({ typeof(x) _x = (x); asm volatile ( "" : "+r" (_x) ); _x; })

In principle this is a macro that could be of use elsewhere. That's also
reflected in its entirely generic name. It therefore feels mis-placed in
this header. Otoh though the use of "+r" is more restricting than truly
necessary: While I'm not sure if "+g" would work, i.e. if that wouldn't
cause issues with literals, pretty surely "+rm" ought to work, removing
the strict requirement for the compiler to put a certain value in a
register.

Assuming you may have reservations against "+g" / "+rm" (and hence the
construct wants keeping here), maybe rename to e.g. BOOT_CHECK_HIDE()?
Alternatively, if generalized, moving to xen/macros.h would seem
appropriate to me.

Finally, plainly as a remark with no request for any change (but
possibly a minor argument against moving to xen/macros.h), this construct
won't, afaict, work if x is of array(-of-const) type. A more specialized
variant may need introducing, should any such use ever appear.

Jan

Re: [PATCH v2 05/13] xen/bitops: Implement generic_f?sl() in lib/

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> generic_f?s() being static inline is the cause of lots of the complexity
> between the common and arch-specific bitops.h
> 
> They appear to be static inline for constant-folding reasons (ARM uses them
> for this), but there are better ways to achieve the same effect.
> 
> It is presumptuous that an unrolled binary search is the right algorithm to
> use on all microarchitectures.  Indeed, it's not for the eventual users, but
> that can be addressed at a later point.
> 
> It is also nonsense to implement the int form as the base primitive and
> construct the long form from 2x int in 64-bit builds, when it's just one extra
> step to operate at the native register width.
> 
> Therefore, implement generic_f?sl() in lib/.  They're not actually needed in
> x86/ARM/PPC by the end of the cleanup (i.e. the functions will be dropped by
> the linker), and they're only expected be needed by RISC-V on hardware which
> lacks the Zbb extension.
> 
> Implement generic_fls() in terms of generic_flsl() for now, but this will be
> cleaned up in due course.
> 
> Provide basic runtime testing using __constructor inside the lib/ file.  This
> is important, as it means testing runs if and only if generic_f?sl() are used
> elsewhere in Xen.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>
with a suggestion and a question.

> I suspect we want to swap CONFIG_DEBUG for CONFIG_BOOT_UNIT_TESTS in due
> course.  These ought to be able to be used in a release build too.

+1

> --- /dev/null
> +++ b/xen/lib/generic-ffsl.c
> @@ -0,0 +1,65 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +
> +#include <xen/bitops.h>
> +#include <xen/boot-check.h>
> +#include <xen/init.h>
> +
> +unsigned int generic_ffsl(unsigned long x)
> +{
> +    unsigned int r = 1;
> +
> +    if ( !x )
> +        return 0;
> +
> +#if BITS_PER_LONG > 32

To be future-proof, perhaps ahead of this

#if BITS_PER_LONG > 64
# error "..."
#endif

or a functionally similar BUILD_BUG_ON()?

> --- /dev/null
> +++ b/xen/lib/generic-flsl.c
> @@ -0,0 +1,68 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +
> +#include <xen/bitops.h>
> +#include <xen/boot-check.h>
> +#include <xen/init.h>
> +
> +/* Mask of type UL with the upper x bits set. */
> +#define UPPER_MASK(x) (~0UL << (BITS_PER_LONG - (x)))
> +
> +unsigned int generic_flsl(unsigned long x)
> +{
> +    unsigned int r = BITS_PER_LONG;
> +
> +    if ( !x )
> +        return 0;
> +
> +#if BITS_PER_LONG > 32
> +    if ( !(x & UPPER_MASK(32)) )
> +    {
> +        x <<= 32;
> +        r -= 32;
> +    }
> +#endif
> +    if ( !(x & UPPER_MASK(16)) )
> +    {
> +        x <<= 16;
> +        r -= 16;
> +    }
> +    if ( !(x & UPPER_MASK(8)) )
> +    {
> +        x <<= 8;
> +        r -= 8;
> +    }
> +    if ( !(x & UPPER_MASK(4)) )
> +    {
> +        x <<= 4;
> +        r -= 4;
> +    }
> +    if ( !(x & UPPER_MASK(2)) )
> +    {
> +        x <<= 2;
> +        r -= 2;
> +    }
> +    if ( !(x & UPPER_MASK(1)) )
> +    {
> +        x <<= 1;
> +        r -= 1;
> +    }
> +
> +    return r;
> +}

While, as you say, the expectation is for this code to not commonly come
into actual use, I still find the algorithm a little inefficient in terms
of the constants used, specifically considering how they would need
instantiating in resulting assembly. It may be that Arm's fancy constant-
move insns can actually efficiently synthesize them, but I think on most
other architectures it would be more efficient (and presumably no less
efficient on Arm) to shift the "remaining" value right, thus allowing for
successively smaller (and hence easier to instantiate) constants to be
used.

Jan

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> Perform constant-folding unconditionally, rather than having it implemented
> inconsistency between architectures.
> 
> Confirm the expected behaviour with compile time and boot time tests.
> 
> For non-constant inputs, use arch_ffs() if provided but fall back to
> generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin that
> works in all configurations.
> 
> For x86, rename ffs() to arch_ffs() and adjust the prototype.
> 
> For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to
> generic_fls().  Drop the definition entirely.  ARM too benefits in the general
> case by using __builtin_ctz(), but less dramatically because it using
> optimised asm().
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> The asm in arch_ffs() is safe but inefficient.
> 
> CMOV would be an improvement over a conditional branch, but for 64bit CPUs
> both Intel and AMD have provided enough details about the behaviour for a zero
> input.  It is safe to pre-load the destination register with -1 and drop the
> conditional logic.
> 
> However, it is common to find ffs() in a context where the optimiser knows
> that x in nonzero even if it the value isn't known precisely, and in that case
> it's safe to drop the preload of -1 too.
> 
> There are only a handful of uses of ffs() in the x86 build, and all of them
> improve as a result of this:
> 
>   add/remove: 0/0 grow/shrink: 0/2 up/down: 0/-31 (-31)
>   Function                                     old     new   delta
>   mask_write                                   114     107      -7
>   xmem_pool_alloc                             1063    1039     -24
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>
with one suggestion:

> --- a/xen/arch/x86/include/asm/bitops.h
> +++ b/xen/arch/x86/include/asm/bitops.h
> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>  
>  static always_inline unsigned int arch_ffs(unsigned int x)
>  {
> -    int r;
> +    unsigned int r;
> +
> +    if ( __builtin_constant_p(x > 0) && x > 0 )

__builtin_constant_p(x) surely will do. In fact even the other "> 0" could
in principle be left out here.

Jan

Re: [PATCH v2 08/13] xen/bitops: Implement ffsl() in common logic

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> Just like ffs() in the previous changes.  Express the upper bound of the
> testing in terms of BITS_PER_LONG as it varies between architectures.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

> @@ -458,6 +441,24 @@ static always_inline unsigned int arch_ffs(unsigned int x)
>  }
>  #define arch_ffs arch_ffs
>  
> +static always_inline unsigned int arch_ffsl(unsigned long x)
> +{
> +    unsigned int r;
> +
> +    /* See arch_ffs() for safety discussions. */
> +    if ( __builtin_constant_p(x > 0) && x > 0 )

See remark on arch_ffs() for possible slight reduction of code.

Jan

Re: [PATCH v2 09/13] xen/bitops: Replace find_first_set_bit() with ffsl() - 1

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> --- a/xen/arch/x86/hvm/hpet.c
> +++ b/xen/arch/x86/hvm/hpet.c
> @@ -335,7 +335,7 @@ static void timer_sanitize_int_route(HPETState *h, unsigned int tn)
>       * enabled pick the first irq.
>       */
>      timer_config(h, tn) |=
> -        MASK_INSR(find_first_set_bit(timer_int_route_cap(h, tn)),
> +        MASK_INSR(ffsl(timer_int_route_cap(h, tn)) - 1,
>                    HPET_TN_ROUTE);
>  }

This can be just ffs().

> @@ -409,7 +409,7 @@ static int cf_check hpet_write(
>          {
>              bool active;
>  
> -            i = find_first_set_bit(new_val);
> +            i = ffsl(new_val) - 1;
>              if ( i >= HPET_TIMER_NUM )
>                  break;

This in principle can be, too, but would require a little further care.

> @@ -535,14 +535,14 @@ static int cf_check hpet_write(
>      /* stop/start timers whos state was changed by this write. */
>      while (stop_timers)
>      {
> -        i = find_first_set_bit(stop_timers);
> +        i = ffsl(stop_timers) - 1;
>          __clear_bit(i, &stop_timers);
>          hpet_stop_timer(h, i, guest_time);
>      }
>  
>      while (start_timers)
>      {
> -        i = find_first_set_bit(start_timers);
> +        i = ffsl(start_timers) - 1;
>          __clear_bit(i, &start_timers);
>          hpet_set_timer(h, i, guest_time);
>      }

Same here; in fact {start,stop}_timers are needlessly unsigned long in
the first place.

> --- a/xen/arch/x86/include/asm/pt-contig-markers.h
> +++ b/xen/arch/x86/include/asm/pt-contig-markers.h
> @@ -60,7 +60,7 @@ static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx,
>      /* Step 1: Reduce markers in lower numbered entries. */
>      while ( i )
>      {
> -        b = find_first_set_bit(i);
> +        b = ffsl(i) - 1;
>          i &= ~(1U << b);

Considering i's type and the immediately following expression, this again
can easily be just ffs().

> --- a/xen/drivers/passthrough/amd/iommu_map.c
> +++ b/xen/drivers/passthrough/amd/iommu_map.c
> @@ -137,7 +137,7 @@ static void set_iommu_ptes_present(unsigned long pt_mfn,
>          ASSERT(!pde->u);
>  
>          if ( pde > table )
> -            ASSERT(pde->ign0 == find_first_set_bit(pde - table));
> +            ASSERT(pde->ign0 == ffsl(pde - table) - 1);

pde pointing into the page starting at table, this can be ffs(), too.

Preferably with at least the easy adjustments done:
Reviewed-by: Jan Beulich <jbeulich@suse.com>

Jan

Re: [PATCH v2 10/13] xen/bitops: Delete find_first_set_bit()

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> No more users.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Acked-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> --- a/xen/arch/x86/include/asm/bitops.h
> +++ b/xen/arch/x86/include/asm/bitops.h
> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>  
>  static always_inline unsigned int arch_ffs(unsigned int x)
>  {
> -    int r;
> +    unsigned int r;
> +
> +    if ( __builtin_constant_p(x > 0) && x > 0 )
> +    {
> +        /* Safe, when the compiler knows that x is nonzero. */
> +        asm ( "bsf %[val], %[res]"
> +              : [res] "=r" (r)
> +              : [val] "rm" (x) );
> +    }

In patch 11 relevant things are all in a single patch, making it easier
to spot that this is dead code: The sole caller already has a
__builtin_constant_p(), hence I don't see how the one here could ever
return true. With that the respective part of the description is then
questionable, too, I'm afraid: Where did you observe any actual effect
from this? Or if you did - what am I missing?

Jan

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Jan Beulich]

On 27.05.2024 15:27, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
>> --- a/xen/arch/x86/include/asm/bitops.h
>> +++ b/xen/arch/x86/include/asm/bitops.h
>> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>>  
>>  static always_inline unsigned int arch_ffs(unsigned int x)
>>  {
>> -    int r;
>> +    unsigned int r;
>> +
>> +    if ( __builtin_constant_p(x > 0) && x > 0 )
>> +    {
>> +        /* Safe, when the compiler knows that x is nonzero. */
>> +        asm ( "bsf %[val], %[res]"
>> +              : [res] "=r" (r)
>> +              : [val] "rm" (x) );
>> +    }
> 
> In patch 11 relevant things are all in a single patch, making it easier
> to spot that this is dead code: The sole caller already has a
> __builtin_constant_p(), hence I don't see how the one here could ever
> return true. With that the respective part of the description is then
> questionable, too, I'm afraid: Where did you observe any actual effect
> from this? Or if you did - what am I missing?

Hmm, thinking about it: I suppose that's why you have
__builtin_constant_p(x > 0), not __builtin_constant_p(x). I have to admit
I'm (positively) surprised that the former may return true when the latter
doesn't. Nevertheless I'm inclined to think this deserves a brief comment.

As an aside, to better match the comment inside the if()'s body, how about

    if ( __builtin_constant_p(!!x) && x )

? That also may make a little more clear that this isn't just a style
choice, but actually needed for the intended purpose.

Jan

Re: [PATCH v2 11/13] xen/bitops: Implement fls()/flsl() in common logic

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> From: Oleksii Kurochko <oleksii.kurochko@gmail.com>
> 
> This is most easily done together because of how arm32 is currently
> structured, but it does just mirror the existing ffs()/ffsl() work.
> 
> Introduce compile and boot time testing.
> 
> Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com>
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>
with small adjustments possibly to be done on the earlier similar patches
also done here.

Jan

Re: [PATCH v2 12/13] xen/bitops: Clean up ffs64()/fls64() definitions

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> Implement ffs64() and fls64() as plain static inlines, dropping the ifdefary
> and intermediate generic_f?s64() forms.
> 
> Add tests for all interesting bit positions at 32bit boundaries.
> 
> No functional change.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>
with two remarks:

> --- a/xen/common/bitops.c
> +++ b/xen/common/bitops.c
> @@ -24,6 +24,22 @@ static void __init test_ffs(void)
>      CHECK(ffsl, 1UL << 32, 33);
>      CHECK(ffsl, 1UL << 63, 64);
>  #endif
> +
> +    /*
> +     * unsigned int ffs64(uint64_t)
> +     *
> +     * 32-bit builds of Xen have to split this into two adjacent operations,
> +     * so test all interesting bit positions across the divide.
> +     */
> +    CHECK(ffs64, 0, 0);
> +    CHECK(ffs64, 1, 1);
> +    CHECK(ffs64, 3, 1);
> +    CHECK(ffs64, 7, 1);
> +    CHECK(ffs64, 6, 2);
> +
> +    CHECK(ffs64, 0x8000000080000000ULL, 32);
> +    CHECK(ffs64, 0x8000000100000000ULL, 33);
> +    CHECK(ffs64, 0x8000000000000000ULL, 64);

With the intermediate blank line, the respective part of the comment doesn't
look to be related to these 3 lines. Could I talk you into moving that part
down?

> --- a/xen/include/xen/bitops.h
> +++ b/xen/include/xen/bitops.h
> @@ -60,6 +60,14 @@ static always_inline __pure unsigned int ffsl(unsigned long x)
>  #endif
>  }
>  
> +static always_inline __pure unsigned int ffs64(uint64_t x)
> +{
> +    if ( BITS_PER_LONG == 64 )

In principle >= 64 would be okay here, and hence I'd prefer if we used that
less strict form. Yet I'm not going to insist.

Jan

Re: [PATCH v2 13/13] xen/bitops: Rearrange the top of xen/bitops.h

[Jan Beulich]

On 24.05.2024 22:03, Andrew Cooper wrote:
> The #include <asm/bitops.h> can move to the top of the file now now that
> generic_f?s() have been untangled.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Acked-by: Jan Beulich <jbeulich@suse.com>

Re: [PATCH v2 for-4.19 00/13] xen/bitops: Untangle ffs()/fls() infrastructure

[Oleksii K.]

I think we can consider to have this patch series in Xen 4.19 release:
 Release-acked-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> 

~ Oleksii
On Fri, 2024-05-24 at 21:03 +0100, Andrew Cooper wrote:
> bitops.h is a mess.  It has grown organtically over many years, and
> forces
> unreasonable repsonsibilities out into the per-arch stubs.
> 
> Start cleaning it up with ffs() and friends.  Across the board, this
> adds:
> 
>  * Functioning bitops without arch-specific asm
>  * An option for arches to provide more optimal code generation
>  * Compile-time constant folding
>  * Testing at both compile time and during init that the basic
> operations
>    behave according to spec.
> 
> and the only reason this series isn't a net reduction in code alone
> is the
> because of the new unit testing.
> 
> This form is superior in many ways, including getting RISC-V support
> for free.
> 
> v2:
>  * Many changes.  See patches for details
>  * Include the fls() side of the infrastructure too.
> 
> Testing:
>  
> https://gitlab.com/xen-project/people/andyhhp/xen/-/pipelines/1304664544
>   https://cirrus-ci.com/github/andyhhp/xen/
> 
> Series-wide net bloat-o-meter:
> 
>   x86:   up/down: 51/-247 (-196)
>   ARM64: up/down: 40/-400 (-360)
> 
> and PPC64 reproduced in full, just to demonstrate how absurd it was
> to have
> generic_f?s() as static inlines...
> 
>   add/remove: 1/0 grow/shrink: 1/11 up/down: 228/-4832 (-4604)
>   Function                                     old     new   delta
>   init_constructors                              -     220    +220
>   start_xen                                     92     100      +8
>   alloc_heap_pages                            1980    1744    -236
>   xenheap_max_mfn                              360     120    -240
>   free_heap_pages                              784     536    -248
>   find_next_zero_bit                           564     276    -288
>   find_next_bit                                548     260    -288
>   find_first_zero_bit                          444     148    -296
>   find_first_bit                               444     132    -312
>   xmem_pool_free                              1776    1440    -336
>   __do_softirq                                 604     252    -352
>   init_heap_pages                             2328    1416    -912
>   xmem_pool_alloc                             2920    1596   -1324
> 
> 
> Andrew Cooper (12):
>   ppc/boot: Run constructors on boot
>   xen/bitops: Cleanup ahead of rearrangements
>   ARM/bitops: Change find_first_set_bit() to be a define
>   xen/page_alloc: Coerce min(flsl(), foo) expressions to being
> unsigned
>   xen/bitops: Implement generic_f?sl() in lib/
>   xen/bitops: Implement ffs() in common logic
>   x86/bitops: Improve arch_ffs() in the general case
>   xen/bitops: Implement ffsl() in common logic
>   xen/bitops: Replace find_first_set_bit() with ffsl() - 1
>   xen/bitops: Delete find_first_set_bit()
>   xen/bitops: Clean up ffs64()/fls64() definitions
>   xen/bitops: Rearrange the top of xen/bitops.h
> 
> Oleksii Kurochko (1):
>   xen/bitops: Implement fls()/flsl() in common logic
> 
>  xen/arch/arm/include/asm/arm32/bitops.h      |   2 -
>  xen/arch/arm/include/asm/arm64/bitops.h      |  12 --
>  xen/arch/arm/include/asm/bitops.h            |  35 +---
>  xen/arch/ppc/include/asm/bitops.h            |  17 +-
>  xen/arch/ppc/setup.c                         |   2 +
>  xen/arch/x86/guest/xen/xen.c                 |   4 +-
>  xen/arch/x86/hvm/dom0_build.c                |   2 +-
>  xen/arch/x86/hvm/hpet.c                      |   8 +-
>  xen/arch/x86/include/asm/bitops.h            | 114 +++++++------
>  xen/arch/x86/include/asm/pt-contig-markers.h |   2 +-
>  xen/arch/x86/mm.c                            |   2 +-
>  xen/arch/x86/mm/p2m-pod.c                    |   4 +-
>  xen/common/Makefile                          |   1 +
>  xen/common/bitops.c                          |  89 +++++++++++
>  xen/common/page_alloc.c                      |   6 +-
>  xen/common/softirq.c                         |   2 +-
>  xen/drivers/passthrough/amd/iommu_map.c      |   2 +-
>  xen/drivers/passthrough/iommu.c              |   4 +-
>  xen/drivers/passthrough/x86/iommu.c          |   4 +-
>  xen/include/xen/bitops.h                     | 159 ++++++++---------
> --
>  xen/include/xen/boot-check.h                 |  60 +++++++
>  xen/include/xen/compiler.h                   |   3 +-
>  xen/lib/Makefile                             |   2 +
>  xen/lib/generic-ffsl.c                       |  65 ++++++++
>  xen/lib/generic-flsl.c                       |  68 ++++++++
>  25 files changed, 444 insertions(+), 225 deletions(-)
>  create mode 100644 xen/common/bitops.c
>  create mode 100644 xen/include/xen/boot-check.h
>  create mode 100644 xen/lib/generic-ffsl.c
>  create mode 100644 xen/lib/generic-flsl.c
> 

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Andrew Cooper]

On 27/05/2024 2:37 pm, Jan Beulich wrote:
> On 27.05.2024 15:27, Jan Beulich wrote:
>> On 24.05.2024 22:03, Andrew Cooper wrote:
>>> --- a/xen/arch/x86/include/asm/bitops.h
>>> +++ b/xen/arch/x86/include/asm/bitops.h
>>> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>>>  
>>>  static always_inline unsigned int arch_ffs(unsigned int x)
>>>  {
>>> -    int r;
>>> +    unsigned int r;
>>> +
>>> +    if ( __builtin_constant_p(x > 0) && x > 0 )
>>> +    {
>>> +        /* Safe, when the compiler knows that x is nonzero. */
>>> +        asm ( "bsf %[val], %[res]"
>>> +              : [res] "=r" (r)
>>> +              : [val] "rm" (x) );
>>> +    }
>> In patch 11 relevant things are all in a single patch, making it easier
>> to spot that this is dead code: The sole caller already has a
>> __builtin_constant_p(), hence I don't see how the one here could ever
>> return true. With that the respective part of the description is then
>> questionable, too, I'm afraid: Where did you observe any actual effect
>> from this? Or if you did - what am I missing?
> Hmm, thinking about it: I suppose that's why you have
> __builtin_constant_p(x > 0), not __builtin_constant_p(x). I have to admit
> I'm (positively) surprised that the former may return true when the latter
> doesn't.

So was I, but this recommendation came straight from the GCC mailing
list.  And it really does work, even back in obsolete versions of GCC.

__builtin_constant_p() operates on an expression not a value, and is
documented as such.


>  Nevertheless I'm inclined to think this deserves a brief comment.

There is a comment, and it's even visible in the snippet.

> As an aside, to better match the comment inside the if()'s body, how about
>
>     if ( __builtin_constant_p(!!x) && x )
>
> ? That also may make a little more clear that this isn't just a style
> choice, but actually needed for the intended purpose.

I am not changing the logic.

Apart from anything else, your suggestion is trivially buggy.  I care
about whether the RHS collapses to a constant, and the only way of doing
that correctly is asking the compiler about the *exact* expression. 
Asking about some other expression which you hope - but do not know -
that the compiler will treat equivalently is bogus.  It would be
strictly better to only take the else clause, than to have both halves
emitted.

This is the form I've tested extensively.  It's also the clearest form
IMO.  You can experiment with alternative forms when we're not staring
down code freeze of 4.19.

~Andrew

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Jan Beulich]

On 28.05.2024 14:30, Andrew Cooper wrote:
> On 27/05/2024 2:37 pm, Jan Beulich wrote:
>> On 27.05.2024 15:27, Jan Beulich wrote:
>>> On 24.05.2024 22:03, Andrew Cooper wrote:
>>>> --- a/xen/arch/x86/include/asm/bitops.h
>>>> +++ b/xen/arch/x86/include/asm/bitops.h
>>>> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>>>>  
>>>>  static always_inline unsigned int arch_ffs(unsigned int x)
>>>>  {
>>>> -    int r;
>>>> +    unsigned int r;
>>>> +
>>>> +    if ( __builtin_constant_p(x > 0) && x > 0 )
>>>> +    {
>>>> +        /* Safe, when the compiler knows that x is nonzero. */
>>>> +        asm ( "bsf %[val], %[res]"
>>>> +              : [res] "=r" (r)
>>>> +              : [val] "rm" (x) );
>>>> +    }
>>> In patch 11 relevant things are all in a single patch, making it easier
>>> to spot that this is dead code: The sole caller already has a
>>> __builtin_constant_p(), hence I don't see how the one here could ever
>>> return true. With that the respective part of the description is then
>>> questionable, too, I'm afraid: Where did you observe any actual effect
>>> from this? Or if you did - what am I missing?
>> Hmm, thinking about it: I suppose that's why you have
>> __builtin_constant_p(x > 0), not __builtin_constant_p(x). I have to admit
>> I'm (positively) surprised that the former may return true when the latter
>> doesn't.
> 
> So was I, but this recommendation came straight from the GCC mailing
> list.  And it really does work, even back in obsolete versions of GCC.
> 
> __builtin_constant_p() operates on an expression not a value, and is
> documented as such.

Of course.

>>  Nevertheless I'm inclined to think this deserves a brief comment.
> 
> There is a comment, and it's even visible in the snippet.

The comment is about the asm(); it is neither placed to clearly relate
to __builtin_constant_p(), nor is it saying anything about this specific
property of it. You said you were equally surprised; don't you think
that when both of us are surprised, a specific (even if brief) comment
is warranted?

>> As an aside, to better match the comment inside the if()'s body, how about
>>
>>     if ( __builtin_constant_p(!!x) && x )
>>
>> ? That also may make a little more clear that this isn't just a style
>> choice, but actually needed for the intended purpose.
> 
> I am not changing the logic.
> 
> Apart from anything else, your suggestion is trivially buggy.  I care
> about whether the RHS collapses to a constant, and the only way of doing
> that correctly is asking the compiler about the *exact* expression. 
> Asking about some other expression which you hope - but do not know -
> that the compiler will treat equivalently is bogus.  It would be
> strictly better to only take the else clause, than to have both halves
> emitted.
> 
> This is the form I've tested extensively.  It's also the clearest form
> IMO.  You can experiment with alternative forms when we're not staring
> down code freeze of 4.19.

"Clearest form" is almost always a matter of taste. To me, comparing
unsigned values with > or < against 0 is generally at least suspicious.
Using != is typically better (again: imo), and simply omitting the != 0
then is shorter with no difference in effect. Except in peculiar cases
like this one, where indeed it took me some time to figure why the
comparison operator may not be omitted.

All that said: I'm not going to insist on any change; the R-b previously
offered still stands. I would highly appreciate though if the (further)
comment asked for could be added.

What I definitely dislike here is you - not for the first time - turning
down remarks because a change of yours is late. This feels even more so
bad when considering that I'm typically replying to your patches with
pretty little turnaround. Whereas various of mine, pending in part for
years, do not seem to deserve any review comments at all. Unlike before,
where it was "only" improvements or feature additions, meanwhile even
bug fixes are left sit like that. If I may be blunt: This may not work
this way for much longer. At some point I will need to artificially
delay reviews, making them dependent on my own work also being allowed
to make progress. I question though whether that would be in everyone's
interest.

Jan

Re: [PATCH v2 05/13] xen/bitops: Implement generic_f?sl() in lib/

[Andrew Cooper]

On 27/05/2024 9:44 am, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
>> generic_f?s() being static inline is the cause of lots of the complexity
>> between the common and arch-specific bitops.h
>>
>> They appear to be static inline for constant-folding reasons (ARM uses them
>> for this), but there are better ways to achieve the same effect.
>>
>> It is presumptuous that an unrolled binary search is the right algorithm to
>> use on all microarchitectures.  Indeed, it's not for the eventual users, but
>> that can be addressed at a later point.
>>
>> It is also nonsense to implement the int form as the base primitive and
>> construct the long form from 2x int in 64-bit builds, when it's just one extra
>> step to operate at the native register width.
>>
>> Therefore, implement generic_f?sl() in lib/.  They're not actually needed in
>> x86/ARM/PPC by the end of the cleanup (i.e. the functions will be dropped by
>> the linker), and they're only expected be needed by RISC-V on hardware which
>> lacks the Zbb extension.
>>
>> Implement generic_fls() in terms of generic_flsl() for now, but this will be
>> cleaned up in due course.
>>
>> Provide basic runtime testing using __constructor inside the lib/ file.  This
>> is important, as it means testing runs if and only if generic_f?sl() are used
>> elsewhere in Xen.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

Thanks.

> with a suggestion and a question.
>
>> I suspect we want to swap CONFIG_DEBUG for CONFIG_BOOT_UNIT_TESTS in due
>> course.  These ought to be able to be used in a release build too.
> +1

Actually - I might as well do this now.  Start as we mean to go on.

>
>> --- /dev/null
>> +++ b/xen/lib/generic-ffsl.c
>> @@ -0,0 +1,65 @@
>> +/* SPDX-License-Identifier: GPL-2.0 */
>> +
>> +#include <xen/bitops.h>
>> +#include <xen/boot-check.h>
>> +#include <xen/init.h>
>> +
>> +unsigned int generic_ffsl(unsigned long x)
>> +{
>> +    unsigned int r = 1;
>> +
>> +    if ( !x )
>> +        return 0;
>> +
>> +#if BITS_PER_LONG > 32
> To be future-proof, perhaps ahead of this
>
> #if BITS_PER_LONG > 64
> # error "..."
> #endif
>
> or a functionally similar BUILD_BUG_ON()?

Good point.  I'll fold this in to both files.

>
>> --- /dev/null
>> +++ b/xen/lib/generic-flsl.c
>> @@ -0,0 +1,68 @@
>> +/* SPDX-License-Identifier: GPL-2.0 */
>> +
>> +#include <xen/bitops.h>
>> +#include <xen/boot-check.h>
>> +#include <xen/init.h>
>> +
>> +/* Mask of type UL with the upper x bits set. */
>> +#define UPPER_MASK(x) (~0UL << (BITS_PER_LONG - (x)))
>> +
>> +unsigned int generic_flsl(unsigned long x)
>> +{
>> +    unsigned int r = BITS_PER_LONG;
>> +
>> +    if ( !x )
>> +        return 0;
>> +
>> +#if BITS_PER_LONG > 32
>> +    if ( !(x & UPPER_MASK(32)) )
>> +    {
>> +        x <<= 32;
>> +        r -= 32;
>> +    }
>> +#endif
>> +    if ( !(x & UPPER_MASK(16)) )
>> +    {
>> +        x <<= 16;
>> +        r -= 16;
>> +    }
>> +    if ( !(x & UPPER_MASK(8)) )
>> +    {
>> +        x <<= 8;
>> +        r -= 8;
>> +    }
>> +    if ( !(x & UPPER_MASK(4)) )
>> +    {
>> +        x <<= 4;
>> +        r -= 4;
>> +    }
>> +    if ( !(x & UPPER_MASK(2)) )
>> +    {
>> +        x <<= 2;
>> +        r -= 2;
>> +    }
>> +    if ( !(x & UPPER_MASK(1)) )
>> +    {
>> +        x <<= 1;
>> +        r -= 1;
>> +    }
>> +
>> +    return r;
>> +}
> While, as you say, the expectation is for this code to not commonly come
> into actual use, I still find the algorithm a little inefficient in terms
> of the constants used, specifically considering how they would need
> instantiating in resulting assembly. It may be that Arm's fancy constant-
> move insns can actually efficiently synthesize them, but I think on most
> other architectures it would be more efficient (and presumably no less
> efficient on Arm) to shift the "remaining" value right, thus allowing for
> successively smaller (and hence easier to instantiate) constants to be
> used.

ARM can only synthesise UPPER_MASK(16) and narrower masks, I think.

That said, I'm not concerned about the (in)efficiency seeing as this
doesn't get included in x86/ARM/PPC builds by the end of the series.

It's RISC-V which matters, and I'm pretty sure this is the wrong
algorithm to be using.

Incidentally, this algorithm is terrible for superscalar pipelines,
because each branch is inherently unpredictable.

Both these files want rewriting based on an analysis of the H-capable
Zbb-incapable RISC-V cores which exist.

I expect that what we actually want is the De Bruijn form which is an
O(1) algorithm, given a decent hardware multiplier.  If not, there's a
loop form which I expect would still be better than this.

~Andrew

[PATCH v2 for-4.19 0.5/13] xen: Introduce CONFIG_SELF_TESTS

[Andrew Cooper]

... and move x86's stub_selftest() under this new option.

There is value in having these tests included in release builds too.

It will shortly be used to gate the bitops unit tests on all architectures.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: Jan Beulich <JBeulich@suse.com>
CC: Roger Pau Monné <roger.pau@citrix.com>
CC: Wei Liu <wl@xen.org>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Julien Grall <julien@xen.org>
CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
CC: Bertrand Marquis <bertrand.marquis@arm.com>
CC: Michal Orzel <michal.orzel@amd.com>
CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
CC: Shawn Anastasio <sanastasio@raptorengineering.com>
CC: consulting@bugseng.com <consulting@bugseng.com>
CC: Simone Ballarin <simone.ballarin@bugseng.com>
CC: Federico Serafini <federico.serafini@bugseng.com>
CC: Nicola Vetrini <nicola.vetrini@bugseng.com>

v2.5:
 * As suggested in "[PATCH v2 05/13] xen/bitops: Implement generic_f?sl() in
 lib/"

I've gone with SELF_TESTS rather than BOOT_TESTS, because already in bitops
we've got compile time tests (which aren't strictly boot time), and the
livepatching testing wants to be included here and is definitely not boot
time.
---
 xen/Kconfig.debug      | 6 ++++++
 xen/arch/x86/extable.c | 4 ++--
 xen/arch/x86/setup.c   | 2 +-
 3 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/xen/Kconfig.debug b/xen/Kconfig.debug
index 61b24ac552cd..07ff7eb7ba83 100644
--- a/xen/Kconfig.debug
+++ b/xen/Kconfig.debug
@@ -29,6 +29,12 @@ config FRAME_POINTER
 	  maybe slower, but it gives very useful debugging information
 	  in case of any Xen bugs.
 
+config SELF_TESTS
+	bool "Extra self-testing"
+	default DEBUG
+	help
+	  Enable extra unit and functional testing.
+
 config COVERAGE
 	bool "Code coverage support"
 	depends on !LIVEPATCH
diff --git a/xen/arch/x86/extable.c b/xen/arch/x86/extable.c
index 8415cd1fa249..705cf9eb94ca 100644
--- a/xen/arch/x86/extable.c
+++ b/xen/arch/x86/extable.c
@@ -144,7 +144,7 @@ search_exception_table(const struct cpu_user_regs *regs, unsigned long *stub_ra)
     return 0;
 }
 
-#ifdef CONFIG_DEBUG
+#ifdef CONFIG_SELF_TESTS
 #include <asm/setup.h>
 #include <asm/traps.h>
 
@@ -214,7 +214,7 @@ int __init cf_check stub_selftest(void)
     return 0;
 }
 __initcall(stub_selftest);
-#endif
+#endif /* CONFIG_SELF_TESTS */
 
 unsigned long asmlinkage search_pre_exception_table(struct cpu_user_regs *regs)
 {
diff --git a/xen/arch/x86/setup.c b/xen/arch/x86/setup.c
index b50c9c84af6d..dd51e68dbe5b 100644
--- a/xen/arch/x86/setup.c
+++ b/xen/arch/x86/setup.c
@@ -742,7 +742,7 @@ static void noreturn init_done(void)
     system_state = SYS_STATE_active;
 
     /* Re-run stub recovery self-tests with CET-SS active. */
-    if ( IS_ENABLED(CONFIG_DEBUG) && cpu_has_xen_shstk )
+    if ( IS_ENABLED(CONFIG_SELF_TESTS) && cpu_has_xen_shstk )
         stub_selftest();
 
     domain_unpause_by_systemcontroller(dom0);

base-commit: 2d93f78bfe25f695d8ffb61d110da9df293ed71b
-- 
2.30.2

Re: [PATCH v2 for-4.19 0.5/13] xen: Introduce CONFIG_SELF_TESTS

[Jan Beulich]

On 28.05.2024 16:22, Andrew Cooper wrote:
> ... and move x86's stub_selftest() under this new option.
> 
> There is value in having these tests included in release builds too.
> 
> It will shortly be used to gate the bitops unit tests on all architectures.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Reviewed-by: Jan Beulich <jbeulich@suse.com>

> I've gone with SELF_TESTS rather than BOOT_TESTS, because already in bitops
> we've got compile time tests (which aren't strictly boot time), and the
> livepatching testing wants to be included here and is definitely not boot
> time.

I second this consideration, fwiw.

Jan

Re: [PATCH v2 for-4.19 0.5/13] xen: Introduce CONFIG_SELF_TESTS

[Oleksii K.]

On Tue, 2024-05-28 at 15:22 +0100, Andrew Cooper wrote:
> ... and move x86's stub_selftest() under this new option.
> 
> There is value in having these tests included in release builds too.
> 
> It will shortly be used to gate the bitops unit tests on all
> architectures.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Looks good to me.
We can consider it to be merged to 4.19:
Release-Acked-by: Oleksii Kurochko <oleksii.kurochko@gmail.com>

~ Oleksii
> ---
> CC: Jan Beulich <JBeulich@suse.com>
> CC: Roger Pau Monné <roger.pau@citrix.com>
> CC: Wei Liu <wl@xen.org>
> CC: Stefano Stabellini <sstabellini@kernel.org>
> CC: Julien Grall <julien@xen.org>
> CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
> CC: Bertrand Marquis <bertrand.marquis@arm.com>
> CC: Michal Orzel <michal.orzel@amd.com>
> CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
> CC: Shawn Anastasio <sanastasio@raptorengineering.com>
> CC: consulting@bugseng.com <consulting@bugseng.com>
> CC: Simone Ballarin <simone.ballarin@bugseng.com>
> CC: Federico Serafini <federico.serafini@bugseng.com>
> CC: Nicola Vetrini <nicola.vetrini@bugseng.com>
> 
> v2.5:
>  * As suggested in "[PATCH v2 05/13] xen/bitops: Implement
> generic_f?sl() in
>  lib/"
> 
> I've gone with SELF_TESTS rather than BOOT_TESTS, because already in
> bitops
> we've got compile time tests (which aren't strictly boot time), and
> the
> livepatching testing wants to be included here and is definitely not
> boot
> time.
> ---
>  xen/Kconfig.debug      | 6 ++++++
>  xen/arch/x86/extable.c | 4 ++--
>  xen/arch/x86/setup.c   | 2 +-
>  3 files changed, 9 insertions(+), 3 deletions(-)
> 
> diff --git a/xen/Kconfig.debug b/xen/Kconfig.debug
> index 61b24ac552cd..07ff7eb7ba83 100644
> --- a/xen/Kconfig.debug
> +++ b/xen/Kconfig.debug
> @@ -29,6 +29,12 @@ config FRAME_POINTER
>  	  maybe slower, but it gives very useful debugging
> information
>  	  in case of any Xen bugs.
>  
> +config SELF_TESTS
> +	bool "Extra self-testing"
> +	default DEBUG
> +	help
> +	  Enable extra unit and functional testing.
> +
>  config COVERAGE
>  	bool "Code coverage support"
>  	depends on !LIVEPATCH
> diff --git a/xen/arch/x86/extable.c b/xen/arch/x86/extable.c
> index 8415cd1fa249..705cf9eb94ca 100644
> --- a/xen/arch/x86/extable.c
> +++ b/xen/arch/x86/extable.c
> @@ -144,7 +144,7 @@ search_exception_table(const struct cpu_user_regs
> *regs, unsigned long *stub_ra)
>      return 0;
>  }
>  
> -#ifdef CONFIG_DEBUG
> +#ifdef CONFIG_SELF_TESTS
>  #include <asm/setup.h>
>  #include <asm/traps.h>
>  
> @@ -214,7 +214,7 @@ int __init cf_check stub_selftest(void)
>      return 0;
>  }
>  __initcall(stub_selftest);
> -#endif
> +#endif /* CONFIG_SELF_TESTS */
>  
>  unsigned long asmlinkage search_pre_exception_table(struct
> cpu_user_regs *regs)
>  {
> diff --git a/xen/arch/x86/setup.c b/xen/arch/x86/setup.c
> index b50c9c84af6d..dd51e68dbe5b 100644
> --- a/xen/arch/x86/setup.c
> +++ b/xen/arch/x86/setup.c
> @@ -742,7 +742,7 @@ static void noreturn init_done(void)
>      system_state = SYS_STATE_active;
>  
>      /* Re-run stub recovery self-tests with CET-SS active. */
> -    if ( IS_ENABLED(CONFIG_DEBUG) && cpu_has_xen_shstk )
> +    if ( IS_ENABLED(CONFIG_SELF_TESTS) && cpu_has_xen_shstk )
>          stub_selftest();
>  
>      domain_unpause_by_systemcontroller(dom0);
> 
> base-commit: 2d93f78bfe25f695d8ffb61d110da9df293ed71b

Re: [PATCH v2 04/13] xen/page_alloc: Coerce min(flsl(), foo) expressions to being unsigned

[Andrew Cooper]

On 27/05/2024 7:26 am, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
>> This is in order to maintain bisectability through the subsequent changes,
>> where flsl() changes sign-ness non-atomically by architecture.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Jan Beulich <jbeulich@suse.com>
>
>

Actually, by coercing the min() in pvh_populate_memory_range() from
patch 9 in this patch, the bisection-complexity of this series drops
massively, and in particular I can merge patch 3 into 10.

As you've given R-by on both, I'm going to go ahead and do this in order
to make some headway on the series, given the deadlines, and that the
RISC-V series is still pending this one.

~Andrew

Re: [PATCH v2 04/13] xen/page_alloc: Coerce min(flsl(), foo) expressions to being unsigned

[Andrew Cooper]

On 29/05/2024 8:07 pm, Andrew Cooper wrote:
> On 27/05/2024 7:26 am, Jan Beulich wrote:
>> On 24.05.2024 22:03, Andrew Cooper wrote:
>>> This is in order to maintain bisectability through the subsequent changes,
>>> where flsl() changes sign-ness non-atomically by architecture.
>>>
>>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
>> Reviewed-by: Jan Beulich <jbeulich@suse.com>
>>
>>
> Actually, by coercing the min() in pvh_populate_memory_range() from
> patch 9 in this patch, the bisection-complexity of this series drops
> massively, and in particular I can merge patch 3 into 10.
>
> As you've given R-by on both, I'm going to go ahead and do this in order
> to make some headway on the series, given the deadlines, and that the
> RISC-V series is still pending this one.

Actually not quite.  It's even more simple.  This patch stays the same,
and the coercion gets added as find_first_set_bit() turns into ffsl().

~Andrew

Re: [PATCH v2 01/13] ppc/boot: Run constructors on boot

[Shawn Anastasio]

Hi Andrew,

On 5/24/24 3:03 PM, Andrew Cooper wrote:
> PPC collects constructors, but doesn't run them yet.  Do so.
> 
> They'll shortly be used to confirm correct behaviour of the bitops primitives.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> ---

Looks good to me.

Acked-by: Shawn Anastasio <sanastasio@raptorengineering.com>

Thanks,
Shawn

Re: [PATCH v2 10/13] xen/bitops: Delete find_first_set_bit()

[Andrew Cooper]

On 27/05/2024 1:58 pm, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
>> No more users.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Acked-by: Jan Beulich <jbeulich@suse.com>
>
>

FYI, with the rearrangements I've done, this safely merges into and
supersedes patch 4.

~Andrew

Re: [PATCH v2 03/13] ARM/bitops: Change find_first_set_bit() to be a define

[Stefano Stabellini]

On Fri, 24 May 2024, Andrew Cooper wrote:
> This is in order to maintain bisectability through the subsequent changes, as
> the order of definitions is altered.
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

Acked-by: Stefano Stabellini <sstabellini@kernel.org>

Re: [PATCH v2 05/13] xen/bitops: Implement generic_f?sl() in lib/

[Stefano Stabellini]

On Mon, 27 May 2024, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
> > generic_f?s() being static inline is the cause of lots of the complexity
> > between the common and arch-specific bitops.h
> > 
> > They appear to be static inline for constant-folding reasons (ARM uses them
> > for this), but there are better ways to achieve the same effect.
> > 
> > It is presumptuous that an unrolled binary search is the right algorithm to
> > use on all microarchitectures.  Indeed, it's not for the eventual users, but
> > that can be addressed at a later point.
> > 
> > It is also nonsense to implement the int form as the base primitive and
> > construct the long form from 2x int in 64-bit builds, when it's just one extra
> > step to operate at the native register width.
> > 
> > Therefore, implement generic_f?sl() in lib/.  They're not actually needed in
> > x86/ARM/PPC by the end of the cleanup (i.e. the functions will be dropped by
> > the linker), and they're only expected be needed by RISC-V on hardware which
> > lacks the Zbb extension.
> > 
> > Implement generic_fls() in terms of generic_flsl() for now, but this will be
> > cleaned up in due course.
> > 
> > Provide basic runtime testing using __constructor inside the lib/ file.  This
> > is important, as it means testing runs if and only if generic_f?sl() are used
> > elsewhere in Xen.
> > 
> > Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> 
> Reviewed-by: Jan Beulich <jbeulich@suse.com>
> with a suggestion and a question.

Acked-by: Stefano Stabellini <sstabellini@kernel.org>


> > I suspect we want to swap CONFIG_DEBUG for CONFIG_BOOT_UNIT_TESTS in due
> > course.  These ought to be able to be used in a release build too.
> 
> +1

+1

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Stefano Stabellini]

[-- Attachment #1: Type: text/plain, Size: 5828 bytes --]

On Fri, 24 May 2024, Andrew Cooper wrote:
> Perform constant-folding unconditionally, rather than having it implemented
> inconsistency between architectures.
> 
> Confirm the expected behaviour with compile time and boot time tests.
> 
> For non-constant inputs, use arch_ffs() if provided but fall back to
> generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin that
> works in all configurations.
> 
> For x86, rename ffs() to arch_ffs() and adjust the prototype.
> 
> For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to
> generic_fls().  Drop the definition entirely.  ARM too benefits in the general
> case by using __builtin_ctz(), but less dramatically because it using
> optimised asm().
> 
> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>

This patch made me realize that we should add __builtin_ctz,
__builtin_constant_p and always_inline to
docs/misra/C-language-toolchain.rst as they don't seem to be currently
documented and they are not part of the C standard

Patch welcome :-)

Reviewed-by: Stefano Stabellini <sstabellini@kernel.org>


> ---
> CC: Jan Beulich <JBeulich@suse.com>
> CC: Roger Pau Monné <roger.pau@citrix.com>
> CC: Wei Liu <wl@xen.org>
> CC: Stefano Stabellini <sstabellini@kernel.org>
> CC: Julien Grall <julien@xen.org>
> CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
> CC: Bertrand Marquis <bertrand.marquis@arm.com>
> CC: Michal Orzel <michal.orzel@amd.com>
> CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
> CC: Shawn Anastasio <sanastasio@raptorengineering.com>
> CC: consulting@bugseng.com <consulting@bugseng.com>
> CC: Simone Ballarin <simone.ballarin@bugseng.com>
> CC: Federico Serafini <federico.serafini@bugseng.com>
> CC: Nicola Vetrini <nicola.vetrini@bugseng.com>
> 
> v2:
>  * Fall back to generic, not builtin.
>  * Extend the testing with multi-bit values.
>  * Use always_inline for x86
>  * Defer x86 optimisation to a later change
> ---
>  xen/arch/arm/include/asm/bitops.h |  2 +-
>  xen/arch/ppc/include/asm/bitops.h |  2 +-
>  xen/arch/x86/include/asm/bitops.h |  3 ++-
>  xen/common/Makefile               |  1 +
>  xen/common/bitops.c               | 19 +++++++++++++++++++
>  xen/include/xen/bitops.h          | 17 +++++++++++++++++
>  6 files changed, 41 insertions(+), 3 deletions(-)
>  create mode 100644 xen/common/bitops.c
> 
> diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h
> index ec1cf7b9b323..a88ec2612e16 100644
> --- a/xen/arch/arm/include/asm/bitops.h
> +++ b/xen/arch/arm/include/asm/bitops.h
> @@ -157,7 +157,7 @@ static inline int fls(unsigned int x)
>  }
>  
>  
> -#define ffs(x) ({ unsigned int __t = (x); fls(ISOLATE_LSB(__t)); })
> +#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
>  #define ffsl(x) ({ unsigned long __t = (x); flsl(ISOLATE_LSB(__t)); })
>  
>  /**
> diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h
> index ab692d01717b..5c36a6cc0ce3 100644
> --- a/xen/arch/ppc/include/asm/bitops.h
> +++ b/xen/arch/ppc/include/asm/bitops.h
> @@ -173,7 +173,7 @@ static inline int __test_and_clear_bit(int nr, volatile void *addr)
>  
>  #define flsl(x) generic_flsl(x)
>  #define fls(x) generic_flsl(x)
> -#define ffs(x) ({ unsigned int t_ = (x); fls(t_ & -t_); })
> +#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
>  #define ffsl(x) ({ unsigned long t_ = (x); flsl(t_ & -t_); })
>  
>  /**
> diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h
> index 5a71afbc89d5..122767fc0d10 100644
> --- a/xen/arch/x86/include/asm/bitops.h
> +++ b/xen/arch/x86/include/asm/bitops.h
> @@ -430,7 +430,7 @@ static inline int ffsl(unsigned long x)
>      return (int)r+1;
>  }
>  
> -static inline int ffs(unsigned int x)
> +static always_inline unsigned int arch_ffs(unsigned int x)
>  {
>      int r;
>  
> @@ -440,6 +440,7 @@ static inline int ffs(unsigned int x)
>            "1:" : "=r" (r) : "rm" (x));
>      return r + 1;
>  }
> +#define arch_ffs arch_ffs
>  
>  /**
>   * fls - find last bit set
> diff --git a/xen/common/Makefile b/xen/common/Makefile
> index d512cad5243f..21a4fb4c7166 100644
> --- a/xen/common/Makefile
> +++ b/xen/common/Makefile
> @@ -1,5 +1,6 @@
>  obj-$(CONFIG_ARGO) += argo.o
>  obj-y += bitmap.o
> +obj-bin-$(CONFIG_DEBUG) += bitops.init.o
>  obj-$(CONFIG_GENERIC_BUG_FRAME) += bug.o
>  obj-$(CONFIG_HYPFS_CONFIG) += config_data.o
>  obj-$(CONFIG_CORE_PARKING) += core_parking.o
> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
> new file mode 100644
> index 000000000000..8c161b8ea7fa
> --- /dev/null
> +++ b/xen/common/bitops.c
> @@ -0,0 +1,19 @@
> +#include <xen/bitops.h>
> +#include <xen/boot-check.h>
> +#include <xen/init.h>
> +
> +static void __init test_ffs(void)
> +{
> +    /* unsigned int ffs(unsigned int) */
> +    CHECK(ffs, 0, 0);
> +    CHECK(ffs, 1, 1);
> +    CHECK(ffs, 3, 1);
> +    CHECK(ffs, 7, 1);
> +    CHECK(ffs, 6, 2);
> +    CHECK(ffs, 0x80000000U, 32);
> +}
> +
> +static void __init __constructor test_bitops(void)
> +{
> +    test_ffs();
> +}
> diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
> index cd405df96180..f7e90a2893a5 100644
> --- a/xen/include/xen/bitops.h
> +++ b/xen/include/xen/bitops.h
> @@ -31,6 +31,23 @@ unsigned int __pure generic_flsl(unsigned long x);
>  
>  #include <asm/bitops.h>
>  
> +/*
> + * Find First/Last Set bit (all forms).
> + *
> + * Bits are labelled from 1.  Returns 0 if given 0.
> + */
> +static always_inline __pure unsigned int ffs(unsigned int x)
> +{
> +    if ( __builtin_constant_p(x) )
> +        return __builtin_ffs(x);
> +
> +#ifdef arch_ffs
> +    return arch_ffs(x);
> +#else
> +    return generic_ffsl(x);
> +#endif
> +}
> +
>  /* --------------------- Please tidy below here --------------------- */
>  
>  #ifndef find_next_bit
> -- 
> 2.30.2
> 

Re: [PATCH v2 08/13] xen/bitops: Implement ffsl() in common logic

[Stefano Stabellini]

On Mon, 27 May 2024, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
> > Just like ffs() in the previous changes.  Express the upper bound of the
> > testing in terms of BITS_PER_LONG as it varies between architectures.
> > 
> > Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> 
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

Acked-by: Stefano Stabellini <sstabellini@kernel.org>

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Nicola Vetrini]

On 2024-05-31 03:14, Stefano Stabellini wrote:
> On Fri, 24 May 2024, Andrew Cooper wrote:
>> Perform constant-folding unconditionally, rather than having it 
>> implemented
>> inconsistency between architectures.
>> 
>> Confirm the expected behaviour with compile time and boot time tests.
>> 
>> For non-constant inputs, use arch_ffs() if provided but fall back to
>> generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin 
>> that
>> works in all configurations.
>> 
>> For x86, rename ffs() to arch_ffs() and adjust the prototype.
>> 
>> For PPC, __builtin_ctz() is 1/3 of the size of size of the transform 
>> to
>> generic_fls().  Drop the definition entirely.  ARM too benefits in the 
>> general
>> case by using __builtin_ctz(), but less dramatically because it using
>> optimised asm().
>> 
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> 
> This patch made me realize that we should add __builtin_ctz,
> __builtin_constant_p and always_inline to
> docs/misra/C-language-toolchain.rst as they don't seem to be currently
> documented and they are not part of the C standard
> 
> Patch welcome :-)
> 

I can send a patch for the builtins. I think that for attributes it was 
decided to document the use of the __attribute__ token, rather than 
listing all the attributes used by Xen

> Reviewed-by: Stefano Stabellini <sstabellini@kernel.org>
> 
> 
>> ---
>> CC: Jan Beulich <JBeulich@suse.com>
>> CC: Roger Pau Monné <roger.pau@citrix.com>
>> CC: Wei Liu <wl@xen.org>
>> CC: Stefano Stabellini <sstabellini@kernel.org>
>> CC: Julien Grall <julien@xen.org>
>> CC: Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
>> CC: Bertrand Marquis <bertrand.marquis@arm.com>
>> CC: Michal Orzel <michal.orzel@amd.com>
>> CC: Oleksii Kurochko <oleksii.kurochko@gmail.com>
>> CC: Shawn Anastasio <sanastasio@raptorengineering.com>
>> CC: consulting@bugseng.com <consulting@bugseng.com>
>> CC: Simone Ballarin <simone.ballarin@bugseng.com>
>> CC: Federico Serafini <federico.serafini@bugseng.com>
>> CC: Nicola Vetrini <nicola.vetrini@bugseng.com>
>> 
>> v2:
>>  * Fall back to generic, not builtin.
>>  * Extend the testing with multi-bit values.
>>  * Use always_inline for x86
>>  * Defer x86 optimisation to a later change
>> ---
>>  xen/arch/arm/include/asm/bitops.h |  2 +-
>>  xen/arch/ppc/include/asm/bitops.h |  2 +-
>>  xen/arch/x86/include/asm/bitops.h |  3 ++-
>>  xen/common/Makefile               |  1 +
>>  xen/common/bitops.c               | 19 +++++++++++++++++++
>>  xen/include/xen/bitops.h          | 17 +++++++++++++++++
>>  6 files changed, 41 insertions(+), 3 deletions(-)
>>  create mode 100644 xen/common/bitops.c
>> 
>> diff --git a/xen/arch/arm/include/asm/bitops.h 
>> b/xen/arch/arm/include/asm/bitops.h
>> index ec1cf7b9b323..a88ec2612e16 100644
>> --- a/xen/arch/arm/include/asm/bitops.h
>> +++ b/xen/arch/arm/include/asm/bitops.h
>> @@ -157,7 +157,7 @@ static inline int fls(unsigned int x)
>>  }
>> 
>> 
>> -#define ffs(x) ({ unsigned int __t = (x); fls(ISOLATE_LSB(__t)); })
>> +#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
>>  #define ffsl(x) ({ unsigned long __t = (x); flsl(ISOLATE_LSB(__t)); 
>> })
>> 
>>  /**
>> diff --git a/xen/arch/ppc/include/asm/bitops.h 
>> b/xen/arch/ppc/include/asm/bitops.h
>> index ab692d01717b..5c36a6cc0ce3 100644
>> --- a/xen/arch/ppc/include/asm/bitops.h
>> +++ b/xen/arch/ppc/include/asm/bitops.h
>> @@ -173,7 +173,7 @@ static inline int __test_and_clear_bit(int nr, 
>> volatile void *addr)
>> 
>>  #define flsl(x) generic_flsl(x)
>>  #define fls(x) generic_flsl(x)
>> -#define ffs(x) ({ unsigned int t_ = (x); fls(t_ & -t_); })
>> +#define arch_ffs(x)  ((x) ? 1 + __builtin_ctz(x) : 0)
>>  #define ffsl(x) ({ unsigned long t_ = (x); flsl(t_ & -t_); })
>> 
>>  /**
>> diff --git a/xen/arch/x86/include/asm/bitops.h 
>> b/xen/arch/x86/include/asm/bitops.h
>> index 5a71afbc89d5..122767fc0d10 100644
>> --- a/xen/arch/x86/include/asm/bitops.h
>> +++ b/xen/arch/x86/include/asm/bitops.h
>> @@ -430,7 +430,7 @@ static inline int ffsl(unsigned long x)
>>      return (int)r+1;
>>  }
>> 
>> -static inline int ffs(unsigned int x)
>> +static always_inline unsigned int arch_ffs(unsigned int x)
>>  {
>>      int r;
>> 
>> @@ -440,6 +440,7 @@ static inline int ffs(unsigned int x)
>>            "1:" : "=r" (r) : "rm" (x));
>>      return r + 1;
>>  }
>> +#define arch_ffs arch_ffs
>> 
>>  /**
>>   * fls - find last bit set
>> diff --git a/xen/common/Makefile b/xen/common/Makefile
>> index d512cad5243f..21a4fb4c7166 100644
>> --- a/xen/common/Makefile
>> +++ b/xen/common/Makefile
>> @@ -1,5 +1,6 @@
>>  obj-$(CONFIG_ARGO) += argo.o
>>  obj-y += bitmap.o
>> +obj-bin-$(CONFIG_DEBUG) += bitops.init.o
>>  obj-$(CONFIG_GENERIC_BUG_FRAME) += bug.o
>>  obj-$(CONFIG_HYPFS_CONFIG) += config_data.o
>>  obj-$(CONFIG_CORE_PARKING) += core_parking.o
>> diff --git a/xen/common/bitops.c b/xen/common/bitops.c
>> new file mode 100644
>> index 000000000000..8c161b8ea7fa
>> --- /dev/null
>> +++ b/xen/common/bitops.c
>> @@ -0,0 +1,19 @@
>> +#include <xen/bitops.h>
>> +#include <xen/boot-check.h>
>> +#include <xen/init.h>
>> +
>> +static void __init test_ffs(void)
>> +{
>> +    /* unsigned int ffs(unsigned int) */
>> +    CHECK(ffs, 0, 0);
>> +    CHECK(ffs, 1, 1);
>> +    CHECK(ffs, 3, 1);
>> +    CHECK(ffs, 7, 1);
>> +    CHECK(ffs, 6, 2);
>> +    CHECK(ffs, 0x80000000U, 32);
>> +}
>> +
>> +static void __init __constructor test_bitops(void)
>> +{
>> +    test_ffs();
>> +}
>> diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
>> index cd405df96180..f7e90a2893a5 100644
>> --- a/xen/include/xen/bitops.h
>> +++ b/xen/include/xen/bitops.h
>> @@ -31,6 +31,23 @@ unsigned int __pure generic_flsl(unsigned long x);
>> 
>>  #include <asm/bitops.h>
>> 
>> +/*
>> + * Find First/Last Set bit (all forms).
>> + *
>> + * Bits are labelled from 1.  Returns 0 if given 0.
>> + */
>> +static always_inline __pure unsigned int ffs(unsigned int x)
>> +{
>> +    if ( __builtin_constant_p(x) )
>> +        return __builtin_ffs(x);
>> +
>> +#ifdef arch_ffs
>> +    return arch_ffs(x);
>> +#else
>> +    return generic_ffsl(x);
>> +#endif
>> +}
>> +
>>  /* --------------------- Please tidy below here --------------------- 
>> */
>> 
>>  #ifndef find_next_bit
>> --
>> 2.30.2
>> 

-- 
Nicola Vetrini, BSc
Software Engineer, BUGSENG srl (https://bugseng.com)

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Andrew Cooper]

On 31/05/2024 7:56 am, Nicola Vetrini wrote:
> On 2024-05-31 03:14, Stefano Stabellini wrote:
>> On Fri, 24 May 2024, Andrew Cooper wrote:
>>> Perform constant-folding unconditionally, rather than having it
>>> implemented
>>> inconsistency between architectures.
>>>
>>> Confirm the expected behaviour with compile time and boot time tests.
>>>
>>> For non-constant inputs, use arch_ffs() if provided but fall back to
>>> generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin
>>> that
>>> works in all configurations.
>>>
>>> For x86, rename ffs() to arch_ffs() and adjust the prototype.
>>>
>>> For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to
>>> generic_fls().  Drop the definition entirely.  ARM too benefits in
>>> the general
>>> case by using __builtin_ctz(), but less dramatically because it using
>>> optimised asm().
>>>
>>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
>>
>> This patch made me realize that we should add __builtin_ctz,
>> __builtin_constant_p and always_inline to
>> docs/misra/C-language-toolchain.rst as they don't seem to be currently
>> documented and they are not part of the C standard
>>
>> Patch welcome :-)
>>
>
> I can send a patch for the builtins.

That's very kind of you.

In total by the end of this series, we've got __builtin_constant_p() 
(definitely used elsewhere already), and __builtin_{ffs,ctz,clz}{,l}() 
(3x primitives, 2x input types).

If we're going for a list of the primitive operations, lets add
__builtin_popcnt{,l}() too right away, because if it weren't for 4.19
code freeze, I'd have cleaned up the hweight() helpers too.

~Andrew

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Andrew Cooper]

On 31/05/2024 9:34 am, Andrew Cooper wrote:
> On 31/05/2024 7:56 am, Nicola Vetrini wrote:
>> On 2024-05-31 03:14, Stefano Stabellini wrote:
>>> On Fri, 24 May 2024, Andrew Cooper wrote:
>>>> Perform constant-folding unconditionally, rather than having it
>>>> implemented
>>>> inconsistency between architectures.
>>>>
>>>> Confirm the expected behaviour with compile time and boot time tests.
>>>>
>>>> For non-constant inputs, use arch_ffs() if provided but fall back to
>>>> generic_ffsl() if not.  In particular, RISC-V doesn't have a builtin
>>>> that
>>>> works in all configurations.
>>>>
>>>> For x86, rename ffs() to arch_ffs() and adjust the prototype.
>>>>
>>>> For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to
>>>> generic_fls().  Drop the definition entirely.  ARM too benefits in
>>>> the general
>>>> case by using __builtin_ctz(), but less dramatically because it using
>>>> optimised asm().
>>>>
>>>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
>>> This patch made me realize that we should add __builtin_ctz,
>>> __builtin_constant_p and always_inline to
>>> docs/misra/C-language-toolchain.rst as they don't seem to be currently
>>> documented and they are not part of the C standard
>>>
>>> Patch welcome :-)
>>>
>> I can send a patch for the builtins.
> That's very kind of you.
>
> In total by the end of this series, we've got __builtin_constant_p() 
> (definitely used elsewhere already), and __builtin_{ffs,ctz,clz}{,l}() 
> (3x primitives, 2x input types).
>
> If we're going for a list of the primitive operations, lets add
> __builtin_popcnt{,l}() too right away, because if it weren't for 4.19
> code freeze, I'd have cleaned up the hweight() helpers too.

Oh, and it's worth noting that __builtin_{ctz,clz}{,l}() have explicit
UB if given an input of 0.  (Sadly, even on architectures where the
underlying instruction emitted is safe with a 0 input. [0])

This is why every patch in the series using them checks for nonzero input.

UBSAN (with an adequate compiler) will instrument this, and Xen has
__ubsan_handle_invalid_builtin() to diagnose these.

~Andrew

[0] It turns out that Clang has a 2-argument form of the builtin with
the second being the "value forwarded" in case the first is 0.  I've not
investigated whether GCC has the same.

Re: [PATCH v2 02/13] xen/bitops: Cleanup ahead of rearrangements

[Andrew Cooper]

On 27/05/2024 9:24 am, Jan Beulich wrote:
> On 24.05.2024 22:03, Andrew Cooper wrote:
>>  * Rename __attribute_pure__ to just __pure before it gains users.
>>  * Introduce __constructor which is going to be used in lib/, and is
>>    unconditionally cf_check.
>>  * Identify the areas of xen/bitops.h which are a mess.
>>  * Introduce xen/boot-check.h as helpers for compile and boot time testing.
>>    This provides a statement of the ABI, and a confirmation that arch-specific
>>    implementations behave as expected.
>>
>> Sadly Clang 7 and older isn't happy with the compile time checks.  Skip them,
>> and just rely on the runtime checks.
>>
>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

Thanks.

>
> Further remarks, though:
>
>> ---
>>  xen/include/xen/bitops.h     | 13 ++++++--
>>  xen/include/xen/boot-check.h | 60 ++++++++++++++++++++++++++++++++++++
>>  xen/include/xen/compiler.h   |  3 +-
>>  3 files changed, 72 insertions(+), 4 deletions(-)
>>  create mode 100644 xen/include/xen/boot-check.h
> The bulk of the changes isn't about bitops; it's just that you're intending
> to first use it for testing there. The subject prefix therefore is somewhat
> misleading.

I'll change to "Cleanup and infrastructure ahead ..." but the bitops
aspect is still reasonably important.
>> --- /dev/null
>> +++ b/xen/include/xen/boot-check.h
>> @@ -0,0 +1,60 @@
>> +/* SPDX-License-Identifier: GPL-2.0-or-later */
>> +
>> +/*
>> + * Helpers for boot-time checks of basic logic, including confirming that
>> + * examples which should be calculated by the compiler are.
>> + */
>> +#ifndef XEN_BOOT_CHECK_H
>> +#define XEN_BOOT_CHECK_H

Given that CONFIG_SELF_TESTS was subsequently approved, I've renamed
this file to match.

>> +
>> +#include <xen/lib.h>
>> +
>> +/* Hide a value from the optimiser. */
>> +#define HIDE(x)                                                         \
>> +    ({ typeof(x) _x = (x); asm volatile ( "" : "+r" (_x) ); _x; })
> In principle this is a macro that could be of use elsewhere. That's also
> reflected in its entirely generic name. It therefore feels mis-placed in
> this header.

I'd forgotten that we several variations of this already.  compiler.h
has both OPTIMIZER_HIDE_VAR() and RELOC_HIDE().

>  Otoh though the use of "+r" is more restricting than truly
> necessary: While I'm not sure if "+g" would work, i.e. if that wouldn't
> cause issues with literals,

OPTIMIZER_HIDE_VAR() is indeed buggy using "+g", and RELOC_HIDE() even
explains how "g" tickles a bug in a compiler we probably don't care
about any more.

[Slightly out of order] the use of OPTIMIZER_HIDE_VAR() in gsi_vioapic()
is bogus AFAICT, and is actively creating the problem the commit message
says it was trying to avoid.

>  pretty surely "+rm" ought to work, removing
> the strict requirement for the compiler to put a certain value in a
> register.

"+rm" would be ideal in theory, we can't use it in practice because
Clang will (still!) interpret it as "+m" and force a spill.

While that's not necessarily a problem for the SELF_TESTS, it really is
a problem in array_index_mask_nospec(), which is latently buggy even now.

If the compiler really uses the flexibility offered by
OPTIMIZER_HIDE_VAR() to spill the value, array_index_mask_nospec() has
entirely failed at its purpose.

> Assuming you may have reservations against "+g" / "+rm" (and hence the
> construct wants keeping here), maybe rename to e.g. BOOT_CHECK_HIDE()?
> Alternatively, if generalized, moving to xen/macros.h would seem
> appropriate to me.

I've moved it to macros.h (because we should consolidate around it), but
kept as "+r" for both Clang and array_index_mask_nospec() reasons.

I don't expect HIDE() is ever actually going to be used in a case where
letting the value stay in memory is a useful thing overall.  But if you
still feel strongly about it, we can debate further when consolidating
the other users.

~Andrew

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Andrew Cooper]

On 28/05/2024 2:12 pm, Jan Beulich wrote:
> On 28.05.2024 14:30, Andrew Cooper wrote:
>> On 27/05/2024 2:37 pm, Jan Beulich wrote:
>>> On 27.05.2024 15:27, Jan Beulich wrote:
>>>> On 24.05.2024 22:03, Andrew Cooper wrote:
>>>>> --- a/xen/arch/x86/include/asm/bitops.h
>>>>> +++ b/xen/arch/x86/include/asm/bitops.h
>>>>> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>>>>>  
>>>>>  static always_inline unsigned int arch_ffs(unsigned int x)
>>>>>  {
>>>>> -    int r;
>>>>> +    unsigned int r;
>>>>> +
>>>>> +    if ( __builtin_constant_p(x > 0) && x > 0 )
>>>>> +    {
>>>>> +        /* Safe, when the compiler knows that x is nonzero. */
>>>>> +        asm ( "bsf %[val], %[res]"
>>>>> +              : [res] "=r" (r)
>>>>> +              : [val] "rm" (x) );
>>>>> +    }
>>>> In patch 11 relevant things are all in a single patch, making it easier
>>>> to spot that this is dead code: The sole caller already has a
>>>> __builtin_constant_p(), hence I don't see how the one here could ever
>>>> return true. With that the respective part of the description is then
>>>> questionable, too, I'm afraid: Where did you observe any actual effect
>>>> from this? Or if you did - what am I missing?
>>> Hmm, thinking about it: I suppose that's why you have
>>> __builtin_constant_p(x > 0), not __builtin_constant_p(x). I have to admit
>>> I'm (positively) surprised that the former may return true when the latter
>>> doesn't.
>> So was I, but this recommendation came straight from the GCC mailing
>> list.  And it really does work, even back in obsolete versions of GCC.
>>
>> __builtin_constant_p() operates on an expression not a value, and is
>> documented as such.
> Of course.
>
>>>  Nevertheless I'm inclined to think this deserves a brief comment.
>> There is a comment, and it's even visible in the snippet.
> The comment is about the asm(); it is neither placed to clearly relate
> to __builtin_constant_p(), nor is it saying anything about this specific
> property of it. You said you were equally surprised; don't you think
> that when both of us are surprised, a specific (even if brief) comment
> is warranted?

Spell it out for me like I'm an idiot.

Because I'm looking at the patch I submitted, and at your request for "a
brief comment", and I still have no idea what you think is wrong at the
moment.

I'm also not included to write a comment saying "go and read the GCC
manual more carefully".

>
>>> As an aside, to better match the comment inside the if()'s body, how about
>>>
>>>     if ( __builtin_constant_p(!!x) && x )
>>>
>>> ? That also may make a little more clear that this isn't just a style
>>> choice, but actually needed for the intended purpose.
>> I am not changing the logic.
>>
>> Apart from anything else, your suggestion is trivially buggy.  I care
>> about whether the RHS collapses to a constant, and the only way of doing
>> that correctly is asking the compiler about the *exact* expression. 
>> Asking about some other expression which you hope - but do not know -
>> that the compiler will treat equivalently is bogus.  It would be
>> strictly better to only take the else clause, than to have both halves
>> emitted.
>>
>> This is the form I've tested extensively.  It's also the clearest form
>> IMO.  You can experiment with alternative forms when we're not staring
>> down code freeze of 4.19.
> "Clearest form" is almost always a matter of taste. To me, comparing
> unsigned values with > or < against 0 is generally at least suspicious.
> Using != is typically better (again: imo), and simply omitting the != 0
> then is shorter with no difference in effect. Except in peculiar cases
> like this one, where indeed it took me some time to figure why the
> comparison operator may not be omitted.
>
> All that said: I'm not going to insist on any change; the R-b previously
> offered still stands. I would highly appreciate though if the (further)
> comment asked for could be added.
>
> What I definitely dislike here is you - not for the first time - turning
> down remarks because a change of yours is late.

Actually it's not to do with the release.  I'd reject it at any point
because it's an unreasonable request to make; to me, or to anyone else.

It would be a matter of taste (which again you have a singular view on),
if it wasn't for the fact that what you actually said was:

"I don't like it, and you should discard all the careful analysis you
did because here's a form I prefer, that I haven't tested concerning a
behaviour I didn't even realise until this email."

and even if it wasn't a buggy suggestion to begin with, it's still toxic
maintainer feedback.


Frankly, I'd have more time to review other peoples patches if I wasn't
wasting all of my time on premium grade manure like this, while trying
to help Oleksii who's had it far worse this release trying to clean up
droppings of maintainers-past.

~Andrew

Re: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic

[Nicola Vetrini]

[-- Attachment #1: Type: text/plain, Size: 3165 bytes --]

On 2024-05-31 10:48, Andrew Cooper wrote:
> On 31/05/2024 9:34 am, Andrew Cooper wrote:
>> On 31/05/2024 7:56 am, Nicola Vetrini wrote:
>>> On 2024-05-31 03:14, Stefano Stabellini wrote:
>>>> On Fri, 24 May 2024, Andrew Cooper wrote:
>>>>> Perform constant-folding unconditionally, rather than having it
>>>>> implemented
>>>>> inconsistency between architectures.
>>>>> 
>>>>> Confirm the expected behaviour with compile time and boot time 
>>>>> tests.
>>>>> 
>>>>> For non-constant inputs, use arch_ffs() if provided but fall back 
>>>>> to
>>>>> generic_ffsl() if not.  In particular, RISC-V doesn't have a 
>>>>> builtin
>>>>> that
>>>>> works in all configurations.
>>>>> 
>>>>> For x86, rename ffs() to arch_ffs() and adjust the prototype.
>>>>> 
>>>>> For PPC, __builtin_ctz() is 1/3 of the size of size of the 
>>>>> transform to
>>>>> generic_fls().  Drop the definition entirely.  ARM too benefits in
>>>>> the general
>>>>> case by using __builtin_ctz(), but less dramatically because it 
>>>>> using
>>>>> optimised asm().
>>>>> 
>>>>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
>>>> This patch made me realize that we should add __builtin_ctz,
>>>> __builtin_constant_p and always_inline to
>>>> docs/misra/C-language-toolchain.rst as they don't seem to be 
>>>> currently
>>>> documented and they are not part of the C standard
>>>> 
>>>> Patch welcome :-)
>>>> 
>>> I can send a patch for the builtins.
>> That's very kind of you.
>> 
>> In total by the end of this series, we've got __builtin_constant_p() 
>> (definitely used elsewhere already), and 
>> __builtin_{ffs,ctz,clz}{,l}() 
>> (3x primitives, 2x input types).
>> 
>> If we're going for a list of the primitive operations, lets add
>> __builtin_popcnt{,l}() too right away, because if it weren't for 4.19
>> code freeze, I'd have cleaned up the hweight() helpers too.
> 
> Oh, and it's worth noting that __builtin_{ctz,clz}{,l}() have explicit
> UB if given an input of 0.  (Sadly, even on architectures where the
> underlying instruction emitted is safe with a 0 input. [0])
> 
> This is why every patch in the series using them checks for nonzero 
> input.
> 
> UBSAN (with an adequate compiler) will instrument this, and Xen has
> __ubsan_handle_invalid_builtin() to diagnose these.
> 
> ~Andrew
> 
> [0] It turns out that Clang has a 2-argument form of the builtin with
> the second being the "value forwarded" in case the first is 0.  I've 
> not
> investigated whether GCC has the same.

Hmm, maybe then it's best if builtins are listed in a separate section 
in that file, for ease of browsing. Xen also uses (conditionally) 
__builtin_mem*, __builtin_str* and others, so if all nonstandard 
intrinsics should be listed (as opposed to the ones in some way relevant 
for MISRA violations, which was the original scope of the document), 
then a subset of the attached list would be needed. There are a handful 
only used in ppc, and since the document only covers x86 and arm, those 
should be ignored for the time being.

Anyway, I'll send an RFC next week to decide the best route.

-- 
Nicola Vetrini, BSc
Software Engineer, BUGSENG srl (https://bugseng.com)

[-- Attachment #2: builtins.txt --]
[-- Type: text/plain, Size: 724 bytes --]

0|$ git grep -E -o "__builtin[a-z_]+" -- xen | cut -d':' -f2 | sort -u
__builtin_bswap
__builtin_clz
__builtin_clzll
__builtin_constant_p
__builtin_ctz
__builtin_ctzll
__builtin_expect
__builtin_frame_address
__builtin_has_attribute
__builtin_memchr
__builtin_memcmp
__builtin_memcpy
__builtin_memmove
__builtin_memset
__builtin_offsetof
__builtin_popcount
__builtin_popcountll
__builtin_prefetch
__builtin_return_address
__builtin_strcasecmp
__builtin_strchr
__builtin_strcmp
__builtin_strlen
__builtin_strncasecmp
__builtin_strncmp
__builtin_strrchr
__builtin_strstr
__builtin_trap
__builtin_types_compatible_p
__builtin_unreachable
__builtin_va_arg
__builtin_va_copy
__builtin_va_end
__builtin_va_list
__builtin_va_start

Re: [PATCH v2 12/13] xen/bitops: Clean up ffs64()/fls64() definitions

[Andrew Cooper]

On 27/05/2024 2:44 pm, Jan Beulich wrote:
>> --- a/xen/include/xen/bitops.h
>> +++ b/xen/include/xen/bitops.h
>> @@ -60,6 +60,14 @@ static always_inline __pure unsigned int ffsl(unsigned long x)
>>  #endif
>>  }
>>  
>> +static always_inline __pure unsigned int ffs64(uint64_t x)
>> +{
>> +    if ( BITS_PER_LONG == 64 )
> In principle >= 64 would be okay here, and hence I'd prefer if we used that
> less strict form. Yet I'm not going to insist.

Sorry - I'd meant to include this, but I've just found it still local to
my dev branch.

~Andrew

Re: [PATCH v2 07/13] x86/bitops: Improve arch_ffs() in the general case

[Jan Beulich]

On 01.06.2024 03:47, Andrew Cooper wrote:
> On 28/05/2024 2:12 pm, Jan Beulich wrote:
>> On 28.05.2024 14:30, Andrew Cooper wrote:
>>> On 27/05/2024 2:37 pm, Jan Beulich wrote:
>>>> On 27.05.2024 15:27, Jan Beulich wrote:
>>>>> On 24.05.2024 22:03, Andrew Cooper wrote:
>>>>>> --- a/xen/arch/x86/include/asm/bitops.h
>>>>>> +++ b/xen/arch/x86/include/asm/bitops.h
>>>>>> @@ -432,12 +432,28 @@ static inline int ffsl(unsigned long x)
>>>>>>  
>>>>>>  static always_inline unsigned int arch_ffs(unsigned int x)
>>>>>>  {
>>>>>> -    int r;
>>>>>> +    unsigned int r;
>>>>>> +
>>>>>> +    if ( __builtin_constant_p(x > 0) && x > 0 )
>>>>>> +    {
>>>>>> +        /* Safe, when the compiler knows that x is nonzero. */
>>>>>> +        asm ( "bsf %[val], %[res]"
>>>>>> +              : [res] "=r" (r)
>>>>>> +              : [val] "rm" (x) );
>>>>>> +    }
>>>>> In patch 11 relevant things are all in a single patch, making it easier
>>>>> to spot that this is dead code: The sole caller already has a
>>>>> __builtin_constant_p(), hence I don't see how the one here could ever
>>>>> return true. With that the respective part of the description is then
>>>>> questionable, too, I'm afraid: Where did you observe any actual effect
>>>>> from this? Or if you did - what am I missing?
>>>> Hmm, thinking about it: I suppose that's why you have
>>>> __builtin_constant_p(x > 0), not __builtin_constant_p(x). I have to admit
>>>> I'm (positively) surprised that the former may return true when the latter
>>>> doesn't.
>>> So was I, but this recommendation came straight from the GCC mailing
>>> list.  And it really does work, even back in obsolete versions of GCC.
>>>
>>> __builtin_constant_p() operates on an expression not a value, and is
>>> documented as such.
>> Of course.
>>
>>>>  Nevertheless I'm inclined to think this deserves a brief comment.
>>> There is a comment, and it's even visible in the snippet.
>> The comment is about the asm(); it is neither placed to clearly relate
>> to __builtin_constant_p(), nor is it saying anything about this specific
>> property of it. You said you were equally surprised; don't you think
>> that when both of us are surprised, a specific (even if brief) comment
>> is warranted?
> 
> Spell it out for me like I'm an idiot.
> 
> Because I'm looking at the patch I submitted, and at your request for "a
> brief comment", and I still have no idea what you think is wrong at the
> moment.
> 
> I'm also not included to write a comment saying "go and read the GCC
> manual more carefully".
> 
>>
>>>> As an aside, to better match the comment inside the if()'s body, how about
>>>>
>>>>     if ( __builtin_constant_p(!!x) && x )
>>>>
>>>> ? That also may make a little more clear that this isn't just a style
>>>> choice, but actually needed for the intended purpose.
>>> I am not changing the logic.
>>>
>>> Apart from anything else, your suggestion is trivially buggy.  I care
>>> about whether the RHS collapses to a constant, and the only way of doing
>>> that correctly is asking the compiler about the *exact* expression. 
>>> Asking about some other expression which you hope - but do not know -
>>> that the compiler will treat equivalently is bogus.  It would be
>>> strictly better to only take the else clause, than to have both halves
>>> emitted.
>>>
>>> This is the form I've tested extensively.  It's also the clearest form
>>> IMO.  You can experiment with alternative forms when we're not staring
>>> down code freeze of 4.19.
>> "Clearest form" is almost always a matter of taste. To me, comparing
>> unsigned values with > or < against 0 is generally at least suspicious.
>> Using != is typically better (again: imo), and simply omitting the != 0
>> then is shorter with no difference in effect. Except in peculiar cases
>> like this one, where indeed it took me some time to figure why the
>> comparison operator may not be omitted.
>>
>> All that said: I'm not going to insist on any change; the R-b previously
>> offered still stands. I would highly appreciate though if the (further)
>> comment asked for could be added.
>>
>> What I definitely dislike here is you - not for the first time - turning
>> down remarks because a change of yours is late.
> 
> Actually it's not to do with the release.  I'd reject it at any point
> because it's an unreasonable request to make; to me, or to anyone else.
> 
> It would be a matter of taste (which again you have a singular view on),
> if it wasn't for the fact that what you actually said was:
> 
> "I don't like it, and you should discard all the careful analysis you
> did because here's a form I prefer, that I haven't tested concerning a
> behaviour I didn't even realise until this email."

Just to clarify: Long before this reply of yours I understood and admitted
my mistake. A more clear / well placed comment (see further up) might have
avoided that. Still - thanks for extending the comment in what you have
committed.

> and even if it wasn't a buggy suggestion to begin with, it's still toxic
> maintainer feedback.

What's toxic about making a mistake? What's toxic about disliking "x > 0"
for unsigned quantities? As you say, it's a matter of taste to a fair
degree. Yet there are ample cases where taste as in "make it as clear as
possible to every reader" is used to ask me or others to change style. I
don't see why I shouldn't be permitted to at least make a similar remark,
even if then it's turned down (for good or bad reasons).

Jan