xref: /linux/drivers/char/random.c (revision 5eb10d912ea0add5c15b0df1920ddd1681f0c9fb)
11da177e4SLinus Torvalds /*
21da177e4SLinus Torvalds  * random.c -- A strong random number generator
31da177e4SLinus Torvalds  *
49e95ce27SMatt Mackall  * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
51da177e4SLinus Torvalds  *
61da177e4SLinus Torvalds  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
71da177e4SLinus Torvalds  * rights reserved.
81da177e4SLinus Torvalds  *
91da177e4SLinus Torvalds  * Redistribution and use in source and binary forms, with or without
101da177e4SLinus Torvalds  * modification, are permitted provided that the following conditions
111da177e4SLinus Torvalds  * are met:
121da177e4SLinus Torvalds  * 1. Redistributions of source code must retain the above copyright
131da177e4SLinus Torvalds  *    notice, and the entire permission notice in its entirety,
141da177e4SLinus Torvalds  *    including the disclaimer of warranties.
151da177e4SLinus Torvalds  * 2. Redistributions in binary form must reproduce the above copyright
161da177e4SLinus Torvalds  *    notice, this list of conditions and the following disclaimer in the
171da177e4SLinus Torvalds  *    documentation and/or other materials provided with the distribution.
181da177e4SLinus Torvalds  * 3. The name of the author may not be used to endorse or promote
191da177e4SLinus Torvalds  *    products derived from this software without specific prior
201da177e4SLinus Torvalds  *    written permission.
211da177e4SLinus Torvalds  *
221da177e4SLinus Torvalds  * ALTERNATIVELY, this product may be distributed under the terms of
231da177e4SLinus Torvalds  * the GNU General Public License, in which case the provisions of the GPL are
241da177e4SLinus Torvalds  * required INSTEAD OF the above restrictions.  (This clause is
251da177e4SLinus Torvalds  * necessary due to a potential bad interaction between the GPL and
261da177e4SLinus Torvalds  * the restrictions contained in a BSD-style copyright.)
271da177e4SLinus Torvalds  *
281da177e4SLinus Torvalds  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
291da177e4SLinus Torvalds  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
301da177e4SLinus Torvalds  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
311da177e4SLinus Torvalds  * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
321da177e4SLinus Torvalds  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
331da177e4SLinus Torvalds  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
341da177e4SLinus Torvalds  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
351da177e4SLinus Torvalds  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
361da177e4SLinus Torvalds  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
371da177e4SLinus Torvalds  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
381da177e4SLinus Torvalds  * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
391da177e4SLinus Torvalds  * DAMAGE.
401da177e4SLinus Torvalds  */
411da177e4SLinus Torvalds 
421da177e4SLinus Torvalds /*
431da177e4SLinus Torvalds  * (now, with legal B.S. out of the way.....)
441da177e4SLinus Torvalds  *
451da177e4SLinus Torvalds  * This routine gathers environmental noise from device drivers, etc.,
461da177e4SLinus Torvalds  * and returns good random numbers, suitable for cryptographic use.
471da177e4SLinus Torvalds  * Besides the obvious cryptographic uses, these numbers are also good
481da177e4SLinus Torvalds  * for seeding TCP sequence numbers, and other places where it is
491da177e4SLinus Torvalds  * desirable to have numbers which are not only random, but hard to
501da177e4SLinus Torvalds  * predict by an attacker.
511da177e4SLinus Torvalds  *
521da177e4SLinus Torvalds  * Theory of operation
531da177e4SLinus Torvalds  * ===================
541da177e4SLinus Torvalds  *
551da177e4SLinus Torvalds  * Computers are very predictable devices.  Hence it is extremely hard
561da177e4SLinus Torvalds  * to produce truly random numbers on a computer --- as opposed to
571da177e4SLinus Torvalds  * pseudo-random numbers, which can easily generated by using a
581da177e4SLinus Torvalds  * algorithm.  Unfortunately, it is very easy for attackers to guess
591da177e4SLinus Torvalds  * the sequence of pseudo-random number generators, and for some
601da177e4SLinus Torvalds  * applications this is not acceptable.  So instead, we must try to
611da177e4SLinus Torvalds  * gather "environmental noise" from the computer's environment, which
621da177e4SLinus Torvalds  * must be hard for outside attackers to observe, and use that to
631da177e4SLinus Torvalds  * generate random numbers.  In a Unix environment, this is best done
641da177e4SLinus Torvalds  * from inside the kernel.
651da177e4SLinus Torvalds  *
661da177e4SLinus Torvalds  * Sources of randomness from the environment include inter-keyboard
671da177e4SLinus Torvalds  * timings, inter-interrupt timings from some interrupts, and other
681da177e4SLinus Torvalds  * events which are both (a) non-deterministic and (b) hard for an
691da177e4SLinus Torvalds  * outside observer to measure.  Randomness from these sources are
701da177e4SLinus Torvalds  * added to an "entropy pool", which is mixed using a CRC-like function.
711da177e4SLinus Torvalds  * This is not cryptographically strong, but it is adequate assuming
721da177e4SLinus Torvalds  * the randomness is not chosen maliciously, and it is fast enough that
731da177e4SLinus Torvalds  * the overhead of doing it on every interrupt is very reasonable.
741da177e4SLinus Torvalds  * As random bytes are mixed into the entropy pool, the routines keep
751da177e4SLinus Torvalds  * an *estimate* of how many bits of randomness have been stored into
761da177e4SLinus Torvalds  * the random number generator's internal state.
771da177e4SLinus Torvalds  *
781da177e4SLinus Torvalds  * When random bytes are desired, they are obtained by taking the SHA
791da177e4SLinus Torvalds  * hash of the contents of the "entropy pool".  The SHA hash avoids
801da177e4SLinus Torvalds  * exposing the internal state of the entropy pool.  It is believed to
811da177e4SLinus Torvalds  * be computationally infeasible to derive any useful information
821da177e4SLinus Torvalds  * about the input of SHA from its output.  Even if it is possible to
831da177e4SLinus Torvalds  * analyze SHA in some clever way, as long as the amount of data
841da177e4SLinus Torvalds  * returned from the generator is less than the inherent entropy in
851da177e4SLinus Torvalds  * the pool, the output data is totally unpredictable.  For this
861da177e4SLinus Torvalds  * reason, the routine decreases its internal estimate of how many
871da177e4SLinus Torvalds  * bits of "true randomness" are contained in the entropy pool as it
881da177e4SLinus Torvalds  * outputs random numbers.
891da177e4SLinus Torvalds  *
901da177e4SLinus Torvalds  * If this estimate goes to zero, the routine can still generate
911da177e4SLinus Torvalds  * random numbers; however, an attacker may (at least in theory) be
921da177e4SLinus Torvalds  * able to infer the future output of the generator from prior
931da177e4SLinus Torvalds  * outputs.  This requires successful cryptanalysis of SHA, which is
941da177e4SLinus Torvalds  * not believed to be feasible, but there is a remote possibility.
951da177e4SLinus Torvalds  * Nonetheless, these numbers should be useful for the vast majority
961da177e4SLinus Torvalds  * of purposes.
971da177e4SLinus Torvalds  *
981da177e4SLinus Torvalds  * Exported interfaces ---- output
991da177e4SLinus Torvalds  * ===============================
1001da177e4SLinus Torvalds  *
1011da177e4SLinus Torvalds  * There are three exported interfaces; the first is one designed to
1021da177e4SLinus Torvalds  * be used from within the kernel:
1031da177e4SLinus Torvalds  *
1041da177e4SLinus Torvalds  * 	void get_random_bytes(void *buf, int nbytes);
1051da177e4SLinus Torvalds  *
1061da177e4SLinus Torvalds  * This interface will return the requested number of random bytes,
1071da177e4SLinus Torvalds  * and place it in the requested buffer.
1081da177e4SLinus Torvalds  *
1091da177e4SLinus Torvalds  * The two other interfaces are two character devices /dev/random and
1101da177e4SLinus Torvalds  * /dev/urandom.  /dev/random is suitable for use when very high
1111da177e4SLinus Torvalds  * quality randomness is desired (for example, for key generation or
1121da177e4SLinus Torvalds  * one-time pads), as it will only return a maximum of the number of
1131da177e4SLinus Torvalds  * bits of randomness (as estimated by the random number generator)
1141da177e4SLinus Torvalds  * contained in the entropy pool.
1151da177e4SLinus Torvalds  *
1161da177e4SLinus Torvalds  * The /dev/urandom device does not have this limit, and will return
1171da177e4SLinus Torvalds  * as many bytes as are requested.  As more and more random bytes are
1181da177e4SLinus Torvalds  * requested without giving time for the entropy pool to recharge,
1191da177e4SLinus Torvalds  * this will result in random numbers that are merely cryptographically
1201da177e4SLinus Torvalds  * strong.  For many applications, however, this is acceptable.
1211da177e4SLinus Torvalds  *
1221da177e4SLinus Torvalds  * Exported interfaces ---- input
1231da177e4SLinus Torvalds  * ==============================
1241da177e4SLinus Torvalds  *
1251da177e4SLinus Torvalds  * The current exported interfaces for gathering environmental noise
1261da177e4SLinus Torvalds  * from the devices are:
1271da177e4SLinus Torvalds  *
128a2080a67SLinus Torvalds  *	void add_device_randomness(const void *buf, unsigned int size);
1291da177e4SLinus Torvalds  * 	void add_input_randomness(unsigned int type, unsigned int code,
1301da177e4SLinus Torvalds  *                                unsigned int value);
131775f4b29STheodore Ts'o  *	void add_interrupt_randomness(int irq, int irq_flags);
132442a4fffSJarod Wilson  * 	void add_disk_randomness(struct gendisk *disk);
1331da177e4SLinus Torvalds  *
134a2080a67SLinus Torvalds  * add_device_randomness() is for adding data to the random pool that
135a2080a67SLinus Torvalds  * is likely to differ between two devices (or possibly even per boot).
136a2080a67SLinus Torvalds  * This would be things like MAC addresses or serial numbers, or the
137a2080a67SLinus Torvalds  * read-out of the RTC. This does *not* add any actual entropy to the
138a2080a67SLinus Torvalds  * pool, but it initializes the pool to different values for devices
139a2080a67SLinus Torvalds  * that might otherwise be identical and have very little entropy
140a2080a67SLinus Torvalds  * available to them (particularly common in the embedded world).
141a2080a67SLinus Torvalds  *
1421da177e4SLinus Torvalds  * add_input_randomness() uses the input layer interrupt timing, as well as
1431da177e4SLinus Torvalds  * the event type information from the hardware.
1441da177e4SLinus Torvalds  *
145775f4b29STheodore Ts'o  * add_interrupt_randomness() uses the interrupt timing as random
146775f4b29STheodore Ts'o  * inputs to the entropy pool. Using the cycle counters and the irq source
147775f4b29STheodore Ts'o  * as inputs, it feeds the randomness roughly once a second.
148442a4fffSJarod Wilson  *
149442a4fffSJarod Wilson  * add_disk_randomness() uses what amounts to the seek time of block
150442a4fffSJarod Wilson  * layer request events, on a per-disk_devt basis, as input to the
151442a4fffSJarod Wilson  * entropy pool. Note that high-speed solid state drives with very low
152442a4fffSJarod Wilson  * seek times do not make for good sources of entropy, as their seek
153442a4fffSJarod Wilson  * times are usually fairly consistent.
1541da177e4SLinus Torvalds  *
1551da177e4SLinus Torvalds  * All of these routines try to estimate how many bits of randomness a
1561da177e4SLinus Torvalds  * particular randomness source.  They do this by keeping track of the
1571da177e4SLinus Torvalds  * first and second order deltas of the event timings.
1581da177e4SLinus Torvalds  *
1591da177e4SLinus Torvalds  * Ensuring unpredictability at system startup
1601da177e4SLinus Torvalds  * ============================================
1611da177e4SLinus Torvalds  *
1621da177e4SLinus Torvalds  * When any operating system starts up, it will go through a sequence
1631da177e4SLinus Torvalds  * of actions that are fairly predictable by an adversary, especially
1641da177e4SLinus Torvalds  * if the start-up does not involve interaction with a human operator.
1651da177e4SLinus Torvalds  * This reduces the actual number of bits of unpredictability in the
1661da177e4SLinus Torvalds  * entropy pool below the value in entropy_count.  In order to
1671da177e4SLinus Torvalds  * counteract this effect, it helps to carry information in the
1681da177e4SLinus Torvalds  * entropy pool across shut-downs and start-ups.  To do this, put the
1691da177e4SLinus Torvalds  * following lines an appropriate script which is run during the boot
1701da177e4SLinus Torvalds  * sequence:
1711da177e4SLinus Torvalds  *
1721da177e4SLinus Torvalds  *	echo "Initializing random number generator..."
1731da177e4SLinus Torvalds  *	random_seed=/var/run/random-seed
1741da177e4SLinus Torvalds  *	# Carry a random seed from start-up to start-up
1751da177e4SLinus Torvalds  *	# Load and then save the whole entropy pool
1761da177e4SLinus Torvalds  *	if [ -f $random_seed ]; then
1771da177e4SLinus Torvalds  *		cat $random_seed >/dev/urandom
1781da177e4SLinus Torvalds  *	else
1791da177e4SLinus Torvalds  *		touch $random_seed
1801da177e4SLinus Torvalds  *	fi
1811da177e4SLinus Torvalds  *	chmod 600 $random_seed
1821da177e4SLinus Torvalds  *	dd if=/dev/urandom of=$random_seed count=1 bs=512
1831da177e4SLinus Torvalds  *
1841da177e4SLinus Torvalds  * and the following lines in an appropriate script which is run as
1851da177e4SLinus Torvalds  * the system is shutdown:
1861da177e4SLinus Torvalds  *
1871da177e4SLinus Torvalds  *	# Carry a random seed from shut-down to start-up
1881da177e4SLinus Torvalds  *	# Save the whole entropy pool
1891da177e4SLinus Torvalds  *	echo "Saving random seed..."
1901da177e4SLinus Torvalds  *	random_seed=/var/run/random-seed
1911da177e4SLinus Torvalds  *	touch $random_seed
1921da177e4SLinus Torvalds  *	chmod 600 $random_seed
1931da177e4SLinus Torvalds  *	dd if=/dev/urandom of=$random_seed count=1 bs=512
1941da177e4SLinus Torvalds  *
1951da177e4SLinus Torvalds  * For example, on most modern systems using the System V init
1961da177e4SLinus Torvalds  * scripts, such code fragments would be found in
1971da177e4SLinus Torvalds  * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
1981da177e4SLinus Torvalds  * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
1991da177e4SLinus Torvalds  *
2001da177e4SLinus Torvalds  * Effectively, these commands cause the contents of the entropy pool
2011da177e4SLinus Torvalds  * to be saved at shut-down time and reloaded into the entropy pool at
2021da177e4SLinus Torvalds  * start-up.  (The 'dd' in the addition to the bootup script is to
2031da177e4SLinus Torvalds  * make sure that /etc/random-seed is different for every start-up,
2041da177e4SLinus Torvalds  * even if the system crashes without executing rc.0.)  Even with
2051da177e4SLinus Torvalds  * complete knowledge of the start-up activities, predicting the state
2061da177e4SLinus Torvalds  * of the entropy pool requires knowledge of the previous history of
2071da177e4SLinus Torvalds  * the system.
2081da177e4SLinus Torvalds  *
2091da177e4SLinus Torvalds  * Configuring the /dev/random driver under Linux
2101da177e4SLinus Torvalds  * ==============================================
2111da177e4SLinus Torvalds  *
2121da177e4SLinus Torvalds  * The /dev/random driver under Linux uses minor numbers 8 and 9 of
2131da177e4SLinus Torvalds  * the /dev/mem major number (#1).  So if your system does not have
2141da177e4SLinus Torvalds  * /dev/random and /dev/urandom created already, they can be created
2151da177e4SLinus Torvalds  * by using the commands:
2161da177e4SLinus Torvalds  *
2171da177e4SLinus Torvalds  * 	mknod /dev/random c 1 8
2181da177e4SLinus Torvalds  * 	mknod /dev/urandom c 1 9
2191da177e4SLinus Torvalds  *
2201da177e4SLinus Torvalds  * Acknowledgements:
2211da177e4SLinus Torvalds  * =================
2221da177e4SLinus Torvalds  *
2231da177e4SLinus Torvalds  * Ideas for constructing this random number generator were derived
2241da177e4SLinus Torvalds  * from Pretty Good Privacy's random number generator, and from private
2251da177e4SLinus Torvalds  * discussions with Phil Karn.  Colin Plumb provided a faster random
2261da177e4SLinus Torvalds  * number generator, which speed up the mixing function of the entropy
2271da177e4SLinus Torvalds  * pool, taken from PGPfone.  Dale Worley has also contributed many
2281da177e4SLinus Torvalds  * useful ideas and suggestions to improve this driver.
2291da177e4SLinus Torvalds  *
2301da177e4SLinus Torvalds  * Any flaws in the design are solely my responsibility, and should
2311da177e4SLinus Torvalds  * not be attributed to the Phil, Colin, or any of authors of PGP.
2321da177e4SLinus Torvalds  *
2331da177e4SLinus Torvalds  * Further background information on this topic may be obtained from
2341da177e4SLinus Torvalds  * RFC 1750, "Randomness Recommendations for Security", by Donald
2351da177e4SLinus Torvalds  * Eastlake, Steve Crocker, and Jeff Schiller.
2361da177e4SLinus Torvalds  */
2371da177e4SLinus Torvalds 
2381da177e4SLinus Torvalds #include <linux/utsname.h>
2391da177e4SLinus Torvalds #include <linux/module.h>
2401da177e4SLinus Torvalds #include <linux/kernel.h>
2411da177e4SLinus Torvalds #include <linux/major.h>
2421da177e4SLinus Torvalds #include <linux/string.h>
2431da177e4SLinus Torvalds #include <linux/fcntl.h>
2441da177e4SLinus Torvalds #include <linux/slab.h>
2451da177e4SLinus Torvalds #include <linux/random.h>
2461da177e4SLinus Torvalds #include <linux/poll.h>
2471da177e4SLinus Torvalds #include <linux/init.h>
2481da177e4SLinus Torvalds #include <linux/fs.h>
2491da177e4SLinus Torvalds #include <linux/genhd.h>
2501da177e4SLinus Torvalds #include <linux/interrupt.h>
25127ac792cSAndrea Righi #include <linux/mm.h>
2521da177e4SLinus Torvalds #include <linux/spinlock.h>
2531da177e4SLinus Torvalds #include <linux/percpu.h>
2541da177e4SLinus Torvalds #include <linux/cryptohash.h>
2555b739ef8SNeil Horman #include <linux/fips.h>
256775f4b29STheodore Ts'o #include <linux/ptrace.h>
257e6d4947bSTheodore Ts'o #include <linux/kmemcheck.h>
2586265e169STheodore Ts'o #include <linux/workqueue.h>
259d178a1ebSYinghai Lu #include <linux/irq.h>
260d178a1ebSYinghai Lu 
2611da177e4SLinus Torvalds #include <asm/processor.h>
2621da177e4SLinus Torvalds #include <asm/uaccess.h>
2631da177e4SLinus Torvalds #include <asm/irq.h>
264775f4b29STheodore Ts'o #include <asm/irq_regs.h>
2651da177e4SLinus Torvalds #include <asm/io.h>
2661da177e4SLinus Torvalds 
26700ce1db1STheodore Ts'o #define CREATE_TRACE_POINTS
26800ce1db1STheodore Ts'o #include <trace/events/random.h>
26900ce1db1STheodore Ts'o 
2701da177e4SLinus Torvalds /*
2711da177e4SLinus Torvalds  * Configuration information
2721da177e4SLinus Torvalds  */
27330e37ec5SH. Peter Anvin #define INPUT_POOL_SHIFT	12
27430e37ec5SH. Peter Anvin #define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
27530e37ec5SH. Peter Anvin #define OUTPUT_POOL_SHIFT	10
27630e37ec5SH. Peter Anvin #define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
2771da177e4SLinus Torvalds #define SEC_XFER_SIZE		512
278e954bc91SMatt Mackall #define EXTRACT_SIZE		10
2791da177e4SLinus Torvalds 
280392a546dSTheodore Ts'o #define DEBUG_RANDOM_BOOT 0
281392a546dSTheodore Ts'o 
282d2e7c96aSH. Peter Anvin #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
283d2e7c96aSH. Peter Anvin 
2841da177e4SLinus Torvalds /*
28595b709b6STheodore Ts'o  * To allow fractional bits to be tracked, the entropy_count field is
28695b709b6STheodore Ts'o  * denominated in units of 1/8th bits.
28730e37ec5SH. Peter Anvin  *
28830e37ec5SH. Peter Anvin  * 2*(ENTROPY_SHIFT + log2(poolbits)) must <= 31, or the multiply in
28930e37ec5SH. Peter Anvin  * credit_entropy_bits() needs to be 64 bits wide.
290a283b5c4SH. Peter Anvin  */
291a283b5c4SH. Peter Anvin #define ENTROPY_SHIFT 3
292a283b5c4SH. Peter Anvin #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
293a283b5c4SH. Peter Anvin 
294a283b5c4SH. Peter Anvin /*
2951da177e4SLinus Torvalds  * The minimum number of bits of entropy before we wake up a read on
2961da177e4SLinus Torvalds  * /dev/random.  Should be enough to do a significant reseed.
2971da177e4SLinus Torvalds  */
2982132a96fSGreg Price static int random_read_wakeup_bits = 64;
2991da177e4SLinus Torvalds 
3001da177e4SLinus Torvalds /*
3011da177e4SLinus Torvalds  * If the entropy count falls under this number of bits, then we
3021da177e4SLinus Torvalds  * should wake up processes which are selecting or polling on write
3031da177e4SLinus Torvalds  * access to /dev/random.
3041da177e4SLinus Torvalds  */
3052132a96fSGreg Price static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS;
3061da177e4SLinus Torvalds 
3071da177e4SLinus Torvalds /*
308dfd38750SGreg Price  * The minimum number of seconds between urandom pool reseeding.  We
309f5c2742cSTheodore Ts'o  * do this to limit the amount of entropy that can be drained from the
310f5c2742cSTheodore Ts'o  * input pool even if there are heavy demands on /dev/urandom.
3111da177e4SLinus Torvalds  */
312f5c2742cSTheodore Ts'o static int random_min_urandom_seed = 60;
3131da177e4SLinus Torvalds 
3141da177e4SLinus Torvalds /*
3156e9fa2c8STheodore Ts'o  * Originally, we used a primitive polynomial of degree .poolwords
3166e9fa2c8STheodore Ts'o  * over GF(2).  The taps for various sizes are defined below.  They
3176e9fa2c8STheodore Ts'o  * were chosen to be evenly spaced except for the last tap, which is 1
3186e9fa2c8STheodore Ts'o  * to get the twisting happening as fast as possible.
3191da177e4SLinus Torvalds  *
3206e9fa2c8STheodore Ts'o  * For the purposes of better mixing, we use the CRC-32 polynomial as
3216e9fa2c8STheodore Ts'o  * well to make a (modified) twisted Generalized Feedback Shift
3226e9fa2c8STheodore Ts'o  * Register.  (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR
3236e9fa2c8STheodore Ts'o  * generators.  ACM Transactions on Modeling and Computer Simulation
3246e9fa2c8STheodore Ts'o  * 2(3):179-194.  Also see M. Matsumoto & Y. Kurita, 1994.  Twisted
325dfd38750SGreg Price  * GFSR generators II.  ACM Transactions on Modeling and Computer
3266e9fa2c8STheodore Ts'o  * Simulation 4:254-266)
3271da177e4SLinus Torvalds  *
3281da177e4SLinus Torvalds  * Thanks to Colin Plumb for suggesting this.
3291da177e4SLinus Torvalds  *
3306e9fa2c8STheodore Ts'o  * The mixing operation is much less sensitive than the output hash,
3316e9fa2c8STheodore Ts'o  * where we use SHA-1.  All that we want of mixing operation is that
3326e9fa2c8STheodore Ts'o  * it be a good non-cryptographic hash; i.e. it not produce collisions
3336e9fa2c8STheodore Ts'o  * when fed "random" data of the sort we expect to see.  As long as
3346e9fa2c8STheodore Ts'o  * the pool state differs for different inputs, we have preserved the
3356e9fa2c8STheodore Ts'o  * input entropy and done a good job.  The fact that an intelligent
3366e9fa2c8STheodore Ts'o  * attacker can construct inputs that will produce controlled
3376e9fa2c8STheodore Ts'o  * alterations to the pool's state is not important because we don't
3386e9fa2c8STheodore Ts'o  * consider such inputs to contribute any randomness.  The only
3396e9fa2c8STheodore Ts'o  * property we need with respect to them is that the attacker can't
3406e9fa2c8STheodore Ts'o  * increase his/her knowledge of the pool's state.  Since all
3416e9fa2c8STheodore Ts'o  * additions are reversible (knowing the final state and the input,
3426e9fa2c8STheodore Ts'o  * you can reconstruct the initial state), if an attacker has any
3436e9fa2c8STheodore Ts'o  * uncertainty about the initial state, he/she can only shuffle that
3446e9fa2c8STheodore Ts'o  * uncertainty about, but never cause any collisions (which would
3451da177e4SLinus Torvalds  * decrease the uncertainty).
3461da177e4SLinus Torvalds  *
3476e9fa2c8STheodore Ts'o  * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
3486e9fa2c8STheodore Ts'o  * Videau in their paper, "The Linux Pseudorandom Number Generator
3496e9fa2c8STheodore Ts'o  * Revisited" (see: http://eprint.iacr.org/2012/251.pdf).  In their
3506e9fa2c8STheodore Ts'o  * paper, they point out that we are not using a true Twisted GFSR,
3516e9fa2c8STheodore Ts'o  * since Matsumoto & Kurita used a trinomial feedback polynomial (that
3526e9fa2c8STheodore Ts'o  * is, with only three taps, instead of the six that we are using).
3536e9fa2c8STheodore Ts'o  * As a result, the resulting polynomial is neither primitive nor
3546e9fa2c8STheodore Ts'o  * irreducible, and hence does not have a maximal period over
3556e9fa2c8STheodore Ts'o  * GF(2**32).  They suggest a slight change to the generator
3566e9fa2c8STheodore Ts'o  * polynomial which improves the resulting TGFSR polynomial to be
3576e9fa2c8STheodore Ts'o  * irreducible, which we have made here.
3581da177e4SLinus Torvalds  */
3591da177e4SLinus Torvalds static struct poolinfo {
360a283b5c4SH. Peter Anvin 	int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
361a283b5c4SH. Peter Anvin #define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
3621da177e4SLinus Torvalds 	int tap1, tap2, tap3, tap4, tap5;
3631da177e4SLinus Torvalds } poolinfo_table[] = {
3646e9fa2c8STheodore Ts'o 	/* was: x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 */
3656e9fa2c8STheodore Ts'o 	/* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
3666e9fa2c8STheodore Ts'o 	{ S(128),	104,	76,	51,	25,	1 },
3676e9fa2c8STheodore Ts'o 	/* was: x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 */
3686e9fa2c8STheodore Ts'o 	/* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */
3696e9fa2c8STheodore Ts'o 	{ S(32),	26,	19,	14,	7,	1 },
3701da177e4SLinus Torvalds #if 0
3711da177e4SLinus Torvalds 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
3729ed17b70SH. Peter Anvin 	{ S(2048),	1638,	1231,	819,	411,	1 },
3731da177e4SLinus Torvalds 
3741da177e4SLinus Torvalds 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
3759ed17b70SH. Peter Anvin 	{ S(1024),	817,	615,	412,	204,	1 },
3761da177e4SLinus Torvalds 
3771da177e4SLinus Torvalds 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
3789ed17b70SH. Peter Anvin 	{ S(1024),	819,	616,	410,	207,	2 },
3791da177e4SLinus Torvalds 
3801da177e4SLinus Torvalds 	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
3819ed17b70SH. Peter Anvin 	{ S(512),	411,	308,	208,	104,	1 },
3821da177e4SLinus Torvalds 
3831da177e4SLinus Torvalds 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
3849ed17b70SH. Peter Anvin 	{ S(512),	409,	307,	206,	102,	2 },
3851da177e4SLinus Torvalds 	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
3869ed17b70SH. Peter Anvin 	{ S(512),	409,	309,	205,	103,	2 },
3871da177e4SLinus Torvalds 
3881da177e4SLinus Torvalds 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
3899ed17b70SH. Peter Anvin 	{ S(256),	205,	155,	101,	52,	1 },
3901da177e4SLinus Torvalds 
3911da177e4SLinus Torvalds 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
3929ed17b70SH. Peter Anvin 	{ S(128),	103,	78,	51,	27,	2 },
3931da177e4SLinus Torvalds 
3941da177e4SLinus Torvalds 	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
3959ed17b70SH. Peter Anvin 	{ S(64),	52,	39,	26,	14,	1 },
3961da177e4SLinus Torvalds #endif
3971da177e4SLinus Torvalds };
3981da177e4SLinus Torvalds 
3991da177e4SLinus Torvalds /*
4001da177e4SLinus Torvalds  * Static global variables
4011da177e4SLinus Torvalds  */
4021da177e4SLinus Torvalds static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
4031da177e4SLinus Torvalds static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
4049a6f70bbSJeff Dike static struct fasync_struct *fasync;
4051da177e4SLinus Torvalds 
4061da177e4SLinus Torvalds /**********************************************************************
4071da177e4SLinus Torvalds  *
4081da177e4SLinus Torvalds  * OS independent entropy store.   Here are the functions which handle
4091da177e4SLinus Torvalds  * storing entropy in an entropy pool.
4101da177e4SLinus Torvalds  *
4111da177e4SLinus Torvalds  **********************************************************************/
4121da177e4SLinus Torvalds 
4131da177e4SLinus Torvalds struct entropy_store;
4141da177e4SLinus Torvalds struct entropy_store {
41543358209SMatt Mackall 	/* read-only data: */
41630e37ec5SH. Peter Anvin 	const struct poolinfo *poolinfo;
4171da177e4SLinus Torvalds 	__u32 *pool;
4181da177e4SLinus Torvalds 	const char *name;
4191da177e4SLinus Torvalds 	struct entropy_store *pull;
4206265e169STheodore Ts'o 	struct work_struct push_work;
4211da177e4SLinus Torvalds 
4221da177e4SLinus Torvalds 	/* read-write data: */
423f5c2742cSTheodore Ts'o 	unsigned long last_pulled;
42443358209SMatt Mackall 	spinlock_t lock;
425c59974aeSTheodore Ts'o 	unsigned short add_ptr;
426c59974aeSTheodore Ts'o 	unsigned short input_rotate;
427cda796a3SMatt Mackall 	int entropy_count;
428775f4b29STheodore Ts'o 	int entropy_total;
429775f4b29STheodore Ts'o 	unsigned int initialized:1;
430c59974aeSTheodore Ts'o 	unsigned int limit:1;
431c59974aeSTheodore Ts'o 	unsigned int last_data_init:1;
432e954bc91SMatt Mackall 	__u8 last_data[EXTRACT_SIZE];
4331da177e4SLinus Torvalds };
4341da177e4SLinus Torvalds 
4356265e169STheodore Ts'o static void push_to_pool(struct work_struct *work);
4361da177e4SLinus Torvalds static __u32 input_pool_data[INPUT_POOL_WORDS];
4371da177e4SLinus Torvalds static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
4381da177e4SLinus Torvalds static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
4391da177e4SLinus Torvalds 
4401da177e4SLinus Torvalds static struct entropy_store input_pool = {
4411da177e4SLinus Torvalds 	.poolinfo = &poolinfo_table[0],
4421da177e4SLinus Torvalds 	.name = "input",
4431da177e4SLinus Torvalds 	.limit = 1,
444eece09ecSThomas Gleixner 	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
4451da177e4SLinus Torvalds 	.pool = input_pool_data
4461da177e4SLinus Torvalds };
4471da177e4SLinus Torvalds 
4481da177e4SLinus Torvalds static struct entropy_store blocking_pool = {
4491da177e4SLinus Torvalds 	.poolinfo = &poolinfo_table[1],
4501da177e4SLinus Torvalds 	.name = "blocking",
4511da177e4SLinus Torvalds 	.limit = 1,
4521da177e4SLinus Torvalds 	.pull = &input_pool,
453eece09ecSThomas Gleixner 	.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
4546265e169STheodore Ts'o 	.pool = blocking_pool_data,
4556265e169STheodore Ts'o 	.push_work = __WORK_INITIALIZER(blocking_pool.push_work,
4566265e169STheodore Ts'o 					push_to_pool),
4571da177e4SLinus Torvalds };
4581da177e4SLinus Torvalds 
4591da177e4SLinus Torvalds static struct entropy_store nonblocking_pool = {
4601da177e4SLinus Torvalds 	.poolinfo = &poolinfo_table[1],
4611da177e4SLinus Torvalds 	.name = "nonblocking",
4621da177e4SLinus Torvalds 	.pull = &input_pool,
463eece09ecSThomas Gleixner 	.lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock),
4646265e169STheodore Ts'o 	.pool = nonblocking_pool_data,
4656265e169STheodore Ts'o 	.push_work = __WORK_INITIALIZER(nonblocking_pool.push_work,
4666265e169STheodore Ts'o 					push_to_pool),
4671da177e4SLinus Torvalds };
4681da177e4SLinus Torvalds 
469775f4b29STheodore Ts'o static __u32 const twist_table[8] = {
470775f4b29STheodore Ts'o 	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
471775f4b29STheodore Ts'o 	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
472775f4b29STheodore Ts'o 
4731da177e4SLinus Torvalds /*
474e68e5b66SMatt Mackall  * This function adds bytes into the entropy "pool".  It does not
4751da177e4SLinus Torvalds  * update the entropy estimate.  The caller should call
476adc782daSMatt Mackall  * credit_entropy_bits if this is appropriate.
4771da177e4SLinus Torvalds  *
4781da177e4SLinus Torvalds  * The pool is stirred with a primitive polynomial of the appropriate
4791da177e4SLinus Torvalds  * degree, and then twisted.  We twist by three bits at a time because
4801da177e4SLinus Torvalds  * it's cheap to do so and helps slightly in the expected case where
4811da177e4SLinus Torvalds  * the entropy is concentrated in the low-order bits.
4821da177e4SLinus Torvalds  */
48300ce1db1STheodore Ts'o static void _mix_pool_bytes(struct entropy_store *r, const void *in,
484e68e5b66SMatt Mackall 			    int nbytes, __u8 out[64])
4851da177e4SLinus Torvalds {
486993ba211SMatt Mackall 	unsigned long i, j, tap1, tap2, tap3, tap4, tap5;
487feee7697SMatt Mackall 	int input_rotate;
4881da177e4SLinus Torvalds 	int wordmask = r->poolinfo->poolwords - 1;
489e68e5b66SMatt Mackall 	const char *bytes = in;
4906d38b827SMatt Mackall 	__u32 w;
4911da177e4SLinus Torvalds 
4921da177e4SLinus Torvalds 	tap1 = r->poolinfo->tap1;
4931da177e4SLinus Torvalds 	tap2 = r->poolinfo->tap2;
4941da177e4SLinus Torvalds 	tap3 = r->poolinfo->tap3;
4951da177e4SLinus Torvalds 	tap4 = r->poolinfo->tap4;
4961da177e4SLinus Torvalds 	tap5 = r->poolinfo->tap5;
4971da177e4SLinus Torvalds 
498902c098aSTheodore Ts'o 	smp_rmb();
499902c098aSTheodore Ts'o 	input_rotate = ACCESS_ONCE(r->input_rotate);
500902c098aSTheodore Ts'o 	i = ACCESS_ONCE(r->add_ptr);
5011da177e4SLinus Torvalds 
502e68e5b66SMatt Mackall 	/* mix one byte at a time to simplify size handling and churn faster */
503e68e5b66SMatt Mackall 	while (nbytes--) {
504c59974aeSTheodore Ts'o 		w = rol32(*bytes++, input_rotate);
505993ba211SMatt Mackall 		i = (i - 1) & wordmask;
5061da177e4SLinus Torvalds 
5071da177e4SLinus Torvalds 		/* XOR in the various taps */
508993ba211SMatt Mackall 		w ^= r->pool[i];
5091da177e4SLinus Torvalds 		w ^= r->pool[(i + tap1) & wordmask];
5101da177e4SLinus Torvalds 		w ^= r->pool[(i + tap2) & wordmask];
5111da177e4SLinus Torvalds 		w ^= r->pool[(i + tap3) & wordmask];
5121da177e4SLinus Torvalds 		w ^= r->pool[(i + tap4) & wordmask];
5131da177e4SLinus Torvalds 		w ^= r->pool[(i + tap5) & wordmask];
514993ba211SMatt Mackall 
515993ba211SMatt Mackall 		/* Mix the result back in with a twist */
5161da177e4SLinus Torvalds 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
517feee7697SMatt Mackall 
518feee7697SMatt Mackall 		/*
519feee7697SMatt Mackall 		 * Normally, we add 7 bits of rotation to the pool.
520feee7697SMatt Mackall 		 * At the beginning of the pool, add an extra 7 bits
521feee7697SMatt Mackall 		 * rotation, so that successive passes spread the
522feee7697SMatt Mackall 		 * input bits across the pool evenly.
523feee7697SMatt Mackall 		 */
524c59974aeSTheodore Ts'o 		input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
5251da177e4SLinus Torvalds 	}
5261da177e4SLinus Torvalds 
527902c098aSTheodore Ts'o 	ACCESS_ONCE(r->input_rotate) = input_rotate;
528902c098aSTheodore Ts'o 	ACCESS_ONCE(r->add_ptr) = i;
529902c098aSTheodore Ts'o 	smp_wmb();
5301da177e4SLinus Torvalds 
531993ba211SMatt Mackall 	if (out)
532993ba211SMatt Mackall 		for (j = 0; j < 16; j++)
533e68e5b66SMatt Mackall 			((__u32 *)out)[j] = r->pool[(i - j) & wordmask];
5341da177e4SLinus Torvalds }
5351da177e4SLinus Torvalds 
53600ce1db1STheodore Ts'o static void __mix_pool_bytes(struct entropy_store *r, const void *in,
53700ce1db1STheodore Ts'o 			     int nbytes, __u8 out[64])
53800ce1db1STheodore Ts'o {
53900ce1db1STheodore Ts'o 	trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
54000ce1db1STheodore Ts'o 	_mix_pool_bytes(r, in, nbytes, out);
54100ce1db1STheodore Ts'o }
54200ce1db1STheodore Ts'o 
543902c098aSTheodore Ts'o static void mix_pool_bytes(struct entropy_store *r, const void *in,
544902c098aSTheodore Ts'o 			   int nbytes, __u8 out[64])
5451da177e4SLinus Torvalds {
546902c098aSTheodore Ts'o 	unsigned long flags;
547902c098aSTheodore Ts'o 
54800ce1db1STheodore Ts'o 	trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
549902c098aSTheodore Ts'o 	spin_lock_irqsave(&r->lock, flags);
55000ce1db1STheodore Ts'o 	_mix_pool_bytes(r, in, nbytes, out);
551902c098aSTheodore Ts'o 	spin_unlock_irqrestore(&r->lock, flags);
5521da177e4SLinus Torvalds }
5531da177e4SLinus Torvalds 
554775f4b29STheodore Ts'o struct fast_pool {
555775f4b29STheodore Ts'o 	__u32		pool[4];
556775f4b29STheodore Ts'o 	unsigned long	last;
557775f4b29STheodore Ts'o 	unsigned short	count;
558775f4b29STheodore Ts'o 	unsigned char	rotate;
559775f4b29STheodore Ts'o 	unsigned char	last_timer_intr;
560775f4b29STheodore Ts'o };
561775f4b29STheodore Ts'o 
562775f4b29STheodore Ts'o /*
563775f4b29STheodore Ts'o  * This is a fast mixing routine used by the interrupt randomness
564775f4b29STheodore Ts'o  * collector.  It's hardcoded for an 128 bit pool and assumes that any
565775f4b29STheodore Ts'o  * locks that might be needed are taken by the caller.
566775f4b29STheodore Ts'o  */
567655b2264STheodore Ts'o static void fast_mix(struct fast_pool *f, __u32 input[4])
568775f4b29STheodore Ts'o {
569775f4b29STheodore Ts'o 	__u32		w;
570775f4b29STheodore Ts'o 	unsigned	input_rotate = f->rotate;
571775f4b29STheodore Ts'o 
572655b2264STheodore Ts'o 	w = rol32(input[0], input_rotate) ^ f->pool[0] ^ f->pool[3];
573655b2264STheodore Ts'o 	f->pool[0] = (w >> 3) ^ twist_table[w & 7];
574655b2264STheodore Ts'o 	input_rotate = (input_rotate + 14) & 31;
575655b2264STheodore Ts'o 	w = rol32(input[1], input_rotate) ^ f->pool[1] ^ f->pool[0];
576655b2264STheodore Ts'o 	f->pool[1] = (w >> 3) ^ twist_table[w & 7];
577655b2264STheodore Ts'o 	input_rotate = (input_rotate + 7) & 31;
578655b2264STheodore Ts'o 	w = rol32(input[2], input_rotate) ^ f->pool[2] ^ f->pool[1];
579655b2264STheodore Ts'o 	f->pool[2] = (w >> 3) ^ twist_table[w & 7];
580655b2264STheodore Ts'o 	input_rotate = (input_rotate + 7) & 31;
581655b2264STheodore Ts'o 	w = rol32(input[3], input_rotate) ^ f->pool[3] ^ f->pool[2];
582655b2264STheodore Ts'o 	f->pool[3] = (w >> 3) ^ twist_table[w & 7];
583655b2264STheodore Ts'o 	input_rotate = (input_rotate + 7) & 31;
584655b2264STheodore Ts'o 
585775f4b29STheodore Ts'o 	f->rotate = input_rotate;
586655b2264STheodore Ts'o 	f->count++;
587775f4b29STheodore Ts'o }
588775f4b29STheodore Ts'o 
5891da177e4SLinus Torvalds /*
590a283b5c4SH. Peter Anvin  * Credit (or debit) the entropy store with n bits of entropy.
591a283b5c4SH. Peter Anvin  * Use credit_entropy_bits_safe() if the value comes from userspace
592a283b5c4SH. Peter Anvin  * or otherwise should be checked for extreme values.
5931da177e4SLinus Torvalds  */
594adc782daSMatt Mackall static void credit_entropy_bits(struct entropy_store *r, int nbits)
5951da177e4SLinus Torvalds {
596902c098aSTheodore Ts'o 	int entropy_count, orig;
59730e37ec5SH. Peter Anvin 	const int pool_size = r->poolinfo->poolfracbits;
59830e37ec5SH. Peter Anvin 	int nfrac = nbits << ENTROPY_SHIFT;
5991da177e4SLinus Torvalds 
600adc782daSMatt Mackall 	if (!nbits)
601adc782daSMatt Mackall 		return;
602adc782daSMatt Mackall 
603902c098aSTheodore Ts'o retry:
604902c098aSTheodore Ts'o 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
60530e37ec5SH. Peter Anvin 	if (nfrac < 0) {
60630e37ec5SH. Peter Anvin 		/* Debit */
60730e37ec5SH. Peter Anvin 		entropy_count += nfrac;
60830e37ec5SH. Peter Anvin 	} else {
60930e37ec5SH. Peter Anvin 		/*
61030e37ec5SH. Peter Anvin 		 * Credit: we have to account for the possibility of
61130e37ec5SH. Peter Anvin 		 * overwriting already present entropy.	 Even in the
61230e37ec5SH. Peter Anvin 		 * ideal case of pure Shannon entropy, new contributions
61330e37ec5SH. Peter Anvin 		 * approach the full value asymptotically:
61430e37ec5SH. Peter Anvin 		 *
61530e37ec5SH. Peter Anvin 		 * entropy <- entropy + (pool_size - entropy) *
61630e37ec5SH. Peter Anvin 		 *	(1 - exp(-add_entropy/pool_size))
61730e37ec5SH. Peter Anvin 		 *
61830e37ec5SH. Peter Anvin 		 * For add_entropy <= pool_size/2 then
61930e37ec5SH. Peter Anvin 		 * (1 - exp(-add_entropy/pool_size)) >=
62030e37ec5SH. Peter Anvin 		 *    (add_entropy/pool_size)*0.7869...
62130e37ec5SH. Peter Anvin 		 * so we can approximate the exponential with
62230e37ec5SH. Peter Anvin 		 * 3/4*add_entropy/pool_size and still be on the
62330e37ec5SH. Peter Anvin 		 * safe side by adding at most pool_size/2 at a time.
62430e37ec5SH. Peter Anvin 		 *
62530e37ec5SH. Peter Anvin 		 * The use of pool_size-2 in the while statement is to
62630e37ec5SH. Peter Anvin 		 * prevent rounding artifacts from making the loop
62730e37ec5SH. Peter Anvin 		 * arbitrarily long; this limits the loop to log2(pool_size)*2
62830e37ec5SH. Peter Anvin 		 * turns no matter how large nbits is.
62930e37ec5SH. Peter Anvin 		 */
63030e37ec5SH. Peter Anvin 		int pnfrac = nfrac;
63130e37ec5SH. Peter Anvin 		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
63230e37ec5SH. Peter Anvin 		/* The +2 corresponds to the /4 in the denominator */
63330e37ec5SH. Peter Anvin 
63430e37ec5SH. Peter Anvin 		do {
63530e37ec5SH. Peter Anvin 			unsigned int anfrac = min(pnfrac, pool_size/2);
63630e37ec5SH. Peter Anvin 			unsigned int add =
63730e37ec5SH. Peter Anvin 				((pool_size - entropy_count)*anfrac*3) >> s;
63830e37ec5SH. Peter Anvin 
63930e37ec5SH. Peter Anvin 			entropy_count += add;
64030e37ec5SH. Peter Anvin 			pnfrac -= anfrac;
64130e37ec5SH. Peter Anvin 		} while (unlikely(entropy_count < pool_size-2 && pnfrac));
64230e37ec5SH. Peter Anvin 	}
64300ce1db1STheodore Ts'o 
6448b76f46aSAndrew Morton 	if (entropy_count < 0) {
645f80bbd8bSTheodore Ts'o 		pr_warn("random: negative entropy/overflow: pool %s count %d\n",
646f80bbd8bSTheodore Ts'o 			r->name, entropy_count);
647f80bbd8bSTheodore Ts'o 		WARN_ON(1);
6488b76f46aSAndrew Morton 		entropy_count = 0;
64930e37ec5SH. Peter Anvin 	} else if (entropy_count > pool_size)
65030e37ec5SH. Peter Anvin 		entropy_count = pool_size;
651902c098aSTheodore Ts'o 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
652902c098aSTheodore Ts'o 		goto retry;
6531da177e4SLinus Torvalds 
654775f4b29STheodore Ts'o 	r->entropy_total += nbits;
6550891ad82SLinus Torvalds 	if (!r->initialized && r->entropy_total > 128) {
656775f4b29STheodore Ts'o 		r->initialized = 1;
6576265e169STheodore Ts'o 		r->entropy_total = 0;
6580891ad82SLinus Torvalds 		if (r == &nonblocking_pool) {
6594af712e8SHannes Frederic Sowa 			prandom_reseed_late();
6600891ad82SLinus Torvalds 			pr_notice("random: %s pool is initialized\n", r->name);
6614af712e8SHannes Frederic Sowa 		}
662775f4b29STheodore Ts'o 	}
663775f4b29STheodore Ts'o 
664a283b5c4SH. Peter Anvin 	trace_credit_entropy_bits(r->name, nbits,
665a283b5c4SH. Peter Anvin 				  entropy_count >> ENTROPY_SHIFT,
66600ce1db1STheodore Ts'o 				  r->entropy_total, _RET_IP_);
66700ce1db1STheodore Ts'o 
6686265e169STheodore Ts'o 	if (r == &input_pool) {
6697d1b08c4SGreg Price 		int entropy_bits = entropy_count >> ENTROPY_SHIFT;
6706265e169STheodore Ts'o 
67188c730daSMatt Mackall 		/* should we wake readers? */
6722132a96fSGreg Price 		if (entropy_bits >= random_read_wakeup_bits) {
67388c730daSMatt Mackall 			wake_up_interruptible(&random_read_wait);
6749a6f70bbSJeff Dike 			kill_fasync(&fasync, SIGIO, POLL_IN);
6759a6f70bbSJeff Dike 		}
6766265e169STheodore Ts'o 		/* If the input pool is getting full, send some
6776265e169STheodore Ts'o 		 * entropy to the two output pools, flipping back and
6786265e169STheodore Ts'o 		 * forth between them, until the output pools are 75%
6796265e169STheodore Ts'o 		 * full.
6806265e169STheodore Ts'o 		 */
6812132a96fSGreg Price 		if (entropy_bits > random_write_wakeup_bits &&
6826265e169STheodore Ts'o 		    r->initialized &&
6832132a96fSGreg Price 		    r->entropy_total >= 2*random_read_wakeup_bits) {
6846265e169STheodore Ts'o 			static struct entropy_store *last = &blocking_pool;
6856265e169STheodore Ts'o 			struct entropy_store *other = &blocking_pool;
6866265e169STheodore Ts'o 
6876265e169STheodore Ts'o 			if (last == &blocking_pool)
6886265e169STheodore Ts'o 				other = &nonblocking_pool;
6896265e169STheodore Ts'o 			if (other->entropy_count <=
6906265e169STheodore Ts'o 			    3 * other->poolinfo->poolfracbits / 4)
6916265e169STheodore Ts'o 				last = other;
6926265e169STheodore Ts'o 			if (last->entropy_count <=
6936265e169STheodore Ts'o 			    3 * last->poolinfo->poolfracbits / 4) {
6946265e169STheodore Ts'o 				schedule_work(&last->push_work);
6956265e169STheodore Ts'o 				r->entropy_total = 0;
6966265e169STheodore Ts'o 			}
6976265e169STheodore Ts'o 		}
6986265e169STheodore Ts'o 	}
6991da177e4SLinus Torvalds }
7001da177e4SLinus Torvalds 
701a283b5c4SH. Peter Anvin static void credit_entropy_bits_safe(struct entropy_store *r, int nbits)
702a283b5c4SH. Peter Anvin {
703a283b5c4SH. Peter Anvin 	const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1));
704a283b5c4SH. Peter Anvin 
705a283b5c4SH. Peter Anvin 	/* Cap the value to avoid overflows */
706a283b5c4SH. Peter Anvin 	nbits = min(nbits,  nbits_max);
707a283b5c4SH. Peter Anvin 	nbits = max(nbits, -nbits_max);
708a283b5c4SH. Peter Anvin 
709a283b5c4SH. Peter Anvin 	credit_entropy_bits(r, nbits);
7101da177e4SLinus Torvalds }
7111da177e4SLinus Torvalds 
7121da177e4SLinus Torvalds /*********************************************************************
7131da177e4SLinus Torvalds  *
7141da177e4SLinus Torvalds  * Entropy input management
7151da177e4SLinus Torvalds  *
7161da177e4SLinus Torvalds  *********************************************************************/
7171da177e4SLinus Torvalds 
7181da177e4SLinus Torvalds /* There is one of these per entropy source */
7191da177e4SLinus Torvalds struct timer_rand_state {
7201da177e4SLinus Torvalds 	cycles_t last_time;
7211da177e4SLinus Torvalds 	long last_delta, last_delta2;
7221da177e4SLinus Torvalds 	unsigned dont_count_entropy:1;
7231da177e4SLinus Torvalds };
7241da177e4SLinus Torvalds 
725644008dfSTheodore Ts'o #define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, };
726644008dfSTheodore Ts'o 
727a2080a67SLinus Torvalds /*
728a2080a67SLinus Torvalds  * Add device- or boot-specific data to the input and nonblocking
729a2080a67SLinus Torvalds  * pools to help initialize them to unique values.
730a2080a67SLinus Torvalds  *
731a2080a67SLinus Torvalds  * None of this adds any entropy, it is meant to avoid the
732a2080a67SLinus Torvalds  * problem of the nonblocking pool having similar initial state
733a2080a67SLinus Torvalds  * across largely identical devices.
734a2080a67SLinus Torvalds  */
735a2080a67SLinus Torvalds void add_device_randomness(const void *buf, unsigned int size)
736a2080a67SLinus Torvalds {
73761875f30STheodore Ts'o 	unsigned long time = random_get_entropy() ^ jiffies;
7383ef4cb2dSTheodore Ts'o 	unsigned long flags;
739a2080a67SLinus Torvalds 
7405910895fSTheodore Ts'o 	trace_add_device_randomness(size, _RET_IP_);
7413ef4cb2dSTheodore Ts'o 	spin_lock_irqsave(&input_pool.lock, flags);
7423ef4cb2dSTheodore Ts'o 	_mix_pool_bytes(&input_pool, buf, size, NULL);
7433ef4cb2dSTheodore Ts'o 	_mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
7443ef4cb2dSTheodore Ts'o 	spin_unlock_irqrestore(&input_pool.lock, flags);
7453ef4cb2dSTheodore Ts'o 
7463ef4cb2dSTheodore Ts'o 	spin_lock_irqsave(&nonblocking_pool.lock, flags);
7473ef4cb2dSTheodore Ts'o 	_mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
7483ef4cb2dSTheodore Ts'o 	_mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL);
7493ef4cb2dSTheodore Ts'o 	spin_unlock_irqrestore(&nonblocking_pool.lock, flags);
750a2080a67SLinus Torvalds }
751a2080a67SLinus Torvalds EXPORT_SYMBOL(add_device_randomness);
752a2080a67SLinus Torvalds 
753644008dfSTheodore Ts'o static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE;
7543060d6feSYinghai Lu 
7551da177e4SLinus Torvalds /*
7561da177e4SLinus Torvalds  * This function adds entropy to the entropy "pool" by using timing
7571da177e4SLinus Torvalds  * delays.  It uses the timer_rand_state structure to make an estimate
7581da177e4SLinus Torvalds  * of how many bits of entropy this call has added to the pool.
7591da177e4SLinus Torvalds  *
7601da177e4SLinus Torvalds  * The number "num" is also added to the pool - it should somehow describe
7611da177e4SLinus Torvalds  * the type of event which just happened.  This is currently 0-255 for
7621da177e4SLinus Torvalds  * keyboard scan codes, and 256 upwards for interrupts.
7631da177e4SLinus Torvalds  *
7641da177e4SLinus Torvalds  */
7651da177e4SLinus Torvalds static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
7661da177e4SLinus Torvalds {
76740db23e5STheodore Ts'o 	struct entropy_store	*r;
7681da177e4SLinus Torvalds 	struct {
7691da177e4SLinus Torvalds 		long jiffies;
770cf833d0bSLinus Torvalds 		unsigned cycles;
7711da177e4SLinus Torvalds 		unsigned num;
7721da177e4SLinus Torvalds 	} sample;
7731da177e4SLinus Torvalds 	long delta, delta2, delta3;
7741da177e4SLinus Torvalds 
7751da177e4SLinus Torvalds 	preempt_disable();
7761da177e4SLinus Torvalds 
7771da177e4SLinus Torvalds 	sample.jiffies = jiffies;
77861875f30STheodore Ts'o 	sample.cycles = random_get_entropy();
7791da177e4SLinus Torvalds 	sample.num = num;
78040db23e5STheodore Ts'o 	r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
78140db23e5STheodore Ts'o 	mix_pool_bytes(r, &sample, sizeof(sample), NULL);
7821da177e4SLinus Torvalds 
7831da177e4SLinus Torvalds 	/*
7841da177e4SLinus Torvalds 	 * Calculate number of bits of randomness we probably added.
7851da177e4SLinus Torvalds 	 * We take into account the first, second and third-order deltas
7861da177e4SLinus Torvalds 	 * in order to make our estimate.
7871da177e4SLinus Torvalds 	 */
7881da177e4SLinus Torvalds 
7891da177e4SLinus Torvalds 	if (!state->dont_count_entropy) {
7901da177e4SLinus Torvalds 		delta = sample.jiffies - state->last_time;
7911da177e4SLinus Torvalds 		state->last_time = sample.jiffies;
7921da177e4SLinus Torvalds 
7931da177e4SLinus Torvalds 		delta2 = delta - state->last_delta;
7941da177e4SLinus Torvalds 		state->last_delta = delta;
7951da177e4SLinus Torvalds 
7961da177e4SLinus Torvalds 		delta3 = delta2 - state->last_delta2;
7971da177e4SLinus Torvalds 		state->last_delta2 = delta2;
7981da177e4SLinus Torvalds 
7991da177e4SLinus Torvalds 		if (delta < 0)
8001da177e4SLinus Torvalds 			delta = -delta;
8011da177e4SLinus Torvalds 		if (delta2 < 0)
8021da177e4SLinus Torvalds 			delta2 = -delta2;
8031da177e4SLinus Torvalds 		if (delta3 < 0)
8041da177e4SLinus Torvalds 			delta3 = -delta3;
8051da177e4SLinus Torvalds 		if (delta > delta2)
8061da177e4SLinus Torvalds 			delta = delta2;
8071da177e4SLinus Torvalds 		if (delta > delta3)
8081da177e4SLinus Torvalds 			delta = delta3;
8091da177e4SLinus Torvalds 
8101da177e4SLinus Torvalds 		/*
8111da177e4SLinus Torvalds 		 * delta is now minimum absolute delta.
8121da177e4SLinus Torvalds 		 * Round down by 1 bit on general principles,
8131da177e4SLinus Torvalds 		 * and limit entropy entimate to 12 bits.
8141da177e4SLinus Torvalds 		 */
81540db23e5STheodore Ts'o 		credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
8161da177e4SLinus Torvalds 	}
8171da177e4SLinus Torvalds 	preempt_enable();
8181da177e4SLinus Torvalds }
8191da177e4SLinus Torvalds 
820d251575aSStephen Hemminger void add_input_randomness(unsigned int type, unsigned int code,
8211da177e4SLinus Torvalds 				 unsigned int value)
8221da177e4SLinus Torvalds {
8231da177e4SLinus Torvalds 	static unsigned char last_value;
8241da177e4SLinus Torvalds 
8251da177e4SLinus Torvalds 	/* ignore autorepeat and the like */
8261da177e4SLinus Torvalds 	if (value == last_value)
8271da177e4SLinus Torvalds 		return;
8281da177e4SLinus Torvalds 
8291da177e4SLinus Torvalds 	last_value = value;
8301da177e4SLinus Torvalds 	add_timer_randomness(&input_timer_state,
8311da177e4SLinus Torvalds 			     (type << 4) ^ code ^ (code >> 4) ^ value);
832f80bbd8bSTheodore Ts'o 	trace_add_input_randomness(ENTROPY_BITS(&input_pool));
8331da177e4SLinus Torvalds }
83480fc9f53SDmitry Torokhov EXPORT_SYMBOL_GPL(add_input_randomness);
8351da177e4SLinus Torvalds 
836775f4b29STheodore Ts'o static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
837775f4b29STheodore Ts'o 
838775f4b29STheodore Ts'o void add_interrupt_randomness(int irq, int irq_flags)
8391da177e4SLinus Torvalds {
840775f4b29STheodore Ts'o 	struct entropy_store	*r;
841775f4b29STheodore Ts'o 	struct fast_pool	*fast_pool = &__get_cpu_var(irq_randomness);
842775f4b29STheodore Ts'o 	struct pt_regs		*regs = get_irq_regs();
843775f4b29STheodore Ts'o 	unsigned long		now = jiffies;
844655b2264STheodore Ts'o 	cycles_t		cycles = random_get_entropy();
845655b2264STheodore Ts'o 	__u32			input[4], c_high, j_high;
846655b2264STheodore Ts'o 	__u64			ip;
84783664a69SH. Peter Anvin 	unsigned long		seed;
84883664a69SH. Peter Anvin 	int			credit;
8493060d6feSYinghai Lu 
850655b2264STheodore Ts'o 	c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
851655b2264STheodore Ts'o 	j_high = (sizeof(now) > 4) ? now >> 32 : 0;
852655b2264STheodore Ts'o 	input[0] = cycles ^ j_high ^ irq;
853655b2264STheodore Ts'o 	input[1] = now ^ c_high;
854655b2264STheodore Ts'o 	ip = regs ? instruction_pointer(regs) : _RET_IP_;
855775f4b29STheodore Ts'o 	input[2] = ip;
856775f4b29STheodore Ts'o 	input[3] = ip >> 32;
8573060d6feSYinghai Lu 
858655b2264STheodore Ts'o 	fast_mix(fast_pool, input);
859775f4b29STheodore Ts'o 
860655b2264STheodore Ts'o 	if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ))
8611da177e4SLinus Torvalds 		return;
8621da177e4SLinus Torvalds 
863775f4b29STheodore Ts'o 	fast_pool->last = now;
864775f4b29STheodore Ts'o 
865775f4b29STheodore Ts'o 	r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
866902c098aSTheodore Ts'o 	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL);
86783664a69SH. Peter Anvin 
868775f4b29STheodore Ts'o 	/*
869775f4b29STheodore Ts'o 	 * If we don't have a valid cycle counter, and we see
870775f4b29STheodore Ts'o 	 * back-to-back timer interrupts, then skip giving credit for
87183664a69SH. Peter Anvin 	 * any entropy, otherwise credit 1 bit.
872775f4b29STheodore Ts'o 	 */
87383664a69SH. Peter Anvin 	credit = 1;
874775f4b29STheodore Ts'o 	if (cycles == 0) {
875775f4b29STheodore Ts'o 		if (irq_flags & __IRQF_TIMER) {
876775f4b29STheodore Ts'o 			if (fast_pool->last_timer_intr)
87783664a69SH. Peter Anvin 				credit = 0;
878775f4b29STheodore Ts'o 			fast_pool->last_timer_intr = 1;
879775f4b29STheodore Ts'o 		} else
880775f4b29STheodore Ts'o 			fast_pool->last_timer_intr = 0;
881775f4b29STheodore Ts'o 	}
88283664a69SH. Peter Anvin 
88383664a69SH. Peter Anvin 	/*
88483664a69SH. Peter Anvin 	 * If we have architectural seed generator, produce a seed and
88583664a69SH. Peter Anvin 	 * add it to the pool.  For the sake of paranoia count it as
88683664a69SH. Peter Anvin 	 * 50% entropic.
88783664a69SH. Peter Anvin 	 */
88883664a69SH. Peter Anvin 	if (arch_get_random_seed_long(&seed)) {
88983664a69SH. Peter Anvin 		__mix_pool_bytes(r, &seed, sizeof(seed), NULL);
89083664a69SH. Peter Anvin 		credit += sizeof(seed) * 4;
89183664a69SH. Peter Anvin 	}
89283664a69SH. Peter Anvin 
89383664a69SH. Peter Anvin 	credit_entropy_bits(r, credit);
8941da177e4SLinus Torvalds }
8951da177e4SLinus Torvalds 
8969361401eSDavid Howells #ifdef CONFIG_BLOCK
8971da177e4SLinus Torvalds void add_disk_randomness(struct gendisk *disk)
8981da177e4SLinus Torvalds {
8991da177e4SLinus Torvalds 	if (!disk || !disk->random)
9001da177e4SLinus Torvalds 		return;
9011da177e4SLinus Torvalds 	/* first major is 1, so we get >= 0x200 here */
902f331c029STejun Heo 	add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
903f80bbd8bSTheodore Ts'o 	trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool));
9041da177e4SLinus Torvalds }
905bdcfa3e5SChristoph Hellwig EXPORT_SYMBOL_GPL(add_disk_randomness);
9069361401eSDavid Howells #endif
9071da177e4SLinus Torvalds 
9081da177e4SLinus Torvalds /*********************************************************************
9091da177e4SLinus Torvalds  *
9101da177e4SLinus Torvalds  * Entropy extraction routines
9111da177e4SLinus Torvalds  *
9121da177e4SLinus Torvalds  *********************************************************************/
9131da177e4SLinus Torvalds 
9141da177e4SLinus Torvalds static ssize_t extract_entropy(struct entropy_store *r, void *buf,
9151da177e4SLinus Torvalds 			       size_t nbytes, int min, int rsvd);
9161da177e4SLinus Torvalds 
9171da177e4SLinus Torvalds /*
91825985edcSLucas De Marchi  * This utility inline function is responsible for transferring entropy
9191da177e4SLinus Torvalds  * from the primary pool to the secondary extraction pool. We make
9201da177e4SLinus Torvalds  * sure we pull enough for a 'catastrophic reseed'.
9211da177e4SLinus Torvalds  */
9226265e169STheodore Ts'o static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes);
9231da177e4SLinus Torvalds static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
9241da177e4SLinus Torvalds {
925f5c2742cSTheodore Ts'o 	if (r->limit == 0 && random_min_urandom_seed) {
926f5c2742cSTheodore Ts'o 		unsigned long now = jiffies;
927f5c2742cSTheodore Ts'o 
928f5c2742cSTheodore Ts'o 		if (time_before(now,
929f5c2742cSTheodore Ts'o 				r->last_pulled + random_min_urandom_seed * HZ))
930f5c2742cSTheodore Ts'o 			return;
931f5c2742cSTheodore Ts'o 		r->last_pulled = now;
932f5c2742cSTheodore Ts'o 	}
933a283b5c4SH. Peter Anvin 	if (r->pull &&
934a283b5c4SH. Peter Anvin 	    r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) &&
9356265e169STheodore Ts'o 	    r->entropy_count < r->poolinfo->poolfracbits)
9366265e169STheodore Ts'o 		_xfer_secondary_pool(r, nbytes);
9376265e169STheodore Ts'o }
9386265e169STheodore Ts'o 
9396265e169STheodore Ts'o static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
9406265e169STheodore Ts'o {
9411da177e4SLinus Torvalds 	__u32	tmp[OUTPUT_POOL_WORDS];
9421da177e4SLinus Torvalds 
9432132a96fSGreg Price 	/* For /dev/random's pool, always leave two wakeups' worth */
9442132a96fSGreg Price 	int rsvd_bytes = r->limit ? 0 : random_read_wakeup_bits / 4;
9455a021e9fSMatt Mackall 	int bytes = nbytes;
9465a021e9fSMatt Mackall 
9472132a96fSGreg Price 	/* pull at least as much as a wakeup */
9482132a96fSGreg Price 	bytes = max_t(int, bytes, random_read_wakeup_bits / 8);
9495a021e9fSMatt Mackall 	/* but never more than the buffer size */
950d2e7c96aSH. Peter Anvin 	bytes = min_t(int, bytes, sizeof(tmp));
9511da177e4SLinus Torvalds 
952f80bbd8bSTheodore Ts'o 	trace_xfer_secondary_pool(r->name, bytes * 8, nbytes * 8,
953f80bbd8bSTheodore Ts'o 				  ENTROPY_BITS(r), ENTROPY_BITS(r->pull));
954d2e7c96aSH. Peter Anvin 	bytes = extract_entropy(r->pull, tmp, bytes,
9552132a96fSGreg Price 				random_read_wakeup_bits / 8, rsvd_bytes);
956d2e7c96aSH. Peter Anvin 	mix_pool_bytes(r, tmp, bytes, NULL);
957adc782daSMatt Mackall 	credit_entropy_bits(r, bytes*8);
9581da177e4SLinus Torvalds }
9596265e169STheodore Ts'o 
9606265e169STheodore Ts'o /*
9616265e169STheodore Ts'o  * Used as a workqueue function so that when the input pool is getting
9626265e169STheodore Ts'o  * full, we can "spill over" some entropy to the output pools.  That
9636265e169STheodore Ts'o  * way the output pools can store some of the excess entropy instead
9646265e169STheodore Ts'o  * of letting it go to waste.
9656265e169STheodore Ts'o  */
9666265e169STheodore Ts'o static void push_to_pool(struct work_struct *work)
9676265e169STheodore Ts'o {
9686265e169STheodore Ts'o 	struct entropy_store *r = container_of(work, struct entropy_store,
9696265e169STheodore Ts'o 					      push_work);
9706265e169STheodore Ts'o 	BUG_ON(!r);
9712132a96fSGreg Price 	_xfer_secondary_pool(r, random_read_wakeup_bits/8);
9726265e169STheodore Ts'o 	trace_push_to_pool(r->name, r->entropy_count >> ENTROPY_SHIFT,
9736265e169STheodore Ts'o 			   r->pull->entropy_count >> ENTROPY_SHIFT);
9741da177e4SLinus Torvalds }
9751da177e4SLinus Torvalds 
9761da177e4SLinus Torvalds /*
97719fa5be1SGreg Price  * This function decides how many bytes to actually take from the
97819fa5be1SGreg Price  * given pool, and also debits the entropy count accordingly.
9791da177e4SLinus Torvalds  */
9801da177e4SLinus Torvalds static size_t account(struct entropy_store *r, size_t nbytes, int min,
9811da177e4SLinus Torvalds 		      int reserved)
9821da177e4SLinus Torvalds {
983a283b5c4SH. Peter Anvin 	int have_bytes;
984a283b5c4SH. Peter Anvin 	int entropy_count, orig;
985a283b5c4SH. Peter Anvin 	size_t ibytes;
9861da177e4SLinus Torvalds 
987a283b5c4SH. Peter Anvin 	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
9881da177e4SLinus Torvalds 
9891da177e4SLinus Torvalds 	/* Can we pull enough? */
99010b3a32dSJiri Kosina retry:
99110b3a32dSJiri Kosina 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
992a283b5c4SH. Peter Anvin 	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
993a283b5c4SH. Peter Anvin 	ibytes = nbytes;
994a283b5c4SH. Peter Anvin 	/* If limited, never pull more than available */
995ee1de406SGreg Price 	if (r->limit)
996ee1de406SGreg Price 		ibytes = min_t(size_t, ibytes, have_bytes - reserved);
9970fb7a01aSGreg Price 	if (ibytes < min)
9980fb7a01aSGreg Price 		ibytes = 0;
999f9c6d498STheodore Ts'o 	if (have_bytes >= ibytes + reserved)
1000f9c6d498STheodore Ts'o 		entropy_count -= ibytes << (ENTROPY_SHIFT + 3);
1001f9c6d498STheodore Ts'o 	else
1002f9c6d498STheodore Ts'o 		entropy_count = reserved << (ENTROPY_SHIFT + 3);
1003f9c6d498STheodore Ts'o 
100410b3a32dSJiri Kosina 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
100510b3a32dSJiri Kosina 		goto retry;
10061da177e4SLinus Torvalds 
1007f80bbd8bSTheodore Ts'o 	trace_debit_entropy(r->name, 8 * ibytes);
10080fb7a01aSGreg Price 	if (ibytes &&
10092132a96fSGreg Price 	    (r->entropy_count >> ENTROPY_SHIFT) < random_write_wakeup_bits) {
1010b9809552STheodore Ts'o 		wake_up_interruptible(&random_write_wait);
1011b9809552STheodore Ts'o 		kill_fasync(&fasync, SIGIO, POLL_OUT);
1012b9809552STheodore Ts'o 	}
1013b9809552STheodore Ts'o 
1014a283b5c4SH. Peter Anvin 	return ibytes;
10151da177e4SLinus Torvalds }
10161da177e4SLinus Torvalds 
101719fa5be1SGreg Price /*
101819fa5be1SGreg Price  * This function does the actual extraction for extract_entropy and
101919fa5be1SGreg Price  * extract_entropy_user.
102019fa5be1SGreg Price  *
102119fa5be1SGreg Price  * Note: we assume that .poolwords is a multiple of 16 words.
102219fa5be1SGreg Price  */
10231da177e4SLinus Torvalds static void extract_buf(struct entropy_store *r, __u8 *out)
10241da177e4SLinus Torvalds {
1025602b6aeeSMatt Mackall 	int i;
1026d2e7c96aSH. Peter Anvin 	union {
1027d2e7c96aSH. Peter Anvin 		__u32 w[5];
102885a1f777STheodore Ts'o 		unsigned long l[LONGS(20)];
1029d2e7c96aSH. Peter Anvin 	} hash;
1030d2e7c96aSH. Peter Anvin 	__u32 workspace[SHA_WORKSPACE_WORDS];
1031e68e5b66SMatt Mackall 	__u8 extract[64];
1032902c098aSTheodore Ts'o 	unsigned long flags;
10331da177e4SLinus Torvalds 
10341da177e4SLinus Torvalds 	/*
1035dfd38750SGreg Price 	 * If we have an architectural hardware random number
103646884442STheodore Ts'o 	 * generator, use it for SHA's initial vector
103785a1f777STheodore Ts'o 	 */
103846884442STheodore Ts'o 	sha_init(hash.w);
103985a1f777STheodore Ts'o 	for (i = 0; i < LONGS(20); i++) {
104085a1f777STheodore Ts'o 		unsigned long v;
104185a1f777STheodore Ts'o 		if (!arch_get_random_long(&v))
104285a1f777STheodore Ts'o 			break;
104346884442STheodore Ts'o 		hash.l[i] = v;
104485a1f777STheodore Ts'o 	}
104585a1f777STheodore Ts'o 
104646884442STheodore Ts'o 	/* Generate a hash across the pool, 16 words (512 bits) at a time */
104746884442STheodore Ts'o 	spin_lock_irqsave(&r->lock, flags);
104846884442STheodore Ts'o 	for (i = 0; i < r->poolinfo->poolwords; i += 16)
104946884442STheodore Ts'o 		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
105046884442STheodore Ts'o 
105185a1f777STheodore Ts'o 	/*
10521c0ad3d4SMatt Mackall 	 * We mix the hash back into the pool to prevent backtracking
10531c0ad3d4SMatt Mackall 	 * attacks (where the attacker knows the state of the pool
10541c0ad3d4SMatt Mackall 	 * plus the current outputs, and attempts to find previous
10551c0ad3d4SMatt Mackall 	 * ouputs), unless the hash function can be inverted. By
10561c0ad3d4SMatt Mackall 	 * mixing at least a SHA1 worth of hash data back, we make
10571c0ad3d4SMatt Mackall 	 * brute-forcing the feedback as hard as brute-forcing the
10581c0ad3d4SMatt Mackall 	 * hash.
10591da177e4SLinus Torvalds 	 */
1060d2e7c96aSH. Peter Anvin 	__mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
1061902c098aSTheodore Ts'o 	spin_unlock_irqrestore(&r->lock, flags);
10621c0ad3d4SMatt Mackall 
10631c0ad3d4SMatt Mackall 	/*
10641c0ad3d4SMatt Mackall 	 * To avoid duplicates, we atomically extract a portion of the
10651c0ad3d4SMatt Mackall 	 * pool while mixing, and hash one final time.
10661c0ad3d4SMatt Mackall 	 */
1067d2e7c96aSH. Peter Anvin 	sha_transform(hash.w, extract, workspace);
1068ffd8d3faSMatt Mackall 	memset(extract, 0, sizeof(extract));
1069ffd8d3faSMatt Mackall 	memset(workspace, 0, sizeof(workspace));
10701da177e4SLinus Torvalds 
10711da177e4SLinus Torvalds 	/*
10721c0ad3d4SMatt Mackall 	 * In case the hash function has some recognizable output
10731c0ad3d4SMatt Mackall 	 * pattern, we fold it in half. Thus, we always feed back
10741c0ad3d4SMatt Mackall 	 * twice as much data as we output.
10751da177e4SLinus Torvalds 	 */
1076d2e7c96aSH. Peter Anvin 	hash.w[0] ^= hash.w[3];
1077d2e7c96aSH. Peter Anvin 	hash.w[1] ^= hash.w[4];
1078d2e7c96aSH. Peter Anvin 	hash.w[2] ^= rol32(hash.w[2], 16);
1079d2e7c96aSH. Peter Anvin 
1080d2e7c96aSH. Peter Anvin 	memcpy(out, &hash, EXTRACT_SIZE);
1081d2e7c96aSH. Peter Anvin 	memset(&hash, 0, sizeof(hash));
10821da177e4SLinus Torvalds }
10831da177e4SLinus Torvalds 
108419fa5be1SGreg Price /*
108519fa5be1SGreg Price  * This function extracts randomness from the "entropy pool", and
108619fa5be1SGreg Price  * returns it in a buffer.
108719fa5be1SGreg Price  *
108819fa5be1SGreg Price  * The min parameter specifies the minimum amount we can pull before
108919fa5be1SGreg Price  * failing to avoid races that defeat catastrophic reseeding while the
109019fa5be1SGreg Price  * reserved parameter indicates how much entropy we must leave in the
109119fa5be1SGreg Price  * pool after each pull to avoid starving other readers.
109219fa5be1SGreg Price  */
10931da177e4SLinus Torvalds static ssize_t extract_entropy(struct entropy_store *r, void *buf,
10941da177e4SLinus Torvalds 				 size_t nbytes, int min, int reserved)
10951da177e4SLinus Torvalds {
10961da177e4SLinus Torvalds 	ssize_t ret = 0, i;
10971da177e4SLinus Torvalds 	__u8 tmp[EXTRACT_SIZE];
10981e7e2e05SJarod Wilson 	unsigned long flags;
10991da177e4SLinus Torvalds 
1100ec8f02daSJarod Wilson 	/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
11011e7e2e05SJarod Wilson 	if (fips_enabled) {
11021e7e2e05SJarod Wilson 		spin_lock_irqsave(&r->lock, flags);
11031e7e2e05SJarod Wilson 		if (!r->last_data_init) {
1104c59974aeSTheodore Ts'o 			r->last_data_init = 1;
11051e7e2e05SJarod Wilson 			spin_unlock_irqrestore(&r->lock, flags);
11061e7e2e05SJarod Wilson 			trace_extract_entropy(r->name, EXTRACT_SIZE,
1107a283b5c4SH. Peter Anvin 					      ENTROPY_BITS(r), _RET_IP_);
11081e7e2e05SJarod Wilson 			xfer_secondary_pool(r, EXTRACT_SIZE);
11091e7e2e05SJarod Wilson 			extract_buf(r, tmp);
11101e7e2e05SJarod Wilson 			spin_lock_irqsave(&r->lock, flags);
11111e7e2e05SJarod Wilson 			memcpy(r->last_data, tmp, EXTRACT_SIZE);
11121e7e2e05SJarod Wilson 		}
11131e7e2e05SJarod Wilson 		spin_unlock_irqrestore(&r->lock, flags);
11141e7e2e05SJarod Wilson 	}
1115ec8f02daSJarod Wilson 
1116a283b5c4SH. Peter Anvin 	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
11171da177e4SLinus Torvalds 	xfer_secondary_pool(r, nbytes);
11181da177e4SLinus Torvalds 	nbytes = account(r, nbytes, min, reserved);
11191da177e4SLinus Torvalds 
11201da177e4SLinus Torvalds 	while (nbytes) {
11211da177e4SLinus Torvalds 		extract_buf(r, tmp);
11225b739ef8SNeil Horman 
1123e954bc91SMatt Mackall 		if (fips_enabled) {
11245b739ef8SNeil Horman 			spin_lock_irqsave(&r->lock, flags);
11255b739ef8SNeil Horman 			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
11265b739ef8SNeil Horman 				panic("Hardware RNG duplicated output!\n");
11275b739ef8SNeil Horman 			memcpy(r->last_data, tmp, EXTRACT_SIZE);
11285b739ef8SNeil Horman 			spin_unlock_irqrestore(&r->lock, flags);
11295b739ef8SNeil Horman 		}
11301da177e4SLinus Torvalds 		i = min_t(int, nbytes, EXTRACT_SIZE);
11311da177e4SLinus Torvalds 		memcpy(buf, tmp, i);
11321da177e4SLinus Torvalds 		nbytes -= i;
11331da177e4SLinus Torvalds 		buf += i;
11341da177e4SLinus Torvalds 		ret += i;
11351da177e4SLinus Torvalds 	}
11361da177e4SLinus Torvalds 
11371da177e4SLinus Torvalds 	/* Wipe data just returned from memory */
11381da177e4SLinus Torvalds 	memset(tmp, 0, sizeof(tmp));
11391da177e4SLinus Torvalds 
11401da177e4SLinus Torvalds 	return ret;
11411da177e4SLinus Torvalds }
11421da177e4SLinus Torvalds 
114319fa5be1SGreg Price /*
114419fa5be1SGreg Price  * This function extracts randomness from the "entropy pool", and
114519fa5be1SGreg Price  * returns it in a userspace buffer.
114619fa5be1SGreg Price  */
11471da177e4SLinus Torvalds static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
11481da177e4SLinus Torvalds 				    size_t nbytes)
11491da177e4SLinus Torvalds {
11501da177e4SLinus Torvalds 	ssize_t ret = 0, i;
11511da177e4SLinus Torvalds 	__u8 tmp[EXTRACT_SIZE];
11521da177e4SLinus Torvalds 
1153a283b5c4SH. Peter Anvin 	trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
11541da177e4SLinus Torvalds 	xfer_secondary_pool(r, nbytes);
11551da177e4SLinus Torvalds 	nbytes = account(r, nbytes, 0, 0);
11561da177e4SLinus Torvalds 
11571da177e4SLinus Torvalds 	while (nbytes) {
11581da177e4SLinus Torvalds 		if (need_resched()) {
11591da177e4SLinus Torvalds 			if (signal_pending(current)) {
11601da177e4SLinus Torvalds 				if (ret == 0)
11611da177e4SLinus Torvalds 					ret = -ERESTARTSYS;
11621da177e4SLinus Torvalds 				break;
11631da177e4SLinus Torvalds 			}
11641da177e4SLinus Torvalds 			schedule();
11651da177e4SLinus Torvalds 		}
11661da177e4SLinus Torvalds 
11671da177e4SLinus Torvalds 		extract_buf(r, tmp);
11681da177e4SLinus Torvalds 		i = min_t(int, nbytes, EXTRACT_SIZE);
11691da177e4SLinus Torvalds 		if (copy_to_user(buf, tmp, i)) {
11701da177e4SLinus Torvalds 			ret = -EFAULT;
11711da177e4SLinus Torvalds 			break;
11721da177e4SLinus Torvalds 		}
11731da177e4SLinus Torvalds 
11741da177e4SLinus Torvalds 		nbytes -= i;
11751da177e4SLinus Torvalds 		buf += i;
11761da177e4SLinus Torvalds 		ret += i;
11771da177e4SLinus Torvalds 	}
11781da177e4SLinus Torvalds 
11791da177e4SLinus Torvalds 	/* Wipe data just returned from memory */
11801da177e4SLinus Torvalds 	memset(tmp, 0, sizeof(tmp));
11811da177e4SLinus Torvalds 
11821da177e4SLinus Torvalds 	return ret;
11831da177e4SLinus Torvalds }
11841da177e4SLinus Torvalds 
11851da177e4SLinus Torvalds /*
11861da177e4SLinus Torvalds  * This function is the exported kernel interface.  It returns some
1187c2557a30STheodore Ts'o  * number of good random numbers, suitable for key generation, seeding
118818e9cea7SGreg Price  * TCP sequence numbers, etc.  It does not rely on the hardware random
118918e9cea7SGreg Price  * number generator.  For random bytes direct from the hardware RNG
119018e9cea7SGreg Price  * (when available), use get_random_bytes_arch().
11911da177e4SLinus Torvalds  */
11921da177e4SLinus Torvalds void get_random_bytes(void *buf, int nbytes)
11931da177e4SLinus Torvalds {
1194392a546dSTheodore Ts'o #if DEBUG_RANDOM_BOOT > 0
1195392a546dSTheodore Ts'o 	if (unlikely(nonblocking_pool.initialized == 0))
1196392a546dSTheodore Ts'o 		printk(KERN_NOTICE "random: %pF get_random_bytes called "
1197392a546dSTheodore Ts'o 		       "with %d bits of entropy available\n",
1198392a546dSTheodore Ts'o 		       (void *) _RET_IP_,
1199392a546dSTheodore Ts'o 		       nonblocking_pool.entropy_total);
1200392a546dSTheodore Ts'o #endif
12015910895fSTheodore Ts'o 	trace_get_random_bytes(nbytes, _RET_IP_);
1202c2557a30STheodore Ts'o 	extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
1203c2557a30STheodore Ts'o }
1204c2557a30STheodore Ts'o EXPORT_SYMBOL(get_random_bytes);
1205c2557a30STheodore Ts'o 
1206c2557a30STheodore Ts'o /*
1207c2557a30STheodore Ts'o  * This function will use the architecture-specific hardware random
1208c2557a30STheodore Ts'o  * number generator if it is available.  The arch-specific hw RNG will
1209c2557a30STheodore Ts'o  * almost certainly be faster than what we can do in software, but it
1210c2557a30STheodore Ts'o  * is impossible to verify that it is implemented securely (as
1211c2557a30STheodore Ts'o  * opposed, to, say, the AES encryption of a sequence number using a
1212c2557a30STheodore Ts'o  * key known by the NSA).  So it's useful if we need the speed, but
1213c2557a30STheodore Ts'o  * only if we're willing to trust the hardware manufacturer not to
1214c2557a30STheodore Ts'o  * have put in a back door.
1215c2557a30STheodore Ts'o  */
1216c2557a30STheodore Ts'o void get_random_bytes_arch(void *buf, int nbytes)
1217c2557a30STheodore Ts'o {
121863d77173SH. Peter Anvin 	char *p = buf;
121963d77173SH. Peter Anvin 
12205910895fSTheodore Ts'o 	trace_get_random_bytes_arch(nbytes, _RET_IP_);
122163d77173SH. Peter Anvin 	while (nbytes) {
122263d77173SH. Peter Anvin 		unsigned long v;
122363d77173SH. Peter Anvin 		int chunk = min(nbytes, (int)sizeof(unsigned long));
122463d77173SH. Peter Anvin 
122563d77173SH. Peter Anvin 		if (!arch_get_random_long(&v))
122663d77173SH. Peter Anvin 			break;
122763d77173SH. Peter Anvin 
1228bd29e568SLuck, Tony 		memcpy(p, &v, chunk);
122963d77173SH. Peter Anvin 		p += chunk;
123063d77173SH. Peter Anvin 		nbytes -= chunk;
123163d77173SH. Peter Anvin 	}
123263d77173SH. Peter Anvin 
1233c2557a30STheodore Ts'o 	if (nbytes)
123463d77173SH. Peter Anvin 		extract_entropy(&nonblocking_pool, p, nbytes, 0, 0);
12351da177e4SLinus Torvalds }
1236c2557a30STheodore Ts'o EXPORT_SYMBOL(get_random_bytes_arch);
1237c2557a30STheodore Ts'o 
12381da177e4SLinus Torvalds 
12391da177e4SLinus Torvalds /*
12401da177e4SLinus Torvalds  * init_std_data - initialize pool with system data
12411da177e4SLinus Torvalds  *
12421da177e4SLinus Torvalds  * @r: pool to initialize
12431da177e4SLinus Torvalds  *
12441da177e4SLinus Torvalds  * This function clears the pool's entropy count and mixes some system
12451da177e4SLinus Torvalds  * data into the pool to prepare it for use. The pool is not cleared
12461da177e4SLinus Torvalds  * as that can only decrease the entropy in the pool.
12471da177e4SLinus Torvalds  */
12481da177e4SLinus Torvalds static void init_std_data(struct entropy_store *r)
12491da177e4SLinus Torvalds {
12503e88bdffSTheodore Ts'o 	int i;
1251902c098aSTheodore Ts'o 	ktime_t now = ktime_get_real();
1252902c098aSTheodore Ts'o 	unsigned long rv;
12531da177e4SLinus Torvalds 
1254f5c2742cSTheodore Ts'o 	r->last_pulled = jiffies;
1255902c098aSTheodore Ts'o 	mix_pool_bytes(r, &now, sizeof(now), NULL);
12569ed17b70SH. Peter Anvin 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
125783664a69SH. Peter Anvin 		if (!arch_get_random_seed_long(&rv) &&
125883664a69SH. Peter Anvin 		    !arch_get_random_long(&rv))
1259ae9ecd92STheodore Ts'o 			rv = random_get_entropy();
1260902c098aSTheodore Ts'o 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
12613e88bdffSTheodore Ts'o 	}
1262902c098aSTheodore Ts'o 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
12631da177e4SLinus Torvalds }
12641da177e4SLinus Torvalds 
1265cbc96b75STony Luck /*
1266cbc96b75STony Luck  * Note that setup_arch() may call add_device_randomness()
1267cbc96b75STony Luck  * long before we get here. This allows seeding of the pools
1268cbc96b75STony Luck  * with some platform dependent data very early in the boot
1269cbc96b75STony Luck  * process. But it limits our options here. We must use
1270cbc96b75STony Luck  * statically allocated structures that already have all
1271cbc96b75STony Luck  * initializations complete at compile time. We should also
1272cbc96b75STony Luck  * take care not to overwrite the precious per platform data
1273cbc96b75STony Luck  * we were given.
1274cbc96b75STony Luck  */
127553c3f63eSMatt Mackall static int rand_initialize(void)
12761da177e4SLinus Torvalds {
12771da177e4SLinus Torvalds 	init_std_data(&input_pool);
12781da177e4SLinus Torvalds 	init_std_data(&blocking_pool);
12791da177e4SLinus Torvalds 	init_std_data(&nonblocking_pool);
12801da177e4SLinus Torvalds 	return 0;
12811da177e4SLinus Torvalds }
1282ae9ecd92STheodore Ts'o early_initcall(rand_initialize);
12831da177e4SLinus Torvalds 
12849361401eSDavid Howells #ifdef CONFIG_BLOCK
12851da177e4SLinus Torvalds void rand_initialize_disk(struct gendisk *disk)
12861da177e4SLinus Torvalds {
12871da177e4SLinus Torvalds 	struct timer_rand_state *state;
12881da177e4SLinus Torvalds 
12891da177e4SLinus Torvalds 	/*
1290f8595815SEric Dumazet 	 * If kzalloc returns null, we just won't use that entropy
12911da177e4SLinus Torvalds 	 * source.
12921da177e4SLinus Torvalds 	 */
1293f8595815SEric Dumazet 	state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
1294644008dfSTheodore Ts'o 	if (state) {
1295644008dfSTheodore Ts'o 		state->last_time = INITIAL_JIFFIES;
12961da177e4SLinus Torvalds 		disk->random = state;
12971da177e4SLinus Torvalds 	}
1298644008dfSTheodore Ts'o }
12999361401eSDavid Howells #endif
13001da177e4SLinus Torvalds 
1301331c6490SH. Peter Anvin /*
1302331c6490SH. Peter Anvin  * Attempt an emergency refill using arch_get_random_seed_long().
1303331c6490SH. Peter Anvin  *
1304331c6490SH. Peter Anvin  * As with add_interrupt_randomness() be paranoid and only
1305331c6490SH. Peter Anvin  * credit the output as 50% entropic.
1306331c6490SH. Peter Anvin  */
1307331c6490SH. Peter Anvin static int arch_random_refill(void)
1308331c6490SH. Peter Anvin {
1309331c6490SH. Peter Anvin 	const unsigned int nlongs = 64;	/* Arbitrary number */
1310331c6490SH. Peter Anvin 	unsigned int n = 0;
1311331c6490SH. Peter Anvin 	unsigned int i;
1312331c6490SH. Peter Anvin 	unsigned long buf[nlongs];
1313331c6490SH. Peter Anvin 
13147b878d4bSH. Peter Anvin 	if (!arch_has_random_seed())
13157b878d4bSH. Peter Anvin 		return 0;
13167b878d4bSH. Peter Anvin 
1317331c6490SH. Peter Anvin 	for (i = 0; i < nlongs; i++) {
1318331c6490SH. Peter Anvin 		if (arch_get_random_seed_long(&buf[n]))
1319331c6490SH. Peter Anvin 			n++;
1320331c6490SH. Peter Anvin 	}
1321331c6490SH. Peter Anvin 
1322331c6490SH. Peter Anvin 	if (n) {
1323331c6490SH. Peter Anvin 		unsigned int rand_bytes = n * sizeof(unsigned long);
1324331c6490SH. Peter Anvin 
1325331c6490SH. Peter Anvin 		mix_pool_bytes(&input_pool, buf, rand_bytes, NULL);
1326331c6490SH. Peter Anvin 		credit_entropy_bits(&input_pool, rand_bytes*4);
1327331c6490SH. Peter Anvin 	}
1328331c6490SH. Peter Anvin 
1329331c6490SH. Peter Anvin 	return n;
1330331c6490SH. Peter Anvin }
1331331c6490SH. Peter Anvin 
13321da177e4SLinus Torvalds static ssize_t
13331da177e4SLinus Torvalds random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
13341da177e4SLinus Torvalds {
133512ff3a51SGreg Price 	ssize_t n;
13361da177e4SLinus Torvalds 
13371da177e4SLinus Torvalds 	if (nbytes == 0)
13381da177e4SLinus Torvalds 		return 0;
13391da177e4SLinus Torvalds 
134012ff3a51SGreg Price 	nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
134112ff3a51SGreg Price 	while (1) {
134212ff3a51SGreg Price 		n = extract_entropy_user(&blocking_pool, buf, nbytes);
134312ff3a51SGreg Price 		if (n < 0)
134412ff3a51SGreg Price 			return n;
1345f80bbd8bSTheodore Ts'o 		trace_random_read(n*8, (nbytes-n)*8,
1346f80bbd8bSTheodore Ts'o 				  ENTROPY_BITS(&blocking_pool),
1347f80bbd8bSTheodore Ts'o 				  ENTROPY_BITS(&input_pool));
134812ff3a51SGreg Price 		if (n > 0)
134912ff3a51SGreg Price 			return n;
1350331c6490SH. Peter Anvin 
135112ff3a51SGreg Price 		/* Pool is (near) empty.  Maybe wait and retry. */
13521da177e4SLinus Torvalds 
1353331c6490SH. Peter Anvin 		/* First try an emergency refill */
1354331c6490SH. Peter Anvin 		if (arch_random_refill())
1355331c6490SH. Peter Anvin 			continue;
1356331c6490SH. Peter Anvin 
135712ff3a51SGreg Price 		if (file->f_flags & O_NONBLOCK)
135812ff3a51SGreg Price 			return -EAGAIN;
13591da177e4SLinus Torvalds 
13601da177e4SLinus Torvalds 		wait_event_interruptible(random_read_wait,
1361a283b5c4SH. Peter Anvin 			ENTROPY_BITS(&input_pool) >=
13622132a96fSGreg Price 			random_read_wakeup_bits);
136312ff3a51SGreg Price 		if (signal_pending(current))
136412ff3a51SGreg Price 			return -ERESTARTSYS;
13651da177e4SLinus Torvalds 	}
13661da177e4SLinus Torvalds }
13671da177e4SLinus Torvalds 
13681da177e4SLinus Torvalds static ssize_t
136990b75ee5SMatt Mackall urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
13701da177e4SLinus Torvalds {
1371301f0595STheodore Ts'o 	int ret;
1372301f0595STheodore Ts'o 
1373301f0595STheodore Ts'o 	if (unlikely(nonblocking_pool.initialized == 0))
1374301f0595STheodore Ts'o 		printk_once(KERN_NOTICE "random: %s urandom read "
1375301f0595STheodore Ts'o 			    "with %d bits of entropy available\n",
1376301f0595STheodore Ts'o 			    current->comm, nonblocking_pool.entropy_total);
1377301f0595STheodore Ts'o 
1378301f0595STheodore Ts'o 	ret = extract_entropy_user(&nonblocking_pool, buf, nbytes);
1379f80bbd8bSTheodore Ts'o 
1380f80bbd8bSTheodore Ts'o 	trace_urandom_read(8 * nbytes, ENTROPY_BITS(&nonblocking_pool),
1381f80bbd8bSTheodore Ts'o 			   ENTROPY_BITS(&input_pool));
1382f80bbd8bSTheodore Ts'o 	return ret;
13831da177e4SLinus Torvalds }
13841da177e4SLinus Torvalds 
13851da177e4SLinus Torvalds static unsigned int
13861da177e4SLinus Torvalds random_poll(struct file *file, poll_table * wait)
13871da177e4SLinus Torvalds {
13881da177e4SLinus Torvalds 	unsigned int mask;
13891da177e4SLinus Torvalds 
13901da177e4SLinus Torvalds 	poll_wait(file, &random_read_wait, wait);
13911da177e4SLinus Torvalds 	poll_wait(file, &random_write_wait, wait);
13921da177e4SLinus Torvalds 	mask = 0;
13932132a96fSGreg Price 	if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
13941da177e4SLinus Torvalds 		mask |= POLLIN | POLLRDNORM;
13952132a96fSGreg Price 	if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits)
13961da177e4SLinus Torvalds 		mask |= POLLOUT | POLLWRNORM;
13971da177e4SLinus Torvalds 	return mask;
13981da177e4SLinus Torvalds }
13991da177e4SLinus Torvalds 
14007f397dcdSMatt Mackall static int
14017f397dcdSMatt Mackall write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
14027f397dcdSMatt Mackall {
14037f397dcdSMatt Mackall 	size_t bytes;
14047f397dcdSMatt Mackall 	__u32 buf[16];
14057f397dcdSMatt Mackall 	const char __user *p = buffer;
14067f397dcdSMatt Mackall 
14077f397dcdSMatt Mackall 	while (count > 0) {
14087f397dcdSMatt Mackall 		bytes = min(count, sizeof(buf));
14097f397dcdSMatt Mackall 		if (copy_from_user(&buf, p, bytes))
14107f397dcdSMatt Mackall 			return -EFAULT;
14117f397dcdSMatt Mackall 
14127f397dcdSMatt Mackall 		count -= bytes;
14137f397dcdSMatt Mackall 		p += bytes;
14147f397dcdSMatt Mackall 
1415902c098aSTheodore Ts'o 		mix_pool_bytes(r, buf, bytes, NULL);
141691f3f1e3SMatt Mackall 		cond_resched();
14177f397dcdSMatt Mackall 	}
14187f397dcdSMatt Mackall 
14197f397dcdSMatt Mackall 	return 0;
14207f397dcdSMatt Mackall }
14217f397dcdSMatt Mackall 
142290b75ee5SMatt Mackall static ssize_t random_write(struct file *file, const char __user *buffer,
14231da177e4SLinus Torvalds 			    size_t count, loff_t *ppos)
14241da177e4SLinus Torvalds {
14257f397dcdSMatt Mackall 	size_t ret;
14267f397dcdSMatt Mackall 
14277f397dcdSMatt Mackall 	ret = write_pool(&blocking_pool, buffer, count);
14287f397dcdSMatt Mackall 	if (ret)
14297f397dcdSMatt Mackall 		return ret;
14307f397dcdSMatt Mackall 	ret = write_pool(&nonblocking_pool, buffer, count);
14317f397dcdSMatt Mackall 	if (ret)
14327f397dcdSMatt Mackall 		return ret;
14337f397dcdSMatt Mackall 
14347f397dcdSMatt Mackall 	return (ssize_t)count;
14351da177e4SLinus Torvalds }
14361da177e4SLinus Torvalds 
143743ae4860SMatt Mackall static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
14381da177e4SLinus Torvalds {
14391da177e4SLinus Torvalds 	int size, ent_count;
14401da177e4SLinus Torvalds 	int __user *p = (int __user *)arg;
14411da177e4SLinus Torvalds 	int retval;
14421da177e4SLinus Torvalds 
14431da177e4SLinus Torvalds 	switch (cmd) {
14441da177e4SLinus Torvalds 	case RNDGETENTCNT:
144543ae4860SMatt Mackall 		/* inherently racy, no point locking */
1446a283b5c4SH. Peter Anvin 		ent_count = ENTROPY_BITS(&input_pool);
1447a283b5c4SH. Peter Anvin 		if (put_user(ent_count, p))
14481da177e4SLinus Torvalds 			return -EFAULT;
14491da177e4SLinus Torvalds 		return 0;
14501da177e4SLinus Torvalds 	case RNDADDTOENTCNT:
14511da177e4SLinus Torvalds 		if (!capable(CAP_SYS_ADMIN))
14521da177e4SLinus Torvalds 			return -EPERM;
14531da177e4SLinus Torvalds 		if (get_user(ent_count, p))
14541da177e4SLinus Torvalds 			return -EFAULT;
1455a283b5c4SH. Peter Anvin 		credit_entropy_bits_safe(&input_pool, ent_count);
14561da177e4SLinus Torvalds 		return 0;
14571da177e4SLinus Torvalds 	case RNDADDENTROPY:
14581da177e4SLinus Torvalds 		if (!capable(CAP_SYS_ADMIN))
14591da177e4SLinus Torvalds 			return -EPERM;
14601da177e4SLinus Torvalds 		if (get_user(ent_count, p++))
14611da177e4SLinus Torvalds 			return -EFAULT;
14621da177e4SLinus Torvalds 		if (ent_count < 0)
14631da177e4SLinus Torvalds 			return -EINVAL;
14641da177e4SLinus Torvalds 		if (get_user(size, p++))
14651da177e4SLinus Torvalds 			return -EFAULT;
14667f397dcdSMatt Mackall 		retval = write_pool(&input_pool, (const char __user *)p,
14677f397dcdSMatt Mackall 				    size);
14681da177e4SLinus Torvalds 		if (retval < 0)
14691da177e4SLinus Torvalds 			return retval;
1470a283b5c4SH. Peter Anvin 		credit_entropy_bits_safe(&input_pool, ent_count);
14711da177e4SLinus Torvalds 		return 0;
14721da177e4SLinus Torvalds 	case RNDZAPENTCNT:
14731da177e4SLinus Torvalds 	case RNDCLEARPOOL:
1474ae9ecd92STheodore Ts'o 		/*
1475ae9ecd92STheodore Ts'o 		 * Clear the entropy pool counters. We no longer clear
1476ae9ecd92STheodore Ts'o 		 * the entropy pool, as that's silly.
1477ae9ecd92STheodore Ts'o 		 */
14781da177e4SLinus Torvalds 		if (!capable(CAP_SYS_ADMIN))
14791da177e4SLinus Torvalds 			return -EPERM;
1480ae9ecd92STheodore Ts'o 		input_pool.entropy_count = 0;
1481ae9ecd92STheodore Ts'o 		nonblocking_pool.entropy_count = 0;
1482ae9ecd92STheodore Ts'o 		blocking_pool.entropy_count = 0;
14831da177e4SLinus Torvalds 		return 0;
14841da177e4SLinus Torvalds 	default:
14851da177e4SLinus Torvalds 		return -EINVAL;
14861da177e4SLinus Torvalds 	}
14871da177e4SLinus Torvalds }
14881da177e4SLinus Torvalds 
14899a6f70bbSJeff Dike static int random_fasync(int fd, struct file *filp, int on)
14909a6f70bbSJeff Dike {
14919a6f70bbSJeff Dike 	return fasync_helper(fd, filp, on, &fasync);
14929a6f70bbSJeff Dike }
14939a6f70bbSJeff Dike 
14942b8693c0SArjan van de Ven const struct file_operations random_fops = {
14951da177e4SLinus Torvalds 	.read  = random_read,
14961da177e4SLinus Torvalds 	.write = random_write,
14971da177e4SLinus Torvalds 	.poll  = random_poll,
149843ae4860SMatt Mackall 	.unlocked_ioctl = random_ioctl,
14999a6f70bbSJeff Dike 	.fasync = random_fasync,
15006038f373SArnd Bergmann 	.llseek = noop_llseek,
15011da177e4SLinus Torvalds };
15021da177e4SLinus Torvalds 
15032b8693c0SArjan van de Ven const struct file_operations urandom_fops = {
15041da177e4SLinus Torvalds 	.read  = urandom_read,
15051da177e4SLinus Torvalds 	.write = random_write,
150643ae4860SMatt Mackall 	.unlocked_ioctl = random_ioctl,
15079a6f70bbSJeff Dike 	.fasync = random_fasync,
15086038f373SArnd Bergmann 	.llseek = noop_llseek,
15091da177e4SLinus Torvalds };
15101da177e4SLinus Torvalds 
15111da177e4SLinus Torvalds /***************************************************************
15121da177e4SLinus Torvalds  * Random UUID interface
15131da177e4SLinus Torvalds  *
15141da177e4SLinus Torvalds  * Used here for a Boot ID, but can be useful for other kernel
15151da177e4SLinus Torvalds  * drivers.
15161da177e4SLinus Torvalds  ***************************************************************/
15171da177e4SLinus Torvalds 
15181da177e4SLinus Torvalds /*
15191da177e4SLinus Torvalds  * Generate random UUID
15201da177e4SLinus Torvalds  */
15211da177e4SLinus Torvalds void generate_random_uuid(unsigned char uuid_out[16])
15221da177e4SLinus Torvalds {
15231da177e4SLinus Torvalds 	get_random_bytes(uuid_out, 16);
1524c41b20e7SAdam Buchbinder 	/* Set UUID version to 4 --- truly random generation */
15251da177e4SLinus Torvalds 	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
15261da177e4SLinus Torvalds 	/* Set the UUID variant to DCE */
15271da177e4SLinus Torvalds 	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
15281da177e4SLinus Torvalds }
15291da177e4SLinus Torvalds EXPORT_SYMBOL(generate_random_uuid);
15301da177e4SLinus Torvalds 
15311da177e4SLinus Torvalds /********************************************************************
15321da177e4SLinus Torvalds  *
15331da177e4SLinus Torvalds  * Sysctl interface
15341da177e4SLinus Torvalds  *
15351da177e4SLinus Torvalds  ********************************************************************/
15361da177e4SLinus Torvalds 
15371da177e4SLinus Torvalds #ifdef CONFIG_SYSCTL
15381da177e4SLinus Torvalds 
15391da177e4SLinus Torvalds #include <linux/sysctl.h>
15401da177e4SLinus Torvalds 
15411da177e4SLinus Torvalds static int min_read_thresh = 8, min_write_thresh;
15428c2aa339SGreg Price static int max_read_thresh = OUTPUT_POOL_WORDS * 32;
15431da177e4SLinus Torvalds static int max_write_thresh = INPUT_POOL_WORDS * 32;
15441da177e4SLinus Torvalds static char sysctl_bootid[16];
15451da177e4SLinus Torvalds 
15461da177e4SLinus Torvalds /*
1547f22052b2SGreg Price  * This function is used to return both the bootid UUID, and random
15481da177e4SLinus Torvalds  * UUID.  The difference is in whether table->data is NULL; if it is,
15491da177e4SLinus Torvalds  * then a new UUID is generated and returned to the user.
15501da177e4SLinus Torvalds  *
1551f22052b2SGreg Price  * If the user accesses this via the proc interface, the UUID will be
1552f22052b2SGreg Price  * returned as an ASCII string in the standard UUID format; if via the
1553f22052b2SGreg Price  * sysctl system call, as 16 bytes of binary data.
15541da177e4SLinus Torvalds  */
1555a151427eSJoe Perches static int proc_do_uuid(struct ctl_table *table, int write,
15561da177e4SLinus Torvalds 			void __user *buffer, size_t *lenp, loff_t *ppos)
15571da177e4SLinus Torvalds {
1558a151427eSJoe Perches 	struct ctl_table fake_table;
15591da177e4SLinus Torvalds 	unsigned char buf[64], tmp_uuid[16], *uuid;
15601da177e4SLinus Torvalds 
15611da177e4SLinus Torvalds 	uuid = table->data;
15621da177e4SLinus Torvalds 	if (!uuid) {
15631da177e4SLinus Torvalds 		uuid = tmp_uuid;
15641da177e4SLinus Torvalds 		generate_random_uuid(uuid);
156544e4360fSMathieu Desnoyers 	} else {
156644e4360fSMathieu Desnoyers 		static DEFINE_SPINLOCK(bootid_spinlock);
156744e4360fSMathieu Desnoyers 
156844e4360fSMathieu Desnoyers 		spin_lock(&bootid_spinlock);
156944e4360fSMathieu Desnoyers 		if (!uuid[8])
157044e4360fSMathieu Desnoyers 			generate_random_uuid(uuid);
157144e4360fSMathieu Desnoyers 		spin_unlock(&bootid_spinlock);
157244e4360fSMathieu Desnoyers 	}
15731da177e4SLinus Torvalds 
157435900771SJoe Perches 	sprintf(buf, "%pU", uuid);
157535900771SJoe Perches 
15761da177e4SLinus Torvalds 	fake_table.data = buf;
15771da177e4SLinus Torvalds 	fake_table.maxlen = sizeof(buf);
15781da177e4SLinus Torvalds 
15798d65af78SAlexey Dobriyan 	return proc_dostring(&fake_table, write, buffer, lenp, ppos);
15801da177e4SLinus Torvalds }
15811da177e4SLinus Torvalds 
1582a283b5c4SH. Peter Anvin /*
1583a283b5c4SH. Peter Anvin  * Return entropy available scaled to integral bits
1584a283b5c4SH. Peter Anvin  */
1585*5eb10d91SJoe Perches static int proc_do_entropy(struct ctl_table *table, int write,
1586a283b5c4SH. Peter Anvin 			   void __user *buffer, size_t *lenp, loff_t *ppos)
1587a283b5c4SH. Peter Anvin {
1588*5eb10d91SJoe Perches 	struct ctl_table fake_table;
1589a283b5c4SH. Peter Anvin 	int entropy_count;
1590a283b5c4SH. Peter Anvin 
1591a283b5c4SH. Peter Anvin 	entropy_count = *(int *)table->data >> ENTROPY_SHIFT;
1592a283b5c4SH. Peter Anvin 
1593a283b5c4SH. Peter Anvin 	fake_table.data = &entropy_count;
1594a283b5c4SH. Peter Anvin 	fake_table.maxlen = sizeof(entropy_count);
1595a283b5c4SH. Peter Anvin 
1596a283b5c4SH. Peter Anvin 	return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
1597a283b5c4SH. Peter Anvin }
1598a283b5c4SH. Peter Anvin 
15991da177e4SLinus Torvalds static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
1600a151427eSJoe Perches extern struct ctl_table random_table[];
1601a151427eSJoe Perches struct ctl_table random_table[] = {
16021da177e4SLinus Torvalds 	{
16031da177e4SLinus Torvalds 		.procname	= "poolsize",
16041da177e4SLinus Torvalds 		.data		= &sysctl_poolsize,
16051da177e4SLinus Torvalds 		.maxlen		= sizeof(int),
16061da177e4SLinus Torvalds 		.mode		= 0444,
16076d456111SEric W. Biederman 		.proc_handler	= proc_dointvec,
16081da177e4SLinus Torvalds 	},
16091da177e4SLinus Torvalds 	{
16101da177e4SLinus Torvalds 		.procname	= "entropy_avail",
16111da177e4SLinus Torvalds 		.maxlen		= sizeof(int),
16121da177e4SLinus Torvalds 		.mode		= 0444,
1613a283b5c4SH. Peter Anvin 		.proc_handler	= proc_do_entropy,
16141da177e4SLinus Torvalds 		.data		= &input_pool.entropy_count,
16151da177e4SLinus Torvalds 	},
16161da177e4SLinus Torvalds 	{
16171da177e4SLinus Torvalds 		.procname	= "read_wakeup_threshold",
16182132a96fSGreg Price 		.data		= &random_read_wakeup_bits,
16191da177e4SLinus Torvalds 		.maxlen		= sizeof(int),
16201da177e4SLinus Torvalds 		.mode		= 0644,
16216d456111SEric W. Biederman 		.proc_handler	= proc_dointvec_minmax,
16221da177e4SLinus Torvalds 		.extra1		= &min_read_thresh,
16231da177e4SLinus Torvalds 		.extra2		= &max_read_thresh,
16241da177e4SLinus Torvalds 	},
16251da177e4SLinus Torvalds 	{
16261da177e4SLinus Torvalds 		.procname	= "write_wakeup_threshold",
16272132a96fSGreg Price 		.data		= &random_write_wakeup_bits,
16281da177e4SLinus Torvalds 		.maxlen		= sizeof(int),
16291da177e4SLinus Torvalds 		.mode		= 0644,
16306d456111SEric W. Biederman 		.proc_handler	= proc_dointvec_minmax,
16311da177e4SLinus Torvalds 		.extra1		= &min_write_thresh,
16321da177e4SLinus Torvalds 		.extra2		= &max_write_thresh,
16331da177e4SLinus Torvalds 	},
16341da177e4SLinus Torvalds 	{
1635f5c2742cSTheodore Ts'o 		.procname	= "urandom_min_reseed_secs",
1636f5c2742cSTheodore Ts'o 		.data		= &random_min_urandom_seed,
1637f5c2742cSTheodore Ts'o 		.maxlen		= sizeof(int),
1638f5c2742cSTheodore Ts'o 		.mode		= 0644,
1639f5c2742cSTheodore Ts'o 		.proc_handler	= proc_dointvec,
1640f5c2742cSTheodore Ts'o 	},
1641f5c2742cSTheodore Ts'o 	{
16421da177e4SLinus Torvalds 		.procname	= "boot_id",
16431da177e4SLinus Torvalds 		.data		= &sysctl_bootid,
16441da177e4SLinus Torvalds 		.maxlen		= 16,
16451da177e4SLinus Torvalds 		.mode		= 0444,
16466d456111SEric W. Biederman 		.proc_handler	= proc_do_uuid,
16471da177e4SLinus Torvalds 	},
16481da177e4SLinus Torvalds 	{
16491da177e4SLinus Torvalds 		.procname	= "uuid",
16501da177e4SLinus Torvalds 		.maxlen		= 16,
16511da177e4SLinus Torvalds 		.mode		= 0444,
16526d456111SEric W. Biederman 		.proc_handler	= proc_do_uuid,
16531da177e4SLinus Torvalds 	},
1654894d2491SEric W. Biederman 	{ }
16551da177e4SLinus Torvalds };
16561da177e4SLinus Torvalds #endif 	/* CONFIG_SYSCTL */
16571da177e4SLinus Torvalds 
16586e5714eaSDavid S. Miller static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
16591da177e4SLinus Torvalds 
166047d06e53STheodore Ts'o int random_int_secret_init(void)
16611da177e4SLinus Torvalds {
16626e5714eaSDavid S. Miller 	get_random_bytes(random_int_secret, sizeof(random_int_secret));
16631da177e4SLinus Torvalds 	return 0;
16641da177e4SLinus Torvalds }
16651da177e4SLinus Torvalds 
16661da177e4SLinus Torvalds /*
16671da177e4SLinus Torvalds  * Get a random word for internal kernel use only. Similar to urandom but
16681da177e4SLinus Torvalds  * with the goal of minimal entropy pool depletion. As a result, the random
16691da177e4SLinus Torvalds  * value is not cryptographically secure but for several uses the cost of
16701da177e4SLinus Torvalds  * depleting entropy is too high
16711da177e4SLinus Torvalds  */
167274feec5dSTheodore Ts'o static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
16731da177e4SLinus Torvalds unsigned int get_random_int(void)
16741da177e4SLinus Torvalds {
167563d77173SH. Peter Anvin 	__u32 *hash;
16766e5714eaSDavid S. Miller 	unsigned int ret;
16778a0a9bd4SLinus Torvalds 
167863d77173SH. Peter Anvin 	if (arch_get_random_int(&ret))
167963d77173SH. Peter Anvin 		return ret;
168063d77173SH. Peter Anvin 
168163d77173SH. Peter Anvin 	hash = get_cpu_var(get_random_int_hash);
16828a0a9bd4SLinus Torvalds 
168361875f30STheodore Ts'o 	hash[0] += current->pid + jiffies + random_get_entropy();
16846e5714eaSDavid S. Miller 	md5_transform(hash, random_int_secret);
16856e5714eaSDavid S. Miller 	ret = hash[0];
16868a0a9bd4SLinus Torvalds 	put_cpu_var(get_random_int_hash);
16878a0a9bd4SLinus Torvalds 
16888a0a9bd4SLinus Torvalds 	return ret;
16891da177e4SLinus Torvalds }
169016c7fa05SAndy Shevchenko EXPORT_SYMBOL(get_random_int);
16911da177e4SLinus Torvalds 
16921da177e4SLinus Torvalds /*
16931da177e4SLinus Torvalds  * randomize_range() returns a start address such that
16941da177e4SLinus Torvalds  *
16951da177e4SLinus Torvalds  *    [...... <range> .....]
16961da177e4SLinus Torvalds  *  start                  end
16971da177e4SLinus Torvalds  *
16981da177e4SLinus Torvalds  * a <range> with size "len" starting at the return value is inside in the
16991da177e4SLinus Torvalds  * area defined by [start, end], but is otherwise randomized.
17001da177e4SLinus Torvalds  */
17011da177e4SLinus Torvalds unsigned long
17021da177e4SLinus Torvalds randomize_range(unsigned long start, unsigned long end, unsigned long len)
17031da177e4SLinus Torvalds {
17041da177e4SLinus Torvalds 	unsigned long range = end - len - start;
17051da177e4SLinus Torvalds 
17061da177e4SLinus Torvalds 	if (end <= start + len)
17071da177e4SLinus Torvalds 		return 0;
17081da177e4SLinus Torvalds 	return PAGE_ALIGN(get_random_int() % range + start);
17091da177e4SLinus Torvalds }
1710