2021-06-12 12:38:59

by Yury Norov

Subject: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

find_first_*_bit() is simpler and faster than 'next' version [1], and they
work identically if start == 0. But in many cases kernel code uses the
'next' version where 'first' can be used. This series addresses this issue.

Patches 1-3 move find.h under include/linux as it simplifies development.
Patches 4-8 switch the kernel and tools to find_first_*_bit() implementation
where appropriate.

Yury Norov (8):
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

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/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/um/Kconfig | 1 -
arch/xtensa/include/asm/bitops.h | 1 -
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 +-
include/asm-generic/bitops.h | 1 -
include/asm-generic/bitops/le.h | 64 --------
include/linux/bitmap.h | 1 +
include/linux/cpumask.h | 30 ++--
.../bitops => include/linux}/find.h | 149 +++++++++++++++++-
lib/Kconfig | 3 -
lib/find_bit.c | 21 +++
lib/find_bit_benchmark.c | 21 +++
lib/genalloc.c | 2 +-
net/ncsi/ncsi-manage.c | 4 +-
tools/include/asm-generic/bitops.h | 1 -
tools/include/linux/bitmap.h | 7 +-
.../bitops => tools/include/linux}/find.h | 54 +++++--
tools/lib/find_bit.c | 20 +++
60 files changed, 319 insertions(+), 185 deletions(-)
rename {tools/include/asm-generic/bitops => include/linux}/find.h (50%)
rename {include/asm-generic/bitops => tools/include/linux}/find.h (83%)

--
2.30.2

2021-06-12 12:39:07

by Yury Norov

Subject: [PATCH 5/8] lib: add find_first_and_bit()

Currently 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.)

Signed-off-by: Yury Norov <[email protected]>
---
include/linux/find.h | 27 +++++++++++++++++++++++++++
lib/find_bit.c | 21 +++++++++++++++++++++
lib/find_bit_benchmark.c | 21 +++++++++++++++++++++
3 files changed, 69 insertions(+)

diff --git a/include/linux/find.h b/include/linux/find.h
index ea57f7f38c49..6048f8c97418 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -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
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 0f8e2e369b1d..1b8e4b2a9cba 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -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.
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 5637c5711db9..db904b57d4b8 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -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);

/*
--
2.30.2

2021-06-12 12:39:29

by Yury Norov

Subject: [PATCH 7/8] all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate

find_first{,_zero}_bit is a more effective analogue of 'next' version if
start == 0. This patch replaces 'next' with 'first' where things look
trivial.

Signed-off-by: Yury Norov <[email protected]>
---
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(-)

diff --git a/arch/powerpc/platforms/pasemi/dma_lib.c b/arch/powerpc/platforms/pasemi/dma_lib.c
index 270fa3c0d372..26427311fc72 100644
--- a/arch/powerpc/platforms/pasemi/dma_lib.c
+++ b/arch/powerpc/platforms/pasemi/dma_lib.c
@@ -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))
diff --git a/arch/s390/kvm/kvm-s390.c b/arch/s390/kvm/kvm-s390.c
index 582e947675e6..68c8eb471405 100644
--- a/arch/s390/kvm/kvm-s390.c
+++ b/arch/s390/kvm/kvm-s390.c
@@ -1999,7 +1999,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;
}
diff --git a/drivers/block/rnbd/rnbd-clt.c b/drivers/block/rnbd/rnbd-clt.c
index c604a402cd5c..a0c0bfe7c060 100644
--- a/drivers/block/rnbd/rnbd-clt.c
+++ b/drivers/block/rnbd/rnbd-clt.c
@@ -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);
}
diff --git a/drivers/dma/ti/edma.c b/drivers/dma/ti/edma.c
index 35d81bd857f1..caa4050ecc02 100644
--- a/drivers/dma/ti/edma.c
+++ b/drivers/dma/ti/edma.c
@@ -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;

diff --git a/drivers/iio/adc/ad7124.c b/drivers/iio/adc/ad7124.c
index a27db78ea13e..71b174b52089 100644
--- a/drivers/iio/adc/ad7124.c
+++ b/drivers/iio/adc/ad7124.c
@@ -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;

diff --git a/drivers/infiniband/hw/irdma/hw.c b/drivers/infiniband/hw/irdma/hw.c
index 518516b9a454..9ba90b202559 100644
--- a/drivers/infiniband/hw/irdma/hw.c
+++ b/drivers/infiniband/hw/irdma/hw.c
@@ -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)
diff --git a/drivers/media/cec/core/cec-core.c b/drivers/media/cec/core/cec-core.c
index 551689d371a7..7322e7cd9753 100644
--- a/drivers/media/cec/core/cec-core.c
+++ b/drivers/media/cec/core/cec-core.c
@@ -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");
diff --git a/drivers/media/mc/mc-devnode.c b/drivers/media/mc/mc-devnode.c
index f11382afe23b..680fbb3a9340 100644
--- a/drivers/media/mc/mc-devnode.c
+++ b/drivers/media/mc/mc-devnode.c
@@ -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");
diff --git a/drivers/pci/controller/dwc/pci-dra7xx.c b/drivers/pci/controller/dwc/pci-dra7xx.c
index 047cfbdc1330..8d7ec6448d5f 100644
--- a/drivers/pci/controller/dwc/pci-dra7xx.c
+++ b/drivers/pci/controller/dwc/pci-dra7xx.c
@@ -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) {
irq = irq_find_mapping(pp->irq_domain,
(index * MAX_MSI_IRQS_PER_CTRL) + pos);
diff --git a/drivers/scsi/lpfc/lpfc_sli.c b/drivers/scsi/lpfc/lpfc_sli.c
index e2cfb86f7e61..62a917675570 100644
--- a/drivers/scsi/lpfc/lpfc_sli.c
+++ b/drivers/scsi/lpfc/lpfc_sli.c
@@ -17227,8 +17227,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;
@@ -18905,7 +18905,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 {
@@ -19548,8 +19548,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);
}


diff --git a/drivers/soc/ti/k3-ringacc.c b/drivers/soc/ti/k3-ringacc.c
index 312ba0f98ad7..573be88f8191 100644
--- a/drivers/soc/ti/k3-ringacc.c
+++ b/drivers/soc/ti/k3-ringacc.c
@@ -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;
}
diff --git a/drivers/tty/n_tty.c b/drivers/tty/n_tty.c
index 0ec93f1a61f5..0965793dfe4f 100644
--- a/drivers/tty/n_tty.c
+++ b/drivers/tty/n_tty.c
@@ -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;
diff --git a/drivers/virt/acrn/ioreq.c b/drivers/virt/acrn/ioreq.c
index 80b2e3f0e276..5ff1c53740c0 100644
--- a/drivers/virt/acrn/ioreq.c
+++ b/drivers/virt/acrn/ioreq.c
@@ -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,
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index 15cc89eef28d..f8dcd16f6b1f 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -2495,8 +2495,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;
@@ -2511,8 +2511,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;
}
diff --git a/fs/ocfs2/cluster/heartbeat.c b/fs/ocfs2/cluster/heartbeat.c
index f89ffcbd585f..a17be1618bf7 100644
--- a/fs/ocfs2/cluster/heartbeat.c
+++ b/fs/ocfs2/cluster/heartbeat.c
@@ -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)) {
diff --git a/fs/ocfs2/dlm/dlmdomain.c b/fs/ocfs2/dlm/dlmdomain.c
index 9f90fc9551e1..c4eccd499db8 100644
--- a/fs/ocfs2/dlm/dlmdomain.c
+++ b/fs/ocfs2/dlm/dlmdomain.c
@@ -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);
diff --git a/fs/ocfs2/dlm/dlmmaster.c b/fs/ocfs2/dlm/dlmmaster.c
index 9b88219febb5..227da5b1b6ab 100644
--- a/fs/ocfs2/dlm/dlmmaster.c
+++ b/fs/ocfs2/dlm/dlmmaster.c
@@ -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);
diff --git a/fs/ocfs2/dlm/dlmrecovery.c b/fs/ocfs2/dlm/dlmrecovery.c
index 0e7aad1b11cc..e24e327524f8 100644
--- a/fs/ocfs2/dlm/dlmrecovery.c
+++ b/fs/ocfs2/dlm/dlmrecovery.c
@@ -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
diff --git a/fs/ocfs2/dlm/dlmthread.c b/fs/ocfs2/dlm/dlmthread.c
index c350bd4df770..eedf07ca23ca 100644
--- a/fs/ocfs2/dlm/dlmthread.c
+++ b/fs/ocfs2/dlm/dlmthread.c
@@ -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;

diff --git a/lib/genalloc.c b/lib/genalloc.c
index 9a57257988c7..00fc50d0a640 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -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);
diff --git a/net/ncsi/ncsi-manage.c b/net/ncsi/ncsi-manage.c
index ca04b6df1341..d4b87ea30b9c 100644
--- a/net/ncsi/ncsi-manage.c
+++ b/net/ncsi/ncsi-manage.c
@@ -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",
--
2.30.2

2021-06-12 12:39:35

by Yury Norov

Subject: [PATCH 6/8] cpumask: use find_first_and_bit()

Now we have an efficient implementation for find_first_and_bit(),
so switch cpumask to use it where appropriate.

Signed-off-by: Yury Norov <[email protected]>
---
include/linux/cpumask.h | 30 ++++++++++++++++++++----------
1 file changed, 20 insertions(+), 10 deletions(-)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index bfc4690de4f4..6bee58600946 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -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
--
2.30.2

2021-06-12 12:40:19

by Yury Norov

Subject: [PATCH 3/8] include: move find.h from asm_generic to linux

find_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.

Signed-off-by: Yury Norov <[email protected]>
---
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%)

diff --git a/MAINTAINERS b/MAINTAINERS
index 88c2c4d1cfd0..1c648c18c567 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -3226,8 +3226,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
diff --git a/arch/alpha/include/asm/bitops.h b/arch/alpha/include/asm/bitops.h
index 5adca78830b5..e1d8483a45f2 100644
--- a/arch/alpha/include/asm/bitops.h
+++ b/arch/alpha/include/asm/bitops.h
@@ -430,8 +430,6 @@ static inline unsigned int __arch_hweight8(unsigned int w)

#endif /* __KERNEL__ */

-#include <asm-generic/bitops/find.h>
-
#ifdef __KERNEL__

/*
diff --git a/arch/arc/include/asm/bitops.h b/arch/arc/include/asm/bitops.h
index fb98440c0bd4..0cc24ae6a8d9 100644
--- a/arch/arc/include/asm/bitops.h
+++ b/arch/arc/include/asm/bitops.h
@@ -369,7 +369,6 @@ static inline __attribute__ ((const)) unsigned long __ffs(unsigned long x)
#include <asm-generic/bitops/sched.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-setbit.h>

diff --git a/arch/arm/include/asm/bitops.h b/arch/arm/include/asm/bitops.h
index c92e42a5c8f7..8e94fe7ab5eb 100644
--- a/arch/arm/include/asm/bitops.h
+++ b/arch/arm/include/asm/bitops.h
@@ -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>

/*
diff --git a/arch/arm64/include/asm/bitops.h b/arch/arm64/include/asm/bitops.h
index 81a3e519b07d..9b3c787132d2 100644
--- a/arch/arm64/include/asm/bitops.h
+++ b/arch/arm64/include/asm/bitops.h
@@ -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>
diff --git a/arch/csky/include/asm/bitops.h b/arch/csky/include/asm/bitops.h
index 91818787d860..9604f47bd850 100644
--- a/arch/csky/include/asm/bitops.h
+++ b/arch/csky/include/asm/bitops.h
@@ -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
diff --git a/arch/h8300/include/asm/bitops.h b/arch/h8300/include/asm/bitops.h
index c867a80cab5b..4489e3d6edd3 100644
--- a/arch/h8300/include/asm/bitops.h
+++ b/arch/h8300/include/asm/bitops.h
@@ -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>
diff --git a/arch/hexagon/include/asm/bitops.h b/arch/hexagon/include/asm/bitops.h
index 71429f756af0..75d6ba3643b8 100644
--- a/arch/hexagon/include/asm/bitops.h
+++ b/arch/hexagon/include/asm/bitops.h
@@ -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>
diff --git a/arch/ia64/include/asm/bitops.h b/arch/ia64/include/asm/bitops.h
index 2f24ee6459d2..577be93c0818 100644
--- a/arch/ia64/include/asm/bitops.h
+++ b/arch/ia64/include/asm/bitops.h
@@ -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>
diff --git a/arch/m68k/include/asm/bitops.h b/arch/m68k/include/asm/bitops.h
index 7b414099e5fc..f551a2160294 100644
--- a/arch/m68k/include/asm/bitops.h
+++ b/arch/m68k/include/asm/bitops.h
@@ -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 */
diff --git a/arch/mips/include/asm/bitops.h b/arch/mips/include/asm/bitops.h
index dc2a6234dd3c..c09d57f907f7 100644
--- a/arch/mips/include/asm/bitops.h
+++ b/arch/mips/include/asm/bitops.h
@@ -446,7 +446,6 @@ static inline int ffs(int word)
}

#include <asm-generic/bitops/ffz.h>
-#include <asm-generic/bitops/find.h>

#ifdef __KERNEL__

diff --git a/arch/openrisc/include/asm/bitops.h b/arch/openrisc/include/asm/bitops.h
index 7f1ca35213d8..d773ed938acb 100644
--- a/arch/openrisc/include/asm/bitops.h
+++ b/arch/openrisc/include/asm/bitops.h
@@ -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
diff --git a/arch/parisc/include/asm/bitops.h b/arch/parisc/include/asm/bitops.h
index aa4e883431c1..c7a9997ac9cb 100644
--- a/arch/parisc/include/asm/bitops.h
+++ b/arch/parisc/include/asm/bitops.h
@@ -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>
diff --git a/arch/powerpc/include/asm/bitops.h b/arch/powerpc/include/asm/bitops.h
index 299ab33505a6..ce2c1fa1a45d 100644
--- a/arch/powerpc/include/asm/bitops.h
+++ b/arch/powerpc/include/asm/bitops.h
@@ -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>
diff --git a/arch/riscv/include/asm/bitops.h b/arch/riscv/include/asm/bitops.h
index 396a3303c537..3540b690944b 100644
--- a/arch/riscv/include/asm/bitops.h
+++ b/arch/riscv/include/asm/bitops.h
@@ -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>

diff --git a/arch/s390/include/asm/bitops.h b/arch/s390/include/asm/bitops.h
index 68da67d2c4c9..66839f352a5e 100644
--- a/arch/s390/include/asm/bitops.h
+++ b/arch/s390/include/asm/bitops.h
@@ -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>
diff --git a/arch/sh/include/asm/bitops.h b/arch/sh/include/asm/bitops.h
index 3b6c7b5b7ec9..10ceb0d6b5a9 100644
--- a/arch/sh/include/asm/bitops.h
+++ b/arch/sh/include/asm/bitops.h
@@ -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 */
diff --git a/arch/sparc/include/asm/bitops_32.h b/arch/sparc/include/asm/bitops_32.h
index 0ceff3b915a8..889afa9f990f 100644
--- a/arch/sparc/include/asm/bitops_32.h
+++ b/arch/sparc/include/asm/bitops_32.h
@@ -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>

diff --git a/arch/sparc/include/asm/bitops_64.h b/arch/sparc/include/asm/bitops_64.h
index ca7ea5913494..005a8ae858f1 100644
--- a/arch/sparc/include/asm/bitops_64.h
+++ b/arch/sparc/include/asm/bitops_64.h
@@ -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>
diff --git a/arch/x86/include/asm/bitops.h b/arch/x86/include/asm/bitops.h
index 0367efdc5b7a..a288ecd230ab 100644
--- a/arch/x86/include/asm/bitops.h
+++ b/arch/x86/include/asm/bitops.h
@@ -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>
diff --git a/arch/xtensa/include/asm/bitops.h b/arch/xtensa/include/asm/bitops.h
index 3f71d364ba90..cd225896c40f 100644
--- a/arch/xtensa/include/asm/bitops.h
+++ b/arch/xtensa/include/asm/bitops.h
@@ -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>
diff --git a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
index df9b5bc3d282..a47b8a71d6fe 100644
--- a/include/asm-generic/bitops.h
+++ b/include/asm-generic/bitops.h
@@ -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
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index a36cfcec4e77..3f7c6731b203 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -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>
diff --git a/include/asm-generic/bitops/find.h b/include/linux/find.h
similarity index 97%
rename from include/asm-generic/bitops/find.h
rename to include/linux/find.h
index 91b1b23f2b0c..c5410c243e04 100644
--- a/include/asm-generic/bitops/find.h
+++ b/include/linux/find.h
@@ -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_ */
--
2.30.2

2021-06-12 12:40:35

by Yury Norov

Subject: [PATCH 8/8] tools: sync tools/bitmap with mother linux

Remove 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.

Signed-off-by: Yury Norov <[email protected]>
---
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%)

diff --git a/MAINTAINERS b/MAINTAINERS
index 1c648c18c567..63e81fbb59c1 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -3232,8 +3232,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

diff --git a/tools/include/asm-generic/bitops.h b/tools/include/asm-generic/bitops.h
index 5d2ab38965cc..9ab313e93555 100644
--- a/tools/include/asm-generic/bitops.h
+++ b/tools/include/asm-generic/bitops.h
@@ -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
diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h
index 330dbf7509cc..9d136fc9a8c8 100644
--- a/tools/include/linux/bitmap.h
+++ b/tools/include/linux/bitmap.h
@@ -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>

@@ -170,4 +171,4 @@ static inline int bitmap_equal(const unsigned long *src1,
return __bitmap_equal(src1, src2, nbits);
}

-#endif /* _PERF_BITOPS_H */
+#endif /* _TOOLS_LINUX_BITMAP_H */
diff --git a/tools/include/asm-generic/bitops/find.h b/tools/include/linux/find.h
similarity index 63%
rename from tools/include/asm-generic/bitops/find.h
rename to tools/include/linux/find.h
index 6481fd11012a..47e2bd6c5174 100644
--- a/tools/include/asm-generic/bitops/find.h
+++ b/tools/include/linux/find.h
@@ -1,11 +1,19 @@
/* SPDX-License-Identifier: GPL-2.0 */
-#ifndef _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_
-#define _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_
+#ifndef _TOOLS_LINUX_FIND_H_
+#define _TOOLS_LINUX_FIND_H_
+
+#ifndef _TOOLS_LINUX_BITMAP_H
+#error tools: 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,
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);

@@ -96,7 +104,6 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
#endif

#ifndef find_first_bit
-
/**
* find_first_bit - find the first set bit in a memory region
* @addr: The address to start the search at
@@ -116,11 +123,34 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)

return _find_first_bit(addr, 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);

-#endif /* find_first_bit */
+ return val ? __ffs(val) : size;
+ }

-#ifndef find_first_zero_bit
+ 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
* @addr: The address to start the search at
@@ -142,4 +172,43 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
}
#endif

-#endif /*_TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_ */
+#ifndef find_last_bit
+/**
+ * find_last_bit - find the last set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The number of bits to search
+ *
+ * Returns the bit number of the last set bit, or size.
+ */
+static inline
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+{
+ if (small_const_nbits(size)) {
+ unsigned long val = *addr & GENMASK(size - 1, 0);
+
+ return val ? __fls(val) : size;
+ }
+
+ return _find_last_bit(addr, size);
+}
+#endif
+
+/**
+ * find_next_clump8 - find next 8-bit clump with set bits in a memory region
+ * @clump: location to store copy of found clump
+ * @addr: address to base the search on
+ * @size: bitmap size in number of bits
+ * @offset: bit offset at which to start searching
+ *
+ * Returns the bit offset for the next set clump; the found clump value is
+ * copied to the location pointed by @clump. If no bits are set, returns @size.
+ */
+extern unsigned long find_next_clump8(unsigned long *clump,
+ const unsigned long *addr,
+ unsigned long size, unsigned long offset);
+
+#define find_first_clump8(clump, bits, size) \
+ find_next_clump8((clump), (bits), (size), 0)
+
+
+#endif /*__LINUX_FIND_H_ */
diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c
index 109aa7ffcf97..ba4b8d94e004 100644
--- a/tools/lib/find_bit.c
+++ b/tools/lib/find_bit.c
@@ -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.
--
2.30.2

2021-06-12 21:52:12

by Andy Shevchenko

Subject: Re: [PATCH 7/8] all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate

On Sat, Jun 12, 2021 at 3:39 PM Yury Norov <[email protected]> wrote:
>
> find_first{,_zero}_bit is a more effective analogue of 'next' version if
> start == 0. This patch replaces 'next' with 'first' where things look
> trivial.

Depending on the maintainers (but I think there will be at least few
in this case) they would like to have this be split on a per-driver
basis.
I counted 17 patches. I would split.

Since many of them are independent you may send without Cc'ing all
non-relevant people in each case.

> 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(-)


--
With Best Regards,
Andy Shevchenko

2021-06-13 00:35:55

by Yury Norov

Subject: Re: [PATCH 7/8] all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate

On Sun, Jun 13, 2021 at 12:47:31AM +0300, Andy Shevchenko wrote:
> On Sat, Jun 12, 2021 at 3:39 PM Yury Norov <[email protected]> wrote:
> >
> > find_first{,_zero}_bit is a more effective analogue of 'next' version if
> > start == 0. This patch replaces 'next' with 'first' where things look
> > trivial.
>
> Depending on the maintainers (but I think there will be at least few
> in this case) they would like to have this be split on a per-driver
> basis.
> I counted 17 patches. I would split.
>
> Since many of them are independent you may send without Cc'ing all
> non-relevant people in each case.

submitting-patches.rst says:

On the other hand, if you make a single change to numerous files,
group those changes into a single patch. Thus a single logical change
is contained within a single patch.

Also refer 96d4f267e40f9 ("Remove 'type' argument from access_ok() functioin.")

Yury

2021-06-13 23:18:42

by Yury Norov

Subject: [PATCH] cpumask: replace cpumask_next_* with cpumask_first_* where appropriate

cpumask_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.

Signed-off-by: Yury Norov <[email protected]>
---
I found another ~10 spots where people use find_next_bit() instead
of find_first_bit(). This patch should be added to the series.

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(-)

diff --git a/arch/powerpc/include/asm/cputhreads.h b/arch/powerpc/include/asm/cputhreads.h
index 98c8bd155bf9..fb5bb080e5cd 100644
--- a/arch/powerpc/include/asm/cputhreads.h
+++ b/arch/powerpc/include/asm/cputhreads.h
@@ -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);
}
diff --git a/block/blk-mq.c b/block/blk-mq.c
index 4261adee9964..99644209d693 100644
--- a/block/blk-mq.c
+++ b/block/blk-mq.c
@@ -2547,7 +2547,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;
diff --git a/drivers/net/virtio_net.c b/drivers/net/virtio_net.c
index 21ff7b9e49c2..2608e51fe6e9 100644
--- a/drivers/net/virtio_net.c
+++ b/drivers/net/virtio_net.c
@@ -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);
diff --git a/drivers/soc/fsl/qbman/bman_portal.c b/drivers/soc/fsl/qbman/bman_portal.c
index acda8a5637c5..4d7b9caee1c4 100644
--- a/drivers/soc/fsl/qbman/bman_portal.c
+++ b/drivers/soc/fsl/qbman/bman_portal.c
@@ -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 */
diff --git a/drivers/soc/fsl/qbman/qman_portal.c b/drivers/soc/fsl/qbman/qman_portal.c
index 96f74a1dc603..e23b60618c1a 100644
--- a/drivers/soc/fsl/qbman/qman_portal.c
+++ b/drivers/soc/fsl/qbman/qman_portal.c
@@ -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 */
diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 6bee58600946..7831f406cad2 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -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
diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c
index 4485635b69f5..61f429fd9c0e 100644
--- a/kernel/time/clocksource.c
+++ b/kernel/time/clocksource.c
@@ -256,7 +256,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))
@@ -278,7 +278,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);
}
--
2.30.2

2021-06-14 15:47:53

by Alexey Klimov

Subject: Re: [PATCH 5/8] lib: add find_first_and_bit()

On Sat, Jun 12, 2021 at 1:36 PM Yury Norov <[email protected]> wrote:
>
> Currently 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.)
>
> Signed-off-by: Yury Norov <[email protected]>

Tested-by: Alexey Klimov <[email protected]>

[..]

Best regards,
Alexey

2021-06-15 02:48:11

by Andrew Morton

Subject: Re: [PATCH 7/8] all: replace find_next{,_zero}_bit with find_first{,_zero}_bit where appropriate

On Sun, 13 Jun 2021 12:41:38 +0300 Andy Shevchenko <[email protected]> wrote:

> On Sunday, June 13, 2021, Yury Norov <[email protected]> wrote:
>
> > On Sun, Jun 13, 2021 at 12:47:31AM +0300, Andy Shevchenko wrote:
> > > On Sat, Jun 12, 2021 at 3:39 PM Yury Norov <[email protected]> wrote:
> > > >
> > > > find_first{,_zero}_bit is a more effective analogue of 'next' version
> > if
> > > > start == 0. This patch replaces 'next' with 'first' where things look
> > > > trivial.
> > >
> > > Depending on the maintainers (but I think there will be at least few
> > > in this case) they would like to have this be split on a per-driver
> > > basis.
> > > I counted 17 patches. I would split.
> > >
> > > Since many of them are independent you may send without Cc'ing all
> > > non-relevant people in each case.
> >
> > submitting-patches.rst says:
> >
> > On the other hand, if you make a single change to numerous files,
> > group those changes into a single patch. Thus a single logical
> > change
> > is contained within a single patch.
> >
> > Also refer 96d4f267e40f9 ("Remove 'type' argument from access_ok()
> > functioin.")
>
>
> Mixing arch and non arch is not good, fs stuff can be separated as well,
> so, at least 4 patches. Otherwise it might be not good for bissection /
> reverting.

Actually I don't have a problem taking/merging splatterpatches like
this one, as long as all relevant maintainers are cc'ed throughout.

If they review/test/ack then great. If they don't then their stuff
breaks during -rc and they get to fix it (this almost never happens
anyway).

If the splatterpatch is prepared as a series of patches then that's OK
as well. I'll queue them all up behind linux-next so I can see when
maintainers have merged them and drop the individual patches as/when
needed.

On balance... I guess individual patches is a bit better because the
more diligent maintainers will sometimes merge them and get them better
tested. But in practice, 95% of maintainers will eyeball it, say "yeah
fine" and let Andrew handle it.

2021-06-29 01:50:37

by Yury Norov

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Sat, Jun 12, 2021 at 05:36:31AM -0700, Yury Norov wrote:
> find_first_*_bit() is simpler and faster than 'next' version [1], and they
> work identically if start == 0. But in many cases kernel code uses the
> 'next' version where 'first' can be used. This series addresses this issue.
>
> Patches 1-3 move find.h under include/linux as it simplifies development.
> Patches 4-8 switch the kernel and tools to find_first_*_bit() implementation
> where appropriate.

Guys, do we have any blocker for this series? If not, I'd like to have it
merged in this window.

And this too: https://lore.kernel.org/lkml/YNirnaYw1GSxg1jK@yury-ThinkPad/T/

2021-06-29 16:22:18

by Andy Shevchenko

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Mon, Jun 28, 2021 at 06:48:20PM -0700, Yury Norov wrote:
> On Sat, Jun 12, 2021 at 05:36:31AM -0700, Yury Norov wrote:
> > find_first_*_bit() is simpler and faster than 'next' version [1], and they
> > work identically if start == 0. But in many cases kernel code uses the
> > 'next' version where 'first' can be used. This series addresses this issue.
> >
> > Patches 1-3 move find.h under include/linux as it simplifies development.
> > Patches 4-8 switch the kernel and tools to find_first_*_bit() implementation
> > where appropriate.
>
> Guys, do we have any blocker for this series? If not, I'd like to have it
> merged in this window.
>
> And this too: https://lore.kernel.org/lkml/YNirnaYw1GSxg1jK@yury-ThinkPad/T/

"This window" now equals for v5.15-rc1, hence we have a few weeks time anyway.

--
With Best Regards,
Andy Shevchenko

2021-07-28 15:05:38

by Yury Norov

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

Ping again.

The rebased series together with other bitmap patches can be found
here:

https://github.com/norov/linux/tree/bitmap-20210716

On Sat, Jun 12, 2021 at 05:36:31AM -0700, Yury Norov wrote:
> find_first_*_bit() is simpler and faster than 'next' version [1], and they
> work identically if start == 0. But in many cases kernel code uses the
> 'next' version where 'first' can be used. This series addresses this issue.
>
> Patches 1-3 move find.h under include/linux as it simplifies development.
> Patches 4-8 switch the kernel and tools to find_first_*_bit() implementation
> where appropriate.
>
> Yury Norov (8):
> 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
>
> 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/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/um/Kconfig | 1 -
> arch/xtensa/include/asm/bitops.h | 1 -
> 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 +-
> include/asm-generic/bitops.h | 1 -
> include/asm-generic/bitops/le.h | 64 --------
> include/linux/bitmap.h | 1 +
> include/linux/cpumask.h | 30 ++--
> .../bitops => include/linux}/find.h | 149 +++++++++++++++++-
> lib/Kconfig | 3 -
> lib/find_bit.c | 21 +++
> lib/find_bit_benchmark.c | 21 +++
> lib/genalloc.c | 2 +-
> net/ncsi/ncsi-manage.c | 4 +-
> tools/include/asm-generic/bitops.h | 1 -
> tools/include/linux/bitmap.h | 7 +-
> .../bitops => tools/include/linux}/find.h | 54 +++++--
> tools/lib/find_bit.c | 20 +++
> 60 files changed, 319 insertions(+), 185 deletions(-)
> rename {tools/include/asm-generic/bitops => include/linux}/find.h (50%)
> rename {include/asm-generic/bitops => tools/include/linux}/find.h (83%)
>
> --
> 2.30.2

2021-07-28 15:16:10

by Joe Perches

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Wed, 2021-07-28 at 08:00 -0700, Yury Norov wrote:
> Ping again.
>
> The rebased series together with other bitmap patches can be found
> here:
>
> https://github.com/norov/linux/tree/bitmap-20210716
[]
> > ?.../bitops => include/linux}/find.h | 149 +++++++++++++++++-

A file named find.h in a directory named bitops seems relatively sensible,
but a bitops specific file named find.h in include/linux does not.

2021-07-28 15:57:00

by Yury Norov

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Wed, Jul 28, 2021 at 08:13:32AM -0700, Joe Perches wrote:
> On Wed, 2021-07-28 at 08:00 -0700, Yury Norov wrote:
> > Ping again.
> >
> > The rebased series together with other bitmap patches can be found
> > here:
> >
> > https://github.com/norov/linux/tree/bitmap-20210716
> []
> > > ?.../bitops => include/linux}/find.h | 149 +++++++++++++++++-
>
> A file named find.h in a directory named bitops seems relatively sensible,
> but a bitops specific file named find.h in include/linux does not.

I'm OK with any name, it's not supposed to be included directly. What
do you think about bitmap_find.h, or can you suggest a better name?

2021-07-28 16:13:13

by Joe Perches

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Wed, 2021-07-28 at 08:55 -0700, Yury Norov wrote:
> On Wed, Jul 28, 2021 at 08:13:32AM -0700, Joe Perches wrote:
> > On Wed, 2021-07-28 at 08:00 -0700, Yury Norov wrote:
> > > Ping again.
> > >
> > > The rebased series together with other bitmap patches can be found
> > > here:
> > >
> > > https://github.com/norov/linux/tree/bitmap-20210716
> > []
> > > > ?.../bitops => include/linux}/find.h | 149 +++++++++++++++++-
> >
> > A file named find.h in a directory named bitops seems relatively sensible,
> > but a bitops specific file named find.h in include/linux does not.
> ?
>
> I'm OK with any name, it's not supposed to be included directly. What
> do you think about bitmap_find.h, or can you suggest a better name?

Dunno.

But I'm a bit curious about the duplicate function naming (conflicts?)
with functions in include/linux/bitmap.h

2021-07-28 16:30:39

by Yury Norov

Subject: Re: [PATCH 0/8] all: use find_next_*_bit() instead of find_first_*_bit() where possible

On Wed, Jul 28, 2021 at 09:06:18AM -0700, Joe Perches wrote:
> On Wed, 2021-07-28 at 08:55 -0700, Yury Norov wrote:
> > On Wed, Jul 28, 2021 at 08:13:32AM -0700, Joe Perches wrote:
> > > On Wed, 2021-07-28 at 08:00 -0700, Yury Norov wrote:
> > > > Ping again.
> > > >
> > > > The rebased series together with other bitmap patches can be found
> > > > here:
> > > >
> > > > https://github.com/norov/linux/tree/bitmap-20210716
> > > []
> > > > > ?.../bitops => include/linux}/find.h | 149 +++++++++++++++++-
> > >
> > > A file named find.h in a directory named bitops seems relatively sensible,
> > > but a bitops specific file named find.h in include/linux does not.
> > ?
> >
> > I'm OK with any name, it's not supposed to be included directly. What
> > do you think about bitmap_find.h, or can you suggest a better name?
>
> Dunno.
>
> But I'm a bit curious about the duplicate function naming (conflicts?)
> with functions in include/linux/bitmap.h

What names duplicate?