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

[Juri Lelli <juri.lelli@arm.com>]

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 <luca.abeni@unitn.it>
> Signed-off-by: Wanpeng Li <wanpeng.li@hotmail.com>
> ---
> 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
>