ARM: 7173/1: Add optimised swahb32() byteswap helper for v6 and above

ARMv6 and later processors have the REV16 instruction, which swaps
the bytes within each halfword of a register value.

This is already used to implement swab16(), but since the native
operation performaed by REV16 is actually swahb32(), this patch
renames the existing swab16() helper accordingly and defines
__arch_swab16() in terms of it.  This allows calls to both swab16()
and swahb32() to be optimised.

The compiler's generated code might improve someday, but as of
4.5.2 the code generated for pure C implementing these 16-bit
bytesswaps remains pessimal.

swahb32() is useful for converting 32-bit Thumb instructions
between integer and memory representation on BE8 platforms (among
other uses).

Signed-off-by: Dave Martin <dave.martin@linaro.org>
Reviewed-by: Nicolas Pitre <nico@linaro.org>
Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
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.

Signed-off-by: Will Deacon <will.deacon@arm.com>
ARM: Don't enable GENERIC_LOCKBREAK with ticket spinlocks

Now that ARM has implemented its spinlocks with tickets we don't
need to use the generic lockbreak algorithm. Remove the Kconfig
from ARM so that we use the arch_spin_is_contended() definition
from the asm header. This also saves a word in each lock because
we don't need the break_lock member anymore.

Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
Acked-by: Will Deacon <will.deacon@arm.com>
Proportional Rate Reduction for TCP.

This patch implements Proportional Rate Reduction (PRR) for TCP.
PRR is an algorithm that determines TCP's sending rate in fast
recovery. PRR avoids excessive window reductions and aims for
the actual congestion window size at the end of recovery to be as
close as possible to the window determined by the congestion control
algorithm. PRR also improves accuracy of the amount of data sent
during loss recovery.

The patch implements the recommended flavor of PRR called PRR-SSRB
(Proportional rate reduction with slow start reduction bound) and
replaces the existing rate halving algorithm. PRR improves upon the
existing Linux fast recovery under a number of conditions including:
  1) burst losses where the losses implicitly reduce the amount of
outstanding data (pipe) below the ssthresh value selected by the
congestion control algorithm and,
  2) losses near the end of short flows where application runs out of
data to send.

As an example, with the existing rate halving implementation a single
loss event can cause a connection carrying short Web transactions to
go into the slow start mode after the recovery. This is because during
recovery Linux pulls the congestion window down to packets_in_flight+1
on every ACK. A short Web response often runs out of new data to send
and its pipe reduces to zero by the end of recovery when all its packets
are drained from the network. Subsequent HTTP responses using the same
connection will have to slow start to raise cwnd to ssthresh. PRR on
the other hand aims for the cwnd to be as close as possible to ssthresh
by the end of recovery.

A description of PRR and a discussion of its performance can be found at
the following links:
- IETF Draft:
    http://tools.ietf.org/html/draft-mathis-tcpm-proportional-rate-reduction-01
- IETF Slides:
    http://www.ietf.org/proceedings/80/slides/tcpm-6.pdf
    http://tools.ietf.org/agenda/81/slides/tcpm-2.pdf
- Paper to appear in Internet Measurements Conference (IMC) 2011:
    Improving TCP Loss Recovery
    Nandita Dukkipati, Matt Mathis, Yuchung Cheng

Signed-off-by: Nandita Dukkipati <nanditad@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
timer: optimize apply_slack()

__fls(mask) is equivalent to find_last_bit(&mask, BITS_PER_LONG), but cheaper.
find_last_bit was showing up high on the list when I was profiling for stalls
on icache misses on a system with very small cache size (MIPS).

Signed-off-by: Felix Fietkau <nbd@openwrt.org>
binfmt_elf.c: use get_random_int() to fix entropy depleting

Hello,

The problems have been fixed in this version as per Kees's comments for v3.

Hi Kees,
Would you please ACK this patch if you think it is ok except the strength
of these various RNGs you are concerned?

Changes:
--------
v4->v3:
- s/random_stack_user()/get_atrandom_bytes()/
- Move this function to ahead of its use to avoid the predeclaration.

v3->v2:
- Tweak code comments of random_stack_user().
- Remove redundant bits mask and shift upon the random variable.

v2->v1:
- Fix random copy to check up buffer length that are not 4-byte multiples.

v3 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59597.html
v2 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59418.html
v1 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59128.html

Thanks,
-Jeff

Entropy is quickly depleted under normal operations like ls(1), cat(1),
etc...  between 2.6.30 to current mainline, for instance:

$ cat /proc/sys/kernel/random/entropy_avail
3428
$ cat /proc/sys/kernel/random/entropy_avail
2911
$cat /proc/sys/kernel/random/entropy_avail
2620

We observed this problem has been occurring since 2.6.30 with
fs/binfmt_elf.c: create_elf_tables()->get_random_bytes(), introduced by
f06295b44c296c8f ("ELF: implement AT_RANDOM for glibc PRNG seeding").

/*
 * Generate 16 random bytes for userspace PRNG seeding.
 */
get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));

The patch introduces a wrapper around get_random_int() which has lower
overhead than calling get_random_bytes() directly.

With this patch applied:
$ cat /proc/sys/kernel/random/entropy_avail
2731
$ cat /proc/sys/kernel/random/entropy_avail
2802
$ cat /proc/sys/kernel/random/entropy_avail
2878

Analyzed by John Sobecki.

Signed-off-by: Jie Liu <jeff.liu@oracle.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Andreas Dilger <aedilger@gmail.com>
Cc: Alan Cox <alan@linux.intel.com>
Cc: Arnd Bergmann <arnn@arndb.de>
Cc: John Sobecki <john.sobecki@oracle.com>
Cc: James Morris <james.l.morris@oracle.com>
Cc: Jakub Jelinek <jakub@redhat.com>
Cc: Ted Ts'o <tytso@mit.edu>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Kees Cook <keescook@chromium.org>
Cc: Ulrich Drepper <drepper@redhat.com>
Acked-by: Kees Cook <keescook@chromium.org>
Modify arch/arm's Makefile with compiler flags.

*I'm unsure if this does something that the root Makefile doesn't but just in case...