diff options
Diffstat (limited to 'drivers/char/random.c')
| -rw-r--r-- | drivers/char/random.c | 261 |
1 files changed, 177 insertions, 84 deletions
diff --git a/drivers/char/random.c b/drivers/char/random.c index b96751b63b58..5885ed574c6a 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -53,6 +53,7 @@ #include <linux/uaccess.h> #include <linux/suspend.h> #include <linux/siphash.h> +#include <linux/sched/isolation.h> #include <crypto/chacha.h> #include <crypto/blake2s.h> #include <asm/processor.h> @@ -84,6 +85,7 @@ static DEFINE_STATIC_KEY_FALSE(crng_is_ready); /* Various types of waiters for crng_init->CRNG_READY transition. */ static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait); static struct fasync_struct *fasync; +static ATOMIC_NOTIFIER_HEAD(random_ready_notifier); /* Control how we warn userspace. */ static struct ratelimit_state urandom_warning = @@ -120,7 +122,7 @@ static void try_to_generate_entropy(void); * Wait for the input pool to be seeded and thus guaranteed to supply * cryptographically secure random numbers. This applies to: the /dev/urandom * device, the get_random_bytes function, and the get_random_{u8,u16,u32,u64, - * int,long} family of functions. Using any of these functions without first + * long} family of functions. Using any of these functions without first * calling this function forfeits the guarantee of security. * * Returns: 0 if the input pool has been seeded. @@ -140,6 +142,26 @@ int wait_for_random_bytes(void) } EXPORT_SYMBOL(wait_for_random_bytes); +/* + * Add a callback function that will be invoked when the crng is initialised, + * or immediately if it already has been. Only use this is you are absolutely + * sure it is required. Most users should instead be able to test + * `rng_is_initialized()` on demand, or make use of `get_random_bytes_wait()`. + */ +int __cold execute_with_initialized_rng(struct notifier_block *nb) +{ + unsigned long flags; + int ret = 0; + + spin_lock_irqsave(&random_ready_notifier.lock, flags); + if (crng_ready()) + nb->notifier_call(nb, 0, NULL); + else + ret = raw_notifier_chain_register((struct raw_notifier_head *)&random_ready_notifier.head, nb); + spin_unlock_irqrestore(&random_ready_notifier.lock, flags); + return ret; +} + #define warn_unseeded_randomness() \ if (IS_ENABLED(CONFIG_WARN_ALL_UNSEEDED_RANDOM) && !crng_ready()) \ printk_deferred(KERN_NOTICE "random: %s called from %pS with crng_init=%d\n", \ @@ -160,6 +182,9 @@ EXPORT_SYMBOL(wait_for_random_bytes); * u8 get_random_u8() * u16 get_random_u16() * u32 get_random_u32() + * u32 get_random_u32_below(u32 ceil) + * u32 get_random_u32_above(u32 floor) + * u32 get_random_u32_inclusive(u32 floor, u32 ceil) * u64 get_random_u64() * unsigned long get_random_long() * @@ -179,7 +204,6 @@ enum { static struct { u8 key[CHACHA_KEY_SIZE] __aligned(__alignof__(long)); - unsigned long birth; unsigned long generation; spinlock_t lock; } base_crng = { @@ -197,16 +221,41 @@ static DEFINE_PER_CPU(struct crng, crngs) = { .lock = INIT_LOCAL_LOCK(crngs.lock), }; +/* + * Return the interval until the next reseeding, which is normally + * CRNG_RESEED_INTERVAL, but during early boot, it is at an interval + * proportional to the uptime. + */ +static unsigned int crng_reseed_interval(void) +{ + static bool early_boot = true; + + if (unlikely(READ_ONCE(early_boot))) { + time64_t uptime = ktime_get_seconds(); + if (uptime >= CRNG_RESEED_INTERVAL / HZ * 2) + WRITE_ONCE(early_boot, false); + else + return max_t(unsigned int, CRNG_RESEED_START_INTERVAL, + (unsigned int)uptime / 2 * HZ); + } + return CRNG_RESEED_INTERVAL; +} + /* Used by crng_reseed() and crng_make_state() to extract a new seed from the input pool. */ static void extract_entropy(void *buf, size_t len); /* This extracts a new crng key from the input pool. */ -static void crng_reseed(void) +static void crng_reseed(struct work_struct *work) { + static DECLARE_DELAYED_WORK(next_reseed, crng_reseed); unsigned long flags; unsigned long next_gen; u8 key[CHACHA_KEY_SIZE]; + /* Immediately schedule the next reseeding, so that it fires sooner rather than later. */ + if (likely(system_unbound_wq)) + queue_delayed_work(system_unbound_wq, &next_reseed, crng_reseed_interval()); + extract_entropy(key, sizeof(key)); /* @@ -221,7 +270,6 @@ static void crng_reseed(void) if (next_gen == ULONG_MAX) ++next_gen; WRITE_ONCE(base_crng.generation, next_gen); - WRITE_ONCE(base_crng.birth, jiffies); if (!static_branch_likely(&crng_is_ready)) crng_init = CRNG_READY; spin_unlock_irqrestore(&base_crng.lock, flags); @@ -261,26 +309,6 @@ static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE], } /* - * Return the interval until the next reseeding, which is normally - * CRNG_RESEED_INTERVAL, but during early boot, it is at an interval - * proportional to the uptime. - */ -static unsigned int crng_reseed_interval(void) -{ - static bool early_boot = true; - - if (unlikely(READ_ONCE(early_boot))) { - time64_t uptime = ktime_get_seconds(); - if (uptime >= CRNG_RESEED_INTERVAL / HZ * 2) - WRITE_ONCE(early_boot, false); - else - return max_t(unsigned int, CRNG_RESEED_START_INTERVAL, - (unsigned int)uptime / 2 * HZ); - } - return CRNG_RESEED_INTERVAL; -} - -/* * This function returns a ChaCha state that you may use for generating * random data. It also returns up to 32 bytes on its own of random data * that may be used; random_data_len may not be greater than 32. @@ -315,13 +343,6 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS], return; } - /* - * If the base_crng is old enough, we reseed, which in turn bumps the - * generation counter that we check below. - */ - if (unlikely(time_is_before_jiffies(READ_ONCE(base_crng.birth) + crng_reseed_interval()))) - crng_reseed(); - local_lock_irqsave(&crngs.lock, flags); crng = raw_cpu_ptr(&crngs); @@ -383,11 +404,11 @@ static void _get_random_bytes(void *buf, size_t len) } /* - * This function is the exported kernel interface. It returns some number of - * good random numbers, suitable for key generation, seeding TCP sequence - * numbers, etc. In order to ensure that the randomness returned by this - * function is okay, the function wait_for_random_bytes() should be called and - * return 0 at least once at any point prior. + * This returns random bytes in arbitrary quantities. The quality of the + * random bytes is good as /dev/urandom. In order to ensure that the + * randomness provided by this function is okay, the function + * wait_for_random_bytes() should be called and return 0 at least once + * at any point prior. */ void get_random_bytes(void *buf, size_t len) { @@ -510,6 +531,41 @@ DEFINE_BATCHED_ENTROPY(u16) DEFINE_BATCHED_ENTROPY(u32) DEFINE_BATCHED_ENTROPY(u64) +u32 __get_random_u32_below(u32 ceil) +{ + /* + * This is the slow path for variable ceil. It is still fast, most of + * the time, by doing traditional reciprocal multiplication and + * opportunistically comparing the lower half to ceil itself, before + * falling back to computing a larger bound, and then rejecting samples + * whose lower half would indicate a range indivisible by ceil. The use + * of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable + * in 32-bits. + */ + u32 rand = get_random_u32(); + u64 mult; + + /* + * This function is technically undefined for ceil == 0, and in fact + * for the non-underscored constant version in the header, we build bug + * on that. But for the non-constant case, it's convenient to have that + * evaluate to being a straight call to get_random_u32(), so that + * get_random_u32_inclusive() can work over its whole range without + * undefined behavior. + */ + if (unlikely(!ceil)) + return rand; + + mult = (u64)ceil * rand; + if (unlikely((u32)mult < ceil)) { + u32 bound = -ceil % ceil; + while (unlikely((u32)mult < bound)) + mult = (u64)ceil * get_random_u32(); + } + return mult >> 32; +} +EXPORT_SYMBOL(__get_random_u32_below); + #ifdef CONFIG_SMP /* * This function is called when the CPU is coming up, with entry @@ -660,9 +716,10 @@ static void __cold _credit_init_bits(size_t bits) } while (!try_cmpxchg(&input_pool.init_bits, &orig, new)); if (orig < POOL_READY_BITS && new >= POOL_READY_BITS) { - crng_reseed(); /* Sets crng_init to CRNG_READY under base_crng.lock. */ + crng_reseed(NULL); /* Sets crng_init to CRNG_READY under base_crng.lock. */ if (static_key_initialized) execute_in_process_context(crng_set_ready, &set_ready); + atomic_notifier_call_chain(&random_ready_notifier, 0, NULL); wake_up_interruptible(&crng_init_wait); kill_fasync(&fasync, SIGIO, POLL_IN); pr_notice("crng init done\n"); @@ -689,7 +746,7 @@ static void __cold _credit_init_bits(size_t bits) * the above entropy accumulation routines: * * void add_device_randomness(const void *buf, size_t len); - * void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy); + * void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy, bool sleep_after); * void add_bootloader_randomness(const void *buf, size_t len); * void add_vmfork_randomness(const void *unique_vm_id, size_t len); * void add_interrupt_randomness(int irq); @@ -710,7 +767,7 @@ static void __cold _credit_init_bits(size_t bits) * * add_bootloader_randomness() is called by bootloader drivers, such as EFI * and device tree, and credits its input depending on whether or not the - * configuration option CONFIG_RANDOM_TRUST_BOOTLOADER is set. + * command line option 'random.trust_bootloader'. * * add_vmfork_randomness() adds a unique (but not necessarily secret) ID * representing the current instance of a VM to the pool, without crediting, @@ -736,8 +793,8 @@ static void __cold _credit_init_bits(size_t bits) * **********************************************************************/ -static bool trust_cpu __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_CPU); -static bool trust_bootloader __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_BOOTLOADER); +static bool trust_cpu __initdata = true; +static bool trust_bootloader __initdata = true; static int __init parse_trust_cpu(char *arg) { return kstrtobool(arg, &trust_cpu); @@ -768,7 +825,7 @@ static int random_pm_notification(struct notifier_block *nb, unsigned long actio if (crng_ready() && (action == PM_RESTORE_PREPARE || (action == PM_POST_SUSPEND && !IS_ENABLED(CONFIG_PM_AUTOSLEEP) && !IS_ENABLED(CONFIG_PM_USERSPACE_AUTOSLEEP)))) { - crng_reseed(); + crng_reseed(NULL); pr_notice("crng reseeded on system resumption\n"); } return 0; @@ -791,13 +848,13 @@ void __init random_init_early(const char *command_line) #endif for (i = 0, arch_bits = sizeof(entropy) * 8; i < ARRAY_SIZE(entropy);) { - longs = arch_get_random_seed_longs_early(entropy, ARRAY_SIZE(entropy) - i); + longs = arch_get_random_seed_longs(entropy, ARRAY_SIZE(entropy) - i); if (longs) { _mix_pool_bytes(entropy, sizeof(*entropy) * longs); i += longs; continue; } - longs = arch_get_random_longs_early(entropy, ARRAY_SIZE(entropy) - i); + longs = arch_get_random_longs(entropy, ARRAY_SIZE(entropy) - i); if (longs) { _mix_pool_bytes(entropy, sizeof(*entropy) * longs); i += longs; @@ -812,7 +869,7 @@ void __init random_init_early(const char *command_line) /* Reseed if already seeded by earlier phases. */ if (crng_ready()) - crng_reseed(); + crng_reseed(NULL); else if (trust_cpu) _credit_init_bits(arch_bits); } @@ -840,7 +897,7 @@ void __init random_init(void) /* Reseed if already seeded by earlier phases. */ if (crng_ready()) - crng_reseed(); + crng_reseed(NULL); WARN_ON(register_pm_notifier(&pm_notifier)); @@ -869,11 +926,11 @@ void add_device_randomness(const void *buf, size_t len) EXPORT_SYMBOL(add_device_randomness); /* - * 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. + * Interface for in-kernel drivers of true hardware RNGs. Those devices + * may produce endless random bits, so this function will sleep for + * some amount of time after, if the sleep_after parameter is true. */ -void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy) +void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy, bool sleep_after) { mix_pool_bytes(buf, len); credit_init_bits(entropy); @@ -882,14 +939,14 @@ void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy) * Throttle writing to once every reseed interval, unless we're not yet * initialized or no entropy is credited. */ - if (!kthread_should_stop() && (crng_ready() || !entropy)) + if (sleep_after && !kthread_should_stop() && (crng_ready() || !entropy)) schedule_timeout_interruptible(crng_reseed_interval()); } EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); /* - * Handle random seed passed by bootloader, and credit it if - * CONFIG_RANDOM_TRUST_BOOTLOADER is set. + * Handle random seed passed by bootloader, and credit it depending + * on the command line option 'random.trust_bootloader'. */ void __init add_bootloader_randomness(const void *buf, size_t len) { @@ -910,7 +967,7 @@ void __cold add_vmfork_randomness(const void *unique_vm_id, size_t len) { add_device_randomness(unique_vm_id, len); if (crng_ready()) { - crng_reseed(); + crng_reseed(NULL); pr_notice("crng reseeded due to virtual machine fork\n"); } blocking_notifier_call_chain(&vmfork_chain, 0, NULL); @@ -1176,66 +1233,102 @@ void __cold rand_initialize_disk(struct gendisk *disk) struct entropy_timer_state { unsigned long entropy; struct timer_list timer; - unsigned int samples, samples_per_bit; + atomic_t samples; + unsigned int samples_per_bit; }; /* - * Each time the timer fires, we expect that we got an unpredictable - * jump in the cycle counter. Even if the timer is running on another - * CPU, the timer activity will be touching the stack of the CPU that is - * generating entropy.. + * Each time the timer fires, we expect that we got an unpredictable jump in + * the cycle counter. Even if the timer is running on another CPU, the timer + * activity will be touching the stack of the CPU that is generating entropy. * - * Note that we don't re-arm the timer in the timer itself - we are - * happy to be scheduled away, since that just makes the load more - * complex, but we do not want the timer to keep ticking unless the - * entropy loop is running. + * Note that we don't re-arm the timer in the timer itself - we are happy to be + * scheduled away, since that just makes the load more complex, but we do not + * want the timer to keep ticking unless the entropy loop is running. * * So the re-arming always happens in the entropy loop itself. */ static void __cold entropy_timer(struct timer_list *timer) { struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer); + unsigned long entropy = random_get_entropy(); - if (++state->samples == state->samples_per_bit) { + mix_pool_bytes(&entropy, sizeof(entropy)); + if (atomic_inc_return(&state->samples) % state->samples_per_bit == 0) credit_init_bits(1); - state->samples = 0; - } } /* - * If we have an actual cycle counter, see if we can - * generate enough entropy with timing noise + * If we have an actual cycle counter, see if we can generate enough entropy + * with timing noise. */ static void __cold try_to_generate_entropy(void) { enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 15 }; - struct entropy_timer_state stack; + u8 stack_bytes[sizeof(struct entropy_timer_state) + SMP_CACHE_BYTES - 1]; + struct entropy_timer_state *stack = PTR_ALIGN((void *)stack_bytes, SMP_CACHE_BYTES); unsigned int i, num_different = 0; unsigned long last = random_get_entropy(); + int cpu = -1; for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) { - stack.entropy = random_get_entropy(); - if (stack.entropy != last) + stack->entropy = random_get_entropy(); + if (stack->entropy != last) ++num_different; - last = stack.entropy; + last = stack->entropy; } - stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1); - if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT) + stack->samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1); + if (stack->samples_per_bit > MAX_SAMPLES_PER_BIT) return; - stack.samples = 0; - timer_setup_on_stack(&stack.timer, entropy_timer, 0); + atomic_set(&stack->samples, 0); + timer_setup_on_stack(&stack->timer, entropy_timer, 0); while (!crng_ready() && !signal_pending(current)) { - if (!timer_pending(&stack.timer)) - mod_timer(&stack.timer, jiffies); - mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); + /* + * Check !timer_pending() and then ensure that any previous callback has finished + * executing by checking try_to_del_timer_sync(), before queueing the next one. + */ + if (!timer_pending(&stack->timer) && try_to_del_timer_sync(&stack->timer) >= 0) { + struct cpumask timer_cpus; + unsigned int num_cpus; + + /* + * Preemption must be disabled here, both to read the current CPU number + * and to avoid scheduling a timer on a dead CPU. + */ + preempt_disable(); + + /* Only schedule callbacks on timer CPUs that are online. */ + cpumask_and(&timer_cpus, housekeeping_cpumask(HK_TYPE_TIMER), cpu_online_mask); + num_cpus = cpumask_weight(&timer_cpus); + /* In very bizarre case of misconfiguration, fallback to all online. */ + if (unlikely(num_cpus == 0)) { + timer_cpus = *cpu_online_mask; + num_cpus = cpumask_weight(&timer_cpus); + } + + /* Basic CPU round-robin, which avoids the current CPU. */ + do { + cpu = cpumask_next(cpu, &timer_cpus); + if (cpu == nr_cpumask_bits) + cpu = cpumask_first(&timer_cpus); + } while (cpu == smp_processor_id() && num_cpus > 1); + + /* Expiring the timer at `jiffies` means it's the next tick. */ + stack->timer.expires = jiffies; + + add_timer_on(&stack->timer, cpu); + + preempt_enable(); + } + mix_pool_bytes(&stack->entropy, sizeof(stack->entropy)); schedule(); - stack.entropy = random_get_entropy(); + stack->entropy = random_get_entropy(); } + mix_pool_bytes(&stack->entropy, sizeof(stack->entropy)); - del_timer_sync(&stack.timer); - destroy_timer_on_stack(&stack.timer); - mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); + del_timer_sync(&stack->timer); + destroy_timer_on_stack(&stack->timer); } @@ -1432,7 +1525,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) return -EPERM; if (!crng_ready()) return -ENODATA; - crng_reseed(); + crng_reseed(NULL); return 0; default: return -EINVAL; |