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

[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,

- 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)
--