|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [xen master] xen/bitops: Implement generic_ffsl()/generic_flsl() in lib/
commit 95ddb7e9b00c1d3ce38930e631c8892b6a137759
Author: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
AuthorDate: Fri May 24 13:36:25 2024 +0100
Commit: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CommitDate: Sat Jun 1 02:28:14 2024 +0100
xen/bitops: Implement generic_ffsl()/generic_flsl() in lib/
generic_ffs()/generic_fls*( 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), 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_ffsl()/generic_flsl() 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@xxxxxxxxxx>
Reviewed-by: Jan Beulich <jbeulich@xxxxxxxx>
Acked-by: Stefano Stabellini <sstabellini@xxxxxxxxxx>
Release-acked-by: Oleksii Kurochko <oleksii.kurochko@xxxxxxxxx>
---
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 | 67 +++++++++++++++++++++++++++++
xen/lib/generic-flsl.c | 70 ++++++++++++++++++++++++++++++
6 files changed, 146 insertions(+), 86 deletions(-)
diff --git a/xen/arch/arm/include/asm/bitops.h
b/xen/arch/arm/include/asm/bitops.h
index 6c5ec34e66..685abfafb2 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 f984789e28..c8b11326ad 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 9b40f20381..218c346af2 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 (all forms).
+ *
+ * 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 e63798e1d4..a485415964 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 0000000000..c9fb34ffcd
--- /dev/null
+++ b/xen/lib/generic-ffsl.c
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <xen/bitops.h>
+#include <xen/init.h>
+#include <xen/self-tests.h>
+
+unsigned int generic_ffsl(unsigned long x)
+{
+ unsigned int r = 1;
+
+ if ( !x )
+ return 0;
+
+ BUILD_BUG_ON(BITS_PER_LONG > 64); /* Extend me when necessary. */
+
+#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_SELF_TESTS
+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_SELF_TESTS */
diff --git a/xen/lib/generic-flsl.c b/xen/lib/generic-flsl.c
new file mode 100644
index 0000000000..8f44f670fb
--- /dev/null
+++ b/xen/lib/generic-flsl.c
@@ -0,0 +1,70 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <xen/bitops.h>
+#include <xen/init.h>
+#include <xen/self-tests.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;
+
+ BUILD_BUG_ON(BITS_PER_LONG > 64); /* Extend me when necessary. */
+
+#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_SELF_TESTS
+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_SELF_TESTS */
--
generated by git-patchbot for /home/xen/git/xen.git#master
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |