scheduler fixes
cover scheduler fixes
The following changes since commit 1314bb58bbe2a2c146490c59986c511687543d3c:
Gregory Haskins (1):
sched: enhance the pre/post scheduling logic
are available in the git repository at:
git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git sched/updates
Gregory Haskins (2):
[RESEND] sched: Fully integrate cpus_active_map and root-domain code
sched: fix race in cpupri introduced by cpumask_var changes
kernel/sched.c | 2 +- kernel/sched_cpupri.c | 15 ++++++++++++++- kernel/sched_fair.c | 10 +++++++--- kernel/sched_rt.c | 7 ------- 4 files changed, 22 insertions(+), 12 deletions(-)
Regards,
-Greg
PATCH RESEND 1/2 sched: Fully integrate cpus_active_map and root-domain code
(Applies to 2.6.31-rc4)
[
This patch was originaly sent about a year ago, but got dropped presumably by accident. Here is the original thread.
http://lkml.org/lkml/2008/7/22/281
At that time, Peter and Max acked it. It has now been forward ported to the new cpumask interface. I will be so bold as to carry their acks forward since the basic logic is the same. However, a new acknowledgement, if they have the time to review, would be ideal.
I have tested this patch on a 4-way system using Max's recommended "echo 0|1 > cpu1/online" technique and it appears to work properly
]
What: Reflect "active" cpus in the rq->rd->online field, instead of the online_map.
Motivation: Things that use the root-domain code (such as cpupri) only care about cpus classified as "active" anyway. By synchronizing the root-domain state with the active map, we allow several optimizations.
For instance, we can remove an extra cpumask_and from the scheduler hotpath by utilizing rq->rd->online (since it is now a cached version of cpu_active_map & rq->rd->span).
---
kernel/sched.c | 2 +- kernel/sched_fair.c | 10 +++++++--- kernel/sched_rt.c | 7 ------- 3 files changed, 8 insertions(+), 11 deletions(-)
kernel/sched.c +1 -1
@@ -7874,7 +7874,7 @@ static void rq_attach_root(struct rq *rq, struct root_domain *rd) rq->rd = rd;cpumask_set_cpu (rq->cpu, rd->span); -if (cpumask_test_cpu (rq->cpu, cpu_online_mask)) +if (cpumask_test_cpu (rq->cpu, cpu_active_mask))set_rq_online (rq);spin_unlock_irqrestore (&rq->lock, flags);
kernel/sched_fair.c +7 -3
@@ -1040,17 +1040,21 @@ static void yield_task_fair(struct rq *rq)* search starts with cpus closest then further out as needed, * so we always favor a closer, idle cpu. * Domains may include CPUs that are not usable for migration, -* hence we need to mask them out (cpu_active_mask) +* hence we need to mask them out (rq->rd->online) * * Returns the CPU we should wake onto. */ #if defined(ARCH_HAS_SCHED_WAKE_IDLE ) + +#define cpu_rd_active (cpu, rq) cpumask_test_cpu(cpu, rq->rd->online) +static int wake_idle (int cpu,struct task_struct *p) {struct sched_domain *sd;int i;unsigned int chosen_wakeup_cpu;int this_cpu; +struct rq *task_rq =task_rq (p);/* * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu
@@ -1083,10 +1087,10 @@ static int wake_idle(int cpu, struct task_struct *p)for_each_domain (cpu, sd) {if ((sd->flags &SD_WAKE_IDLE ) || ((sd->flags &SD_WAKE_IDLE_FAR ) - && !task_hot (p,task_rq (p)->clock, sd))) { + && !task_hot (p, task_rq->clock, sd))) {for_each_cpu_and (i,sched_domain_span (sd), &p->cpus_allowed) { -if (cpu_active (i) &&idle_cpu (i)) { +if (cpu_rd_active (i, task_rq) &&idle_cpu (i)) {if (i !=task_cpu (p)) {schedstat_inc (p, se.nr_wakeups_idle);
kernel/sched_rt.c +0 -7
@@ -1173,13 +1173,6 @@ static int find_lowest_rq(struct task_struct *task)return -1 ;/* No targets found */ /* -* Only consider CPUs that are usable for migration. -* I guess we might want to change cpupri_find() to ignore those -* in the first place. -*/ -cpumask_and (lowest_mask, lowest_mask, cpu_active_mask); - -/* * At this point we have built a mask of cpus representing the * lowest priority tasks in the system. Now we want to elect * the best one based on our affinity and topology.
PATCH 2/2 sched: fix race in cpupri introduced by cpumask_var changes
In reply to Gregory Haskins[
Note: obsoletes c8cab1ddfafd112c82a69a6cc4ec608984eeac97, though it should be harmless to leave the old patch applied.
]
Background:
Several race conditions in the scheduler have cropped up recently, which Steven and I have tracked down using ftrace. The most recent one turns out to be a race in how the scheduler determines a suitable migration target for RT tasks, introduced recently with commit:
commit 68e74568fbe5854952355e942acca51f138096d9
Author: Rusty Russell <[email protected]>
Date: Tue Nov 25 02:35:13 2008 +1030
sched: convert struct cpupri_vec cpumask_var_t.
The original design of cpupri allowed lockless readers to quickly determine a best-estimate target. Races between the pri_active bitmap and the vec->mask were handled in the original code because we would detect and return "0" when this occured. The design was predicated on the *effective* atomicity (*) of caching the result of cpus_and() between the cpus_allowed and the vec->mask.
Commit 68e74568 changed the behavior such that vec->mask is accessed multiple times. This introduces a subtle race, the result of which means we can have a result that returns "1", but with an empty bitmap.
*) yes, we know cpus_and() is not a locked operator across the entire
composite array, but it is implicitly atomic on a per-word basis which is all the design required to work.
Implementation:
Rather than forgoing the lockless design, or reverting to a stack-based cpumask_t, we simply check for when the race has been encountered and continue processing in the event that the race is hit. This renders the removal race as if the priority bit had been atomically cleared as well, and allows the algorithm to execute correctly.
---
kernel/sched_cpupri.c | 15 ++++++++++++++- 1 files changed, 14 insertions(+), 1 deletions(-)
kernel/sched_cpupri.c +14 -1
@@ -81,8 +81,21 @@ int cpupri_find(struct cpupri *cp, struct task_struct *p,if (cpumask_any_and (&p->cpus_allowed, vec->mask) >= nr_cpu_ids)continue ; -if (lowest_mask) +if (lowest_mask) {cpumask_and (lowest_mask, &p->cpus_allowed, vec->mask); + +/* +* We have to ensure that we have at least one bit +* still set in the array, since the map could have +* been concurrently emptied between the first and +* second reads of vec->mask. If we hit this +* condition, simply act as though we never hit this +* priority level and continue on. +*/ +if (cpumask_any (lowest_mask) >= nr_cpu_ids) +continue ; + } +return 1 ; }
Re: [PATCH 1/2] [RESEND] sched: Fully integrate cpus_active_map and root-domain code
In reply to Gregory HaskinsQuoted 80 lines · Gregory Haskins
(Applies to 2.6.31-rc4)
[
This patch was originaly sent about a year ago, but got dropped presumably by accident. Here is the original thread.http://lkml.org/lkml/2008/7/22/281
At that time, Peter and Max acked it. It has now been forward ported to the new cpumask interface. I will be so bold as to carry their acks forward since the basic logic is the same. However, a new acknowledgement, if they have the time to review, would be ideal.
I have tested this patch on a 4-way system using Max's recommended "echo 0|1 > cpu1/online" technique and it appears to work properly
]What: Reflect "active" cpus in the
rq->rd->onlinefield, instead of theonline_map.Motivation: Things that use the root-domain code (such as cpupri) only care about cpus classified as "active" anyway. By synchronizing the root-domain state with the active map, we allow several optimizations.
For instance, we can remove an extra
cpumask_andfrom the scheduler hotpath by utilizingrq->rd->online(since it is now a cached version ofcpu_active_map&rq->rd->span).Signed-off-by Gregory Haskins <[email protected]>Acked-by Peter Zijlstra <[email protected]>Acked-by Max Krasnyansky <[email protected]>---
kernel/sched.c | 2 +- kernel/sched_fair.c | 10 +++++++--- kernel/sched_rt.c | 7 ------- 3 files changed, 8 insertions(+), 11 deletions(-)kernel/sched.c +1
-1@@ -7874,7 +7874,7 @@ static void rq_attach_root(struct rq *rq, struct root_domain *rd) rq->rd = rd;cpumask_set_cpu (rq->cpu, rd->span); -if (cpumask_test_cpu (rq->cpu, cpu_online_mask)) +if (cpumask_test_cpu (rq->cpu, cpu_active_mask))set_rq_online (rq);spin_unlock_irqrestore (&rq->lock, flags);kernel/sched_fair.c +5
-1@@ -1040,17 +1040,21 @@ static void yield_task_fair(struct rq *rq)* search starts with cpus closest then further out as needed, * so we always favor a closer, idle cpu. * Domains may include CPUs that are not usable for migration, -* hence we need to mask them out (cpu_active_mask) +* hence we need to mask them out (rq->rd->online) * * Returns the CPU we should wake onto. */ #if defined(ARCH_HAS_SCHED_WAKE_IDLE ) + +#define cpu_rd_active (cpu, rq) cpumask_test_cpu(cpu, rq->rd->online) +static int wake_idle (int cpu,struct task_struct *p) {struct sched_domain *sd;int i;unsigned int chosen_wakeup_cpu;int this_cpu; +struct rq *task_rq =task_rq (p);/* * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu
kernel/sched_fair.c static int wake_idle(int cpu, struct task_struct *p) · line 1092
Quoted 7 lines
kernel/sched_fair.c +1
-1@@ -1083,10 +1087,10 @@ static int wake_idle(int cpu, struct task_struct *p)for_each_domain (cpu, sd) {if ((sd->flags &SD_WAKE_IDLE ) || ((sd->flags &SD_WAKE_IDLE_FAR ) - && !task_hot (p,task_rq (p)->clock, sd))) { + && !task_hot (p, task_rq->clock, sd))) {for_each_cpu_and (i,sched_domain_span (sd), &p->cpus_allowed) {
Hmm, something got suboptimal in translation from the original patch.
This would be better expressed as:
for_each_cpu_and(i, rq->rd->online, &p->cpus_allowed) {
if (idle_cpu(i)...
}Quoted 29 lines
kernel/sched_fair.c +1
-1-if (cpu_active (i) &&idle_cpu (i)) { +if (cpu_rd_active (i, task_rq) &&idle_cpu (i)) {if (i !=task_cpu (p)) {schedstat_inc (p, se.nr_wakeups_idle);kernel/sched_rt.c +0
-8@@ -1173,13 +1173,6 @@ static int find_lowest_rq(struct task_struct *task)return -1 ;/* No targets found */ /* -* Only consider CPUs that are usable for migration. -* I guess we might want to change cpupri_find() to ignore those -* in the first place. -*/ -cpumask_and (lowest_mask, lowest_mask, cpu_active_mask); - -/* * At this point we have built a mask of cpus representing the * lowest priority tasks in the system. Now we want to elect * the best one based on our affinity and topology. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/2] [RESEND] sched: Fully integrate cpus_active_map and root-domain code
Quoted 91 lines · Gregory Haskins
Quoted 80 lines · Gregory Haskins
(Applies to 2.6.31-rc4)
[
This patch was originaly sent about a year ago, but got dropped presumably by accident. Here is the original thread.http://lkml.org/lkml/2008/7/22/281
At that time, Peter and Max acked it. It has now been forward ported to the new cpumask interface. I will be so bold as to carry their acks forward since the basic logic is the same. However, a new acknowledgement, if they have the time to review, would be ideal.
I have tested this patch on a 4-way system using Max's recommended "echo 0|1 > cpu1/online" technique and it appears to work properly
]What: Reflect "active" cpus in the
rq->rd->onlinefield, instead of theonline_map.Motivation: Things that use the root-domain code (such as cpupri) only care about cpus classified as "active" anyway. By synchronizing the root-domain state with the active map, we allow several optimizations.
For instance, we can remove an extra
cpumask_andfrom the scheduler hotpath by utilizingrq->rd->online(since it is now a cached version ofcpu_active_map&rq->rd->span).Signed-off-by Gregory Haskins <[email protected]>Acked-by Peter Zijlstra <[email protected]>Acked-by Max Krasnyansky <[email protected]>---
kernel/sched.c | 2 +- kernel/sched_fair.c | 10 +++++++--- kernel/sched_rt.c | 7 ------- 3 files changed, 8 insertions(+), 11 deletions(-)kernel/sched.c +1
-1@@ -7874,7 +7874,7 @@ static void rq_attach_root(struct rq *rq, struct root_domain *rd) rq->rd = rd;cpumask_set_cpu (rq->cpu, rd->span); -if (cpumask_test_cpu (rq->cpu, cpu_online_mask)) +if (cpumask_test_cpu (rq->cpu, cpu_active_mask))set_rq_online (rq);spin_unlock_irqrestore (&rq->lock, flags);kernel/sched_fair.c +5
-1@@ -1040,17 +1040,21 @@ static void yield_task_fair(struct rq *rq)* search starts with cpus closest then further out as needed, * so we always favor a closer, idle cpu. * Domains may include CPUs that are not usable for migration, -* hence we need to mask them out (cpu_active_mask) +* hence we need to mask them out (rq->rd->online) * * Returns the CPU we should wake onto. */ #if defined(ARCH_HAS_SCHED_WAKE_IDLE ) + +#define cpu_rd_active (cpu, rq) cpumask_test_cpu(cpu, rq->rd->online) +static int wake_idle (int cpu,struct task_struct *p) {struct sched_domain *sd;int i;unsigned int chosen_wakeup_cpu;int this_cpu; +struct rq *task_rq =task_rq (p);/* * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu kernel/sched_fair.c static int wake_idle(int cpu, struct task_struct *p) · line 1092
Quoted 7 lines
kernel/sched_fair.c +1
-1@@ -1083,10 +1087,10 @@ static int wake_idle(int cpu, struct task_struct *p)for_each_domain (cpu, sd) {if ((sd->flags &SD_WAKE_IDLE ) || ((sd->flags &SD_WAKE_IDLE_FAR ) - && !task_hot (p,task_rq (p)->clock, sd))) { + && !task_hot (p, task_rq->clock, sd))) {for_each_cpu_and (i,sched_domain_span (sd), &p->cpus_allowed) {Hmm, something got suboptimal in translation from the original patch.
Quoted 5 lines
This would be better expressed as:
for_each_cpu_and(i, rq->rd->online, &p->cpus_allowed) { if (idle_cpu(i)... }
NM. My first instinct was correct.
We need the result of sd->span, cpus_allowed, and active_map. The submitted logic (or the original) is correct, and my comment above is wrong.
Sorry for the noise,
-Greg
[tip:sched/core] sched: Fix race in cpupri introduced by cpumask_var changes
In reply to Gregory HaskinsCommit-ID: 07903af152b0597d94e9b0030746b63c4664e787 Gitweb: http://git.kernel.org/tip/07903af152b0597d94e9b0030746b63c4664e787 Author: Gregory Haskins <[email protected]> AuthorDate: Thu, 30 Jul 2009 10:57:28 -0400 Committer: Ingo Molnar <[email protected]> CommitDate: Sun, 2 Aug 2009 14:23:29 +0200
sched: Fix race in cpupri introduced by cpumask_var changes
Background:
Several race conditions in the scheduler have cropped up recently, which Steven and I have tracked down using ftrace. The most recent one turns out to be a race in how the scheduler determines a suitable migration target for RT tasks, introduced recently with commit:
commit 68e74568fbe5854952355e942acca51f138096d9
Date: Tue Nov 25 02:35:13 2008 +1030
sched: convert struct cpupri_vec cpumask_var_t.The original design of cpupri allowed lockless readers to quickly determine a best-estimate target. Races between the pri_active bitmap and the vec->mask were handled in the original code because we would detect and return "0" when this occured. The design was predicated on the *effective* atomicity (*) of caching the result of cpus_and() between the cpus_allowed and the vec->mask.
Commit 68e74568 changed the behavior such that vec->mask is accessed multiple times. This introduces a subtle race, the result of which means we can have a result that returns "1", but with an empty bitmap.
*) yes, we know cpus_and() is not a locked operator across the
entire composite array, but it is implicitly atomic on a per-word basis which is all the design required to work.
Implementation:
Rather than forgoing the lockless design, or reverting to a stack-based cpumask_t, we simply check for when the race has been encountered and continue processing in the event that the race is hit. This renders the removal race as if the priority bit had been atomically cleared as well, and allows the algorithm to execute correctly.
LKML-Reference: <[email protected]>
--- kernel/sched_cpupri.c | 15 ++++++++++++++- 1 files changed, 14 insertions(+), 1 deletions(-)
kernel/sched_cpupri.c +14 -1
@@ -81,8 +81,21 @@ int cpupri_find(struct cpupri *cp, struct task_struct *p,if (cpumask_any_and (&p->cpus_allowed, vec->mask) >= nr_cpu_ids)continue ; -if (lowest_mask) +if (lowest_mask) {cpumask_and (lowest_mask, &p->cpus_allowed, vec->mask); + +/* +* We have to ensure that we have at least one bit +* still set in the array, since the map could have +* been concurrently emptied between the first and +* second reads of vec->mask. If we hit this +* condition, simply act as though we never hit this +* priority level and continue on. +*/ +if (cpumask_any (lowest_mask) >= nr_cpu_ids) +continue ; + } +return 1 ; }
[tip:sched/core] sched: Fully integrate cpus_active_map and root-domain code
In reply to Gregory HaskinsCommit-ID: 00aec93d10a051ea64f83eff75d4065a19508ea6 Gitweb: http://git.kernel.org/tip/00aec93d10a051ea64f83eff75d4065a19508ea6 Author: Gregory Haskins <[email protected]> AuthorDate: Thu, 30 Jul 2009 10:57:23 -0400 Committer: Ingo Molnar <[email protected]> CommitDate: Sun, 2 Aug 2009 14:26:12 +0200
sched: Fully integrate cpus_active_map and root-domain code
Reflect "active" cpus in the rq->rd->online field, instead of the online_map.
The motivation is that things that use the root-domain code (such as cpupri) only care about cpus classified as "active" anyway. By synchronizing the root-domain state with the active map, we allow several optimizations.
For instance, we can remove an extra cpumask_and from the scheduler hotpath by utilizing rq->rd->online (since it is now a cached version of cpu_active_map & rq->rd->span).
LKML-Reference: <[email protected]>
--- kernel/sched.c | 2 +- kernel/sched_fair.c | 10 +++++++--- kernel/sched_rt.c | 7 ------- 3 files changed, 8 insertions(+), 11 deletions(-)
kernel/sched.c +1 -1
@@ -7927,7 +7927,7 @@ static void rq_attach_root(struct rq *rq, struct root_domain *rd) rq->rd = rd;cpumask_set_cpu (rq->cpu, rd->span); -if (cpumask_test_cpu (rq->cpu, cpu_online_mask)) +if (cpumask_test_cpu (rq->cpu, cpu_active_mask))set_rq_online (rq);spin_unlock_irqrestore (&rq->lock, flags);
kernel/sched_fair.c +7 -3
@@ -1046,17 +1046,21 @@ static void yield_task_fair(struct rq *rq)* search starts with cpus closest then further out as needed, * so we always favor a closer, idle cpu. * Domains may include CPUs that are not usable for migration, -* hence we need to mask them out (cpu_active_mask) +* hence we need to mask them out (rq->rd->online) * * Returns the CPU we should wake onto. */ #if defined(ARCH_HAS_SCHED_WAKE_IDLE ) + +#define cpu_rd_active (cpu, rq) cpumask_test_cpu(cpu, rq->rd->online) +static int wake_idle (int cpu,struct task_struct *p) {struct sched_domain *sd;int i;unsigned int chosen_wakeup_cpu;int this_cpu; +struct rq *task_rq =task_rq (p);/* * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu
@@ -1089,10 +1093,10 @@ static int wake_idle(int cpu, struct task_struct *p)for_each_domain (cpu, sd) {if ((sd->flags &SD_WAKE_IDLE ) || ((sd->flags &SD_WAKE_IDLE_FAR ) - && !task_hot (p,task_rq (p)->clock, sd))) { + && !task_hot (p, task_rq->clock, sd))) {for_each_cpu_and (i,sched_domain_span (sd), &p->cpus_allowed) { -if (cpu_active (i) &&idle_cpu (i)) { +if (cpu_rd_active (i, task_rq) &&idle_cpu (i)) {if (i !=task_cpu (p)) {schedstat_inc (p, se.nr_wakeups_idle);
kernel/sched_rt.c +0 -7
@@ -1173,13 +1173,6 @@ static int find_lowest_rq(struct task_struct *task)return -1 ;/* No targets found */ /* -* Only consider CPUs that are usable for migration. -* I guess we might want to change cpupri_find() to ignore those -* in the first place. -*/ -cpumask_and (lowest_mask, lowest_mask, cpu_active_mask); - -/* * At this point we have built a mask of cpus representing the * lowest priority tasks in the system. Now we want to elect * the best one based on our affinity and topology.