NULL pointer dereference in pick_next_task_fair
Hi all,
The following issue has been observed with 5.4-rc*-based android kernels both on an x86 VM and native arm64:
---8<---
[ 222.515957] BUG: kernel NULL pointer dereference, address: 0000000000000040 [ 222.518871] #PF: supervisor read access in kernel mode [ 222.518871] #PF: error_code(0x0000) - not-present page [ 222.518871] PGD 800000007cdf7067 P4D 800000007cdf7067 PUD 7c868067 PMD 0 [ 222.518871] Oops: 0000 [#1] PREEMPT SMP PTI [ 222.518871] CPU: 2 PID: 0 Comm: swapper/2 Not tainted 5.4.0-rc4-mainline-g6a9b34166c05 #1 [ 222.518871] Hardware name: ChromiumOS crosvm, BIOS 0 [ 222.518871] RIP: 0010:set_next_entity+0xf/0xf0 [ 222.518871] Code: 42 0b e5 85 31 c0 e8 90 1a fc ff 0f 0b eb 9b 66 90 66 2e 0f 1f 84 00 00 00 00 00 55 48 89 e5 41 57 41 56 53 48 89 f3 49 89 fe <83> 7e 40 00 74 3d 4c 89 f7 48 89 de e8 80 f9 ff ff 4c 8d 7b 18 4d [ 222.518871] RSP: 0018:ffffb95040073de8 EFLAGS: 00010046 [ 222.518871] RAX: 0000000000000000 RBX: 0000000000000000 RCX: ffffffff85ec0c30 [ 222.518871] RDX: 0000000000000000 RSI: 0000000000000000 RDI: ffff9ec44c728500 [ 222.518871] RBP: ffffb95040073e00 R08: 0000000000000000 R09: 0000000000000000 [ 222.518871] R10: 0000000000000000 R11: ffffffff84ef0a30 R12: 0000000000000000 [ 222.518871] R13: 0000000000000000 R14: ffff9ec44c728500 R15: ffffb95040073e60 [ 222.518871] FS: 0000000000000000(0000) GS:ffff9ec44c700000(0000) knlGS:0000000000000000 [ 222.518871] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 222.518871] CR2: 0000000000000040 CR3: 000000007c87a002 CR4: 00000000003606e0 [ 222.518871] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 222.518871] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 222.518871] Call Trace: [ 222.518871] pick_next_task_fair+0xe8/0x410 [ 222.518871] ? rcu_note_context_switch+0x3ef/0x520 [ 222.518871] ? finish_task_switch+0x10d/0x250 [ 222.518871] __schedule+0x1f8/0x6e0 [ 222.518871] schedule_idle+0x27/0x40 [ 222.518871] do_idle+0x21c/0x240 [ 222.518871] cpu_startup_entry+0x25/0x30 [ 222.518871] start_secondary+0x18d/0x1b0 [ 222.518871] secondary_startup_64+0xa4/0xb0 [ 222.518871] Modules linked in: vmw_vsock_virtio_transport vmw_vsock_virtio_transport_common vsock_diag vsock can_raw can snd_intel8x0 snd_ac97_codec ac97_bus virtio_input virtio_pci virtio_mmio virtio_crypto mmc_block mmc_core dummy_cpufreq rtc_test dummy_hcd can_dev vcan virtio_net net_failover failover virt_wifi virtio_blk virtio_gpu ttm virtio_rng virtio_ring virtio 8250_of crypto_engine [ 222.518871] CR2: 0000000000000040 [ 222.518871] ---[ end trace ae741809965b22f2 ]--- [ 222.518871] RIP: 0010:set_next_entity+0xf/0xf0 [ 222.518871] Code: 42 0b e5 85 31 c0 e8 90 1a fc ff 0f 0b eb 9b 66 90 66 2e 0f 1f 84 00 00 00 00 00 55 48 89 e5 41 57 41 56 53 48 89 f3 49 89 fe <83> 7e 40 00 74 3d 4c 89 f7 48 89 de e8 80 f9 ff ff 4c 8d 7b 18 4d [ 222.518871] RSP: 0018:ffffb95040073de8 EFLAGS: 00010046 [ 222.518871] RAX: 0000000000000000 RBX: 0000000000000000 RCX: ffffffff85ec0c30 [ 222.518871] RDX: 0000000000000000 RSI: 0000000000000000 RDI: ffff9ec44c728500 [ 222.518871] RBP: ffffb95040073e00 R08: 0000000000000000 R09: 0000000000000000 [ 222.518871] R10: 0000000000000000 R11: ffffffff84ef0a30 R12: 0000000000000000 [ 222.518871] R13: 0000000000000000 R14: ffff9ec44c728500 R15: ffffb95040073e60 [ 222.518871] FS: 0000000000000000(0000) GS:ffff9ec44c700000(0000) knlGS:0000000000000000 [ 222.518871] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 222.518871] CR2: 0000000000000040 CR3: 000000007c87a002 CR4: 00000000003606e0 [ 222.518871] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 222.518871] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 222.518871] Kernel panic - not syncing: Fatal exception [ 222.518871] Kernel Offset: 0x3e00000 from 0xffffffff81000000 (relocation range: 0xffffffff80000000-0xffffffffbfffffff)
--->8---
The issue is very transient and relatively hard to reproduce.
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that pick_next_entity() returns a NULL se in the 'simple' path of pick_next_task_fair(), which causes obvious problems in the subsequent call to set_next_entity().
I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 6 lines · Quentin Perret
The issue is very transient and relatively hard to reproduce.
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")
Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
The only way for pick_next_entity() to return NULL is if the tree is empty and !cfs_rq->curr. But in that case, cfs_rq->nr_running _should_ be 0 and or it's related se should not be enqueued in the parent cfs_rq.
Now for the root cfs_rq we check nr_running this and jump to the idle path, however if this occurs in the middle of the hierarchy, we're up a creek without no paddles. This is something that really should not happen (because empty cfs_rq should not be enqueued)
Also, if we take the simple patch, as you say, then we'll have done a put_prev_task(), regardless of how we got there, so we know cfs_rq->curr must be NULL. Which, with the above, means the tree really is empty.
And as stated above, when the tree is empty and !cfs_rq->curr, the cfs_rq's se should not be enqueued in the parent cfs_rq so we should not be getting here.
Clearly something is buggered with the cgroup state. What is your cgroup setup, are you using cpu-bandwidth?
Peter Zijlstra
maintainerQuoted 6 lines · Quentin Perret
The issue is very transient and relatively hard to reproduce.
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")
Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
Can you please see if this makes any difference?
--- kernel/sched/core.c | 6 ++++-- kernel/sched/fair.c | 2 +- kernel/sched/idle.c | 3 +-- 3 files changed, 6 insertions(+), 5 deletions(-)
kernel/sched/core.c +4 -2
@@ -3922,8 +3922,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) goto restart;/* Assumes fair_sched_class->next == idle_sched_class */ -if (unlikely (!p)) - p = idle_sched_class.pick_next_task (rq, prev, rf); +if (unlikely (!p)) { + prev->sched_class->put_prev_task (rq, prev, rf); + p = idle_sched_class.pick_next_task (rq,NULL ,NULL ); + }return p; }
kernel/sched/fair.c +1 -1
@@ -6820,7 +6820,7 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf simple: #endif if (prev) - put_prev_task(rq, prev); + prev->sched_class->put_prev_task(rq, prev, rf); do { se = pick_next_entity(cfs_rq, NULL);
kernel/sched/idle.c +1 -2
@@ -390,8 +390,7 @@ pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf {struct task_struct *next = rq->idle; -if (prev) -put_prev_task (rq, prev); +WARN_ON_ONCE (prev || rf);set_next_task_idle (rq, next);
Quoted 59 lines · Peter Zijlstra
Quoted 6 lines · Quentin Perret
The issue is very transient and relatively hard to reproduce.
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
Can you please see if this makes any difference?
--- kernel/sched/core.c | 6 ++++-- kernel/sched/fair.c | 2 +- kernel/sched/idle.c | 3 +-- 3 files changed, 6 insertions(+), 5 deletions(-)kernel/sched/core.c +4
-2@@ -3922,8 +3922,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) goto restart;/* Assumes fair_sched_class->next == idle_sched_class */ -if (unlikely (!p)) - p = idle_sched_class.pick_next_task (rq, prev, rf); +if (unlikely (!p)) { + prev->sched_class->put_prev_task (rq, prev, rf); + p = idle_sched_class.pick_next_task (rq,NULL ,NULL ); + }return p; }kernel/sched/fair.c +1
-1@@ -6820,7 +6820,7 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf simple: #endif if (prev) - put_prev_task(rq, prev); + prev->sched_class->put_prev_task(rq, prev, rf); do { se = pick_next_entity(cfs_rq, NULL);kernel/sched/idle.c +0
-0
kernel/sched/idle.c pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf · line 396
Quoted 9 lines
kernel/sched/idle.c +1
-2@@ -390,8 +390,7 @@ pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf {struct task_struct *next = rq->idle; -if (prev) -put_prev_task (rq, prev); +WARN_ON_ONCE (prev || rf);set_next_task_idle (rq, next);
Unfortunately the issue went into hiding this morning and I struggle to reproduce it (this is turning bordeline nightmare now TBH).
I'll try the patch once my reproducer is fixed :/
Thank you very much for the help,
Quentin
Quoted 74 lines · Quentin Perret' via kernel-team
Quoted 59 lines · Peter Zijlstra
Quoted 6 lines · Quentin Perret
The issue is very transient and relatively hard to reproduce.
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
Can you please see if this makes any difference?
--- kernel/sched/core.c | 6 ++++-- kernel/sched/fair.c | 2 +- kernel/sched/idle.c | 3 +-- 3 files changed, 6 insertions(+), 5 deletions(-)kernel/sched/core.c +4
-2@@ -3922,8 +3922,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) goto restart;/* Assumes fair_sched_class->next == idle_sched_class */ -if (unlikely (!p)) - p = idle_sched_class.pick_next_task (rq, prev, rf); +if (unlikely (!p)) { + prev->sched_class->put_prev_task (rq, prev, rf); + p = idle_sched_class.pick_next_task (rq,NULL ,NULL ); + }return p; }kernel/sched/fair.c +1
-1@@ -6820,7 +6820,7 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf simple: #endif if (prev) - put_prev_task(rq, prev); + prev->sched_class->put_prev_task(rq, prev, rf); do { se = pick_next_entity(cfs_rq, NULL);kernel/sched/idle.c +0
-0kernel/sched/idle.c pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf · line 396
Quoted 9 lines
kernel/sched/idle.c +1
-2@@ -390,8 +390,7 @@ pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf {struct task_struct *next = rq->idle; -if (prev) -put_prev_task (rq, prev); +WARN_ON_ONCE (prev || rf);set_next_task_idle (rq, next);Unfortunately the issue went into hiding this morning and I struggle to reproduce it (this is turning bordeline nightmare now TBH).
Quoted 8 lines
I'll try the patch once my reproducer is fixed :/
Thank you very much for the help,
Quentin--
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
Quentin and I were able to create a setup which reproduces the issue.
Given this, I tried Peter's proposed fix and was still able to reproduce the issue unfortunately. Current patch is located here -
https://android-review.googlesource.com/c/kernel/common/+/1153487
Our mitigation for this issue on the android-mainline branch has been to revert 67692435c411 ("sched: Rework pick_next_task() slow-path").
https://android-review.googlesource.com/c/kernel/common/+/1152564
I'll spend some time detailing repro steps next. I should be able to provide an update on those details early next week.
We appreciate the help so far.
Thanks,
Ram
Quoted 11 lines · Ram Muthiah
Quentin and I were able to create a setup which reproduces the issue.
Given this, I tried Peter's proposed fix and was still able to reproduce the issue unfortunately. Current patch is located here -
https://android-review.googlesource.com/c/kernel/common/+/1153487Our mitigation for this issue on the android-mainline branch has been to revert
67692435c411("sched: Reworkpick_next_task()slow-path").
https://android-review.googlesource.com/c/kernel/common/+/1152564
Quoted 7 lines
I'll spend some time detailing repro steps next. I should be able to provide an update on those details early next week.
We appreciate the help so far.
Thanks,
Ram
The splat Quentin posted happens at secondary startup, is that always the case? I'm trying to think of what could make rq.cfs_rq.nr_running non-zero at secondary bringup time. It might not explain the NULL pointer, but I'm still curious as to how we can get something there this early, as it could point towards something. Be warned, I might bring up stuff I know nothing about, but this looks "fun" so I can't help myself :)
sched domains are only setup after smp_init() in sched_init_smp(), thus after we've booted all secondaries. This should take load balance out of the picture.
For wakeups, select_task_rq_fair() can only ever pick prev_cpu or this_cpu since there are no sched domains. I don't see many candidates that could wakeup on a secondary (thus have non-zero this_cpu) this early there. Perhaps the smpboot threads, but from a quick look they are first created *after* sched_init_smp(), so they couldn't exist during (boot-time) secondary bringup. Seems to be the same for IRQ threads (and they're setscheduler'd to FIFO anyway).
So now I'm even more curious as to what CFS task could be enqueued on a secondary CPU rq before sched_init_smp(). Have you been sending stuff to space without any shielding lately?
Quoted 5 lines · Valentin Schneider
For wakeups,
select_task_rq_fair()can only ever pickprev_cpuorthis_cpusince there are no sched domains. I don't see many candidates that could wakeup on a secondary (thus have non-zerothis_cpu) this early there. Perhaps the smpboot threads, but from a quick look they are first created *after*sched_init_smp(), so they couldn't exist during (boot-time) secondary bringup.
Scratch that, I can't read. The registration is done in early initcalls (and we have the unpark in the secondary bringup anyway), so when we spool up the secondaries we'll get wakeups for the smpboot threads. AFAIR only softirqd and cpuhp are CFS, but while this satisfied some of my curiosity this doesn't seem super helpful on its own.
Quoted 7 lines
Seems to be the same for IRQ threads (and they're setscheduler'd to FIFO anyway).
So now I'm even more curious as to what CFS task could be enqueued on a secondary CPU rq before
sched_init_smp(). Have you been sending stuff to space without any shielding lately?
Quoted 4 lines · Valentin Schneider
Quoted 3 lines · Valentin Schneider
For wakeups,
select_task_rq_fair()can only ever pickprev_cpuorthis_cpusince there are no sched domains. I don't see many candidates that could wakeup on a secondary (thus have non-zerothis_cpu) this early there.
And another fail here, this doesn't have to be at secondary bringup, it's just that the bringup will always be in the idle task's callstack (if the timestamps weren't enough of a clue already). I guess I'll stop writing nonsense and keep staring in silence.
Quoted 10 lines · Ram Muthiah
Quentin and I were able to create a setup which reproduces the issue.
Given this, I tried Peter's proposed fix and was still able to reproduce the issue unfortunately. Current patch is located here -
https://android-review.googlesource.com/c/kernel/common/+/1153487Our mitigation for this issue on the android-mainline branch has been to revert
67692435c411("sched: Reworkpick_next_task()slow-path").
https://android-review.googlesource.com/c/kernel/common/+/1152564
Still no cigar, but one thing to note is that we got a similar splat on a Juno just yesterday, here it is fed through decode_stacktrace.sh:
[ 22.930829] Mem abort info: [ 22.935904] ESR = 0x96000006 [ 22.938924] EC = 0x25: DABT (current EL), IL = 32 bits [ 22.944178] SET = 0, FnV = 0 [ 22.947197] EA = 0, S1PTW = 0 [ 22.950300] Data abort info: [ 22.953145] ISV = 0, ISS = 0x00000006 [ 22.956937] CM = 0, WnR = 0 [ 22.959870] user pgtable: 4k pages, 48-bit VAs, pgdp=00000009f3905000 [ 22.966243] [0000000000000040] pgd=00000009efa6e003, pud=00000009f41c3003, pmd=0000000000000000 [ 22.974858] Internal error: Oops: 96000006 [#1] PREEMPT SMP [ 22.980369] Modules linked in: tda998x drm_kms_helper drm crct10dif_ce ip_tables x_tables ipv6 nf_defrag_ipv6 [ 22.990200] CPU: 1 PID: 0 Comm: swapper/1 Not tainted 5.4.0-rc2-00001-gaa57157be69f #1 [ 22.998036] Hardware name: ARM LTD ARM Juno Development Platform/ARM Juno Development Platform, BIOS EDK II Oct 19 2018 [ 23.008710] pstate: 60000085 (nZCv daIf -PAN -UAO) [ 23.013457] pc : set_next_entity (kernel/sched/fair.c:4156) [ 23.017511] lr : pick_next_task_fair (kernel/sched/fair.c:6829 (discriminator 1)) [ 23.021991] sp : ffff800011a13e10 [ 23.025267] x29: ffff800011a13e10 x28: 0000000000000000 [ 23.030525] x27: ffff800011a13f10 x26: ffff800010c205ec [ 23.035782] x25: ffff000975cea108 x24: ffff800011789000 [ 23.041038] x23: ffff8000113cf000 x22: ffff000975ce9b80 [ 23.046294] x21: ffff00097ef78d40 x20: ffff000974e21a00 [ 23.051550] x19: 0000000000000000 x18: 0000000000000000 [ 23.056806] x17: 0000000000000000 x16: 0000000000000000 [ 23.062062] x15: 0000000000000000 x14: 00000000000001ad [ 23.067317] x13: 0000000000000001 x12: 071c71c71c71c71c [ 23.072573] x11: 0000000000000500 x10: ffff00097ef77dc8 [ 23.077829] x9 : 0000000000000087 x8 : ffff00097ef77de8 [ 23.083085] x7 : 0000000000000003 x6 : 0000000000000000 [ 23.088340] x5 : 0000000000000000 x4 : 0000000000000000 [ 23.093596] x3 : 000000054f6e7800 x2 : 0000000000000000 [ 23.098851] x1 : 0000000000000000 x0 : ffff000974e21a00 [ 23.104107] Call trace: [ 23.106527] set_next_entity (kernel/sched/fair.c:4156) [ 23.110236] pick_next_task_fair (kernel/sched/fair.c:6829 (discriminator 1)) [ 23.114377] __schedule (kernel/sched/core.c:3920 kernel/sched/core.c:4039) [ 23.117828] schedule_idle (kernel/sched/core.c:4165 (discriminator 1)) [ 23.121365] do_idle (./arch/arm64/include/asm/current.h:19 ./arch/arm64/include/asm/preempt.h:31 kernel/sched/idle.c:275) [ 23.124557] cpu_startup_entry (kernel/sched/idle.c:355 (discriminator 1)) [ 23.128439] secondary_start_kernel (arch/arm64/kernel/smp.c:262)
The faulty line is the very first se dereference in set_next_entity(). As Peter pointed out on IRC, this happens in the 'simple' path (prev is the idle task).
Peter Zijlstra
maintainer Tested-by Quentin Perret Tested-by Qais Yousef Tested-by Valentin Schneider Tested-by Dietmar EggemannQuoted 5 lines · Quentin Perret
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")
Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
So for all those who didn't follow along on IRC, the below seems to cure things.
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling put_prev_task(). I'll go audit the RT/DL cases.
---
Subject: sched: Fix pick_next_task() vs 'change' pattern race
From: Peter Zijlstra <[email protected]>
Date: Mon Nov 4 22:18:14 CET 2019
Commit 67692435c411 ("sched: Rework pick_next_task() slow-path") inadvertly introduced a race because it changed a previously unexplored dependency between dropping the rq->lock and sched_class::put_prev_task().
The comments about dropping rq->lock, in for example newidle_balance(), only mentions the task being current and ->on_cpu being set. But when we look at the 'change' pattern (in for example sched_setnuma()):
queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */ running = task_current(rq, p); /* rq->curr == p */ if (queued) dequeue_task(...); if (running) put_prev_task(...); /* change task properties */ if (queued) enqueue_task(...); if (running) set_next_task(...);
It becomes obvious that if we do this after put_prev_task() has already been called on @p, things go sideways. This is exactly what the commit in question allows to happen when it does:
prev->sched_class->put_prev_task(rq, prev, rf); if (!rq->nr_running) newidle_balance(rq, rf);
The newidle_balance() call will drop rq->lock after we've called put_prev_task() and that allows the above 'change' pattern to interleave and mess up the state.
The order in pick_next_task() is mandated by the fact that RT/DL put_prev_task() can pull other RT tasks, in which case we should not call newidle_balance() since we'll not be going idle. Similarly, we cannot put newidle_balance() in put_prev_task_fair() because it should be called every time we'll end up selecting the idle task.
Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse' p->on_cpu to carry more state. Adding more state to p->on_rq is possible but is far more invasive and also ends up duplicating much of the state we already carry in p->on_cpu.
Introduce task_on_rq_curr() to indicate the if sched_class::set_next_task() has been called -- and we thus need to call put_prev_task().
--- kernel/sched/core.c | 22 +++++++++++++++------- kernel/sched/sched.h | 16 ++++++++++++++++ 2 files changed, 31 insertions(+), 7 deletions(-)
kernel/sched/core.c +15 -7
@@ -1595,7 +1595,7 @@ void do_set_cpus_allowed(struct task_strlockdep_assert_held (&p->pi_lock); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued) {/*
@@ -3934,8 +3934,16 @@ pick_next_task(struct rq *rq, struct tas* can PULL higher prio tasks when we lower the RQ 'priority'. */ prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) +#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do +* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf); + } +#endif for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );
@@ -4422,7 +4430,7 @@ void rt_mutex_setprio(struct task_struct prev_class = p->sched_class; queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flag);if (running)
@@ -4509,7 +4517,7 @@ void set_user_nice(struct task_struct *p goto out_unlock; } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK );if (running)
@@ -4957,7 +4965,7 @@ static int __sched_setscheduler(struct t } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flags);if (running)
@@ -6141,7 +6149,7 @@ void sched_setnuma(struct task_struct *p rq =task_rq_lock (p, &rf); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE );
@@ -7031,7 +7039,7 @@ void sched_move_task(struct task_struct rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); + running =task_on_rq_curr (rq, tsk); queued =task_on_rq_queued (tsk);if (queued)
kernel/sched/sched.h +16 -0
@@ -1628,6 +1628,22 @@ static inline int task_running(struct rq#endif } +/* +* If true, @p has had sched_class::set_next_task() called on it. +* See pick_next_task(). +*/ +static inline bool task_on_rq_curr (struct rq *rq,struct task_struct *p) +{ +#ifdef CONFIG_SMP +return rq->curr == p && p->on_cpu ==1 ; +#else +return rq->curr == p; +#endif +} + +/* +* If true, @p has has sched_class::enqueue_task() called on it. +*/ static inline int task_on_rq_queued (struct task_struct *p) {return p->on_rq ==TASK_ON_RQ_QUEUED ;
Peter Zijlstra
maintainerQuoted 14 lines · Peter Zijlstra
Quoted 5 lines · Quentin Perret
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
Quoted 6 lines
So for all those who didn't follow along on IRC, the below seems to cure things.
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling
put_prev_task(). I'll go audit the RT/DL cases.
So I think it all works, but that's more by accident than anything else. I'll move the ->on_cpu=2 assignment earlier. That clearly avoids calling put_prev_task() while we're in put_prev_task().
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Peter Zijlstra
Quoted 5 lines · Quentin Perret
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
So for all those who didn't follow along on IRC, the below seems to cure things.
Quoted 7 lines
Quoted 3 lines
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling
put_prev_task(). I'll go audit the RT/DL cases.So I think it all works, but that's more by accident than anything else. I'll move the ->on_cpu=2 assignment earlier. That clearly avoids calling
put_prev_task()while we're input_prev_task().
Did you mean avoids calling *set_next_task()* while we're in put_prev_task()?
So what you're saying is that put_prev_task_{rt,dl}() could drop the rq_lock() too and the race could happen while we're inside these functions, correct? Or is it a different reason?
By the way, is all reads/writes to ->on_cpu happen when a lock is held? Ie: we don't need to use any smp read/write barriers?
Cheers
--
Qais Yousef
Quoted 105 lines · Peter Zijlstra
Quoted 5 lines · Quentin Perret
After digging a bit, the offending commit seems to be:
67692435c411 ("sched: Rework pick_next_task() slow-path")Quoted 7 lines
By 'offending' I mean that reverting it makes the issue go away. The issue comes from the fact that
pick_next_entity()returns a NULL se in the 'simple' path ofpick_next_task_fair(), which causes obvious problems in the subsequent call toset_next_entity().I'll dig more, but if anybody understands the issue in the meatime feel free to send me a patch to try out :)
So for all those who didn't follow along on IRC, the below seems to cure things.
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling
put_prev_task(). I'll go audit the RT/DL cases.---
Subject: sched: Fixpick_next_task()vs 'change' pattern race
From: Peter Zijlstra <[email protected]>
Date: Mon Nov 4 22:18:14 CET 2019Commit
67692435c411("sched: Reworkpick_next_task()slow-path") inadvertly introduced a race because it changed a previously unexplored dependency between dropping therq->lockandsched_class::put_prev_task().The comments about dropping
rq->lock, in for examplenewidle_balance(), only mentions the task being current and ->on_cpu being set. But when we look at the 'change' pattern (in for examplesched_setnuma()):queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */ running = task_current(rq, p); /* rq->curr == p */ if (queued) dequeue_task(...); if (running) put_prev_task(...); /* change task properties */ if (queued) enqueue_task(...); if (running) set_next_task(...);It becomes obvious that if we do this after
put_prev_task()has already been called on @p, things go sideways. This is exactly what the commit in question allows to happen when it does:prev->sched_class->put_prev_task(rq, prev, rf); if (!rq->nr_running) newidle_balance(rq, rf);The
newidle_balance()call will droprq->lockafter we've calledput_prev_task()and that allows the above 'change' pattern to interleave and mess up the state.The order in
pick_next_task()is mandated by the fact that RT/DLput_prev_task()can pull other RT tasks, in which case we should not callnewidle_balance()since we'll not be going idle. Similarly, we cannot putnewidle_balance()input_prev_task_fair()because it should be called every time we'll end up selecting the idle task.Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse'
p->on_cputo carry more state. Adding more state top->on_rqis possible but is far more invasive and also ends up duplicating much of the state we already carry inp->on_cpu.Introduce
task_on_rq_curr()to indicate the ifsched_class::set_next_task()has been called -- and we thus need to callput_prev_task().Fixes 67692435c411 ("sched: Rework pick_next_task() slow-path")Reported-by Quentin Perret <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by Quentin Perret <[email protected]>Tested-by Qais Yousef <[email protected]>Tested-by Valentin Schneider <[email protected]>Tested-by Dietmar Eggemann <[email protected]>--- kernel/sched/core.c | 22 +++++++++++++++------- kernel/sched/sched.h | 16 ++++++++++++++++ 2 files changed, 31 insertions(+), 7 deletions(-)kernel/sched/core.c +1
-1@@ -1595,7 +1595,7 @@ void do_set_cpus_allowed(struct task_strlockdep_assert_held (&p->pi_lock); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued) {/* @@ -3934,8 +3934,16 @@ pick_next_task(struct rq *rq, struct tas* can PULL higher prio tasks when we lower the RQ 'priority'. */
kernel/sched/core.c pick_next_task(struct rq *rq, struct tas · line 3944
Quoted 10 lines
kernel/sched/core.c +7
-1prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) +#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do +* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);
Shouldn't we restore prev->on_cpu = 1 after newidle_balance()? Can't prev become pickable again after newidle_balance() releases rq->lock, and we take it again, so this on_cpu == 2 never will be cleared?
Quoted 76 lines
kernel/sched/core.c +7
-5+ } +#endif for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );@@ -4422,7 +4430,7 @@ void rt_mutex_setprio(struct task_struct prev_class = p->sched_class; queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flag);if (running)@@ -4509,7 +4517,7 @@ void set_user_nice(struct task_struct *p goto out_unlock; } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK );if (running)@@ -4957,7 +4965,7 @@ static int __sched_setscheduler(struct t } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flags);if (running)@@ -6141,7 +6149,7 @@ void sched_setnuma(struct task_struct *p rq =task_rq_lock (p, &rf); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE );@@ -7031,7 +7039,7 @@ void sched_move_task(struct task_struct rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); + running =task_on_rq_curr (rq, tsk); queued =task_on_rq_queued (tsk);if (queued)kernel/sched/sched.h +16
-0@@ -1628,6 +1628,22 @@ static inline int task_running(struct rq#endif } +/* +* If true, @p has had sched_class::set_next_task() called on it. +* See pick_next_task(). +*/ +static inline bool task_on_rq_curr (struct rq *rq,struct task_struct *p) +{ +#ifdef CONFIG_SMP +return rq->curr == p && p->on_cpu ==1 ; +#else +return rq->curr == p; +#endif +} + +/* +* If true, @p has has sched_class::enqueue_task() called on it. +*/ static inline int task_on_rq_queued (struct task_struct *p) {return p->on_rq ==TASK_ON_RQ_QUEUED ;
Peter Zijlstra
maintainerQuoted 4 lines · Kirill Tkhai
Quoted 4 lines
kernel/sched/core.c +4
-0+#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do
Quoted 8 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct tas · line 3944
Quoted 4 lines
kernel/sched/core.c +3
-0+* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?
Indeed so.
Peter Zijlstra
maintainerQuoted 7 lines · Qais Yousef
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Peter Zijlstra
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling
put_prev_task(). I'll go audit the RT/DL cases.
Quoted 5 lines
Quoted 3 lines
So I think it all works, but that's more by accident than anything else. I'll move the ->on_cpu=2 assignment earlier. That clearly avoids calling
put_prev_task()while we're input_prev_task().Did you mean avoids calling *set_next_task()* while we're in
put_prev_task()?
Either, really. The change pattern does put_prev_task() first, and then restores state by calling set_next_task(). And it can do that while we're in put_prev_task(), unless we're setting ->on_cpu=2.
Quoted 3 lines
So what you're saying is that put_prev_task_{rt,dl}() could drop the
rq_lock()too and the race could happen while we're inside these functions, correct? Or is it a different reason?
Indeed, except it looks like that actually works (mostly by accident).
Quoted 2 lines
By the way, is all reads/writes to ->on_cpu happen when a lock is held? Ie: we don't need to use any smp read/write barriers?
Yes, ->on_cpu is fully serialized by rq->lock. We use smp_store_release() in finish_task() due to ttwu spin-waiting on it (which reminds me, riel was seeing lots of that).
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Qais Yousef
Quoted 9 lines · Peter Zijlstra
Quoted 3 lines · Peter Zijlstra
The only thing I'm now considering is if we shouldn't be setting ->on_cpu=2 _before_ calling
put_prev_task(). I'll go audit the RT/DL cases.So I think it all works, but that's more by accident than anything else. I'll move the ->on_cpu=2 assignment earlier. That clearly avoids calling
put_prev_task()while we're input_prev_task().
Quoted 5 lines
Quoted 1 line
Did you mean avoids calling *set_next_task()* while we're in
put_prev_task()?Either, really. The change pattern does
put_prev_task()first, and then restores state by callingset_next_task(). And it can do that while we're input_prev_task(), unless we're setting ->on_cpu=2.
*head starts spinning*
I can't see how we can have double put_prev_task() in a row. Let me stare more at the code.
Quoted 6 lines
Quoted 4 lines
So what you're saying is that put_prev_task_{rt,dl}() could drop the
rq_lock()too and the race could happen while we're inside these functions, correct? Or is it a different reason?Indeed, except it looks like that actually works (mostly by accident).
+1
I think I got it now, it's the double_lock_balance() that can drop the lock. It even has a comment above it!
Quoted 7 lines
Quoted 3 lines
By the way, is all reads/writes to ->on_cpu happen when a lock is held? Ie: we don't need to use any smp read/write barriers?
Yes, ->on_cpu is fully serialized by
rq->lock. We usesmp_store_release()infinish_task()due to ttwu spin-waiting on it (which reminds me, riel was seeing lots of that).
Thanks. I had to ask as it was hard to walk all the paths.
Sometimes I get tempted to sprinkle comments or lockdep_assert() but then I think that can easily get ugly and out of hand. I guess one just has to know the code.
Cheers
--
Qais Yousef
Peter Zijlstra
maintainerQuoted 14 lines · Peter Zijlstra
Quoted 4 lines · Kirill Tkhai
Quoted 4 lines
kernel/sched/core.c +4
-0+#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do Quoted 8 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct tas · line 3944
Quoted 4 lines
kernel/sched/core.c +3
-0+* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?
Quoted 1 line
Indeed so.
Oh wait, the way it was written this is not possible. Because rq->nr_running == 0 and prev->on_cpu > 0 it means the current task is going to sleep and cannot be woken back up.
But if I move the ->on_cpu=2 thing earlier, as I wrote I'd do, then yes, we have to set it back to 1. Because in that case we can get here for a spurious schedule and we'll pick the same task again.
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · Kirill Tkhai
kernel/sched/core.c pick_next_task(struct rq *rq, struct tas · line 3944
Quoted 8 lines
kernel/sched/core.c +7
-0+#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do +* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?
Quoted 5 lines
Quoted 1 line
Indeed so.
Oh wait, the way it was written this is not possible. Because
rq->nr_running== 0 andprev->on_cpu> 0 it means the current task is going to sleep and cannot be woken back up.
I mostly mean throttling. AFAIR, tasks of throttled rt_rq are not accounted in rq->nr_running. But it seems rt_rq may become unthrottled again after newidle_balance() unlocks rq lock, and prev will become pickable again.
Quoted 3 lines
But if I move the ->on_cpu=2 thing earlier, as I wrote I'd do, then yes, we have to set it back to 1. Because in that case we can get here for a spurious schedule and we'll pick the same task again.
Peter Zijlstra
maintainer Tested-by Quentin Perret Tested-by Qais Yousef Tested-by Valentin Schneider Tested-by Dietmar EggemannQuoted 18 lines · Kirill Tkhai
Quoted 17 lines · Peter Zijlstra
Quoted 15 lines · Peter Zijlstra
Quoted 4 lines · Kirill Tkhai
Quoted 4 lines
(quoted diff) +4
-0+#ifdef CONFIG_SMP + if (!rq->nr_running) { + /* + * Make sure task_on_rq_curr() fails, such that we don't doQuoted 8 lines
Review
Quoted 4 lines
(quoted diff) +3
-0+ * put_prev_task() + set_next_task() on this task again. + */ + prev->on_cpu = 2; newidle_balance(rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?Indeed so.
Quoted 7 lines
Quoted 3 lines
Oh wait, the way it was written this is not possible. Because
rq->nr_running== 0 andprev->on_cpu> 0 it means the current task is going to sleep and cannot be woken back up.I mostly mean throttling. AFAIR, tasks of throttled
rt_rqare not accounted inrq->nr_running. But it seemsrt_rqmay become unthrottled again afternewidle_balance()unlocks rq lock, and prev will become pickable again.
Urgh... throttling.
Bah.. I had just named the "->on_cpu = 2" thing leave_task(), to match prepare_task() and finish_task(), but when we have to flip it back to 1 that doesn't really work.
Also, I'm still flip-flopping on where to place it. Yesterday I suggested placing it before put_prev_task(), but then I went to write a comment, and either way around put_prev_task() needs to be very careful.
So I went back to placing it after and putting lots of comments on.
How does the below look?
---
Subject: sched: Fix pick_next_task() vs 'change' pattern race
From: Peter Zijlstra <[email protected]>
Date: Mon Nov 4 22:18:14 CET 2019
Commit 67692435c411 ("sched: Rework pick_next_task() slow-path") inadvertly introduced a race because it changed a previously unexplored dependency between dropping the rq->lock and sched_class::put_prev_task().
The comments about dropping rq->lock, in for example newidle_balance(), only mentions the task being current and ->on_cpu being set. But when we look at the 'change' pattern (in for example sched_setnuma()):
queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */ running = task_current(rq, p); /* rq->curr == p */ if (queued) dequeue_task(...); if (running) put_prev_task(...); /* change task properties */ if (queued) enqueue_task(...); if (running) set_next_task(...);
It becomes obvious that if we do this after put_prev_task() has already been called on @p, things go sideways. This is exactly what the commit in question allows to happen when it does:
prev->sched_class->put_prev_task(rq, prev, rf); if (!rq->nr_running) newidle_balance(rq, rf);
The newidle_balance() call will drop rq->lock after we've called put_prev_task() and that allows the above 'change' pattern to interleave and mess up the state.
The order in pick_next_task() is mandated by the fact that RT/DL put_prev_task() can pull other RT tasks, in which case we should not call newidle_balance() since we'll not be going idle. Similarly, we cannot put newidle_balance() in put_prev_task_fair() because it should be called every time we'll end up selecting the idle task.
Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse' p->on_cpu to carry more state. Adding more state to p->on_rq is possible but is far more invasive and also ends up duplicating much of the state we already carry in p->on_cpu.
Introduce task_on_rq_curr() to indicate the if sched_class::set_next_task() has been called -- and we thus need to call put_prev_task().
--- kernel/sched/core.c | 35 ++++++++++++++++++++++++++++------- kernel/sched/deadline.c | 9 +++++++++ kernel/sched/rt.c | 9 +++++++++ kernel/sched/sched.h | 21 +++++++++++++++++++++ 4 files changed, 67 insertions(+), 7 deletions(-)
kernel/sched/core.c +28 -7
@@ -1595,7 +1595,7 @@ void do_set_cpus_allowed(struct task_strlockdep_assert_held (&p->pi_lock); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued) {/*
@@ -3078,6 +3078,19 @@ static inline void prepare_task(struct t#endif } +static inline void leave_task (struct task_struct *prev) +{ +#ifdef CONFIG_SMP +/* +* The task is on its way out, we'll have called put_prev_task() on it. +* +* Make sure task_on_rq_curr() fails, such that we don't do +* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ; +#endif +} +static inline void finish_task (struct task_struct *prev) {#ifdef CONFIG_SMP
@@ -3934,8 +3947,16 @@ pick_next_task(struct rq *rq, struct tas* can PULL higher prio tasks when we lower the RQ 'priority'. */ prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) +if (!rq->nr_running) { +leave_task (prev);newidle_balance (rq, rf); +/* +* When the below pick loop results in @p == @prev, then we +* will not go through context_switch() but the +* pick_next_task() will have done set_next_task() again. +*/ +prepare_task (prev); + }for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );
@@ -4422,7 +4443,7 @@ void rt_mutex_setprio(struct task_struct prev_class = p->sched_class; queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flag);if (running)
@@ -4509,7 +4530,7 @@ void set_user_nice(struct task_struct *p goto out_unlock; } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK );if (running)
@@ -4957,7 +4978,7 @@ static int __sched_setscheduler(struct t } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flags);if (running)
@@ -6141,7 +6162,7 @@ void sched_setnuma(struct task_struct *p rq =task_rq_lock (p, &rf); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE );
@@ -7031,7 +7052,7 @@ void sched_move_task(struct task_struct rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); + running =task_on_rq_curr (rq, tsk); queued =task_on_rq_queued (tsk);if (queued)
kernel/sched/deadline.c +9 -0
@@ -1778,6 +1778,15 @@ pick_next_task_dl(struct rq *rq, structreturn p; } +/* +* As per the note for sched_class::put_prev_task() we must only drop +* the rq->lock before any permanent state change. +* +* In this case, the state change and the pull action are mutually exclusive. +* If @prev is still on the runqueue, the priority will not have dropped and we +* don't need to pull. If @prev is no longer on the runqueue we don't need +* to add it back to the pushable list. +*/ static void put_prev_task_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) {update_curr_dl (rq);
kernel/sched/rt.c +9 -0
@@ -1566,6 +1566,15 @@ pick_next_task_rt(struct rq *rq, structreturn p; } +/* +* As per the note for sched_class::put_prev_task() we must only drop +* the rq->lock before any permanent state change. +* +* In this case, the state change and the pull action are mutually exclusive. +* If @prev is still on the runqueue, the priority will not have dropped and we +* don't need to pull. If @prev is no longer on the runqueue we don't need +* to add it back to the pushable list. +*/ static void put_prev_task_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) {update_curr_rt (rq);
kernel/sched/sched.h +21 -0
@@ -1628,6 +1628,22 @@ static inline int task_running(struct rq#endif } +/* +* If true, @p has had sched_class::set_next_task() called on it. +* See pick_next_task(). +*/ +static inline bool task_on_rq_curr (struct rq *rq,struct task_struct *p) +{ +#ifdef CONFIG_SMP +return rq->curr == p && p->on_cpu ==1 ; +#else +return rq->curr == p; +#endif +} + +/* +* If true, @p has has sched_class::enqueue_task() called on it. +*/ static inline int task_on_rq_queued (struct task_struct *p) {return p->on_rq ==TASK_ON_RQ_QUEUED ;
@@ -1727,6 +1743,11 @@ struct sched_class {struct task_struct * (*pick_next_task)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf); +/* +* When put_prev_task() drops the rq->lock (RT/DL) it must do this +* before any effective state change, such that a nested +* 'put_prev_task() + set_next_task' pair will work correctly. +*/ void (*put_prev_task)(struct rq *rq,struct task_struct *p,struct rq_flags *rf);void (*set_next_task)(struct rq *rq,struct task_struct *p);
Kirill Tkhai
Reviewed-byQuoted 33 lines · Peter Zijlstra
Quoted 18 lines · Kirill Tkhai
Quoted 17 lines · Peter Zijlstra
Quoted 15 lines · Peter Zijlstra
Quoted 4 lines · Kirill Tkhai
Quoted 4 lines
kernel/sched/core.c +4
-0+#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do Quoted 8 lines
kernel/sched/core.c static inline void prepare_task(struct t
Quoted 4 lines
kernel/sched/core.c +3
-0+* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?Indeed so.
Quoted 7 lines
Quoted 3 lines
Oh wait, the way it was written this is not possible. Because
rq->nr_running== 0 andprev->on_cpu> 0 it means the current task is going to sleep and cannot be woken back up.I mostly mean throttling. AFAIR, tasks of throttled
rt_rqare not accounted inrq->nr_running. But it seemsrt_rqmay become unthrottled again afternewidle_balance()unlocks rq lock, and prev will become pickable again.Urgh... throttling.
Bah.. I had just named the "->on_cpu = 2" thing
leave_task(), to matchprepare_task()andfinish_task(), but when we have to flip it back to 1 that doesn't really work.
Quoted 7 lines
Also, I'm still flip-flopping on where to place it. Yesterday I suggested placing it before
put_prev_task(), but then I went to write a comment, and either way aroundput_prev_task()needs to be very careful.So I went back to placing it after and putting lots of comments on.
How does the below look?
For me the below patch looks OK.
One more thing about current code in git. After rq->lock became able to be unlocked after put_prev_task() is commited, we got a new corner case. We usually had the same order for running task:
dequeue_task()
put_prev_task()
Now the order may be reversed (this is also in case of throttling):
put_prev_task() (called from pick_next_task())
dequeue_task() (called from another cpu)
This is more theoretically, since I don't see a problem here. But there are too many statistics and counters in sched_class methods, that it is impossible to be sure all of them work as expected.
Kirill
Quoted 58 lines
---
Subject: sched: Fixpick_next_task()vs 'change' pattern race
From: Peter Zijlstra <[email protected]>
Date: Mon Nov 4 22:18:14 CET 2019Commit
67692435c411("sched: Reworkpick_next_task()slow-path") inadvertly introduced a race because it changed a previously unexplored dependency between dropping therq->lockandsched_class::put_prev_task().The comments about dropping
rq->lock, in for examplenewidle_balance(), only mentions the task being current and ->on_cpu being set. But when we look at the 'change' pattern (in for examplesched_setnuma()):queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */ running = task_current(rq, p); /* rq->curr == p */ if (queued) dequeue_task(...); if (running) put_prev_task(...); /* change task properties */ if (queued) enqueue_task(...); if (running) set_next_task(...);It becomes obvious that if we do this after
put_prev_task()has already been called on @p, things go sideways. This is exactly what the commit in question allows to happen when it does:prev->sched_class->put_prev_task(rq, prev, rf); if (!rq->nr_running) newidle_balance(rq, rf);The
newidle_balance()call will droprq->lockafter we've calledput_prev_task()and that allows the above 'change' pattern to interleave and mess up the state.The order in
pick_next_task()is mandated by the fact that RT/DLput_prev_task()can pull other RT tasks, in which case we should not callnewidle_balance()since we'll not be going idle. Similarly, we cannot putnewidle_balance()input_prev_task_fair()because it should be called every time we'll end up selecting the idle task.Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse'
p->on_cputo carry more state. Adding more state top->on_rqis possible but is far more invasive and also ends up duplicating much of the state we already carry inp->on_cpu.Introduce
task_on_rq_curr()to indicate the ifsched_class::set_next_task()has been called -- and we thus need to callput_prev_task().
Quoted 7 lines
Fixes 67692435c411 ("sched: Rework pick_next_task() slow-path")Reported-by Quentin Perret <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by Quentin Perret <[email protected]>Tested-by Qais Yousef <[email protected]>Tested-by Valentin Schneider <[email protected]>Tested-by Dietmar Eggemann <[email protected]>
Quoted 175 lines
--- kernel/sched/core.c | 35 ++++++++++++++++++++++++++++------- kernel/sched/deadline.c | 9 +++++++++ kernel/sched/rt.c | 9 +++++++++ kernel/sched/sched.h | 21 +++++++++++++++++++++ 4 files changed, 67 insertions(+), 7 deletions(-)kernel/sched/core.c +28
-7@@ -1595,7 +1595,7 @@ void do_set_cpus_allowed(struct task_strlockdep_assert_held (&p->pi_lock); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued) {/* @@ -3078,6 +3078,19 @@ static inline void prepare_task(struct t#endif } +static inline void leave_task (struct task_struct *prev) +{ +#ifdef CONFIG_SMP +/* +* The task is on its way out, we'll have called put_prev_task() on it. +* +* Make sure task_on_rq_curr() fails, such that we don't do +* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ; +#endif +} +static inline void finish_task (struct task_struct *prev) {#ifdef CONFIG_SMP @@ -3934,8 +3947,16 @@ pick_next_task(struct rq *rq, struct tas* can PULL higher prio tasks when we lower the RQ 'priority'. */ prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) +if (!rq->nr_running) { +leave_task (prev);newidle_balance (rq, rf); +/* +* When the below pick loop results in @p == @prev, then we +* will not go through context_switch() but the +* pick_next_task() will have done set_next_task() again. +*/ +prepare_task (prev); + }for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );@@ -4422,7 +4443,7 @@ void rt_mutex_setprio(struct task_struct prev_class = p->sched_class; queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flag);if (running)@@ -4509,7 +4530,7 @@ void set_user_nice(struct task_struct *p goto out_unlock; } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK );if (running)@@ -4957,7 +4978,7 @@ static int __sched_setscheduler(struct t } queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p, queue_flags);if (running)@@ -6141,7 +6162,7 @@ void sched_setnuma(struct task_struct *p rq =task_rq_lock (p, &rf); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_on_rq_curr (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE );@@ -7031,7 +7052,7 @@ void sched_move_task(struct task_struct rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); + running =task_on_rq_curr (rq, tsk); queued =task_on_rq_queued (tsk);if (queued)kernel/sched/deadline.c +9
-0@@ -1778,6 +1778,15 @@ pick_next_task_dl(struct rq *rq, structreturn p; } +/* +* As per the note for sched_class::put_prev_task() we must only drop +* the rq->lock before any permanent state change. +* +* In this case, the state change and the pull action are mutually exclusive. +* If @prev is still on the runqueue, the priority will not have dropped and we +* don't need to pull. If @prev is no longer on the runqueue we don't need +* to add it back to the pushable list. +*/ static void put_prev_task_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) {update_curr_dl (rq);kernel/sched/rt.c +9
-0@@ -1566,6 +1566,15 @@ pick_next_task_rt(struct rq *rq, structreturn p; } +/* +* As per the note for sched_class::put_prev_task() we must only drop +* the rq->lock before any permanent state change. +* +* In this case, the state change and the pull action are mutually exclusive. +* If @prev is still on the runqueue, the priority will not have dropped and we +* don't need to pull. If @prev is no longer on the runqueue we don't need +* to add it back to the pushable list. +*/ static void put_prev_task_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) {update_curr_rt (rq);kernel/sched/sched.h +21
-0@@ -1628,6 +1628,22 @@ static inline int task_running(struct rq#endif } +/* +* If true, @p has had sched_class::set_next_task() called on it. +* See pick_next_task(). +*/ +static inline bool task_on_rq_curr (struct rq *rq,struct task_struct *p) +{ +#ifdef CONFIG_SMP +return rq->curr == p && p->on_cpu ==1 ; +#else +return rq->curr == p; +#endif +} + +/* +* If true, @p has has sched_class::enqueue_task() called on it. +*/ static inline int task_on_rq_queued (struct task_struct *p) {return p->on_rq ==TASK_ON_RQ_QUEUED ;@@ -1727,6 +1743,11 @@ struct sched_class {struct task_struct * (*pick_next_task)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf); +/* +* When put_prev_task() drops the rq->lock (RT/DL) it must do this +* before any effective state change, such that a nested +* 'put_prev_task() + set_next_task' pair will work correctly. +*/ void (*put_prev_task)(struct rq *rq,struct task_struct *p,struct rq_flags *rf);void (*set_next_task)(struct rq *rq,struct task_struct *p);
Quoted 5 lines · Peter Zijlstra
Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse'
p->on_cputo carry more state. Adding more state top->on_rqis possible but is far more invasive and also ends up duplicating much of the state we already carry inp->on_cpu.
I think there is another solution, which is to 'de-factorize' the call to put_prev_task() (that is, have each class do it). I gave it a go and I basically end up with something equivalent to reverting 67692435c411 ("sched: Rework pick_next_task() slow-path"), which isn't the worst solution IMO. I'm thinking at least we should consider it.
Now, 67692435c411 _is_ a nice clean-up, it's just a shame that the fix on top isn't as nice (IMO). It might just be a matter of personal taste, so I don't have a strong opinion on this :)
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 11 lines · Kirill Tkhai
Quoted 1 line · Peter Zijlstra
Urgh... throttling.
One more thing about current code in git. After
rq->lockbecame able to be unlocked afterput_prev_task()is commited, we got a new corner case. We usually had the same order for running task:
dequeue_task()
put_prev_task()
Quoted 8 lines
Now the order may be reversed (this is also in case of throttling):
put_prev_task()(called frompick_next_task())
dequeue_task()(called from another cpu)This is more theoretically, since I don't see a problem here. But there are too many statistics and counters in
sched_classmethods, that it is impossible to be sure all of them work as expected.
Hmm,.. where does throttling happen on a remote CPU? I through both cfs-bandwidth and dl throttle locally.
Or are you talking about NO_HZ_FULL's sched_remote_tick() ?
Quoted 17 lines · Peter Zijlstra
Quoted 16 lines · Kirill Tkhai
Quoted 1 line · Peter Zijlstra
Urgh... throttling.
One more thing about current code in git. After
rq->lockbecame able to be unlocked afterput_prev_task()is commited, we got a new corner case. We usually had the same order for running task:
dequeue_task()
put_prev_task()Now the order may be reversed (this is also in case of throttling):
put_prev_task()(called frompick_next_task())
dequeue_task()(called from another cpu)
Quoted 8 lines
Quoted 3 lines
This is more theoretically, since I don't see a problem here. But there are too many statistics and counters in
sched_classmethods, that it is impossible to be sure all of them work as expected.Hmm,.. where does throttling happen on a remote CPU? I through both cfs-bandwidth and dl throttle locally.
Or are you talking about NO_HZ_FULL's
sched_remote_tick()?
I mean ordinary path: local throttling -> resched_curr -> schedule(). Then rq->nr_running == 0, but task is on rq. We call put_prev_task() and newidle_balance().
On another cpu someone calls set_user_nice() and it makes dequeue_task() in the middle of local cpu's newidle_balance().
Thus, we first made put_prev_task() and second dequeue_task().
Quoted 33 lines · Peter Zijlstra
Quoted 18 lines · Kirill Tkhai
Quoted 17 lines · Peter Zijlstra
Quoted 15 lines · Peter Zijlstra
Quoted 4 lines · Kirill Tkhai
Quoted 4 lines
kernel/sched/core.c +4
-0+#ifdef CONFIG_SMP +if (!rq->nr_running) { +/* +* Make sure task_on_rq_curr() fails, such that we don't do Quoted 8 lines
kernel/sched/core.c static inline void prepare_task(struct t
Quoted 4 lines
kernel/sched/core.c +3
-0+* put_prev_task() + set_next_task() on this task again. +*/ + prev->on_cpu =2 ;newidle_balance (rq, rf);Shouldn't we restore
prev->on_cpu= 1 afternewidle_balance()? Can't prev become pickable again afternewidle_balance()releasesrq->lock, and we take it again, so thison_cpu== 2 never will be cleared?Indeed so.
Quoted 7 lines
Quoted 3 lines
Oh wait, the way it was written this is not possible. Because
rq->nr_running== 0 andprev->on_cpu> 0 it means the current task is going to sleep and cannot be woken back up.I mostly mean throttling. AFAIR, tasks of throttled
rt_rqare not accounted inrq->nr_running. But it seemsrt_rqmay become unthrottled again afternewidle_balance()unlocks rq lock, and prev will become pickable again.Urgh... throttling.
Bah.. I had just named the "->on_cpu = 2" thing
leave_task(), to matchprepare_task()andfinish_task(), but when we have to flip it back to 1 that doesn't really work.
Quoted 7 lines
Also, I'm still flip-flopping on where to place it. Yesterday I suggested placing it before
put_prev_task(), but then I went to write a comment, and either way aroundput_prev_task()needs to be very careful.So I went back to placing it after and putting lots of comments on.
How does the below look?
This looks good to me. But it makes me wonder, if there's no penalty to adding the leave_task() before put_prev_task(), and if it results on relaxing the requirement of 'no permanent state change before releasing the rq lock', shouldn't we just do it?
Anyways. I'll pick this version and spin it through my reproducer.
Thanks for fixing this!
--
Qais Yousef
Peter Zijlstra
maintainerQuoted 7 lines · Quentin Perret
Quoted 5 lines · Peter Zijlstra
Given that we're stuck with this order, the only solution is fixing the 'change' pattern. The simplest fix seems to be to 'absuse'
p->on_cputo carry more state. Adding more state top->on_rqis possible but is far more invasive and also ends up duplicating much of the state we already carry inp->on_cpu.
Quoted 5 lines
I think there is another solution, which is to 'de-factorize' the call to
put_prev_task()(that is, have each class do it). I gave it a go and I basically end up with something equivalent to reverting67692435c411("sched: Reworkpick_next_task()slow-path"), which isn't the worst solution IMO. I'm thinking at least we should consider it.
The purpose of 67692435c411 is to ret rid of the RETRY_TASK logic restarting the pick.
But you mean something like:
for (class = prev->sched_class; class; class = class->next) {
if (class->balance(rq, rf))
break;
}
put_prev_task(rq, prev);
for_each_class(class) {
p = class->pick_next_task(rq);
if (p)
return p;
}
BUG();like?
I had convinced myself we didn't need that, but that DL to RT case is pesky and might require it after all.
Quoted 3 lines
Now,
67692435c411_is_ a nice clean-up, it's just a shame that the fix on top isn't as nice (IMO). It might just be a matter of personal taste, so I don't have a strong opinion on this :)
Yeah, it does rather make a mess of things.
I'll try and code up the above after dinner.
Quoted 17 lines · Peter Zijlstra
But you mean something like:
for (class = prev->sched_class; class; class = class->next) { if (class->balance(rq, rf)) break; } put_prev_task(rq, prev); for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } BUG();
Quoted 1 line
like?
Right, something like that, though what I had was basically doing the pull from within the pick_next_task_*() functions directly, like we were doing before. I'm now seeing how easy it is to get this wrong, and that even good-looking code in this area can be broken in very subtle ways, so I didn't feel comfortable refactoring again so close to rc7. If you feel more confident, I'm more than happy to test a patch implemeting the above :)
Quoted 2 lines
I had convinced myself we didn't need that, but that DL to RT case is pesky and might require it after all.
Yep, I don't see a way to avoid iterating all classes to do the balance, one way or another ...
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 17 lines · Peter Zijlstra
But you mean something like:
for (class = prev->sched_class; class; class = class->next) { if (class->balance(rq, rf)) break; } put_prev_task(rq, prev); for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } BUG();
Quoted 1 line
like?
I still havne't had food, but this here compiles...
--- kernel/sched/core.c | 20 ++++++++++++-------- kernel/sched/deadline.c | 23 +++++++++++++++-------- kernel/sched/fair.c | 12 ++++++++++-- kernel/sched/idle.c | 8 +++++++- kernel/sched/rt.c | 32 +++++++++++++++++++------------- kernel/sched/sched.h | 5 +++-- kernel/sched/stop_task.c | 8 +++++++- 7 files changed, 73 insertions(+), 35 deletions(-)
kernel/sched/core.c +12 -8
@@ -3929,13 +3929,17 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) } restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP +for (class = prev->sched_class; + class != &idle_sched_class; + class = class->next) { + +if (class->balance (rq, prev, rf)) +break ; + } +#endif + +put_prev_task (rq, prev);for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );
@@ -6201,7 +6205,7 @@ static struct task_struct *__pick_migrate_task(struct rq *rq)for_each_class (class) { next = class->pick_next_task (rq,NULL ,NULL );if (next) { - next->sched_class->put_prev_task (rq, next,NULL ); + next->sched_class->put_prev_task (rq, next);return next; } }
kernel/sched/deadline.c +15 -8
@@ -1778,15 +1778,9 @@ pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)return p; } -static void put_prev_task_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +static int balance_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) { -update_curr_dl (rq); - -update_dl_rq_load_avg (rq_clock_pelt (rq), rq,1 ); -if (on_dl_rq (&p->dl) && p->nr_cpus_allowed >1 ) -enqueue_pushable_dl_task (rq, p); - -if (rf && !on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) { +if (!on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) {/* * This is OK, because current is on_cpu, which avoids it being * picked for load-balance and preemption/IRQs are still
@@ -1797,6 +1791,18 @@ static void put_prev_task_dl(struct rq *rq, struct task_struct *p, struct rq_flapull_dl_task (rq);rq_repin_lock (rq, rf); } + +return rq->dl.dl_nr_running >0 ; +} + + +static void put_prev_task_dl (struct rq *rq,struct task_struct *p) +{ +update_curr_dl (rq); + +update_dl_rq_load_avg (rq_clock_pelt (rq), rq,1 ); +if (on_dl_rq (&p->dl) && p->nr_cpus_allowed >1 ) +enqueue_pushable_dl_task (rq, p); }/*
@@ -2438,6 +2444,7 @@ const struct sched_class dl_sched_class = { .check_preempt_curr = check_preempt_curr_dl, .pick_next_task = pick_next_task_dl, + .balance = balance_dl, .put_prev_task = put_prev_task_dl, .set_next_task = set_next_task_dl,
kernel/sched/fair.c +10 -2
@@ -6746,10 +6746,18 @@ done: __maybe_unused;return NULL ; } +static int balance_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +if (rq->cfs.nr_running) +return 1 ; + +return newidle_balance (rq, rf) !=0 ; +} +/* * Account for a descheduled task: */ -static void put_prev_task_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) {struct sched_entity *se = &prev->se;struct cfs_rq *cfs_rq;
@@ -10609,7 +10617,7 @@ const struct sched_class fair_sched_class = { .check_preempt_curr = check_preempt_wakeup, .pick_next_task = pick_next_task_fair, - + .balance = balance_fair, .put_prev_task = put_prev_task_fair, .set_next_task = set_next_task_fair,
kernel/sched/idle.c +7 -1
@@ -375,7 +375,12 @@ static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p, int flresched_curr (rq); } -static void put_prev_task_idle (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static int balance_idle (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +return 1 ;/* always runnable */ +} + +static void put_prev_task_idle (struct rq *rq,struct task_struct *prev) { }
@@ -456,6 +461,7 @@ const struct sched_class idle_sched_class = { .check_preempt_curr = check_preempt_curr_idle, .pick_next_task = pick_next_task_idle, + .balance = balance_idle, .put_prev_task = put_prev_task_idle, .set_next_task = set_next_task_idle,
kernel/sched/rt.c +19 -13
@@ -1566,20 +1566,9 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)return p; } -static void put_prev_task_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +static int balance_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) { -update_curr_rt (rq); - -update_rt_rq_load_avg (rq_clock_pelt (rq), rq,1 ); - -/* -* The previous task needs to be made eligible for pushing -* if it is still active -*/ -if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) -enqueue_pushable_task (rq, p); - -if (rf && !on_rt_rq (&p->rt) &&need_pull_rt_task (rq, p)) { +if (!on_rt_rq (&p->rt) &&need_pull_rt_task (rq, p)) {/* * This is OK, because current is on_cpu, which avoids it being * picked for load-balance and preemption/IRQs are still
@@ -1590,6 +1579,22 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p, struct rq_flapull_rt_task (rq);rq_repin_lock (rq, rf); } + +return rq->rt.rt_queued >0 ; +} + +static void put_prev_task_rt (struct rq *rq,struct task_struct *p) +{ +update_curr_rt (rq); + +update_rt_rq_load_avg (rq_clock_pelt (rq), rq,1 ); + +/* +* The previous task needs to be made eligible for pushing +* if it is still active +*/ +if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) +enqueue_pushable_task (rq, p); }#ifdef CONFIG_SMP
@@ -2362,6 +2367,7 @@ const struct sched_class rt_sched_class = { .check_preempt_curr = check_preempt_curr_rt, .pick_next_task = pick_next_task_rt, + .balance = balance_rt, .put_prev_task = put_prev_task_rt, .set_next_task = set_next_task_rt,
kernel/sched/sched.h +3 -2
@@ -1727,7 +1727,8 @@ struct sched_class {struct task_struct * (*pick_next_task)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf); -void (*put_prev_task)(struct rq *rq,struct task_struct *p,struct rq_flags *rf); +int (*balance)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf); +void (*put_prev_task)(struct rq *rq,struct task_struct *p);void (*set_next_task)(struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP
@@ -1773,7 +1774,7 @@ struct sched_class {static inline void put_prev_task (struct rq *rq,struct task_struct *prev) {WARN_ON_ONCE (rq->curr != prev); - prev->sched_class->put_prev_task (rq, prev,NULL ); + prev->sched_class->put_prev_task (rq, prev); }static inline void set_next_task (struct rq *rq,struct task_struct *next)
kernel/sched/stop_task.c +7 -1
@@ -60,7 +60,12 @@ static void yield_task_stop(struct rq *rq)BUG ();/* the stop task should never yield, its pointless. */ } -static void put_prev_task_stop (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static int balance_stop (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +return 0 ; +} + +static void put_prev_task_stop (struct rq *rq,struct task_struct *prev) {struct task_struct *curr = rq->curr;u64 delta_exec;
@@ -125,6 +130,7 @@ const struct sched_class stop_sched_class = { .check_preempt_curr = check_preempt_curr_stop, .pick_next_task = pick_next_task_stop, + .balance = balance_stop, .put_prev_task = put_prev_task_stop, .set_next_task = set_next_task_stop,
Peter Zijlstra
maintainerQuoted 20 lines · Quentin Perret
Quoted 17 lines · Peter Zijlstra
But you mean something like:
for (class = prev->sched_class; class; class = class->next) { if (class->balance(rq, rf)) break; } put_prev_task(rq, prev); for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } BUG();Quoted 1 line
like?
Quoted 7 lines
Right, something like that, though what I had was basically doing the pull from within the pick_next_task_*() functions directly, like we were doing before. I'm now seeing how easy it is to get this wrong, and that even good-looking code in this area can be broken in very subtle ways, so I didn't feel comfortable refactoring again so close to rc7. If you feel more confident, I'm more than happy to test a patch implemeting the above :)
Thing is, if we revert (and we might have to), we'll have to revert more than just the one patch due to that other (__pick_migrate_task) borkage that got reported today.
Quoted 3 lines · Peter Zijlstra
Thing is, if we revert (and we might have to), we'll have to revert more than just the one patch due to that other (
__pick_migrate_task) borkage that got reported today.
Fair enough, let's try an avoid reverting the world if possible ... I'll give a go to your patch tomorrow first thing.
Cheers,
Quentin
Quoted 1 line · Peter Zijlstra
I still havne't had food, but this here compiles...
And it seems to work, too :)
Quoted 12 lines
kernel/sched/core.c +1
-7@@ -3929,13 +3929,17 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) } restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3942
Quoted 10 lines
kernel/sched/core.c +10
-0+for (class = prev->sched_class; + class != &idle_sched_class; + class = class->next) { + +if (class->balance (rq, prev, rf)) +break ; + } +#endif + +put_prev_task (rq, prev);
Right, that looks much cleaner IMO. I'm thinking if we killed the special case for CFS above we could do with a single loop to iterate the classes, and you could fold ->balance() in ->pick_next_task() ... That would remove one call site to newidle_balance() too, which I think is good. Hackbench probably won't like that, though.
Quoted 18 lines
kernel/sched/core.c +1
-1for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );@@ -6201,7 +6205,7 @@ static struct task_struct *__pick_migrate_task(struct rq *rq)for_each_class (class) { next = class->pick_next_task (rq,NULL ,NULL );if (next) { - next->sched_class->put_prev_task (rq, next,NULL ); + next->sched_class->put_prev_task (rq, next);return next; } }kernel/sched/deadline.c +0
-0@@ -1778,15 +1778,9 @@ pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)return p; }
kernel/sched/deadline.c pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 1788
Quoted 10 lines
kernel/sched/deadline.c +1
-7-static void put_prev_task_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +static int balance_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) { -update_curr_dl (rq); - -update_dl_rq_load_avg (rq_clock_pelt (rq), rq,1 ); -if (on_dl_rq (&p->dl) && p->nr_cpus_allowed >1 ) -enqueue_pushable_dl_task (rq, p); -
Ah, and this can actually be done after the pull because the two are in fact mutually exclusive. And same thing for RT. Good :)
Quoted 37 lines
kernel/sched/deadline.c +14
-1-if (rf && !on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) { +if (!on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) {/* * This is OK, because current is on_cpu, which avoids it being * picked for load-balance and preemption/IRQs are still @@ -1797,6 +1791,18 @@ static void put_prev_task_dl(struct rq *rq, struct task_struct *p, struct rq_flapull_dl_task (rq);rq_repin_lock (rq, rf); } + +return rq->dl.dl_nr_running >0 ; +} + + +static void put_prev_task_dl (struct rq *rq,struct task_struct *p) +{ +update_curr_dl (rq); + +update_dl_rq_load_avg (rq_clock_pelt (rq), rq,1 ); +if (on_dl_rq (&p->dl) && p->nr_cpus_allowed >1 ) +enqueue_pushable_dl_task (rq, p); }/* @@ -2438,6 +2444,7 @@ const struct sched_class dl_sched_class = { .check_preempt_curr = check_preempt_curr_dl, .pick_next_task = pick_next_task_dl, + .balance = balance_dl, .put_prev_task = put_prev_task_dl, .set_next_task = set_next_task_dl,kernel/sched/fair.c +0
-0
kernel/sched/fair.c done: __maybe_unused; · line 6754
Quoted 9 lines
kernel/sched/fair.c +6
-0@@ -6746,10 +6746,18 @@ done: __maybe_unused;return NULL ; } +static int balance_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +if (rq->cfs.nr_running) +return 1 ; + +return newidle_balance (rq, rf) !=0 ;
And you can ignore the RETRY_TASK case here under the assumption that we must have tried to pull from RT/DL before ending up here ?
Thanks,
Quentin
Quoted 8 lines · Quentin Perret
Quoted 8 lines
kernel/sched/fair.c +0
-0@@ -6746,10 +6746,18 @@ done: __maybe_unused;return NULL ; }
Quoted 10 lines
kernel/sched/fair.c done: __maybe_unused; · line 6754
Quoted 6 lines
kernel/sched/fair.c +6
-0+static int balance_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +if (rq->cfs.nr_running) +return 1 ; + +return newidle_balance (rq, rf) !=0 ;And you can ignore the
RETRY_TASKcase here under the assumption that we must have tried to pull from RT/DL before ending up here ?
I think we can ignore RETRY_TASK because this happens before the picking loop, so we'll observe any new DL/RT task that got enqueued while newidle released the lock. This also means we can safely break the balance loop in pick_next_task() when we get RETRY_TASK, because we've got something to pick (some new RT/DL task). This wants a comment though, methinks.
Other than that I agree with Quentin, it's a much cleaner approach and I quite like it.
Quoted 3 lines
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 1 line · Peter Zijlstra
I still havne't had food, but this here compiles...
A more polished patch.
---
Subject: sched: Fix pick_next_task() vs 'change' pattern race
From: Peter Zijlstra <[email protected]>
Date: Fri Nov 8 11:11:52 CET 2019
Commit 67692435c411 ("sched: Rework pick_next_task() slow-path") inadvertly introduced a race because it changed a previously unexplored dependency between dropping the rq->lock and sched_class::put_prev_task().
The comments about dropping rq->lock, in for example newidle_balance(), only mentions the task being current and ->on_cpu being set. But when we look at the 'change' pattern (in for example sched_setnuma()):
queued = task_on_rq_queued(p); /* p->on_rq == TASK_ON_RQ_QUEUED */ running = task_current(rq, p); /* rq->curr == p */ if (queued) dequeue_task(...); if (running) put_prev_task(...); /* change task properties */ if (queued) enqueue_task(...); if (running) set_next_task(...);
It becomes obvious that if we do this after put_prev_task() has already been called on @p, things go sideways. This is exactly what the commit in question allows to happen when it does:
prev->sched_class->put_prev_task(rq, prev, rf); if (!rq->nr_running) newidle_balance(rq, rf);
The newidle_balance() call will drop rq->lock after we've called put_prev_task() and that allows the above 'change' pattern to interleave and mess up the state.
Furthermore, it turns out we lost the RT-pull when we put the last DL task.
Fix both problems by extracting the balancing from put_prev_task() and doing a multi-class balance() pass before put_prev_task().
--- kernel/sched/core.c | 17 +++++++++-------- kernel/sched/deadline.c | 40 ++++++++++++++++++++-------------------- kernel/sched/fair.c | 15 ++++++++++++--- kernel/sched/idle.c | 9 ++++++++- kernel/sched/rt.c | 37 +++++++++++++++++++------------------ kernel/sched/sched.h | 30 +++++++++++++++++++++++++++--- kernel/sched/stop_task.c | 18 +++++++++++------- 7 files changed, 106 insertions(+), 60 deletions(-)
kernel/sched/core.c +9 -8
@@ -3929,13 +3929,14 @@ pick_next_task(struct rq *rq, struct tas } restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP + for_class_range(class, prev->sched_class, &idle_sched_class) { +if (class->balance (rq, prev, rf)) +break ; + } +#endif + +put_prev_task (rq, prev);for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );
@@ -6201,7 +6202,7 @@ static struct task_struct *__pick_migratfor_each_class (class) { next = class->pick_next_task (rq,NULL ,NULL );if (next) { - next->sched_class->put_prev_task (rq, next,NULL ); + next->sched_class->put_prev_task (rq, next);return next; } }
kernel/sched/deadline.c +20 -20
@@ -1691,6 +1691,22 @@ static void check_preempt_equal_dl(struc resched_curr(rq); } +static int balance_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +{ +if (!on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) { +/* +* This is OK, because current is on_cpu, which avoids it being +* picked for load-balance and preemption/IRQs are still +* disabled avoiding further scheduler activity on it and we've +* not yet started the picking loop. +*/ +rq_unpin_lock (rq, rf); +pull_dl_task (rq); +rq_repin_lock (rq, rf); + } + +return sched_stop_runnable (rq) ||sched_dl_runnable (rq); +}#endif /* CONFIG_SMP */ /*
@@ -1758,45 +1774,28 @@ static struct task_struct * pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { struct sched_dl_entity *dl_se; +struct dl_rq *dl_rq = &rq->dl;struct task_struct *p; -struct dl_rq *dl_rq;WARN_ON_ONCE (prev || rf); - dl_rq = &rq->dl; - -if (unlikely (!dl_rq->dl_nr_running)) +if (!sched_dl_runnable (rq))return NULL ; dl_se =pick_next_dl_entity (rq, dl_rq);BUG_ON (!dl_se); - p =dl_task_of (dl_se); -set_next_task_dl (rq, p); -return p; } -static void put_prev_task_dl (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +static void put_prev_task_dl (struct rq *rq,struct task_struct *p) {update_curr_dl (rq);update_dl_rq_load_avg (rq_clock_pelt (rq), rq,1 );if (on_dl_rq (&p->dl) && p->nr_cpus_allowed >1 )enqueue_pushable_dl_task (rq, p); - -if (rf && !on_dl_rq (&p->dl) &&need_pull_dl_task (rq, p)) { -/* -* This is OK, because current is on_cpu, which avoids it being -* picked for load-balance and preemption/IRQs are still -* disabled avoiding further scheduler activity on it and we've -* not yet started the picking loop. -*/ -rq_unpin_lock (rq, rf); -pull_dl_task (rq); -rq_repin_lock (rq, rf); - } }/*
@@ -2442,6 +2441,7 @@ const struct sched_class dl_sched_class .set_next_task = set_next_task_dl, #ifdef CONFIG_SMP + .balance = balance_dl, .select_task_rq = select_task_rq_dl, .migrate_task_rq = migrate_task_rq_dl, .set_cpus_allowed = set_cpus_allowed_dl,
kernel/sched/fair.c +12 -3
@@ -6423,6 +6423,15 @@ static void task_dead_fair(struct task_s {remove_entity_load_avg (&p->se); } + +static int +balance_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +if (rq->nr_running) +return 1 ; + +return newidle_balance (rq, rf) !=0 ; +}#endif /* CONFIG_SMP */ static unsigned long wakeup_gran (struct sched_entity *se)
@@ -6599,7 +6608,7 @@ pick_next_task_fair(struct rq *rq, strucint new_tasks; again: -if (!cfs_rq->nr_running) +if (!sched_fair_runnable (rq)) goto idle;#ifdef CONFIG_FAIR_GROUP_SCHED
@@ -6737,7 +6746,7 @@ done: __maybe_unused;/* * Account for a descheduled task: */ -static void put_prev_task_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) {struct sched_entity *se = &prev->se;struct cfs_rq *cfs_rq;
@@ -10597,11 +10606,11 @@ const struct sched_class fair_sched_clas .check_preempt_curr = check_preempt_wakeup, .pick_next_task = pick_next_task_fair, - .put_prev_task = put_prev_task_fair, .set_next_task = set_next_task_fair, #ifdef CONFIG_SMP + .balance = balance_fair, .select_task_rq = select_task_rq_fair, .migrate_task_rq = migrate_task_rq_fair,
kernel/sched/idle.c +8 -1
@@ -365,6 +365,12 @@ select_task_rq_idle(struct task_struct * {return task_cpu (p);/* IDLE tasks as never migrated */ } + +static int +balance_idle (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +return WARN_ON_ONCE (1 ); +}#endif /*
@@ -375,7 +381,7 @@ static void check_preempt_curr_idle(struresched_curr (rq); } -static void put_prev_task_idle (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static void put_prev_task_idle (struct rq *rq,struct task_struct *prev) { }
@@ -460,6 +466,7 @@ const struct sched_class idle_sched_clas .set_next_task = set_next_task_idle,#ifdef CONFIG_SMP + .balance = balance_idle, .select_task_rq = select_task_rq_idle, .set_cpus_allowed = set_cpus_allowed_common,#endif
kernel/sched/rt.c +19 -18
@@ -1469,6 +1469,22 @@ static void check_preempt_equal_prio(str resched_curr(rq); } +static int balance_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +{ +if (!on_rt_rq (&p->rt) &&need_pull_rt_task (rq, p)) { +/* +* This is OK, because current is on_cpu, which avoids it being +* picked for load-balance and preemption/IRQs are still +* disabled avoiding further scheduler activity on it and we've +* not yet started the picking loop. +*/ +rq_unpin_lock (rq, rf); +pull_rt_task (rq); +rq_repin_lock (rq, rf); + } + +return sched_stop_runnable (rq) ||sched_dl_runnable (rq) ||sched_rt_runnable (rq); +}#endif /* CONFIG_SMP */ /*
@@ -1552,21 +1568,18 @@ static struct task_struct * pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { struct task_struct *p; -struct rt_rq *rt_rq = &rq->rt;WARN_ON_ONCE (prev || rf); -if (!rt_rq->rt_queued) +if (!sched_rt_runnable (rq))return NULL ; p =_pick_next_task_rt (rq); -set_next_task_rt (rq, p); -return p; } -static void put_prev_task_rt (struct rq *rq,struct task_struct *p,struct rq_flags *rf) +static void put_prev_task_rt (struct rq *rq,struct task_struct *p) {update_curr_rt (rq);
@@ -1578,18 +1591,6 @@ static void put_prev_task_rt(struct rq **/ if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 )enqueue_pushable_task (rq, p); - -if (rf && !on_rt_rq (&p->rt) &&need_pull_rt_task (rq, p)) { -/* -* This is OK, because current is on_cpu, which avoids it being -* picked for load-balance and preemption/IRQs are still -* disabled avoiding further scheduler activity on it and we've -* not yet started the picking loop. -*/ -rq_unpin_lock (rq, rf); -pull_rt_task (rq); -rq_repin_lock (rq, rf); - } }#ifdef CONFIG_SMP
@@ -2366,8 +2367,8 @@ const struct sched_class rt_sched_class .set_next_task = set_next_task_rt, #ifdef CONFIG_SMP + .balance = balance_rt, .select_task_rq = select_task_rq_rt, - .set_cpus_allowed = set_cpus_allowed_common, .rq_online = rq_online_rt, .rq_offline = rq_offline_rt,
kernel/sched/sched.h +27 -3
@@ -1727,10 +1727,11 @@ struct sched_class {struct task_struct * (*pick_next_task)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf); -void (*put_prev_task)(struct rq *rq,struct task_struct *p,struct rq_flags *rf); +void (*put_prev_task)(struct rq *rq,struct task_struct *p);void (*set_next_task)(struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP +int (*balance)(struct rq *rq,struct task_struct *prev,struct rq_flags *rf);int (*select_task_rq)(struct task_struct *p,int task_cpu,int sd_flag,int flags);void (*migrate_task_rq)(struct task_struct *p,int new_cpu);
@@ -1773,7 +1774,7 @@ struct sched_class {static inline void put_prev_task (struct rq *rq,struct task_struct *prev) {WARN_ON_ONCE (rq->curr != prev); - prev->sched_class->put_prev_task (rq, prev,NULL ); + prev->sched_class->put_prev_task (rq, prev); }static inline void set_next_task (struct rq *rq,struct task_struct *next)
@@ -1787,8 +1788,12 @@ static inline void set_next_task(struct#else #define sched_class_highest (&dl_sched_class)#endif + +#define for_class_range (class, _from, _to) \ + for (class = (_from); class != (_to); class = class->next) +#define for_each_class (class) \ - for (class = sched_class_highest; class; class = class->next) + for_class_range(class, sched_class_highest, NULL)extern const struct sched_class stop_sched_class;extern const struct sched_class dl_sched_class;
@@ -1796,6 +1801,25 @@ extern const struct sched_class rt_schedextern const struct sched_class fair_sched_class;extern const struct sched_class idle_sched_class; +static inline bool sched_stop_runnable (struct rq *rq) +{ +return rq->stop &&task_on_rq_queued (rq->stop); +} + +static inline bool sched_dl_runnable (struct rq *rq) +{ +return rq->dl.dl_nr_running >0 ; +} + +static inline bool sched_rt_runnable (struct rq *rq) +{ +return rq->rt.rt_queued >0 ; +} + +static inline bool sched_fair_runnable (struct rq *rq) +{ +return rq->cfs.nr_running >0 ; +}#ifdef CONFIG_SMP
kernel/sched/stop_task.c +11 -7
@@ -15,6 +15,12 @@ select_task_rq_stop(struct task_struct * {return task_cpu (p);/* stop tasks as never migrate */ } + +static int +balance_stop (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +return sched_stop_runnable (rq); +}#endif /* CONFIG_SMP */ static void
@@ -31,16 +37,13 @@ static void set_next_task_stop(struct rqstatic struct task_struct *pick_next_task_stop (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) { -struct task_struct *stop = rq->stop; -WARN_ON_ONCE (prev || rf); -if (!stop || !task_on_rq_queued (stop)) +if (!sched_stop_runnable (rq))return NULL ; -set_next_task_stop (rq, stop); - -return stop; +set_next_task_stop (rq, rq->stop); +return rq->stop; } static void
@@ -60,7 +63,7 @@ static void yield_task_stop(struct rq *rBUG ();/* the stop task should never yield, its pointless. */ } -static void put_prev_task_stop (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +static void put_prev_task_stop (struct rq *rq,struct task_struct *prev) {struct task_struct *curr = rq->curr;u64 delta_exec;
@@ -129,6 +132,7 @@ const struct sched_class stop_sched_clas .set_next_task = set_next_task_stop,#ifdef CONFIG_SMP + .balance = balance_stop, .select_task_rq = select_task_rq_stop, .set_cpus_allowed = set_cpus_allowed_common,#endif
Quoted 5 lines · Valentin Schneider
I think we can ignore
RETRY_TASKbecause this happens before the picking loop, so we'll observe any new DL/RT task that got enqueued while newidle released the lock. This also means we can safely break the balance loop inpick_next_task()when we getRETRY_TASK, because we've got something to pick (some new RT/DL task).
Ah right, the second loop always iterates from DL, so that works.
Quoted 1 line
This wants a comment though, methinks.
+1 :)
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 4 lines · Quentin Perret
Quoted 1 line · Peter Zijlstra
I still havne't had food, but this here compiles...
And it seems to work, too :)
Excellent!
Quoted 18 lines
Quoted 18 lines
kernel/sched/core.c +7
-7@@ -3929,13 +3929,17 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) } restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP +for (class = prev->sched_class; + class != &idle_sched_class; + class = class->next) { + +if (class->balance (rq, prev, rf)) +break ;
Quoted 8 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3942
Quoted 4 lines
kernel/sched/core.c +4
-0+ } +#endif + +put_prev_task (rq, prev);Right, that looks much cleaner IMO. I'm thinking if we killed the special case for CFS above we could do with a single loop to iterate the classes, and you could fold ->balance() in ->pick_next_task() ...
No, you can't, because then you're back to having to restart the pick when something happens when we drop the rq halfway down the pick. Which is something I really wanted to get rid of.
Quoted 2 lines
That would remove one call site to
newidle_balance()too, which I think is good. Hackbench probably won't like that, though.
Yeah, that fast path really is important. I've got a few patches pending there, fixing a few things and that gets me 2% extra on a sched-yield benchmark.
Quoted 3 lines
kernel/sched/fair.c done: __maybe_unused; · line 6751
Quoted 3 lines
kernel/sched/fair.c +3
-0+static int balance_fair (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) +{ +if (rq->cfs.nr_running)
FWIW that must test rq->nr_running.
Quoted 6 lines
kernel/sched/fair.c done: __maybe_unused; · line 6754
Quoted 3 lines
kernel/sched/fair.c +3
-0+return 1 ; + +return newidle_balance (rq, rf) !=0 ;And you can ignore the
RETRY_TASKcase here under the assumption that we must have tried to pull from RT/DL before ending up here ?
Well, the balance callback can always return 0 and be correct. The point is mostly to avoid more work.
In this case, since fair is the last class and we've already excluded idle for balancing, the win is minimal. But since we have the code, might as well dtrt.
Quoted 35 lines · Peter Zijlstra
Quoted 4 lines · Quentin Perret
Quoted 1 line · Peter Zijlstra
I still havne't had food, but this here compiles...
And it seems to work, too :)
Excellent!
Quoted 18 lines
Quoted 18 lines
kernel/sched/core.c +7
-7@@ -3929,13 +3929,17 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) } restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP +for (class = prev->sched_class; + class != &idle_sched_class; + class = class->next) { + +if (class->balance (rq, prev, rf)) +break ;Quoted 8 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3942
Quoted 4 lines
kernel/sched/core.c +4
-0+ } +#endif + +put_prev_task (rq, prev);Right, that looks much cleaner IMO. I'm thinking if we killed the special case for CFS above we could do with a single loop to iterate the classes, and you could fold ->balance() in ->pick_next_task() ...
Quoted 3 lines
No, you can't, because then you're back to having to restart the pick when something happens when we drop the rq halfway down the pick. Which is something I really wanted to get rid of.
Right, with a single loop you'll have to re-iterate the classes from the start in case of RETRY_TASK, but you're re-iterating all the classes too with this patch. You're doing a little less work in the second loop though, so maybe it's worth it. And I was the one worried about refactoring the code too much close to the release, so maybe that's for another time ;)
Thanks,
Quentin
Peter Zijlstra
maintainerQuoted 6 lines · Peter Zijlstra
Quoted 2 lines
That would remove one call site to
newidle_balance()too, which I think is good. Hackbench probably won't like that, though.Yeah, that fast path really is important. I've got a few patches pending there, fixing a few things and that gets me 2% extra on a sched-yield benchmark.
That is, the fast path also allows a cpu-cgroup optimization that wins something in the order of 3% for cgroup workloads.
The cgroup optimization is basically that when we schedule from fair->fair, we can avoid having to put/set the whole cgroup hierarchy but only have to update the part that changed.
Couple that with the set_next_buddy() from dequeue_task_fair(), which results in the next task being more likely to be from the same cgroup, and you've got a win.
Peter Zijlstra
maintainerQuoted 4 lines · Quentin Perret
Right, with a single loop you'll have to re-iterate the classes from the start in case of
RETRY_TASK, but you're re-iterating all the classes too with this patch. You're doing a little less work in the second loop though, so maybe it's worth it.
The thing with the restart is that it'll make your head explode when we go do core-scheduling.
Quoted 3 lines
And I was the one worried about
refactoring the code too much close to the release, so maybe that's for another time ;)
It is either this patch or reverting a bunch of patches :/
Peter Zijlstra
maintainerQuoted 4 lines · Peter Zijlstra
kernel/sched/core.c +0
-0@@ -3929,13 +3929,14 @@ pick_next_task(struct rq *rq, struct tas }
kernel/sched/core.c pick_next_task(struct rq *rq, struct tas · line 3932
Quoted 10 lines
kernel/sched/core.c +1
-7restart: -/* -* Ensure that we put DL/RT tasks before the pick loop, such that they -* can PULL higher prio tasks when we lower the RQ 'priority'. -*/ - prev->sched_class->put_prev_task (rq, prev, rf); -if (!rq->nr_running) -newidle_balance (rq, rf); +#ifdef CONFIG_SMP
/*
* We must do the balancing pass before put_next_task(), such
* that when we release the rq->lock the task is in the same
* state as before we took rq->lock.
*
* We can terminate the balance pass as soon as we know there is
* a runnable task of @class priority or higher.
*/
Quoted 10 lines
kernel/sched/core.c +7
-0+ for_class_range(class, prev->sched_class, &idle_sched_class) { +if (class->balance (rq, prev, rf)) +break ; + } +#endif + +put_prev_task (rq, prev);for_each_class (class) { p = class->pick_next_task (rq,NULL ,NULL );