| 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
| ||
|
Message-ID: <565ED709.3030305@unitn.it>
Date: Wed, 2 Dec 2015 12:33:29 +0100
From: Luca Abeni <luca.abeni@...tn.it>
To: Wanpeng Li <kernellwp@...il.com>, Ingo Molnar <mingo@...nel.org>,
Peter Zijlstra <peterz@...radead.org>
Cc: Juri Lelli <juri.lelli@....com>, linux-kernel@...r.kernel.org,
Wanpeng Li <wanpeng.li@...mail.com>
Subject: Re: [PATCH v4] sched/deadline: fix earliest_dl.next logic
Hi,
On 12/01/2015 01:10 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@...mail.com>
I ran some tests with this patch, and I found no issues; so, you can add
Tested-by: luca abeni <luca.abeni@...tn.it>
I just have one minor comment on the patch:
[...]
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 8b0a15e..8ac17c7 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);
> +
I think with the new version of the patch the addition of these 2 lines
becomes useless.
Luca
> static inline int dl_overloaded(struct rq *rq)
> {
> return atomic_read(&rq->rd->dlo_count);
> @@ -176,13 +178,20 @@ 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);
> }
>
> +static inline int has_pushable_dl_tasks(struct rq *rq)
> +{
> + return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
> +}
> +
> static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
> {
> struct dl_rq *dl_rq = &rq->dl;
> @@ -199,11 +208,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);
> -}
>
> -static inline int has_pushable_dl_tasks(struct rq *rq)
> -{
> - return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
> + if (has_pushable_dl_tasks(rq)) {
> + p = rb_entry(rq->dl.pushable_dl_tasks_leftmost,
> + struct task_struct, pushable_dl_tasks);
> + dl_rq->earliest_dl.next = p->dl.deadline;
> + }
> }
>
> static int push_dl_task(struct rq *rq);
> @@ -782,42 +792,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);
> }
> }
>
> @@ -839,7 +821,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);
> }
> }
> @@ -1274,28 +1255,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:
>
--
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/
Powered by blists - more mailing lists