Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753843AbbKXJe0 (ORCPT ); Tue, 24 Nov 2015 04:34:26 -0500 Received: from foss.arm.com ([217.140.101.70]:60724 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753822AbbKXJeX (ORCPT ); Tue, 24 Nov 2015 04:34:23 -0500 Date: Tue, 24 Nov 2015 09:34:44 +0000 From: Juri Lelli To: Wanpeng Li Cc: Ingo Molnar , Peter Zijlstra , linux-kernel@vger.kernel.org Subject: Re: [PATCH v3] sched/deadline: fix earliest_dl.next logic Message-ID: <20151124093444.GJ26372@e106622-lin> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: 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: 5968 Lines: 156 Hi, On 24/11/15 09:58, Wanpeng Li wrote: > Ping Peterz, :-) > On 11/19/15 6:11 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 > >--- > >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; > > } > > 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; On a second thought, this might be useless as deadlines can wraparound. However, there are other things that I need to check about pull_dl_ tasks(). Please, bear with me for a few other days :-). Thanks, - Juri > > } > > static inline int has_pushable_dl_tasks(struct rq *rq) > >@@ -775,42 +787,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); > > } > > } > >@@ -832,7 +816,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); > > } > > } > >@@ -1267,28 +1250,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/