word-at-a-time: make the interfaces truly generic

This changes the interfaces in <asm/word-at-a-time.h> to be a bit more
complicated, but a lot more generic.

In particular, it allows us to really do the operations efficiently on
both little-endian and big-endian machines, pretty much regardless of
machine details.  For example, if you can rely on a fast population
count instruction on your architecture, this will allow you to make your
optimized <asm/word-at-a-time.h> file with that.

NOTE! The "generic" version in include/asm-generic/word-at-a-time.h is
not truly generic, it actually only works on big-endian.  Why? Because
on little-endian the generic algorithms are wasteful, since you can
inevitably do better. The x86 implementation is an example of that.

(The only truly non-generic part of the asm-generic implementation is
the "find_zero()" function, and you could make a little-endian version
of it.  And if the Kbuild infrastructure allowed us to pick a particular
header file, that would be lovely)

The <asm/word-at-a-time.h> functions are as follows:

 - WORD_AT_A_TIME_CONSTANTS: specific constants that the algorithm
   uses.

 - has_zero(): take a word, and determine if it has a zero byte in it.
   It gets the word, the pointer to the constant pool, and a pointer to
   an intermediate "data" field it can set.

   This is the "quick-and-dirty" zero tester: it's what is run inside
   the hot loops.

 - "prep_zero_mask()": take the word, the data that has_zero() produced,
   and the constant pool, and generate an *exact* mask of which byte had
   the first zero.  This is run directly *outside* the loop, and allows
   the "has_zero()" function to answer the "is there a zero byte"
   question without necessarily getting exactly *which* byte is the
   first one to contain a zero.

   If you do multiple byte lookups concurrently (eg "hash_name()", which
   looks for both NUL and '/' bytes), after you've done the prep_zero_mask()
   phase, the result of those can be or'ed together to get the "either
   or" case.

 - The result from "prep_zero_mask()" can then be fed into "find_zero()"
   (to find the byte offset of the first byte that was zero) or into
   "zero_bytemask()" (to find the bytemask of the bytes preceding the
   zero byte).

   The existence of zero_bytemask() is optional, and is not necessary
   for the normal string routines.  But dentry name hashing needs it, so
   if you enable DENTRY_WORD_AT_A_TIME you need to expose it.

This changes the generic strncpy_from_user() function and the dentry
hashing functions to use these modified word-at-a-time interfaces.  This
gets us back to the optimized state of the x86 strncpy that we lost in
the previous commit when moving over to the generic version.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
modified for Linux 3.0 from Linux 3.4+ by faux123
lib: add generic strnlen_user() function

This adds a new generic optimized strnlen_user() function that uses the
<asm/word-at-a-time.h> infrastructure to portably do efficient string
handling.

In many ways, strnlen is much simpler than strncpy, and in particular we
can always pre-align the words we load from memory.  That means that all
the worries about alignment etc are a non-issue, so this one can easily
be used on any architecture.  You obviously do have to do the
appropriate word-at-a-time.h macros.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
lib: Fix generic strnlen_user for 32-bit big-endian machines

The aligned_byte_mask() definition is wrong for 32-bit big-endian
machines: the "7-(n)" part of the definition assumes a long is 8
bytes.  This fixes it by using BITS_PER_LONG - 8 instead of 8*7.
Tested on 32-bit and 64-bit PowerPC.

Signed-off-by: Paul Mackerras <paulus@samba.org>
Acked-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
kernel: Move REPEAT_BYTE definition into linux/kernel.h

And make sure that everything using it explicitly includes
that header file.

Signed-off-by: David S. Miller <davem@xxxxxxxxxxxxx>
modified for Linux 3.0 from Linux 3.4+ by faux123
ARM: use generic strnlen_user and strncpy_from_user
 functions

This patch implements the word-at-a-time interface for ARM using the
same algorithm as x86. Although we have a clz instruction from ARMv5,
this only saves us one mov instruction when building with Thumb-2 and
makes no difference when targetting ARM, so we use the magic 0x0ff0001
constant for all CPUs. For big-endian configurations, we use the
implementation from asm-generic.

With this implemented, we can replace our byte-at-a-time strnlen_user
and strncpy_from_user functions with the optimised generic versions.

Signed-off-by: Will Deacon <will.deacon@arm.com>
modified for Linux 3.0 from Linux 3.4+ by faux123
fs/dyn_sync_cntrl: dynamic sync control

The dynamic sync control interface uses Android kernel's unique early
suspend / lat resume interface.

While screen is on, file sync is disabled
when screen is off, a file sync is called to flush all outstanding writes
and restore file sync operation as normal.

Signed-off-by: Paul Reioux <reioux@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>
defconfig : enable FSYNC control and use the optimized AES and SHA1 routines
switch do_fsync() to fget_light()

Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
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>
Added optimized CRC32 algorithm.
sched: Folding nohz load accounting more accurate

After patch 453494c3d4 (sched: Fix nohz load accounting -- again!), we can fold
the idle into calc_load_tasks_idle between the last cpu load calculating and
calc_global_load calling. However problem still exits between the first cpu
load calculating and the last cpu load calculating. Every time when we do load
calculating, calc_load_tasks_idle will be added into calc_load_tasks, even if
the idle load is caused by calculated cpus. This problem is also described in
the following link:

https://lkml.org/lkml/2012/5/24/419

This bug can be found in our work load. The average running processes number
is about 15, but the load only shows about 4.

The patch provides a solution, by taking calculated load cpus' idle away from
 real effective idle. First adds a cpumask to record those cpus that alread
calculated their load, and then adds a calc_unmask_cpu_load_idle to record
thoses not marked cpus' go-idle load. Calc_unmask_cpu_load_idle takes place
of calc_load_tasks_idle to be added into calc_load_tasks every 5HZ when cpu
calculate its load. Go-idle load on those cpus which load alread has been calculated
will only be added into calc_load_tasks_idle, no in calc_unmask_cpu_load_idle.

Reported-by: Sha Zhengju <handai.szj@xxxxxxxxx>
Signed-off-by: Charles Wang <muming.wq@xxxxxxxxxx>
modified for HTC One X kernel from Linux 3.4+ by faux123
mm, oom: fix potential killing of thread that is disabled from oom killing

/proc/sys/vm/oom_kill_allocating_task will immediately kill current when
the oom killer is called to avoid a potentially expensive tasklist scan
for large systems.

Currently, however, it is not checking current's oom_score_adj value
which may be OOM_SCORE_ADJ_MIN, meaning that it has been disabled from
oom killing.

This patch avoids killing current in such a condition and simply falls
back to the tasklist scan since memory still needs to be freed.

Signed-off-by: David Rientjes <rientjes@google.com>
backported from Linux 3.5 to linux 2.6.39 by faux123
SCHEDULER: Autogroup patch group by current user android UID instead of task ID
sched: don't call task_group() many times in set_task_rq()

It improves perfomance, especially if autogroup enabled.

The size of set_task_rq() was 0x180 and now it is 0xa0.

Signed-off-by: Andrew Vagin <avagin@openvz.org>
slub: set slub_max_order to 0

To avoid locking and per-cpu overhead, SLUB optimisically uses
high-order allocations up to order-3 by default and falls back to lower
allocations if they fail.

So, with the default value (slub_max_order = 3), the kernel may ask up
to 3 contigous pages for each slab. However, with a reduced amount of
memory it is not worth to try to do order-3 allocations, it adds more
overhead (shrinkers have to free more objects to release any memory) and
probably it can easily fail to success with order-3 allocations.

For this reason it is better to immediately fallback to oder-0
allocations to reduce unnecessary overhead.

Signed-off-by: Andrea Righi <andrea@betterlinux.com>
Added optimized ARM RWSEM algorithm.
sched/nohz: Fix rq->cpu_load[] calculations

While investigating why the load-balancer did funny I found that the
rq->cpu_load[] tables were completely screwy.. a bit more digging
revealed that the updates that got through were missing ticks followed
by a catchup of 2 ticks.

The catchup assumes the cpu was idle during that time (since only nohz
can cause missed ticks and the machine is idle etc..) this means that
esp. the higher indices were significantly lower than they ought to
be.

The reason for this is that its not correct to compare against jiffies
on every jiffy on any other cpu than the cpu that updates jiffies.

This patch cludges around it by only doing the catch-up stuff from
nohz_idle_balance() and doing the regular stuff unconditionally from
the tick.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: pjt@google.com
Cc: Venkatesh Pallipadi <venki@google.com>
Link: http://lkml.kernel.org/n/tip-tp4kj18xdd5aj4vvj0qg55s2@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
modified for Linux 3.0 from Linux 3.4+ by faux123
Reduced Android Logger RAM usage. TNX to sakindia123@xda for point.

Conflicts:

	drivers/staging/android/logger.c
slub: zero page to fix boot crashes

Latest mmotm rarely boots if SLUB is enabled: earlyprintk=vga shows
it crashing with various backtraces.  The memset has now been removed
from kmem_cache_open(), so kmem_cache_init() needs to zero its page.
This gets SLUB booting reliably again.

Signed-off-by: Hugh Dickins <hughd@google.com>