rcu_dereference() without protection in select_task_rq_fair()

rcu_dereference() without protection in select_task_rq_fair()

[Paul E. McKenney]

Hello, Peter,

My lockdep-ified RCU complains about the for_each_domain() in
select_task_rq_fair(), see below for the lockdep complaint.  I added
rcu_dereference_check() annotations as follows:

#define for_each_domain_rd(p) \
	rcu_dereference_check((p), \
			      rcu_read_lock_sched_held() || \
			      lockdep_is_held(&sched_domains_mutex))

#define for_each_domain(cpu, __sd) \
	for (__sd = for_each_domain_rd(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)

In other words, I believe (perhaps incorrectly) that for_each_domain()
can be called either within an RCU-sched read-side critical section or
with sched_domains_mutex held.  Lockdep claims that no locks of any
kind, RCU or otherwise, were held.  I considered the possibility that
this was an initialization-time thing, but the code traverses CPU
structures rather than task structures.

One other possibility is that this is safe due to the fact that we are
booting up, before the second CPU has come online.  Are you relying on
this?

For reference, here is the definition of rcu_read_lock_sched_held():

static inline int rcu_read_lock_sched_held(void)
{
	int lockdep_opinion = 0;

	if (debug_locks)
		lockdep_opinion = lock_is_held(&rcu_sched_lock_map);
	return lockdep_opinion || preempt_count() != 0;
}

Help?

							Thanx, Paul

==============================================
[ BUG: Unsafe rcu_dereference_check() usage! ]
----------------------------------------------
kernel/sched_fair.c:1464 invoked rcu_dereference_check() without protection!

other info that might help us debug this:

no locks held by swapper/0.

stack backtrace:
Pid: 0, comm: swapper Not tainted 2.6.33-rc7-autokern1 #1
Call Trace:
 [<ffffffff81060c30>] lockdep_rcu_dereference+0x8a/0x92
 [<ffffffff81033ec4>] select_task_rq_fair+0xc1/0x686
 [<ffffffff8105173d>] ? __task_pid_nr_ns+0x0/0xb2
 [<ffffffff810353f4>] wake_up_new_task+0x1e/0x13e
 [<ffffffff8105173d>] ? __task_pid_nr_ns+0x0/0xb2
 [<ffffffff810389a2>] do_fork+0x2ad/0x329
 [<ffffffff8152c7ae>] ? kernel_init+0x0/0x199
 [<ffffffff81009cc3>] kernel_thread+0x7d/0x8d
 [<ffffffff8152c7ae>] ? kernel_init+0x0/0x199
 [<ffffffff81003750>] ? kernel_thread_helper+0x0/0x10
 [<ffffffff81033513>] ? nr_context_switches+0x3f/0x51
 [<ffffffff812e4aad>] rest_init+0x21/0xc2
 [<ffffffff8152ccc9>] start_kernel+0x382/0x38f
 [<ffffffff8152c299>] x86_64_start_reservations+0xa9/0xad
 [<ffffffff8152c383>] x86_64_start_kernel+0xe6/0xed
Setting APIC routing to flat
..TIMER: vector=0x30 apic1=0 pin1=2 apic2=-1 pin2=-1
CPU0: Intel(R) Xeon(R) CPU           E5440  @ 2.83GHz stepping 06
lockdep: fixing up alternatives.
Booting Node   0, Processors  #1lockdep: fixing up alternatives.
 #2lockdep: fixing up alternatives.
 #3lockdep: fixing up alternatives.
 #4lockdep: fixing up alternatives.
 #5lockdep: fixing up alternatives.
 #6lockdep: fixing up alternatives.
 #7 Ok.
Brought up 8 CPUs
Total of 8 processors activated (45335.31 BogoMIPS).
NET: Registered protocol family 16
ACPI: bus type pci registered

Re: rcu_dereference() without protection in select_task_rq_fair()

[Peter Zijlstra]

On Thu, 2010-02-11 at 08:52 -0800, Paul E. McKenney wrote:
> Hello, Peter,
> 
> My lockdep-ified RCU complains about the for_each_domain() in
> select_task_rq_fair(), see below for the lockdep complaint.  I added
> rcu_dereference_check() annotations as follows:
> 
> #define for_each_domain_rd(p) \
>         rcu_dereference_check((p), \
>                               rcu_read_lock_sched_held() || \
>                               lockdep_is_held(&sched_domains_mutex))
> 
> #define for_each_domain(cpu, __sd) \
>         for (__sd = for_each_domain_rd(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
> 
> In other words, I believe (perhaps incorrectly) that for_each_domain()
> can be called either within an RCU-sched read-side critical section or
> with sched_domains_mutex held.  Lockdep claims that no locks of any
> kind, RCU or otherwise, were held.  I considered the possibility that
> this was an initialization-time thing, but the code traverses CPU
> structures rather than task structures.
> 
> One other possibility is that this is safe due to the fact that we are
> booting up, before the second CPU has come online.  Are you relying on
> this?
> 
> For reference, here is the definition of rcu_read_lock_sched_held():
> 
> static inline int rcu_read_lock_sched_held(void)
> {
>         int lockdep_opinion = 0;
> 
>         if (debug_locks)
>                 lockdep_opinion = lock_is_held(&rcu_sched_lock_map);
>         return lockdep_opinion || preempt_count() != 0;
> }
> 
> Help? 

We use synchronize_sched() and preempt_disable() for the sched domain
stuff. The comment above for_each_domain():

/*
 * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
 * See detach_destroy_domains: synchronize_sched for details.
 *
 * The domain tree of any CPU may only be accessed from within
 * preempt-disabled sections.
 */
#define for_each_domain(cpu, __sd) \
        for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)

explains this usage, also see detach_destroy_domains().

So one thing you can do is add (preempt_count() & ~PREEMPT_ACTIVE) to
the rcu_read_lock_sched_held() function to catch all those cases that
rely on preemption without having to add annotations to everything that
disables preemption.

Re: rcu_dereference() without protection in select_task_rq_fair()

[Paul E. McKenney]

On Sun, Feb 14, 2010 at 11:12:38AM +0100, Peter Zijlstra wrote:
> On Thu, 2010-02-11 at 08:52 -0800, Paul E. McKenney wrote:
> > Hello, Peter,
> > 
> > My lockdep-ified RCU complains about the for_each_domain() in
> > select_task_rq_fair(), see below for the lockdep complaint.  I added
> > rcu_dereference_check() annotations as follows:
> > 
> > #define for_each_domain_rd(p) \
> >         rcu_dereference_check((p), \
> >                               rcu_read_lock_sched_held() || \
> >                               lockdep_is_held(&sched_domains_mutex))
> > 
> > #define for_each_domain(cpu, __sd) \
> >         for (__sd = for_each_domain_rd(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
> > 
> > In other words, I believe (perhaps incorrectly) that for_each_domain()
> > can be called either within an RCU-sched read-side critical section or
> > with sched_domains_mutex held.  Lockdep claims that no locks of any
> > kind, RCU or otherwise, were held.  I considered the possibility that
> > this was an initialization-time thing, but the code traverses CPU
> > structures rather than task structures.
> > 
> > One other possibility is that this is safe due to the fact that we are
> > booting up, before the second CPU has come online.  Are you relying on
> > this?
> > 
> > For reference, here is the definition of rcu_read_lock_sched_held():
> > 
> > static inline int rcu_read_lock_sched_held(void)
> > {
> >         int lockdep_opinion = 0;
> > 
> >         if (debug_locks)
> >                 lockdep_opinion = lock_is_held(&rcu_sched_lock_map);
> >         return lockdep_opinion || preempt_count() != 0;
> > }
> > 
> > Help? 
> 
> We use synchronize_sched() and preempt_disable() for the sched domain
> stuff. The comment above for_each_domain():
> 
> /*
>  * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
>  * See detach_destroy_domains: synchronize_sched for details.
>  *
>  * The domain tree of any CPU may only be accessed from within
>  * preempt-disabled sections.
>  */
> #define for_each_domain(cpu, __sd) \
>         for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
> 
> explains this usage, also see detach_destroy_domains().
> 
> So one thing you can do is add (preempt_count() & ~PREEMPT_ACTIVE) to
> the rcu_read_lock_sched_held() function to catch all those cases that
> rely on preemption without having to add annotations to everything that
> disables preemption.

OK, but doesn't the "preempt_count() != 0" that is in the current version
of rcu_read_lock_sched_held() already cover this check?

In other words, I believe that I have located a usage of for_each_domain()
that violates the rule that it may only be called within preempt-disabled
sections.

							Thanx, Paul

Re: rcu_dereference() without protection in select_task_rq_fair()

[Peter Zijlstra]

On Sun, 2010-02-14 at 09:04 -0800, Paul E. McKenney wrote:

> OK, but doesn't the "preempt_count() != 0" that is in the current version
> of rcu_read_lock_sched_held() already cover this check?

Hmm, yes it should.

> In other words, I believe that I have located a usage of for_each_domain()
> that violates the rule that it may only be called within preempt-disabled
> sections.

>From the trace:

>  [<ffffffff81033ec4>] select_task_rq_fair+0xc1/0x686
>  [<ffffffff810353f4>] wake_up_new_task+0x1e/0x13e

Which reads like:

void wake_up_new_task(...)
{
	...

        int cpu __maybe_unused = get_cpu();

#ifdef CONFIG_SMP
        /*
         * Fork balancing, do it here and not earlier because:
         *  - cpus_allowed can change in the fork path
         *  - any previously selected cpu might disappear through hotplug
         *
         * We still have TASK_WAKING but PF_STARTING is gone now, meaning
         * ->cpus_allowed is stable, we have preemption disabled, meaning
         * cpu_online_mask is stable.
         */
        cpu = select_task_rq(p, SD_BALANCE_FORK, 0);
        set_task_cpu(p, cpu);
#endif

	...

	put_cpu()
}

I cannot see how we can get there without preemption disabled.

Re: rcu_dereference() without protection in select_task_rq_fair()

[Paul E. McKenney]

On Mon, Feb 15, 2010 at 10:12:06AM +0100, Peter Zijlstra wrote:
> On Sun, 2010-02-14 at 09:04 -0800, Paul E. McKenney wrote:
> 
> > OK, but doesn't the "preempt_count() != 0" that is in the current version
> > of rcu_read_lock_sched_held() already cover this check?
> 
> Hmm, yes it should.
> 
> > In other words, I believe that I have located a usage of for_each_domain()
> > that violates the rule that it may only be called within preempt-disabled
> > sections.
> 
> >From the trace:
> 
> >  [<ffffffff81033ec4>] select_task_rq_fair+0xc1/0x686
> >  [<ffffffff810353f4>] wake_up_new_task+0x1e/0x13e
> 
> Which reads like:
> 
> void wake_up_new_task(...)
> {
> 	...
> 
>         int cpu __maybe_unused = get_cpu();
> 
> #ifdef CONFIG_SMP
>         /*
>          * Fork balancing, do it here and not earlier because:
>          *  - cpus_allowed can change in the fork path
>          *  - any previously selected cpu might disappear through hotplug
>          *
>          * We still have TASK_WAKING but PF_STARTING is gone now, meaning
>          * ->cpus_allowed is stable, we have preemption disabled, meaning
>          * cpu_online_mask is stable.
>          */
>         cpu = select_task_rq(p, SD_BALANCE_FORK, 0);
>         set_task_cpu(p, cpu);
> #endif
> 
> 	...
> 
> 	put_cpu()
> }
> 
> I cannot see how we can get there without preemption disabled.

Interesting point.  I have seen this but once.  If it reproduces, I will
instrument the code path and see if I can track it down.

							Thanx, Paul