Introduce Hierarchical Per-CPU Counters
Subsystems (4)
Mathieu Desnoyers
reviewerRFC PATCH v3 1/1 Introduce Hierarchical Per-CPU Counters
* 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.
It aims at fixing the per-mm RSS tracking which has become too inaccurate for OOM killer purposes on large many-core systems [1].
* 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: 0For a binary tree, the maximum inaccuracy is bound by:
batch_size * log2(nr_cpus) * nr_cpus
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.
---
Changes since v2:
- Introduce N-way tree to reduce tree depth on larger systems.
Changes since v1:
- Remove percpu_counter_tree_precise_sum_unbiased from public header, make this function static,
- Introduce precise and approximate comparisons between two counters,
- Reorder the struct percpu_counter_tree fields,
- Introduce approx_sum field, which points to the approximate sum for the percpu_counter_tree_approximate_sum() fast path.
--- include/linux/percpu_counter_tree.h | 108 ++++++++ lib/Makefile | 1 + lib/percpu_counter_tree.c | 393 ++++++++++++++++++++++++++++ 3 files changed, 502 insertions(+) create mode 100644 include/linux/percpu_counter_tree.h create mode 100644 lib/percpu_counter_tree.c
include/linux/percpu_counter_tree.h new file +108 -0
@@ -0,0 +1,108 @@ +/* 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 + +#include <linux/cleanup.h> +#include <linux/preempt.h> +#include <linux/atomic.h> +#include <linux/percpu.h> + +struct percpu_counter_tree_level_item { +atomic_t count; +}____cacheline_aligned_in_smp ; + +struct percpu_counter_tree { +/* Fast-path fields. */ +unsigned int __percpu *level0; +unsigned int level0_bit_mask; +union { +unsigned int *i; +atomic_t *a; + } approx_sum; +int bias;/* bias for counter_set */ + +/* Slow-path fields. */ +struct percpu_counter_tree_level_item *items; +unsigned int batch_size; +unsigned int inaccuracy;/* approximation imprecise within ± inaccuracy */ +}; + +int percpu_counter_tree_init (struct percpu_counter_tree *counter,unsigned int batch_size); +void percpu_counter_tree_destroy (struct percpu_counter_tree *counter); +void percpu_counter_tree_add_slowpath (struct percpu_counter_tree *counter,int inc); +int percpu_counter_tree_precise_sum (struct percpu_counter_tree *counter); +int percpu_counter_tree_approximate_compare (struct percpu_counter_tree *a,struct percpu_counter_tree *b); +int percpu_counter_tree_approximate_compare_value (struct percpu_counter_tree *counter,int v); +int percpu_counter_tree_precise_compare (struct percpu_counter_tree *a,struct percpu_counter_tree *b); +int percpu_counter_tree_precise_compare_value (struct percpu_counter_tree *counter,int v); +void percpu_counter_tree_set_bias (struct percpu_counter_tree *counter,int bias); +void percpu_counter_tree_set (struct percpu_counter_tree *counter,int v); +unsigned int percpu_counter_tree_inaccuracy (struct percpu_counter_tree *counter); + +/* Fast paths */ + +static inline +int percpu_counter_tree_carry (int orig,int res,int inc,unsigned int bit_mask) +{ +if (inc <0 ) { + inc = -(-inc & ~(bit_mask -1 )); +/* +* xor bit_mask: underflow. +* +* If inc has bit set, decrement an additional bit if +* there is _no_ bit transition between orig and res. +* Else, inc has bit cleared, decrement an additional +* bit if there is a bit transition between orig and +* res. +*/ +if ((inc ^ orig ^ res) & bit_mask) + inc -= bit_mask; + }else { + inc &= ~(bit_mask -1 ); +/* +* xor bit_mask: overflow. +* +* If inc has bit set, increment an additional bit if +* there is _no_ bit transition between orig and res. +* Else, inc has bit cleared, increment an additional +* bit if there is a bit transition between orig and +* res. +*/ +if ((inc ^ orig ^ res) & bit_mask) + inc += bit_mask; + } +return inc; +} + +static inline +void percpu_counter_tree_add (struct percpu_counter_tree *counter,int inc) +{ +unsigned int bit_mask = counter->level0_bit_mask, orig, res; + +if (!inc) +return ; +/* Make sure the fast and slow paths use the same cpu number. */ +guard (migrate)(); + res =this_cpu_add_return (*counter->level0, inc); + orig = res - inc; + inc =percpu_counter_tree_carry (orig, res, inc, bit_mask); +if (!inc) +return ; +percpu_counter_tree_add_slowpath (counter, inc); +} + +static inline +int percpu_counter_tree_approximate_sum (struct percpu_counter_tree *counter) +{ +unsigned int v; + +if (!counter->level0_bit_mask) + v =READ_ONCE (*counter->approx_sum.i); +else + v =atomic_read (counter->approx_sum.a); +return (int ) (v + (unsigned int )READ_ONCE (counter->bias)); +} + +#endif /* _PERCPU_COUNTER_TREE_H */
lib/Makefile +1 -0
@@ -201,6 +201,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 +393 -0
393 lines not on this page · raw message
Signature · 1 line
2.39.5