Kernel

Kernel Git Source Tree

Root/drivers/char/random.c

1	/*
2	* random.c -- A strong random number generator
3	*
4	* Copyright Matt Mackall <mpm@selenic.com>, 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;
425	struct entropy_store {
426	/* read-only data: */
427	struct poolinfo *poolinfo;
428	__u32 *pool;
429	const char *name;
430	struct entropy_store *pull;
431	int limit;
432
433	/* read-write data: */
434	spinlock_t lock;
435	unsigned add_ptr;
436	unsigned input_rotate;
437	int entropy_count;
438	int entropy_total;
439	unsigned int initialized:1;
440	__u8 last_data[EXTRACT_SIZE];
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
530	ACCESS_ONCE(r->input_rotate) = input_rotate;
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 {
558	__u32 pool[4];
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 */
633	struct timer_rand_state {
634	cycles_t last_time;
635	long last_delta, last_delta2;
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	}
656	EXPORT_SYMBOL(add_device_randomness);
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	}
743	EXPORT_SYMBOL_GPL(add_input_randomness);
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	{
818	__u32 tmp[OUTPUT_POOL_WORDS];
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;
900	__u32 workspace[SHA_WORKSPACE_WORDS];
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	}
1037	EXPORT_SYMBOL(get_random_bytes);
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	}
1069	EXPORT_SYMBOL(get_random_bytes_arch);
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	n8, (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
1297	const struct file_operations random_fops = {
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
1306	const struct file_operations urandom_fops = {
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	}
1332	EXPORT_SYMBOL(generate_random_uuid);
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,
1393	.proc_handler = proc_dointvec,
1394	},
1395	{
1396	.procname = "entropy_avail",
1397	.maxlen = sizeof(int),
1398	.mode = 0444,
1399	.proc_handler = proc_dointvec,
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,
1407	.proc_handler = proc_dointvec_minmax,
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,
1416	.proc_handler = proc_dointvec_minmax,
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	}
1489

Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9

Kernel

Kernel Git Source Tree

Root/drivers/char/random.c

interactive