find_fisrt_{zero_}bit are too heavy for bitmap_{full,empty}. We don't
need to calculate and compare the position of bitmap. This set of patch
instroduces lightweight api and replaces the heavy one.
Jia He (3):
linux/bitmap: Move 2 mask macro from bitmap.h to bitops.h
lib: Introduce 2 find bit api: all_is_bit_{one,zero}
linux/bitmap: Replace find_fisrt_{zero_}bit with the new lightweight api
include/asm-generic/bitops/find.h | 3 +++
include/linux/bitmap.h | 7 ++----
include/linux/bitops.h | 4 ++++
lib/find_bit.c | 50 +++++++++++++++++++++++++++++++++++++++
4 files changed, 59 insertions(+), 5 deletions(-)
--
2.5.0
This patch moves the mask macro to bitops.h and then the new introduced
api in find_bit.c can use it.
Signed-off-by: Jia He <[email protected]>
---
include/linux/bitmap.h | 3 ---
include/linux/bitops.h | 4 ++++
2 files changed, 4 insertions(+), 3 deletions(-)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 9653fdb..15524f6 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -172,9 +172,6 @@ extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int
extern int bitmap_print_to_pagebuf(bool list, char *buf,
const unsigned long *maskp, int nmaskbits);
-#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
-#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
-
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 2b8ed12..b881028 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -24,6 +24,10 @@
#define GENMASK_ULL(h, l) \
(((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LONG_LONG - 1 - (h))))
+/* For bitmap ops*/
+#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
+#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
+
extern unsigned int __sw_hweight8(unsigned int w);
extern unsigned int __sw_hweight16(unsigned int w);
extern unsigned int __sw_hweight32(unsigned int w);
--
2.5.0
This patch introduces 2 lightweight bit api.
all_bit_is_zero return 1 if the bit string is all zero.
The addr is the start address, the size is the bit size of the bit string.
all_bit_is_one is the opposite.
Signed-off-by: Jia He <[email protected]>
---
lib/find_bit.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 50 insertions(+)
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 18072ea..1d56d8d 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -131,6 +131,56 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
EXPORT_SYMBOL(find_last_bit);
#endif
+#ifndef all_bit_is_zero
+/*
+ * return val: 1 means all bit is zero
+ */
+unsigned int all_bit_is_zero(const unsigned long *addr, unsigned size)
+{
+ unsigned long idx;
+ unsigned long mask = size;
+
+ if (unlikely(size == 0))
+ return 1;
+
+ if (size > BITS_PER_LONG) {
+ for (idx = 0; idx * BITS_PER_LONG < size; idx++)
+ if (addr[idx])
+ return 0;
+
+ mask = size - (idx - 1) * BITS_PER_LONG;
+ }
+
+ return !(*addr & BITMAP_LAST_WORD_MASK(mask));
+}
+EXPORT_SYMBOL(all_bit_is_zero);
+#endif
+
+#ifndef all_bit_is_one
+/*
+ * return val: 1 means all bit is one
+ */
+unsigned int all_bit_is_one(const unsigned long *addr, unsigned size)
+{
+ unsigned long idx;
+ unsigned long mask = size;
+
+ if (unlikely(size == 0))
+ return 1;
+
+ if (size > BITS_PER_LONG) {
+ for (idx = 0; idx * BITS_PER_LONG < size; idx++)
+ if (~addr[idx])
+ return 0;
+
+ mask = size - (idx - 1) * BITS_PER_LONG;
+ }
+
+ return !(~(*addr) & BITMAP_LAST_WORD_MASK(mask));
+}
+EXPORT_SYMBOL(all_bit_is_one);
+#endif
+
#ifdef __BIG_ENDIAN
/* include/linux/byteorder does not support "unsigned long" type */
--
2.5.0
This is to replace find_fisrt_{zero_}bit with the new lightweight api
all_bit_is_{one,zero} in bitmap_{full,empty}
Signed-off-by: Jia He <[email protected]>
---
include/asm-generic/bitops/find.h | 3 +++
include/linux/bitmap.h | 4 ++--
2 files changed, 5 insertions(+), 2 deletions(-)
diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h
index 998d4d5..1ec1d45 100644
--- a/include/asm-generic/bitops/find.h
+++ b/include/asm-generic/bitops/find.h
@@ -59,4 +59,7 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
+extern unsigned int all_bit_is_one(const unsigned long *addr, unsigned size);
+extern unsigned int all_bit_is_zero(const unsigned long *addr, unsigned size);
+
#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 15524f6..8877a68 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -281,7 +281,7 @@ static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
if (small_const_nbits(nbits))
return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
- return find_first_bit(src, nbits) == nbits;
+ return all_bit_is_zero(src, nbits);
}
static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
@@ -289,7 +289,7 @@ static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
if (small_const_nbits(nbits))
return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
- return find_first_zero_bit(src, nbits) == nbits;
+ return all_bit_is_one(src, nbits);
}
static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
--
2.5.0
Hi Jia,
[auto build test ERROR on: v4.4-rc1]
[also build test ERROR on: next-20151118]
url: https://github.com/0day-ci/linux/commits/Jia-He/Improve-bitmap_empty-and-bitmap_full/20151119-103554
config: m68k-allyesconfig (attached as .config)
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=m68k
All errors (new ones prefixed by >>):
kernel/time/Kconfig:155:warning: range is invalid
warning: (USB_OTG_FSM && FSL_USB2_OTG && USB_MV_OTG) selects USB_OTG which has unmet direct dependencies (USB_SUPPORT && USB && PM)
warning: (SINGLE_MEMORY_CHUNK) selects NEED_MULTIPLE_NODES which has unmet direct dependencies (DISCONTIGMEM || NUMA)
warning: (PREEMPT && DEBUG_ATOMIC_SLEEP) selects PREEMPT_COUNT which has unmet direct dependencies (COLDFIRE)
warning: (USB_OTG_FSM && FSL_USB2_OTG && USB_MV_OTG) selects USB_OTG which has unmet direct dependencies (USB_SUPPORT && USB && PM)
warning: (SINGLE_MEMORY_CHUNK) selects NEED_MULTIPLE_NODES which has unmet direct dependencies (DISCONTIGMEM || NUMA)
warning: (PREEMPT && DEBUG_ATOMIC_SLEEP) selects PREEMPT_COUNT which has unmet direct dependencies (COLDFIRE)
In file included from include/linux/cpumask.h:11:0,
from include/linux/rcupdate.h:40,
from include/linux/rbtree.h:34,
from include/linux/sched.h:22,
from arch/m68k/kernel/asm-offsets.c:14:
include/linux/bitmap.h: In function 'bitmap_empty':
>> include/linux/bitmap.h:284:2: error: implicit declaration of function 'all_bit_is_zero' [-Werror=implicit-function-declaration]
return all_bit_is_zero(src, nbits);
^
include/linux/bitmap.h: In function 'bitmap_full':
>> include/linux/bitmap.h:292:2: error: implicit declaration of function 'all_bit_is_one' [-Werror=implicit-function-declaration]
return all_bit_is_one(src, nbits);
^
cc1: some warnings being treated as errors
make[2]: *** [arch/m68k/kernel/asm-offsets.s] Error 1
make[2]: Target '__build' not remade because of errors.
make[1]: *** [prepare0] Error 2
make[1]: Target 'prepare' not remade because of errors.
make: *** [sub-make] Error 2
vim +/all_bit_is_zero +284 include/linux/bitmap.h
278
279 static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
280 {
281 if (small_const_nbits(nbits))
282 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
283
> 284 return all_bit_is_zero(src, nbits);
285 }
286
287 static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
288 {
289 if (small_const_nbits(nbits))
290 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
291
> 292 return all_bit_is_one(src, nbits);
293 }
294
295 static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
Thanks, I only compiled and tested in x86_64, will check what's wrong in
m68k
B.R.
Justin
在 11/19/15 10:53 AM, kbuild test robot 写道:
> Hi Jia,
>
> [auto build test ERROR on: v4.4-rc1]
> [also build test ERROR on: next-20151118]
>
> url: https://github.com/0day-ci/linux/commits/Jia-He/Improve-bitmap_empty-and-bitmap_full/20151119-103554
> config: m68k-allyesconfig (attached as .config)
> reproduce:
> wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
> chmod +x ~/bin/make.cross
> # save the attached .config to linux build tree
> make.cross ARCH=m68k
>
> All errors (new ones prefixed by >>):
>
> kernel/time/Kconfig:155:warning: range is invalid
> warning: (USB_OTG_FSM && FSL_USB2_OTG && USB_MV_OTG) selects USB_OTG which has unmet direct dependencies (USB_SUPPORT && USB && PM)
> warning: (SINGLE_MEMORY_CHUNK) selects NEED_MULTIPLE_NODES which has unmet direct dependencies (DISCONTIGMEM || NUMA)
> warning: (PREEMPT && DEBUG_ATOMIC_SLEEP) selects PREEMPT_COUNT which has unmet direct dependencies (COLDFIRE)
> warning: (USB_OTG_FSM && FSL_USB2_OTG && USB_MV_OTG) selects USB_OTG which has unmet direct dependencies (USB_SUPPORT && USB && PM)
> warning: (SINGLE_MEMORY_CHUNK) selects NEED_MULTIPLE_NODES which has unmet direct dependencies (DISCONTIGMEM || NUMA)
> warning: (PREEMPT && DEBUG_ATOMIC_SLEEP) selects PREEMPT_COUNT which has unmet direct dependencies (COLDFIRE)
> In file included from include/linux/cpumask.h:11:0,
> from include/linux/rcupdate.h:40,
> from include/linux/rbtree.h:34,
> from include/linux/sched.h:22,
> from arch/m68k/kernel/asm-offsets.c:14:
> include/linux/bitmap.h: In function 'bitmap_empty':
>>> include/linux/bitmap.h:284:2: error: implicit declaration of function 'all_bit_is_zero' [-Werror=implicit-function-declaration]
> return all_bit_is_zero(src, nbits);
> ^
> include/linux/bitmap.h: In function 'bitmap_full':
>>> include/linux/bitmap.h:292:2: error: implicit declaration of function 'all_bit_is_one' [-Werror=implicit-function-declaration]
> return all_bit_is_one(src, nbits);
> ^
> cc1: some warnings being treated as errors
> make[2]: *** [arch/m68k/kernel/asm-offsets.s] Error 1
> make[2]: Target '__build' not remade because of errors.
> make[1]: *** [prepare0] Error 2
> make[1]: Target 'prepare' not remade because of errors.
> make: *** [sub-make] Error 2
>
> vim +/all_bit_is_zero +284 include/linux/bitmap.h
>
> 278
> 279 static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
> 280 {
> 281 if (small_const_nbits(nbits))
> 282 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
> 283
> > 284 return all_bit_is_zero(src, nbits);
> 285 }
> 286
> 287 static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
> 288 {
> 289 if (small_const_nbits(nbits))
> 290 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
> 291
> > 292 return all_bit_is_one(src, nbits);
> 293 }
> 294
> 295 static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
>
> ---
> 0-DAY kernel test infrastructure Open Source Technology Center
> https://lists.01.org/pipermail/kbuild-all Intel Corporation
On Thu, Nov 19, 2015 at 3:31 AM, Jia He <[email protected]> wrote:
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -131,6 +131,56 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> EXPORT_SYMBOL(find_last_bit);
> #endif
>
> +#ifndef all_bit_is_zero
> +/*
> + * return val: 1 means all bit is zero
> + */
> +unsigned int all_bit_is_zero(const unsigned long *addr, unsigned size)
> +{
> + unsigned long idx;
> + unsigned long mask = size;
> +
> + if (unlikely(size == 0))
> + return 1;
> +
> + if (size > BITS_PER_LONG) {
> + for (idx = 0; idx * BITS_PER_LONG < size; idx++)
Please move the multiplication (yes, a shift) out of the loop. Not all CPUs
have barrel shifters.
> + if (addr[idx])
> + return 0;
> +
> + mask = size - (idx - 1) * BITS_PER_LONG;
> + }
> +
> + return !(*addr & BITMAP_LAST_WORD_MASK(mask));
> +}
> +EXPORT_SYMBOL(all_bit_is_zero);
Gr{oetje,eeting}s,
Geert
--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]
In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds
On Thu, Nov 19 2015, Jia He wrote:
> This patch introduces 2 lightweight bit api.
> all_bit_is_zero return 1 if the bit string is all zero.
> The addr is the start address, the size is the bit size of the bit string.
> all_bit_is_one is the opposite.
>
> Signed-off-by: Jia He <[email protected]>
> ---
> lib/find_bit.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 50 insertions(+)
>
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 18072ea..1d56d8d 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -131,6 +131,56 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> EXPORT_SYMBOL(find_last_bit);
> #endif
>
> +#ifndef all_bit_is_zero
> +/*
> + * return val: 1 means all bit is zero
> + */
> +unsigned int all_bit_is_zero(const unsigned long *addr, unsigned
> size)
Why does it return unsigned int, not bool?
> +{
> + unsigned long idx;
> + unsigned long mask = size;
> +
> + if (unlikely(size == 0))
> + return 1;
> +
> + if (size > BITS_PER_LONG) {
> + for (idx = 0; idx * BITS_PER_LONG < size; idx++)
> + if (addr[idx])
> + return 0;
> +
> + mask = size - (idx - 1) * BITS_PER_LONG;
Uh?
> + }
> +
> + return !(*addr & BITMAP_LAST_WORD_MASK(mask));
BITMAP_LAST_WORD_MASK takes size not mask.
> +}
The whole implementation seems weird, this seems much better to me:
unsigned int all_bit_is_zero(const unsigned long *addr, unsigned size)
{
for (; size > BITS_PER_LONG; size -= BITS_PER_LONG, ++addr)
if (*addr)
return 0;
return !size || !(*addr & BITMAP_LAST_WORD_MASK(size));
}
But to be honest I’m not entirely sure this is worth the effort.
find_next_bit and find_next_zero_bit may do a little bit more work but
some architectures have specialised optimised versions which will be
lost if all_bit_is_zero and all_bit_is_one are introduced.
> +EXPORT_SYMBOL(all_bit_is_zero);
> +#endif
> +
> +#ifndef all_bit_is_one
> +/*
> + * return val: 1 means all bit is one
> + */
> +unsigned int all_bit_is_one(const unsigned long *addr, unsigned size)
> +{
> + unsigned long idx;
> + unsigned long mask = size;
> +
> + if (unlikely(size == 0))
> + return 1;
> +
> + if (size > BITS_PER_LONG) {
> + for (idx = 0; idx * BITS_PER_LONG < size; idx++)
> + if (~addr[idx])
> + return 0;
> +
> + mask = size - (idx - 1) * BITS_PER_LONG;
> + }
> +
> + return !(~(*addr) & BITMAP_LAST_WORD_MASK(mask));
> +}
> +EXPORT_SYMBOL(all_bit_is_one);
> +#endif
> +
> #ifdef __BIG_ENDIAN
>
> /* include/linux/byteorder does not support "unsigned long" type */
> --
> 2.5.0
>
--
Best regards, _ _
.o. | Liege of Serenely Enlightened Majesty of o' \,=./ `o
..o | Computer Science, ミハウ “mina86” ナザレヴイツ (o o)
ooo +--<[email protected]>--<xmpp:[email protected]>-----ooO--(_)--Ooo--
On Thu, Nov 19, 2015 at 4:31 AM, Jia He <[email protected]> wrote:
> This patch moves the mask macro to bitops.h and then the new introduced
> api in find_bit.c can use it.
Why API can't use GENMASK() instead?
>
> Signed-off-by: Jia He <[email protected]>
> ---
> include/linux/bitmap.h | 3 ---
> include/linux/bitops.h | 4 ++++
> 2 files changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 9653fdb..15524f6 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -172,9 +172,6 @@ extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int
> extern int bitmap_print_to_pagebuf(bool list, char *buf,
> const unsigned long *maskp, int nmaskbits);
>
> -#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
> -#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
> -
> #define small_const_nbits(nbits) \
> (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
>
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 2b8ed12..b881028 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -24,6 +24,10 @@
> #define GENMASK_ULL(h, l) \
> (((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LONG_LONG - 1 - (h))))
>
> +/* For bitmap ops*/
> +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
> +#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
> +
> extern unsigned int __sw_hweight8(unsigned int w);
> extern unsigned int __sw_hweight16(unsigned int w);
> extern unsigned int __sw_hweight32(unsigned int w);
> --
> 2.5.0
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
--
With Best Regards,
Andy Shevchenko