[PATCH v6] sched/deadline: fix earliest_dl.next logic

[PATCH v6] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

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 <luca.abeni@unitn.it>
Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
---
v5 -> v6:
 * take advantage of next_node
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 | 58 +++++--------------------------------------------
 1 file changed, 6 insertions(+), 52 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 8b0a15e..a35e24a 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -176,8 +176,10 @@ 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);
@@ -195,6 +197,9 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 
 		next_node = rb_next(&p->pushable_dl_tasks);
 		dl_rq->pushable_dl_tasks_leftmost = next_node;
+		if (next_node)
+			dl_rq->earliest_dl.next = rb_entry(next_node,
+				struct task_struct, pushable_dl_tasks)->dl.deadline;
 	}
 
 	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
@@ -782,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);
 	}
 }
 
@@ -839,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);
 	}
 }
@@ -1274,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:
-- 
1.9.1

Re: [PATCH v6] sched/deadline: fix earliest_dl.next logic

[Luca Abeni]

On 12/03/2015 10:42 AM, 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.
I just re-ran some tests with this version of the patch, and
it still looks ok.


			Luca


>
> Tested-by: Luca Abeni <luca.abeni@unitn.it>
> Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
> ---
> v5 -> v6:
>   * take advantage of next_node
> 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 | 58 +++++--------------------------------------------
>   1 file changed, 6 insertions(+), 52 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 8b0a15e..a35e24a 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -176,8 +176,10 @@ 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);
> @@ -195,6 +197,9 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>
>   		next_node = rb_next(&p->pushable_dl_tasks);
>   		dl_rq->pushable_dl_tasks_leftmost = next_node;
> +		if (next_node)
> +			dl_rq->earliest_dl.next = rb_entry(next_node,
> +				struct task_struct, pushable_dl_tasks)->dl.deadline;
>   	}
>
>   	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> @@ -782,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);
>   	}
>   }
>
> @@ -839,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);
>   	}
>   }
> @@ -1274,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:
>

Re: [PATCH v6] sched/deadline: fix earliest_dl.next logic

[Juri Lelli]

Hi,

On 03/12/15 17:42, 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 <luca.abeni@unitn.it>
> Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
> ---
> v5 -> v6:
>  * take advantage of next_node
> 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 | 58 +++++--------------------------------------------
>  1 file changed, 6 insertions(+), 52 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 8b0a15e..a35e24a 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -176,8 +176,10 @@ 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);
> @@ -195,6 +197,9 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>  
>  		next_node = rb_next(&p->pushable_dl_tasks);
>  		dl_rq->pushable_dl_tasks_leftmost = next_node;
> +		if (next_node)
> +			dl_rq->earliest_dl.next = rb_entry(next_node,
> +				struct task_struct, pushable_dl_tasks)->dl.deadline;

Small nitpick, we are breaking 80 columns here, checkpatch should have
complained. I guess a different indentation could help.

Apart from this, I couldn't spot any more problems with this patch.

Acked-by: Juri Lelli <juri.lelli@arm.com>

Thanks Wanpeng Li and Luca for your time on this!

Best,

- Juri

>  	}
>  
>  	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> @@ -782,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);
>  	}
>  }
>  
> @@ -839,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);
>  	}
>  }
> @@ -1274,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:
> -- 
> 1.9.1
> 

Re: [PATCH v6] sched/deadline: fix earliest_dl.next logic

[Peter Zijlstra]

On Fri, Dec 04, 2015 at 09:59:52AM +0000, Juri Lelli wrote:
> > +		if (next_node)
> > +			dl_rq->earliest_dl.next = rb_entry(next_node,
> > +				struct task_struct, pushable_dl_tasks)->dl.deadline;
> 
> Small nitpick, we are breaking 80 columns here, checkpatch should have
> complained. I guess a different indentation could help.
> 
> Apart from this, I couldn't spot any more problems with this patch.

So I don't mind the occasional violation of that rule if it aids in
better readable code.

However, that should now have included {} because the statement is
multi-line. Coding style suggests we have braces for anything over 1
line. I'll make that edit when applying, no need to resend yet another
time :-)

> Acked-by: Juri Lelli <juri.lelli@arm.com>

Thanks, I'll try and get it queued later today.

Re: [PATCH v6] sched/deadline: fix earliest_dl.next logic

[Wanpeng Li]

2015-12-03 17:42 GMT+08:00 Wanpeng Li <kernellwp@gmail.com>:

From: Wanpeng Li <wanpeng.li@hotmail.com>

>From my hotmail instead of gmail. :-)

Regards,
Wanpeng Li

> 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 <luca.abeni@unitn.it>
> Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
> ---
> v5 -> v6:
>  * take advantage of next_node
> 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 | 58 +++++--------------------------------------------
>  1 file changed, 6 insertions(+), 52 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 8b0a15e..a35e24a 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -176,8 +176,10 @@ 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);
> @@ -195,6 +197,9 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
>
>                 next_node = rb_next(&p->pushable_dl_tasks);
>                 dl_rq->pushable_dl_tasks_leftmost = next_node;
> +               if (next_node)
> +                       dl_rq->earliest_dl.next = rb_entry(next_node,
> +                               struct task_struct, pushable_dl_tasks)->dl.deadline;
>         }
>
>         rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
> @@ -782,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);
>         }
>  }
>
> @@ -839,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);
>         }
>  }
> @@ -1274,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:
> --
> 1.9.1
>



-- 
Regards,
Wanpeng Li

[tip:sched/core] sched/deadline: Fix the earliest_dl.next logic

[tip-bot for Wanpeng Li]

Commit-ID:  7d92de3a8285ab3dfd68aa3a99823acd5b190444
Gitweb:     http://git.kernel.org/tip/7d92de3a8285ab3dfd68aa3a99823acd5b190444
Author:     Wanpeng Li <kernellwp@gmail.com>
AuthorDate: Thu, 3 Dec 2015 17:42:10 +0800
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 6 Jan 2016 11:05:56 +0100

sched/deadline: Fix the 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.

Tested-by: Luca Abeni <luca.abeni@unitn.it>
Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Acked-by: Juri Lelli <juri.lelli@arm.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1449135730-27202-1-git-send-email-wanpeng.li@hotmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/deadline.c | 59 ++++++-------------------------------------------
 1 file changed, 7 insertions(+), 52 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 8b0a15e..cd64c97 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -176,8 +176,10 @@ 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);
@@ -195,6 +197,10 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 
 		next_node = rb_next(&p->pushable_dl_tasks);
 		dl_rq->pushable_dl_tasks_leftmost = next_node;
+		if (next_node) {
+			dl_rq->earliest_dl.next = rb_entry(next_node,
+				struct task_struct, pushable_dl_tasks)->dl.deadline;
+		}
 	}
 
 	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
@@ -782,42 +788,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 +817,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 +1251,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: