| Message ID | fea2e65768457adcfedbfcc294004b1d5c2e86ea.1707495704.git.oleksii.kurochko@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v2] xen/lib: introduce generic find next bit operations | expand |
On 09.02.2024 18:58, Oleksii Kurochko wrote: > find-next-bit.c is common for Arm64, PPC and RISCV64, > so it is moved to xen/lib. > > PPC has been transitioned to generic functions from find-next-bit.c > since it now shares the same implementation as the PPC-specific code. > > The MISRA exclude list has been updated to verify > lib/find-next-bit.c instead of Arm's find_next_bit.c, > as Arm's find_next_bit.c has been relocated to xen/lib/. > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > Xen and being removed from the Linux kernel [1], it could theoretically > prove useful for Xen. This is because the Linux kernel transitioned > Arm to the generic version of find_first_bit() and > find_first_zero_bit() due to improvements [1] in both performance > and .text size. > It would be prudent to investigate whether [1] is applicable to Xen > as well and, if so, implement the necessary changes in a separate patch. > > [1] https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > Suggested-by: Jan Beulich <jbeulich@suse.com> > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> A revision log would have been nice, though. Jan
Hi Oleksii, On 09/02/2024 17:58, Oleksii Kurochko wrote: > find-next-bit.c is common for Arm64, PPC and RISCV64, > so it is moved to xen/lib. > > PPC has been transitioned to generic functions from find-next-bit.c > since it now shares the same implementation as the PPC-specific code. > > The MISRA exclude list has been updated to verify > lib/find-next-bit.c instead of Arm's find_next_bit.c, > as Arm's find_next_bit.c has been relocated to xen/lib/. > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > Xen and being removed from the Linux kernel [1], it could theoretically > prove useful for Xen. This is because the Linux kernel transitioned > Arm to the generic version of find_first_bit() and > find_first_zero_bit() due to improvements [1] in both performance > and .text size. > It would be prudent to investigate whether [1] is applicable to Xen > as well and, if so, implement the necessary changes in a separate patch. > > [1] https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > Suggested-by: Jan Beulich <jbeulich@suse.com> > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> Reviewed-by: Julien Grall <jgrall@amazon.com> Cheers,
On Mon, 2024-02-12 at 15:15 +0100, Jan Beulich wrote: > On 09.02.2024 18:58, Oleksii Kurochko wrote: > > find-next-bit.c is common for Arm64, PPC and RISCV64, > > so it is moved to xen/lib. > > > > PPC has been transitioned to generic functions from find-next-bit.c > > since it now shares the same implementation as the PPC-specific > > code. > > > > The MISRA exclude list has been updated to verify > > lib/find-next-bit.c instead of Arm's find_next_bit.c, > > as Arm's find_next_bit.c has been relocated to xen/lib/. > > > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > > Xen and being removed from the Linux kernel [1], it could > > theoretically > > prove useful for Xen. This is because the Linux kernel transitioned > > Arm to the generic version of find_first_bit() and > > find_first_zero_bit() due to improvements [1] in both performance > > and .text size. > > It would be prudent to investigate whether [1] is applicable to Xen > > as well and, if so, implement the necessary changes in a separate > > patch. > > > > [1] > > https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > > > Suggested-by: Jan Beulich <jbeulich@suse.com> > > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> > > Reviewed-by: Jan Beulich <jbeulich@suse.com> Thanks! > > A revision log would have been nice, though. Missed that. In case if it will be needed a new patch version, I'll back the log. ~ Oleksii
Hi Julien, On Tue, 2024-02-13 at 17:18 +0000, Julien Grall wrote: > Hi Oleksii, > > On 09/02/2024 17:58, Oleksii Kurochko wrote: > > find-next-bit.c is common for Arm64, PPC and RISCV64, > > so it is moved to xen/lib. > > > > PPC has been transitioned to generic functions from find-next-bit.c > > since it now shares the same implementation as the PPC-specific > > code. > > > > The MISRA exclude list has been updated to verify > > lib/find-next-bit.c instead of Arm's find_next_bit.c, > > as Arm's find_next_bit.c has been relocated to xen/lib/. > > > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > > Xen and being removed from the Linux kernel [1], it could > > theoretically > > prove useful for Xen. This is because the Linux kernel transitioned > > Arm to the generic version of find_first_bit() and > > find_first_zero_bit() due to improvements [1] in both performance > > and .text size. > > It would be prudent to investigate whether [1] is applicable to Xen > > as well and, if so, implement the necessary changes in a separate > > patch. > > > > [1] > > https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > > > Suggested-by: Jan Beulich <jbeulich@suse.com> > > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> > > Reviewed-by: Julien Grall <jgrall@amazon.com> Thanks for review. ~ Oleksii
Hi Shawn, Could you please take a look at the patch and PPC-related changes ( xen/arch/ppc/include/asm/bitops.h )? Thanks in advance. ~ Oleksii On Fri, 2024-02-09 at 18:58 +0100, Oleksii Kurochko wrote: > find-next-bit.c is common for Arm64, PPC and RISCV64, > so it is moved to xen/lib. > > PPC has been transitioned to generic functions from find-next-bit.c > since it now shares the same implementation as the PPC-specific code. > > The MISRA exclude list has been updated to verify > lib/find-next-bit.c instead of Arm's find_next_bit.c, > as Arm's find_next_bit.c has been relocated to xen/lib/. > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > Xen and being removed from the Linux kernel [1], it could > theoretically > prove useful for Xen. This is because the Linux kernel transitioned > Arm to the generic version of find_first_bit() and > find_first_zero_bit() due to improvements [1] in both performance > and .text size. > It would be prudent to investigate whether [1] is applicable to Xen > as well and, if so, implement the necessary changes in a separate > patch. > > [1] > https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > Suggested-by: Jan Beulich <jbeulich@suse.com> > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> > --- > docs/misra/exclude-list.json | 8 +- > xen/arch/arm/arm64/lib/Makefile | 2 +- > xen/arch/arm/include/asm/arm64/bitops.h | 46 +------ > xen/arch/ppc/include/asm/bitops.h | 115 ---------------- > -- > xen/include/xen/bitops.h | 48 ++++++++ > xen/lib/Makefile | 1 + > .../find_next_bit.c => lib/find-next-bit.c} | 0 > 7 files changed, 55 insertions(+), 165 deletions(-) > rename xen/{arch/arm/arm64/lib/find_next_bit.c => lib/find-next- > bit.c} (100%) > > diff --git a/docs/misra/exclude-list.json b/docs/misra/exclude- > list.json > index 7971d0e70f..b28174d0eb 100644 > --- a/docs/misra/exclude-list.json > +++ b/docs/misra/exclude-list.json > @@ -13,10 +13,6 @@ > "rel_path": "arch/arm/arm64/insn.c", > "comment": "Imported on Linux, ignore for now" > }, > - { > - "rel_path": "arch/arm/arm64/lib/find_next_bit.c", > - "comment": "Imported from Linux, ignore for now" > - }, > { > "rel_path": "arch/x86/acpi/boot.c", > "comment": "Imported from Linux, ignore for now" > @@ -221,6 +217,10 @@ > "rel_path": "include/xen/decompress.h", > "comment": "Imported from Linux, ignore for now" > }, > + { > + "rel_path": "lib/find-next-bit.c", > + "comment": "Imported from Linux, ignore for now" > + }, > { > "rel_path": "lib/list-sort.c", > "comment": "Imported from Linux, ignore for now" > diff --git a/xen/arch/arm/arm64/lib/Makefile > b/xen/arch/arm/arm64/lib/Makefile > index 1b9c7a95e6..66cfac435a 100644 > --- a/xen/arch/arm/arm64/lib/Makefile > +++ b/xen/arch/arm/arm64/lib/Makefile > @@ -1,4 +1,4 @@ > obj-y += memcpy.o memcmp.o memmove.o memset.o memchr.o > obj-y += clear_page.o > -obj-y += bitops.o find_next_bit.o > +obj-y += bitops.o > obj-y += strchr.o strcmp.o strlen.o strncmp.o strnlen.o strrchr.o > diff --git a/xen/arch/arm/include/asm/arm64/bitops.h > b/xen/arch/arm/include/asm/arm64/bitops.h > index d85a49bca4..0efde29068 100644 > --- a/xen/arch/arm/include/asm/arm64/bitops.h > +++ b/xen/arch/arm/include/asm/arm64/bitops.h > @@ -36,57 +36,13 @@ static inline int flsl(unsigned long x) > > /* Based on linux/include/asm-generic/bitops/find.h */ > > -#ifndef find_next_bit > -/** > - * find_next_bit - find the next set bit in a memory region > - * @addr: The address to base the search on > - * @offset: The bitnumber to start searching at > - * @size: The bitmap size in bits > - */ > -extern unsigned long find_next_bit(const unsigned long *addr, > unsigned long > - size, unsigned long offset); > -#endif > - > -#ifndef find_next_zero_bit > -/** > - * find_next_zero_bit - find the next cleared bit in a memory region > - * @addr: The address to base the search on > - * @offset: The bitnumber to start searching at > - * @size: The bitmap size in bits > - */ > -extern unsigned long find_next_zero_bit(const unsigned long *addr, > unsigned > - long size, unsigned long offset); > -#endif > - > -#ifdef CONFIG_GENERIC_FIND_FIRST_BIT > - > -/** > - * find_first_bit - find the first set bit in a memory region > - * @addr: The address to start the search at > - * @size: The maximum size to search > - * > - * Returns the bit number of the first set bit. > - */ > -extern unsigned long find_first_bit(const unsigned long *addr, > - unsigned long size); > - > -/** > - * find_first_zero_bit - find the first cleared bit in a memory > region > - * @addr: The address to start the search at > - * @size: The maximum size to search > - * > - * Returns the bit number of the first cleared bit. > - */ > -extern unsigned long find_first_zero_bit(const unsigned long *addr, > - unsigned long size); > -#else /* CONFIG_GENERIC_FIND_FIRST_BIT */ > +#ifndef CONFIG_GENERIC_FIND_FIRST_BIT > > #define find_first_bit(addr, size) find_next_bit((addr), (size), 0) > #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), > (size), 0) > > #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ > > - > #endif /* _ARM_ARM64_BITOPS_H */ > /* > * Local variables: > diff --git a/xen/arch/ppc/include/asm/bitops.h > b/xen/arch/ppc/include/asm/bitops.h > index 5e7f36c21d..5820b9ce7b 100644 > --- a/xen/arch/ppc/include/asm/bitops.h > +++ b/xen/arch/ppc/include/asm/bitops.h > @@ -217,119 +217,4 @@ static always_inline unsigned long > __ffs(unsigned long word) > */ > #define find_first_set_bit(x) (ffsl(x) - 1) > > -/* > - * Find the first set bit in a memory region. > - */ > -static inline 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); > -} > - > -static inline unsigned long find_next_bit(const unsigned long *addr, > - unsigned long size, > - unsigned long offset) > -{ > - const unsigned long *p = addr + BITOP_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); > -} > - > -/* > - * This implementation of find_{first,next}_zero_bit was stolen from > - * Linus' asm-alpha/bitops.h. > - */ > -static inline unsigned long find_next_zero_bit(const unsigned long > *addr, > - unsigned long size, > - unsigned long offset) > -{ > - const unsigned long *p = addr + BITOP_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); > -} > - > #endif /* _ASM_PPC_BITOPS_H */ > diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h > index 2cb7892bcc..e3c5a4ccf3 100644 > --- a/xen/include/xen/bitops.h > +++ b/xen/include/xen/bitops.h > @@ -105,6 +105,54 @@ static inline int generic_flsl(unsigned long x) > */ > #include <asm/bitops.h> > > +#ifndef find_next_bit > +/** > + * find_next_bit - find the next set bit in a memory region > + * @addr: The address to base the search on > + * @offset: The bitnumber to start searching at > + * @size: The bitmap size in bits > + */ > +extern unsigned long find_next_bit(const unsigned long *addr, > + unsigned long size, > + unsigned long offset); > +#endif > + > +#ifndef find_next_zero_bit > +/** > + * find_next_zero_bit - find the next cleared bit in a memory region > + * @addr: The address to base the search on > + * @offset: The bitnumber to start searching at > + * @size: The bitmap size in bits > + */ > +extern unsigned long find_next_zero_bit(const unsigned long *addr, > + unsigned long size, > + unsigned long offset); > +#endif > + > +#ifndef find_first_bit > +/** > + * find_first_bit - find the first set bit in a memory region > + * @addr: The address to start the search at > + * @size: The maximum size to search > + * > + * Returns the bit number of the first set bit. > + */ > +extern unsigned long find_first_bit(const unsigned long *addr, > + unsigned long size); > +#endif > + > +#ifndef find_first_zero_bit > +/** > + * find_first_zero_bit - find the first cleared bit in a memory > region > + * @addr: The address to start the search at > + * @size: The maximum size to search > + * > + * Returns the bit number of the first cleared bit. > + */ > +extern unsigned long find_first_zero_bit(const unsigned long *addr, > + unsigned long size); > +#endif > + > #if BITS_PER_LONG == 64 > # define fls64 flsl > # define ffs64 ffsl > diff --git a/xen/lib/Makefile b/xen/lib/Makefile > index 2d9ebb945f..e63798e1d4 100644 > --- 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-y += find-next-bit.o > lib-y += list-sort.o > lib-y += memchr.o > lib-y += memchr_inv.o > diff --git a/xen/arch/arm/arm64/lib/find_next_bit.c b/xen/lib/find- > next-bit.c > similarity index 100% > rename from xen/arch/arm/arm64/lib/find_next_bit.c > rename to xen/lib/find-next-bit.c
Hi Oleksii, On 2/20/24 9:20 AM, Oleksii wrote: > Hi Shawn, > > Could you please take a look at the patch and PPC-related changes ( > xen/arch/ppc/include/asm/bitops.h )? > Hi Oleksii, Sorry for the delay. This all looks good to me: Acked-by: Shawn Anastasio <sanastasio@raptorengineering.com> > Thanks in advance. > > ~ Oleksii Thanks, Shawn
Hi Oleksii, On 09/02/2024 17:58, Oleksii Kurochko wrote: > find-next-bit.c is common for Arm64, PPC and RISCV64, > so it is moved to xen/lib. > > PPC has been transitioned to generic functions from find-next-bit.c > since it now shares the same implementation as the PPC-specific code. > > The MISRA exclude list has been updated to verify > lib/find-next-bit.c instead of Arm's find_next_bit.c, > as Arm's find_next_bit.c has been relocated to xen/lib/. > > Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in > Xen and being removed from the Linux kernel [1], it could theoretically > prove useful for Xen. This is because the Linux kernel transitioned > Arm to the generic version of find_first_bit() and > find_first_zero_bit() due to improvements [1] in both performance > and .text size. > It would be prudent to investigate whether [1] is applicable to Xen > as well and, if so, implement the necessary changes in a separate patch. > > [1] https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ > > Suggested-by: Jan Beulich <jbeulich@suse.com> > Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> This is now committed. Cheers,
diff --git a/docs/misra/exclude-list.json b/docs/misra/exclude-list.json index 7971d0e70f..b28174d0eb 100644 --- a/docs/misra/exclude-list.json +++ b/docs/misra/exclude-list.json @@ -13,10 +13,6 @@ "rel_path": "arch/arm/arm64/insn.c", "comment": "Imported on Linux, ignore for now" }, - { - "rel_path": "arch/arm/arm64/lib/find_next_bit.c", - "comment": "Imported from Linux, ignore for now" - }, { "rel_path": "arch/x86/acpi/boot.c", "comment": "Imported from Linux, ignore for now" @@ -221,6 +217,10 @@ "rel_path": "include/xen/decompress.h", "comment": "Imported from Linux, ignore for now" }, + { + "rel_path": "lib/find-next-bit.c", + "comment": "Imported from Linux, ignore for now" + }, { "rel_path": "lib/list-sort.c", "comment": "Imported from Linux, ignore for now" diff --git a/xen/arch/arm/arm64/lib/Makefile b/xen/arch/arm/arm64/lib/Makefile index 1b9c7a95e6..66cfac435a 100644 --- a/xen/arch/arm/arm64/lib/Makefile +++ b/xen/arch/arm/arm64/lib/Makefile @@ -1,4 +1,4 @@ obj-y += memcpy.o memcmp.o memmove.o memset.o memchr.o obj-y += clear_page.o -obj-y += bitops.o find_next_bit.o +obj-y += bitops.o obj-y += strchr.o strcmp.o strlen.o strncmp.o strnlen.o strrchr.o diff --git a/xen/arch/arm/include/asm/arm64/bitops.h b/xen/arch/arm/include/asm/arm64/bitops.h index d85a49bca4..0efde29068 100644 --- a/xen/arch/arm/include/asm/arm64/bitops.h +++ b/xen/arch/arm/include/asm/arm64/bitops.h @@ -36,57 +36,13 @@ static inline int flsl(unsigned long x) /* Based on linux/include/asm-generic/bitops/find.h */ -#ifndef find_next_bit -/** - * find_next_bit - find the next set bit in a memory region - * @addr: The address to base the search on - * @offset: The bitnumber to start searching at - * @size: The bitmap size in bits - */ -extern unsigned long find_next_bit(const unsigned long *addr, unsigned long - size, unsigned long offset); -#endif - -#ifndef find_next_zero_bit -/** - * find_next_zero_bit - find the next cleared bit in a memory region - * @addr: The address to base the search on - * @offset: The bitnumber to start searching at - * @size: The bitmap size in bits - */ -extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned - long size, unsigned long offset); -#endif - -#ifdef CONFIG_GENERIC_FIND_FIRST_BIT - -/** - * find_first_bit - find the first set bit in a memory region - * @addr: The address to start the search at - * @size: The maximum size to search - * - * Returns the bit number of the first set bit. - */ -extern unsigned long find_first_bit(const unsigned long *addr, - unsigned long size); - -/** - * find_first_zero_bit - find the first cleared bit in a memory region - * @addr: The address to start the search at - * @size: The maximum size to search - * - * Returns the bit number of the first cleared bit. - */ -extern unsigned long find_first_zero_bit(const unsigned long *addr, - unsigned long size); -#else /* CONFIG_GENERIC_FIND_FIRST_BIT */ +#ifndef CONFIG_GENERIC_FIND_FIRST_BIT #define find_first_bit(addr, size) find_next_bit((addr), (size), 0) #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0) #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ - #endif /* _ARM_ARM64_BITOPS_H */ /* * Local variables: diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h index 5e7f36c21d..5820b9ce7b 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -217,119 +217,4 @@ static always_inline unsigned long __ffs(unsigned long word) */ #define find_first_set_bit(x) (ffsl(x) - 1) -/* - * Find the first set bit in a memory region. - */ -static inline 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); -} - -static inline unsigned long find_next_bit(const unsigned long *addr, - unsigned long size, - unsigned long offset) -{ - const unsigned long *p = addr + BITOP_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); -} - -/* - * This implementation of find_{first,next}_zero_bit was stolen from - * Linus' asm-alpha/bitops.h. - */ -static inline unsigned long find_next_zero_bit(const unsigned long *addr, - unsigned long size, - unsigned long offset) -{ - const unsigned long *p = addr + BITOP_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); -} - #endif /* _ASM_PPC_BITOPS_H */ diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 2cb7892bcc..e3c5a4ccf3 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -105,6 +105,54 @@ static inline int generic_flsl(unsigned long x) */ #include <asm/bitops.h> +#ifndef find_next_bit +/** + * find_next_bit - find the next set bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The bitmap size in bits + */ +extern unsigned long find_next_bit(const unsigned long *addr, + unsigned long size, + unsigned long offset); +#endif + +#ifndef find_next_zero_bit +/** + * find_next_zero_bit - find the next cleared bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The bitmap size in bits + */ +extern unsigned long find_next_zero_bit(const unsigned long *addr, + unsigned long size, + unsigned long offset); +#endif + +#ifndef find_first_bit +/** + * find_first_bit - find the first set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit. + */ +extern unsigned long find_first_bit(const unsigned long *addr, + unsigned long size); +#endif + +#ifndef find_first_zero_bit +/** + * find_first_zero_bit - find the first cleared bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first cleared bit. + */ +extern unsigned long find_first_zero_bit(const unsigned long *addr, + unsigned long size); +#endif + #if BITS_PER_LONG == 64 # define fls64 flsl # define ffs64 ffsl diff --git a/xen/lib/Makefile b/xen/lib/Makefile index 2d9ebb945f..e63798e1d4 100644 --- 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-y += find-next-bit.o lib-y += list-sort.o lib-y += memchr.o lib-y += memchr_inv.o diff --git a/xen/arch/arm/arm64/lib/find_next_bit.c b/xen/lib/find-next-bit.c similarity index 100% rename from xen/arch/arm/arm64/lib/find_next_bit.c rename to xen/lib/find-next-bit.c
find-next-bit.c is common for Arm64, PPC and RISCV64, so it is moved to xen/lib. PPC has been transitioned to generic functions from find-next-bit.c since it now shares the same implementation as the PPC-specific code. The MISRA exclude list has been updated to verify lib/find-next-bit.c instead of Arm's find_next_bit.c, as Arm's find_next_bit.c has been relocated to xen/lib/. Despite CONFIG_GENERIC_FIND_FIRST_BIT not currently being used in Xen and being removed from the Linux kernel [1], it could theoretically prove useful for Xen. This is because the Linux kernel transitioned Arm to the generic version of find_first_bit() and find_first_zero_bit() due to improvements [1] in both performance and .text size. It would be prudent to investigate whether [1] is applicable to Xen as well and, if so, implement the necessary changes in a separate patch. [1] https://lore.kernel.org/linux-arch/20211005054059.475634-5-yury.norov@gmail.com/ Suggested-by: Jan Beulich <jbeulich@suse.com> Signed-off-by: Oleksii Kurochko <oleksii.kurochko@gmail.com> --- docs/misra/exclude-list.json | 8 +- xen/arch/arm/arm64/lib/Makefile | 2 +- xen/arch/arm/include/asm/arm64/bitops.h | 46 +------ xen/arch/ppc/include/asm/bitops.h | 115 ------------------ xen/include/xen/bitops.h | 48 ++++++++ xen/lib/Makefile | 1 + .../find_next_bit.c => lib/find-next-bit.c} | 0 7 files changed, 55 insertions(+), 165 deletions(-) rename xen/{arch/arm/arm64/lib/find_next_bit.c => lib/find-next-bit.c} (100%)