1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
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/kthread.h>
254#include <linux/percpu.h>
255#include <linux/cryptohash.h>
256#include <linux/fips.h>
257#include <linux/ptrace.h>
258#include <linux/kmemcheck.h>
259#include <linux/workqueue.h>
260#include <linux/irq.h>
261#include <linux/syscalls.h>
262#include <linux/completion.h>
263
264#include <asm/processor.h>
265#include <asm/uaccess.h>
266#include <asm/irq.h>
267#include <asm/irq_regs.h>
268#include <asm/io.h>
269
270#define CREATE_TRACE_POINTS
271#include <trace/events/random.h>
272
273
274
275
276
277
278#define INPUT_POOL_SHIFT 12
279#define INPUT_POOL_WORDS (1 << (INPUT_POOL_SHIFT-5))
280#define OUTPUT_POOL_SHIFT 10
281#define OUTPUT_POOL_WORDS (1 << (OUTPUT_POOL_SHIFT-5))
282#define SEC_XFER_SIZE 512
283#define EXTRACT_SIZE 10
284
285#define DEBUG_RANDOM_BOOT 0
286
287#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
288
289
290
291
292
293
294
295
296#define ENTROPY_SHIFT 3
297#define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
298
299
300
301
302
303static int random_read_wakeup_bits = 64;
304
305
306
307
308
309
310static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS;
311
312
313
314
315
316
317static int random_min_urandom_seed = 60;
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364static struct poolinfo {
365 int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
366#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
367 int tap1, tap2, tap3, tap4, tap5;
368} poolinfo_table[] = {
369
370
371 { S(128), 104, 76, 51, 25, 1 },
372
373
374 { S(32), 26, 19, 14, 7, 1 },
375#if 0
376
377 { S(2048), 1638, 1231, 819, 411, 1 },
378
379
380 { S(1024), 817, 615, 412, 204, 1 },
381
382
383 { S(1024), 819, 616, 410, 207, 2 },
384
385
386 { S(512), 411, 308, 208, 104, 1 },
387
388
389 { S(512), 409, 307, 206, 102, 2 },
390
391 { S(512), 409, 309, 205, 103, 2 },
392
393
394 { S(256), 205, 155, 101, 52, 1 },
395
396
397 { S(128), 103, 78, 51, 27, 2 },
398
399
400 { S(64), 52, 39, 26, 14, 1 },
401#endif
402};
403
404
405
406
407static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
408static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
409static DECLARE_WAIT_QUEUE_HEAD(urandom_init_wait);
410static struct fasync_struct *fasync;
411
412static DEFINE_SPINLOCK(random_ready_list_lock);
413static LIST_HEAD(random_ready_list);
414
415
416
417
418
419
420
421
422struct entropy_store;
423struct entropy_store {
424
425 const struct poolinfo *poolinfo;
426 __u32 *pool;
427 const char *name;
428 struct entropy_store *pull;
429 struct work_struct push_work;
430
431
432 unsigned long last_pulled;
433 spinlock_t lock;
434 unsigned short add_ptr;
435 unsigned short input_rotate;
436 int entropy_count;
437 int entropy_total;
438 unsigned int initialized:1;
439 unsigned int limit:1;
440 unsigned int last_data_init:1;
441 __u8 last_data[EXTRACT_SIZE];
442};
443
444static void push_to_pool(struct work_struct *work);
445static __u32 input_pool_data[INPUT_POOL_WORDS];
446static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
447static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
448
449static struct entropy_store input_pool = {
450 .poolinfo = &poolinfo_table[0],
451 .name = "input",
452 .limit = 1,
453 .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
454 .pool = input_pool_data
455};
456
457static struct entropy_store blocking_pool = {
458 .poolinfo = &poolinfo_table[1],
459 .name = "blocking",
460 .limit = 1,
461 .pull = &input_pool,
462 .lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
463 .pool = blocking_pool_data,
464 .push_work = __WORK_INITIALIZER(blocking_pool.push_work,
465 push_to_pool),
466};
467
468static struct entropy_store nonblocking_pool = {
469 .poolinfo = &poolinfo_table[1],
470 .name = "nonblocking",
471 .pull = &input_pool,
472 .lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock),
473 .pool = nonblocking_pool_data,
474 .push_work = __WORK_INITIALIZER(nonblocking_pool.push_work,
475 push_to_pool),
476};
477
478static __u32 const twist_table[8] = {
479 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
480 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
481
482
483
484
485
486
487
488
489
490
491
492static void _mix_pool_bytes(struct entropy_store *r, const void *in,
493 int nbytes)
494{
495 unsigned long i, tap1, tap2, tap3, tap4, tap5;
496 int input_rotate;
497 int wordmask = r->poolinfo->poolwords - 1;
498 const char *bytes = in;
499 __u32 w;
500
501 tap1 = r->poolinfo->tap1;
502 tap2 = r->poolinfo->tap2;
503 tap3 = r->poolinfo->tap3;
504 tap4 = r->poolinfo->tap4;
505 tap5 = r->poolinfo->tap5;
506
507 input_rotate = r->input_rotate;
508 i = r->add_ptr;
509
510
511 while (nbytes--) {
512 w = rol32(*bytes++, input_rotate);
513 i = (i - 1) & wordmask;
514
515
516 w ^= r->pool[i];
517 w ^= r->pool[(i + tap1) & wordmask];
518 w ^= r->pool[(i + tap2) & wordmask];
519 w ^= r->pool[(i + tap3) & wordmask];
520 w ^= r->pool[(i + tap4) & wordmask];
521 w ^= r->pool[(i + tap5) & wordmask];
522
523
524 r->pool[i] = (w >> 3) ^ twist_table[w & 7];
525
526
527
528
529
530
531
532 input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
533 }
534
535 r->input_rotate = input_rotate;
536 r->add_ptr = i;
537}
538
539static void __mix_pool_bytes(struct entropy_store *r, const void *in,
540 int nbytes)
541{
542 trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
543 _mix_pool_bytes(r, in, nbytes);
544}
545
546static void mix_pool_bytes(struct entropy_store *r, const void *in,
547 int nbytes)
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);
554 spin_unlock_irqrestore(&r->lock, flags);
555}
556
557struct fast_pool {
558 __u32 pool[4];
559 unsigned long last;
560 unsigned short reg_idx;
561 unsigned char count;
562};
563
564
565
566
567
568
569static void fast_mix(struct fast_pool *f)
570{
571 __u32 a = f->pool[0], b = f->pool[1];
572 __u32 c = f->pool[2], d = f->pool[3];
573
574 a += b; c += d;
575 b = rol32(b, 6); d = rol32(d, 27);
576 d ^= a; b ^= c;
577
578 a += b; c += d;
579 b = rol32(b, 16); d = rol32(d, 14);
580 d ^= a; b ^= c;
581
582 a += b; c += d;
583 b = rol32(b, 6); d = rol32(d, 27);
584 d ^= a; b ^= c;
585
586 a += b; c += d;
587 b = rol32(b, 16); d = rol32(d, 14);
588 d ^= a; b ^= c;
589
590 f->pool[0] = a; f->pool[1] = b;
591 f->pool[2] = c; f->pool[3] = d;
592 f->count++;
593}
594
595static void process_random_ready_list(void)
596{
597 unsigned long flags;
598 struct random_ready_callback *rdy, *tmp;
599
600 spin_lock_irqsave(&random_ready_list_lock, flags);
601 list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) {
602 struct module *owner = rdy->owner;
603
604 list_del_init(&rdy->list);
605 rdy->func(rdy);
606 module_put(owner);
607 }
608 spin_unlock_irqrestore(&random_ready_list_lock, flags);
609}
610
611
612
613
614
615
616static void credit_entropy_bits(struct entropy_store *r, int nbits)
617{
618 int entropy_count, orig;
619 const int pool_size = r->poolinfo->poolfracbits;
620 int nfrac = nbits << ENTROPY_SHIFT;
621
622 if (!nbits)
623 return;
624
625retry:
626 entropy_count = orig = ACCESS_ONCE(r->entropy_count);
627 if (nfrac < 0) {
628
629 entropy_count += nfrac;
630 } else {
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652 int pnfrac = nfrac;
653 const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
654
655
656 do {
657 unsigned int anfrac = min(pnfrac, pool_size/2);
658 unsigned int add =
659 ((pool_size - entropy_count)*anfrac*3) >> s;
660
661 entropy_count += add;
662 pnfrac -= anfrac;
663 } while (unlikely(entropy_count < pool_size-2 && pnfrac));
664 }
665
666 if (unlikely(entropy_count < 0)) {
667 pr_warn("random: negative entropy/overflow: pool %s count %d\n",
668 r->name, entropy_count);
669 WARN_ON(1);
670 entropy_count = 0;
671 } else if (entropy_count > pool_size)
672 entropy_count = pool_size;
673 if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
674 goto retry;
675
676 r->entropy_total += nbits;
677 if (!r->initialized && r->entropy_total > 128) {
678 r->initialized = 1;
679 r->entropy_total = 0;
680 if (r == &nonblocking_pool) {
681 prandom_reseed_late();
682 process_random_ready_list();
683 wake_up_all(&urandom_init_wait);
684 pr_notice("random: %s pool is initialized\n", r->name);
685 }
686 }
687
688 trace_credit_entropy_bits(r->name, nbits,
689 entropy_count >> ENTROPY_SHIFT,
690 r->entropy_total, _RET_IP_);
691
692 if (r == &input_pool) {
693 int entropy_bits = entropy_count >> ENTROPY_SHIFT;
694
695
696 if (entropy_bits >= random_read_wakeup_bits) {
697 wake_up_interruptible(&random_read_wait);
698 kill_fasync(&fasync, SIGIO, POLL_IN);
699 }
700
701
702
703
704
705 if (entropy_bits > random_write_wakeup_bits &&
706 r->initialized &&
707 r->entropy_total >= 2*random_read_wakeup_bits) {
708 static struct entropy_store *last = &blocking_pool;
709 struct entropy_store *other = &blocking_pool;
710
711 if (last == &blocking_pool)
712 other = &nonblocking_pool;
713 if (other->entropy_count <=
714 3 * other->poolinfo->poolfracbits / 4)
715 last = other;
716 if (last->entropy_count <=
717 3 * last->poolinfo->poolfracbits / 4) {
718 schedule_work(&last->push_work);
719 r->entropy_total = 0;
720 }
721 }
722 }
723}
724
725static void credit_entropy_bits_safe(struct entropy_store *r, int nbits)
726{
727 const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1));
728
729
730 nbits = min(nbits, nbits_max);
731 nbits = max(nbits, -nbits_max);
732
733 credit_entropy_bits(r, nbits);
734}
735
736
737
738
739
740
741
742
743struct timer_rand_state {
744 cycles_t last_time;
745 long last_delta, last_delta2;
746 unsigned dont_count_entropy:1;
747};
748
749#define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, };
750
751
752
753
754
755
756
757
758
759void add_device_randomness(const void *buf, unsigned int size)
760{
761 unsigned long time = random_get_entropy() ^ jiffies;
762 unsigned long flags;
763
764 trace_add_device_randomness(size, _RET_IP_);
765 spin_lock_irqsave(&input_pool.lock, flags);
766 _mix_pool_bytes(&input_pool, buf, size);
767 _mix_pool_bytes(&input_pool, &time, sizeof(time));
768 spin_unlock_irqrestore(&input_pool.lock, flags);
769
770 spin_lock_irqsave(&nonblocking_pool.lock, flags);
771 _mix_pool_bytes(&nonblocking_pool, buf, size);
772 _mix_pool_bytes(&nonblocking_pool, &time, sizeof(time));
773 spin_unlock_irqrestore(&nonblocking_pool.lock, flags);
774}
775EXPORT_SYMBOL(add_device_randomness);
776
777static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE;
778
779
780
781
782
783
784
785
786
787
788
789static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
790{
791 struct entropy_store *r;
792 struct {
793 long jiffies;
794 unsigned cycles;
795 unsigned num;
796 } sample;
797 long delta, delta2, delta3;
798
799 preempt_disable();
800
801 sample.jiffies = jiffies;
802 sample.cycles = random_get_entropy();
803 sample.num = num;
804 r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
805 mix_pool_bytes(r, &sample, sizeof(sample));
806
807
808
809
810
811
812
813 if (!state->dont_count_entropy) {
814 delta = sample.jiffies - state->last_time;
815 state->last_time = sample.jiffies;
816
817 delta2 = delta - state->last_delta;
818 state->last_delta = delta;
819
820 delta3 = delta2 - state->last_delta2;
821 state->last_delta2 = delta2;
822
823 if (delta < 0)
824 delta = -delta;
825 if (delta2 < 0)
826 delta2 = -delta2;
827 if (delta3 < 0)
828 delta3 = -delta3;
829 if (delta > delta2)
830 delta = delta2;
831 if (delta > delta3)
832 delta = delta3;
833
834
835
836
837
838
839 credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
840 }
841 preempt_enable();
842}
843
844void add_input_randomness(unsigned int type, unsigned int code,
845 unsigned int value)
846{
847 static unsigned char last_value;
848
849
850 if (value == last_value)
851 return;
852
853 last_value = value;
854 add_timer_randomness(&input_timer_state,
855 (type << 4) ^ code ^ (code >> 4) ^ value);
856 trace_add_input_randomness(ENTROPY_BITS(&input_pool));
857}
858EXPORT_SYMBOL_GPL(add_input_randomness);
859
860static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
861
862#ifdef ADD_INTERRUPT_BENCH
863static unsigned long avg_cycles, avg_deviation;
864
865#define AVG_SHIFT 8
866#define FIXED_1_2 (1 << (AVG_SHIFT-1))
867
868static void add_interrupt_bench(cycles_t start)
869{
870 long delta = random_get_entropy() - start;
871
872
873 delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT);
874 avg_cycles += delta;
875
876 delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT);
877 avg_deviation += delta;
878}
879#else
880#define add_interrupt_bench(x)
881#endif
882
883static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
884{
885 __u32 *ptr = (__u32 *) regs;
886
887 if (regs == NULL)
888 return 0;
889 if (f->reg_idx >= sizeof(struct pt_regs) / sizeof(__u32))
890 f->reg_idx = 0;
891 return *(ptr + f->reg_idx++);
892}
893
894void add_interrupt_randomness(int irq, int irq_flags)
895{
896 struct entropy_store *r;
897 struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
898 struct pt_regs *regs = get_irq_regs();
899 unsigned long now = jiffies;
900 cycles_t cycles = random_get_entropy();
901 __u32 c_high, j_high;
902 __u64 ip;
903 unsigned long seed;
904 int credit = 0;
905
906 if (cycles == 0)
907 cycles = get_reg(fast_pool, regs);
908 c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
909 j_high = (sizeof(now) > 4) ? now >> 32 : 0;
910 fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
911 fast_pool->pool[1] ^= now ^ c_high;
912 ip = regs ? instruction_pointer(regs) : _RET_IP_;
913 fast_pool->pool[2] ^= ip;
914 fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
915 get_reg(fast_pool, regs);
916
917 fast_mix(fast_pool);
918 add_interrupt_bench(cycles);
919
920 if ((fast_pool->count < 64) &&
921 !time_after(now, fast_pool->last + HZ))
922 return;
923
924 r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
925 if (!spin_trylock(&r->lock))
926 return;
927
928 fast_pool->last = now;
929 __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
930
931
932
933
934
935
936
937 if (arch_get_random_seed_long(&seed)) {
938 __mix_pool_bytes(r, &seed, sizeof(seed));
939 credit = 1;
940 }
941 spin_unlock(&r->lock);
942
943 fast_pool->count = 0;
944
945
946 credit_entropy_bits(r, credit + 1);
947}
948
949#ifdef CONFIG_BLOCK
950void add_disk_randomness(struct gendisk *disk)
951{
952 if (!disk || !disk->random)
953 return;
954
955 add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
956 trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool));
957}
958EXPORT_SYMBOL_GPL(add_disk_randomness);
959#endif
960
961
962
963
964
965
966
967static ssize_t extract_entropy(struct entropy_store *r, void *buf,
968 size_t nbytes, int min, int rsvd);
969
970
971
972
973
974
975static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes);
976static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
977{
978 if (!r->pull ||
979 r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) ||
980 r->entropy_count > r->poolinfo->poolfracbits)
981 return;
982
983 if (r->limit == 0 && random_min_urandom_seed) {
984 unsigned long now = jiffies;
985
986 if (time_before(now,
987 r->last_pulled + random_min_urandom_seed * HZ))
988 return;
989 r->last_pulled = now;
990 }
991
992 _xfer_secondary_pool(r, nbytes);
993}
994
995static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
996{
997 __u32 tmp[OUTPUT_POOL_WORDS];
998
999
1000 int rsvd_bytes = r->limit ? 0 : random_read_wakeup_bits / 4;
1001 int bytes = nbytes;
1002
1003
1004 bytes = max_t(int, bytes, random_read_wakeup_bits / 8);
1005
1006 bytes = min_t(int, bytes, sizeof(tmp));
1007
1008 trace_xfer_secondary_pool(r->name, bytes * 8, nbytes * 8,
1009 ENTROPY_BITS(r), ENTROPY_BITS(r->pull));
1010 bytes = extract_entropy(r->pull, tmp, bytes,
1011 random_read_wakeup_bits / 8, rsvd_bytes);
1012 mix_pool_bytes(r, tmp, bytes);
1013 credit_entropy_bits(r, bytes*8);
1014}
1015
1016
1017
1018
1019
1020
1021
1022static void push_to_pool(struct work_struct *work)
1023{
1024 struct entropy_store *r = container_of(work, struct entropy_store,
1025 push_work);
1026 BUG_ON(!r);
1027 _xfer_secondary_pool(r, random_read_wakeup_bits/8);
1028 trace_push_to_pool(r->name, r->entropy_count >> ENTROPY_SHIFT,
1029 r->pull->entropy_count >> ENTROPY_SHIFT);
1030}
1031
1032
1033
1034
1035
1036static size_t account(struct entropy_store *r, size_t nbytes, int min,
1037 int reserved)
1038{
1039 int entropy_count, orig;
1040 size_t ibytes, nfrac;
1041
1042 BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
1043
1044
1045retry:
1046 entropy_count = orig = ACCESS_ONCE(r->entropy_count);
1047 ibytes = nbytes;
1048
1049 if (r->limit) {
1050 int have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
1051
1052 if ((have_bytes -= reserved) < 0)
1053 have_bytes = 0;
1054 ibytes = min_t(size_t, ibytes, have_bytes);
1055 }
1056 if (ibytes < min)
1057 ibytes = 0;
1058
1059 if (unlikely(entropy_count < 0)) {
1060 pr_warn("random: negative entropy count: pool %s count %d\n",
1061 r->name, entropy_count);
1062 WARN_ON(1);
1063 entropy_count = 0;
1064 }
1065 nfrac = ibytes << (ENTROPY_SHIFT + 3);
1066 if ((size_t) entropy_count > nfrac)
1067 entropy_count -= nfrac;
1068 else
1069 entropy_count = 0;
1070
1071 if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
1072 goto retry;
1073
1074 trace_debit_entropy(r->name, 8 * ibytes);
1075 if (ibytes &&
1076 (r->entropy_count >> ENTROPY_SHIFT) < random_write_wakeup_bits) {
1077 wake_up_interruptible(&random_write_wait);
1078 kill_fasync(&fasync, SIGIO, POLL_OUT);
1079 }
1080
1081 return ibytes;
1082}
1083
1084
1085
1086
1087
1088
1089
1090static void extract_buf(struct entropy_store *r, __u8 *out)
1091{
1092 int i;
1093 union {
1094 __u32 w[5];
1095 unsigned long l[LONGS(20)];
1096 } hash;
1097 __u32 workspace[SHA_WORKSPACE_WORDS];
1098 unsigned long flags;
1099
1100
1101
1102
1103
1104 sha_init(hash.w);
1105 for (i = 0; i < LONGS(20); i++) {
1106 unsigned long v;
1107 if (!arch_get_random_long(&v))
1108 break;
1109 hash.l[i] = v;
1110 }
1111
1112
1113 spin_lock_irqsave(&r->lock, flags);
1114 for (i = 0; i < r->poolinfo->poolwords; i += 16)
1115 sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126 __mix_pool_bytes(r, hash.w, sizeof(hash.w));
1127 spin_unlock_irqrestore(&r->lock, flags);
1128
1129 memzero_explicit(workspace, sizeof(workspace));
1130
1131
1132
1133
1134
1135
1136 hash.w[0] ^= hash.w[3];
1137 hash.w[1] ^= hash.w[4];
1138 hash.w[2] ^= rol32(hash.w[2], 16);
1139
1140 memcpy(out, &hash, EXTRACT_SIZE);
1141 memzero_explicit(&hash, sizeof(hash));
1142}
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153static ssize_t extract_entropy(struct entropy_store *r, void *buf,
1154 size_t nbytes, int min, int reserved)
1155{
1156 ssize_t ret = 0, i;
1157 __u8 tmp[EXTRACT_SIZE];
1158 unsigned long flags;
1159
1160
1161 if (fips_enabled) {
1162 spin_lock_irqsave(&r->lock, flags);
1163 if (!r->last_data_init) {
1164 r->last_data_init = 1;
1165 spin_unlock_irqrestore(&r->lock, flags);
1166 trace_extract_entropy(r->name, EXTRACT_SIZE,
1167 ENTROPY_BITS(r), _RET_IP_);
1168 xfer_secondary_pool(r, EXTRACT_SIZE);
1169 extract_buf(r, tmp);
1170 spin_lock_irqsave(&r->lock, flags);
1171 memcpy(r->last_data, tmp, EXTRACT_SIZE);
1172 }
1173 spin_unlock_irqrestore(&r->lock, flags);
1174 }
1175
1176 trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
1177 xfer_secondary_pool(r, nbytes);
1178 nbytes = account(r, nbytes, min, reserved);
1179
1180 while (nbytes) {
1181 extract_buf(r, tmp);
1182
1183 if (fips_enabled) {
1184 spin_lock_irqsave(&r->lock, flags);
1185 if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
1186 panic("Hardware RNG duplicated output!\n");
1187 memcpy(r->last_data, tmp, EXTRACT_SIZE);
1188 spin_unlock_irqrestore(&r->lock, flags);
1189 }
1190 i = min_t(int, nbytes, EXTRACT_SIZE);
1191 memcpy(buf, tmp, i);
1192 nbytes -= i;
1193 buf += i;
1194 ret += i;
1195 }
1196
1197
1198 memzero_explicit(tmp, sizeof(tmp));
1199
1200 return ret;
1201}
1202
1203
1204
1205
1206
1207static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
1208 size_t nbytes)
1209{
1210 ssize_t ret = 0, i;
1211 __u8 tmp[EXTRACT_SIZE];
1212 int large_request = (nbytes > 256);
1213
1214 trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
1215 xfer_secondary_pool(r, nbytes);
1216 nbytes = account(r, nbytes, 0, 0);
1217
1218 while (nbytes) {
1219 if (large_request && need_resched()) {
1220 if (signal_pending(current)) {
1221 if (ret == 0)
1222 ret = -ERESTARTSYS;
1223 break;
1224 }
1225 schedule();
1226 }
1227
1228 extract_buf(r, tmp);
1229 i = min_t(int, nbytes, EXTRACT_SIZE);
1230 if (copy_to_user(buf, tmp, i)) {
1231 ret = -EFAULT;
1232 break;
1233 }
1234
1235 nbytes -= i;
1236 buf += i;
1237 ret += i;
1238 }
1239
1240
1241 memzero_explicit(tmp, sizeof(tmp));
1242
1243 return ret;
1244}
1245
1246
1247
1248
1249
1250
1251
1252
1253void get_random_bytes(void *buf, int nbytes)
1254{
1255#if DEBUG_RANDOM_BOOT > 0
1256 if (unlikely(nonblocking_pool.initialized == 0))
1257 printk(KERN_NOTICE "random: %pF get_random_bytes called "
1258 "with %d bits of entropy available\n",
1259 (void *) _RET_IP_,
1260 nonblocking_pool.entropy_total);
1261#endif
1262 trace_get_random_bytes(nbytes, _RET_IP_);
1263 extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
1264}
1265EXPORT_SYMBOL(get_random_bytes);
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275int add_random_ready_callback(struct random_ready_callback *rdy)
1276{
1277 struct module *owner;
1278 unsigned long flags;
1279 int err = -EALREADY;
1280
1281 if (likely(nonblocking_pool.initialized))
1282 return err;
1283
1284 owner = rdy->owner;
1285 if (!try_module_get(owner))
1286 return -ENOENT;
1287
1288 spin_lock_irqsave(&random_ready_list_lock, flags);
1289 if (nonblocking_pool.initialized)
1290 goto out;
1291
1292 owner = NULL;
1293
1294 list_add(&rdy->list, &random_ready_list);
1295 err = 0;
1296
1297out:
1298 spin_unlock_irqrestore(&random_ready_list_lock, flags);
1299
1300 module_put(owner);
1301
1302 return err;
1303}
1304EXPORT_SYMBOL(add_random_ready_callback);
1305
1306
1307
1308
1309void del_random_ready_callback(struct random_ready_callback *rdy)
1310{
1311 unsigned long flags;
1312 struct module *owner = NULL;
1313
1314 spin_lock_irqsave(&random_ready_list_lock, flags);
1315 if (!list_empty(&rdy->list)) {
1316 list_del_init(&rdy->list);
1317 owner = rdy->owner;
1318 }
1319 spin_unlock_irqrestore(&random_ready_list_lock, flags);
1320
1321 module_put(owner);
1322}
1323EXPORT_SYMBOL(del_random_ready_callback);
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335void get_random_bytes_arch(void *buf, int nbytes)
1336{
1337 char *p = buf;
1338
1339 trace_get_random_bytes_arch(nbytes, _RET_IP_);
1340 while (nbytes) {
1341 unsigned long v;
1342 int chunk = min(nbytes, (int)sizeof(unsigned long));
1343
1344 if (!arch_get_random_long(&v))
1345 break;
1346
1347 memcpy(p, &v, chunk);
1348 p += chunk;
1349 nbytes -= chunk;
1350 }
1351
1352 if (nbytes)
1353 extract_entropy(&nonblocking_pool, p, nbytes, 0, 0);
1354}
1355EXPORT_SYMBOL(get_random_bytes_arch);
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367static void init_std_data(struct entropy_store *r)
1368{
1369 int i;
1370 ktime_t now = ktime_get_real();
1371 unsigned long rv;
1372
1373 r->last_pulled = jiffies;
1374 mix_pool_bytes(r, &now, sizeof(now));
1375 for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
1376 if (!arch_get_random_seed_long(&rv) &&
1377 !arch_get_random_long(&rv))
1378 rv = random_get_entropy();
1379 mix_pool_bytes(r, &rv, sizeof(rv));
1380 }
1381 mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
1382}
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394static int rand_initialize(void)
1395{
1396 init_std_data(&input_pool);
1397 init_std_data(&blocking_pool);
1398 init_std_data(&nonblocking_pool);
1399 return 0;
1400}
1401early_initcall(rand_initialize);
1402
1403#ifdef CONFIG_BLOCK
1404void rand_initialize_disk(struct gendisk *disk)
1405{
1406 struct timer_rand_state *state;
1407
1408
1409
1410
1411
1412 state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
1413 if (state) {
1414 state->last_time = INITIAL_JIFFIES;
1415 disk->random = state;
1416 }
1417}
1418#endif
1419
1420static ssize_t
1421_random_read(int nonblock, char __user *buf, size_t nbytes)
1422{
1423 ssize_t n;
1424
1425 if (nbytes == 0)
1426 return 0;
1427
1428 nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
1429 while (1) {
1430 n = extract_entropy_user(&blocking_pool, buf, nbytes);
1431 if (n < 0)
1432 return n;
1433 trace_random_read(n*8, (nbytes-n)*8,
1434 ENTROPY_BITS(&blocking_pool),
1435 ENTROPY_BITS(&input_pool));
1436 if (n > 0)
1437 return n;
1438
1439
1440 if (nonblock)
1441 return -EAGAIN;
1442
1443 wait_event_interruptible(random_read_wait,
1444 ENTROPY_BITS(&input_pool) >=
1445 random_read_wakeup_bits);
1446 if (signal_pending(current))
1447 return -ERESTARTSYS;
1448 }
1449}
1450
1451static ssize_t
1452random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
1453{
1454 return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes);
1455}
1456
1457static ssize_t
1458urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
1459{
1460 int ret;
1461
1462 if (unlikely(nonblocking_pool.initialized == 0))
1463 printk_once(KERN_NOTICE "random: %s urandom read "
1464 "with %d bits of entropy available\n",
1465 current->comm, nonblocking_pool.entropy_total);
1466
1467 nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3));
1468 ret = extract_entropy_user(&nonblocking_pool, buf, nbytes);
1469
1470 trace_urandom_read(8 * nbytes, ENTROPY_BITS(&nonblocking_pool),
1471 ENTROPY_BITS(&input_pool));
1472 return ret;
1473}
1474
1475static unsigned int
1476random_poll(struct file *file, poll_table * wait)
1477{
1478 unsigned int mask;
1479
1480 poll_wait(file, &random_read_wait, wait);
1481 poll_wait(file, &random_write_wait, wait);
1482 mask = 0;
1483 if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
1484 mask |= POLLIN | POLLRDNORM;
1485 if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits)
1486 mask |= POLLOUT | POLLWRNORM;
1487 return mask;
1488}
1489
1490static int
1491write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
1492{
1493 size_t bytes;
1494 __u32 buf[16];
1495 const char __user *p = buffer;
1496
1497 while (count > 0) {
1498 bytes = min(count, sizeof(buf));
1499 if (copy_from_user(&buf, p, bytes))
1500 return -EFAULT;
1501
1502 count -= bytes;
1503 p += bytes;
1504
1505 mix_pool_bytes(r, buf, bytes);
1506 cond_resched();
1507 }
1508
1509 return 0;
1510}
1511
1512static ssize_t random_write(struct file *file, const char __user *buffer,
1513 size_t count, loff_t *ppos)
1514{
1515 size_t ret;
1516
1517 ret = write_pool(&blocking_pool, buffer, count);
1518 if (ret)
1519 return ret;
1520 ret = write_pool(&nonblocking_pool, buffer, count);
1521 if (ret)
1522 return ret;
1523
1524 return (ssize_t)count;
1525}
1526
1527static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
1528{
1529 int size, ent_count;
1530 int __user *p = (int __user *)arg;
1531 int retval;
1532
1533 switch (cmd) {
1534 case RNDGETENTCNT:
1535
1536 ent_count = ENTROPY_BITS(&input_pool);
1537 if (put_user(ent_count, p))
1538 return -EFAULT;
1539 return 0;
1540 case RNDADDTOENTCNT:
1541 if (!capable(CAP_SYS_ADMIN))
1542 return -EPERM;
1543 if (get_user(ent_count, p))
1544 return -EFAULT;
1545 credit_entropy_bits_safe(&input_pool, ent_count);
1546 return 0;
1547 case RNDADDENTROPY:
1548 if (!capable(CAP_SYS_ADMIN))
1549 return -EPERM;
1550 if (get_user(ent_count, p++))
1551 return -EFAULT;
1552 if (ent_count < 0)
1553 return -EINVAL;
1554 if (get_user(size, p++))
1555 return -EFAULT;
1556 retval = write_pool(&input_pool, (const char __user *)p,
1557 size);
1558 if (retval < 0)
1559 return retval;
1560 credit_entropy_bits_safe(&input_pool, ent_count);
1561 return 0;
1562 case RNDZAPENTCNT:
1563 case RNDCLEARPOOL:
1564
1565
1566
1567
1568 if (!capable(CAP_SYS_ADMIN))
1569 return -EPERM;
1570 input_pool.entropy_count = 0;
1571 nonblocking_pool.entropy_count = 0;
1572 blocking_pool.entropy_count = 0;
1573 return 0;
1574 default:
1575 return -EINVAL;
1576 }
1577}
1578
1579static int random_fasync(int fd, struct file *filp, int on)
1580{
1581 return fasync_helper(fd, filp, on, &fasync);
1582}
1583
1584const struct file_operations random_fops = {
1585 .read = random_read,
1586 .write = random_write,
1587 .poll = random_poll,
1588 .unlocked_ioctl = random_ioctl,
1589 .fasync = random_fasync,
1590 .llseek = noop_llseek,
1591};
1592
1593const struct file_operations urandom_fops = {
1594 .read = urandom_read,
1595 .write = random_write,
1596 .unlocked_ioctl = random_ioctl,
1597 .fasync = random_fasync,
1598 .llseek = noop_llseek,
1599};
1600
1601SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
1602 unsigned int, flags)
1603{
1604 if (flags & ~(GRND_NONBLOCK|GRND_RANDOM))
1605 return -EINVAL;
1606
1607 if (count > INT_MAX)
1608 count = INT_MAX;
1609
1610 if (flags & GRND_RANDOM)
1611 return _random_read(flags & GRND_NONBLOCK, buf, count);
1612
1613 if (unlikely(nonblocking_pool.initialized == 0)) {
1614 if (flags & GRND_NONBLOCK)
1615 return -EAGAIN;
1616 wait_event_interruptible(urandom_init_wait,
1617 nonblocking_pool.initialized);
1618 if (signal_pending(current))
1619 return -ERESTARTSYS;
1620 }
1621 return urandom_read(NULL, buf, count, NULL);
1622}
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634void generate_random_uuid(unsigned char uuid_out[16])
1635{
1636 get_random_bytes(uuid_out, 16);
1637
1638 uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
1639
1640 uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
1641}
1642EXPORT_SYMBOL(generate_random_uuid);
1643
1644
1645
1646
1647
1648
1649
1650#ifdef CONFIG_SYSCTL
1651
1652#include <linux/sysctl.h>
1653
1654static int min_read_thresh = 8, min_write_thresh;
1655static int max_read_thresh = OUTPUT_POOL_WORDS * 32;
1656static int max_write_thresh = INPUT_POOL_WORDS * 32;
1657static char sysctl_bootid[16];
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668static int proc_do_uuid(struct ctl_table *table, int write,
1669 void __user *buffer, size_t *lenp, loff_t *ppos)
1670{
1671 struct ctl_table fake_table;
1672 unsigned char buf[64], tmp_uuid[16], *uuid;
1673
1674 uuid = table->data;
1675 if (!uuid) {
1676 uuid = tmp_uuid;
1677 generate_random_uuid(uuid);
1678 } else {
1679 static DEFINE_SPINLOCK(bootid_spinlock);
1680
1681 spin_lock(&bootid_spinlock);
1682 if (!uuid[8])
1683 generate_random_uuid(uuid);
1684 spin_unlock(&bootid_spinlock);
1685 }
1686
1687 sprintf(buf, "%pU", uuid);
1688
1689 fake_table.data = buf;
1690 fake_table.maxlen = sizeof(buf);
1691
1692 return proc_dostring(&fake_table, write, buffer, lenp, ppos);
1693}
1694
1695
1696
1697
1698static int proc_do_entropy(struct ctl_table *table, int write,
1699 void __user *buffer, size_t *lenp, loff_t *ppos)
1700{
1701 struct ctl_table fake_table;
1702 int entropy_count;
1703
1704 entropy_count = *(int *)table->data >> ENTROPY_SHIFT;
1705
1706 fake_table.data = &entropy_count;
1707 fake_table.maxlen = sizeof(entropy_count);
1708
1709 return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
1710}
1711
1712static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
1713extern struct ctl_table random_table[];
1714struct ctl_table random_table[] = {
1715 {
1716 .procname = "poolsize",
1717 .data = &sysctl_poolsize,
1718 .maxlen = sizeof(int),
1719 .mode = 0444,
1720 .proc_handler = proc_dointvec,
1721 },
1722 {
1723 .procname = "entropy_avail",
1724 .maxlen = sizeof(int),
1725 .mode = 0444,
1726 .proc_handler = proc_do_entropy,
1727 .data = &input_pool.entropy_count,
1728 },
1729 {
1730 .procname = "read_wakeup_threshold",
1731 .data = &random_read_wakeup_bits,
1732 .maxlen = sizeof(int),
1733 .mode = 0644,
1734 .proc_handler = proc_dointvec_minmax,
1735 .extra1 = &min_read_thresh,
1736 .extra2 = &max_read_thresh,
1737 },
1738 {
1739 .procname = "write_wakeup_threshold",
1740 .data = &random_write_wakeup_bits,
1741 .maxlen = sizeof(int),
1742 .mode = 0644,
1743 .proc_handler = proc_dointvec_minmax,
1744 .extra1 = &min_write_thresh,
1745 .extra2 = &max_write_thresh,
1746 },
1747 {
1748 .procname = "urandom_min_reseed_secs",
1749 .data = &random_min_urandom_seed,
1750 .maxlen = sizeof(int),
1751 .mode = 0644,
1752 .proc_handler = proc_dointvec,
1753 },
1754 {
1755 .procname = "boot_id",
1756 .data = &sysctl_bootid,
1757 .maxlen = 16,
1758 .mode = 0444,
1759 .proc_handler = proc_do_uuid,
1760 },
1761 {
1762 .procname = "uuid",
1763 .maxlen = 16,
1764 .mode = 0444,
1765 .proc_handler = proc_do_uuid,
1766 },
1767#ifdef ADD_INTERRUPT_BENCH
1768 {
1769 .procname = "add_interrupt_avg_cycles",
1770 .data = &avg_cycles,
1771 .maxlen = sizeof(avg_cycles),
1772 .mode = 0444,
1773 .proc_handler = proc_doulongvec_minmax,
1774 },
1775 {
1776 .procname = "add_interrupt_avg_deviation",
1777 .data = &avg_deviation,
1778 .maxlen = sizeof(avg_deviation),
1779 .mode = 0444,
1780 .proc_handler = proc_doulongvec_minmax,
1781 },
1782#endif
1783 { }
1784};
1785#endif
1786
1787static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
1788
1789int random_int_secret_init(void)
1790{
1791 get_random_bytes(random_int_secret, sizeof(random_int_secret));
1792 return 0;
1793}
1794
1795
1796
1797
1798
1799
1800
1801static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
1802unsigned int get_random_int(void)
1803{
1804 __u32 *hash;
1805 unsigned int ret;
1806
1807 if (arch_get_random_int(&ret))
1808 return ret;
1809
1810 hash = get_cpu_var(get_random_int_hash);
1811
1812 hash[0] += current->pid + jiffies + random_get_entropy();
1813 md5_transform(hash, random_int_secret);
1814 ret = hash[0];
1815 put_cpu_var(get_random_int_hash);
1816
1817 return ret;
1818}
1819EXPORT_SYMBOL(get_random_int);
1820
1821
1822
1823
1824unsigned long get_random_long(void)
1825{
1826 __u32 *hash;
1827 unsigned long ret;
1828
1829 if (arch_get_random_long(&ret))
1830 return ret;
1831
1832 hash = get_cpu_var(get_random_int_hash);
1833
1834 hash[0] += current->pid + jiffies + random_get_entropy();
1835 md5_transform(hash, random_int_secret);
1836 ret = *(unsigned long *)hash;
1837 put_cpu_var(get_random_int_hash);
1838
1839 return ret;
1840}
1841EXPORT_SYMBOL(get_random_long);
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852unsigned long
1853randomize_range(unsigned long start, unsigned long end, unsigned long len)
1854{
1855 unsigned long range = end - len - start;
1856
1857 if (end <= start + len)
1858 return 0;
1859 return PAGE_ALIGN(get_random_int() % range + start);
1860}
1861
1862
1863
1864
1865
1866void add_hwgenerator_randomness(const char *buffer, size_t count,
1867 size_t entropy)
1868{
1869 struct entropy_store *poolp = &input_pool;
1870
1871
1872
1873
1874
1875 wait_event_interruptible(random_write_wait, kthread_should_stop() ||
1876 ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
1877 mix_pool_bytes(poolp, buffer, count);
1878 credit_entropy_bits(poolp, entropy);
1879}
1880EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);
1881