Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Juri Lelli]

Hi,

On 24/11/15 09:58, Wanpeng Li wrote:
> Ping Peterz, :-)
> On 11/19/15 6:11 PM, Wanpeng li wrote:
> >earliest_dl.next should cache deadline of the earliest ready task that
> >is also enqueued in the pushable rbtree, as pull algorithm uses this
> >information to find candidates for migration: if the earliest_dl.next
> >deadline of source rq is earlier than the earliest_dl.curr deadline of
> >destination rq, the task from the source rq can be pulled.
> >
> >However, current implementation only guarantees that earliest_dl.next is
> >the deadline of the next ready task instead of the next pushable task;
> >which will result in potentially holding both rqs' lock and find nothing
> >to migrate because of affinity constraints. In addition, current logic
> >doesn't update the next candidate for pushing in pick_next_task_dl(),
> >even if the running task is never eligible.
> >
> >This patch fixes both problems by updating earliest_dl.next when
> >pushable dl task is enqueued/dequeued, similar to what we already do for
> >RT.
> >
> >Signed-off-by: Wanpeng li <wanpeng.li@hotmail.com>
> >---
> >v2 -> v3:
> >  * reset dl_rq->earliest_dl.next to 0 if !next_pushable
> >v1 -> v2:
> >  * fix potential NULL pointer dereference
> >
> >  kernel/sched/deadline.c | 63 ++++++++++---------------------------------------
> >  1 file changed, 12 insertions(+), 51 deletions(-)
> >
> >diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> >index 142df26..547d102 100644
> >--- a/kernel/sched/deadline.c
> >+++ b/kernel/sched/deadline.c
> >@@ -87,6 +87,8 @@ void init_dl_rq(struct dl_rq *dl_rq)
> >  #ifdef CONFIG_SMP
> >+static struct task_struct *pick_next_pushable_dl_task(struct rq *rq);
> >+
> >  static inline int dl_overloaded(struct rq *rq)
> >  {
> >  	return atomic_read(&rq->rd->dlo_count);
> >@@ -181,11 +183,15 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
> >  	rb_link_node(&p->pushable_dl_tasks, parent, link);
> >  	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> >+
> >+	if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
> >+		dl_rq->earliest_dl.next = p->dl.deadline;
> >  }
> >  static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
> >  {
> >  	struct dl_rq *dl_rq = &rq->dl;
> >+	struct task_struct *next_pushable;
> >  	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
> >  		return;
> >@@ -199,6 +205,12 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
> >  	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> >  	RB_CLEAR_NODE(&p->pushable_dl_tasks);
> >+
> >+	next_pushable = pick_next_pushable_dl_task(rq);
> >+	if (next_pushable)
> >+		dl_rq->earliest_dl.next = next_pushable->dl.deadline;
> >+	else
> >+		dl_rq->earliest_dl.next = 0;

On a second thought, this might be useless as deadlines can wraparound.
However, there are other things that I need to check about pull_dl_
tasks(). Please, bear with me for a few other days :-).

Thanks,

- Juri

> >  }
> >  static inline int has_pushable_dl_tasks(struct rq *rq)
> >@@ -775,42 +787,14 @@ static void update_curr_dl(struct rq *rq)
> >  #ifdef CONFIG_SMP
> >-static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu);
> >-
> >-static inline u64 next_deadline(struct rq *rq)
> >-{
> >-	struct task_struct *next = pick_next_earliest_dl_task(rq, rq->cpu);
> >-
> >-	if (next && dl_prio(next->prio))
> >-		return next->dl.deadline;
> >-	else
> >-		return 0;
> >-}
> >-
> >  static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
> >  {
> >  	struct rq *rq = rq_of_dl_rq(dl_rq);
> >  	if (dl_rq->earliest_dl.curr == 0 ||
> >  	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
> >-		/*
> >-		 * If the dl_rq had no -deadline tasks, or if the new task
> >-		 * has shorter deadline than the current one on dl_rq, we
> >-		 * know that the previous earliest becomes our next earliest,
> >-		 * as the new task becomes the earliest itself.
> >-		 */
> >-		dl_rq->earliest_dl.next = dl_rq->earliest_dl.curr;
> >  		dl_rq->earliest_dl.curr = deadline;
> >  		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, 1);
> >-	} else if (dl_rq->earliest_dl.next == 0 ||
> >-		   dl_time_before(deadline, dl_rq->earliest_dl.next)) {
> >-		/*
> >-		 * On the other hand, if the new -deadline task has a
> >-		 * a later deadline than the earliest one on dl_rq, but
> >-		 * it is earlier than the next (if any), we must
> >-		 * recompute the next-earliest.
> >-		 */
> >-		dl_rq->earliest_dl.next = next_deadline(rq);
> >  	}
> >  }
> >@@ -832,7 +816,6 @@ static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
> >  		entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
> >  		dl_rq->earliest_dl.curr = entry->deadline;
> >-		dl_rq->earliest_dl.next = next_deadline(rq);
> >  		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline, 1);
> >  	}
> >  }
> >@@ -1267,28 +1250,6 @@ static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
> >  	return 0;
> >  }
> >-/* Returns the second earliest -deadline task, NULL otherwise */
> >-static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu)
> >-{
> >-	struct rb_node *next_node = rq->dl.rb_leftmost;
> >-	struct sched_dl_entity *dl_se;
> >-	struct task_struct *p = NULL;
> >-
> >-next_node:
> >-	next_node = rb_next(next_node);
> >-	if (next_node) {
> >-		dl_se = rb_entry(next_node, struct sched_dl_entity, rb_node);
> >-		p = dl_task_of(dl_se);
> >-
> >-		if (pick_dl_task(rq, p, cpu))
> >-			return p;
> >-
> >-		goto next_node;
> >-	}
> >-
> >-	return NULL;
> >-}
> >-
> >  /*
> >   * Return the earliest pushable rq's task, which is suitable to be executed
> >   * on the CPU, NULL otherwise:
> 

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Juri Lelli]

Hi,

[+Luca, as he has been testing this patch an he has probably findings to
share]

On 19/11/15 18:11, Wanpeng li wrote:
> earliest_dl.next should cache deadline of the earliest ready task that
> is also enqueued in the pushable rbtree, as pull algorithm uses this
> information to find candidates for migration: if the earliest_dl.next
> deadline of source rq is earlier than the earliest_dl.curr deadline of
> destination rq, the task from the source rq can be pulled.
> 
> However, current implementation only guarantees that earliest_dl.next is
> the deadline of the next ready task instead of the next pushable task;
> which will result in potentially holding both rqs' lock and find nothing
> to migrate because of affinity constraints. In addition, current logic
> doesn't update the next candidate for pushing in pick_next_task_dl(),
> even if the running task is never eligible.
> 
> This patch fixes both problems by updating earliest_dl.next when
> pushable dl task is enqueued/dequeued, similar to what we already do for
> RT.
> 
> Signed-off-by: Wanpeng li <wanpeng.li@hotmail.com>
> ---
> v2 -> v3:
>  * reset dl_rq->earliest_dl.next to 0 if !next_pushable
> v1 -> v2:
>  * fix potential NULL pointer dereference
> 
>  kernel/sched/deadline.c | 63 ++++++++++---------------------------------------
>  1 file changed, 12 insertions(+), 51 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 142df26..547d102 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -87,6 +87,8 @@ void init_dl_rq(struct dl_rq *dl_rq)
>  
>  #ifdef CONFIG_SMP
>  
> +static struct task_struct *pick_next_pushable_dl_task(struct rq *rq);
> +
>  static inline int dl_overloaded(struct rq *rq)
>  {
>  	return atomic_read(&rq->rd->dlo_count);
> @@ -181,11 +183,15 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>  
>  	rb_link_node(&p->pushable_dl_tasks, parent, link);
>  	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> +
> +	if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
> +		dl_rq->earliest_dl.next = p->dl.deadline;

This seems to be a bug, as earliest_dl.next is initialized to 0 and
dl_time_before() will say that p has later deadline than
earliest_dl.next even if p is actually the first pushable task.

>  }
>  
>  static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>  {
>  	struct dl_rq *dl_rq = &rq->dl;
> +	struct task_struct *next_pushable;
>  
>  	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
>  		return;
> @@ -199,6 +205,12 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>  
>  	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
>  	RB_CLEAR_NODE(&p->pushable_dl_tasks);
> +
> +	next_pushable = pick_next_pushable_dl_task(rq);
> +	if (next_pushable)
> +		dl_rq->earliest_dl.next = next_pushable->dl.deadline;
> +	else
> +		dl_rq->earliest_dl.next = 0;

As already said, this is useless (sorry for suggesting it in the first
instance).

What follows might fix these two issue. However, Luca is telling me that
he is seeing some other issue with this patch on his testing box. Maybe
he can directly comment on this.

Thanks,

- Juri

---
 kernel/sched/deadline.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 547d102..d6de660 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -178,14 +178,13 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 		}
 	}
 
-	if (leftmost)
+	if (leftmost) {
 		dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
+		dl_rq->earliest_dl.next = p->dl.deadline;
+	}
 
 	rb_link_node(&p->pushable_dl_tasks, parent, link);
 	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
-
-	if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
-		dl_rq->earliest_dl.next = p->dl.deadline;
 }
 
 static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
@@ -209,8 +208,6 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 	next_pushable = pick_next_pushable_dl_task(rq);
 	if (next_pushable)
 		dl_rq->earliest_dl.next = next_pushable->dl.deadline;
-	else
-		dl_rq->earliest_dl.next = 0;
 }
 
 static inline int has_pushable_dl_tasks(struct rq *rq)
-- 

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Luca Abeni]

Hi all,

I ran some quick tests on this patch (because I was working on something
related), and it seems to me that it triggers a bug. Here are some information:
- I applied the patch to git master (to be sure that I did not corrupt the patch,
   I extracted it again with git format-patch, and posted it here:
   http://disi.unitn.it/~abeni/H-Test/0001-sched-deadline-fix-earliest_dl.next-logic.patch )
- I tried a simple test program creating 4 periodic threads and scheduling them with
   SCHED_DEADLINE. And I got something like:
[   29.055688] ------------[ cut here ]------------
[   29.056563] kernel BUG at /home/luca/Src/Kernel/linux/kernel/sched/deadline.c:1443!
[   29.056563] invalid opcode: 0000 [#1] SMP
[   29.056563] Modules linked in:
[   29.056563] CPU: 0 PID: 1136 Comm: periodic_thread Not tainted 4.4.0-rc2+ #3
[   29.056563] Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS Bochs 01/01/2011
[   29.056563] task: ffff880006603d80 ti: ffff8800067f4000 task.ti: ffff8800067f4000
[   29.056563] RIP: 0010:[<ffffffff8109704a>]  [<ffffffff8109704a>] pick_next_pushable_dl_task+0x5a/0x60
[   29.056563] RSP: 0000:ffff8800067f7e38  EFLAGS: 00010046
[   29.056563] RAX: ffff880006603d80 RBX: ffff880006a7ac50 RCX: ffff8800067f4000
[   29.056563] RDX: ffff8800066040d0 RSI: 0000000000000000 RDI: ffff880007a15ac0
[   29.056563] RBP: ffff8800067f7e38 R08: 0000000000000000 R09: 0000000000000000
[   29.056563] R10: ffff880006603d80 R11: ffff880006604548 R12: ffff880007a15ac0
[   29.056563] R13: ffff880006a7a900 R14: ffff8800066042e0 R15: ffffffff81a09cc0
[   29.056563] FS:  00007f667e179700(0000) GS:ffff880007a00000(0000) knlGS:0000000000000000
[   29.056563] CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
[   29.056563] CR2: 00007f71f3c221b8 CR3: 00000000067ae000 CR4: 00000000000006f0
[   29.056563] Stack:
[   29.056563]  ffff8800067f7e60 ffffffff81097137 ffff880007a15ac0 ffff880006a7ab20
[   29.056563]  ffff880006a7a900 ffff8800067f7e90 ffffffff81098ef1 ffff880006603d80
[   29.056563]  ffff880007a15ac0 ffff880007a15ad8 0000000000000000 ffff8800067f7ee8
[   29.056563] Call Trace:
[   29.056563]  [<ffffffff81097137>] dequeue_pushable_dl_task+0x47/0x90
[   29.056563]  [<ffffffff81098ef1>] pick_next_task_dl+0x81/0x200
[   29.056563]  [<ffffffff819521ad>] __schedule+0xb3d/0xd00
[   29.056563]  [<ffffffff819523a7>] schedule+0x37/0x80
[   29.056563]  [<ffffffff81050d46>] exit_to_usermode_loop+0x39/0x7f
[   29.056563]  [<ffffffff81001a76>] prepare_exit_to_usermode+0x46/0x50
[   29.056563]  [<ffffffff819586a5>] retint_user+0x8/0x20
[   29.056563] Code: 3b 87 18 09 00 00 74 23 83 7a 98 01 7e 1b 83 ba f4 fc ff ff 01 75 10 8b 92 f8 fc ff ff 85 d2 78 04 0f 0b 31 c0 5d c3 0f 0b 0f 0b <0f> 0b 0f 0b 66 90 55 48 89 
e5 41 54 49 89 f4 53 48 8b b7 18 09
[   29.056563] RIP  [<ffffffff8109704a>] pick_next_pushable_dl_task+0x5a/0x60
[   29.056563]  RSP <ffff8800067f7e38>
[   29.056563] ---[ end trace 9f49218ec54a0b55 ]---
- How to reproduce:
   + Download http://disi.unitn.it/~abeni/H-Test/newcore-3.gz
   + Start KVM with:
	qemu-system-x86_64 -initrd newcore-3.gz -machine pc-q35-2.0,accel=kvm -smp cpus=2 -kernel bzImage -serial file:qlog.txt -append "console=ttyS0"
   + Inside the VM, do
	cd /
	sudo ./periodic_thread
   + You should see a crash in few seconds
   The "periodic_thread" program just creates 4 periodic threads (with execution time about
   10ms and period about 100ms) scheduled with SCHED_DEADLINE (with runtime 15ms and period
   100ms). I can provide the source code if needed.
- The full kernel log is available here: http://disi.unitn.it/~abeni/H-Test/qlog.txt


Here is my understanding of the crash:
- schedule() invokes pick_next_task_dl() which wants to do a context switch (by selecting
   for execution a new task "p" which is different from "prev")
- pick_next_task_dl() invokes put_prev, which puts the "prev" task in the pushable tasks
   queue (WARNING! "prev" is still the "current" task in this rq, because the scheduler is
   still running... I think this is the source of the issue)
- then, pick_next_task_dl() invokes dequeue_pushable_dl_task() on p, to remove the selected
   task from the pushable tasks queue...
- ...But after your patch dequeue_pushable_dl_task() invokes pick_next_pushable_dl_task().
   Which sees that the next pushable task is the "current" task (see above). This happens
   becuase "prev" has already been inserted in the pushable tasks queue, and can be the
   next pushable task... But "current" has not been updated yet.
- The BUG_ON() at line 1443 of deadline.c is just "BUG_ON(task_current(rq, p))"

Summing up, I think pick_next_pushable_dl_task() cannot be called from
dequeue_pushable_dl_task() (at least, not without removing or modifying that BUG_ON()).


On 11/27/2015 12:26 PM, Juri Lelli wrote:
[...]
>> +
>> +	if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
>> +		dl_rq->earliest_dl.next = p->dl.deadline;
>
> This seems to be a bug, as earliest_dl.next is initialized to 0 and
> dl_time_before() will say that p has later deadline than
> earliest_dl.next even if p is actually the first pushable task.
I also think the "if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))"
might be wrong, but I have no testcases...

I _suspect_ (but I might be wrong) that here you could use
	if (leftmost)
		dl_rq->earliest_dl.next = p->dl.deadline;



				Luca

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

2015-11-27 20:14 GMT+08:00 Luca Abeni <luca.abeni@unitn.it>:
> Hi all,
>
> I ran some quick tests on this patch (because I was working on something
> related), and it seems to me that it triggers a bug. Here are some
> information:
> - I applied the patch to git master (to be sure that I did not corrupt the
> patch,
>   I extracted it again with git format-patch, and posted it here:
>
> http://disi.unitn.it/~abeni/H-Test/0001-sched-deadline-fix-earliest_dl.next-logic.patch
> )
> - I tried a simple test program creating 4 periodic threads and scheduling
> them with
>   SCHED_DEADLINE. And I got something like:
> [   29.055688] ------------[ cut here ]------------
> [   29.056563] kernel BUG at
> /home/luca/Src/Kernel/linux/kernel/sched/deadline.c:1443!
> [   29.056563] invalid opcode: 0000 [#1] SMP
> [   29.056563] Modules linked in:
> [   29.056563] CPU: 0 PID: 1136 Comm: periodic_thread Not tainted 4.4.0-rc2+
> #3
> [   29.056563] Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS
> Bochs 01/01/2011
> [   29.056563] task: ffff880006603d80 ti: ffff8800067f4000 task.ti:
> ffff8800067f4000
> [   29.056563] RIP: 0010:[<ffffffff8109704a>]  [<ffffffff8109704a>]
> pick_next_pushable_dl_task+0x5a/0x60
> [   29.056563] RSP: 0000:ffff8800067f7e38  EFLAGS: 00010046
> [   29.056563] RAX: ffff880006603d80 RBX: ffff880006a7ac50 RCX:
> ffff8800067f4000
> [   29.056563] RDX: ffff8800066040d0 RSI: 0000000000000000 RDI:
> ffff880007a15ac0
> [   29.056563] RBP: ffff8800067f7e38 R08: 0000000000000000 R09:
> 0000000000000000
> [   29.056563] R10: ffff880006603d80 R11: ffff880006604548 R12:
> ffff880007a15ac0
> [   29.056563] R13: ffff880006a7a900 R14: ffff8800066042e0 R15:
> ffffffff81a09cc0
> [   29.056563] FS:  00007f667e179700(0000) GS:ffff880007a00000(0000)
> knlGS:0000000000000000
> [   29.056563] CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
> [   29.056563] CR2: 00007f71f3c221b8 CR3: 00000000067ae000 CR4:
> 00000000000006f0
> [   29.056563] Stack:
> [   29.056563]  ffff8800067f7e60 ffffffff81097137 ffff880007a15ac0
> ffff880006a7ab20
> [   29.056563]  ffff880006a7a900 ffff8800067f7e90 ffffffff81098ef1
> ffff880006603d80
> [   29.056563]  ffff880007a15ac0 ffff880007a15ad8 0000000000000000
> ffff8800067f7ee8
> [   29.056563] Call Trace:
> [   29.056563]  [<ffffffff81097137>] dequeue_pushable_dl_task+0x47/0x90
> [   29.056563]  [<ffffffff81098ef1>] pick_next_task_dl+0x81/0x200
> [   29.056563]  [<ffffffff819521ad>] __schedule+0xb3d/0xd00
> [   29.056563]  [<ffffffff819523a7>] schedule+0x37/0x80
> [   29.056563]  [<ffffffff81050d46>] exit_to_usermode_loop+0x39/0x7f
> [   29.056563]  [<ffffffff81001a76>] prepare_exit_to_usermode+0x46/0x50
> [   29.056563]  [<ffffffff819586a5>] retint_user+0x8/0x20
> [   29.056563] Code: 3b 87 18 09 00 00 74 23 83 7a 98 01 7e 1b 83 ba f4 fc
> ff ff 01 75 10 8b 92 f8 fc ff ff 85 d2 78 04 0f 0b 31 c0 5d c3 0f 0b 0f 0b
> <0f> 0b 0f 0b 66 90 55 48 89 e5 41 54 49 89 f4 53 48 8b b7 18 09
> [   29.056563] RIP  [<ffffffff8109704a>]
> pick_next_pushable_dl_task+0x5a/0x60
> [   29.056563]  RSP <ffff8800067f7e38>
> [   29.056563] ---[ end trace 9f49218ec54a0b55 ]---
> - How to reproduce:
>   + Download http://disi.unitn.it/~abeni/H-Test/newcore-3.gz
>   + Start KVM with:
>         qemu-system-x86_64 -initrd newcore-3.gz -machine
> pc-q35-2.0,accel=kvm -smp cpus=2 -kernel bzImage -serial file:qlog.txt
> -append "console=ttyS0"
>   + Inside the VM, do
>         cd /
>         sudo ./periodic_thread
>   + You should see a crash in few seconds
>   The "periodic_thread" program just creates 4 periodic threads (with
> execution time about
>   10ms and period about 100ms) scheduled with SCHED_DEADLINE (with runtime
> 15ms and period
>   100ms). I can provide the source code if needed.
> - The full kernel log is available here:
> http://disi.unitn.it/~abeni/H-Test/qlog.txt
>
>
> Here is my understanding of the crash:
> - schedule() invokes pick_next_task_dl() which wants to do a context switch
> (by selecting
>   for execution a new task "p" which is different from "prev")
> - pick_next_task_dl() invokes put_prev, which puts the "prev" task in the
> pushable tasks
>   queue (WARNING! "prev" is still the "current" task in this rq, because the
> scheduler is
>   still running... I think this is the source of the issue)
> - then, pick_next_task_dl() invokes dequeue_pushable_dl_task() on p, to
> remove the selected
>   task from the pushable tasks queue...
> - ...But after your patch dequeue_pushable_dl_task() invokes
> pick_next_pushable_dl_task().
>   Which sees that the next pushable task is the "current" task (see above).
> This happens
>   becuase "prev" has already been inserted in the pushable tasks queue, and
> can be the
>   next pushable task... But "current" has not been updated yet.
> - The BUG_ON() at line 1443 of deadline.c is just "BUG_ON(task_current(rq,
> p))"

Thanks for your report and great analyse, Luca, you are right.

>
> Summing up, I think pick_next_pushable_dl_task() cannot be called from
> dequeue_pushable_dl_task() (at least, not without removing or modifying that
> BUG_ON()).

Juri, how about remove this BUG_ON() just like rt class?

Regards,
Wanpeng Li

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Juri Lelli]

On 30/11/15 10:20, Wanpeng Li wrote:
> 2015-11-27 20:14 GMT+08:00 Luca Abeni <luca.abeni@unitn.it>:
> > Hi all,
> >
> > I ran some quick tests on this patch (because I was working on something
> > related), and it seems to me that it triggers a bug. Here are some
> > information:

[snip]

> >
> > Here is my understanding of the crash:
> > - schedule() invokes pick_next_task_dl() which wants to do a context switch
> > (by selecting
> >   for execution a new task "p" which is different from "prev")
> > - pick_next_task_dl() invokes put_prev, which puts the "prev" task in the
> > pushable tasks
> >   queue (WARNING! "prev" is still the "current" task in this rq, because the
> > scheduler is
> >   still running... I think this is the source of the issue)
> > - then, pick_next_task_dl() invokes dequeue_pushable_dl_task() on p, to
> > remove the selected
> >   task from the pushable tasks queue...
> > - ...But after your patch dequeue_pushable_dl_task() invokes
> > pick_next_pushable_dl_task().
> >   Which sees that the next pushable task is the "current" task (see above).
> > This happens
> >   becuase "prev" has already been inserted in the pushable tasks queue, and
> > can be the
> >   next pushable task... But "current" has not been updated yet.
> > - The BUG_ON() at line 1443 of deadline.c is just "BUG_ON(task_current(rq,
> > p))"
> 
> Thanks for your report and great analyse, Luca, you are right.
> 
> >
> > Summing up, I think pick_next_pushable_dl_task() cannot be called from
> > dequeue_pushable_dl_task() (at least, not without removing or modifying that
> > BUG_ON()).
> 
> Juri, how about remove this BUG_ON() just like rt class?
> 

It seems that we actually check the very same conditions for RT, as we
do for DL. The difference is that RT doesn't call pick_next_pushable
_task(). I think we can do the same, just checking and eventually using
the updated leftmost in dequeue_pushable_dl_task().

Thanks,

- Juri

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

2015-12-01 19:30 GMT+08:00 Juri Lelli <juri.lelli@arm.com>:
> On 30/11/15 10:20, Wanpeng Li wrote:
>> 2015-11-27 20:14 GMT+08:00 Luca Abeni <luca.abeni@unitn.it>:
>> > Hi all,
>> >
>> > I ran some quick tests on this patch (because I was working on something
>> > related), and it seems to me that it triggers a bug. Here are some
>> > information:
>
> [snip]
>
>> >
>> > Here is my understanding of the crash:
>> > - schedule() invokes pick_next_task_dl() which wants to do a context switch
>> > (by selecting
>> >   for execution a new task "p" which is different from "prev")
>> > - pick_next_task_dl() invokes put_prev, which puts the "prev" task in the
>> > pushable tasks
>> >   queue (WARNING! "prev" is still the "current" task in this rq, because the
>> > scheduler is
>> >   still running... I think this is the source of the issue)
>> > - then, pick_next_task_dl() invokes dequeue_pushable_dl_task() on p, to
>> > remove the selected
>> >   task from the pushable tasks queue...
>> > - ...But after your patch dequeue_pushable_dl_task() invokes
>> > pick_next_pushable_dl_task().
>> >   Which sees that the next pushable task is the "current" task (see above).
>> > This happens
>> >   becuase "prev" has already been inserted in the pushable tasks queue, and
>> > can be the
>> >   next pushable task... But "current" has not been updated yet.
>> > - The BUG_ON() at line 1443 of deadline.c is just "BUG_ON(task_current(rq,
>> > p))"
>>
>> Thanks for your report and great analyse, Luca, you are right.
>>
>> >
>> > Summing up, I think pick_next_pushable_dl_task() cannot be called from
>> > dequeue_pushable_dl_task() (at least, not without removing or modifying that
>> > BUG_ON()).
>>
>> Juri, how about remove this BUG_ON() just like rt class?
>>
>
> It seems that we actually check the very same conditions for RT, as we
> do for DL. The difference is that RT doesn't call pick_next_pushable
> _task(). I think we can do the same, just checking and eventually using
> the updated leftmost in dequeue_pushable_dl_task().

Thanks for your suggestion, just send out v4.

Regards,
Wanpeng Li

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

Hi Luca,
2015-11-27 20:14 GMT+08:00 Luca Abeni <luca.abeni@unitn.it>:
> Hi all,
>
> I ran some quick tests on this patch (because I was working on something
> related), and it seems to me that it triggers a bug. Here are some

Your Tested-by to v4 is a great appreciated.

Regards,
Wanpeng Li

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Luca Abeni]

On 12/02/2015 11:42 AM, Wanpeng Li wrote:
> Hi Luca,
> 2015-11-27 20:14 GMT+08:00 Luca Abeni <luca.abeni@unitn.it>:
>> Hi all,
>>
>> I ran some quick tests on this patch (because I was working on something
>> related), and it seems to me that it triggers a bug. Here are some
>
> Your Tested-by to v4 is a great appreciated.
Sorry; I've been busy with other stuff, but I am now testing the new patch.
The crash is gone, and the first tests seem to show that the patch is ok;
I'll send another email later when more tests will be finished.



				Luca

Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

2015-11-27 19:26 GMT+08:00 Juri Lelli <juri.lelli@arm.com>:
> Hi,
>
> [+Luca, as he has been testing this patch an he has probably findings to
> share]
>
> On 19/11/15 18:11, Wanpeng li wrote:
>> earliest_dl.next should cache deadline of the earliest ready task that
>> is also enqueued in the pushable rbtree, as pull algorithm uses this
>> information to find candidates for migration: if the earliest_dl.next
>> deadline of source rq is earlier than the earliest_dl.curr deadline of
>> destination rq, the task from the source rq can be pulled.
>>
>> However, current implementation only guarantees that earliest_dl.next is
>> the deadline of the next ready task instead of the next pushable task;
>> which will result in potentially holding both rqs' lock and find nothing
>> to migrate because of affinity constraints. In addition, current logic
>> doesn't update the next candidate for pushing in pick_next_task_dl(),
>> even if the running task is never eligible.
>>
>> This patch fixes both problems by updating earliest_dl.next when
>> pushable dl task is enqueued/dequeued, similar to what we already do for
>> RT.
>>
>> Signed-off-by: Wanpeng li <wanpeng.li@hotmail.com>
>> ---
>> v2 -> v3:
>>  * reset dl_rq->earliest_dl.next to 0 if !next_pushable
>> v1 -> v2:
>>  * fix potential NULL pointer dereference
>>
>>  kernel/sched/deadline.c | 63 ++++++++++---------------------------------------
>>  1 file changed, 12 insertions(+), 51 deletions(-)
>>
>> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>> index 142df26..547d102 100644
>> --- a/kernel/sched/deadline.c
>> +++ b/kernel/sched/deadline.c
>> @@ -87,6 +87,8 @@ void init_dl_rq(struct dl_rq *dl_rq)
>>
>>  #ifdef CONFIG_SMP
>>
>> +static struct task_struct *pick_next_pushable_dl_task(struct rq *rq);
>> +
>>  static inline int dl_overloaded(struct rq *rq)
>>  {
>>       return atomic_read(&rq->rd->dlo_count);
>> @@ -181,11 +183,15 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>>
>>       rb_link_node(&p->pushable_dl_tasks, parent, link);
>>       rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
>> +
>> +     if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
>> +             dl_rq->earliest_dl.next = p->dl.deadline;
>
> This seems to be a bug, as earliest_dl.next is initialized to 0 and
> dl_time_before() will say that p has later deadline than
> earliest_dl.next even if p is actually the first pushable task.
>
>>  }
>>
>>  static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>>  {
>>       struct dl_rq *dl_rq = &rq->dl;
>> +     struct task_struct *next_pushable;
>>
>>       if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
>>               return;
>> @@ -199,6 +205,12 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>>
>>       rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
>>       RB_CLEAR_NODE(&p->pushable_dl_tasks);
>> +
>> +     next_pushable = pick_next_pushable_dl_task(rq);
>> +     if (next_pushable)
>> +             dl_rq->earliest_dl.next = next_pushable->dl.deadline;
>> +     else
>> +             dl_rq->earliest_dl.next = 0;
>
> As already said, this is useless (sorry for suggesting it in the first
> instance).
>
> What follows might fix these two issue. However, Luca is telling me that
> he is seeing some other issue with this patch on his testing box. Maybe
> he can directly comment on this.

Thanks for your help Juri, I will fold your suggestion into next version.

Regards,
Wanpeng Li

>
> Thanks,
>
> - Juri
>
> ---
>  kernel/sched/deadline.c | 9 +++------
>  1 file changed, 3 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 547d102..d6de660 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -178,14 +178,13 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>                 }
>         }
>
> -       if (leftmost)
> +       if (leftmost) {
>                 dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
> +               dl_rq->earliest_dl.next = p->dl.deadline;
> +       }
>
>         rb_link_node(&p->pushable_dl_tasks, parent, link);
>         rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> -
> -       if (dl_time_before(p->dl.deadline, dl_rq->earliest_dl.next))
> -               dl_rq->earliest_dl.next = p->dl.deadline;
>  }
>
>  static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
> @@ -209,8 +208,6 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>         next_pushable = pick_next_pushable_dl_task(rq);
>         if (next_pushable)
>                 dl_rq->earliest_dl.next = next_pushable->dl.deadline;
> -       else
> -               dl_rq->earliest_dl.next = 0;
>  }
>
>  static inline int has_pushable_dl_tasks(struct rq *rq)