linux-toradex.git/Documentation/RCU/trace.txt, branch v3.17-rc6

Merge branches 'doc.2013.12.03a', 'fixes.2013.12.12a', 'rcutorture.2013.12.03a' and 'sparse.2013.12.12a' into HEAD

2013-12-12T20:35:38+00:00

doc.2013.12.03a: Topic branch for documentation changes.
fixes.2013.12.12a: Topic branch for miscellaneous fixes.
rcutorture.2013.12.03a: Topic branch for new rcutorture/KVM scripting.
sparse.2013.12.12a: Topic branch for sparse-RCU changes.

rcu: Break call_rcu() deadlock involving scheduler and perf

2013-12-03T18:10:18+00:00

Dave Jones got the following lockdep splat:

>  ======================================================
>  [ INFO: possible circular locking dependency detected ]
>  3.12.0-rc3+ #92 Not tainted
>  -------------------------------------------------------
>  trinity-child2/15191 is trying to acquire lock:
>   (&rdp->nocb_wq){......}, at: [] __wake_up+0x23/0x50
>
> but task is already holding lock:
>   (&ctx->lock){-.-...}, at: [] perf_event_exit_task+0x109/0x230
>
> which lock already depends on the new lock.
>
>
> the existing dependency chain (in reverse order) is:
>
> -> #3 (&ctx->lock){-.-...}:
>         [] lock_acquire+0x93/0x200
>         [] _raw_spin_lock+0x40/0x80
>         [] __perf_event_task_sched_out+0x2df/0x5e0
>         [] perf_event_task_sched_out+0x93/0xa0
>         [] __schedule+0x1d2/0xa20
>         [] preempt_schedule_irq+0x50/0xb0
>         [] retint_kernel+0x26/0x30
>         [] tty_flip_buffer_push+0x34/0x50
>         [] pty_write+0x54/0x60
>         [] n_tty_write+0x32d/0x4e0
>         [] tty_write+0x158/0x2d0
>         [] vfs_write+0xc0/0x1f0
>         [] SyS_write+0x4c/0xa0
>         [] tracesys+0xdd/0xe2
>
> -> #2 (&rq->lock){-.-.-.}:
>         [] lock_acquire+0x93/0x200
>         [] _raw_spin_lock+0x40/0x80
>         [] wake_up_new_task+0xc2/0x2e0
>         [] do_fork+0x126/0x460
>         [] kernel_thread+0x26/0x30
>         [] rest_init+0x23/0x140
>         [] start_kernel+0x3f6/0x403
>         [] x86_64_start_reservations+0x2a/0x2c
>         [] x86_64_start_kernel+0xf1/0xf4
>
> -> #1 (&p->pi_lock){-.-.-.}:
>         [] lock_acquire+0x93/0x200
>         [] _raw_spin_lock_irqsave+0x4b/0x90
>         [] try_to_wake_up+0x31/0x350
>         [] default_wake_function+0x12/0x20
>         [] autoremove_wake_function+0x18/0x40
>         [] __wake_up_common+0x58/0x90
>         [] __wake_up+0x39/0x50
>         [] __call_rcu_nocb_enqueue+0xa8/0xc0
>         [] __call_rcu+0x140/0x820
>         [] call_rcu+0x1d/0x20
>         [] cpu_attach_domain+0x287/0x360
>         [] build_sched_domains+0xe5e/0x10a0
>         [] sched_init_smp+0x3b7/0x47a
>         [] kernel_init_freeable+0xf6/0x202
>         [] kernel_init+0xe/0x190
>         [] ret_from_fork+0x7c/0xb0
>
> -> #0 (&rdp->nocb_wq){......}:
>         [] __lock_acquire+0x191a/0x1be0
>         [] lock_acquire+0x93/0x200
>         [] _raw_spin_lock_irqsave+0x4b/0x90
>         [] __wake_up+0x23/0x50
>         [] __call_rcu_nocb_enqueue+0xa8/0xc0
>         [] __call_rcu+0x140/0x820
>         [] kfree_call_rcu+0x20/0x30
>         [] put_ctx+0x4f/0x70
>         [] perf_event_exit_task+0x12e/0x230
>         [] do_exit+0x30d/0xcc0
>         [] do_group_exit+0x4c/0xc0
>         [] SyS_exit_group+0x14/0x20
>         [] tracesys+0xdd/0xe2
>
> other info that might help us debug this:
>
> Chain exists of:
>   &rdp->nocb_wq --> &rq->lock --> &ctx->lock
>
>   Possible unsafe locking scenario:
>
>         CPU0                    CPU1
>         ----                    ----
>    lock(&ctx->lock);
>                                 lock(&rq->lock);
>                                 lock(&ctx->lock);
>    lock(&rdp->nocb_wq);
>
>  *** DEADLOCK ***
>
> 1 lock held by trinity-child2/15191:
>  #0:  (&ctx->lock){-.-...}, at: [] perf_event_exit_task+0x109/0x230
>
> stack backtrace:
> CPU: 2 PID: 15191 Comm: trinity-child2 Not tainted 3.12.0-rc3+ #92
>  ffffffff82565b70 ffff880070c2dbf8 ffffffff8172a363 ffffffff824edf40
>  ffff880070c2dc38 ffffffff81726741 ffff880070c2dc90 ffff88022383b1c0
>  ffff88022383aac0 0000000000000000 ffff88022383b188 ffff88022383b1c0
> Call Trace:
>  [] dump_stack+0x4e/0x82
>  [] print_circular_bug+0x200/0x20f
>  [] __lock_acquire+0x191a/0x1be0
>  [] ? get_lock_stats+0x19/0x60
>  [] ? native_sched_clock+0x24/0x80
>  [] lock_acquire+0x93/0x200
>  [] ? __wake_up+0x23/0x50
>  [] _raw_spin_lock_irqsave+0x4b/0x90
>  [] ? __wake_up+0x23/0x50
>  [] __wake_up+0x23/0x50
>  [] __call_rcu_nocb_enqueue+0xa8/0xc0
>  [] __call_rcu+0x140/0x820
>  [] ? local_clock+0x3f/0x50
>  [] kfree_call_rcu+0x20/0x30
>  [] put_ctx+0x4f/0x70
>  [] perf_event_exit_task+0x12e/0x230
>  [] do_exit+0x30d/0xcc0
>  [] ? trace_hardirqs_on_caller+0x115/0x1e0
>  [] ? trace_hardirqs_on+0xd/0x10
>  [] do_group_exit+0x4c/0xc0
>  [] SyS_exit_group+0x14/0x20
>  [] tracesys+0xdd/0xe2

The underlying problem is that perf is invoking call_rcu() with the
scheduler locks held, but in NOCB mode, call_rcu() will with high
probability invoke the scheduler -- which just might want to use its
locks.  The reason that call_rcu() needs to invoke the scheduler is
to wake up the corresponding rcuo callback-offload kthread, which
does the job of starting up a grace period and invoking the callbacks
afterwards.

One solution (championed on a related problem by Lai Jiangshan) is to
simply defer the wakeup to some point where scheduler locks are no longer
held.  Since we don't want to unnecessarily incur the cost of such
deferral, the task before us is threefold:

1.	Determine when it is likely that a relevant scheduler lock is held.

2.	Defer the wakeup in such cases.

3.	Ensure that all deferred wakeups eventually happen, preferably
	sooner rather than later.

We use irqs_disabled_flags() as a proxy for relevant scheduler locks
being held.  This works because the relevant locks are always acquired
with interrupts disabled.  We may defer more often than needed, but that
is at least safe.

The wakeup deferral is tracked via a new field in the per-CPU and
per-RCU-flavor rcu_data structure, namely ->nocb_defer_wakeup.

This flag is checked by the RCU core processing.  The __rcu_pending()
function now checks this flag, which causes rcu_check_callbacks()
to initiate RCU core processing at each scheduling-clock interrupt
where this flag is set.  Of course this is not sufficient because
scheduling-clock interrupts are often turned off (the things we used to
be able to count on!).  So the flags are also checked on entry to any
state that RCU considers to be idle, which includes both NO_HZ_IDLE idle
state and NO_HZ_FULL user-mode-execution state.

This approach should allow call_rcu() to be invoked regardless of what
locks you might be holding, the key word being "should".

Reported-by: Dave Jones 
Signed-off-by: Paul E. McKenney 
Cc: Peter Zijlstra

rcu: Fix typo in Documentation/RCU/trace.txt

2013-12-03T18:08:56+00:00

Signed-off-by: Paul E. McKenney

rcu: Remove TINY_PREEMPT_RCU tracing documentation

2013-06-10T20:45:52+00:00

Because TINY_PREEMPT_RCU is no more, this commit removes its tracing
formats from the documentation.

Signed-off-by: Paul E. McKenney 
Reviewed-by: Josh Triplett

rcu: Add documentation for the new rcuexp debugfs trace file

2012-11-16T17:55:31+00:00

This commit adds the documentation of the rcuexp debugfs trace file
that records statistics for expedited grace periods.

Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney

rcu: Update documentation for TREE_RCU debugfs tracing

2012-11-16T17:54:02+00:00

This commit updates the tracing documentation to reflect the new
format that has per-RCU-flavor directories.

Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney

rcu: Adjust debugfs tracing for kthread-based quiescent-state forcing

2012-09-23T14:41:54+00:00

Moving quiescent-state forcing into a kthread dispenses with the need
for the ->n_rp_need_fqs field, so this commit removes it.

Signed-off-by: Paul E. McKenney 
Reviewed-by: Josh Triplett

rcu: Rework detection of use of RCU by offline CPUs

2012-02-21T17:06:07+00:00

Because newly offlined CPUs continue executing after completing the
CPU_DYING notifiers, they legitimately enter the scheduler and use
RCU while appearing to be offline.  This calls for a more sophisticated
approach as follows:

1.	RCU marks the CPU online during the CPU_UP_PREPARE phase.

2.	RCU marks the CPU offline during the CPU_DEAD phase.

3.	Diagnostics regarding use of read-side RCU by offline CPUs use
	RCU's accounting rather than the cpu_online_map.  (Note that
	__call_rcu() still uses cpu_online_map to detect illegal
	invocations within CPU_DYING notifiers.)

4.	Offline CPUs are prevented from hanging the system by
	force_quiescent_state(), which pays attention to cpu_online_map.
	Some additional work (in a later commit) will be needed to
	guarantee that force_quiescent_state() waits a full jiffy before
	assuming that a CPU is offline, for example, when called from
	idle entry.  (This commit also makes the one-jiffy wait
	explicit, since the old-style implicit wait can now be defeated
	by RCU_FAST_NO_HZ and by rcutorture.)

This approach avoids the false positives encountered when attempting to
use more exact classification of CPU online/offline state.

Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney

rcu: Track idleness independent of idle tasks

2011-12-11T18:31:24+00:00

Earlier versions of RCU used the scheduling-clock tick to detect idleness
by checking for the idle task, but handled idleness differently for
CONFIG_NO_HZ=y.  But there are now a number of uses of RCU read-side
critical sections in the idle task, for example, for tracing.  A more
fine-grained detection of idleness is therefore required.

This commit presses the old dyntick-idle code into full-time service,
so that rcu_idle_enter(), previously known as rcu_enter_nohz(), is
always invoked at the beginning of an idle loop iteration.  Similarly,
rcu_idle_exit(), previously known as rcu_exit_nohz(), is always invoked
at the end of an idle-loop iteration.  This allows the idle task to
use RCU everywhere except between consecutive rcu_idle_enter() and
rcu_idle_exit() calls, in turn allowing architecture maintainers to
specify exactly where in the idle loop that RCU may be used.

Because some of the userspace upcall uses can result in what looks
to RCU like half of an interrupt, it is not possible to expect that
the irq_enter() and irq_exit() hooks will give exact counts.  This
patch therefore expands the ->dynticks_nesting counter to 64 bits
and uses two separate bitfields to count process/idle transitions
and interrupt entry/exit transitions.  It is presumed that userspace
upcalls do not happen in the idle loop or from usermode execution
(though usermode might do a system call that results in an upcall).
The counter is hard-reset on each process/idle transition, which
avoids the interrupt entry/exit error from accumulating.  Overflow
is avoided by the 64-bitness of the ->dyntick_nesting counter.

This commit also adds warnings if a non-idle task asks RCU to enter
idle state (and these checks will need some adjustment before applying
Frederic's OS-jitter patches (http://lkml.org/lkml/2011/10/7/246).
In addition, validation of ->dynticks and ->dynticks_nesting is added.

Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney 
Reviewed-by: Josh Triplett

rcu: Simplify quiescent-state accounting

2011-09-29T04:38:22+00:00

There is often a delay between the time that a CPU passes through a
quiescent state and the time that this quiescent state is reported to the
RCU core.  It is quite possible that the grace period ended before the
quiescent state could be reported, for example, some other CPU might have
deduced that this CPU passed through dyntick-idle mode.  It is critically
important that quiescent state be counted only against the grace period
that was in effect at the time that the quiescent state was detected.

Previously, this was handled by recording the number of the last grace
period to complete when passing through a quiescent state.  The RCU
core then checks this number against the current value, and rejects
the quiescent state if there is a mismatch.  However, one additional
possibility must be accounted for, namely that the quiescent state was
recorded after the prior grace period completed but before the current
grace period started.  In this case, the RCU core must reject the
quiescent state, but the recorded number will match.  This is handled
when the CPU becomes aware of a new grace period -- at that point,
it invalidates any prior quiescent state.

This works, but is a bit indirect.  The new approach records the current
grace period, and the RCU core checks to see (1) that this is still the
current grace period and (2) that this grace period has not yet ended.
This approach simplifies reasoning about correctness, and this commit
changes over to this new approach.

Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney