Re: [PATCH] x86/bitops: Improve code generation for __scanbit()

[Jan Beulich <jbeulich@xxxxxxxx>]

On 10.11.2026 13:14, Andrew Cooper wrote:
> On 09/11/2026 8:46 am, Jan Beulich wrote:
>> On 06.11.2026 18:12, Andrew Cooper wrote:
>>> There's no need for an alternative.  Use the same technique as arch_ffs() by
>>> pre-loading the destination register using the caller chosen "zero case"
>>> instead of -1.
>>>
>>> No functional change.
>>>
>>> Signed-off-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
>>> ---
>>> CC: Jan Beulich <jbeulich@xxxxxxxx>
>>> CC: Roger Pau Monné <roger@xxxxxxxxxxxxxx>
>>> CC: Teddy Astie <teddy.astie@xxxxxxxxxx>
>>>
>>> Slightly RFC.  I don't particualrly like forward-declaring ffsl(), but I 
>>> don't
>>> see another option while maintaining a non-tangled common/arch header split.
>> Forward-declaring isn't a problem by itself, just that imo that wants putting
>> in xen/bitops.h, not ...
>>
>>> --- a/xen/arch/x86/include/asm/bitops.h
>>> +++ b/xen/arch/x86/include/asm/bitops.h
>>> @@ -320,18 +320,35 @@ extern unsigned int __find_first_zero_bit(
>>>  extern unsigned int __find_next_zero_bit(
>>>      const unsigned long *addr, unsigned int size, unsigned int offset);
>>>  
>>> +static attr_const unsigned int ffsl(unsigned long x);
>> ... here. asm/bitops.h already isn't included at the very top of the file, so
>> putting the decl there looks clean enough to me.
>>
>> (Another alternative would be to see about doing away with __scanbit().)
> 
> I'd like to do away with it.  There are only 4 users:
> 
> xen.git/xen$ git grep __scanbit
> arch/x86/bitops.c:38:        set = __scanbit(*p >> bit, BITS_PER_LONG);
> arch/x86/bitops.c:88:        set = __scanbit(~*p >> bit, BITS_PER_LONG);
> arch/x86/include/asm/bitops.h:329:static always_inline unsigned int 
> __scanbit(unsigned long val, unsigned int max)
> arch/x86/include/asm/bitops.h:378:        r__ = o__ + __scanbit(*a__ >> o__, 
> s__);                            \
> arch/x86/include/asm/bitops.h:410:        r__ = o__ + __scanbit(~*a__ >> o__, 
> s__);                           \
> 
> 
> i.e. the find_next{_zero,}bit() infrastructure.
> 
> For the two real functions, we could convert along the following lines:
> 
> diff --git a/xen/arch/x86/bitops.c b/xen/arch/x86/bitops.c
> index 22cfb6d8ec3a..009146df92b5 100644
> --- a/xen/arch/x86/bitops.c
> +++ b/xen/arch/x86/bitops.c
> @@ -35,9 +35,11 @@ unsigned int __find_next_bit(
>      if ( bit != 0 )
>      {
>          /* Look for a bit in the first word. */
> -        set = __scanbit(*p >> bit, BITS_PER_LONG);
> -        if ( set < BITS_PER_LONG )
> -            return (offset + set);
> +        set = ffsl(*p >> bit);
> +
> +        if ( set > 0 )
> +            return (offset + set - 1);
> +
>          offset += BITS_PER_LONG - bit;
>          p++;
>      }
> 
> except it has the disadvantage of turning a TZCNT into a BSR when in
> this path the "64 in the zero case" is fine.  That said, it's only older
> AMD CPUs where TZCNT vs BSR matters perf-wise, and this is a horrible
> path anyway because of the hand-rolled asm in __find_first_bit() so I'm
> most likely worrying over nothing.
> 
> What I don't see is an easy way to make the same transformation in the
> find_next{_zero,}_bit() macros.  This accounts for all the other
> invocations when expanded, which are quite a lot including behind
> bitmap_for_each().
> 
> 
> Alternatively, we could have a dedicated tzcnt(), and lean on the fact
> that "64 in the zero case" is probably fine in find_next{_zero,}_bit()
> even for the s__ < BITS_PER_LONG case.

I think this isn't just "probably", as istr us going through all
find_next{_zero,}_bit() (and derivatives) to check that they don't rely
on getting back the exact upper bound when no bit is set. IOW yes, I
think this might be a yet better way to go.

Jan