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

[Jan Beulich <jbeulich@xxxxxxxx>]

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?

> --- 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?

> --- /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.

Jan