epoll: optimize EPOLL_CTL_DEL using rcu

Date	Tue, 1 Oct 2013 17:08:10 +0000 (GMT)

Optimize EPOLL_CTL_DEL such that it does not require the 'epmutex' by
converting the file->f_ep_links list into an rcu one. In this way, we can
traverse the epoll network on the add path in parallel with deletes. Since
deletes can't create loops or worse wakeup paths, this is safe.

This patch in combination with the patch "epoll: Do not take global 'epmutex'
for simple topologies", shows a dramatic performance improvement in
scalability for SPECjbb.

Tested-by: Nathan Zimmer <nzimmer@sgi.com>
Signed-off-by: Jason Baron <jbaron@akamai.com>

backported for Linux 3.4 for use on Android
Signed-off-by: Paul Reioux <reioux@gmail.com>
epoll: Do not take global 'epmutex' for simple topologies

Date	Tue, 1 Oct 2013 17:08:14 +0000 (GMT)

When calling EPOLL_CTL_ADD for an epoll file descriptor that is attached
directly to a wakeup source, we do not need to take the global 'epmutex',
unless the epoll file descriptor is nested. The purpose of taking
the 'epmutex' on add is to prevent complex topologies such as loops and
deep wakeup paths from forming in parallel through multiple EPOLL_CTL_ADD
operations. However, for the simple case of an epoll file descriptor
attached directly to a wakeup source (with no nesting), we do not need
to hold the 'epmutex'.

This patch along with 'epoll: optimize EPOLL_CTL_DEL using rcu' improves
scalability on larger systems. Quoting Nathan Zimmer's mail on SPECjbb
performance:

"
On the 16 socket run the performance went from 35k jOPS to 125k jOPS.
In addition the benchmark when from scaling well on 10 sockets to scaling well
on just over 40 sockets.

...

Currently the benchmark stops scaling at around 40-44 sockets but it seems like
I found a second unrelated bottleneck.
"

Tested-by: Nathan Zimmer <nzimmer@sgi.com>
Signed-off-by: Jason Baron <jbaron@akamai.com>

backported to Linux 3.4 for use on Android
Signed-off-by: Paul Reioux <reioux@gmail.com>
epoll: do not take globals epmutex for simple topologies fix

- use `bool' for boolean variables
- remove unneeded/undesirable cast of void*
- add missed ep_scan_ready_list() kerneldoc

Cc: "Paul E. McKenney" <paulmck@us.ibm.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Davide Libenzi <davidel@xmailserver.org>
Cc: Eric Wong <normalperson@yhbt.net>
Cc: Jason Baron <jbaron@akamai.com>
Cc: Nathan Zimmer <nzimmer@sgi.com>
Cc: Nelson Elhage <nelhage@nelhage.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>
hrtimer: Introduce effective timer slack

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>
Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
hrtimer: Implement PR_GET_EFFECTIVE_TIMERSLACK

PR_GET_EFFECTIVE_TIMERSLACK allows process to know its effective timer
slack value.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>

Conflicts:
	include/linux/prctl.h
cgroups: Introduce timer slack controller

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>
Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>

Conflicts:
	include/linux/cgroup_subsys.h
kernel: cgroup_timer_slack: Adaptations for 3.4 kernel

Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
kernel: cgroup_timer_slack: Dynamic management of timer slack

This feature allows to use different minimal timer slack values and to
dynamically manage them when the system has been resumed (it's active)
or when has been suspended.

A new file is provided in addition to the two files provided by the
original timer slack controller:
- "timer_slack.min_slack_suspend_ns" is the minimal timer slack value
  to use when the system is suspended (screen off)

For further info, please refers to the timer slack documentation:
Documentation/cgroupd/timer_slack.txt

Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
kernel: cgroup_timer_slack: Dynamic management change to powersuspend
Add Snappy compression library (v5)

Google's Snappy data compression library is a faster alternative to LZO,
optimized for x86-64. On compressible input it compresses ~2.5x faster than LZO
and decompresses ~1.5-2x faster than LZO. On incompressible input, it skips the
input at 100x faster than LZO and decompresses ~4x faster than LZO.
It is released under BSD license.
This is a kernel port from user space C++ code..
ZSWAP remove crypto dependenciy and change to snappy
Add the snappy-c compressor to lib v2

This is a C port of the google snappy compressor. It has roughly
comparable compression to LZO, but is significantly faster on many file
types. For example it beats all other compressors on already
compressed data.

I ported the original C++ code over to C and did some changes
to make it better fit into the kernel. It preallocates the worst
case memory consumption now. While the code being larger
than lzo it is still reasonable (about 5K on x86).

Decompression needs very little memory, Compression
currently 192K on 64bit and 128K on 32bit. For comparison
LZO compression needs 128K on 64bit and 64K on 32bit.

[This could be lowered significantly by not preallocating
for most use cases, typically the footprint is much lower.
The original C++ version only allocated most of this
when (rarely) needed, but this is more problematic in the kernel]

There are some minor divergences from the Linux coding standards:
in particular I kept the C++/C99 style mixed statement/declarations.
This was mainly to not diverge too much from the reference C++
source, so that improvements from there can be easily ported.
There are some other left overs from the google style, but very
little now.

Performance:

The compressor performs best on 64bit-LE systems,
but is also quite good on 32bit. I haven't tested BE, but
I don't expect that to add a lot of overhead.

Here is some performance data (32bit, Nehalem):
c/b = cycles/byte; lower numbers are better.

x86-64 executable: (compression minimally slower than qlz, but
much better at decompression, lzo is left in the dust):

snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 8.13 uncomp 2.65 c/b
lzo   : emacs-gtk: 11007968 b: ratio 0.33: comp 12.74 uncomp 4.70 c/b
zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 49.96 uncomp 13.14 c/b
zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 64.17 uncomp 12.33 c/b
lzf   : emacs-gtk: 11007968 b: ratio 0.37: comp 9.85 uncomp 4.33 c/b
qlz   : emacs-gtk: 11007968 b: ratio 0.34: comp 7.51 uncomp 6.28 c/b
fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 10.73 uncomp 4.97 c/b

Compressed data (beats everything else):

snappy: udev-151.tar.gz: 634842 b: ratio 1.00: comp 0.99 uncomp 0.33 c/b
lzo   : udev-151.tar.gz: 634842 b: ratio 1.00: comp 41.44 uncomp 0.66 c/b
zlib1 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 116.99 uncomp 3.94 c/b
zlib3 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 117.68 uncomp 3.94 c/b
lzf   : udev-151.tar.gz: 634842 b: ratio 1.03: comp 16.32 uncomp 1.14 c/b
qlz   : udev-151.tar.gz: 634842 b: ratio 1.00: comp 10.42 uncomp 0.42 c/b
fastlz: udev-151.tar.gz: 634842 b: ratio 1.03: comp 19.35 uncomp 2.07 c/b

Text file (compression somewhat slower than qlz, but decompression
much better, lzo is much worse):

snappy: manual.txt: 445343 b: ratio 0.47: comp 12.01 uncomp 3.12 c/b
lzo   : manual.txt: 445343 b: ratio 0.44: comp 16.32 uncomp 7.53 c/b
zlib1 : manual.txt: 445343 b: ratio 0.35: comp 56.37 uncomp 15.59 c/b
zlib3 : manual.txt: 445343 b: ratio 0.31: comp 73.45 uncomp 13.99 c/b
lzf   : manual.txt: 445343 b: ratio 0.46: comp 13.43 uncomp 5.47 c/b
qlz   : manual.txt: 445343 b: ratio 0.44: comp 9.16 uncomp 8.19 c/b
fastlz: manual.txt: 445343 b: ratio 0.46: comp 14.22 uncomp 7.28 c/b

As you can see snappy is a good all-around compressor.

On 64bit the compression is even faster and beats everything else easily:

snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 4.90 uncomp 2.65 c/b
lzo   : emacs-gtk: 11007968 b: ratio 0.33: comp 11.24 uncomp 4.46 c/b
zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 41.67 uncomp 11.13 c/b
zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 51.80 uncomp 10.54 c/b
lzf   : emacs-gtk: 11007968 b: ratio 0.37: comp 8.79 uncomp 4.05 c/b
qlz   : emacs-gtk: 11007968 b: ratio 0.34: comp 5.44 uncomp 5.46 c/b
fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 9.91 uncomp 4.77 c/b

On 64bit it's now nearly as fast as qlz on the text file too:

snappy: manual.txt: 445343 b: ratio 0.47: comp 7.79 uncomp 3.47 c/b
lzo   : manual.txt: 445343 b: ratio 0.44: comp 15.46 uncomp 7.27 c/b
zlib1 : manual.txt: 445343 b: ratio 0.35: comp 45.79 uncomp 12.78 c/b
zlib3 : manual.txt: 445343 b: ratio 0.31: comp 60.52 uncomp 11.72 c/b
lzf   : manual.txt: 445343 b: ratio 0.46: comp 12.62 uncomp 5.30 c/b
qlz   : manual.txt: 445343 b: ratio 0.44: comp 6.81 uncomp 7.65 c/b
fastlz: manual.txt: 445343 b: ratio 0.46: comp 13.75 uncomp 6.52 c/b

Overall it's a good alternative to lzo, with the only
drawback being the somewhat higher memory use.

v2: Some minor performance improvements and cleanups.
32bit compression should be a few percent faster now.
Signed-off-by: Andi Kleen <ak@linux.intel.com>

Conflicts:
	lib/Kconfig
	lib/Makefile
Add snappy interface to crypto API

Mainly so that ubifs can use it.

Cc: herbert@gondor.apana.org.au
Signed-off-by: Andi Kleen <ak@linux.intel.com>

Conflicts:
	crypto/Kconfig
	crypto/Makefile
Update to latest snappy-c

- Several performance improvements from snappy reference
- Fix a build failure on x86
- Fix a 32bit performance issue
- Run through unifdef
lib: Update Snappy-C to version 1.1.0 and misc
[PATCH 1/3] Rename ARM assembler push/pull macros

The ARM assembler library functions use a macro called "push" that
along with a macro called "pull" is used to shift bytes around in a
word in an endian-independent way. However, the modern unified
ARM assembler syntax also defines the instruction "push" to push
data onto the stack, which has specific encodings in the Thumb2
instruction set. For prevent possible conflicts going forward, and
to allow the use of the more transparent "push" instruction along
with the modern unified assembler syntax, this patch renames all
occurrences of the "push" macro to "pushbits", as well as renaming
the macro argument, when also called "push", to "pushshift".

For consistency, the macro called "pull" with its argument name
"pull" are also renamed to "pullbits" and "pullshift", respectively.

Signed-off-by: Harm Hanemaaijer <fgenfb@yahoo.com>
[PATCH 2/3] Optimize copy_page for modern ARM platforms

The existing implementation of copy_page for ARM appears to be
optimized for older platforms. Benchmark testing in a sandbox
environment shows suboptimal performance on modern platforms
like armv6 and armv7, with speed-ups ranging from 10% (Cortex A8)
to 80% (armv6 used in Raspberry Pi) being achievable.

This commit optimizes copy_page and introduces the new compile-time
constant PREFETCH_DISTANCE, defined in cache.h, which when
multiplied by L1_CACHE_BYTES is equal to the offset used for
prefetches performed with the PLD instruction. For platforms where
L1_CACHE_BYTES is 32 (armv5 and armv6), copy_page processes 32 bytes
at a time while doing one prefetch per iteration, while for armv7
(with L1_CACHE_BYTES equal to 64), 64 bytes are processed at at time
with one prefetch per iteration. When no preload instruction is
available (platforms earlier than armv5), no preload instructions
are generated and 32 bytes are processed at at time.

To facilitate specifying instructions for architectures with no
preload instruction, the NO_PLD macro is added to assembler.h,
augmenting the PLD macro.

Signed-off-by: Harm Hanemaaijer <fgenfb@yahoo.com>
[PATCH 3/3] Optimize ARM memset and memzero functions

The ARM memset and memzero functions are optimized with lower overhead
for small requests, generation of more 16-bit Thumb2 instructions when
compiled in Thumb2 mode, and configurable destination alignment before
the main block-copying loop.

The new compile-time constant MEMSET_WRITE_ALIGN_BYTES is introduced
in assembler.h, to augment the CALGN macro that previously regulated
32-byte write alignment but was only used on the Feroceon platform.
MEMSET_WRITE_ALIGN_BYTES can have values of 0 (no write alignment),
8, or 32. Apart from Feroceon, memset write alignment of 32 bytes
appears to benefit the armv6 platform, while the armv7 platform
seems benefit from alignment to 8 bytes for memset/memzero.

The CALGN macro is renamed to MEMSET_CALGN for memset and memzero; the
original CALGN macro is reserved for the memcpy family of functions
(memcpy, copy_from_user, copy_to_user) currently implemented in
copy_template.S, and the associated compile time constant
WRITE_ALIGN_BYTES defines the write alignment for memcpy-related
functions that will be utilized in subsequent contributions. Because
the current CALGN implementation in copy_template.S only implements
32-byte write alignment and is broken on Thumb2, it is only enabled
when WRITE_ALIGN_BYTES is equal to 32 and Thumb2 mode is not enabled.

Finally, memset and memzero now include a directive to enable unified
ARM assembler syntax.

Signed-off-by: Harm Hanemaaijer <fgenfb@yahoo.com>
Revert "[PATCH 1/3] Rename ARM assembler push/pull macros"

This reverts commit 30c1729487385fb13ca00a1fa5b9dc9a7446e271.
Revert "[PATCH 3/3] Optimize ARM memset and memzero functions"

This reverts commit fbc1268efd3869977303fb3f32e645572ec393eb.