PM / Sleep: Do not check wakeup too often in try_to_freeze_tasks()

Use the observation that it is more efficient to check the wakeup
variable once before the loop reporting tasks that were not
frozen in try_to_freeze_tasks() than to do that in every step of that
loop.

Signed-off-by: Rafael J. Wysocki <rjw@sisk.pl>

Conflicts:

	kernel/power/process.c

Signed-off-by: Srivalli Oguri <oguri@codeaurora.org>
(cherry picked from commit a15cc22b56b803b8f943c57d9535bdb9953ff3ec)

Change-Id: Ic41cd71a0ec49cd0c633c14aa3fce02025a4de3f
Signed-off-by: Sridhar Gujje <sgujje@codeaurora.org>
sched: Folding nohz load accounting more accurate

After patch 453494c3d4 (sched: Fix nohz load accounting -- again!), we can fold
the idle into calc_load_tasks_idle between the last cpu load calculating and
calc_global_load calling. However problem still exits between the first cpu
load calculating and the last cpu load calculating. Every time when we do load
calculating, calc_load_tasks_idle will be added into calc_load_tasks, even if
the idle load is caused by calculated cpus. This problem is also described in
the following link:

https://lkml.org/lkml/2012/5/24/419

This bug can be found in our work load. The average running processes number
is about 15, but the load only shows about 4.

The patch provides a solution, by taking calculated load cpus' idle away from
 real effective idle. First adds a cpumask to record those cpus that alread
calculated their load, and then adds a calc_unmask_cpu_load_idle to record
thoses not marked cpus' go-idle load. Calc_unmask_cpu_load_idle takes place
of calc_load_tasks_idle to be added into calc_load_tasks every 5HZ when cpu
calculate its load. Go-idle load on those cpus which load alread has been calculated
will only be added into calc_load_tasks_idle, no in calc_unmask_cpu_load_idle.

Reported-by: Sha Zhengju <handai.szj@xxxxxxxxx>
Signed-off-by: Charles Wang <muming.wq@xxxxxxxxxx>
modified for HTC One X kernel from Linux 3.4+ by faux123
block: introduce the BFQ-v5 I/O sched for 3.0

Add the BFQ-v5 I/O scheduler to 3.0.
The general structure is borrowed from CFQ, as much code. A (bfq_)queue is
associated to each task doing I/O on a device, and each time a scheduling
decision has to be taken a queue is selected and it is served until it expires.

    - Slices are given in the service domain: tasks are assigned budgets,
      measured in number of sectors. Once got the disk, a task must
      however consume its assigned budget within a configurable maximum time
      (by default, the maximum possible value of the budgets is automatically
      computed to comply with this timeout). This allows the desired latency
      vs "throughput boosting" tradeoff to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - A low-latency tunable is provided; if enabled, both interactive and soft
      real-time applications are guaranteed very low latency.

    - Latency guarantees are preserved also in presence of NCQ.

    - High throughput with flash-based devices, while still preserving
      latency guarantees.

    - Useful features borrowed from CFQ: cooperating-queues merging (with
      some additional optimizations with respect to the original CFQ version),
      static fallback queue for OOM.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio and an ioprio_class.

    - If the cgroups interface is used, weights can be explictly assigned,
      otherwise ioprio values are mapped to weights using the relation
      weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher priority
      queues.  Among queues in the same class the bandwidth is distributed
      in proportion to the weights of each queue. A very thin extra bandwidth
      is however guaranteed to the Idle class, to prevent it from starving.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

Conflicts:

	block/bfq-iosched.c
cpufreq: smartassv2: make smartass scale down faster (from @existz)
sched: track the runnable average on a per-task entitiy basis

From: Paul Turner <pjt@google.com>

Instead of tracking averaging the load parented by a cfs_rq, we can track
entity load directly.  With the load for a given cfs_rq then being the sum of
its children.

To do this we represent the historical contribution to runnable average within each
trailing 1024us of execution as the coefficients of a geometric series.

We can express this for a given task t as:
  runnable_sum(t) = \Sum u_i * y^i, runnable_avg_period(t) = \Sum 1024 * y^i
  load(t) = weight_t * runnable_sum(t) / runnable_avg_period(t)

Where: u_i is the usage in the last i`th 1024us period (approximately 1ms) ~ms
and y is chosen such that y^k = 1/2.  We currently choose k to be 32 which
roughly translates to about a sched period.

Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
backported to Linux 3.0.x by faux123 from Linux 3.5+
sched: add an rq migration call-back to sched_class

From: Paul Turner <pjt@google.com>

Since we are now doing bottom up load accumulation we need explicit
notification when a task has been re-parented so that the old hierarchy can be
updated.

Adds: migrate_task_rq(struct task_struct *p, int next_cpu)

(The alternative is to do this out of __set_task_cpu, but it was suggested that
this would be a cleaner encapsulation.)

Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
backported from Linux 3.5+ to Linux 3.0 by faux123
sched: make __update_entity_runnable_avg() fast

From: Paul Turner <pjt@google.com>

__update_entity_runnable_avg forms the core of maintaining an entity's runnable
load average.  In this function we charge the accumulated run-time since last
update and handle appropriate decay.  In some cases, e.g. a waking task, this
time interval may be much larger than our period unit.

Fortunately we can exploit some properties of our series to perform decay for a
blocked update in constant time and account the contribution for a running
update in essentially-constant* time.

[*]: For any running entity they should be performing updates at the tick which
gives us a soft limit of 1 jiffy between updates, and we can compute up to a
32 jiffy update in a single pass.

Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
backported from Linux 3.5+ to Linux 3.0 by faux123
sched: unify the check on atomic sleeping in __might_sleep() & schedule_bug()

From: Michael Wang <wangyun@linux.vnet.ibm.com>

Fengguang Wu <wfg@linux.intel.com> has reported the bug:

[    0.043953] BUG: scheduling while atomic: swapper/0/1/0x10000002
[    0.044017] no locks held by swapper/0/1.
[    0.044692] Pid: 1, comm: swapper/0 Not tainted 3.6.0-rc1-00420-gb7aebb9 #34
[    0.045861] Call Trace:
[    0.048071]  [<c106361e>] __schedule_bug+0x5e/0x70
[    0.048890]  [<c1b28701>] __schedule+0x91/0xb10
[    0.049660]  [<c14472ea>] ? vsnprintf+0x33a/0x450
[    0.050444]  [<c1060006>] ? lg_local_lock+0x6/0x70
[    0.051256]  [<c14fb5b1>] ? wait_for_xmitr+0x31/0x90
[    0.052019]  [<c144fd55>] ? do_raw_spin_unlock+0xa5/0xf0
[    0.052903]  [<c1b2a532>] ? _raw_spin_unlock+0x22/0x30
[    0.053759]  [<c105cdbb>] ? up+0x1b/0x70
[    0.054421]  [<c1065d6b>] __cond_resched+0x1b/0x30
[    0.055228]  [<c1b292d5>] _cond_resched+0x45/0x50
[    0.056020]  [<c1b26c58>] mutex_lock_nested+0x28/0x370
[    0.056884]  [<c1034222>] ? console_unlock+0x3a2/0x4e0
[    0.057741]  [<c1ac8559>] __irq_alloc_descs+0x39/0x1c0
[    0.058589]  [<c10223bc>] io_apic_setup_irq_pin+0x2c/0x310
[    0.060042]  [<c20638df>] setup_IO_APIC+0x101/0x744
[    0.060878]  [<c1021d51>] ? clear_IO_APIC+0x31/0x50
[    0.061695]  [<c20600f4>] native_smp_prepare_cpus+0x538/0x680
[    0.062644]  [<c2056a91>] ? do_one_initcall+0x12c/0x12c
[    0.063517]  [<c2056a91>] ? do_one_initcall+0x12c/0x12c
[    0.064016]  [<c2056adc>] kernel_init+0x4b/0x17f
[    0.064790]  [<c2056a91>] ? do_one_initcall+0x12c/0x12c
[    0.065660]  [<c1b2bbd6>] kernel_thread_helper+0x6/0x10
It was caused by that:

	native_smp_prepare_cpus()
	preempt_disable()		//preempt_count++
	mutex_lock()			//in __irq_alloc_descs
	__might_sleep()			//system is booting, avoid check
	might_resched()
	__schedule()
	preempt_disable()		//preempt_count++
	schedule_bug()			//preempt_count > 1, report bug
The __might_sleep() avoid check on atomic sleeping until the system booted
while the schedule_bug() doesn't, it's the reason for the bug.

This patch will add one additional check in schedule_bug() to avoid check
until the system booted, so the check on atomic sleeping will be unified.

Signed-off-by: Michael Wang <wangyun@linux.vnet.ibm.com>
Tested-by: Fengguang Wu <wfg@linux.intel.com>
backported to Tuna Kernel by faux123 from Linux 3.5+
ARM: smp: Fix cpu_up() racing with sys_reboot

Nothing stops a process from hotplugging in a CPU concurrently
with a sys_reboot() call. In such a situation we could have
ipi_cpu_stop() mark a cpu as 'offline' and _cpu_up() ignore the
fact that the CPU is not really offline and call the
CPU_UP_PREPARE notifier. When this happens stop_machine code will
complain that the cpu thread already exists and BUG_ON().

CPU0                      CPU1

sys_reboot()
 kernel_restart()
  machine_restart()
   machine_shutdown()
    smp_send_stop()
    ...                   ipi_cpu_stop()
                           set_cpu_online(1, false)
                            local_irq_disable()
                             while(1)
    <PREEMPT>
cpu_up()
 _cpu_up()
   if (!cpu_online(1))
    __cpu_notify(CPU_UP_PREPARE...)
cpu_stop_cpu_callback()
  BUG_ON(stopper->thread)

This is easily reproducible by hotplugging in and out in a tight
loop while also rebooting.

Since the CPU is not really offline and hasn't gone through the
proper steps to be marked as such, let's mark the CPU as inactive.
This is just as easily testable as online and avoids any possibility
of _cpu_up() trying to bring the CPU back online when it never was
offline to begin with.

Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
modified for tuna kernel by faux123 from Linux 3.5+
sched: update correct entity's runtime in check_preempt_wakeup()

While looking at check_preempt_wakeup() I realized that we are
potentially updating the wrong entity in the fair-group scheduling
case. In this case the current task's cfs_rq may not be the same as
the one used for the comparison between the waking task and the
existing task's vruntime.

This potentially results in us using a stale vruntime in the
pre-emption decision, providing a small false preference for the
previous task. The effects of this are bounded since we always
perform a hierarchal update on the tick.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/CAPM31R+2Ke2urUZKao5W92_LupdR4AYEv-EZWiJ3tG=tEes2cw@mail.gmail.com
Signed-off-by: Ingo Molnar <mingo@elte.hu>
sched: Don't update shares twice on on_rq parent

In dequeue_task_fair() we bail on dequeue when we encounter a parenting entity
with additional weight.  However, we perform a double shares update on this
entity as we continue the shares update traversal from this point, despite
dequeue_entity() having already updated its queuing cfs_rq.
Avoid this by starting from the parent when we resume.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20110707053059.797714697@google.com
Signed-off-by: Ingo Molnar <mingo@elte.hu>
sched, cgroup: Optimize load_balance_fair()

Use for_each_leaf_cfs_rq() instead of list_for_each_entry_rcu(), this
achieves that load_balance_fair() only iterates those task_groups that
actually have tasks on busiest, and that we iterate bottom-up, trying to
move light groups before the heavier ones.

No idea if it will actually work out to be beneficial in practice, does
anybody have a cgroup workload that might show a difference one way or
the other?

[ Also move update_h_load to sched_fair.c, loosing #ifdef-ery ]

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Reviewed-by: Paul Turner <pjt@google.com>
Link: http://lkml.kernel.org/r/1310557009.2586.28.camel@twins
Signed-off-by: Ingo Molnar <mingo@elte.hu>
sched: Replace use of entity_key()

"entity_key()" is only used in "__enqueue_entity()" and
its only function is to subtract a tasks vruntime by
its groups minvruntime.
Before this patch a rbtree enqueue-decision is done by
comparing two tasks in the style:

	"if (entity_key(cfs_rq, se) < entity_key(cfs_rq, entry))"

which would be

	"if (se->vruntime-cfs_rq->min_vruntime < entry->vruntime-cfs_rq->min_vruntime)"

or (if reducing cfs_rq->min_vruntime out)

	"if (se->vruntime < entry->vruntime)"

which is

	"if (entity_before(se, entry))"

So we do not need "entity_key()".
If "entity_before()" is inline we will also save one subtraction (only one,
because "entity_key(cfs_rq, se)"  was cached in "key")

Signed-off-by: Stephan Baerwolf <stephan.baerwolf@tu-ilmenau.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/n/tip-ns12mnd2h5w8rb9agd8hnsfk@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@elte.hu>
sched: Cleanup duplicate local variable in [enqueue|dequeue]_task_fair

No need to define a new "cfs_rq" variable in the "for" block.
Just use the one at the top of the function.

Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/1311297271.3938.1352.camel@minggr.sh.intel.com
Signed-off-by: Ingo Molnar <mingo@elte.hu>
sched: Kill WAKEUP_PREEMPT

Remove the WAKEUP_PREEMPT feature, disabling it doesn't make any sense
and its outlived its use by a long long while.

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Acked-by: Mike Galbraith <efault@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20110729082033.GB12106@zhy
Signed-off-by: Ingo Molnar <mingo@elte.hu>
EXPERIMENTAL: try to implement ondemand governor from faux123's Mako kernel source.
cpufreq: ondemand: tweaks from mike1968's kernel source.