Re: [PATCH v21 1/6] lib: introduce hierarchical per-cpu counters

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

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@efficios.com> */
>> +
>> +#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