diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2014-08-06 08:16:24 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2014-08-06 08:16:24 -0700 |
commit | f4f142ed4ef835709c7e6d12eaca10d190bcebed (patch) | |
tree | a0bc6850239fe3551bb67f5707bfef153ac437fe /drivers/char/random.c | |
parent | bb2cbf5e9367d8598fecd0c48dead69560750223 (diff) | |
parent | e02b876597777ab26288dd2611a97b597d14d661 (diff) | |
download | op-kernel-dev-f4f142ed4ef835709c7e6d12eaca10d190bcebed.zip op-kernel-dev-f4f142ed4ef835709c7e6d12eaca10d190bcebed.tar.gz |
Merge tag 'random_for_linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tytso/random
Pull randomness updates from Ted Ts'o:
"Cleanups and bug fixes to /dev/random, add a new getrandom(2) system
call, which is a superset of OpenBSD's getentropy(2) call, for use
with userspace crypto libraries such as LibreSSL.
Also add the ability to have a kernel thread to pull entropy from
hardware rng devices into /dev/random"
* tag 'random_for_linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tytso/random:
hwrng: Pass entropy to add_hwgenerator_randomness() in bits, not bytes
random: limit the contribution of the hw rng to at most half
random: introduce getrandom(2) system call
hw_random: fix sparse warning (NULL vs 0 for pointer)
random: use registers from interrupted code for CPU's w/o a cycle counter
hwrng: add per-device entropy derating
hwrng: create filler thread
random: add_hwgenerator_randomness() for feeding entropy from devices
random: use an improved fast_mix() function
random: clean up interrupt entropy accounting for archs w/o cycle counters
random: only update the last_pulled time if we actually transferred entropy
random: remove unneeded hash of a portion of the entropy pool
random: always update the entropy pool under the spinlock
Diffstat (limited to 'drivers/char/random.c')
-rw-r--r-- | drivers/char/random.c | 315 |
1 files changed, 187 insertions, 128 deletions
diff --git a/drivers/char/random.c b/drivers/char/random.c index 71529e1..c18d41d 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -250,6 +250,7 @@ #include <linux/interrupt.h> #include <linux/mm.h> #include <linux/spinlock.h> +#include <linux/kthread.h> #include <linux/percpu.h> #include <linux/cryptohash.h> #include <linux/fips.h> @@ -257,6 +258,8 @@ #include <linux/kmemcheck.h> #include <linux/workqueue.h> #include <linux/irq.h> +#include <linux/syscalls.h> +#include <linux/completion.h> #include <asm/processor.h> #include <asm/uaccess.h> @@ -267,6 +270,8 @@ #define CREATE_TRACE_POINTS #include <trace/events/random.h> +/* #define ADD_INTERRUPT_BENCH */ + /* * Configuration information */ @@ -401,6 +406,7 @@ static struct poolinfo { */ static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); +static DECLARE_WAIT_QUEUE_HEAD(urandom_init_wait); static struct fasync_struct *fasync; /********************************************************************** @@ -481,9 +487,9 @@ static __u32 const twist_table[8] = { * the entropy is concentrated in the low-order bits. */ static void _mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { - unsigned long i, j, tap1, tap2, tap3, tap4, tap5; + unsigned long i, tap1, tap2, tap3, tap4, tap5; int input_rotate; int wordmask = r->poolinfo->poolwords - 1; const char *bytes = in; @@ -495,9 +501,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in, tap4 = r->poolinfo->tap4; tap5 = r->poolinfo->tap5; - smp_rmb(); - input_rotate = ACCESS_ONCE(r->input_rotate); - i = ACCESS_ONCE(r->add_ptr); + input_rotate = r->input_rotate; + i = r->add_ptr; /* mix one byte at a time to simplify size handling and churn faster */ while (nbytes--) { @@ -524,39 +529,33 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in, input_rotate = (input_rotate + (i ? 7 : 14)) & 31; } - ACCESS_ONCE(r->input_rotate) = input_rotate; - ACCESS_ONCE(r->add_ptr) = i; - smp_wmb(); - - if (out) - for (j = 0; j < 16; j++) - ((__u32 *)out)[j] = r->pool[(i - j) & wordmask]; + r->input_rotate = input_rotate; + r->add_ptr = i; } static void __mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_); - _mix_pool_bytes(r, in, nbytes, out); + _mix_pool_bytes(r, in, nbytes); } static void mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { unsigned long flags; trace_mix_pool_bytes(r->name, nbytes, _RET_IP_); spin_lock_irqsave(&r->lock, flags); - _mix_pool_bytes(r, in, nbytes, out); + _mix_pool_bytes(r, in, nbytes); spin_unlock_irqrestore(&r->lock, flags); } struct fast_pool { __u32 pool[4]; unsigned long last; - unsigned short count; - unsigned char rotate; - unsigned char last_timer_intr; + unsigned short reg_idx; + unsigned char count; }; /* @@ -564,25 +563,29 @@ struct fast_pool { * collector. It's hardcoded for an 128 bit pool and assumes that any * locks that might be needed are taken by the caller. */ -static void fast_mix(struct fast_pool *f, __u32 input[4]) +static void fast_mix(struct fast_pool *f) { - __u32 w; - unsigned input_rotate = f->rotate; - - w = rol32(input[0], input_rotate) ^ f->pool[0] ^ f->pool[3]; - f->pool[0] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 14) & 31; - w = rol32(input[1], input_rotate) ^ f->pool[1] ^ f->pool[0]; - f->pool[1] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - w = rol32(input[2], input_rotate) ^ f->pool[2] ^ f->pool[1]; - f->pool[2] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - w = rol32(input[3], input_rotate) ^ f->pool[3] ^ f->pool[2]; - f->pool[3] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - - f->rotate = input_rotate; + __u32 a = f->pool[0], b = f->pool[1]; + __u32 c = f->pool[2], d = f->pool[3]; + + a += b; c += d; + b = rol32(a, 6); d = rol32(c, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 16); d = rol32(c, 14); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 6); d = rol32(c, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 16); d = rol32(c, 14); + d ^= a; b ^= c; + + f->pool[0] = a; f->pool[1] = b; + f->pool[2] = c; f->pool[3] = d; f->count++; } @@ -657,6 +660,7 @@ retry: r->entropy_total = 0; if (r == &nonblocking_pool) { prandom_reseed_late(); + wake_up_interruptible(&urandom_init_wait); pr_notice("random: %s pool is initialized\n", r->name); } } @@ -739,13 +743,13 @@ void add_device_randomness(const void *buf, unsigned int size) trace_add_device_randomness(size, _RET_IP_); spin_lock_irqsave(&input_pool.lock, flags); - _mix_pool_bytes(&input_pool, buf, size, NULL); - _mix_pool_bytes(&input_pool, &time, sizeof(time), NULL); + _mix_pool_bytes(&input_pool, buf, size); + _mix_pool_bytes(&input_pool, &time, sizeof(time)); spin_unlock_irqrestore(&input_pool.lock, flags); spin_lock_irqsave(&nonblocking_pool.lock, flags); - _mix_pool_bytes(&nonblocking_pool, buf, size, NULL); - _mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL); + _mix_pool_bytes(&nonblocking_pool, buf, size); + _mix_pool_bytes(&nonblocking_pool, &time, sizeof(time)); spin_unlock_irqrestore(&nonblocking_pool.lock, flags); } EXPORT_SYMBOL(add_device_randomness); @@ -778,7 +782,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) sample.cycles = random_get_entropy(); sample.num = num; r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; - mix_pool_bytes(r, &sample, sizeof(sample), NULL); + mix_pool_bytes(r, &sample, sizeof(sample)); /* * Calculate number of bits of randomness we probably added. @@ -835,6 +839,38 @@ EXPORT_SYMBOL_GPL(add_input_randomness); static DEFINE_PER_CPU(struct fast_pool, irq_randomness); +#ifdef ADD_INTERRUPT_BENCH +static unsigned long avg_cycles, avg_deviation; + +#define AVG_SHIFT 8 /* Exponential average factor k=1/256 */ +#define FIXED_1_2 (1 << (AVG_SHIFT-1)) + +static void add_interrupt_bench(cycles_t start) +{ + long delta = random_get_entropy() - start; + + /* Use a weighted moving average */ + delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT); + avg_cycles += delta; + /* And average deviation */ + delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT); + avg_deviation += delta; +} +#else +#define add_interrupt_bench(x) +#endif + +static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs) +{ + __u32 *ptr = (__u32 *) regs; + + if (regs == NULL) + return 0; + if (f->reg_idx >= sizeof(struct pt_regs) / sizeof(__u32)) + f->reg_idx = 0; + return *(ptr + f->reg_idx++); +} + void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; @@ -842,55 +878,52 @@ void add_interrupt_randomness(int irq, int irq_flags) struct pt_regs *regs = get_irq_regs(); unsigned long now = jiffies; cycles_t cycles = random_get_entropy(); - __u32 input[4], c_high, j_high; + __u32 c_high, j_high; __u64 ip; unsigned long seed; - int credit; + int credit = 0; + if (cycles == 0) + cycles = get_reg(fast_pool, regs); c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; j_high = (sizeof(now) > 4) ? now >> 32 : 0; - input[0] = cycles ^ j_high ^ irq; - input[1] = now ^ c_high; + fast_pool->pool[0] ^= cycles ^ j_high ^ irq; + fast_pool->pool[1] ^= now ^ c_high; ip = regs ? instruction_pointer(regs) : _RET_IP_; - input[2] = ip; - input[3] = ip >> 32; + fast_pool->pool[2] ^= ip; + fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 : + get_reg(fast_pool, regs); - fast_mix(fast_pool, input); + fast_mix(fast_pool); + add_interrupt_bench(cycles); - if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ)) + if ((fast_pool->count < 64) && + !time_after(now, fast_pool->last + HZ)) return; - fast_pool->last = now; - r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; - __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL); + if (!spin_trylock(&r->lock)) + return; - /* - * If we don't have a valid cycle counter, and we see - * back-to-back timer interrupts, then skip giving credit for - * any entropy, otherwise credit 1 bit. - */ - credit = 1; - if (cycles == 0) { - if (irq_flags & __IRQF_TIMER) { - if (fast_pool->last_timer_intr) - credit = 0; - fast_pool->last_timer_intr = 1; - } else - fast_pool->last_timer_intr = 0; - } + fast_pool->last = now; + __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); /* * If we have architectural seed generator, produce a seed and - * add it to the pool. For the sake of paranoia count it as - * 50% entropic. + * add it to the pool. For the sake of paranoia don't let the + * architectural seed generator dominate the input from the + * interrupt noise. */ if (arch_get_random_seed_long(&seed)) { - __mix_pool_bytes(r, &seed, sizeof(seed), NULL); - credit += sizeof(seed) * 4; + __mix_pool_bytes(r, &seed, sizeof(seed)); + credit = 1; } + spin_unlock(&r->lock); - credit_entropy_bits(r, credit); + fast_pool->count = 0; + + /* award one bit for the contents of the fast pool */ + credit_entropy_bits(r, credit + 1); } #ifdef CONFIG_BLOCK @@ -922,6 +955,11 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes); static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) { + if (!r->pull || + r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) || + r->entropy_count > r->poolinfo->poolfracbits) + return; + if (r->limit == 0 && random_min_urandom_seed) { unsigned long now = jiffies; @@ -930,10 +968,8 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) return; r->last_pulled = now; } - if (r->pull && - r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) && - r->entropy_count < r->poolinfo->poolfracbits) - _xfer_secondary_pool(r, nbytes); + + _xfer_secondary_pool(r, nbytes); } static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes) @@ -953,7 +989,7 @@ static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes) ENTROPY_BITS(r), ENTROPY_BITS(r->pull)); bytes = extract_entropy(r->pull, tmp, bytes, random_read_wakeup_bits / 8, rsvd_bytes); - mix_pool_bytes(r, tmp, bytes, NULL); + mix_pool_bytes(r, tmp, bytes); credit_entropy_bits(r, bytes*8); } @@ -1039,7 +1075,6 @@ static void extract_buf(struct entropy_store *r, __u8 *out) unsigned long l[LONGS(20)]; } hash; __u32 workspace[SHA_WORKSPACE_WORDS]; - __u8 extract[64]; unsigned long flags; /* @@ -1068,15 +1103,9 @@ static void extract_buf(struct entropy_store *r, __u8 *out) * brute-forcing the feedback as hard as brute-forcing the * hash. */ - __mix_pool_bytes(r, hash.w, sizeof(hash.w), extract); + __mix_pool_bytes(r, hash.w, sizeof(hash.w)); spin_unlock_irqrestore(&r->lock, flags); - /* - * To avoid duplicates, we atomically extract a portion of the - * pool while mixing, and hash one final time. - */ - sha_transform(hash.w, extract, workspace); - memset(extract, 0, sizeof(extract)); memset(workspace, 0, sizeof(workspace)); /* @@ -1160,13 +1189,14 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, { ssize_t ret = 0, i; __u8 tmp[EXTRACT_SIZE]; + int large_request = (nbytes > 256); trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); xfer_secondary_pool(r, nbytes); nbytes = account(r, nbytes, 0, 0); while (nbytes) { - if (need_resched()) { + if (large_request && need_resched()) { if (signal_pending(current)) { if (ret == 0) ret = -ERESTARTSYS; @@ -1263,14 +1293,14 @@ static void init_std_data(struct entropy_store *r) unsigned long rv; r->last_pulled = jiffies; - mix_pool_bytes(r, &now, sizeof(now), NULL); + mix_pool_bytes(r, &now, sizeof(now)); for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { if (!arch_get_random_seed_long(&rv) && !arch_get_random_long(&rv)) rv = random_get_entropy(); - mix_pool_bytes(r, &rv, sizeof(rv), NULL); + mix_pool_bytes(r, &rv, sizeof(rv)); } - mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL); + mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); } /* @@ -1309,39 +1339,8 @@ void rand_initialize_disk(struct gendisk *disk) } #endif -/* - * Attempt an emergency refill using arch_get_random_seed_long(). - * - * As with add_interrupt_randomness() be paranoid and only - * credit the output as 50% entropic. - */ -static int arch_random_refill(void) -{ - const unsigned int nlongs = 64; /* Arbitrary number */ - unsigned int n = 0; - unsigned int i; - unsigned long buf[nlongs]; - - if (!arch_has_random_seed()) - return 0; - - for (i = 0; i < nlongs; i++) { - if (arch_get_random_seed_long(&buf[n])) - n++; - } - - if (n) { - unsigned int rand_bytes = n * sizeof(unsigned long); - - mix_pool_bytes(&input_pool, buf, rand_bytes, NULL); - credit_entropy_bits(&input_pool, rand_bytes*4); - } - - return n; -} - static ssize_t -random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) +_random_read(int nonblock, char __user *buf, size_t nbytes) { ssize_t n; @@ -1360,12 +1359,7 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) return n; /* Pool is (near) empty. Maybe wait and retry. */ - - /* First try an emergency refill */ - if (arch_random_refill()) - continue; - - if (file->f_flags & O_NONBLOCK) + if (nonblock) return -EAGAIN; wait_event_interruptible(random_read_wait, @@ -1377,6 +1371,12 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) } static ssize_t +random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) +{ + return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes); +} + +static ssize_t urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { int ret; @@ -1424,7 +1424,7 @@ write_pool(struct entropy_store *r, const char __user *buffer, size_t count) count -= bytes; p += bytes; - mix_pool_bytes(r, buf, bytes, NULL); + mix_pool_bytes(r, buf, bytes); cond_resched(); } @@ -1520,6 +1520,29 @@ const struct file_operations urandom_fops = { .llseek = noop_llseek, }; +SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count, + unsigned int, flags) +{ + if (flags & ~(GRND_NONBLOCK|GRND_RANDOM)) + return -EINVAL; + + if (count > INT_MAX) + count = INT_MAX; + + if (flags & GRND_RANDOM) + return _random_read(flags & GRND_NONBLOCK, buf, count); + + if (unlikely(nonblocking_pool.initialized == 0)) { + if (flags & GRND_NONBLOCK) + return -EAGAIN; + wait_event_interruptible(urandom_init_wait, + nonblocking_pool.initialized); + if (signal_pending(current)) + return -ERESTARTSYS; + } + return urandom_read(NULL, buf, count, NULL); +} + /*************************************************************** * Random UUID interface * @@ -1663,6 +1686,22 @@ struct ctl_table random_table[] = { .mode = 0444, .proc_handler = proc_do_uuid, }, +#ifdef ADD_INTERRUPT_BENCH + { + .procname = "add_interrupt_avg_cycles", + .data = &avg_cycles, + .maxlen = sizeof(avg_cycles), + .mode = 0444, + .proc_handler = proc_doulongvec_minmax, + }, + { + .procname = "add_interrupt_avg_deviation", + .data = &avg_deviation, + .maxlen = sizeof(avg_deviation), + .mode = 0444, + .proc_handler = proc_doulongvec_minmax, + }, +#endif { } }; #endif /* CONFIG_SYSCTL */ @@ -1719,3 +1758,23 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len) return 0; return PAGE_ALIGN(get_random_int() % range + start); } + +/* Interface for in-kernel drivers of true hardware RNGs. + * Those devices may produce endless random bits and will be throttled + * when our pool is full. + */ +void add_hwgenerator_randomness(const char *buffer, size_t count, + size_t entropy) +{ + struct entropy_store *poolp = &input_pool; + + /* Suspend writing if we're above the trickle threshold. + * We'll be woken up again once below random_write_wakeup_thresh, + * or when the calling thread is about to terminate. + */ + wait_event_interruptible(random_write_wait, kthread_should_stop() || + ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits); + mix_pool_bytes(poolp, buffer, count); + credit_entropy_bits(poolp, entropy); +} +EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); |