Optimized ARM RWSEM algorithm

RWSEM implementation for ARM using atomic functions.
Heavily based on arch/sh/include/asm/rwsem.h

Signed-off-by: Ashwin Chaugule <ashwinc@codeaurora.org>
Add new, lookup3-based jhash. See: http://burtleburtle.net/bob/hash/doobs.html
pids: fix a race in pid generation that causes pids to be reused immediately

A program that repeatedly forks and waits is susceptible to having the
same pid repeated, especially when it competes with another instance of
the same program.  This is really bad for bash implementation.
Furthermore, many shell scripts assume that pid numbers will not be used
for some length of time.

Race Description:

A                                    B

// pid == offset == n                // pid == offset == n + 1
test_and_set_bit(offset, map->page)
									 test_and_set_bit(offset, map->page);
									 pid_ns->last_pid = pid;
pid_ns->last_pid = pid;
									 // pid == n + 1 is freed (wait())

									 // Next fork()...
									 last = pid_ns->last_pid; // == n
									 pid = last + 1;

Code to reproduce it (Running multiple instances is more effective):

#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

// The distance mod 32768 between two pids, where the first pid is expected
// to be smaller than the second.
int PidDistance(pid_t first, pid_t second) {
  return (second + 32768 - first) % 32768;
}

int main(int argc, char* argv[]) {
  int failed = 0;
  pid_t last_pid = 0;
  int i;
  printf("%d\n", sizeof(pid_t));
  for (i = 0; i < 10000000; ++i) {
	if (i % 32786 == 0)
	  printf("Iter: %d\n", i/32768);
	int child_exit_code = i % 256;
	pid_t pid = fork();
	if (pid == -1) {
	  fprintf(stderr, "fork failed, iteration %d, errno=%d", i, errno);
	  exit(1);
	}
	if (pid == 0) {
	  // Child
	  exit(child_exit_code);
	} else {
	  // Parent
	  if (i > 0) {
		int distance = PidDistance(last_pid, pid);
		if (distance == 0 || distance > 30000) {
		  fprintf(stderr,
				  "Unexpected pid sequence: previous fork: pid=%d, "
				  "current fork: pid=%d for iteration=%d.\n",
				  last_pid, pid, i);
		  failed = 1;
		}
	  }
	  last_pid = pid;
	  int status;
	  int reaped = wait(&status);
	  if (reaped != pid) {
		fprintf(stderr,
				"Wait return value: expected pid=%d, "
				"got %d, iteration %d\n",
				pid, reaped, i);
		failed = 1;
	  } else if (WEXITSTATUS(status) != child_exit_code) {
		fprintf(stderr,
				"Unexpected exit status %x, iteration %d\n",
				WEXITSTATUS(status), i);
		failed = 1;
	  }
	}
  }
  exit(failed);
}

Thanks to Ted Tso for the key ideas of this implementation.

Signed-off-by: Salman Qazi <sqazi@google.com>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Theodore Ts'o <tytso@mit.edu>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Sukadev Bhattiprolu <sukadev@us.ibm.com>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
net sched: fix some kernel memory leaks

We leak at least 32bits of kernel memory to user land in tc dump,
because we dont init all fields (capab ?) of the dumped structure.

Use C99 initializers so that holes and non explicit fields are zeroed.

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

Conflicts:

	net/sched/act_nat.c
rcu: "Tiny RCU", The Bloatwatch Edition

This patch is a version of RCU designed for !SMP provided for a
small-footprint RCU implementation.  In particular, the
implementation of synchronize_rcu() is extremely lightweight and
high performance. It passes rcutorture testing in each of the
four relevant configurations (combinations of NO_HZ and PREEMPT)
on x86.  This saves about 1K bytes compared to old Classic RCU
(which is no longer in mainline), and more than three kilobytes
compared to Hierarchical RCU (updated to 2.6.30):

	CONFIG_TREE_RCU:

	   text	   data	    bss	    dec	    filename
		183       4       0     187     kernel/rcupdate.o
	   2783     520      36    3339     kernel/rcutree.o
				   3526 Total (vs 4565 for v7)

	CONFIG_TREE_PREEMPT_RCU:

	   text	   data	    bss	    dec	    filename
		263       4       0     267     kernel/rcupdate.o
	   4594     776      52    5422     kernel/rcutree.o
				   5689 Total (6155 for v7)

	CONFIG_TINY_RCU:

	   text	   data	    bss	    dec	    filename
		 96       4       0     100     kernel/rcupdate.o
		734      24       0     758     kernel/rcutiny.o
						858 Total (vs 848 for v7)

The above is for x86.  Your mileage may vary on other platforms.
Further compression is possible, but is being procrastinated.

Changes from v7 (http://lkml.org/lkml/2009/10/9/388)

o	Apply Lai Jiangshan's review comments (aside from
might_sleep() 	in synchronize_sched(), which is covered by SMP builds).

o	Fix up expedited primitives.

Changes from v6 (http://lkml.org/lkml/2009/9/23/293).

o	Forward ported to put it into the 2.6.33 stream.

o	Added lockdep support.

o	Make lightweight rcu_barrier.

Changes from v5 (http://lkml.org/lkml/2009/6/23/12).

o	Ported to latest pre-2.6.32 merge window kernel.

	- Renamed rcu_qsctr_inc() to rcu_sched_qs().
	- Renamed rcu_bh_qsctr_inc() to rcu_bh_qs().
	- Provided trivial rcu_cpu_notify().
	- Provided trivial exit_rcu().
	- Provided trivial rcu_needs_cpu().
	- Fixed up the rcu_*_enter/exit() functions in linux/hardirq.h.

o	Removed the dependence on EMBEDDED, with a view to making
	TINY_RCU default for !SMP at some time in the future.

o	Added (trivial) support for expedited grace periods.

Changes from v4 (http://lkml.org/lkml/2009/5/2/91) include:

o	Squeeze the size down a bit further by removing the
	->completed field from struct rcu_ctrlblk.

o	This permits synchronize_rcu() to become the empty function.
	Previous concerns about rcutorture were unfounded, as
	rcutorture correctly handles a constant value from
	rcu_batches_completed() and rcu_batches_completed_bh().

Changes from v3 (http://lkml.org/lkml/2009/3/29/221) include:

o	Changed rcu_batches_completed(), rcu_batches_completed_bh()
	rcu_enter_nohz(), rcu_exit_nohz(), rcu_nmi_enter(), and
	rcu_nmi_exit(), to be static inlines, as suggested by David
	Howells.  Doing this saves about 100 bytes from rcutiny.o.
	(The numbers between v3 and this v4 of the patch are not directly
	comparable, since they are against different versions of Linux.)

Changes from v2 (http://lkml.org/lkml/2009/2/3/333) include:

o	Fix whitespace issues.

o	Change short-circuit "||" operator to instead be "+" in order
to 	fix performance bug noted by "kraai" on LWN.

		(http://lwn.net/Articles/324348/)

Changes from v1 (http://lkml.org/lkml/2009/1/13/440) include:

o	This version depends on EMBEDDED as well as !SMP, as suggested
	by Ingo.

o	Updated rcu_needs_cpu() to unconditionally return zero,
	permitting the CPU to enter dynticks-idle mode at any time.
	This works because callbacks can be invoked upon entry to
	dynticks-idle mode.

o	Paul is now OK with this being included, based on a poll at
the 	Kernel Miniconf at linux.conf.au, where about ten people said
	that they cared about saving 900 bytes on single-CPU systems.

o	Applies to both mainline and tip/core/rcu.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: David Howells <dhowells@redhat.com>
Acked-by: Josh Triplett <josh@joshtriplett.org>
Reviewed-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Cc: dipankar@in.ibm.com
Cc: mathieu.desnoyers@polymtl.ca
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
Cc: rostedt@goodmis.org
Cc: Valdis.Kletnieks@vt.edu
Cc: avi@redhat.com
Cc: mtosatti@redhat.com
LKML-Reference: <12565226351355-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>
lib: Improve the performance of memcpy and memmove of the general version

The performance of memcpy and memmove of the general version is
very inefficient, this patch improves them.
lib: Introduce some memory copy macros and functions

The kernel's memcpy and memmove is very inefficient. But the glibc version is
quite fast, in some cases it is 10 times faster than the kernel version. So I
introduce some memory copy macros and functions of the glibc to improve the
kernel version's performance.

The strategy of the memory functions is:
1. Copy bytes until the destination pointer is aligned.
2. Copy words in unrolled loops. If the source and destination are not aligned
   in the same way, use word memory operations, but shift and merge two read
   words before writing.
3. Copy the few remaining bytes.

Signed-off-by: Miao Xie <miaox@...fujitsu.com>
net/ipv4: Eliminate kstrdup memory leak

The string clone is only used as a temporary copy of the argument val
within the while loop, and so it should be freed before leaving the
function.  The call to strsep, however, modifies clone, so a pointer to the
front of the string is kept in saved_clone, to make it possible to free it.

The sematic match that finds this problem is as follows:
(http://coccinelle.lip6.fr/)

// <smpl>
@r exists@
local idexpression x;
expression E;
identifier l;
statement S;
@@

*x= \(kasprintf\|kstrdup\)(...);
...
if (x == NULL) S
... when != kfree(x)
	when != E = x
if (...) {
  <... when != kfree(x)
* goto l;
  ...>
* return ...;
}
// </smpl>

Signed-off-by: Julia Lawall <julia@diku.dk>
Signed-off-by: David S. Miller <davem@davemloft.net>
Grants system server access to /proc/<pid>/oom_adj for Android applications.

Signed-off-by: Brian Swetland <swetland@google.com>
Lower vfs_cache_pressure 100->25

    This gives less priority to the filesystem cache because it is at the expense of RAM (and we don't have much).
    	See: http://rudd-o.com/en/linux-and-free-software/tales-from-responsivenessland-why-linux-feels-slow-and-how-to-fix-that
    	See: http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.7/2.6.7-mm1/broken-out/vfs-shrinkage-tuning.patch
cpufreq: interactive: New 'interactive' governor

New interactive governor.

This governor is designed for latency sensitive workloads, UI interaction for
example.

Advantages:
+ significantly more responsive to ramp cpu up when required (UI interaction)
+ more consistent ramping, existing governors do their cpu load sampling in a
workqueue context, the 'interactive' governor does this in a timer context, which
gives more consistent cpu load sampling.
+ higher priority for cpu frequency increase, rt_workqueue is used for scaling
up, giving the remaining tasks the cpu performance benefit, unlike existing
governors which schedule rampup work to occur after your performance starved
tasks have completed.

Existing governors sample cpu load at a particular rate, typically
every X ms. Which can lead to under powering UI threads when the user has
interacted with an idle system until the next sample period happns.

The 'interactive' governor has a different approach. Instead of sampling the cpu
at a specified rate, the governor will scale the cpu frequency up when coming
out of idle. When the cpu comes out of idle, a timer is configured to fire
within 1-2 ticks. If the cpu is 100% busy from exiting idle to when the timer
fires then we assume the cpu is underpowered and ramp to MAX speed.

If the cpu was not 100% busy, then the governor evaluates the cpu load over the
last 'min_sample_rate' (default 50000 uS) to determine the cpu speed to ramp down
to.

There is only one tuneable for this governor:
/sys/devices/system/cpu/cpufreq/interactive/min_sample_rate:
	The minimum ammount of time to spend at the current frequency before
	ramping down. This is to ensure that the governor has seen enough
	historic cpu load data to determine the appropriate workload.
	Default is 5000 uS.

Signed-off-by: Mike Chan <mike@android.com>
Change-Id: I686d2f57b0ed9cbb73217403b7438be5719588d2