linux-toradex.git/kernel/rcutree.h, branch v3.0.16

rcu: Move RCU_BOOST #ifdefs to header file

2011-06-16T23:12:05+00:00

The commit "use softirq instead of kthreads except when RCU_BOOST=y"
just applied #ifdef in place.  This commit is a cleanup that moves
the newly #ifdef'ed code to the header file kernel/rcutree_plugin.h.

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

rcu: use softirq instead of kthreads except when RCU_BOOST=y

2011-06-16T06:07:21+00:00

This patch #ifdefs RCU kthreads out of the kernel unless RCU_BOOST=y,
thus eliminating context-switch overhead if RCU priority boosting has
not been configured.

Signed-off-by: Paul E. McKenney

rcu: Use softirq to address performance regression

2011-06-14T22:25:39+00:00

Commit a26ac2455ffcf3(rcu: move TREE_RCU from softirq to kthread)
introduced performance regression. In an AIM7 test, this commit degraded
performance by about 40%.

The commit runs rcu callbacks in a kthread instead of softirq. We observed
high rate of context switch which is caused by this. Out test system has
64 CPUs and HZ is 1000, so we saw more than 64k context switch per second
which is caused by RCU's per-CPU kthread.  A trace showed that most of
the time the RCU per-CPU kthread doesn't actually handle any callbacks,
but instead just does a very small amount of work handling grace periods.
This means that RCU's per-CPU kthreads are making the scheduler do quite
a bit of work in order to allow a very small amount of RCU-related
processing to be done.

Alex Shi's analysis determined that this slowdown is due to lock
contention within the scheduler.  Unfortunately, as Peter Zijlstra points
out, the scheduler's real-time semantics require global action, which
means that this contention is inherent in real-time scheduling.  (Yes,
perhaps someone will come up with a workaround -- otherwise, -rt is not
going to do well on large SMP systems -- but this patch will work around
this issue in the meantime.  And "the meantime" might well be forever.)

This patch therefore re-introduces softirq processing to RCU, but only
for core RCU work.  RCU callbacks are still executed in kthread context,
so that only a small amount of RCU work runs in softirq context in the
common case.  This should minimize ksoftirqd execution, allowing us to
skip boosting of ksoftirqd for CONFIG_RCU_BOOST=y kernels.

Signed-off-by: Shaohua Li 
Tested-by: "Alex,Shi" 
Signed-off-by: Paul E. McKenney

rcu: Remove waitqueue usage for cpu, node, and boost kthreads

2011-05-28T15:41:52+00:00

It is not necessary to use waitqueues for the RCU kthreads because
we always know exactly which thread is to be awakened.  In addition,
wake_up() only issues an actual wakeup when there is a thread waiting on
the queue, which was why there was an extra explicit wake_up_process()
to get the RCU kthreads started.

Eliminating the waitqueues (and wake_up()) in favor of wake_up_process()
eliminates the need for the initial wake_up_process() and also shrinks
the data structure size a bit.  The wakeup logic is placed in a new
rcu_wait() macro.

Signed-off-by: Peter Zijlstra 
Signed-off-by: Paul E. McKenney 
Signed-off-by: Ingo Molnar

rcu: Avoid acquiring rcu_node locks in timer functions

2011-05-28T15:41:49+00:00

This commit switches manipulations of the rcu_node ->wakemask field
to atomic operations, which allows rcu_cpu_kthread_timer() to avoid
acquiring the rcu_node lock.  This should avoid the following lockdep
splat reported by Valdis Kletnieks:

[   12.872150] usb 1-4: new high speed USB device number 3 using ehci_hcd
[   12.986667] usb 1-4: New USB device found, idVendor=413c, idProduct=2513
[   12.986679] usb 1-4: New USB device strings: Mfr=0, Product=0, SerialNumber=0
[   12.987691] hub 1-4:1.0: USB hub found
[   12.987877] hub 1-4:1.0: 3 ports detected
[   12.996372] input: PS/2 Generic Mouse as /devices/platform/i8042/serio1/input/input10
[   13.071471] udevadm used greatest stack depth: 3984 bytes left
[   13.172129]
[   13.172130] =======================================================
[   13.172425] [ INFO: possible circular locking dependency detected ]
[   13.172650] 2.6.39-rc6-mmotm0506 #1
[   13.172773] -------------------------------------------------------
[   13.172997] blkid/267 is trying to acquire lock:
[   13.173009]  (&p->pi_lock){-.-.-.}, at: [] try_to_wake_up+0x29/0x1aa
[   13.173009]
[   13.173009] but task is already holding lock:
[   13.173009]  (rcu_node_level_0){..-...}, at: [] rcu_cpu_kthread_timer+0x27/0x58
[   13.173009]
[   13.173009] which lock already depends on the new lock.
[   13.173009]
[   13.173009]
[   13.173009] the existing dependency chain (in reverse order) is:
[   13.173009]
[   13.173009] -> #2 (rcu_node_level_0){..-...}:
[   13.173009]        [] check_prevs_add+0x8b/0x104
[   13.173009]        [] validate_chain+0x36f/0x3ab
[   13.173009]        [] __lock_acquire+0x369/0x3e2
[   13.173009]        [] lock_acquire+0xfc/0x14c
[   13.173009]        [] _raw_spin_lock+0x36/0x45
[   13.173009]        [] rcu_read_unlock_special+0x8c/0x1d5
[   13.173009]        [] __rcu_read_unlock+0x4f/0xd7
[   13.173009]        [] rcu_read_unlock+0x21/0x23
[   13.173009]        [] cpuacct_charge+0x6c/0x75
[   13.173009]        [] update_curr+0x101/0x12e
[   13.173009]        [] check_preempt_wakeup+0xf7/0x23b
[   13.173009]        [] check_preempt_curr+0x2b/0x68
[   13.173009]        [] ttwu_do_wakeup+0x76/0x128
[   13.173009]        [] ttwu_do_activate.constprop.63+0x57/0x5c
[   13.173009]        [] scheduler_ipi+0x48/0x5d
[   13.173009]        [] smp_reschedule_interrupt+0x16/0x18
[   13.173009]        [] reschedule_interrupt+0x13/0x20
[   13.173009]        [] rcu_read_unlock+0x21/0x23
[   13.173009]        [] find_get_page+0xa9/0xb9
[   13.173009]        [] filemap_fault+0x6a/0x34d
[   13.173009]        [] __do_fault+0x54/0x3e6
[   13.173009]        [] handle_pte_fault+0x12c/0x1ed
[   13.173009]        [] handle_mm_fault+0x1cd/0x1e0
[   13.173009]        [] do_page_fault+0x42d/0x5de
[   13.173009]        [] page_fault+0x1f/0x30
[   13.173009]
[   13.173009] -> #1 (&rq->lock){-.-.-.}:
[   13.173009]        [] check_prevs_add+0x8b/0x104
[   13.173009]        [] validate_chain+0x36f/0x3ab
[   13.173009]        [] __lock_acquire+0x369/0x3e2
[   13.173009]        [] lock_acquire+0xfc/0x14c
[   13.173009]        [] _raw_spin_lock+0x36/0x45
[   13.173009]        [] __task_rq_lock+0x8b/0xd3
[   13.173009]        [] wake_up_new_task+0x41/0x108
[   13.173009]        [] do_fork+0x265/0x33f
[   13.173009]        [] kernel_thread+0x6b/0x6d
[   13.173009]        [] rest_init+0x21/0xd2
[   13.173009]        [] start_kernel+0x3bb/0x3c6
[   13.173009]        [] x86_64_start_reservations+0xaf/0xb3
[   13.173009]        [] x86_64_start_kernel+0xf0/0xf7
[   13.173009]
[   13.173009] -> #0 (&p->pi_lock){-.-.-.}:
[   13.173009]        [] check_prev_add+0x68/0x20e
[   13.173009]        [] check_prevs_add+0x8b/0x104
[   13.173009]        [] validate_chain+0x36f/0x3ab
[   13.173009]        [] __lock_acquire+0x369/0x3e2
[   13.173009]        [] lock_acquire+0xfc/0x14c
[   13.173009]        [] _raw_spin_lock_irqsave+0x44/0x57
[   13.173009]        [] try_to_wake_up+0x29/0x1aa
[   13.173009]        [] wake_up_process+0x10/0x12
[   13.173009]        [] rcu_cpu_kthread_timer+0x44/0x58
[   13.173009]        [] call_timer_fn+0xac/0x1e9
[   13.173009]        [] run_timer_softirq+0x1aa/0x1f2
[   13.173009]        [] __do_softirq+0x109/0x26a
[   13.173009]        [] call_softirq+0x1c/0x30
[   13.173009]        [] do_softirq+0x44/0xf1
[   13.173009]        [] irq_exit+0x58/0xc8
[   13.173009]        [] smp_apic_timer_interrupt+0x79/0x87
[   13.173009]        [] apic_timer_interrupt+0x13/0x20
[   13.173009]        [] get_page_from_freelist+0x2aa/0x310
[   13.173009]        [] __alloc_pages_nodemask+0x178/0x243
[   13.173009]        [] pte_alloc_one+0x1e/0x3a
[   13.173009]        [] __pte_alloc+0x22/0x14b
[   13.173009]        [] handle_mm_fault+0x17e/0x1e0
[   13.173009]        [] do_page_fault+0x42d/0x5de
[   13.173009]        [] page_fault+0x1f/0x30
[   13.173009]
[   13.173009] other info that might help us debug this:
[   13.173009]
[   13.173009] Chain exists of:
[   13.173009]   &p->pi_lock --> &rq->lock --> rcu_node_level_0
[   13.173009]
[   13.173009]  Possible unsafe locking scenario:
[   13.173009]
[   13.173009]        CPU0                    CPU1
[   13.173009]        ----                    ----
[   13.173009]   lock(rcu_node_level_0);
[   13.173009]                                lock(&rq->lock);
[   13.173009]                                lock(rcu_node_level_0);
[   13.173009]   lock(&p->pi_lock);
[   13.173009]
[   13.173009]  *** DEADLOCK ***
[   13.173009]
[   13.173009] 3 locks held by blkid/267:
[   13.173009]  #0:  (&mm->mmap_sem){++++++}, at: [] do_page_fault+0x1f3/0x5de
[   13.173009]  #1:  (&yield_timer){+.-...}, at: [] call_timer_fn+0x0/0x1e9
[   13.173009]  #2:  (rcu_node_level_0){..-...}, at: [] rcu_cpu_kthread_timer+0x27/0x58
[   13.173009]
[   13.173009] stack backtrace:
[   13.173009] Pid: 267, comm: blkid Not tainted 2.6.39-rc6-mmotm0506 #1
[   13.173009] Call Trace:
[   13.173009]    [] print_circular_bug+0xc8/0xd9
[   13.173009]  [] check_prev_add+0x68/0x20e
[   13.173009]  [] ? save_stack_trace+0x28/0x46
[   13.173009]  [] check_prevs_add+0x8b/0x104
[   13.173009]  [] validate_chain+0x36f/0x3ab
[   13.173009]  [] __lock_acquire+0x369/0x3e2
[   13.173009]  [] ? try_to_wake_up+0x29/0x1aa
[   13.173009]  [] lock_acquire+0xfc/0x14c
[   13.173009]  [] ? try_to_wake_up+0x29/0x1aa
[   13.173009]  [] ? rcu_check_quiescent_state+0x82/0x82
[   13.173009]  [] _raw_spin_lock_irqsave+0x44/0x57
[   13.173009]  [] ? try_to_wake_up+0x29/0x1aa
[   13.173009]  [] try_to_wake_up+0x29/0x1aa
[   13.173009]  [] ? rcu_check_quiescent_state+0x82/0x82
[   13.173009]  [] wake_up_process+0x10/0x12
[   13.173009]  [] rcu_cpu_kthread_timer+0x44/0x58
[   13.173009]  [] ? rcu_check_quiescent_state+0x82/0x82
[   13.173009]  [] call_timer_fn+0xac/0x1e9
[   13.173009]  [] ? del_timer+0x75/0x75
[   13.173009]  [] ? rcu_check_quiescent_state+0x82/0x82
[   13.173009]  [] run_timer_softirq+0x1aa/0x1f2
[   13.173009]  [] __do_softirq+0x109/0x26a
[   13.173009]  [] ? tick_dev_program_event+0x37/0xf6
[   13.173009]  [] ? time_hardirqs_off+0x1b/0x2f
[   13.173009]  [] call_softirq+0x1c/0x30
[   13.173009]  [] do_softirq+0x44/0xf1
[   13.173009]  [] irq_exit+0x58/0xc8
[   13.173009]  [] smp_apic_timer_interrupt+0x79/0x87
[   13.173009]  [] apic_timer_interrupt+0x13/0x20
[   13.173009]    [] ? get_page_from_freelist+0x114/0x310
[   13.173009]  [] ? get_page_from_freelist+0x2aa/0x310
[   13.173009]  [] ? clear_page_c+0x7/0x10
[   13.173009]  [] ? prep_new_page+0x14c/0x1cd
[   13.173009]  [] get_page_from_freelist+0x2aa/0x310
[   13.173009]  [] __alloc_pages_nodemask+0x178/0x243
[   13.173009]  [] ? __pmd_alloc+0x87/0x99
[   13.173009]  [] pte_alloc_one+0x1e/0x3a
[   13.173009]  [] ? __pmd_alloc+0x87/0x99
[   13.173009]  [] __pte_alloc+0x22/0x14b
[   13.173009]  [] handle_mm_fault+0x17e/0x1e0
[   13.173009]  [] do_page_fault+0x42d/0x5de
[   13.173009]  [] ? sys_brk+0x32/0x10c
[   13.173009]  [] ? time_hardirqs_off+0x1b/0x2f
[   13.173009]  [] ? trace_hardirqs_off_caller+0x3f/0x9c
[   13.173009]  [] ? trace_hardirqs_off_thunk+0x3a/0x3c
[   13.173009]  [] page_fault+0x1f/0x30
[   14.010075] usb 5-1: new full speed USB device number 2 using uhci_hcd

Reported-by: Valdis Kletnieks 
Signed-off-by: Paul E. McKenney 
Signed-off-by: Paul E. McKenney 
Signed-off-by: Ingo Molnar

rcu: Decrease memory-barrier usage based on semi-formal proof

2011-05-26T16:42:23+00:00

(Note: this was reverted, and is now being re-applied in pieces, with
this being the fifth and final piece.  See below for the reason that
it is now felt to be safe to re-apply this.)

Commit d09b62d fixed grace-period synchronization, but left some smp_mb()
invocations in rcu_process_callbacks() that are no longer needed, but
sheer paranoia prevented them from being removed.  This commit removes
them and provides a proof of correctness in their absence.  It also adds
a memory barrier to rcu_report_qs_rsp() immediately before the update to
rsp->completed in order to handle the theoretical possibility that the
compiler or CPU might move massive quantities of code into a lock-based
critical section.  This also proves that the sheer paranoia was not
entirely unjustified, at least from a theoretical point of view.

In addition, the old dyntick-idle synchronization depended on the fact
that grace periods were many milliseconds in duration, so that it could
be assumed that no dyntick-idle CPU could reorder a memory reference
across an entire grace period.  Unfortunately for this design, the
addition of expedited grace periods breaks this assumption, which has
the unfortunate side-effect of requiring atomic operations in the
functions that track dyntick-idle state for RCU.  (There is some hope
that the algorithms used in user-level RCU might be applied here, but
some work is required to handle the NMIs that user-space applications
can happily ignore.  For the short term, better safe than sorry.)

This proof assumes that neither compiler nor CPU will allow a lock
acquisition and release to be reordered, as doing so can result in
deadlock.  The proof is as follows:

1.	A given CPU declares a quiescent state under the protection of
	its leaf rcu_node's lock.

2.	If there is more than one level of rcu_node hierarchy, the
	last CPU to declare a quiescent state will also acquire the
	->lock of the next rcu_node up in the hierarchy,  but only
	after releasing the lower level's lock.  The acquisition of this
	lock clearly cannot occur prior to the acquisition of the leaf
	node's lock.

3.	Step 2 repeats until we reach the root rcu_node structure.
	Please note again that only one lock is held at a time through
	this process.  The acquisition of the root rcu_node's ->lock
	must occur after the release of that of the leaf rcu_node.

4.	At this point, we set the ->completed field in the rcu_state
	structure in rcu_report_qs_rsp().  However, if the rcu_node
	hierarchy contains only one rcu_node, then in theory the code
	preceding the quiescent state could leak into the critical
	section.  We therefore precede the update of ->completed with a
	memory barrier.  All CPUs will therefore agree that any updates
	preceding any report of a quiescent state will have happened
	before the update of ->completed.

5.	Regardless of whether a new grace period is needed, rcu_start_gp()
	will propagate the new value of ->completed to all of the leaf
	rcu_node structures, under the protection of each rcu_node's ->lock.
	If a new grace period is needed immediately, this propagation
	will occur in the same critical section that ->completed was
	set in, but courtesy of the memory barrier in #4 above, is still
	seen to follow any pre-quiescent-state activity.

6.	When a given CPU invokes __rcu_process_gp_end(), it becomes
	aware of the end of the old grace period and therefore makes
	any RCU callbacks that were waiting on that grace period eligible
	for invocation.

	If this CPU is the same one that detected the end of the grace
	period, and if there is but a single rcu_node in the hierarchy,
	we will still be in the single critical section.  In this case,
	the memory barrier in step #4 guarantees that all callbacks will
	be seen to execute after each CPU's quiescent state.

	On the other hand, if this is a different CPU, it will acquire
	the leaf rcu_node's ->lock, and will again be serialized after
	each CPU's quiescent state for the old grace period.

On the strength of this proof, this commit therefore removes the memory
barriers from rcu_process_callbacks() and adds one to rcu_report_qs_rsp().
The effect is to reduce the number of memory barriers by one and to
reduce the frequency of execution from about once per scheduling tick
per CPU to once per grace period.

This was reverted do to hangs found during testing by Yinghai Lu and
Ingo Molnar.  Frederic Weisbecker supplied Yinghai with tracing that
located the underlying problem, and Frederic also provided the fix.

The underlying problem was that the HARDIRQ_ENTER() macro from
lib/locking-selftest.c invoked irq_enter(), which in turn invokes
rcu_irq_enter(), but HARDIRQ_EXIT() invoked __irq_exit(), which
does not invoke rcu_irq_exit().  This situation resulted in calls
to rcu_irq_enter() that were not balanced by the required calls to
rcu_irq_exit().  Therefore, after these locking selftests completed,
RCU's dyntick-idle nesting count was a large number (for example,
72), which caused RCU to to conclude that the affected CPU was not in
dyntick-idle mode when in fact it was.

RCU would therefore incorrectly wait for this dyntick-idle CPU, resulting
in hangs.

In contrast, with Frederic's patch, which replaces the irq_enter()
in HARDIRQ_ENTER() with an __irq_enter(), these tests don't ever call
either rcu_irq_enter() or rcu_irq_exit(), which works because the CPU
running the test is already marked as not being in dyntick-idle mode.
This means that the rcu_irq_enter() and rcu_irq_exit() calls and RCU
then has no problem working out which CPUs are in dyntick-idle mode and
which are not.

The reason that the imbalance was not noticed before the barrier patch
was applied is that the old implementation of rcu_enter_nohz() ignored
the nesting depth.  This could still result in delays, but much shorter
ones.  Whenever there was a delay, RCU would IPI the CPU with the
unbalanced nesting level, which would eventually result in rcu_enter_nohz()
being called, which in turn would force RCU to see that the CPU was in
dyntick-idle mode.

The reason that very few people noticed the problem is that the mismatched
irq_enter() vs. __irq_exit() occured only when the kernel was built with
CONFIG_DEBUG_LOCKING_API_SELFTESTS.

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

Revert "rcu: Decrease memory-barrier usage based on semi-formal proof"

2011-05-19T21:25:29+00:00

This reverts commit e59fb3120becfb36b22ddb8bd27d065d3cdca499.

This reversion was due to (extreme) boot-time slowdowns on SPARC seen by
Yinghai Lu and on x86 by Ingo
.
This is a non-trivial reversion due to intervening commits.

Conflicts:

	Documentation/RCU/trace.txt
	kernel/rcutree.c

Signed-off-by: Ingo Molnar

rcu: permit rcu_read_unlock() to be called while holding runqueue locks

2011-05-08T05:50:45+00:00

Avoid calling into the scheduler while holding core RCU locks.  This
allows rcu_read_unlock() to be called while holding the runqueue locks,
but only as long as there was no chance of the RCU read-side critical
section having been preempted.  (Otherwise, if RCU priority boosting
is enabled, rcu_read_unlock() might call into the scheduler in order to
unboost itself, which might allows self-deadlock on the runqueue locks
within the scheduler.)

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

rcu: fix spelling

2011-05-06T06:16:59+00:00

The "preemptible" spelling is preferable.  May as well fix it.

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

rcu: add grace-period age and more kthread state to tracing

2011-05-06T06:16:56+00:00

This commit adds the age in jiffies of the current grace period along
with the duration in jiffies of the longest grace period since boot
to the rcu/rcugp debugfs file.  It also adds an additional "O" state
to kthread tracing to differentiate between the kthread waiting due to
having nothing to do on the one hand and waiting due to being on the
wrong CPU on the other hand.

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