arch/arm/mach-msm/cpufreq.c: reduce dmesg log spam

Signed-off-by: Paul Reioux <reioux@gmail.com>
SCHEDULER: Autogroup patch group by current user android UID instead of task ID
sched: Optimize build_sched_domains() for saving first SD node for a cpu

Date	Tue, 4 Jun 2013 16:50:18 +0530

We are saving first scheduling domain for a cpu in build_sched_domains() by
iterating over the nested sd->child list. We don't actually need to do it this
way.

*per_cpu_ptr(d.sd, i) is guaranteed to be NULL in the beginning as we have
called __visit_domain_allocation_hell() which does a memset to zero for struct
s_data.

So, save pointer to first SD while running the iteration loop over tl's.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Optimize build_sched_domains() for saving first SD node for a cpu

We are saving first scheduling domain for a cpu in build_sched_domains() by
iterating over the nested sd->child list. We don't actually need to do it this
way.

tl will be equal to sched_domain_topology for the first iteration and so we can
set *per_cpu_ptr(d.sd, i) based on that.  So, save pointer to first SD while
running the iteration loop over tl's.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Remove unused params of build_sched_domain()

Date	Tue, 4 Jun 2013 16:50:19 +0530

build_sched_domain() never uses parameter struct s_data *d and so passing it is
useless.

Remove it.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
SELinux: reduce overhead of mls_level_isvalid() function call

Date	Wed, 10 Apr 2013 14:26:22 -0400

While running the high_systime workload of the AIM7 benchmark on
a 2-socket 12-core Westmere x86-64 machine running 3.8.2 kernel,
it was found that a pretty sizable amount of time was spent in the
SELinux code. Below was the perf trace of the "perf record -a -s"
of a test run at 1500 users:

  3.96%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  1.44%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  1.33%            ls  [kernel.kallsyms]     [k] find_next_bit

The ebitmap_get_bit() was the hottest function in the perf-report
output.  Both the ebitmap_get_bit() and find_next_bit() functions
were, in fact, called by mls_level_isvalid(). As a result, the
mls_level_isvalid() call consumed 6.73% of the total CPU time of all
the 24 virtual CPUs which is quite a lot.

Looking at the mls_level_isvalid() function, it is checking to see
if all the bits set in one of the ebitmap structure are also set in
another one as well as the highest set bit is no bigger than the one
specified by the given policydb data structure. It is doing it in
a bit-by-bit manner. So if the ebitmap structure has many bits set,
the iteration loop will be done many times.

The current code can be rewritten to use a similar algorithm as the
ebitmap_contains() function with an additional check for the highest
set bit. With that change, the perf trace showed that the used CPU
time drop down to just 0.09% of the total which is about 100X less
than before.

  0.04%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  0.04%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  0.01%            ls  [kernel.kallsyms]     [k] find_next_bit

Actually, the remaining ebitmap_get_bit() and find_next_bit() function
calls are made by other kernel routines as the new mls_level_isvalid()
function will not call them anymore.

This patch also improves the high_systime AIM7 benchmark result,
though the improvement is not as impressive as is suggested by the
reduction in CPU time. The table below shows the performance change
on the 2-socket x86-64 system mentioned above.

+--------------+---------------+----------------+-----------------+
|   Workload   | mean % change | mean % change  | mean % change   |
|              | 10-100 users  | 200-1000 users | 1100-2000 users |
+--------------+---------------+----------------+-----------------+
| high_systime |     +0.2%     |     +1.1%      |     +2.4%       |
+--------------+---------------+----------------+-----------------+
Signed-off-by: Waiman Long <Waiman.Long@hp.com>

Signed-off-by: Paul Reioux <reioux@gmail.com>
Revert "SELinux: reduce overhead of mls_level_isvalid() function call"

This reverts commit ada60871076634915c357cfa9640beb4e7730da7.
SELinux: Reduce overhead of mls_level_isvalid() function call

Date	Mon, 10 Jun 2013 13:55:08 -0400

v4->v5:
  - Fix scripts/checkpatch.pl warning.

v3->v4:
  - Merge the 2 separate while loops in ebitmap_contains() into
    a single one.

v2->v3:
  - Remove unused local variables i, node from mls_level_isvalid().

v1->v2:
 - Move the new ebitmap comparison logic from mls_level_isvalid()
   into the ebitmap_contains() helper function.
 - Rerun perf and performance tests on the latest v3.10-rc4 kernel.

While running the high_systime workload of the AIM7 benchmark on
a 2-socket 12-core Westmere x86-64 machine running 3.10-rc4 kernel
(with HT on), it was found that a pretty sizable amount of time was
spent in the SELinux code. Below was the perf trace of the "perf
record -a -s" of a test run at 1500 users:

  5.04%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  1.96%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  1.95%            ls  [kernel.kallsyms]     [k] find_next_bit

The ebitmap_get_bit() was the hottest function in the perf-report
output.  Both the ebitmap_get_bit() and find_next_bit() functions
were, in fact, called by mls_level_isvalid(). As a result, the
mls_level_isvalid() call consumed 8.95% of the total CPU time of
all the 24 virtual CPUs which is quite a lot. The majority of the
mls_level_isvalid() function invocations come from the socket creation
system call.

Looking at the mls_level_isvalid() function, it is checking to see
if all the bits set in one of the ebitmap structure are also set in
another one as well as the highest set bit is no bigger than the one
specified by the given policydb data structure. It is doing it in
a bit-by-bit manner. So if the ebitmap structure has many bits set,
the iteration loop will be done many times.

The current code can be rewritten to use a similar algorithm as the
ebitmap_contains() function with an additional check for the
highest set bit. The ebitmap_contains() function was extended to
cover an optional additional check for the highest set bit, and the
mls_level_isvalid() function was modified to call ebitmap_contains().

With that change, the perf trace showed that the used CPU time drop
down to just 0.08% (ebitmap_contains + mls_level_isvalid) of the
total which is about 100X less than before.

  0.07%            ls  [kernel.kallsyms]     [k] ebitmap_contains
  0.05%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  0.01%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  0.01%            ls  [kernel.kallsyms]     [k] find_next_bit

The remaining ebitmap_get_bit() and find_next_bit() functions calls
are made by other kernel routines as the new mls_level_isvalid()
function will not call them anymore.

This patch also improves the high_systime AIM7 benchmark result,
though the improvement is not as impressive as is suggested by the
reduction in CPU time spent in the ebitmap functions. The table below
shows the performance change on the 2-socket x86-64 system (with HT
on) mentioned above.

+--------------+---------------+----------------+-----------------+
|   Workload   | mean % change | mean % change  | mean % change   |
|              | 10-100 users  | 200-1000 users | 1100-2000 users |
+--------------+---------------+----------------+-----------------+
| high_systime |     +0.1%     |     +0.9%      |     +2.6%       |
+--------------+---------------+----------------+-----------------+
Signed-off-by: Waiman Long <Waiman.Long@hp.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Use cached value of span instead of calling sched_domain_span()

Date	Tue, 11 Jun 2013 16:32:43 +0530

In the beginning of build_sched_groups() we called sched_domain_span() and
cached its return value in span. Few statements later we are calling it again to
get the same pointer.

Lets use the cached value instead as it hasn't changed in between.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: don't call get_group() for covered cpus

Date	Tue, 11 Jun 2013 16:32:44 +0530

In build_sched_groups() we don't need to call get_group() for cpus which are
already covered in previous iterations. So, call get_group() after checking if
cpu is covered or not.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: remove WARN_ON(!sd) from init_sched_groups_power()

Date	Tue, 11 Jun 2013 16:32:45 +0530

sd can't be NULL in init_sched_groups_power() and so checking it for NULL isn't
useful. In case it is required, then also we need to rearrange the code a bit as
we already accessed invalid pointer sd to get sg: sg = sd->groups.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: reduce calculation effort in fix_small_imbalance

Date	Mon, 17 Jun 2013 21:00:22 +0800

Actually all below item could be repalced by scaled_busy_load_per_task
	(sds->busiest_load_per_task * SCHED_POWER_SCALE)
		/sds->busiest->sgp->power;

Signed-off-by: Lei Wen <leiwen@marvell.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: scale the busy and this queue's per-task load before compare

Date	Mon, 17 Jun 2013 21:00:23 +0800

Since for max_load and this_load, they are the value that already be
scaled. It is not reasonble to get a minimum value between the scaled
and non-scaled value, like below example.
	min(sds->busiest_load_per_task, sds->max_load);

Also add comment over in what condition, there would be cpu power gain
in move the load.

Signed-off-by: Lei Wen <leiwen@marvell.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: scale cpu load for judgment of group imbalance

Date	Mon, 17 Jun 2013 21:00:24 +0800

We cannot compare two load directly from two cpus, since the cpu power
over two cpu may vary largely.

Suppose we meet such two kind of cpus.
CPU A:
	No real time work, and there are 3 task, with rq->load.weight
being 512.
CPU B:
	Has real time work, and it take 3/4 of the cpu power, which
makes CFS only take 1/4, that is 1024/4=256 cpu power. And over its CFS
runqueue, there is only one task with weight as 128.

Since both cpu's CFS task take for half of the CFS's cpu power, it
should be considered as balanced in such case.

But original judgment like:
        if ((max_cpu_load - min_cpu_load) >= avg_load_per_task &&
            (max_nr_running - min_nr_running) > 1)
It makes (512-128)>=((512+128)/4), and lead to imbalance conclusion...
Make the load as scaled, to avoid such case.

Signed-off-by: Lei Wen <leiwen@marvell.com>

modified for Mako kernel from LKML reference
Signed-off-by: Paul Reioux <reioux@gmail.com>
silence GCC 4.7 compile warning
Use 200MHz GPU frequency
sched: Reduce overestimating rq->avg_idle

Date	Thu, 29 Aug 2013 13:05:34 -0700

When updating avg_idle, if the delta exceeds some max value, then avg_idle
gets set to the max, regardless of what the previous avg was. This can cause
avg_idle to often be overestimated.

This patch modifies the way we update avg_idle by always updating it with the
function call to update_avg() first. Then, if avg_idle exceeds the max, we set
it to the max.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Rik van Riel <riel@redhat.com>

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Consider max cost of idle balance per sched domain

Date    Thu, 29 Aug 2013 13:05:35 -0700

In this patch, we keep track of the max cost we spend doing idle load balancing
for each sched domain. If the avg time the CPU remains idle is less then the
time we have already spent on idle balancing + the max cost of idle balancing
in the sched domain, then we don't continue to attempt the balance. We also
keep a per rq variable, max_idle_balance_cost, which keeps track of the max
time spent on newidle load balances throughout all its domains. Additionally,
we swap sched_migration_cost used in idle_balance for rq->max_idle_balance_cost.

By using the max, we avoid overrunning the average. This further reduces the chance
we attempt balancing when the CPU is not idle for longer than the cost to balance.

I also limited the max cost of each domain to 5*sysctl_sched_migration_cost as
a way to prevent the max from becoming too inflated.

Signed-off-by: Jason Low <jason.low2@hp.com>

backported for Linux 3.4

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Periodically decay max cost of idle balance

This RFC patch builds on patch 2 and periodically decays that max value to
do idle balancing per sched domain.

Though we want to decay it fairly consistently, we may not want to lower it by
too much each time, especially since avg_idle is capped based on that value.
So I thought that decaying the value every second and lowering it by half a
percent each time appeared to be fairly reasonable.

This change would allow us to remove the limit we set on each domain's max cost
to idle balance. Also, since the max can be reduced now, we now have to
update rq->max_idle balance_cost more frequently. So after every idle balance,
we loop through the sched domain to find the max sd's newidle load balance cost
for any one domain. Then we will set rq->max_idle_balance_cost to that value.

Since we are now decaying the max cost to do idle balancing, that max cost can
also become not high enough. One possible explanation for why is that
besides the time spent on each newidle load balance, there are other costs
associated with attempting idle balancing. Idle balance also releases and
reacquires a spin lock. That cost is not counted when we keep track of each
domain's cost to do newidle load balance. Also, acquiring the rq locks can
potentially prevent other CPUs from running something useful. And after
migrating tasks, it might potentially have to pay the costs of cache misses and
refreshing tasks' cache.

Because of that, this patch also compares avg_idle with max cost to do idle
balancing + sched_migration_cost. While using the max cost helps reduce
overestimating the average idle, the sched_migration_cost can help account
for those additional costs of idle balancing.

Signed-off-by: Jason Low <jason.low2@hp.com>
[peterz: rewrote the logic, but kept the spirit]
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
backported to Linux 3.4
Signed-off-by: Paul Reioux <reioux@gmail.com>
hwrng: add randomness to system from rng sources

When bringing a new RNG source online, it seems like it would make sense
to use some of its bytes to make the system entropy pool more random,
as done with all sorts of other devices that contain per-device or
per-boot differences.

Signed-off-by: Kees Cook <keescook@chromium.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>