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+
sched: Separate group-scheduling code more clearly

Clean up cfs/rt runqueue initialization by moving group scheduling
related code into the corresponding functions.

Also, keep group scheduling as an add-on, so that things are only done
additionally, i. e. remove the init_*_rq() calls from init_tg_*_entry().
(This removes a redundant initalization during sched_init()).

In case of group scheduling rt_rq->highest_prio.curr is now initialized
twice, but adding another #ifdef seems not worth it.

Signed-off-by: Jan H. Schönherr <schnhrr@cs.tu-berlin.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/1310661163-16606-1-git-send-email-schnhrr@cs.tu-berlin.de
Signed-off-by: Ingo Molnar <mingo@elte.hu>

Conflicts:

	kernel/sched.c
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: maintain per-rq runnable averages

From: Ben Segall <bsegall@google.com>

Since runqueues do not have a corresponding sched_entity we instead embed a
sched_avg structure directly.

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

Conflicts:
	kernel/sched_fair.c
sched: aggregate load contributed by task entities on parenting cfs_rq

From: Paul Turner <pjt@google.com>

For a given task t, we can compute its contribution to load as:
  task_load(t) = runnable_avg(t) * weight(t)

On a parenting cfs_rq we can then aggregate
  runnable_load(cfs_rq) = \Sum task_load(t), for all runnable children t

Maintain this bottom up, with task entities adding their contributed load to
the parenting cfs_rq sum.  When a task entity's load changes we add the same
delta to the maintained sum.

Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
backported by faux123 for Linux 3.0 kernel from Linux 3.5+
sched: maintain the load contribution of blocked entities

From: Paul Turner <pjt@google.com>

We are currently maintaining:
  runnable_load(cfs_rq) = \Sum task_load(t)

For all running children t of cfs_rq.  While this can be naturally updated for
tasks in a runnable state (as they are scheduled); this does not account for
the load contributed by blocked task entities.

This can be solved by introducing a separate accounting for blocked load:
  blocked_load(cfs_rq) = \Sum runnable(b) * weight(b)

Obviously we do not want to iterate over all blocked entities to account for
their decay, we instead observe that:
  runnable_load(t) = \Sum p_i*y^i

and that to account for an additional idle period we only need to compute:
  y*runnable_load(t).

This means that we can compute all blocked entities at once by evaluating:
  blocked_load(cfs_rq)` = y * blocked_load(cfs_rq)

Finally we maintain a decay counter so that when a sleeping entity re-awakens
we can determine how much of its load should be removed from the blocked sum.

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: 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: account for blocked load waking back up

From: Paul Turner <pjt@google.com>

When a running entity blocks we migrate its tracked load to
cfs_rq->blocked_runnable_avg.  In the sleep case this occurs while holding
rq->lock and so is a natural transition.  Wake-ups however, are potentially
asynchronous in the presence of migration and so special care must be taken.

We use an atomic counter to track such migrated load, taking care to match this
with the previously introduced decay counters so that we don't migrate too much
load.

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: aggregate total task_group load

From: Paul Turner <pjt@google.com>

Maintain a global running sum of the average load seen on each cfs_rq belonging
to each task group so that it may be used in calculating an appropriate
shares:weight distribution.

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: compute load contribution by a group entity

From: Paul Turner <pjt@google.com>

Unlike task entities who have a fixed weight, group entities instead own a
fraction of their parenting task_group's shares as their contributed weight.

Compute this fraction so that we can correctly account hierarchies and shared
entity nodes.

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: normalize tg load contributions against runnable time

From: Paul Turner <pjt@google.com>

Entities of equal weight should receive equitable distribution of cpu time.
This is challenging in the case of a task_group's shares as execution may be
occurring on multiple cpus simultaneously.

To handle this we divide up the shares into weights proportionate with the load
on each cfs_rq.  This does not however, account for the fact that the sum of
the parts may be less than one cpu and so we need to normalize:
  load(tg) = min(runnable_avg(tg), 1) * tg->shares
Where runnable_avg is the aggregate time in which the task_group had runnable
children.

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: maintain runnable averages across throttled periods

From: Paul Turner <pjt@google.com>

With bandwidth control tracked entities may cease execution according to user
specified bandwidth limits.  Charging this time as either throttled or blocked
however, is incorrect and would falsely skew in either direction.

What we actually want is for any throttled periods to be "invisible" to
load-tracking as they are removed from the system for that interval and
contribute normally otherwise.

Do this by moderating the progression of time to omit any periods in which the
entity belonged to a throttled hierarchy.

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

Conflicts:
	kernel/sched.c
	kernel/sched_fair.c
sched: task_times() explosion avoidance for tasks with > 2^32 acrued ticks

If stime + utime > 2^32, and lower 32 are 0 when user calls getrusage(),
you've got a dead box.
Signed-off-by: Mike Galbraith <efault@gmx.de>
backported from Linux 3.5+ to Linux 3.0 by faux123
ARM: OMAP4: PM: Keep static dep between MPUSS and ABE clockdomain

Commit 68523f4233de5f233478dde0a63047b4efb710b8 (ARM: OMAP4:
Workaround the OCP synchronisation issue with 32K synctimer)
does not include GP Timers in ABE domain. Since synchronization
issue is applicable to all GPTIMER[1-12], we also need to set
static dependency of MPUSS with abe_clkdm and l4_per_clkdm.
Dependency with l4_per_clkdm timers is already set in commit
12f27826bdaf56b01cbdfc8bdeb577ebc106dee3 (ARM: OMAP4: PM: Keep
static dep between MPUSS-EMIF and MPUSS-L3/L4 and DUCATI-L3).
Therefore, set static dependency of MPUSS with abe_clkdm.

Cc: Kevin Hilman <khilman@ti.com>
Cc: Tony Lindgren <tony@atomide.com>
Cc: Russell King <linux@arm.linux.org.uk>
Signed-off-by: Tarun Kanti DebBarma <tarun.kanti@ti.com>
modified for TUNA kernel from Linux 3.4+ by faux123
sched, fair: Let minimally loaded cpu balance the group

Currently we let the leftmost (or first idle) cpu acend the
sched_domain tree and perform load-balancing. The result is that the
busiest cpu in the group might be performing this function and pull
more load to itself. The next load balance pass will then try to
equalize this again.

Change this to pick the least loaded cpu to perform higher domain
balancing.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
modified for Linux 3.0 from Linux 3.4+