mm: Fix OOM killer inaccuracy on large many-core systems
Subsystems (7)
Mathieu Desnoyers
reviewerv6 cover mm: Fix OOM killer inaccuracy on large many-core systems
Introduce hierarchical per-cpu counters and use them for rss tracking to fix the per-mm RSS tracking which has become too inaccurate for OOM killer purposes on large many-core systems.
The approach proposed here is to replace this by the hierarchical per-cpu counters, which bounds the inaccuracy based on the system topology with O(N*logN).
Relevant delta since v5: introduce !CONFIG_SMP static inlines to fix UP build and introduce percpu_counter_tree_approximate_sum_positive.
Testing and feedback are welcome!
Thanks,
Mathieu
Mathieu Desnoyers (2):
lib: Introduce hierarchical per-cpu counters
mm: Fix OOM killer inaccuracy on large many-core systems
include/linux/mm.h | 8 +- include/linux/mm_types.h | 4 +- include/linux/percpu_counter_tree.h | 203 ++++++++++++++ include/trace/events/kmem.h | 2 +- kernel/fork.c | 31 ++- lib/Makefile | 1 + lib/percpu_counter_tree.c | 394 ++++++++++++++++++++++++++++ 7 files changed, 626 insertions(+), 17 deletions(-) create mode 100644 include/linux/percpu_counter_tree.h create mode 100644 lib/percpu_counter_tree.c
Signature · 1 line
2.39.5
Mathieu Desnoyers
reviewerRFC PATCH v6 1/2 lib: 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 v5:
- Introduce percpu_counter_tree_approximate_sum_positive.
- Introduce !CONFIG_SMP static inlines for UP build.
- Remove percpu_counter_tree_set_bias from the public API and make it static.
Changes since v3:
- Add gfp flags to init function.
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 | 203 ++++++++++++++ lib/Makefile | 1 + lib/percpu_counter_tree.c | 394 ++++++++++++++++++++++++++++ 3 files changed, 598 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 +203 -0
@@ -0,0 +1,203 @@ +/* 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> + +#ifdef CONFIG_SMP + +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,gfp_t gfp_flags); +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 (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)); +} + +#else /* !CONFIG_SMP */ + +struct percpu_counter_tree { +atomic_t count; +}; + +static inline +int percpu_counter_tree_init (struct percpu_counter_tree *counter,unsigned int batch_size,gfp_t gfp_flags) +{ +atomic_set (&counter->count,0 ); +return 0 ; +} + +static inline +void percpu_counter_tree_destroy (struct percpu_counter_tree *counter) +{ +} + +static inline +int percpu_counter_tree_precise_sum (struct percpu_counter_tree *counter) +{ +return atomic_read (&counter->count); +} + +static inline +int percpu_counter_tree_precise_compare (struct percpu_counter_tree *a,struct percpu_counter_tree *b) +{ +int count_a =percpu_counter_tree_precise_sum (a), + count_b =percpu_counter_tree_precise_sum (b); + +if (count_a == count_b) +return 0 ; +if (count_a < count_b) +return -1 ; +return 1 ; +} + +static inline +int percpu_counter_tree_precise_compare_value (struct percpu_counter_tree *counter,int v) +{ +int count =percpu_counter_tree_precise_sum (counter); + +if (count == v) +return 0 ; +if (count < v) +return -1 ; +return 1 ; +} + +static inline +int percpu_counter_tree_approximate_compare (struct percpu_counter_tree *a,struct percpu_counter_tree *b) +{ +return percpu_counter_tree_precise_compare (a, b); +} + +static inline +int percpu_counter_tree_approximate_compare_value (struct percpu_counter_tree *counter,int v) +{ +return percpu_counter_tree_precise_compare_value (counter, v); +} + +static inline +void percpu_counter_tree_set (struct percpu_counter_tree *counter,int v) +{ +atomic_set (&counter->count, v); +} + +static inline +unsigned int percpu_counter_tree_inaccuracy (struct percpu_counter_tree *counter) +{ +return 0 ; +} + +static inline +void percpu_counter_tree_add (struct percpu_counter_tree *counter,int inc) +{ +atomic_add (inc, &counter->count); +} + +static inline +int percpu_counter_tree_approximate_sum (struct percpu_counter_tree *counter) +{ +return percpu_counter_tree_precise_sum (counter); +} + +#endif /* CONFIG_SMP */ + +static inline +int percpu_counter_tree_approximate_sum_positive (struct percpu_counter_tree *counter) +{ +int v =percpu_counter_tree_approximate_sum (counter); +return v >0 ? v :0 ; +} + +#endif /* _PERCPU_COUNTER_TREE_H */
lib/Makefile +1 -0
@@ -191,6 +191,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 +394 -0
394 lines not on this page · raw message
Signature · 1 line
2.39.5
Mathieu Desnoyers
reviewerRFC PATCH v6 2/2 mm: Fix OOM killer inaccuracy on large many-core systems
In reply to Mathieu DesnoyersUse hierarchical per-cpu counters for rss tracking to fix the per-mm RSS tracking which has become too inaccurate for OOM killer purposes on large many-core systems.
The following rss tracking issues were noted by Sweet Tea Dorminy [1], which lead to picking wrong tasks as OOM kill target:
Recently, several internal services had an RSS usage regression as part of a kernel upgrade. Previously, they were on a pre-6.2 kernel and were able to read RSS statistics in a backup watchdog process to monitor and decide if they'd overrun their memory budget. Now, however, a representative service with five threads, expected to use about a hundred MB of memory, on a 250-cpu machine had memory usage tens of megabytes different from the expected amount -- this constituted a significant percentage of inaccuracy, causing the watchdog to act.
This was a result of f1a7941243c1 ("mm: convert mm's rss stats into percpu_counter") [1]. Previously, the memory error was bounded by 64*nr_threads pages, a very livable megabyte. Now, however, as a result of scheduler decisions moving the threads around the CPUs, the memory error could be as large as a gigabyte.
This is a really tremendous inaccuracy for any few-threaded program on a large machine and impedes monitoring significantly. These stat counters are also used to make OOM killing decisions, so this additional inaccuracy could make a big difference in OOM situations -- either resulting in the wrong process being killed, or in less memory being returned from an OOM-kill than expected.
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).
The approach proposed here is to replace this by the hierarchical per-cpu counters, which bounds the inaccuracy based on the system topology with O(N*logN).
---
Changes since v5:
- Use percpu_counter_tree_approximate_sum_positive.
Change since v4:
- get_mm_counter needs to return 0 or a positive value.
--- include/linux/mm.h | 8 ++++---- include/linux/mm_types.h | 4 ++-- include/trace/events/kmem.h | 2 +- kernel/fork.c | 31 +++++++++++++++++++++---------- 4 files changed, 28 insertions(+), 17 deletions(-)
include/linux/mm.h +4 -4
@@ -2705,28 +2705,28 @@ static inline bool get_user_page_fast_only(unsigned long addr,*/ 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]); }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 +2 -2
@@ -18,7 +18,7 @@#include <linux/page-flags-layout.h> #include <linux/workqueue.h> #include <linux/seqlock.h> -#include <linux/percpu_counter.h> +#include <linux/percpu_counter_tree.h> #include <linux/types.h> #include <asm/mmu.h>
@@ -1059,7 +1059,7 @@ struct mm_struct {unsigned long saved_auxv[AT_VECTOR_SIZE ];/* for /proc/PID/auxv */ -struct percpu_counter rss_stat[NR_MM_COUNTERS ]; +struct percpu_counter_tree rss_stat[NR_MM_COUNTERS ];struct linux_binfmt *binfmt;
include/trace/events/kmem.h +1 -1
@@ -477,7 +477,7 @@ TRACE_EVENT(rss_stat, __entry->mm_id =mm_ptr_to_hash (mm); __entry->curr = !!(current->mm == mm); __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 +21 -10
@@ -129,6 +129,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) */
@@ -843,11 +848,10 @@ 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)) -pr_alert ("BUG: Bad rss-counter state mm:%p type:%s val:%ld\n" , - mm, resident_page_types[i], 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:%d\n" , + mm, resident_page_types[i], +percpu_counter_tree_precise_sum (&mm->rss_stat[i])); }if (mm_pgtables_bytes (mm))
@@ -930,6 +934,8 @@ static void cleanup_lazy_tlbs(struct mm_struct *mm)*/ void __mmdrop (struct mm_struct *mm) { +int i; +BUG_ON (mm == &init_mm);WARN_ON_ONCE (mm == current->mm);
@@ -945,8 +951,8 @@ void __mmdrop(struct mm_struct *mm)put_user_ns (mm->user_ns);mm_pasid_drop (mm);mm_destroy_cid (mm); -percpu_counter_destroy_many (mm->rss_stat,NR_MM_COUNTERS ); - +for (i =0 ; i <NR_MM_COUNTERS ; i++) +percpu_counter_tree_destroy (&mm->rss_stat[i]);free_mm (mm); }EXPORT_SYMBOL_GPL (__mmdrop);
@@ -1285,6 +1291,8 @@ static void mmap_init_lock(struct mm_struct *mm)static struct mm_struct *mm_init (struct mm_struct *mm,struct task_struct *p,struct user_namespace *user_ns) { +int i; +mt_init_flags (&mm->mm_mt,MM_MT_FLAGS );mt_set_external_lock (&mm->mm_mt, &mm->mmap_lock);atomic_set (&mm->mm_users,1 );
@@ -1332,15 +1340,18 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,if (mm_alloc_cid (mm, p)) goto fail_cid; -if (percpu_counter_init_many (mm->rss_stat,0 ,GFP_KERNEL_ACCOUNT , -NR_MM_COUNTERS )) - goto fail_pcpu; +for (i =0 ; i <NR_MM_COUNTERS ; i++) { +if (percpu_counter_tree_init (&mm->rss_stat[i],RSS_STAT_BATCH_SIZE ,GFP_KERNEL_ACCOUNT )) + goto fail_pcpu; + } mm->user_ns =get_user_ns (user_ns);lru_gen_init_mm (mm);return mm; fail_pcpu: +for (i--; i >=0 ; i--) +percpu_counter_tree_destroy (&mm->rss_stat[i]);mm_destroy_cid (mm); fail_cid:destroy_context (mm);
Signature · 1 line
2.39.5