random: entropy tweaks are all the rage nowadays

use non-blocking pool for all

http://lwn.net/Articles/489734/

Conflicts:

	drivers/char/random.c
random: prevent add_input from doing anything
random: remove warning
random: squashed faux123 N5 kernel implementation

commit 54c3832918af1f8a30cd1675a4c89a0b61d798d0
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Nov 3 18:24:08 2013 -0500

    random: add debugging code to detect early use of get_random_bytes()

    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

commit 2d42a5d51a2a5403a3fc8a790929966dbaf4dbce
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Nov 3 16:40:53 2013 -0500

    random: initialize the last_time field in struct timer_rand_state

    Since we initialize jiffies to wrap five minutes before boot (see
    INITIAL_JIFFIES defined in include/linux/jiffies.h) it's important to
    make sure the last_time field is initialized to INITIAL_JIFFIES.
    Otherwise, the entropy estimator will overestimate the amount of
    entropy resulting from the first call to add_timer_randomness(),
    generally by about 8 bits.

    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

commit 401bddcefbcea3b67169df5d95e74aba1000f763
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Nov 3 07:56:17 2013 -0500

    random: don't zap entropy count in rand_initialize()

    The rand_initialize() function was being run fairly late in the kernel
    boot sequence.  This was unfortunate, since it zero'ed the entropy
    counters, thus throwing away credit that was accumulated earlier in
    the boot sequence, and it also meant that initcall functions run
    before rand_initialize were using a minimally initialized pool.

    To fix this, fix init_std_data() to no longer zap the entropy counter;
    it wasn't necessary, and move rand_initialize() to be an early
    initcall.

    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

commit 2ae33a2878e5a654408f446bb681c723df527fee
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Nov 3 06:54:51 2013 -0500

    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>

commit a2ae03dc90efffc6a958367b5b89d4ab70ef4d06
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Nov 3 00:15:05 2013 -0400

    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>

commit f940e53a6f4b72dd4b19a93f2efc8dac79a5738b
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Oct 3 12:02:37 2013 -0400

    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>

commit 7291e694d328f8461636987593ae27c2fff26e02
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Oct 3 01:08:15 2013 -0400

    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>

commit b49a9c09aa3c77a774fefd1f3a65bf74bbe21577
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Wed Oct 2 21:10:35 2013 -0400

    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>

commit b5e2c13bf36efb033d4aa469fd4fcf5e62219c1b
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Sep 22 16:04:19 2013 -0400

    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>

commit fba4e324d89ad5f40cb41d2e65cf002646af932d
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Sep 22 15:24:02 2013 -0400

    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>

commit b2138205442046e213eddef7ce776b0f156b8a33
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sun Sep 22 15:14:32 2013 -0400

    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>

commit 0b8688eab355f4fdbfeedc0b4856dc23d76929a4
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sat Sep 21 19:42:41 2013 -0400

    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>

commit 9790f5d910f75a99dd73ee02181bfd588e51a9db
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Sep 12 14:27:22 2013 -0400

    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>

commit a27420591e090c2ad03f9d58dd4eae145302d031
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Sep 12 14:10:25 2013 -0400

    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>

commit 9564dc0093d586ba693a3443a41390a4912cddc2
Author: H. Peter Anvin <hpa@linux.intel.com>
Date:   Tue Sep 10 23:16:17 2013 -0400

    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>

commit 23ffd726acb429adaf09fd9153773f268249aea7
Author: H. Peter Anvin <hpa@zytor.com>
Date:   Tue Sep 10 23:16:17 2013 -0400

    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>

    Conflicts:

        drivers/char/random.c

    also sync with mainline kernel

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

commit 067553019d8a702d2bf8a0597c9facf2265ab460
Author: H. Peter Anvin <hpa@linux.intel.com>
Date:   Tue Sep 10 23:16:17 2013 -0400

    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>

commit 5dd781605790b7d9bfb79d85b0d1092e8a25d633
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sat Sep 21 18:06:02 2013 -0400

    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>

commit a3f076385cbc092eb925d5d748f478ffa7f64a0f
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Sat Sep 21 13:58:22 2013 -0400

    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: poondog <markj338@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: poondog <markj338@gmail.com>