path: root/drivers/char/random.c

/*
 * random.c -- A strong random number generator
 *
 * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
 *
 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
 * rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, and the entire permission notice in its entirety,
 *    including the disclaimer of warranties.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission.
 *
 * ALTERNATIVELY, this product may be distributed under the terms of
 * the GNU General Public License, in which case the provisions of the GPL are
 * required INSTEAD OF the above restrictions.  (This clause is
 * necessary due to a potential bad interaction between the GPL and
 * the restrictions contained in a BSD-style copyright.)
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
 * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */

/*
 * (now, with legal B.S. out of the way.....)

 * This routine gathers environmental noise from device drivers, etc.,
 * and returns good randomly distributed numbers, suitable for
 * cryptographic use.  Besides the obvious cryptographic uses, these
 * numbers are also good for seeding TCP sequence numbers, and other
 * places where it is desirable to have numbers which are not only
 * random, but hard to predict by an attacker.

 * Theory of operation
 * ===================

 * Computers are very predictable devices.  Hence it is extremely hard
 * to implement a truly random distribution on a computer --- as
 * opposed to a pseudo-random distribution, which can easily
 * implemented by an algorithm.  Unfortunately, it is sometimes
 * possible for attackers to guess the output sequence of
 * pseudo-random generators, and for some applications this is not
 * acceptable.  So instead, we must try to gather "noise" from the
 * computer's environment, i.e. signals that contain an element of
 * actual entropy, and that are hard for outside attackers to observe,
 * and use that to generate randomly-distributed numbers.

 * Environmental sources that are available to the kernel include
 * inter-keyboard timings, inter-interrupt timings from some
 * interrupts, and similar events.  Again, these must be both (a)
 * non-deterministic and (b) hard for an outside observer to measure.

 * Operation of this device is centered on four "pools".  The four
 * pools are similar in structure but serve different purposes.
 */

/*
 * Here is a block diagram:
 *
 * fast       fast
 * events --> pool --\   input   /------------> /dev/random
 *                    --> pool --
 * slower, larger    /           \     PRNG
 * events ----------/             \--> pool --> /dev/urandom
 */

/*
 * The fast pool is similar in function to the input pool, as
 * described below.  It handles events that occur frequently but
 * contain little entropy.  It is fast enough that the overhead of
 * doing it on every interrupt is affordable.  It is similar in
 * structure to the input pool, but much smaller.  After accumulating
 * a modest amount of entropy, it passes the entropy on to the input
 * pool.

 * The input pool is serves as a concentrator, mixer, and storage
 * area.  The entropy that is available as input to the input pool
 * commonly has an entropy density of much less than 8 bits per byte.
 * This is mixed into the input pool, which is mixed using a CRC-like
 * function.  The mixing is not cryptographically strong, but should
 * be adequate if the randomness is not chosen maliciously.  As bytes
 * are mixed into this pool, the routines keep an *estimate* of how
 * many bits of entropy are contained in the pool.

 * When randomly-distributed bytes are desired, they can be extracted
 * from the input pool by taking the SHA1 hash of the pool contents.
 * This avoids exposing the internal state of the pool.  It is
 * believed to be computationally infeasible to derive any useful
 * information about the input of SHA1 from its output.  Even if it is
 * possible to analyze SHA1 in some clever way, as long as the amount
 * of data extracted in this way is less than the entropy content of
 * the the input pool, the extracted data is totally unpredictable.
 * For this reason, the routine decreases its internal estimate of how
 * many bits of "true randomness" (aka entropy) are contained in the
 * input pool whenever data is extracted.

 * The devrandom pool (if any) is associated with /dev/random.  It is
 * similar in structure to the input pool, but its purpose is
 * different.  Its input comes from the input pool, which means the
 * the entropy density is high (8 bits per byte), so no concentration
 * or mixing is necessary.  Therefore this pool serves primarily as a
 * fifo.  If the amount of entropy stored in the devrandom pool is
 * insufficient to meet the demand, and no more entropy can be pulled
 * from the input pool, any read to /dev/random will block.

 * The PRNG pool is associated with the /dev/urandom device, and with
 * the get_random_bytes() function used by the kernel internally.
 * This pool is similar in structure, but its function is quite
 * different from the other pools.  It functions primarily as a PRNG
 * i.e. pseudo ranomness generator.  Specifically, it functions as
 * hash function operated in counter mode.  The PRNG is reseeded from
 * time to time, using entropy from the input pool.  An attacker may
 * (at least in theory) be able to infer the future output of the PRNG
 * from prior outputs.  This requires successful cryptanalysis of SHA,
 * which is not believed to be feasible, but there is a remote
 * possibility.  Nonetheless, a pseudorandom distribution of numbers
 * should be useful for a wide range of purposes.

 * Low-entropy case; startup transient
 * ===================================

 * The following applies to the input pool.

 * Scenario #1: Suppose the pool starts out with all zeros, or in some
 * other state that the attacker knows or could readily guess.  This
 * is a definite possibility immediately after startup.  If we add N=8
 * bits of entropy to the pool and then extract one 8-bit byte, that
 * byte will have an entropy of approximately 7.18 bits, as can be
 * verified by Monte Carlo integration over the ensemble.  That is an
 * entropy density of just under 90%, which we consider too low.

 * Scenario #2: Same as above, except that we load 18 bits before
 * extracting the first byte.  In other words, there is 10 bits of
 * /margin/.  Then the first byte will contain 7.99935 bits.  That is
 * an entropy density of 99.992%, which should be acceptable for a
 * wide range of purposes.

 * The idea of margin extends to larger N.  Let's keep the margin at
 * 10 bits.  If we load 16+10 = 26 bits into the pool before
 * extracting the first two bytes, the output entropy will be
 * approximately 15.9993 bits.  The entropy density will be
 * approximately 99.996%.  Again, you can verify this by Monte Carlo
 * integration over the ensemble.

 * The margin is easily implemented by initializing the entropy_count
 * of the input pool to a negative number.

 * Strategy for reseeding the PRNG
 * ===============================
 *
 *  There are a lot of things in this world that depend on adaptive
 *  load-balancing and resource-sharing.  Examples include:
 *
 *   a) The "invisible hand" of microeconomics.  If a resource is
 *    plentiful it will be cheap, and everybody can use it.  If/when the
 *    resource is scare, the price goes up, and only those who really
 *    need it will pay for it.
 *
 *   b) The "exponential backoff" algorithm used for the Ethernet
 *    layer-1 CSMA/CD.  http://en.wikipedia.org/wiki/Exponential_backoff
 *
 *   c) The rate of TCP retries, which is another example of exponential
 *    backoff.  http://www.pcvr.nl/tcpip/tcp_time.htm
 *
 *  So, the idea is that if entropy is plentiful, the PRNG can reseed
 *  itself relatively often.  If entropy is not plentiful, the PRNG
 *  should wait longer between reseedings.  The number of bits delivered
 *  by the PRNG between reseedings is an exponential function of how far
 *  the input pool is below its ceiling.  That's the concept.  The
 *  implementation goes about it in a somewhat backward way, because it
 *  is implemented on top of the existing "rsvd" mechanism, and usually
 *  it is better to use the existing mechanism whenever possible.  So,
 *  if the PRNG has been reseeded recently, it uses a large reserve
 *  ("rsvd").  If it has not been reseeded in a long time, the reserve
 *  goes down, eventually down all the way to zero.
 *
 *  The intent is that other processes that need entropy from
 *  /dev/random will play by the same rules.  That is, when entropy is
 *  scarce they will use it more sparingly.  This mechanism is voluntary
 *  not mandatory, but voluntary load- balancing is better than none at
 *  all.

 * Exported interfaces ---- output
 * ===============================
 *
 * There are three exported interfaces; the first is one designed to
 * be used from within the kernel:
 *
 * 	void get_random_bytes(void *buf, int nbytes);
 *
 * This interface will return the requested number of bytes, and place
 * it them the requested buffer.

 * The two other interfaces are two character devices /dev/random and
 * /dev/urandom.  /dev/random is suitable for use when very high
 * quality randomness is desired (for example, for key generation or
 * one-time pads), as it will only return a maximum of the number of
 * bits of randomness on hand (as estimated by the random number
 * generator).

 * The /dev/urandom device will never block, and will return as many
 * bytes as are requested.  It is a PRNG.  It is reseeded from time to
 * time.  The resulting distribution of numbers is cryptographically
 * strong, but not in principle unbreakable.  For many applications,
 * however, this is acceptable.

 * Exported interfaces ---- input
 * ==============================
 *
 * The current exported interfaces for gathering environmental noise
 * from the devices are:
 *
 *	void add_device_randomness(const void *buf, unsigned int size);
 * 	void add_input_randomness(unsigned int type, unsigned int code,
 *                                unsigned int value);
 *	void add_interrupt_randomness(int irq, int irq_flags);
 * 	void add_disk_randomness(struct gendisk *disk);
 *
 * add_device_randomness() is for adding data to the random pool that
 * is likely to differ between two devices (or possibly even per boot).
 * This would be things like MAC addresses or serial numbers, or the
 * read-out of the RTC. This does *not* add any actual entropy to the
 * pool, but it initializes the pool to different values for devices
 * that might otherwise be identical and have very little entropy
 * available to them (particularly common in the embedded world).
 *
 * add_input_randomness() uses the input layer interrupt timing, as well as
 * the event type information from the hardware.
 *
 * add_interrupt_randomness() uses the interrupt timing as random
 * inputs to the fast pool. Using the cycle counters and the irq source
 * as inputs, it feeds the randomness roughly once a second.
 *
 * add_disk_randomness() uses what amounts to the seek time of block
 * layer request events, on a per-disk_devt basis, as input to the
 * fast pool. Note that high-speed solid state drives with very low
 * seek times do not make for good sources of entropy, as their seek
 * times are usually fairly consistent.
 *
 * All of these routines try to estimate how many bits of randomness a
 * particular randomness source.  They do this by keeping track of the
 * first and second order deltas of the event timings.

 * Exported interfaces ---- sysctl
 * ===============================

 * files in /proc/sys/kernel/random :

 * .../poolsize (read only) -- reports the size of the input pool.  Since
 * 2.6.12 this is measured in bits.  Previously it was measured in
 * bytes.  Note that the devrandom pool and the prng pool are 4x
 * smaller than the input pool.

 * .../entropy_avail (read only) -- reports the total amount of stored
 * entropy, measured in bits.  This includes entropy stored in both
 * the input pool and the devrandom pool.

 * .../entropy_avail_input .../entropy_avail_random
 * .../entropy_avail_urandom (r/w) -- same as above, but report the
 * content of each pool separately

 * .../extracted_total_input .../extracted_total_random
 * .../extracted_total_urandom (r/w) -- report the total number of
 * bits of randomness extracted from the pool since the start of
 * operation.

 * .../extracted_subttl_input .../extracted_subttl_random
 * .../extracted_subttl_urandom (r/w) -- report the number of bits of
 * randomness extracted from the pool since the last time it was
 * reseeded.  This is particularly significant for /dev/urandom

 * Exported interfaces ---- ioctl
 * ===============================
 *** FIXME

 **?? There may be older programs out there that write to
  /dev/random and then do ioctl(RNDADDTOENTCNT...);  this
  is guaranteed to fail insidiously, since writing
  to /dev/random does nothing to the input pool.

 * Ensuring unpredictability at system startup
 * ============================================
 *
 * When any operating system starts up, it will go through a sequence
 * of actions that are fairly predictable by an adversary, especially
 * if the start-up does not involve interaction with a human operator.
 * There is likely to be virtually zero real entropy available.

 * However, we still need the /dev/urandom and get_random_bytes()
 * interfaces to be usable at startup, and to have some semblance of
 * security.  Therefore, it helps to store a seed that can be used to
 * re-seed the PRNG, and to carry this seed across shut-downs and
 * start-ups.  To do this, put the following lines an appropriate
 * script which is run during the boot sequence:

 * The byte count of 512 a factor of 4 more than is needed to reseed
 * the PRNG.  It is just right for reseeding the input pool, but one
 * could argue that it doesn't need to be reseeded at all.  We
 * preserve the 512 recommendation because it is traditional, because
 * it is mostly harmless, and because it might come in handy at some
 * point in the future.

 *	echo "Initializing random number generator..."
 *	random_seed=/var/run/random-seed
 *	# Carry a random seed from start-up to start-up
 *	# Load the input pool:
 *	if [ -f $random_seed ]; then
 *		cat $random_seed >/dev/urandom
 *	else
 *		touch $random_seed
 *	fi
 *	chmod 600 $random_seed
 *      # Save enough to reseed (differently!) next time:
 *	dd if=/dev/urandom of=$random_seed count=1 bs=512
 *
 * and the following lines in an appropriate script which is run as
 * the system is shutdown:
 *
 *	# Carry a random seed from shut-down to start-up
 *	# Save enough reseed the input pool.
 *	echo "Saving random seed..."
 *	random_seed=/var/run/random-seed
 *	touch $random_seed
 *	chmod 600 $random_seed
 *	dd if=/dev/urandom of=$random_seed count=1 bs=512

 * For example, on most modern systems using the System V init
 * scripts, such code fragments would be found in
 * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
 * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.

 * Effectively, these commands save a pseudorandomly-distribted seed
 * and then use that to initialize the prng pool -- and the input
 * pool -- at the next start-up.  (The seed is saved by the bootup
 * script, not only by the shutdown script, to make sure that
 * /etc/random-seed is never re-used.  It must be different for every
 * start-up, even if the system crashes without executing rc.0.)  Even
 * with complete knowledge of the start-up activities, predicting the
 * state of the output pools requires knowledge of the previous
 * history of the system.

 * Note that writing to /dev/urandom affects only the input pool
 * and prng pool (not the fast pool).

 * Writing to /dev/random is identical to writing to /dev/urandom.

 * Configuring the /dev/random driver under Linux
 * ==============================================
 *
 * The /dev/random driver under Linux uses minor numbers 8 and 9 of
 * the /dev/mem major number (#1).  So if your system does not have
 * /dev/random and /dev/urandom created already, they can be created
 * by using the commands:
 *
 * 	mknod /dev/random c 1 8
 * 	mknod /dev/urandom c 1 9
 *
 * Acknowledgements:
 * =================
 *
 * Ideas for constructing this random number generator were derived
 * from Pretty Good Privacy's random number generator, and from private
 * discussions with Phil Karn.  Colin Plumb provided a faster random
 * number generator, which speed up the mixing function of the entropy
 * pool, taken from PGPfone.  Dale Worley has also contributed many
 * useful ideas and suggestions to improve this driver.
 *
 * Any flaws in the design are solely my responsibility, and should
 * not be attributed to the Phil, Colin, or any of authors of PGP.
 *
 * Further background information on this topic may be obtained from
 * RFC 1750, "Randomness Recommendations for Security", by Donald
 * Eastlake, Steve Crocker, and Jeff Schiller.
 */

// TODO: Scatter/gather, to reduce the number of files under /proc.

#include <linux/utsname.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/major.h>
#include <linux/string.h>
#include <linux/fcntl.h>
#include <linux/slab.h>
#include <linux/random.h>
#include <linux/poll.h>
#include <linux/init.h>
#include <linux/fs.h>
#include <linux/genhd.h>
#include <linux/interrupt.h>
#include <linux/mm.h>
#include <linux/spinlock.h>
#include <linux/percpu.h>
#include <linux/cryptohash.h>
#include <linux/fips.h>
#include <linux/ptrace.h>
#include <linux/kmemcheck.h>

#ifdef CONFIG_GENERIC_HARDIRQS
# include <linux/irq.h>
#endif

#include <asm/processor.h>
#include <asm/uaccess.h>
#include <asm/irq.h>
#include <asm/irq_regs.h>
#include <asm/io.h>

#define CREATE_TRACE_POINTS
#include <trace/events/random.h>

/*
 * Configuration information.
 * Here, a "word" is of type __u32
 */
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
#define SEC_XFER_SIZE 512
#define EXTRACT_SIZE 10
#ifdef OVERCOMPLICATED
/* Three fills of size BUFFILL_ZONE would be more than enough
 * to fill the output buffer */
#  define BUFFILL_ZONE 400      /* measured in bits */
#endif

/* Choose 160 bits.  Seems reasonable.  Recommended in the Yarrow paper.  */
#define RESEED_BATCH 160                /* bits */
#define FIRST_RESEED 18                 /* dimensionless log(ratio) */
#define MIN_DILUTION 1000               /* bits, approximately */
#define APP_MAX 20                      /* dimensionless # steps */
/*
 * We design for MIN_DILUTION=1000 approximately.  We get 819 exactly,
 * because FIRST_RESEED has to be rounded to an integer.
 *
 * The dilution factor ranges from 819 to 1 (at appetite=0) to 819<<20
 * i.e. 858,993,459 to 1 (at appetite=20) ... assuming APP_MAX == 20.
 */
#if RESEED_BATCH*MIN_DILUTION < 1<<(FIRST_RESEED-1) \
   || RESEED_BATCH*MIN_DILUTION >= 1<<(FIRST_RESEED)
#  error Inconsistent values of FIRST_RESEED and RESEED_BATCH*MIN_DILUTION
#endif

/* Saturation point of extraction subttl counters; large round number: */
#define SUBTTL_SAT 1000000000000000000LL
#if SUBTTL_SAT <= RESEED_BATCH<<(FIRST_RESEED + APP_MAX)
#  error Bogus value for SUBTTL_SAT
#endif

typedef unsigned long long int ulonglong;
#if defined __SIZEOF_LONG_LONG__ && __SIZEOF_LONG_LONG__ == 8
/* This is how we expect things to be when using gcc
 * on both Intel x86_32 and Intel 64 architectures.
 * I don't know how to extrapolate to other architectures
 * or other compilers ...
 * but at least we are being clear about the assumptions being made.
 */
#else
#error Broken assumption:  __SIZEOF_LONG_LONG__ should be defined and equal to 8
#endif

#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
#define W2BYTE(X)       ((X)*4)         /* convert #words to #bytes */
#define W2BIT(X)        ((X)*32)        /* convert #words to #bits  */
#define BIT2BYTE(X)     ((X)/8)         /* convert #bits  to #bytes */
#define BYTE2BIT(X)     ((X)*8)         /* convert #bytes to #bits */

/*
 * The minimum number of bits of entropy before we wake up a read on
 * /dev/random.
 * Can be changed at runtime via /proc/.
 * The minimum value is RESEED_BATCH; enforced at runtime.
 */
static int random_read_wakeup_thresh = RESEED_BATCH;

/*
 * If the entropy count falls under this number of bits, then we
 * should wake up processes which are selecting or polling on write
 * access to /dev/random.
 */
static int random_write_wakeup_thresh = 128;

/*
 * When the input pool goes over trickle_thresh, start dropping most
 * samples to avoid wasting CPU time and reduce lock contention.
 */

static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;

static DEFINE_PER_CPU(int, trickle_count);

/*
 * A pool of size .poolwords is stirred with a primitive polynomial
 * of degree .poolwords over GF(2).  The taps for various sizes are
 * defined below.  They are chosen to be evenly spaced (minimum RMS
 * distance from evenly spaced; the numbers in the comments are a
 * scaled squared error sum) except for the last tap, which is 1 to
 * get the twisting happening as fast as possible.
 */
static struct poolinfo {
	int poolwords;
	int tap1, tap2, tap3, tap4, tap5;
} poolinfo_table[] = {
	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ 128,	103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ 32,	26,	20,	14,	7,	1 },
#if 0
	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
	{ 2048,	1638,	1231,	819,	411,	1 },

	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
	{ 1024,	817,	615,	412,	204,	1 },

	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
	{ 1024,	819,	616,	410,	207,	2 },

	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
	{ 512,	411,	308,	208,	104,	1 },

	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
	{ 512,	409,	307,	206,	102,	2 },
	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
	{ 512,	409,	309,	205,	103,	2 },

	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
	{ 256,	205,	155,	101,	52,	1 },

	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
	{ 128,	103,	78,	51,	27,	2 },

	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
	{ 64,	52,	39,	26,	14,	1 },
#endif
};

#define POOLBITS	poolwords*32
#define POOLBYTES	poolwords*4

/*
 * For the purposes of better mixing, we use the CRC-32 polynomial as
 * well to make a twisted Generalized Feedback Shift Reigster
 *
 * (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators.  ACM
 * Transactions on Modeling and Computer Simulation 2(3):179-194.
 * Also see M. Matsumoto & Y. Kurita, 1994.  Twisted GFSR generators
 * II.  ACM Transactions on Mdeling and Computer Simulation 4:254-266)
 *
 * Thanks to Colin Plumb for suggesting this.
 *
 * We have not analyzed the resultant polynomial to prove it primitive;
 * in fact it almost certainly isn't.  Nonetheless, the irreducible factors
 * of a random large-degree polynomial over GF(2) are more than large enough
 * that periodicity is not a concern.

 * The input hash is much less sensitive than the output hash.  All
 * that we want of it is that it be a good hash in the sense that it
 * not produce collisions when fed "random" data of the sort we expect
 * to see.  It need not be a cryptographically-strong hash.  As long
 * as the pool state differs for different inputs, we have preserved
 * the input entropy and done a good job.  The fact that an
 * intelligent attacker can construct inputs that will produce
 * controlled alterations to the pool's state is not important because
 * we don't consider such inputs to contribute any randomness.  The
 * only property we need with respect to them is that the attacker
 * can't increase his/her knowledge of the pool's state.  Since all
 * additions are reversible (knowing the final state and the input,
 * you can reconstruct the initial state), if an attacker has any
 * uncertainty about the initial state, he/she can only shuffle that
 * uncertainty about, but never cause any collisions (which would
 * decrease the uncertainty).

 * The chosen system lets the state of the pool be (essentially) the input
 * modulo the generator polymnomial.  Now, for random primitive polynomials,
 * this is a universal class of hash functions, meaning that the chance
 * of a collision is limited by the attacker's knowledge of the generator
 * polynomial, so if it is chosen at random, an attacker can never force
 * a collision.  Here, we use a fixed polynomial, but we *can* assume that
 * ###--> it is unknown to the processes generating the input entropy. <-###
 * Because of this important property, this is a good, collision-resistant
 * hash; hash collisions will occur no more often than chance.
 */

/*
 * Static global variables
 */
static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
static struct fasync_struct *fasync;

static bool debug = 0;
module_param(debug, bool, 0644);
#define DEBUG_ENT(fmt, arg...) do { \
	if (debug) \
		printk(KERN_DEBUG "random %04d %04d %04d: " \
		fmt,\
		input_pool.entropy_count,\
		devrand_pool.entropy_count,\
		prng_pool.entropy_count,\
		## arg); } while (0)

/**********************************************************************
 *
 * OS independent pool.   Here are the functions which handle
 * entropy storage, mixing, concentration, and PRNG counter mode.
 *
 **********************************************************************/

struct Pool {
	/* read-only data: */
	struct poolinfo *poolinfo;
	__u32 *pooldata;
	const char *name;
	struct Pool *pull;
	int blockable;

	/* read-write data: */
	spinlock_t lock;
	unsigned add_ptr;
	unsigned input_rotate;
	int entropy_count;
	int entropy_total;      /* entropy input; used only during initialization */
        ulonglong extracted_subttl;
        ulonglong extracted_total;
	unsigned int initialized:1;
	bool last_data_init;
	__u8 last_data[EXTRACT_SIZE];
};

static __u32 input_pool_data[INPUT_POOL_WORDS];
static __u32 prng_pool_data[OUTPUT_POOL_WORDS];

static struct Pool input_pool = {
	.poolinfo = &poolinfo_table[0],
	.name = "input",
	.blockable = 1,
	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
        .entropy_count = -10,
	.pooldata = input_pool_data
};

#define devrand_pool input_pool

static struct Pool prng_pool = {
	.poolinfo = &poolinfo_table[1],
	.name = "nonblocking",
	.pull = &input_pool,
	.lock = __SPIN_LOCK_UNLOCKED(prng_pool.lock),
	.pooldata = prng_pool_data
};

static __u32 const twist_table[8] = {
	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };

/*
 * This function adds bytes into the entropy "pool".  It does not
 * update the entropy estimate.  The caller should call
 * credit_entropy_bits if this is appropriate.
 *
 * The pool is stirred with a primitive polynomial of the appropriate
 * degree, and then twisted.  We twist by three bits at a time because
 * it's cheap to do so and helps slightly in the expected case where
 * the entropy is concentrated in the low-order bits.
 */
static void _mix_pool_bytes(struct Pool *r, const void *in,
			    int nbytes, __u8 out[64])
{
	unsigned long i, j, tap1, tap2, tap3, tap4, tap5;
	int input_rotate;
	int wordmask = r->poolinfo->poolwords - 1;
	const char *bytes = in;
	__u32 w;

	tap1 = r->poolinfo->tap1;
	tap2 = r->poolinfo->tap2;
	tap3 = r->poolinfo->tap3;
	tap4 = r->poolinfo->tap4;
	tap5 = r->poolinfo->tap5;

	smp_rmb();
	input_rotate = ACCESS_ONCE(r->input_rotate);
	i = ACCESS_ONCE(r->add_ptr);

	/* mix one byte at a time to simplify size handling and churn faster */
	while (nbytes--) {
		w = rol32(*bytes++, input_rotate & 31);
		i = (i - 1) & wordmask;

		/* XOR in the various taps */
		w ^= r->pooldata[i];
		w ^= r->pooldata[(i + tap1) & wordmask];
		w ^= r->pooldata[(i + tap2) & wordmask];
		w ^= r->pooldata[(i + tap3) & wordmask];
		w ^= r->pooldata[(i + tap4) & wordmask];
		w ^= r->pooldata[(i + tap5) & wordmask];

		/* Mix the result back in with a twist */
		r->pooldata[i] = (w >> 3) ^ twist_table[w & 7];

		/*
		 * Normally, we add 7 bits of rotation to the pool.
		 * At the beginning of the pool, add an extra 7 bits
		 * rotation, so that successive passes spread the
		 * input bits across the pool evenly.
		 */
		input_rotate += i ? 7 : 14;
	}

	ACCESS_ONCE(r->input_rotate) = input_rotate;
	ACCESS_ONCE(r->add_ptr) = i;
	smp_wmb();

	if (out)
		for (j = 0; j < 16; j++)
			((__u32 *)out)[j] = r->pooldata[(i - j) & wordmask];
}

static void __mix_pool_bytes(struct Pool *r, const void *in,
			     int nbytes, __u8 out[64])
{
	trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
	_mix_pool_bytes(r, in, nbytes, out);
}

static void mix_pool_bytes(struct Pool *r, const void *in,
			   int nbytes, __u8 out[64])
{
	unsigned long flags;

	trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
	spin_lock_irqsave(&r->lock, flags);
	_mix_pool_bytes(r, in, nbytes, out);
	spin_unlock_irqrestore(&r->lock, flags);
}

struct fast_pool {
	__u32		pooldata[4];
	unsigned long	last;
	unsigned short	count;
	unsigned char	rotate;
	unsigned char	last_timer_intr;
};

/*
 * This is a fast mixing routine used by the interrupt randomness
 * collector.  It's hardcoded for an 128 bit pool and assumes that any
 * locks that might be needed are taken by the caller.
 */
static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
{
	const char	*bytes = in;
	__u32		w;
	unsigned	i = f->count;
	unsigned	input_rotate = f->rotate;

	while (nbytes--) {
		w = rol32(*bytes++, input_rotate & 31) ^ f->pooldata[i & 3] ^
			f->pooldata[(i + 1) & 3];
		f->pooldata[i & 3] = (w >> 3) ^ twist_table[w & 7];
		input_rotate += (i++ & 3) ? 7 : 14;
	}
	f->count = i;
	f->rotate = input_rotate;
}

/*
 * Credit the pool with n bits of entropy.
 * Normally n is positive.
 * Sufficiently large n will wake up a blocked reader.
 * Negative n values are allowed, but the resulting behavior
 * might not be what you wanted.
 */
static void credit_entropy_bits(struct Pool *r, int nbits)
{
	int entropy_count, orig;

	if (!nbits)
		return;

	DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name);
retry:
	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
	entropy_count += nbits;

	if (entropy_count < 0) {
		DEBUG_ENT("negative entropy/overflow\n");
		entropy_count = 0;
	} else if (entropy_count > r->poolinfo->POOLBITS)
		entropy_count = r->poolinfo->POOLBITS;
	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
		goto retry;

	if (!r->initialized && nbits > 0) {
		r->entropy_total += nbits;
		if (r->entropy_total > 128)
			r->initialized = 1;
	}

	trace_credit_entropy_bits(r->name, nbits, entropy_count,
				  r->entropy_total, _RET_IP_);

	/* should we wake readers? */
	if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {
		wake_up_interruptible(&random_read_wait);
		kill_fasync(&fasync, SIGIO, POLL_IN);
	}
}

/*********************************************************************
 *
 * Entropy input management
 *
 *********************************************************************/

/* There is one of these per entropy source */
struct timer_rand_state {
	cycles_t last_time;
	long last_delta, last_delta2;
	unsigned dont_count_entropy:1;
};

/*
 * Add device- or boot-specific data to the input and nonblocking
 * pools to help initialize them to unique values.
 *
 * None of this adds any entropy, it is meant to avoid the
 * problem of the prng pool having similar initial state
 * across largely identical devices.
 */
void add_device_randomness(const void *buf, unsigned int size)
{
	unsigned long time = get_cycles() ^ jiffies;

	mix_pool_bytes(&input_pool, buf, size, NULL);
	mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
	mix_pool_bytes(&prng_pool, buf, size, NULL);
	mix_pool_bytes(&prng_pool, &time, sizeof(time), NULL);
}
EXPORT_SYMBOL(add_device_randomness);

static struct timer_rand_state input_timer_state;

/*
 * This function adds entropy to the input pool by using timing
 * delays.  It uses the timer_rand_state structure to make an estimate
 * of how many bits of entropy this call has added to the pool.
 *
 * The number "num" is also added to the pool - it should somehow describe
 * the type of event which just happened.  This is currently 0-255 for
 * keyboard scan codes, and 256 upwards for interrupts.
 *
 */
static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
{
	struct {
		long jiffies;
		unsigned cycles;
		unsigned num;
	} sample;
	long delta, delta2, delta3;

	preempt_disable();
	/* if over the trickle threshold, use only 1 in 4096 samples */
	if (input_pool.entropy_count > trickle_thresh &&
	    ((__this_cpu_inc_return(trickle_count) - 1) & 0xfff))
		goto out;

	sample.jiffies = jiffies;
	sample.cycles = get_cycles();
	sample.num = num;
	mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL);

	/*
	 * Calculate number of bits of randomness we probably added.
	 * We take into account the first, second and third-order deltas
	 * in order to make our estimate.
	 */

	if (!state->dont_count_entropy) {
		delta = sample.jiffies - state->last_time;
		state->last_time = sample.jiffies;

		delta2 = delta - state->last_delta;
		state->last_delta = delta;

		delta3 = delta2 - state->last_delta2;
		state->last_delta2 = delta2;

		if (delta < 0)
			delta = -delta;
		if (delta2 < 0)
			delta2 = -delta2;
		if (delta3 < 0)
			delta3 = -delta3;
		if (delta > delta2)
			delta = delta2;
		if (delta > delta3)
			delta = delta3;

		/*
		 * delta is now minimum absolute delta.
		 * Round down by 1 bit on general principles,
		 * and limit entropy entimate to 12 bits.
		 */
		credit_entropy_bits(&input_pool,
				    min_t(int, fls(delta>>1), 11));
	}
out:
	preempt_enable();
}

void add_input_randomness(unsigned int type, unsigned int code,
				 unsigned int value)
{
	static unsigned char last_value;

	/* ignore autorepeat and the like */
	if (value == last_value)
		return;

	DEBUG_ENT("input event\n");
	last_value = value;
	add_timer_randomness(&input_timer_state,
			     (type << 4) ^ code ^ (code >> 4) ^ value);
}
EXPORT_SYMBOL_GPL(add_input_randomness);

static DEFINE_PER_CPU(struct fast_pool, irq_randomness);

void add_interrupt_randomness(int irq, int irq_flags)
{
	struct Pool	*r;
	struct fast_pool	*fast_pool = &__get_cpu_var(irq_randomness);
	struct pt_regs		*regs = get_irq_regs();
	unsigned long		now = jiffies;
	__u32			input[4], cycles = get_cycles();

	input[0] = cycles ^ jiffies;
	input[1] = irq;
	if (regs) {
		__u64 ip = instruction_pointer(regs);
		input[2] = ip;
		input[3] = ip >> 32;
	}

	fast_mix(fast_pool, input, sizeof(input));

	if ((fast_pool->count & 1023) &&
	    !time_after(now, fast_pool->last + HZ))
		return;

	fast_pool->last = now;

	r = prng_pool.initialized ? &input_pool : &prng_pool;
	__mix_pool_bytes(r, &fast_pool->pooldata, sizeof(fast_pool->pooldata), NULL);
	/*
	 * If we don't have a valid cycle counter, and we see
	 * back-to-back timer interrupts, then skip giving credit for
	 * any entropy.
	 */
	if (cycles == 0) {
		if (irq_flags & __IRQF_TIMER) {
			if (fast_pool->last_timer_intr)
				return;
			fast_pool->last_timer_intr = 1;
		} else
			fast_pool->last_timer_intr = 0;
	}
	credit_entropy_bits(r, 1);
}

#ifdef CONFIG_BLOCK
void add_disk_randomness(struct gendisk *disk)
{
	if (!disk || !disk->random)
		return;
	/* first major is 1, so we get >= 0x200 here */
	DEBUG_ENT("disk event %d:%d\n",
		  MAJOR(disk_devt(disk)), MINOR(disk_devt(disk)));

	add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
}
#endif

/*********************************************************************
 *
 * Extraction routines.

 * These routines extract bytes from the pools.  The extracted bytes
 * exhibit a random distribution, possibly "random" in the sense of
 * pseudorandom, or possibly "random" in the sense of actual entropy.
 * Since the latter is not guaranteed, please do not call them
 * "entropy" extraction routines.

 * Specifically, in the case of the PRNG, i.e. the prng pool,
 * the extracted bytes may have an entropy density that is vastly less
 * than 8 bits per byte, orders of magnitude less.

 * ********************************************************************/

/* Forward reference */
static ssize_t extract_rnd(struct Pool *r, void *buf,
			       size_t nbytes, int min, int rsvd);

/*
 * This function is responsible for filling this pool (r)
 * to an appropriate level, by pulling from the upstream
 * pool (r->pull), if any, if necessary.
 *
 * We enforce the requirement that any contribution to the
 * nonblocking PRNG be large enough to be "significant" to any attacker.
 *
 * In principle, this would cascade, pulling from other pools
 * even farther upstream, but as it stands there are only two
 * pools, so no cascade.
 *
 * It is conceivable that the caller's want_level could exceed
 * POOL_BYTES, and this would not be ridiculous.
 * Mild fixme:  Handling of this case needs more thought.
 */
static void fill_pool(
        struct Pool *r,
        size_t want_level               /* measured in BYTES */
){
	__u32 tmp[OUTPUT_POOL_WORDS];
        int rsvd = 0;                   /* measured in bits */
        int mybatch = 0;
        int txbits;
        int actual;                     /* measured in BYTES */
	if (!r->pull) return;           /* no upstream pool to pull from */
        if (r->blockable) {
#ifndef OVERCOMPLICATED
/* should never get here; devrandom pool has nowhere to pull from */
#else
/* Here if we are blockable i.e. /dev/random i.e. TRNG. */
/* How much _unfilled_ headspace is our buffer: */
                int ourhead = r->poolinfo->POOLBITS
                            - r->entropy_count;
/* Ditto for the upstream source: */
                int pullhead = r->pull->poolinfo->POOLBITS
                             - r->pull->entropy_count;
/* The more the source is unfilled, the less we can buffill */
                int buffill = BUFFILL_ZONE - pullhead;
/* Don't buffill more than needed to fill our headspace: */
                buffill = min_t(int, buffill, headspace);
/* Number of bits to transfer: */
                txbits = BYTE2BIT(want_level) - r->entropy_count;
/*
 * Transfer enough to meet the requested level,
 * or buffill with whatever is freely available,
 * whichever is more:
 */
                txbits =  max_t(int, txbits, buffill);
                if (txbits <= 0) return;        /* already have all we want */
                mybatch = rsvd = 0;
#endif
        } else {
/*
 * Here if we are non-blocking i.e. urandom i.e. PRNG.  Reserve a
 * suitable amount of entropy in the upstream source, on a sliding
 * scale based on how desperately we need to be reseeded.
 *
 * Ignore the caller's want_level.  Entropy level doesn't mean much
 * for a PRNG.  The only amount the PRNG ever requests is RESEED_BATCH.
 *
 */
         int appetite = fls64(r->extracted_subttl) - FIRST_RESEED;
          if (appetite < 0) return;      /* 128k bits maps to appetite 0 */
/* The largest rsvd that makes any sense;
 * applies when appetite=0:
 */
          rsvd = W2BIT(r->pull->poolinfo->poolwords) - RESEED_BATCH;
/* When the appetite gets to 20, rsvd goes to zero: */
          rsvd = rsvd - appetite*rsvd / APP_MAX;
          if (rsvd < 0) rsvd = 0;
/*
 * For the PRNG, make the requested batch big enough to be
 * "significant" to any attacker:
 */
          mybatch = txbits = RESEED_BATCH;
        }

        /* Don't request more than fits in our buffer: */
        txbits = min_t(int, txbits, 8*sizeof(tmp));

        DEBUG_ENT("About to reseed %s adding %d bits;"
                  "  caller want_level: %zu  prev level: %d bits\n",
                  r->name, txbits,
                  want_level * 8, r->entropy_count);
        DEBUG_ENT("Reseed batch: %d  rsvd: %d bytes\n",
                  BIT2BYTE(mybatch), BIT2BYTE(rsvd));
        if (txbits <= 0) return;         /* already full enough */

        actual = extract_rnd(r->pull, tmp, BIT2BYTE(txbits),
                BIT2BYTE(mybatch), BIT2BYTE(rsvd));
        mix_pool_bytes(r, tmp, actual, NULL);
        credit_entropy_bits(r, actual*8);
/*
 * The subtotal starts over every time we transfer a
 * sufficiently-large batch.  Super-important for PRNG;
 * probably not significant for TRNG.
 */
        if (BYTE2BIT(actual) >= RESEED_BATCH) {
          r->extracted_subttl = 0;
        }
}

/*
 * General note, applying to several of the following routines:
 *
 * The /min/ parameter specifies the minimum amount we are allowed to pull;
 *   otherwise we pull nothing.  The PRNG uses this when reseeding,
 *   to make sure the pull is "significant" to any attacker.
 *
 * The /reserved/ parameter indicates how much entropy we must leave
 *   in the pool after each pull to avoid starving other readers.
 */


/*
 * Debit the entropy estimate for pool r.
 * Usually done right before an extract_buf().
 * The return value is the amount to extract.
 */
static size_t debit(struct Pool *r, size_t nbytes, int min,
		      int reserved)
{
	unsigned long flags;
	int wakeup_write = 0;

	/* Hold lock while accounting */
	spin_lock_irqsave(&r->lock, flags);

	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
	DEBUG_ENT("trying to debit %zu bits from %s\n",
		  nbytes * 8, r->name);

	/* If there's not enough available, don't extract anything. */
	if (r->entropy_count / 8 < min + reserved) {
		nbytes = 0;
	} else {
		int entropy_count, orig;
retry:
		entropy_count = orig = ACCESS_ONCE(r->entropy_count);
		/* If blockable, never pull more than available */
		if (r->blockable && nbytes + reserved >= entropy_count / 8)
			nbytes = entropy_count/8 - reserved;

		if (entropy_count / 8 >= nbytes + reserved) {
			entropy_count -= nbytes*8;
			if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
				goto retry;
		} else {
			entropy_count = reserved;
			if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
				goto retry;
		}

		if (entropy_count < random_write_wakeup_thresh)
			wakeup_write = 1;
	}

	DEBUG_ENT("debiting %zu entropy credits from %s%s\n",
		  nbytes * 8, r->name, r->blockable ? "" : " (nonblocking)");

	spin_unlock_irqrestore(&r->lock, flags);

	if (wakeup_write) {
		wake_up_interruptible(&random_write_wait);
		kill_fasync(&fasync, SIGIO, POLL_OUT);
	}

	return nbytes;
}

/*
 * Extract randomness from the specified pool (r) and return it in a buffer.
 * Probably should always be preceded by debit(...).
 */
static void extract_buf(struct Pool *r, __u8 *out)
{
	int i;
	union {
		__u32 w[5];
		unsigned long l[LONGS(EXTRACT_SIZE)];
	} hash;
	__u32 workspace[SHA_WORKSPACE_WORDS];
	__u8 extract[64];
	unsigned long flags;

	/* Generate a hash across the pool, 16 words (512 bits) at a time */
	sha_init(hash.w);
	spin_lock_irqsave(&r->lock, flags);
	for (i = 0; i < r->poolinfo->poolwords; i += 16)
		sha_transform(hash.w, (__u8 *)(r->pooldata + i), workspace);

	/*
	 * We mix the hash back into the pool to prevent backtracking
	 * attacks (where the attacker knows the state of the pool
	 * plus the current outputs, and attempts to find previous
	 * ouputs), unless the hash function can be inverted. By
	 * mixing at least a SHA1 worth of hash data back, we make
	 * brute-forcing the feedback as hard as brute-forcing the
	 * hash.
	 */
	__mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
	spin_unlock_irqrestore(&r->lock, flags);

	/*
	 * To avoid duplicates, we atomically extract a portion of the
	 * pool while mixing, and hash one final time.
	 */
	sha_transform(hash.w, extract, workspace);
	memset(extract, 0, sizeof(extract));
	memset(workspace, 0, sizeof(workspace));

	/*
	 * In case the hash function has some recognizable output
	 * pattern, we fold it in half. Thus, we always feed back
	 * twice as much data as we output.
	 */
	hash.w[0] ^= hash.w[3];
	hash.w[1] ^= hash.w[4];
	hash.w[2] ^= rol32(hash.w[2], 16);

	/*
	 * If we have a architectural hardware random number
	 * generator, mix that in, too.
	 */
	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
		unsigned long v;
		if (!arch_get_random_long(&v))
			break;
		hash.l[i] ^= v;
	}

	memcpy(out, &hash, EXTRACT_SIZE);
	memset(&hash, 0, sizeof(hash));
}

/*
 * Note: Here we assume that .poolwords is a multiple of 16 words.
 *
 * We return the actual number of bytes extracted.
 */
static ssize_t extract_rnd(struct Pool *r, void *buf,
				 size_t txbytes, int min, int reserved)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];
	unsigned long flags;

	/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
	if (fips_enabled) {
		spin_lock_irqsave(&r->lock, flags);
		if (!r->last_data_init) {
			r->last_data_init = true;
			spin_unlock_irqrestore(&r->lock, flags);
			trace_extract_rnd(r->name, EXTRACT_SIZE,
					      r->entropy_count, _RET_IP_);
			fill_pool(r, EXTRACT_SIZE);
/* FIXME: */
/* why is there no debit() associated with this extract_buf()? */
			extract_buf(r, tmp);
			spin_lock_irqsave(&r->lock, flags);
			memcpy(r->last_data, tmp, EXTRACT_SIZE);
		}
		spin_unlock_irqrestore(&r->lock, flags);
	}

	trace_extract_rnd(r->name, txbytes, r->entropy_count, _RET_IP_);
/*
 * We want our pool (r) to have enough entropy, if possible.
 * So pull it up to a level (txbits) that will cover the
 * extraction we are about to do.
 */
	fill_pool(r, txbytes);
/* This pool (r) has already been credited for the fill-in we just did. */

/* Debit this pool for the extraction we are about to do. */
	txbytes = debit(r, txbytes, min, reserved);
	while (txbytes) {
		extract_buf(r, tmp);

		if (fips_enabled) {
			spin_lock_irqsave(&r->lock, flags);
			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
				panic("Hardware RNG duplicated output!\n");
			memcpy(r->last_data, tmp, EXTRACT_SIZE);
			spin_unlock_irqrestore(&r->lock, flags);
		}
		i = min_t(int, txbytes, EXTRACT_SIZE);
		memcpy(buf, tmp, i);
		txbytes -= i;
		buf += i;
		ret += i;
	}

	/* Wipe data just returned from memory */
	memset(tmp, 0, sizeof(tmp));

        if (ret > 0) {
/* Subttl does not overflow; it saturates at a user-friendly round number: */
                r->extracted_subttl += BYTE2BIT(ret);
                if (r->extracted_subttl > SUBTTL_SAT)
                        r->extracted_subttl = SUBTTL_SAT;
/* Total does not saturate;  it just overflows and wraps around. */
                r->extracted_total  += BYTE2BIT(ret);
        }
	return ret;
}

static ssize_t extract_rnd_user(struct Pool *r, void __user *buf,
				    size_t nbytes)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];

	trace_extract_rnd_user(r->name, nbytes, r->entropy_count, _RET_IP_);
	fill_pool(r, nbytes);

/* Debit the estimate, according to the extraction we are about to do: */
	nbytes = debit(r, nbytes, 0, 0);

	while (nbytes) {
		if (need_resched()) {
			if (signal_pending(current)) {
				if (ret == 0)
					ret = -ERESTARTSYS;
				break;
			}
			schedule();
		}

		extract_buf(r, tmp);
		i = min_t(int, nbytes, EXTRACT_SIZE);
		if (copy_to_user(buf, tmp, i)) {
			ret = -EFAULT;
			break;
		}

		nbytes -= i;
		buf += i;
		ret += i;
	}

	/* Wipe data just returned from memory */
	memset(tmp, 0, sizeof(tmp));

        if (ret > 0) {
                r->extracted_subttl += BYTE2BIT(ret);
                r->extracted_total  += BYTE2BIT(ret);
        }
	return ret;
}

/*
 * This function is the exported kernel interface.  It returns some
 * number of good pseudorandomly distributed numbers, suitable for key
 * generation, seeding TCP sequence numbers, etc.  It does not use the
 * hw random number generator, if available; use
 * get_random_bytes_arch() for that.
 */
void get_random_bytes(void *buf, int nbytes)
{
	extract_rnd(&prng_pool, buf, nbytes, 0, 0);
}
EXPORT_SYMBOL(get_random_bytes);

/*
 * This function will use the architecture-specific hardware random
 * number generator if it is available.  The arch-specific hw RNG will
 * almost certainly be faster than what we can do in software, but it
 * is impossible to verify that it is implemented securely (as
 * opposed, to, say, the AES encryption of a sequence number using a
 * key known by the NSA).  So it's useful if we need the speed, but
 * only if we're willing to trust the hardware manufacturer not to
 * have put in a back door.
 */
void get_random_bytes_arch(void *buf, int nbytes)
{
	char *p = buf;

	trace_get_random_bytes(nbytes, _RET_IP_);
	while (nbytes) {
		unsigned long v;
		int chunk = min(nbytes, (int)sizeof(unsigned long));

		if (!arch_get_random_long(&v))
			break;

		memcpy(p, &v, chunk);
		p += chunk;
		nbytes -= chunk;
	}

	if (nbytes)
		extract_rnd(&prng_pool, p, nbytes, 0, 0);
}
EXPORT_SYMBOL(get_random_bytes_arch);


/*
 * init_std_data - initialize pool with system data
 *
 * @r: pool to initialize
 *
 * This function clears the pool's entropy count and mixes some system
 * data into the pool to prepare it for use. The pool is not cleared
 * as that can only decrease the entropy in the pool.
 */
static void init_std_data(struct Pool *r)
{
	int i;
	ktime_t now = ktime_get_real();
	unsigned long rv;

	r->entropy_count = 0;
	r->entropy_total = 0;
	r->extracted_subttl = 0;
	r->extracted_total = 0;
	r->last_data_init = false;
	mix_pool_bytes(r, &now, sizeof(now), NULL);
	for (i = r->poolinfo->POOLBYTES; i > 0; i -= sizeof(rv)) {
		if (!arch_get_random_long(&rv))
			break;
		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
	}
	mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
}

/*
 * Note that setup_arch() may call add_device_randomness()
 * long before we get here. This allows seeding of the pools
 * with some platform dependent data very early in the boot
 * process. But it limits our options here. We must use
 * statically allocated structures that already have all
 * initializations complete at compile time. We should also
 * take care not to overwrite the precious per platform data
 * we were given.
 */
static int rand_initialize(void)
{
	init_std_data(&input_pool);
	init_std_data(&devrand_pool);
	init_std_data(&prng_pool);
	return 0;
}
module_init(rand_initialize);

#ifdef CONFIG_BLOCK
void rand_initialize_disk(struct gendisk *disk)
{
	struct timer_rand_state *state;

	/*
	 * If kzalloc returns null, we just won't use that entropy
	 * source.
	 */
	state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
	if (state)
		disk->random = state;
}
#endif

/*
 * Interface used by the actual /dev/random.
 *
 * This is the only place where the process can block.
 * It blocks if /dev/random wants to read more bits than are available.
 */
static ssize_t
random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
{
	ssize_t n, retval = 0, count = 0;

	if (nbytes == 0){
		return 0;
        }

	while (nbytes > 0) {
		n = nbytes;
		if (n > SEC_XFER_SIZE)
			n = SEC_XFER_SIZE;

		DEBUG_ENT("reading %zu bits\n", n*8);

		n = extract_rnd_user(&devrand_pool, buf, n);

		if (n < 0) {
			retval = n;
			break;
		}

		DEBUG_ENT("read got %zd bits (%zd still needed)\n",
			  n*8, (nbytes-n)*8);

		if (n == 0) {
			if (file->f_flags & O_NONBLOCK) {
				retval = -EAGAIN;
				break;
			}

			DEBUG_ENT("sleeping?\n");

			wait_event_interruptible(random_read_wait,
				input_pool.entropy_count >=
						 random_read_wakeup_thresh);

			DEBUG_ENT("awake\n");

			if (signal_pending(current)) {
				retval = -ERESTARTSYS;
				break;
			}

			continue;
		}

		count += n;
		buf += n;
		nbytes -= n;
		break;		/* This break makes the device work */
				/* like a named pipe */
	}

	return (count ? count : retval);
}

static ssize_t
urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
{
	return extract_rnd_user(&prng_pool, buf, nbytes);
}

static unsigned int
random_poll(struct file *file, poll_table * wait)
{
	unsigned int mask;

	poll_wait(file, &random_read_wait, wait);
	poll_wait(file, &random_write_wait, wait);
	mask = 0;
	if (input_pool.entropy_count >= random_read_wakeup_thresh)
		mask |= POLLIN | POLLRDNORM;
	if (input_pool.entropy_count < random_write_wakeup_thresh)
		mask |= POLLOUT | POLLWRNORM;
	return mask;
}

static int
write_pool(struct Pool *r, const char __user *buffer, size_t count)
{
	size_t bytes;
	__u32 buf[16];
	const char __user *p = buffer;

	while (count > 0) {
		bytes = min(count, sizeof(buf));
		if (copy_from_user(&buf, p, bytes))
			return -EFAULT;

		count -= bytes;
		p += bytes;

		mix_pool_bytes(r, buf, bytes, NULL);
		cond_resched();
	}

	return 0;
}

static ssize_t random_write(struct file *file, const char __user *buffer,
			    size_t count, loff_t *ppos)
{
	size_t ret;

	ret = write_pool(&devrand_pool, buffer, count);
	if (ret)
		return ret;     /* some error */
	ret = write_pool(&prng_pool, buffer, count);
	if (ret)
		return ret;     /* some error */

	return (ssize_t)count;
}

static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
{
	int size, ent_count;
	int __user *p = (int __user *)arg;
	int retval;

	switch (cmd) {
	case RNDGETENTCNT:
		/* inherently racy, no point locking */
		if (put_user(input_pool.entropy_count, p))
			return -EFAULT;
		return 0;
	case RNDADDTOENTCNT:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p))
			return -EFAULT;
		credit_entropy_bits(&input_pool, ent_count);
		return 0;
	case RNDADDENTROPY:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p++))
			return -EFAULT;
		if (ent_count < 0)
			return -EINVAL;
		if (get_user(size, p++))
			return -EFAULT;
		retval = write_pool(&input_pool, (const char __user *)p,
				    size);
		if (retval < 0)
			return retval;
		credit_entropy_bits(&input_pool, ent_count);
		return 0;
	case RNDZAPENTCNT:
	case RNDCLEARPOOL:
		/* Clear the entropy estimates. */
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		rand_initialize();
		return 0;
	default:
		return -EINVAL;
	}
}

static int random_fasync(int fd, struct file *filp, int on)
{
	return fasync_helper(fd, filp, on, &fasync);
}

const struct file_operations random_fops = {
	.read  = random_read,
	.write = random_write,
	.poll  = random_poll,
	.unlocked_ioctl = random_ioctl,
	.fasync = random_fasync,
	.llseek = noop_llseek,
};

const struct file_operations urandom_fops = {
	.read  = urandom_read,
	.write = random_write,
	.unlocked_ioctl = random_ioctl,
	.fasync = random_fasync,
	.llseek = noop_llseek,
};

/***************************************************************
 * Random UUID interface
 *
 * Used here for a Boot ID, but can be useful for other kernel
 * drivers.
 ***************************************************************/

/*
 * Generate randomly-distributed UUID
 */
void generate_random_uuid(unsigned char uuid_out[16])
{
	get_random_bytes(uuid_out, 16);
	/* Set UUID version to 4 --- truly random generation */
	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
	/* Set the UUID variant to DCE */
	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
}
EXPORT_SYMBOL(generate_random_uuid);

/********************************************************************
 *
 * Sysctl interface
 *
 ********************************************************************/

#ifdef CONFIG_SYSCTL

#include <linux/sysctl.h>

static int min_read_thresh = RESEED_BATCH;
static int min_write_thresh;            /* shouldn't this have a value? */
static int max_read_thresh = INPUT_POOL_WORDS * 32;
static int max_write_thresh = INPUT_POOL_WORDS * 32;
static char sysctl_bootid[16];

/*
 * These functions is used to return both the bootid UUID, and random
 * UUID.  The difference is in whether table->data is NULL; if it is,
 * then a new UUID is generated and returned to the user.
 *
 * If the user accesses this via the proc interface, it will be returned
 * as an ASCII string in the standard UUID format.  If accesses via the
 * sysctl system call, it is returned as 16 bytes of binary data.
 */
static int proc_do_uuid(struct ctl_table *table, int write,
			void __user *buffer, size_t *lenp, loff_t *ppos)
{
	struct ctl_table fake_table;
	unsigned char buf[64], tmp_uuid[16], *uuid;

	uuid = table->data;
	if (!uuid) {
		uuid = tmp_uuid;
		generate_random_uuid(uuid);
	} else {
		static DEFINE_SPINLOCK(bootid_spinlock);

		spin_lock(&bootid_spinlock);
		if (!uuid[8])
			generate_random_uuid(uuid);
		spin_unlock(&bootid_spinlock);
	}

	sprintf(buf, "%pU", uuid);

	fake_table.data = buf;
	fake_table.maxlen = sizeof(buf);

	return proc_dostring(&fake_table, write, buffer, lenp, ppos);
}

static int total_entropy_count;
static int sum_entropy_count(struct ctl_table *table, int write,
			void __user *buffer, size_t *lenp, loff_t *ppos){
        total_entropy_count = input_pool.entropy_count;
	return proc_dointvec(table, write, buffer, lenp, ppos);
}

static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
extern struct ctl_table random_table[];
struct ctl_table random_table[] = {
	{
		.procname	= "poolsize",
		.data		= &sysctl_poolsize,
		.maxlen		= sizeof(int),
		.mode		= 0444,
		.proc_handler	= proc_dointvec,
	},
	{
		.procname	= "entropy_avail",
		.maxlen		= sizeof(int),
		.mode		= 0444,
		.proc_handler	= sum_entropy_count,
		.data		= &total_entropy_count,
	},
	{
		.procname	= "read_wakeup_threshold",
		.data		= &random_read_wakeup_thresh,
		.maxlen		= sizeof(int),
		.mode		= 0644,
		.proc_handler	= proc_dointvec_minmax,
		.extra1		= &min_read_thresh,
		.extra2		= &max_read_thresh,
	},
	{
		.procname	= "write_wakeup_threshold",
		.data		= &random_write_wakeup_thresh,
		.maxlen		= sizeof(int),
		.mode		= 0644,
		.proc_handler	= proc_dointvec_minmax,
		.extra1		= &min_write_thresh,
		.extra2		= &max_write_thresh,
	},
	{
		.procname	= "boot_id",
		.data		= &sysctl_bootid,
		.maxlen		= 16,
		.mode		= 0444,
		.proc_handler	= proc_do_uuid,
	},
	{
		.procname	= "uuid",
		.maxlen		= 16,
		.mode		= 0444,
		.proc_handler	= proc_do_uuid,
	},
	{ }
};
#endif 	/* CONFIG_SYSCTL */

static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;

static int __init random_int_secret_init(void)
{
	get_random_bytes(random_int_secret, sizeof(random_int_secret));
	return 0;
}
late_initcall(random_int_secret_init);

/*
 * Get a word from a random distribution, for internal kernel use
 * only. Similar to urandom but with the goal of minimal consumption
 * of entropy.  As a result, the random distribution is not
 * cryptographically secure but for several uses the cost of depleting
 * entropy is too high.

 * Presumably no longer needed, now that /dev/urandom
 * no longer consumes entropy so rapaciously.
 */
static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
unsigned int get_random_int(void)
{
	__u32 *hash;
	unsigned int ret;

	if (arch_get_random_int(&ret))
		return ret;

	hash = get_cpu_var(get_random_int_hash);

	hash[0] += current->pid + jiffies + get_cycles();
	md5_transform(hash, random_int_secret);
	ret = hash[0];
	put_cpu_var(get_random_int_hash);

	return ret;
}
EXPORT_SYMBOL(get_random_int);

/*
 * randomize_range() returns a start address such that
 *
 *    [...... <range> .....]
 *  start                  end
 *
 * a <range> with size "len" starting at the return value is inside in the
 * area defined by [start, end], but is otherwise randomized.
 */
unsigned long
randomize_range(unsigned long start, unsigned long end, unsigned long len)
{
	unsigned long range = end - len - start;

	if (end <= start + len)
		return 0;
	return PAGE_ALIGN(get_random_int() % range + start);
}