ARM: spinlock: use ticket algorithm for ARMv6+ locking implementation

Ticket spinlocks ensure locking fairness by reducing the thundering herd
effect when acquiring a lock. This is especially important on systems
where memory-access times are not necessarily uniform when accessing
the lock structure (for example, on a multi-cluster platform where the
lock is allocated into L1 when a CPU releases it).

This patch implements the ticket spinlock algorithm for ARM, replacing
the simpler implementation for ARMv6+ processors.

Cc: Nicolas Pitre <nico at fluxnic.net>
Signed-off-by: Will Deacon <will.deacon at arm.com>
ARM: rwlocks: remove unused branch labels from trylock routines

The ARM arch_{read,write}_trylock implementations include unused
backwards branch labels, since we don't retry the locking operation
if the exclusive store fails.

This patch removes the labels.

Signed-off-by: Will Deacon <will.deacon at arm.com>
ARM: cacheflush: don't round address range up to nearest page

The flush_cache_user_range macro takes a pair of addresses describing
the start and end of the virtual address range to flush. Due to an
accidental oversight when flush_cache_range_user was introduced, the
address range was rounded up so that the start and end addresses were
page-aligned.

For historical reference, the interesting commits in history.git are:

10eacf1775e1 ("[ARM] Clean up ARM cache handling interfaces (part 1)")
71432e79b76b ("[ARM] Add flush_cache_user_page() for sys_cacheflush()")

This patch removes the alignment code, reducing the amount of flushing
required for ranges that are not an exact multiple of PAGE_SIZE.

Reported-by: Jonathan Austin <jonathan.austin at arm.com>
Signed-off-by: Will Deacon <will.deacon at arm.com>
ARM: cacheflush: don't bother rounding to nearest vma

do_cache_op finds the lowest VMA contained in the specified address
range and rounds the range to cover only the mapped addresses.

Since commit 4542b6a0fa6b ("ARM: 7365/1: drop unused parameter from
flush_cache_user_range") the VMA is not used for anything else in this
code and seeing as the low-level cache flushing routines return -EFAULT
if the address is not valid, there is no need for this range truncation.

This patch removes the VMA handling code from the cacheflushing syscall.

Signed-off-by: Will Deacon <will.deacon at arm.com>
ARM: cacheflush: add new iovec-based cache flushing system call

The cacheflush system call flushes a contiguous range, specified by a
pair of addresses. This means that user applications wishing to flush
discrete ranges must issue multiple system calls, since attempting to
flush past a vma results in range truncation.

This patch introduces a new private system call for ARM, cacheflush_iov,
which processes a range of addresses described in an iovec structure.

Signed-off-by: Will Deacon <will.deacon at arm.com>
ARM: cache: detect PIPT I-cache using CTR

The Cache Type Register L1Ip field identifies I-caches with a PIPT
policy using the encoding 11b.

This patch extends the cache policy parsing to identify PIPT I-caches
correctly and prevent them from being treated as VIPT aliasing in cases
where they are sufficiently large.

Signed-off-by: Will Deacon <will.deacon at arm.com>
Signed-off-by: Willi Ye <williye97@gmail.com>

Conflicts:
	arch/arm/kernel/setup.c
Fix build errors
mm, vmalloc: use well-defined find_last_bit() func

Our intention in here is to find last_bit within the region to flush.
There is well-defined function, find_last_bit() for this purpose and
it's performance may be slightly better than current implementation.
So change it.

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
mm/vmalloc: use wrapper function get_vm_area_size to caculate size of vm area

Use wrapper function get_vm_area_size to calculate size of vm area.

Signed-off-by: Wanpeng Li <liwanp@linux.vnet.ibm.com>
Fix build error
sched: smart wake-affine foundation

wake-affine stuff is always trying to pull wakee close to waker, by theory,
this will bring benefit if waker's cpu cached hot data for wakee, or the
extreme ping-pong case.

And testing show it could benefit hackbench 15% at most.

However, the whole stuff is somewhat blindly and time-consuming, some
workload therefore suffer.

And testing show it could damage pgbench 50% at most.

Thus, wake-affine stuff should be more smart, and realise when to stop
it's thankless effort.

This patch introduced 'nr_wakee_switch', which will be increased each
time the task switch it's wakee.

So a high 'nr_wakee_switch' means the task has more than one wakee, and
bigger the number, higher the wakeup frequency.

Now when making the decision on whether to pull or not, pay attention on
the wakee with a high 'nr_wakee_switch', pull such task may benefit wakee,
but also imply that waker will face cruel competition later, it could be
very cruel or very fast depends on the story behind 'nr_wakee_switch',
whatever, waker therefore suffer.

Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
tasks rely on it, then waker's higher latency will damage all of them, pull
wakee seems to be a bad deal.

Thus, when 'waker->nr_wakee_switch / wakee->nr_wakee_switch' become higher
and higher, the deal seems to be worse and worse.

The patch therefore help wake-affine stuff to stop it's work when:

	wakee->nr_wakee_switch > factor &&
	waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)
The factor here is the node-size of current-cpu, so bigger node will lead
to more pull since the trial become more severe.

After applied the patch, pgbench show 40% improvement at most.

Test:
	Tested with 12 cpu X86 server and tip 3.10.0-rc7.

	pgbench		    base	smart

	| db_size | clients |  tps  |	|  tps  |
	+---------+---------+-------+   +-------+
	| 22 MB   |       1 | 10598 |   | 10796 |
	| 22 MB   |       2 | 21257 |   | 21336 |
	| 22 MB   |       4 | 41386 |   | 41622 |
	| 22 MB   |       8 | 51253 |   | 57932 |
	| 22 MB   |      12 | 48570 |   | 54000 |
	| 22 MB   |      16 | 46748 |   | 55982 | +19.75%
	| 22 MB   |      24 | 44346 |   | 55847 | +25.93%
	| 22 MB   |      32 | 43460 |   | 54614 | +25.66%
	| 7484 MB |       1 |  8951 |   |  9193 |
	| 7484 MB |       2 | 19233 |   | 19240 |
	| 7484 MB |       4 | 37239 |   | 37302 |
	| 7484 MB |       8 | 46087 |   | 50018 |
	| 7484 MB |      12 | 42054 |   | 48763 |
	| 7484 MB |      16 | 40765 |   | 51633 | +26.66%
	| 7484 MB |      24 | 37651 |   | 52377 | +39.11%
	| 7484 MB |      32 | 37056 |   | 51108 | +37.92%
	| 15 GB   |       1 |  8845 |   |  9104 |
	| 15 GB   |       2 | 19094 |   | 19162 |
	| 15 GB   |       4 | 36979 |   | 36983 |
	| 15 GB   |       8 | 46087 |   | 49977 |
	| 15 GB   |      12 | 41901 |   | 48591 |
	| 15 GB   |      16 | 40147 |   | 50651 | +26.16%
	| 15 GB   |      24 | 37250 |   | 52365 | +40.58%
	| 15 GB   |      32 | 36470 |   | 50015 | +37.14%
CC: Ingo Molnar <mingo@kernel.org>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Mike Galbraith <efault@gmx.de>
Signed-off-by: Michael Wang <wangyun@linux.vnet.ibm.com>
sched: reduce the overhead of obtain factor

Smart wake-affine is using node-size as the factor, but the overhead of
mask operation is high.

Thus, this patch introduce the 'sd_llc_size', which will record the highest
cache-share domain size, and make it to be the new factor, in order to
reduce the overhead and make more reasonable.

And we suppose it will benefit a lot when facing a huge platform.

Test:
	Tested with 12 cpu X86 server and tip 3.10.0-rc7.

	pgbench		    base	smart + optimization

	| db_size | clients |  tps  |	|  tps  |
	+---------+---------+-------+   +-------+
	| 22 MB   |       1 | 10598 |   | 10781 |
	| 22 MB   |       2 | 21257 |   | 21328 |
	| 22 MB   |       4 | 41386 |   | 41622 |
	| 22 MB   |       8 | 51253 |   | 60351 |
	| 22 MB   |      12 | 48570 |   | 54255 |
	| 22 MB   |      16 | 46748 |   | 55534 | +18.79%
	| 22 MB   |      24 | 44346 |   | 55976 | +26.23%
	| 22 MB   |      32 | 43460 |   | 55279 | +27.20%
	| 7484 MB |       1 |  8951 |   |  9054 |
	| 7484 MB |       2 | 19233 |   | 19252 |
	| 7484 MB |       4 | 37239 |   | 37354 |
	| 7484 MB |       8 | 46087 |   | 51218 |
	| 7484 MB |      12 | 42054 |   | 49510 |
	| 7484 MB |      16 | 40765 |   | 52151 | +27.93%
	| 7484 MB |      24 | 37651 |   | 52720 | +40.02%
	| 7484 MB |      32 | 37056 |   | 51094 | +37.88%
	| 15 GB   |       1 |  8845 |   |  9139 |
	| 15 GB   |       2 | 19094 |   | 19379 |
	| 15 GB   |       4 | 36979 |   | 37077 |
	| 15 GB   |       8 | 46087 |   | 50490 |
	| 15 GB   |      12 | 41901 |   | 48235 |
	| 15 GB   |      16 | 40147 |   | 51878 | +29.22%
	| 15 GB   |      24 | 37250 |   | 52676 | +41.41%
	| 15 GB   |      32 | 36470 |   | 50198 | +37.64%
CC: Ingo Molnar <mingo@kernel.org>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Mike Galbraith <efault@gmx.de>
Signed-off-by: Michael Wang <wangyun@linux.vnet.ibm.com>