rcu: Fix day-one dyntick-idle stall-warning bug

Each grace period is supposed to have at least one callback waiting
for that grace period to complete.  However, if CONFIG_NO_HZ=n, an
extra callback-free grace period is no big problem -- it will chew up
a tiny bit of CPU time, but it will complete normally.  In contrast,
CONFIG_NO_HZ=y kernels have the potential for all the CPUs to go to
sleep indefinitely, in turn indefinitely delaying completion of the
callback-free grace period.  Given that nothing is waiting on this grace
period, this is also not a problem.

That is, unless RCU CPU stall warnings are also enabled, as they are
in recent kernels.  In this case, if a CPU wakes up after at least one
minute of inactivity, an RCU CPU stall warning will result.  The reason
that no one noticed until quite recently is that most systems have enough
OS noise that they will never remain absolutely idle for a full minute.
But there are some embedded systems with cut-down userspace configurations
that consistently get into this situation.

All this begs the question of exactly how a callback-free grace period
gets started in the first place.  This can happen due to the fact that
CPUs do not necessarily agree on which grace period is in progress.
If a CPU still believes that the grace period that just completed is
still ongoing, it will believe that it has callbacks that need to wait for
another grace period, never mind the fact that the grace period that they
were waiting for just completed.  This CPU can therefore erroneously
decide to start a new grace period.  Note that this can happen in
TREE_RCU and TREE_PREEMPT_RCU even on a single-CPU system:  Deadlock
considerations mean that the CPU that detected the end of the grace
period is not necessarily officially informed of this fact for some time.

Once this CPU notices that the earlier grace period completed, it will
invoke its callbacks.  It then won't have any callbacks left.  If no
other CPU has any callbacks, we now have a callback-free grace period.

This commit therefore makes CPUs check more carefully before starting a
new grace period.  This new check relies on an array of tail pointers
into each CPU's list of callbacks.  If the CPU is up to date on which
grace periods have completed, it checks to see if any callbacks follow
the RCU_DONE_TAIL segment, otherwise it checks to see if any callbacks
follow the RCU_WAIT_TAIL segment.  The reason that this works is that
the RCU_WAIT_TAIL segment will be promoted to the RCU_DONE_TAIL segment
as soon as the CPU is officially notified that the old grace period
has ended.

This change is to cpu_needs_another_gp(), which is called in a number
of places.  The only one that really matters is in rcu_start_gp(), where
the root rcu_node structure's ->lock is held, which prevents any
other CPU from starting or completing a grace period, so that the
comparison that determines whether the CPU is missing the completion
of a grace period is stable.

Change-Id: Ic77e2bbe865059aa6f363db284473e9adcf8797e
Reported-by: Becky Bruce <bgillbruce@gmail.com>
Reported-by: Subodh Nijsure <snijsure@grid-net.com>
Reported-by: Paul Walmsley <paul@pwsan.com>
Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Tested-by: Paul Walmsley <paul@pwsan.com>  # OMAP3730, OMAP4430
Cc: stable@vger.kernel.org
Signed-off-by: Jin Hong <jinh@codeaurora.org>
sched: fix rq->lock recursion

Enabling SCHED_HRTICK currently results in rq->lock recursion and a hard
hang at bootup.  Essentially try_to_wakeup() grabs rq->lock and tries
arming a hrtimer via hrtimer_restart(), which deep down tries waking up
ksoftirqd, which leads to a recursive call to try_to_wakeup() and thus
attempt to take rq->lock recursively!!

This is fixed by having scheduler queue hrtimer via
__hrtimer_start_range_ns() which avoids waking up ksoftirqd.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Change-Id: I11a13be1d9db3a749614ccf3d4f5fb7bf6f18fa1
net/ipv6/addrconf: IPv6 tethering enhancement

Added new procfs flag to toggle the automatic addition of prefix
routes on a per device basis. The new flag is accept_ra_prefix_route.
Defaults to 1 as to not break existing behavior.

Change-Id: If25493890c7531c27f5b2c4855afebbbbf5d072a
CRs-Fixed: 435320
Acked-by: Harout S. Hedeshian <harouth@qti.qualcomm.com>
Signed-off-by: Tianyi Gou <tgou@codeaurora.org>

Conflicts:
	net/ipv6/addrconf.c
sched: Reset rq->next_interval before going idle

next_balance, the point in jiffy time scale when a cpu will next load
balance, could have been calculated when the cpu was busy. A busy cpu
will apply its sched domain's busy_factor (usually > 1) in computing
next_balance for that sched domain, which causes the (busy) cpu to load
balance less frequently in its sched domains. However when the same cpu
is going idle, its next_balance needs to be reset without consideration
of busy_factor. Failure to do so would not trigger nohz idle balancer on
that cpu for unnecessarily long time (introducing additional scheduling
latencies for tasks). Fix bug in scheduler which aims to reset
next_balance before a cpu goes idle (as per existing comment) but is
clearly not doing so.

Change-Id: I7e027a51686528c4092d770c7d33c874d38f5df4
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>

Conflicts:
	kernel/sched/fair.c
hrtimer: Don't reinitialize a cpu_base's lock on CPU_UP

The current code makes the assumption that a cpu_base lock cannot
be held if a CPU is offline, which is tragically wrong.

If a hrtimer is not queued, then it will not be migrated by
migrate_hrtimers() when a CPU is offlined. Therefore, the
hrtimer's cpu_base may still point to a CPU which has
subsequently gone offline if the timer wasn't enqueued at the
time the CPU went down.

Normally this wouldn't be a problem, but a cpu_base's lock is
blindly reinitialized each time a CPU is brought up. If a CPU is
brought online during the period that another thread is
performing a hrtimer operation on a stale hrtimer, then the lock
will be reinitialized under its feet, and a SPIN_BUG() like the
following will be observed:

 [  448.212369] BUG: spinlock already unlocked on CPU#3,
 swapper/3/0
[  448.217368]  lock: 0xc47b1a40, .magic: dead4ead, .owner:
swapper/3/0, .owner_cpu: -1
[  448.217398] [<c0014398>] (unwind_backtrace+0x0/0x120) from
[<c0269ab0>] (do_raw_spin_unlock+0x44/0xdc)
[  448.217419] [<c0269ab0>] (do_raw_spin_unlock+0x44/0xdc) from
[<c071bbb0>] (_raw_spin_unlock_irqrestore+0xc/0x38)
[  448.217438] [<c071bbb0>]
(_raw_spin_unlock_irqrestore+0xc/0x38) from [<c00aa498>]
(hrtimer_try_to_cancel+0xf8/0x10c)
[  448.217455] [<c00aa498>] (hrtimer_try_to_cancel+0xf8/0x10c)
from [<c00aa4bc>] (hrtimer_cancel+0x10/0x20)
[  448.217475] [<c00aa4bc>] (hrtimer_cancel+0x10/0x20) from
[<c00e6934>] (rcu_idle_exit_common+0x5c/0xe0)
[  448.217494] [<c00e6934>] (rcu_idle_exit_common+0x5c/0xe0) from
[<c00e6ae8>] (rcu_idle_exit+0x9c/0xb4)
[  448.217514] [<c00e6ae8>] (rcu_idle_exit+0x9c/0xb4) from
[<c000f2dc>] (cpu_idle+0x98/0xf0)
[  448.217529] [<c000f2dc>] (cpu_idle+0x98/0xf0) from
[<000081ac>] (0x81ac)

CRs-Fixed: 460670
Change-Id: I588f6a864054abe6d4c249aad815c6d2f5a54077
Signed-off-by: Michael Bohan <mbohan@codeaurora.org>

Conflicts:
	kernel/hrtimer.c
hrtimer: Prevent hrtimer_enqueue_reprogram race

hrtimer_enqueue_reprogram contains a race which could result in
timer.base switch during unlock/lock sequence.

hrtimer_enqueue_reprogram is releasing the lock protecting the timer
base for calling raise_softirq_irqsoff() due to a lock ordering issue
versus rq->lock.

If during that time another CPU calls __hrtimer_start_range_ns() on
the same hrtimer, the timer base might switch, before the current CPU
can lock base->lock again and therefor the unlock_timer_base() call
will unlock the wrong lock.

[ tglx: Added comment and massaged changelog ]

Change-Id: I327d862c28f24b77a62861764393c4bf660a7318
Signed-off-by: Leonid Shatz <leonid.shatz@ravellosystems.com>
Signed-off-by: Izik Eidus <izik.eidus@ravellosystems.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: stable@vger.kernel.org
Link: http://lkml.kernel.org/r/1359981217-389-1-git-send-email-izik.eidus@ravellosystems.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Git-commit: b22affe0aef429d657bc6505aacb1c569340ddd2
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Taniya Das <tdas@codeaurora.org>
hrtimer: Consider preemption when migrating hrtimer cpu_bases

When switching to a new cpu_base in switch_hrtimer_base(), we
briefly enable preemption by unlocking the cpu_base lock in two
places. During this interval it's possible for the running thread
to be swapped to a different CPU.

Consider the following example:

CPU #0                                 CPU #1
----                                   ----
hrtimer_start()                        ...
 lock_hrtimer_base()
 switch_hrtimer_base()
  this_cpu = 0;
  target_cpu_base = 0;
  raw_spin_unlock(&cpu_base->lock)
<migrate to CPU 1>
...                                    this_cpu == 0
                                       cpu == this_cpu
                                       timer->base = CPU #0
                                       timer->base != LOCAL_CPU

Since the cached this_cpu is no longer accurate, we'll skip the
hrtimer_check_target() check. Once we eventually go to program
the hardware, we'll decide not to do so since it knows the real
CPU that we're running on is not the same as the chosen base. As
a consequence, we may end up missing the hrtimer's deadline.

Fix this by updating the local CPU number each time we retake a
cpu_base lock in switch_hrtimer_base().

Another possibility is to disable preemption across the whole of
switch_hrtimer_base.  This looks suboptimal since preemption
would be disabled while waiting for lock(s).

Change-Id: I3f76d528ab2288ef5f950f4d048e7f3fa6cf1228
Signed-off-by: Michael Bohan <mbohan@codeaurora.org>
hrtimer: Prevent enqueue of hrtimer on dead CPU

When switching the hrtimer cpu_base, we briefly allow for
preemption to become enabled by unlocking the cpu_base lock.
During this time, the CPU corresponding to the new cpu_base
that was selected may in fact go offline. In this scenario, the
hrtimer is enqueued to a CPU that's not online, and therefore
it never fires.

As an example, consider this example:

CPU #0                          CPU #1
----                            ----
...                             hrtimer_start()
                                 lock_hrtimer_base()
                                 switch_hrtimer_base()
                                  cpu = hrtimer_get_target() -> 1
                                  spin_unlock(&cpu_base->lock)
                                <migrate thread to CPU #0>
                                <offline>
spin_lock(&new_base->lock)
this_cpu = 0
cpu != this_cpu
enqueue_hrtimer(cpu_base #1)

To prevent this scenario, verify that the CPU corresponding to
the new cpu_base is indeed online before selecting it in
hrtimer_switch_base(). If it's not online, fallback to using the
base of the current CPU.

Change-Id: I6359cb299ba7e08abf25d3360fcdd925b4c03b69
Signed-off-by: Michael Bohan <mbohan@codeaurora.org>
sched: Fix SCHED_HRTICK bug leading to late preemption of tasks

SCHED_HRTICK feature is useful to preempt SCHED_FAIR tasks on-the-dot
(just when they would have exceeded their ideal_runtime). It makes use
of a a per-cpu hrtimer resource and hence alarming that hrtimer should
be based on total SCHED_FAIR tasks a cpu has across its various cfs_rqs,
rather than being based on number of tasks in a particular cfs_rq (as
implemented currently). As a result, with current code, its possible for
a running task (which is the sole task in its cfs_rq) to be preempted
much after its ideal_runtime has elapsed, resulting in increased latency
for tasks in other cfs_rq on same cpu.

Fix this by alarming sched hrtimer based on total number of SCHED_FAIR
tasks a CPU has across its various cfs_rqs.

Change-Id: I1f23680a64872f8ce0f451ac4bcae28e8967918f
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
sched: Mark schedule_io_timeout() with EXPORT_SYMBOL

Make schedule_io_timeout() visible to modules.

Change-Id: Ic0dedbad8a591a9a721f0d2e8f6c372ec75bc4b2
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
kernel: Mark find_task_by_vpid with EXPORT_SYMBOL_GPL

make find_task_by_vpid() visible to modules.

Change-Id: Ic0dedbad21a0d908a08dd64479a7acc6b3197d5f
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
sched: provide per cpu-cgroup option to notify on migrations

On systems where CPUs may run asynchronously, task migrations
between CPUs running at grossly different speeds can cause
problems.

This change provides a mechanism to notify a subsystem
in the kernel if a task in a particular cgroup migrates to a
different CPU. Other subsystems (such as cpufreq) may then
register for this notifier to take appropriate action when
such a task is migrated.

The cgroup attribute to set for this behavior is
"notify_on_migrate" .

Change-Id: Ie1868249e53ef901b89c837fdc33b0ad0c0a4590
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>

Conflicts:
	kernel/sched/core.c
	kernel/sched/rt.c
Revert "hrtimer: Prevent enqueue of hrtimer on dead CPU"

This reverts commit 878f1bd9ddd4b9734ad72d187b0266e640c99e08.

Based on upstream mailing list discussions, this patch is not
necessary since switch_hrtimer_base() is called with interrupts
disabled.

Change-Id: I53c64b1a4cea3a310ef53d1729a00baee6e4534a
Signed-off-by: Michael Bohan <mbohan@codeaurora.org>
Revert "hrtimer: Consider preemption when migrating hrtimer cpu_bases"

This reverts commit f31b9b9f30f76847c94155f9da4da12f912b0885.

Based on upstream mailing list discussions, this patch is not
necessary since switch_hrtimer_base() is called with interrupts
disabled.

Change-Id: I0244a744516e1c289af25043ee8b866be54813e3
Signed-off-by: Michael Bohan <mbohan@codeaurora.org>