Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757930AbbLBLde (ORCPT ); Wed, 2 Dec 2015 06:33:34 -0500 Received: from mail-wm0-f48.google.com ([74.125.82.48]:37143 "EHLO mail-wm0-f48.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756908AbbLBLdc (ORCPT ); Wed, 2 Dec 2015 06:33:32 -0500 Subject: Re: [PATCH v4] sched/deadline: fix earliest_dl.next logic To: Wanpeng Li , Ingo Molnar , Peter Zijlstra References: <1448971807-11118-1-git-send-email-wanpeng.li@hotmail.com> Cc: Juri Lelli , linux-kernel@vger.kernel.org, Wanpeng Li From: Luca Abeni Message-ID: <565ED709.3030305@unitn.it> Date: Wed, 2 Dec 2015 12:33:29 +0100 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: <1448971807-11118-1-git-send-email-wanpeng.li@hotmail.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5792 Lines: 173 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 I ran some tests with this patch, and I found no issues; so, you can add Tested-by: luca abeni 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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/