* [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS
@ 2026-11-02 19:06 Mathieu Desnoyers
2026-11-02 19:06 ` [RFC PATCH v23 01/10] lib: introduce hierarchical per-cpu counters Mathieu Desnoyers
` (9 more replies)
0 siblings, 10 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:06 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Hi David,
Here is the hierarchical per-cpu counters series for the RSS counters,
based on v7.4-rc1. It is an RFC because of the questions at the end,
and because of the significant changes since v22 [1], notably the
per-cpu counter size (long -> byte), the configuration heuristics, and
the lazy activation introduced by patches 6 and 7.
The problem
-----------
Since commit f1a7941243c1 ("mm: convert mm's rss stats into
percpu_counter"), the RSS counters are struct percpu_counter with a
batch size of max(32, 2 * nr_cpus): their approximation error grows with
O(nr_cpus^2), up to 1.1GB per counter at 384 logical CPUs.
/proc/PID/status, /proc/PID/statm and the OOM killer moved to precise
sums (commits 82241a83cd15 and 5898aa8f9a0b), but the other readers
still use the approximation: the RSS high watermark (VmHWM, the
ru_maxrss reported as "Maximum resident set size" by /usr/bin/time -v,
taskstats), /proc/PID/stat (ps, top, monitoring agents), the taskstats
RSS-time integral (coremem, sampled at each tick), NUMA balancing and
the mark_victim tracepoint. On the test machine below, the
/proc/PID/stat RSS of a test process was off by 17MB while
single-threaded, and by up to 134MB with 64 threads.
Precise sums cannot fix the high watermark or the RSS-time integral:
update_hiwater_rss() samples the RSS on every unmap path, and the
integral at each tick, while a precise sum reads every possible CPU,
about 4us per counter at 384 logical CPUs. A smaller struct
percpu_counter batch takes the counter spinlock on every carry: at batch
32, an update of the counters of a shared mm costs 4.4 to 69us with one
thread per CPU, compared to 26ns to 1.2us with this series.
The series
----------
Patches 1 to 5 replace struct percpu_counter for the RSS counters with
hierarchical per-cpu counters: per-cpu bytes carry into a tree of atomic
counters shaped at boot from nr_cpu_ids, with a fixed batch of 32, an
error bound in O(n*log(n)) and no global lock. Each level carries only
once its residual reaches the batch in either direction, so updates
going back and forth around a boundary do not climb the tree. The
comparison functions have no user in this series; a follow-up will use
them for a faster OOM killer task selection.
Patches 6 and 7 keep the RSS counters of single-threaded processes exact
and without per-cpu memory: until a second thread shares the mm, the
task running on the mm adds to the bias of each counter without atomic
instructions, and other tasks add to its atomic bias, both read in O(1).
Creating the second thread allocates the per-cpu counters and tree
items, and activates the tree. struct percpu_counter cannot do this as
is: its count is an s64 under a raw spinlock, which the remote updates
(reclaim, khugepaged, remote GUP) would then take.
Patches 8 to 10 are the tools to tune the tree shape on other hardware:
the percpu_counter_tree.arity= and rss_stat_batch= boot parameters, and
a KUnit benchmark. The default shapes were measured on one machine,
with up to 384 logical CPUs, so results from other hardware are welcome.
Results
-------
2-socket AMD EPYC 9654, 192 cores, 384 logical CPUs with SMT (the CPU
counts in this letter are logical CPUs, as in nr_cpu_ids), tree 8,8,8,
batch 32, whole series; details in patches 3 and 7. The bare-metal
results were measured on v7.3: the rebase onto v7.4-rc1 had no conflict,
and the hpcc update costs of the series as sent, measured in a pinned
384-vCPU guest, match the bare-metal ones within 2%.
Accuracy per counter: bound, and largest |approximate - precise| seen
by get_mm_counter() while a process hops across all CPUs doing
mmap/munmap of 1 to 16 pages (384-vCPU KVM guest pinned to the host):
hpcc upstream
bound 158.5MB 1.1GB
measured, single-threaded 0 (exact) 841MB
measured, with a second thread 96MB 845MB
Update cost, ns per update per thread, one thread per CPU, bare metal
(mm: the 4 counters of one mm; private: one counter per thread; batch
32: local change of the benchmark, bound 46.5MB):
upstream upstream
hpcc batch 768 batch 32
mm, +1 26 288 4370
mm, random +-32 135 385 69171
mm, random +-512 1174 20229 69186
private, random +-32 31 20 -
/proc/PID/statm read with 1000 to 16000 processes, bare metal:
5.3-6.5us vs 16.5-19.0us for single-threaded processes, on par for
multi-threaded ones (14.4-16.0us vs 14.5-17.1us, guest). fork + exit
of a single-threaded child: 116us vs 139us. will-it-scale
page_fault1, 2 and 3: no regression (-0.6% to +5.1%, one boot each,
the upstream one on the previous day).
Memory per mm, counting the slab objects of mm_struct and of the tree
items, and the per-cpu memory of the RSS counters, in bytes (guest,
v7.4-rc1):
single-threaded threaded upstream
16 CPUs 1820 1948 2076
384 CPUs 1928 8145 8072
1024 CPUs 2185 17204 18569
The tree items are allocated with the per-cpu counters when the second
thread is created, and the mm_struct slab object keeps its upstream
size.
Behavior changes
----------------
- The allocation of the per-cpu counters and tree items moves from
fork() to the second thread (clone() with CLONE_VM, without
CLONE_VFORK), which can then fail with -ENOMEM.
- mm_struct gains rss_owner, the task running on the mm, compared with
current and never dereferenced, and rss_stat_mutex, which serializes
the activations of the tree, as mm_cid.mutex serializes the mode
changes of mm_cid at fork and exit.
- The precise sums (/proc/PID/status, /proc/PID/statm, the OOM killer)
take no lock: under concurrent updates of a multi-threaded process,
they can miss a carry on its way up the tree, where upstream counts
each concurrent update either whole or not at all. They are exact for
a process at rest.
- The rss_stat tracepoint reports the approximation (patch 5): exact for
single-threaded processes, within the bound otherwise.
- Like struct percpu_counter, the tree is sized at boot and not
reshaped on hotplug; its shape and bound depend on nr_cpu_ids, while
the default upstream batch follows the online CPUs.
Caveats
-------
- From 33 to 39 CPUs, up to 1.37 times less accurate than upstream.
- The tree is shaped for the number of CPUs rounded up to a power of 2:
just above a power of 2, the RSS counters of a threaded process, with
rss_owner and the mutex, use up to 1.50 times the memory of upstream
(129 CPUs, 1.28 times at 65 and 1.38 times at 257), compared to at
most 0.90 times at a power of 2, and 1.02 times at 384 logical CPUs.
- Private counters with random +-32 updates: 31ns vs 20ns, the price of
a 7 times tighter bound.
- A multi-threaded process which ran on few CPUs can hold more error
than upstream: 2047 pages per CPU path vs 767 at 384 logical CPUs. A
follow-up could index the counters by concurrency ID (mm_cid) instead
of CPU, so the accuracy bound and the precise sums would scale with
the concurrency the process uses.
- Before activation, concurrent remote updates of a single-threaded
process contend on one atomic per counter.
- The second thread allocates per-cpu memory, which the per-cpu
allocator serializes, as it does upstream at every fork: with 384
threads at once, init + destroy of 4 counters takes 874us per
operation (1004us upstream, 6.0us alone). Tree item slab objects
owning their per-cpu counters, with slab destructors, could avoid it.
- The accuracy was measured in a guest, with a debug patch and a test
program which are not part of the series. The bound is analytic and
tested in both directions.
Changes since v22 [1]
---------------------
- Per-cpu byte counters with hysteresis, updated with
this_cpu_try_cmpxchg(); the tree items of counters initialized
together share cache lines; the library allocates the per-cpu
counters and tree items, so struct percpu_counter_tree has a fixed
size of 40 bytes, like struct percpu_counter, and mm_struct no longer
embeds tree items.
- Flat tree up to 32 CPUs, 16,4 up to 64, fan-out 8 beyond, with a root
fan-out of 16 when one order remains (8,16 at 128 CPUs, 8,8,16 at
1024).
- New patches 6 and 7, for single-threaded processes.
- Fixed approximation margins in the comparison functions; hysteresis
on the intermediate levels, so the accuracy range is exact and
symmetric.
- Userspace test of every tree configuration, KUnit tests on per-CPU
workqueues, Sashiko review comments, MAINTAINERS entry.
Testing: every commit builds without warnings on x86_64 (SMP and UP),
arm64, ppc64le and 32-bit powerpc, sparse adds no warnings, KUnit passes
on bare metal (v7.3) and in guests with 1, 16 and 384 vCPUs, the
userspace test passes on simulated topologies up to 65536 CPUs, and the
RSS counters match a page table walk from 1 to 64 threads. KUnit and
the RSS check also pass with lockdep (PROVE_LOCKING) in guests with 16
and 64 vCPUs, without report.
Starting from v22, which I wrote, an LLM coding assistant drove the
implementation of this revision from my design decisions: it wrote the
code, the tests, the benchmark and the measurement scripts, ran the
measurements in guests and prepared the bare-metal ones, and drafted the
comments, the changelogs and this letter. I made the design decisions,
reviewed every change and directed the rework through my review
comments.
Questions
---------
1. Is mm->rss_owner acceptable, or would you prefer current->mm == mm
(without PF_KTHREAD) and an "activated" flag?
2. Is moving the -ENOMEM from fork() to the second thread acceptable?
3. Would you rather take the single-threaded mode first, on its own?
4. Should the rss_stat tracepoint report the approximation, stay
precise, or report both?
5. Should the tuning tools be merged, built only with the benchmark
config, or dropped later? Who could run them on non-AMD, 4-socket,
arm64 or POWER machines?
6. Is tools/testing/hpcc the right home for the topology test?
Thanks,
Mathieu
[1] https://lore.kernel.org/lkml/20260227153730.1556542-1-mathieu.desnoyers@efficios.com/
Mathieu Desnoyers (10):
lib: introduce hierarchical per-cpu counters
lib: test hierarchical per-cpu counters
mm: use hierarchical per-cpu counters for the RSS counters
tools/testing/hpcc: add userspace test of hierarchical per-CPU
counters
mm: report the approximate RSS in the rss_stat tracepoint
lib: percpu_counter_tree: add lazy tree activation
mm: keep the RSS counters of single-threaded processes exact
lib: percpu_counter_tree: add the arity boot parameter
mm: add the rss_stat_batch boot parameter
lib: add a benchmark of hierarchical per-cpu counters
.../admin-guide/kernel-parameters.txt | 24 +
Documentation/core-api/index.rst | 1 +
.../core-api/percpu-counter-tree.rst | 145 ++
MAINTAINERS | 12 +
fs/exec.c | 5 +
include/linux/mm.h | 28 +-
include/linux/mm_types.h | 19 +-
include/linux/percpu_counter_tree.h | 365 +++++
include/trace/events/kmem.h | 3 +-
init/main.c | 3 +
kernel/exit.c | 3 +
kernel/fork.c | 61 +-
lib/Kconfig | 27 +
lib/Makefile | 1 +
lib/percpu_counter_tree.c | 1450 +++++++++++++++++
lib/tests/Makefile | 3 +
lib/tests/percpu_counter_tree_bench.c | 604 +++++++
lib/tests/percpu_counter_tree_kunit.c | 1050 ++++++++++++
tools/testing/hpcc/.gitignore | 2 +
tools/testing/hpcc/Makefile | 18 +
tools/testing/hpcc/include/hpcc_shim.h | 203 +++
tools/testing/hpcc/include/kunit/visibility.h | 2 +
tools/testing/hpcc/include/linux/args.h | 4 +
tools/testing/hpcc/include/linux/atomic.h | 2 +
tools/testing/hpcc/include/linux/bug.h | 2 +
tools/testing/hpcc/include/linux/cache.h | 2 +
tools/testing/hpcc/include/linux/cpumask.h | 2 +
tools/testing/hpcc/include/linux/errno.h | 3 +
tools/testing/hpcc/include/linux/limits.h | 2 +
tools/testing/hpcc/include/linux/math.h | 2 +
.../testing/hpcc/include/linux/moduleparam.h | 12 +
tools/testing/hpcc/include/linux/percpu.h | 2 +
.../hpcc/include/linux/percpu_counter_tree.h | 2 +
tools/testing/hpcc/include/linux/preempt.h | 2 +
tools/testing/hpcc/include/linux/slab.h | 2 +
tools/testing/hpcc/main.c | 536 ++++++
36 files changed, 4592 insertions(+), 12 deletions(-)
create mode 100644 Documentation/core-api/percpu-counter-tree.rst
create mode 100644 include/linux/percpu_counter_tree.h
create mode 100644 lib/percpu_counter_tree.c
create mode 100644 lib/tests/percpu_counter_tree_bench.c
create mode 100644 lib/tests/percpu_counter_tree_kunit.c
create mode 100644 tools/testing/hpcc/.gitignore
create mode 100644 tools/testing/hpcc/Makefile
create mode 100644 tools/testing/hpcc/include/hpcc_shim.h
create mode 100644 tools/testing/hpcc/include/kunit/visibility.h
create mode 100644 tools/testing/hpcc/include/linux/args.h
create mode 100644 tools/testing/hpcc/include/linux/atomic.h
create mode 100644 tools/testing/hpcc/include/linux/bug.h
create mode 100644 tools/testing/hpcc/include/linux/cache.h
create mode 100644 tools/testing/hpcc/include/linux/cpumask.h
create mode 100644 tools/testing/hpcc/include/linux/errno.h
create mode 100644 tools/testing/hpcc/include/linux/limits.h
create mode 100644 tools/testing/hpcc/include/linux/math.h
create mode 100644 tools/testing/hpcc/include/linux/moduleparam.h
create mode 100644 tools/testing/hpcc/include/linux/percpu.h
create mode 100644 tools/testing/hpcc/include/linux/percpu_counter_tree.h
create mode 100644 tools/testing/hpcc/include/linux/preempt.h
create mode 100644 tools/testing/hpcc/include/linux/slab.h
create mode 100644 tools/testing/hpcc/main.c
base-commit: 6628e7d4c6b25c8d18f1345e3a20d21829aae7e4
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 01/10] lib: introduce hierarchical per-cpu counters
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
@ 2026-11-02 19:06 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 02/10] lib: test " Mathieu Desnoyers
` (8 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:06 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Introduce hierarchical per-cpu counters, struct percpu_counter_tree: a
split counter whose approximate sum stays within a fixed bound of its
precise sum, without taking a global lock on updates. They are meant
for counters updated from many CPUs whose approximation is read often,
such as the RSS counters of an mm. A following patch uses them for the
RSS counters, to bound their inaccuracy on large many-core systems [1].
* Motivation
The purpose of this hierarchical split-counter scheme is to:
- Minimize contention when incrementing and decrementing counters,
- Provide fast access to a sum approximation,
- Provide a sum approximation with an acceptable accuracy level when
scaling to many-core systems.
- Provide approximate and precise comparison of two counters, and
between a counter and a value.
- Provide possible precise sum ranges for a given sum approximation.
* Design
The hierarchical per-CPU counters propagate a sum approximation through an
N-way tree. When reaching the batch size, the carry is propagated up the
tree, whose fan-out at each level is selected at boot from nr_cpu_ids. The
batch size of each level is the batch size of the prior level multiplied by
the prior level's fan-out.
The following diagram illustrates the propagation with 8 CPUs through a
binary tree. This is not an actual configuration: at 8 CPUs, the
default tree is flat (see the default shapes below). CPU c propagates
into item (c & (L - 1)) of a level holding L items, so the CPUs are
listed in bit-reversed order:
Level 3: 0 (root)
| \
| \
| \
Level 2: 0 1
| \ | \
| \ | \
| \ | \
Level 1: 0 2 1 3
| \ | \ | \ | \
| \ | \ | \ | \
| \ | \ | \ | \
Level 0: 0 4 2 6 1 5 3 7
Each counter below the root keeps a residual: once it reaches its batch
size in either direction, it propagates its multiples of the batch size
and subtracts them, which leaves a residual within (-batch, +batch).
This hysteresis absorbs updates going back and forth around a batch size
boundary, instead of propagating them up to the root on each update.
The residual moves in steps of the counter's input: 1 for the per-cpu
counters, which receive the updates, and BATCH(N - 1), the batch size of
the level below, for the counters of level N, which only receive its
carries. The largest residual is therefore batch - 1 at level 0, and
BATCH(N) - BATCH(N - 1) at level N. The approximate sum is the precise
sum minus the residuals, so it is within the same distance of the
precise sum in both directions:
accuracy = nr_cpu_ids * (batch - 1) +
sum(N >= 1) (BATCH(N) - BATCH(N - 1)) * nr_items(N)
The level 0 per-cpu counters are signed bytes, updated with a
this_cpu_try_cmpxchg() loop, which limits the batch size to 128.
Up to 32 CPUs, the tree is flat: the per-cpu counters propagate directly
to the root, like struct percpu_counter. From 33 to 64 CPUs, the
per-cpu counters propagate to 4 intermediate counters, each shared by up
to 16 CPUs, so the carries of all CPUs do not contend on the root.
Beyond, each level has a fan-out of 8: a remaining order of 1 gives the
root a fan-out of 16, and a remaining order of 2 adds a level with a
fan-out of 4 below the root. With a fixed batch size, the maximum
inaccuracy grows with O(n*log(n)) as the number of CPUs increases,
compared to O(n^2) for struct percpu_counter, whose batch size grows
with the number of CPUs. For example, at 384 logical CPUs with a batch
size of 32, the bound is 40576, compared to 294528 for a struct
percpu_counter with its default batch size of 768.
* CPU hotplug
Like the per-cpu data of struct percpu_counter, the tree is sized at
boot, and is not reshaped on CPU hotplug. The level 0 residual of an
offline CPU stays in place: the precise sum still reads it, and the
bound, computed from nr_cpu_ids, still holds. Unlike the default batch
size of struct percpu_counter, which follows the number of online CPUs,
the bound does not shrink when fewer CPUs are online. When the possible
CPUs are sparse, the tree is still shaped for nr_cpu_ids, the highest
possible CPU number plus one, and the bound also counts the level 0
residuals of the missing CPUs: it holds, but cannot be reached.
* Memory Use
Each counter uses a 32-byte struct percpu_counter_tree, one byte of
per-cpu data per possible CPU, and its tree items.
percpu_counter_tree_init_many() allocates the per-cpu data and the tree
items, whose sizes depend on the number of possible CPUs and on
nr_cpu_ids, so struct percpu_counter_tree has a fixed size. The items
at the same tree position of all the counters initialized together are
packed in a cache line aligned block, so a set of counters updated
together, such as the 4 RSS counters of an mm, shares cache lines
without false sharing between CPUs updating different branches of the
tree. When the items of a tree position fit in a cache line, the tree
items come from a slab cache created by
percpu_counter_tree_subsystem_init(), which runs once the slab allocator
is up.
The memory use of nr_counters initialized together, up to 8, on a
64-bit arch with 64-byte cache lines is:
nr_counters * 32 + ALIGN(nr_counters, 4) * nr_possible_cpus
+ nr_items * 64
as the per-cpu allocator rounds sizes up to 4 bytes. The tree is shaped
for nr_cpu_ids rounded up to a power of 2: nr_items is 1 (the root) up
to 32 CPUs, 5 up to 64, 17 up to 128, 41 up to 256, 73 up to 512, 145 up
to 1024 and 585 up to 4096. In comparison, a struct percpu_counter uses
40 bytes and 4 bytes of per-cpu data per possible CPU.
For a set of 4 counters, the hierarchical counters use less memory than
as many struct percpu_counter from 3 to 64 CPUs, and beyond when the
number of CPUs is a power of 2 (at most 0.89 times as much). Between
powers of 2, fewer CPUs share the cost of the tree items: 0.94 to 1.09
times at 3 * 2^n CPUs (96, 192, 384, ...), and up to 1.47 times just
above a power of 2 (129 CPUs). A lone counter uses one item of each
cache line: 3.0 to 3.5 times the memory of a struct percpu_counter when
the number of CPUs is a power of 2 beyond 64, and up to 5.7 times just
above.
Link: https://lkml.kernel.org/r/20260227153730.1556542-1-mathieu.desnoyers@efficios.com
Link: https://lore.kernel.org/lkml/20250331223516.7810-2-sweettea-kernel@dorminy.me/ # [1]
Link: https://lkml.kernel.org/r/20260227153730.1556542-2-mathieu.desnoyers@efficios.com
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Christoph Lameter <cl@gentwo.org>
Cc: Martin Liu <liumartin@google.com>
Cc: David Rientjes <rientjes@google.com>
Cc: christian.koenig@amd.com
Cc: Shakeel Butt <shakeel.butt@linux.dev>
Cc: SeongJae Park <sj@kernel.org>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Sweet Tea Dorminy <sweettea-kernel@dorminy.me>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: Christian Brauner <brauner@kernel.org>
Cc: Wei Yang <richard.weiyang@gmail.com>
Cc: David Hildenbrand <david@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Yu Zhao <yuzhao@google.com>
Cc: Roman Gushchin <roman.gushchin@linux.dev>
Cc: Mateusz Guzik <mjguzik@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Aboorva Devarajan <aboorvad@linux.ibm.com>
Cc: David Carlier <devnexen@gmail.com>
Cc: Josh Law <objecting@objecting.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: linux-mm@kvack.org
---
Changes since v22:
- Refactor configuration table, remove duplicated definitions,
document heuristic, add table content validation, run by the KUnit
and userspace tests.
- Allocate the per-cpu counters and the tree items in
percpu_counter_tree_init_many(), instead of taking tree items from
the caller: remove percpu_counter_tree_items_size(),
PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE and the items argument of the
init functions. struct percpu_counter_tree has a fixed size of 32
bytes, down from 64.
- Call percpu_counter_tree_subsystem_init() after mm_core_init(), once
its boot parameters are parsed and slab is up, before the first
counter is used, and warn about counters initialized before it.
- Use signed bytes for the level 0 per-cpu counters, with the same
hysteresis as the intermediate levels, updated with a
this_cpu_try_cmpxchg() loop. Limit the batch size to 128.
- Pack the tree items of the counters initialized together by
percpu_counter_tree_init_many() in cache lines, allocated from a slab
cache when the items of a tree position fit in one cache line.
- Use a flat tree up to 32 CPUs, a fan-out of 16 then 4 from 33 to 64
CPUs to keep the carries of all CPUs from contending on the root, and
a fan-out of 8 beyond, with a root fan-out of 16 for a remaining order
of 1, to match the memory footprint and accuracy of struct
percpu_counter at low CPU counts and bound the inaccuracy with
O(n*log(n)) at high CPU counts.
- Print the tree shape at boot.
- Document that the accuracy range is a property of settled counters.
(Reported by Sashiko.)
- Add a diagram of the approximation ranges above compare_delta().
(Reported by Sashiko.)
- Introduce wrapped_delta(), and document that comparisons are valid
only for counters differing by less than LONG_MAX. (Reported by
Sashiko.)
- Fix the direction of the approximation margins in the comparison
functions. They were swapped, which returned wrong definitive answers
when 2^arity of a level exceeds the batch size (batch size 2 from 9
CPUs, batch size 4 from 65 CPUs).
- Add hysteresis to the intermediate tree levels: they keep a residual
within (-batch, +batch) of their level, and only propagate once it
reaches their batch size, so updates going back and forth around a
batch size boundary no longer propagate up to the root on each
update.
- Replace percpu_counter_tree_approximate_accuracy_range() and its
"under" and "over" ranges by a single accuracy, the exact bound of the
residuals, which is the same in both directions:
percpu_counter_tree_approximate_accuracy().
- Add percpu_counter_tree_check_residuals() for the tests: it checks the
residuals of the intermediate counters, and that no carry was lost
or duplicated.
- Extract the carries of the intermediate counters with a cmpxchg on
the value returned by the addition, so concurrent updaters never
subtract a carry computed from a stale residual, and explain why
relaxed ordering is sufficient.
- Read the level 0 counters with READ_ONCE() in the precise sum.
- Document that percpu_counter_tree_set() must not run concurrently
with updates.
- Add the documentation to the core-api toctree.
- Fix the propagation diagram to match the CPU to item mapping.
- Mark boot-time topology state __ro_after_init, use pr_err().
- Validate the batch size on UP as on SMP.
- Fix the sign of the !CONFIG_SMP value comparisons, and compare on
the wrapped difference as on SMP.
- Add a MAINTAINERS entry.
- Fix checkpatch warnings.
- Fix documentation typos.
---
Documentation/core-api/index.rst | 1 +
.../core-api/percpu-counter-tree.rst | 109 ++
MAINTAINERS | 9 +
include/linux/percpu_counter_tree.h | 292 +++++
init/main.c | 3 +
lib/Makefile | 1 +
lib/percpu_counter_tree.c | 1119 +++++++++++++++++
7 files changed, 1534 insertions(+)
create mode 100644 Documentation/core-api/percpu-counter-tree.rst
create mode 100644 include/linux/percpu_counter_tree.h
create mode 100644 lib/percpu_counter_tree.c
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 92f91c6a0d79..fe03cefc1734 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -48,6 +48,7 @@ Library functionality that is used throughout the kernel.
generic-radix-tree
packing
this_cpu_ops
+ percpu-counter-tree
timekeeping
errseq
wrappers/atomic_t
diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation/core-api/percpu-counter-tree.rst
new file mode 100644
index 000000000000..6b381deacd83
--- /dev/null
+++ b/Documentation/core-api/percpu-counter-tree.rst
@@ -0,0 +1,109 @@
+.. SPDX-License-Identifier: GPL-2.0+ OR MIT
+
+========================================
+The Hierarchical Per-CPU Counters (HPCC)
+========================================
+
+:Author: Mathieu Desnoyers
+
+Introduction
+============
+
+Counters come in many varieties, each with their own trade offs:
+
+ * A global atomic counter provides a fast read access to the current
+ sum, at the expense of cache-line bouncing on updates. This leads to
+ poor performance of frequent updates from various cores on large SMP
+ systems.
+
+ * A per-cpu split counter provides fast updates to per-cpu counters,
+ at the expense of a slower aggregation (sum). The sum operation needs
+ to iterate over all per-cpu counters to calculate the current total.
+
+The hierarchical per-cpu counters attempt to provide the best of both
+worlds (fast updates, and fast sum) by relaxing requirements on the sum
+accuracy. It allows quickly querying an approximated sum value, along
+with the possible min/max ranges of the associated precise sum. The
+exact precise sum can still be calculated with an iteration on all
+per-cpu counters, but the availability of an approximated sum value with
+possible precise sum min/max ranges allows eliminating candidates which
+are certainly outside of a known target range without the overhead of
+precise sums.
+
+Overview
+========
+
+The hierarchical per-cpu counters are organized as a tree with the
+per-cpu counters as its first level and the tree root as its last
+level.
+
+The intermediate tree levels contain carry propagation counters. When
+reaching a threshold (batch size), the carry is propagated up the
+tree.
+
+Each counter below the root, from the per-cpu counters up, keeps the
+residual it has not propagated yet, and only propagates once this
+residual reaches its batch size in either direction. This hysteresis
+prevents updates going back and forth around a batch size boundary from
+propagating further up the tree each time.
+
+This allows reading an approximated value at the root, which has a
+bounded accuracy determined by the tree topology and the batch size:
+the precise sum is within the same distance of the approximation in
+both directions. This bound grows as O(nr_cpus * log(nr_cpus)).
+
+The per-cpu counters are bytes, which limits the batch size to 128. The
+tree positions are cache line aligned to prevent false sharing between
+CPUs updating different branches of the tree. A tree position holds the
+items of all the counter trees initialized together by
+percpu_counter_tree_init_many(), so a set of counters updated together,
+such as the RSS counters of an mm, shares cache lines.
+percpu_counter_tree_init_many() allocates the per-cpu counters, one per
+possible CPU, and the tree items, whose number depends on nr_cpu_ids, so
+struct percpu_counter_tree has a fixed size.
+
+The fan-out of each tree level is selected at boot from nr_cpu_ids, the
+highest possible CPU number plus one.
+
+The bounded accuracy is a property of the settled tree. While updates are
+in flight the transient error can exceed it, bounded by the number of
+updaters and their increment size.
+
+Likewise, the precise sum is exact when no update runs concurrently. It
+takes no lock: an update which carries from the per-cpu counter to the
+upper levels can be counted in part, the residual it left below read and
+its carry missed on the way up.
+
+Use Cases
+=========
+
+Use cases HPCC is meant to handle involve tracking resources which are
+used across many CPUs to quickly sum as feedback for decision making to
+apply throttling, quota limits, sort tasks, and perform memory or task
+migration decisions. When considering approximated sums within the
+accuracy range of the decision threshold, the user can either:
+
+ * Be conservative and fast: Consider that the sum has reached the
+ limit as soon as the given limit is within the approximation range.
+
+ * Be aggressive and fast: Consider that the sum is over the
+ limit only when the approximation range is over the given limit.
+
+ * Be precise and slow: Do a precise comparison with the limit, which
+ requires a precise sum when the limit is within the approximated
+ range.
+
+One use-case for these hierarchical counters is to implement a two-pass
+algorithm to speed up picking a maximum/minimum sum value from
+a set. A first pass compares the approximated values, and then a second
+pass only needs the precise sum for counter trees which are within the
+possible precise sum range of the counter tree chosen by the first pass.
+
+Because the comparison is on the wrapped difference, it is not transitive:
+ordering is undefined over a set of counters spanning more than LONG_MAX.
+
+Functions and structures
+========================
+
+.. kernel-doc:: include/linux/percpu_counter_tree.h
+.. kernel-doc:: lib/percpu_counter_tree.c
diff --git a/MAINTAINERS b/MAINTAINERS
index 93abbb315065..712af0536005 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -11947,6 +11947,15 @@ L: linux-input@vger.kernel.org
S: Maintained
F: drivers/hid/hid-logitech-hidpp.c
+HIERARCHICAL PER-CPU COUNTERS (HPCC)
+M: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+L: linux-mm@kvack.org
+L: linux-kernel@vger.kernel.org
+S: Supported
+F: Documentation/core-api/percpu-counter-tree.rst
+F: include/linux/percpu_counter_tree.h
+F: lib/percpu_counter_tree.c
+
HIGH-RESOLUTION TIMERS, TIMER WHEEL, CLOCKEVENTS
M: Anna-Maria Behnsen <anna-maria@linutronix.de>
M: Frederic Weisbecker <frederic@kernel.org>
diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_counter_tree.h
new file mode 100644
index 000000000000..741a6877aa99
--- /dev/null
+++ b/include/linux/percpu_counter_tree.h
@@ -0,0 +1,292 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* SPDX-FileCopyrightText: 2025-2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> */
+
+#ifndef _PERCPU_COUNTER_TREE_H
+#define _PERCPU_COUNTER_TREE_H
+
+#include <linux/bug.h>
+#include <linux/atomic.h>
+#include <linux/limits.h>
+#include <linux/percpu.h>
+
+/* Largest batch size: level 0 residuals are within (-batch, +batch) of a signed byte. */
+#define PERCPU_COUNTER_TREE_MAX_BATCH 128
+static_assert(PERCPU_COUNTER_TREE_MAX_BATCH - 1 <= S8_MAX);
+
+#ifdef CONFIG_SMP
+
+struct percpu_counter_tree {
+ /*
+ * Per-CPU split counters (tree level 0): residuals not propagated
+ * yet, within (-batch, +batch).
+ */
+ s8 __percpu *level0;
+ /*
+ * The batch size is the increment step at level 0 which triggers a
+ * carry propagation: a power of 2 between 2 and
+ * PERCPU_COUNTER_TREE_MAX_BATCH. It is stored next to level0, the
+ * other field read by the update fast path, so both usually share a
+ * cache line: this leaves a hole before items_stride.
+ */
+ unsigned char batch_order;
+ unsigned int items_stride; /* Distance between this counter's consecutive items. */
+ /*
+ * Approximate sum: this counter's item of the root, in the tree
+ * items allocated with the per-CPU counters.
+ */
+ atomic_long_t *approx_sum;
+ long bias; /* Bias to apply to counter precise and approximate values. */
+};
+
+int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size,
+ gfp_t gfp_flags);
+int percpu_counter_tree_init(struct percpu_counter_tree *counter,
+ unsigned long batch_size, gfp_t gfp_flags);
+void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters);
+void percpu_counter_tree_destroy(struct percpu_counter_tree *counter);
+void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc);
+long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter);
+int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b);
+int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tree *counter, long v);
+int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b);
+int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *counter, long v);
+void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v);
+int percpu_counter_tree_subsystem_init(void);
+
+/**
+ * percpu_counter_tree_approximate_sum() - Return approximate counter sum.
+ * @counter: The counter to sum.
+ *
+ * Querying the approximate sum is fast, but it is only accurate within
+ * the bound returned by percpu_counter_tree_approximate_accuracy().
+ * This is meant to be used when speed is preferred over accuracy.
+ *
+ * Return: The current approximate counter sum.
+ */
+static inline
+long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *counter)
+{
+ unsigned long v = atomic_long_read(counter->approx_sum);
+
+ return (long)(v + (unsigned long)READ_ONCE(counter->bias));
+}
+
+unsigned long percpu_counter_tree_approximate_accuracy(struct percpu_counter_tree *counter);
+
+#if IS_ENABLED(CONFIG_KUNIT)
+unsigned int percpu_counter_tree_check_config(void);
+unsigned int percpu_counter_tree_check_residuals(struct percpu_counter_tree *counter);
+void percpu_counter_tree_copy_state(struct percpu_counter_tree *dst,
+ struct percpu_counter_tree *src);
+#endif
+
+#else /* !CONFIG_SMP */
+
+struct percpu_counter_tree {
+ atomic_long_t count;
+};
+
+static inline
+int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size,
+ gfp_t gfp_flags)
+{
+ /*
+ * There is no tree to batch into on UP, so @batch_size has no
+ * effect. Validate it anyway so callers get the same result as
+ * on SMP.
+ */
+ if (WARN_ON(batch_size <= 1 || (batch_size & (batch_size - 1)) ||
+ batch_size > PERCPU_COUNTER_TREE_MAX_BATCH))
+ return -EINVAL;
+ for (unsigned int i = 0; i < nr_counters; i++)
+ atomic_long_set(&counters[i].count, 0);
+ return 0;
+}
+
+static inline
+int percpu_counter_tree_init(struct percpu_counter_tree *counter,
+ unsigned long batch_size, gfp_t gfp_flags)
+{
+ return percpu_counter_tree_init_many(counter, 1, batch_size, gfp_flags);
+}
+
+static inline
+void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters)
+{
+}
+
+static inline
+void percpu_counter_tree_destroy(struct percpu_counter_tree *counter)
+{
+}
+
+static inline
+long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter)
+{
+ return atomic_long_read(&counter->count);
+}
+
+static inline
+int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b)
+{
+ /* Compare on the wrapped difference, as on SMP. */
+ long delta = (long)((unsigned long)percpu_counter_tree_precise_sum(a) -
+ (unsigned long)percpu_counter_tree_precise_sum(b));
+
+ if (delta < 0)
+ return -1;
+ if (delta > 0)
+ return 1;
+ return 0;
+}
+
+static inline
+int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *counter, long v)
+{
+ /* Compare on the wrapped difference, as on SMP. */
+ long delta = (long)((unsigned long)v -
+ (unsigned long)percpu_counter_tree_precise_sum(counter));
+
+ if (delta < 0)
+ return -1;
+ if (delta > 0)
+ return 1;
+ return 0;
+}
+
+static inline
+int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b)
+{
+ return percpu_counter_tree_precise_compare(a, b);
+}
+
+static inline
+int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tree *counter, long v)
+{
+ return percpu_counter_tree_precise_compare_value(counter, v);
+}
+
+static inline
+void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v)
+{
+ atomic_long_set(&counter->count, v);
+}
+
+static inline
+unsigned long percpu_counter_tree_approximate_accuracy(struct percpu_counter_tree *counter)
+{
+ return 0;
+}
+
+static inline
+void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
+{
+ atomic_long_add(inc, &counter->count);
+}
+
+static inline
+long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *counter)
+{
+ return percpu_counter_tree_precise_sum(counter);
+}
+
+static inline
+int percpu_counter_tree_subsystem_init(void)
+{
+ return 0;
+}
+
+#endif /* CONFIG_SMP */
+
+/**
+ * percpu_counter_tree_approximate_sum_positive() - Return a positive approximate counter sum.
+ * @counter: The counter to sum.
+ *
+ * Return an approximate counter sum which is guaranteed to be greater
+ * or equal to 0.
+ *
+ * Return: The current positive approximate counter sum.
+ */
+static inline
+long percpu_counter_tree_approximate_sum_positive(struct percpu_counter_tree *counter)
+{
+ long v = percpu_counter_tree_approximate_sum(counter);
+
+ return v > 0 ? v : 0;
+}
+
+/**
+ * percpu_counter_tree_precise_sum_positive() - Return a positive precise counter sum.
+ * @counter: The counter to sum.
+ *
+ * Return a precise counter sum which is guaranteed to be greater
+ * or equal to 0.
+ *
+ * Return: The current positive precise counter sum.
+ */
+static inline
+long percpu_counter_tree_precise_sum_positive(struct percpu_counter_tree *counter)
+{
+ long v = percpu_counter_tree_precise_sum(counter);
+
+ return v > 0 ? v : 0;
+}
+
+/**
+ * percpu_counter_tree_approximate_min_max_range() - Return the min and max precise values.
+ * @approx_sum: Approximated sum.
+ * @accuracy: Tree accuracy, from percpu_counter_tree_approximate_accuracy().
+ * @precise_min: Minimum possible value for precise sum (output).
+ * @precise_max: Maximum possible value for precise sum (output).
+ *
+ * Calculate the minimum and maximum precise values for a given approximation
+ * and accuracy. The accuracy is a bound on a settled tree: one with no update
+ * in progress.
+ *
+ * The approximation is within the accuracy of the precise sum, in both
+ * directions:
+ *
+ * precise_sum - accuracy <= approx_sum <= precise_sum + accuracy
+ *
+ * Therefore, the precise sum is within the accuracy of the approximation:
+ *
+ * approx_sum - accuracy <= precise_sum <= approx_sum + accuracy
+ */
+static inline
+void percpu_counter_tree_approximate_min_max_range(long approx_sum, unsigned long accuracy,
+ long *precise_min, long *precise_max)
+{
+ *precise_min = approx_sum - accuracy;
+ *precise_max = approx_sum + accuracy;
+}
+
+/**
+ * percpu_counter_tree_approximate_min_max() - Return the approximation, min and max precise values.
+ * @counter: The counter to sum.
+ * @approx_sum: Approximate sum (output).
+ * @precise_min: Minimum possible value for precise sum (output).
+ * @precise_max: Maximum possible value for precise sum (output).
+ *
+ * Return the approximate sum, minimum and maximum precise values for
+ * a counter.
+ */
+static inline
+void percpu_counter_tree_approximate_min_max(struct percpu_counter_tree *counter,
+ long *approx_sum, long *precise_min, long *precise_max)
+{
+ unsigned long accuracy = percpu_counter_tree_approximate_accuracy(counter);
+ long v = percpu_counter_tree_approximate_sum(counter);
+
+ percpu_counter_tree_approximate_min_max_range(v, accuracy, precise_min, precise_max);
+ *approx_sum = v;
+}
+
+#endif /* _PERCPU_COUNTER_TREE_H */
diff --git a/init/main.c b/init/main.c
index 7b0c8c34e6a9..d9614cc5bd63 100644
--- a/init/main.c
+++ b/init/main.c
@@ -108,6 +108,7 @@
#include <linux/time_namespace.h>
#include <linux/unaligned.h>
#include <linux/vdso_datastore.h>
+#include <linux/percpu_counter_tree.h>
#include <net/net_namespace.h>
#include <asm/io.h>
@@ -1104,6 +1105,8 @@ void start_kernel(void)
sort_main_extable();
trap_init();
mm_core_init();
+ /* After parsing its boot parameters and setting up slab, before the first counter. */
+ percpu_counter_tree_subsystem_init();
maple_tree_init();
poking_init();
ftrace_init();
diff --git a/lib/Makefile b/lib/Makefile
index a2afe954805c..07410b1d20a3 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -182,6 +182,7 @@ obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o
obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o
obj-$(CONFIG_SMP) += percpu_counter.o
+obj-$(CONFIG_SMP) += percpu_counter_tree.o
obj-$(CONFIG_AUDIT_GENERIC) += audit.o
obj-$(CONFIG_AUDIT_COMPAT_GENERIC) += compat_audit.o
diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c
new file mode 100644
index 000000000000..67cdb22c3786
--- /dev/null
+++ b/lib/percpu_counter_tree.c
@@ -0,0 +1,1119 @@
+// SPDX-License-Identifier: GPL-2.0+ OR MIT
+// SPDX-FileCopyrightText: 2025-2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+
+/*
+ * Split Counters With Tree Approximation Propagation
+ *
+ * * Overview
+ *
+ * Each counter is a tree of counters. A CPU updates its own level 0
+ * counter, a signed byte. Each counter keeps the residual it has not
+ * propagated yet, and propagates a carry to its parent on the next level
+ * once that residual reaches the batch size of its level, up to the root.
+ * Most updates therefore stay on the updating CPU. The root holds the
+ * approximate sum, read in O(1), and the precise sum adds the residuals of
+ * all levels to it.
+ *
+ * * Tree shape
+ *
+ * Illustration with 8 CPUs and a fan-out of 2 at each level, which makes
+ * 3 levels of counters below the root. This is not an actual
+ * configuration: at 8 CPUs, the default tree is flat.
+ *
+ * Level 3: 0 (root)
+ * | \
+ * | \
+ * | \
+ * Level 2: 0 1
+ * | \ | \
+ * | \ | \
+ * | \ | \
+ * Level 1: 0 2 1 3
+ * | \ | \ | \ | \
+ * | \ | \ | \ | \
+ * | \ | \ | \ | \
+ * Level 0: 0 4 2 6 1 5 3 7
+ *
+ * CPU c propagates into item (c & (L - 1)) of a level holding L items,
+ * so the CPUs sharing an item are not adjacent: CPUs 0 and 4 share
+ * level 1 item 0, and CPUs 0, 2, 4, 6 share level 2 item 0. This mapping
+ * uses every item of each level and gives each item the same number of
+ * CPUs, give or take one, even when nr_cpu_ids is not a power of 2. The
+ * diagram lists the CPUs in bit-reversed order to avoid crossing lines.
+ *
+ * The actual fan-out of each level depends on the topology (see
+ * per_nr_cpu_order_config): up to 32 CPUs, the tree is flat, and the
+ * level 0 counters propagate directly to the root.
+ *
+ * * Batch sizes and residuals
+ *
+ * The batch size of a level, BATCH(level N), is the batch size of the
+ * level below multiplied by the fan-out of that level. Example for
+ * BATCH(level 0) = 32, with the tree of the illustration above:
+ *
+ * BATCH(level 0) = 32
+ * BATCH(level 1) = 64
+ * BATCH(level 2) = 128
+ *
+ * Once the residual of a counter reaches +/- BATCH(level N), it propagates
+ * its multiples of BATCH(level N), truncated toward zero, and subtracts
+ * them. This hysteresis prevents updates going back and forth around a
+ * BATCH(level N) boundary from propagating up the tree each time.
+ *
+ * The residual of a settled counter therefore stays within
+ * (-BATCH(level N), +BATCH(level N)), and moves in steps of the counter's
+ * input: level 0 receives the updates, in steps of 1, while a counter
+ * above level 0 only receives the carries of the level below, in steps of
+ * BATCH(level N - 1). The largest residual of a counter is the largest
+ * multiple of its input step below its batch size: BATCH(level 0) - 1 at
+ * level 0, and BATCH(level N) - BATCH(level N - 1) above:
+ *
+ * input residual worst case worst case
+ * step per counter below precise above precise
+ * Level 0: 1 [-31 .. 31] 248 (8 * 31) 248 (8 * 31)
+ * Level 1: 32 {-32, 0, 32} 128 (4 * 32) 128 (4 * 32)
+ * Level 2: 64 {-64, 0, 64} 128 (2 * 64) 128 (2 * 64)
+ * Total: 504 504
+ *
+ * * Approximation accuracy
+ *
+ * The approximate sum is the precise sum minus the residuals, so a
+ * settled counter (no update in progress) is within:
+ *
+ * precise - 504 <= approx <= precise + 504
+ *
+ * The accuracy returned by percpu_counter_tree_approximate_accuracy() is
+ * exact. It adds the largest residuals of all the counters:
+ * BATCH(level 0) - 1 for each of the nr_cpu_ids level 0 counters, and
+ * BATCH(level N) - BATCH(level N - 1) for each counter of level N above.
+ * Counting each level 0 counter as one BATCH(level 0), minus its input
+ * step of 1:
+ *
+ * accuracy_multiplier = nr_cpu_ids + sum over levels N >= 1 of
+ * (number of counters at level N) *
+ * (BATCH(level N) - BATCH(level N - 1)) / BATCH(level 0)
+ *
+ * accuracy = BATCH(level 0) * accuracy_multiplier - nr_cpu_ids
+ *
+ * In the example above, accuracy_multiplier = 8 + 4 * 1 + 2 * 2 = 16, and:
+ *
+ * accuracy = 32 * 16 - 8 = 504
+ *
+ * Every counter above level 0 is reachable from a CPU below nr_cpu_ids,
+ * even when nr_cpu_ids is not a power of 2, so both bounds can be reached
+ * when the possible CPUs are contiguous. When they are sparse, the bound
+ * also counts the level 0 residuals of the missing CPUs: it holds, but
+ * cannot be reached.
+ *
+ * * Carry propagation
+ *
+ * The items at each tree position of the counters initialized together
+ * share cache lines, which are not shared with other tree positions to
+ * prevent false sharing between CPUs.
+ *
+ * Example with expanded values, for the tree and batch sizes above:
+ *
+ * counter_add(counter, inc):
+ *
+ * if (!inc)
+ * return;
+ *
+ * // Level 0: per-CPU residual within (-32, +32).
+ * old = percpu_read(counter @ Level 0);
+ * do {
+ * v = old + inc;
+ * out = v < 0 ? -(-v & ~0b00011111) : (v & ~0b00011111);
+ * } while (!percpu_try_cmpxchg(counter @ Level 0, &old, v - out));
+ * inc = out;
+ * if (!inc)
+ * return;
+ *
+ * // Levels 1 and 2: add the carry, then extract the multiples
+ * // of the level batch held by the counter, truncated toward
+ * // zero. A failed cmpxchg updates res to the current residual.
+ * res = atomic_long_add_return(counter @ Level 1, inc);
+ * do {
+ * inc = res < 0 ? -(-res & ~0b00111111) : (res & ~0b00111111);
+ * if (!inc)
+ * return;
+ * } while (!atomic_long_try_cmpxchg(counter @ Level 1, &res, res - inc));
+ *
+ * res = atomic_long_add_return(counter @ Level 2, inc);
+ * do {
+ * inc = res < 0 ? -(-res & ~0b01111111) : (res & ~0b01111111);
+ * if (!inc)
+ * return;
+ * } while (!atomic_long_try_cmpxchg(counter @ Level 2, &res, res - inc));
+ *
+ * atomic_long_add(counter @ Level 3, inc);
+ */
+
+#define pr_fmt(fmt) "percpu_counter_tree: " fmt
+
+#include <linux/percpu_counter_tree.h>
+#include <linux/align.h>
+#include <linux/cache.h>
+#include <linux/cpumask.h>
+#include <linux/atomic.h>
+#include <linux/export.h>
+#include <linux/percpu.h>
+#include <linux/errno.h>
+#include <linux/slab.h>
+#include <linux/math.h>
+#include <linux/log2.h>
+#include <linux/args.h>
+#include <kunit/visibility.h>
+
+#define MAX_NR_LEVELS 7
+
+/*
+ * The counter configuration is selected at boot time based on the
+ * hardware topology.
+ */
+struct counter_config {
+ /*
+ * nr_levels is the number of hierarchical counter tree levels. It
+ * excludes the final level (approximate sum).
+ */
+ unsigned char nr_levels;
+ /* n-arity of each level from 0 to (nr_levels - 1). */
+ unsigned char n_arity_order[MAX_NR_LEVELS];
+};
+
+/*
+ * The fan-out of each level of the tree is chosen with a heuristic trying to
+ * minimize both the tree depth and the fan-out.
+ */
+#define PCT_COUNTER_CONFIG(order, ...) \
+ [order] = { \
+ .nr_levels = COUNT_ARGS(__VA_ARGS__), \
+ .n_arity_order = { __VA_ARGS__ }, \
+ }
+
+/*
+ * Up to 32 CPUs, the tree is flat: the level 0 counters propagate directly
+ * to the root, like struct percpu_counter. From 33 to 64 CPUs, the level 0
+ * counters propagate to 4 intermediate counters, each shared by up to 16
+ * CPUs, so the carries of all CPUs do not contend on the root. Beyond, each
+ * level has a fan-out of 8. When the order is not a multiple of 3, a
+ * remaining order of 1 gives the root a fan-out of 16, and a remaining
+ * order of 2 adds a level with a fan-out of 4 below the root: a root
+ * fan-out of 16 updates about as fast as a fan-out of 2 below the root,
+ * with one level less, which shrinks the accuracy bound and the tree
+ * items, while a root fan-out of 32 is slower than a fan-out of 4 below
+ * it. This keeps the carry rate reaching each tree item low with the RSS
+ * batch size of 32, and the approximation error grows as
+ * O(nr_cpus * log(nr_cpus)), compared to O(nr_cpus^2) for struct
+ * percpu_counter whose batch size grows with the number of CPUs.
+ *
+ * The tree is shaped for nr_cpu_ids rounded up to a power of 2, and each
+ * tree position takes a cache line. A set of 4 counters initialized together,
+ * such as the RSS counters of an mm, uses less memory than 4 struct
+ * percpu_counter from a few CPUs up to 64, and beyond when nr_cpu_ids is a
+ * power of 2 (at most 0.89 times as much). Between powers of 2, fewer CPUs
+ * share the cost of the tree items: up to 1.1 times at 3 * 2^n CPUs, and
+ * up to 1.48 times just above a power of 2. A lone counter uses one item
+ * of each cache line: 3.0 to 3.5 times the memory of a struct
+ * percpu_counter when nr_cpu_ids is a power of 2 beyond 64, and up to 5.7
+ * times just above.
+ */
+static const struct counter_config per_nr_cpu_order_config[] = {
+ PCT_COUNTER_CONFIG(0),
+ PCT_COUNTER_CONFIG(1, 1),
+ PCT_COUNTER_CONFIG(2, 2),
+ PCT_COUNTER_CONFIG(3, 3),
+ PCT_COUNTER_CONFIG(4, 4),
+ PCT_COUNTER_CONFIG(5, 5),
+ PCT_COUNTER_CONFIG(6, 4, 2),
+ PCT_COUNTER_CONFIG(7, 3, 4),
+ PCT_COUNTER_CONFIG(8, 3, 2, 3),
+ PCT_COUNTER_CONFIG(9, 3, 3, 3),
+ PCT_COUNTER_CONFIG(10, 3, 3, 4),
+ PCT_COUNTER_CONFIG(11, 3, 3, 2, 3),
+ PCT_COUNTER_CONFIG(12, 3, 3, 3, 3),
+ PCT_COUNTER_CONFIG(13, 3, 3, 3, 4),
+ PCT_COUNTER_CONFIG(14, 3, 3, 3, 2, 3),
+ PCT_COUNTER_CONFIG(15, 3, 3, 3, 3, 3),
+ PCT_COUNTER_CONFIG(16, 3, 3, 3, 3, 4),
+ PCT_COUNTER_CONFIG(17, 3, 3, 3, 3, 2, 3),
+ PCT_COUNTER_CONFIG(18, 3, 3, 3, 3, 3, 3),
+ PCT_COUNTER_CONFIG(19, 3, 3, 3, 3, 3, 4),
+ PCT_COUNTER_CONFIG(20, 3, 3, 3, 3, 3, 2, 3),
+};
+
+#undef PCT_COUNTER_CONFIG
+
+/* The configuration table covers every possible number of CPUs. */
+#define MAX_NR_CPUS_ORDER 20
+#if NR_CPUS > (1UL << MAX_NR_CPUS_ORDER)
+#error "NR_CPUS exceeds the hierarchical counter configuration table"
+#endif
+static_assert(ARRAY_SIZE(per_nr_cpu_order_config) == MAX_NR_CPUS_ORDER + 1);
+
+/* Tree topology, selected at boot and shared by all the counters. */
+static struct {
+ /* Hierarchical counter configuration for the hardware topology. */
+ const struct counter_config *config;
+ /* Order of nr_cpu_ids. */
+ unsigned int nr_cpus_order;
+ /*
+ * Tree items per counter, including the root. UINT_MAX catches early
+ * boot misuses.
+ */
+ unsigned int nr_items;
+ /*
+ * Largest residuals of all the counters, in units of the level 0
+ * batch size: see percpu_counter_tree_accuracy().
+ */
+ unsigned long accuracy_multiplier;
+ /* Tree items when those of a tree position fit in one cache line. */
+ struct kmem_cache *items_cachep;
+} tree_topology __ro_after_init = {
+ .nr_items = UINT_MAX,
+};
+
+/*
+ * Size of the items of one tree position for the counters initialized
+ * together by percpu_counter_tree_init_many(), packed in cache lines which
+ * are not shared with other tree positions. Each item is the residual of
+ * the carries received and not propagated yet, within (-batch, +batch) of
+ * its tree level when settled. The items of a tree position are updated
+ * by the same CPUs, so packing them does not add contention between
+ * unrelated CPUs.
+ */
+static
+size_t percpu_counter_tree_position_size(unsigned int nr_counters)
+{
+ return ALIGN(nr_counters * sizeof(atomic_long_t), SMP_CACHE_BYTES);
+}
+
+/* Distance between the consecutive items of each of @nr_counters counters. */
+static inline
+unsigned int percpu_counter_tree_items_stride(unsigned int nr_counters)
+{
+ return percpu_counter_tree_position_size(nr_counters) / sizeof(atomic_long_t);
+}
+
+/* Allocate the zeroed tree items of @nr_counters counters, the root last. */
+static
+atomic_long_t *percpu_counter_tree_alloc_items(unsigned int nr_counters, gfp_t gfp_flags)
+{
+ size_t position_size = percpu_counter_tree_position_size(nr_counters);
+
+ if (position_size == SMP_CACHE_BYTES)
+ return kmem_cache_zalloc(tree_topology.items_cachep, gfp_flags);
+ /* kmalloc() aligns power of 2 sizes on their size. */
+ return kzalloc(roundup_pow_of_two(tree_topology.nr_items * position_size),
+ gfp_flags);
+}
+
+static
+void percpu_counter_tree_free_items(atomic_long_t *items, unsigned int nr_counters)
+{
+ if (percpu_counter_tree_position_size(nr_counters) == SMP_CACHE_BYTES)
+ kmem_cache_free(tree_topology.items_cachep, items);
+ else
+ kfree(items);
+}
+
+static
+int __percpu_counter_tree_init(struct percpu_counter_tree *counter,
+ unsigned long batch_size,
+ s8 __percpu *level0,
+ atomic_long_t *items, unsigned int items_stride)
+{
+ /* Batch size must be greater than 1, a power of 2, and fit in a byte. */
+ if (WARN_ON(batch_size <= 1 || (batch_size & (batch_size - 1)) ||
+ batch_size > PERCPU_COUNTER_TREE_MAX_BATCH))
+ return -EINVAL;
+ counter->batch_order = ilog2(batch_size);
+ counter->bias = 0;
+ counter->level0 = level0;
+ counter->items_stride = items_stride;
+ /* The root is the last item. */
+ counter->approx_sum = &items[(tree_topology.nr_items - 1) * items_stride];
+ return 0;
+}
+
+static inline
+unsigned long percpu_counter_tree_batch_size(struct percpu_counter_tree *counter)
+{
+ return 1UL << counter->batch_order;
+}
+
+/* This counter's first item. */
+static inline
+atomic_long_t *percpu_counter_tree_items(struct percpu_counter_tree *counter)
+{
+ return counter->approx_sum - (tree_topology.nr_items - 1) * counter->items_stride;
+}
+
+/*
+ * The residuals of all levels are within (-batch, +batch) of their level,
+ * so the approximation is within the same distance of the precise sum in
+ * both directions: the largest residuals of all the counters, which
+ * accuracy_multiplier counts in units of the level 0 batch size, minus the
+ * input step of 1 of each level 0 counter. See "Approximation accuracy" at
+ * the top of this file.
+ */
+static inline
+unsigned long percpu_counter_tree_accuracy(struct percpu_counter_tree *counter)
+{
+ unsigned long batch_size = percpu_counter_tree_batch_size(counter);
+
+ return batch_size * tree_topology.accuracy_multiplier - nr_cpu_ids;
+}
+
+/**
+ * percpu_counter_tree_init_many() - Initialize many per-CPU counter trees.
+ * @counters: An array of @nr_counters counters to initialize.
+ * Their memory is provided by the caller.
+ * @nr_counters: The number of counter trees to initialize
+ * @batch_size: The batch size is the increment step at level 0 which triggers a
+ * carry propagation.
+ * The batch size is required to be greater than 1, a power of 2, and at
+ * most PERCPU_COUNTER_TREE_MAX_BATCH.
+ * @gfp_flags: gfp flags to pass to the per-CPU and tree item allocators.
+ *
+ * Initialize many per-CPU counter trees, with a single allocation of
+ * per-CPU counters and a single allocation of tree items for the
+ * @nr_counters counters. The items at each tree position of the
+ * @nr_counters counters share cache lines. When they fit in one cache
+ * line (up to 8 counters on 64-bit with 64-byte cache lines), the tree
+ * items come from a slab cache; beyond, their allocation is
+ * rounded up to a power of 2, which can double it.
+ *
+ * Return:
+ * * %0: Success
+ * * %-EINVAL: - Invalid @batch_size argument
+ * * %-ENOMEM: - Out of memory
+ */
+int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size,
+ gfp_t gfp_flags)
+{
+ unsigned int items_stride = percpu_counter_tree_items_stride(nr_counters);
+ s8 __percpu *level0;
+ atomic_long_t *items;
+ unsigned int i;
+ int ret;
+
+ /* The tree shape is selected by percpu_counter_tree_subsystem_init() at boot. */
+ if (WARN_ON_ONCE(tree_topology.nr_items == UINT_MAX))
+ return -EINVAL;
+ level0 = __alloc_percpu_gfp(nr_counters * sizeof(*level0),
+ __alignof__(*counters->level0), gfp_flags);
+ if (!level0)
+ return -ENOMEM;
+ items = percpu_counter_tree_alloc_items(nr_counters, gfp_flags);
+ if (!items) {
+ ret = -ENOMEM;
+ goto free_level0;
+ }
+ for (i = 0; i < nr_counters; i++) {
+ ret = __percpu_counter_tree_init(&counters[i], batch_size, level0 + i,
+ items + i, items_stride);
+ if (ret)
+ goto free_items;
+ }
+ return 0;
+
+free_items:
+ percpu_counter_tree_free_items(items, nr_counters);
+free_level0:
+ free_percpu(level0);
+ return ret;
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_init_many);
+
+/**
+ * percpu_counter_tree_init() - Initialize one per-CPU counter tree.
+ * @counter: Counter to initialize.
+ * Its memory is provided by the caller.
+ * @batch_size: The batch size is the increment step at level 0 which triggers a
+ * carry propagation.
+ * The batch size is required to be greater than 1, a power of 2, and at
+ * most PERCPU_COUNTER_TREE_MAX_BATCH.
+ * @gfp_flags: gfp flags to pass to the per-CPU and tree item allocators.
+ *
+ * Initialize one per-CPU counter tree.
+ *
+ * Return:
+ * * %0: Success
+ * * %-EINVAL: - Invalid @batch_size argument
+ * * %-ENOMEM: - Out of memory
+ */
+int percpu_counter_tree_init(struct percpu_counter_tree *counter,
+ unsigned long batch_size, gfp_t gfp_flags)
+{
+ return percpu_counter_tree_init_many(counter, 1, batch_size, gfp_flags);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_init);
+
+/**
+ * percpu_counter_tree_destroy_many() - Destroy many per-CPU counter trees.
+ * @counters: Array of counters trees to destroy.
+ * @nr_counters: The number of counter trees to destroy.
+ *
+ * Release internal resources allocated for @nr_counters per-CPU counter trees.
+ * @counters and @nr_counters must be those passed to
+ * percpu_counter_tree_init_many().
+ */
+void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters)
+{
+ free_percpu(counters->level0);
+ /*
+ * @nr_counters selects the allocator of the tree items: on a mismatch
+ * with the initialization, leak them rather than corrupt the allocator.
+ */
+ if (WARN_ON_ONCE(counters->items_stride !=
+ percpu_counter_tree_items_stride(nr_counters)))
+ return;
+ /* The first item of the first counter is the base of the tree items. */
+ percpu_counter_tree_free_items(percpu_counter_tree_items(counters), nr_counters);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_destroy_many);
+
+/**
+ * percpu_counter_tree_destroy() - Destroy one per-CPU counter tree.
+ * @counter: Counter to destroy.
+ *
+ * Release internal resources allocated for one per-CPU counter tree.
+ */
+void percpu_counter_tree_destroy(struct percpu_counter_tree *counter)
+{
+ return percpu_counter_tree_destroy_many(counter, 1);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_destroy);
+
+/*
+ * Amount propagated by a counter holding @v: the multiples of @bit_mask,
+ * truncated toward zero.
+ */
+static inline
+long percpu_counter_tree_item_carry(long v, unsigned long bit_mask)
+{
+ if (v < 0)
+ return -(long)(-(unsigned long)v & ~(bit_mask - 1));
+ return (long)((unsigned long)v & ~(bit_mask - 1));
+}
+
+/*
+ * It does not matter through which path the carry propagates up the
+ * tree, therefore there is no need to disable preemption because the
+ * cpu number is only used to favor cache locality.
+ */
+static
+void percpu_counter_tree_add_slowpath(struct percpu_counter_tree *counter, long inc)
+{
+ unsigned int level_items, nr_levels = tree_topology.config->nr_levels,
+ level, n_arity_order;
+ unsigned long bit_mask;
+ unsigned int stride = counter->items_stride;
+ atomic_long_t *item = percpu_counter_tree_items(counter);
+ unsigned int cpu = raw_smp_processor_id();
+
+ n_arity_order = tree_topology.config->n_arity_order[0];
+ bit_mask = percpu_counter_tree_batch_size(counter) << n_arity_order;
+ level_items = 1U << (tree_topology.nr_cpus_order - n_arity_order);
+
+ for (level = 1; level < nr_levels; level++) {
+ /*
+ * A multiple of bit_mask would leave the residual of this
+ * level unchanged: propagate it to the next level directly.
+ * This trades the hysteresis of this level for not touching
+ * its cache line.
+ */
+ if (abs(inc) & (bit_mask - 1)) {
+ atomic_long_t *count = &item[(cpu & (level_items - 1)) * stride];
+ long res;
+
+ /*
+ * Add the carry to the residual of this level, then
+ * extract the multiples of bit_mask of the residual,
+ * truncated toward zero, and propagate them to the
+ * next level, which leaves the residual within
+ * (-bit_mask, +bit_mask).
+ *
+ * The extraction is a cmpxchg on the value returned by
+ * the addition, whose cache line is already exclusive,
+ * so it usually succeeds at once. When a concurrent
+ * updater changed the residual in between, the cmpxchg
+ * fails and the carry is recomputed from the current
+ * value, which is 0 if the other updater extracted it.
+ * Each carry is thus extracted once, from an exact
+ * value: the residual only exceeds its range by the
+ * additions in flight, and is within range once all
+ * the updaters are done. An addition which does not
+ * carry stays a single atomic operation, which cannot
+ * fail.
+ *
+ * Relaxed ordering is sufficient for the residual
+ * itself: the reasoning above only involves this
+ * atomic, whose modifications all CPUs see in the same
+ * order, each read-modify-write reading the value
+ * written by the one just before it, whatever its
+ * ordering. Ordering only matters relative to the other
+ * levels, for the precise sum: the release ordering of
+ * the addition orders the departure of the carry from
+ * the level below before its arrival here.
+ */
+ res = atomic_long_add_return_release(inc, count);
+ do {
+ inc = percpu_counter_tree_item_carry(res, bit_mask);
+ if (likely(!inc))
+ return;
+ } while (!atomic_long_try_cmpxchg_relaxed(count, &res, res - inc));
+ }
+ item += level_items * stride;
+ n_arity_order = tree_topology.config->n_arity_order[level];
+ level_items >>= n_arity_order;
+ bit_mask <<= n_arity_order;
+ }
+ atomic_long_add_return_release(inc, counter->approx_sum);
+}
+
+/**
+ * percpu_counter_tree_add() - Add to a per-CPU counter tree.
+ * @counter: Counter added to.
+ * @inc: Increment value (either positive or negative).
+ *
+ * Add @inc to a per-CPU counter tree. This is a fast-path which will
+ * typically increment per-CPU counters as long as there is no carry
+ * greater or equal to the counter tree batch size.
+ */
+void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
+{
+ unsigned long bit_mask = percpu_counter_tree_batch_size(counter);
+ s8 old, new;
+ long v, carry;
+
+ /*
+ * Keep the residual within (-batch, +batch) and propagate its
+ * multiples of the batch size, truncated toward zero. This
+ * hysteresis prevents updates going back and forth around a batch
+ * boundary from propagating each time.
+ *
+ * Preemption stays enabled: the update may go to the level 0
+ * counter of any CPU, and the cmpxchg validates the value read.
+ * After a migration or an interrupt between the read and the
+ * cmpxchg, the cmpxchg either fails and retries with the current
+ * residual of the current CPU, or succeeds on a residual equal to
+ * the value read, which the new value correctly replaces. Each
+ * this_cpu operation is itself safe against preemption and
+ * interrupts, and the carry may propagate from any CPU, see
+ * percpu_counter_tree_add_slowpath().
+ */
+ old = this_cpu_read(*counter->level0);
+ do {
+ v = old + inc;
+ carry = percpu_counter_tree_item_carry(v, bit_mask);
+ new = (s8)(v - carry);
+ } while (!this_cpu_try_cmpxchg(*counter->level0, &old, new));
+ if (likely(!carry))
+ return;
+ percpu_counter_tree_add_slowpath(counter, carry);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_add);
+
+/*
+ * The precise sum is the sum of the residuals of all tree levels. A carry
+ * leaves a level before reaching a higher level, and the release ordering
+ * of its arrival orders its departure before it. Reading the levels from
+ * the root down, separated by read barriers, therefore never counts a carry
+ * twice. A carry in flight during the sum may be missed: the result is
+ * precise for a counter without concurrent updates.
+ */
+static
+long percpu_counter_tree_precise_sum_unbiased(struct percpu_counter_tree *counter)
+{
+ unsigned int nr_levels = tree_topology.config->nr_levels, i,
+ level_items[MAX_NR_LEVELS], stride = counter->items_stride;
+ atomic_long_t *item;
+ unsigned long sum;
+ int level, cpu;
+
+ /* Number of items of each level above level 0. */
+ level_items[0] = 1U << tree_topology.nr_cpus_order;
+ for (level = 1; level < (int)nr_levels; level++)
+ level_items[level] = level_items[level - 1] >>
+ tree_topology.config->n_arity_order[level - 1];
+ sum = atomic_long_read(counter->approx_sum);
+ smp_rmb(); /* Read each level before the level below it. */
+ /* The items of each level precede those of the level above it. */
+ item = counter->approx_sum;
+ for (level = (int)nr_levels - 1; level >= 1; level--) {
+ item -= level_items[level] * stride;
+ for (i = 0; i < level_items[level]; i++)
+ sum += atomic_long_read(&item[i * stride]);
+ smp_rmb(); /* Read this level before the level below it. */
+ }
+ for_each_possible_cpu(cpu)
+ sum += (long)READ_ONCE(*per_cpu_ptr(counter->level0, cpu));
+ return (long)sum;
+}
+
+/**
+ * percpu_counter_tree_precise_sum() - Return precise counter sum.
+ * @counter: The counter to sum.
+ *
+ * Querying the precise sum is relatively expensive because it needs to
+ * iterate over all CPUs.
+ * This is meant to be used when accuracy is preferred over speed.
+ *
+ * The sum is exact when no update runs concurrently. It takes no lock, so
+ * a concurrent update which carries from level 0 to the levels above can
+ * be counted in part: the sum may read the residual it left below and miss
+ * its carry on the way up, an error in either direction of at most the
+ * carries in flight. A carry is never counted twice.
+ *
+ * Return: The current precise counter sum.
+ */
+long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter)
+{
+ return percpu_counter_tree_precise_sum_unbiased(counter) + READ_ONCE(counter->bias);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_sum);
+
+/*
+ * The comparison between counters is on the wrapped difference. It is valid
+ * only when the two counters differ by less than LONG_MAX, and results are
+ * undefined beyond that.
+ */
+static inline
+long wrapped_delta(long a, long b)
+{
+ return (long)((unsigned long)a - (unsigned long)b);
+}
+
+/*
+ * Each counter's approximation lies within its accuracy of its precise sum,
+ * in both directions. The comparison only observes the approximations, so
+ * it must reason about the possible precise values around each observed
+ * approximation, which lie within [approx - accuracy, approx + accuracy]:
+ *
+ * precise_a range
+ * <-----------+----------->
+ * accuracy_a | accuracy_a
+ * approx_a
+ * | precise_b range
+ * | <-----------+----------->
+ * | accuracy_b | accuracy_b
+ * | approx_b
+ * | |
+ * |<------------ gap ------------->|
+ * ----------------------+--------------------------------+-------------> values
+ *
+ * The two precise ranges are disjoint, and the comparison can return a
+ * definitive answer, only once the gap between approximations exceeds the
+ * sum of the two accuracies:
+ *
+ * gap > accuracy_a + accuracy_b
+ *
+ * When comparing against a plain value, the value has zero width, so the
+ * margin reduces to the accuracy of the counter: the value is above the
+ * counter once it exceeds approx + accuracy, and below it once it is less
+ * than approx - accuracy.
+ */
+static
+int compare_delta(long delta, unsigned long accuracy)
+{
+ if (delta >= 0) {
+ if (delta <= accuracy)
+ return 0;
+ else
+ return 1;
+ } else {
+ if (-delta <= accuracy)
+ return 0;
+ else
+ return -1;
+ }
+}
+
+/**
+ * percpu_counter_tree_approximate_compare - Approximated comparison of two counter trees.
+ * @a: First counter to compare.
+ * @b: Second counter to compare.
+ *
+ * Evaluate an approximate comparison of two counter trees. This approximation
+ * comparison is fast, and provides an accurate answer if the counters are
+ * found to be either less than or greater than the other. However, if the
+ * approximated comparison returns 0, the counters respective sums are found to
+ * be within the two counters accuracy range. The two counters are read
+ * independently; the result is not an atomic snapshot of both.
+ * The comparison between counters is on the wrapped difference. It is valid
+ * only when the two counters differ by less than LONG_MAX, and results are
+ * undefined beyond that.
+ *
+ * Return:
+ * * %0 - Counters @a and @b do not differ by more than the sum of their respective
+ * accuracy ranges.
+ * * %-1 - Counter @a less than counter @b.
+ * * %1 - Counter @a is greater than counter @b.
+ */
+int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b)
+{
+ unsigned long accuracy = percpu_counter_tree_accuracy(a) + percpu_counter_tree_accuracy(b);
+
+ /* See the range geometry above compare_delta(). */
+ return compare_delta(wrapped_delta(percpu_counter_tree_approximate_sum(a),
+ percpu_counter_tree_approximate_sum(b)),
+ accuracy);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compare);
+
+/**
+ * percpu_counter_tree_approximate_compare_value - Approximated comparison of a counter tree
+ * against a given value.
+ * @counter: Counter to compare.
+ * @v: Value to compare.
+ *
+ * Evaluate an approximate comparison of a counter tree against a given value.
+ * This approximation comparison is fast, and provides an accurate
+ * answer if the counter is found to be either less than or greater
+ * than the value. However, if the approximated comparison returns
+ * 0, the value is within the counter accuracy range.
+ * The comparison between counters is on the wrapped difference. It is valid
+ * only when @v and the counter differ by less than LONG_MAX, and results are
+ * undefined beyond that.
+ *
+ * Return:
+ * * %0 - The value @v is within the accuracy range of the counter.
+ * * %-1 - The value @v is less than the counter.
+ * * %1 - The value @v is greater than the counter.
+ */
+int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tree *counter, long v)
+{
+ unsigned long accuracy = percpu_counter_tree_accuracy(counter);
+
+ /* See the range geometry above compare_delta(). */
+ return compare_delta(wrapped_delta(v, percpu_counter_tree_approximate_sum(counter)),
+ accuracy);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compare_value);
+
+/**
+ * percpu_counter_tree_precise_compare - Precise comparison of two counter trees.
+ * @a: First counter to compare.
+ * @b: Second counter to compare.
+ *
+ * Evaluate a precise comparison of two counter trees. As an optimization, it
+ * uses the approximate counter comparison to quickly compare counters which
+ * are far apart. Only cases where counter sums are within the accuracy range
+ * require precise counter sums. The two counters are read independently; the
+ * result is not an atomic snapshot of both. With concurrent updates, the
+ * precise sums can count updates in part, see
+ * percpu_counter_tree_precise_sum().
+ * The comparison between counters is on the wrapped difference. It is valid
+ * only when the two counters differ by less than LONG_MAX, and results are
+ * undefined beyond that.
+ *
+ * Return:
+ * * %0 - Counters are equal.
+ * * %-1 - Counter @a less than counter @b.
+ * * %1 - Counter @a is greater than counter @b.
+ */
+int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a,
+ struct percpu_counter_tree *b)
+{
+ long count_a = percpu_counter_tree_approximate_sum(a),
+ count_b = percpu_counter_tree_approximate_sum(b);
+ unsigned long accuracy_a = percpu_counter_tree_accuracy(a),
+ accuracy_b = percpu_counter_tree_accuracy(b);
+ long delta = wrapped_delta(count_a, count_b);
+ int res;
+
+ /* See the range geometry above compare_delta(). */
+ res = compare_delta(delta, accuracy_a + accuracy_b);
+ /* The values are distanced enough for an accurate approximated comparison. */
+ if (res)
+ return res;
+
+ /*
+ * The approximated comparison is within the accuracy range, therefore at least one
+ * precise sum is needed. Sum the counter which has the largest accuracy first.
+ */
+ if (accuracy_b < accuracy_a) {
+ count_a = percpu_counter_tree_precise_sum(a);
+ /* precise_a - approx_b: only b's precise range remains. */
+ res = compare_delta(wrapped_delta(count_a, count_b), accuracy_b);
+ if (res)
+ return res;
+ /* Precise sum of second counter is required. */
+ count_b = percpu_counter_tree_precise_sum(b);
+ } else {
+ count_b = percpu_counter_tree_precise_sum(b);
+ /* approx_a - precise_b: only a's precise range remains. */
+ res = compare_delta(wrapped_delta(count_a, count_b), accuracy_a);
+ if (res)
+ return res;
+ /* Precise sum of second counter is required. */
+ count_a = percpu_counter_tree_precise_sum(a);
+ }
+ delta = wrapped_delta(count_a, count_b);
+ if (delta < 0)
+ return -1;
+ if (delta > 0)
+ return 1;
+ return 0;
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare);
+
+/**
+ * percpu_counter_tree_precise_compare_value - Precise comparison of a counter tree against
+ * a given value.
+ * @counter: Counter to compare.
+ * @v: Value to compare.
+ *
+ * Evaluate a precise comparison of a counter tree against a given value. As
+ * an optimization, it uses the approximate counter comparison to quickly
+ * identify whether the counter and value are far apart. Only cases where the
+ * value is within the counter accuracy range require a precise counter sum.
+ * With concurrent updates, the precise sum can count updates in part, see
+ * percpu_counter_tree_precise_sum().
+ * The comparison between counters is on the wrapped difference. It is valid
+ * only when @v and the counter differ by less than LONG_MAX, and results are
+ * undefined beyond that.
+ *
+ * Return:
+ * * %0 - The value @v is equal to the counter.
+ * * %-1 - The value @v is less than the counter.
+ * * %1 - The value @v is greater than the counter.
+ */
+int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *counter, long v)
+{
+ long count = percpu_counter_tree_approximate_sum(counter), delta;
+ unsigned long accuracy = percpu_counter_tree_accuracy(counter);
+ int res;
+
+ /* See the range geometry above compare_delta(). */
+ res = compare_delta(wrapped_delta(v, count), accuracy);
+ /* The values are distanced enough for an accurate approximated comparison. */
+ if (res)
+ return res;
+
+ /* Precise sum is required. */
+ count = percpu_counter_tree_precise_sum(counter);
+ delta = wrapped_delta(v, count);
+ if (delta < 0)
+ return -1;
+ if (delta > 0)
+ return 1;
+ return 0;
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare_value);
+
+/**
+ * percpu_counter_tree_set - Set the counter tree sum to a given value.
+ * @counter: Counter to set.
+ * @v: Value to set.
+ *
+ * Set the counter sum to a given value. It can be useful for instance
+ * to reset the counter sum to 0. Note that even after setting the
+ * counter sum to a given value, the counter sum approximation can
+ * return any value within the accuracy range around that value.
+ *
+ * The caller is responsible for preventing concurrent updates and
+ * precise sums of @counter while it is being set.
+ */
+void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v)
+{
+ WRITE_ONCE(counter->bias, v - percpu_counter_tree_precise_sum_unbiased(counter));
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_set);
+
+/**
+ * percpu_counter_tree_approximate_accuracy - Query the accuracy of a counter tree.
+ * @counter: Counter to query.
+ *
+ * The approximation differs from the precise sum by the residuals not yet propagated
+ * up the tree. The residuals of all levels are symmetric, so the approximation is
+ * within the same distance of the precise sum in both directions.
+ * The accuracy is derived from the hardware topology and the counter tree batch size.
+ * It is invariant for a given counter tree.
+ * The accuracy describes a settled counter: one with no update in progress.
+ * An update in flight between its per-CPU update and its carry propagation is not covered.
+ * Using this function should not be typically required, see the following functions instead:
+ * * percpu_counter_tree_approximate_compare(),
+ * * percpu_counter_tree_approximate_compare_value(),
+ * * percpu_counter_tree_precise_compare(),
+ * * percpu_counter_tree_precise_compare_value().
+ *
+ * Return: The accuracy of the counter: the approximate sum of a settled counter
+ * is within [precise sum - accuracy, precise sum + accuracy].
+ */
+unsigned long percpu_counter_tree_approximate_accuracy(struct percpu_counter_tree *counter)
+{
+ return percpu_counter_tree_accuracy(counter);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_accuracy);
+
+/* Calculate the number of tree items and the accuracy multiplier. */
+static
+void __init calculate_topology(void)
+{
+ unsigned int nr_levels = tree_topology.config->nr_levels, level;
+ unsigned int level_items = 1U << tree_topology.nr_cpus_order;
+ unsigned long batch_size = 1;
+
+ /* The root, and the items of each level above level 0. */
+ tree_topology.nr_items = 1;
+ /* One batch per level 0 counter: see percpu_counter_tree_accuracy(). */
+ tree_topology.accuracy_multiplier = nr_cpu_ids;
+
+ /*
+ * The multiplier is derived from a batch size of 1 to speed up
+ * calculating the accuracy at tree initialization. A level N
+ * counter holds at most BATCH(level N) - BATCH(level N - 1) in
+ * either direction.
+ */
+ for (level = 1; level < nr_levels; level++) {
+ unsigned int n_arity_order = tree_topology.config->n_arity_order[level - 1];
+
+ level_items >>= n_arity_order;
+ tree_topology.nr_items += level_items;
+ tree_topology.accuracy_multiplier +=
+ ((batch_size << n_arity_order) - batch_size) * level_items;
+ batch_size <<= n_arity_order;
+ }
+}
+
+#if IS_ENABLED(CONFIG_KUNIT)
+/*
+ * Validate the configuration table: the n-arity orders of each entry must
+ * sum to its order.
+ *
+ * Return: The number of invalid entries.
+ */
+unsigned int percpu_counter_tree_check_config(void)
+{
+ unsigned int order, nr_errors = 0;
+
+ for (order = 0; order < ARRAY_SIZE(per_nr_cpu_order_config); order++) {
+ const struct counter_config *c = &per_nr_cpu_order_config[order];
+ unsigned int level, shift = 0;
+
+ for (level = 0; level < c->nr_levels; level++)
+ shift += c->n_arity_order[level];
+ if (shift != order) {
+ pr_err("order %u: arity sum %u\n", order, shift);
+ nr_errors++;
+ }
+ }
+ return nr_errors;
+}
+EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_check_config);
+
+/*
+ * Check the invariants of a settled counter (no update in progress):
+ * - a level 0 counter is within (-BATCH(level 0), +BATCH(level 0)),
+ * - a counter at level N, above level 0, holds a multiple of
+ * BATCH(level N - 1) within (-BATCH(level N), +BATCH(level N)),
+ * - the root holds a multiple of the batch of the last level.
+ *
+ * Return: The number of violated invariants.
+ */
+unsigned int percpu_counter_tree_check_residuals(struct percpu_counter_tree *counter)
+{
+ unsigned int nr_levels = tree_topology.config->nr_levels, level, level_items,
+ nr_errors = 0, stride = counter->items_stride;
+ atomic_long_t *item = percpu_counter_tree_items(counter);
+ unsigned long lo = percpu_counter_tree_batch_size(counter);
+ long root;
+ int cpu;
+
+ for_each_possible_cpu(cpu) {
+ long v = READ_ONCE(*per_cpu_ptr(counter->level0, cpu));
+
+ if (v <= -(long)lo || v >= (long)lo) {
+ pr_err("cpu %d: level 0 residual %ld, batch %lu\n", cpu, v, lo);
+ nr_errors++;
+ }
+ }
+ level_items = 1U << tree_topology.nr_cpus_order;
+ for (level = 1; level < nr_levels; level++) {
+ unsigned int n_arity_order = tree_topology.config->n_arity_order[level - 1], i;
+ unsigned long hi = lo << n_arity_order;
+
+ level_items >>= n_arity_order;
+ for (i = 0; i < level_items; i++) {
+ long v = atomic_long_read(&item[i * stride]);
+
+ if (v <= -(long)hi || v >= (long)hi || ((unsigned long)v & (lo - 1))) {
+ pr_err("level %u item %u: residual %ld, batch %lu\n",
+ level, i, v, hi);
+ nr_errors++;
+ }
+ }
+ item += level_items * stride;
+ lo = hi;
+ }
+ root = atomic_long_read(counter->approx_sum);
+ if ((unsigned long)root & (lo - 1)) {
+ pr_err("root %ld: not a multiple of %lu\n", root, lo);
+ nr_errors++;
+ }
+ return nr_errors;
+}
+EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_check_residuals);
+
+/*
+ * Copy the state of counter @src into counter @dst, initialized with the
+ * same batch size and without concurrent updates: their per-CPU counters,
+ * tree items and bias.
+ */
+void percpu_counter_tree_copy_state(struct percpu_counter_tree *dst,
+ struct percpu_counter_tree *src)
+{
+ atomic_long_t *dst_items = percpu_counter_tree_items(dst),
+ *src_items = percpu_counter_tree_items(src);
+ unsigned int pos;
+ int cpu;
+
+ for_each_possible_cpu(cpu)
+ *per_cpu_ptr(dst->level0, cpu) = *per_cpu_ptr(src->level0, cpu);
+ for (pos = 0; pos < tree_topology.nr_items; pos++)
+ atomic_long_set(&dst_items[pos * dst->items_stride],
+ atomic_long_read(&src_items[pos * src->items_stride]));
+ dst->bias = src->bias;
+}
+EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_copy_state);
+#endif
+
+/* Format the fan-out of each level, from level 0 to the root, e.g. "8,2,8". */
+static
+int format_shape(char *buf, size_t size, const struct counter_config *config)
+{
+ unsigned int level;
+ int len = 0;
+
+ for (level = 0; level < config->nr_levels; level++)
+ len += scnprintf(buf + len, size - len, "%s%u", level ? "," : "",
+ 1U << config->n_arity_order[level]);
+ return len;
+}
+
+int __init percpu_counter_tree_subsystem_init(void)
+{
+ char shape[8 * MAX_NR_LEVELS + 1] = "";
+
+ tree_topology.nr_cpus_order = get_count_order(nr_cpu_ids);
+ if (tree_topology.nr_cpus_order >= ARRAY_SIZE(per_nr_cpu_order_config)) {
+ pr_err("Unsupported number of CPUs (%u)\n", nr_cpu_ids);
+ return -EINVAL;
+ }
+ tree_topology.config = &per_nr_cpu_order_config[tree_topology.nr_cpus_order];
+ calculate_topology();
+ tree_topology.items_cachep =
+ kmem_cache_create("percpu_counter_tree_items",
+ tree_topology.nr_items * SMP_CACHE_BYTES,
+ SMP_CACHE_BYTES, SLAB_PANIC, NULL);
+ format_shape(shape, sizeof(shape), tree_topology.config);
+ pr_info("%u CPUs, fan-out %s, %u tree items\n",
+ nr_cpu_ids, tree_topology.nr_cpus_order ? shape : "none",
+ tree_topology.nr_items);
+ return 0;
+}
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 02/10] lib: test hierarchical per-cpu counters
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
2026-11-02 19:06 ` [RFC PATCH v23 01/10] lib: introduce hierarchical per-cpu counters Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 03/10] mm: use hierarchical per-cpu counters for the RSS counters Mathieu Desnoyers
` (7 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Introduce Kunit tests for hierarchical per-cpu counters.
Keep track of two sets of hierarchical counters, each meant to have the
same precise sum at any time, but distributed differently across the
topology.
Keep track of an atomic counter along with each hierarchical counter, for
sum validation.
Those tests cover:
- Single-threaded (no concurrency) updates.
- Concurrent updates of counters from various CPUs.
- Contended carries: rounds of concurrent carries from many CPUs into
the tree items they share.
The multi-threaded tests run their workers on at most 64 CPUs, spread
evenly across the online CPUs, so their run time does not grow with the
size of the machine.
The single-threaded and saturation tests run each update on its target
CPU with work_on_cpu(), and the multi-threaded tests queue their updates
on a CPU intensive workqueue, whose workers are reused across rounds
and can preempt each other on a CPU. The single and multi-threaded
tests stop early after a time bound, so they complete on large virtual
machines where cross-CPU wakeups are slow.
Perform the following validations:
- Compare the precise sum of counters with the sum tracked by
an atomic counter.
- Compare the precise sum of two sets of hierarchical counters.
- Approximated comparison of hierarchical counter with atomic counter.
- Approximated comparison of two sets of hierarchical counters.
- Validate the bounds of approximation ranges.
- Check the residuals of the tree items, and that no carry was lost or
duplicated, whenever the counters are settled, including between the
rounds of contended carries.
- Saturate a counter upward and downward to its worst-case approximation
errors, check that it reaches the edges of its accuracy range exactly
when all possible CPUs are online, and validate the comparisons at the
edges of its precise range.
Run with the following .kunit/.kunitconfig:
CONFIG_KUNIT=y
CONFIG_SMP=y
CONFIG_PREEMPT=y
CONFIG_NR_CPUS=32
CONFIG_HOTPLUG_CPU=y
CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST=y
With the following execution (to use SMP):
./tools/testing/kunit/kunit.py run --arch=x86_64 --qemu_args="-smp 12"
Link: https://lkml.kernel.org/r/20260227153730.1556542-3-mathieu.desnoyers@efficios.com
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Christoph Lameter <cl@gentwo.org>
Cc: Martin Liu <liumartin@google.com>
Cc: David Rientjes <rientjes@google.com>
Cc: christian.koenig@amd.com
Cc: Shakeel Butt <shakeel.butt@linux.dev>
Cc: SeongJae Park <sj@kernel.org>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Sweet Tea Dorminy <sweettea-kernel@dorminy.me>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: Christian Brauner <brauner@kernel.org>
Cc: Wei Yang <richard.weiyang@gmail.com>
Cc: David Hildenbrand <david@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Yu Zhao <yuzhao@google.com>
Cc: Roman Gushchin <roman.gushchin@linux.dev>
Cc: Mateusz Guzik <mjguzik@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Aboorva Devarajan <aboorvad@linux.ibm.com>
Cc: David Carlier <devnexen@gmail.com>
Cc: Josh Law <objecting@objecting.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: linux-mm@kvack.org
---
Changes since v22:
- Fix CPU hotplug locking, module unload, and error handling: ERR_PTR
handling, a test data leak, allocation sizing, the cpu & ~1 skip, a
lost worker when kthread_stop() runs before the thread function, and
a task_struct reaping race. (Reported by Sashiko.)
- Merge the four multi-thread increment tests into one function taking
a CPU selector.
- Add a saturated counter comparison test, upward and downward.
- Add a contended carries test.
- Bound the number of CPUs running workers in the multi-threaded tests.
- Check the residuals and carries of settled counters.
- Add a configuration table validation test.
- Run the updates with work_on_cpu() and a workqueue rather than
creating a kthread for each update, and bound the run time of the
single and multi-threaded tests, which timed out with 192 CPUs in a
virtual machine.
- Fix checkpatch warnings.
Changes since v19:
- Rename config option to PERCPU_COUNTER_TREE_KUNIT_TEST.
---
MAINTAINERS | 1 +
lib/Kconfig | 12 +
lib/tests/Makefile | 2 +
lib/tests/percpu_counter_tree_kunit.c | 832 ++++++++++++++++++++++++++
4 files changed, 847 insertions(+)
create mode 100644 lib/tests/percpu_counter_tree_kunit.c
diff --git a/MAINTAINERS b/MAINTAINERS
index 712af0536005..21348605d06e 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -11955,6 +11955,7 @@ S: Supported
F: Documentation/core-api/percpu-counter-tree.rst
F: include/linux/percpu_counter_tree.h
F: lib/percpu_counter_tree.c
+F: lib/tests/percpu_counter_tree_kunit.c
HIGH-RESOLUTION TIMERS, TIMER WHEEL, CLOCKEVENTS
M: Anna-Maria Behnsen <anna-maria@linutronix.de>
diff --git a/lib/Kconfig b/lib/Kconfig
index 1e42f5167c68..3921177a0d24 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -41,6 +41,18 @@ config PACKING_KUNIT_TEST
When in doubt, say N.
+config PERCPU_COUNTER_TREE_KUNIT_TEST
+ tristate "KUnit tests for hierarchical per-cpu counters" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ default KUNIT_ALL_TESTS
+ help
+ This builds Kunit tests for the hierarchical per-cpu counters.
+
+ For more information on KUnit and unit tests in general,
+ please refer to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+ When in doubt, say N.
+
config BITREVERSE
tristate
select GENERIC_BITREVERSE if !HAVE_ARCH_BITREVERSE
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index df0537e1b91f..e98687da8706 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -59,4 +59,6 @@ obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o
obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
obj-$(CONFIG_UUID_KUNIT_TEST) += uuid_kunit.o
+obj-$(CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST) += percpu_counter_tree_kunit.o
+
obj-$(CONFIG_TEST_RUNTIME_MODULE) += module/
diff --git a/lib/tests/percpu_counter_tree_kunit.c b/lib/tests/percpu_counter_tree_kunit.c
new file mode 100644
index 000000000000..58b2e488e3c6
--- /dev/null
+++ b/lib/tests/percpu_counter_tree_kunit.c
@@ -0,0 +1,832 @@
+// SPDX-License-Identifier: GPL-2.0+ OR MIT
+// SPDX-FileCopyrightText: 2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+
+#include <kunit/test.h>
+#include <linux/percpu_counter_tree.h>
+#include <linux/kthread.h>
+#include <linux/wait.h>
+#include <linux/random.h>
+#include <linux/cpuhplock.h>
+#include <linux/slab.h>
+#include <linux/sched/task.h>
+#include <linux/workqueue.h>
+
+struct multi_thread_test_data {
+ struct work_struct work;
+ long increment;
+ unsigned int nr_inc;
+ int counter_index;
+};
+
+#define NR_COUNTERS 2
+
+/* Hierarchical per-CPU counter instances. */
+static struct percpu_counter_tree counter[NR_COUNTERS];
+
+/* Global atomic counters for validation. */
+static atomic_long_t global_counter[NR_COUNTERS];
+
+static DECLARE_WAIT_QUEUE_HEAD(kernel_threads_wq);
+static atomic_t kernel_threads_to_run;
+
+static void complete_work(void)
+{
+ if (atomic_dec_and_test(&kernel_threads_to_run))
+ wake_up(&kernel_threads_wq);
+}
+
+/* Random tasks test. */
+#define NR_RAND_TASKS 1000
+
+static void hpcc_print_info(struct kunit *test)
+{
+ kunit_info(test, "Running test with %d CPUs\n", num_online_cpus());
+}
+
+static void add_to_counter(int counter_index, unsigned int nr_inc, long increment)
+{
+ unsigned int i;
+
+ for (i = 0; i < nr_inc; i++) {
+ percpu_counter_tree_add(&counter[counter_index], increment);
+ atomic_long_add(increment, &global_counter[counter_index]);
+ }
+}
+
+/* Check the residuals and the carries of a settled counter. */
+static void check_residuals(struct kunit *test, struct percpu_counter_tree *c)
+{
+#ifdef CONFIG_SMP
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_check_residuals(c));
+#endif
+}
+
+static void check_counters(struct kunit *test)
+{
+ int counter_index;
+
+ /* Compare each counter with its global counter. */
+ for (counter_index = 0; counter_index < NR_COUNTERS; counter_index++) {
+ struct percpu_counter_tree *c = &counter[counter_index];
+ long v = atomic_long_read(&global_counter[counter_index]);
+ long approx_sum = percpu_counter_tree_approximate_sum(c);
+ unsigned long accuracy;
+ long precise_min, precise_max;
+
+ /* Precise comparison. */
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(c), v);
+ check_residuals(test, c);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare_value(c, v));
+
+ /* Approximate comparison. */
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(c, v));
+
+ /* Accuracy limits checks. */
+ accuracy = percpu_counter_tree_approximate_accuracy(c);
+
+ /*
+ * The accuracy is an unsigned long, so the inner expression
+ * promotes to unsigned. Compute the difference in unsigned and
+ * cast to signed for the comparison against 0.
+ */
+ KUNIT_EXPECT_GE(test, (long)(approx_sum - (v - accuracy)), 0);
+ KUNIT_EXPECT_LE(test, (long)(approx_sum - (v + accuracy)), 0);
+
+ /* Precise min/max range check. */
+ percpu_counter_tree_approximate_min_max_range(approx_sum, accuracy,
+ &precise_min, &precise_max);
+
+ KUNIT_EXPECT_GE(test, v - precise_min, 0);
+ KUNIT_EXPECT_LE(test, v - precise_max, 0);
+ }
+ /* Compare each counter with the second counter. */
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&counter[0]),
+ percpu_counter_tree_precise_sum(&counter[1]));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare(&counter[0], &counter[1]));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare(&counter[0], &counter[1]));
+}
+
+/*
+ * Workqueue running the updates of the multi-threaded tests. Its workers
+ * are reused across rounds, which keeps the tests fast on machines where
+ * creating threads on remote CPUs is slow. Work items are CPU intensive,
+ * so several of them queued on one CPU run concurrently in separate
+ * workers, and can preempt each other in the middle of an update.
+ */
+static struct workqueue_struct *hpcc_test_wq;
+
+static void multi_thread_work_fn(struct work_struct *work)
+{
+ struct multi_thread_test_data *td =
+ container_of(work, struct multi_thread_test_data, work);
+
+ add_to_counter(td->counter_index, td->nr_inc, td->increment);
+ kfree(td);
+ complete_work();
+}
+
+/* Queue an update of a counter on @target_cpu. Call with the CPU hotplug lock held. */
+static int test_queue_on_cpu(int target_cpu, int counter_index, unsigned int nr_inc,
+ long increment)
+{
+ struct multi_thread_test_data *td = kzalloc(sizeof(*td), GFP_KERNEL);
+
+ if (!td)
+ return -ENOMEM;
+ INIT_WORK(&td->work, multi_thread_work_fn);
+ td->increment = increment;
+ td->nr_inc = nr_inc;
+ td->counter_index = counter_index;
+ atomic_inc(&kernel_threads_to_run);
+ queue_work_on(target_cpu, hpcc_test_wq, &td->work);
+ return 0;
+}
+
+static void init_kthreads(void)
+{
+ atomic_set(&kernel_threads_to_run, 1);
+}
+
+/*
+ * The caller needs to wait for work completion _before_ stopping kthreads.
+ */
+static void fini_kthreads(void)
+{
+ /* Release our own reference. */
+ complete_work();
+ /* Wait for all others threads to run. */
+ wait_event(kernel_threads_wq, (atomic_read(&kernel_threads_to_run) == 0));
+}
+
+static int init_counters(unsigned long batch_size)
+{
+ int i, ret;
+
+ ret = percpu_counter_tree_init_many(counter, NR_COUNTERS, batch_size, GFP_KERNEL);
+ if (ret)
+ return ret;
+ for (i = 0; i < NR_COUNTERS; i++)
+ atomic_long_set(&global_counter[i], 0);
+ return 0;
+}
+
+static void fini_counters(void)
+{
+ percpu_counter_tree_destroy_many(counter, NR_COUNTERS);
+}
+
+enum up_test_inc_type {
+ INC_ONE,
+ INC_MINUS_ONE,
+ INC_RANDOM,
+};
+
+/*
+ * Single-threaded tests. Those run the updates on various CPUs, one at a
+ * time: work_on_cpu() waits for each update to complete before the next,
+ * effectively making sure there are no concurrent updates. Each test
+ * stops early after SINGLE_THREAD_MAX_SECONDS, because cross-CPU wakeups
+ * can be slow on large virtual machines.
+ */
+#define SINGLE_THREAD_MAX_SECONDS 10
+
+struct single_thread_update {
+ long increment;
+ int counter_index;
+};
+
+static long single_thread_update_fn(void *arg)
+{
+ struct single_thread_update *u = arg;
+
+ add_to_counter(u->counter_index, 1, u->increment);
+ return 0;
+}
+
+static void do_hpcc_test_single_thread(struct kunit *test, int _cpu0, int _cpu1,
+ enum up_test_inc_type type)
+{
+ unsigned long batch_size_order = 5;
+ int cpu0 = _cpu0;
+ int cpu1 = _cpu1;
+ unsigned long deadline = jiffies + SINGLE_THREAD_MAX_SECONDS * HZ;
+ int ret, i;
+
+ ret = init_counters(1UL << batch_size_order);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+ cpus_read_lock();
+ for (i = 0; i < 10000 && time_before(jiffies, deadline); i++) {
+ struct single_thread_update u0 = { .counter_index = 0 };
+ struct single_thread_update u1 = { .counter_index = 1 };
+ long increment;
+
+ switch (type) {
+ case INC_ONE:
+ increment = 1;
+ break;
+ case INC_MINUS_ONE:
+ increment = -1;
+ break;
+ case INC_RANDOM:
+ increment = (long)get_random_long() % 50000;
+ break;
+ default:
+ WARN_ON_ONCE(1);
+ increment = 0;
+ }
+ if (_cpu0 < 0)
+ cpu0 = cpumask_any_distribute(cpu_online_mask);
+ if (_cpu1 < 0)
+ cpu1 = cpumask_any_distribute(cpu_online_mask);
+ u0.increment = increment;
+ u1.increment = increment;
+ work_on_cpu(cpu0, single_thread_update_fn, &u0);
+ work_on_cpu(cpu1, single_thread_update_fn, &u1);
+ check_counters(test);
+ }
+ cpus_read_unlock();
+ fini_counters();
+}
+
+static void hpcc_test_single_thread_first(struct kunit *test)
+{
+ int cpu = cpumask_first(cpu_online_mask);
+
+ do_hpcc_test_single_thread(test, cpu, cpu, INC_ONE);
+ do_hpcc_test_single_thread(test, cpu, cpu, INC_MINUS_ONE);
+ do_hpcc_test_single_thread(test, cpu, cpu, INC_RANDOM);
+}
+
+static void hpcc_test_single_thread_first_random(struct kunit *test)
+{
+ int cpu = cpumask_first(cpu_online_mask);
+
+ do_hpcc_test_single_thread(test, cpu, -1, INC_ONE);
+ do_hpcc_test_single_thread(test, cpu, -1, INC_MINUS_ONE);
+ do_hpcc_test_single_thread(test, cpu, -1, INC_RANDOM);
+}
+
+static void hpcc_test_single_thread_random(struct kunit *test)
+{
+ do_hpcc_test_single_thread(test, -1, -1, INC_ONE);
+ do_hpcc_test_single_thread(test, -1, -1, INC_MINUS_ONE);
+ do_hpcc_test_single_thread(test, -1, -1, INC_RANDOM);
+}
+
+/* Multi-threaded SMP tests. */
+
+/*
+ * Bound the number of CPUs running workers in the multi-threaded tests,
+ * so their run time does not grow with the size of the machine. Beyond
+ * this bound, the workers run on a subset spread evenly across the
+ * online CPUs, so they still reach every branch of the tree.
+ */
+#define MAX_WORKER_CPUS 64
+
+/*
+ * Each multi-threaded test stops early after MULTI_THREAD_MAX_SECONDS,
+ * because cross-CPU wakeups can be slow on large virtual machines.
+ */
+#define MULTI_THREAD_MAX_SECONDS 60
+
+static struct cpumask worker_cpus;
+
+/* Select the CPUs running workers. Call with the CPU hotplug lock held. */
+static const struct cpumask *select_worker_cpus(void)
+{
+ unsigned int nr_online = num_online_cpus(), i = 0;
+ int cpu;
+
+ cpumask_clear(&worker_cpus);
+ for_each_online_cpu(cpu) {
+ /* Pick MAX_WORKER_CPUS of the nr_online CPUs, evenly spaced. */
+ if ((i + 1) * MAX_WORKER_CPUS / nr_online !=
+ i * MAX_WORKER_CPUS / nr_online)
+ cpumask_set_cpu(cpu, &worker_cpus);
+ i++;
+ }
+ return &worker_cpus;
+}
+
+/*
+ * CPU selection for the second counter's thread, relative to the CPU
+ * running the first counter's thread.
+ */
+enum mt_cpu_select {
+ MT_SAME_CPU, /* Same CPU as the first counter. */
+ MT_EVEN_CPU, /* Funnel CPU pairs (0, 1), (2, 3), ... to 0, 2, ... */
+ MT_FIRST_CPU, /* First online CPU. */
+ MT_RANDOM_CPU, /* Any online CPU. */
+};
+
+/* Return the CPU for the second counter's thread, or -1 to skip @cpu. */
+static int mt_select_cpu(enum mt_cpu_select select, int cpu)
+{
+ int even_cpu;
+
+ switch (select) {
+ case MT_SAME_CPU:
+ return cpu;
+ case MT_EVEN_CPU:
+ even_cpu = cpu & ~1;
+ return cpumask_test_cpu(even_cpu, cpu_online_mask) ? even_cpu : -1;
+ case MT_FIRST_CPU:
+ return cpumask_first(cpu_online_mask);
+ case MT_RANDOM_CPU:
+ return cpumask_any_distribute(cpu_online_mask);
+ }
+ WARN_ON_ONCE(1);
+ return -1;
+}
+
+static void do_hpcc_multi_thread_increment(struct kunit *test, enum mt_cpu_select select,
+ unsigned long batch_size, unsigned int nr_inc,
+ long increment)
+{
+ const struct cpumask *cpus;
+ int ret, cpu;
+
+ ret = init_counters(batch_size);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+ init_kthreads();
+ cpus_read_lock();
+ cpus = select_worker_cpus();
+ for_each_cpu(cpu, cpus) {
+ int cpu1 = mt_select_cpu(select, cpu);
+
+ if (cpu1 < 0)
+ continue;
+ ret = test_queue_on_cpu(cpu, 0, nr_inc, increment);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ break;
+ ret = test_queue_on_cpu(cpu1, 1, nr_inc, increment);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ break;
+ }
+ fini_kthreads();
+ cpus_read_unlock();
+ check_counters(test);
+ fini_counters();
+}
+
+static void hpcc_test_multi_thread_batch_increment(struct kunit *test)
+{
+ unsigned long deadline = jiffies + MULTI_THREAD_MAX_SECONDS * HZ;
+ unsigned long batch_size_order;
+
+ for (batch_size_order = 2; batch_size_order <= 7; batch_size_order++) {
+ unsigned long batch_size = 1UL << batch_size_order;
+ unsigned int nr_inc;
+
+ for (nr_inc = 1; nr_inc < 1024; nr_inc *= 2) {
+ long increment;
+
+ for (increment = 1; increment < 100000; increment *= 10) {
+ enum mt_cpu_select select;
+
+ if (time_after(jiffies, deadline))
+ return;
+ for (select = MT_SAME_CPU; select <= MT_RANDOM_CPU; select++)
+ do_hpcc_multi_thread_increment(test, select, batch_size,
+ nr_inc, increment);
+ }
+ }
+ }
+}
+
+static void hpcc_test_multi_thread_random_walk(struct kunit *test)
+{
+ unsigned long deadline = jiffies + MULTI_THREAD_MAX_SECONDS * HZ;
+ unsigned long batch_size_order = 5;
+ int loop;
+
+ for (loop = 0; loop < 100 && time_before(jiffies, deadline); loop++) {
+ int ret, i;
+
+ ret = init_counters(1UL << batch_size_order);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+ init_kthreads();
+ cpus_read_lock();
+ for (i = 0; i < NR_RAND_TASKS; i++) {
+ long increment = (long)get_random_long() % 512;
+ unsigned int nr_inc = ((unsigned long)get_random_long()) % 1024;
+
+ ret = test_queue_on_cpu(cpumask_any_distribute(cpu_online_mask),
+ 0, nr_inc, increment);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ break;
+ ret = test_queue_on_cpu(cpumask_any_distribute(cpu_online_mask),
+ 1, nr_inc, increment);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ break;
+ }
+ fini_kthreads();
+ cpus_read_unlock();
+ check_counters(test);
+ fini_counters();
+ }
+}
+
+#define CONTENTION_NR_ROUNDS 20000
+#define CONTENTION_NR_INC 8
+
+struct contention_shared {
+ unsigned long batch_size;
+ atomic_t round; /* Round started by the coordinator. */
+ atomic_t nr_done; /* Rounds completed by the other workers. */
+ unsigned int nr_workers;
+ unsigned int nr_errors; /* Rounds ending with invalid residuals. */
+ bool started;
+};
+
+struct contention_data {
+ struct contention_shared *sh;
+ long sum;
+ u32 seed;
+ bool coordinator;
+} ____cacheline_aligned_in_smp;
+
+static DECLARE_WAIT_QUEUE_HEAD(contention_wq);
+
+/*
+ * Add random multiples of the batch size, of either sign, so each
+ * addition carries into the counters above level 0. Increments of
+ * opposite signs and of more than one batch size exercise concurrent
+ * carry extractions retrying after a concurrent update of the residual.
+ */
+static void contention_add(struct contention_data *cd)
+{
+ unsigned int i;
+
+ for (i = 0; i < CONTENTION_NR_INC; i++) {
+ u32 x = cd->seed;
+ long inc;
+
+ /* xorshift32: get_random_u32() would dominate the loop. */
+ x ^= x << 13;
+ x ^= x >> 17;
+ x ^= x << 5;
+ cd->seed = x;
+ inc = (long)((x & 15) + 1) * cd->sh->batch_size;
+ if (x & 16)
+ inc = -inc;
+ percpu_counter_tree_add(&counter[0], inc);
+ cd->sum += inc;
+ }
+}
+
+/*
+ * The workers run rounds of a few additions each, all starting together.
+ * Between rounds, the coordinator checks the residuals of the settled
+ * counter: an invalid residual left by the last updaters of a round would
+ * otherwise be repaired by the next additions.
+ */
+static int contention_worker_fn(void *data)
+{
+ struct contention_data *cd = data;
+ struct contention_shared *sh = cd->sh;
+ int round;
+
+ wait_event(contention_wq, READ_ONCE(sh->started));
+ for (round = 1; round <= CONTENTION_NR_ROUNDS; round++) {
+ if (cd->coordinator) {
+ atomic_set_release(&sh->round, round);
+ contention_add(cd);
+ while (atomic_read_acquire(&sh->nr_done) < round * (sh->nr_workers - 1))
+ cond_resched();
+#ifdef CONFIG_SMP
+ if (percpu_counter_tree_check_residuals(&counter[0]))
+ sh->nr_errors++;
+#endif
+ } else {
+ while (atomic_read_acquire(&sh->round) < round)
+ cond_resched();
+ contention_add(cd);
+ /* Order the additions before the coordinator check. */
+ atomic_inc_return_release(&sh->nr_done);
+ }
+ }
+ complete_work();
+ return 0;
+}
+
+static void do_hpcc_test_contended_carries(struct kunit *test, unsigned long batch_size)
+{
+ struct percpu_counter_tree *c = &counter[0];
+ struct contention_shared sh = { .batch_size = batch_size };
+ struct contention_data *cd;
+ struct task_struct **task;
+ const struct cpumask *cpus;
+ unsigned long accuracy;
+ long expected = 0, approx;
+ bool first = true;
+ int ret, cpu;
+
+ cd = kvcalloc(nr_cpu_ids, sizeof(*cd), GFP_KERNEL);
+ task = kvcalloc(nr_cpu_ids, sizeof(*task), GFP_KERNEL);
+ KUNIT_EXPECT_NOT_NULL(test, cd);
+ KUNIT_EXPECT_NOT_NULL(test, task);
+ if (!cd || !task)
+ goto free;
+ ret = init_counters(batch_size);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ goto free;
+ init_kthreads();
+ cpus_read_lock();
+ cpus = select_worker_cpus();
+ for_each_cpu(cpu, cpus) {
+ cd[cpu].sh = &sh;
+ cd[cpu].coordinator = first;
+ cd[cpu].seed = get_random_u32() | 1;
+ task[cpu] = kthread_create_on_cpu(contention_worker_fn, &cd[cpu], cpu,
+ "kunit_hpcc_contention/%u");
+ KUNIT_EXPECT_FALSE(test, IS_ERR(task[cpu]));
+ if (IS_ERR(task[cpu]))
+ break;
+ atomic_inc(&kernel_threads_to_run);
+ get_task_struct(task[cpu]);
+ wake_up_process(task[cpu]);
+ sh.nr_workers++;
+ first = false;
+ }
+ /* Start the workers once their number is known. */
+ WRITE_ONCE(sh.started, true);
+ wake_up_all(&contention_wq);
+ fini_kthreads();
+ for_each_cpu(cpu, cpus) {
+ if (IS_ERR_OR_NULL(task[cpu]))
+ continue;
+ kthread_stop_put(task[cpu]);
+ expected += cd[cpu].sum;
+ }
+ cpus_read_unlock();
+
+ kunit_info(test, "batch_size=%lu workers=%u rounds with invalid residuals=%u\n",
+ batch_size, sh.nr_workers, sh.nr_errors);
+ KUNIT_EXPECT_EQ(test, sh.nr_errors, 0);
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(c), expected);
+ check_residuals(test, c);
+ approx = percpu_counter_tree_approximate_sum(c);
+ accuracy = percpu_counter_tree_approximate_accuracy(c);
+ KUNIT_EXPECT_GE(test, approx, expected - (long)accuracy);
+ KUNIT_EXPECT_LE(test, approx, expected + (long)accuracy);
+ fini_counters();
+free:
+ kvfree(task);
+ kvfree(cd);
+}
+
+/*
+ * Concurrent carries from the worker CPUs into the counters above level 0
+ * which they share, with a check that the residuals are back within range
+ * and that no carry was lost or duplicated after each round.
+ */
+static void hpcc_test_contended_carries(struct kunit *test)
+{
+ unsigned long batch_size_order;
+
+ if (num_online_cpus() < 2)
+ kunit_skip(test, "needs at least 2 online CPUs");
+ for (batch_size_order = 1; batch_size_order <= 5; batch_size_order += 2)
+ do_hpcc_test_contended_carries(test, 1UL << batch_size_order);
+}
+
+static void hpcc_test_init_one(struct kunit *test)
+{
+ struct percpu_counter_tree pct;
+ int ret;
+
+ ret = percpu_counter_tree_init(&pct, 32, GFP_KERNEL);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+
+ percpu_counter_tree_destroy(&pct);
+}
+
+static void hpcc_test_set(struct kunit *test)
+{
+ static long values[] = {
+ 5, 100, 127, 128, 255, 256, 4095, 4096, 500000, 0,
+ -5, -100, -127, -128, -255, -256, -4095, -4096, -500000,
+ };
+ struct percpu_counter_tree pct;
+ int i, ret;
+
+ ret = percpu_counter_tree_init(&pct, 32, GFP_KERNEL);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+
+ for (i = 0; i < ARRAY_SIZE(values); i++) {
+ long v = values[i];
+
+ percpu_counter_tree_set(&pct, v);
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), v);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&pct, v));
+
+ percpu_counter_tree_add(&pct, v);
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), 2 * v);
+ KUNIT_EXPECT_EQ(test, 0,
+ percpu_counter_tree_approximate_compare_value(&pct, 2 * v));
+
+ percpu_counter_tree_add(&pct, -2 * v);
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), 0);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&pct, 0));
+ }
+
+ percpu_counter_tree_destroy(&pct);
+}
+
+struct saturate_data {
+ struct percpu_counter_tree *c, *probe;
+ long inc;
+ unsigned long max_steps;
+ bool overrun;
+};
+
+/* Copy the state of counter @src into counter @dst, of the same topology. */
+static void copy_counter_state(struct percpu_counter_tree *dst,
+ struct percpu_counter_tree *src)
+{
+#ifdef CONFIG_SMP
+ percpu_counter_tree_copy_state(dst, src);
+#else
+ atomic_long_set(&dst->count, atomic_long_read(&src->count));
+#endif
+}
+
+/*
+ * Add inc (1 or -1) until the next addition would propagate a carry to the
+ * approximate sum. This leaves every tree item on the path from this CPU to
+ * the root holding its largest residual in the direction of inc which has
+ * not been propagated yet, without knowledge of the tree topology. Each
+ * addition is first tried on the probe counter, which holds the same state:
+ * reverting an addition which reached the approximate sum would not restore
+ * the residuals subtracted on the way. The path from a CPU to the root
+ * holds less than the accuracy bound: more additions mean that a carry was
+ * lost.
+ */
+static long saturate_worker_fn(void *data)
+{
+ struct saturate_data *sd = data;
+ unsigned long steps;
+
+ for (steps = 0; steps < sd->max_steps; steps++) {
+ long approx = percpu_counter_tree_approximate_sum(sd->probe);
+
+ percpu_counter_tree_add(sd->probe, sd->inc);
+ if (percpu_counter_tree_approximate_sum(sd->probe) != approx) {
+ copy_counter_state(sd->probe, sd->c);
+ break;
+ }
+ percpu_counter_tree_add(sd->c, sd->inc);
+ }
+ if (steps == sd->max_steps)
+ sd->overrun = true;
+ return 0;
+}
+
+static void do_hpcc_test_saturated_compare(struct kunit *test, unsigned long batch_size,
+ long inc)
+{
+ struct percpu_counter_tree *c = &counter[0], *exact = &counter[1], probe;
+ struct saturate_data sd = { .c = c, .probe = &probe, .inc = inc };
+ unsigned long accuracy;
+ long approx, precise, precise_min, precise_max;
+ int ret, cpu;
+
+ ret = percpu_counter_tree_init(&probe, batch_size, GFP_KERNEL);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ return;
+ ret = init_counters(batch_size);
+ KUNIT_EXPECT_EQ(test, ret, 0);
+ if (ret)
+ goto destroy_probe;
+ accuracy = percpu_counter_tree_approximate_accuracy(c);
+ sd.max_steps = batch_size + accuracy;
+ cpus_read_lock();
+ for_each_online_cpu(cpu) {
+ work_on_cpu(cpu, saturate_worker_fn, &sd);
+ KUNIT_EXPECT_FALSE(test, sd.overrun);
+ if (sd.overrun)
+ break;
+ }
+ cpus_read_unlock();
+
+ precise = percpu_counter_tree_precise_sum(c);
+ approx = percpu_counter_tree_approximate_sum(c);
+ kunit_info(test, "batch_size=%lu inc=%ld precise=%ld approx=%ld accuracy=%lu\n",
+ batch_size, inc, precise, approx, accuracy);
+
+ check_residuals(test, c);
+ check_residuals(test, &probe);
+
+ /* Accuracy contract. */
+ KUNIT_EXPECT_GE(test, approx, precise - (long)accuracy);
+ KUNIT_EXPECT_LE(test, approx, precise + (long)accuracy);
+ /* Saturating every possible CPU reaches the accuracy exactly. */
+ if (num_online_cpus() == nr_cpu_ids)
+ KUNIT_EXPECT_EQ(test, (precise - approx) * inc, (long)accuracy);
+ percpu_counter_tree_approximate_min_max_range(approx, accuracy,
+ &precise_min, &precise_max);
+ KUNIT_EXPECT_GE(test, precise, precise_min);
+ KUNIT_EXPECT_LE(test, precise, precise_max);
+
+ /* Comparisons against a value. */
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(c, precise));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare_value(c, precise));
+ KUNIT_EXPECT_EQ(test, -1, percpu_counter_tree_precise_compare_value(c, precise - 1));
+ KUNIT_EXPECT_EQ(test, 1, percpu_counter_tree_precise_compare_value(c, precise + 1));
+
+ /* Comparisons against a counter with the same precise sum, exactly approximated. */
+ percpu_counter_tree_set(exact, precise);
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_approximate_sum(exact), precise);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare(c, exact));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare(exact, c));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare(c, exact));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare(exact, c));
+
+ fini_counters();
+destroy_probe:
+ percpu_counter_tree_destroy(&probe);
+}
+
+/*
+ * Saturate the unpropagated residuals of every tree item reachable from
+ * online CPUs, upward and downward, which yields the largest distance
+ * between the precise and approximate sums of a settled counter in each
+ * direction, and check that the comparison
+ * functions do not return a wrong definitive answer. Small batch sizes
+ * are the most likely to expose margin errors, because the fan-out of
+ * the tree levels can be larger than the batch size.
+ */
+static void hpcc_test_saturated_compare(struct kunit *test)
+{
+ unsigned long batch_size_order;
+
+ for (batch_size_order = 1; batch_size_order <= 5; batch_size_order++) {
+ do_hpcc_test_saturated_compare(test, 1UL << batch_size_order, 1);
+ do_hpcc_test_saturated_compare(test, 1UL << batch_size_order, -1);
+ }
+}
+
+static void hpcc_test_check_config(struct kunit *test)
+{
+#ifdef CONFIG_SMP
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_check_config());
+#else
+ kunit_skip(test, "The configuration table requires CONFIG_SMP");
+#endif
+}
+
+static struct kunit_case hpcc_test_cases[] = {
+ KUNIT_CASE(hpcc_test_check_config),
+ KUNIT_CASE(hpcc_print_info),
+ KUNIT_CASE(hpcc_test_single_thread_first),
+ KUNIT_CASE(hpcc_test_single_thread_first_random),
+ KUNIT_CASE_SLOW(hpcc_test_single_thread_random),
+ KUNIT_CASE(hpcc_test_multi_thread_batch_increment),
+ KUNIT_CASE_SLOW(hpcc_test_multi_thread_random_walk),
+ KUNIT_CASE(hpcc_test_init_one),
+ KUNIT_CASE(hpcc_test_set),
+ KUNIT_CASE(hpcc_test_saturated_compare),
+ KUNIT_CASE(hpcc_test_contended_carries),
+ {}
+};
+
+static int hpcc_test_suite_init(struct kunit_suite *suite)
+{
+ hpcc_test_wq = alloc_workqueue("hpcc_test", WQ_PERCPU | WQ_CPU_INTENSIVE, 0);
+ return hpcc_test_wq ? 0 : -ENOMEM;
+}
+
+static void hpcc_test_suite_exit(struct kunit_suite *suite)
+{
+ destroy_workqueue(hpcc_test_wq);
+}
+
+static struct kunit_suite hpcc_test_suite = {
+ .name = "percpu_counter_tree",
+ .suite_init = hpcc_test_suite_init,
+ .suite_exit = hpcc_test_suite_exit,
+ .test_cases = hpcc_test_cases,
+};
+
+kunit_test_suite(hpcc_test_suite);
+
+MODULE_DESCRIPTION("Test cases for hierarchical per-CPU counters");
+MODULE_LICENSE("Dual MIT/GPL");
+MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 03/10] mm: use hierarchical per-cpu counters for the RSS counters
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
2026-11-02 19:06 ` [RFC PATCH v23 01/10] lib: introduce hierarchical per-cpu counters Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 02/10] lib: test " Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 04/10] tools/testing/hpcc: add userspace test of hierarchical per-CPU counters Mathieu Desnoyers
` (6 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Use hierarchical per-cpu counters for RSS tracking to bound the inaccuracy
of the per-mm RSS approximation on large many-core systems [1].
The approximation is read by /proc/PID/stat (rss), by the RSS high
watermark (VmHWM in /proc/PID/status, getrusage() ru_maxrss, taskstats
hiwater_rss), by the taskstats integral RSS, by NUMA balancing to scale
its scan period, and by the mark_victim OOM tracepoint.
/proc/PID/status, /proc/PID/statm, the OOM killer and the rss_stat
tracepoint use precise sums, which iterate over all CPUs for each read:
the tracepoint since commit f1a7941243c1 ("mm: convert mm's rss stats
into percpu_counter"), and the others since commit 82241a83cd15 ("mm:
fix the inaccurate memory statistics issue for users") and
commit 5898aa8f9a0b ("mm: fix OOM killer inaccuracy on large many-core
systems").
Here is a (possibly incomplete) list of the prior approaches that were
used or proposed, along with their downside:
1) Per-thread rss tracking: large error on many-thread processes.
2) Per-CPU counters: up to 12% slower for short-lived processes and 9%
increased system time in make test workloads [1]. Moreover, the
inaccuracy increases with O(n^2) with the number of CPUs.
3) Per-NUMA-node counters: requires atomics on fast-path (overhead),
error is high with systems that have lots of NUMA nodes (32 times
the number of NUMA nodes).
4) Use a precise per-cpu counter sum for each counter value query:
Requires iteration on each possible CPU for each sum, which
adds overhead on large many-core systems running many processes.
The approach proposed here is to replace the per-cpu counters by the
hierarchical per-cpu counters, which bounds the inaccuracy based on the
system topology with O(N*logN).
* Testing results:
Test hardware: 2 sockets AMD EPYC 9654 96-Core Processor (384 logical CPUs)
Methodology:
Comparing the current upstream implementation with the hierarchical
counters is done with a debug patch, which keeps both implementations
wired up in parallel, and a test program, neither part of this series.
The single-process, single-threaded program hops randomly across CPUs in
the system, calling mmap(2) and munmap(2) on random CPUs, keeping track of
an array of 100000 mapping slots, randomly choosing slots to either map 1
to 16 pages or unmap them.
get_mm_counter() is instrumented to compare both counter approximations
to the precise value, and to record the largest delta of each. The test
runs in a KVM guest with 384 vCPUs, each pinned to its own CPU of the test
hardware, with the NUMA topology of the host.
With the counters of this patch, before the single-threaded mode added
later in the series, the upstream implementation counter approximation
reaches an 830MB delta from the precise value within the first seconds,
while the mappings accumulate, compared to a 106MB delta with the
hierarchical counter. The hierarchical counter approximation is
guaranteed to be within 158.5MB of the precise value in both directions
on that hardware topology, compared to 1.1GB for the upstream
implementation (384 CPUs * 767 pages).
* Fast path implementation comparison
The new percpu_counter_tree_add() updates a per-cpu byte with a
this_cpu_try_cmpxchg() loop on the fast path, like the upstream
percpu_counter_add_batch(). When the per-cpu residual reaches the batch
size, it calls a slow path which "trickles up" the carry to upper level
counters with atomic_add_return(), each of them keeping its own residual.
In comparison, the upstream percpu_counter_add_batch() takes a global
raw_spin_lock_irqsave() when reaching the batch size, and flushes the
whole per-cpu count into the global count.
The hierarchical implementation is therefore expected to have less
contention on mid-sized allocations than the upstream counters because
the atomic counters tracking those bits are each shared by a fraction of
the CPUs.
* Benchmarks
Using will-it-scale page_fault1 benchmarks to compare the upstream
counters to the hierarchical counters of this patch. This is done with
hyperthreading disabled at runtime, so the counter tree keeps its shape
for 384 logical CPUs, while the upstream batch size follows the 192
online ones (384 instead of 768). The differences are within the
boot-to-boot spread of up to 3%, and the multi-threaded runs, bound by
the mmap_lock, have a standard deviation of 5% to 11%: no regression is
measured, and no gain is claimed. The numbers with the whole series are
in patch 7 and the cover letter.
upstream hierarchical delta
page_fault1_processes -s 100 -t 1 544932 557092 +2.2%
page_fault1_threads -s 100 -t 1 547501 557742 +1.9%
page_fault1_processes -s 100 -t 96 37374404 37580199 +0.6%
page_fault1_threads -s 100 -t 96 2311884 2299998 -0.5%
page_fault1_processes -s 100 -t 192 69491758 70590309 +1.6%
page_fault1_threads -s 100 -t 192 2284108 2271423 -0.6%
* Memory Use
Each mm_struct holds NR_MM_COUNTERS (4) counters, initialized together
by percpu_counter_tree_init_many() with a batch size of 32, so their tree
items share cache lines. Per mm, on a 64-bit arch with 64-byte cache
lines, compared to the upstream percpu counters, along with the maximum
inaccuracy of each counter in pages:
Bytes per mm Accuracy (pages)
nr_cpus fan-out hpcc upstream hpcc upstream
2 2 200 192 +-62 +-62
16 16 256 416 +-496 +-496
64 16,4 704 1184 +-3904 +-8128
128 8,16 1728 2208 +-7552 +-32640
256 8,4,8 3776 4256 +-21248 +-130816
384 8,8,8 6336 6304 +-40576 +-294528
512 8,8,8 6848 8352 +-44544 +-523776
1024 8,8,16 13504 16544 +-89088 +-2096128
4096 8,8,8,8 53952 65696 +-471040 +-33550336
This counts the 4 counter structures, their per-cpu data, and the tree
items, without the rounding of the slab cache holding them. The
fan-out is listed from the per-cpu counters to the root. Up to 32 CPUs,
the tree is flat. Up to 16 CPUs, its accuracy matches the upstream
counters, whose batch size of max(32, 2 * nr_cpus) grows beyond, making
them less accurate than the hierarchical counters, except from 33 to 39
CPUs, where the intermediate counters of the 16,4 tree make the
hierarchical counters up to 1.37 times less accurate.
The hierarchical counters use less memory than the upstream counters
from 3 to 64 CPUs. The tree is shaped for nr_cpus rounded up to a power
of 2: when nr_cpus is a power of 2, they also use less memory beyond 64
CPUs (at most 0.89 times as much). Between powers of 2, fewer CPUs
share the cost of the tree items: 1.01 times at 384 logical CPUs, 1.09
at 192 and 0.94 at 96, and up to 1.47 times just above a power of 2 (at
129 CPUs, 1.23 at 65 and 1.36 at 257).
* mm_struct layout
percpu_counter_tree_init_many() allocates the per-cpu data and the tree
items of the RSS counters, so their size in mm_struct does not depend on
the number of CPUs: struct mm_struct shrinks by 32 bytes, as a struct
percpu_counter_tree is 32 bytes, compared to 40 for a struct
percpu_counter.
* rss_stat tracepoint
The rss_stat tracepoint keeps reporting the precise sum, now computed
from the hierarchical per-cpu counter.
Link: https://lore.kernel.org/lkml/20250331223516.7810-2-sweettea-kernel@dorminy.me/ # [1]
Link: https://lkml.kernel.org/r/20260227153730.1556542-4-mathieu.desnoyers@efficios.com
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Christoph Lameter <cl@gentwo.org>
Cc: Martin Liu <liumartin@google.com>
Cc: David Rientjes <rientjes@google.com>
Cc: christian.koenig@amd.com
Cc: Shakeel Butt <shakeel.butt@linux.dev>
Cc: SeongJae Park <sj@kernel.org>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Sweet Tea Dorminy <sweettea-kernel@dorminy.me>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: Christian Brauner <brauner@kernel.org>
Cc: Wei Yang <richard.weiyang@gmail.com>
Cc: David Hildenbrand <david@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Yu Zhao <yuzhao@google.com>
Cc: Roman Gushchin <roman.gushchin@linux.dev>
Cc: Mateusz Guzik <mjguzik@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Aboorva Devarajan <aboorvad@linux.ibm.com>
Cc: David Carlier <devnexen@gmail.com>
Cc: Josh Law <objecting@objecting.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: linux-mm@kvack.org
---
Changes since v22:
- The library allocates the per-cpu counters and the tree items of the
RSS counters: mm_struct holds no tree items, and the static init_mm
and efi_mm need no change.
- check_mm(): sum each RSS counter once.
- Keep reporting the precise sum in the rss_stat tracepoint. Switching
it to the approximation is done by a separate patch.
- Initialize the 4 RSS counters together so their tree items share cache
lines.
- Fix checkpatch warnings.
---
include/linux/mm.h | 10 +++++-----
include/linux/mm_types.h | 3 ++-
include/trace/events/kmem.h | 3 +--
kernel/fork.c | 13 +++++++++----
4 files changed, 17 insertions(+), 12 deletions(-)
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 9f167950926a..36242c7ff84f 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -3607,33 +3607,33 @@ static inline bool get_user_page_fast_only(unsigned long addr,
*/
static inline unsigned long get_mm_counter(struct mm_struct *mm, int member)
{
- return percpu_counter_read_positive(&mm->rss_stat[member]);
+ return percpu_counter_tree_approximate_sum_positive(&mm->rss_stat[member]);
}
static inline unsigned long get_mm_counter_sum(struct mm_struct *mm, int member)
{
- return percpu_counter_sum_positive(&mm->rss_stat[member]);
+ return percpu_counter_tree_precise_sum_positive(&mm->rss_stat[member]);
}
void mm_trace_rss_stat(struct mm_struct *mm, int member);
static inline void add_mm_counter(struct mm_struct *mm, int member, long value)
{
- percpu_counter_add(&mm->rss_stat[member], value);
+ percpu_counter_tree_add(&mm->rss_stat[member], value);
mm_trace_rss_stat(mm, member);
}
static inline void inc_mm_counter(struct mm_struct *mm, int member)
{
- percpu_counter_inc(&mm->rss_stat[member]);
+ percpu_counter_tree_add(&mm->rss_stat[member], 1);
mm_trace_rss_stat(mm, member);
}
static inline void dec_mm_counter(struct mm_struct *mm, int member)
{
- percpu_counter_dec(&mm->rss_stat[member]);
+ percpu_counter_tree_add(&mm->rss_stat[member], -1);
mm_trace_rss_stat(mm, member);
}
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 1ed35d258d2e..20b4517b7329 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -19,6 +19,7 @@
#include <linux/workqueue.h>
#include <linux/seqlock.h>
#include <linux/percpu_counter.h>
+#include <linux/percpu_counter_tree.h>
#include <linux/types.h>
#include <linux/futex_types.h>
#include <linux/rseq_types.h>
@@ -1350,7 +1351,7 @@ struct mm_struct {
unsigned long saved_e_flags;
#endif
- struct percpu_counter rss_stat[NR_MM_COUNTERS];
+ struct percpu_counter_tree rss_stat[NR_MM_COUNTERS];
struct linux_binfmt *binfmt;
diff --git a/include/trace/events/kmem.h b/include/trace/events/kmem.h
index cd7920c81f85..ac4c96db7638 100644
--- a/include/trace/events/kmem.h
+++ b/include/trace/events/kmem.h
@@ -448,8 +448,7 @@ TRACE_EVENT(rss_stat,
*/
__entry->curr = current->mm == mm && !(current->flags & PF_KTHREAD);
__entry->member = member;
- __entry->size = (percpu_counter_sum_positive(&mm->rss_stat[member])
- << PAGE_SHIFT);
+ __entry->size = get_mm_counter_sum(mm, member) << PAGE_SHIFT;
),
TP_printk("mm_id=%u curr=%d type=%s size=%ldB",
diff --git a/kernel/fork.c b/kernel/fork.c
index 8b108ed37152..02e25115ff85 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -137,6 +137,11 @@
*/
#define MAX_THREADS FUTEX_TID_MASK
+/*
+ * Batch size of rss stat approximation
+ */
+#define RSS_STAT_BATCH_SIZE 32
+
/*
* Protected counters by write_lock_irq(&tasklist_lock)
*/
@@ -633,7 +638,7 @@ static void check_mm(struct mm_struct *mm)
"Please make sure 'struct resident_page_types[]' is updated as well");
for (i = 0; i < NR_MM_COUNTERS; i++) {
- long x = percpu_counter_sum(&mm->rss_stat[i]);
+ long x = percpu_counter_tree_precise_sum(&mm->rss_stat[i]);
if (unlikely(x)) {
pr_alert("BUG: Bad rss-counter state mm:%p type:%s val:%ld Comm:%s Pid:%d\n",
@@ -738,7 +743,7 @@ void __mmdrop(struct mm_struct *mm)
check_mm(mm);
mm_pasid_drop(mm);
mm_destroy_cid(mm);
- percpu_counter_destroy_many(mm->rss_stat, NR_MM_COUNTERS);
+ percpu_counter_tree_destroy_many(mm->rss_stat, NR_MM_COUNTERS);
free_mm(mm);
}
@@ -1143,8 +1148,8 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
if (mm_alloc_sched(mm))
goto fail_sched;
- if (percpu_counter_init_many(mm->rss_stat, 0, GFP_KERNEL_ACCOUNT,
- NR_MM_COUNTERS))
+ if (percpu_counter_tree_init_many(mm->rss_stat, NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE,
+ GFP_KERNEL_ACCOUNT))
goto fail_pcpu;
lru_gen_init_mm(mm);
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 04/10] tools/testing/hpcc: add userspace test of hierarchical per-CPU counters
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (2 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 03/10] mm: use hierarchical per-cpu counters for the RSS counters Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 05/10] mm: report the approximate RSS in the rss_stat tracepoint Mathieu Desnoyers
` (5 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
The KUnit test only covers the topology of the machine it runs on.
Add a userspace test which builds lib/percpu_counter_tree.c with a
simulated topology, which allows testing every supported tree
configuration on a single machine, following the approach of
tools/testing/vma and tools/testing/radix-tree.
A small shim header provides the kernel environment needed by the
library, on top of tools/include: per-CPU data is an array indexed by
the simulated current CPU, and atomic operations are plain operations,
because the test is single-threaded. It therefore only covers settled
counters.
Validate the configuration table, then, for each simulated number of
CPUs (1 to 65536, up to 1048576 with -a) and batch size (2 to 128):
- Saturate the counter upward and downward: leave every tree item with
its largest positive (or negative) residual which has not been
propagated yet, check that the distance between the precise and
approximate sums matches the residual capacity of the tree, computed
from the configuration table, which is exactly the accuracy range, the
same in both directions, and check the accuracy range contract and the
comparison functions in these worst-case states. A lost carry fails
the saturation rather than hanging it.
- Random walk: apply random increments from random CPUs to two counters,
and check the accuracy range contract and the comparison functions
against shadow sums after each increment.
Along with the accuracy range contract, check the residuals of the tree
items, and that no carry was lost or duplicated.
The comparison checks include the edges of the possible precise range:
the approximate comparison against a value must be definitive exactly
outside of [approx - over, approx + under].
Usage:
make -C tools/testing/hpcc
tools/testing/hpcc/hpcc [-a]
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
MAINTAINERS | 1 +
tools/testing/hpcc/.gitignore | 2 +
tools/testing/hpcc/Makefile | 18 +
tools/testing/hpcc/include/hpcc_shim.h | 177 ++++++++
tools/testing/hpcc/include/kunit/visibility.h | 2 +
tools/testing/hpcc/include/linux/args.h | 4 +
tools/testing/hpcc/include/linux/atomic.h | 2 +
tools/testing/hpcc/include/linux/bug.h | 2 +
tools/testing/hpcc/include/linux/cache.h | 2 +
tools/testing/hpcc/include/linux/cpumask.h | 2 +
tools/testing/hpcc/include/linux/errno.h | 3 +
tools/testing/hpcc/include/linux/limits.h | 2 +
tools/testing/hpcc/include/linux/math.h | 2 +
tools/testing/hpcc/include/linux/percpu.h | 2 +
.../hpcc/include/linux/percpu_counter_tree.h | 2 +
tools/testing/hpcc/include/linux/preempt.h | 2 +
tools/testing/hpcc/include/linux/slab.h | 2 +
tools/testing/hpcc/main.c | 413 ++++++++++++++++++
18 files changed, 640 insertions(+)
create mode 100644 tools/testing/hpcc/.gitignore
create mode 100644 tools/testing/hpcc/Makefile
create mode 100644 tools/testing/hpcc/include/hpcc_shim.h
create mode 100644 tools/testing/hpcc/include/kunit/visibility.h
create mode 100644 tools/testing/hpcc/include/linux/args.h
create mode 100644 tools/testing/hpcc/include/linux/atomic.h
create mode 100644 tools/testing/hpcc/include/linux/bug.h
create mode 100644 tools/testing/hpcc/include/linux/cache.h
create mode 100644 tools/testing/hpcc/include/linux/cpumask.h
create mode 100644 tools/testing/hpcc/include/linux/errno.h
create mode 100644 tools/testing/hpcc/include/linux/limits.h
create mode 100644 tools/testing/hpcc/include/linux/math.h
create mode 100644 tools/testing/hpcc/include/linux/percpu.h
create mode 100644 tools/testing/hpcc/include/linux/percpu_counter_tree.h
create mode 100644 tools/testing/hpcc/include/linux/preempt.h
create mode 100644 tools/testing/hpcc/include/linux/slab.h
create mode 100644 tools/testing/hpcc/main.c
diff --git a/MAINTAINERS b/MAINTAINERS
index 21348605d06e..4d421a784e88 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -11956,6 +11956,7 @@ F: Documentation/core-api/percpu-counter-tree.rst
F: include/linux/percpu_counter_tree.h
F: lib/percpu_counter_tree.c
F: lib/tests/percpu_counter_tree_kunit.c
+F: tools/testing/hpcc/
HIGH-RESOLUTION TIMERS, TIMER WHEEL, CLOCKEVENTS
M: Anna-Maria Behnsen <anna-maria@linutronix.de>
diff --git a/tools/testing/hpcc/.gitignore b/tools/testing/hpcc/.gitignore
new file mode 100644
index 000000000000..f362a8a46868
--- /dev/null
+++ b/tools/testing/hpcc/.gitignore
@@ -0,0 +1,2 @@
+# SPDX-License-Identifier: GPL-2.0+ OR MIT
+hpcc
diff --git a/tools/testing/hpcc/Makefile b/tools/testing/hpcc/Makefile
new file mode 100644
index 000000000000..e4758643a3f0
--- /dev/null
+++ b/tools/testing/hpcc/Makefile
@@ -0,0 +1,18 @@
+# SPDX-License-Identifier: GPL-2.0+ OR MIT
+
+.PHONY: default clean
+
+default: hpcc
+
+CFLAGS += -O2 -g -Wall -I./include -I../../include -fno-strict-overflow -fno-strict-aliasing
+CFLAGS += -DCONFIG_SMP -DCONFIG_KUNIT=1 -D'NR_CPUS=(1U << 20)'
+
+DEPS = ../../../lib/percpu_counter_tree.c \
+ ../../../include/linux/percpu_counter_tree.h \
+ include/hpcc_shim.h
+
+hpcc: main.c $(DEPS)
+ $(CC) $(CFLAGS) -o $@ main.c $(LDLIBS)
+
+clean:
+ $(RM) hpcc
diff --git a/tools/testing/hpcc/include/hpcc_shim.h b/tools/testing/hpcc/include/hpcc_shim.h
new file mode 100644
index 000000000000..7e268de984c6
--- /dev/null
+++ b/tools/testing/hpcc/include/hpcc_shim.h
@@ -0,0 +1,177 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/*
+ * Minimal userspace environment to build lib/percpu_counter_tree.c.
+ *
+ * The test is single-threaded: per-CPU data is an array indexed by the
+ * simulated current CPU, and atomic operations are plain operations.
+ */
+#ifndef _HPCC_SHIM_H
+#define _HPCC_SHIM_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+/* From tools/include. */
+#include <linux/compiler.h>
+#include <linux/gfp_types.h>
+#include <linux/init.h>
+#include <linux/kconfig.h>
+#include <linux/kernel.h>
+#include <linux/types.h>
+
+#define __ro_after_init
+#define __percpu
+#define SMP_CACHE_BYTES 64
+#define ____cacheline_aligned_in_smp __aligned(SMP_CACHE_BYTES)
+#define S8_MAX INT8_MAX
+
+#undef abs
+#define abs(x) ({ typeof(x) __x = (x); __x < 0 ? -__x : __x; })
+
+#define pr_err(...) fprintf(stderr, __VA_ARGS__)
+#define pr_info(...) do { if (0) printf(__VA_ARGS__); } while (0)
+
+extern unsigned long hpcc_nr_warnings;
+
+#define WARN(cond, ...) ({ \
+ int __ret_warn = !!(cond); \
+ if (__ret_warn) { \
+ hpcc_nr_warnings++; \
+ fprintf(stderr, "WARNING at %s:%d: ", __FILE__, __LINE__); \
+ fprintf(stderr, __VA_ARGS__); \
+ } \
+ __ret_warn; \
+})
+#define WARN_ON(cond) WARN(cond, "%s\n", #cond)
+#define WARN_ON_ONCE(cond) WARN_ON(cond)
+
+static inline int get_count_order(unsigned int count)
+{
+ int order;
+
+ if (!count)
+ return -1;
+ order = 31 - __builtin_clz(count);
+ if (count & (count - 1))
+ order++;
+ return order;
+}
+
+#define atomic_long_read(v) READ_ONCE((v)->counter)
+#define atomic_long_set(v, i) WRITE_ONCE((v)->counter, (i))
+#define atomic_long_add(i, v) ((void)((v)->counter += (i)))
+#define atomic_long_add_return_relaxed(i, v) ((v)->counter += (i))
+#define atomic_long_add_return_release(i, v) ((v)->counter += (i))
+#define smp_rmb() barrier()
+
+static inline bool atomic_long_try_cmpxchg_relaxed(atomic_long_t *v, long *old, long new)
+{
+ if (v->counter == *old) {
+ v->counter = new;
+ return true;
+ }
+ *old = v->counter;
+ return false;
+}
+
+/* Simulated topology, and CPU on which the current code runs. */
+extern unsigned int nr_cpu_ids;
+extern unsigned int hpcc_current_cpu;
+
+#define raw_smp_processor_id() hpcc_current_cpu
+#define for_each_possible_cpu(cpu) for ((cpu) = 0; (cpu) < (int)nr_cpu_ids; (cpu)++)
+
+/*
+ * Each per-CPU allocation reserves HPCC_PCPU_UNIT bytes per CPU, so
+ * per_cpu_ptr() can be applied to a pointer within an allocation.
+ */
+#define HPCC_PCPU_UNIT 64
+
+static inline void *__alloc_percpu_gfp(size_t size, size_t align, gfp_t gfp)
+{
+ if (size > HPCC_PCPU_UNIT || align > HPCC_PCPU_UNIT)
+ return NULL;
+ return calloc(nr_cpu_ids, HPCC_PCPU_UNIT);
+}
+
+static inline void free_percpu(void *ptr)
+{
+ free(ptr);
+}
+
+#define SLAB_PANIC 0
+
+struct kmem_cache {
+ size_t size;
+ size_t align;
+};
+
+static inline struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
+ unsigned int align, unsigned int flags,
+ void (*ctor)(void *))
+{
+ struct kmem_cache *s = malloc(sizeof(*s));
+
+ if (!s)
+ abort();
+ s->size = size;
+ s->align = align;
+ return s;
+}
+
+static inline void kmem_cache_destroy(struct kmem_cache *s)
+{
+ free(s);
+}
+
+static inline void *kmem_cache_zalloc(struct kmem_cache *s, gfp_t gfp)
+{
+ /* The allocation size needs to be a multiple of the alignment. */
+ void *p = aligned_alloc(s->align, (s->size + s->align - 1) / s->align * s->align);
+
+ if (p)
+ memset(p, 0, s->size);
+ return p;
+}
+
+static inline void kmem_cache_free(struct kmem_cache *s, void *p)
+{
+ free(p);
+}
+
+static inline void *kzalloc(size_t size, gfp_t gfp)
+{
+ return calloc(1, size);
+}
+
+static inline void kfree(void *p)
+{
+ free(p);
+}
+
+#define per_cpu_ptr(ptr, cpu) \
+ ((typeof(ptr))((char *)(ptr) + (size_t)(cpu) * HPCC_PCPU_UNIT))
+
+/* Level 0 counters are the only per-CPU data: s8. */
+static inline bool __hpcc_this_cpu_try_cmpxchg(s8 *pcp, s8 *old, s8 new)
+{
+ s8 *p = per_cpu_ptr(pcp, hpcc_current_cpu);
+
+ if (*p != *old) {
+ *old = *p;
+ return false;
+ }
+ *p = new;
+ return true;
+}
+
+#define this_cpu_read(pcp) (*per_cpu_ptr(&(pcp), hpcc_current_cpu))
+#define this_cpu_try_cmpxchg(pcp, ovalp, nval) \
+ __hpcc_this_cpu_try_cmpxchg(&(pcp), (ovalp), (nval))
+
+#endif /* _HPCC_SHIM_H */
diff --git a/tools/testing/hpcc/include/kunit/visibility.h b/tools/testing/hpcc/include/kunit/visibility.h
new file mode 100644
index 000000000000..dfcbfd01a415
--- /dev/null
+++ b/tools/testing/hpcc/include/kunit/visibility.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#define EXPORT_SYMBOL_IF_KUNIT(symbol)
diff --git a/tools/testing/hpcc/include/linux/args.h b/tools/testing/hpcc/include/linux/args.h
new file mode 100644
index 000000000000..0c00a85fdd21
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/args.h
@@ -0,0 +1,4 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* Also defined by the C library <sys/cdefs.h>. */
+#undef __CONCAT
+#include "../../../../../include/linux/args.h"
diff --git a/tools/testing/hpcc/include/linux/atomic.h b/tools/testing/hpcc/include/linux/atomic.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/atomic.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/bug.h b/tools/testing/hpcc/include/linux/bug.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/bug.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/cache.h b/tools/testing/hpcc/include/linux/cache.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/cache.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/cpumask.h b/tools/testing/hpcc/include/linux/cpumask.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/cpumask.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/errno.h b/tools/testing/hpcc/include/linux/errno.h
new file mode 100644
index 000000000000..45fdd60261e7
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/errno.h
@@ -0,0 +1,3 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* Also included by the C library <errno.h>: only provide the error numbers. */
+#include <asm/errno.h>
diff --git a/tools/testing/hpcc/include/linux/limits.h b/tools/testing/hpcc/include/linux/limits.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/limits.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/math.h b/tools/testing/hpcc/include/linux/math.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/math.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/percpu.h b/tools/testing/hpcc/include/linux/percpu.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/percpu.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/percpu_counter_tree.h b/tools/testing/hpcc/include/linux/percpu_counter_tree.h
new file mode 100644
index 000000000000..065a2aca4d5b
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/percpu_counter_tree.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../../../../../include/linux/percpu_counter_tree.h"
diff --git a/tools/testing/hpcc/include/linux/preempt.h b/tools/testing/hpcc/include/linux/preempt.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/preempt.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/include/linux/slab.h b/tools/testing/hpcc/include/linux/slab.h
new file mode 100644
index 000000000000..b2aa26415cca
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/slab.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
diff --git a/tools/testing/hpcc/main.c b/tools/testing/hpcc/main.c
new file mode 100644
index 000000000000..b707754aab0a
--- /dev/null
+++ b/tools/testing/hpcc/main.c
@@ -0,0 +1,413 @@
+// SPDX-License-Identifier: GPL-2.0+ OR MIT
+/*
+ * Userspace test of the hierarchical per-CPU counters (lib/percpu_counter_tree.c).
+ *
+ * The library is built with a simulated topology, which allows testing
+ * every supported tree configuration on a single machine, whereas the
+ * KUnit test only covers the topology of the machine it runs on.
+ *
+ * For each simulated number of CPUs and batch size:
+ *
+ * - Saturate the counter upward and downward: leave every tree item with
+ * its largest positive (or negative) residual which has not been
+ * propagated yet, check that the distance between the precise and
+ * approximate sums matches the residual capacity of the tree in that
+ * direction, and check the accuracy range contract and the comparison
+ * functions in these worst-case states.
+ *
+ * - Random walk: apply random increments from random CPUs to two counters,
+ * and check the accuracy range contract and the comparison functions
+ * against shadow sums after each increment.
+ *
+ * The test is single-threaded, so it only covers settled counters.
+ */
+
+#include <stdarg.h>
+#include "hpcc_shim.h"
+
+unsigned int nr_cpu_ids;
+unsigned int hpcc_current_cpu;
+unsigned long hpcc_nr_warnings;
+
+#include "../../../lib/percpu_counter_tree.c"
+
+#define MAX_REPORTED_FAILURES 10
+
+static unsigned long nr_case_failures;
+
+#define CHECK(cond) do { \
+ if (!(cond)) { \
+ if (nr_case_failures++ < MAX_REPORTED_FAILURES) \
+ printf("# %s:%d: check failed: %s\n", \
+ __FILE__, __LINE__, #cond); \
+ } \
+} while (0)
+
+static uint64_t rng_state = 88172645463325252ULL;
+
+static uint64_t rnd(void)
+{
+ rng_state ^= rng_state << 13;
+ rng_state ^= rng_state >> 7;
+ rng_state ^= rng_state << 17;
+ return rng_state;
+}
+
+static int sign(long v)
+{
+ return (v > 0) - (v < 0);
+}
+
+struct test_counter {
+ struct percpu_counter_tree tree;
+ long shadow; /* Expected precise sum. */
+};
+
+int scnprintf(char *buf, size_t size, const char *fmt, ...)
+{
+ va_list args;
+ int len;
+
+ if (!size)
+ return 0;
+ va_start(args, fmt);
+ len = vsnprintf(buf, size, fmt, args);
+ va_end(args);
+ return len < (int)size ? len : (int)size - 1;
+}
+
+static void hpcc_init_topology(unsigned int nr_cpus)
+{
+ nr_cpu_ids = nr_cpus;
+ /* Reset the state accumulated by a prior subsystem initialization. */
+ kmem_cache_destroy(tree_topology.items_cachep);
+ memset(&tree_topology, 0, sizeof(tree_topology));
+ tree_topology.nr_items = UINT_MAX;
+ CHECK(!percpu_counter_tree_subsystem_init());
+}
+
+static int test_counter_init(struct test_counter *c, unsigned long batch_size)
+{
+ c->shadow = 0;
+ return percpu_counter_tree_init(&c->tree, batch_size, GFP_KERNEL);
+}
+
+static void test_counter_destroy(struct test_counter *c)
+{
+ percpu_counter_tree_destroy(&c->tree);
+}
+
+static void test_counter_add(struct test_counter *c, unsigned int cpu, long inc)
+{
+ hpcc_current_cpu = cpu;
+ percpu_counter_tree_add(&c->tree, inc);
+ c->shadow += inc;
+}
+
+static void test_counter_set(struct test_counter *c, long v)
+{
+ percpu_counter_tree_set(&c->tree, v);
+ c->shadow = v;
+}
+
+/*
+ * Residual capacity of the tree items above level 0, in either direction:
+ * sum of the largest residual which each item can hold without propagating
+ * a carry. A level L item only receives multiples of the level L - 1 carry,
+ * and propagates once its residual reaches the level L carry, so it holds
+ * at most bit(L) - bit(L - 1) in either direction.
+ */
+static unsigned long tree_item_capacity(unsigned long batch_size)
+{
+ unsigned long capacity = 0, lo = batch_size, hi;
+ unsigned int level, level_items;
+
+ level_items = 1U << tree_topology.nr_cpus_order;
+ for (level = 1; level < tree_topology.config->nr_levels; level++) {
+ unsigned int n_arity_order = tree_topology.config->n_arity_order[level - 1];
+
+ level_items >>= n_arity_order;
+ hi = lo << n_arity_order;
+ capacity += level_items * (hi - lo);
+ lo = hi;
+ }
+ return capacity;
+}
+
+/*
+ * Residual capacity of the tree, in either direction: a level 0 counter
+ * holds at most batch_size - 1 on top of the item capacity.
+ */
+static unsigned long tree_residual_capacity(unsigned long batch_size)
+{
+ return nr_cpu_ids * (batch_size - 1) + tree_item_capacity(batch_size);
+}
+
+/* Copy the state of counter @src into counter @dst, of the same topology. */
+static void test_counter_copy(struct test_counter *dst, struct test_counter *src)
+{
+ percpu_counter_tree_copy_state(&dst->tree, &src->tree);
+ dst->shadow = src->shadow;
+}
+
+/*
+ * Check the accuracy range contract, and the comparison of the counter
+ * against values around its precise sum and its possible precise range.
+ */
+static void check_counter(struct test_counter *c)
+{
+ struct percpu_counter_tree *t = &c->tree;
+ long approx = percpu_counter_tree_approximate_sum(t);
+ long precise = c->shadow, precise_min, precise_max;
+ unsigned long accuracy;
+ long values[7];
+ unsigned int i;
+
+ CHECK(percpu_counter_tree_precise_sum(t) == precise);
+ CHECK(!percpu_counter_tree_check_residuals(t));
+
+ /* precise - accuracy <= approx <= precise + accuracy */
+ accuracy = percpu_counter_tree_approximate_accuracy(t);
+ CHECK(approx >= precise - (long)accuracy);
+ CHECK(approx <= precise + (long)accuracy);
+
+ percpu_counter_tree_approximate_min_max_range(approx, accuracy,
+ &precise_min, &precise_max);
+ CHECK(precise >= precise_min);
+ CHECK(precise <= precise_max);
+
+ /* Approximate comparison is definitive exactly outside of the precise range. */
+ CHECK(percpu_counter_tree_approximate_compare_value(t, precise_min - 1) == -1);
+ CHECK(percpu_counter_tree_approximate_compare_value(t, precise_min) == 0);
+ CHECK(percpu_counter_tree_approximate_compare_value(t, precise_max) == 0);
+ CHECK(percpu_counter_tree_approximate_compare_value(t, precise_max + 1) == 1);
+
+ values[0] = precise - 1;
+ values[1] = precise;
+ values[2] = precise + 1;
+ values[3] = precise_min - 1;
+ values[4] = precise_min;
+ values[5] = precise_max;
+ values[6] = precise_max + 1;
+ for (i = 0; i < ARRAY_SIZE(values); i++) {
+ long v = values[i];
+ int expect = sign(v - precise);
+ int res = percpu_counter_tree_approximate_compare_value(t, v);
+
+ CHECK(res == 0 || res == expect);
+ CHECK(percpu_counter_tree_precise_compare_value(t, v) == expect);
+ }
+}
+
+/* Check the comparison of two counters against their shadow sums. */
+static void check_counter_pair(struct test_counter *a, struct test_counter *b)
+{
+ int expect = sign(a->shadow - b->shadow);
+ int res = percpu_counter_tree_approximate_compare(&a->tree, &b->tree);
+
+ CHECK(res == 0 || res == expect);
+ CHECK(percpu_counter_tree_precise_compare(&a->tree, &b->tree) == expect);
+ res = percpu_counter_tree_approximate_compare(&b->tree, &a->tree);
+ CHECK(res == 0 || res == -expect);
+ CHECK(percpu_counter_tree_precise_compare(&b->tree, &a->tree) == -expect);
+}
+
+/*
+ * On each CPU, add @inc (1 or -1) until the next addition would propagate a
+ * carry to the approximate sum. This leaves every tree item on the path from
+ * this CPU to the root holding its largest residual in the direction of @inc.
+ * Each addition is first tried on @probe, which holds the same state as @c:
+ * reverting an addition which reached the approximate sum would not restore
+ * the residuals subtracted on the way. The path from a CPU to the root
+ * holds less than the accuracy bound: more additions mean that a carry was
+ * lost.
+ */
+static void saturate(struct test_counter *c, struct test_counter *probe, long inc)
+{
+ unsigned long max_steps;
+ unsigned int cpu;
+
+ max_steps = percpu_counter_tree_approximate_accuracy(&c->tree) +
+ (1UL << c->tree.batch_order);
+ for (cpu = 0; cpu < nr_cpu_ids; cpu++) {
+ unsigned long steps;
+
+ for (steps = 0; steps < max_steps; steps++) {
+ long approx = percpu_counter_tree_approximate_sum(&probe->tree);
+
+ test_counter_add(probe, cpu, inc);
+ if (percpu_counter_tree_approximate_sum(&probe->tree) != approx) {
+ test_counter_copy(probe, c);
+ break;
+ }
+ test_counter_add(c, cpu, inc);
+ }
+ if (steps == max_steps) {
+ CHECK(0);
+ return;
+ }
+ }
+}
+
+static void test_saturated(unsigned long batch_size, long inc)
+{
+ struct test_counter c, probe, exact;
+ unsigned long accuracy;
+ long approx, delta;
+
+ if (test_counter_init(&c, batch_size) || test_counter_init(&probe, batch_size) ||
+ test_counter_init(&exact, batch_size)) {
+ CHECK(0);
+ return;
+ }
+ saturate(&c, &probe, inc);
+ approx = percpu_counter_tree_approximate_sum(&c.tree);
+ accuracy = percpu_counter_tree_approximate_accuracy(&c.tree);
+ /* Symmetric residuals: the accuracy is reached in both directions. */
+ CHECK((c.shadow - approx) * inc == (long)tree_residual_capacity(batch_size));
+ CHECK((c.shadow - approx) * inc == (long)accuracy);
+ check_counter(&c);
+
+ /* Compare with exactly approximated counters around the saturated precise sum. */
+ for (delta = -1; delta <= 1; delta++) {
+ test_counter_set(&exact, c.shadow + delta);
+ CHECK(percpu_counter_tree_approximate_sum(&exact.tree) == exact.shadow);
+ check_counter_pair(&c, &exact);
+ }
+ test_counter_destroy(&c);
+ test_counter_destroy(&probe);
+ test_counter_destroy(&exact);
+}
+
+static long random_increment(unsigned long batch_size)
+{
+ long v;
+
+ switch (rnd() % 4) {
+ case 0:
+ v = rnd() % 4;
+ break;
+ case 1:
+ v = rnd() % (4 * batch_size);
+ break;
+ case 2:
+ v = rnd() % (64 * batch_size);
+ break;
+ default:
+ v = rnd() % 1000000;
+ break;
+ }
+ return rnd() & 1 ? v : -v;
+}
+
+static void test_random_walk(unsigned long batch_size, unsigned long nr_steps)
+{
+ struct test_counter c[2];
+ unsigned long step;
+
+ if (test_counter_init(&c[0], batch_size) || test_counter_init(&c[1], batch_size)) {
+ CHECK(0);
+ return;
+ }
+ for (step = 0; step < nr_steps; step++) {
+ struct test_counter *t = &c[rnd() & 1];
+
+ test_counter_add(t, rnd() % nr_cpu_ids, random_increment(batch_size));
+ /* Bring the counters close to each other to exercise the precise comparison. */
+ if (!(rnd() % 8)) {
+ long delta = c[0].shadow - c[1].shadow;
+ unsigned long accuracy;
+
+ accuracy = percpu_counter_tree_approximate_accuracy(&c[0].tree);
+ delta += (long)(rnd() % (2 * accuracy + 1)) - (long)accuracy;
+ test_counter_add(&c[1], rnd() % nr_cpu_ids, delta);
+ }
+ check_counter(t);
+ check_counter_pair(&c[0], &c[1]);
+ }
+ test_counter_destroy(&c[0]);
+ test_counter_destroy(&c[1]);
+}
+
+static const unsigned int test_nr_cpus[] = {
+ 1, 2, 3, 4, 5, 8, 9, 16, 17, 32, 33, 64, 65, 100, 128, 256, 512,
+ 1000, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
+};
+
+/* Exhaustive mode: also cover the largest supported configurations. */
+static const unsigned int test_nr_cpus_large[] = {
+ 1U << 17, 1U << 18, 1U << 19, 1U << 20,
+};
+
+static const unsigned long test_batch_sizes[] = { 2, 4, 8, 16, 32, 64, 128 };
+
+static int test_num;
+
+static int run_case(unsigned int nr_cpus, unsigned long batch_size)
+{
+ /* Each check iterates over all CPUs: bound the random walk cost. */
+ unsigned long nr_steps = 10000000 / nr_cpus;
+
+ if (nr_steps < 100)
+ nr_steps = 100;
+ if (nr_steps > 50000)
+ nr_steps = 50000;
+
+ nr_case_failures = 0;
+ hpcc_nr_warnings = 0;
+ hpcc_init_topology(nr_cpus);
+ test_saturated(batch_size, 1);
+ test_saturated(batch_size, -1);
+ test_random_walk(batch_size, nr_steps);
+ CHECK(!hpcc_nr_warnings);
+ printf("%sok %d - nr_cpus=%u batch_size=%lu\n", nr_case_failures ? "not " : "",
+ ++test_num, nr_cpus, batch_size);
+ if (nr_case_failures > MAX_REPORTED_FAILURES)
+ printf("# ... %lu failed checks in total\n", nr_case_failures);
+ return nr_case_failures ? 1 : 0;
+}
+
+static int run_check_config(void)
+{
+ unsigned int nr_errors = percpu_counter_tree_check_config();
+
+ printf("%sok %d - configuration table\n", nr_errors ? "not " : "", ++test_num);
+ return nr_errors ? 1 : 0;
+}
+
+static void usage(const char *name)
+{
+ fprintf(stderr, "Usage: %s [-a]\n", name);
+ fprintf(stderr, " -a Also test the largest supported numbers of CPUs (slow).\n");
+}
+
+int main(int argc, char **argv)
+{
+ unsigned int i, j, nr_tests;
+ bool large = false;
+ int failed = 0;
+
+ if (argc > 2 || (argc == 2 && strcmp(argv[1], "-a"))) {
+ usage(argv[0]);
+ return 2;
+ }
+ if (argc == 2)
+ large = true;
+
+ nr_tests = 1 + ARRAY_SIZE(test_nr_cpus) * ARRAY_SIZE(test_batch_sizes);
+ if (large)
+ nr_tests += ARRAY_SIZE(test_nr_cpus_large) * ARRAY_SIZE(test_batch_sizes);
+ printf("1..%u\n", nr_tests);
+
+ failed += run_check_config();
+ for (i = 0; i < ARRAY_SIZE(test_nr_cpus); i++)
+ for (j = 0; j < ARRAY_SIZE(test_batch_sizes); j++)
+ failed += run_case(test_nr_cpus[i], test_batch_sizes[j]);
+ if (large) {
+ for (i = 0; i < ARRAY_SIZE(test_nr_cpus_large); i++)
+ for (j = 0; j < ARRAY_SIZE(test_batch_sizes); j++)
+ failed += run_case(test_nr_cpus_large[i], test_batch_sizes[j]);
+ }
+ printf("# %d/%u test cases failed\n", failed, nr_tests);
+ return failed ? 1 : 0;
+}
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 05/10] mm: report the approximate RSS in the rss_stat tracepoint
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (3 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 04/10] tools/testing/hpcc: add userspace test of hierarchical per-CPU counters Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 06/10] lib: percpu_counter_tree: add lazy tree activation Mathieu Desnoyers
` (4 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
The rss_stat tracepoint is emitted on every RSS update, including each
page fault. When it is enabled, it reports the precise sum of the RSS
counter, which iterates over all possible CPUs for each event: 384 per
page fault on a machine with 384 logical CPUs.
Report the approximate sum of the hierarchical per-cpu counter instead,
through get_mm_counter(), which reads the root of the counter tree. The
size field of the event, the RSS counter after the update, is therefore
within the accuracy bound of the counter from the precise value: within
158.5MB on a machine with 384 logical CPUs and 4kB pages.
The tracepoint reports the precise sum since commit f1a7941243c1 ("mm:
convert mm's rss stats into percpu_counter"). Before that, it reported
an atomic counter which only received the per-task cached updates in
batches.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Christoph Lameter <cl@gentwo.org>
Cc: Martin Liu <liumartin@google.com>
Cc: David Rientjes <rientjes@google.com>
Cc: christian.koenig@amd.com
Cc: Shakeel Butt <shakeel.butt@linux.dev>
Cc: SeongJae Park <sj@kernel.org>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Sweet Tea Dorminy <sweettea-kernel@dorminy.me>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: Christian Brauner <brauner@kernel.org>
Cc: Wei Yang <richard.weiyang@gmail.com>
Cc: David Hildenbrand <david@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Yu Zhao <yuzhao@google.com>
Cc: Roman Gushchin <roman.gushchin@linux.dev>
Cc: Mateusz Guzik <mjguzik@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Aboorva Devarajan <aboorvad@linux.ibm.com>
Cc: David Carlier <devnexen@gmail.com>
Cc: Josh Law <objecting@objecting.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: linux-mm@kvack.org
---
Changes since v22:
- Split from "mm: improve RSS counter approximation accuracy for proc
interfaces", which now keeps reporting the precise sum.
---
include/trace/events/kmem.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/include/trace/events/kmem.h b/include/trace/events/kmem.h
index ac4c96db7638..8ee6d5df5961 100644
--- a/include/trace/events/kmem.h
+++ b/include/trace/events/kmem.h
@@ -448,7 +448,7 @@ TRACE_EVENT(rss_stat,
*/
__entry->curr = current->mm == mm && !(current->flags & PF_KTHREAD);
__entry->member = member;
- __entry->size = get_mm_counter_sum(mm, member) << PAGE_SHIFT;
+ __entry->size = get_mm_counter(mm, member) << PAGE_SHIFT;
),
TP_printk("mm_id=%u curr=%d type=%s size=%ldB",
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 06/10] lib: percpu_counter_tree: add lazy tree activation
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (4 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 05/10] mm: report the approximate RSS in the rss_stat tracepoint Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 07/10] mm: keep the RSS counters of single-threaded processes exact Mathieu Desnoyers
` (3 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Add counters which start without their tree, for counters which may
never need its scalability, such as the RSS counters of a
single-threaded process.
percpu_counter_tree_init_many_lazy() initializes counters without
allocating their per-cpu counters and tree items. Until
percpu_counter_tree_activate_many() allocates and publishes them, the
counters are exact:
- percpu_counter_tree_add_owner() adds to the bias of the counter,
without atomic instruction. Its calls for a given counter must not
run concurrently with each other: they come from a single context,
the owner chosen by the user of the counters, such as a task.
- percpu_counter_tree_add() adds atomically to a new atomic bias of the
counter, for any other updater.
The precise and approximate sums read both biases, in O(1). The
activation does not move these values: the sums keep reading them along
with the tree, so updates racing with the activation are not lost,
whichever side of it they land on. The bias only has the owner as
writer, and the atomic bias only receives atomic additions, before and
after the activation. After the activation, both update functions add
to the tree, and percpu_counter_tree_active() reports it, so a user can
skip selecting between them. The accuracy range of a lazily initialized
counter is the range of its tree, even before activation, which keeps
the comparison functions correct across an activation.
The activations of the same counters must be serialized by the caller,
for instance with a mutex: a concurrent activation would publish a
second tree. The activation publishes the root, then the per-cpu
counters, of each counter in order, with release ordering. Once the
last counter is active, the activation is complete, so a caller which
sees it active can skip the activation and its serialization; it may not
observe the other counters active yet, which only delays their updates
going to the tree. The update functions only reach the per-cpu counters
through their published pointer, which orders their initialization
before their use by address dependency, as for rcu_dereference(),
without an acquire on the fast path. The approximate sum reaches the
root the same way. The carry path reads the root pointer after the
per-cpu counters pointer with a read barrier between them, and the
precise sum reads the per-cpu counters pointer with an acquire.
struct percpu_counter_tree grows from 32 to 40 bytes with the atomic
bias, the size of struct percpu_counter.
Test the lazy counters:
- KUnit: exact sums before activation with owner and atomic updates,
set(), idempotent activation, destruction without activation, and an
activation racing with an owner and remote updaters on other CPUs,
which also activate the tree when released, serialized by a mutex,
checking that the counter is exact while they pause, that the tree is
active once an activation returns, and that no update is lost across
the activations.
- Userspace test: random owner and atomic updates from random CPUs,
exact before the tree is activated halfway, with the accuracy and
comparison checks after each update. The test checks that the
activation allocates one tree, that activating again allocates
nothing, and that destroying the counter frees the tree. The shim
provides the ordering primitives as plain accesses.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
.../core-api/percpu-counter-tree.rst | 28 ++
include/linux/percpu_counter_tree.h | 81 ++++-
lib/percpu_counter_tree.c | 315 ++++++++++++++++--
lib/tests/percpu_counter_tree_kunit.c | 218 ++++++++++++
tools/testing/hpcc/include/hpcc_shim.h | 28 +-
tools/testing/hpcc/main.c | 47 +++
6 files changed, 674 insertions(+), 43 deletions(-)
diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation/core-api/percpu-counter-tree.rst
index 6b381deacd83..138e9b74b0c8 100644
--- a/Documentation/core-api/percpu-counter-tree.rst
+++ b/Documentation/core-api/percpu-counter-tree.rst
@@ -74,6 +74,34 @@ takes no lock: an update which carries from the per-cpu counter to the
upper levels can be counted in part, the residual it left below read and
its carry missed on the way up.
+Lazy Tree Activation
+====================
+
+Counters initialized with percpu_counter_tree_init_many_lazy() start
+without their per-cpu counters and tree items, for counters which may
+never need the scalability of the tree. Until
+percpu_counter_tree_activate_many() allocates and publishes the tree,
+the counters are exact:
+
+ * percpu_counter_tree_add_owner() adds to the bias of the counter,
+ written only by its owner, a single context chosen by the user of the
+ counters, such as a task, without atomic instruction.
+
+ * percpu_counter_tree_add() adds to the atomic bias of the counter, for
+ any other updater.
+
+The precise and approximate sums read both, in O(1), and count each
+update whole. The activation does not move these values: the sums keep
+reading them along with the tree, so updates racing with the activation
+are not lost, whichever side of it they land on. The bias only has the
+owner as writer, and the atomic bias only receives atomic additions,
+before and after the activation. After activation, both update functions
+add to the tree, and the approximation has the accuracy of the tree.
+
+The activations of the same counters must be serialized by the caller:
+a concurrent activation would publish a second tree and lose the
+updates made to the first.
+
Use Cases
=========
diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_counter_tree.h
index 741a6877aa99..60ef1da22bd3 100644
--- a/include/linux/percpu_counter_tree.h
+++ b/include/linux/percpu_counter_tree.h
@@ -32,10 +32,22 @@ struct percpu_counter_tree {
unsigned int items_stride; /* Distance between this counter's consecutive items. */
/*
* Approximate sum: this counter's item of the root, in the tree
- * items allocated with the per-CPU counters.
+ * items allocated with the per-CPU counters. NULL until the tree of a
+ * counter initialized by percpu_counter_tree_init_many_lazy() is
+ * activated.
*/
atomic_long_t *approx_sum;
- long bias; /* Bias to apply to counter precise and approximate values. */
+ /*
+ * Bias to apply to counter precise and approximate values. Before the
+ * tree is activated, it also accumulates the updates of
+ * percpu_counter_tree_add_owner(), written only by the owner.
+ */
+ long bias;
+ /*
+ * Updates of percpu_counter_tree_add() made before the tree is
+ * activated, also applied to the precise and approximate values.
+ */
+ atomic_long_t atomic_bias;
};
int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
@@ -43,10 +55,15 @@ int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
gfp_t gfp_flags);
int percpu_counter_tree_init(struct percpu_counter_tree *counter,
unsigned long batch_size, gfp_t gfp_flags);
+int percpu_counter_tree_init_many_lazy(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size);
+int percpu_counter_tree_activate_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, gfp_t gfp_flags);
void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
unsigned int nr_counters);
void percpu_counter_tree_destroy(struct percpu_counter_tree *counter);
void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc);
+void percpu_counter_tree_add_owner(struct percpu_counter_tree *counter, long inc);
long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter);
int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,
struct percpu_counter_tree *b);
@@ -57,6 +74,26 @@ int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *counte
void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v);
int percpu_counter_tree_subsystem_init(void);
+/**
+ * percpu_counter_tree_active() - Query whether the tree of a counter is active.
+ * @counter: The counter to query.
+ *
+ * A counter initialized by percpu_counter_tree_init_many() is active. A
+ * counter initialized by percpu_counter_tree_init_many_lazy() becomes
+ * active when percpu_counter_tree_activate_many() publishes its tree, and
+ * stays active. Once active, percpu_counter_tree_add() and
+ * percpu_counter_tree_add_owner() both add to the tree, so a user can skip
+ * selecting between them.
+ *
+ * Return: true if the updates of @counter go to its tree.
+ */
+static inline
+bool percpu_counter_tree_active(struct percpu_counter_tree *counter)
+{
+ /* No ordering: the update functions and the sums read level0 again. */
+ return !!READ_ONCE(counter->level0);
+}
+
/**
* percpu_counter_tree_approximate_sum() - Return approximate counter sum.
* @counter: The counter to sum.
@@ -70,9 +107,19 @@ int percpu_counter_tree_subsystem_init(void);
static inline
long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *counter)
{
- unsigned long v = atomic_long_read(counter->approx_sum);
+ /*
+ * Pairs with the release of approx_sum in
+ * percpu_counter_tree_activate_many(): the root is zeroed before its
+ * pointer, and the address dependency orders the read of the root
+ * after it, as for rcu_dereference().
+ */
+ atomic_long_t *approx_sum = READ_ONCE(counter->approx_sum);
+ unsigned long v = (unsigned long)READ_ONCE(counter->bias) +
+ (unsigned long)atomic_long_read(&counter->atomic_bias);
- return (long)(v + (unsigned long)READ_ONCE(counter->bias));
+ if (approx_sum)
+ v += (unsigned long)atomic_long_read(approx_sum);
+ return (long)v;
}
unsigned long percpu_counter_tree_approximate_accuracy(struct percpu_counter_tree *counter);
@@ -115,6 +162,26 @@ int percpu_counter_tree_init(struct percpu_counter_tree *counter,
return percpu_counter_tree_init_many(counter, 1, batch_size, gfp_flags);
}
+static inline
+int percpu_counter_tree_init_many_lazy(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size)
+{
+ return percpu_counter_tree_init_many(counters, nr_counters, batch_size, 0);
+}
+
+static inline
+int percpu_counter_tree_activate_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, gfp_t gfp_flags)
+{
+ return 0;
+}
+
+static inline
+bool percpu_counter_tree_active(struct percpu_counter_tree *counter)
+{
+ return true;
+}
+
static inline
void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
unsigned int nr_counters)
@@ -192,6 +259,12 @@ void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
atomic_long_add(inc, &counter->count);
}
+static inline
+void percpu_counter_tree_add_owner(struct percpu_counter_tree *counter, long inc)
+{
+ percpu_counter_tree_add(counter, inc);
+}
+
static inline
long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *counter)
{
diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c
index 67cdb22c3786..32c4f05d7d7d 100644
--- a/lib/percpu_counter_tree.c
+++ b/lib/percpu_counter_tree.c
@@ -328,10 +328,12 @@ int __percpu_counter_tree_init(struct percpu_counter_tree *counter,
return -EINVAL;
counter->batch_order = ilog2(batch_size);
counter->bias = 0;
+ atomic_long_set(&counter->atomic_bias, 0);
counter->level0 = level0;
counter->items_stride = items_stride;
- /* The root is the last item. */
- counter->approx_sum = &items[(tree_topology.nr_items - 1) * items_stride];
+ /* The root is the last item, allocated by the activation if lazy. */
+ counter->approx_sum = items ?
+ &items[(tree_topology.nr_items - 1) * items_stride] : NULL;
return 0;
}
@@ -364,6 +366,26 @@ unsigned long percpu_counter_tree_accuracy(struct percpu_counter_tree *counter)
return batch_size * tree_topology.accuracy_multiplier - nr_cpu_ids;
}
+/* Initialize @nr_counters counters, with their per-CPU counters and tree items, or NULL if lazy. */
+static
+int __percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size,
+ s8 __percpu *level0, atomic_long_t *items)
+{
+ unsigned int items_stride = percpu_counter_tree_items_stride(nr_counters);
+ unsigned int i;
+ int ret;
+
+ for (i = 0; i < nr_counters; i++) {
+ ret = __percpu_counter_tree_init(&counters[i], batch_size,
+ level0 ? level0 + i : NULL,
+ items ? items + i : NULL, items_stride);
+ if (ret)
+ return ret;
+ }
+ return 0;
+}
+
/**
* percpu_counter_tree_init_many() - Initialize many per-CPU counter trees.
* @counters: An array of @nr_counters counters to initialize.
@@ -392,10 +414,8 @@ int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
unsigned int nr_counters, unsigned long batch_size,
gfp_t gfp_flags)
{
- unsigned int items_stride = percpu_counter_tree_items_stride(nr_counters);
s8 __percpu *level0;
atomic_long_t *items;
- unsigned int i;
int ret;
/* The tree shape is selected by percpu_counter_tree_subsystem_init() at boot. */
@@ -410,15 +430,9 @@ int percpu_counter_tree_init_many(struct percpu_counter_tree *counters,
ret = -ENOMEM;
goto free_level0;
}
- for (i = 0; i < nr_counters; i++) {
- ret = __percpu_counter_tree_init(&counters[i], batch_size, level0 + i,
- items + i, items_stride);
- if (ret)
- goto free_items;
- }
- return 0;
-
-free_items:
+ ret = __percpu_counter_tree_init_many(counters, nr_counters, batch_size, level0, items);
+ if (!ret)
+ return 0;
percpu_counter_tree_free_items(items, nr_counters);
free_level0:
free_percpu(level0);
@@ -450,6 +464,163 @@ int percpu_counter_tree_init(struct percpu_counter_tree *counter,
}
EXPORT_SYMBOL_GPL(percpu_counter_tree_init);
+/**
+ * percpu_counter_tree_init_many_lazy() - Initialize many counters, without their tree.
+ * @counters: An array of @nr_counters counters to initialize.
+ * Their memory is provided by the caller.
+ * @nr_counters: The number of counter trees to initialize
+ * @batch_size: The batch size, as for percpu_counter_tree_init_many().
+ *
+ * Initialize counters without allocating their per-CPU counters and tree
+ * items, for counters which may never need the scalability of the tree,
+ * such as the RSS counters of a single-threaded process. Until
+ * percpu_counter_tree_activate_many() allocates the tree, the counters
+ * are exact: percpu_counter_tree_add_owner() adds to the bias, written
+ * only by the owner, percpu_counter_tree_add() adds to the atomic bias,
+ * and the precise and approximate sums read both in O(1).
+ * percpu_counter_tree_destroy_many() and percpu_counter_tree_set() work on
+ * counters which were never activated. The accuracy range of a lazily
+ * initialized counter is the range of its tree, even before activation,
+ * which keeps the comparison functions correct across an activation.
+ * The batch size is fixed here: the activation only publishes the per-CPU
+ * counters and the tree, so updaters read the batch size without ordering.
+ *
+ * Return:
+ * * %0: Success
+ * * %-EINVAL: - Invalid @batch_size argument
+ */
+int percpu_counter_tree_init_many_lazy(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, unsigned long batch_size)
+{
+ /* The tree shape is selected by percpu_counter_tree_subsystem_init() at boot. */
+ if (WARN_ON_ONCE(tree_topology.nr_items == UINT_MAX))
+ return -EINVAL;
+ return __percpu_counter_tree_init_many(counters, nr_counters, batch_size, NULL, NULL);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_init_many_lazy);
+
+/*
+ * Publication of the tree
+ *
+ * The updaters and the readers of a counter take no lock, and may run
+ * while percpu_counter_tree_activate_many() publishes its tree. The
+ * activation allocates the per-CPU counters and the tree items zeroed,
+ * then publishes two pointers per counter, each with a store-release:
+ *
+ * - the release of approx_sum: the root is zeroed before its pointer,
+ * - the release of level0, after it: the per-CPU counters, the tree items
+ * and approx_sum are set before level0.
+ *
+ * level0 opens the tree to updates: until it is published, the tree is
+ * empty. Each load of a published pointer pairs with one of the releases:
+ *
+ * - Update fast path, percpu_counter_tree_add() and
+ * percpu_counter_tree_add_owner(): READ_ONCE(level0), then the per-CPU
+ * counters through it. The address dependency pairs with the release of
+ * level0, as for rcu_dereference().
+ * - Carry slow path: smp_rmb() after the read of level0, then
+ * READ_ONCE(approx_sum). Pairs with the release of level0, which
+ * follows the store of approx_sum.
+ * - Precise sum: smp_load_acquire(level0), then approx_sum, the tree items
+ * and the per-CPU counters. Pairs with the release of level0.
+ * - Approximate sum: READ_ONCE(approx_sum), then the root through it. The
+ * address dependency pairs with the release of approx_sum.
+ * - percpu_counter_tree_active(): READ_ONCE(level0), without ordering. It
+ * only selects the update function, which reads level0 again, or lets
+ * the caller skip an activation which is complete.
+ * - Activations: serialized by the caller, for instance with a mutex,
+ * which orders a complete activation before the check of level0 at the
+ * start of the next one.
+ *
+ * The update fast path has no acquire. smp_load_acquire() is free on
+ * strongly ordered architectures such as x86, but on weakly ordered ones,
+ * such as arm64, powerpc and RISC-V, it costs an ordering load or a barrier
+ * on every update, to order a publication which happens at most once in
+ * the life of a counter. The address dependency orders the per-CPU
+ * counters, reached through level0, at no cost. It does not order
+ * approx_sum, a separate field: the carry slow path, taken only when an
+ * update carries, pays an smp_rmb() to read it, and the precise sum, which
+ * reads the whole tree, reads level0 with an acquire.
+ *
+ * Missing the publication is harmless. An updater which reads level0 as
+ * NULL adds to the bias (owner) or to the atomic bias (others), and a
+ * reader which reads a NULL pointer sums the bias and the atomic bias:
+ * the sums keep reading both after the activation, and the tree receives
+ * no update before level0 is published.
+ *
+ * The read barriers between the levels of the precise sum are unrelated
+ * to the publication: they order carries, see
+ * percpu_counter_tree_precise_sum_unbiased().
+ */
+
+/**
+ * percpu_counter_tree_activate_many() - Activate the tree of lazily initialized counters.
+ * @counters: The array of @nr_counters counters passed to
+ * percpu_counter_tree_init_many_lazy().
+ * @nr_counters: The number of counters.
+ * @gfp_flags: gfp flags to pass to the per-CPU and tree item allocators.
+ *
+ * Allocate the per-CPU counters and the tree items, and publish them:
+ * later updates go to the tree, and the approximation then has the
+ * accuracy of the tree. The updates made before activation stay in the
+ * bias and the atomic bias, which the sums keep reading, so updates racing
+ * with the activation are not lost: the bias only has the owner as writer,
+ * and the atomic bias only receives atomic additions. Activating active
+ * counters does nothing. @counters and @nr_counters must be those passed
+ * to percpu_counter_tree_init_many_lazy().
+ *
+ * The activations of the same counters must be serialized by the caller,
+ * for instance with a mutex: a concurrent activation would publish a second
+ * tree and lose the updates made to the first. The counters are published
+ * in order: once percpu_counter_tree_active() reports the last one active,
+ * the activation is complete, and a caller can skip it and its
+ * serialization. The caller may not observe the other counters active yet,
+ * which only delays their updates going to the tree.
+ *
+ * Return:
+ * * %0: Success
+ * * %-EINVAL: - @nr_counters differs from percpu_counter_tree_init_many_lazy()
+ * * %-ENOMEM: - Out of memory
+ */
+int percpu_counter_tree_activate_many(struct percpu_counter_tree *counters,
+ unsigned int nr_counters, gfp_t gfp_flags)
+{
+ s8 __percpu *level0;
+ atomic_long_t *items, *root;
+ unsigned int i;
+
+ /* Serialized by the caller: a previous activation is complete. */
+ if (counters[0].level0)
+ return 0;
+ /* The tree items are sized for @nr_counters, at the stride set by the initialization. */
+ if (WARN_ON_ONCE(counters[0].items_stride !=
+ percpu_counter_tree_items_stride(nr_counters)))
+ return -EINVAL;
+ level0 = __alloc_percpu_gfp(nr_counters * sizeof(*level0),
+ __alignof__(*counters->level0), gfp_flags);
+ if (!level0)
+ return -ENOMEM;
+ items = percpu_counter_tree_alloc_items(nr_counters, gfp_flags);
+ if (!items) {
+ free_percpu(level0);
+ return -ENOMEM;
+ }
+ root = &items[(tree_topology.nr_items - 1) * counters[0].items_stride];
+ /* See "Publication of the tree" above. */
+ for (i = 0; i < nr_counters; i++) {
+ /* Release of approx_sum: the root is zeroed before its pointer. */
+ smp_store_release(&counters[i].approx_sum, root + i);
+ /*
+ * Release of level0: the per-CPU counters, the tree items and
+ * approx_sum are set before level0, which opens the tree to
+ * updates.
+ */
+ smp_store_release(&counters[i].level0, level0 + i);
+ }
+ return 0;
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_activate_many);
+
/**
* percpu_counter_tree_destroy_many() - Destroy many per-CPU counter trees.
* @counters: Array of counters trees to destroy.
@@ -457,7 +628,7 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_init);
*
* Release internal resources allocated for @nr_counters per-CPU counter trees.
* @counters and @nr_counters must be those passed to
- * percpu_counter_tree_init_many().
+ * percpu_counter_tree_init_many() or percpu_counter_tree_init_many_lazy().
*/
void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
unsigned int nr_counters)
@@ -470,8 +641,9 @@ void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters,
if (WARN_ON_ONCE(counters->items_stride !=
percpu_counter_tree_items_stride(nr_counters)))
return;
- /* The first item of the first counter is the base of the tree items. */
- percpu_counter_tree_free_items(percpu_counter_tree_items(counters), nr_counters);
+ /* The first item of the first counter is the base of the tree items, if allocated. */
+ if (counters->approx_sum)
+ percpu_counter_tree_free_items(percpu_counter_tree_items(counters), nr_counters);
}
EXPORT_SYMBOL_GPL(percpu_counter_tree_destroy_many);
@@ -511,9 +683,19 @@ void percpu_counter_tree_add_slowpath(struct percpu_counter_tree *counter, long
level, n_arity_order;
unsigned long bit_mask;
unsigned int stride = counter->items_stride;
- atomic_long_t *item = percpu_counter_tree_items(counter);
unsigned int cpu = raw_smp_processor_id();
+ atomic_long_t *root, *item;
+ /*
+ * Pairs with the release of level0 in
+ * percpu_counter_tree_activate_many(), which follows the store of
+ * approx_sum. The caller read level0, but approx_sum is a separate
+ * field, which the address dependency of that read does not order:
+ * read it after level0.
+ */
+ smp_rmb();
+ root = READ_ONCE(counter->approx_sum);
+ item = root - (tree_topology.nr_items - 1) * stride;
n_arity_order = tree_topology.config->n_arity_order[0];
bit_mask = percpu_counter_tree_batch_size(counter) << n_arity_order;
level_items = 1U << (tree_topology.nr_cpus_order - n_arity_order);
@@ -571,19 +753,14 @@ void percpu_counter_tree_add_slowpath(struct percpu_counter_tree *counter, long
level_items >>= n_arity_order;
bit_mask <<= n_arity_order;
}
- atomic_long_add_return_release(inc, counter->approx_sum);
+ /* The atomic API has no add with release ordering without a return value. */
+ atomic_long_add_return_release(inc, root);
}
-/**
- * percpu_counter_tree_add() - Add to a per-CPU counter tree.
- * @counter: Counter added to.
- * @inc: Increment value (either positive or negative).
- *
- * Add @inc to a per-CPU counter tree. This is a fast-path which will
- * typically increment per-CPU counters as long as there is no carry
- * greater or equal to the counter tree batch size.
- */
-void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
+/* Add @inc to the per-CPU counters @level0 of an activated tree. */
+static inline
+void percpu_counter_tree_add_tree(struct percpu_counter_tree *counter,
+ s8 __percpu *level0, long inc)
{
unsigned long bit_mask = percpu_counter_tree_batch_size(counter);
s8 old, new;
@@ -605,18 +782,69 @@ void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
* interrupts, and the carry may propagate from any CPU, see
* percpu_counter_tree_add_slowpath().
*/
- old = this_cpu_read(*counter->level0);
+ old = this_cpu_read(*level0);
do {
v = old + inc;
carry = percpu_counter_tree_item_carry(v, bit_mask);
new = (s8)(v - carry);
- } while (!this_cpu_try_cmpxchg(*counter->level0, &old, new));
+ } while (!this_cpu_try_cmpxchg(*level0, &old, new));
if (likely(!carry))
return;
percpu_counter_tree_add_slowpath(counter, carry);
}
+
+/**
+ * percpu_counter_tree_add() - Add to a per-CPU counter tree.
+ * @counter: Counter added to.
+ * @inc: Increment value (either positive or negative).
+ *
+ * Add @inc to a per-CPU counter tree. This is a fast-path which will
+ * typically increment per-CPU counters as long as there is no carry
+ * greater or equal to the counter tree batch size. Before the tree is
+ * activated, add to the atomic bias.
+ */
+void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
+{
+ /*
+ * Pairs with the release of level0 in
+ * percpu_counter_tree_activate_many(): the per-CPU counters are only
+ * reached through this pointer, and the address dependency orders
+ * their initialization before their use, as for rcu_dereference().
+ * No acquire, see "Publication of the tree".
+ */
+ s8 __percpu *level0 = READ_ONCE(counter->level0);
+
+ if (!level0) {
+ atomic_long_add(inc, &counter->atomic_bias);
+ return;
+ }
+ percpu_counter_tree_add_tree(counter, level0, inc);
+}
EXPORT_SYMBOL_GPL(percpu_counter_tree_add);
+/**
+ * percpu_counter_tree_add_owner() - Add to a per-CPU counter tree as its owner.
+ * @counter: Counter added to.
+ * @inc: Increment value (either positive or negative).
+ *
+ * Like percpu_counter_tree_add(), but before the tree is activated, add
+ * to the bias without atomic instruction. The calls for a given counter
+ * must not run concurrently with each other: they come from a single
+ * context, the owner chosen by the user of the counter, such as a task.
+ */
+void percpu_counter_tree_add_owner(struct percpu_counter_tree *counter, long inc)
+{
+ /* Address dependency, as in percpu_counter_tree_add(). */
+ s8 __percpu *level0 = READ_ONCE(counter->level0);
+
+ if (!level0) {
+ WRITE_ONCE(counter->bias, (long)((unsigned long)READ_ONCE(counter->bias) + inc));
+ return;
+ }
+ percpu_counter_tree_add_tree(counter, level0, inc);
+}
+EXPORT_SYMBOL_GPL(percpu_counter_tree_add_owner);
+
/*
* The precise sum is the sum of the residuals of all tree levels. A carry
* leaves a level before reaching a higher level, and the release ordering
@@ -630,19 +858,29 @@ long percpu_counter_tree_precise_sum_unbiased(struct percpu_counter_tree *counte
{
unsigned int nr_levels = tree_topology.config->nr_levels, i,
level_items[MAX_NR_LEVELS], stride = counter->items_stride;
+ /*
+ * Pairs with the release of level0 in
+ * percpu_counter_tree_activate_many(): approx_sum, the tree items and
+ * the per-CPU counters read below are set before level0.
+ */
+ s8 __percpu *level0 = smp_load_acquire(&counter->level0);
+ unsigned long sum = atomic_long_read(&counter->atomic_bias);
atomic_long_t *item;
- unsigned long sum;
int level, cpu;
+ /* Before activation, the atomic bias holds the whole unbiased sum. */
+ if (!level0)
+ return (long)sum;
/* Number of items of each level above level 0. */
level_items[0] = 1U << tree_topology.nr_cpus_order;
for (level = 1; level < (int)nr_levels; level++)
level_items[level] = level_items[level - 1] >>
tree_topology.config->n_arity_order[level - 1];
- sum = atomic_long_read(counter->approx_sum);
+ /* Published before level0, so ordered by its acquire. */
+ item = READ_ONCE(counter->approx_sum);
+ sum += atomic_long_read(item);
smp_rmb(); /* Read each level before the level below it. */
/* The items of each level precede those of the level above it. */
- item = counter->approx_sum;
for (level = (int)nr_levels - 1; level >= 1; level--) {
item -= level_items[level] * stride;
for (i = 0; i < level_items[level]; i++)
@@ -650,7 +888,7 @@ long percpu_counter_tree_precise_sum_unbiased(struct percpu_counter_tree *counte
smp_rmb(); /* Read this level before the level below it. */
}
for_each_possible_cpu(cpu)
- sum += (long)READ_ONCE(*per_cpu_ptr(counter->level0, cpu));
+ sum += (long)READ_ONCE(*per_cpu_ptr(level0, cpu));
return (long)sum;
}
@@ -1013,6 +1251,7 @@ EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_check_config);
* - a counter at level N, above level 0, holds a multiple of
* BATCH(level N - 1) within (-BATCH(level N), +BATCH(level N)),
* - the root holds a multiple of the batch of the last level.
+ * Before activation, a lazily initialized counter has no tree to check.
*
* Return: The number of violated invariants.
*/
@@ -1020,11 +1259,14 @@ unsigned int percpu_counter_tree_check_residuals(struct percpu_counter_tree *cou
{
unsigned int nr_levels = tree_topology.config->nr_levels, level, level_items,
nr_errors = 0, stride = counter->items_stride;
- atomic_long_t *item = percpu_counter_tree_items(counter);
unsigned long lo = percpu_counter_tree_batch_size(counter);
+ atomic_long_t *item;
long root;
int cpu;
+ if (!counter->level0)
+ return 0;
+ item = percpu_counter_tree_items(counter);
for_each_possible_cpu(cpu) {
long v = READ_ONCE(*per_cpu_ptr(counter->level0, cpu));
@@ -1063,7 +1305,7 @@ EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_check_residuals);
/*
* Copy the state of counter @src into counter @dst, initialized with the
* same batch size and without concurrent updates: their per-CPU counters,
- * tree items and bias.
+ * tree items and biases. Both trees are active.
*/
void percpu_counter_tree_copy_state(struct percpu_counter_tree *dst,
struct percpu_counter_tree *src)
@@ -1079,6 +1321,7 @@ void percpu_counter_tree_copy_state(struct percpu_counter_tree *dst,
atomic_long_set(&dst_items[pos * dst->items_stride],
atomic_long_read(&src_items[pos * src->items_stride]));
dst->bias = src->bias;
+ atomic_long_set(&dst->atomic_bias, atomic_long_read(&src->atomic_bias));
}
EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_copy_state);
#endif
diff --git a/lib/tests/percpu_counter_tree_kunit.c b/lib/tests/percpu_counter_tree_kunit.c
index 58b2e488e3c6..2f5852b1f521 100644
--- a/lib/tests/percpu_counter_tree_kunit.c
+++ b/lib/tests/percpu_counter_tree_kunit.c
@@ -2,6 +2,8 @@
// SPDX-FileCopyrightText: 2026 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
#include <kunit/test.h>
+#include <linux/delay.h>
+#include <linux/mutex.h>
#include <linux/percpu_counter_tree.h>
#include <linux/kthread.h>
#include <linux/wait.h>
@@ -783,6 +785,220 @@ static void hpcc_test_saturated_compare(struct kunit *test)
}
}
+/* Check a counter against its expected sum: exact before activation, within range after. */
+static void check_lazy_counter(struct kunit *test, struct percpu_counter_tree *c, long v)
+{
+ long approx_sum = percpu_counter_tree_approximate_sum(c);
+ unsigned long accuracy;
+
+ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(c), v);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare_value(c, v));
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(c, v));
+ check_residuals(test, c);
+#ifdef CONFIG_SMP
+ if (!READ_ONCE(c->level0)) {
+ KUNIT_EXPECT_EQ(test, approx_sum, v);
+ return;
+ }
+#endif
+ accuracy = percpu_counter_tree_approximate_accuracy(c);
+ KUNIT_EXPECT_GE(test, (long)(approx_sum - (v - accuracy)), 0);
+ KUNIT_EXPECT_LE(test, (long)(approx_sum - (v + accuracy)), 0);
+}
+
+/*
+ * Lazily initialized counters: exact sums before the tree is activated,
+ * with owner and atomic updates, set(), idempotent activation, updates
+ * after activation, and destruction of counters never activated.
+ */
+static void hpcc_test_lazy(struct kunit *test)
+{
+ struct percpu_counter_tree pct[2];
+ long expect[2] = { 0, 0 };
+ int i, j;
+
+ KUNIT_ASSERT_EQ(test, 0, percpu_counter_tree_init_many_lazy(pct, 2, 32));
+#ifdef CONFIG_SMP
+ KUNIT_EXPECT_FALSE(test, percpu_counter_tree_active(&pct[0]));
+ KUNIT_EXPECT_FALSE(test, percpu_counter_tree_active(&pct[1]));
+ /* The level 0 counters are __percpu pointers: compare them as booleans. */
+ KUNIT_EXPECT_TRUE(test, !pct[0].level0);
+ KUNIT_EXPECT_TRUE(test, !pct[1].level0);
+ KUNIT_EXPECT_NULL(test, pct[0].approx_sum);
+ KUNIT_EXPECT_NULL(test, pct[1].approx_sum);
+#endif
+ for (j = 0; j < 2; j++) {
+ /* j == 0: before activation; j == 1: after activation. */
+ for (i = 0; i < 10000; i++) {
+ long inc = (long)(get_random_u32() % 1025) - 512;
+
+ if (get_random_u32() & 1)
+ percpu_counter_tree_add_owner(&pct[0], inc);
+ else
+ percpu_counter_tree_add(&pct[0], inc);
+ expect[0] += inc;
+ percpu_counter_tree_add(&pct[1], -inc);
+ expect[1] -= inc;
+ }
+ check_lazy_counter(test, &pct[0], expect[0]);
+ check_lazy_counter(test, &pct[1], expect[1]);
+ percpu_counter_tree_set(&pct[1], 12345);
+ expect[1] = 12345;
+ check_lazy_counter(test, &pct[1], expect[1]);
+ if (j)
+ break;
+ KUNIT_ASSERT_EQ(test, 0, percpu_counter_tree_activate_many(pct, 2, GFP_KERNEL));
+ KUNIT_EXPECT_TRUE(test, percpu_counter_tree_active(&pct[0]));
+ KUNIT_EXPECT_TRUE(test, percpu_counter_tree_active(&pct[1]));
+#ifdef CONFIG_SMP
+ {
+ s8 __percpu *level0 = pct[0].level0;
+
+ KUNIT_EXPECT_TRUE(test, level0);
+ KUNIT_EXPECT_TRUE(test, pct[1].level0 == level0 + 1);
+ KUNIT_EXPECT_NOT_NULL(test, pct[0].approx_sum);
+ KUNIT_EXPECT_PTR_EQ(test, pct[1].approx_sum, pct[0].approx_sum + 1);
+ KUNIT_EXPECT_EQ(test, 0,
+ percpu_counter_tree_activate_many(pct, 2, GFP_KERNEL));
+ KUNIT_EXPECT_TRUE(test, pct[0].level0 == level0);
+ }
+#endif
+ /* The sums carry the updates made before activation. */
+ check_lazy_counter(test, &pct[0], expect[0]);
+ check_lazy_counter(test, &pct[1], expect[1]);
+ }
+ percpu_counter_tree_destroy_many(pct, 2);
+
+ /* Destroy counters which were never activated. */
+ KUNIT_ASSERT_EQ(test, 0, percpu_counter_tree_init_many_lazy(pct, 2, 32));
+ percpu_counter_tree_add_owner(&pct[0], 7);
+ percpu_counter_tree_add(&pct[1], -7);
+ check_lazy_counter(test, &pct[0], 7);
+ check_lazy_counter(test, &pct[1], -7);
+ percpu_counter_tree_destroy_many(pct, 2);
+}
+
+/*
+ * Activation racing with updates: one owner and updaters on other CPUs add
+ * to a lazily initialized counter. Each worker makes a first part of its
+ * updates, reports their sum and waits. The test checks that the counter
+ * is exact, then releases the workers and activates the tree while they
+ * make the rest of their updates. The remote updaters also activate the
+ * tree when released, serialized with the test and with each other by a
+ * mutex, and check that the tree is active once their activation returns.
+ * No update may be lost, whichever side of the activation it lands on.
+ */
+#define LAZY_RACE_NR_INC 200000
+#define LAZY_RACE_NR_FIRST (LAZY_RACE_NR_INC / 8)
+#define LAZY_RACE_MAX_REMOTE 8
+
+struct lazy_race_shared {
+ struct percpu_counter_tree *c;
+ atomic_long_t first_sum; /* Sum of the updates made before the release. */
+ atomic_long_t expect; /* Sum of all updates. */
+ struct mutex activate_lock; /* Serializes the activations. */
+ atomic_t paused; /* Workers waiting for the release. */
+ atomic_t activate_errors; /* Failed activations of the workers. */
+ bool go; /* Releases the workers. */
+};
+
+struct lazy_race_work {
+ struct work_struct work;
+ struct lazy_race_shared *sh;
+ bool owner;
+};
+
+static void lazy_race_fn(struct work_struct *work)
+{
+ struct lazy_race_work *w = container_of(work, struct lazy_race_work, work);
+ struct lazy_race_shared *sh = w->sh;
+ long sum = 0;
+ int i;
+
+ for (i = 0; i < LAZY_RACE_NR_INC; i++) {
+ long inc = (long)(get_random_u32() % 65) - 32;
+
+ if (i == LAZY_RACE_NR_FIRST) {
+ /* Fully ordered: the first updates are visible before the pause. */
+ atomic_long_add_return(sum, &sh->first_sum);
+ atomic_inc_return(&sh->paused);
+ while (!READ_ONCE(sh->go))
+ cond_resched();
+ if (!w->owner) {
+ mutex_lock(&sh->activate_lock);
+ if (percpu_counter_tree_activate_many(sh->c, 1, GFP_KERNEL) ||
+ !percpu_counter_tree_active(sh->c))
+ atomic_inc(&sh->activate_errors);
+ mutex_unlock(&sh->activate_lock);
+ }
+ }
+ if (w->owner)
+ percpu_counter_tree_add_owner(sh->c, inc);
+ else
+ percpu_counter_tree_add(sh->c, inc);
+ sum += inc;
+ if (!(i & 1023))
+ cond_resched();
+ }
+ atomic_long_add(sum, &sh->expect);
+ kfree(w);
+ complete_work();
+}
+
+static void hpcc_test_lazy_activation_race(struct kunit *test)
+{
+ struct percpu_counter_tree pct;
+ int round;
+
+ if (num_online_cpus() < 2)
+ kunit_skip(test, "needs at least 2 online CPUs");
+ for (round = 0; round < 4; round++) {
+ struct lazy_race_shared sh = { .c = &pct };
+ unsigned long timeout = jiffies + 10 * HZ;
+ int cpu, nr_workers = 0;
+
+ KUNIT_ASSERT_EQ(test, 0, percpu_counter_tree_init_many_lazy(&pct, 1, 32));
+ mutex_init(&sh.activate_lock);
+ init_kthreads();
+ cpus_read_lock();
+ for_each_online_cpu(cpu) {
+ struct lazy_race_work *w;
+
+ if (nr_workers > LAZY_RACE_MAX_REMOTE)
+ break;
+ w = kzalloc_obj(*w);
+ KUNIT_EXPECT_NOT_NULL(test, w);
+ if (!w)
+ break;
+ INIT_WORK(&w->work, lazy_race_fn);
+ w->sh = &sh;
+ /* The first worker is the owner, the others update remotely. */
+ w->owner = !nr_workers;
+ atomic_inc(&kernel_threads_to_run);
+ queue_work_on(cpu, hpcc_test_wq, &w->work);
+ nr_workers++;
+ }
+ cpus_read_unlock();
+ while (atomic_read(&sh.paused) < nr_workers && time_before(jiffies, timeout))
+ usleep_range(100, 200);
+ smp_mb(); /* Read the counter after the first updates of the workers. */
+ /* Every worker, the owner included, has updates left for after the activation. */
+ KUNIT_EXPECT_EQ(test, atomic_read(&sh.paused), nr_workers);
+ /* Before activation, the owner and atomic updates are exact. */
+ check_lazy_counter(test, &pct, atomic_long_read(&sh.first_sum));
+ WRITE_ONCE(sh.go, true);
+ mutex_lock(&sh.activate_lock);
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_activate_many(&pct, 1, GFP_KERNEL));
+ KUNIT_EXPECT_TRUE(test, percpu_counter_tree_active(&pct));
+ mutex_unlock(&sh.activate_lock);
+ fini_kthreads();
+ mutex_destroy(&sh.activate_lock);
+ KUNIT_EXPECT_EQ(test, 0, atomic_read(&sh.activate_errors));
+ check_lazy_counter(test, &pct, atomic_long_read(&sh.expect));
+ percpu_counter_tree_destroy_many(&pct, 1);
+ }
+}
+
static void hpcc_test_check_config(struct kunit *test)
{
#ifdef CONFIG_SMP
@@ -804,6 +1020,8 @@ static struct kunit_case hpcc_test_cases[] = {
KUNIT_CASE(hpcc_test_set),
KUNIT_CASE(hpcc_test_saturated_compare),
KUNIT_CASE(hpcc_test_contended_carries),
+ KUNIT_CASE(hpcc_test_lazy),
+ KUNIT_CASE(hpcc_test_lazy_activation_race),
{}
};
diff --git a/tools/testing/hpcc/include/hpcc_shim.h b/tools/testing/hpcc/include/hpcc_shim.h
index 7e268de984c6..d321c8363b0b 100644
--- a/tools/testing/hpcc/include/hpcc_shim.h
+++ b/tools/testing/hpcc/include/hpcc_shim.h
@@ -68,6 +68,9 @@ static inline int get_count_order(unsigned int count)
#define atomic_long_add_return_relaxed(i, v) ((v)->counter += (i))
#define atomic_long_add_return_release(i, v) ((v)->counter += (i))
#define smp_rmb() barrier()
+/* The harness runs on one thread: ordering primitives are plain accesses. */
+#define smp_load_acquire(p) READ_ONCE(*(p))
+#define smp_store_release(p, v) WRITE_ONCE(*(p), (v))
static inline bool atomic_long_try_cmpxchg_relaxed(atomic_long_t *v, long *old, long new)
{
@@ -92,15 +95,32 @@ extern unsigned int hpcc_current_cpu;
*/
#define HPCC_PCPU_UNIT 64
+/* Outstanding allocations, to check for leaks. */
+extern long hpcc_nr_allocs;
+
+static inline void *hpcc_alloc_account(void *p)
+{
+ if (p)
+ hpcc_nr_allocs++;
+ return p;
+}
+
+static inline void hpcc_free_account(void *p)
+{
+ if (p)
+ hpcc_nr_allocs--;
+}
+
static inline void *__alloc_percpu_gfp(size_t size, size_t align, gfp_t gfp)
{
if (size > HPCC_PCPU_UNIT || align > HPCC_PCPU_UNIT)
return NULL;
- return calloc(nr_cpu_ids, HPCC_PCPU_UNIT);
+ return hpcc_alloc_account(calloc(nr_cpu_ids, HPCC_PCPU_UNIT));
}
static inline void free_percpu(void *ptr)
{
+ hpcc_free_account(ptr);
free(ptr);
}
@@ -136,21 +156,23 @@ static inline void *kmem_cache_zalloc(struct kmem_cache *s, gfp_t gfp)
if (p)
memset(p, 0, s->size);
- return p;
+ return hpcc_alloc_account(p);
}
static inline void kmem_cache_free(struct kmem_cache *s, void *p)
{
+ hpcc_free_account(p);
free(p);
}
static inline void *kzalloc(size_t size, gfp_t gfp)
{
- return calloc(1, size);
+ return hpcc_alloc_account(calloc(1, size));
}
static inline void kfree(void *p)
{
+ hpcc_free_account(p);
free(p);
}
diff --git a/tools/testing/hpcc/main.c b/tools/testing/hpcc/main.c
index b707754aab0a..c3583a287cdd 100644
--- a/tools/testing/hpcc/main.c
+++ b/tools/testing/hpcc/main.c
@@ -19,6 +19,10 @@
* and check the accuracy range contract and the comparison functions
* against shadow sums after each increment.
*
+ * - Lazy counter: random owner and atomic updates of a lazily initialized
+ * counter, exact before its tree is activated halfway, with the same
+ * checks after each increment.
+ *
* The test is single-threaded, so it only covers settled counters.
*/
@@ -28,6 +32,7 @@
unsigned int nr_cpu_ids;
unsigned int hpcc_current_cpu;
unsigned long hpcc_nr_warnings;
+long hpcc_nr_allocs;
#include "../../../lib/percpu_counter_tree.c"
@@ -329,6 +334,47 @@ static void test_random_walk(unsigned long batch_size, unsigned long nr_steps)
test_counter_destroy(&c[1]);
}
+static void test_lazy(unsigned long batch_size, unsigned long nr_steps)
+{
+ long nr_allocs = hpcc_nr_allocs;
+ struct test_counter c;
+ unsigned long step;
+
+ if (percpu_counter_tree_init_many_lazy(&c.tree, 1, batch_size)) {
+ CHECK(0);
+ return;
+ }
+ c.shadow = 0;
+ CHECK(!c.tree.level0);
+ CHECK(!c.tree.approx_sum);
+ CHECK(!percpu_counter_tree_active(&c.tree));
+ for (step = 0; step < nr_steps; step++) {
+ long inc = random_increment(batch_size);
+
+ hpcc_current_cpu = rnd() % nr_cpu_ids;
+ if (rnd() & 1)
+ percpu_counter_tree_add_owner(&c.tree, inc);
+ else
+ percpu_counter_tree_add(&c.tree, inc);
+ c.shadow += inc;
+ if (!c.tree.level0)
+ CHECK(percpu_counter_tree_approximate_sum(&c.tree) == c.shadow);
+ check_counter(&c);
+ if (step == nr_steps / 2) {
+ CHECK(!percpu_counter_tree_activate_many(&c.tree, 1, GFP_KERNEL));
+ CHECK(c.tree.level0);
+ CHECK(c.tree.approx_sum);
+ CHECK(percpu_counter_tree_active(&c.tree));
+ /* One tree: its per-CPU counters and its tree items. */
+ CHECK(hpcc_nr_allocs == nr_allocs + 2);
+ CHECK(!percpu_counter_tree_activate_many(&c.tree, 1, GFP_KERNEL));
+ CHECK(hpcc_nr_allocs == nr_allocs + 2);
+ }
+ }
+ test_counter_destroy(&c);
+ CHECK(hpcc_nr_allocs == nr_allocs);
+}
+
static const unsigned int test_nr_cpus[] = {
1, 2, 3, 4, 5, 8, 9, 16, 17, 32, 33, 64, 65, 100, 128, 256, 512,
1000, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
@@ -359,6 +405,7 @@ static int run_case(unsigned int nr_cpus, unsigned long batch_size)
test_saturated(batch_size, 1);
test_saturated(batch_size, -1);
test_random_walk(batch_size, nr_steps);
+ test_lazy(batch_size, nr_steps / 2);
CHECK(!hpcc_nr_warnings);
printf("%sok %d - nr_cpus=%u batch_size=%lu\n", nr_case_failures ? "not " : "",
++test_num, nr_cpus, batch_size);
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 07/10] mm: keep the RSS counters of single-threaded processes exact
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (5 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 06/10] lib: percpu_counter_tree: add lazy tree activation Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 08/10] lib: percpu_counter_tree: add the arity boot parameter Mathieu Desnoyers
` (2 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Until a second thread shares the mm, initialize the RSS counters lazily,
without their counter tree: the task owning the mm adds to a plain
counter, and other tasks, such as reclaim, khugepaged, the OOM reaper or
remote GUP, add atomically. The RSS counters of single-threaded
processes are therefore exact, their precise sums for /proc/PID/status,
/proc/PID/statm and the OOM killer take O(1), and they use no per-cpu
memory. The readers of the approximation, such as /proc/PID/stat, the
RSS high watermark and the rss_stat tracepoint, get the exact value for
these processes.
The owner, mm->rss_owner, is the task running on the mm: the child in
dup_mm(), or the task in exec_mmap(), which also clears it from the mm
it leaves, as exit_mm() does. It stays NULL, which matches no task, in
the mm of exec() until exec_mmap() and in those of the other users of
mm_alloc(): all their updates are atomic. It is only compared with
current, never dereferenced, so a single task writes the plain counter,
including while a vfork() child shares the mm. mm->owner (CONFIG_MEMCG)
is not used, because mm_update_next_owner() hands it over to another
task while a vfork() child may still update the counters.
copy_mm() activates the counter tree when a thread is created with
CLONE_VM, except for vfork(), whose parent waits while the child shares
the mm. mm->rss_stat_mutex serializes the activations, as
mm->mm_cid.mutex serializes the mode changes of mm_cid at fork and exit,
without relying on which tasks can create threads. Once the tree is
active, thread creation no longer takes the mutex. This moves the
allocation of the per-cpu counters and tree items of the RSS counters
from fork() to the creation of the second thread of a process, which
returns -ENOMEM if it fails, as fork() could before. The tasks the
kernel creates with CLONE_VM for a process, such as the io_uring workers
and the vhost tasks, also share its mm: a single-threaded process using
them gets the counter tree. The updates made before the activation stay
in the single counters, which the sums keep reading, so updates racing
with the activation are not lost. Once the tree is active,
__add_mm_counter() no longer reads rss_owner, so the updates of the
threads of a process do not pull in its cache line, which other
mm_struct fields share.
The tree stays active when the process returns to a single thread:
going back to the single counters would need a grace period for the
remote updaters, and a process alternating between one and two threads
would pay for each switch.
Before the activation, the updates of tasks other than the owner are
atomic additions to one word per counter: concurrent remote updates
of the same single-threaded process from many CPUs, such as direct
reclaim unmapping its pages, contend on it.
* Testing results:
Test hardware: 2 sockets AMD EPYC 9654 96-Core Processor (384 logical
CPUs).
With the test program and the instrumentation described in the patch
switching the RSS counters to hierarchical counters, in a KVM guest with
384 vCPUs, each pinned to its own CPU of the host, with the NUMA topology
of the host, the approximation of the RSS counters of the single-threaded
program is exact, compared to an 841MB delta for the upstream counters.
With an idle second thread, which activates the counter tree, the
hierarchical counters reach a 96MB delta, compared to 845MB for the
upstream counters.
On bare metal, with 1000 to 16000 single-threaded processes alive, a
read of /proc/PID/statm, which computes 3 precise sums, takes 5.3 to
6.5us, compared to 16.5 to 19.0us with the upstream counters, and a read
of /proc/PID/status, which computes 4 precise sums, takes 11.4 to
13.1us, compared to 26.6 to 28.6us. A fork + exit of a child touching
no pages takes 116us, compared to 139us (219us compared to 247us when it
touches 64 pages): its counters are destroyed without 4 precise sums
over 384 logical CPUs in check_mm(), and neither per-cpu memory nor tree
items are allocated or freed.
On bare metal with SMT disabled at runtime, where the upstream batch
size is 384, will-it-scale page_fault2 with one process is 5.1% faster
than with the upstream counters, and page_fault3 1.3% faster (one boot
each, the upstream one on the previous day; the boot-to-boot spread
reaches 3%, so neither is claimed as a gain).
* Memory Use
Per mm, on a 64-bit arch with 64-byte cache lines, including the
rss_owner pointer and the 24-byte activation mutex, for a
single-threaded and a multi-threaded process, compared to the upstream
percpu counters:
Bytes per mm
nr_cpus fan-out 1 thread threads upstream
2 2 192 264 192
16 16 192 320 416
64 16,4 192 768 1184
384 8,8,8 192 6400 6304
1024 8,8,16 192 13568 16544
A single-threaded process uses 192 bytes for its RSS counters whatever
the number of CPUs: the 4 counter structures, rss_owner and the mutex in
mm_struct, compared to the 4 upstream counter structures (160 bytes) and
their per-cpu memory. On x86_64 with 16, 384 and 1024 possible CPUs,
the mm_struct slab object keeps its upstream size (1752, 1872 and 2112
bytes in /proc/slabinfo). A multi-threaded process adds nr_cpus bytes
of per-cpu memory per counter (1536 per mm at 384 logical CPUs),
compared to 4 * nr_cpus bytes per counter (6144 per mm) for the upstream
counters, and the tree items, without the rounding of their slab cache.
fork() no longer allocates memory for the RSS counters.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
.../core-api/percpu-counter-tree.rst | 7 ++++
fs/exec.c | 5 +++
include/linux/mm.h | 24 +++++++++++--
include/linux/mm_types.h | 16 +++++++++
kernel/exit.c | 3 ++
kernel/fork.c | 35 +++++++++++++++++--
6 files changed, 85 insertions(+), 5 deletions(-)
diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation/core-api/percpu-counter-tree.rst
index 138e9b74b0c8..87babe2276c4 100644
--- a/Documentation/core-api/percpu-counter-tree.rst
+++ b/Documentation/core-api/percpu-counter-tree.rst
@@ -102,6 +102,13 @@ The activations of the same counters must be serialized by the caller:
a concurrent activation would publish a second tree and lose the
updates made to the first.
+The RSS counters of an mm use this: the task owning the mm updates the
+plain counter, and other tasks, such as reclaim, update the atomic
+counter. The tree is activated when a second thread shares the mm,
+under mm->rss_stat_mutex, which serializes the activations.
+A single-threaded process therefore has exact RSS counters, cheap
+precise sums, and neither per-cpu memory nor tree items for them.
+
Use Cases
=========
diff --git a/fs/exec.c b/fs/exec.c
index 8d2b14e1d455..7a6f07a6d482 100644
--- a/fs/exec.c
+++ b/fs/exec.c
@@ -875,6 +875,8 @@ static int exec_mmap(struct linux_binprm *bprm)
}
}
+ /* This task owns the RSS counters of the new mm, see __add_mm_counter(). */
+ WRITE_ONCE(mm->rss_owner, tsk);
task_lock(tsk);
membarrier_exec_mmap(mm);
@@ -903,6 +905,9 @@ static int exec_mmap(struct linux_binprm *bprm)
if (old_mm) {
mmap_read_unlock(old_mm);
BUG_ON(active_mm != old_mm);
+ /* Updates of the old mm by this task are now atomic. */
+ if (READ_ONCE(old_mm->rss_owner) == tsk)
+ WRITE_ONCE(old_mm->rss_owner, NULL);
/* Defer teardown to setup_new_exec(), outside the exec locks. */
bprm->old_mm = old_mm;
} else {
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 36242c7ff84f..4d740c0c5f54 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -3617,23 +3617,41 @@ static inline unsigned long get_mm_counter_sum(struct mm_struct *mm, int member)
void mm_trace_rss_stat(struct mm_struct *mm, int member);
+/*
+ * Until a second thread shares the mm, the RSS counters are exact single
+ * counters: the task which owns the mm updates a plain counter, and other
+ * tasks (reclaim, khugepaged, the OOM reaper, remote GUP, ...) an atomic
+ * one. See copy_mm(). Once the tree is active, all updates go to it:
+ * rss_owner is not read, so the updates of the threads of a process do not
+ * touch its cache line.
+ */
+static inline void __add_mm_counter(struct mm_struct *mm, int member, long value)
+{
+ struct percpu_counter_tree *counter = &mm->rss_stat[member];
+
+ if (!percpu_counter_tree_active(counter) && current == READ_ONCE(mm->rss_owner))
+ percpu_counter_tree_add_owner(counter, value);
+ else
+ percpu_counter_tree_add(counter, value);
+}
+
static inline void add_mm_counter(struct mm_struct *mm, int member, long value)
{
- percpu_counter_tree_add(&mm->rss_stat[member], value);
+ __add_mm_counter(mm, member, value);
mm_trace_rss_stat(mm, member);
}
static inline void inc_mm_counter(struct mm_struct *mm, int member)
{
- percpu_counter_tree_add(&mm->rss_stat[member], 1);
+ __add_mm_counter(mm, member, 1);
mm_trace_rss_stat(mm, member);
}
static inline void dec_mm_counter(struct mm_struct *mm, int member)
{
- percpu_counter_tree_add(&mm->rss_stat[member], -1);
+ __add_mm_counter(mm, member, -1);
mm_trace_rss_stat(mm, member);
}
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 20b4517b7329..f0d315d72adb 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -1352,6 +1352,22 @@ struct mm_struct {
#endif
struct percpu_counter_tree rss_stat[NR_MM_COUNTERS];
+ /*
+ * Task updating rss_stat with percpu_counter_tree_add_owner()
+ * until the counter tree is activated by a second thread: the
+ * task running on this mm, set by dup_mm() and exec_mmap(),
+ * cleared when that task exits or execs, NULL for the other
+ * users of mm_alloc(). Only compared with current, never
+ * dereferenced. Not mm->owner, which depends on CONFIG_MEMCG
+ * and which mm_update_next_owner() hands over to another task
+ * while a vfork() child may still update the counters.
+ */
+ struct task_struct *rss_owner;
+ /*
+ * Serializes the activations of the rss_stat counter tree,
+ * until the tree is active. See mm_activate_rss_stat().
+ */
+ struct mutex rss_stat_mutex;
struct linux_binfmt *binfmt;
diff --git a/kernel/exit.c b/kernel/exit.c
index d5e7bc2af804..c153cd064987 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -582,6 +582,9 @@ static void exit_mm(void)
local_irq_enable();
task_unlock(current);
mmap_read_unlock(mm);
+ /* From now on, this task updates the RSS counters of @mm atomically. */
+ if (READ_ONCE(mm->rss_owner) == current)
+ WRITE_ONCE(mm->rss_owner, NULL);
mm_update_next_owner(mm);
mmput(mm);
if (test_thread_flag(TIF_MEMDIE))
diff --git a/kernel/fork.c b/kernel/fork.c
index 02e25115ff85..ac4eb1370e62 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1108,6 +1108,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
memset(&mm->rss_stat, 0, sizeof(mm->rss_stat));
spin_lock_init(&mm->page_table_lock);
spin_lock_init(&mm->arg_lock);
+ mutex_init(&mm->rss_stat_mutex);
mm_init_cpumask(mm);
mm_init_aio(mm);
mm_init_owner(mm, p);
@@ -1148,8 +1149,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
if (mm_alloc_sched(mm))
goto fail_sched;
- if (percpu_counter_tree_init_many(mm->rss_stat, NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE,
- GFP_KERNEL_ACCOUNT))
+ if (percpu_counter_tree_init_many_lazy(mm->rss_stat, NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE))
goto fail_pcpu;
lru_gen_init_mm(mm);
@@ -1542,6 +1542,8 @@ static struct mm_struct *dup_mm(struct task_struct *tsk,
if (!mm_init(mm, tsk))
goto fail_nomem;
+ /* The child owns its RSS counters, see __add_mm_counter(). */
+ mm->rss_owner = tsk;
uprobe_start_dup_mmap();
err = dup_mmap(mm, oldmm);
@@ -1569,6 +1571,23 @@ static struct mm_struct *dup_mm(struct task_struct *tsk,
return NULL;
}
+/*
+ * Serialize the activations of the RSS counter tree, whichever tasks create
+ * threads. Once the last counter is active, the activation is complete and
+ * thread creation skips the mutex. That check needs no acquire: the updates
+ * and the sums of the counters order their own accesses to the tree. Not
+ * observing the other counters active yet only delays their updates going
+ * to the tree.
+ */
+static int mm_activate_rss_stat(struct mm_struct *mm)
+{
+ if (percpu_counter_tree_active(&mm->rss_stat[NR_MM_COUNTERS - 1]))
+ return 0;
+ guard(mutex)(&mm->rss_stat_mutex);
+ return percpu_counter_tree_activate_many(mm->rss_stat, NR_MM_COUNTERS,
+ GFP_KERNEL_ACCOUNT);
+}
+
static int copy_mm(u64 clone_flags, struct task_struct *tsk)
{
struct mm_struct *mm, *oldmm;
@@ -1593,6 +1612,18 @@ static int copy_mm(u64 clone_flags, struct task_struct *tsk)
return 0;
if (clone_flags & CLONE_VM) {
+ int err = 0;
+
+ /*
+ * A second thread shares the mm: activate the RSS counter
+ * tree. A vfork child shares the mm while the parent waits,
+ * so the single counters still fit. The tree stays active if
+ * the clone fails later, which is harmless.
+ */
+ if (!(clone_flags & CLONE_VFORK))
+ err = mm_activate_rss_stat(oldmm);
+ if (err)
+ return err;
mmget(oldmm);
mm = oldmm;
} else {
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 08/10] lib: percpu_counter_tree: add the arity boot parameter
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (6 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 07/10] mm: keep the RSS counters of single-threaded processes exact Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 09/10] mm: add the rss_stat_batch " Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 10/10] lib: add a benchmark of hierarchical per-cpu counters Mathieu Desnoyers
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
The fan-out of each tree level is selected at boot from nr_cpu_ids, the
highest possible CPU number plus one, using a table tuned for the RSS
counters on one machine, a 2-socket AMD EPYC 9654 with 192 cores and 384
logical CPUs. The best shape depends on the cost of cache line
transfers on a given machine, which varies with the number of sockets,
the cache topology and SMT, so it may differ on other hardware.
Add the percpu_counter_tree.arity= boot parameter, which overrides the
tree shape with the fan-out of each level, from the per-cpu counters to
the root, so the shapes can be compared on other machines, to improve
the default table. For example, when nr_cpu_ids is 16, "16" is a flat
tree and "4,4" a tree with 4 intermediate counters. Each fan-out is a
power of 2, and their product must be nr_cpu_ids rounded up to a power
of 2. An invalid shape is ignored with a warning.
The shape in use is printed at boot, and can be read from
/sys/module/percpu_counter_tree/parameters/arity.
Cover the parsing of the parameter in the userspace test, with valid and
invalid shapes, and run the counter tests on the valid ones.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
.../admin-guide/kernel-parameters.txt | 14 +++
.../core-api/percpu-counter-tree.rst | 3 +-
lib/percpu_counter_tree.c | 96 ++++++++++++++++++-
tools/testing/hpcc/include/hpcc_shim.h | 4 +
.../testing/hpcc/include/linux/moduleparam.h | 12 +++
tools/testing/hpcc/main.c | 78 ++++++++++++++-
6 files changed, 201 insertions(+), 6 deletions(-)
create mode 100644 tools/testing/hpcc/include/linux/moduleparam.h
diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
index 0b3c140babd9..c368affa2115 100644
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -5342,6 +5342,20 @@ Kernel parameters
allocator. This parameter is primarily for debugging
and performance comparison.
+ percpu_counter_tree.arity= [KNL,SMP]
+ Format: <fan-out>[,<fan-out>...]
+ Override the shape of the hierarchical per-cpu
+ counter trees (used for the RSS counters), listing
+ the fan-out of each tree level from the per-cpu
+ counters to the root. Each fan-out is a power of 2
+ and their product must be nr_cpu_ids (the highest
+ possible CPU number plus one) rounded up to a power
+ of 2, e.g. "16" (flat) or "4,4" when nr_cpu_ids
+ is 16. An invalid shape is ignored with a warning.
+ The shape in use is shown in
+ /sys/module/percpu_counter_tree/parameters/arity.
+ This parameter is meant for performance comparison.
+
pirq= [SMP,APIC] Manual mp-table setup
See Documentation/arch/x86/i386/IO-APIC.rst.
diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation/core-api/percpu-counter-tree.rst
index 87babe2276c4..8aebf91aa133 100644
--- a/Documentation/core-api/percpu-counter-tree.rst
+++ b/Documentation/core-api/percpu-counter-tree.rst
@@ -63,7 +63,8 @@ possible CPU, and the tree items, whose number depends on nr_cpu_ids, so
struct percpu_counter_tree has a fixed size.
The fan-out of each tree level is selected at boot from nr_cpu_ids, the
-highest possible CPU number plus one.
+highest possible CPU number plus one. It can be overridden with the
+percpu_counter_tree.arity= boot parameter for performance comparison.
The bounded accuracy is a property of the settled tree. While updates are
in flight the transient error can exceed it, bounded by the number of
diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c
index 32c4f05d7d7d..491675897e41 100644
--- a/lib/percpu_counter_tree.c
+++ b/lib/percpu_counter_tree.c
@@ -151,6 +151,7 @@
#define pr_fmt(fmt) "percpu_counter_tree: " fmt
#include <linux/percpu_counter_tree.h>
+#include <linux/moduleparam.h>
#include <linux/align.h>
#include <linux/cache.h>
#include <linux/cpumask.h>
@@ -162,6 +163,7 @@
#include <linux/math.h>
#include <linux/log2.h>
#include <linux/args.h>
+#include <linux/string.h>
#include <kunit/visibility.h>
#define MAX_NR_LEVELS 7
@@ -254,6 +256,8 @@ static_assert(ARRAY_SIZE(per_nr_cpu_order_config) == MAX_NR_CPUS_ORDER + 1);
static struct {
/* Hierarchical counter configuration for the hardware topology. */
const struct counter_config *config;
+ /* Tree shape selected with the "arity" boot parameter. */
+ struct counter_config boot_config;
/* Order of nr_cpu_ids. */
unsigned int nr_cpus_order;
/*
@@ -272,6 +276,9 @@ static struct {
.nr_items = UINT_MAX,
};
+/* Value of the "arity" boot parameter, parsed at subsystem initialization. */
+static const char *arity_param;
+
/*
* Size of the items of one tree position for the counters initialized
* together by percpu_counter_tree_init_many(), packed in cache lines which
@@ -1326,7 +1333,10 @@ void percpu_counter_tree_copy_state(struct percpu_counter_tree *dst,
EXPORT_SYMBOL_IF_KUNIT(percpu_counter_tree_copy_state);
#endif
-/* Format the fan-out of each level, from level 0 to the root, e.g. "8,2,8". */
+/* Room for the fan-out of each level, up to 7 digits and a comma, and a NUL. */
+#define SHAPE_BUF_SIZE (8 * MAX_NR_LEVELS + 1)
+
+/* Format the fan-out of each level, from level 0 to the root, e.g. "8,4,8". */
static
int format_shape(char *buf, size_t size, const struct counter_config *config)
{
@@ -1339,9 +1349,78 @@ int format_shape(char *buf, size_t size, const struct counter_config *config)
return len;
}
+static
+int arity_param_set(const char *val, const struct kernel_param *kp)
+{
+ /* Applied once by percpu_counter_tree_subsystem_init(). */
+ if (tree_topology.config)
+ return -EBUSY;
+ arity_param = val;
+ return 0;
+}
+
+static
+int arity_param_get(char *buffer, const struct kernel_param *kp)
+{
+ int len;
+
+ if (!tree_topology.config)
+ return sprintf(buffer, "%s\n", arity_param ? : "");
+ /* The buffer is a page, larger than any shape and its newline. */
+ len = format_shape(buffer, SHAPE_BUF_SIZE, tree_topology.config);
+ buffer[len++] = '\n';
+ return len;
+}
+
+static const struct kernel_param_ops arity_param_ops = {
+ .set = arity_param_set,
+ .get = arity_param_get,
+};
+
+/*
+ * percpu_counter_tree.arity=<fan-out>[,<fan-out>...] overrides the tree
+ * shape chosen for nr_cpu_ids, to compare shapes on a given machine.
+ * Reading the parameter shows the shape in use.
+ */
+module_param_cb(arity, &arity_param_ops, NULL, 0444);
+MODULE_PARM_DESC(arity, "Fan-out of each tree level from level 0 to the root, e.g. 8,4,8");
+
+/*
+ * Parse a list of fan-outs, from level 0 to the root, into @config. Each
+ * fan-out is a power of 2 of at least 2, and their product is nr_cpu_ids
+ * rounded up to a power of 2.
+ *
+ * Return: 0 on success, -EINVAL if the list does not describe a tree
+ * covering the CPU numbers below nr_cpu_ids.
+ */
+static
+int __init parse_arity(const char *str, struct counter_config *config)
+{
+ int ints[MAX_NR_LEVELS + 2]; /* Count, levels, and one extra to detect overflow. */
+ unsigned int level, order = 0;
+
+ if (*get_options(str, ARRAY_SIZE(ints), ints) || ints[0] > MAX_NR_LEVELS)
+ return -EINVAL;
+ config->nr_levels = ints[0];
+ for (level = 0; level < config->nr_levels; level++) {
+ int fan_out = ints[level + 1];
+
+ if (fan_out < 2 || !is_power_of_2(fan_out))
+ return -EINVAL;
+ config->n_arity_order[level] = ilog2(fan_out);
+ order += config->n_arity_order[level];
+ if (order > tree_topology.nr_cpus_order)
+ return -EINVAL;
+ }
+ if (order != tree_topology.nr_cpus_order)
+ return -EINVAL;
+ return 0;
+}
+
int __init percpu_counter_tree_subsystem_init(void)
{
- char shape[8 * MAX_NR_LEVELS + 1] = "";
+ const char *origin = "default";
+ char shape[SHAPE_BUF_SIZE] = "";
tree_topology.nr_cpus_order = get_count_order(nr_cpu_ids);
if (tree_topology.nr_cpus_order >= ARRAY_SIZE(per_nr_cpu_order_config)) {
@@ -1349,14 +1428,23 @@ int __init percpu_counter_tree_subsystem_init(void)
return -EINVAL;
}
tree_topology.config = &per_nr_cpu_order_config[tree_topology.nr_cpus_order];
+ if (arity_param && *arity_param) {
+ if (parse_arity(arity_param, &tree_topology.boot_config)) {
+ pr_warn("Invalid arity \"%s\" for %u CPUs, using the default\n",
+ arity_param, nr_cpu_ids);
+ } else {
+ tree_topology.config = &tree_topology.boot_config;
+ origin = "boot parameter";
+ }
+ }
calculate_topology();
tree_topology.items_cachep =
kmem_cache_create("percpu_counter_tree_items",
tree_topology.nr_items * SMP_CACHE_BYTES,
SMP_CACHE_BYTES, SLAB_PANIC, NULL);
format_shape(shape, sizeof(shape), tree_topology.config);
- pr_info("%u CPUs, fan-out %s, %u tree items\n",
- nr_cpu_ids, tree_topology.nr_cpus_order ? shape : "none",
+ pr_info("%u CPUs, fan-out %s (%s), %u tree items\n",
+ nr_cpu_ids, tree_topology.nr_cpus_order ? shape : "none", origin,
tree_topology.nr_items);
return 0;
}
diff --git a/tools/testing/hpcc/include/hpcc_shim.h b/tools/testing/hpcc/include/hpcc_shim.h
index d321c8363b0b..eaac72eab2d1 100644
--- a/tools/testing/hpcc/include/hpcc_shim.h
+++ b/tools/testing/hpcc/include/hpcc_shim.h
@@ -34,8 +34,12 @@
#define abs(x) ({ typeof(x) __x = (x); __x < 0 ? -__x : __x; })
#define pr_err(...) fprintf(stderr, __VA_ARGS__)
+#define pr_warn(...) fprintf(stderr, __VA_ARGS__)
#define pr_info(...) do { if (0) printf(__VA_ARGS__); } while (0)
+/* Implemented in main.c. */
+char *get_options(const char *str, int nints, int *ints);
+
extern unsigned long hpcc_nr_warnings;
#define WARN(cond, ...) ({ \
diff --git a/tools/testing/hpcc/include/linux/moduleparam.h b/tools/testing/hpcc/include/linux/moduleparam.h
new file mode 100644
index 000000000000..7e40df4295b2
--- /dev/null
+++ b/tools/testing/hpcc/include/linux/moduleparam.h
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+#include "../hpcc_shim.h"
+
+struct kernel_param;
+
+struct kernel_param_ops {
+ int (*set)(const char *val, const struct kernel_param *kp);
+ int (*get)(char *buffer, const struct kernel_param *kp);
+};
+
+#define module_param_cb(name, ops, arg, perm)
+#define MODULE_PARM_DESC(parm, desc)
diff --git a/tools/testing/hpcc/main.c b/tools/testing/hpcc/main.c
index c3583a287cdd..be17b8873126 100644
--- a/tools/testing/hpcc/main.c
+++ b/tools/testing/hpcc/main.c
@@ -81,6 +81,27 @@ int scnprintf(char *buf, size_t size, const char *fmt, ...)
return len < (int)size ? len : (int)size - 1;
}
+/* Comma-separated integers, without the ranges of lib/cmdline.c. */
+char *get_options(const char *str, int nints, int *ints)
+{
+ char *end;
+ int i = 0;
+
+ while (i < nints - 1 && *str) {
+ long v = strtol(str, &end, 0);
+
+ if (end == str)
+ break;
+ ints[++i] = v;
+ str = end;
+ if (*str != ',')
+ break;
+ str++;
+ }
+ ints[0] = i;
+ return (char *)str;
+}
+
static void hpcc_init_topology(unsigned int nr_cpus)
{
nr_cpu_ids = nr_cpus;
@@ -414,6 +435,58 @@ static int run_case(unsigned int nr_cpus, unsigned long batch_size)
return nr_case_failures ? 1 : 0;
}
+/* Tree shapes given with the arity boot parameter. */
+static const struct {
+ unsigned int nr_cpus;
+ const char *arity;
+ const char *shape; /* Shape in use, NULL if the arity is invalid. */
+} test_arity[] = {
+ { 16, "16", "16" },
+ { 16, "4,4", "4,4" },
+ { 16, "2,2,2,2", "2,2,2,2" },
+ { 16, "4,2", NULL }, /* Covers 8 CPUs. */
+ { 16, "4,8", NULL }, /* Covers 32 CPUs. */
+ { 16, "4,4,1", NULL }, /* Fan-out of 1. */
+ { 16, "4,3", NULL }, /* Not a power of 2. */
+ { 16, "4,4x", NULL }, /* Trailing characters. */
+ { 16, "-4,-4", NULL },
+ { 17, "8,4", "8,4" },
+ { 100, "128", "128" },
+ { 192, "8,4,8", "8,4,8" },
+ { 192, "2,2,2,2,2,2,2,2", NULL }, /* More than MAX_NR_LEVELS. */
+ { 1024, "32,32", "32,32" },
+ { 1, "2", NULL },
+};
+
+static int run_arity_case(unsigned int i)
+{
+ const char *expect = test_arity[i].shape;
+ char buf[SHAPE_BUF_SIZE];
+ int len;
+
+ nr_case_failures = 0;
+ hpcc_nr_warnings = 0;
+ tree_topology.config = NULL;
+ CHECK(!arity_param_set(test_arity[i].arity, NULL));
+ hpcc_init_topology(test_arity[i].nr_cpus);
+ arity_param = NULL;
+ CHECK(arity_param_set("16", NULL) == -EBUSY);
+ CHECK((tree_topology.config == &tree_topology.boot_config) == !!expect);
+ len = arity_param_get(buf, NULL);
+ CHECK(len > 0 && buf[len - 1] == '\n');
+ buf[len - 1] = '\0';
+ if (expect) {
+ CHECK(!strcmp(buf, expect));
+ test_saturated(2, 1);
+ test_saturated(32, -1);
+ test_random_walk(32, 20000);
+ }
+ CHECK(!hpcc_nr_warnings);
+ printf("%sok %d - arity nr_cpus=%u \"%s\" -> \"%s\"\n", nr_case_failures ? "not " : "",
+ ++test_num, test_arity[i].nr_cpus, test_arity[i].arity, buf);
+ return nr_case_failures ? 1 : 0;
+}
+
static int run_check_config(void)
{
unsigned int nr_errors = percpu_counter_tree_check_config();
@@ -441,12 +514,15 @@ int main(int argc, char **argv)
if (argc == 2)
large = true;
- nr_tests = 1 + ARRAY_SIZE(test_nr_cpus) * ARRAY_SIZE(test_batch_sizes);
+ nr_tests = 1 + ARRAY_SIZE(test_arity) +
+ ARRAY_SIZE(test_nr_cpus) * ARRAY_SIZE(test_batch_sizes);
if (large)
nr_tests += ARRAY_SIZE(test_nr_cpus_large) * ARRAY_SIZE(test_batch_sizes);
printf("1..%u\n", nr_tests);
failed += run_check_config();
+ for (i = 0; i < ARRAY_SIZE(test_arity); i++)
+ failed += run_arity_case(i);
for (i = 0; i < ARRAY_SIZE(test_nr_cpus); i++)
for (j = 0; j < ARRAY_SIZE(test_batch_sizes); j++)
failed += run_case(test_nr_cpus[i], test_batch_sizes[j]);
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 09/10] mm: add the rss_stat_batch boot parameter
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (7 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 08/10] lib: percpu_counter_tree: add the arity boot parameter Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 10/10] lib: add a benchmark of hierarchical per-cpu counters Mathieu Desnoyers
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
The RSS counters use a batch size of 32: each CPU accumulates up to 31
pages in either direction before propagating a carry into the counter
tree. A smaller batch improves the accuracy of the approximate RSS, and
a larger batch reduces the cost of updates.
Add the rss_stat_batch= boot parameter to compare batch sizes on a
given machine, along with the percpu_counter_tree.arity= boot parameter
for the tree shape. It accepts a power of 2 between 2 and 128, and is
ignored with a warning otherwise.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
.../admin-guide/kernel-parameters.txt | 10 ++++++++
kernel/fork.c | 23 ++++++++++++++++---
2 files changed, 30 insertions(+), 3 deletions(-)
diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
index c368affa2115..ba2bdeb1480b 100644
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -6792,6 +6792,16 @@ Kernel parameters
debug mode. Defaults to CONFIG_RSEQ_DEBUG_DEFAULT_ENABLE.
Format: <bool>
+ rss_stat_batch= [KNL,SMP]
+ Format: <integer>
+ Batch size of the per-mm RSS counters: the number of
+ pages a CPU accumulates before propagating them into
+ the counter tree. A power of 2 between 2 and 128.
+ A smaller batch improves the accuracy of the
+ approximate RSS, a larger batch reduces the update
+ cost. Default: 32.
+ This parameter is meant for performance comparison.
+
rt_group_sched= [KNL] Enable or disable SCHED_RR/FIFO group scheduling
when CONFIG_RT_GROUP_SCHED=y. Defaults to
!CONFIG_RT_GROUP_SCHED_DEFAULT_DISABLED.
diff --git a/kernel/fork.c b/kernel/fork.c
index ac4eb1370e62..d0641700cd9c 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -138,9 +138,26 @@
#define MAX_THREADS FUTEX_TID_MASK
/*
- * Batch size of rss stat approximation
+ * Batch size of rss stat approximation, tunable with the rss_stat_batch=
+ * boot parameter to compare batch sizes on a given machine.
*/
-#define RSS_STAT_BATCH_SIZE 32
+static unsigned int rss_stat_batch_size __ro_after_init = 32;
+
+static int __init setup_rss_stat_batch(char *str)
+{
+ unsigned int batch;
+
+ if (kstrtouint(str, 0, &batch) || batch < 2 || !is_power_of_2(batch) ||
+ batch > PERCPU_COUNTER_TREE_MAX_BATCH) {
+ pr_warn("rss_stat_batch: expecting a power of 2 between 2 and %u\n",
+ PERCPU_COUNTER_TREE_MAX_BATCH);
+ return 1;
+ }
+ rss_stat_batch_size = batch;
+ pr_info("rss_stat_batch: %u\n", batch);
+ return 1;
+}
+__setup("rss_stat_batch=", setup_rss_stat_batch);
/*
* Protected counters by write_lock_irq(&tasklist_lock)
@@ -1149,7 +1166,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
if (mm_alloc_sched(mm))
goto fail_sched;
- if (percpu_counter_tree_init_many_lazy(mm->rss_stat, NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE))
+ if (percpu_counter_tree_init_many_lazy(mm->rss_stat, NR_MM_COUNTERS, rss_stat_batch_size))
goto fail_pcpu;
lru_gen_init_mm(mm);
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RFC PATCH v23 10/10] lib: add a benchmark of hierarchical per-cpu counters
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
` (8 preceding siblings ...)
2026-11-02 19:07 ` [RFC PATCH v23 09/10] mm: add the rss_stat_batch " Mathieu Desnoyers
@ 2026-11-02 19:07 ` Mathieu Desnoyers
9 siblings, 0 replies; 11+ messages in thread
From: Mathieu Desnoyers @ 2026-11-02 19:07 UTC (permalink / raw)
To: David Hildenbrand
Cc: linux-kernel, Mathieu Desnoyers, Paul E. McKenney,
Steven Rostedt, Masami Hiramatsu, Dennis Zhou, Tejun Heo,
Christoph Lameter, Martin Liu, David Rientjes, christian.koenig,
Shakeel Butt, SeongJae Park, Michal Hocko, Johannes Weiner,
Sweet Tea Dorminy, Lorenzo Stoakes, Liam R. Howlett,
Mike Rapoport, Suren Baghdasaryan, Vlastimil Babka,
Christian Brauner, Wei Yang, Miaohe Lin, Al Viro, Yu Zhao,
Roman Gushchin, Mateusz Guzik, Matthew Wilcox, Baolin Wang,
Aboorva Devarajan, David Carlier, Josh Law, Andrew Morton,
linux-mm, Jonathan Corbet, Shuah Khan, Randy Dunlap, linux-doc,
Kees Cook, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, linux-trace-kernel,
Jan Kara, linux-fsdevel, Oleg Nesterov
Add a KUnit benchmark comparing the hierarchical per-cpu counters with
struct percpu_counter, so their performance can be compared on various
machines:
- update: cost of an update with a kthread on each online CPU, on one
shared counter, on one counter per thread, on groups of 4 counters
initialized together like the RSS counters of an mm, and on one lazily
initialized counter per thread updated by its owner, like a
single-threaded process, with increments of +1, alternating +1/-1, and
random increments up to 32 and 512.
- lifecycle: cost of initializing and destroying 4 counters together,
like fork and exit of an mm, eagerly or lazily, from one thread or from
all online CPUs.
- churn: like lifecycle, with a few updates, keeping some of the
counters alive until the end, like long-lived processes.
The batch size of the hierarchical counters is selected with the
percpu_counter_tree_bench.batch= parameter (32 by default, like the RSS
counters), and the tree shape with the percpu_counter_tree.arity= boot
parameter. The struct percpu_counter variants use their default batch
size, like the RSS counters before the hierarchical counters.
The benchmark reports the accuracy of both counter implementations along
with the timings. It runs for a few minutes on large machines, so it
has its own config option, CONFIG_PERCPU_COUNTER_TREE_BENCH.
For example:
./tools/testing/kunit/kunit.py run --arch=x86_64 \
--kconfig_add CONFIG_PERCPU_COUNTER_TREE_BENCH=y \
--kconfig_add CONFIG_NR_CPUS=256 --qemu_args="-smp 64 -m 8192" \
--kernel_args percpu_counter_tree.arity=8,8 \
--kernel_args percpu_counter_tree_bench.batch=16 \
--timeout 3000 percpu_counter_tree_bench
or, on a running kernel with CONFIG_PERCPU_COUNTER_TREE_BENCH=m:
modprobe percpu_counter_tree_bench batch=16
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
MAINTAINERS | 1 +
lib/Kconfig | 15 +
lib/tests/Makefile | 1 +
lib/tests/percpu_counter_tree_bench.c | 604 ++++++++++++++++++++++++++
4 files changed, 621 insertions(+)
create mode 100644 lib/tests/percpu_counter_tree_bench.c
diff --git a/MAINTAINERS b/MAINTAINERS
index 4d421a784e88..3878203de1c3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -11955,6 +11955,7 @@ S: Supported
F: Documentation/core-api/percpu-counter-tree.rst
F: include/linux/percpu_counter_tree.h
F: lib/percpu_counter_tree.c
+F: lib/tests/percpu_counter_tree_bench.c
F: lib/tests/percpu_counter_tree_kunit.c
F: tools/testing/hpcc/
diff --git a/lib/Kconfig b/lib/Kconfig
index 3921177a0d24..6ab9644a4cb8 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -53,6 +53,21 @@ config PERCPU_COUNTER_TREE_KUNIT_TEST
When in doubt, say N.
+config PERCPU_COUNTER_TREE_BENCH
+ tristate "Benchmark of hierarchical per-cpu counters"
+ depends on KUNIT && SMP
+ help
+ This builds a KUnit benchmark comparing the hierarchical per-cpu
+ counters with struct percpu_counter: update cost with all online
+ CPUs updating shared and private counters, and init/destroy cost.
+ It runs for a few minutes on large machines.
+
+ The batch size and the tree shape can be changed with the
+ percpu_counter_tree_bench.batch= and percpu_counter_tree.arity=
+ parameters, see lib/tests/percpu_counter_tree_bench.c.
+
+ When in doubt, say N.
+
config BITREVERSE
tristate
select GENERIC_BITREVERSE if !HAVE_ARCH_BITREVERSE
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index e98687da8706..d158a8be8a19 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -60,5 +60,6 @@ obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
obj-$(CONFIG_UUID_KUNIT_TEST) += uuid_kunit.o
obj-$(CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST) += percpu_counter_tree_kunit.o
+obj-$(CONFIG_PERCPU_COUNTER_TREE_BENCH) += percpu_counter_tree_bench.o
obj-$(CONFIG_TEST_RUNTIME_MODULE) += module/
diff --git a/lib/tests/percpu_counter_tree_bench.c b/lib/tests/percpu_counter_tree_bench.c
new file mode 100644
index 000000000000..bf260bef196a
--- /dev/null
+++ b/lib/tests/percpu_counter_tree_bench.c
@@ -0,0 +1,604 @@
+// SPDX-License-Identifier: GPL-2.0+ OR MIT
+/*
+ * Benchmark of hierarchical per-CPU counters against struct percpu_counter.
+ *
+ * update: ns per percpu_counter_tree_add() per thread, one kthread pinned
+ * on each online CPU, on one shared counter, on one counter per
+ * thread, or on the counters of a few mm-like groups of 4 counters
+ * initialized together. The "single" variant gives each thread a
+ * lazily initialized counter updated with
+ * percpu_counter_tree_add_owner(), like a single-threaded process.
+ * The "percpu_counter" variants use percpu_counter_add() with the
+ * default batch, like the RSS counters before hierarchical counters.
+ * lifecycle: ns per init_many(4) + destroy_many(4), like fork + exit of an
+ * mm, from one thread or from all online CPUs at once; "lazy" uses
+ * init_many_lazy(4), like a single-threaded process.
+ * churn: like lifecycle with a few updates, keeping one in @pin_period sets
+ * of counters alive until the end, like long-lived processes.
+ *
+ * Each result ends with the implementation measured: "tree" for the
+ * hierarchical counters, "percpu_counter" for struct percpu_counter.
+ *
+ * The knobs to try on a given machine are:
+ * - the batch size: percpu_counter_tree_bench.batch=<2..128> (power of 2),
+ * or "modprobe percpu_counter_tree_bench batch=<n>",
+ * - the tree shape: percpu_counter_tree.arity=<fan-out>,... on the kernel
+ * command line, from level 0 to the root. The product of the fan-outs
+ * is nr_cpu_ids rounded up to a power of 2, e.g. "16" (flat) or "4,4"
+ * when nr_cpu_ids is 16. The shape in use is shown in
+ * /sys/module/percpu_counter_tree/parameters/arity.
+ *
+ * For example, in a VM:
+ * ./tools/testing/kunit/kunit.py run --arch=x86_64 \
+ * --kconfig_add CONFIG_PERCPU_COUNTER_TREE_BENCH=y \
+ * --kconfig_add CONFIG_NR_CPUS=256 --qemu_args="-smp 64 -m 8192" \
+ * --kernel_args percpu_counter_tree.arity=8,8 \
+ * --kernel_args percpu_counter_tree_bench.batch=16 \
+ * --timeout 3000 percpu_counter_tree_bench
+ */
+#include <kunit/test.h>
+#include <linux/percpu_counter_tree.h>
+#include <linux/percpu_counter.h>
+#include <linux/kthread.h>
+#include <linux/random.h>
+#include <linux/slab.h>
+#include <linux/delay.h>
+#include <linux/ktime.h>
+#include <linux/math64.h>
+#include <linux/sched/task.h>
+#include <linux/cpuhplock.h>
+#include <linux/moduleparam.h>
+
+/* Like the RSS counters by default. */
+static unsigned int batch = 32;
+module_param(batch, uint, 0444);
+MODULE_PARM_DESC(batch, "Batch size of the hierarchical counters (power of 2, 2 to 128)");
+
+#define BENCH_MS 300
+#define LIFECYCLE_NR 4 /* Counters per mm. */
+#define LIFECYCLE_ITER 2000
+#define CHURN_ITER 4096
+
+enum { W_MONO, W_BOUNCE, W_RAND32, W_RAND512, NR_W };
+static const char * const wname[] = { "monotonic +1", "bounce +-1", "random +-32", "random +-512" };
+
+enum bench_impl { IMPL_TREE, IMPL_PERCPU_COUNTER };
+static const char * const impl_name[] = { "tree", "percpu_counter" };
+
+struct bench_shared {
+ atomic_t ready;
+ int wl;
+ unsigned int pin_period; /* churn: keep one in pin_period sets, 0: none. */
+ enum bench_impl impl;
+ bool go, stop;
+ bool owner; /* update: percpu_counter_tree_add_owner(). */
+ bool lifecycle;
+ bool lazy; /* lifecycle: percpu_counter_tree_init_many_lazy(). */
+};
+
+struct bench_thread {
+ u64 ns;
+ unsigned long ops;
+ struct bench_shared *sh;
+ struct percpu_counter_tree *c;
+ struct percpu_counter *pc; /* update: IMPL_PERCPU_COUNTER. */
+ struct percpu_counter_tree *pinned; /* churn: IMPL_TREE sets kept alive. */
+ struct percpu_counter *pinned_pc; /* churn: IMPL_PERCPU_COUNTER sets kept alive. */
+ struct task_struct *task;
+ unsigned int nr_pinned;
+ u32 seed;
+} ____cacheline_aligned_in_smp;
+
+/*
+ * Buffers are allocated through KUnit, which frees them if an assertion
+ * aborts the test, and are freed explicitly otherwise, since the benchmark
+ * runs many steps within one test.
+ */
+KUNIT_DEFINE_ACTION_WRAPPER(bench_kvfree, kvfree, const void *);
+
+static void *bench_kvzalloc(struct kunit *test, size_t size)
+{
+ void *p = kvzalloc(size, GFP_KERNEL);
+
+ if (p && kunit_add_action_or_reset(test, bench_kvfree, p))
+ return NULL;
+ return p;
+}
+
+static void bench_kvfree_now(struct kunit *test, void *p)
+{
+ kunit_release_action(test, bench_kvfree, p);
+}
+
+/* Wait for the start signal; return true if the benchmark is cancelled. */
+static bool bench_wait_go(struct bench_shared *sh)
+{
+ atomic_inc(&sh->ready);
+ /* Pairs with bench_start(): a cancellation sets stop before go. */
+ while (!smp_load_acquire(&sh->go))
+ cond_resched();
+ return READ_ONCE(sh->stop);
+}
+
+static int bench_update_fn(void *data)
+{
+ struct bench_thread *t = data;
+ struct bench_shared *sh = t->sh;
+ unsigned long ops = 0;
+ long sign = -1;
+ u32 x = t->seed;
+ int i;
+
+ if (bench_wait_go(sh))
+ return 0;
+ while (!READ_ONCE(sh->stop)) {
+ for (i = 0; i < 1024; i++) {
+ long inc;
+
+ switch (sh->wl) {
+ case W_MONO:
+ inc = 1;
+ break;
+ case W_BOUNCE:
+ inc = sign;
+ sign = -sign;
+ break;
+ default:
+ x ^= x << 13;
+ x ^= x >> 17;
+ x ^= x << 5;
+ inc = sh->wl == W_RAND32 ? 32 : 512;
+ if (x & 1)
+ inc = -inc;
+ break;
+ }
+ if (sh->impl == IMPL_PERCPU_COUNTER)
+ percpu_counter_add(t->pc, inc);
+ else if (sh->owner)
+ percpu_counter_tree_add_owner(t->c, inc);
+ else
+ percpu_counter_tree_add(t->c, inc);
+ }
+ ops += 1024;
+ cond_resched();
+ }
+ t->ops = ops;
+ return 0;
+}
+
+static int bench_lifecycle_fn(void *data)
+{
+ struct bench_thread *t = data;
+ struct percpu_counter_tree c[LIFECYCLE_NR];
+ struct percpu_counter pc[LIFECYCLE_NR];
+ u64 t0;
+ int i;
+
+ if (bench_wait_go(t->sh))
+ return 0;
+ t0 = ktime_get_ns();
+ for (i = 0; t->sh->impl == IMPL_PERCPU_COUNTER && i < LIFECYCLE_ITER; i++) {
+ if (percpu_counter_init_many(pc, 0, GFP_KERNEL, LIFECYCLE_NR))
+ break;
+ percpu_counter_add(&pc[0], 1);
+ percpu_counter_add(&pc[0], -1);
+ percpu_counter_destroy_many(pc, LIFECYCLE_NR);
+ cond_resched();
+ }
+ for (; t->sh->impl == IMPL_TREE && t->sh->lazy && i < LIFECYCLE_ITER; i++) {
+ if (percpu_counter_tree_init_many_lazy(c, LIFECYCLE_NR, batch))
+ break;
+ percpu_counter_tree_add_owner(&c[0], 1);
+ percpu_counter_tree_add_owner(&c[0], -1);
+ percpu_counter_tree_destroy_many(c, LIFECYCLE_NR);
+ cond_resched();
+ }
+ for (; t->sh->impl == IMPL_TREE && !t->sh->lazy && i < LIFECYCLE_ITER; i++) {
+ if (percpu_counter_tree_init_many(c, LIFECYCLE_NR, batch, GFP_KERNEL))
+ break;
+ percpu_counter_tree_add(&c[0], 1);
+ percpu_counter_tree_add(&c[0], -1);
+ percpu_counter_tree_destroy_many(c, LIFECYCLE_NR);
+ cond_resched();
+ }
+ t->ns = ktime_get_ns() - t0;
+ t->ops = i;
+ return 0;
+}
+
+static int bench_churn_fn(void *data)
+{
+ struct bench_thread *t = data;
+ unsigned int pin_period = t->sh->pin_period;
+ struct percpu_counter_tree tmp[LIFECYCLE_NR], *c;
+ struct percpu_counter tmp_pc[LIFECYCLE_NR], *pc;
+ u64 t0;
+ int i;
+
+ if (bench_wait_go(t->sh))
+ return 0;
+ t0 = ktime_get_ns();
+ for (i = 0; t->sh->impl == IMPL_PERCPU_COUNTER && i < CHURN_ITER; i++) {
+ bool pin = pin_period && !(i % pin_period);
+
+ pc = pin ? &t->pinned_pc[t->nr_pinned * LIFECYCLE_NR] : tmp_pc;
+ if (percpu_counter_init_many(pc, 0, GFP_KERNEL, LIFECYCLE_NR))
+ break;
+ percpu_counter_add(&pc[0], 100);
+ percpu_counter_add(&pc[1], -77);
+ percpu_counter_add(&pc[2], 1);
+ if (pin)
+ t->nr_pinned++;
+ else
+ percpu_counter_destroy_many(pc, LIFECYCLE_NR);
+ cond_resched();
+ }
+ for (; t->sh->impl == IMPL_TREE && i < CHURN_ITER; i++) {
+ bool pin = pin_period && !(i % pin_period);
+
+ c = pin ? &t->pinned[t->nr_pinned * LIFECYCLE_NR] : tmp;
+ if (percpu_counter_tree_init_many(c, LIFECYCLE_NR, batch, GFP_KERNEL))
+ break;
+ percpu_counter_tree_add(&c[0], 100);
+ percpu_counter_tree_add(&c[1], -77);
+ percpu_counter_tree_add(&c[2], 1);
+ if (pin)
+ t->nr_pinned++;
+ else
+ percpu_counter_tree_destroy_many(c, LIFECYCLE_NR);
+ cond_resched();
+ }
+ t->ns = ktime_get_ns() - t0;
+ t->ops = i;
+ return 0;
+}
+
+/* List at most @max online CPUs in @cpus, and return their number. */
+static unsigned int bench_cpus(int *cpus, unsigned int max)
+{
+ unsigned int n = 0;
+ int cpu;
+
+ for_each_online_cpu(cpu) {
+ if (n == max)
+ break;
+ cpus[n++] = cpu;
+ }
+ return n;
+}
+
+static void bench_stop(struct bench_thread *t, unsigned int n)
+{
+ unsigned int i;
+
+ for (i = 0; i < n; i++)
+ kthread_stop_put(t[i].task);
+}
+
+/*
+ * Start a thread on each of the @n CPUs of @cpus, waiting for the start
+ * signal. On failure, cancel and join the threads already started.
+ */
+static int bench_start(struct bench_shared *sh, struct bench_thread *t, const int *cpus,
+ unsigned int n)
+{
+ unsigned int i;
+
+ for (i = 0; i < n; i++) {
+ t[i].sh = sh;
+ t[i].task = kthread_create_on_cpu(sh->pin_period != UINT_MAX ? bench_churn_fn :
+ sh->lifecycle ? bench_lifecycle_fn :
+ bench_update_fn, &t[i], cpus[i], "hpcc_bench/%u");
+ if (IS_ERR(t[i].task)) {
+ int ret = PTR_ERR(t[i].task);
+
+ WRITE_ONCE(sh->stop, true);
+ /* Pairs with bench_wait_go(): the threads see stop with go. */
+ smp_store_release(&sh->go, true);
+ bench_stop(t, i);
+ return ret;
+ }
+ get_task_struct(t[i].task);
+ wake_up_process(t[i].task);
+ }
+ while (atomic_read(&sh->ready) < n)
+ usleep_range(1000, 2000);
+ return 0;
+}
+
+enum bench_mode { BENCH_SHARED, BENCH_PRIVATE, BENCH_MM, BENCH_SINGLE };
+static const char * const mode_name[] = { "shared", "private", "mm", "single" };
+
+/*
+ * BENCH_SHARED: all threads update one counter.
+ * BENCH_PRIVATE: each thread updates its own counter (a separate mm).
+ * BENCH_MM: blocks of n / LIFECYCLE_NR threads each update one counter of
+ * one mm. Its counters share the cache lines of their tree items, and
+ * CPUs sharing an item are strided, so each line is updated for every
+ * counter.
+ * BENCH_SINGLE: each thread owns a lazily initialized counter, like a
+ * single-threaded process, never activated. Its IMPL_PERCPU_COUNTER
+ * comparison is BENCH_PRIVATE.
+ */
+/* Counters @i of bench_update(), @c_stride and @pc_stride bytes apart. */
+#define BENCH_C(i) ((struct percpu_counter_tree *)((char *)c + (i) * c_stride))
+#define BENCH_PC(i) ((struct percpu_counter *)((char *)pc + (i) * pc_stride))
+
+static void bench_update(struct kunit *test, enum bench_mode mode, int wl,
+ enum bench_impl impl)
+{
+ bool shared = mode == BENCH_SHARED || mode == BENCH_MM;
+ unsigned int n, i, nr_counters, nr_init = 0;
+ struct bench_shared sh = { .wl = wl, .pin_period = UINT_MAX, .impl = impl,
+ .owner = mode == BENCH_SINGLE };
+ struct percpu_counter_tree *c;
+ struct percpu_counter *pc;
+ struct bench_thread *t;
+ unsigned long ops = 0;
+ unsigned int *perm;
+ size_t c_stride, pc_stride;
+ void *c_mem, *pc_mem;
+ u64 t0, t1;
+ int *cpus;
+ int ret;
+
+ cpus = kunit_kcalloc(test, nr_cpu_ids, sizeof(*cpus), GFP_KERNEL);
+ t = bench_kvzalloc(test, array_size(nr_cpu_ids, sizeof(*t)));
+ perm = kunit_kcalloc(test, nr_cpu_ids, sizeof(*perm), GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, cpus);
+ KUNIT_ASSERT_NOT_NULL(test, t);
+ KUNIT_ASSERT_NOT_NULL(test, perm);
+ /*
+ * Set up the counters for the CPUs online now, before taking
+ * cpus_read_lock(), which a failed assertion would leave held. The
+ * threads then run on the CPUs online under the lock, at most as many.
+ */
+ n = num_online_cpus();
+ nr_counters = mode == BENCH_SHARED ? 1 : mode == BENCH_MM ? LIFECYCLE_NR : n;
+ /*
+ * Each private counter is written by its own thread: give each its
+ * own cache line, as the RSS counters of separate mms, to avoid false
+ * sharing. The counters of one mm stay packed, as in mm_struct.
+ */
+ c_stride = shared ? sizeof(*c) : ALIGN(sizeof(*c), SMP_CACHE_BYTES);
+ pc_stride = shared ? sizeof(*pc) : ALIGN(sizeof(*pc), SMP_CACHE_BYTES);
+ c_mem = kunit_kzalloc(test, nr_counters * c_stride + SMP_CACHE_BYTES, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, c_mem);
+ c = PTR_ALIGN(c_mem, SMP_CACHE_BYTES);
+ pc_mem = kunit_kzalloc(test, nr_counters * pc_stride + SMP_CACHE_BYTES, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, pc_mem);
+ pc = PTR_ALIGN(pc_mem, SMP_CACHE_BYTES);
+ /*
+ * Each private counter stands for a separate mm: initialize them
+ * separately so they do not share the cache lines of their tree items.
+ */
+ if (impl == IMPL_PERCPU_COUNTER && mode == BENCH_MM) {
+ if (!percpu_counter_init_many(pc, 0, GFP_KERNEL, nr_counters))
+ nr_init = nr_counters;
+ } else if (impl == IMPL_PERCPU_COUNTER) {
+ for (; nr_init < nr_counters; nr_init++)
+ if (percpu_counter_init(BENCH_PC(nr_init), 0, GFP_KERNEL))
+ break;
+ } else if (mode == BENCH_MM) {
+ if (!percpu_counter_tree_init_many(c, nr_counters, batch, GFP_KERNEL))
+ nr_init = nr_counters;
+ } else {
+ for (; nr_init < nr_counters; nr_init++) {
+ if (mode == BENCH_SINGLE ?
+ percpu_counter_tree_init_many_lazy(BENCH_C(nr_init), 1, batch) :
+ percpu_counter_tree_init(BENCH_C(nr_init), batch, GFP_KERNEL))
+ break;
+ }
+ }
+ if (nr_init < nr_counters) {
+ KUNIT_FAIL(test, "cannot initialize %u counters", nr_counters);
+ goto destroy;
+ }
+ cpus_read_lock();
+ n = bench_cpus(cpus, n);
+ /* Random placement of the private counters. */
+ for (i = 0; i < n; i++)
+ perm[i] = mode == BENCH_SHARED ? 0 : mode == BENCH_MM ? i * LIFECYCLE_NR / n : i;
+ for (i = n - 1; !shared && i > 0; i--)
+ swap(perm[i], perm[get_random_u32_below(i + 1)]);
+ for (i = 0; i < n; i++) {
+ t[i].c = BENCH_C(perm[i]);
+ t[i].pc = BENCH_PC(perm[i]);
+ t[i].seed = get_random_u32() | 1;
+ }
+ ret = bench_start(&sh, t, cpus, n);
+ if (ret) {
+ cpus_read_unlock();
+ KUNIT_FAIL(test, "cannot start the benchmark threads: %d", ret);
+ goto destroy;
+ }
+ t0 = ktime_get_ns();
+ WRITE_ONCE(sh.go, true);
+ msleep(BENCH_MS);
+ WRITE_ONCE(sh.stop, true);
+ t1 = ktime_get_ns();
+ bench_stop(t, n);
+ cpus_read_unlock();
+ for (i = 0; i < n; i++)
+ ops += t[i].ops;
+ for (i = 0; impl == IMPL_TREE && i < nr_counters; i++)
+ KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_check_residuals(BENCH_C(i)));
+ kunit_info(test, "update %-8s %-14s %3u thr %10llu ns/op/thr %s\n",
+ mode_name[mode], wname[wl], n,
+ ops ? div64_ul((t1 - t0) * n, ops) : 0, impl_name[impl]);
+destroy:
+ if (impl == IMPL_PERCPU_COUNTER && mode == BENCH_MM) {
+ if (nr_init)
+ percpu_counter_destroy_many(pc, nr_counters);
+ } else if (impl == IMPL_PERCPU_COUNTER) {
+ for (i = 0; i < nr_init; i++)
+ percpu_counter_destroy(BENCH_PC(i));
+ } else if (mode == BENCH_MM) {
+ if (nr_init)
+ percpu_counter_tree_destroy_many(c, nr_counters);
+ } else {
+ for (i = 0; i < nr_init; i++)
+ percpu_counter_tree_destroy(BENCH_C(i));
+ }
+ kunit_kfree(test, pc_mem);
+ kunit_kfree(test, c_mem);
+ kunit_kfree(test, perm);
+ bench_kvfree_now(test, t);
+ kunit_kfree(test, cpus);
+}
+
+static void bench_lifecycle(struct kunit *test, bool all, enum bench_impl impl, bool lazy)
+{
+ struct bench_shared sh = { .lifecycle = true, .pin_period = UINT_MAX,
+ .impl = impl, .lazy = lazy };
+ unsigned int n, i;
+ struct bench_thread *t;
+ unsigned long ops = 0;
+ u64 ns = 0;
+ int *cpus;
+ int ret;
+
+ cpus = kunit_kcalloc(test, nr_cpu_ids, sizeof(*cpus), GFP_KERNEL);
+ t = bench_kvzalloc(test, array_size(nr_cpu_ids, sizeof(*t)));
+ KUNIT_ASSERT_NOT_NULL(test, cpus);
+ KUNIT_ASSERT_NOT_NULL(test, t);
+ cpus_read_lock();
+ n = bench_cpus(cpus, all ? num_online_cpus() : 1);
+ ret = bench_start(&sh, t, cpus, n);
+ if (ret) {
+ cpus_read_unlock();
+ KUNIT_FAIL(test, "cannot start the benchmark threads: %d", ret);
+ goto free;
+ }
+ WRITE_ONCE(sh.go, true);
+ bench_stop(t, n);
+ cpus_read_unlock();
+ for (i = 0; i < n; i++) {
+ ops += t[i].ops;
+ ns += t[i].ns;
+ }
+ KUNIT_EXPECT_EQ(test, ops, (unsigned long)n * LIFECYCLE_ITER);
+ kunit_info(test, "lifecycle init_many%s(%d)+destroy_many %3u thr %10llu ns/op %s\n",
+ lazy ? "_lazy" : "", LIFECYCLE_NR, n, ops ? div64_ul(ns, ops) : 0,
+ impl_name[impl]);
+free:
+ bench_kvfree_now(test, t);
+ kunit_kfree(test, cpus);
+}
+
+static void bench_churn(struct kunit *test, bool all, unsigned int pin_period,
+ enum bench_impl impl)
+{
+ struct bench_shared sh = { .pin_period = pin_period, .impl = impl };
+ unsigned int n, i, j, max_pinned = pin_period ? DIV_ROUND_UP(CHURN_ITER, pin_period) : 0;
+ unsigned long ops = 0, live = 0;
+ unsigned int nr_alloc;
+ struct bench_thread *t;
+ u64 ns = 0;
+ int *cpus;
+ int ret;
+
+ cpus = kunit_kcalloc(test, nr_cpu_ids, sizeof(*cpus), GFP_KERNEL);
+ t = bench_kvzalloc(test, array_size(nr_cpu_ids, sizeof(*t)));
+ KUNIT_ASSERT_NOT_NULL(test, cpus);
+ KUNIT_ASSERT_NOT_NULL(test, t);
+ /* Allocate before taking cpus_read_lock(), as in bench_update(). */
+ nr_alloc = all ? num_online_cpus() : 1;
+ for (i = 0; i < nr_alloc; i++) {
+ t[i].pinned = bench_kvzalloc(test, array_size(max_pinned * LIFECYCLE_NR + 1,
+ sizeof(*t[i].pinned)));
+ t[i].pinned_pc = bench_kvzalloc(test, array_size(max_pinned * LIFECYCLE_NR + 1,
+ sizeof(*t[i].pinned_pc)));
+ KUNIT_ASSERT_NOT_NULL(test, t[i].pinned_pc);
+ KUNIT_ASSERT_NOT_NULL(test, t[i].pinned);
+ }
+ cpus_read_lock();
+ n = bench_cpus(cpus, nr_alloc);
+ ret = bench_start(&sh, t, cpus, n);
+ if (ret) {
+ cpus_read_unlock();
+ KUNIT_FAIL(test, "cannot start the benchmark threads: %d", ret);
+ goto destroy;
+ }
+ WRITE_ONCE(sh.go, true);
+ bench_stop(t, n);
+ cpus_read_unlock();
+ for (i = 0; i < n; i++) {
+ ops += t[i].ops;
+ ns += t[i].ns;
+ live += t[i].nr_pinned * LIFECYCLE_NR;
+ }
+ KUNIT_EXPECT_EQ(test, ops, (unsigned long)n * CHURN_ITER);
+ kunit_info(test, "churn pin 1/%-4u %3u thr %8llu ns/op live %6lu %s\n",
+ pin_period, n, ops ? div64_ul(ns, ops) : 0, live, impl_name[impl]);
+destroy:
+ for (i = 0; i < nr_alloc; i++) {
+ for (j = 0; j < t[i].nr_pinned; j++) {
+ if (impl == IMPL_PERCPU_COUNTER)
+ percpu_counter_destroy_many(&t[i].pinned_pc[j * LIFECYCLE_NR],
+ LIFECYCLE_NR);
+ else
+ percpu_counter_tree_destroy_many(&t[i].pinned[j * LIFECYCLE_NR],
+ LIFECYCLE_NR);
+ }
+ bench_kvfree_now(test, t[i].pinned_pc);
+ bench_kvfree_now(test, t[i].pinned);
+ }
+ bench_kvfree_now(test, t);
+ kunit_kfree(test, cpus);
+}
+
+static void hpcc_bench(struct kunit *test)
+{
+ static const unsigned int pin_periods[] = { 0, 256, 64, 16, 4 };
+ struct percpu_counter_tree probe;
+ unsigned int p;
+ int wl;
+
+ if (batch < 2 || !is_power_of_2(batch) || batch > PERCPU_COUNTER_TREE_MAX_BATCH)
+ kunit_skip(test, "invalid batch size %u", batch);
+ KUNIT_ASSERT_EQ(test, 0, percpu_counter_tree_init(&probe, batch, GFP_KERNEL));
+ kunit_info(test, "%u CPUs online, nr_cpu_ids %u\n", num_online_cpus(), nr_cpu_ids);
+ kunit_info(test, "%s batch %u, accuracy +-%lu\n", impl_name[IMPL_TREE], batch,
+ percpu_counter_tree_approximate_accuracy(&probe));
+ kunit_info(test, "%s batch %d, accuracy +-%lu\n", impl_name[IMPL_PERCPU_COUNTER],
+ percpu_counter_batch, (unsigned long)nr_cpu_ids * (percpu_counter_batch - 1));
+ percpu_counter_tree_destroy(&probe);
+ bench_lifecycle(test, false, IMPL_TREE, false);
+ bench_lifecycle(test, false, IMPL_TREE, true);
+ bench_lifecycle(test, false, IMPL_PERCPU_COUNTER, false);
+ bench_lifecycle(test, true, IMPL_TREE, false);
+ bench_lifecycle(test, true, IMPL_TREE, true);
+ bench_lifecycle(test, true, IMPL_PERCPU_COUNTER, false);
+ for (p = 0; p < ARRAY_SIZE(pin_periods); p++) {
+ bench_churn(test, false, pin_periods[p], IMPL_TREE);
+ bench_churn(test, false, pin_periods[p], IMPL_PERCPU_COUNTER);
+ bench_churn(test, true, pin_periods[p], IMPL_TREE);
+ bench_churn(test, true, pin_periods[p], IMPL_PERCPU_COUNTER);
+ }
+ for (wl = 0; wl < NR_W; wl++) {
+ bench_update(test, BENCH_SHARED, wl, IMPL_TREE);
+ bench_update(test, BENCH_SHARED, wl, IMPL_PERCPU_COUNTER);
+ bench_update(test, BENCH_PRIVATE, wl, IMPL_TREE);
+ bench_update(test, BENCH_PRIVATE, wl, IMPL_PERCPU_COUNTER);
+ bench_update(test, BENCH_MM, wl, IMPL_TREE);
+ bench_update(test, BENCH_MM, wl, IMPL_PERCPU_COUNTER);
+ bench_update(test, BENCH_SINGLE, wl, IMPL_TREE);
+ }
+}
+
+static struct kunit_case hpcc_bench_cases[] = {
+ KUNIT_CASE_SLOW(hpcc_bench),
+ {}
+};
+
+static struct kunit_suite hpcc_bench_suite = {
+ .name = "percpu_counter_tree_bench",
+ .test_cases = hpcc_bench_cases,
+};
+
+kunit_test_suite(hpcc_bench_suite);
+
+MODULE_DESCRIPTION("Benchmark for hierarchical per-CPU counters");
+MODULE_LICENSE("Dual MIT/GPL");
+MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
--
2.47.3
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2026-11-02 19:07 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-02 19:06 [RFC PATCH v23 00/10] Hierarchical Percpu Counters for RSS Mathieu Desnoyers
2026-11-02 19:06 ` [RFC PATCH v23 01/10] lib: introduce hierarchical per-cpu counters Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 02/10] lib: test " Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 03/10] mm: use hierarchical per-cpu counters for the RSS counters Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 04/10] tools/testing/hpcc: add userspace test of hierarchical per-CPU counters Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 05/10] mm: report the approximate RSS in the rss_stat tracepoint Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 06/10] lib: percpu_counter_tree: add lazy tree activation Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 07/10] mm: keep the RSS counters of single-threaded processes exact Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 08/10] lib: percpu_counter_tree: add the arity boot parameter Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 09/10] mm: add the rss_stat_batch " Mathieu Desnoyers
2026-11-02 19:07 ` [RFC PATCH v23 10/10] lib: add a benchmark of hierarchical per-cpu counters Mathieu Desnoyers
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®