From patchwork Tue Dec 30 23:41:16 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Simon Glass X-Patchwork-Id: 1127 Return-Path: X-Original-To: u-boot-concept@u-boot.org Delivered-To: u-boot-concept@u-boot.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=u-boot.org; s=default; t=1767138281; bh=8mDs2jyTtWzGrvzFWAhmGKxBW9KhsDOtZrrdgxvaN4U=; h=From:To:Date:In-Reply-To:References:CC:Subject:List-Id: List-Archive:List-Help:List-Owner:List-Post:List-Subscribe: List-Unsubscribe:From; b=KSKwSeLa7ZFapHTpsi0NSkYN73uj+ZjSB1cYs9l5AxN3r7hvscZdw4Okns+etLJjh XBjtw93be+7O7qax1ZIUr8UFXiNbSMzX/cB73s5tgnB7RthIFa4C00XJfKhJIbdFG7 tZhkLtVnC7On0jHeMEcku4mCEbIUCPCnoaNR+JUjqL3DN+r8uzwrdkhm+zehfzlPyI n3U2Ik1h6gJ+f07+S5jy5g8r8bspR8ROY0e1sN4wiH/orTEQkCPMOsR3wHFDEg9YbG aCeP/RullWkycvbbPp9P1fp8c6PIDdHYJQ37yz9SDmVMHvJaRSbjvi2h15lJV6gEcu xTrjHWnYv+LgA== Received: from localhost (localhost [127.0.0.1]) by mail.u-boot.org (Postfix) with ESMTP id 8899B64E2A for ; Tue, 30 Dec 2025 16:44:41 -0700 (MST) X-Virus-Scanned: Debian amavis at Received: from mail.u-boot.org ([127.0.0.1]) by localhost (mail.u-boot.org [127.0.0.1]) (amavis, port 10024) with ESMTP id NPJQgBKewW21 for ; Tue, 30 Dec 2025 16:44:41 -0700 (MST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=u-boot.org; s=default; t=1767138280; bh=8mDs2jyTtWzGrvzFWAhmGKxBW9KhsDOtZrrdgxvaN4U=; h=From:To:Date:In-Reply-To:References:CC:Subject:List-Id: List-Archive:List-Help:List-Owner:List-Post:List-Subscribe: List-Unsubscribe:From; b=kpWTFDsCyFGJuINCg79JhrAUmuN6TM4NinmneC6yulINYOG7u5c+ECOeGFK2AKG3n S+N4jcZ6xFNs3dJ6ycocJ4sDZd+EV+5D9lqaAjFNVVqj6BVIUvkH32B8phJknypi/y YFVHfEocq+sMU+wXdrjGZR0xUqpyqiG6aK24owZtyT4j2RojzCQx+bHKyhm1SL2BOl 3f95dYIthkXtnqcjzomsz0orxA/7CdlQLawgQ11qIjpKJzslYqPDCWm8mjtKI3EhJJ F0QaCvhUkc+d5drs31pWQ7HY4+GZUU+gPlpIyX3zgnFiu+J9Me1sJmFkSeFc6dWiVq pvyiTjhJAt7BQ== Received: from mail.u-boot.org (localhost [127.0.0.1]) by mail.u-boot.org (Postfix) with ESMTP id 8F5B268C57 for ; Tue, 30 Dec 2025 16:44:40 -0700 (MST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=u-boot.org; s=default; t=1767138279; bh=nVkUVPV8+5eqWqeO4IW/c2UkmacjwYwDR+BqPnB49fM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=iuWZXY2puPYr/tlGk7g2OLQ6CayIxzUSYGqeqvVB2vQQx1i2XN5U6te092RZvYlc6 vmoBLwfQSE4QZlCBAgiuWF62H8ZjtqOzwOlV1T8a0g7J6cAU9vWthcSdgB5Hav1dI0 rYzresdhGu4Wqz/pmNeH9fyFJLsXAJKZBwSQmZIzcOff6yhlZ4tlIoMmjbLrQ6B6ZA BsredPUvJJ+49uiv4OaKXE8fwKHur/i4XRNrQ4NeTRKJIQu6g9yrcexMsfTR3VmTba JPXwwYp+i8ZRFqqrOyA8cAVn3UUf6sOpE4Aq6zzg7yWEY7DQBgIaP+l9idqiGWE0Oo 5D5aLK6NkGD6Q== Received: from localhost (localhost [127.0.0.1]) by mail.u-boot.org (Postfix) with ESMTP id 2649668C58; Tue, 30 Dec 2025 16:44:39 -0700 (MST) X-Virus-Scanned: Debian amavis at Received: from mail.u-boot.org ([127.0.0.1]) by localhost (mail.u-boot.org [127.0.0.1]) (amavis, port 10026) with ESMTP id 0aM4eeoVoB1k; Tue, 30 Dec 2025 16:44:39 -0700 (MST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=u-boot.org; s=default; t=1767138276; bh=Iw0HHFgQaBMHVsjYLbovzm274otvH/tK6rjiUBOrnVI=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=Ypb+ZkX8Mnk20toC+whfQIHPnivugzro+Mu5URO/JPYi3SQJmjtIX7o8F8lx4nJou PSX0Ew+Mi12r/LnejmYpYXPW49rRvc8oHwrsxfk3EqKnxpsSCcnjfOpy0iAeYzspY0 ijaTZv2EQ2k/bx35DeKFXSb5lm93MjnAmNt/M6o6EQSgR0osecqsCJDI+TUt3eCZ1e ZpASlWh1BDXCKHjhD5Rr18VMYugVLX1VERE5JfyJ9NrYFjsQ6wrE9kgXFOg5OtP7UQ 7SVDtQiUs4EmbDuGhpdihPt/mu3n2VLCiRlBckIh4lyLxIse/TldGQwWvBuvr6lB1H 8i+bTO5CL/9ew== Received: from u-boot.org (unknown [73.34.74.121]) by mail.u-boot.org (Postfix) with ESMTPSA id 3CB2764E2A; Tue, 30 Dec 2025 16:44:36 -0700 (MST) From: Simon Glass To: U-Boot Concept Date: Tue, 30 Dec 2025 16:41:16 -0700 Message-ID: <20251230234134.906477-5-sjg@u-boot.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20251230234134.906477-1-sjg@u-boot.org> References: <20251230234134.906477-1-sjg@u-boot.org> MIME-Version: 1.0 Message-ID-Hash: PTKG7DG6ENH5FG56U4P5ZLCTL3DBN26R X-Message-ID-Hash: PTKG7DG6ENH5FG56U4P5ZLCTL3DBN26R X-MailFrom: sjg@u-boot.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; loop; banned-address; emergency; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: Simon Glass , "Claude Opus 4 . 5" X-Mailman-Version: 3.3.10 Precedence: list Subject: [Concept] [PATCH 04/15] lib: linux: Add find_bit from Linux List-Id: Discussion and patches related to U-Boot Concept Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: From: Simon Glass 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 Signed-off-by: Simon Glass --- 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 + +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 " +#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 + * (Inspired by David Howell's find_next_bit implementation) + * + * Rewritten by Yury Norov to decrease + * size and improve performance, 2015. + */ + +#include +#include +#include +#include + +/* + * 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);