Re: [PATCH v21 1/6] lib: introduce hierarchical per-cpu counters
From: Mathieu Desnoyers
Date: Fri Sep 11 2026 - 12:55:20 EST
On 2026-09-10 08:24, David Hildenbrand (Arm) wrote:
[...]
diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_counter_tree.h
new file mode 100644
index 000000000000..828c763edd4a
--- /dev/null
+++ b/include/linux/percpu_counter_tree.h
@@ -0,0 +1,367 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* SPDX-FileCopyrightText: 2025 Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx> */
+
+#ifndef _PERCPU_COUNTER_TREE_H
+#define _PERCPU_COUNTER_TREE_H
+
+#include <linux/preempt.h>
+#include <linux/atomic.h>
+#include <linux/percpu.h>
+
+#ifdef CONFIG_SMP
+
Would it be possible to document here how these values are determined?
Those come from lib/percpu_counter_tree.c:
static const struct counter_config per_nr_cpu_order_config[] = {
[0] = { .nr_items = 0, .nr_levels = 0, .n_arity_order = { 0 } },
[1] = { .nr_items = 1, .nr_levels = 1, .n_arity_order = { 1 } },
[2] = { .nr_items = 3, .nr_levels = 2, .n_arity_order = { 1, 1 } },
[3] = { .nr_items = 7, .nr_levels = 3, .n_arity_order = { 1, 1, 1 } },
[4] = { .nr_items = 7, .nr_levels = 3, .n_arity_order = { 2, 1, 1 } },
[5] = { .nr_items = 11, .nr_levels = 3, .n_arity_order = { 2, 2, 1 } },
[6] = { .nr_items = 21, .nr_levels = 3, .n_arity_order = { 2, 2, 2 } },
[7] = { .nr_items = 21, .nr_levels = 3, .n_arity_order = { 3, 2, 2 } },
[8] = { .nr_items = 37, .nr_levels = 3, .n_arity_order = { 3, 3, 2 } },
[9] = { .nr_items = 73, .nr_levels = 3, .n_arity_order = { 3, 3, 3 } },
[10] = { .nr_items = 149, .nr_levels = 4, .n_arity_order = { 3, 3, 2, 2 } },
[11] = { .nr_items = 293, .nr_levels = 4, .n_arity_order = { 3, 3, 3, 2 } },
[12] = { .nr_items = 585, .nr_levels = 4, .n_arity_order = { 3, 3, 3, 3 } },
[13] = { .nr_items = 1173, .nr_levels = 5, .n_arity_order = { 3, 3, 3, 2, 2 } },
[14] = { .nr_items = 2341, .nr_levels = 5, .n_arity_order = { 3, 3, 3, 3, 2 } },
[15] = { .nr_items = 4681, .nr_levels = 5, .n_arity_order = { 3, 3, 3, 3, 3 } },
[16] = { .nr_items = 4681, .nr_levels = 5, .n_arity_order = { 4, 3, 3, 3, 3 } },
[17] = { .nr_items = 8777, .nr_levels = 5, .n_arity_order = { 4, 4, 3, 3, 3 } },
[18] = { .nr_items = 17481, .nr_levels = 5, .n_arity_order = { 4, 4, 4, 3, 3 } },
[19] = { .nr_items = 34953, .nr_levels = 5, .n_arity_order = { 4, 4, 4, 4, 3 } },
[20] = { .nr_items = 69905, .nr_levels = 5, .n_arity_order = { 4, 4, 4, 4, 4 } },
};
Currently they need to be kept in sync manually between the public header
and the implementation, which is error prone. I should do something about that.
Note that the nr_levels and n_arity_order are only used within the implementation,
so ideally we would only have the nr_items values in the public header, not the
rest.
Those values are calculated by calculating the number of items needed for the tree
hierarchy of a given topology, excluding level 0. For instance with 8 (2^3) CPUs:
* Level 0: 0 1 2 3 4 5 6 7
* | / | / | / | /
* | / | / | / | /
* | / | / | / | /
* Level 1: 0 1 2 3
* | / | /
* | / | /
* | / | /
* Level 2: 0 1
* | /
* | /
* | /
* Level 3: 0
we need 4 items at level 1, 2 at level 2, and 1 at level 3, for a total of 7.
Without that, ...
+#if NR_CPUS == (1U << 0)
+# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 0
+#elif NR_CPUS <= (1U << 1)
+# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 1
+#elif NR_CPUS <= (1U << 2)
+# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 3
+#elif NR_CPUS <= (1U << 3)
+# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 7
+#elif NR_CPUS <= (1U << 4)
+# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 7
... I'm confused why two separate statements share the same number.
This is because both 2^3 and 2^4 have 3 levels, but the fan-out changes. We go from:
{ 1, 1, 1 }
to
{ 2, 1, 1 }
so even though we have twice the number of CPUs, the number of items is the same
because the fan-out of level 0 went from 2^1=2 to 2^2=4 (it doubled as well).
(should we simply drop the "elif NR_CPUS <= (1U << 3)" in that case?)
We should, it's indeed redundant. I kept it to have a 1 to 1 mapping with the
static const table, but if we introduce a compile-time check that they match
dropping it is not an issue.
I do wonder whether there is an (easy) way to encode this into a formula. I
assume you tried and it got too hairy :)
generating it with a formula gets quickly complex in a way that makes it
tricky to review.
Something like the trick below would allow us to make sure the values match
between the public header and the implementation, which where I think we'd
really need validation:
* Public header:
/* Number of inner nodes for a tree covering @nr_cpus CPUs, -1 if unsupported. */
#define __PERCPU_COUNTER_TREE_NR_ITEMS(nr_cpus) \
((nr_cpus) <= (1U << 0) ? 0 : \
(nr_cpus) <= (1U << 1) ? 1 : \
(nr_cpus) <= (1U << 2) ? 3 : \
(nr_cpus) <= (1U << 4) ? 7 : \
(nr_cpus) <= (1U << 5) ? 11 : \
(nr_cpus) <= (1U << 7) ? 21 : \
(nr_cpus) <= (1U << 8) ? 37 : \
(nr_cpus) <= (1U << 9) ? 73 : \
(nr_cpus) <= (1U << 10) ? 149 : \
(nr_cpus) <= (1U << 11) ? 293 : \
(nr_cpus) <= (1U << 12) ? 585 : \
(nr_cpus) <= (1U << 13) ? 1173 : \
(nr_cpus) <= (1U << 14) ? 2341 : \
(nr_cpus) <= (1U << 16) ? 4681 : \
(nr_cpus) <= (1U << 17) ? 8777 : \
(nr_cpus) <= (1U << 18) ? 17481 : \
(nr_cpus) <= (1U << 19) ? 34953 : \
(nr_cpus) <= (1U << 20) ? 69905 : -1)
#define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS \
__PERCPU_COUNTER_TREE_NR_ITEMS(NR_CPUS)
#if PERCPU_COUNTER_TREE_STATIC_NR_ITEMS < 0
# error "Unsupported number of CPUs."
#endif
* Implementation:
/*
* X(order, nr_levels, ARITY(arity order per level, leaf level first))
* Row "order" covers nr_cpus <= 2^order. nr_items comes from the public
* header and is checked against nr_levels and ARITY() below.
*/
#define PERCPU_COUNTER_TREE_CONFIGS(X) \
X( 0, 0, ARITY()) \
X( 1, 1, ARITY(1)) \
X( 2, 2, ARITY(1, 1)) \
X( 3, 3, ARITY(1, 1, 1)) \
X( 4, 3, ARITY(2, 1, 1)) \
X( 5, 3, ARITY(2, 2, 1)) \
X( 6, 3, ARITY(2, 2, 2)) \
X( 7, 3, ARITY(3, 2, 2)) \
X( 8, 3, ARITY(3, 3, 2)) \
X( 9, 3, ARITY(3, 3, 3)) \
X(10, 4, ARITY(3, 3, 2, 2)) \
X(11, 4, ARITY(3, 3, 3, 2)) \
X(12, 4, ARITY(3, 3, 3, 3)) \
X(13, 5, ARITY(3, 3, 3, 2, 2)) \
X(14, 5, ARITY(3, 3, 3, 3, 2)) \
X(15, 5, ARITY(3, 3, 3, 3, 3)) \
X(16, 5, ARITY(4, 3, 3, 3, 3)) \
X(17, 5, ARITY(4, 4, 3, 3, 3)) \
X(18, 5, ARITY(4, 4, 4, 3, 3)) \
X(19, 5, ARITY(4, 4, 4, 4, 3)) \
X(20, 5, ARITY(4, 4, 4, 4, 4))
/*
* ARITY() is never defined: consumers paste a prefix onto it, so that
* __PCT_LIST_##arity turns ARITY(3, 2, 2) into __PCT_LIST_ARITY(3, 2, 2).
*/
#define __PCT_LIST_ARITY(...) __VA_ARGS__
/* Pad to COUNTER_TREE_MAX_LEVELS (5) entries; "+ 0" keeps ARITY() valid. */
#define __PCT_PAD_ARITY(...) __PCT_PAD_(__VA_ARGS__ + 0, 0, 0, 0, 0, 0)
#define __PCT_PAD_(a0, a1, a2, a3, a4, ...) a0, a1, a2, a3, a4
#define __PCT_NR_ITEMS(order) __PERCPU_COUNTER_TREE_NR_ITEMS(1U << (order))
#define __PCT_CONFIG(order, levels, arity) \
[order] = { .nr_items = __PCT_NR_ITEMS(order), \
.nr_levels = (levels), \
.n_arity_order = { __PCT_LIST_##arity } },
static const struct counter_config per_nr_cpu_order_config[] = {
PERCPU_COUNTER_TREE_CONFIGS(__PCT_CONFIG)
};
#define __PCT_CALL(m, ...) m(__VA_ARGS__)
#define __PCT_SUM(a0, a1, a2, a3, a4) (a0 + a1 + a2 + a3 + a4)
/* Inner nodes at level @j (1 = parents of the per-CPU counters). */
#define __PCT_LVL(j, order, levels, sum) \
((j) <= (levels) ? 1U << ((order) - (sum)) : 0U)
#define __PCT_ITEMS(order, levels, a0, a1, a2, a3, a4) \
(__PCT_LVL(1, order, levels, a0) + \
__PCT_LVL(2, order, levels, a0 + a1) + \
__PCT_LVL(3, order, levels, a0 + a1 + a2) + \
__PCT_LVL(4, order, levels, a0 + a1 + a2 + a3) + \
__PCT_LVL(5, order, levels, a0 + a1 + a2 + a3 + a4))
#define __PCT_CHECK_ROW(order, levels, arity) \
static_assert((levels) <= COUNTER_TREE_MAX_LEVELS, \
"percpu_counter_tree: order " #order ": too many levels"); \
static_assert(__PCT_CALL(__PCT_SUM, __PCT_PAD_##arity) == (order), \
"percpu_counter_tree: order " #order ": arity orders do not sum to order"); \
static_assert(__PCT_CALL(__PCT_ITEMS, order, levels, \
__PCT_PAD_##arity) == __PCT_NR_ITEMS(order), \
"percpu_counter_tree: order " #order ": nr_items does not match levels/arities"); \
static_assert(__PERCPU_COUNTER_TREE_NR_ITEMS((1U << (order)) / 2) <= \
__PCT_NR_ITEMS(order), \
"percpu_counter_tree: order " #order ": nr_items not monotonic");
PERCPU_COUNTER_TREE_CONFIGS(__PCT_CHECK_ROW)
One alternative would be to derive the public header nr items from a formula, e.g.:
enum {
__PCT_ORDER = order_base_2(NR_CPUS),
/* at most 8-ary per level while that fits in 3..5 levels */
__PCT_LEVELS = MIN(5, MAX(MIN(__PCT_ORDER, 3),
DIV_ROUND_UP(__PCT_ORDER, 3))),
__PCT_DIV = MAX(__PCT_LEVELS, 1), /* avoid /0 for 1 CPU */
__PCT_BASE = __PCT_ORDER / __PCT_DIV, /* arity order per level */
__PCT_EXTRA = __PCT_ORDER % __PCT_DIV, /* leaf-side levels with +1 */
};
/* Number of inner nodes at depth @k (root is depth 0). */
#define __PCT_NODES(k) \
((k) < __PCT_LEVELS ? \
1U << ((k) * __PCT_BASE + \
MAX(0, (k) - (__PCT_LEVELS - __PCT_EXTRA))) : 0)
#define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS \
(__PCT_NODES(0) + __PCT_NODES(1) + __PCT_NODES(2) + \
__PCT_NODES(3) + __PCT_NODES(4))
static_assert(NR_CPUS <= (1U << 20), "Unsupported number of CPUs.");
It's more compact, but it's also less straightforward to understand how many
items we end up with for a given order.
Any preference ?
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com