random: Account for entropy loss due to overwrites

When we write entropy into a non-empty pool, we currently don't
account at all for the fact that we will probabilistically overwrite
some of the entropy in that pool.  This means that unless the pool is
fully empty, we are currently *guaranteed* to overestimate the amount
of entropy in the pool!

Assuming Shannon entropy with zero correlations we end up with an
exponentally decaying value of new entropy added:

	entropy <- entropy + (pool_size - entropy) *
		(1 - exp(-add_entropy/pool_size))

However, calculations involving fractional exponentials are not
practical in the kernel, so apply a piecewise linearization:

	  For add_entropy <= pool_size then

	  (1 - exp(-add_entropy/pool_size)) >= (add_entropy/pool_size)*0.632...

	  ... so we can approximate the exponential with
	  add_entropy/(pool_size*2) and still be on the
	  safe side by adding at most one pool_size at a time.

In order for the loop not to take arbitrary amounts of time if a bad
ioctl is received, terminate if we are within one bit of full.  This
way the loop is guaranteed to terminate after no more than
log2(poolsize) iterations, no matter what the input value is.  The
vast majority of the time the loop will be executed exactly once.

The piecewise linearization is very conservative, approaching 1/2 of
the usable input value for small inputs, however, our entropy
estimation is pretty weak at best, especially for small values; we
have no handle on correlation; and the Shannon entropy measure (Réi
entropy of order 1) is not the correct one to use in the first place,
but rather the correct entropy measure is the min-entropy, the Réi
entropy of infinite order.

As such, this conservatism seems more than justified.  Note, however,
that attempting to add one bit of entropy will never succeed; nor will
two bits unless the pool is completely empty.  These roundoff
artifacts could be improved by using fixed-point arithmetic and adding
some number of fractional entropy bits.

[ v2: rely on the previous patch for poolbitshift ]

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: DJ Johnston <dj.johnston@intel.com>
Cc: <stable@vger.kernel.org>

Conflicts:
	drivers/char/random.c
Signed-off-by: poondog <markj338@gmail.com>
random: Statically compute poolbitshift, poolbytes, poolbits

Use a macro to statically compute poolbitshift (will be used in a
subsequent patch), poolbytes, and poolbits.  On virtually all
architectures the cost of a memory load with an offset is the same as
the one of a memory load.

It is still possible for this to generate worse code since the C
compiler doesn't know the fixed relationship between these fields, but
that is somewhat unlikely.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: poondog <markj338@gmail.com>
random: prevent add_input from doing anything

Signed-off-by: poondog <markj338@gmail.com>
random: entropy tweaks are all the rage nowadays

use nonblocking for all.  Read this web page:
http://lwn.net/Articles/489734/

Signed-off-by: poondog <markj338@gmail.com>
random: remove warning

Signed-off-by: poondog <markj338@gmail.com>
DRIVERS: RANDOM: sync with anarikia1976 mako kernel
cpuinit: get rid of __cpuinit, first regexp

This commit is the result of:

find -name "*.c" | xargs sed -i "s/ __cpuinit / /g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: Cerebro <zarboz@gmail.com>
cpuinit: get rid of __cpuinit, second regexp

This commit is the result of:

find -name "*.c" | xargs sed -i "s/ __cpuexit / /g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>
cpuinit: get rid of __cpuinit, third regexp

This commit is the result of:

find -name "*.c" | xargs sed -i "s/ __cpuinitdata//g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>
cpuinit: get rid of __cpuinit, fourth regexp

This commit is the result of:

find -name "*.c" | xargs sed -i "s/ __cpuinit$//g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>
cpuinit: get rid of __cpuinit, fifth regexp

This commit is the result of:

find arch/ -name "*.h" | xargs sed -i "s/ __cpuinit//g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>
cpuinit: get rid of __cpuinit, sixth regexp

This commit is the result of:

find -name "*.c" | xargs sed -i "s/^__cpuinit //g"

Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
Signed-off-by: Dennis Rassmann <showp1984@gmail.com>
Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>
cpuinit: get rid of __cpuinit, manual fixups

a few final fixups that haven't been caught by regexps

Signed-off-by: Dennis Rassmann <showp1984@gmail.com>

Signed-off-by: Zarboz <zarboz@gmail.com>
Signed-off-by: poondog <markj338@gmail.com>