linux-kernel - Re: [PATCH v2] sched/deadline: fix earliest

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Thu, 19 Nov 2015 18:01:36 +0800
From:	Wanpeng Li <kernellwp@...il.com>
To:	Juri Lelli <juri.lelli@....com>
Cc:	Wanpeng Li <wanpeng.li@...mail.com>,
	Ingo Molnar <mingo@...nel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v2] sched/deadline: fix earliest_dl.next is not the
 pushable candidate

Hi Juri,
2015-11-19 17:38 GMT+08:00 Juri Lelli <juri.lelli@....com>:
> Hi,
>
> On 10/11/15 20:33, Wanpeng Li wrote:
>> earliest_dl.next is used to cache the next earliest ready task
>> which also is pushable in order to be a candidate of pushable
>> tasks during pull algorithm. If the earliest_dl.next deadline
>> of the sr_rq is earlier than the earliest_dl.curr deadline of
>> current rq, the task from the sr_rq can be pulled. However,
>> current implementation logic of earliest_dl.next just guarantee
>> it is the next earliest ready task instead of the next pushable
>> earliest task, which will result in hold both rqs' lock and find
>> nothing to preempt our current since the affinity in pull algorithm.
>> 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 fix it by updating earliest_dl.next when pushable dl
>> task is enqueued/dequeued the same way as rt class.
>>
>
> I'd slightly modify subject and changelog as something like:

Thanks for your help. :-)

>
> sched/deadline: fix earliest_dl.next logic
>
> 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@...mail.com>
>> ---
>> v1 -> v2:
>>  * fix potential NULL pointer dereference
>>
>>  kernel/sched/deadline.c | 61 ++++++++-----------------------------------------
>>  1 file changed, 10 insertions(+), 51 deletions(-)
>>
>> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>> index 142df26..b18c116 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,10 @@ 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;
>
> We should reset this to 0 if !next_pushable.

I will fix it soon. :-)

Regards,
Wanpeng Li
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/