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/[email protected]
Link:
https://lore.kernel.org/lkml/[email protected]/
# [1]
Link:
https://lkml.kernel.org/r/[email protected]
Signed-off-by: Mathieu Desnoyers <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>
Cc: Steven Rostedt <[email protected]>
Cc: Masami Hiramatsu <[email protected]>
Cc: Dennis Zhou <[email protected]>
Cc: Tejun Heo <[email protected]>
Cc: Christoph Lameter <[email protected]>
Cc: Martin Liu <[email protected]>
Cc: David Rientjes <[email protected]>
Cc: [email protected]
Cc: Shakeel Butt <[email protected]>
Cc: SeongJae Park <[email protected]>
Cc: Michal Hocko <[email protected]>
Cc: Johannes Weiner <[email protected]>
Cc: Sweet Tea Dorminy <[email protected]>
Cc: Lorenzo Stoakes <[email protected]>
Cc: Liam R. Howlett <[email protected]>
Cc: Mike Rapoport <[email protected]>
Cc: Suren Baghdasaryan <[email protected]>
Cc: Vlastimil Babka <[email protected]>
Cc: Christian Brauner <[email protected]>
Cc: Wei Yang <[email protected]>
Cc: David Hildenbrand <[email protected]>
Cc: Miaohe Lin <[email protected]>
Cc: Al Viro <[email protected]>
Cc: Yu Zhao <[email protected]>
Cc: Roman Gushchin <[email protected]>
Cc: Mateusz Guzik <[email protected]>
Cc: Matthew Wilcox <[email protected]>
Cc: Baolin Wang <[email protected]>
Cc: Aboorva Devarajan <[email protected]>
Cc: David Carlier <[email protected]>
Cc: Josh Law <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: [email protected]
---
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: [email protected]
S: Maintained
F: drivers/hid/hid-logitech-hidpp.c
+HIERARCHICAL PER-CPU COUNTERS (HPCC)
+M: Mathieu Desnoyers <[email protected]>
+L: [email protected]
+L: [email protected]
+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 <[email protected]>
M: Frederic Weisbecker <[email protected]>
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
<[email protected]> */
+
+#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
<[email protected]>
+
+/*
+ * 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
