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 testing infrastructure in patch 1.

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

Testing:
  https://gitlab.com/xen-project/people/andyhhp/xen/-/pipelines/1212269924
  https://cirrus-ci.com/build/4939856296542208

Andrew Cooper (7):
  xen/bitops: Cleanup ahead of rearrangements
  xen/bitops: Implement ffs() in common logic
  xen/bitops: Implement ffsl() in common logic
  xen/bitops: Delete generic_ffs{,l}()
  xen/bitops: Implement ffs64() in common logic
  xen: Swap find_first_set_bit() for ffsl() - 1
  xen/bitops: Delete find_first_set_bit()

 xen/arch/arm/include/asm/bitops.h            | 16 +---
 xen/arch/ppc/include/asm/bitops.h            | 11 ---
 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            | 53 +++++------
 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                          | 70 ++++++++++++++
 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 +-
 xen/include/xen/bitops.h                     | 97 +++++++++-----------
 xen/include/xen/compiler.h                   |  3 +-
 18 files changed, 160 insertions(+), 127 deletions(-)
 create mode 100644 xen/common/bitops.c


base-commit: 03cf7ca23e0e876075954c558485b267b7d02406
-- 
2.30.2

On 13/03/2024 5:27 pm, Andrew Cooper wrote:
> Start cleaning it up with ffs() and friends.  Across the board, this adds:
>
>  * Functioning bitops without arch-specific asm

It turns out that RISC-V doesn't have a CLZ instruction in the base
ISA.  As a consequence, __builtin_ffs() emits a library call to ffs() on
GCC, or a de Bruijn sequence on Clang.

The optional Zbb extension adds a CLZ instruction, after which
__builtin_ffs() emits a very simple sequence.

This leaves us with several options.

1) Put generic_ffs() back in, although if we do this then it's going to
be out-of-line in lib/ where it can be mostly ignored.

2) Require Zbb for Xen.

3) Alternative it up with Zbb or generic_ffs().


I've got half a mind to do 1) irrespective.  It's mostly just shuffling
logic out of bitops.h into lib/.

I also think we should do option 2 for RISCV.  Given the instruction
groups that H does mandate, it's unrealistic to expect that such a chip
wouldn't support Zbb/etc.

Also, getting full alternatives working is yet-more work that's not
trivial at this point in RISCV's development.  I think it is entirely
reasonable to avoid this work for now, and make it a problem for anyone
who has an H-capable Zbb-incapable system.  (with a strong implication
that this is work that probably never needs to be done.)

~Andrew

On 14.03.2024 15:45, Andrew Cooper wrote:
> On 13/03/2024 5:27 pm, Andrew Cooper wrote:
>> Start cleaning it up with ffs() and friends.  Across the board, this adds:
>>
>>  * Functioning bitops without arch-specific asm
> 
> It turns out that RISC-V doesn't have a CLZ instruction in the base
> ISA.  As a consequence, __builtin_ffs() emits a library call to ffs() on
> GCC, or a de Bruijn sequence on Clang.
> 
> The optional Zbb extension adds a CLZ instruction, after which
> __builtin_ffs() emits a very simple sequence.
> 
> This leaves us with several options.
> 
> 1) Put generic_ffs() back in, although if we do this then it's going to
> be out-of-line in lib/ where it can be mostly ignored.
> 
> 2) Require Zbb for Xen.
> 
> 3) Alternative it up with Zbb or generic_ffs().
> 
> 
> I've got half a mind to do 1) irrespective.  It's mostly just shuffling
> logic out of bitops.h into lib/.

Yes. Might also help with the bi-sectability issue you faced.

> I also think we should do option 2 for RISCV.  Given the instruction
> groups that H does mandate, it's unrealistic to expect that such a chip
> wouldn't support Zbb/etc.

I'm not so sure here.

> Also, getting full alternatives working is yet-more work that's not
> trivial at this point in RISCV's development.  I think it is entirely
> reasonable to avoid this work for now, and make it a problem for anyone
> who has an H-capable Zbb-incapable system.  (with a strong implication
> that this is work that probably never needs to be done.)

That's definitely for later.

Jan

On Thu, 2024-03-14 at 16:33 +0100, Jan Beulich wrote:
> On 14.03.2024 15:45, Andrew Cooper wrote:
> > On 13/03/2024 5:27 pm, Andrew Cooper wrote:
> > > Start cleaning it up with ffs() and friends.  Across the board,
> > > this adds:
> > > 
> > >  * Functioning bitops without arch-specific asm
> > 
> > It turns out that RISC-V doesn't have a CLZ instruction in the base
> > ISA.  As a consequence, __builtin_ffs() emits a library call to
> > ffs() on
> > GCC, or a de Bruijn sequence on Clang.
> > 
> > The optional Zbb extension adds a CLZ instruction, after which
> > __builtin_ffs() emits a very simple sequence.
> > 
> > This leaves us with several options.
> > 
> > 1) Put generic_ffs() back in, although if we do this then it's
> > going to
> > be out-of-line in lib/ where it can be mostly ignored.
> > 
> > 2) Require Zbb for Xen.
> > 
> > 3) Alternative it up with Zbb or generic_ffs().
> > 
> > 
> > I've got half a mind to do 1) irrespective.  It's mostly just
> > shuffling
> > logic out of bitops.h into lib/.
> 
> Yes. Might also help with the bi-sectability issue you faced.
> 
> > I also think we should do option 2 for RISCV.  Given the
> > instruction
> > groups that H does mandate, it's unrealistic to expect that such a
> > chip
> > wouldn't support Zbb/etc.
> 
> I'm not so sure here.
If to look at available specs of CPUs with H, then, for example, SiFive
P600 series family doesn't support Zbb extenstion:
https://sifive.cdn.prismic.io/sifive/7be0420e-dac1-4558-85bc-50c7a10787e7_p600_datasheet.pdf

But I asked a team who are producing CPU with H support and they have
Zbb extenstion.

> 
> > Also, getting full alternatives working is yet-more work that's not
> > trivial at this point in RISCV's development.  I think it is
> > entirely
> > reasonable to avoid this work for now, and make it a problem for
> > anyone
> > who has an H-capable Zbb-incapable system.  (with a strong
> > implication
> > that this is work that probably never needs to be done.)
> 
> That's definitely for later.
Considering that we are mainly using QEMU and it provides Zbb extension
we can just update -march, and that a real h/w where I can ask to test
a code also support this extenstion I will update riscv/booting.txt and
update -march.

~ Oleksii

On 14/03/2024 3:33 pm, Jan Beulich wrote:
> On 14.03.2024 15:45, Andrew Cooper wrote:
>> On 13/03/2024 5:27 pm, Andrew Cooper wrote:
>>> Start cleaning it up with ffs() and friends.  Across the board, this adds:
>>>
>>>  * Functioning bitops without arch-specific asm
>> It turns out that RISC-V doesn't have a CLZ instruction in the base
>> ISA.  As a consequence, __builtin_ffs() emits a library call to ffs() on
>> GCC, or a de Bruijn sequence on Clang.
>>
>> The optional Zbb extension adds a CLZ instruction, after which
>> __builtin_ffs() emits a very simple sequence.
>>
>> This leaves us with several options.
>>
>> 1) Put generic_ffs() back in, although if we do this then it's going to
>> be out-of-line in lib/ where it can be mostly ignored.
>>
>> 2) Require Zbb for Xen.
>>
>> 3) Alternative it up with Zbb or generic_ffs().
>>
>>
>> I've got half a mind to do 1) irrespective.  It's mostly just shuffling
>> logic out of bitops.h into lib/.
> Yes. Might also help with the bi-sectability issue you faced.

I'm not sure it will help for bisectability in this case.  But it might
simplify some of the other rearrangements.


>> I also think we should do option 2 for RISCV.  Given the instruction
>> groups that H does mandate, it's unrealistic to expect that such a chip
>> wouldn't support Zbb/etc.
> I'm not so sure here.
>
>> Also, getting full alternatives working is yet-more work that's not
>> trivial at this point in RISCV's development.  I think it is entirely
>> reasonable to avoid this work for now, and make it a problem for anyone
>> who has an H-capable Zbb-incapable system.  (with a strong implication
>> that this is work that probably never needs to be done.)
> That's definitely for later.

The argument being made is that it seems highly unlikely for there to be
non-Zbb systems running Xen, and furthermore, if this turns out not to
be true, it is reasonable to offload the effort of making it work to
whomever has hardware looking like that.

i.e. it's fine to require Zbb at this point.

This doesn't prevent someone else doing the work to alter this in the
future, for what appears to be an absurd configuration that is unlikely
to exist in reality.

~Andrew