[PATCH 0/2] sched: pick and check task if double_lock_balance() unlock the rq

[PATCH 0/2] sched: pick and check task if double_lock_balance() unlock the rq

[Li Bin]

Li Bin (1):
  sched/deadline.c: pick and check task if double_lock_balance() unlock
    the rq

Zhou Chengming (1):
  sched/rt.c: pick and check task if double_lock_balance() unlock the
    rq

 kernel/sched/deadline.c | 48 +++++++++++++++++++++++-------------------------
 kernel/sched/rt.c       | 49 +++++++++++++++++++++++--------------------------
 2 files changed, 46 insertions(+), 51 deletions(-)

-- 
1.7.12.4

[PATCH 1/2] sched/rt.c: pick and check task if double_lock_balance() unlock the rq

[Li Bin]

From: Zhou Chengming <zhouchengming1@huawei.com>

push_rt_task() pick the first pushable task and find an eligible
lowest_rq, then double_lock_balance(rq, lowest_rq). So if
double_lock_balance() unlock the rq (when double_lock_balance() return 1),
we have to check if this task is still on the rq.

The problem is that the check conditions are not sufficient:

if (unlikely(task_rq(task) != rq ||
	     !cpumask_test_cpu(lowest_rq->cpu, &task->cpus_allowed) ||
	     task_running(rq, task) ||
	     !rt_task(task) ||
	     !task_on_rq_queued(task))) {

cpu2				cpu1			cpu0
push_rt_task(rq1)
  pick task_A on rq1
  find rq0
    double_lock_balance(rq1, rq0)
      unlock(rq1)
				rq1 __schedule
				  pick task_A run
				task_A sleep (dequeued)
      lock(rq0)
      lock(rq1)
    do_above_check(task_A)
      task_rq(task_A) == rq1
      cpus_allowed unchanged
      task_running == false
      rt_task(task_A) == true
							try_to_wake_up(task_A)
							  select_cpu = cpu3
							  enqueue(rq3, task_A)
							  task_A->on_rq = 1
      task_on_rq_queued(task_A)
    above_check passed, return rq0
    ...
    migrate task_A from rq1 to rq0

So we can't rely on these checks of task_A to make sure the task_A is
still on the rq1, even though we hold the rq1->lock. This patch will
repick the first pushable task to be sure the task is still on the rq.

Signed-off-by: Zhou Chengming <zhouchengming1@huawei.com>
Signed-off-by: Li Bin <huawei.libin@huawei.com>
---
 kernel/sched/rt.c | 49 +++++++++++++++++++++++--------------------------
 1 file changed, 23 insertions(+), 26 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index aad49451..e51d574 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1695,6 +1695,26 @@ static int find_lowest_rq(struct task_struct *task)
 	return -1;
 }
 
+static struct task_struct *pick_next_pushable_task(struct rq *rq)
+{
+	struct task_struct *p;
+
+	if (!has_pushable_tasks(rq))
+		return NULL;
+
+	p = plist_first_entry(&rq->rt.pushable_tasks,
+			      struct task_struct, pushable_tasks);
+
+	BUG_ON(rq->cpu != task_cpu(p));
+	BUG_ON(task_current(rq, p));
+	BUG_ON(p->nr_cpus_allowed <= 1);
+
+	BUG_ON(!task_on_rq_queued(p));
+	BUG_ON(!rt_task(p));
+
+	return p;
+}
+
 /* Will lock the rq it finds */
 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 {
@@ -1726,13 +1746,10 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 			 * We had to unlock the run queue. In
 			 * the mean time, task could have
 			 * migrated already or had its affinity changed.
-			 * Also make sure that it wasn't scheduled on its rq.
 			 */
-			if (unlikely(task_rq(task) != rq ||
-				     !cpumask_test_cpu(lowest_rq->cpu, &task->cpus_allowed) ||
-				     task_running(rq, task) ||
-				     !rt_task(task) ||
-				     !task_on_rq_queued(task))) {
+			struct task_struct *next_task = pick_next_pushable_task(rq);
+			if (unlikely(next_task != task ||
+				     !cpumask_test_cpu(lowest_rq->cpu, &task->cpus_allowed))) {
 
 				double_unlock_balance(rq, lowest_rq);
 				lowest_rq = NULL;
@@ -1752,26 +1769,6 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 	return lowest_rq;
 }
 
-static struct task_struct *pick_next_pushable_task(struct rq *rq)
-{
-	struct task_struct *p;
-
-	if (!has_pushable_tasks(rq))
-		return NULL;
-
-	p = plist_first_entry(&rq->rt.pushable_tasks,
-			      struct task_struct, pushable_tasks);
-
-	BUG_ON(rq->cpu != task_cpu(p));
-	BUG_ON(task_current(rq, p));
-	BUG_ON(p->nr_cpus_allowed <= 1);
-
-	BUG_ON(!task_on_rq_queued(p));
-	BUG_ON(!rt_task(p));
-
-	return p;
-}
-
 /*
  * If the current CPU has more than one RT task, see if the non
  * running task can migrate over to a CPU that is running a task
-- 
1.7.12.4

Re: [PATCH 1/2] sched/rt.c: pick and check task if double_lock_balance() unlock the rq

[Steven Rostedt]

On Thu, 12 Apr 2018 18:58:54 +0800
Li Bin <huawei.libin@huawei.com> wrote:

> @@ -1726,13 +1746,10 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
>  			 * We had to unlock the run queue. In
>  			 * the mean time, task could have
>  			 * migrated already or had its affinity changed.
> -			 * Also make sure that it wasn't scheduled on its rq.
>  			 */
> -			if (unlikely(task_rq(task) != rq ||
> -				     !cpumask_test_cpu(lowest_rq->cpu, &task->cpus_allowed) ||
> -				     task_running(rq, task) ||
> -				     !rt_task(task) ||
> -				     !task_on_rq_queued(task))) {
> +			struct task_struct *next_task = pick_next_pushable_task(rq);

Could you declare next_task above the comment. It's better styling.

	struct task_struct *next_task;
	/*
	 * Comment
	 */
	next_task = pick_next_pushable_task(rq);


-- Steve

> +			if (unlikely(next_task != task ||
> +				     !cpumask_test_cpu(lowest_rq->cpu, &task->cpus_allowed))) {
>  
>  				double_unlock_balance(rq, lowest_rq);
>  				lowest_rq = NULL;
> @@ -1752,26 +1769,6 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)

[PATCH 2/2] sched/deadline.c: pick and check task if double_lock_balance() unlock the rq

[Li Bin]

push_dl_task() pick the first pushable task and find an eligible
later_rq, then double_lock_balance(rq, lowest_rq). So if
double_lock_balance() unlock the rq (when double_lock_balance() return
1), we have to check if this task is still on the rq.

The problem is that the check conditions are not sufficient:

if (unlikely(task_rq(task) != rq ||
             !cpumask_test_cpu(later_rq->cpu, &task->cpus_allowed) ||
             task_running(rq, task) ||
             !dl_task(task) ||
             !task_on_rq_queued(task))) {

cpu2                                cpu1                    cpu0
push_dl_task(rq1)
  pick task_A on rq1
  find rq0
    double_lock_balance(rq1, rq0)
      unlock(rq1)
                            rq1 __schedule
                              pick task_A run
                            task_A sleep (dequeued)
      lock(rq0)
      lock(rq1)
    do_above_check(task_A)
      task_rq(task_A) == rq1
      cpus_allowed unchanged
      task_running == false
      dl_task(task_A) == true
                                                    try_to_wake_up(task_A)
                                                      select_cpu = cpu3
                                                      enqueue(rq3, task_A)
                                                      task_A->on_rq = 1
      task_on_rq_queued(task_A)
    above_check passed, return rq0
    ...
    migrate task_A from rq1 to rq0

So we can't rely on these checks of task_A to make sure the task_A is
still on the rq1, even though we hold the rq1->lock. This patch will
repick the first pushable task to be sure the task is still on the rq.

Signed-off-by: Li Bin <huawei.libin@huawei.com>
---
 kernel/sched/deadline.c | 48 +++++++++++++++++++++++-------------------------
 1 file changed, 23 insertions(+), 25 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 9df0978..87cd7ca 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1936,6 +1936,26 @@ static int find_later_rq(struct task_struct *task)
 	return -1;
 }
 
+static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
+{
+	struct task_struct *p;
+
+	if (!has_pushable_dl_tasks(rq))
+		return NULL;
+
+	p = rb_entry(rq->dl.pushable_dl_tasks_root.rb_leftmost,
+		     struct task_struct, pushable_dl_tasks);
+
+	BUG_ON(rq->cpu != task_cpu(p));
+	BUG_ON(task_current(rq, p));
+	BUG_ON(p->nr_cpus_allowed <= 1);
+
+	BUG_ON(!task_on_rq_queued(p));
+	BUG_ON(!dl_task(p));
+
+	return p;
+}
+
 /* Locks the rq it finds */
 static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
 {
@@ -1965,11 +1985,9 @@ static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
 
 		/* Retry if something changed. */
 		if (double_lock_balance(rq, later_rq)) {
-			if (unlikely(task_rq(task) != rq ||
-				     !cpumask_test_cpu(later_rq->cpu, &task->cpus_allowed) ||
-				     task_running(rq, task) ||
-				     !dl_task(task) ||
-				     !task_on_rq_queued(task))) {
+			struct task_struct *next_task = pick_next_pushable_dl_task(rq);
+			if (unlikely(next_task != task ||
+						!cpumask_test_cpu(later_rq->cpu, &task->cpus_allowed))) {
 				double_unlock_balance(rq, later_rq);
 				later_rq = NULL;
 				break;
@@ -1994,26 +2012,6 @@ static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
 	return later_rq;
 }
 
-static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
-{
-	struct task_struct *p;
-
-	if (!has_pushable_dl_tasks(rq))
-		return NULL;
-
-	p = rb_entry(rq->dl.pushable_dl_tasks_root.rb_leftmost,
-		     struct task_struct, pushable_dl_tasks);
-
-	BUG_ON(rq->cpu != task_cpu(p));
-	BUG_ON(task_current(rq, p));
-	BUG_ON(p->nr_cpus_allowed <= 1);
-
-	BUG_ON(!task_on_rq_queued(p));
-	BUG_ON(!dl_task(p));
-
-	return p;
-}
-
 /*
  * See if the non running -deadline tasks on this rq
  * can be sent to some other CPU where they can preempt
-- 
1.7.12.4

Re: [PATCH 2/2] sched/deadline.c: pick and check task if double_lock_balance() unlock the rq

[Steven Rostedt]

On Thu, 12 Apr 2018 18:58:55 +0800
Li Bin <huawei.libin@huawei.com> wrote:

> @@ -1965,11 +1985,9 @@ static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
>  
>  		/* Retry if something changed. */
>  		if (double_lock_balance(rq, later_rq)) {
> -			if (unlikely(task_rq(task) != rq ||
> -				     !cpumask_test_cpu(later_rq->cpu, &task->cpus_allowed) ||
> -				     task_running(rq, task) ||
> -				     !dl_task(task) ||
> -				     !task_on_rq_queued(task))) {
> +			struct task_struct *next_task = pick_next_pushable_dl_task(rq);

I would do the same thing here, and add the comment from rt.c as it
is the same reason.

-- Steve

> +			if (unlikely(next_task != task ||
> +						!cpumask_test_cpu(later_rq->cpu, &task->cpus_allowed))) {
>  				double_unlock_balance(rq, later_rq);
>  				later_rq = NULL;

Re: [PATCH 0/2] sched: pick and check task if double_lock_balance() unlock the rq

[Peter Zijlstra]

On Thu, Apr 12, 2018 at 06:58:53PM +0800, Li Bin wrote:
> Li Bin (1):
>   sched/deadline.c: pick and check task if double_lock_balance() unlock
>     the rq
> 
> Zhou Chengming (1):
>   sched/rt.c: pick and check task if double_lock_balance() unlock the
>     rq
> 

Much thanks!

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

Ingo, please apply.

Re: [PATCH 0/2] sched: pick and check task if double_lock_balance() unlock the rq

[Steven Rostedt]

On Thu, 12 Apr 2018 14:11:45 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Thu, Apr 12, 2018 at 06:58:53PM +0800, Li Bin wrote:
> > Li Bin (1):
> >   sched/deadline.c: pick and check task if double_lock_balance() unlock
> >     the rq
> > 
> > Zhou Chengming (1):
> >   sched/rt.c: pick and check task if double_lock_balance() unlock the
> >     rq
> >   
> 
> Much thanks!
> 
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> Ingo, please apply.

You can add my:

Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

but I would still like to see the declaration of next_task before the
comment, just for style concerns.

-- Steve

Re: [PATCH 0/2] sched: pick and check task if double_lock_balance() unlock the rq

[Libin (Huawei)]

在 2018/4/12 20:20, Steven Rostedt 写道:
> On Thu, 12 Apr 2018 14:11:45 +0200
> Peter Zijlstra <peterz@infradead.org> wrote:
> 
>> On Thu, Apr 12, 2018 at 06:58:53PM +0800, Li Bin wrote:
>>> Li Bin (1):
>>>    sched/deadline.c: pick and check task if double_lock_balance() unlock
>>>      the rq
>>>
>>> Zhou Chengming (1):
>>>    sched/rt.c: pick and check task if double_lock_balance() unlock the
>>>      rq
>>>    
>>
>> Much thanks!
>>
>> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
>>
>> Ingo, please apply.
> 
> You can add my:
> 
> Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> 
> but I would still like to see the declaration of next_task before the
> comment, just for style concerns.

Ok, I will resend the patchset v2.

Thanks,
Li Bin

> 
> -- Steve
> 
> .
>