sched/cpupri: Remove count field from struct cpupri_vec
PATCH 1/1 sched/cpupri: Remove count field from struct cpupri_vec
Under heavy I/O workloads (such as fio using threaded IRQs), irq_thread runs as SCHED_FIFO 50 and undergoes frequent enqueue/dequeue cycles. Every dequeue invokes cpupri_set() to transition the CPU priority back to CPUPRI_NORMAL.
The "count" field in struct cpupri_vec was designed as an early-exit heuristic for __cpupri_find(). However, maintaining count in sync with mask requires atomics and expensive barriers (e.g. "dmb ish" on ARM), which on large multicore systems become extremely expensive:
Experiment on a dual socket ARM with 220 CPUs:
- runtime for cpupri_set(), nanoseconds:
with count: p10: 700 p50: 1915 p90: 6619 p98 11150 p99: 13200 without: p10: 290 p50: 425 p90: 567 p98: 685 p99: 821
- cpupri_set() usage on softirq CPU, measured with perf top
with count: ~ 25%
without: < 2%
Remove the count field from struct cpupri_vec and code manipulating it. This eliminates the cache-line contention and pipeline stalls while preserving scheduler correctness.
--- kernel/sched/cpupri.c | 61 ++----------------------------------------- kernel/sched/cpupri.h | 2 -- 2 files changed, 2 insertions(+), 61 deletions(-)
kernel/sched/cpupri.c +2 -59
@@ -69,33 +69,6 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p, struct cpumask *lowest_mask, int idx) {struct cpupri_vec *vec = &cp->pri_to_cpu[idx]; -int skip =0 ; - -if (!atomic_read (&(vec)->count)) - skip =1 ; -/* -* When looking at the vector, we need to read the counter, -* do a memory barrier, then read the mask. -* -* Note: This is still all racy, but we can deal with it. -* Ideally, we only want to look at masks that are set. -* -* If a mask is not set, then the only thing wrong is that we -* did a little more work than necessary. -* -* If we read a zero count but the mask is set, because of the -* memory barriers, that can only happen when the highest prio -* task for a run queue has left the run queue, in which case, -* it will be followed by a pull. If the task we are processing -* fails to find a proper place to go, that pull request will -* pull this task if the run queue is running at a lower -* priority. -*/ -smp_rmb (); - -/* Need to do the rmb for every iteration */ -if (skip) -return 0 ;if (cpumask_any_and (&p->cpus_mask, vec->mask) >= nr_cpu_ids)return 0 ;
@@ -212,7 +185,6 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri) {int *currpri = &cp->cpu_to_pri[cpu];int oldpri = *currpri; -int do_mb =0 ; newpri =convert_prio (newpri);
@@ -231,39 +203,11 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)struct cpupri_vec *vec = &cp->pri_to_cpu[newpri];cpumask_set_cpu (cpu, vec->mask); -/* -* When adding a new vector, we update the mask first, -* do a write memory barrier, and then update the count, to -* make sure the vector is visible when count is set. -*/ -smp_mb__before_atomic (); -atomic_inc (&(vec)->count); - do_mb =1 ; } -if (likely (oldpri !=CPUPRI_INVALID )) { -struct cpupri_vec *vec = &cp->pri_to_cpu[oldpri]; -/* -* Because the order of modification of the vec->count -* is important, we must make sure that the update -* of the new prio is seen before we decrement the -* old prio. This makes sure that the loop sees -* one or the other when we raise the priority of -* the run queue. We don't care about when we lower the -* priority, as that will trigger an rt pull anyway. -* -* We only need to do a memory barrier if we updated -* the new priority vec. -*/ -if (do_mb) -smp_mb__after_atomic (); +if (likely (oldpri !=CPUPRI_INVALID )) { +struct cpupri_vec *vec = &cp->pri_to_cpu[oldpri]; -/* -* When removing from the vector, we decrement the counter first -* do a memory barrier and then clear the mask. -*/ -atomic_dec (&(vec)->count); -smp_mb__after_atomic ();cpumask_clear_cpu (cpu, vec->mask); }
@@ -283,7 +227,6 @@ int cpupri_init(struct cpupri *cp)for (i =0 ; i <CPUPRI_NR_PRIORITIES ; i++) {struct cpupri_vec *vec = &cp->pri_to_cpu[i]; -atomic_set (&vec->count,0 );if (!zalloc_cpumask_var (&vec->mask,GFP_KERNEL )) goto cleanup; }
kernel/sched/cpupri.h +0 -2
@@ -1,5 +1,4 @@/* SPDX-License-Identifier: GPL-2.0 */ -#include <linux/atomic.h> #include <linux/cpumask.h> #include <linux/sched/rt.h>
@@ -11,7 +10,6 @@#define CPUPRI_HIGHER 100struct cpupri_vec { -atomic_t count;cpumask_var_t mask; };
Signature · 1 line
2.55.0.737.g08866a6d13-goog
PATCH v2 1/1 sched/cpupri: Remove count field from struct cpupri_vec
Under heavy I/O workloads (such as fio using threaded IRQs), irq_thread runs as SCHED_FIFO 50 and undergoes frequent enqueue/dequeue cycles. Every dequeue invokes cpupri_set() to transition the CPU priority back to CPUPRI_NORMAL.
The "count" field in struct cpupri_vec was designed as an early-exit heuristic for __cpupri_find(). However, maintaining count in sync with mask requires atomics and expensive barriers (e.g. "dmb ish" on ARM), which on large multicore systems become extremely expensive:
Remove the count field from struct cpupri_vec and code manipulating it. This eliminates the cache-line contention and pipeline stalls while preserving scheduler correctness.
Experiment on a dual socket ARM with 220 CPUs:
cpupri_set() measured with a fio workload, 220 threads on 220 queues:
- runtime for cpupri_set(), nanoseconds:
with count: p10: 700 p50: 1915 p90: 6619 p98 11150 p99: 13200 without: p10: 290 p50: 425 p90: 567 p98: 685 p99: 821
- cpupri_set() usage on softirq CPU, measured with perf top
with count: ~ 25%
without: < 2%
The effect on cpupri_find() can be seen with a competing workload that stresses it while running the above fio workload:
for ((i = 0; i < 20; i++)) { taskset -c 10-20 sudo chrt -f 50 sh -c 'while true; do sleep 0.001; done' & }
- runtime for cpupri_find(), nanoseconds:
with count: p10: 350 p50: 565 p90: 1660 p98 3300 p99: 3800 without: p10: 240 p50: 410 p90: 550 p98: 800 p99: 820
---
v1 -> v2:
- Added cpupri_find() benchmark results and test command under stress.
- Added explanatory comment in cpupri_set() on safety without memory barriers.
- Streamlined cpumask_set_cpu() and cpumask_clear_cpu() in cpupri_set().
kernel/sched/cpupri.c | 86 +++++++------------------------------------ kernel/sched/cpupri.h | 2 - 2 files changed, 14 insertions(+), 74 deletions(-)
kernel/sched/cpupri.c +14 -72
@@ -69,33 +69,6 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p, struct cpumask *lowest_mask, int idx) {struct cpupri_vec *vec = &cp->pri_to_cpu[idx]; -int skip =0 ; - -if (!atomic_read (&(vec)->count)) - skip =1 ; -/* -* When looking at the vector, we need to read the counter, -* do a memory barrier, then read the mask. -* -* Note: This is still all racy, but we can deal with it. -* Ideally, we only want to look at masks that are set. -* -* If a mask is not set, then the only thing wrong is that we -* did a little more work than necessary. -* -* If we read a zero count but the mask is set, because of the -* memory barriers, that can only happen when the highest prio -* task for a run queue has left the run queue, in which case, -* it will be followed by a pull. If the task we are processing -* fails to find a proper place to go, that pull request will -* pull this task if the run queue is running at a lower -* priority. -*/ -smp_rmb (); - -/* Need to do the rmb for every iteration */ -if (skip) -return 0 ;if (cpumask_any_and (&p->cpus_mask, vec->mask) >= nr_cpu_ids)return 0 ;
@@ -212,7 +185,6 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri) {int *currpri = &cp->cpu_to_pri[cpu];int oldpri = *currpri; -int do_mb =0 ; newpri =convert_prio (newpri);
@@ -222,50 +194,21 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)return ;/* -* If the CPU was currently mapped to a different value, we -* need to map it to the new value then remove the old value. -* Note, we must add the new value first, otherwise we risk the -* cpu being missed by the priority loop in cpupri_find. +* Map the CPU to the new priority before removing it from the old one. +* +* Note: Without memory barriers, the set and clear operations are +* unordered across vectors. Concurrent readers in cpupri_find() may +* transiently see the CPU in neither vector (or both). This is safe +* because cpupri is a best-effort routing hint: +* - If a CPU dropping priority is missed during push, it will pull +* tasks itself via balance_rt() / pull_rt_task(). +* - If a CPU raising priority is missed, it avoids pushing to a busy CPU. +* - Stale matches are validated under rq->lock in find_lock_lowest_rq(). */ -if (likely (newpri !=CPUPRI_INVALID )) { -struct cpupri_vec *vec = &cp->pri_to_cpu[newpri]; - -cpumask_set_cpu (cpu, vec->mask); -/* -* When adding a new vector, we update the mask first, -* do a write memory barrier, and then update the count, to -* make sure the vector is visible when count is set. -*/ -smp_mb__before_atomic (); -atomic_inc (&(vec)->count); - do_mb =1 ; - } -if (likely (oldpri !=CPUPRI_INVALID )) { -struct cpupri_vec *vec = &cp->pri_to_cpu[oldpri]; - -/* -* Because the order of modification of the vec->count -* is important, we must make sure that the update -* of the new prio is seen before we decrement the -* old prio. This makes sure that the loop sees -* one or the other when we raise the priority of -* the run queue. We don't care about when we lower the -* priority, as that will trigger an rt pull anyway. -* -* We only need to do a memory barrier if we updated -* the new priority vec. -*/ -if (do_mb) -smp_mb__after_atomic (); - -/* -* When removing from the vector, we decrement the counter first -* do a memory barrier and then clear the mask. -*/ -atomic_dec (&(vec)->count); -smp_mb__after_atomic (); -cpumask_clear_cpu (cpu, vec->mask); - } +if (likely (newpri !=CPUPRI_INVALID )) +cpumask_set_cpu (cpu, cp->pri_to_cpu[newpri].mask); +if (likely (oldpri !=CPUPRI_INVALID )) +cpumask_clear_cpu (cpu, cp->pri_to_cpu[oldpri].mask); *currpri = newpri; }
@@ -283,7 +226,6 @@ int cpupri_init(struct cpupri *cp)for (i =0 ; i <CPUPRI_NR_PRIORITIES ; i++) {struct cpupri_vec *vec = &cp->pri_to_cpu[i]; -atomic_set (&vec->count,0 );if (!zalloc_cpumask_var (&vec->mask,GFP_KERNEL )) goto cleanup; }
kernel/sched/cpupri.h +0 -2
@@ -1,5 +1,4 @@/* SPDX-License-Identifier: GPL-2.0 */ -#include <linux/atomic.h> #include <linux/cpumask.h> #include <linux/sched/rt.h>
@@ -11,7 +10,6 @@#define CPUPRI_HIGHER 100struct cpupri_vec { -atomic_t count;cpumask_var_t mask; };
Signature · 1 line
2.55.0.737.g08866a6d13-goog