| Message ID | 20240828220351.2686408-12-andrew.cooper3@citrix.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | xen/bitops: hweight() cleanup/improvements | expand |
On 29.08.2024 00:03, Andrew Cooper wrote: > It has existed in x86 CPUs since 2008, so we're only 16 years late adding > support. With all the other scafolding in place, implement arch_hweightl() > for x86. > > The only complication is that the call to arch_generic_hweightl() is behind > the compilers back. Address this by writing it in ASM and ensure that it > preserves all registers. > > Copy the code generation from generic_hweightl(). It's not a complicated > algorithm, and is easy to regenerate if needs be, but cover it with the same > unit tests as test_generic_hweightl() just for piece of mind. > > Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> > --- > CC: Jan Beulich <JBeulich@suse.com> > CC: Roger Pau Monné <roger.pau@citrix.com> > > v2: > * Fix MISRA 8.2 (parameter name) and 8.5 (single declaration) regressions. > * Rename {arch->x86}-generic-hweightl.{S->c} > * Adjust ASM formating > > The __constructor trick to cause any reference to $foo() to pull in > test_$foo() only works when both are in the same TU. i.e. what I did in > v1 (putting test_arch_generic_hweightl() in the regular generic-hweightl.c) > didn't work. I'm afraid I don't understand this. What exactly didn't work, breaking in which way? Presumably as much as you, I don't really like the global asm() in a C file, when ideally the same could be written with less clutter in an assembly one. > This in turn means that arch_generic_hweightl() needs writing in a global asm > block, and also that we can't use FUNC()/END(). While we could adjust it to > work for GCC/binutils, we can't have CPP macros in Clang-IAS strings. What does Clang different from gcc there? I was hoping that at least their pre- processors would work in (sufficiently) similar ways. > --- /dev/null > +++ b/xen/lib/x86-generic-hweightl.c > @@ -0,0 +1,69 @@ > +/* SPDX-License-Identifier: GPL-2.0-only */ > + > +#include <xen/bitops.h> > +#include <xen/init.h> > +#include <xen/self-tests.h> > + > +/* > + * An implementation of generic_hweightl() used on hardware without the POPCNT > + * instruction. > + * > + * This function is called from within an ALTERNATIVE in arch_hweightl(). > + * i.e. behind the back of the compiler. Therefore all registers are callee > + * preserved. > + * > + * The ASM is what GCC-12 emits for generic_hweightl() in a release build of > + * Xen, with spilling of %rdi/%rdx to preserve the callers registers. > + * > + * Note: When we can use __attribute__((no_caller_saved_registers)) > + * unconditionally (GCC 7, Clang 5), we can implement this in plain C. > + */ > +asm ( > + ".type arch_generic_hweightl, STT_FUNC\n\t" > + ".globl arch_generic_hweightl\n\t" > + ".hidden arch_generic_hweightl\n\t" > + ".balign " STR(CONFIG_FUNCTION_ALIGNMENT) ", 0x90\n\t" Maybe better avoid open-coding CODE_FILL, in case we want to change that down the road? Also could I talk you into dropping the \t there? Canonical assembly code wants ... > + "arch_generic_hweightl:\n\t" .. labels unindented. Jan
On 29/08/2024 3:36 pm, Jan Beulich wrote: > On 29.08.2024 00:03, Andrew Cooper wrote: >> It has existed in x86 CPUs since 2008, so we're only 16 years late adding >> support. With all the other scafolding in place, implement arch_hweightl() >> for x86. >> >> The only complication is that the call to arch_generic_hweightl() is behind >> the compilers back. Address this by writing it in ASM and ensure that it >> preserves all registers. >> >> Copy the code generation from generic_hweightl(). It's not a complicated >> algorithm, and is easy to regenerate if needs be, but cover it with the same >> unit tests as test_generic_hweightl() just for piece of mind. >> >> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> >> --- >> CC: Jan Beulich <JBeulich@suse.com> >> CC: Roger Pau Monné <roger.pau@citrix.com> >> >> v2: >> * Fix MISRA 8.2 (parameter name) and 8.5 (single declaration) regressions. >> * Rename {arch->x86}-generic-hweightl.{S->c} >> * Adjust ASM formating >> >> The __constructor trick to cause any reference to $foo() to pull in >> test_$foo() only works when both are in the same TU. i.e. what I did in >> v1 (putting test_arch_generic_hweightl() in the regular generic-hweightl.c) >> didn't work. > I'm afraid I don't understand this. What exactly didn't work, breaking in which > way? Presumably as much as you, I don't really like the global asm() in a C > file, when ideally the same could be written with less clutter in an assembly > one. We have lib-y because we wish to not include arch_generic_hweightl() if it isn't referenced. But, test_arch_generic_hweightl() unconditionally references arch_generic_hweightl() (in CONFIG_SELF_TESTS builds). So, the trick is to have both {test_,}arch_generic_hweightl() together in the same object file, with test_* being entirely self contained as a constructor. That way, if and only if something else references arch_generic_hweightl() do we pull in this object file, and pick up the tests as side effect. v1 of this patch had the test in a separate object file, causing arch_generic_hweightl() to be referenced based on the inclusion criteria for regular generic-hweightl.c This patch causes the x86 build of Xen to no longer reference generic_hweightl(), so it was excluded along with its own tests, and test_arch_generic_hweightl(). Therefore, we had arch_generic_hweightl() in use, but the selftests not included. Both {test_,}arch_generic_hweightl() do need to be in the same TU for this to work (nicely), and I'm very uninterested in writing test_arch_generic_hweightl() in asm. > >> This in turn means that arch_generic_hweightl() needs writing in a global asm >> block, and also that we can't use FUNC()/END(). While we could adjust it to >> work for GCC/binutils, we can't have CPP macros in Clang-IAS strings. > What does Clang different from gcc there? I was hoping that at least their pre- > processors would work in (sufficiently) similar ways. It's inside a string, not outside, so CPP on the C file does nothing. Passing CPP over the intermediate .S would work, but we don't have an intermediate .S with Clang-IAS. I'm also not particularly interested in doubling up xen/linkage.h with different quoting in !__ASSEMBLY__ case. One other option which comes to mind is to have: .macro func name FUNC(\name) .endm which (I think) could be used as: asm ( "FUNC foo\n\t" ... "ret\n\t" "END foo" ); It reads almost the same, and avoids opencoding contents of FUNC, but even this requires changing the __ASSEMBLY__-ness of linkage.h and I can't see a nice way of making it happen. Or we finally bump our minimum toolchain version... GCC 7 is already old enough to be out of the recent LTS's... ~Andrew
On 30.08.2024 22:03, Andrew Cooper wrote: > On 29/08/2024 3:36 pm, Jan Beulich wrote: >> On 29.08.2024 00:03, Andrew Cooper wrote: >>> It has existed in x86 CPUs since 2008, so we're only 16 years late adding >>> support. With all the other scafolding in place, implement arch_hweightl() >>> for x86. >>> >>> The only complication is that the call to arch_generic_hweightl() is behind >>> the compilers back. Address this by writing it in ASM and ensure that it >>> preserves all registers. >>> >>> Copy the code generation from generic_hweightl(). It's not a complicated >>> algorithm, and is easy to regenerate if needs be, but cover it with the same >>> unit tests as test_generic_hweightl() just for piece of mind. >>> >>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> >>> --- >>> CC: Jan Beulich <JBeulich@suse.com> >>> CC: Roger Pau Monné <roger.pau@citrix.com> >>> >>> v2: >>> * Fix MISRA 8.2 (parameter name) and 8.5 (single declaration) regressions. >>> * Rename {arch->x86}-generic-hweightl.{S->c} >>> * Adjust ASM formating >>> >>> The __constructor trick to cause any reference to $foo() to pull in >>> test_$foo() only works when both are in the same TU. i.e. what I did in >>> v1 (putting test_arch_generic_hweightl() in the regular generic-hweightl.c) >>> didn't work. >> I'm afraid I don't understand this. What exactly didn't work, breaking in which >> way? Presumably as much as you, I don't really like the global asm() in a C >> file, when ideally the same could be written with less clutter in an assembly >> one. > > We have lib-y because we wish to not include arch_generic_hweightl() if > it isn't referenced. > > But, test_arch_generic_hweightl() unconditionally references > arch_generic_hweightl() (in CONFIG_SELF_TESTS builds). Which I assumed was intentional: Always have the tests, to make sure the code doesn't go stale (or even break). Looking at the v2 code again I notice that while now you're running the tests only when the to-be-tested function is referenced from elsewhere, the testing has become independent of CONFIG_SELF_TESTS. I don't think that was intended? > Both {test_,}arch_generic_hweightl() do need to be in the same TU for > this to work (nicely), and I'm very uninterested in writing > test_arch_generic_hweightl() in asm. Well - surely absolutely no question about this last aspect. >>> This in turn means that arch_generic_hweightl() needs writing in a global asm >>> block, and also that we can't use FUNC()/END(). While we could adjust it to >>> work for GCC/binutils, we can't have CPP macros in Clang-IAS strings. >> What does Clang different from gcc there? I was hoping that at least their pre- >> processors would work in (sufficiently) similar ways. > > It's inside a string, not outside, so CPP on the C file does nothing. > > Passing CPP over the intermediate .S would work, but we don't have an > intermediate .S with Clang-IAS. There's never an intermediate .S; it's always .s (not subject to C pre- processing). Therefore I continue to struggle with how CPP macros would come into (inconsistent) play here, unless they were used in construction of the string literal (and then work similarly for gcc and Clang). But as you say, we want to avoid playing with the intermediate file in any event. Jan
On 02/09/2024 9:06 am, Jan Beulich wrote: > On 30.08.2024 22:03, Andrew Cooper wrote: >> On 29/08/2024 3:36 pm, Jan Beulich wrote: >>> On 29.08.2024 00:03, Andrew Cooper wrote: >>>> It has existed in x86 CPUs since 2008, so we're only 16 years late adding >>>> support. With all the other scafolding in place, implement arch_hweightl() >>>> for x86. >>>> >>>> The only complication is that the call to arch_generic_hweightl() is behind >>>> the compilers back. Address this by writing it in ASM and ensure that it >>>> preserves all registers. >>>> >>>> Copy the code generation from generic_hweightl(). It's not a complicated >>>> algorithm, and is easy to regenerate if needs be, but cover it with the same >>>> unit tests as test_generic_hweightl() just for piece of mind. >>>> >>>> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> >>>> --- >>>> CC: Jan Beulich <JBeulich@suse.com> >>>> CC: Roger Pau Monné <roger.pau@citrix.com> >>>> >>>> v2: >>>> * Fix MISRA 8.2 (parameter name) and 8.5 (single declaration) regressions. >>>> * Rename {arch->x86}-generic-hweightl.{S->c} >>>> * Adjust ASM formating >>>> >>>> The __constructor trick to cause any reference to $foo() to pull in >>>> test_$foo() only works when both are in the same TU. i.e. what I did in >>>> v1 (putting test_arch_generic_hweightl() in the regular generic-hweightl.c) >>>> didn't work. >>> I'm afraid I don't understand this. What exactly didn't work, breaking in which >>> way? Presumably as much as you, I don't really like the global asm() in a C >>> file, when ideally the same could be written with less clutter in an assembly >>> one. >> We have lib-y because we wish to not include arch_generic_hweightl() if >> it isn't referenced. >> >> But, test_arch_generic_hweightl() unconditionally references >> arch_generic_hweightl() (in CONFIG_SELF_TESTS builds). > Which I assumed was intentional: Always have the tests, to make sure the code > doesn't go stale (or even break). Come to think of it, we already have two subtlety different things. common/bitops.c is SELF_TESTS only, and does both compile time (constant-folding) and runtime (non-folded) tests on the top-level APIs. This checks that the compiler agrees with the test parameters that I (or hopefully in the future, others) have chosen, and that every arch_$foo() override agrees with the compiler version. It has already found bugs. Both __builtin foo() vs fool() mismatches and I dread to think how long a bugs like that could have gone unnoticed. I caught ppc's arch_hweightl() before posting v1, but noone noticed ARM's arch_flsl() snafu when it was on the list (I found it when retrofitting SELF_TESTS around the series). Separately, anything that causes any {arch_,}generic_$foo()'s to be included also pulls in the SELF_TEST for that specific function. They're runtime only tests (no constant folding in an intentionally out-of-line function). But, it was intentional to try and make CONFIG_SELF_TESTS not blindly pull in the unused generic_$foo()'s. They'll get tested if they are referenced in a build, but the tests are only liable to break are during bitops development or a new/weird arch/environments. Furthermore, I expect (/hope) that we'll get to the point where we're being conservative with selftests. It's part of why I'm trying to keep the current ones pretty lean. > Looking at the v2 code again I notice that while now you're running the tests > only when the to-be-tested function is referenced from elsewhere, the testing > has become independent of CONFIG_SELF_TESTS. I don't think that was intended? Correct - that was an oversight. The CONFIG_SELF_TESTS guard wants to go back in. ~Andrew
On 29/08/2024 3:36 pm, Jan Beulich wrote: > On 29.08.2024 00:03, Andrew Cooper wrote: >> +asm ( >> + ".type arch_generic_hweightl, STT_FUNC\n\t" >> + ".globl arch_generic_hweightl\n\t" >> + ".hidden arch_generic_hweightl\n\t" >> + ".balign " STR(CONFIG_FUNCTION_ALIGNMENT) ", 0x90\n\t" > Maybe better avoid open-coding CODE_FILL, in case we want to change that > down the road? Sadly not. They're both inside #ifdef __ASSEMBLY__, causing this to turn into a "CODE_FILL" literal. For now I'll leave some grep fodder, until we can think of a nicer way of doing this. > Also could I talk you into dropping the \t there? Done. ~Andrew
diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h index 642d8e58b288..39e37f1cbe55 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -6,6 +6,7 @@ */ #include <asm/alternative.h> +#include <asm/asm_defns.h> #include <asm/cpufeatureset.h> /* @@ -475,4 +476,26 @@ static always_inline unsigned int arch_flsl(unsigned long x) } #define arch_flsl arch_flsl +unsigned int arch_generic_hweightl(unsigned long x); + +static always_inline unsigned int arch_hweightl(unsigned long x) +{ + unsigned int r; + + /* + * arch_generic_hweightl() is written in ASM in order to preserve all + * registers, as the compiler can't see the call. + * + * This limits the POPCNT instruction to using the same ABI as a function + * call (input in %rdi, output in %eax) but that's fine. + */ + alternative_io("call arch_generic_hweightl", + "popcnt %[val], %q[res]", X86_FEATURE_POPCNT, + ASM_OUTPUT2([res] "=a" (r) ASM_CALL_CONSTRAINT), + [val] "D" (x)); + + return r; +} +#define arch_hweightl arch_hweightl + #endif /* _X86_BITOPS_H */ diff --git a/xen/lib/Makefile b/xen/lib/Makefile index b6558e108bd9..54440f628aae 100644 --- a/xen/lib/Makefile +++ b/xen/lib/Makefile @@ -36,6 +36,7 @@ lib-y += strtol.o lib-y += strtoll.o lib-y += strtoul.o lib-y += strtoull.o +lib-$(CONFIG_X86) += x86-generic-hweightl.o lib-$(CONFIG_X86) += xxhash32.o lib-$(CONFIG_X86) += xxhash64.o diff --git a/xen/lib/x86-generic-hweightl.c b/xen/lib/x86-generic-hweightl.c new file mode 100644 index 000000000000..e0be25a01c1d --- /dev/null +++ b/xen/lib/x86-generic-hweightl.c @@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#include <xen/bitops.h> +#include <xen/init.h> +#include <xen/self-tests.h> + +/* + * An implementation of generic_hweightl() used on hardware without the POPCNT + * instruction. + * + * This function is called from within an ALTERNATIVE in arch_hweightl(). + * i.e. behind the back of the compiler. Therefore all registers are callee + * preserved. + * + * The ASM is what GCC-12 emits for generic_hweightl() in a release build of + * Xen, with spilling of %rdi/%rdx to preserve the callers registers. + * + * Note: When we can use __attribute__((no_caller_saved_registers)) + * unconditionally (GCC 7, Clang 5), we can implement this in plain C. + */ +asm ( + ".type arch_generic_hweightl, STT_FUNC\n\t" + ".globl arch_generic_hweightl\n\t" + ".hidden arch_generic_hweightl\n\t" + ".balign " STR(CONFIG_FUNCTION_ALIGNMENT) ", 0x90\n\t" + "arch_generic_hweightl:\n\t" + + "push %rdi\n\t" + "push %rdx\n\t" + + "movabs $0x5555555555555555, %rdx\n\t" + "mov %rdi, %rax\n\t" + "shr $1, %rax\n\t" + "and %rdx, %rax\n\t" + "sub %rax, %rdi\n\t" + "movabs $0x3333333333333333, %rax\n\t" + "mov %rdi, %rdx\n\t" + "shr $2, %rdi\n\t" + "and %rax, %rdx\n\t" + "and %rax, %rdi\n\t" + "add %rdi, %rdx\n\t" + "mov %rdx, %rax\n\t" + "shr $4, %rax\n\t" + "add %rdx, %rax\n\t" + "movabs $0x0f0f0f0f0f0f0f0f, %rdx\n\t" + "and %rdx, %rax\n\t" + "movabs $0x0101010101010101, %rdx\n\t" + "imul %rdx, %rax\n\t" + "shr $" STR(BITS_PER_LONG) "- 8, %rax\n\t" + + "pop %rdx\n\t" + "pop %rdi\n\t" + + "ret\n\t" + + ".size arch_generic_hweightl, . - arch_generic_hweightl\n\t" +); + +static void __init __constructor test_arch_generic_hweightl(void) +{ + RUNTIME_CHECK(arch_generic_hweightl, 0, 0); + RUNTIME_CHECK(arch_generic_hweightl, 1, 1); + RUNTIME_CHECK(arch_generic_hweightl, 3, 2); + RUNTIME_CHECK(arch_generic_hweightl, 7, 3); + RUNTIME_CHECK(arch_generic_hweightl, 0xff, 8); + + RUNTIME_CHECK(arch_generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); + RUNTIME_CHECK(arch_generic_hweightl, -1UL, BITS_PER_LONG); +}
It has existed in x86 CPUs since 2008, so we're only 16 years late adding support. With all the other scafolding in place, implement arch_hweightl() for x86. The only complication is that the call to arch_generic_hweightl() is behind the compilers back. Address this by writing it in ASM and ensure that it preserves all registers. Copy the code generation from generic_hweightl(). It's not a complicated algorithm, and is easy to regenerate if needs be, but cover it with the same unit tests as test_generic_hweightl() just for piece of mind. Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> --- CC: Jan Beulich <JBeulich@suse.com> CC: Roger Pau Monné <roger.pau@citrix.com> v2: * Fix MISRA 8.2 (parameter name) and 8.5 (single declaration) regressions. * Rename {arch->x86}-generic-hweightl.{S->c} * Adjust ASM formating The __constructor trick to cause any reference to $foo() to pull in test_$foo() only works when both are in the same TU. i.e. what I did in v1 (putting test_arch_generic_hweightl() in the regular generic-hweightl.c) didn't work. This in turn means that arch_generic_hweightl() needs writing in a global asm block, and also that we can't use FUNC()/END(). While we could adjust it to work for GCC/binutils, we can't have CPP macros in Clang-IAS strings. I don't particularly like opencoding FUNC()/END(), but I can't think of anything better. --- xen/arch/x86/include/asm/bitops.h | 23 +++++++++++ xen/lib/Makefile | 1 + xen/lib/x86-generic-hweightl.c | 69 +++++++++++++++++++++++++++++++ 3 files changed, 93 insertions(+) create mode 100644 xen/lib/x86-generic-hweightl.c