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

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

On 2026-09-11 12:30, Mathieu Desnoyers wrote:
> 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?

Do you consider this a blocker for integrating the series into mm
for testing ? This has been repeatedly postponed from rc1 to rc1 for
many cycles now.

Thanks,

Mathieu

> 
> 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