Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758016AbbLBME3 (ORCPT ); Wed, 2 Dec 2015 07:04:29 -0500 Received: from foss.arm.com ([217.140.101.70]:42016 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757860AbbLBME2 (ORCPT ); Wed, 2 Dec 2015 07:04:28 -0500 Date: Wed, 2 Dec 2015 12:04:54 +0000 From: Juri Lelli To: Wanpeng Li Cc: Ingo Molnar , Peter Zijlstra , Luca Abeni , linux-kernel@vger.kernel.org, Wanpeng Li Subject: Re: [PATCH v5] sched/deadline: fix earliest_dl.next logic Message-ID: <20151202120454.GZ20439@e106622-lin> References: <1449056847-17190-1-git-send-email-wanpeng.li@hotmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1449056847-17190-1-git-send-email-wanpeng.li@hotmail.com> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6066 Lines: 180 Hi, On 02/12/15 19:47, 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. > > Tested-by: Luca Abeni > Signed-off-by: Wanpeng Li > --- > v4 -> v5: > * remove useless pick_next_earliest_dl_task declare > v3 -> v4: > * move earliest_dl.next caculation under if (leftmost) > * don't reset dl_rq->earliest_dl.next > * just checking and eventually using the updated leftmost in > dequeue_pushable_dl_task() > v2 -> v3: > * reset dl_rq->earliest_dl.next to 0 if !next_pushable > v1 -> v2: > * fix potential NULL pointer dereference > > kernel/sched/deadline.c | 69 ++++++++++--------------------------------------- > 1 file changed, 13 insertions(+), 56 deletions(-) > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c > index 8b0a15e..087d090 100644 > --- a/kernel/sched/deadline.c > +++ b/kernel/sched/deadline.c > @@ -176,13 +176,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 +206,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); I just skimmed through this, but here you are pointing p to leftmost. Couldn't this cause troubles afterwards? We updated leftmost above, can't we simply use that path for this thing below? Thanks, - Juri > + dl_rq->earliest_dl.next = p->dl.deadline; > + } > } > > static int push_dl_task(struct rq *rq); > @@ -782,42 +790,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 +819,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 +1253,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: > -- > 1.9.1 > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/