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>
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>
ARM: fault: assume no context when IRQs are disabled during data abort.

Bail out early if IRQs are disabled in do_page_fault or else
  [14415.157266] BUG: sleeping function called from invalid context at arch/arm/mm/fault.c:301

Russell King's idea from
  http://comments.gmane.org/gmane.linux.ports.arm.omap/59256

Signed-off-by: JP Abgrall <jpa@google.com>
f_fs: ffs_func_free: cleanup requests allocated by autoconfig

functionfs was leaking request objects created by autoconfig.

Bug: 8659094

Change-Id: I641326cb5cb26e0a2ffa082cd2be2c21c66c38e5
Signed-off-by: Peter Korsgaard <peter.korsgaard@barco.com>
Signed-off-by: Felipe Balbi <balbi@ti.com>
Signed-off-by: Benoit Goby <benoit@android.com>
mm: Clear page active before releasing pages

Active pages should not be freed to the page allocator as it triggers
a bad page state warning. Fengguang Wu reported the following
bug and bisected it to the patch "mm: remove lru parameter from
__lru_cache_add and lru_cache_add_lru" which is currently in mmotm as
mm-remove-lru-parameter-from-__lru_cache_add-and-lru_cache_add_lru.patch

[   84.212960] BUG: Bad page state in process rm  pfn:0b0c9
[   84.214682] page:ffff88000d646240 count:0 mapcount:0 mapping:          (null) index:0x0
[   84.216883] page flags: 0x20000000004c(referenced|uptodate|active)
[   84.218697] CPU: 1 PID: 283 Comm: rm Not tainted 3.10.0-rc4-04361-geeb9bfc #49
[   84.220729]  ffff88000d646240 ffff88000d179bb8 ffffffff82562956 ffff88000d179bd8
[   84.223242]  ffffffff811333f1 000020000000004c ffff88000d646240 ffff88000d179c28
[   84.225387]  ffffffff811346a4 ffff880000270000 0000000000000000 0000000000000006
[   84.227294] Call Trace:
[   84.227867]  [<ffffffff82562956>] dump_stack+0x27/0x30
[   84.229045]  [<ffffffff811333f1>] bad_page+0x130/0x158
[   84.230261]  [<ffffffff811346a4>] free_pages_prepare+0x8b/0x1e3
[   84.231765]  [<ffffffff8113542a>] free_hot_cold_page+0x28/0x1cf
[   84.233171]  [<ffffffff82585830>] ? _raw_spin_unlock_irqrestore+0x6b/0xc6
[   84.234822]  [<ffffffff81135b59>] free_hot_cold_page_list+0x30/0x5a
[   84.236311]  [<ffffffff8113a4ed>] release_pages+0x251/0x267
[   84.237653]  [<ffffffff8112a88d>] ? delete_from_page_cache+0x48/0x9e
[   84.239142]  [<ffffffff8113ad93>] __pagevec_release+0x2b/0x3d
[   84.240473]  [<ffffffff8113b45a>] truncate_inode_pages_range+0x1b0/0x7ce
[   84.242032]  [<ffffffff810e76ab>] ? put_lock_stats.isra.20+0x1c/0x53
[   84.243480]  [<ffffffff810e77f5>] ? lock_release_holdtime+0x113/0x11f
[   84.244935]  [<ffffffff8113ba8c>] truncate_inode_pages+0x14/0x1d
[   84.246337]  [<ffffffff8119b3ef>] evict+0x11f/0x232
[   84.247501]  [<ffffffff8119c527>] iput+0x1a5/0x218
[   84.248607]  [<ffffffff8118f015>] do_unlinkat+0x19b/0x25a
[   84.249828]  [<ffffffff810ea993>] ? trace_hardirqs_on_caller+0x210/0x2ce
[   84.251382]  [<ffffffff8144372e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[   84.252879]  [<ffffffff8118f10d>] SyS_unlinkat+0x39/0x4c
[   84.254174]  [<ffffffff825874d6>] system_call_fastpath+0x1a/0x1f
[   84.255596] Disabling lock debugging due to kernel taint
The problem was that a page marked for activation was released via
pagevec. This patch clears the active bit before freeing in this case.

Signed-off-by: Mel Gorman <mgorman@suse.de>
Reported-and-Tested-by: Fengguang Wu <fengguang.wu@intel.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>