[PATCH] sched/cpupri: Remove count field from struct cpupri_vec

[PATCH] sched/cpupri: Remove count field from struct cpupri_vec

[Luigi Rizzo]

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.

Signed-off-by: Luigi Rizzo <lrizzo@google.com>
---
 kernel/sched/cpupri.c | 61 ++-----------------------------------------
 kernel/sched/cpupri.h |  2 --
 2 files changed, 2 insertions(+), 61 deletions(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index 8f2237e8b484f..e9025f47880d9 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -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;
 	}
diff --git a/kernel/sched/cpupri.h b/kernel/sched/cpupri.h
index 6f562088c0565..78516c8428761 100644
--- a/kernel/sched/cpupri.h
+++ b/kernel/sched/cpupri.h
@@ -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		100
 
 struct cpupri_vec {
-	atomic_t		count;
 	cpumask_var_t		mask;
 };
 
-- 
2.55.0.737.g08866a6d13-goog

[PATCH v2] sched/cpupri: Remove count field from struct cpupri_vec

[Luigi Rizzo]

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

Signed-off-by: Luigi Rizzo <lrizzo@google.com>
---
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(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index 8f2237e8b484f..5b107e863312a 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -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;
 	}
diff --git a/kernel/sched/cpupri.h b/kernel/sched/cpupri.h
index 6f562088c0565..78516c8428761 100644
--- a/kernel/sched/cpupri.h
+++ b/kernel/sched/cpupri.h
@@ -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		100
 
 struct cpupri_vec {
-	atomic_t		count;
 	cpumask_var_t		mask;
 };
 
-- 
2.55.0.737.g08866a6d13-goog