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: Pranav Vashi <neobuddy89@gmail.com>
SELinux: include definition of new capabilities

Signed-off-by: Eric Paris <eparis@redhat.com>
Signed-off-by: James Morris <james.l.morris@oracle.com>
[sds: rename epollwakeup to block_suspend to match upstream merge]
Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
writeback: fix occasional slow sync(1)

In case when system contains no dirty pages, wakeup_flusher_threads() will
submit WB_SYNC_NONE writeback for 0 pages so wb_writeback() exits
immediately without doing anything, even though there are dirty inodes in
the system.  Thus sync(1) will write all the dirty inodes from a
WB_SYNC_ALL writeback pass which is slow.

Fix the problem by using get_nr_dirty_pages() in wakeup_flusher_threads()
instead of calculating number of dirty pages manually.  That function also
takes number of dirty inodes into account.

Signed-off-by: Jan Kara <jack@suse.cz>
Reported-by: Paul Taysom <taysom@chromium.org>
Cc: Wu Fengguang <fengguang.wu@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
jiffies conversions: Use compile time constants when possible

Do the multiplications and divisions at compile time
instead of runtime when the converted value is a constant.

Make the calculation functions static __always_inline to jiffies.h.

Add #defines with __builtin_constant_p to test and use the
static inline or the runtime functions as appropriate.

Prefix the old exported symbols/functions with __

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
softirq: reduce latencies

In various network workloads, __do_softirq() latencies can be up
to 20 ms if HZ=1000, and 200 ms if HZ=100.

This is because we iterate 10 times in the softirq dispatcher,
and some actions can consume a lot of cycles.

This patch changes the fallback to ksoftirqd condition to :

- A time limit of 2 ms.
- need_resched() being set on current task

When one of this condition is met, we wakeup ksoftirqd for further
softirq processing if we still have pending softirqs.

Using need_resched() as the only condition can trigger RCU stalls,
as we can keep BH disabled for too long.

I ran several benchmarks and got no significant difference in
throughput, but a very significant reduction of latencies (one order
of magnitude) :

In following bench, 200 antagonist "netperf -t TCP_RR" are started in
background, using all available cpus.

Then we start one "netperf -t TCP_RR", bound to the cpu handling the NIC
IRQ (hard+soft)

Before patch :

RT_LATENCY,MIN_LATENCY,MAX_LATENCY,P50_LATENCY,P90_LATENCY,P99_LATENCY,MEAN_LATENCY,STDDEV_LATENCY
MIGRATED TCP REQUEST/RESPONSE TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET
to 7.7.7.84 () port 0 AF_INET : first burst 0 : cpu bind
RT_LATENCY=550110.424
MIN_LATENCY=146858
MAX_LATENCY=997109
P50_LATENCY=305000
P90_LATENCY=550000
P99_LATENCY=710000
MEAN_LATENCY=376989.12
STDDEV_LATENCY=184046.92
After patch :

RT_LATENCY,MIN_LATENCY,MAX_LATENCY,P50_LATENCY,P90_LATENCY,P99_LATENCY,MEAN_LATENCY,STDDEV_LATENCY
MIGRATED TCP REQUEST/RESPONSE TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET
to 7.7.7.84 () port 0 AF_INET : first burst 0 : cpu bind
RT_LATENCY=40545.492
MIN_LATENCY=9834
MAX_LATENCY=78366
P50_LATENCY=33583
P90_LATENCY=59000
P99_LATENCY=69000
MEAN_LATENCY=38364.67
STDDEV_LATENCY=12865.26

Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: David Miller <davem@davemloft.net>
Cc: Tom Herbert <therbert@google.com>
Cc: Ben Hutchings <bhutchings@solarflare.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
arm/crypto: Add optimized AES and SHA1 routines

Add assembler versions of AES and SHA1 for ARM platforms.  This has provided
up to a 50% improvement in IPsec/TCP throughout for tunnels using AES128/SHA1.

Platform   CPU SPeed    Endian   Before (bps)   After (bps)   Improvement

IXP425      533 MHz      big     11217042        15566294        ~38%
KS8695      166 MHz     little    3828549         5795373        ~51%

Signed-off-by: David McCullough <ucdevel@gmail.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
Revert "jiffies conversions: Use compile time constants when possible"

This reverts commit 690d8d78ee4e767917332ca6c3b690e0c642f034.
netfilter: nf_ct_sip: don't drop packets with offsets pointing outside the packet

Some Cisco phones create huge messages that are spread over multiple packets.
After calculating the offset of the SIP body, it is validated to be within
the packet and the packet is dropped otherwise. This breaks operation of
these phones. Since connection tracking is supposed to be passive, just let
those packets pass unmodified and untracked.

Signed-off-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

Conflicts:
	net/netfilter/nf_conntrack_sip.c

This commit appears in the 3.8 and 3.9 branches of the Linux kernel
and according to feanor3 on xda-developers:

The "Cisco Jabber" app lets you use your cell phone as a SIP
endpoint with your work number on a Cisco phone system. The
registration packets that Cisco uses are apparently larger
than normal. With your kernel, the registration does not complete.
With your kernel and line 1421 changed to NF_ACCEPT, the registration
complete
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
ondemand: cpuidle detection

I found a problem with the ondemand governor while in earlysuspend
suspend mode (ondemand keeping the freq close to the max at all times
despite near 0% load). The problem is that the cpu starts to go in
long cpuidle cycles, a sampling_rate of 10000 (usec) is applied only
once in a while and the real sampling_rate becomes 1 second (or more).

So when a wakeup happens we return to the 10000usec sampling rate. The
ondemand sees lots of activity after the wakeup but those "loads" must
be adjusted down if the previous wall_time delta was huge and the
current one is tiny. We're too close to long cpuidle to worry about
the cpu freq anyway and it may be just a jitter load that if we take
into account without adjusting it down, will lead to the next long
cpuidle to be entered at the max freq again, and this repeats forever.

So my solution is to tweak the ondemand to scale down the "load"
according to the decrease in the wall_time delta ratio
(deep_sleep_ratio variable). This allows the CPU to stay at the lowest
freq during the deep sleeps even when the ondemand governor is enabled
and the sampling_rate is set to 10000. (setting the sampling_rate to
values >100000 would also tend to hide the problem but it'd screw the
interactive behavior by running at the lowest frequency for too long
during interactive usage)

During interactive usage with the screen on (not in earlysuspend
mode), or during playback or voip with screen off the deep_sleep_rate
is set to 1 practically all the time so it won't alter the behavior of
the ondemand governor unless the system is very idle (and in turn when
we want it to stay at low freq).

Change-Id: If0391e6d6c41c1c8c9fa590502e88e681a800b04

Signed-off-by: Andrea Arcangeli <andrea@cpushare.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
hrtimer:__run_hrtimer races with enqueue_hrtimer We hit a kernel panic at __run_hrtimer=>BUG_ON(timer->state != HRTIMER_STATE_CALLBACK). <2>[ 10.226053, 3] kernel BUG at /home/android/xiaobing/ymz/r4/hardware/intel/linux-2.6/kernel/hrtimer.c:1228! <0>[ 10.235682, 3] invalid opcode: 0000 [#1] PREEMPT SMP <4>[ 10.240716, 3] Modules linked in: wl12xx_sdio wl12xx mac80211 cfg80211 compat btwilink rmi4(C) fmdrv_chr st_drv matrix(C) <4>[ 10.251651, 3] <4>[ 10.253391, 3] Pid: 68, comm: kworker/3:4 Tainted: G WC 3.0.34-140430-g2af538d #45 Intel Corporation CloverTrail/FFRD <4>[ 10.264674, 3] EIP: 0060:[<c126c7ed>] EFLAGS: 00010002 CPU: 3 <4>[ 10.270411, 3] EIP is at __run_hrtimer+0xbd/0x240 <4>[ 10.275091, 3] EAX: 00000001 EBX: f67fb6b8 ECX: f57b4000 EDX: 00007301 <4>[ 10.281602, 3] ESI: c1d614c0 EDI: f67fb680 EBP: f57b5dd8 ESP: f57b5da8 <4>[ 10.288113, 3] DS: 007b ES: 007b FS: 00d8 GS: 0000 SS: 0068 <0>[ 10.293754, 3] Process kworker/3:4 (pid: 68, ti=f57b4000 task=f57aa730 task.ti=f57b4000) <0>[ 10.301827, 3] Stack: <4>[ 10.304083, 3] 00000000 c1afef40 f57b5dd8 c167a6e0 f67fb680 20b366e3 f67fb6b8 f57b5e14 <4>[ 10.312069, 3] 00000001 f67fb6b8 00000001 f67fb680 f57b5e28 c126d1e5 f57b5e08 c126f325 <4>[ 10.320055, 3] 00000000 86b9868d 00000001 86b9868d 00000001 00000003 ffffffff 7fffffff <0>[ 10.328041, 3] Call Trace: <4>[ 10.330742, 3] [<c167a6e0>] ? gburst_thread_stop.isra.25+0x40/0x40 <4>[ 10.336988, 3] [<c126d1e5>] hrtimer_interrupt+0xd5/0x250 <4>[ 10.342368, 3] [<c126f325>] ? sched_clock_cpu+0xe5/0x150 <4>[ 10.347753, 3] [<c1871d44>] smp_apic_timer_interrupt+0x54/0x88 <4>[ 10.353654, 3] [<c1496558>] ? trace_hardirqs_off_thunk+0xc/0x14 <4>[ 10.359643, 3] [<c186be9f>] apic_timer_interrupt+0x2f/0x34 <4>[ 10.365199, 3] [<c186e60f>] ? sub_preempt_count+0x1f/0x50 <4>[ 10.370669, 3] [<c149558a>] delay_tsc+0x3a/0xc0 <6>[ 10.371589, 0] android_work: did not send uevent (0 0 (null)) <4>[ 10.381171, 3] [<c14954e3>] __const_udelay+0x23/0x30 <4>[ 10.386207, 3] [<c16d043a>] mdfld_dsi_send_dcs+0x12a/0x5d0 <4>[ 10.391760, 3] [<c186b6c6>] ? _raw_spin_unlock_irqrestore+0x26/0x50 <4>[ 10.398101, 3] [<c16af431>] ? ospm_power_using_hw_begin+0xa1/0x350 <4>[ 10.399053, 3] [<c186a49f>] ? __mutex_lock_slowpath+0x1ff/0x2f0 <4>[ 10.399069, 3] [<c16bd59e>] mdfld_dbi_update_panel+0x21e/0x2d0 <4>[ 10.399085, 3] [<c16b1ae1>] mdfld_te_handler_work+0x71/0x80 <4>[ 10.399099, 3] [<c12642be>] process_one_work+0xfe/0x3f0 <4>[ 10.399114, 3] [<c16b1a70>] ? mdfld_async_flip_te_handler+0xf0/0xf0

Basically, __run_hrtimer has a race with enqueue_hrtimer. When __run_hrtimer calls
the timer callback fn, another thread might call enqueue_hrtimer or hrtimer_start
to requeue it, and the timer->state is equal to HRTIMER_STATE_CALLBACK|HRTIMER_STATE_ENQUEUED,
which causes the BUG_ON(timer->state != HRTIMER_STATE_CALLBACK) checking fails.

The patch fixes it by checking only bit HRTIMER_STATE_CALLBACK.

Signed-off-by: Yanmin Zhang <yanmin.zhang@intel.com>
Reviewed-by: He, Bo <bo.he@intel.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
block: ioctl support for sanitize in eMMC 4.5

Adding a new ioctl to support sanitize operation in eMMC cards version 4.5.
The sanitize ioctl support helps performing this operation via user application.

Signed-off-by: Yaniv Gardi <ygardi@codeaurora.org>
Signed-off-by: Maya Erez <merez@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
block: make auto block plug flush threshold per-disk based

We do auto block plug flush to reduce latency, the threshold is 16 requests.
This works well if the task is accessing one or two drives.
The problem is if the task is accessing a raid 0 device and the raid disk number is big,
say 8 or 16, 16/8 = 2 or 16/16=1, we will have heavy lock contention.

This patch makes the threshold per-disk based. The latency should be
still ok accessing one or two drives. The setup with application
accessing a lot of drives in the meantime uaually is big machine,
avoiding lock contention is more important, because any contention
will actually increase latency.

Signed-off-by: Shaohua Li <shli@fusionio.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
Deadline i/o scheduler - added morfic's 1:1 secret sauce

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
deadline: Allow 0ms deadline latency, increase the read speed Change a timer compare from after to after-equals, thus allowing 0 timeout and making deadline schedule FIFO.

Signed-off-by: xiaobing tu <xiaobing.tu@intel.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
block: deadline: hardcode magic values from the usual suspects. Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
irq: Set CPU affinity as soon as the irq thread is created In an embedded target where IRQ affinities are pre-configured during boot-time (and not modified through /proc/irq/../smp_affinity) during run-time, the extra latency due to irq_thread_check_affinity can be avoided during processing of the first interrupt with this patch. Thoughts?

backported from Linux 3.5+ by faux123

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
procfs: add num_to_str() to speed up /proc/stat == stat_check.py num = 0 with open("/proc/stat") as f: while num < 1000 : data = f.read() f.seek(0, 0) num = num + 1 ==

perf shows

    20.39%  stat_check.py  [kernel.kallsyms]    [k] format_decode
    13.41%  stat_check.py  [kernel.kallsyms]    [k] number
    12.61%  stat_check.py  [kernel.kallsyms]    [k] vsnprintf
    10.85%  stat_check.py  [kernel.kallsyms]    [k] memcpy
     4.85%  stat_check.py  [kernel.kallsyms]    [k] radix_tree_lookup
     4.43%  stat_check.py  [kernel.kallsyms]    [k] seq_printf

This patch removes most of calls to vsnprintf() by adding num_to_str()
and seq_print_decimal_ull(), which prints decimal numbers without rich
functions provided by printf().

On my 8cpu box.
== Before patch ==
[root@bluextal test]# time ./stat_check.py

real    0m0.150s
user    0m0.026s
sys     0m0.121s

== After patch ==
[root@bluextal test]# time ./stat_check.py

real    0m0.055s
user    0m0.022s
sys     0m0.030s

[akpm@linux-foundation.org: remove incorrect comment, use less statck in num_to_str(), move comment from .h to .c, simplify seq_put_decimal_ull()]
[andrea@betterlinux.com: avoid breaking the ABI in /proc/stat]
Signed-off-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
Signed-off-by: Andrea Righi <andrea@betterlinux.com>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Glauber Costa <glommer@parallels.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Paul Turner <pjt@google.com>
Cc: Russell King <rmk@arm.linux.org.uk>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
backported from Linux 3.4-rc4 to Linux 3.0.x by faux123
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>