Introduce timer slack controller

From: "Kirill A. Shutemov" <kirill@shutemov.name>

task_get_effective_timer_slack() returns timer slack value to be used
to configure per-task timers. It can be equal or higher than task's
timer slack value.

For now task_get_effective_timer_slack() returns timer_slack_ns of the
task. Timer slack cgroup controller will implement a bit more
sophisticated logic.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

PR_GET_EFFECTIVE_TIMERSLACK allows process to know its effective timer
slack value.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

Every task_struct has timer_slack_ns value. This value uses to round up
poll() and select() timeout values. This feature can be useful in
mobile environment where combined wakeups are desired.

Originally, prctl() was the only way to change timer slack value of
a process. So you was not able change timer slack value of another
process.

cgroup subsys "timer_slack" implements timer slack controller. It
provides a way to set minimal timer slack value for a group of tasks.
If a task belongs to a cgroup with minimal timer slack value higher than
task's value, cgroup's value will be applied.

Timer slack controller allows to implement setting timer slack value of
a process based on a policy. For example, you can create foreground and
background cgroups and move tasks between them based on system state.

Idea-by: Jacob Pan <jacob.jun.pan@linux.intel.com>
Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>

From: "Kirill A. Shutemov" <kirill@shutemov.name>

Changelog:

v10 [7 month later, thanks to A Plumber's Wish List]:
 - rebased to linux-next-20111011
v9:
 - update documentation
 - minor cleanup
v8:
 - change hiearchy rules
 - introduce timer_slack.effective_slack_ns
 - get_task_timer_slack() -> task_get_effective_timer_slack()
 - task_get_effective_timer_slack() splited in separate patch
 - implement PR_GET_EFFECTIVE_TIMERSLACK
v7:
 - totally reworked interface and rewritten from scratch
   (See Documentation/cgroups/timer_slack.txt for more information)
v6:
 - add documentation
 - use notifier_call_chain() instead of check hook
 - fix validate_change()
 - cleanup
v5:
 - -EBUSY on writing to timer_slack.min_slack_ns/max_slack_ns if a child has
   wider min-max range
v4:
 - hierarchy support
 - drop dummy_timer_slack_check()
 - workaround lockdep false (?) positive
 - allow 0 as timer slack value
v3:
 - rework interface
 - s/EXPORT_SYMBOL/EXPORT_SYMBOL_GPL/
v2:
 - fixed with CONFIG_CGROUP_TIMER_SLACK=y
v1:
 - initial revision

Kirill A. Shutemov (3):
  hrtimer: introduce effective timer slack
  hrtimer: implement PR_GET_EFFECTIVE_TIMERSLACK
  cgroups: introduce timer slack controller

 Documentation/cgroups/timer_slack.txt |   72 +++++++++++++++++++
 fs/select.c                           |    7 +--
 include/linux/cgroup_subsys.h         |    7 ++
 include/linux/prctl.h                 |    6 ++
 include/linux/sched.h                 |   10 +++
 init/Kconfig                          |    8 ++
 kernel/Makefile                       |    1 +
 kernel/cgroup_timer_slack.c           |  124 +++++++++++++++++++++++++++++++++
 kernel/fork.c                         |    4 +
 kernel/futex.c                        |    4 +-
 kernel/hrtimer.c                      |    2 +-
 kernel/sys.c                          |    3 +
 12 files changed, 240 insertions(+), 8 deletions(-)
 create mode 100644 Documentation/cgroups/timer_slack.txt
 create mode 100644 kernel/cgroup_timer_slack.c
CHROMIUM: ARM: delay: Implement ndelay using UMULL

ARM has a UMULL (32x32=64-bit) multiply instruction, which is very
convenient for doing "division by multiplication".

For 'busy-loop' delaying, the number of loops calculation is (for ns in
nsecs):

loops = ns / 1000000000 * HZ * loops_per_jiffy
loops = (ns * ((HZ / 1000000000) << 32) * lpj) >> 32

Using UMULL makes it trivial to do the * and (>> 32).
The constant ((HZ / 1000000000) << 32) can be pre-computed at
compile-time, since HZ is constant.

Keeping the same HZ <= 1000 range as before, this gives an ndelay range
up to 999999 nsec, and allows loops_per_jiffy values up to 8589934, all
with no loss of precision.

This patch just adds ndelay(), but leaves udelay() unchanged.

Signed-off-by: Daniel Kurtz <djkurtz@chromium.org>

BUG=chromium-os:33912
TEST=manual, using ktime() to time ndelay, and const ndelay, loops
TEST=manual, observe i2c transactions of i2c-s3c2410 driver

Change-Id: Icfae5a7d46619e914670fe2de1f2325e9a96a972
CHROMIUM: ARM: Implement udelay using ndelay

ndelay() based on UMULL has a range up to 999,999 ns.

udelay is implemented by iteratively calling ndelay in chunks of 999
us.

Signed-off-by: Daniel Kurtz <djkurtz@chromium.org>

BUG=chromium-os:33912
TEST=manually with using udelay() loops and measuring elapsed ktime()

Change-Id: I2569fc531334c5c9f9609b92abb6fb6b50afa13d
sched/nohz: Rewrite, fix and add more accurate load-avg computation

Part 1)

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. Consider following case:
5HZ+1
| cpu0_load     cpu1    cpu2    cpu3    calc_load_tasks    tasks_idle
|    1           1       1       1
|  -->calc_load                             1                  0
|    1           1       1       1
|                    -->calc_load           2                  0
|    0           0       1       0
|                    -->calc_load           2+1-3=0            -3
|    1           1       0       1
|                            -->calc_load   1-1=0              -1
V
5HZ+11     -->calc_global_load              0                  0

actually the load should be around 3, but shows nearly 0.

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

We provides a solution, by taking those load not calculated cpus' idle out from
global idle as calc_unmask_cpu_load_idle. Then when calc_load execute on every
cpu, we only fold calc_unmask_cpu_load_idle. After this patch, case above
should be as follow:
5HZ+1
| cpu0_load     cpu1    cpu2    cpu3   calc_load_tasks tasks_idle  unmask_idle
|    1           1       1       1
|  -->calc_load                             1              0           0
|    1           1       1       1
|              -->calc_load                 2              0           0
|    0           0       1       0
|                    -->calc_load           2+1-1=2        -3          -1
|    1           1       0       1
|                            -->calc_load   2+1=3          -2-1=-3     0
V
5HZ+11     -->calc_global_load              3              -3          0

CC: Peter Zijlstra <peterz@infradead.org>
CC: Doug Smythies <dsmythies@telus.net>
CC: Ingo Molnar <mingo@redhat.com>
CC: Tao Ma <tm@tao.ma>
CC: Sha Zhengju <handai.szj@gmail.com>
Reported-by: Sha Zhengju <handai.szj@gmail.com>
Signed-off-by: Charles Wang <muming.wq@taobao.com>

Part 2)

Thanks to Charles Wang for spotting the defects in the current code:

 - If we go idle during the sample window -- after sampling, we get a
   negative bias because we can negate our own sample.

 - If we wake up during the sample window we get a positive bias
   because we push the sample to a known active period.

So rewrite the entire nohz load-avg muck once again, now adding
copious documentation to the code.

Reported-and-tested-by: Doug Smythies <dsmythies@telus.net>
Reported-and-tested-by: Charles Wang <muming.wq@gmail.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: stable@kernel.org
Link: http://lkml.kernel.org/r/1340373782.18025.74.camel@twins
[ minor edits ]
Signed-off-by: Ingo Molnar <mingo@kernel.org>
exynos: Update loops_per_jiffy with frequency transition

Update the loops_per_jiffy with every transition in the cpu frequency.
Revert "Workaround for outdated kernel tree"

This reverts commit fc47bea3c904c5426a7e0ffda625dcbda7c56a4e.
Revert "exynos: Update loops_per_jiffy with frequency transition"

This reverts commit 3c1cf1067249ac2eb280b7f413884e381c87e86e.
Source update: update4 > update5
Revert "CHROMIUM: ARM: Implement udelay using ndelay"

This reverts commit cf67d2da86c0b72ab109d918e5eb400348eb2d72.
Revert "CHROMIUM: ARM: delay: Implement ndelay using UMULL"

This reverts commit a51dbf75f89b230d43d107cbe8d430480ddf5966.