sched: fix race in schedule

Hi Ingo,

I found a race condition in scheduler.
The first report is the below;
http://lkml.org/lkml/2008/2/26/459

It took a bit long time to investigate and I couldn't have much time last week. It is hard to reproduce but -rt is little easier because it has preemptible spin lock and rcu.

Could you please check the scenario and the patch. It will be needed for the stable, too.

---
From: Hiroshi Shimamoto <[email protected]>

There is a race condition between schedule() and some dequeue/enqueue functions; rt_mutex_setprio(), __setscheduler() and sched_move_task().

When scheduling to idle, idle_balance() is called to pull tasks from other busy processor. It might drop the rq lock.
It means that those 3 functions encounter on_rq=0 and running=1. The current task should be put when running.

Here is a possible scenario;
CPU0 CPU1

    |                              schedule()
    |                              ->deactivate_task()
    |                              ->idle_balance()
    |                              -->load_balance_newidle()

rt_mutex_setprio() |
| --->double_lock_balance()
*get lock *rel lock
* on_rq=0, ruuning=1 |
* sched_class is changed |
*rel lock *get lock
: |
:
->put_prev_task_rt() ->pick_next_task_fair()
=> panic

The current process of CPU1(P1) is scheduling. Deactivated P1, and the scheduler looks for another process on other CPU's runqueue because CPU1 will be idle. idle_balance(), load_balance_newidle() and double_lock_balance() are called and double_lock_balance() could drop the rq lock. On the other hand, CPU0 is trying to boost the priority of P1. The result of boosting only P1's prio and sched_class are changed to RT. The sched entities of P1 and P1's group are never put. It makes cfs_rq invalid, because the cfs_rq has curr and no leaf, but pick_next_task_fair() is called, then the kernel panics.

Quoted 42 lines · Hiroshi Shimamoto

Hi Ingo,

I found a race condition in scheduler.
The first report is the below;
http://lkml.org/lkml/2008/2/26/459

It took a bit long time to investigate and I couldn't have much time last week. It is hard to reproduce but -rt is little easier because it has preemptible spin lock and rcu.

Could you please check the scenario and the patch. It will be needed for the stable, too.

---
From: Hiroshi Shimamoto <[email protected]>

There is a race condition between schedule() and some dequeue/enqueue functions; rt_mutex_setprio(), __setscheduler() and sched_move_task().

When scheduling to idle, idle_balance() is called to pull tasks from other busy processor. It might drop the rq lock.
It means that those 3 functions encounter on_rq=0 and running=1. The current task should be put when running.

Here is a possible scenario;
CPU0 CPU1

    |                              schedule()
    |                              ->deactivate_task()
    |                              ->idle_balance()
    |                              -->load_balance_newidle()

rt_mutex_setprio() |
| --->double_lock_balance()
*get lock *rel lock
* on_rq=0, ruuning=1 |
* sched_class is changed |
*rel lock *get lock
: |
:
->put_prev_task_rt() ->pick_next_task_fair()
=> panic

Quoted 9 lines

The current process of CPU1(P1) is scheduling. Deactivated P1, and the scheduler looks for another process on other CPU's runqueue because CPU1 will be idle. idle_balance(), load_balance_newidle() and double_lock_balance() are called and double_lock_balance() could drop the rq lock. On the other hand, CPU0 is trying to boost the priority of P1. The result of boosting only P1's prio and sched_class are changed to RT. The sched entities of P1 and P1's group are never put. It makes cfs_rq invalid, because the cfs_rq has curr and no leaf, but pick_next_task_fair() is called, then the kernel panics.

Very nice catch, this had me puzzled for a while. I'm not quite sure I fully understand. Could you explain why the below isn't sufficient?

---

kernel/sched.c +2 -1

index a0c79e9..ebd9fc5 100644
@@ -4067,10 +4067,11 @@ need_resched_nonpreemptible:
 		prev->sched_class->pre_schedule(rq, prev);
 #endif
 
+	prev->sched_class->put_prev_task(rq, prev);
+
 	if (unlikely(!rq->nr_running))
 		idle_balance(cpu, rq);
 
-	prev->sched_class->put_prev_task(rq, prev);
 	next = pick_next_task(rq, prev);
 
 	sched_info_switch(prev, next);

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

---
From: Hiroshi Shimamoto <[email protected]>

There is a race condition between schedule() and some dequeue/enqueue functions; rt_mutex_setprio(), __setscheduler() and sched_move_task().

When scheduling to idle, idle_balance() is called to pull tasks from other busy processor. It might drop the rq lock.
It means that those 3 functions encounter on_rq=0 and running=1. The current task should be put when running.

Here is a possible scenario;
CPU0 CPU1

    |                              schedule()
    |                              ->deactivate_task()
    |                              ->idle_balance()
    |                              -->load_balance_newidle()

rt_mutex_setprio() |
| --->double_lock_balance()
*get lock *rel lock
* on_rq=0, ruuning=1 |
* sched_class is changed |
*rel lock *get lock
: |
:
->put_prev_task_rt() ->pick_next_task_fair()
=> panic

The current process of CPU1(P1) is scheduling. Deactivated P1, and the scheduler looks for another process on other CPU's runqueue because CPU1 will be idle. idle_balance(), load_balance_newidle() and double_lock_balance() are called and double_lock_balance() could drop the rq lock. On the other hand, CPU0 is trying to boost the priority of P1. The result of boosting only P1's prio and sched_class are changed to RT. The sched entities of P1 and P1's group are never put. It makes cfs_rq invalid, because the cfs_rq has curr and no leaf, but pick_next_task_fair() is called, then the kernel panics.

Signed-off-by Hiroshi Shimamoto <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

CC [email protected]

---
 kernel/sched.c |    8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

Index: linux-2.6-2/kernel/sched.c
===================================================================

kernel/sched.c +7 -1

@@ -4062,6 +4062,13 @@ need_resched_nonpreemptible:
 		switch_count = &prev->nvcsw;
 	}
 
+	/*
+	 * ->pre_schedule() and idle_balance() can release the rq->lock so we
+	 * have to call ->put_prev_task() before we do the balancing calls,
+	 * otherwise its possible to see the rq in an inconsistent state.
+	 */
+	prev->sched_class->put_prev_task(rq, prev);
+
 #ifdef CONFIG_SMP
 	if (prev->sched_class->pre_schedule)
 		prev->sched_class->pre_schedule(rq, prev);

@@ -4070,7 +4077,6 @@ need_resched_nonpreemptible:
 	if (unlikely(!rq->nr_running))
 		idle_balance(cpu, rq);
 
-	prev->sched_class->put_prev_task(rq, prev);
 	next = pick_next_task(rq, prev);
 
 	sched_info_switch(prev, next);

Quoted 9 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Quoted 5 lines

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

thanks for working, I'm OK, and will test it soon.
IIRC, it came from the group scheduling, .23 probably doesn't have this issue.

Quoted 12 lines · Hiroshi Shimamoto

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

Quoted 4 lines

Quoted 2 lines

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

thanks for working, I'm OK, and will test it soon.
IIRC, it came from the group scheduling, .23 probably doesn't have this issue.

Might not have this exact race, but I've checked both .23 and .24, both can unlock the rq before we do ->put_prev_task(), leaving a window for potential nasties. I'm rather safe than sorry :-)

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

Quoted 9 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Quoted 6 lines

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

Unfortunately, I encountered similar panic with this patch on -rt. I'll look into this, again. I might have missed something...

Unable to handle kernel NULL pointer dereference at 0000000000000128 RIP:
 [<ffffffff802297f5>] pick_next_task_fair+0x2d/0x42

Quoted 12 lines · Hiroshi Shimamoto

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

Quoted 8 lines

Quoted 3 lines

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

Unfortunately, I encountered similar panic with this patch on -rt. I'll look into this, again. I might have missed something...

Unable to handle kernel NULL pointer dereference at 0000000000000128 RIP:
 [<ffffffff802297f5>] pick_next_task_fair+0x2d/0x42

:-(

OK, so that means I'm not getting it.

So what does your patch do that mine doesn't?

It removes the dependency of running (=task_current()) from on_rq (p->se.on_rq).

So how can a current task not be on the runqueue?

Only sched.c:dequeue_task() and sched_fair.c:account_entity_dequeue() set on_rq to 0, the only one changing rq->curr is schedule().

So the only scheme I can come up with is that we did dequeue p (on_rq == 0), but we didn't yet schedule so rq->curr == p.

Is this how you ended up with your previuos analysis that it must be due to a hole introduced by double_lock_balance()?

Because now we can seemingly call deactivate_task() and put_prev_task() in non-atomic fashion, but by placing the put_prev_task() before the load balance calls we should avoid doing that.

So what else is going on... /me puzzled

Quoted 39 lines · Peter Zijlstra

Quoted 12 lines · Hiroshi Shimamoto

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

Quoted 8 lines

Quoted 3 lines

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

Unfortunately, I encountered similar panic with this patch on -rt. I'll look into this, again. I might have missed something...

Unable to handle kernel NULL pointer dereference at 0000000000000128 RIP:
 [<ffffffff802297f5>] pick_next_task_fair+0x2d/0x42

:-(

OK, so that means I'm not getting it.

So what does your patch do that mine doesn't?

It removes the dependency of running (=task_current()) from on_rq (p->se.on_rq).

So how can a current task not be on the runqueue?

Only sched.c:dequeue_task() and sched_fair.c:account_entity_dequeue() set on_rq to 0, the only one changing rq->curr is schedule().

So the only scheme I can come up with is that we did dequeue p (on_rq == 0), but we didn't yet schedule so rq->curr == p.

Quoted 8 lines

Is this how you ended up with your previuos analysis that it must be due to a hole introduced by double_lock_balance()?

Because now we can seemingly call deactivate_task() and put_prev_task() in non-atomic fashion, but by placing the put_prev_task() before the load balance calls we should avoid doing that.

So what else is going on... /me puzzled

thanks for taking time.
I've tested it with debug tracer, it took several hours to half day to reproduce it on my box. And I got the possible scenario.

Before begin, I can tell that se->on_rq is changed at enqueue_task() or dequeue_task() in sched.c.

Here is the flow to panic which I got;

   CPU0                               CPU1
    |                              schedule()
    |                              ->deactivate_task()

    |                              -->dequeue_task()
    |                                  * on_rq=0
    |                              ->put_prev_task_fair()

    |                              ->idle_balance()
    |                              -->load_balance_newidle()

(a wakeup function) |

| --->double_lock_balance()
*get lock *rel lock

* wake up target is CPU1's curr |
->enqueue_task() |
* on_rq=1 |
->rt_mutex_setprio() |
* on_rq=1, ruuning=1 |
-->dequeue_task()!! |
-->put_prev_task_fair()!! |

Hiroshi Shimamoto

Quoted 75 lines · Hiroshi Shimamoto

Quoted 39 lines · Peter Zijlstra

Quoted 12 lines · Hiroshi Shimamoto

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Hiroshi Shimamoto

thanks, your patch looks nice to me.
I had focused setprio, on_rq=0 and running=1 situation, it makes me to fix these functions.
But one point, I've just noticed. I'm not sure on same situation against sched_rt. I think the pre_schedule() of rt has chance to drop rq lock. Is it OK?

Ah, you are quite right, that'll teach me to rush out a patch just because dinner is ready :-).

Quoted 8 lines

Quoted 3 lines

How about we submit the following patch for mainline and CC -stable to fix .23 and .24:

Unfortunately, I encountered similar panic with this patch on -rt. I'll look into this, again. I might have missed something...

Unable to handle kernel NULL pointer dereference at 0000000000000128 RIP:
 [<ffffffff802297f5>] pick_next_task_fair+0x2d/0x42

:-(

OK, so that means I'm not getting it.

So what does your patch do that mine doesn't?

It removes the dependency of running (=task_current()) from on_rq (p->se.on_rq).

So how can a current task not be on the runqueue?

Only sched.c:dequeue_task() and sched_fair.c:account_entity_dequeue() set on_rq to 0, the only one changing rq->curr is schedule().

So the only scheme I can come up with is that we did dequeue p (on_rq == 0), but we didn't yet schedule so rq->curr == p.

Quoted 8 lines

Is this how you ended up with your previuos analysis that it must be due to a hole introduced by double_lock_balance()?

Because now we can seemingly call deactivate_task() and put_prev_task() in non-atomic fashion, but by placing the put_prev_task() before the load balance calls we should avoid doing that.

So what else is going on... /me puzzled

thanks for taking time.
I've tested it with debug tracer, it took several hours to half day to reproduce it on my box. And I got the possible scenario.

Before begin, I can tell that se->on_rq is changed at enqueue_task() or dequeue_task() in sched.c.

Here is the flow to panic which I got;

   CPU0                               CPU1
    |                              schedule()
    |                              ->deactivate_task()

    |                              -->dequeue_task()
    |                                  * on_rq=0
    |                              ->put_prev_task_fair()

    |                              ->idle_balance()
    |                              -->load_balance_newidle()

(a wakeup function) |

| --->double_lock_balance()
*get lock *rel lock

Quoted 7 lines

* wake up target is CPU1's curr |

 ->enqueue_task()                      |
    * on_rq=1                          |
 ->rt_mutex_setprio()                  |
    * on_rq=1, ruuning=1               |
 -->dequeue_task()!!                   |
 -->put_prev_task_fair()!!             |

humm... this one should have caused the problem.

->put_prev_task() has been previously done in schedule() so we get 2 consequent ->put_prev_task() without set_curr_task/pick_next_task() being called in between
[ as a result, __enqueue_entitty() is called twice for CPU1's curr and that definitely corrupts an rb-tree ]

your initial patch doesn't have this problem. humm... logically-wise, it looks like a change of the 'current' which can be expressed by a pair :

(1) put_prev_task() + (2) pick_next_task() or set_curr_task() (both end up calling set_next_entity())

has to be 'atomic' wrt the rq->lock.

For schedule() that also involves a change of rq->curr.

Your initial patch seems to qualify for this rule... but I'm still thinking whether the current scheme is a bit 'hairy' :-/

[ ... ]

Quoted 41 lines

Quoted 21 lines

Before begin, I can tell that se->on_rq is changed at enqueue_task() or dequeue_task() in sched.c.

Here is the flow to panic which I got;

   CPU0                               CPU1
    |                              schedule()
    |                              ->deactivate_task()

    |                              -->dequeue_task()
    |                                  * on_rq=0
    |                              ->put_prev_task_fair()

    |                              ->idle_balance()
    |                              -->load_balance_newidle()

(a wakeup function) |

| --->double_lock_balance()
*get lock *rel lock

Quoted 7 lines

* wake up target is CPU1's curr |

 ->enqueue_task()                      |
    * on_rq=1                          |
 ->rt_mutex_setprio()                  |
    * on_rq=1, ruuning=1               |
 -->dequeue_task()!!                   |
 -->put_prev_task_fair()!!             |

humm... this one should have caused the problem.

->put_prev_task() has been previously done in schedule() so we get 2 consequent ->put_prev_task() without set_curr_task/pick_next_task() being called in between
[ as a result, __enqueue_entitty() is called twice for CPU1's curr and that definitely corrupts an rb-tree ]

your initial patch doesn't have this problem. humm... logically-wise, it looks like a change of the 'current' which can be expressed by a pair :

Quoted 6 lines

(1) put_prev_task() + (2) pick_next_task() or set_curr_task() (both end up calling set_next_entity())

has to be 'atomic' wrt the rq->lock.

For schedule() that also involves a change of rq->curr.

Right, this seems to 'rely' on rq->curr lagging behind put_prev_task().
So by doing something like:

---
diff --git a/kernel/sched.c b/kernel/sched.c

index a0c79e9..62d796f 100644

--- a/kernel/sched.c
+++ b/kernel/sched.c

kernel/sched.c +2 -0

@@ -4061,6 +4061,8 @@ need_resched_nonpreemptible:
                }
                switch_count = &prev->nvcsw;
        }
 
+       prev->sched_class->put_prev_task(rq, prev);
 
+       rq->curr = rq->idle;
 

  #ifdef CONFIG_SMP
        if (prev->sched_class->pre_schedule)

(quoted diff) +1 -0

@@ -4070,14 +4072,13 @@ need_resched_nonpreemptible:
 
        if (unlikely(!rq->nr_running))
                idle_balance(cpu, rq);
 
 -       prev->sched_class->put_prev_task(rq, prev);
        next = pick_next_task(rq, prev);
 
+       rq->curr = next;
 
 

We would avoid being considered running while we're not.

Quoted 88 lines · Peter Zijlstra

[ ... ]

Quoted 41 lines

Quoted 21 lines

Before begin, I can tell that se->on_rq is changed at enqueue_task() or dequeue_task() in sched.c.

Here is the flow to panic which I got;

   CPU0                               CPU1
    |                              schedule()
    |                              ->deactivate_task()

    |                              -->dequeue_task()
    |                                  * on_rq=0
    |                              ->put_prev_task_fair()

    |                              ->idle_balance()
    |                              -->load_balance_newidle()

(a wakeup function) |

| --->double_lock_balance()
*get lock *rel lock

Quoted 7 lines

* wake up target is CPU1's curr |

 ->enqueue_task()                      |
    * on_rq=1                          |
 ->rt_mutex_setprio()                  |
    * on_rq=1, ruuning=1               |
 -->dequeue_task()!!                   |
 -->put_prev_task_fair()!!             |

humm... this one should have caused the problem.

->put_prev_task() has been previously done in schedule() so we get 2 consequent ->put_prev_task() without set_curr_task/pick_next_task() being called in between
[ as a result, __enqueue_entitty() is called twice for CPU1's curr and that definitely corrupts an rb-tree ]

your initial patch doesn't have this problem. humm... logically-wise, it looks like a change of the 'current' which can be expressed by a pair :

Quoted 6 lines

(1) put_prev_task() + (2) pick_next_task() or set_curr_task() (both end up calling set_next_entity())

has to be 'atomic' wrt the rq->lock.

For schedule() that also involves a change of rq->curr.

Right, this seems to 'rely' on rq->curr lagging behind put_prev_task().
So by doing something like:

---
diff --git a/kernel/sched.c b/kernel/sched.c

index a0c79e9..62d796f 100644

--- a/kernel/sched.c
+++ b/kernel/sched.c

kernel/sched.c +2 -0

@@ -4061,6 +4061,8 @@ need_resched_nonpreemptible:
                }
                switch_count = &prev->nvcsw;
        }
 
+       prev->sched_class->put_prev_task(rq, prev);
 
+       rq->curr = rq->idle;
 

  #ifdef CONFIG_SMP
        if (prev->sched_class->pre_schedule)

(quoted diff) +1 -0

@@ -4070,14 +4072,13 @@ need_resched_nonpreemptible:
 
        if (unlikely(!rq->nr_running))
                idle_balance(cpu, rq);
 
 -       prev->sched_class->put_prev_task(rq, prev);
        next = pick_next_task(rq, prev);
 
+       rq->curr = next;
 
 

Review need_resched_nonpreemptible:

Quoted 10 lines

(quoted diff) +0 -0

        sched_info_switch(prev, next);
 
 
        if (likely(prev != next)) {
                rq->nr_switches++;
 -               rq->curr = next;
                ++*switch_count;
 
                context_switch(rq, prev, next); /* unlocks the rq */
 ---

hum, I'm quite suspicious about this approach... mainly, due to the fact that I think your next assumption is wrong:
(unless we specify 'running' wrt to whom)

Quoted 3 lines

We would avoid being considered running while we're not.

the fact is that we are (i.e. 'prev') actually running on a cpu until some point in context_switch().

At the very least, the load balancer has to exactly know who is the 'current' on other cpus to treat such tasks differently.

With this patch, the load balancer can be confused/broken by the fact that 'prev' is considered for migration as a "not-on-rq and not-running" task [ from another cpu at the moment when either pre_schedule() or idle_balance() drop a rq->lock of prev's cpu ].

well, the version of task_current() for __ARCH_WANT_UNLOCKED_CTXSW would fix it if used by default.

But maybe there is something esle that would be exposed by the 'rq->curr = rq->idle' manipulation... I can't provide examples right now though (I need to think on it).

Quoted 115 lines · Dmitry Adamushko

Quoted 87 lines · Peter Zijlstra

[ ... ]

Quoted 41 lines

Quoted 21 lines

Before begin, I can tell that se->on_rq is changed at enqueue_task() or dequeue_task() in sched.c.

Here is the flow to panic which I got;

   CPU0                               CPU1
    |                              schedule()
    |                              ->deactivate_task()

    |                              -->dequeue_task()
    |                                  * on_rq=0
    |                              ->put_prev_task_fair()

    |                              ->idle_balance()
    |                              -->load_balance_newidle()

(a wakeup function) |

| --->double_lock_balance()
*get lock *rel lock

Quoted 7 lines

* wake up target is CPU1's curr |

 ->enqueue_task()                      |
    * on_rq=1                          |
 ->rt_mutex_setprio()                  |
    * on_rq=1, ruuning=1               |
 -->dequeue_task()!!                   |
 -->put_prev_task_fair()!!             |

humm... this one should have caused the problem.

->put_prev_task() has been previously done in schedule() so we get 2 consequent ->put_prev_task() without set_curr_task/pick_next_task() being called in between
[ as a result, __enqueue_entitty() is called twice for CPU1's curr and that definitely corrupts an rb-tree ]

your initial patch doesn't have this problem. humm... logically-wise, it looks like a change of the 'current' which can be expressed by a pair :

Quoted 6 lines

(1) put_prev_task() + (2) pick_next_task() or set_curr_task() (both end up calling set_next_entity())

has to be 'atomic' wrt the rq->lock.

For schedule() that also involves a change of rq->curr.

Right, this seems to 'rely' on rq->curr lagging behind put_prev_task().
So by doing something like:

---
diff --git a/kernel/sched.c b/kernel/sched.c

index a0c79e9..62d796f 100644

--- a/kernel/sched.c
+++ b/kernel/sched.c

kernel/sched.c +2 -0

@@ -4061,6 +4061,8 @@ need_resched_nonpreemptible:
                }
                switch_count = &prev->nvcsw;
        }
 
+       prev->sched_class->put_prev_task(rq, prev);
 
+       rq->curr = rq->idle;
 

  #ifdef CONFIG_SMP
        if (prev->sched_class->pre_schedule)

(quoted diff) +1 -0

@@ -4070,14 +4072,13 @@ need_resched_nonpreemptible:
 
        if (unlikely(!rq->nr_running))
                idle_balance(cpu, rq);
 
 -       prev->sched_class->put_prev_task(rq, prev);
        next = pick_next_task(rq, prev);
 
+       rq->curr = next;
 
 

Review need_resched_nonpreemptible:

Quoted 10 lines

(quoted diff) +0 -0

        sched_info_switch(prev, next);
 
 
        if (likely(prev != next)) {
                rq->nr_switches++;
 -               rq->curr = next;
                ++*switch_count;
 
                context_switch(rq, prev, next); /* unlocks the rq */
 ---

hum, I'm quite suspicious about this approach... mainly, due to the fact that I think your next assumption is wrong:
(unless we specify 'running' wrt to whom)

Quoted 2 lines

We would avoid being considered running while we're not.

the fact is that we are (i.e. 'prev') actually running on a cpu until some point in context_switch().

At the very least, the load balancer has to exactly know who is the 'current' on other cpus to treat such tasks differently.

With this patch, the load balancer can be confused/broken by the fact that 'prev' is considered for migration as a "not-on-rq and not-running" task [ from another cpu at the moment when either pre_schedule() or idle_balance() drop a rq->lock of prev's cpu ].

Quoted 6 lines

well, the version of task_current() for __ARCH_WANT_UNLOCKED_CTXSW would fix it if used by default.

But maybe there is something esle that would be exposed by the 'rq->curr = rq->idle' manipulation... I can't provide examples right now though (I need to think on it).

I share your concerns, I don't really like it either. Just spewing out ideas here - bad ideas it seems :-/

Ingo also suggested moving the balance calls right before deactivate_task(), but that gives a whole other set of head-aches.

[ ... ]

Quoted 10 lines

Quoted 3 lines

But maybe there is something esle that would be exposed by the 'rq->curr = rq->idle' manipulation... I can't provide examples right now though (I need to think on it).

I share your concerns, I don't really like it either. Just spewing out ideas here - bad ideas it seems :-/

Ingo also suggested moving the balance calls right before deactivate_task(), but that gives a whole other set of head-aches.

Well, what will we do about this issue?
I see you're thinking to fix inconsistency in scheduler, right? I agree about it.

However, I don't think it's good to remain this issue long time in the -stable kernel.

Could you please let me know what I can do?

Hiroshi Shimamoto

Quoted 19 lines · Hiroshi Shimamoto

[ ... ]

Quoted 10 lines

Quoted 3 lines

But maybe there is something esle that would be exposed by the 'rq->curr = rq->idle' manipulation... I can't provide examples right now though (I need to think on it).

I share your concerns, I don't really like it either. Just spewing out ideas here - bad ideas it seems :-/

Ingo also suggested moving the balance calls right before deactivate_task(), but that gives a whole other set of head-aches.

Well, what will we do about this issue?
I see you're thinking to fix inconsistency in scheduler, right? I agree about it.

Quoted 4 lines

However, I don't think it's good to remain this issue long time in the -stable kernel.

Could you please let me know what I can do?

IMHO, the safest solution for the time being (and esp. for -stable) would be to proceed with Hiroshi's patch. It looks safe and it does fix a real problem.

Hi Ingo,

I found a race condition in scheduler.
The first report is the below;
http://lkml.org/lkml/2008/2/26/459

It took a bit long time to investigate and I couldn't have much time last week. It is hard to reproduce but -rt is little easier because it has preemptible spin lock and rcu.

Could you please check the scenario and the patch. It will be needed for the stable, too.

---
From: Hiroshi Shimamoto <[email protected]>

There is a race condition between schedule() and some dequeue/enqueue functions; rt_mutex_setprio(), __setscheduler() and sched_move_task().

When scheduling to idle, idle_balance() is called to pull tasks from other busy processor. It might drop the rq lock.
It means that those 3 functions encounter on_rq=0 and running=1. The current task should be put when running.

Here is a possible scenario;
CPU0 CPU1

    |                              schedule()
    |                              ->deactivate_task()
    |                              ->idle_balance()
    |                              -->load_balance_newidle()

rt_mutex_setprio() |

| --->double_lock_balance()

*get lock *rel lock
* on_rq=0, ruuning=1 |
* sched_class is changed |
*rel lock *get lock

->put_prev_task_rt() ->pick_next_task_fair()
=> panic

The current process of CPU1(P1) is scheduling. Deactivated P1, and the scheduler looks for another process on other CPU's runqueue because CPU1 will be idle. idle_balance(), load_balance_newidle() and double_lock_balance() are called and double_lock_balance() could drop the rq lock. On the other hand, CPU0 is trying to boost the priority of P1. The result of boosting only P1's prio and sched_class are changed to RT. The sched entities of P1 and P1's group are never put. It makes cfs_rq invalid, because the cfs_rq has curr and no leaf, but pick_next_task_fair() is called, then the kernel panics.

Signed-off-by Hiroshi Shimamoto <[email protected]>

---
 kernel/sched.c |   38 ++++++++++++++++----------------------
 1 files changed, 16 insertions(+), 22 deletions(-)

kernel/sched.c +5 -7

index 52b9867..eedf748 100644
@@ -4268,11 +4268,10 @@ void rt_mutex_setprio(struct task_struct *p,
 int prio) oldprio = p->prio;
 	on_rq = p->se.on_rq;
 	running = task_current(rq, p);
-	if (on_rq) {
+	if (on_rq)
 		dequeue_task(rq, p, 0);
-		if (running)
-			p->sched_class->put_prev_task(rq, p);
-	}
+	if (running)
+		p->sched_class->put_prev_task(rq, p);
 
 	if (rt_prio(prio))
 		p->sched_class = &rt_sched_class;

@@ -4281,10 +4280,9 @@ void rt_mutex_setprio(struct task_struct *p,
 int prio)
 
 	p->prio = prio;
 
+	if (running)
+		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		if (running)
-			p->sched_class->set_curr_task(rq);
-
 		enqueue_task(rq, p, 0);
 

kernel/sched.c +11 -15

 		check_class_changed(rq, p, prev_class, oldprio, running);

@@ -4581,19 +4579,17 @@ recheck:
 	update_rq_clock(rq);
 	on_rq = p->se.on_rq;
 	running = task_current(rq, p);
-	if (on_rq) {
+	if (on_rq)
 		deactivate_task(rq, p, 0);
-		if (running)
-			p->sched_class->put_prev_task(rq, p);
-	}
+	if (running)
+		p->sched_class->put_prev_task(rq, p);
 
 	oldprio = p->prio;
 	__setscheduler(rq, p, policy, param->sched_priority);
 
+	if (running)
+		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		if (running)
-			p->sched_class->set_curr_task(rq);
-
 		activate_task(rq, p, 0);
 
 		check_class_changed(rq, p, prev_class, oldprio, running);

@@ -7617,11 +7613,10 @@ void sched_move_task(struct task_struct *tsk)
 	running = task_current(rq, tsk);
 	on_rq = tsk->se.on_rq;
 
-	if (on_rq) {
+	if (on_rq)
 		dequeue_task(rq, tsk, 0);
-		if (unlikely(running))
-			tsk->sched_class->put_prev_task(rq, tsk);
-	}
+	if (unlikely(running))
+		tsk->sched_class->put_prev_task(rq, tsk);
 
 	set_task_rq(tsk, task_cpu(tsk));
 

@@ -7630,11 +7625,10 @@ void sched_move_task(struct task_struct *tsk)
 		tsk->sched_class->moved_group(tsk);
 #endif
 
-	if (on_rq) {
-		if (unlikely(running))
-			tsk->sched_class->set_curr_task(rq);
+	if (unlikely(running))
+		tsk->sched_class->set_curr_task(rq);
+	if (on_rq)
 		enqueue_task(rq, tsk, 0);
-	}
 
 	task_rq_unlock(rq, &flags);
 }