Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
random.c
Go to the documentation of this file.
1 /*
2  * random.c -- A strong random number generator
3  *
4  * Copyright Matt Mackall <[email protected]>, 2003, 2004, 2005
5  *
6  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
7  * rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, and the entire permission notice in its entirety,
14  * including the disclaimer of warranties.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  * 3. The name of the author may not be used to endorse or promote
19  * products derived from this software without specific prior
20  * written permission.
21  *
22  * ALTERNATIVELY, this product may be distributed under the terms of
23  * the GNU General Public License, in which case the provisions of the GPL are
24  * required INSTEAD OF the above restrictions. (This clause is
25  * necessary due to a potential bad interaction between the GPL and
26  * the restrictions contained in a BSD-style copyright.)
27  *
28  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
29  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
30  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
31  * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
32  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
33  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
34  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
35  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
38  * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
39  * DAMAGE.
40  */
41 
42 /*
43  * (now, with legal B.S. out of the way.....)
44  *
45  * This routine gathers environmental noise from device drivers, etc.,
46  * and returns good random numbers, suitable for cryptographic use.
47  * Besides the obvious cryptographic uses, these numbers are also good
48  * for seeding TCP sequence numbers, and other places where it is
49  * desirable to have numbers which are not only random, but hard to
50  * predict by an attacker.
51  *
52  * Theory of operation
53  * ===================
54  *
55  * Computers are very predictable devices. Hence it is extremely hard
56  * to produce truly random numbers on a computer --- as opposed to
57  * pseudo-random numbers, which can easily generated by using a
58  * algorithm. Unfortunately, it is very easy for attackers to guess
59  * the sequence of pseudo-random number generators, and for some
60  * applications this is not acceptable. So instead, we must try to
61  * gather "environmental noise" from the computer's environment, which
62  * must be hard for outside attackers to observe, and use that to
63  * generate random numbers. In a Unix environment, this is best done
64  * from inside the kernel.
65  *
66  * Sources of randomness from the environment include inter-keyboard
67  * timings, inter-interrupt timings from some interrupts, and other
68  * events which are both (a) non-deterministic and (b) hard for an
69  * outside observer to measure. Randomness from these sources are
70  * added to an "entropy pool", which is mixed using a CRC-like function.
71  * This is not cryptographically strong, but it is adequate assuming
72  * the randomness is not chosen maliciously, and it is fast enough that
73  * the overhead of doing it on every interrupt is very reasonable.
74  * As random bytes are mixed into the entropy pool, the routines keep
75  * an *estimate* of how many bits of randomness have been stored into
76  * the random number generator's internal state.
77  *
78  * When random bytes are desired, they are obtained by taking the SHA
79  * hash of the contents of the "entropy pool". The SHA hash avoids
80  * exposing the internal state of the entropy pool. It is believed to
81  * be computationally infeasible to derive any useful information
82  * about the input of SHA from its output. Even if it is possible to
83  * analyze SHA in some clever way, as long as the amount of data
84  * returned from the generator is less than the inherent entropy in
85  * the pool, the output data is totally unpredictable. For this
86  * reason, the routine decreases its internal estimate of how many
87  * bits of "true randomness" are contained in the entropy pool as it
88  * outputs random numbers.
89  *
90  * If this estimate goes to zero, the routine can still generate
91  * random numbers; however, an attacker may (at least in theory) be
92  * able to infer the future output of the generator from prior
93  * outputs. This requires successful cryptanalysis of SHA, which is
94  * not believed to be feasible, but there is a remote possibility.
95  * Nonetheless, these numbers should be useful for the vast majority
96  * of purposes.
97  *
98  * Exported interfaces ---- output
99  * ===============================
100  *
101  * There are three exported interfaces; the first is one designed to
102  * be used from within the kernel:
103  *
104  * void get_random_bytes(void *buf, int nbytes);
105  *
106  * This interface will return the requested number of random bytes,
107  * and place it in the requested buffer.
108  *
109  * The two other interfaces are two character devices /dev/random and
110  * /dev/urandom. /dev/random is suitable for use when very high
111  * quality randomness is desired (for example, for key generation or
112  * one-time pads), as it will only return a maximum of the number of
113  * bits of randomness (as estimated by the random number generator)
114  * contained in the entropy pool.
115  *
116  * The /dev/urandom device does not have this limit, and will return
117  * as many bytes as are requested. As more and more random bytes are
118  * requested without giving time for the entropy pool to recharge,
119  * this will result in random numbers that are merely cryptographically
120  * strong. For many applications, however, this is acceptable.
121  *
122  * Exported interfaces ---- input
123  * ==============================
124  *
125  * The current exported interfaces for gathering environmental noise
126  * from the devices are:
127  *
128  * void add_device_randomness(const void *buf, unsigned int size);
129  * void add_input_randomness(unsigned int type, unsigned int code,
130  * unsigned int value);
131  * void add_interrupt_randomness(int irq, int irq_flags);
132  * void add_disk_randomness(struct gendisk *disk);
133  *
134  * add_device_randomness() is for adding data to the random pool that
135  * is likely to differ between two devices (or possibly even per boot).
136  * This would be things like MAC addresses or serial numbers, or the
137  * read-out of the RTC. This does *not* add any actual entropy to the
138  * pool, but it initializes the pool to different values for devices
139  * that might otherwise be identical and have very little entropy
140  * available to them (particularly common in the embedded world).
141  *
142  * add_input_randomness() uses the input layer interrupt timing, as well as
143  * the event type information from the hardware.
144  *
145  * add_interrupt_randomness() uses the interrupt timing as random
146  * inputs to the entropy pool. Using the cycle counters and the irq source
147  * as inputs, it feeds the randomness roughly once a second.
148  *
149  * add_disk_randomness() uses what amounts to the seek time of block
150  * layer request events, on a per-disk_devt basis, as input to the
151  * entropy pool. Note that high-speed solid state drives with very low
152  * seek times do not make for good sources of entropy, as their seek
153  * times are usually fairly consistent.
154  *
155  * All of these routines try to estimate how many bits of randomness a
156  * particular randomness source. They do this by keeping track of the
157  * first and second order deltas of the event timings.
158  *
159  * Ensuring unpredictability at system startup
160  * ============================================
161  *
162  * When any operating system starts up, it will go through a sequence
163  * of actions that are fairly predictable by an adversary, especially
164  * if the start-up does not involve interaction with a human operator.
165  * This reduces the actual number of bits of unpredictability in the
166  * entropy pool below the value in entropy_count. In order to
167  * counteract this effect, it helps to carry information in the
168  * entropy pool across shut-downs and start-ups. To do this, put the
169  * following lines an appropriate script which is run during the boot
170  * sequence:
171  *
172  * echo "Initializing random number generator..."
173  * random_seed=/var/run/random-seed
174  * # Carry a random seed from start-up to start-up
175  * # Load and then save the whole entropy pool
176  * if [ -f $random_seed ]; then
177  * cat $random_seed >/dev/urandom
178  * else
179  * touch $random_seed
180  * fi
181  * chmod 600 $random_seed
182  * dd if=/dev/urandom of=$random_seed count=1 bs=512
183  *
184  * and the following lines in an appropriate script which is run as
185  * the system is shutdown:
186  *
187  * # Carry a random seed from shut-down to start-up
188  * # Save the whole entropy pool
189  * echo "Saving random seed..."
190  * random_seed=/var/run/random-seed
191  * touch $random_seed
192  * chmod 600 $random_seed
193  * dd if=/dev/urandom of=$random_seed count=1 bs=512
194  *
195  * For example, on most modern systems using the System V init
196  * scripts, such code fragments would be found in
197  * /etc/rc.d/init.d/random. On older Linux systems, the correct script
198  * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
199  *
200  * Effectively, these commands cause the contents of the entropy pool
201  * to be saved at shut-down time and reloaded into the entropy pool at
202  * start-up. (The 'dd' in the addition to the bootup script is to
203  * make sure that /etc/random-seed is different for every start-up,
204  * even if the system crashes without executing rc.0.) Even with
205  * complete knowledge of the start-up activities, predicting the state
206  * of the entropy pool requires knowledge of the previous history of
207  * the system.
208  *
209  * Configuring the /dev/random driver under Linux
210  * ==============================================
211  *
212  * The /dev/random driver under Linux uses minor numbers 8 and 9 of
213  * the /dev/mem major number (#1). So if your system does not have
214  * /dev/random and /dev/urandom created already, they can be created
215  * by using the commands:
216  *
217  * mknod /dev/random c 1 8
218  * mknod /dev/urandom c 1 9
219  *
220  * Acknowledgements:
221  * =================
222  *
223  * Ideas for constructing this random number generator were derived
224  * from Pretty Good Privacy's random number generator, and from private
225  * discussions with Phil Karn. Colin Plumb provided a faster random
226  * number generator, which speed up the mixing function of the entropy
227  * pool, taken from PGPfone. Dale Worley has also contributed many
228  * useful ideas and suggestions to improve this driver.
229  *
230  * Any flaws in the design are solely my responsibility, and should
231  * not be attributed to the Phil, Colin, or any of authors of PGP.
232  *
233  * Further background information on this topic may be obtained from
234  * RFC 1750, "Randomness Recommendations for Security", by Donald
235  * Eastlake, Steve Crocker, and Jeff Schiller.
236  */
237 
238 #include <linux/utsname.h>
239 #include <linux/module.h>
240 #include <linux/kernel.h>
241 #include <linux/major.h>
242 #include <linux/string.h>
243 #include <linux/fcntl.h>
244 #include <linux/slab.h>
245 #include <linux/random.h>
246 #include <linux/poll.h>
247 #include <linux/init.h>
248 #include <linux/fs.h>
249 #include <linux/genhd.h>
250 #include <linux/interrupt.h>
251 #include <linux/mm.h>
252 #include <linux/spinlock.h>
253 #include <linux/percpu.h>
254 #include <linux/cryptohash.h>
255 #include <linux/fips.h>
256 #include <linux/ptrace.h>
257 #include <linux/kmemcheck.h>
258 
259 #ifdef CONFIG_GENERIC_HARDIRQS
260 # include <linux/irq.h>
261 #endif
262 
263 #include <asm/processor.h>
264 #include <asm/uaccess.h>
265 #include <asm/irq.h>
266 #include <asm/irq_regs.h>
267 #include <asm/io.h>
268 
269 #define CREATE_TRACE_POINTS
270 #include <trace/events/random.h>
271 
272 /*
273  * Configuration information
274  */
275 #define INPUT_POOL_WORDS 128
276 #define OUTPUT_POOL_WORDS 32
277 #define SEC_XFER_SIZE 512
278 #define EXTRACT_SIZE 10
279 
280 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
281 
282 /*
283  * The minimum number of bits of entropy before we wake up a read on
284  * /dev/random. Should be enough to do a significant reseed.
285  */
286 static int random_read_wakeup_thresh = 64;
287 
288 /*
289  * If the entropy count falls under this number of bits, then we
290  * should wake up processes which are selecting or polling on write
291  * access to /dev/random.
292  */
293 static int random_write_wakeup_thresh = 128;
294 
295 /*
296  * When the input pool goes over trickle_thresh, start dropping most
297  * samples to avoid wasting CPU time and reduce lock contention.
298  */
299 
300 static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
301 
302 static DEFINE_PER_CPU(int, trickle_count);
303 
304 /*
305  * A pool of size .poolwords is stirred with a primitive polynomial
306  * of degree .poolwords over GF(2). The taps for various sizes are
307  * defined below. They are chosen to be evenly spaced (minimum RMS
308  * distance from evenly spaced; the numbers in the comments are a
309  * scaled squared error sum) except for the last tap, which is 1 to
310  * get the twisting happening as fast as possible.
311  */
312 static struct poolinfo {
313  int poolwords;
314  int tap1, tap2, tap3, tap4, tap5;
315 } poolinfo_table[] = {
316  /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
317  { 128, 103, 76, 51, 25, 1 },
318  /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
319  { 32, 26, 20, 14, 7, 1 },
320 #if 0
321  /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */
322  { 2048, 1638, 1231, 819, 411, 1 },
323 
324  /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
325  { 1024, 817, 615, 412, 204, 1 },
326 
327  /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
328  { 1024, 819, 616, 410, 207, 2 },
329 
330  /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
331  { 512, 411, 308, 208, 104, 1 },
332 
333  /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
334  { 512, 409, 307, 206, 102, 2 },
335  /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
336  { 512, 409, 309, 205, 103, 2 },
337 
338  /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
339  { 256, 205, 155, 101, 52, 1 },
340 
341  /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
342  { 128, 103, 78, 51, 27, 2 },
343 
344  /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
345  { 64, 52, 39, 26, 14, 1 },
346 #endif
347 };
348 
349 #define POOLBITS poolwords*32
350 #define POOLBYTES poolwords*4
351 
352 /*
353  * For the purposes of better mixing, we use the CRC-32 polynomial as
354  * well to make a twisted Generalized Feedback Shift Reigster
355  *
356  * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM
357  * Transactions on Modeling and Computer Simulation 2(3):179-194.
358  * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators
359  * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266)
360  *
361  * Thanks to Colin Plumb for suggesting this.
362  *
363  * We have not analyzed the resultant polynomial to prove it primitive;
364  * in fact it almost certainly isn't. Nonetheless, the irreducible factors
365  * of a random large-degree polynomial over GF(2) are more than large enough
366  * that periodicity is not a concern.
367  *
368  * The input hash is much less sensitive than the output hash. All
369  * that we want of it is that it be a good non-cryptographic hash;
370  * i.e. it not produce collisions when fed "random" data of the sort
371  * we expect to see. As long as the pool state differs for different
372  * inputs, we have preserved the input entropy and done a good job.
373  * The fact that an intelligent attacker can construct inputs that
374  * will produce controlled alterations to the pool's state is not
375  * important because we don't consider such inputs to contribute any
376  * randomness. The only property we need with respect to them is that
377  * the attacker can't increase his/her knowledge of the pool's state.
378  * Since all additions are reversible (knowing the final state and the
379  * input, you can reconstruct the initial state), if an attacker has
380  * any uncertainty about the initial state, he/she can only shuffle
381  * that uncertainty about, but never cause any collisions (which would
382  * decrease the uncertainty).
383  *
384  * The chosen system lets the state of the pool be (essentially) the input
385  * modulo the generator polymnomial. Now, for random primitive polynomials,
386  * this is a universal class of hash functions, meaning that the chance
387  * of a collision is limited by the attacker's knowledge of the generator
388  * polynomail, so if it is chosen at random, an attacker can never force
389  * a collision. Here, we use a fixed polynomial, but we *can* assume that
390  * ###--> it is unknown to the processes generating the input entropy. <-###
391  * Because of this important property, this is a good, collision-resistant
392  * hash; hash collisions will occur no more often than chance.
393  */
394 
395 /*
396  * Static global variables
397  */
398 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
399 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
400 static struct fasync_struct *fasync;
401 
402 #if 0
403 static bool debug;
404 module_param(debug, bool, 0644);
405 #define DEBUG_ENT(fmt, arg...) do { \
406  if (debug) \
407  printk(KERN_DEBUG "random %04d %04d %04d: " \
408  fmt,\
409  input_pool.entropy_count,\
410  blocking_pool.entropy_count,\
411  nonblocking_pool.entropy_count,\
412  ## arg); } while (0)
413 #else
414 #define DEBUG_ENT(fmt, arg...) do {} while (0)
415 #endif
416 
417 /**********************************************************************
418  *
419  * OS independent entropy store. Here are the functions which handle
420  * storing entropy in an entropy pool.
421  *
422  **********************************************************************/
423 
424 struct entropy_store;
426  /* read-only data: */
429  const char *name;
431  int limit;
432 
433  /* read-write data: */
435  unsigned add_ptr;
436  unsigned input_rotate;
439  unsigned int initialized:1;
441 };
442 
443 static __u32 input_pool_data[INPUT_POOL_WORDS];
444 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
445 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
446 
447 static struct entropy_store input_pool = {
448  .poolinfo = &poolinfo_table[0],
449  .name = "input",
450  .limit = 1,
451  .lock = __SPIN_LOCK_UNLOCKED(&input_pool.lock),
452  .pool = input_pool_data
453 };
454 
455 static struct entropy_store blocking_pool = {
456  .poolinfo = &poolinfo_table[1],
457  .name = "blocking",
458  .limit = 1,
459  .pull = &input_pool,
460  .lock = __SPIN_LOCK_UNLOCKED(&blocking_pool.lock),
461  .pool = blocking_pool_data
462 };
463 
464 static struct entropy_store nonblocking_pool = {
465  .poolinfo = &poolinfo_table[1],
466  .name = "nonblocking",
467  .pull = &input_pool,
468  .lock = __SPIN_LOCK_UNLOCKED(&nonblocking_pool.lock),
469  .pool = nonblocking_pool_data
470 };
471 
472 static __u32 const twist_table[8] = {
473  0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
474  0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
475 
476 /*
477  * This function adds bytes into the entropy "pool". It does not
478  * update the entropy estimate. The caller should call
479  * credit_entropy_bits if this is appropriate.
480  *
481  * The pool is stirred with a primitive polynomial of the appropriate
482  * degree, and then twisted. We twist by three bits at a time because
483  * it's cheap to do so and helps slightly in the expected case where
484  * the entropy is concentrated in the low-order bits.
485  */
486 static void _mix_pool_bytes(struct entropy_store *r, const void *in,
487  int nbytes, __u8 out[64])
488 {
489  unsigned long i, j, tap1, tap2, tap3, tap4, tap5;
490  int input_rotate;
491  int wordmask = r->poolinfo->poolwords - 1;
492  const char *bytes = in;
493  __u32 w;
494 
495  tap1 = r->poolinfo->tap1;
496  tap2 = r->poolinfo->tap2;
497  tap3 = r->poolinfo->tap3;
498  tap4 = r->poolinfo->tap4;
499  tap5 = r->poolinfo->tap5;
500 
501  smp_rmb();
502  input_rotate = ACCESS_ONCE(r->input_rotate);
503  i = ACCESS_ONCE(r->add_ptr);
504 
505  /* mix one byte at a time to simplify size handling and churn faster */
506  while (nbytes--) {
507  w = rol32(*bytes++, input_rotate & 31);
508  i = (i - 1) & wordmask;
509 
510  /* XOR in the various taps */
511  w ^= r->pool[i];
512  w ^= r->pool[(i + tap1) & wordmask];
513  w ^= r->pool[(i + tap2) & wordmask];
514  w ^= r->pool[(i + tap3) & wordmask];
515  w ^= r->pool[(i + tap4) & wordmask];
516  w ^= r->pool[(i + tap5) & wordmask];
517 
518  /* Mix the result back in with a twist */
519  r->pool[i] = (w >> 3) ^ twist_table[w & 7];
520 
521  /*
522  * Normally, we add 7 bits of rotation to the pool.
523  * At the beginning of the pool, add an extra 7 bits
524  * rotation, so that successive passes spread the
525  * input bits across the pool evenly.
526  */
527  input_rotate += i ? 7 : 14;
528  }
529 
531  ACCESS_ONCE(r->add_ptr) = i;
532  smp_wmb();
533 
534  if (out)
535  for (j = 0; j < 16; j++)
536  ((__u32 *)out)[j] = r->pool[(i - j) & wordmask];
537 }
538 
539 static void __mix_pool_bytes(struct entropy_store *r, const void *in,
540  int nbytes, __u8 out[64])
541 {
542  trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
543  _mix_pool_bytes(r, in, nbytes, out);
544 }
545 
546 static void mix_pool_bytes(struct entropy_store *r, const void *in,
547  int nbytes, __u8 out[64])
548 {
549  unsigned long flags;
550 
551  trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
552  spin_lock_irqsave(&r->lock, flags);
553  _mix_pool_bytes(r, in, nbytes, out);
554  spin_unlock_irqrestore(&r->lock, flags);
555 }
556 
557 struct fast_pool {
559  unsigned long last;
560  unsigned short count;
561  unsigned char rotate;
562  unsigned char last_timer_intr;
563 };
564 
565 /*
566  * This is a fast mixing routine used by the interrupt randomness
567  * collector. It's hardcoded for an 128 bit pool and assumes that any
568  * locks that might be needed are taken by the caller.
569  */
570 static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
571 {
572  const char *bytes = in;
573  __u32 w;
574  unsigned i = f->count;
575  unsigned input_rotate = f->rotate;
576 
577  while (nbytes--) {
578  w = rol32(*bytes++, input_rotate & 31) ^ f->pool[i & 3] ^
579  f->pool[(i + 1) & 3];
580  f->pool[i & 3] = (w >> 3) ^ twist_table[w & 7];
581  input_rotate += (i++ & 3) ? 7 : 14;
582  }
583  f->count = i;
584  f->rotate = input_rotate;
585 }
586 
587 /*
588  * Credit (or debit) the entropy store with n bits of entropy
589  */
590 static void credit_entropy_bits(struct entropy_store *r, int nbits)
591 {
592  int entropy_count, orig;
593 
594  if (!nbits)
595  return;
596 
597  DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name);
598 retry:
599  entropy_count = orig = ACCESS_ONCE(r->entropy_count);
600  entropy_count += nbits;
601 
602  if (entropy_count < 0) {
603  DEBUG_ENT("negative entropy/overflow\n");
604  entropy_count = 0;
605  } else if (entropy_count > r->poolinfo->POOLBITS)
606  entropy_count = r->poolinfo->POOLBITS;
607  if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
608  goto retry;
609 
610  if (!r->initialized && nbits > 0) {
611  r->entropy_total += nbits;
612  if (r->entropy_total > 128)
613  r->initialized = 1;
614  }
615 
616  trace_credit_entropy_bits(r->name, nbits, entropy_count,
617  r->entropy_total, _RET_IP_);
618 
619  /* should we wake readers? */
620  if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {
621  wake_up_interruptible(&random_read_wait);
622  kill_fasync(&fasync, SIGIO, POLL_IN);
623  }
624 }
625 
626 /*********************************************************************
627  *
628  * Entropy input management
629  *
630  *********************************************************************/
631 
632 /* There is one of these per entropy source */
636  unsigned dont_count_entropy:1;
637 };
638 
639 /*
640  * Add device- or boot-specific data to the input and nonblocking
641  * pools to help initialize them to unique values.
642  *
643  * None of this adds any entropy, it is meant to avoid the
644  * problem of the nonblocking pool having similar initial state
645  * across largely identical devices.
646  */
647 void add_device_randomness(const void *buf, unsigned int size)
648 {
649  unsigned long time = get_cycles() ^ jiffies;
650 
651  mix_pool_bytes(&input_pool, buf, size, NULL);
652  mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
653  mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
654  mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL);
655 }
657 
658 static struct timer_rand_state input_timer_state;
659 
660 /*
661  * This function adds entropy to the entropy "pool" by using timing
662  * delays. It uses the timer_rand_state structure to make an estimate
663  * of how many bits of entropy this call has added to the pool.
664  *
665  * The number "num" is also added to the pool - it should somehow describe
666  * the type of event which just happened. This is currently 0-255 for
667  * keyboard scan codes, and 256 upwards for interrupts.
668  *
669  */
670 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
671 {
672  struct {
673  long jiffies;
674  unsigned cycles;
675  unsigned num;
676  } sample;
677  long delta, delta2, delta3;
678 
679  preempt_disable();
680  /* if over the trickle threshold, use only 1 in 4096 samples */
681  if (input_pool.entropy_count > trickle_thresh &&
682  ((__this_cpu_inc_return(trickle_count) - 1) & 0xfff))
683  goto out;
684 
685  sample.jiffies = jiffies;
686  sample.cycles = get_cycles();
687  sample.num = num;
688  mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL);
689 
690  /*
691  * Calculate number of bits of randomness we probably added.
692  * We take into account the first, second and third-order deltas
693  * in order to make our estimate.
694  */
695 
696  if (!state->dont_count_entropy) {
697  delta = sample.jiffies - state->last_time;
698  state->last_time = sample.jiffies;
699 
700  delta2 = delta - state->last_delta;
701  state->last_delta = delta;
702 
703  delta3 = delta2 - state->last_delta2;
704  state->last_delta2 = delta2;
705 
706  if (delta < 0)
707  delta = -delta;
708  if (delta2 < 0)
709  delta2 = -delta2;
710  if (delta3 < 0)
711  delta3 = -delta3;
712  if (delta > delta2)
713  delta = delta2;
714  if (delta > delta3)
715  delta = delta3;
716 
717  /*
718  * delta is now minimum absolute delta.
719  * Round down by 1 bit on general principles,
720  * and limit entropy entimate to 12 bits.
721  */
722  credit_entropy_bits(&input_pool,
723  min_t(int, fls(delta>>1), 11));
724  }
725 out:
726  preempt_enable();
727 }
728 
729 void add_input_randomness(unsigned int type, unsigned int code,
730  unsigned int value)
731 {
732  static unsigned char last_value;
733 
734  /* ignore autorepeat and the like */
735  if (value == last_value)
736  return;
737 
738  DEBUG_ENT("input event\n");
739  last_value = value;
740  add_timer_randomness(&input_timer_state,
741  (type << 4) ^ code ^ (code >> 4) ^ value);
742 }
744 
745 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
746 
747 void add_interrupt_randomness(int irq, int irq_flags)
748 {
749  struct entropy_store *r;
750  struct fast_pool *fast_pool = &__get_cpu_var(irq_randomness);
751  struct pt_regs *regs = get_irq_regs();
752  unsigned long now = jiffies;
753  __u32 input[4], cycles = get_cycles();
754 
755  input[0] = cycles ^ jiffies;
756  input[1] = irq;
757  if (regs) {
758  __u64 ip = instruction_pointer(regs);
759  input[2] = ip;
760  input[3] = ip >> 32;
761  }
762 
763  fast_mix(fast_pool, input, sizeof(input));
764 
765  if ((fast_pool->count & 1023) &&
766  !time_after(now, fast_pool->last + HZ))
767  return;
768 
769  fast_pool->last = now;
770 
771  r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
772  __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL);
773  /*
774  * If we don't have a valid cycle counter, and we see
775  * back-to-back timer interrupts, then skip giving credit for
776  * any entropy.
777  */
778  if (cycles == 0) {
779  if (irq_flags & __IRQF_TIMER) {
780  if (fast_pool->last_timer_intr)
781  return;
782  fast_pool->last_timer_intr = 1;
783  } else
784  fast_pool->last_timer_intr = 0;
785  }
786  credit_entropy_bits(r, 1);
787 }
788 
789 #ifdef CONFIG_BLOCK
790 void add_disk_randomness(struct gendisk *disk)
791 {
792  if (!disk || !disk->random)
793  return;
794  /* first major is 1, so we get >= 0x200 here */
795  DEBUG_ENT("disk event %d:%d\n",
796  MAJOR(disk_devt(disk)), MINOR(disk_devt(disk)));
797 
798  add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
799 }
800 #endif
801 
802 /*********************************************************************
803  *
804  * Entropy extraction routines
805  *
806  *********************************************************************/
807 
808 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
809  size_t nbytes, int min, int rsvd);
810 
811 /*
812  * This utility inline function is responsible for transferring entropy
813  * from the primary pool to the secondary extraction pool. We make
814  * sure we pull enough for a 'catastrophic reseed'.
815  */
816 static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
817 {
819 
820  if (r->pull && r->entropy_count < nbytes * 8 &&
821  r->entropy_count < r->poolinfo->POOLBITS) {
822  /* If we're limited, always leave two wakeup worth's BITS */
823  int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
824  int bytes = nbytes;
825 
826  /* pull at least as many as BYTES as wakeup BITS */
827  bytes = max_t(int, bytes, random_read_wakeup_thresh / 8);
828  /* but never more than the buffer size */
829  bytes = min_t(int, bytes, sizeof(tmp));
830 
831  DEBUG_ENT("going to reseed %s with %d bits "
832  "(%d of %d requested)\n",
833  r->name, bytes * 8, nbytes * 8, r->entropy_count);
834 
835  bytes = extract_entropy(r->pull, tmp, bytes,
836  random_read_wakeup_thresh / 8, rsvd);
837  mix_pool_bytes(r, tmp, bytes, NULL);
838  credit_entropy_bits(r, bytes*8);
839  }
840 }
841 
842 /*
843  * These functions extracts randomness from the "entropy pool", and
844  * returns it in a buffer.
845  *
846  * The min parameter specifies the minimum amount we can pull before
847  * failing to avoid races that defeat catastrophic reseeding while the
848  * reserved parameter indicates how much entropy we must leave in the
849  * pool after each pull to avoid starving other readers.
850  *
851  * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
852  */
853 
854 static size_t account(struct entropy_store *r, size_t nbytes, int min,
855  int reserved)
856 {
857  unsigned long flags;
858 
859  /* Hold lock while accounting */
860  spin_lock_irqsave(&r->lock, flags);
861 
862  BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
863  DEBUG_ENT("trying to extract %d bits from %s\n",
864  nbytes * 8, r->name);
865 
866  /* Can we pull enough? */
867  if (r->entropy_count / 8 < min + reserved) {
868  nbytes = 0;
869  } else {
870  /* If limited, never pull more than available */
871  if (r->limit && nbytes + reserved >= r->entropy_count / 8)
872  nbytes = r->entropy_count/8 - reserved;
873 
874  if (r->entropy_count / 8 >= nbytes + reserved)
875  r->entropy_count -= nbytes*8;
876  else
877  r->entropy_count = reserved;
878 
879  if (r->entropy_count < random_write_wakeup_thresh) {
880  wake_up_interruptible(&random_write_wait);
881  kill_fasync(&fasync, SIGIO, POLL_OUT);
882  }
883  }
884 
885  DEBUG_ENT("debiting %d entropy credits from %s%s\n",
886  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
887 
888  spin_unlock_irqrestore(&r->lock, flags);
889 
890  return nbytes;
891 }
892 
893 static void extract_buf(struct entropy_store *r, __u8 *out)
894 {
895  int i;
896  union {
897  __u32 w[5];
898  unsigned long l[LONGS(EXTRACT_SIZE)];
899  } hash;
901  __u8 extract[64];
902  unsigned long flags;
903 
904  /* Generate a hash across the pool, 16 words (512 bits) at a time */
905  sha_init(hash.w);
906  spin_lock_irqsave(&r->lock, flags);
907  for (i = 0; i < r->poolinfo->poolwords; i += 16)
908  sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
909 
910  /*
911  * We mix the hash back into the pool to prevent backtracking
912  * attacks (where the attacker knows the state of the pool
913  * plus the current outputs, and attempts to find previous
914  * ouputs), unless the hash function can be inverted. By
915  * mixing at least a SHA1 worth of hash data back, we make
916  * brute-forcing the feedback as hard as brute-forcing the
917  * hash.
918  */
919  __mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
920  spin_unlock_irqrestore(&r->lock, flags);
921 
922  /*
923  * To avoid duplicates, we atomically extract a portion of the
924  * pool while mixing, and hash one final time.
925  */
926  sha_transform(hash.w, extract, workspace);
927  memset(extract, 0, sizeof(extract));
928  memset(workspace, 0, sizeof(workspace));
929 
930  /*
931  * In case the hash function has some recognizable output
932  * pattern, we fold it in half. Thus, we always feed back
933  * twice as much data as we output.
934  */
935  hash.w[0] ^= hash.w[3];
936  hash.w[1] ^= hash.w[4];
937  hash.w[2] ^= rol32(hash.w[2], 16);
938 
939  /*
940  * If we have a architectural hardware random number
941  * generator, mix that in, too.
942  */
943  for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
944  unsigned long v;
945  if (!arch_get_random_long(&v))
946  break;
947  hash.l[i] ^= v;
948  }
949 
950  memcpy(out, &hash, EXTRACT_SIZE);
951  memset(&hash, 0, sizeof(hash));
952 }
953 
954 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
955  size_t nbytes, int min, int reserved)
956 {
957  ssize_t ret = 0, i;
958  __u8 tmp[EXTRACT_SIZE];
959 
960  trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_);
961  xfer_secondary_pool(r, nbytes);
962  nbytes = account(r, nbytes, min, reserved);
963 
964  while (nbytes) {
965  extract_buf(r, tmp);
966 
967  if (fips_enabled) {
968  unsigned long flags;
969 
970  spin_lock_irqsave(&r->lock, flags);
971  if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
972  panic("Hardware RNG duplicated output!\n");
973  memcpy(r->last_data, tmp, EXTRACT_SIZE);
974  spin_unlock_irqrestore(&r->lock, flags);
975  }
976  i = min_t(int, nbytes, EXTRACT_SIZE);
977  memcpy(buf, tmp, i);
978  nbytes -= i;
979  buf += i;
980  ret += i;
981  }
982 
983  /* Wipe data just returned from memory */
984  memset(tmp, 0, sizeof(tmp));
985 
986  return ret;
987 }
988 
989 static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
990  size_t nbytes)
991 {
992  ssize_t ret = 0, i;
993  __u8 tmp[EXTRACT_SIZE];
994 
995  trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_);
996  xfer_secondary_pool(r, nbytes);
997  nbytes = account(r, nbytes, 0, 0);
998 
999  while (nbytes) {
1000  if (need_resched()) {
1001  if (signal_pending(current)) {
1002  if (ret == 0)
1003  ret = -ERESTARTSYS;
1004  break;
1005  }
1006  schedule();
1007  }
1008 
1009  extract_buf(r, tmp);
1010  i = min_t(int, nbytes, EXTRACT_SIZE);
1011  if (copy_to_user(buf, tmp, i)) {
1012  ret = -EFAULT;
1013  break;
1014  }
1015 
1016  nbytes -= i;
1017  buf += i;
1018  ret += i;
1019  }
1020 
1021  /* Wipe data just returned from memory */
1022  memset(tmp, 0, sizeof(tmp));
1023 
1024  return ret;
1025 }
1026 
1027 /*
1028  * This function is the exported kernel interface. It returns some
1029  * number of good random numbers, suitable for key generation, seeding
1030  * TCP sequence numbers, etc. It does not use the hw random number
1031  * generator, if available; use get_random_bytes_arch() for that.
1032  */
1033 void get_random_bytes(void *buf, int nbytes)
1034 {
1035  extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
1036 }
1038 
1039 /*
1040  * This function will use the architecture-specific hardware random
1041  * number generator if it is available. The arch-specific hw RNG will
1042  * almost certainly be faster than what we can do in software, but it
1043  * is impossible to verify that it is implemented securely (as
1044  * opposed, to, say, the AES encryption of a sequence number using a
1045  * key known by the NSA). So it's useful if we need the speed, but
1046  * only if we're willing to trust the hardware manufacturer not to
1047  * have put in a back door.
1048  */
1049 void get_random_bytes_arch(void *buf, int nbytes)
1050 {
1051  char *p = buf;
1052 
1053  trace_get_random_bytes(nbytes, _RET_IP_);
1054  while (nbytes) {
1055  unsigned long v;
1056  int chunk = min(nbytes, (int)sizeof(unsigned long));
1057 
1058  if (!arch_get_random_long(&v))
1059  break;
1060 
1061  memcpy(p, &v, chunk);
1062  p += chunk;
1063  nbytes -= chunk;
1064  }
1065 
1066  if (nbytes)
1067  extract_entropy(&nonblocking_pool, p, nbytes, 0, 0);
1068 }
1070 
1071 
1072 /*
1073  * init_std_data - initialize pool with system data
1074  *
1075  * @r: pool to initialize
1076  *
1077  * This function clears the pool's entropy count and mixes some system
1078  * data into the pool to prepare it for use. The pool is not cleared
1079  * as that can only decrease the entropy in the pool.
1080  */
1081 static void init_std_data(struct entropy_store *r)
1082 {
1083  int i;
1084  ktime_t now = ktime_get_real();
1085  unsigned long rv;
1086 
1087  r->entropy_count = 0;
1088  r->entropy_total = 0;
1089  mix_pool_bytes(r, &now, sizeof(now), NULL);
1090  for (i = r->poolinfo->POOLBYTES; i > 0; i -= sizeof(rv)) {
1091  if (!arch_get_random_long(&rv))
1092  break;
1093  mix_pool_bytes(r, &rv, sizeof(rv), NULL);
1094  }
1095  mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
1096 }
1097 
1098 /*
1099  * Note that setup_arch() may call add_device_randomness()
1100  * long before we get here. This allows seeding of the pools
1101  * with some platform dependent data very early in the boot
1102  * process. But it limits our options here. We must use
1103  * statically allocated structures that already have all
1104  * initializations complete at compile time. We should also
1105  * take care not to overwrite the precious per platform data
1106  * we were given.
1107  */
1108 static int rand_initialize(void)
1109 {
1110  init_std_data(&input_pool);
1111  init_std_data(&blocking_pool);
1112  init_std_data(&nonblocking_pool);
1113  return 0;
1114 }
1115 module_init(rand_initialize);
1116 
1117 #ifdef CONFIG_BLOCK
1118 void rand_initialize_disk(struct gendisk *disk)
1119 {
1120  struct timer_rand_state *state;
1121 
1122  /*
1123  * If kzalloc returns null, we just won't use that entropy
1124  * source.
1125  */
1126  state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
1127  if (state)
1128  disk->random = state;
1129 }
1130 #endif
1131 
1132 static ssize_t
1133 random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
1134 {
1135  ssize_t n, retval = 0, count = 0;
1136 
1137  if (nbytes == 0)
1138  return 0;
1139 
1140  while (nbytes > 0) {
1141  n = nbytes;
1142  if (n > SEC_XFER_SIZE)
1143  n = SEC_XFER_SIZE;
1144 
1145  DEBUG_ENT("reading %d bits\n", n*8);
1146 
1147  n = extract_entropy_user(&blocking_pool, buf, n);
1148 
1149  DEBUG_ENT("read got %d bits (%d still needed)\n",
1150  n*8, (nbytes-n)*8);
1151 
1152  if (n == 0) {
1153  if (file->f_flags & O_NONBLOCK) {
1154  retval = -EAGAIN;
1155  break;
1156  }
1157 
1158  DEBUG_ENT("sleeping?\n");
1159 
1160  wait_event_interruptible(random_read_wait,
1161  input_pool.entropy_count >=
1162  random_read_wakeup_thresh);
1163 
1164  DEBUG_ENT("awake\n");
1165 
1166  if (signal_pending(current)) {
1167  retval = -ERESTARTSYS;
1168  break;
1169  }
1170 
1171  continue;
1172  }
1173 
1174  if (n < 0) {
1175  retval = n;
1176  break;
1177  }
1178  count += n;
1179  buf += n;
1180  nbytes -= n;
1181  break; /* This break makes the device work */
1182  /* like a named pipe */
1183  }
1184 
1185  return (count ? count : retval);
1186 }
1187 
1188 static ssize_t
1189 urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
1190 {
1191  return extract_entropy_user(&nonblocking_pool, buf, nbytes);
1192 }
1193 
1194 static unsigned int
1195 random_poll(struct file *file, poll_table * wait)
1196 {
1197  unsigned int mask;
1198 
1199  poll_wait(file, &random_read_wait, wait);
1200  poll_wait(file, &random_write_wait, wait);
1201  mask = 0;
1202  if (input_pool.entropy_count >= random_read_wakeup_thresh)
1203  mask |= POLLIN | POLLRDNORM;
1204  if (input_pool.entropy_count < random_write_wakeup_thresh)
1205  mask |= POLLOUT | POLLWRNORM;
1206  return mask;
1207 }
1208 
1209 static int
1210 write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
1211 {
1212  size_t bytes;
1213  __u32 buf[16];
1214  const char __user *p = buffer;
1215 
1216  while (count > 0) {
1217  bytes = min(count, sizeof(buf));
1218  if (copy_from_user(&buf, p, bytes))
1219  return -EFAULT;
1220 
1221  count -= bytes;
1222  p += bytes;
1223 
1224  mix_pool_bytes(r, buf, bytes, NULL);
1225  cond_resched();
1226  }
1227 
1228  return 0;
1229 }
1230 
1231 static ssize_t random_write(struct file *file, const char __user *buffer,
1232  size_t count, loff_t *ppos)
1233 {
1234  size_t ret;
1235 
1236  ret = write_pool(&blocking_pool, buffer, count);
1237  if (ret)
1238  return ret;
1239  ret = write_pool(&nonblocking_pool, buffer, count);
1240  if (ret)
1241  return ret;
1242 
1243  return (ssize_t)count;
1244 }
1245 
1246 static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
1247 {
1248  int size, ent_count;
1249  int __user *p = (int __user *)arg;
1250  int retval;
1251 
1252  switch (cmd) {
1253  case RNDGETENTCNT:
1254  /* inherently racy, no point locking */
1255  if (put_user(input_pool.entropy_count, p))
1256  return -EFAULT;
1257  return 0;
1258  case RNDADDTOENTCNT:
1259  if (!capable(CAP_SYS_ADMIN))
1260  return -EPERM;
1261  if (get_user(ent_count, p))
1262  return -EFAULT;
1263  credit_entropy_bits(&input_pool, ent_count);
1264  return 0;
1265  case RNDADDENTROPY:
1266  if (!capable(CAP_SYS_ADMIN))
1267  return -EPERM;
1268  if (get_user(ent_count, p++))
1269  return -EFAULT;
1270  if (ent_count < 0)
1271  return -EINVAL;
1272  if (get_user(size, p++))
1273  return -EFAULT;
1274  retval = write_pool(&input_pool, (const char __user *)p,
1275  size);
1276  if (retval < 0)
1277  return retval;
1278  credit_entropy_bits(&input_pool, ent_count);
1279  return 0;
1280  case RNDZAPENTCNT:
1281  case RNDCLEARPOOL:
1282  /* Clear the entropy pool counters. */
1283  if (!capable(CAP_SYS_ADMIN))
1284  return -EPERM;
1285  rand_initialize();
1286  return 0;
1287  default:
1288  return -EINVAL;
1289  }
1290 }
1291 
1292 static int random_fasync(int fd, struct file *filp, int on)
1293 {
1294  return fasync_helper(fd, filp, on, &fasync);
1295 }
1296 
1298  .read = random_read,
1299  .write = random_write,
1300  .poll = random_poll,
1301  .unlocked_ioctl = random_ioctl,
1302  .fasync = random_fasync,
1303  .llseek = noop_llseek,
1304 };
1305 
1307  .read = urandom_read,
1308  .write = random_write,
1309  .unlocked_ioctl = random_ioctl,
1310  .fasync = random_fasync,
1311  .llseek = noop_llseek,
1312 };
1313 
1314 /***************************************************************
1315  * Random UUID interface
1316  *
1317  * Used here for a Boot ID, but can be useful for other kernel
1318  * drivers.
1319  ***************************************************************/
1320 
1321 /*
1322  * Generate random UUID
1323  */
1324 void generate_random_uuid(unsigned char uuid_out[16])
1325 {
1326  get_random_bytes(uuid_out, 16);
1327  /* Set UUID version to 4 --- truly random generation */
1328  uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
1329  /* Set the UUID variant to DCE */
1330  uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
1331 }
1333 
1334 /********************************************************************
1335  *
1336  * Sysctl interface
1337  *
1338  ********************************************************************/
1339 
1340 #ifdef CONFIG_SYSCTL
1341 
1342 #include <linux/sysctl.h>
1343 
1344 static int min_read_thresh = 8, min_write_thresh;
1345 static int max_read_thresh = INPUT_POOL_WORDS * 32;
1346 static int max_write_thresh = INPUT_POOL_WORDS * 32;
1347 static char sysctl_bootid[16];
1348 
1349 /*
1350  * These functions is used to return both the bootid UUID, and random
1351  * UUID. The difference is in whether table->data is NULL; if it is,
1352  * then a new UUID is generated and returned to the user.
1353  *
1354  * If the user accesses this via the proc interface, it will be returned
1355  * as an ASCII string in the standard UUID format. If accesses via the
1356  * sysctl system call, it is returned as 16 bytes of binary data.
1357  */
1358 static int proc_do_uuid(ctl_table *table, int write,
1359  void __user *buffer, size_t *lenp, loff_t *ppos)
1360 {
1361  ctl_table fake_table;
1362  unsigned char buf[64], tmp_uuid[16], *uuid;
1363 
1364  uuid = table->data;
1365  if (!uuid) {
1366  uuid = tmp_uuid;
1367  generate_random_uuid(uuid);
1368  } else {
1369  static DEFINE_SPINLOCK(bootid_spinlock);
1370 
1371  spin_lock(&bootid_spinlock);
1372  if (!uuid[8])
1373  generate_random_uuid(uuid);
1374  spin_unlock(&bootid_spinlock);
1375  }
1376 
1377  sprintf(buf, "%pU", uuid);
1378 
1379  fake_table.data = buf;
1380  fake_table.maxlen = sizeof(buf);
1381 
1382  return proc_dostring(&fake_table, write, buffer, lenp, ppos);
1383 }
1384 
1385 static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
1386 extern ctl_table random_table[];
1387 ctl_table random_table[] = {
1388  {
1389  .procname = "poolsize",
1390  .data = &sysctl_poolsize,
1391  .maxlen = sizeof(int),
1392  .mode = 0444,
1394  },
1395  {
1396  .procname = "entropy_avail",
1397  .maxlen = sizeof(int),
1398  .mode = 0444,
1400  .data = &input_pool.entropy_count,
1401  },
1402  {
1403  .procname = "read_wakeup_threshold",
1404  .data = &random_read_wakeup_thresh,
1405  .maxlen = sizeof(int),
1406  .mode = 0644,
1408  .extra1 = &min_read_thresh,
1409  .extra2 = &max_read_thresh,
1410  },
1411  {
1412  .procname = "write_wakeup_threshold",
1413  .data = &random_write_wakeup_thresh,
1414  .maxlen = sizeof(int),
1415  .mode = 0644,
1417  .extra1 = &min_write_thresh,
1418  .extra2 = &max_write_thresh,
1419  },
1420  {
1421  .procname = "boot_id",
1422  .data = &sysctl_bootid,
1423  .maxlen = 16,
1424  .mode = 0444,
1425  .proc_handler = proc_do_uuid,
1426  },
1427  {
1428  .procname = "uuid",
1429  .maxlen = 16,
1430  .mode = 0444,
1431  .proc_handler = proc_do_uuid,
1432  },
1433  { }
1434 };
1435 #endif /* CONFIG_SYSCTL */
1436 
1437 static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
1438 
1439 static int __init random_int_secret_init(void)
1440 {
1441  get_random_bytes(random_int_secret, sizeof(random_int_secret));
1442  return 0;
1443 }
1444 late_initcall(random_int_secret_init);
1445 
1446 /*
1447  * Get a random word for internal kernel use only. Similar to urandom but
1448  * with the goal of minimal entropy pool depletion. As a result, the random
1449  * value is not cryptographically secure but for several uses the cost of
1450  * depleting entropy is too high
1451  */
1452 static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
1453 unsigned int get_random_int(void)
1454 {
1455  __u32 *hash;
1456  unsigned int ret;
1457 
1458  if (arch_get_random_int(&ret))
1459  return ret;
1460 
1461  hash = get_cpu_var(get_random_int_hash);
1462 
1463  hash[0] += current->pid + jiffies + get_cycles();
1464  md5_transform(hash, random_int_secret);
1465  ret = hash[0];
1466  put_cpu_var(get_random_int_hash);
1467 
1468  return ret;
1469 }
1470 
1471 /*
1472  * randomize_range() returns a start address such that
1473  *
1474  * [...... <range> .....]
1475  * start end
1476  *
1477  * a <range> with size "len" starting at the return value is inside in the
1478  * area defined by [start, end], but is otherwise randomized.
1479  */
1480 unsigned long
1481 randomize_range(unsigned long start, unsigned long end, unsigned long len)
1482 {
1483  unsigned long range = end - len - start;
1484 
1485  if (end <= start + len)
1486  return 0;
1487  return PAGE_ALIGN(get_random_int() % range + start);
1488 }