Backport AIO from Linux 3.6.x
aio: convert the ioctx list to radix tree

Date	Wed, 3 Apr 2013 16:20:48 +0300

When using a large number of threads performing AIO operations the
IOCTX list may get a significant number of entries which will cause
significant overhead. For example, when running this fio script:

rw=randrw; size=256k ;directory=/mnt/fio; ioengine=libaio; iodepth=1
blocksize=1024; numjobs=512; thread; loops=100

on an EXT2 filesystem mounted on top of a ramdisk we can observe up to
30% CPU time spent by lookup_ioctx:

 32.51%  [guest.kernel]  [g] lookup_ioctx
  9.19%  [guest.kernel]  [g] __lock_acquire.isra.28
  4.40%  [guest.kernel]  [g] lock_release
  4.19%  [guest.kernel]  [g] sched_clock_local
  3.86%  [guest.kernel]  [g] local_clock
  3.68%  [guest.kernel]  [g] native_sched_clock
  3.08%  [guest.kernel]  [g] sched_clock_cpu
  2.64%  [guest.kernel]  [g] lock_release_holdtime.part.11
  2.60%  [guest.kernel]  [g] memcpy
  2.33%  [guest.kernel]  [g] lock_acquired
  2.25%  [guest.kernel]  [g] lock_acquire
  1.84%  [guest.kernel]  [g] do_io_submit

This patchs converts the ioctx list to a radix tree. For a performance
comparison the above FIO script was run on a 2 sockets 8 core
machine. This are the results for the original list based
implementation and for the radix tree based implementation:

cores         1         2         4         8         16        32
list        111025 ms  62219 ms  34193 ms  22998 ms  19335 ms  15956 ms
radix        75400 ms  42668 ms  23923 ms  17206 ms  15820 ms  13295 ms
% of radix
relative      68%       69%       70%       75%       82%       83%
to list

To consider the impact of the patch on the typical case of having
only one ctx per process the following FIO script was run:

rw=randrw; size=100m ;directory=/mnt/fio; ioengine=libaio; iodepth=1
blocksize=1024; numjobs=1; thread; loops=100

on the same system and the results are the following:

list        65241 ms
radix       65402 ms
% of radix
relative    100.25%
to list

Cc: Andi Kleen <ak@linux.intel.com>

Signed-off-by: Octavian Purdila <octavian.purdila@intel.com>
modified for Mako hybrid from LKML

Signed-off-by: Paul Reioux <reioux@gmail.com>
ARM: 7805/1: mm: change max*pfn to include the physical offset of memory

Most of the kernel code assumes that max*pfn is maximum pfns because
the physical start of memory is expected to be PFN0. Since this
assumption is not true on ARM architectures, the meaning of max*pfn
is number of memory pages. This is done to keep drivers happy which
are making use of of these variable to calculate the dma bounce limit
using dma_mask.

Now since we have a architecture override possibility for DMAable
maximum pfns, lets make meaning of max*pfns as maximum pnfs on ARM
as well.

Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Will Deacon <will.deacon@arm.com>
Cc: Nicolas Pitre <nicolas.pitre@linaro.org>
Signed-off-by: Santosh Shilimkar <santosh.shilimkar@ti.com>
Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
slub.c: Remove Page allocation

This increase the performance because there won't be any COSTLY_ORDER

Improves performance by 3%.

Signed-off-by: Locasto <amperific@gmail.com>
cpuset: mm: reduce large amounts of memory barrier related damage v3

commit cc9a6c8776615f9c194ccf0b63a0aa5628235545 upstream.

Stable note:  Not tracked in Bugzilla. [get|put]_mems_allowed() is extremely
	expensive and severely impacted page allocator performance. This
	is part of a series of patches that reduce page allocator overhead.

Commit c0ff7453bb5c ("cpuset,mm: fix no node to alloc memory when
changing cpuset's mems") wins a super prize for the largest number of
memory barriers entered into fast paths for one commit.

[get|put]_mems_allowed is incredibly heavy with pairs of full memory
barriers inserted into a number of hot paths.  This was detected while
investigating at large page allocator slowdown introduced some time
after 2.6.32.  The largest portion of this overhead was shown by
oprofile to be at an mfence introduced by this commit into the page
allocator hot path.

For extra style points, the commit introduced the use of yield() in an
implementation of what looks like a spinning mutex.

This patch replaces the full memory barriers on both read and write
sides with a sequence counter with just read barriers on the fast path
side.  This is much cheaper on some architectures, including x86.  The
main bulk of the patch is the retry logic if the nodemask changes in a
manner that can cause a false failure.

While updating the nodemask, a check is made to see if a false failure
is a risk.  If it is, the sequence number gets bumped and parallel
allocators will briefly stall while the nodemask update takes place.

In a page fault test microbenchmark, oprofile samples from
__alloc_pages_nodemask went from 4.53% of all samples to 1.15%.  The
actual results were

                             3.3.0-rc3          3.3.0-rc3
                             rc3-vanilla        nobarrier-v2r1
    Clients   1 UserTime       0.07 (  0.00%)   0.08 (-14.19%)
    Clients   2 UserTime       0.07 (  0.00%)   0.07 (  2.72%)
    Clients   4 UserTime       0.08 (  0.00%)   0.07 (  3.29%)
    Clients   1 SysTime        0.70 (  0.00%)   0.65 (  6.65%)
    Clients   2 SysTime        0.85 (  0.00%)   0.82 (  3.65%)
    Clients   4 SysTime        1.41 (  0.00%)   1.41 (  0.32%)
    Clients   1 WallTime       0.77 (  0.00%)   0.74 (  4.19%)
    Clients   2 WallTime       0.47 (  0.00%)   0.45 (  3.73%)
    Clients   4 WallTime       0.38 (  0.00%)   0.37 (  1.58%)
    Clients   1 Flt/sec/cpu  497620.28 (  0.00%) 520294.53 (  4.56%)
    Clients   2 Flt/sec/cpu  414639.05 (  0.00%) 429882.01 (  3.68%)
    Clients   4 Flt/sec/cpu  257959.16 (  0.00%) 258761.48 (  0.31%)
    Clients   1 Flt/sec      495161.39 (  0.00%) 517292.87 (  4.47%)
    Clients   2 Flt/sec      820325.95 (  0.00%) 850289.77 (  3.65%)
    Clients   4 Flt/sec      1020068.93 (  0.00%) 1022674.06 (  0.26%)
    MMTests Statistics: duration
    Sys Time Running Test (seconds)             135.68    132.17
    User+Sys Time Running Test (seconds)         164.2    160.13
    Total Elapsed Time (seconds)                123.46    120.87

The overall improvement is small but the System CPU time is much
improved and roughly in correlation to what oprofile reported (these
performance figures are without profiling so skew is expected).  The
actual number of page faults is noticeably improved.

For benchmarks like kernel builds, the overall benefit is marginal but
the system CPU time is slightly reduced.

To test the actual bug the commit fixed I opened two terminals.  The
first ran within a cpuset and continually ran a small program that
faulted 100M of anonymous data.  In a second window, the nodemask of the
cpuset was continually randomised in a loop.

Without the commit, the program would fail every so often (usually
within 10 seconds) and obviously with the commit everything worked fine.
With this patch applied, it also worked fine so the fix should be
functionally equivalent.

Change-Id: Iee6899cd3ed28a491aee41845228e283a379ecbc
Signed-off-by: Mel Gorman <mgorman@suse.de>
Cc: Miao Xie <miaox@cn.fujitsu.com>
Cc: David Rientjes <rientjes@google.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Christoph Lameter <cl@linux.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Mel Gorman <mgorman@suse.de>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
arm: optimized current_pt_regs()

... no need to read current_thread_info()->task only to
feed it to task_thread_page() immediately afterwards.
Moreover, not using current_thread_info() at all ends
up with better assembler - we need a location very close
to the top of kernel stack page and it's actually better
to do or with 0x1fff, followed be subtracting a small
constant than and with ~0x1fff, followed by adding a large
one.  Both & and | would be a couple of insns (mvn lsr/mvn lsl
for |, a pair of bic for &), but the following addition
would cost a pair of add while the subtraction ends up
as a single sub.

Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
 block: Disable IO Stat and Add Random

These functions don't really do much so let's get rid of them.

Signed-off-by: Chet Kener <Cl3Kener@gmail.com>

Conflicts:
	arch/arm/boot/zImage
Add zzmove governor

Conflicts:
	drivers/cpufreq/Kconfig
	drivers/cpufreq/Makefile
	include/linux/cpufreq.h
Update zzmoove governor to 0.4
credits to mialwe and ktoonsez
cpufreq: zzmoove governor v0.5

Changelog:

- completely reworked fast scaling functionality. now using a 'line jump' logic instead of fixed freq 'colums'.
  fast scaling now in 4 steps and 2 modes possible (mode 1: only fast scaling up and mode2: fast scaling up/down)
- added support for 'Dynamic Screen Frequency Scaling' (original implementation into zzmoove governor highly improved by Yank555)
  originated by AndreiLux more info: http://forum.xda-developers.com/showpost.php?p=38499071&postcount=3
- re-enabled broken conservative sampling down factor functionality ('down skip' method).
  originated by Stratosk - upstream kernel 3.10rc1:
  https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/log/?id=refs%2Ftags%2Fv3.10-rc1&qt=author&q=Stratos+Ka
- changed down threshold check to act like it should.
  originated by Stratosk - upstream kernel 3.10rc1:
  https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/log/?id=refs%2Ftags%2Fv3.10-rc1&qt=author&q=Stratos+Ka
- implemented/ported 'early demand' from ondemand governor.
  originated by Stratosk - more info: http://www.semaphore.gr/80-latests/98-ondemand-early-demand
- implemented/ported 'sampling down momentum' from ondemand governor.
  originated by Stratosk - more info: http://www.semaphore.gr/80-latests/80-sampling-down-momentum
- modified some original conservative code parts regarding frequency scaling which should work better now.
  originated by DerTeufel1980: https://github.com/DerTeufel/android_kernel_samsung_smdk4412/commit/6bab622344c548be853db19adf28c3917896f0a0
- added the possibility to use sampling down momentum or conservative 'down skip' method.
- increased possible max sampling rate sleep multiplier to 4 and sampling down factor to 100000
  accordingly to sampling down momentum implementation.
- added frequency search limit for more efficient frequency searching in scaling 'table' and for improving
  frequency 'hard' and 'soft' limit handling.
- added cpu idle exit time handling like it is in lulzactive
  again work from ktoonsez : https://github.com/ktoonsez/KT747-JB/commit/a5931bee6ea9e69f386a340229745da6f2443b78
  description in lulzactive governor:
  https://github.com/ktoonsez/KT747-JB/blob/a5931bee6ea9e69f386a340229745da6f2443b78/drivers/cpufreq/cpufreq_lulzactive.c
- fixed a little scaling step mistake and added overclocking frequencies up to 1800 mhz in scaling frequency 'tables'.
- fixed possible freezes during start/stop/reload of governor and frequency limit change.
- fixed hotplugging logic at online core 0+3 or 0+2 situations and improved hotplugging in general by
  removing mutex locks and skipping hotplugging when it is not needed.
- added possibility to disable hotplugging (that's a debugging relict but i thought maybe someone will find that usefull so i didn't remove it)
- try to fix lags when coming from suspend if hotplug limitation at sleep was active by enabling all offline cores during resume.
- code cleaning and documentation.

Signed-off-by: ZaneZam <cyxman@yahoo.com>

Conflicts:

	drivers/cpufreq/cpufreq_zzmoove.c
cpufreq: zzmoove governor v0.5.1b

Changelog:

- highly optimised scaling logic (thx and credits to Yank555)
- simplified some tuneables by using already available stuff instead of using redundant code (thx Yank555)
- reduced/optimised hotplug logic and preperation for automatic detection of available cores
  (maybe this fixes also the scaling/core stuck problems)
- finally fixed the freezing issue on governor stop!

Conflicts:

	drivers/cpufreq/cpufreq_zzmoove.c
zzmoove 0.6 - flexibility (in cooperation with Yank555)
Changelog:

       - removed fixed scaling lookup tables and use the system frequency table instead
         changed scaling logic accordingly for this modification (thx and credits to Yank555)
       - reduced new hotplug logic loop to a minimum
       - again try to fix stuck issues by using seperate hotplug functions out of dbs_check_cpu (credits to ktoonesz)
       - added support for 2 and 8 core systems and added automatic detection of cores were it is needed
         (for setting the different core modes you can use the macro 'MAX_CORES'. possible values are: 2,4 or 8, default are 4 cores)
         reduced core threshold defaults to only one up/down default and use an array to hold all threshold values
       - fixed some mistakes in 'frequency tuneables' (Yank555):
         stop looping once the frequency has been found
         return invalid error if new frequency is not found in the frequency table
Version 0.6a - scaling logic felxibility (in cooperation with Yank555)
Changelog:

  - added check if CPU freq. table is in ascending or descending order and scale accordingly
    (compatibility for systems with 'inverted' frequency table like it is on OMAP4 platform)
    thanks and credits to Yank555
drivers/cpufreq: update Zzmoove to v0.8

Conflicts:
	drivers/cpufreq/cpufreq_zzmoove.c
cpufreq: zzmoove v0.8 - fix settings for yank profiles
drivers/cpufreq: Zzmoove v0.9_beta1
cpufreq: Update to zzmoove 0.9-beta3

credits to ZaneZam

Conflicts:
	drivers/cpufreq/cpufreq_zzmoove.c
netfilter: no-loop-parallelize-all in CFLAGS (Linaro Optimisations build fix)

Applied for:
netfilter/nf_conntrack_core.o
netfilter/xt_hashlimit.o
netfilter/ipset/ip_set_hash_ipportip.o
netfilter/ipset/ip_set_hash_ipportnet.o
bitops.h: define set_mask_bits
Revert "ARM: smp: Save CPU registers before IPI_CPU_STOP processing (faux123)"

This reverts commit e61138540ffd280216821e20b7f2bdd88e5addf0.