From: Simon Glass <simon.glass@canonical.com> Add lib/find_bit.c and include/linux/find.h from Linux v6.19, trimmed to include only the functions needed for ext4l: find_first_bit(), find_first_zero_bit(), find_next_bit(), find_next_zero_bit() and find_last_bit() The following items are removed from the Linux originals: - find.h: _and_bit, _andnot_bit, _or_bit, _nth_bit variants, wrap functions, clump8 functions, big-endian support, most for_each_... macros - find_bit.c: Corresponding implementations, random.h include Add wrapper functions matching sandbox's asm/bitops.h declarations (int return type, void* addr) that call the _find_* implementations. Build find_bit.o only for sandbox for now. Co-developed-by: Claude Opus 4.5 <noreply@anthropic.com> Signed-off-by: Simon Glass <simon.glass@canonical.com> --- include/linux/find.h | 176 +++++++++++++++++++++++++++++++++++++++++++ lib/Makefile | 1 + lib/find_bit.c | 142 ++++++++++++++++++++++++++++++++++ 3 files changed, 319 insertions(+) create mode 100644 include/linux/find.h create mode 100644 lib/find_bit.c diff --git a/include/linux/find.h b/include/linux/find.h new file mode 100644 index 00000000000..117d9015c57 --- /dev/null +++ b/include/linux/find.h @@ -0,0 +1,176 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_FIND_H_ +#define __LINUX_FIND_H_ + +#include <linux/bitops.h> + +unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits, + unsigned long start); +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, + unsigned long start); +extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); +extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); +extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); + +#ifndef find_next_bit +/** + * find_next_bit - find the next set bit in a memory region + * @addr: The address to base the search on + * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at + * + * Returns the bit number for the next set bit + * If no bits are set, returns @size. + */ +static __always_inline +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + if (small_const_nbits(size)) { + unsigned long val; + + if (unlikely(offset >= size)) + return size; + + val = *addr & GENMASK(size - 1, offset); + return val ? __ffs(val) : size; + } + + return _find_next_bit(addr, size, 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 + * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at + * + * Returns the bit number of the next zero bit + * If no bits are zero, returns @size. + */ +static __always_inline +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + if (small_const_nbits(size)) { + unsigned long val; + + if (unlikely(offset >= size)) + return size; + + val = *addr | ~GENMASK(size - 1, offset); + return val == ~0UL ? size : ffz(val); + } + + return _find_next_zero_bit(addr, size, 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 number of bits to search + * + * Returns the bit number of the first set bit. + * If no bits are set, returns @size. + */ +static __always_inline +unsigned long find_first_bit(const unsigned long *addr, unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val = *addr & GENMASK(size - 1, 0); + + return val ? __ffs(val) : size; + } + + return _find_first_bit(addr, 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 number of bits to search + * + * Returns the bit number of the first cleared bit. + * If no bits are zero, returns @size. + */ +static __always_inline +unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val = *addr | ~GENMASK(size - 1, 0); + + return val == ~0UL ? size : ffz(val); + } + + return _find_first_zero_bit(addr, size); +} +#endif + +#ifndef find_last_bit +/** + * find_last_bit - find the last set bit in a memory region + * @addr: The address to start the search at + * @size: The number of bits to search + * + * Returns the bit number of the last set bit, or size. + */ +static __always_inline +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val = *addr & GENMASK(size - 1, 0); + + return val ? __fls(val) : size; + } + + return _find_last_bit(addr, size); +} +#endif + +#if defined(__LITTLE_ENDIAN) + +static __always_inline +unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset) +{ + return find_next_zero_bit(addr, size, offset); +} + +static __always_inline +unsigned long find_next_bit_le(const void *addr, unsigned long size, unsigned long offset) +{ + return find_next_bit(addr, size, offset); +} + +static __always_inline +unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) +{ + return find_first_zero_bit(addr, size); +} + +#else +#error "Please fix <asm/byteorder.h>" +#endif + +#define for_each_set_bit(bit, addr, size) \ + for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) + +/* same as for_each_set_bit() but use bit as value to start with */ +#define for_each_set_bit_from(bit, addr, size) \ + for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) + +#define for_each_clear_bit(bit, addr, size) \ + for ((bit) = 0; \ + (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); \ + (bit)++) + +/* same as for_each_clear_bit() but use bit as value to start with */ +#define for_each_clear_bit_from(bit, addr, size) \ + for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++) + +#endif /*__LINUX_FIND_H_ */ diff --git a/lib/Makefile b/lib/Makefile index 01b967d46b7..3890a827d1c 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -58,6 +58,7 @@ obj-$(CONFIG_PHYSMEM) += physmem.o obj-y += rc4.o obj-$(CONFIG_RBTREE) += rbtree.o obj-$(CONFIG_BITREVERSE) += bitrev.o +obj-$(CONFIG_SANDBOX) += find_bit.o obj-y += list_sort.o endif diff --git a/lib/find_bit.c b/lib/find_bit.c new file mode 100644 index 00000000000..762c5448d84 --- /dev/null +++ b/lib/find_bit.c @@ -0,0 +1,142 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* bit search implementation + * + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * + * Copyright (C) 2008 IBM Corporation + * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> + * (Inspired by David Howell's find_next_bit implementation) + * + * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease + * size and improve performance, 2015. + */ + +#include <asm/byteorder.h> +#include <linux/bitops.h> +#include <linux/bitmap.h> +#include <linux/export.h> + +/* + * Common helper for find_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) + * @MUNGE: The expression that post-processes a word containing found bit (may be empty) + * @size: The bitmap size in bits + */ +#define FIND_FIRST_BIT(FETCH, MUNGE, size) \ +({ \ + unsigned long idx, val, sz = (size); \ + \ + for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ + val = (FETCH); \ + if (val) { \ + sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ + break; \ + } \ + } \ + \ + sz; \ +}) + +/* + * Common helper for find_next_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) + * @MUNGE: The expression that post-processes a word containing found bit (may be empty) + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + */ +#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ +({ \ + unsigned long mask, idx, tmp, sz = (size), __start = (start); \ + \ + if (unlikely(__start >= sz)) \ + goto out; \ + \ + mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ + idx = __start / BITS_PER_LONG; \ + \ + for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ + if ((idx + 1) * BITS_PER_LONG >= sz) \ + goto out; \ + idx++; \ + } \ + \ + sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ +out: \ + sz; \ +}) + +#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) +{ + return FIND_FIRST_BIT(addr[idx], /* nop */, size); +} +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) +{ + return FIND_FIRST_BIT(~addr[idx], /* nop */, size); +} +EXPORT_SYMBOL(_find_first_zero_bit); +#endif + +#ifndef find_next_bit +unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_bit); +#endif + +#ifndef find_next_zero_bit +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, + unsigned long start) +{ + return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_zero_bit); +#endif + +#ifndef find_last_bit +unsigned long _find_last_bit(const unsigned long *addr, unsigned long size) +{ + if (size) { + unsigned long val = BITMAP_LAST_WORD_MASK(size); + unsigned long idx = (size-1) / BITS_PER_LONG; + + do { + val &= addr[idx]; + if (val) + return idx * BITS_PER_LONG + __fls(val); + + val = ~0ul; + } while (idx--); + } + return size; +} +EXPORT_SYMBOL(_find_last_bit); +#endif + +/* + * Wrapper functions matching sandbox's asm/bitops.h declarations. + * These provide the expected function signatures for sandbox platform. + */ +int find_first_zero_bit(void *addr, unsigned int size) +{ + return _find_first_zero_bit(addr, size); +} +EXPORT_SYMBOL(find_first_zero_bit); + +int find_next_zero_bit(void *addr, int size, int offset) +{ + return _find_next_zero_bit(addr, size, offset); +} +EXPORT_SYMBOL(find_next_zero_bit); -- 2.43.0