From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from lists.ozlabs.org (lists.ozlabs.org [112.213.38.117]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 680B8C00528 for ; Wed, 2 Aug 2023 09:18:09 +0000 (UTC) Received: from boromir.ozlabs.org (localhost [IPv6:::1]) by lists.ozlabs.org (Postfix) with ESMTP id 4RG5xC6BdQz3bv0 for ; Wed, 2 Aug 2023 19:18:07 +1000 (AEST) Authentication-Results: lists.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=linux.alibaba.com (client-ip=115.124.30.112; helo=out30-112.freemail.mail.aliyun.com; envelope-from=jefflexu@linux.alibaba.com; receiver=lists.ozlabs.org) Received: from out30-112.freemail.mail.aliyun.com (out30-112.freemail.mail.aliyun.com [115.124.30.112]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 4RG5x40MZ0z2xqH for ; Wed, 2 Aug 2023 19:17:58 +1000 (AEST) X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R181e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=ay29a033018045176;MF=jefflexu@linux.alibaba.com;NM=1;PH=DS;RN=2;SR=0;TI=SMTPD_---0VouSZH6_1690967872; Received: from localhost(mailfrom:jefflexu@linux.alibaba.com fp:SMTPD_---0VouSZH6_1690967872) by smtp.aliyun-inc.com; Wed, 02 Aug 2023 17:17:53 +0800 From: Jingbo Xu To: xiang@kernel.org, linux-erofs@lists.ozlabs.org Subject: [PATCH v2 03/16] erofs-utils: lib: add bitops library Date: Wed, 2 Aug 2023 17:17:37 +0800 Message-Id: <20230802091750.74181-3-jefflexu@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.6.gb485710b In-Reply-To: <20230802091750.74181-1-jefflexu@linux.alibaba.com> References: <20230802091750.74181-1-jefflexu@linux.alibaba.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-BeenThere: linux-erofs@lists.ozlabs.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Development of Linux EROFS file system List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: linux-erofs-bounces+linux-erofs=archiver.kernel.org@lists.ozlabs.org Sender: "Linux-erofs" Introduce following bitmap helpers: DECLARE_BITMAP test_bit __set_bit __clear_bit find_next_bit find_next_zero_bit Signed-off-by: Jingbo Xu --- include/erofs/bitops.h | 43 ++++++++++++++++++++++++ include/erofs/defs.h | 75 ++++++++++++++++++++++++++++++++++++++++++ lib/Makefile.am | 3 +- lib/bitops.c | 58 ++++++++++++++++++++++++++++++++ 4 files changed, 178 insertions(+), 1 deletion(-) create mode 100644 include/erofs/bitops.h create mode 100644 lib/bitops.c diff --git a/include/erofs/bitops.h b/include/erofs/bitops.h new file mode 100644 index 0000000..985195d --- /dev/null +++ b/include/erofs/bitops.h @@ -0,0 +1,43 @@ +/* SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 */ +#ifndef __EROFS_BITOPS_H +#define __EROFS_BITOPS_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include "defs.h" + +static inline void __set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p |= mask; +} + +static inline void __clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p &= ~mask; +} + +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); +} + +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset); + +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/include/erofs/defs.h b/include/erofs/defs.h index 20f9741..c6bbbb5 100644 --- a/include/erofs/defs.h +++ b/include/erofs/defs.h @@ -343,6 +343,81 @@ unsigned long __roundup_pow_of_two(unsigned long n) #define lstat64 lstat #endif +#define DECLARE_BITMAP(name,bits) \ + unsigned long name[BITS_TO_LONGS(bits)] + +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) + +/** + * __swab32 - return a byteswapped 32-bit value + * @x: value to byteswap + */ +#define __swab32(x) ((__u32)( \ + (((__u32)(x) & (__u32)0x000000ffUL) << 24) | \ + (((__u32)(x) & (__u32)0x0000ff00UL) << 8) | \ + (((__u32)(x) & (__u32)0x00ff0000UL) >> 8) | \ + (((__u32)(x) & (__u32)0xff000000UL) >> 24))) + +/** + * __swab64 - return a byteswapped 64-bit value + * @x: value to byteswap + */ +#define __swab64(x) ((__u64)( \ + (((__u64)(x) & (__u64)0x00000000000000ffULL) << 56) | \ + (((__u64)(x) & (__u64)0x000000000000ff00ULL) << 40) | \ + (((__u64)(x) & (__u64)0x0000000000ff0000ULL) << 24) | \ + (((__u64)(x) & (__u64)0x00000000ff000000ULL) << 8) | \ + (((__u64)(x) & (__u64)0x000000ff00000000ULL) >> 8) | \ + (((__u64)(x) & (__u64)0x0000ff0000000000ULL) >> 24) | \ + (((__u64)(x) & (__u64)0x00ff000000000000ULL) >> 40) | \ + (((__u64)(x) & (__u64)0xff00000000000000ULL) >> 56))) + +static __always_inline unsigned long __swab(const unsigned long y) +{ +#if BITS_PER_LONG == 64 + return __swab64(y); +#else /* BITS_PER_LONG == 32 */ + return __swab32(y); +#endif +} + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static __always_inline unsigned long __ffs(unsigned long word) +{ + int num = 0; + +#if BITS_PER_LONG == 64 + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } +#endif + if ((word & 0xffff) == 0) { + num += 16; + word >>= 16; + } + if ((word & 0xff) == 0) { + num += 8; + word >>= 8; + } + if ((word & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) + num += 1; + return num; +} + #ifdef __cplusplus } #endif diff --git a/lib/Makefile.am b/lib/Makefile.am index 7a5dc03..08e986e 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -19,6 +19,7 @@ noinst_HEADERS = $(top_srcdir)/include/erofs_fs.h \ $(top_srcdir)/include/erofs/io.h \ $(top_srcdir)/include/erofs/list.h \ $(top_srcdir)/include/erofs/print.h \ + $(top_srcdir)/include/erofs/bitops.h \ $(top_srcdir)/include/erofs/tar.h \ $(top_srcdir)/include/erofs/trace.h \ $(top_srcdir)/include/erofs/xattr.h \ @@ -31,7 +32,7 @@ liberofs_la_SOURCES = config.c io.c cache.c super.c inode.c xattr.c exclude.c \ namei.c data.c compress.c compressor.c zmap.c decompress.c \ compress_hints.c hashmap.c sha256.c blobchunk.c dir.c \ fragments.c rb_tree.c dedupe.c uuid_unparse.c uuid.c tar.c \ - block_list.c + block_list.c bitops.c liberofs_la_CFLAGS = -Wall ${libuuid_CFLAGS} -I$(top_srcdir)/include if ENABLE_LZ4 diff --git a/lib/bitops.c b/lib/bitops.c new file mode 100644 index 0000000..6ce521a --- /dev/null +++ b/lib/bitops.c @@ -0,0 +1,58 @@ +// SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 +#include +#include +#include "erofs/internal.h" + +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) + +static unsigned long _find_next_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long nbits, + unsigned long start, unsigned long invert, unsigned long le) +{ + unsigned long tmp, mask; + + if (start >= nbits) + return nbits; + + tmp = addr1[start / BITS_PER_LONG]; + if (addr2) + tmp &= addr2[start / BITS_PER_LONG]; + tmp ^= invert; + + /* Handle 1st word. */ + mask = BITMAP_FIRST_WORD_MASK(start); + if (le) + mask = __swab(mask); + + tmp &= mask; + + start = round_down(start, BITS_PER_LONG); + + while (!tmp) { + start += BITS_PER_LONG; + if (start >= nbits) + return nbits; + + tmp = addr1[start / BITS_PER_LONG]; + if (addr2) + tmp &= addr2[start / BITS_PER_LONG]; + tmp ^= invert; + } + + if (le) + tmp = __swab(tmp); + + return min(start + __ffs(tmp), nbits); +} + +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + return _find_next_bit(addr, NULL, size, offset, 0UL, 0); +} + +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); +} -- 2.19.1.6.gb485710b