From: Peter Zijlstra <peterz@infradead.org>
To: joel@joelfernandes.org, chris.hyser@oracle.com,
joshdon@google.com, mingo@kernel.org, vincent.guittot@linaro.org,
valentin.schneider@arm.com, mgorman@suse.de
Cc: linux-kernel@vger.kernel.org, peterz@infradead.org, tglx@linutronix.de
Subject: [PATCH 14/19] sched: Trivial forced-newidle balancer
Date: Thu, 22 Apr 2021 14:05:13 +0200 [thread overview]
Message-ID: <20210422123308.800048269@infradead.org> (raw)
In-Reply-To: 20210422120459.447350175@infradead.org
When a sibling is forced-idle to match the core-cookie; search for
matching tasks to fill the core.
rcu_read_unlock() can incur an infrequent deadlock in
sched_core_balance(). Fix this by using the RCU-sched flavor instead.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
include/linux/sched.h | 1
kernel/sched/core.c | 130 +++++++++++++++++++++++++++++++++++++++++++++++++-
kernel/sched/idle.c | 1
kernel/sched/sched.h | 6 ++
4 files changed, 137 insertions(+), 1 deletion(-)
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -704,6 +704,7 @@ struct task_struct {
#ifdef CONFIG_SCHED_CORE
struct rb_node core_node;
unsigned long core_cookie;
+ unsigned int core_occupation;
#endif
#ifdef CONFIG_CGROUP_SCHED
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -204,6 +204,21 @@ static struct task_struct *sched_core_fi
return __node_2_sc(node);
}
+static struct task_struct *sched_core_next(struct task_struct *p, unsigned long cookie)
+{
+ struct rb_node *node = &p->core_node;
+
+ node = rb_next(node);
+ if (!node)
+ return NULL;
+
+ p = container_of(node, struct task_struct, core_node);
+ if (p->core_cookie != cookie)
+ return NULL;
+
+ return p;
+}
+
/*
* Magic required such that:
*
@@ -5371,8 +5386,8 @@ pick_next_task(struct rq *rq, struct tas
const struct sched_class *class;
const struct cpumask *smt_mask;
bool fi_before = false;
+ int i, j, cpu, occ = 0;
bool need_sync;
- int i, j, cpu;
if (!sched_core_enabled(rq))
return __pick_next_task(rq, prev, rf);
@@ -5494,6 +5509,9 @@ pick_next_task(struct rq *rq, struct tas
if (!p)
continue;
+ if (!is_task_rq_idle(p))
+ occ++;
+
rq_i->core_pick = p;
if (rq_i->idle == p && rq_i->nr_running) {
rq->core->core_forceidle = true;
@@ -5525,6 +5543,7 @@ pick_next_task(struct rq *rq, struct tas
cpu_rq(j)->core_pick = NULL;
}
+ occ = 1;
goto again;
}
}
@@ -5570,6 +5589,8 @@ pick_next_task(struct rq *rq, struct tas
if (!(fi_before && rq->core->core_forceidle))
task_vruntime_update(rq_i, rq_i->core_pick, rq->core->core_forceidle);
+ rq_i->core_pick->core_occupation = occ;
+
if (i == cpu) {
rq_i->core_pick = NULL;
continue;
@@ -5591,6 +5612,113 @@ pick_next_task(struct rq *rq, struct tas
return next;
}
+static bool try_steal_cookie(int this, int that)
+{
+ struct rq *dst = cpu_rq(this), *src = cpu_rq(that);
+ struct task_struct *p;
+ unsigned long cookie;
+ bool success = false;
+
+ local_irq_disable();
+ double_rq_lock(dst, src);
+
+ cookie = dst->core->core_cookie;
+ if (!cookie)
+ goto unlock;
+
+ if (dst->curr != dst->idle)
+ goto unlock;
+
+ p = sched_core_find(src, cookie);
+ if (p == src->idle)
+ goto unlock;
+
+ do {
+ if (p == src->core_pick || p == src->curr)
+ goto next;
+
+ if (!cpumask_test_cpu(this, &p->cpus_mask))
+ goto next;
+
+ if (p->core_occupation > dst->idle->core_occupation)
+ goto next;
+
+ p->on_rq = TASK_ON_RQ_MIGRATING;
+ deactivate_task(src, p, 0);
+ set_task_cpu(p, this);
+ activate_task(dst, p, 0);
+ p->on_rq = TASK_ON_RQ_QUEUED;
+
+ resched_curr(dst);
+
+ success = true;
+ break;
+
+next:
+ p = sched_core_next(p, cookie);
+ } while (p);
+
+unlock:
+ double_rq_unlock(dst, src);
+ local_irq_enable();
+
+ return success;
+}
+
+static bool steal_cookie_task(int cpu, struct sched_domain *sd)
+{
+ int i;
+
+ for_each_cpu_wrap(i, sched_domain_span(sd), cpu) {
+ if (i == cpu)
+ continue;
+
+ if (need_resched())
+ break;
+
+ if (try_steal_cookie(cpu, i))
+ return true;
+ }
+
+ return false;
+}
+
+static void sched_core_balance(struct rq *rq)
+{
+ struct sched_domain *sd;
+ int cpu = cpu_of(rq);
+
+ preempt_disable();
+ rcu_read_lock();
+ raw_spin_rq_unlock_irq(rq);
+ for_each_domain(cpu, sd) {
+ if (need_resched())
+ break;
+
+ if (steal_cookie_task(cpu, sd))
+ break;
+ }
+ raw_spin_rq_lock_irq(rq);
+ rcu_read_unlock();
+ preempt_enable();
+}
+
+static DEFINE_PER_CPU(struct callback_head, core_balance_head);
+
+void queue_core_balance(struct rq *rq)
+{
+ if (!sched_core_enabled(rq))
+ return;
+
+ if (!rq->core->core_cookie)
+ return;
+
+ if (!rq->nr_running) /* not forced idle */
+ return;
+
+ queue_balance_callback(rq, &per_cpu(core_balance_head, rq->cpu), sched_core_balance);
+}
+
static inline void sched_core_cpu_starting(unsigned int cpu)
{
const struct cpumask *smt_mask = cpu_smt_mask(cpu);
--- a/kernel/sched/idle.c
+++ b/kernel/sched/idle.c
@@ -437,6 +437,7 @@ static void set_next_task_idle(struct rq
{
update_idle_core(rq);
schedstat_inc(rq->sched_goidle);
+ queue_core_balance(rq);
}
#ifdef CONFIG_SMP
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1170,6 +1170,8 @@ static inline raw_spinlock_t *__rq_lockp
bool cfs_prio_less(struct task_struct *a, struct task_struct *b, bool fi);
+extern void queue_core_balance(struct rq *rq);
+
#else /* !CONFIG_SCHED_CORE */
static inline bool sched_core_enabled(struct rq *rq)
@@ -1187,6 +1189,10 @@ static inline raw_spinlock_t *rq_lockp(s
return &rq->__lock;
}
+static inline void queue_core_balance(struct rq *rq)
+{
+}
+
#endif /* CONFIG_SCHED_CORE */
static inline void lockdep_assert_rq_held(struct rq *rq)
next prev parent reply other threads:[~2021-04-22 12:38 UTC|newest]
Thread overview: 103+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-04-22 12:04 [PATCH 00/19] sched: Core Scheduling Peter Zijlstra
2021-04-22 12:05 ` [PATCH 01/19] sched/fair: Add a few assertions Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-05-13 8:56 ` Ning, Hongyu
2021-04-22 12:05 ` [PATCH 02/19] sched: Provide raw_spin_rq_*lock*() helpers Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 03/19] sched: Wrap rq::lock access Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 04/19] sched: Prepare for Core-wide rq->lock Peter Zijlstra
2021-04-24 1:22 ` Josh Don
2021-04-26 8:31 ` Peter Zijlstra
2021-04-26 22:21 ` Josh Don
2021-04-27 17:10 ` Don Hiatt
2021-04-27 23:35 ` Josh Don
2021-04-28 1:03 ` Aubrey Li
2021-04-28 6:05 ` Aubrey Li
2021-04-28 10:57 ` Aubrey Li
2021-04-28 16:41 ` Don Hiatt
2021-04-29 20:48 ` Josh Don
2021-04-29 21:09 ` Don Hiatt
2021-04-29 23:22 ` Josh Don
2021-04-30 16:18 ` Don Hiatt
2021-04-30 8:26 ` Aubrey Li
2021-04-28 16:04 ` Don Hiatt
2021-04-27 23:30 ` Josh Don
2021-04-28 9:13 ` Peter Zijlstra
2021-04-28 10:35 ` Aubrey Li
2021-04-28 11:03 ` Peter Zijlstra
2021-04-28 14:18 ` Paul E. McKenney
2021-04-29 20:11 ` Josh Don
2021-05-03 19:17 ` Peter Zijlstra
2021-04-28 7:13 ` Peter Zijlstra
2021-04-28 6:02 ` Aubrey Li
2021-04-29 8:03 ` Aubrey Li
2021-04-29 20:39 ` Josh Don
2021-04-30 8:20 ` Aubrey Li
2021-04-30 8:48 ` Josh Don
2021-04-30 14:15 ` Aubrey Li
2021-05-04 7:38 ` Peter Zijlstra
2021-05-05 16:20 ` Don Hiatt
2021-05-06 10:25 ` Peter Zijlstra
2021-05-07 9:50 ` [PATCH v2 " Peter Zijlstra
2021-05-08 8:07 ` Aubrey Li
2021-05-12 9:07 ` Peter Zijlstra
2021-04-22 12:05 ` [PATCH 05/19] sched: " Peter Zijlstra
2021-05-07 9:50 ` [PATCH v2 " Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 06/19] sched: Optimize rq_lockp() usage Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 07/19] sched: Allow sched_core_put() from atomic context Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 08/19] sched: Introduce sched_class::pick_task() Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 09/19] sched: Basic tracking of matching tasks Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 10/19] sched: Add core wide task selection and scheduling Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 11/19] sched/fair: Fix forced idle sibling starvation corner case Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Vineeth Pillai
2021-04-22 12:05 ` [PATCH 12/19] sched: Fix priority inversion of cookied task with sibling Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Joel Fernandes (Google)
2021-04-22 12:05 ` [PATCH 13/19] sched/fair: Snapshot the min_vruntime of CPUs on force idle Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Joel Fernandes (Google)
2021-04-22 12:05 ` Peter Zijlstra [this message]
2021-05-12 10:28 ` [tip: sched/core] sched: Trivial forced-newidle balancer tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 15/19] sched: Migration changes for core scheduling Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Aubrey Li
2021-04-22 12:05 ` [PATCH 16/19] sched: Trivial core scheduling cookie management Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 17/19] sched: Inherit task cookie on fork() Peter Zijlstra
2021-05-10 16:06 ` Joel Fernandes
2021-05-10 16:22 ` Chris Hyser
2021-05-10 20:47 ` Joel Fernandes
2021-05-10 21:38 ` Chris Hyser
2021-05-12 9:05 ` Peter Zijlstra
2021-05-12 20:20 ` Josh Don
2021-05-12 21:07 ` Don Hiatt
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 18/19] sched: prctl() core-scheduling interface Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Chris Hyser
2021-06-14 23:36 ` [PATCH 18/19] " Josh Don
2021-06-15 11:31 ` Joel Fernandes
2021-08-05 16:53 ` Eugene Syromiatnikov
2021-08-05 17:00 ` Peter Zijlstra
2021-08-17 15:15 ` Eugene Syromiatnikov
2021-08-17 15:52 ` Peter Zijlstra
2021-08-17 23:17 ` Eugene Syromiatnikov
2021-08-19 11:09 ` [PATCH] sched: Fix Core-wide rq->lock for uninitialized CPUs Peter Zijlstra
2021-08-19 15:50 ` Tao Zhou
2021-08-19 16:19 ` Eugene Syromiatnikov
2021-08-20 0:18 ` Josh Don
2021-08-20 10:02 ` Peter Zijlstra
2021-08-23 9:07 ` [tip: sched/urgent] " tip-bot2 for Peter Zijlstra
2021-04-22 12:05 ` [PATCH 19/19] kselftest: Add test for core sched prctl interface Peter Zijlstra
2021-05-12 10:28 ` [tip: sched/core] " tip-bot2 for Chris Hyser
2021-04-22 16:43 ` [PATCH 00/19] sched: Core Scheduling Don Hiatt
2021-04-22 17:29 ` Peter Zijlstra
2021-04-30 6:47 ` Ning, Hongyu
2021-05-06 10:29 ` Peter Zijlstra
2021-05-06 12:53 ` Ning, Hongyu
2021-05-07 18:02 ` Joel Fernandes
2021-05-10 16:16 ` Vincent Guittot
2021-05-11 7:00 ` Vincent Guittot
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210422123308.800048269@infradead.org \
--to=peterz@infradead.org \
--cc=chris.hyser@oracle.com \
--cc=joel@joelfernandes.org \
--cc=joshdon@google.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mgorman@suse.de \
--cc=mingo@kernel.org \
--cc=tglx@linutronix.de \
--cc=valentin.schneider@arm.com \
--cc=vincent.guittot@linaro.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.