Resend bitmap patches
Subsystems (61)
Yury Norov
maintainercover Resend bitmap patches
This is a resend of previously submitted series:
https://lore.kernel.org/patchwork/cover/1462071/
https://lore.kernel.org/patchwork/patch/1458703/
https://lore.kernel.org/lkml/YPG8SdsbQ+sxjk0w@yury-ThinkPad/T/
https://lore.kernel.org/lkml/YMVSHCY9yEocmfVD@yury-ThinkPad/T/
Most of the patches received testing and review. If I missed to add someone's review tag putting all together - my kind apologise. Please resend it here.
I believe I addessed all comments except Joe's one. In comment to patch 3, Joe Perches suggested to rename include/linux/find.h, but didn't give a new name, so I leave it as is. Since this header is not for direct inclusion, I'm OK with any reasonable name, and we can change it later.
Andrew, can you please take this series in linux-next?
Andy Shevchenko (1):
tools: Rename bitmap_alloc() to bitmap_zalloc()
Yury Norov (16):
bitops: protect find_first_{,zero}_bit properly
bitops: move find_bit_*_le functions from le.h to find.h
include: move find.h from asm_generic to linux
arch: remove GENERIC_FIND_FIRST_BIT entirely
lib: add find_first_and_bit()
cpumask: use find_first_and_bit()
all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where
appropriate
tools: sync tools/bitmap with mother linux
cpumask: replace cpumask_next_* with cpumask_first_* where appropriate include/linux: move for_each_bit() macros from bitops.h to find.h
find: micro-optimize for_each_{set,clear}_bit()
Replace for_each_*_bit_from() with for_each_*_bit() where appropriate mm/percpu: micro-optimize pcpu_is_populated()
bitmap: unify find_bit operations
lib: bitmap: add performance test for bitmap_print_to_pagebuf
vsprintf: rework bitmap_list_string
MAINTAINERS | 4 +-
arch/alpha/include/asm/bitops.h | 2 -
arch/arc/Kconfig | 1 -
arch/arc/include/asm/bitops.h | 1 -
arch/arm/include/asm/bitops.h | 1 -
arch/arm64/Kconfig | 1 -
arch/arm64/include/asm/bitops.h | 1 -
arch/csky/include/asm/bitops.h | 1 -
arch/h8300/include/asm/bitops.h | 1 -
arch/hexagon/include/asm/bitops.h | 1 -
arch/ia64/include/asm/bitops.h | 2 -
arch/m68k/include/asm/bitops.h | 2 -
arch/mips/Kconfig | 1 -
arch/mips/include/asm/bitops.h | 1 -
arch/openrisc/include/asm/bitops.h | 1 -
arch/parisc/include/asm/bitops.h | 2 -
arch/powerpc/include/asm/bitops.h | 2 -
arch/powerpc/include/asm/cputhreads.h | 2 +-
arch/powerpc/platforms/pasemi/dma_lib.c | 4 +-
arch/riscv/include/asm/bitops.h | 1 -
arch/s390/Kconfig | 1 -
arch/s390/include/asm/bitops.h | 1 -
arch/s390/kvm/kvm-s390.c | 2 +-
arch/sh/include/asm/bitops.h | 1 -
arch/sparc/include/asm/bitops_32.h | 1 -
arch/sparc/include/asm/bitops_64.h | 2 -
arch/x86/Kconfig | 1 -
arch/x86/include/asm/bitops.h | 2 -
arch/x86/kernel/apic/vector.c | 4 +-
arch/x86/um/Kconfig | 1 -
arch/xtensa/include/asm/bitops.h | 1 -
block/blk-mq.c | 2 +-
drivers/block/rnbd/rnbd-clt.c | 2 +-
drivers/dma/ti/edma.c | 2 +-
drivers/gpu/drm/etnaviv/etnaviv_gpu.c | 4 +-
drivers/hwmon/ltc2992.c | 3 +-
drivers/iio/adc/ad7124.c | 2 +-
drivers/infiniband/hw/irdma/hw.c | 16 +-
drivers/media/cec/core/cec-core.c | 2 +-
drivers/media/mc/mc-devnode.c | 2 +-
drivers/mmc/host/renesas_sdhi_core.c | 2 +-
drivers/net/virtio_net.c | 2 +-
drivers/pci/controller/dwc/pci-dra7xx.c | 2 +-
drivers/scsi/lpfc/lpfc_sli.c | 10 +-
drivers/soc/fsl/qbman/bman_portal.c | 2 +-
drivers/soc/fsl/qbman/qman_portal.c | 2 +-
drivers/soc/ti/k3-ringacc.c | 4 +-
drivers/tty/n_tty.c | 2 +-
drivers/virt/acrn/ioreq.c | 3 +-
fs/f2fs/segment.c | 8 +-
fs/ocfs2/cluster/heartbeat.c | 2 +-
fs/ocfs2/dlm/dlmdomain.c | 4 +-
fs/ocfs2/dlm/dlmmaster.c | 18 +-
fs/ocfs2/dlm/dlmrecovery.c | 2 +-
fs/ocfs2/dlm/dlmthread.c | 2 +-
include/asm-generic/bitops.h | 1 -
include/asm-generic/bitops/le.h | 64 ---
include/linux/bitmap.h | 34 +-
include/linux/bitops.h | 34 --
include/linux/cpumask.h | 46 ++-
include/linux/find.h | 372 ++++++++++++++++++
kernel/time/clocksource.c | 4 +-
lib/Kconfig | 3 -
lib/find_bit.c | 21 +
lib/find_bit_benchmark.c | 21 +
lib/genalloc.c | 2 +-
lib/test_bitmap.c | 37 ++
lib/vsprintf.c | 24 +-
mm/percpu.c | 35 +-
net/ncsi/ncsi-manage.c | 4 +-
tools/include/asm-generic/bitops.h | 1 -
tools/include/asm-generic/bitops/find.h | 145 -------
tools/include/linux/bitmap.h | 11 +-
.../bitops => tools/include/linux}/find.h | 54 ++-
tools/lib/find_bit.c | 20 +
tools/perf/bench/find-bit-bench.c | 2 +-
tools/perf/builtin-c2c.c | 6 +-
tools/perf/builtin-record.c | 2 +-
tools/perf/tests/bitmap.c | 2 +-
tools/perf/tests/mem2node.c | 2 +-
tools/perf/util/affinity.c | 4 +-
tools/perf/util/header.c | 4 +-
tools/perf/util/metricgroup.c | 2 +-
tools/perf/util/mmap.c | 4 +-
.../selftests/kvm/dirty_log_perf_test.c | 2 +-
tools/testing/selftests/kvm/dirty_log_test.c | 4 +-
.../selftests/kvm/x86_64/vmx_dirty_log_test.c | 2 +-
87 files changed, 657 insertions(+), 461 deletions(-)
create mode 100644 include/linux/find.h
delete mode 100644 tools/include/asm-generic/bitops/find.h
rename {include/asm-generic/bitops => tools/include/linux}/find.h (83%)Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 1/17 bitops: protect find_first_{,zero}_bit properly
find_first_bit() and find_first_zero_bit() are not protected with ifdefs as other functions in find.h. It causes build errors on some platforms if CONFIG_GENERIC_FIND_FIRST_BIT is enabled.
--- include/asm-generic/bitops/find.h | 5 +++++ 1 file changed, 5 insertions(+)
include/asm-generic/bitops/find.h +5 -0
@@ -97,6 +97,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,#ifdef CONFIG_GENERIC_FIND_FIRST_BIT +#ifndef find_first_bit/** * find_first_bit - find the first set bit in a memory region * @addr: The address to start the search at
@@ -116,7 +117,9 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long 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
@@ -136,6 +139,8 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) return _find_first_zero_bit(addr, size); } +#endif +#else /* CONFIG_GENERIC_FIND_FIRST_BIT */ #ifndef find_first_bit
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 2/17 bitops: move find_bit_*_le functions from le.h to find.h
In reply to Yury NorovIt's convenient to have all find_bit declarations in one place.
--- include/asm-generic/bitops/find.h | 69 +++++++++++++++++++++++++++++++ include/asm-generic/bitops/le.h | 64 ---------------------------- 2 files changed, 69 insertions(+), 64 deletions(-)
include/asm-generic/bitops/find.h +69 -0
@@ -190,4 +190,73 @@ extern unsigned long find_next_clump8(unsigned long *clump,#define find_first_clump8 (clump, bits, size) \ find_next_clump8((clump), (bits), (size), 0) +#if defined(__LITTLE_ENDIAN) + +static 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 inline unsigned long find_next_bit_le (const void *addr, +unsigned long size,unsigned long offset) +{ +return find_next_bit (addr, size, offset); +} + +static inline unsigned long find_first_zero_bit_le (const void *addr, +unsigned long size) +{ +return find_first_zero_bit (addr, size); +} + +#elif defined(__BIG_ENDIAN) + +#ifndef find_next_zero_bit_le +static inline +unsigned long find_next_zero_bit_le (const void *addr,unsigned +long size,unsigned long offset) +{ +if (small_const_nbits (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } + +return _find_next_bit (addr,NULL , size, offset, ~0UL ,1 ); +} +#endif + +#ifndef find_next_bit_le +static inline +unsigned long find_next_bit_le (const void *addr,unsigned +long size,unsigned long offset) +{ +if (small_const_nbits (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } + +return _find_next_bit (addr,NULL , size, offset,0UL ,1 ); +} +#endif + +#ifndef find_first_zero_bit_le +#define find_first_zero_bit_le (addr, size) \ + find_next_zero_bit_le((addr), (size), 0) +#endif + +#else +#error "Please fix <asm/byteorder.h>" +#endif +#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
include/asm-generic/bitops/le.h +0 -64
83 lines not on this page · raw message
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 3/17 include: move find.h from asm_generic to linux
In reply to Yury Norovfind_bit API and bitmap API are closely related, but inclusion paths are different - include/asm-generic and include/linux, correspondingly. In the past it made a lot of troubles due to circular dependencies and/or undefined symbols. Fix this by moving find.h under include/linux.
---
MAINTAINERS | 2 +-
arch/alpha/include/asm/bitops.h | 2 --
arch/arc/include/asm/bitops.h | 1 -
arch/arm/include/asm/bitops.h | 1 -
arch/arm64/include/asm/bitops.h | 1 -
arch/csky/include/asm/bitops.h | 1 -
arch/h8300/include/asm/bitops.h | 1 -
arch/hexagon/include/asm/bitops.h | 1 -
arch/ia64/include/asm/bitops.h | 2 --
arch/m68k/include/asm/bitops.h | 2 --
arch/mips/include/asm/bitops.h | 1 -
arch/openrisc/include/asm/bitops.h | 1 -
arch/parisc/include/asm/bitops.h | 2 --
arch/powerpc/include/asm/bitops.h | 2 --
arch/riscv/include/asm/bitops.h | 1 -
arch/s390/include/asm/bitops.h | 1 -
arch/sh/include/asm/bitops.h | 1 -
arch/sparc/include/asm/bitops_32.h | 1 -
arch/sparc/include/asm/bitops_64.h | 2 --
arch/x86/include/asm/bitops.h | 2 --
arch/xtensa/include/asm/bitops.h | 1 -
include/asm-generic/bitops.h | 1 -
include/linux/bitmap.h | 1 +
include/{asm-generic/bitops => linux}/find.h | 12 +++++++++---
24 files changed, 11 insertions(+), 32 deletions(-)
rename include/{asm-generic/bitops => linux}/find.h (97%)MAINTAINERS +1 -1
@@ -3271,8 +3271,8 @@ M: Yury Norov <[email protected]> R: Andy Shevchenko <[email protected]> R: Rasmus Villemoes <[email protected]> S: Maintained -F: include/asm-generic/bitops/find.h F: include/linux/bitmap.h +F: include/linux/find.h F: lib/bitmap.c F: lib/find_bit.c F: lib/find_bit_benchmark.c
arch/alpha/include/asm/bitops.h +0 -2
@@ -430,8 +430,6 @@ static inline unsigned int __arch_hweight8(unsigned int w)#endif /* __KERNEL__ */ -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__/*
arch/arc/include/asm/bitops.h +0 -1
@@ -189,7 +189,6 @@ static inline __attribute__ ((const)) unsigned long __ffs(unsigned long x)#include <asm-generic/bitops/atomic.h> #include <asm-generic/bitops/non-atomic.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic-setbit.h>
arch/arm/include/asm/bitops.h +0 -1
@@ -264,7 +264,6 @@ static inline int find_next_bit_le(const void *p, int size, int offset)#endif -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/le.h> /*
arch/arm64/include/asm/bitops.h +0 -1
@@ -18,7 +18,6 @@#include <asm-generic/bitops/ffz.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/sched.h> #include <asm-generic/bitops/hweight.h>
arch/csky/include/asm/bitops.h +0 -1
@@ -59,7 +59,6 @@ static __always_inline unsigned long __fls(unsigned long x)#include <asm-generic/bitops/ffz.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #ifndef _LINUX_BITOPS_H#error only <linux/bitops.h> can be included directly
arch/h8300/include/asm/bitops.h +0 -1
@@ -168,7 +168,6 @@ static inline unsigned long __ffs(unsigned long word)return result; } -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/sched.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/lock.h>
arch/hexagon/include/asm/bitops.h +0 -1
@@ -271,7 +271,6 @@ static inline unsigned long __fls(unsigned long word) }#include <asm-generic/bitops/lock.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/sched.h>
arch/ia64/include/asm/bitops.h +0 -2
@@ -441,8 +441,6 @@ static __inline__ unsigned long __arch_hweight64(unsigned long x)#endif /* __KERNEL__ */ -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__#include <asm-generic/bitops/le.h>
arch/m68k/include/asm/bitops.h +0 -2
@@ -529,6 +529,4 @@ static inline int __fls(int x)#include <asm-generic/bitops/le.h> #endif /* __KERNEL__ */ -#include <asm-generic/bitops/find.h> -#endif /* _M68K_BITOPS_H */
arch/mips/include/asm/bitops.h +0 -1
@@ -446,7 +446,6 @@ static inline int ffs(int word) }#include <asm-generic/bitops/ffz.h> -#include <asm-generic/bitops/find.h> #ifdef __KERNEL__
arch/openrisc/include/asm/bitops.h +0 -1
@@ -30,7 +30,6 @@#include <asm/bitops/fls.h> #include <asm/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #ifndef _LINUX_BITOPS_H#error only <linux/bitops.h> can be included directly
arch/parisc/include/asm/bitops.h +0 -2
@@ -208,8 +208,6 @@ static __inline__ int fls(unsigned int x)#endif /* __KERNEL__ */ -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__#include <asm-generic/bitops/le.h>
arch/powerpc/include/asm/bitops.h +0 -2
@@ -255,8 +255,6 @@ unsigned long __arch_hweight64(__u64 w);#include <asm-generic/bitops/hweight.h> #endif -#include <asm-generic/bitops/find.h> -/* wrappers that deal with KASAN instrumentation */ #include <asm-generic/bitops/instrumented-atomic.h> #include <asm-generic/bitops/instrumented-lock.h>
arch/riscv/include/asm/bitops.h +0 -1
@@ -20,7 +20,6 @@#include <asm-generic/bitops/fls.h> #include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/sched.h> #include <asm-generic/bitops/ffs.h>
arch/s390/include/asm/bitops.h +0 -1
@@ -387,7 +387,6 @@ static inline int fls(unsigned int word)#endif /* CONFIG_HAVE_MARCH_Z9_109_FEATURES */ #include <asm-generic/bitops/ffz.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/sched.h> #include <asm-generic/bitops/le.h>
arch/sh/include/asm/bitops.h +0 -1
@@ -68,6 +68,5 @@ static inline unsigned long __ffs(unsigned long word)#include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/le.h> -#include <asm-generic/bitops/find.h> #endif /* __ASM_SH_BITOPS_H */
arch/sparc/include/asm/bitops_32.h +0 -1
@@ -100,7 +100,6 @@ static inline void change_bit(unsigned long nr, volatile unsigned long *addr)#include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/lock.h> -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic.h>
arch/sparc/include/asm/bitops_64.h +0 -2
@@ -52,8 +52,6 @@ unsigned int __arch_hweight8(unsigned int w);#include <asm-generic/bitops/lock.h> #endif /* __KERNEL__ */ -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__#include <asm-generic/bitops/le.h>
arch/x86/include/asm/bitops.h +0 -2
@@ -380,8 +380,6 @@ static __always_inline int fls64(__u64 x)#include <asm-generic/bitops/fls64.h> #endif -#include <asm-generic/bitops/find.h> -#include <asm-generic/bitops/sched.h> #include <asm/arch_hweight.h>
arch/xtensa/include/asm/bitops.h +0 -1
@@ -205,7 +205,6 @@ BIT_OPS(change, "xor", )#undef BIT_OP#undef TEST_AND_BIT_OP -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic-setbit.h>
include/asm-generic/bitops.h +0 -1
@@ -20,7 +20,6 @@#include <asm-generic/bitops/fls.h> #include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #ifndef _LINUX_BITOPS_H#error only <linux/bitops.h> can be included directly
include/linux/bitmap.h +1 -0
@@ -6,6 +6,7 @@#include <linux/align.h> #include <linux/bitops.h> +#include <linux/find.h> #include <linux/limits.h> #include <linux/string.h> #include <linux/types.h>
include/linux/find.h renamed from include/asm-generic/bitops/find.h +9 -3
@@ -1,6 +1,12 @@/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef _ASM_GENERIC_BITOPS_FIND_H_ -#define _ASM_GENERIC_BITOPS_FIND_H_ +#ifndef __LINUX_FIND_H_ +#define __LINUX_FIND_H_ + +#ifndef __LINUX_BITMAP_H +#error only <linux/bitmap.h> can be included directly +#endif + +#include <linux/bitops.h> extern unsigned long _find_next_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long nbits,
@@ -259,4 +265,4 @@ unsigned long find_next_bit_le(const void *addr, unsigned#error "Please fix <asm/byteorder.h>"#endif -#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ +#endif /*__LINUX_FIND_H_ */
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 4/17 arch: remove GENERIC_FIND_FIRST_BIT entirely
In reply to Yury NorovIn 5.12 cycle we enabled GENERIC_FIND_FIRST_BIT config option for ARM64 and MIPS. It increased performance and shrunk .text size; and so far I didn't receive any negative feedback on the change.
https://lore.kernel.org/linux-arch/[email protected]/
Now I think it's a good time to switch all architectures to use find_{first,last}_bit() unconditionally, and so remove corresponding config option.
The patch does't introduce functioal changes for arc, arm, arm64, mips, m68k, s390 and x86, for other architectures I expect improvement both in performance and .text size.
--- arch/arc/Kconfig | 1 - arch/arm64/Kconfig | 1 - arch/mips/Kconfig | 1 - arch/s390/Kconfig | 1 - arch/x86/Kconfig | 1 - arch/x86/um/Kconfig | 1 - include/linux/find.h | 13 ------------- lib/Kconfig | 3 --- 8 files changed, 22 deletions(-)
arch/arc/Kconfig +0 -1
@@ -20,7 +20,6 @@ config ARC select COMMON_CLK select DMA_DIRECT_REMAP select GENERIC_ATOMIC64 if !ISA_ARCV2 || !(ARC_HAS_LL64 && ARC_HAS_LLSC) - select GENERIC_FIND_FIRST_BIT # for now, we don't need GENERIC_IRQ_PROBE, CONFIG_GENERIC_IRQ_CHIP select GENERIC_IRQ_SHOW select GENERIC_PCI_IOMAP
arch/arm64/Kconfig +0 -1
@@ -119,7 +119,6 @@ config ARM64 select GENERIC_CPU_AUTOPROBE select GENERIC_CPU_VULNERABILITIES select GENERIC_EARLY_IOREMAP - select GENERIC_FIND_FIRST_BIT select GENERIC_IDLE_POLL_SETUP select GENERIC_IRQ_IPI select GENERIC_IRQ_PROBE
arch/mips/Kconfig +0 -1
@@ -30,7 +30,6 @@ config MIPS select GENERIC_ATOMIC64 if !64BIT select GENERIC_CMOS_UPDATE select GENERIC_CPU_AUTOPROBE - select GENERIC_FIND_FIRST_BIT select GENERIC_GETTIMEOFDAY select GENERIC_IOMAP select GENERIC_IRQ_PROBE
arch/s390/Kconfig +0 -1
@@ -126,7 +126,6 @@ config S390 select GENERIC_CPU_AUTOPROBE select GENERIC_CPU_VULNERABILITIES select GENERIC_ENTRY - select GENERIC_FIND_FIRST_BIT select GENERIC_GETTIMEOFDAY select GENERIC_PTDUMP select GENERIC_SMP_IDLE_THREAD
arch/x86/Kconfig +0 -1
@@ -134,7 +134,6 @@ config X86 select GENERIC_CPU_VULNERABILITIES select GENERIC_EARLY_IOREMAP select GENERIC_ENTRY - select GENERIC_FIND_FIRST_BIT select GENERIC_IOMAP select GENERIC_IRQ_EFFECTIVE_AFF_MASK if SMP select GENERIC_IRQ_MATRIX_ALLOCATOR if X86_LOCAL_APIC
arch/x86/um/Kconfig +0 -1
@@ -8,7 +8,6 @@ endmenu config UML_X86 def_bool y - select GENERIC_FIND_FIRST_BIT config 64BIT bool "64-bit kernel" if "$(SUBARCH)" = "x86"
include/linux/find.h +0 -13
@@ -101,8 +101,6 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, }#endif -#ifdef CONFIG_GENERIC_FIND_FIRST_BIT -#ifndef find_first_bit/** * find_first_bit - find the first set bit in a memory region
@@ -147,17 +145,6 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) }#endif -#else /* CONFIG_GENERIC_FIND_FIRST_BIT */ - -#ifndef find_first_bit -#define find_first_bit (addr, size) find_next_bit((addr), (size), 0) -#endif -#ifndef find_first_zero_bit -#define find_first_zero_bit (addr, size) find_next_zero_bit((addr), (size), 0) -#endif - -#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ -#ifndef find_last_bit/** * find_last_bit - find the last set bit in a memory region
lib/Kconfig +0 -3
@@ -59,9 +59,6 @@ config GENERIC_STRNLEN_USER config GENERIC_NET_UTILS bool -config GENERIC_FIND_FIRST_BIT - bool - source "lib/math/Kconfig" config NO_GENERIC_PCI_IOPORT_MAP
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 5/17 lib: add find_first_and_bit()
In reply to Yury NorovCurrently find_first_and_bit() is an alias to find_next_and_bit(). However, it is widely used in cpumask, so it worth to optimize it. This patch adds its own implementation for find_first_and_bit().
On x86_64 find_bit_benchmark says:
Before (#define find_first_and_bit(...) find_next_and_bit(..., 0):
Start testing find_bit() with random-filled bitmap
[ 140.291468] find_first_and_bit: 46890919 ns, 32671 iterations Start testing find_bit() with sparse bitmap [ 140.295028] find_first_and_bit: 7103 ns, 1 iterations
After:
Start testing find_bit() with random-filled bitmap
[ 162.574907] find_first_and_bit: 25045813 ns, 32846 iterations Start testing find_bit() with sparse bitmap [ 162.578458] find_first_and_bit: 4900 ns, 1 iterations
(Thanks to Alexey Klimov for thorough testing.)
--- include/linux/find.h | 27 +++++++++++++++++++++++++++ lib/find_bit.c | 21 +++++++++++++++++++++ lib/find_bit_benchmark.c | 21 +++++++++++++++++++++ 3 files changed, 69 insertions(+)
include/linux/find.h +27 -0
@@ -12,6 +12,8 @@ extern 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);extern unsigned long _find_first_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_first_and_bit (const unsigned long *addr1, +const unsigned long *addr2,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);
@@ -123,6 +125,31 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size) }#endif +#ifndef find_first_and_bit +/** +* find_first_and_bit - find the first set bit in both memory regions +* @addr1: The first address to base the search on +* @addr2: The second address to base the search on +* @size: The bitmap size in bits +* +* Returns the bit number for the next set bit +* If no bits are set, returns @size. +*/ +static inline +unsigned long find_first_and_bit (const unsigned long *addr1, +const unsigned long *addr2, +unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr1 & *addr2 &GENMASK (size -1 ,0 ); + +return val ?__ffs (val) : size; + } + +return _find_first_and_bit (addr1, addr2, size); +} +#endif +#ifndef find_first_zero_bit/** * find_first_zero_bit - find the first cleared bit in a memory region
lib/find_bit.c +21 -0
@@ -89,6 +89,27 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)EXPORT_SYMBOL (_find_first_bit);#endif +#ifndef find_first_and_bit +/* +* Find the first set bit in two memory regions. +*/ +unsigned long _find_first_and_bit (const unsigned long *addr1, +const unsigned long *addr2, +unsigned long size) +{ +unsigned long idx, val; + +for (idx =0 ; idx *BITS_PER_LONG < size; idx++) { + val = addr1[idx] & addr2[idx]; +if (val) +return min (idx *BITS_PER_LONG +__ffs (val), size); + } + +return size; +} +EXPORT_SYMBOL (_find_first_and_bit); +#endif +#ifndef find_first_zero_bit/* * Find the first cleared bit in a memory region.
lib/find_bit_benchmark.c +21 -0
@@ -49,6 +49,25 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)return 0 ; } +static int __init test_find_first_and_bit (void *bitmap,const void *bitmap2,unsigned long len) +{ + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; +unsigned long i, cnt; +ktime_t time; + +bitmap_copy (cp, bitmap,BITMAP_LEN ); + + time =ktime_get (); +for (cnt = i =0 ; i < len; cnt++) { + i =find_first_and_bit (cp, bitmap2, len); +__clear_bit (i, cp); + } + time =ktime_get () - time; +pr_err ("find_first_and_bit: %18llu ns, %6ld iterations\n" , time, cnt); + +return 0 ; +} +static int __init test_find_next_bit (const void *bitmap,unsigned long len) {unsigned long i, cnt;
@@ -129,6 +148,7 @@ static int __init find_bit_test(void)* traverse only part of bitmap to avoid soft lockup. */ test_find_first_bit (bitmap,BITMAP_LEN /10 ); +test_find_first_and_bit (bitmap, bitmap2,BITMAP_LEN /2 );test_find_next_and_bit (bitmap, bitmap2,BITMAP_LEN );pr_err ("\nStart testing find_bit() with sparse bitmap\n" );
@@ -145,6 +165,7 @@ static int __init find_bit_test(void)test_find_next_zero_bit (bitmap,BITMAP_LEN );test_find_last_bit (bitmap,BITMAP_LEN );test_find_first_bit (bitmap,BITMAP_LEN ); +test_find_first_and_bit (bitmap, bitmap2,BITMAP_LEN );test_find_next_and_bit (bitmap, bitmap2,BITMAP_LEN );/*
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 6/17 cpumask: use find_first_and_bit()
In reply to Yury NorovNow we have an efficient implementation for find_first_and_bit(), so switch cpumask to use it where appropriate.
--- include/linux/cpumask.h | 30 ++++++++++++++++++++---------- 1 file changed, 20 insertions(+), 10 deletions(-)
include/linux/cpumask.h +20 -10
@@ -123,6 +123,12 @@ static inline unsigned int cpumask_first(const struct cpumask *srcp)return 0 ; } +static inline unsigned int cpumask_first_and (const struct cpumask *srcp1, +const struct cpumask *srcp2) +{ +return 0 ; +} +static inline unsigned int cpumask_last (const struct cpumask *srcp) {return 0 ;
@@ -167,7 +173,7 @@ static inline unsigned int cpumask_local_spread(unsigned int i, int node)static inline int cpumask_any_and_distribute (const struct cpumask *src1p,const struct cpumask *src2p) { -return cpumask_next_and (-1 , src1p, src2p); +return cpumask_first_and (src1p, src2p); }static inline int cpumask_any_distribute (const struct cpumask *srcp)
@@ -195,6 +201,19 @@ static inline unsigned int cpumask_first(const struct cpumask *srcp)return find_first_bit (cpumask_bits (srcp), nr_cpumask_bits); } +/** +* cpumask_first_and - return the first cpu from *srcp1 & *srcp2 +* @src1p: the first input +* @src2p: the second input +* +* Returns >= nr_cpu_ids if no cpus set in both. See also cpumask_next_and(). +*/ +static inline +unsigned int cpumask_first_and (const struct cpumask *srcp1,const struct cpumask *srcp2) +{ +return find_first_and_bit (cpumask_bits (srcp1),cpumask_bits (srcp2), nr_cpumask_bits); +} +/** * cpumask_last - get the last CPU in a cpumask * @srcp: - the cpumask pointer
@@ -585,15 +604,6 @@ static inline void cpumask_copy(struct cpumask *dstp,*/ #define cpumask_any (srcp) cpumask_first(srcp) -/** -* cpumask_first_and - return the first cpu from *srcp1 & *srcp2 -* @src1p: the first input -* @src2p: the second input -* -* Returns >= nr_cpu_ids if no cpus set in both. See also cpumask_next_and(). -*/ -#define cpumask_first_and (src1p, src2p) cpumask_next_and(-1, (src1p), (src2p)) -/** * cpumask_any_and - pick a "random" cpu from *mask1 & *mask2 * @mask1: the first input cpumask
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 7/17 all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate
In reply to Yury Norovfind_first{,_zero}_bit is a more effective analogue of 'next' version if start == 0. This patch replaces 'next' with 'first' where things look trivial.
--- arch/powerpc/platforms/pasemi/dma_lib.c | 4 ++-- arch/s390/kvm/kvm-s390.c | 2 +- drivers/block/rnbd/rnbd-clt.c | 2 +- drivers/dma/ti/edma.c | 2 +- drivers/iio/adc/ad7124.c | 2 +- drivers/infiniband/hw/irdma/hw.c | 16 ++++++++-------- drivers/media/cec/core/cec-core.c | 2 +- drivers/media/mc/mc-devnode.c | 2 +- drivers/pci/controller/dwc/pci-dra7xx.c | 2 +- drivers/scsi/lpfc/lpfc_sli.c | 10 +++++----- drivers/soc/ti/k3-ringacc.c | 4 ++-- drivers/tty/n_tty.c | 2 +- drivers/virt/acrn/ioreq.c | 3 +-- fs/f2fs/segment.c | 8 ++++---- fs/ocfs2/cluster/heartbeat.c | 2 +- fs/ocfs2/dlm/dlmdomain.c | 4 ++-- fs/ocfs2/dlm/dlmmaster.c | 18 +++++++++--------- fs/ocfs2/dlm/dlmrecovery.c | 2 +- fs/ocfs2/dlm/dlmthread.c | 2 +- lib/genalloc.c | 2 +- net/ncsi/ncsi-manage.c | 4 ++-- 21 files changed, 47 insertions(+), 48 deletions(-)
arch/powerpc/platforms/pasemi/dma_lib.c +2 -2
@@ -375,7 +375,7 @@ int pasemi_dma_alloc_flag(void)int bit; retry: - bit =find_next_bit (flags_free,MAX_FLAGS ,0 ); + bit =find_first_bit (flags_free,MAX_FLAGS );if (bit >=MAX_FLAGS )return -ENOSPC ;if (!test_and_clear_bit (bit, flags_free))
@@ -440,7 +440,7 @@ int pasemi_dma_alloc_fun(void)int bit; retry: - bit =find_next_bit (fun_free,MAX_FLAGS ,0 ); + bit =find_first_bit (fun_free,MAX_FLAGS );if (bit >=MAX_FLAGS )return -ENOSPC ;if (!test_and_clear_bit (bit, fun_free))
arch/s390/kvm/kvm-s390.c +1 -1
@@ -2023,7 +2023,7 @@ static unsigned long kvm_s390_next_dirty_cmma(struct kvm_memslots *slots,while ((slotidx >0 ) && (ofs >= ms->npages)) { slotidx--; ms = slots->memslots + slotidx; - ofs =find_next_bit (kvm_second_dirty_bitmap (ms), ms->npages,0 ); + ofs =find_first_bit (kvm_second_dirty_bitmap (ms), ms->npages); }return ms->base_gfn + ofs; }
drivers/block/rnbd/rnbd-clt.c +1 -1
@@ -196,7 +196,7 @@ rnbd_get_cpu_qlist(struct rnbd_clt_session *sess, int cpu)return per_cpu_ptr (sess->cpu_queues, bit); }else if (cpu !=0 ) {/* Search from 0 to cpu */ - bit =find_next_bit (sess->cpu_queues_bm, cpu,0 ); + bit =find_first_bit (sess->cpu_queues_bm, cpu);if (bit < cpu)return per_cpu_ptr (sess->cpu_queues, bit); }
drivers/dma/ti/edma.c +1 -1
@@ -1681,7 +1681,7 @@ static irqreturn_t dma_ccerr_handler(int irq, void *data)dev_dbg (ecc->dev,"EMR%d 0x%08x\n" , j, val); emr = val; -for (i =find_next_bit (&emr,32 ,0 ); i <32 ; +for (i =find_first_bit (&emr,32 ); i <32 ; i =find_next_bit (&emr,32 , i +1 )) {int k = (j <<5 ) + i;
drivers/iio/adc/ad7124.c +1 -1
@@ -347,7 +347,7 @@ static int ad7124_find_free_config_slot(struct ad7124_state *st) {unsigned int free_cfg_slot; - free_cfg_slot =find_next_zero_bit (&st->cfg_slots_status,AD7124_MAX_CONFIGS ,0 ); + free_cfg_slot =find_first_zero_bit (&st->cfg_slots_status,AD7124_MAX_CONFIGS );if (free_cfg_slot ==AD7124_MAX_CONFIGS )return -1 ;
drivers/infiniband/hw/irdma/hw.c +8 -8
@@ -1696,14 +1696,14 @@ static enum irdma_status_code irdma_setup_init_state(struct irdma_pci_f *rf)*/ static void irdma_get_used_rsrc (struct irdma_device *iwdev) { - iwdev->rf->used_pds =find_next_zero_bit (iwdev->rf->allocated_pds, - iwdev->rf->max_pd,0 ); - iwdev->rf->used_qps =find_next_zero_bit (iwdev->rf->allocated_qps, - iwdev->rf->max_qp,0 ); - iwdev->rf->used_cqs =find_next_zero_bit (iwdev->rf->allocated_cqs, - iwdev->rf->max_cq,0 ); - iwdev->rf->used_mrs =find_next_zero_bit (iwdev->rf->allocated_mrs, - iwdev->rf->max_mr,0 ); + iwdev->rf->used_pds =find_first_zero_bit (iwdev->rf->allocated_pds, + iwdev->rf->max_pd); + iwdev->rf->used_qps =find_first_zero_bit (iwdev->rf->allocated_qps, + iwdev->rf->max_qp); + iwdev->rf->used_cqs =find_first_zero_bit (iwdev->rf->allocated_cqs, + iwdev->rf->max_cq); + iwdev->rf->used_mrs =find_first_zero_bit (iwdev->rf->allocated_mrs, + iwdev->rf->max_mr); }void irdma_ctrl_deinit_hw (struct irdma_pci_f *rf)
drivers/media/cec/core/cec-core.c +1 -1
@@ -106,7 +106,7 @@ static int __must_check cec_devnode_register(struct cec_devnode *devnode,/* Part 1: Find a free minor number */ mutex_lock (&cec_devnode_lock); - minor =find_next_zero_bit (cec_devnode_nums,CEC_NUM_DEVICES ,0 ); + minor =find_first_zero_bit (cec_devnode_nums,CEC_NUM_DEVICES );if (minor ==CEC_NUM_DEVICES ) {mutex_unlock (&cec_devnode_lock);pr_err ("could not get a free minor\n" );
drivers/media/mc/mc-devnode.c +1 -1
@@ -217,7 +217,7 @@ int __must_check media_devnode_register(struct media_device *mdev,/* Part 1: Find a free minor number */ mutex_lock (&media_devnode_lock); - minor =find_next_zero_bit (media_devnode_nums,MEDIA_NUM_DEVICES ,0 ); + minor =find_first_zero_bit (media_devnode_nums,MEDIA_NUM_DEVICES );if (minor ==MEDIA_NUM_DEVICES ) {mutex_unlock (&media_devnode_lock);pr_err ("could not get a free minor\n" );
drivers/pci/controller/dwc/pci-dra7xx.c +1 -1
@@ -211,7 +211,7 @@ static int dra7xx_pcie_handle_msi(struct pcie_port *pp, int index)if (!val)return 0 ; - pos =find_next_bit (&val,MAX_MSI_IRQS_PER_CTRL ,0 ); + pos =find_first_bit (&val,MAX_MSI_IRQS_PER_CTRL );while (pos !=MAX_MSI_IRQS_PER_CTRL ) {generic_handle_domain_irq (pp->irq_domain, (index *MAX_MSI_IRQS_PER_CTRL ) + pos);
drivers/scsi/lpfc/lpfc_sli.c +5 -5
@@ -17286,8 +17286,8 @@ lpfc_sli4_alloc_xri(struct lpfc_hba *phba)* the driver starts at 0 each time. */ spin_lock_irq (&phba->hbalock); - xri =find_next_zero_bit (phba->sli4_hba.xri_bmask, - phba->sli4_hba.max_cfg_param.max_xri,0 ); + xri =find_first_zero_bit (phba->sli4_hba.xri_bmask, + phba->sli4_hba.max_cfg_param.max_xri);if (xri >= phba->sli4_hba.max_cfg_param.max_xri) {spin_unlock_irq (&phba->hbalock);return NO_XRI ;
@@ -18964,7 +18964,7 @@ lpfc_sli4_alloc_rpi(struct lpfc_hba *phba) max_rpi = phba->sli4_hba.max_cfg_param.max_rpi; rpi_limit = phba->sli4_hba.next_rpi; - rpi =find_next_zero_bit (phba->sli4_hba.rpi_bmask, rpi_limit,0 ); + rpi =find_first_zero_bit (phba->sli4_hba.rpi_bmask, rpi_limit);if (rpi >= rpi_limit) rpi =LPFC_RPI_ALLOC_ERROR ;else {
@@ -19607,8 +19607,8 @@ lpfc_sli4_fcf_rr_next_index_get(struct lpfc_hba *phba)* have been tested so that we can detect when we should * change the priority level. */ - next_fcf_index =find_next_bit (phba->fcf.fcf_rr_bmask, -LPFC_SLI4_FCF_TBL_INDX_MAX ,0 ); + next_fcf_index =find_first_bit (phba->fcf.fcf_rr_bmask, +LPFC_SLI4_FCF_TBL_INDX_MAX ); }
drivers/soc/ti/k3-ringacc.c +2 -2
@@ -358,8 +358,8 @@ struct k3_ring *k3_ringacc_request_ring(struct k3_ringacc *ringacc, goto out;if (flags &K3_RINGACC_RING_USE_PROXY ) { - proxy_id =find_next_zero_bit (ringacc->proxy_inuse, - ringacc->num_proxies,0 ); + proxy_id =find_first_zero_bit (ringacc->proxy_inuse, + ringacc->num_proxies);if (proxy_id == ringacc->num_proxies) goto error; }
drivers/tty/n_tty.c +1 -1
@@ -1975,7 +1975,7 @@ static bool canon_copy_from_read_buf(struct tty_struct *tty, more = n - (size - tail);if (eol ==N_TTY_BUF_SIZE && more) {/* scan wrapped without finding set bit */ - eol =find_next_bit (ldata->read_flags, more,0 ); + eol =find_first_bit (ldata->read_flags, more); found = eol != more; }else found = eol != size;
drivers/virt/acrn/ioreq.c +1 -2
@@ -246,8 +246,7 @@ void acrn_ioreq_request_clear(struct acrn_vm *vm)spin_lock_bh (&vm->ioreq_clients_lock); client = vm->default_client;if (client) { - vcpu =find_next_bit (client->ioreqs_map, -ACRN_IO_REQUEST_MAX ,0 ); + vcpu =find_first_bit (client->ioreqs_map,ACRN_IO_REQUEST_MAX );while (vcpu <ACRN_IO_REQUEST_MAX ) {acrn_ioreq_complete_request (client, vcpu,NULL ); vcpu = find_next_bit(client->ioreqs_map,
fs/f2fs/segment.c +4 -4
@@ -2524,8 +2524,8 @@ static void get_new_segment(struct f2fs_sb_info *sbi, secno =find_next_zero_bit (free_i->free_secmap,MAIN_SECS (sbi), hint);if (secno >=MAIN_SECS (sbi)) {if (dir ==ALLOC_RIGHT ) { - secno =find_next_zero_bit (free_i->free_secmap, -MAIN_SECS (sbi),0 ); + secno =find_first_zero_bit (free_i->free_secmap, +MAIN_SECS (sbi));f2fs_bug_on (sbi, secno >=MAIN_SECS (sbi)); }else { go_left =1 ;
@@ -2540,8 +2540,8 @@ static void get_new_segment(struct f2fs_sb_info *sbi, left_start--;continue ; } - left_start =find_next_zero_bit (free_i->free_secmap, -MAIN_SECS (sbi),0 ); + left_start =find_first_zero_bit (free_i->free_secmap, +MAIN_SECS (sbi));f2fs_bug_on (sbi, left_start >=MAIN_SECS (sbi));break ; }
fs/ocfs2/cluster/heartbeat.c +1 -1
@@ -379,7 +379,7 @@ static void o2hb_nego_timeout(struct work_struct *work)o2hb_fill_node_map (live_node_bitmap,sizeof (live_node_bitmap));/* lowest node as master node to make negotiate decision. */ - master_node =find_next_bit (live_node_bitmap,O2NM_MAX_NODES ,0 ); + master_node =find_first_bit (live_node_bitmap,O2NM_MAX_NODES );if (master_node ==o2nm_this_node ()) {if (!test_bit (master_node, reg->hr_nego_node_bitmap)) {
fs/ocfs2/dlm/dlmdomain.c +2 -2
@@ -1045,7 +1045,7 @@ static int dlm_send_regions(struct dlm_ctxt *dlm, unsigned long *node_map)int status, ret =0 , i;char *p; -if (find_next_bit (node_map,O2NM_MAX_NODES ,0 ) >=O2NM_MAX_NODES ) +if (find_first_bit (node_map,O2NM_MAX_NODES ) >=O2NM_MAX_NODES ) goto bail; qr =kzalloc (sizeof (struct dlm_query_region ),GFP_KERNEL );
@@ -1217,7 +1217,7 @@ static int dlm_send_nodeinfo(struct dlm_ctxt *dlm, unsigned long *node_map)struct o2nm_node *node;int ret =0 , status, count, i; -if (find_next_bit (node_map,O2NM_MAX_NODES ,0 ) >=O2NM_MAX_NODES ) +if (find_first_bit (node_map,O2NM_MAX_NODES ) >=O2NM_MAX_NODES ) goto bail; qn =kzalloc (sizeof (struct dlm_query_nodeinfo ),GFP_KERNEL );
fs/ocfs2/dlm/dlmmaster.c +9 -9
@@ -861,7 +861,7 @@ struct dlm_lock_resource * dlm_get_lock_resource(struct dlm_ctxt *dlm,* to see if there are any nodes that still need to be * considered. these will not appear in the mle nodemap * but they might own this lockres. wait on them. */ - bit =find_next_bit (dlm->recovery_map,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (dlm->recovery_map,O2NM_MAX_NODES );if (bit <O2NM_MAX_NODES ) { mlog(0, "%s: res %.*s, At least one node (%d) " "to recover before lock mastery can begin\n",
@@ -912,7 +912,7 @@ struct dlm_lock_resource * dlm_get_lock_resource(struct dlm_ctxt *dlm,dlm_wait_for_recovery (dlm);spin_lock (&dlm->spinlock); - bit =find_next_bit (dlm->recovery_map,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (dlm->recovery_map,O2NM_MAX_NODES );if (bit <O2NM_MAX_NODES ) { mlog(0, "%s: res %.*s, At least one node (%d) " "to recover before lock mastery can begin\n",
@@ -1079,7 +1079,7 @@ static int dlm_wait_for_lock_mastery(struct dlm_ctxt *dlm, sleep =1 ;/* have all nodes responded? */ if (voting_done && !*blocked) { - bit =find_next_bit (mle->maybe_map,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (mle->maybe_map,O2NM_MAX_NODES );if (dlm->node_num <= bit) {/* my node number is lowest. * now tell other nodes that I am
@@ -1234,8 +1234,8 @@ static int dlm_restart_lock_mastery(struct dlm_ctxt *dlm, }else {mlog (ML_ERROR ,"node down! %d\n" , node);if (blocked) { -int lowest =find_next_bit (mle->maybe_map, -O2NM_MAX_NODES ,0 ); +int lowest =find_first_bit (mle->maybe_map, +O2NM_MAX_NODES );/* act like it was never there */ clear_bit (node, mle->maybe_map);
@@ -1795,7 +1795,7 @@ int dlm_assert_master_handler(struct o2net_msg *msg, u32 len, void *data,"MLE for it! (%.*s)\n" , assert->node_idx, namelen, name); }else { -int bit =find_next_bit (mle->maybe_map,O2NM_MAX_NODES ,0 ); +int bit =find_first_bit (mle->maybe_map,O2NM_MAX_NODES );if (bit >=O2NM_MAX_NODES ) {/* not necessarily an error, though less likely. * could be master just re-asserting. */
@@ -2521,7 +2521,7 @@ static int dlm_is_lockres_migratable(struct dlm_ctxt *dlm, }if (!nonlocal) { - node_ref =find_next_bit (res->refmap,O2NM_MAX_NODES ,0 ); + node_ref =find_first_bit (res->refmap,O2NM_MAX_NODES );if (node_ref >=O2NM_MAX_NODES )return 0 ; }
@@ -3303,7 +3303,7 @@ static void dlm_clean_block_mle(struct dlm_ctxt *dlm,BUG_ON (mle->type !=DLM_MLE_BLOCK );spin_lock (&mle->spinlock); - bit =find_next_bit (mle->maybe_map,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (mle->maybe_map,O2NM_MAX_NODES );if (bit != dead_node) {mlog (0 ,"mle found, but dead node %u would not have been " "master\n" , dead_node);
@@ -3542,7 +3542,7 @@ void dlm_force_free_mles(struct dlm_ctxt *dlm)spin_lock (&dlm->master_lock);BUG_ON (dlm->dlm_state !=DLM_CTXT_LEAVING ); -BUG_ON ((find_next_bit (dlm->domain_map,O2NM_MAX_NODES ,0 ) <O2NM_MAX_NODES )); +BUG_ON ((find_first_bit (dlm->domain_map,O2NM_MAX_NODES ) <O2NM_MAX_NODES ));for (i =0 ; i <DLM_HASH_BUCKETS ; i++) { bucket =dlm_master_hash (dlm, i);
fs/ocfs2/dlm/dlmrecovery.c +1 -1
@@ -451,7 +451,7 @@ static int dlm_do_recovery(struct dlm_ctxt *dlm)if (dlm->reco.dead_node ==O2NM_INVALID_NODE_NUM ) {int bit; - bit =find_next_bit (dlm->recovery_map,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (dlm->recovery_map,O2NM_MAX_NODES );if (bit >=O2NM_MAX_NODES || bit <0 )dlm_set_reco_dead_node (dlm,O2NM_INVALID_NODE_NUM );else
fs/ocfs2/dlm/dlmthread.c +1 -1
@@ -92,7 +92,7 @@ int __dlm_lockres_unused(struct dlm_lock_resource *res)return 0 ;/* Another node has this resource with this node as the master */ - bit =find_next_bit (res->refmap,O2NM_MAX_NODES ,0 ); + bit =find_first_bit (res->refmap,O2NM_MAX_NODES );if (bit <O2NM_MAX_NODES )return 0 ;
lib/genalloc.c +1 -1
@@ -251,7 +251,7 @@ void gen_pool_destroy(struct gen_pool *pool)list_del (&chunk->next_chunk); end_bit =chunk_size (chunk) >> order; - bit =find_next_bit (chunk->bits, end_bit,0 ); + bit =find_first_bit (chunk->bits, end_bit);BUG_ON (bit < end_bit);vfree (chunk);
net/ncsi/ncsi-manage.c +2 -2
@@ -608,7 +608,7 @@ static int clear_one_vid(struct ncsi_dev_priv *ndp, struct ncsi_channel *nc, bitmap = &ncf->bitmap;spin_lock_irqsave (&nc->lock, flags); - index =find_next_bit (bitmap, ncf->n_vids,0 ); + index =find_first_bit (bitmap, ncf->n_vids);if (index >= ncf->n_vids) {spin_unlock_irqrestore (&nc->lock, flags);return -1 ;
@@ -667,7 +667,7 @@ static int set_one_vid(struct ncsi_dev_priv *ndp, struct ncsi_channel *nc,return -1 ; } - index =find_next_zero_bit (bitmap, ncf->n_vids,0 ); + index =find_first_zero_bit (bitmap, ncf->n_vids);if (index <0 || index >= ncf->n_vids) { netdev_err(ndp->ndev.dev, "Channel %u already has all VLAN filters set\n",
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 8/17 tools: sync tools/bitmap with mother linux
In reply to Yury NorovRemove tools/include/asm-generic/bitops/find.h and copy include/linux/bitmap.h to tools. find_*_le() functions are not copied because not needed in tools.
---
MAINTAINERS | 2 +-
tools/include/asm-generic/bitops.h | 1 -
tools/include/linux/bitmap.h | 7 +-
.../{asm-generic/bitops => linux}/find.h | 81 +++++++++++++++++--
tools/lib/find_bit.c | 20 +++++
5 files changed, 100 insertions(+), 11 deletions(-)
rename tools/include/{asm-generic/bitops => linux}/find.h (63%)MAINTAINERS +1 -1
@@ -3277,8 +3277,8 @@ F: lib/bitmap.c F: lib/find_bit.c F: lib/find_bit_benchmark.c F: lib/test_bitmap.c -F: tools/include/asm-generic/bitops/find.h F: tools/include/linux/bitmap.h +F: tools/include/linux/find.h F: tools/lib/bitmap.c F: tools/lib/find_bit.c
tools/include/asm-generic/bitops.h +0 -1
@@ -18,7 +18,6 @@#include <asm-generic/bitops/fls.h> #include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> -#include <asm-generic/bitops/find.h> #ifndef _TOOLS_LINUX_BITOPS_H_#error only <linux/bitops.h> can be included directly
tools/include/linux/bitmap.h +4 -3
@@ -1,9 +1,10 @@/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef _PERF_BITOPS_H -#define _PERF_BITOPS_H +#ifndef _TOOLS_LINUX_BITMAP_H +#define _TOOLS_LINUX_BITMAP_H#include <string.h> #include <linux/bitops.h> +#include <linux/find.h> #include <stdlib.h> #include <linux/kernel.h>
@@ -181,4 +182,4 @@ static inline int bitmap_intersects(const unsigned long *src1, return __bitmap_intersects(src1, src2, nbits); } -#endif /* _PERF_BITOPS_H */ +#endif /* _TOOLS_LINUX_BITMAP_H */
tools/include/linux/find.h renamed from tools/include/asm-generic/bitops/find.h +75 -6
108 lines not on this page · raw message
tools/lib/find_bit.c +20 -0
@@ -96,6 +96,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) }#endif +#ifndef find_first_and_bit +/* +* Find the first set bit in two memory regions. +*/ +unsigned long _find_first_and_bit (const unsigned long *addr1, +const unsigned long *addr2, +unsigned long size) +{ +unsigned long idx, val; + +for (idx =0 ; idx *BITS_PER_LONG < size; idx++) { + val = addr1[idx] & addr2[idx]; +if (val) +return min (idx *BITS_PER_LONG +__ffs (val), size); + } + +return size; +} +#endif +#ifndef find_first_zero_bit/* * Find the first cleared bit in a memory region.
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 9/17 cpumask: replace cpumask_next_* with cpumask_first_* where appropriate
In reply to Yury Norovcpumask_first() is a more effective analogue of 'next' version if n == -1 (which means start == 0). This patch replaces 'next' with 'first' where things look trivial.
There's no cpumask_first_zero() function, so create it.
--- arch/powerpc/include/asm/cputhreads.h | 2 +- block/blk-mq.c | 2 +- drivers/net/virtio_net.c | 2 +- drivers/soc/fsl/qbman/bman_portal.c | 2 +- drivers/soc/fsl/qbman/qman_portal.c | 2 +- include/linux/cpumask.h | 16 ++++++++++++++++ kernel/time/clocksource.c | 4 ++-- 7 files changed, 23 insertions(+), 7 deletions(-)
arch/powerpc/include/asm/cputhreads.h +1 -1
@@ -52,7 +52,7 @@ static inline cpumask_t cpu_thread_mask_to_cores(const struct cpumask *threads)for (i =0 ; i <NR_CPUS ; i += threads_per_core) {cpumask_shift_left (&tmp, &threads_core_mask, i);if (cpumask_intersects (threads, &tmp)) { - cpu =cpumask_next_and (-1 , &tmp, cpu_online_mask); + cpu =cpumask_first_and (&tmp, cpu_online_mask);if (cpu < nr_cpu_ids)cpumask_set_cpu (cpu, &res); }
block/blk-mq.c +1 -1
@@ -2544,7 +2544,7 @@ static bool blk_mq_hctx_has_requests(struct blk_mq_hw_ctx *hctx)static inline bool blk_mq_last_cpu_in_hctx (unsigned int cpu,struct blk_mq_hw_ctx *hctx) { -if (cpumask_next_and (-1 , hctx->cpumask, cpu_online_mask) != cpu) +if (cpumask_first_and (hctx->cpumask, cpu_online_mask) != cpu)return false;if (cpumask_next_and (cpu, hctx->cpumask, cpu_online_mask) < nr_cpu_ids)return false;
drivers/net/virtio_net.c +1 -1
@@ -2080,7 +2080,7 @@ static void virtnet_set_affinity(struct virtnet_info *vi) stragglers = num_cpu >= vi->curr_queue_pairs ? num_cpu % vi->curr_queue_pairs :0 ; - cpu =cpumask_next (-1 , cpu_online_mask); + cpu =cpumask_first (cpu_online_mask);for (i =0 ; i < vi->curr_queue_pairs; i++) { group_size = stride + (i < stragglers ?1 :0 );
drivers/soc/fsl/qbman/bman_portal.c +1 -1
@@ -155,7 +155,7 @@ static int bman_portal_probe(struct platform_device *pdev) }spin_lock (&bman_lock); - cpu =cpumask_next_zero (-1 , &portal_cpus); + cpu =cpumask_first_zero (&portal_cpus);if (cpu >= nr_cpu_ids) { __bman_portals_probed =1 ;/* unassigned portal, skip init */
drivers/soc/fsl/qbman/qman_portal.c +1 -1
@@ -248,7 +248,7 @@ static int qman_portal_probe(struct platform_device *pdev) pcfg->pools =qm_get_pools_sdqcr ();spin_lock (&qman_lock); - cpu =cpumask_next_zero (-1 , &portal_cpus); + cpu =cpumask_first_zero (&portal_cpus);if (cpu >= nr_cpu_ids) { __qman_portals_probed =1 ;/* unassigned portal, skip init */
include/linux/cpumask.h +16 -0
@@ -123,6 +123,11 @@ static inline unsigned int cpumask_first(const struct cpumask *srcp)return 0 ; } +static inline unsigned int cpumask_first_zero (const struct cpumask *srcp) +{ +return 0 ; +} +static inline unsigned int cpumask_first_and (const struct cpumask *srcp1,const struct cpumask *srcp2) {
@@ -201,6 +206,17 @@ static inline unsigned int cpumask_first(const struct cpumask *srcp)return find_first_bit (cpumask_bits (srcp), nr_cpumask_bits); } +/** +* cpumask_first_zero - get the first unset cpu in a cpumask +* @srcp: the cpumask pointer +* +* Returns >= nr_cpu_ids if all cpus are set. +*/ +static inline unsigned int cpumask_first_zero (const struct cpumask *srcp) +{ +return find_first_zero_bit (cpumask_bits (srcp), nr_cpumask_bits); +} +/** * cpumask_first_and - return the first cpu from *srcp1 & *srcp2 * @src1p: the first input
kernel/time/clocksource.c +2 -2
@@ -262,7 +262,7 @@ static void clocksource_verify_choose_cpus(void)return ;/* Make sure to select at least one CPU other than the current CPU. */ - cpu =cpumask_next (-1 , cpu_online_mask); + cpu =cpumask_first (cpu_online_mask);if (cpu ==smp_processor_id ()) cpu =cpumask_next (cpu, cpu_online_mask);if (WARN_ON_ONCE (cpu >= nr_cpu_ids))
@@ -284,7 +284,7 @@ static void clocksource_verify_choose_cpus(void) cpu =prandom_u32 () % nr_cpu_ids; cpu =cpumask_next (cpu -1 , cpu_online_mask);if (cpu >= nr_cpu_ids) - cpu =cpumask_next (-1 , cpu_online_mask); + cpu =cpumask_first (cpu_online_mask);if (!WARN_ON_ONCE (cpu >= nr_cpu_ids))cpumask_set_cpu (cpu, &cpus_chosen); }
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 10/17 include/linux: move for_each_bit() macros from bitops.h to find.h
In reply to Yury Norovfor_each_bit() macros depend on find_bit() machinery, and so the proper place for them is the find.h header.
--- include/linux/bitops.h | 34 ---------------------------------- include/linux/find.h | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 34 insertions(+), 34 deletions(-)
include/linux/bitops.h +0 -34
@@ -32,40 +32,6 @@ extern unsigned long __sw_hweight64(__u64 w);*/ #include <asm/bitops.h> -#define for_each_set_bit (bit, addr, size) \ - for ((bit) = find_first_bit((addr), (size)); \ - (bit) < (size); \ - (bit) = find_next_bit((addr), (size), (bit) + 1)) - -/* 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) = find_next_bit((addr), (size), (bit) + 1)) - -#define for_each_clear_bit (bit, addr, size) \ - for ((bit) = find_first_zero_bit((addr), (size)); \ - (bit) < (size); \ - (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) - -/* 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) = find_next_zero_bit((addr), (size), (bit) + 1)) - -/** -* for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits -* @start: bit offset to start search and to store the current iteration offset -* @clump: location to store copy of current 8-bit clump -* @bits: bitmap address to base the search on -* @size: bitmap size in number of bits -*/ -#define for_each_set_clump8 (start, clump, bits, size) \ - for ((start) = find_first_clump8(&(clump), (bits), (size)); \ - (start) < (size); \ - (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) -static inline int get_bitmask_order (unsigned int count) {int order;
include/linux/find.h +34 -0
@@ -279,4 +279,38 @@ unsigned long find_next_bit_le(const void *addr, unsigned#error "Please fix <asm/byteorder.h>"#endif +#define for_each_set_bit (bit, addr, size) \ + for ((bit) = find_first_bit((addr), (size)); \ + (bit) < (size); \ + (bit) = find_next_bit((addr), (size), (bit) + 1)) + +/* 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) = find_next_bit((addr), (size), (bit) + 1)) + +#define for_each_clear_bit (bit, addr, size) \ + for ((bit) = find_first_zero_bit((addr), (size)); \ + (bit) < (size); \ + (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) + +/* 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) = find_next_zero_bit((addr), (size), (bit) + 1)) + +/** +* for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits +* @start: bit offset to start search and to store the current iteration offset +* @clump: location to store copy of current 8-bit clump +* @bits: bitmap address to base the search on +* @size: bitmap size in number of bits +*/ +#define for_each_set_clump8 (start, clump, bits, size) \ + for ((start) = find_first_clump8(&(clump), (bits), (size)); \ + (start) < (size); \ + (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) +#endif /*__LINUX_FIND_H_ */
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 11/17 find: micro-optimize for_each_{set,clear}_bit()
In reply to Yury NorovThe macros iterate thru all set/clear bits in a bitmap. They search a first bit using find_first_bit(), and the rest bits using find_next_bit().
Since find_next_bit() is called shortly after find_first_bit(), we can save few lines of I-cache by not using find_first_bit().
--- include/linux/find.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/find.h +2 -2
@@ -280,7 +280,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned#endif #define for_each_set_bit (bit, addr, size) \ - for ((bit) = find_first_bit((addr), (size)); \ + for ((bit) = find_next_bit((addr), (size), 0); \ (bit) < (size); \ (bit) = find_next_bit((addr), (size), (bit) + 1))
@@ -291,7 +291,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned (bit) = find_next_bit((addr), (size), (bit) + 1))#define for_each_clear_bit (bit, addr, size) \ - for ((bit) = find_first_zero_bit((addr), (size)); \ + for ((bit) = find_next_zero_bit((addr), (size), 0); \ (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
Signature · 1 line
2.30.2
Petr Mladek
maintainerRe: [PATCH 11/17] find: micro-optimize for_each_{set,clear}_bit()
Quoted 5 lines · Yury Norov
The macros iterate thru all set/clear bits in a bitmap. They search a first bit using
find_first_bit(), and the rest bits usingfind_next_bit().Since
find_next_bit()is called shortly afterfind_first_bit(), we can save few lines of I-cache by not usingfind_first_bit().
Is this only a speculation or does it fix a real performance problem?
The macro is used like:
for_each_set_bit(bit, addr, size) {
fn(bit);
}IMHO, the micro-opimization does not help when fn() is non-trivial.
include/linux/find.h unsigned long find_next_bit_le(const void *addr, unsigned · line 286
Quoted 11 lines
include/linux/find.h +1
-1@@ -280,7 +280,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned#endif #define for_each_set_bit (bit, addr, size) \ - for ((bit) = find_first_bit((addr), (size)); \ + for ((bit) = find_next_bit((addr), (size), 0); \ (bit) < (size); \ (bit) = find_next_bit((addr), (size), (bit) + 1))
It is not a big deal. I just think that the original code is slightly more self-explaining.
Best Regards,
Petr
Yury Norov
maintainerRe: [PATCH 11/17] find: micro-optimize for_each_{set,clear}_bit()
Quoted 9 lines · Petr Mladek
Quoted 5 lines · Yury Norov
The macros iterate thru all set/clear bits in a bitmap. They search a first bit using
find_first_bit(), and the rest bits usingfind_next_bit().Since
find_next_bit()is called shortly afterfind_first_bit(), we can save few lines of I-cache by not usingfind_first_bit().Is this only a speculation or does it fix a real performance problem?
Quoted 7 lines
The macro is used like:
for_each_set_bit(bit, addr, size) { fn(bit); }IMHO, the micro-opimization does not help when
fn()is non-trivial.
The effect is measurable:
Start testing for_each_bit()
for_each_set_bit: 15296 ns, 1000 iterations for_each_set_bit_from: 15225 ns, 1000 iterations
Start testing for_each_bit() with cash flushing
for_each_set_bit: 547626 ns, 1000 iterations for_each_set_bit_from: 497899 ns, 1000 iterations
Refer this:
https://www.mail-archive.com/[email protected]/msg356151.html
Thanks,
Yury
Quoted 17 lines
include/linux/find.h unsigned long find_next_bit_le(const void *addr, unsigned · line 286
Quoted 11 lines
include/linux/find.h +1
-1@@ -280,7 +280,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned#endif #define for_each_set_bit (bit, addr, size) \ - for ((bit) = find_first_bit((addr), (size)); \ + for ((bit) = find_next_bit((addr), (size), 0); \ (bit) < (size); \ (bit) = find_next_bit((addr), (size), (bit) + 1))It is not a big deal. I just think that the original code is slightly more self-explaining.
Best Regards,
Petr
Petr Mladek
maintainerRe: [PATCH 11/17] find: micro-optimize for_each_{set,clear}_bit()
Quoted 24 lines · Yury Norov
Quoted 9 lines · Petr Mladek
Quoted 5 lines · Yury Norov
The macros iterate thru all set/clear bits in a bitmap. They search a first bit using
find_first_bit(), and the rest bits usingfind_next_bit().Since
find_next_bit()is called shortly afterfind_first_bit(), we can save few lines of I-cache by not usingfind_first_bit().Is this only a speculation or does it fix a real performance problem?
Quoted 7 lines
The macro is used like:
for_each_set_bit(bit, addr, size) { fn(bit); }IMHO, the micro-opimization does not help when
fn()is non-trivial.The effect is measurable:
Start testing
for_each_bit()for_each_set_bit: 15296 ns, 1000 iterations for_each_set_bit_from: 15225 ns, 1000 iterations
Quoted 7 lines
Start testing
for_each_bit()with cash flushingfor_each_set_bit: 547626 ns, 1000 iterations for_each_set_bit_from: 497899 ns, 1000 iterationsRefer this:
https://www.mail-archive.com/[email protected]/msg356151.html
I see. The results look convincing on the first look.
But I am still not sure. This patch is basically contradicting many other patches from this patchset:
+ 5th patch optimizes find_first_and_bit() and proves that it is much faster:
Before (#define find_first_and_bit(...) find_next_and_bit(..., 0):
Start testing find_bit() with random-filled bitmap
[ 140.291468] find_first_and_bit: 46890919 ns, 32671 iterations
Start testing find_bit() with sparse bitmap
[ 140.295028] find_first_and_bit: 7103 ns, 1 iterations
After:
Start testing find_bit() with random-filled bitmap
[ 162.574907] find_first_and_bit: 25045813 ns, 32846 iterations
Start testing find_bit() with sparse bitmap
[ 162.578458] find_first_and_bit: 4900 ns, 1 iterations
=> saves 46% in random bitmap
saves 31% in sparse bitmap
+ 6th, 7th, and 9th patch makes the code use find_first_bit()
because it is faster than find_next_bit(mask, size, 0);
+ Now, 11th (this) patch replaces find_first_bit() with find_next_bit(mask, size, 0) because find_first_bit() makes things slower. It is suspicious at minimum.
By other words. The I-cache could safe 10% in one case. But find_first_bit() might safe 46% in random case.
Does I-cache cost more than the faster code?
Or was for_each_set_bit() tested only with a bitmap where find_first_bit() optimization did not help much?
How would for_each_set_bit() work with random bitmap? How does it work with larger bitmaps?
Best Regards,
Petr
Yury Norov
maintainerRe: [PATCH 11/17] find: micro-optimize for_each_{set,clear}_bit()
Quoted 60 lines · Petr Mladek
Quoted 24 lines · Yury Norov
Quoted 9 lines · Petr Mladek
Quoted 5 lines · Yury Norov
The macros iterate thru all set/clear bits in a bitmap. They search a first bit using
find_first_bit(), and the rest bits usingfind_next_bit().Since
find_next_bit()is called shortly afterfind_first_bit(), we can save few lines of I-cache by not usingfind_first_bit().Is this only a speculation or does it fix a real performance problem?
Quoted 7 lines
The macro is used like:
for_each_set_bit(bit, addr, size) { fn(bit); }IMHO, the micro-opimization does not help when
fn()is non-trivial.The effect is measurable:
Start testing
for_each_bit()for_each_set_bit: 15296 ns, 1000 iterations for_each_set_bit_from: 15225 ns, 1000 iterationsQuoted 7 lines
Start testing
for_each_bit()with cash flushingfor_each_set_bit: 547626 ns, 1000 iterations for_each_set_bit_from: 497899 ns, 1000 iterationsRefer this:
https://www.mail-archive.com/[email protected]/msg356151.html
I see. The results look convincing on the first look.
But I am still not sure. This patch is basically contradicting many other patches from this patchset:
+ 5th patch optimizes
find_first_and_bit()and proves that it is much faster:Before (#define
find_first_and_bit(...)find_next_and_bit(..., 0):
Start testingfind_bit()with random-filled bitmap
[ 140.291468]find_first_and_bit: 46890919 ns, 32671 iterations
Start testingfind_bit()with sparse bitmap
[ 140.295028]find_first_and_bit: 7103 ns, 1 iterationsAfter:
Start testingfind_bit()with random-filled bitmap
[ 162.574907]find_first_and_bit: 25045813 ns, 32846 iterations
Start testingfind_bit()with sparse bitmap
[ 162.578458]find_first_and_bit: 4900 ns, 1 iterations=> saves 46% in random bitmap
saves 31% in sparse bitmap+ 6th, 7th, and 9th patch makes the code use
find_first_bit()because it is faster than find_next_bit(mask, size, 0);
Quoted 7 lines
+ Now, 11th (this) patch replaces
find_first_bit()withfind_next_bit(mask, size, 0)becausefind_first_bit()makes things slower. It is suspicious at minimum.By other words. The I-cache could safe 10% in one case. But
find_first_bit()might safe 46% in random case.
Those are different cases. find_first_bit() is approximately twice faster than find_next_bit, and much smaller. The conclusion is simple:
use 'first' version whenever possible if there's no other considerations.
In case of for_each_bit() macros, however, we have such a consideration. In contrast to regular pattern, where user calls either first, or next versions N times, here we call find_first_bit once, and then find_next_bit N-1 times.
Because we know for sure that we'll call find_next_bit shortly, we can benefit from locality under heavy pressure on I-cache, if replace 'first' with 'next'. Consider it as a prefetch mechanism for the following calls to find_next_bit().
Quoted 1 line
Does I-cache cost more than the faster code?
In this case cache miss is more expensive.
Quoted 2 lines
Or was
for_each_set_bit()tested only with a bitmap wherefind_first_bit()optimization did not help much?
I tried to ensure that the effect of I-cache is real and in this case more important than code performance, so in the test I called 'first' once and 'next' twice.
Quoted 1 line
How would
for_each_set_bit()work with random bitmap?
It would work for all bitmaps.
Quoted 1 line
How does it work with larger bitmaps?
Percentage gain (but not absolute) will decrease proportionally to the number of calls of find_next_bit() for big N.
Thanks,
Yury
Quoted 2 lines
Best Regards,
Petr
Yury Norov
maintainerPATCH 12/17 Replace for_each_*_bit_from() with for_each_*_bit() where appropriate
In reply to Yury NorovA couple of kernel functions call for_each_*_bit_from() with start bit equal to 0. Replace them with for_each_*_bit().
No functional changes, but might improve on readability.
--- arch/x86/kernel/apic/vector.c | 4 ++-- drivers/gpu/drm/etnaviv/etnaviv_gpu.c | 4 ++-- drivers/hwmon/ltc2992.c | 3 +-- 3 files changed, 5 insertions(+), 6 deletions(-)
arch/x86/kernel/apic/vector.c +2 -2
@@ -760,9 +760,9 @@ void __init lapic_update_legacy_vectors(void)void __init lapic_assign_system_vectors (void ) { -unsigned int i, vector =0 ; +unsigned int i, vector; -for_each_set_bit_from (vector, system_vectors,NR_VECTORS ) +for_each_set_bit (vector, system_vectors,NR_VECTORS )irq_matrix_assign_system (vector_matrix, vector, false);if (nr_legacy_irqs () >1 )
drivers/gpu/drm/etnaviv/etnaviv_gpu.c +2 -2
@@ -1038,7 +1038,7 @@ int etnaviv_gpu_debugfs(struct etnaviv_gpu *gpu, struct seq_file *m)void etnaviv_gpu_recover_hang (struct etnaviv_gpu *gpu) { -unsigned int i =0 ; +unsigned int i;dev_err (gpu->dev,"recover hung GPU!\n" );
@@ -1051,7 +1051,7 @@ void etnaviv_gpu_recover_hang(struct etnaviv_gpu *gpu)/* complete all events, the GPU won't do it after the reset */ spin_lock (&gpu->event_spinlock); -for_each_set_bit_from (i, gpu->event_bitmap,ETNA_NR_EVENTS ) +for_each_set_bit (i, gpu->event_bitmap,ETNA_NR_EVENTS )complete (&gpu->event_free);bitmap_zero (gpu->event_bitmap,ETNA_NR_EVENTS );spin_unlock (&gpu->event_spinlock);
drivers/hwmon/ltc2992.c +1 -2
@@ -248,8 +248,7 @@ static int ltc2992_gpio_get_multiple(struct gpio_chip *chip, unsigned long *mask gpio_status = reg; - gpio_nr =0 ; -for_each_set_bit_from (gpio_nr, mask,LTC2992_GPIO_NR ) { +for_each_set_bit (gpio_nr, mask,LTC2992_GPIO_NR ) {if (test_bit (LTC2992_GPIO_BIT (gpio_nr), &gpio_status))set_bit (gpio_nr, bits); }
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 13/17 tools: Rename bitmap_alloc() to bitmap_zalloc()
In reply to Yury NorovFrom: Andy Shevchenko <[email protected]>
Rename bitmap_alloc() to bitmap_zalloc() in tools to follow the bitmap API in the kernel.
No functional changes intended.
--- tools/include/linux/bitmap.h | 4 ++-- tools/perf/bench/find-bit-bench.c | 2 +- tools/perf/builtin-c2c.c | 6 +++--- tools/perf/builtin-record.c | 2 +- tools/perf/tests/bitmap.c | 2 +- tools/perf/tests/mem2node.c | 2 +- tools/perf/util/affinity.c | 4 ++-- tools/perf/util/header.c | 4 ++-- tools/perf/util/metricgroup.c | 2 +- tools/perf/util/mmap.c | 4 ++-- tools/testing/selftests/kvm/dirty_log_perf_test.c | 2 +- tools/testing/selftests/kvm/dirty_log_test.c | 4 ++-- tools/testing/selftests/kvm/x86_64/vmx_dirty_log_test.c | 2 +- 13 files changed, 20 insertions(+), 20 deletions(-)
tools/include/linux/bitmap.h +2 -2
@@ -112,10 +112,10 @@ static inline int test_and_clear_bit(int nr, unsigned long *addr) }/** -* bitmap_alloc - Allocate bitmap +* bitmap_zalloc - Allocate bitmap * @nbits: Number of bits */ -static inline unsigned long *bitmap_alloc (int nbits) +static inline unsigned long *bitmap_zalloc (int nbits) {return calloc (1 ,BITS_TO_LONGS (nbits) *sizeof (unsigned long )); }
tools/perf/bench/find-bit-bench.c +1 -1
@@ -54,7 +54,7 @@ static bool asm_test_bit(long nr, const unsigned long *addr)static int do_for_each_set_bit (unsigned int num_bits) { -unsigned long *to_test =bitmap_alloc (num_bits); +unsigned long *to_test =bitmap_zalloc (num_bits);struct timeval start, end, diff;u64 runtime_us;struct stats fb_time_stats, tb_time_stats;
tools/perf/builtin-c2c.c +3 -3
@@ -139,11 +139,11 @@ static void *c2c_he_zalloc(size_t size)if (!c2c_he)return NULL ; - c2c_he->cpuset =bitmap_alloc (c2c.cpus_cnt); + c2c_he->cpuset =bitmap_zalloc (c2c.cpus_cnt);if (!c2c_he->cpuset)return NULL ; - c2c_he->nodeset =bitmap_alloc (c2c.nodes_cnt); + c2c_he->nodeset =bitmap_zalloc (c2c.nodes_cnt);if (!c2c_he->nodeset)return NULL ;
@@ -2047,7 +2047,7 @@ static int setup_nodes(struct perf_session *session)struct perf_cpu_map *map = n[node].map;unsigned long *set; - set =bitmap_alloc (c2c.cpus_cnt); + set =bitmap_zalloc (c2c.cpus_cnt);if (!set)return -ENOMEM ;
tools/perf/builtin-record.c +1 -1
@@ -2786,7 +2786,7 @@ int cmd_record(int argc, const char **argv)if (rec->opts.affinity !=PERF_AFFINITY_SYS ) { rec->affinity_mask.nbits =cpu__max_cpu (); - rec->affinity_mask.bits =bitmap_alloc (rec->affinity_mask.nbits); + rec->affinity_mask.bits =bitmap_zalloc (rec->affinity_mask.nbits);if (!rec->affinity_mask.bits) {pr_err ("Failed to allocate thread mask for %zd cpus\n" , rec->affinity_mask.nbits); err = -ENOMEM ;
tools/perf/tests/bitmap.c +1 -1
@@ -14,7 +14,7 @@ static unsigned long *get_bitmap(const char *str, int nbits)unsigned long *bm =NULL ;int i; - bm =bitmap_alloc (nbits); + bm =bitmap_zalloc (nbits);if (map && bm) {for (i =0 ; i < map->nr; i++)
tools/perf/tests/mem2node.c +1 -1
@@ -27,7 +27,7 @@ static unsigned long *get_bitmap(const char *str, int nbits)unsigned long *bm =NULL ;int i; - bm =bitmap_alloc (nbits); + bm =bitmap_zalloc (nbits);if (map && bm) {for (i =0 ; i < map->nr; i++) {
tools/perf/util/affinity.c +2 -2
@@ -25,11 +25,11 @@ int affinity__setup(struct affinity *a) {int cpu_set_size =get_cpu_set_size (); - a->orig_cpus =bitmap_alloc (cpu_set_size *8 ); + a->orig_cpus =bitmap_zalloc (cpu_set_size *8 );if (!a->orig_cpus)return -1 ;sched_getaffinity (0 , cpu_set_size, (cpu_set_t *)a->orig_cpus); - a->sched_cpus =bitmap_alloc (cpu_set_size *8 ); + a->sched_cpus =bitmap_zalloc (cpu_set_size *8 );if (!a->sched_cpus) {zfree (&a->orig_cpus);return -1 ;
tools/perf/util/header.c +2 -2
@@ -278,7 +278,7 @@ static int do_read_bitmap(struct feat_fd *ff, unsigned long **pset, u64 *psize)if (ret)return ret; - set =bitmap_alloc (size); + set =bitmap_zalloc (size);if (!set)return -ENOMEM ;
@@ -1294,7 +1294,7 @@ static int memory_node__read(struct memory_node *n, unsigned long idx) size++; - n->set =bitmap_alloc (size); + n->set =bitmap_zalloc (size);if (!n->set) {closedir (dir);return -ENOMEM ;
tools/perf/util/metricgroup.c +1 -1
@@ -313,7 +313,7 @@ static int metricgroup__setup_events(struct list_head *groups,struct evsel *evsel, *tmp;unsigned long *evlist_used; - evlist_used =bitmap_alloc (perf_evlist->core.nr_entries); + evlist_used =bitmap_zalloc (perf_evlist->core.nr_entries);if (!evlist_used)return -ENOMEM ;
tools/perf/util/mmap.c +2 -2
@@ -106,7 +106,7 @@ static int perf_mmap__aio_bind(struct mmap *map, int idx, int cpu, int affinity) data = map->aio.data[idx]; mmap_len =mmap__mmap_len (map); node_index =cpu__get_node (cpu); - node_mask =bitmap_alloc (node_index +1 ); + node_mask =bitmap_zalloc (node_index +1 );if (!node_mask) {pr_err ("Failed to allocate node mask for mbind: error %m\n" );return -1 ;
@@ -258,7 +258,7 @@ static void build_node_mask(int node, struct mmap_cpu_mask *mask)static int perf_mmap__setup_affinity_mask (struct mmap *map,struct mmap_params *mp) { map->affinity_mask.nbits =cpu__max_cpu (); - map->affinity_mask.bits =bitmap_alloc (map->affinity_mask.nbits); + map->affinity_mask.bits =bitmap_zalloc (map->affinity_mask.nbits);if (!map->affinity_mask.bits)return -1 ;
tools/testing/selftests/kvm/dirty_log_perf_test.c +1 -1
@@ -171,7 +171,7 @@ static void run_test(enum vm_guest_mode mode, void *arg) guest_num_pages = (nr_vcpus * guest_percpu_mem_size) >>vm_get_page_shift (vm); guest_num_pages =vm_adjust_num_guest_pages (mode, guest_num_pages); host_num_pages =vm_num_host_pages (mode, guest_num_pages); - bmap =bitmap_alloc (host_num_pages); + bmap =bitmap_zalloc (host_num_pages);if (dirty_log_manual_caps) { cap.cap =KVM_CAP_MANUAL_DIRTY_LOG_PROTECT2 ;
tools/testing/selftests/kvm/dirty_log_test.c +2 -2
@@ -749,8 +749,8 @@ static void run_test(enum vm_guest_mode mode, void *arg)pr_info ("guest physical test memory offset: 0x%lx\n" , guest_test_phys_mem); - bmap =bitmap_alloc (host_num_pages); - host_bmap_track =bitmap_alloc (host_num_pages); + bmap =bitmap_zalloc (host_num_pages); + host_bmap_track =bitmap_zalloc (host_num_pages);/* Add an extra memory slot for testing dirty logging */ vm_userspace_mem_region_add(vm, VM_MEM_SRC_ANONYMOUS,
tools/testing/selftests/kvm/x86_64/vmx_dirty_log_test.c +1 -1
@@ -111,7 +111,7 @@ int main(int argc, char *argv[])nested_map (vmx, vm,NESTED_TEST_MEM1 ,GUEST_TEST_MEM ,4096 );nested_map (vmx, vm,NESTED_TEST_MEM2 ,GUEST_TEST_MEM ,4096 ); - bmap =bitmap_alloc (TEST_MEM_PAGES ); + bmap =bitmap_zalloc (TEST_MEM_PAGES ); host_test_mem =addr_gpa2hva (vm,GUEST_TEST_MEM );while (!done) {
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 14/17 mm/percpu: micro-optimize pcpu_is_populated()
In reply to Yury Norovbitmap_next_clear_region() calls find_next_zero_bit() and find_next_bit() sequentially to find a range of clear bits. In case of pcpu_is_populated() there's a chance to return earlier if bitmap has all bits set.
--- mm/percpu.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-)
mm/percpu.c +8 -7
@@ -1070,17 +1070,18 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,static bool pcpu_is_populated (struct pcpu_chunk *chunk,int bit_off,int bits,int *next_off) { -unsigned int page_start, page_end, rs, re; +unsigned int start, end; - page_start =PFN_DOWN (bit_off *PCPU_MIN_ALLOC_SIZE ); - page_end =PFN_UP ((bit_off + bits) *PCPU_MIN_ALLOC_SIZE ); + start =PFN_DOWN (bit_off *PCPU_MIN_ALLOC_SIZE ); + end =PFN_UP ((bit_off + bits) *PCPU_MIN_ALLOC_SIZE ); - rs = page_start; -bitmap_next_clear_region (chunk->populated, &rs, &re, page_end); -if (rs >= page_end) + start =find_next_zero_bit (chunk->populated, end, start); +if (start >= end)return true; - *next_off = re *PAGE_SIZE /PCPU_MIN_ALLOC_SIZE ; + end =find_next_bit (chunk->populated, end, start +1 ); + + *next_off = end *PAGE_SIZE /PCPU_MIN_ALLOC_SIZE ;return false; }
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 15/17 bitmap: unify find_bit operations
In reply to Yury Norovbitmap_for_each_{set,clear}_region() are similar to for_each_bit() macros in include/linux/find.h, but interface and implementation of them are different.
This patch adds for_each_bitrange() macros and drops unused bitmap_*_region() API in sake of unification.
--- drivers/mmc/host/renesas_sdhi_core.c | 2 +- include/linux/bitmap.h | 33 ---------------- include/linux/find.h | 56 ++++++++++++++++++++++++++++ mm/percpu.c | 20 ++++------ 4 files changed, 65 insertions(+), 46 deletions(-)
drivers/mmc/host/renesas_sdhi_core.c +1 -1
@@ -647,7 +647,7 @@ static int renesas_sdhi_select_tuning(struct tmio_mmc_host *host)* is at least SH_MOBILE_SDHI_MIN_TAP_ROW probes long then use the * center index as the tap, otherwise bail out. */ -bitmap_for_each_set_region (bitmap, rs, re,0 , taps_size) { +for_each_set_bitrange (rs, re, bitmap, taps_size) {if (re - rs > tap_cnt) { tap_end = re; tap_start = rs;
include/linux/bitmap.h +0 -33
@@ -55,12 +55,6 @@ struct device;* bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above -* bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region -* bitmap_next_set_region(map, &start, &end, nbits) Find next set region -* bitmap_for_each_clear_region(map, rs, re, start, end) -* Iterate over all clear regions -* bitmap_for_each_set_region(map, rs, re, start, end) -* Iterate over all set regions * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest
@@ -459,14 +453,6 @@ static inline void bitmap_replace(unsigned long *dst,__bitmap_replace (dst, old, new, mask, nbits); } -static inline void bitmap_next_clear_region (unsigned long *bitmap, -unsigned int *rs,unsigned int *re, -unsigned int end) -{ - *rs =find_next_zero_bit (bitmap, end, *rs); - *re =find_next_bit (bitmap, end, *rs +1 ); -} -static inline void bitmap_next_set_region (unsigned long *bitmap,unsigned int *rs,unsigned int *re,unsigned int end)
@@ -475,25 +461,6 @@ static inline void bitmap_next_set_region(unsigned long *bitmap, *re =find_next_zero_bit (bitmap, end, *rs +1 ); } -/* -* Bitmap region iterators. Iterates over the bitmap between [@start, @end). -* @rs and @re should be integer variables and will be set to start and end -* index of the current clear or set region. -*/ -#define bitmap_for_each_clear_region (bitmap, rs, re, start, end) \ - for ((rs) = (start), \ - bitmap_next_clear_region((bitmap), &(rs), &(re), (end)); \ - (rs) < (re); \ - (rs) = (re) + 1, \ - bitmap_next_clear_region((bitmap), &(rs), &(re), (end))) - -#define bitmap_for_each_set_region (bitmap, rs, re, start, end) \ - for ((rs) = (start), \ - bitmap_next_set_region((bitmap), &(rs), &(re), (end)); \ - (rs) < (re); \ - (rs) = (re) + 1, \ - bitmap_next_set_region((bitmap), &(rs), &(re), (end))) -/** * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap. * @n: u64 value
include/linux/find.h +56 -0
62 lines not on this page · raw message
mm/percpu.c +8 -12
@@ -779,7 +779,7 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) {struct pcpu_block_md *block = chunk->md_blocks + index;unsigned long *alloc_map =pcpu_index_alloc_map (chunk, index); -unsigned int rs, re, start;/* region start, region end */ +unsigned int start, end;/* region start, region end */ /* promote scan_hint to contig_hint */ if (block->scan_hint) {
@@ -795,9 +795,8 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) block->right_free =0 ;/* iterate over free areas and update the contig hints */ -bitmap_for_each_clear_region (alloc_map, rs, re, start, -PCPU_BITMAP_BLOCK_BITS ) -pcpu_block_update (block, rs, re); +for_each_clear_bitrange_from (start, end, alloc_map,PCPU_BITMAP_BLOCK_BITS ) +pcpu_block_update (block, start, end); }/**
@@ -1855,13 +1854,12 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved,/* populate if not all pages are already there */ if (!is_atomic) { -unsigned int page_start, page_end, rs, re; +unsigned int page_end, rs, re; - page_start =PFN_DOWN (off); + rs =PFN_DOWN (off); page_end =PFN_UP (off + size); -bitmap_for_each_clear_region (chunk->populated, rs, re, - page_start, page_end) { +for_each_clear_bitrange_from (rs, re, chunk->populated, page_end) {WARN_ON (chunk->immutable); ret =pcpu_populate_chunk (chunk, rs, re, pcpu_gfp);
@@ -2017,8 +2015,7 @@ static void pcpu_balance_free(bool empty_only)list_for_each_entry_safe (chunk, next, &to_free, list) {unsigned int rs, re; -bitmap_for_each_set_region (chunk->populated, rs, re,0 , - chunk->nr_pages) { +for_each_set_bitrange (rs, re, chunk->populated, chunk->nr_pages) {pcpu_depopulate_chunk (chunk, rs, re);spin_lock_irq (&pcpu_lock);pcpu_chunk_depopulated (chunk, rs, re);
@@ -2088,8 +2085,7 @@ static void pcpu_balance_populated(void)continue ;/* @chunk can't go away while pcpu_alloc_mutex is held */ -bitmap_for_each_clear_region (chunk->populated, rs, re,0 , - chunk->nr_pages) { +for_each_clear_bitrange (rs, re, chunk->populated, chunk->nr_pages) {int nr =min_t (int, re - rs, nr_to_pop);spin_unlock_irq (&pcpu_lock);
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 16/17 lib: bitmap: add performance test for bitmap_print_to_pagebuf
In reply to Yury NorovFunctional tests for bitmap_print_to_pagebuf() are provided in lib/test_printf.c. This patch adds performance test for a case of fully set bitmap.
--- lib/test_bitmap.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)
lib/test_bitmap.c +37 -0
@@ -430,6 +430,42 @@ static void __init test_bitmap_parselist(void) } } +static void __init test_bitmap_printlist (void ) +{ +unsigned long *bmap =kmalloc (PAGE_SIZE ,GFP_KERNEL ); +char *buf =kmalloc (PAGE_SIZE ,GFP_KERNEL ); +char expected[256 ]; +int ret, slen; +ktime_t time; + +if (!buf || !bmap) + goto out; + +memset (bmap,-1 ,PAGE_SIZE ); + slen =snprintf (expected,256 ,"0-%ld" ,PAGE_SIZE *8 -1 ); +if (slen <0 ) + goto out; + + time =ktime_get (); + ret =bitmap_print_to_pagebuf (true, buf, bmap,PAGE_SIZE *8 ); + time =ktime_get () - time; + +if (ret != slen +1 ) { +pr_err ("bitmap_print_to_pagebuf: result is %d, expected %d\n" , ret, slen); + goto out; + } + +if (strncmp (buf, expected, slen)) { +pr_err ("bitmap_print_to_pagebuf: result is %s, expected %s\n" , buf, expected); + goto out; + } + +pr_err ("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n" , buf, time); +out: +kfree (buf); +kfree (bmap); +} +static const unsigned long parse_test[]__initconst = {BITMAP_FROM_U64 (0 ),BITMAP_FROM_U64 (1 ),
@@ -669,6 +705,7 @@ static void __init selftest(void)test_bitmap_arr32 ();test_bitmap_parse ();test_bitmap_parselist (); +test_bitmap_printlist ();test_mem_optimisations (); test_for_each_set_clump8();test_bitmap_cut ();
Signature · 1 line
2.30.2
Yury Norov
maintainerPATCH 17/17 vsprintf: rework bitmap_list_string
In reply to Yury Norovbitmap_list_string() is very ineffective when printing bitmaps with long ranges of set bits because it calls find_next_bit for each bit in the bitmap. We can do better by detecting ranges of set bits.
In my environment, before/after is 943008/31008 ns.
--- lib/vsprintf.c | 24 +++++++----------------- 1 file changed, 7 insertions(+), 17 deletions(-)
lib/vsprintf.c +7 -17
@@ -1241,20 +1241,13 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, struct printf_spec spec, const char *fmt) { int nr_bits = max_t(int, spec.field_width, 0); -/* current bit is 'cur', most recently seen range is [rbot, rtop] */ -int cur, rbot, rtop;bool first = true; +int rbot, rtop;if (check_pointer (&buf, end, bitmap, spec))return buf; - rbot = cur =find_first_bit (bitmap, nr_bits); -while (cur < nr_bits) { - rtop = cur; - cur =find_next_bit (bitmap, nr_bits, cur +1 ); -if (cur < nr_bits && cur <= rtop +1 ) -continue ; - +for_each_set_bitrange (rbot, rtop, bitmap, nr_bits) {if (!first) {if (buf < end) *buf =',' ;
@@ -1263,15 +1256,12 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, first = false; buf =number (buf, end, rbot, default_dec_spec); -if (rbot < rtop) { -if (buf < end) - *buf ='-' ; - buf++; - - buf =number (buf, end, rtop, default_dec_spec); - } +if (rtop == rbot +1 ) +continue ; - rbot = cur; +if (buf < end) + *buf ='-' ; + buf =number (++buf, end, rtop -1 , default_dec_spec); }return buf; }
Signature · 1 line
2.30.2
Re: [PATCH 17/17] vsprintf: rework bitmap_list_string
Quoted 6 lines · Yury Norov
bitmap_list_string()is very ineffective when printing bitmaps with long ranges of set bits because it callsfind_next_bitfor each bit in the bitmap. We can do better by detecting ranges of set bits.In my environment, before/after is 943008/31008 ns.
I would add a couple of words, maybe in parentheses, to describe what your environment is.
...
Quoted 1 line
+ buf =
number(++buf, end, rtop - 1, default_dec_spec);
++buf is a bit confusing here. Since you will rewrite the buf value anyway, I would write the parameter as buf + 1.
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 17/17] vsprintf: rework bitmap_list_string
Quoted 11 lines · Andy Shevchenko
Quoted 6 lines · Yury Norov
bitmap_list_string()is very ineffective when printing bitmaps with long ranges of set bits because it callsfind_next_bitfor each bit in the bitmap. We can do better by detecting ranges of set bits.In my environment, before/after is 943008/31008 ns.
I would add a couple of words, maybe in parentheses, to describe what your environment is.
Quoted 6 lines
...
Quoted 1 line
+ buf =
number(++buf, end, rtop - 1, default_dec_spec);++buf is a bit confusing here. Since you will rewrite the buf value anyway, I would write the parameter as buf + 1.
Agree, it's sloppy. I'll send the patch by tomorrow.
Re: [PATCH 17/17] vsprintf: rework bitmap_list_string
In reply to Yury NorovQuoted 8 lines · Yury Norov
bitmap_list_string()is very ineffective when printing bitmaps with long ranges of set bits because it callsfind_next_bitfor each bit in the bitmap. We can do better by detecting ranges of set bits.In my environment, before/after is 943008/31008 ns.
Signed-off-by Yury Norov <[email protected]>Tested-by Wolfram Sang <[email protected]>
I like the patch. The new code is much easier to follow. Feel free to use:
Best Regards,
Petr
Yury Norov
maintainerRe: [PATCH 17/17] vsprintf: rework bitmap_list_string
Quoted 10 lines · Petr Mladek
Quoted 8 lines · Yury Norov
bitmap_list_string()is very ineffective when printing bitmaps with long ranges of set bits because it callsfind_next_bitfor each bit in the bitmap. We can do better by detecting ranges of set bits.In my environment, before/after is 943008/31008 ns.
Signed-off-by Yury Norov <[email protected]>Tested-by Wolfram Sang <[email protected]>
Quoted 7 lines
I like the patch. The new code is much easier to follow. Feel free to use:
Reviewed-by Petr Mladek <[email protected]>Best Regards,
Petr
Thanks Petr! The patch is already in the linux-next.
Andrew, Stephen, can you please append Petr's reviewed-by?
Thanks,
Yury