From: Yury Norov <yury.norov@gmail.com>
To: linux-kernel@vger.kernel.org, Yury Norov <yury.norov@gmail.com>,
"James E.J. Bottomley" <jejb@linux.ibm.com>,
"Martin K. Petersen" <martin.petersen@oracle.com>,
"Paul E. McKenney" <paulmck@kernel.org>,
"Rafael J. Wysocki" <rafael@kernel.org>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Alexey Klimov <aklimov@redhat.com>,
Amitkumar Karwar <amitkarwar@gmail.com>,
Andi Kleen <ak@linux.intel.com>, Andrew Lunn <andrew@lunn.ch>,
Andrew Morton <akpm@linux-foundation.org>,
Andy Gross <agross@kernel.org>, Andy Lutomirski <luto@kernel.org>,
Andy Shevchenko <andy@infradead.org>,
Anup Patel <anup.patel@wdc.com>, Ard Biesheuvel <ardb@kernel.org>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Arnd Bergmann <arnd@arndb.de>, Borislav Petkov <bp@alien8.de>,
Catalin Marinas <catalin.marinas@arm.com>,
Christoph Hellwig <hch@lst.de>, Christoph Lameter <cl@linux.com>,
Daniel Vetter <daniel@ffwll.ch>,
Dave Hansen <dave.hansen@linux.intel.com>,
David Airlie <airlied@linux.ie>,
David Laight <David.Laight@ACULAB.COM>,
Dennis Zhou <dennis@kernel.org>,
Dinh Nguyen <dinguyen@kernel.org>,
Geetha sowjanya <gakula@marvell.com>,
Geert Uytterhoeven <geert@linux-m68k.org>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
Guo Ren <guoren@kernel.org>, Hans de Goede <hdegoede@redhat.com>,
Heiko Carstens <hca@linux.ibm.com>,
Ian Rogers <irogers@google.com>, Ingo Molnar <mingo@redhat.com>,
Jakub Kicinski <kuba@kernel.org>,
Jason Wessel <jason.wessel@windriver.com>,
Jens Axboe <axboe@fb.com>, Jiri Olsa <jolsa@redhat.com>,
Jonathan Cameron <jic23@kernel.org>,
Juri Lelli <juri.lelli@redhat.com>,
Kalle Valo <kvalo@codeaurora.org>,
Kees Cook <keescook@chromium.org>,
Krzysztof Kozlowski <krzysztof.kozlowski@canonical.com>,
Lee Jones <lee.jones@linaro.org>, Marc Zyngier <maz@kernel.org>,
Marcin Wojtas <mw@semihalf.com>,
Mark Gross <markgross@kernel.org>,
Mark Rutland <mark.rutland@arm.com>,
Matti Vaittinen <mazziesaccount@gmail.com>,
Mauro Carvalho Chehab <mchehab@kernel.org>,
Mel Gorman <mgorman@suse.de>,
Michael Ellerman <mpe@ellerman.id.au>,
Mike Marciniszyn <mike.marciniszyn@cornelisnetworks.com>,
Nicholas Piggin <npiggin@gmail.com>,
Palmer Dabbelt <palmer@dabbelt.com>,
Peter Zijlstra <peterz@infradead.org>,
Petr Mladek <pmladek@suse.com>,
Randy Dunlap <rdunlap@infradead.org>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Roy Pledge <Roy.Pledge@nxp.com>,
Russell King <linux@armlinux.org.uk>,
Saeed Mahameed <saeedm@nvidia.com>,
Sagi Grimberg <sagi@grimberg.me>,
Sergey Senozhatsky <senozhatsky@chromium.org>,
Solomon Peachy <pizza@shaftnet.org>,
Stephen Boyd <sboyd@kernel.org>,
Stephen Rothwell <sfr@canb.auug.org.au>,
Steven Rostedt <rostedt@goodmis.org>,
Subbaraya Sundeep <sbhatta@marvell.com>,
Sudeep Holla <sudeep.holla@arm.com>,
Sunil Goutham <sgoutham@marvell.com>,
Tariq Toukan <tariqt@nvidia.com>, Tejun Heo <tj@kernel.org>,
Thomas Bogendoerfer <tsbogend@alpha.franken.de>,
Thomas Gleixner <tglx@linutronix.de>,
Ulf Hansson <ulf.hansson@linaro.org>,
Vincent Guittot <vincent.guittot@linaro.org>,
Vineet Gupta <vgupta@kernel.org>,
Viresh Kumar <viresh.kumar@linaro.org>,
Vivien Didelot <vivien.didelot@gmail.com>,
Vlastimil Babka <vbabka@suse.cz>, Will Deacon <will@kernel.org>,
bcm-kernel-feedback-list@broadcom.com, kvm@vger.kernel.org,
linux-alpha@vger.kernel.org,
linux-arm-kernel@lists.infradead.org,
linux-crypto@vger.kernel.org, linux-csky@vger.kernel.org,
linux-ia64@vger.kernel.org, linux-mips@vger.kernel.org,
linux-mm@kvack.org, linux-perf-users@vger.kernel.org,
linux-riscv@lists.infradead.org, linux-s390@vger.kernel.org,
linux-snps-arc@lists.infradead.org,
linuxppc-dev@lists.ozlabs.org
Subject: [PATCH 0/9] lib/bitmap: optimize bitmap_weight() usage
Date: Sat, 27 Nov 2021 19:56:55 -0800 [thread overview]
Message-ID: <20211128035704.270739-1-yury.norov@gmail.com> (raw)
In many cases people use bitmap_weight()-based functions like this:
if (num_present_cpus() > 1)
do_something();
This may take considerable amount of time on many-cpus machines because
num_present_cpus() will traverse every word of underlying cpumask
unconditionally.
We can significantly improve on it for many real cases if stop traversing
the mask as soon as we count present cpus to any number greater than 1:
if (num_present_cpus_gt(1))
do_something();
To implement this idea, the series adds bitmap_weight_{eq,gt,le}
functions together with corresponding wrappers in cpumask and nodemask.
Yury Norov (9):
lib/bitmap: add bitmap_weight_{eq,gt,le}
lib/bitmap: implement bitmap_{empty,full} with bitmap_weight_eq()
all: replace bitmap_weigth() with bitmap_{empty,full,eq,gt,le}
tools: sync bitmap_weight() usage with the kernel
lib/cpumask: add cpumask_weight_{eq,gt,le}
lib/nodemask: add nodemask_weight_{eq,gt,le}
lib/cpumask: add num_{possible,present,active}_cpus_{eq,gt,le}
lib/nodemask: add num_node_state_eq()
MAINTAINERS: add cpumask and nodemask files to BITMAP_API
MAINTAINERS | 4 ++
arch/alpha/kernel/process.c | 2 +-
arch/arc/kernel/smp.c | 2 +-
arch/arm/kernel/machine_kexec.c | 2 +-
arch/arm/mach-exynos/exynos.c | 2 +-
arch/arm/mm/cache-b15-rac.c | 2 +-
arch/arm64/kernel/smp.c | 2 +-
arch/arm64/mm/context.c | 2 +-
arch/csky/mm/asid.c | 2 +-
arch/csky/mm/context.c | 2 +-
arch/ia64/kernel/setup.c | 2 +-
arch/ia64/mm/tlb.c | 8 +--
arch/mips/cavium-octeon/octeon-irq.c | 4 +-
arch/mips/kernel/crash.c | 2 +-
arch/mips/kernel/i8253.c | 2 +-
arch/mips/kernel/perf_event_mipsxx.c | 4 +-
arch/mips/kernel/rtlx-cmp.c | 2 +-
arch/mips/kernel/smp.c | 4 +-
arch/mips/kernel/vpe-cmp.c | 2 +-
.../loongson2ef/common/cs5536/cs5536_mfgpt.c | 2 +-
arch/mips/mm/context.c | 2 +-
arch/mips/mm/tlbex.c | 2 +-
arch/nds32/kernel/perf_event_cpu.c | 4 +-
arch/nios2/kernel/cpuinfo.c | 2 +-
arch/powerpc/kernel/smp.c | 2 +-
arch/powerpc/kernel/watchdog.c | 4 +-
arch/powerpc/platforms/85xx/smp.c | 2 +-
arch/powerpc/platforms/pseries/hotplug-cpu.c | 4 +-
arch/powerpc/sysdev/mpic.c | 2 +-
arch/powerpc/xmon/xmon.c | 10 +--
arch/riscv/kvm/vmid.c | 2 +-
arch/s390/kernel/perf_cpum_cf.c | 2 +-
arch/sparc/kernel/mdesc.c | 6 +-
arch/x86/events/amd/core.c | 2 +-
arch/x86/kernel/alternative.c | 8 +--
arch/x86/kernel/apic/apic.c | 4 +-
arch/x86/kernel/apic/apic_flat_64.c | 2 +-
arch/x86/kernel/apic/probe_32.c | 2 +-
arch/x86/kernel/cpu/mce/dev-mcelog.c | 2 +-
arch/x86/kernel/cpu/resctrl/rdtgroup.c | 18 +++---
arch/x86/kernel/hpet.c | 2 +-
arch/x86/kernel/i8253.c | 2 +-
arch/x86/kernel/kvm.c | 2 +-
arch/x86/kernel/kvmclock.c | 2 +-
arch/x86/kernel/smpboot.c | 4 +-
arch/x86/kernel/tsc.c | 2 +-
arch/x86/kvm/hyperv.c | 8 +--
arch/x86/mm/amdtopology.c | 2 +-
arch/x86/mm/mmio-mod.c | 2 +-
arch/x86/mm/numa_emulation.c | 4 +-
arch/x86/platform/uv/uv_nmi.c | 2 +-
arch/x86/xen/smp_pv.c | 2 +-
arch/x86/xen/spinlock.c | 2 +-
drivers/acpi/numa/srat.c | 2 +-
drivers/clk/samsung/clk-exynos4.c | 2 +-
drivers/clocksource/ingenic-timer.c | 3 +-
drivers/cpufreq/pcc-cpufreq.c | 2 +-
drivers/cpufreq/qcom-cpufreq-hw.c | 2 +-
drivers/cpufreq/scmi-cpufreq.c | 2 +-
drivers/crypto/ccp/ccp-dev-v5.c | 5 +-
drivers/dma/mv_xor.c | 5 +-
drivers/firmware/psci/psci_checker.c | 2 +-
drivers/gpu/drm/i810/i810_drv.c | 2 +-
drivers/gpu/drm/i915/i915_pmu.c | 2 +-
drivers/gpu/drm/msm/disp/mdp5/mdp5_smp.c | 2 +-
drivers/hv/channel_mgmt.c | 4 +-
drivers/iio/adc/mxs-lradc-adc.c | 3 +-
drivers/iio/dummy/iio_simple_dummy_buffer.c | 4 +-
drivers/iio/industrialio-buffer.c | 2 +-
drivers/iio/industrialio-trigger.c | 2 +-
drivers/infiniband/hw/hfi1/affinity.c | 13 ++--
drivers/infiniband/hw/qib/qib_file_ops.c | 2 +-
drivers/infiniband/hw/qib/qib_iba7322.c | 2 +-
drivers/infiniband/sw/siw/siw_main.c | 3 +-
drivers/irqchip/irq-bcm6345-l1.c | 2 +-
drivers/irqchip/irq-gic.c | 2 +-
drivers/memstick/core/ms_block.c | 4 +-
drivers/net/caif/caif_virtio.c | 2 +-
drivers/net/dsa/b53/b53_common.c | 2 +-
drivers/net/ethernet/broadcom/bcmsysport.c | 6 +-
.../cavium/liquidio/cn23xx_vf_device.c | 2 +-
drivers/net/ethernet/hisilicon/hns/hns_enet.c | 2 +-
.../net/ethernet/intel/ice/ice_virtchnl_pf.c | 4 +-
.../net/ethernet/intel/ixgbe/ixgbe_sriov.c | 2 +-
.../net/ethernet/marvell/mvpp2/mvpp2_main.c | 2 +-
.../marvell/octeontx2/nic/otx2_ethtool.c | 2 +-
.../marvell/octeontx2/nic/otx2_flows.c | 8 +--
.../ethernet/marvell/octeontx2/nic/otx2_pf.c | 2 +-
drivers/net/ethernet/mellanox/mlx4/cmd.c | 10 +--
drivers/net/ethernet/mellanox/mlx4/eq.c | 4 +-
drivers/net/ethernet/mellanox/mlx4/main.c | 2 +-
.../ethernet/mellanox/mlx5/core/en_ethtool.c | 2 +-
drivers/net/ethernet/qlogic/qed/qed_dev.c | 3 +-
drivers/net/ethernet/qlogic/qed/qed_rdma.c | 4 +-
drivers/net/ethernet/qlogic/qed/qed_roce.c | 2 +-
drivers/net/wireless/ath/ath9k/hw.c | 2 +-
drivers/net/wireless/marvell/mwifiex/main.c | 4 +-
drivers/net/wireless/st/cw1200/queue.c | 3 +-
drivers/nvdimm/region.c | 2 +-
drivers/nvme/host/pci.c | 2 +-
drivers/perf/arm-cci.c | 2 +-
drivers/perf/arm_pmu.c | 6 +-
drivers/perf/hisilicon/hisi_uncore_pmu.c | 2 +-
drivers/perf/thunderx2_pmu.c | 3 +-
drivers/perf/xgene_pmu.c | 2 +-
.../intel/speed_select_if/isst_if_common.c | 6 +-
drivers/pwm/pwm-pca9685.c | 2 +-
drivers/scsi/lpfc/lpfc_init.c | 2 +-
drivers/soc/bcm/brcmstb/biuctrl.c | 2 +-
drivers/soc/fsl/dpio/dpio-service.c | 4 +-
drivers/soc/fsl/qbman/qman_test_stash.c | 2 +-
drivers/spi/spi-dw-bt1.c | 2 +-
drivers/staging/media/tegra-video/vi.c | 2 +-
drivers/thermal/intel/intel_powerclamp.c | 10 ++-
drivers/virt/acrn/hsm.c | 2 +-
fs/ocfs2/cluster/heartbeat.c | 14 ++---
fs/xfs/xfs_sysfs.c | 2 +-
include/linux/bitmap.h | 45 ++++++++++---
include/linux/cpumask.h | 55 ++++++++++++++++
include/linux/kdb.h | 2 +-
include/linux/nodemask.h | 29 +++++++++
kernel/debug/kdb/kdb_bt.c | 2 +-
kernel/irq/affinity.c | 2 +-
kernel/padata.c | 2 +-
kernel/printk/printk.c | 2 +-
kernel/rcu/tree_nocb.h | 4 +-
kernel/rcu/tree_plugin.h | 2 +-
kernel/reboot.c | 4 +-
kernel/sched/core.c | 10 +--
kernel/sched/topology.c | 4 +-
kernel/time/clockevents.c | 4 +-
kernel/time/clocksource.c | 2 +-
lib/bitmap.c | 63 +++++++++++++++++++
mm/mempolicy.c | 2 +-
mm/page_alloc.c | 2 +-
mm/percpu.c | 6 +-
mm/slab.c | 2 +-
mm/vmstat.c | 4 +-
tools/include/linux/bitmap.h | 42 ++++++++++---
tools/lib/bitmap.c | 60 ++++++++++++++++++
tools/perf/builtin-c2c.c | 4 +-
tools/perf/util/pmu.c | 2 +-
142 files changed, 490 insertions(+), 251 deletions(-)
--
2.25.1
next reply other threads:[~2021-11-28 3:59 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-11-28 3:56 Yury Norov [this message]
2021-11-28 3:56 ` [PATCH 1/9] lib/bitmap: add bitmap_weight_{eq,gt,le} Yury Norov
2021-11-28 3:56 ` [PATCH 2/9] lib/bitmap: implement bitmap_{empty,full} with bitmap_weight_eq() Yury Norov
2021-11-28 4:37 ` Michał Mirosław
2021-11-28 6:27 ` Yury Norov
2021-11-28 18:10 ` Michał Mirosław
2021-12-14 19:43 ` Yury Norov
2021-12-15 8:40 ` David Laight
2021-12-15 17:45 ` Yury Norov
2021-11-28 3:56 ` [PATCH 3/9] all: replace bitmap_weigth() with bitmap_{empty,full,eq,gt,le} Yury Norov
2021-11-28 4:47 ` Michał Mirosław
2021-11-28 8:01 ` Greg Kroah-Hartman
2021-11-28 3:56 ` [PATCH 4/9] tools: sync bitmap_weight() usage with the kernel Yury Norov
2021-11-28 3:57 ` [PATCH 5/9] lib/cpumask: add cpumask_weight_{eq,gt,le} Yury Norov
2021-11-28 3:57 ` [PATCH 6/9] lib/nodemask: add nodemask_weight_{eq,gt,le} Yury Norov
2021-11-28 3:57 ` [PATCH 7/9] lib/cpumask: add num_{possible,present,active}_cpus_{eq,gt,le} Yury Norov
2021-11-28 4:56 ` Michał Mirosław
2021-11-28 5:09 ` Michał Mirosław
2021-11-28 6:34 ` Yury Norov
2021-11-28 17:07 ` Joe Perches
2021-11-28 17:43 ` Yury Norov
2021-11-28 17:54 ` Dennis Zhou
2021-11-28 18:47 ` Yury Norov
2021-11-28 17:56 ` Emil Renner Berthing
2021-11-28 17:57 ` Joe Perches
2021-11-28 3:57 ` [PATCH 8/9] lib/nodemask: add num_node_state_eq() Yury Norov
2021-11-28 3:57 ` [PATCH 9/9] MAINTAINERS: add cpumask and nodemask files to BITMAP_API Yury Norov
2021-11-28 11:08 ` [PATCH 0/9] lib/bitmap: optimize bitmap_weight() usage Nicholas Piggin
2021-11-28 23:36 ` Yury Norov
2021-11-28 18:03 ` mirq-test
2021-11-28 18:05 ` Michał Mirosław
2021-11-29 6:38 ` Yury Norov
2021-11-29 16:34 ` Michał Mirosław
2021-12-02 0:31 ` Yury Norov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20211128035704.270739-1-yury.norov@gmail.com \
--to=yury.norov@gmail.com \
--cc=David.Laight@ACULAB.COM \
--cc=Roy.Pledge@nxp.com \
--cc=acme@kernel.org \
--cc=agross@kernel.org \
--cc=airlied@linux.ie \
--cc=ak@linux.intel.com \
--cc=aklimov@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=alexander.shishkin@linux.intel.com \
--cc=amitkarwar@gmail.com \
--cc=andrew@lunn.ch \
--cc=andy@infradead.org \
--cc=anup.patel@wdc.com \
--cc=ardb@kernel.org \
--cc=arnd@arndb.de \
--cc=axboe@fb.com \
--cc=bcm-kernel-feedback-list@broadcom.com \
--cc=bp@alien8.de \
--cc=catalin.marinas@arm.com \
--cc=cl@linux.com \
--cc=daniel@ffwll.ch \
--cc=dave.hansen@linux.intel.com \
--cc=dennis@kernel.org \
--cc=dinguyen@kernel.org \
--cc=gakula@marvell.com \
--cc=geert@linux-m68k.org \
--cc=gregkh@linuxfoundation.org \
--cc=guoren@kernel.org \
--cc=hca@linux.ibm.com \
--cc=hch@lst.de \
--cc=hdegoede@redhat.com \
--cc=irogers@google.com \
--cc=jason.wessel@windriver.com \
--cc=jejb@linux.ibm.com \
--cc=jic23@kernel.org \
--cc=jolsa@redhat.com \
--cc=juri.lelli@redhat.com \
--cc=keescook@chromium.org \
--cc=krzysztof.kozlowski@canonical.com \
--cc=kuba@kernel.org \
--cc=kvalo@codeaurora.org \
--cc=kvm@vger.kernel.org \
--cc=lee.jones@linaro.org \
--cc=linux-alpha@vger.kernel.org \
--cc=linux-arm-kernel@lists.infradead.org \
--cc=linux-crypto@vger.kernel.org \
--cc=linux-csky@vger.kernel.org \
--cc=linux-ia64@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mips@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=linux-riscv@lists.infradead.org \
--cc=linux-s390@vger.kernel.org \
--cc=linux-snps-arc@lists.infradead.org \
--cc=linux@armlinux.org.uk \
--cc=linux@rasmusvillemoes.dk \
--cc=linuxppc-dev@lists.ozlabs.org \
--cc=luto@kernel.org \
--cc=mark.rutland@arm.com \
--cc=markgross@kernel.org \
--cc=martin.petersen@oracle.com \
--cc=maz@kernel.org \
--cc=mazziesaccount@gmail.com \
--cc=mchehab@kernel.org \
--cc=mgorman@suse.de \
--cc=mike.marciniszyn@cornelisnetworks.com \
--cc=mingo@redhat.com \
--cc=mpe@ellerman.id.au \
--cc=mw@semihalf.com \
--cc=npiggin@gmail.com \
--cc=palmer@dabbelt.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=pizza@shaftnet.org \
--cc=pmladek@suse.com \
--cc=rafael@kernel.org \
--cc=rdunlap@infradead.org \
--cc=rostedt@goodmis.org \
--cc=saeedm@nvidia.com \
--cc=sagi@grimberg.me \
--cc=sbhatta@marvell.com \
--cc=sboyd@kernel.org \
--cc=senozhatsky@chromium.org \
--cc=sfr@canb.auug.org.au \
--cc=sgoutham@marvell.com \
--cc=sudeep.holla@arm.com \
--cc=tariqt@nvidia.com \
--cc=tglx@linutronix.de \
--cc=tj@kernel.org \
--cc=tsbogend@alpha.franken.de \
--cc=ulf.hansson@linaro.org \
--cc=vbabka@suse.cz \
--cc=vgupta@kernel.org \
--cc=vincent.guittot@linaro.org \
--cc=viresh.kumar@linaro.org \
--cc=vivien.didelot@gmail.com \
--cc=will@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).