Skip to contentSkip to conversation

Hierarchical Percpu Counters for RSS

PATCH Superseded Mathieu Desnoyers 3 participants 12 messages Sep 1 – Sep 15

Subsystems (8)

v21 of 25 Superseded Latest is v25 →

lore
Share & tools
lore

Mathieu Desnoyers

author reviewer
#0 lore raw

v21 cover Hierarchical Percpu Counters for RSS

Hi Andrew,

Here is the hierarchical percpu counters for RSS accounting series rebased on top of v7.3-rc1. It includes small bootup fixes which were needed to fix bootup sequence on specific architectures, and a rename of the test config option to include "KUNIT_".

This aims at replacing the prior version of the series you had in mm.

As a reminder, the goal here is to provide more precise RSS counters through /proc. A future step would be to also use these counters to speed up the OOM killer task selection when OOM is triggered by memcg. In whole-machine OOM situations, latency introduced by the OOM killer task selection may not be too much of an issue, but for memcg, where cgroups may routinely depend on the OOM killer, the acceptable latency tradeoff is quite different.

Thanks,

Mathieu

Mathieu Desnoyers (6):
lib: introduce hierarchical per-cpu counters
lib: test hierarchical per-cpu counters
mm: improve RSS counter approximation accuracy for proc interfaces
mm: reorder mm_struct flexible array to place mm_cpumask first
init: move percpu_counter_tree_subsystem_init() earlier in boot
lib: inline percpu_counter_tree_items_size with boot-safety sentinel

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 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]>
 .../core-api/percpu-counter-tree.rst          |  75 ++
 include/linux/mm.h                            |  20 +-
 include/linux/mm_types.h                      |  65 +-
 include/linux/percpu_counter_tree.h           | 387 ++++++++++
 include/trace/events/kmem.h                   |   2 +-
 init/main.c                                   |   2 +
 kernel/fork.c                                 |  24 +-
 lib/Kconfig                                   |  12 +
 lib/Makefile                                  |   1 +
 lib/percpu_counter_tree.c                     | 694 ++++++++++++++++++
 lib/tests/Makefile                            |   2 +
 lib/tests/percpu_counter_tree_kunit.c         | 399 ++++++++++
 12 files changed, 1651 insertions(+), 32 deletions(-)
 create mode 100644 Documentation/core-api/percpu-counter-tree.rst
 create mode 100644 include/linux/percpu_counter_tree.h
 create mode 100644 lib/percpu_counter_tree.c
 create mode 100644 lib/tests/percpu_counter_tree_kunit.c
Signature · 1 line
2.43.0
author reviewer
#1 lore raw

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

This series introduces the hierarchical tree counter (hpcc) to increase accuracy of approximated RSS counters exposed through proc interfaces.

With a test program hopping across CPUs doing frequent mmap/munmap operations, the upstream implementation approximation reaches a 1GB delta from the precise value after a few minutes, compared to a 80MB delta with the hierarchical counter. The hierarchical counter provides a guaranteed maximum approximation inaccuracy of 192MB on that hardware topology.

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

Its goals are twofold:

- Improve the accuracy of the approximated RSS counter values returned by proc interfaces [1],
- Reduce the latency of the OOM killer on large many-core systems.

* Design

The hierarchical per-CPU counters propagate a sum approximation through a N-way tree. When reaching the batch size, the carry is propagated through a binary tree which consists of logN(nr_cpu_ids) levels. The batch size for each level is twice the batch size of the prior level.

Example propagation diagram with 8 cpus through a binary tree:

Level 0:  0    1    2    3    4    5    6    7
          |   /     |   /     |   /     |   /
          |  /      |  /      |  /      |  /
          | /       | /       | /       | /
Level 1:  0         1         2         3
          |       /           |       /
          |    /              |    /
          | /                 | /
Level 2:  0                   1
          |               /
          |         /
          |   /
Level 3:  0

For a binary tree, the maximum inaccuracy is bound by:
batch_size * log2(nr_cpu_ids) * nr_cpu_ids
which evolves with O(n*log(n)) as the number of CPUs increases.

For a N-way tree, the maximum inaccuracy can be pre-calculated based on the the N-arity of each level and the batch size.

* Memory Use

The most important parts in terms of memory use are the per-cpu counters and the tree items which propagate the carry.

In the proposed implementation, the per-cpu counters are allocated within per-cpu data structures, so they end up using:

nr_possible_cpus * sizeof(unsigned long)

This is in addition to the tree items. The size of those items is defined by the per_nr_cpu_order_config table "nr_items" field. Each item is aligned on cacheline size (typically 64 bytes) to minimize false sharing.

Here is the footprint for a few nr_cpu_ids on a 64-bit arch:

nr_cpu_ids percpu counters (bytes) nr_items items size (bytes) total (bytes)

    2               16                     1                 64                    80
    4               32                     3                192                   224
    8               64                     7                448                   512
   64               512                   21               1344                  1856
  128              1024                   21               1344                  2368
  256              2048                   37               2368                  4416
  512              4096                   73               4672                  8768

There are of course various trade offs we can make here. We can:

* Increase the n-arity of the intermediate items to shrink the nr_items required for a given nr_cpus. This will increase contention of carry propagation across more cores.

* Remove cacheline alignment of intermediate tree items. This will shrink the memory needed for tree items, but will increase false sharing.

* Represent intermediate tree items on a byte rather than long. This further reduces the memory required for intermediate tree items, but further increases false sharing.

* Represent per-cpu counters on bytes rather than long. This makes the "sum" operation trickier, because it needs to iterate on the intermediate carry propagation nodes as well and synchronize with ongoing "tree add" operations. It further reduces memory use.

* Implement a custom strided allocator for intermediate items carry propagation bytes. This shares cachelines across different tree instances, keeping good locality. This ensures that all accesses from a given location in the machine topology touch the same cacheline for the various tree instances. This adds complexity, but provides compactness as well as minimal false-sharing.

Compared to this, the upstream percpu counters use a 32-bit integer per-cpu (4 bytes), and accumulate within a 64-bit global value.

So there is an extra memory footprint added by the current hpcc implementation, but if it's an issue we have various options to consider to reduce its footprint.

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 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]>
---
 .../core-api/percpu-counter-tree.rst          |  75 ++
 include/linux/mm_types.h                      |   4 +-
 include/linux/percpu_counter_tree.h           | 367 +++++++++
 init/main.c                                   |   2 +
 lib/Makefile                                  |   1 +
 lib/percpu_counter_tree.c                     | 702 ++++++++++++++++++
 6 files changed, 1149 insertions(+), 2 deletions(-)
 create mode 100644 Documentation/core-api/percpu-counter-tree.rst
 create mode 100644 include/linux/percpu_counter_tree.h
 create mode 100644 lib/percpu_counter_tree.c
Documentation/core-api/percpu-counter-tree.rst new file +75 -0
new file mode 100644
index 000000000000..196da056e7b4
@@ -0,0 +1,75 @@
+========================================
+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 counter, 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 herarchical per-cpu counters are organized as a tree with the tree
+root at the bottom (last level) and the first level of the tree
+consisting of per-cpu counters.
+
+The intermediate tree levels contain carry propagation counters. When
+reaching a threshold (batch size), the carry is propagated down the
+tree.
+
+This allows reading an approximated value at the root, which has a
+bounded accuracy (minimum/maximum possible precise sum range) determined
+by the tree topology.
+
+Use Cases
+=========
+
+Use cases HPCC is meant to handle invove 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 sorting picking a maximum/minimunm 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.
+
+Functions and structures
+========================
+
+.. kernel-doc:: include/linux/percpu_counter_tree.h
+.. kernel-doc:: lib/percpu_counter_tree.c
include/linux/mm_types.h +2 -2
index 6d815f6440c9..dff5fd1c1b06 100644
@@ -1462,8 +1462,8 @@ static inline void __mm_flags_set_mask_bits_word(struct mm_struct *mm,
 			 MT_FLAGS_USE_RCU)
 extern struct mm_struct init_mm;
 
-#define MM_STRUCT_FLEXIBLE_ARRAY_INIT				\
-{								\
+#define MM_STRUCT_FLEXIBLE_ARRAY_INIT									\
+{													\
 	[0 ... sizeof(cpumask_t) + MM_CID_STATIC_SIZE - 1] = 0	\
 }
 
include/linux/percpu_counter_tree.h new file +367 -0

367 lines not on this page · raw message

init/main.c +2 -0
index 2613d3f9b3ce..eda2170bb21f 100644
@@ -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>
@@ -1041,6 +1042,7 @@ void start_kernel(void)
 	vfs_caches_init_early();
 	sort_main_extable();
 	trap_init();
+	percpu_counter_tree_subsystem_init();
 	mm_core_init();
 	maple_tree_init();
 	poking_init();
lib/Makefile +1 -0
index dfab958327c5..f1d0cb831630 100644
@@ -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
 
lib/percpu_counter_tree.c new file +702 -0

702 lines not on this page · raw message

Signature · 1 line
2.43.0
#2 lore raw

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

Quoted 269 lines · Mathieu Desnoyers

This series introduces the hierarchical tree counter (hpcc) to increase accuracy of approximated RSS counters exposed through proc interfaces.

With a test program hopping across CPUs doing frequent mmap/munmap operations, the upstream implementation approximation reaches a 1GB delta from the precise value after a few minutes, compared to a 80MB delta with the hierarchical counter. The hierarchical counter provides a guaranteed maximum approximation inaccuracy of 192MB on that hardware topology.

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

Its goals are twofold:

- Improve the accuracy of the approximated RSS counter values returned by proc interfaces [1],
- Reduce the latency of the OOM killer on large many-core systems.

* Design

The hierarchical per-CPU counters propagate a sum approximation through a N-way tree. When reaching the batch size, the carry is propagated through a binary tree which consists of logN(nr_cpu_ids) levels. The batch size for each level is twice the batch size of the prior level.

Example propagation diagram with 8 cpus through a binary tree:

Level 0:  0    1    2    3    4    5    6    7
          |   /     |   /     |   /     |   /
          |  /      |  /      |  /      |  /
          | /       | /       | /       | /
Level 1:  0         1         2         3
          |       /           |       /
          |    /              |    /
          | /                 | /
Level 2:  0                   1
          |               /
          |         /
          |   /
Level 3:  0

For a binary tree, the maximum inaccuracy is bound by:
batch_size * log2(nr_cpu_ids) * nr_cpu_ids
which evolves with O(n*log(n)) as the number of CPUs increases.

For a N-way tree, the maximum inaccuracy can be pre-calculated based on the the N-arity of each level and the batch size.

* Memory Use

The most important parts in terms of memory use are the per-cpu counters and the tree items which propagate the carry.

In the proposed implementation, the per-cpu counters are allocated within per-cpu data structures, so they end up using:

nr_possible_cpus * sizeof(unsigned long)

This is in addition to the tree items. The size of those items is defined by the per_nr_cpu_order_config table "nr_items" field. Each item is aligned on cacheline size (typically 64 bytes) to minimize false sharing.

Here is the footprint for a few nr_cpu_ids on a 64-bit arch:

nr_cpu_ids percpu counters (bytes) nr_items items size (bytes) total (bytes)

    2               16                     1                 64                    80
    4               32                     3                192                   224
    8               64                     7                448                   512
   64               512                   21               1344                  1856
  128              1024                   21               1344                  2368
  256              2048                   37               2368                  4416
  512              4096                   73               4672                  8768

There are of course various trade offs we can make here. We can:

* Increase the n-arity of the intermediate items to shrink the nr_items required for a given nr_cpus. This will increase contention of carry propagation across more cores.

* Remove cacheline alignment of intermediate tree items. This will shrink the memory needed for tree items, but will increase false sharing.

* Represent intermediate tree items on a byte rather than long. This further reduces the memory required for intermediate tree items, but further increases false sharing.

* Represent per-cpu counters on bytes rather than long. This makes the "sum" operation trickier, because it needs to iterate on the intermediate carry propagation nodes as well and synchronize with ongoing "tree add" operations. It further reduces memory use.

* Implement a custom strided allocator for intermediate items carry propagation bytes. This shares cachelines across different tree instances, keeping good locality. This ensures that all accesses from a given location in the machine topology touch the same cacheline for the various tree instances. This adds complexity, but provides compactness as well as minimal false-sharing.

Compared to this, the upstream percpu counters use a 32-bit integer per-cpu (4 bytes), and accumulate within a 64-bit global value.

So there is an extra memory footprint added by the current hpcc implementation, but if it's an issue we have various options to consider to reduce its footprint.

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 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]>
---
 .../core-api/percpu-counter-tree.rst          |  75 ++
 include/linux/mm_types.h                      |   4 +-
 include/linux/percpu_counter_tree.h           | 367 +++++++++
 init/main.c                                   |   2 +
 lib/Makefile                                  |   1 +
 lib/percpu_counter_tree.c                     | 702 ++++++++++++++++++
 6 files changed, 1149 insertions(+), 2 deletions(-)
 create mode 100644 Documentation/core-api/percpu-counter-tree.rst
 create mode 100644 include/linux/percpu_counter_tree.h
 create mode 100644 lib/percpu_counter_tree.c
Documentation/core-api/percpu-counter-tree.rst new file +75 -0
new file mode 100644
index 000000000000..196da056e7b4
@@ -0,0 +1,75 @@
+========================================
+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 counter, 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 herarchical per-cpu counters are organized as a tree with the tree
+root at the bottom (last level) and the first level of the tree
+consisting of per-cpu counters.
+
+The intermediate tree levels contain carry propagation counters. When
+reaching a threshold (batch size), the carry is propagated down the
+tree.
+
+This allows reading an approximated value at the root, which has a
+bounded accuracy (minimum/maximum possible precise sum range) determined
+by the tree topology.
+
+Use Cases
+=========
+
+Use cases HPCC is meant to handle invove 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 sorting picking a maximum/minimunm 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.
+
+Functions and structures
+========================
+
+.. kernel-doc:: include/linux/percpu_counter_tree.h
+.. kernel-doc:: lib/percpu_counter_tree.c
include/linux/mm_types.h +2 -2
index 6d815f6440c9..dff5fd1c1b06 100644
@@ -1462,8 +1462,8 @@ static inline void __mm_flags_set_mask_bits_word(struct mm_struct *mm,
 			 MT_FLAGS_USE_RCU)
 extern struct mm_struct init_mm;
 
-#define MM_STRUCT_FLEXIBLE_ARRAY_INIT				\
-{								\
+#define MM_STRUCT_FLEXIBLE_ARRAY_INIT									\
+{													\
 	[0 ... sizeof(cpumask_t) + MM_CID_STATIC_SIZE - 1] = 0	\
 }
 
include/linux/percpu_counter_tree.h new file +2 -0
new file mode 100644
index 000000000000..828c763edd4a
@@ -0,0 +1,367 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* SPDX-FileCopyrightText: 2025 Mathieu Desnoyers <[email protected]> */

include/linux/percpu_counter_tree.h line 12

Quoted 10 lines
include/linux/percpu_counter_tree.h new file +10 -0
+
+#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?

Without that, ...

include/linux/percpu_counter_tree.h line 22

Quoted 10 lines
include/linux/percpu_counter_tree.h new file +10 -0
+#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.

(should we simply drop the "elif NR_CPUS <= (1U << 3)" in that case?)

I do wonder whether there is an (easy) way to encode this into a formula. I assume you tried and it got too hairy :)

Signature · 3 lines
Cheers,

David
author reviewer
#3 lore raw

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

On 2026-09-10 08:24, David Hildenbrand (Arm) wrote:
[...]

Quoted 12 lines
Quoted 12 lines
include/linux/percpu_counter_tree.h new file +6 -0
new file mode 100644
index 000000000000..828c763edd4a
@@ -0,0 +1,367 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* SPDX-FileCopyrightText: 2025 Mathieu Desnoyers <[email protected]> */
+
+#ifndef _PERCPU_COUNTER_TREE_H
+#define _PERCPU_COUNTER_TREE_H
+
Quoted 8 lines

include/linux/percpu_counter_tree.h line 12

Quoted 6 lines
include/linux/percpu_counter_tree.h new file +6 -0
+#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.

Quoted 15 lines

Without that, ...

include/linux/percpu_counter_tree.h line 22

Quoted 10 lines
include/linux/percpu_counter_tree.h new file +10 -0
+#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).

Quoted 1 line

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

Quoted 2 lines

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author reviewer
#4 lore raw

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

Quoted 23 lines · Mathieu Desnoyers

On 2026-09-10 08:24, David Hildenbrand (Arm) wrote:
[...]

Quoted 21 lines
Quoted 9 lines
include/linux/percpu_counter_tree.h new file +2 -0
new file mode 100644
index 000000000000..828c763edd4a
@@ -0,0 +1,367 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR MIT */
+/* SPDX-FileCopyrightText: 2025 Mathieu Desnoyers 

<[email protected]> */

include/linux/percpu_counter_tree.h line 12

Quoted 10 lines
include/linux/percpu_counter_tree.h new file +10 -0
+
+#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

Quoted 262 lines

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.

Quoted 15 lines

Without that, ...

include/linux/percpu_counter_tree.h line 22

Quoted 10 lines
include/linux/percpu_counter_tree.h new file +10 -0
+#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).

Quoted 1 line

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

Quoted 2 lines

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author reviewer
#5 lore raw

PATCH v21 2/6 lib: test hierarchical per-cpu counters

In reply to Mathieu Desnoyers

Introduce Kunit tests for hierarchical per-cpu counters.

Keep track of two sets of hierarchical counters, each meant to have the same precise sum at any time, but distributed differently across the topology.

Keep track of an atomic counter along with each hierarchical counter, for sum validation.

Those tests cover:

- Single-threaded (no concurrency) updates.
- Concurrent updates of counters from various CPUs.

Perform the following validations:

- Compare the precise sum of counters with the sum tracked by an atomic counter.
- Compare the precise sum of two sets of hierarchical counters.
- Approximated comparison of hierarchical counter with atomic counter.
- Approximated comparison of two sets of hierarchical counters.
- Validate the bounds of approximation ranges.

Run with the following .kunit/.kunitconfig:

CONFIG_KUNIT=y
CONFIG_SMP=y
CONFIG_PREEMPT=y
CONFIG_NR_CPUS=32
CONFIG_HOTPLUG_CPU=y
CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST=y

With the following execution (to use SMP):

./tools/testing/kunit/kunit.py run --arch=x86_64 --qemu_args="-smp 12"

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

---
Changes since v19:
- Rename config option to PERCPU_COUNTER_TREE_KUNIT_TEST.

---
 lib/Kconfig                           |  12 +
 lib/tests/Makefile                    |   2 +
 lib/tests/percpu_counter_tree_kunit.c | 399 ++++++++++++++++++++++++++
 3 files changed, 413 insertions(+)
 create mode 100644 lib/tests/percpu_counter_tree_kunit.c
lib/Kconfig +12 -0
index 4e6b34c3346d..c0524258b205 100644
@@ -41,6 +41,18 @@ config PACKING_KUNIT_TEST
 
 	  When in doubt, say N.
 
+config PERCPU_COUNTER_TREE_KUNIT_TEST
+	tristate "KUnit tests for hierarchical per-cpu counters" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  This builds Kunit tests for the hierarchical per-cpu counters.
+
+	  For more information on KUnit and unit tests in general,
+	  please refer to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+	  When in doubt, say N.
+
 config BITREVERSE
 	tristate
 	select GENERIC_BITREVERSE if !HAVE_ARCH_BITREVERSE
lib/tests/Makefile +2 -0
index 3cac3b63a752..051e73705977 100644
@@ -58,4 +58,6 @@ obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o
 obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
 obj-$(CONFIG_UUID_KUNIT_TEST) += uuid_kunit.o
 
+obj-$(CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST) += percpu_counter_tree_kunit.o
+
 obj-$(CONFIG_TEST_RUNTIME_MODULE)		+= module/
lib/tests/percpu_counter_tree_kunit.c new file +399 -0

399 lines not on this page · raw message

Signature · 1 line
2.43.0
author reviewer
#6 lore raw

PATCH v21 3/6 mm: improve RSS counter approximation accuracy for proc interfaces

In reply to Mathieu Desnoyers

Use hierarchical per-cpu counters for RSS tracking to improve the accuracy of per-mm RSS sum approximation on large many-core systems [1]. This improves the accuracy of the RSS values returned by proc interfaces.

Here is a (possibly incomplete) list of the prior approaches that were used or proposed, along with their downside:

1) Per-thread rss tracking: large error on many-thread processes.

2) Per-CPU counters: up to 12% slower for short-lived processes and 9% increased system time in make test workloads [1]. Moreover, the inaccuracy increases with O(n^2) with the number of CPUs.

3) Per-NUMA-node counters: requires atomics on fast-path (overhead), error is high with systems that have lots of NUMA nodes (32 times the number of NUMA nodes).

4) Use a percise per-cpu counter sum for each counter value query:
Requires iteration on each possible CPUs for each sum, which adds overhead on large many-core systems running many processes.

The approach proposed here is to replace the per-cpu counters by the hierarchical per-cpu counters, which bounds the inaccuracy based on the system topology with O(N*logN).

* Testing results:

Test hardware: 2 sockets AMD EPYC 9654 96-Core Processor (384 logical CPUs total)

Methodology:

Comparing the current upstream implementation with the hierarchical counters is done by keeping both implementations wired up in parallel, and running a single-process, single-threaded program which hops randomly across CPUs in the system, calling mmap(2) and munmap(2) on random CPUs, keeping track of an array of allocated mappings, randomly choosing entries to either map or unmap.

get_mm_counter() is instrumented to compare the upstream counter approximation to the precise value, and print the delta when going over a given threshold. The delta of the hierarchical counter approximation to the precise value is also printed for comparison.

After a few minutes running this test, the upstream implementation counter approximation reaches a 1GB delta from the precise value, compared to 80MB delta with the hierarchical counter. The hierarchical counter provides a guaranteed maximum approximation inaccuracy of 192MB on that hardware topology.

* Fast path implementation comparison

The new inline percpu_counter_tree_add() uses a this_cpu_add_return() for the fast path (under a certain allocation size threshold). Above that, it calls a slow path which "trickles up" the carry to upper level counters with atomic_add_return.

In comparison, the upstream counters implementation calls percpu_counter_add_batch which uses this_cpu_try_cmpxchg() on the fast path, and does a raw_spin_lock_irqsave above a certain threshold.

The hierarchical implementation is therefore expected to have less contention on mid-sized allocations than the upstream counters because the atomic counters tracking those bits are only shared across nearby CPUs. In comparison, the upstream counters immediately use a global spinlock when reaching the threshold.

* Benchmarks

Using will-it-scale page_fault1 benchmarks to compare the upstream counters to the hierarchical counters. This is done with hyperthreading disabled. The speedup is within the standard deviation of the upstream runs, so the overhead is not significant.

upstream hierarchical speedup

page_fault1_processes -s 100 -t 1           614783         615558      +0.1%
page_fault1_threads -s 100 -t 1             612788         612447      -0.1%
page_fault1_processes -s 100 -t 96        37994977       37932035      -0.2%
page_fault1_threads -s 100 -t 96           2484130        2504860      +0.8%
page_fault1_processes -s 100 -t 192       71262917       71118830      -0.2%
page_fault1_threads -s 100 -t 192          2446437        2469296      +0.1%

* Memory Use

The most important parts in terms of memory use are the per-cpu counters and the tree items which propagate the carry.

In the proposed implementation, the per-cpu counters are allocated within per-cpu data structures, so they end up using:

nr_possible_cpus * sizeof(unsigned long)

This is in addition to the tree items. The size of those items is defined by the per_nr_cpu_order_config table "nr_items" field. Each item is aligned on cacheline size (typically 64 bytes) to minimize false sharing.

Here is the footprint for a few nr_cpu_ids on a 64-bit arch:

nr_cpu_ids percpu counters (bytes) nr_items items size (bytes) total (bytes)

    2               16                     1                 64                    80
    4               32                     3                192                   224
    8               64                     7                448                   512
   64               512                   21               1344                  1856
  128              1024                   21               1344                  2368
  256              2048                   37               2368                  4416
  512              4096                   73               4672                  8768

Compared to this, the upstream percpu counters use a 32-bit integer per-cpu (4 bytes), and accumulate within a 64-bit global value.

So there is an extra memory footprint added by the current hpcc implementation, but if it's an issue we have various options to consider to reduce its footprint.

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 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]>
---
 include/linux/mm.h          | 19 ++++++++++----
 include/linux/mm_types.h    | 50 +++++++++++++++++++++++++++----------
 include/trace/events/kmem.h |  2 +-
 kernel/fork.c               | 22 +++++++++-------
 4 files changed, 65 insertions(+), 28 deletions(-)
include/linux/mm.h +14 -5
index dd09c438fa23..7dd6fdda9bc8 100644
@@ -3447,38 +3447,47 @@ static inline bool get_user_page_fast_only(unsigned long addr,
 {
 	return get_user_pages_fast_only(addr, 1, gup_flags, pagep) == 1;
 }
+
+static inline struct percpu_counter_tree_level_item *get_rss_stat_items(struct mm_struct *mm)
+{
+	unsigned long ptr = (unsigned long)mm;
+
+	ptr += offsetof(struct mm_struct, flexible_array);
+	return (struct percpu_counter_tree_level_item *)ptr;
+}
+
 /*
  * per-process(per-mm_struct) statistics.
  */
 static inline unsigned long get_mm_counter(struct mm_struct *mm, int member)
 {
-	return percpu_counter_read_positive(&mm->rss_stat[member]);
+	return percpu_counter_tree_approximate_sum_positive(&mm->rss_stat[member]);
 }
 
 static inline unsigned long get_mm_counter_sum(struct mm_struct *mm, int member)
 {
-	return percpu_counter_sum_positive(&mm->rss_stat[member]);
+	return percpu_counter_tree_precise_sum_positive(&mm->rss_stat[member]);
 }
 
 void mm_trace_rss_stat(struct mm_struct *mm, int member);
 
 static inline void add_mm_counter(struct mm_struct *mm, int member, long value)
 {
-	percpu_counter_add(&mm->rss_stat[member], value);
+	percpu_counter_tree_add(&mm->rss_stat[member], value);
 
 	mm_trace_rss_stat(mm, member);
 }
 
 static inline void inc_mm_counter(struct mm_struct *mm, int member)
 {
-	percpu_counter_inc(&mm->rss_stat[member]);
+	percpu_counter_tree_add(&mm->rss_stat[member], 1);
 
 	mm_trace_rss_stat(mm, member);
 }
 
 static inline void dec_mm_counter(struct mm_struct *mm, int member)
 {
-	percpu_counter_dec(&mm->rss_stat[member]);
+	percpu_counter_tree_add(&mm->rss_stat[member], -1);
 
 	mm_trace_rss_stat(mm, member);
 }
include/linux/mm_types.h +37 -13

95 lines not on this page · raw message

include/trace/events/kmem.h +1 -1
index cd7920c81f85..290ccb9fd25d 100644
@@ -448,7 +448,7 @@ TRACE_EVENT(rss_stat,
 		 */
 		__entry->curr = current->mm == mm && !(current->flags & PF_KTHREAD);
 		__entry->member = member;
-		__entry->size = (percpu_counter_sum_positive(&mm->rss_stat[member])
+		__entry->size = (percpu_counter_tree_approximate_sum_positive(&mm->rss_stat[member])
 							    << PAGE_SHIFT);
 	),
 
kernel/fork.c +13 -9
index 416758c8a3d4..5bad7a24d186 100644
@@ -137,6 +137,11 @@
  */
 #define MAX_THREADS FUTEX_TID_MASK
 
+/*
+ * Batch size of rss stat approximation
+ */
+#define RSS_STAT_BATCH_SIZE	32
+
 /*
  * Protected counters by write_lock_irq(&tasklist_lock)
  */
@@ -633,14 +638,12 @@ static void check_mm(struct mm_struct *mm)
 			 "Please make sure 'struct resident_page_types[]' is updated as well");
 
 	for (i = 0; i < NR_MM_COUNTERS; i++) {
-		long x = percpu_counter_sum(&mm->rss_stat[i]);
-
-		if (unlikely(x)) {
+		if (unlikely(percpu_counter_tree_precise_compare_value(&mm->rss_stat[i], 0) != 0))
 			pr_alert("BUG: Bad rss-counter state mm:%p type:%s val:%ld Comm:%s Pid:%d\n",
-				 mm, resident_page_types[i], x,
+				 mm, resident_page_types[i],
+				 percpu_counter_tree_precise_sum(&mm->rss_stat[i]),
 				 current->comm,
 				 task_pid_nr(current));
-		}
 	}
 
 	if (mm_pgtables_bytes(mm))
@@ -738,7 +741,7 @@ void __mmdrop(struct mm_struct *mm)
 	check_mm(mm);
 	mm_pasid_drop(mm);
 	mm_destroy_cid(mm);
-	percpu_counter_destroy_many(mm->rss_stat, NR_MM_COUNTERS);
+	percpu_counter_tree_destroy_many(mm->rss_stat, NR_MM_COUNTERS);
 
 	free_mm(mm);
 }
@@ -1144,8 +1147,9 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
 	if (mm_alloc_sched(mm))
 		goto fail_sched;
 
-	if (percpu_counter_init_many(mm->rss_stat, 0, GFP_KERNEL_ACCOUNT,
-				     NR_MM_COUNTERS))
+	if (percpu_counter_tree_init_many(mm->rss_stat, get_rss_stat_items(mm),
+					  NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE,
+					  GFP_KERNEL_ACCOUNT))
 		goto fail_pcpu;
 
 	lru_gen_init_mm(mm);
@@ -3122,7 +3126,7 @@ void __init mm_cache_init(void)
 	 * dynamically sized based on the maximum CPU number this system
 	 * can have, taking hotplug into account (nr_cpu_ids).
 	 */
-	mm_size = sizeof(struct mm_struct) + cpumask_size() + mm_cid_size();
+	mm_size = sizeof(struct mm_struct) + cpumask_size() + mm_cid_size() + get_rss_stat_items_size();
 
 	mm_cachep = kmem_cache_create_usercopy("mm_struct",
 			mm_size, ARCH_MIN_MMSTRUCT_ALIGN,
Signature · 1 line
2.43.0
author reviewer
#7 lore raw

PATCH v21 4/6 mm: reorder mm_struct flexible array to place mm_cpumask first

In reply to Mathieu Desnoyers

Reorder the mm_struct flexible array layout from:

[HPCC tree items][mm_cpumask][mm_cid]

to:

[mm_cpumask][mm_cid][alignment padding][HPCC tree items]

The previous layout placed the HPCC tree items first, which required mm_cpumask() to skip past them using percpu_counter_tree_items_size(). This created a boot-time initialization ordering dependency: any use of mm_cpumask() before percpu_counter_tree_subsystem_init() would compute the wrong pointer offset, reading from or writing to the HPCC items region instead of the actual cpumask.

On powerpc, switch_mm_irqs_off() accesses mm_cpumask() early in boot via VM_WARN_ON_ONCE(!cpumask_test_cpu(cpu, mm_cpumask(prev))), which could fire spuriously or cause silent memory corruption if the HPCC subsystem was not yet initialized.

By placing mm_cpumask first, mm_cpumask() remains a simple &mm->flexible_array with no runtime dependency on HPCC initialization. The HPCC tree items are accessed via get_rss_stat_items_offset(), which skips past the cpumask and mm_cid with appropriate cacheline alignment padding. This accessor is only used during mm_struct initialization (percpu_counter_tree_init_many), not on context switch or other hot paths.

Introduce the PERCPU_COUNTER_TREE_ITEMS_ALIGN() macro to handle the SMP cacheline alignment vs !SMP no-op in a single place, used by both the static init_mm flexible array initializer and the runtime offset computation.

The cost is at most one cacheline (typically 64 bytes) of padding per mm_struct between the mm_cid data and the HPCC tree items.

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 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]>
---
 include/linux/mm.h                  |  1 +
 include/linux/mm_types.h            | 47 +++++++++++++++++------------
 include/linux/percpu_counter_tree.h |  3 ++
 kernel/fork.c                       |  4 ++-
 4 files changed, 34 insertions(+), 21 deletions(-)
include/linux/mm.h +1 -0
index 7dd6fdda9bc8..ffbcd18c4ecb 100644
@@ -3453,6 +3453,7 @@ static inline struct percpu_counter_tree_level_item *get_rss_stat_items(struct m
 	unsigned long ptr = (unsigned long)mm;
 
 	ptr += offsetof(struct mm_struct, flexible_array);
+	ptr += get_rss_stat_items_offset();
 	return (struct percpu_counter_tree_level_item *)ptr;
 }
 
include/linux/mm_types.h +27 -20

77 lines not on this page · raw message

include/linux/percpu_counter_tree.h +3 -0
index 828c763edd4a..3e8a820e2d1d 100644
@@ -66,6 +66,8 @@ struct percpu_counter_tree_level_item {
 
 #define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE	\
 	(PERCPU_COUNTER_TREE_STATIC_NR_ITEMS * sizeof(struct percpu_counter_tree_level_item))
+#define PERCPU_COUNTER_TREE_ITEMS_ALIGN(offset)	\
+	ALIGN((offset), __alignof__(struct percpu_counter_tree_level_item))
 
 struct percpu_counter_tree {
 	/* Fast-path fields. */
@@ -167,6 +169,7 @@ void percpu_counter_tree_approximate_accuracy_range(struct percpu_counter_tree *
 #else	/* !CONFIG_SMP */
 
 #define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE	0
+#define PERCPU_COUNTER_TREE_ITEMS_ALIGN(offset)	(offset)
 
 struct percpu_counter_tree_level_item;
 
kernel/fork.c +3 -1
index 5bad7a24d186..db398b6c5288 100644
@@ -3126,7 +3126,9 @@ void __init mm_cache_init(void)
 	 * dynamically sized based on the maximum CPU number this system
 	 * can have, taking hotplug into account (nr_cpu_ids).
 	 */
-	mm_size = sizeof(struct mm_struct) + cpumask_size() + mm_cid_size() + get_rss_stat_items_size();
+	mm_size = sizeof(struct mm_struct) +
+		PERCPU_COUNTER_TREE_ITEMS_ALIGN(cpumask_size() + mm_cid_size()) +
+		get_rss_stat_items_size();
 
 	mm_cachep = kmem_cache_create_usercopy("mm_struct",
 			mm_size, ARCH_MIN_MMSTRUCT_ALIGN,
Signature · 1 line
2.43.0
author reviewer
#8 lore raw

PATCH v21 5/6 init: move percpu_counter_tree_subsystem_init() earlier in boot

In reply to Mathieu Desnoyers

Move percpu_counter_tree_subsystem_init() from after trap_init() to immediately after setup_nr_cpu_ids() in start_kernel().

The function's only dependency is nr_cpu_ids: it calls get_count_order(nr_cpu_ids), indexes into a const configuration table, and performs arithmetic to derive accuracy parameters. It requires no memory allocator, percpu areas, or other infrastructure.

Initialize the subsystem as soon as its dependency is available rather than deferring until later in the boot sequence. This ensures percpu_counter_tree_items_size() returns the correct value well before its first use in mm_cache_init().

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 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]>
---
 init/main.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
init/main.c +1 -1
index eda2170bb21f..845cb57e9096 100644
@@ -1011,6 +1011,7 @@ void start_kernel(void)
 	setup_boot_config();
 	setup_command_line(command_line);
 	setup_nr_cpu_ids();
+	percpu_counter_tree_subsystem_init();
 	setup_per_cpu_areas();
 	smp_prepare_boot_cpu();	/* arch-specific boot-cpu hooks */
 	early_numa_node_init();
@@ -1042,7 +1043,6 @@ void start_kernel(void)
 	vfs_caches_init_early();
 	sort_main_extable();
 	trap_init();
-	percpu_counter_tree_subsystem_init();
 	mm_core_init();
 	maple_tree_init();
 	poking_init();
Signature · 1 line
2.43.0
author reviewer
#9 lore raw

PATCH v21 6/6 lib: inline percpu_counter_tree_items_size with boot-safety sentinel

In reply to Mathieu Desnoyers

Replace the out-of-line percpu_counter_tree_items_size() function with a static inline that loads the __ro_after_init variable __percpu_counter_tree_items_size directly. This eliminates a function call on paths that compute mm_struct flexible array layout offsets.

Initialize the variable to SIZE_MAX as a sentinel value, and add a WARN_ON_ONCE check in the inline accessor to catch any accidental use before percpu_counter_tree_subsystem_init() sets the real value based on nr_cpu_ids. An early misuse would produce an absurd offset that triggers the warning with a stack trace pointing at the offending caller, rather than silently computing wrong memory offsets.

percpu_counter_tree_subsystem_init() sets the variable to the runtime value immediately after deriving counter_config from nr_cpu_ids, before calculate_accuracy_topology(). After boot, __ro_after_init moves the variable into read-only memory.

On !CONFIG_SMP, the existing inline returning 0 is unchanged and requires no sentinel.

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 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]>
---
 include/linux/percpu_counter_tree.h | 19 ++++++++++++++++++-
 lib/percpu_counter_tree.c           | 24 ++++++++----------------
 2 files changed, 26 insertions(+), 17 deletions(-)
include/linux/percpu_counter_tree.h +18 -1
index 3e8a820e2d1d..4095acdc879b 100644
@@ -101,7 +101,24 @@ struct percpu_counter_tree {
 	} approx_accuracy_range;
 };
 
-size_t percpu_counter_tree_items_size(void);
+extern size_t __percpu_counter_tree_items_size __ro_after_init;
+
+/*
+ * percpu_counter_tree_items_size - Query the size required for counter tree items.
+ *
+ * Query the size of the memory area required to hold the counter tree
+ * items. This depends on the hardware topology and is invariant after
+ * boot.
+ *
+ * Return: Size required to hold tree items.
+ */
+static inline
+size_t percpu_counter_tree_items_size(void)
+{
+	WARN_ON_ONCE(__percpu_counter_tree_items_size == SIZE_MAX);
+	return __percpu_counter_tree_items_size;
+}
+
 int percpu_counter_tree_init_many(struct percpu_counter_tree *counters, struct percpu_counter_tree_level_item *items,
 				  unsigned int nr_counters, unsigned long batch_size, gfp_t gfp_flags);
 int percpu_counter_tree_init(struct percpu_counter_tree *counter, struct percpu_counter_tree_level_item *items,
lib/percpu_counter_tree.c +8 -16
index 5c8fc2dcdc16..cfa5b04e05d7 100644
@@ -653,22 +653,9 @@ void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v)
 }
 EXPORT_SYMBOL_GPL(percpu_counter_tree_set);
 
-/*
- * percpu_counter_tree_items_size - Query the size required for counter tree items.
- *
- * Query the size of the memory area required to hold the counter tree
- * items. This depends on the hardware topology and is invariant after
- * boot.
- *
- * Return: Size required to hold tree items.
- */
-size_t percpu_counter_tree_items_size(void)
-{
-	if (!nr_cpus_order)
-		return 0;
-	return counter_config->nr_items * sizeof(struct percpu_counter_tree_level_item);
-}
-EXPORT_SYMBOL_GPL(percpu_counter_tree_items_size);
+/* Initialize to SIZE_MAX to catch early boot misuses. */
+size_t __percpu_counter_tree_items_size __ro_after_init = SIZE_MAX;
+EXPORT_SYMBOL_GPL(__percpu_counter_tree_items_size);
 
 static void __init calculate_accuracy_topology(void)
 {
@@ -697,6 +684,11 @@ int __init percpu_counter_tree_subsystem_init(void)
 		return -1;
 	}
 	counter_config = &per_nr_cpu_order_config[nr_cpus_order];
+	if (!nr_cpus_order)
+		__percpu_counter_tree_items_size = 0;
+	else
+		__percpu_counter_tree_items_size = counter_config->nr_items *
+			sizeof(struct percpu_counter_tree_level_item);
 	calculate_accuracy_topology();
 	return 0;
 }
Signature · 1 line
2.43.0
#10 lore raw
In reply to Mathieu Desnoyers
Quoted 10 lines · Mathieu Desnoyers

Hi Andrew,

Here is the hierarchical percpu counters for RSS accounting series rebased on top of v7.3-rc1. It includes small bootup fixes which were needed to fix bootup sequence on specific architectures, and a rename of the test config option to include "KUNIT_".

This aims at replacing the prior version of the series you had in mm.

Quoted 8 lines

As a reminder, the goal here is to provide more precise RSS counters through /proc. A future step would be to also use these counters to speed up the OOM killer task selection when OOM is triggered by memcg. In whole-machine OOM situations, latency introduced by the OOM killer task selection may not be too much of an issue, but for memcg, where cgroups may routinely depend on the OOM killer, the acceptable latency tradeoff is quite different.

Hi Mathieu, can you please comment on the Sashiko's findings [1]? Worth addressing or not?

[1] https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers%40efficios.com

author reviewer
#11 lore raw
Quoted 20 lines · Shakeel Butt
Quoted 10 lines · Mathieu Desnoyers

Hi Andrew,

Here is the hierarchical percpu counters for RSS accounting series rebased on top of v7.3-rc1. It includes small bootup fixes which were needed to fix bootup sequence on specific architectures, and a rename of the test config option to include "KUNIT_".

This aims at replacing the prior version of the series you had in mm.

Quoted 8 lines

As a reminder, the goal here is to provide more precise RSS counters through /proc. A future step would be to also use these counters to speed up the OOM killer task selection when OOM is triggered by memcg. In whole-machine OOM situations, latency introduced by the OOM killer task selection may not be too much of an issue, but for memcg, where cgroups may routinely depend on the OOM killer, the acceptable latency tradeoff is quite different.

Quoted 5 lines

Hi Mathieu, can you please comment on the Sashiko's findings [1]? Worth addressing or not?

[1] https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers%40efficios.com

I've looked at the report. There are 4 classes of things happening there. FWIW I've also used Claude to counter-check the report.

Summary: no code change appears to be needed for classes 1 and 2. I should do test and module teardown fixes, as well as overflow cleanup for a v22.

* Class 1: the supposed "over vs under" swapped accuracy bounds. In that case it appears to be the LLM which is confused. This is because the range of approximation as a function of the precise sum is expressed in the opposite direction than the range of precise sum as a function of the approximation:

+ * The range of the approximation as a function of the precise sum is expressed as:
+ *
+ * approx_sum >= precise_sum - approx_accuracy_range.under
+ * approx_sum <= precise_sum + approx_accuracy_range.over
+ *
+ * Therefore, the range of the precise sum as a function of the approximation is expressed as:
+ *
+ * precise_sum <= approx_sum + approx_accuracy_range.under
+ * precise_sum >= approx_sum - approx_accuracy_range.over

We could possibly extend this documentation elsewhere to make sure that a LLM with limited context don't get confused, but the code is OK there.

Sashiko wrote that the positive margin "should be over_a + under_b" and then claimed the code passes under_a + over_b. The code passes a->over + b->under. Exactly what Sashiko itself derived. Its reasoning agreed with the code; it misread which argument was which.

* Class 2:

Review

Quoted 11 lines
(quoted diff) +11 -0
+void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc)
+{
+    unsigned long bit_mask = counter->level0_bit_mask, orig, res;
+
+    res = this_cpu_add_return(*counter->level0, inc);
+    orig = res - inc;
+    inc = percpu_counter_tree_carry(orig, res, inc, bit_mask);
+    if (likely(!inc))
+        return;
+    percpu_counter_tree_add_slowpath(counter, inc);
+}

Sashiko:
Does this code risk an unbounded approximation error if preemption occurs after this_cpu_add_return() but before percpu_counter_tree_add_slowpath()? The level 0 counter reflects the addition immediately, but if the task is preempted before propagating the carry to the tree, that carry is held back indefinitely. Multiple preempted tasks could cause the approximate sum to deviate from the precise sum by an amount far exceeding the topological accuracy bounds. Could we disable preemption across this entire sequence?

My take on this:

I think we need a clearer _documentation_ statement about what the approximation upper bounds guarantee. It guarantees upper bounds on the approximation error _when the counters are quiescent_, never when they are actively being concurrently updated. So if a thread is preempted _while propagating the carry_, it's not quiescent. I don't think we need any code change there. And disabling preemption would not "fix" anything there, it would merely make the race smaller.

* Class 3:

Test cases boilerplate, module teardown and cpu hotplug issues: Good catches, I'll fix them.

* Class 4: Overflows

In order to be strictly C compliant, I should do the difference in unsigned (where overflow/underflow is OK), and cast the result as signed to compare with 0 with a inequality. It won't change things in practice, but it's a good call.

Thoughts ?

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com