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
cpufreq: add smartassV2 governor

Ported to Huawei U8150 Froyo by Alan Orth <alan.orth@gmail.com>
sched: export nr_running symbol for use by smartassV2 CPU governor
block: prepare I/O context code for BFQ

BFQ uses struct cfq_io_context to store its per-process per-device data,
reusing the same code for cic handling of CFQ.  The code is not shared
ATM to minimize the impact of these patches.

This patch introduces a new hlist to each io_context to store all the
cic's allocated by BFQ to allow calling the right destructor on module
unload; the radix tree used for cic lookup needs to be duplicated
because it can contain dead keys inserted by a scheduler and later
retrieved by the other one.

Update the io_context exit and free paths to take care also of
the BFQ cic's.

Change the type of cfqq inside struct cfq_io_context to void *
to use it also for BFQ per-queue data.

A new bfq-specific ioprio_changed field is necessary, too, to avoid
clobbering cfq's one, so switch ioprio_changed to a bitmap, with one
element per scheduler.

Signed-off-by: Fabio Checconi <fabio@gandalf.sssup.it>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Francesco Allertsen <fallertsen@gmail.com>
Signed-off-by: Mauro Andreolini <mauro.andreolini@unimore.it>
block: add cgroups, kconfig and build bits for BFQ

Add a Kconfig option and do the related Makefile changes to compile
the BFQ I/O scheduler.  Also let the cgroups subsystem know about the
BFQ I/O controller.

Signed-off-by: Fabio Checconi <fabio@gandalf.sssup.it>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Mauro Andreolini <mauro.andreolini@unimore.it>
block: introduce the BFQ I/O scheduler

Add the BFQ I/O scheduler.  The general structure is borrowed from CFQ,
as much of the code.  A (bfq_)queue is associated to each task doing I/O
on a device, and each time a scheduling decision has to be taken a queue
is selected and it is served until it expires.

The main differences are:
     - slices are given in the service domain: tasks are assigned budgets,
       measured in number of sectors. Once got the disk, a task must
       however consume its assigned budget within a configurable maximum time
       (by default, the maximum possible value of the budgets is automaticall
       computed to comply with this timeout). This allows the desired latency
       "throughput boosting" tradeoff to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio and an ioprio_class.

    - If the cgroups interface is used, weights can be explictly assigned,
      otherwise ioprio values are mapped to weights using the relation
      weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher priority
      queues.  Among queues in the same classes the bandwidth is distributed
      in proportion to the weights of each queue.

Regarding what has not changed it is worth noting:
    - the handling of cfq_io_contexts to associate queues to tasks.
      Much
      of the code has been reused just renaming it.  (There is room for
      code sharing with CFQ but we wanted to minimize the impact of this
      patch.)

    - The handling of async queues.

    - The handling of idle windows.

    - The handling of merging.

    - The heuristics to assert that a task is worth an idle window (with
      minor modifications to hw_tag/CIC_SEEKY detection).

Signed-off-by: Fabio Checconi <fabio@gandalf.sssup.it>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Fix atomic functions in bfq
Add V(R) i/o scheduler