random: add tracepoints for easier debugging and verification

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: fix debug format strings

Fix the following warnings in formatting debug output:

drivers/char/random.c: In function ‘xfer_secondary_pool’:
drivers/char/random.c:827: warning: format ‘%d’ expects type ‘int’, but argument 7 has type ‘size_t’
drivers/char/random.c: In function ‘account’:
drivers/char/random.c:859: warning: format ‘%d’ expects type ‘int’, but argument 5 has type ‘size_t’
drivers/char/random.c:881: warning: format ‘%d’ expects type ‘int’, but argument 5 has type ‘size_t’
drivers/char/random.c: In function ‘random_read’:
drivers/char/random.c:1141: warning: format ‘%d’ expects type ‘int’, but argument 5 has type ‘ssize_t’
drivers/char/random.c:1145: warning: format ‘%d’ expects type ‘int’, but argument 5 has type ‘ssize_t’
drivers/char/random.c:1145: warning: format ‘%d’ expects type ‘int’, but argument 6 has type ‘long unsigned int’

by using '%zd' instead of '%d' to properly denote ssize_t/size_t conversion.

Signed-off-by: Jiri Kosina <jkosina@suse.cz>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: prime last_data value per fips requirements

The value stored in last_data must be primed for FIPS 140-2 purposes. Upon
first use, either on system startup or after an RNDCLEARPOOL ioctl, we
need to take an initial random sample, store it internally in last_data,
then pass along the value after that to the requester, so that consistency
checks aren't being run against stale and possibly known data.

CC: Herbert Xu <herbert@gondor.apana.org.au>
CC: "David S. Miller" <davem@davemloft.net>
CC: Matt Mackall <mpm@selenic.com>
CC: linux-crypto@vger.kernel.org
Acked-by: Neil Horman <nhorman@tuxdriver.com>
Signed-off-by: Jarod Wilson <jarod@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: make it possible to enable debugging without rebuild

The module parameter that turns debugging mode (which basically means
printing a few extra lines during runtime) is in '#if 0' block. Forcing
everyone who would like to see how entropy is behaving on his system to
rebuild seems to be a little bit too harsh.

If we were concerned about speed, we could potentially turn 'debug' into a
static key, but I don't think it's necessary.

Drop the '#if 0' block to allow using the 'debug' parameter without rebuilding.

Signed-off-by: Jiri Kosina <jkosina@suse.cz>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: allow architectures to optionally define random_get_entropy()

Allow architectures which have a disabled get_cycles() function to
provide a random_get_entropy() function which provides a fine-grained,
rapidly changing counter that can be used by the /dev/random driver.

For example, an architecture might have a rapidly changing register
used to control random TLB cache eviction, or DRAM refresh that
doesn't meet the requirements of get_cycles(), but which is good
enough for the needs of the random driver.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Cc: stable@vger.kernel.org
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: mix in architectural randomness earlier in extract_buf()

Previously if CPU chip had a built-in random number generator (i.e.,
RDRAND on newer x86 chips), we mixed it in at the very end of
extract_buf() using an XOR operation.

We now mix it in right after the calculate a hash across the entire
pool.  This has the advantage that any contribution of entropy from
the CPU's HWRNG will get mixed back into the pool.  In addition, it
means that if the HWRNG has any defects (either accidentally or
maliciously introduced), this will be mitigated via the non-linear
transform of the SHA-1 hash function before we hand out generated
output.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>

Conflicts:
	drivers/char/random.c
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>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: allow fractional bits to be tracked

Allow fractional bits of entropy to be tracked by scaling the entropy
counter (fixed point).  This will be used in a subsequent patch that
accounts for entropy lost due to overwrites.

[ Modified by tytso to fix up a few missing places where the
  entropy_count wasn't properly converted from fractional bits to
  bits. ]

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>

Conflicts:

	drivers/char/random.c

also sync with mainline kernel

Signed-off-by: Paul Reioux <reioux@gmail.com>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>

Conflicts:
	drivers/char/random.c
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/2 then

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

	  ... so we can approximate the exponential with
	  3/4*add_entropy/pool_size and still be on the
	  safe side by adding at most pool_size/2 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 3/4 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ényi
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ényi
entropy of infinite order.

As such, this conservatism seems more than justified.

This does introduce fractional bit values.  I have left it to have 3
bits of fraction, so that with a pool of 2^12 bits the multiply in
credit_entropy_bits() can still fit into an int, as 2*(3+12) < 31.  It
is definitely possible to allow for more fractional accounting, but
that multiply then would have to be turned into a 32*32 -> 64 multiply.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Cc: DJ Johnston <dj.johnston@intel.com>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: fix the tracepoint for get_random_bytes(_arch)

Fix a problem where get_random_bytes_arch() was calling the tracepoint
get_random_bytes().  So add a new tracepoint for
get_random_bytes_arch(), and make get_random_bytes() and
get_random_bytes_arch() call their correct tracepoint.

Also, add a new tracepoint for add_device_randomness()

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>

Conflicts:
	include/trace/events/random.h

Conflicts:
	include/trace/events/random.h
random: optimize spinlock use in add_device_randomness()

The add_device_randomness() function calls mix_pool_bytes() twice for
the input pool and the non-blocking pool, for a total of four times.
By using _mix_pool_byte() and taking the spinlock in
add_device_randomness(), we can halve the number of times we need
take each pool's spinlock.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: optimize the entropy_store structure

Use smaller types to slightly shrink the size of the entropy store
structure.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: cap the rate which the /dev/urandom pool gets reseeded

In order to avoid draining the input pool of its entropy at too high
of a rate, enforce a minimum time interval between reseedings of the
urandom pool.  This is set to 60 seconds by default.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: speed up the fast_mix function by a factor of four

By mixing the entropy in chunks of 32-bit words instead of byte by
byte, we can speed up the fast_mix function significantly.  Since it
is called on every single interrupt, on systems with a very heavy
interrupt load, this can make a noticeable difference.

Also fix a compilation warning in add_interrupt_randomness() and avoid
xor'ing cycles and jiffies together just in case we have an
architecture which tries to define random_get_entropy() by returning
jiffies.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Reported-by: Jörn Engel <joern@logfs.org>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: adjust the generator polynomials in the mixing function slightly

Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
Videau in their paper, "The Linux Pseudorandom Number Generator
Revisited" (see: http://eprint.iacr.org/2012/251.pdf).

They suggested a slight change to improve our mixing functions
slightly.  I also adjusted the comments to better explain what is
going on, and to document why the polynomials were changed.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: drop trickle mode

The add_timer_randomness() used to drop into trickle mode when entropy
pool was estimated to be 87.5% full.  This was important when
add_timer_randomness() was used to sample interrupts.  It's not used
for this any more --- add_interrupt_randomness() now uses fast_mix()
instead.  By elimitating trickle mode, it allows us to fully utilize
entropy provided by add_input_randomness() and add_disk_randomness()
even when the input pool is above the old trickle threshold of 87.5%.

This helps to answer the criticism in [1] in their hypothetical
scenario where our entropy estimator was inaccurate, even though the
measurements in [2] seem to indicate that our entropy estimator given
real-life entropy collection is actually pretty good, albeit on the
conservative side (which was as it was designed).

[1] http://eprint.iacr.org/2013/338.pdf
[2] http://eprint.iacr.org/2012/251.pdf

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: push extra entropy to the output pools

As the input pool gets filled, start transfering entropy to the output
pools until they get filled.  This allows us to use the output pools
to store more system entropy.  Waste not, want not....

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: convert DEBUG_ENT to tracepoints

Instead of using the random driver's ad-hoc DEBUG_ENT() mechanism, use
tracepoints instead.  This allows for a much more fine-grained control
of which debugging mechanism which a developer might need, and unifies
the debugging messages with all of the existing tracepoints.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: make add_timer_randomness() fill the nonblocking pool first

Change add_timer_randomness() so that it directs incoming entropy to
the nonblocking pool first if it hasn't been fully initialized yet.
This matches the strategy we use in add_interrupt_randomness(), which
allows us to push the randomness where we need it the most during when
the system is first booting up, so that get_random_bytes() and
/dev/urandom become safe to use as soon as possible.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>
random: printk notifications for urandom pool initialization

Print a notification to the console when the nonblocking pool is
initialized.  Also printk a warning when a process tries reading from
/dev/urandom before it is fully initialized.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Chet Kener <Cl3Kener@gmail.com>