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

Wanpeng Li
2015-11-30T02:22:07Z

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)