Re: [PATCH v3 16/34] xen/lib: introduce generic find next bit operations

[Oleksii <oleksii.kurochko@xxxxxxxxx>]

On Tue, 2024-01-23 at 12:14 +0100, Jan Beulich wrote:
> On 22.12.2023 16:13, Oleksii Kurochko wrote:
> > --- a/xen/arch/riscv/include/asm/fence.h
> > +++ b/xen/arch/riscv/include/asm/fence.h
> > @@ -1,4 +1,4 @@
> > -/* SPDX-License-Identifier: GPL-2.0-or-later */
> > +/* SPDX-License-Identifier: GPL-2.0-only */
> >  #ifndef _ASM_RISCV_FENCE_H
> >  #define _ASM_RISCV_FENCE_H
> >  
> > @@ -11,3 +11,12 @@
> >  #endif
> >  
> >  #endif     /* _ASM_RISCV_FENCE_H */
> > +
> > +/*
> > + * Local variables:
> > + * mode: C
> > + * c-file-style: "BSD"
> > + * c-basic-offset: 4
> > + * indent-tabs-mode: nil
> > + * End:
> > + */
> 
> Surely all of this wants doing in the previous patch, where the
> header
> is introduced?
Yes, it should be in the previous patch. I'll do the proper rebase.

> 
> > --- a/xen/common/Kconfig
> > +++ b/xen/common/Kconfig
> > @@ -47,6 +47,9 @@ config ARCH_MAP_DOMAIN_PAGE
> >  config GENERIC_BUG_FRAME
> >     bool
> >  
> > +config GENERIC_FIND_NEXT_BIT
> > +   bool
> 
> There's no need for this, as ...
> 
> > --- a/xen/lib/Makefile
> > +++ b/xen/lib/Makefile
> > @@ -3,6 +3,7 @@ obj-$(CONFIG_X86) += x86/
> >  lib-y += bsearch.o
> >  lib-y += ctors.o
> >  lib-y += ctype.o
> > +lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find-next-bit.o
> 
> ... you're moving this to lib/. Or have you encountered any issue
> with building this uniformly, and you forgot to mention this in
> the description?
I didn't check. My intention was to provide opportunity to check if an
architecture want to use generic version or not. Otherwise, I expected
that we will have multiple definiotion of the funcion.

But considering that they are all defined under #ifdef...#endif we can
remove the declaration of the config GENERIC_FIND_NEXT_BIT.
> 
> > --- /dev/null
> > +++ b/xen/lib/find-next-bit.c
> > @@ -0,0 +1,281 @@
> > +/* find_next_bit.c: fallback find next bit implementation
> > + *
> > + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
> > + * Written by David Howells (dhowells@xxxxxxxxxx)
> > + *
> > + * This program is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU General Public License
> > + * as published by the Free Software Foundation; either version
> > + * 2 of the License, or (at your option) any later version.
> > + */
> > +#include <xen/bitops.h>
> > +
> > +#include <asm/byteorder.h>
> > +
> > +#ifndef find_next_bit
> > +/*
> > + * Find the next set bit in a memory region.
> > + */
> > +unsigned long find_next_bit(const unsigned long *addr, unsigned
> > long size,
> > +                       unsigned long offset)
> > +{
> > +   const unsigned long *p = addr + BIT_WORD(offset);
> > +   unsigned long result = offset & ~(BITS_PER_LONG-1);
> > +   unsigned long tmp;
> > +
> > +   if (offset >= size)
> > +           return size;
> > +   size -= result;
> > +   offset %= BITS_PER_LONG;
> > +   if (offset) {
> > +           tmp = *(p++);
> > +           tmp &= (~0UL << offset);
> > +           if (size < BITS_PER_LONG)
> > +                   goto found_first;
> > +           if (tmp)
> > +                   goto found_middle;
> > +           size -= BITS_PER_LONG;
> > +           result += BITS_PER_LONG;
> > +   }
> > +   while (size & ~(BITS_PER_LONG-1)) {
> > +           if ((tmp = *(p++)))
> > +                   goto found_middle;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +   tmp = *p;
> > +
> > +found_first:
> > +   tmp &= (~0UL >> (BITS_PER_LONG - size));
> > +   if (tmp == 0UL)         /* Are any bits set? */
> > +           return result + size;   /* Nope. */
> > +found_middle:
> > +   return result + __ffs(tmp);
> > +}
> > +EXPORT_SYMBOL(find_next_bit);
> > +#endif
> > +
> > +#ifndef find_next_zero_bit
> > +/*
> > + * This implementation of find_{first,next}_zero_bit was stolen
> > from
> > + * Linus' asm-alpha/bitops.h.
> > + */
> > +unsigned long find_next_zero_bit(const unsigned long *addr,
> > unsigned long size,
> > +                            unsigned long offset)
> > +{
> > +   const unsigned long *p = addr + BIT_WORD(offset);
> > +   unsigned long result = offset & ~(BITS_PER_LONG-1);
> > +   unsigned long tmp;
> > +
> > +   if (offset >= size)
> > +           return size;
> > +   size -= result;
> > +   offset %= BITS_PER_LONG;
> > +   if (offset) {
> > +           tmp = *(p++);
> > +           tmp |= ~0UL >> (BITS_PER_LONG - offset);
> > +           if (size < BITS_PER_LONG)
> > +                   goto found_first;
> > +           if (~tmp)
> > +                   goto found_middle;
> > +           size -= BITS_PER_LONG;
> > +           result += BITS_PER_LONG;
> > +   }
> > +   while (size & ~(BITS_PER_LONG-1)) {
> > +           if (~(tmp = *(p++)))
> > +                   goto found_middle;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +   tmp = *p;
> > +
> > +found_first:
> > +   tmp |= ~0UL << size;
> > +   if (tmp == ~0UL)        /* Are any bits zero? */
> > +           return result + size;   /* Nope. */
> > +found_middle:
> > +   return result + ffz(tmp);
> > +}
> > +EXPORT_SYMBOL(find_next_zero_bit);
> > +#endif
> > +
> > +#ifndef find_first_bit
> > +/*
> > + * Find the first set bit in a memory region.
> > + */
> > +unsigned long find_first_bit(const unsigned long *addr, unsigned
> > long size)
> > +{
> > +   const unsigned long *p = addr;
> > +   unsigned long result = 0;
> > +   unsigned long tmp;
> > +
> > +   while (size & ~(BITS_PER_LONG-1)) {
> > +           if ((tmp = *(p++)))
> > +                   goto found;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +
> > +   tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
> > +   if (tmp == 0UL)         /* Are any bits set? */
> > +           return result + size;   /* Nope. */
> > +found:
> > +   return result + __ffs(tmp);
> > +}
> > +EXPORT_SYMBOL(find_first_bit);
> > +#endif
> > +
> > +#ifndef find_first_zero_bit
> > +/*
> > + * Find the first cleared bit in a memory region.
> > + */
> > +unsigned long find_first_zero_bit(const unsigned long *addr,
> > unsigned long size)
> > +{
> > +   const unsigned long *p = addr;
> > +   unsigned long result = 0;
> > +   unsigned long tmp;
> > +
> > +   while (size & ~(BITS_PER_LONG-1)) {
> > +           if (~(tmp = *(p++)))
> > +                   goto found;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +
> > +   tmp = (*p) | (~0UL << size);
> > +   if (tmp == ~0UL)        /* Are any bits zero? */
> > +           return result + size;   /* Nope. */
> > +found:
> > +   return result + ffz(tmp);
> > +}
> > +EXPORT_SYMBOL(find_first_zero_bit);
> > +#endif
> > +
> > +#ifdef __BIG_ENDIAN
> > +
> > +/* include/linux/byteorder does not support "unsigned long" type
> > */
> > +static inline unsigned long ext2_swabp(const unsigned long * x)
> > +{
> > +#if BITS_PER_LONG == 64
> > +   return (unsigned long) __swab64p((u64 *) x);
> > +#elif BITS_PER_LONG == 32
> > +   return (unsigned long) __swab32p((u32 *) x);
> > +#else
> > +#error BITS_PER_LONG not defined
> > +#endif
> > +}
> > +
> > +/* include/linux/byteorder doesn't support "unsigned long" type */
> > +static inline unsigned long ext2_swab(const unsigned long y)
> > +{
> > +#if BITS_PER_LONG == 64
> > +   return (unsigned long) __swab64((u64) y);
> > +#elif BITS_PER_LONG == 32
> > +   return (unsigned long) __swab32((u32) y);
> > +#else
> > +#error BITS_PER_LONG not defined
> > +#endif
> > +}
> > +
> > +#ifndef find_next_zero_bit_le
> > +unsigned long find_next_zero_bit_le(const void *addr, unsigned
> > +           long size, unsigned long offset)
> > +{
> > +   const unsigned long *p = addr;
> > +   unsigned long result = offset & ~(BITS_PER_LONG - 1);
> > +   unsigned long tmp;
> > +
> > +   if (offset >= size)
> > +           return size;
> > +   p += BIT_WORD(offset);
> > +   size -= result;
> > +   offset &= (BITS_PER_LONG - 1UL);
> > +   if (offset) {
> > +           tmp = ext2_swabp(p++);
> > +           tmp |= (~0UL >> (BITS_PER_LONG - offset));
> > +           if (size < BITS_PER_LONG)
> > +                   goto found_first;
> > +           if (~tmp)
> > +                   goto found_middle;
> > +           size -= BITS_PER_LONG;
> > +           result += BITS_PER_LONG;
> > +   }
> > +
> > +   while (size & ~(BITS_PER_LONG - 1)) {
> > +           if (~(tmp = *(p++)))
> > +                   goto found_middle_swap;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +   tmp = ext2_swabp(p);
> > +found_first:
> > +   tmp |= ~0UL << size;
> > +   if (tmp == ~0UL)        /* Are any bits zero? */
> > +           return result + size; /* Nope. Skip ffz */
> > +found_middle:
> > +   return result + ffz(tmp);
> > +
> > +found_middle_swap:
> > +   return result + ffz(ext2_swab(tmp));
> > +}
> > +EXPORT_SYMBOL(find_next_zero_bit_le);
> > +#endif
> > +
> > +#ifndef find_next_bit_le
> > +unsigned long find_next_bit_le(const void *addr, unsigned
> > +           long size, unsigned long offset)
> > +{
> > +   const unsigned long *p = addr;
> > +   unsigned long result = offset & ~(BITS_PER_LONG - 1);
> > +   unsigned long tmp;
> > +
> > +   if (offset >= size)
> > +           return size;
> > +   p += BIT_WORD(offset);
> > +   size -= result;
> > +   offset &= (BITS_PER_LONG - 1UL);
> > +   if (offset) {
> > +           tmp = ext2_swabp(p++);
> > +           tmp &= (~0UL << offset);
> > +           if (size < BITS_PER_LONG)
> > +                   goto found_first;
> > +           if (tmp)
> > +                   goto found_middle;
> > +           size -= BITS_PER_LONG;
> > +           result += BITS_PER_LONG;
> > +   }
> > +
> > +   while (size & ~(BITS_PER_LONG - 1)) {
> > +           tmp = *(p++);
> > +           if (tmp)
> > +                   goto found_middle_swap;
> > +           result += BITS_PER_LONG;
> > +           size -= BITS_PER_LONG;
> > +   }
> > +   if (!size)
> > +           return result;
> > +   tmp = ext2_swabp(p);
> > +found_first:
> > +   tmp &= (~0UL >> (BITS_PER_LONG - size));
> > +   if (tmp == 0UL)         /* Are any bits set? */
> > +           return result + size; /* Nope. */
> > +found_middle:
> > +   return result + __ffs(tmp);
> > +
> > +found_middle_swap:
> > +   return result + __ffs(ext2_swab(tmp));
> > +}
> > +EXPORT_SYMBOL(find_next_bit_le);
> > +#endif
> > +
> > +#endif /* __BIG_ENDIAN */
> 
> I was going to ask that you convince git to actually present a proper
> diff, to make visible what changes. But other than the description
> says
> you don't really move the file, you copy it. Judging from further
> titles
> there's also nowhere you'd make Arm actually use this now generic
> code.
I wanted to do it separately, outside this patch series to simplify
review and not have Arm specific changes in RISC-V patch series.

Regarding a proper diff, you would like me to make git shows that it
was copy from Arm and it is not newly created file. Am I understand you
correctly?

~ Oleksii