random: clear fast pool, crng, and batches in cpuhp bring up
Subsystems (3)
Jason A. Donenfeld
maintainerPATCH v5 1/1 random: clear fast pool, crng, and batches in cpuhp bring up
For the irq randomness fast pool, rather than having to use expensive atomics, which were visibly the most expensive thing in the entire irq handler, simply take care of the extreme edge case of resetting count to zero in the cpuhp online handler, just after workqueues have been reenabled. This simplifies the code a bit and lets us use vanilla variables rather than atomics, and performance should be improved.
As well, very early on when the CPU comes up, while interrupts are still disabled, we clear out the per-cpu crng and its batches, so that it always starts with fresh randomness.
---
Sebastian - this v5 finally follows your suggestion about what operations to do at which phase. The only deviation from your exact suggestion is that I'm not checking for MIX_INFLIGHT in the online handler, and instead just unconditionally zero it out. I think that's an acceptable tradeoff to make for simplicity, and it just means we'll accumulate even more entropy, which is fine. Hopefully this is an easy ack and has no more pitfalls! -Jason
drivers/char/random.c | 57 ++++++++++++++++++++++++++++---------- include/linux/cpuhotplug.h | 2 ++ include/linux/random.h | 5 ++++ kernel/cpu.c | 11 ++++++++ 4 files changed, 60 insertions(+), 15 deletions(-)
drivers/char/random.c +42 -15
@@ -697,6 +697,25 @@ u32 get_random_u32(void) }EXPORT_SYMBOL (get_random_u32); +#ifdef CONFIG_SMP +/* +* This function is called by the cpuhp system, wired up via the large +* static array in kernel/cpu.c, with the entry CPUHP_RANDOM_PREPARE. +*/ +int random_prepare_cpu (unsigned int cpu) +{ +/* +* When the cpu comes back online, immediately invalidate both +* the per-cpu crng and all batches, so that we serve fresh +* randomness. +*/ +per_cpu_ptr (&crngs, cpu)->generation =ULONG_MAX ; +per_cpu_ptr (&batched_entropy_u32, cpu)->position =UINT_MAX ; +per_cpu_ptr (&batched_entropy_u64, cpu)->position =UINT_MAX ; +return 0 ; +} +#endif +/** * randomize_page - Generate a random, page aligned address * @start: The smallest acceptable address the caller will take.
@@ -1182,7 +1201,7 @@ struct fast_pool { };struct work_struct mix;unsigned long last; -atomic_t count; +unsigned int count;u16 reg_idx; };
@@ -1218,6 +1237,24 @@ static void fast_mix(u32 pool[4]) static DEFINE_PER_CPU(struct fast_pool, irq_randomness); +#ifdef CONFIG_SMP +/* +* This function is called by the cpuhp system, wired up via the large +* static array in kernel/cpu.c, with the entry CPUHP_AP_RANDOM_ONLINE. +*/ +int random_online_cpu (unsigned int cpu) +{ +/* +* Set irq randomness count to zero so that new accumulated +* irqs are fresh, and more importantly, so that its worker +* is permitted to schedule again when it comes back online, +* since the MIX_INFLIGHT flag will be cleared. +*/ +per_cpu_ptr (&irq_randomness, cpu)->count =0 ; +return 0 ; +} +#endif +static u32 get_reg (struct fast_pool *f,struct pt_regs *regs) {u32 *ptr = (u32 *)regs;
@@ -1242,15 +1279,6 @@ static void mix_interrupt_randomness(struct work_struct *work)local_irq_disable ();if (fast_pool !=this_cpu_ptr (&irq_randomness)) {local_irq_enable (); -/* -* If we are unlucky enough to have been moved to another CPU, -* during CPU hotplug while the CPU was shutdown then we set -* our count to zero atomically so that when the CPU comes -* back online, it can enqueue work again. The _release here -* pairs with the atomic_inc_return_acquire in -* add_interrupt_randomness(). -*/ -atomic_set_release (&fast_pool->count,0 );return ; }
@@ -1259,7 +1287,7 @@ static void mix_interrupt_randomness(struct work_struct *work)* consistent view, before we reenable irqs again. */ memcpy (pool, fast_pool->pool32,sizeof (pool)); -atomic_set (&fast_pool->count,0 ); + fast_pool->count =0 ; fast_pool->last = jiffies;local_irq_enable ();
@@ -1295,14 +1323,13 @@ void add_interrupt_randomness(int irq) }fast_mix (fast_pool->pool32); -/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */ - new_count = (unsigned int )atomic_inc_return_acquire (&fast_pool->count); + new_count = ++fast_pool->count;if (unlikely (crng_init ==0 )) {if (new_count >=64 &&crng_pre_init_inject (fast_pool->pool32,sizeof (fast_pool->pool32), true, true) >0 ) { -atomic_set (&fast_pool->count,0 ); + fast_pool->count =0 ; fast_pool->last = now;if (spin_trylock (&input_pool.lock)) {_mix_pool_bytes (&fast_pool->pool32,sizeof (fast_pool->pool32));
@@ -1320,7 +1347,7 @@ void add_interrupt_randomness(int irq)if (unlikely (!fast_pool->mix.func))INIT_WORK (&fast_pool->mix, mix_interrupt_randomness); -atomic_or (MIX_INFLIGHT , &fast_pool->count); + fast_pool->count |=MIX_INFLIGHT ;queue_work_on (raw_smp_processor_id (), system_highpri_wq, &fast_pool->mix); }EXPORT_SYMBOL_GPL (add_interrupt_randomness);
include/linux/cpuhotplug.h +2 -0
@@ -100,6 +100,7 @@ enum cpuhp_state {CPUHP_AP_ARM_CACHE_B15_RAC_DEAD ,CPUHP_PADATA_DEAD ,CPUHP_AP_DTPM_CPU_DEAD , +CPUHP_RANDOM_PREPARE ,CPUHP_WORKQUEUE_PREP ,CPUHP_POWER_NUMA_PREPARE , CPUHP_HRTIMERS_PREPARE,
@@ -240,6 +241,7 @@ enum cpuhp_state {CPUHP_AP_PERF_CSKY_ONLINE ,CPUHP_AP_WATCHDOG_ONLINE ,CPUHP_AP_WORKQUEUE_ONLINE , +CPUHP_AP_RANDOM_ONLINE ,CPUHP_AP_RCUTREE_ONLINE ,CPUHP_AP_BASE_CACHEINFO_ONLINE , CPUHP_AP_ONLINE_DYN,
include/linux/random.h +5 -0
@@ -156,4 +156,9 @@ static inline bool __init arch_get_random_long_early(unsigned long *v) }#endif +#ifdef CONFIG_SMP +extern int random_prepare_cpu (unsigned int cpu); +extern int random_online_cpu (unsigned int cpu); +#endif +#endif /* _LINUX_RANDOM_H */
kernel/cpu.c +11 -0
@@ -34,6 +34,7 @@#include <linux/scs.h> #include <linux/percpu-rwsem.h> #include <linux/cpuset.h> +#include <linux/random.h> #include <trace/events/power.h> #define CREATE_TRACE_POINTS
@@ -1659,6 +1660,11 @@ static struct cpuhp_step cpuhp_hp_states[] = { .startup.single = perf_event_init_cpu, .teardown.single = perf_event_exit_cpu, }, + [CPUHP_RANDOM_PREPARE] = { + .name = "random:prepare", + .startup.single = random_prepare_cpu, + .teardown.single = NULL, + }, [CPUHP_WORKQUEUE_PREP] = { .name = "workqueue:prepare", .startup.single = workqueue_prepare_cpu,
@@ -1782,6 +1788,11 @@ static struct cpuhp_step cpuhp_hp_states[] = { .startup.single = workqueue_online_cpu, .teardown.single = workqueue_offline_cpu, }, + [CPUHP_AP_RANDOM_ONLINE] = { + .name = "random:online", + .startup.single = random_online_cpu, + .teardown.single = NULL, + }, [CPUHP_AP_RCUTREE_ONLINE] = { .name = "RCU/tree:online", .startup.single = rcutree_online_cpu,
Signature · 1 line
2.35.0
Quoted 7 lines · Jason A. Donenfeld
Sebastian - this v5 finally follows your suggestion about what operations to do at which phase. The only deviation from your exact suggestion is that I'm not checking for
MIX_INFLIGHTin the online handler, and instead just unconditionally zero it out. I think that's an acceptable tradeoff to make for simplicity, and it just means we'll accumulate even more entropy, which is fine. Hopefully this is an easy ack and has no more pitfalls! -Jason
So I think this is the latest, right?
What do you think about this small comment update? :)
drivers/char/random.c +9 -12
@@ -698,10 +698,6 @@ u32 get_random_u32(void)EXPORT_SYMBOL (get_random_u32);#ifdef CONFIG_SMP -/* -* This function is called by the cpuhp system, wired up via the large -* static array in kernel/cpu.c, with the entry CPUHP_RANDOM_PREPARE. -*/ int random_prepare_cpu (unsigned int cpu) {/*
@@ -1238,17 +1234,18 @@ static void fast_mix(u32 pool[4]) static DEFINE_PER_CPU(struct fast_pool, irq_randomness);#ifdef CONFIG_SMP -/* -* This function is called by the cpuhp system, wired up via the large -* static array in kernel/cpu.c, with the entry CPUHP_AP_RANDOM_ONLINE. -*/ int random_online_cpu (unsigned int cpu) {/* -* Set irq randomness count to zero so that new accumulated -* irqs are fresh, and more importantly, so that its worker -* is permitted to schedule again when it comes back online, -* since the MIX_INFLIGHT flag will be cleared. +* This function is invoked while the CPU is comming up, after workqueue +* subsystem has been fully initialized for this CPU. +* +* During CPU bring up and shutdown way may schedule a worker +* (and set MIX_INFLIGHT) which will run another CPU because workqueues +* were not yet ready for this CPU. In this case the worker will +* recognize that it runs on the wrong CPU and do nothing. +* Therefore count is set unconditionally to zero which will permit +* to schedule a new worker soon. */ per_cpu_ptr (&irq_randomness, cpu)->count =0 ;return 0 ;
Quoted 11 lines
drivers/char/random.c +5
-0@@ -697,6 +697,25 @@ u32 get_random_u32(void) }EXPORT_SYMBOL (get_random_u32); +#ifdef CONFIG_SMP +/* +* This function is called by the cpuhp system, wired up via the large +* static array in kernel/cpu.c, with the entry CPUHP_RANDOM_PREPARE. +*/
drivers/char/random.c u32 get_random_u32(void) · line 714
Quoted 10 lines
drivers/char/random.c +10
-0+int random_prepare_cpu (unsigned int cpu) +{ +/* +* When the cpu comes back online, immediately invalidate both +* the per-cpu crng and all batches, so that we serve fresh +* randomness. +*/ +per_cpu_ptr (&crngs, cpu)->generation =ULONG_MAX ; +per_cpu_ptr (&batched_entropy_u32, cpu)->position =UINT_MAX ; +per_cpu_ptr (&batched_entropy_u64, cpu)->position =UINT_MAX ;
This runs before the CPU is up. Could you do the initialisation right now?
My problem here is that if this (get_random_u32()) is used between CPUHP_AP_IDLE_DEAD and CPUHP_TEARDOWN_CPU then the initialisation will happen on the target CPU with disabled interrupts. And will acquire a sleeping lock (batched_entropy_u32.lock).
You could perform the initialization cross CPU without the lock because the CPU itself isn't ready yet. Something like
batch = per_cpu_ptr(&batched_entropy_u32, cpu);
_get_random_bytes(batch->entropy_u32, sizeof(batch->entropy_u32));
batch->position = 0;
batch->generation = next_gen;should do the job. Plus u64 and I haven't figured out the generation thingy but I suspect that a sleeping lock is involved.
I did not check if this is a problem on PREEMPT_RT yet but it may become later one (if we get a user in the hotplug path).
Sebastian
Jason A. Donenfeld
maintainerHi Sebastian,
Thank you for finding the time to review this v5.
Quoted 1 line · Sebastian Andrzej Siewior
So I think this is the latest, right?
Yes.
Quoted 1 line
What do you think about this small comment update? :)
I can improve the comments for v6 of this patch, yes. I won't use your text exactly, as there are other errors in it, but I'll synthesize its meaning.
Quoted 10 lines
Quoted 10 lines
(quoted diff) +10
-0+#ifdef CONFIG_SMP +/* + * This function is called by the cpuhp system, wired up via the large + * static array in kernel/cpu.c, with the entry CPUHP_RANDOM_PREPARE. + */ +int random_prepare_cpu(unsigned int cpu) +{ + /* + * When the cpu comes back online, immediately invalidate both + * the per-cpu crng and all batches, so that we serve fresh
Quoted 8 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ * randomness. + */ + per_cpu_ptr(&crngs, cpu)->generation = ULONG_MAX; + per_cpu_ptr(&batched_entropy_u32, cpu)->position = UINT_MAX; + per_cpu_ptr(&batched_entropy_u64, cpu)->position = UINT_MAX;This runs before the CPU is up. Could you do the initialisation right now?
That wouldn't accomplish anything. See below.
Quoted 4 lines
My problem here is that if this (
get_random_u32()) is used betweenCPUHP_AP_IDLE_DEADandCPUHP_TEARDOWN_CPUthen the initialisation will happen on the target CPU with disabled interrupts. And will acquire a sleeping lock (batched_entropy_u32.lock).
That is not a legitimate problem to be addressed in any way at all by this patchset. The batches may well be already depleted and the crng already old, and therefore the "problem" you note is the same both before and after this patch. If you want to address that, send a separate patch for it.
Quoted 6 lines
You could perform the initialization cross CPU without the lock because the CPU itself isn't ready yet. Something like
batch = per_cpu_ptr(&batched_entropy_u32, cpu); _get_random_bytes(batch->entropy_u32, sizeof(batch->entropy_u32)); batch->position = 0; batch->generation = next_gen;
I guess, but it wouldn't solve anything. The entire batch could be filled and then subsequently emptied out before irqs are up, and your problem will just repeat itself. I'm not going to make any changes related to that in this patch.
If you find out that there are actual users of get_random_{...} during that window, and think that this represents a real problem, please send a patch and we can discuss that then.
I'll send a v6 with comments fixed to your liking. I hope that you can ack it.
Jason
Jason A. Donenfeld
maintainerPATCH v6 1/1 random: clear fast pool, crng, and batches in cpuhp bring up
For the irq randomness fast pool, rather than having to use expensive atomics, which were visibly the most expensive thing in the entire irq handler, simply take care of the extreme edge case of resetting count to zero in the cpuhp online handler, just after workqueues have been reenabled. This simplifies the code a bit and lets us use vanilla variables rather than atomics, and performance should be improved.
As well, very early on when the CPU comes up, while interrupts are still disabled, we clear out the per-cpu crng and its batches, so that it always starts with fresh randomness.
---
v6 improves the comments around each of the cpuhp functions, as requested.
drivers/char/random.c | 62 +++++++++++++++++++++++++++++--------- include/linux/cpuhotplug.h | 2 ++ include/linux/random.h | 5 +++ kernel/cpu.c | 11 +++++++ 4 files changed, 65 insertions(+), 15 deletions(-)
drivers/char/random.c +47 -15
@@ -697,6 +697,25 @@ u32 get_random_u32(void) }EXPORT_SYMBOL (get_random_u32); +#ifdef CONFIG_SMP +/* +* This function is called when the CPU is coming up, with entry +* CPUHP_RANDOM_PREPARE, which comes before CPUHP_WORKQUEUE_PREP. +*/ +int random_prepare_cpu (unsigned int cpu) +{ +/* +* When the cpu comes back online, immediately invalidate both +* the per-cpu crng and all batches, so that we serve fresh +* randomness. +*/ +per_cpu_ptr (&crngs, cpu)->generation =ULONG_MAX ; +per_cpu_ptr (&batched_entropy_u32, cpu)->position =UINT_MAX ; +per_cpu_ptr (&batched_entropy_u64, cpu)->position =UINT_MAX ; +return 0 ; +} +#endif +/** * randomize_page - Generate a random, page aligned address * @start: The smallest acceptable address the caller will take.
@@ -1182,7 +1201,7 @@ struct fast_pool { };struct work_struct mix;unsigned long last; -atomic_t count; +unsigned int count;u16 reg_idx; };
@@ -1218,6 +1237,29 @@ static void fast_mix(u32 pool[4]) static DEFINE_PER_CPU(struct fast_pool, irq_randomness); +#ifdef CONFIG_SMP +/* +* This function is called when the CPU has just come online, with +* entry CPUHP_AP_RANDOM_ONLINE, just after CPUHP_AP_WORKQUEUE_ONLINE. +*/ +int random_online_cpu (unsigned int cpu) +{ +/* +* During CPU shutdown and before CPU onlining, add_interrupt_ +* randomness() may schedule mix_interrupt_randomness(), and +* set the MIX_INFLIGHT flag. However, because the worker can +* be scheduled on a different CPU during this period, that +* flag will never be cleared. For that reason, we zero out +* the flag here, which runs just after workqueues are onlined +* for the CPU again. This also has the effect of setting the +* irq randomness count to zero so that new accumulated irqs +* are fresh. +*/ +per_cpu_ptr (&irq_randomness, cpu)->count =0 ; +return 0 ; +} +#endif +static u32 get_reg (struct fast_pool *f,struct pt_regs *regs) {u32 *ptr = (u32 *)regs;
@@ -1242,15 +1284,6 @@ static void mix_interrupt_randomness(struct work_struct *work)local_irq_disable ();if (fast_pool !=this_cpu_ptr (&irq_randomness)) {local_irq_enable (); -/* -* If we are unlucky enough to have been moved to another CPU, -* during CPU hotplug while the CPU was shutdown then we set -* our count to zero atomically so that when the CPU comes -* back online, it can enqueue work again. The _release here -* pairs with the atomic_inc_return_acquire in -* add_interrupt_randomness(). -*/ -atomic_set_release (&fast_pool->count,0 );return ; }
@@ -1259,7 +1292,7 @@ static void mix_interrupt_randomness(struct work_struct *work)* consistent view, before we reenable irqs again. */ memcpy (pool, fast_pool->pool32,sizeof (pool)); -atomic_set (&fast_pool->count,0 ); + fast_pool->count =0 ; fast_pool->last = jiffies;local_irq_enable ();
@@ -1295,14 +1328,13 @@ void add_interrupt_randomness(int irq) }fast_mix (fast_pool->pool32); -/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */ - new_count = (unsigned int )atomic_inc_return_acquire (&fast_pool->count); + new_count = ++fast_pool->count;if (unlikely (crng_init ==0 )) {if (new_count >=64 &&crng_pre_init_inject (fast_pool->pool32,sizeof (fast_pool->pool32), true, true) >0 ) { -atomic_set (&fast_pool->count,0 ); + fast_pool->count =0 ; fast_pool->last = now;if (spin_trylock (&input_pool.lock)) {_mix_pool_bytes (&fast_pool->pool32,sizeof (fast_pool->pool32));
@@ -1320,7 +1352,7 @@ void add_interrupt_randomness(int irq)if (unlikely (!fast_pool->mix.func))INIT_WORK (&fast_pool->mix, mix_interrupt_randomness); -atomic_or (MIX_INFLIGHT , &fast_pool->count); + fast_pool->count |=MIX_INFLIGHT ;queue_work_on (raw_smp_processor_id (), system_highpri_wq, &fast_pool->mix); }EXPORT_SYMBOL_GPL (add_interrupt_randomness);
include/linux/cpuhotplug.h +2 -0
@@ -100,6 +100,7 @@ enum cpuhp_state {CPUHP_AP_ARM_CACHE_B15_RAC_DEAD ,CPUHP_PADATA_DEAD ,CPUHP_AP_DTPM_CPU_DEAD , +CPUHP_RANDOM_PREPARE ,CPUHP_WORKQUEUE_PREP ,CPUHP_POWER_NUMA_PREPARE , CPUHP_HRTIMERS_PREPARE,
@@ -240,6 +241,7 @@ enum cpuhp_state {CPUHP_AP_PERF_CSKY_ONLINE ,CPUHP_AP_WATCHDOG_ONLINE ,CPUHP_AP_WORKQUEUE_ONLINE , +CPUHP_AP_RANDOM_ONLINE ,CPUHP_AP_RCUTREE_ONLINE ,CPUHP_AP_BASE_CACHEINFO_ONLINE , CPUHP_AP_ONLINE_DYN,
include/linux/random.h +5 -0
@@ -156,4 +156,9 @@ static inline bool __init arch_get_random_long_early(unsigned long *v) }#endif +#ifdef CONFIG_SMP +extern int random_prepare_cpu (unsigned int cpu); +extern int random_online_cpu (unsigned int cpu); +#endif +#endif /* _LINUX_RANDOM_H */
kernel/cpu.c +11 -0
@@ -34,6 +34,7 @@#include <linux/scs.h> #include <linux/percpu-rwsem.h> #include <linux/cpuset.h> +#include <linux/random.h> #include <trace/events/power.h> #define CREATE_TRACE_POINTS
@@ -1659,6 +1660,11 @@ static struct cpuhp_step cpuhp_hp_states[] = { .startup.single = perf_event_init_cpu, .teardown.single = perf_event_exit_cpu, }, + [CPUHP_RANDOM_PREPARE] = { + .name = "random:prepare", + .startup.single = random_prepare_cpu, + .teardown.single = NULL, + }, [CPUHP_WORKQUEUE_PREP] = { .name = "workqueue:prepare", .startup.single = workqueue_prepare_cpu,
@@ -1782,6 +1788,11 @@ static struct cpuhp_step cpuhp_hp_states[] = { .startup.single = workqueue_online_cpu, .teardown.single = workqueue_offline_cpu, }, + [CPUHP_AP_RANDOM_ONLINE] = { + .name = "random:online", + .startup.single = random_online_cpu, + .teardown.single = NULL, + }, [CPUHP_AP_RCUTREE_ONLINE] = { .name = "RCU/tree:online", .startup.single = rcutree_online_cpu,
Signature · 1 line
2.35.0
Quoted 18 lines · Jason A. Donenfeld
For the irq randomness fast pool, rather than having to use expensive atomics, which were visibly the most expensive thing in the entire irq handler, simply take care of the extreme edge case of resetting count to zero in the cpuhp online handler, just after workqueues have been reenabled. This simplifies the code a bit and lets us use vanilla variables rather than atomics, and performance should be improved.
As well, very early on when the CPU comes up, while interrupts are still disabled, we clear out the per-cpu crng and its batches, so that it always starts with fresh randomness.
Cc Thomas Gleixner <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Theodore Ts'o <[email protected]>Cc Sebastian Andrzej Siewior <[email protected]>Cc Sultan Alsawaf <[email protected]>Cc Dominik Brodowski <[email protected]>Signed-off-by Jason A. Donenfeld <[email protected]>
Quoted 3 lines
---
v6 improves the comments around each of the cpuhp functions, as requested.
Perfect thank you.
Did you miss my question regarding cross-CPU init in random_prepare_cpu()?
Sebastian
Jason A. Donenfeld
maintainerHi Sebstian,
Quoted 3 lines · Sebastian Andrzej Siewior
Perfect thank you.
Did you miss my question regarding cross-CPU init inrandom_prepare_cpu()?
I saw your suggestion to do cross-CPU init and rejected the proposal for not actually solving a problem. My email about that was here:
https://lore.kernel.org/lkml/CAHmME9prO9dop7iBRwN54=GMtLH7amS3m_VqGUzL44G1h=R+2A@mail.gmail.com/
Do you think you could ack this v6?
Thanks,
Jason
Quoted 18 lines · Jason A. Donenfeld
For the irq randomness fast pool, rather than having to use expensive atomics, which were visibly the most expensive thing in the entire irq handler, simply take care of the extreme edge case of resetting count to zero in the cpuhp online handler, just after workqueues have been reenabled. This simplifies the code a bit and lets us use vanilla variables rather than atomics, and performance should be improved.
As well, very early on when the CPU comes up, while interrupts are still disabled, we clear out the per-cpu crng and its batches, so that it always starts with fresh randomness.
Cc Thomas Gleixner <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Theodore Ts'o <[email protected]>Cc Sebastian Andrzej Siewior <[email protected]>Cc Sultan Alsawaf <[email protected]>Cc Dominik Brodowski <[email protected]>Signed-off-by Jason A. Donenfeld <[email protected]>
Quoted 3 lines
---
v6 improves the comments around each of the cpuhp functions, as requested.
Now that I noticed that the previous email had some more comments, sorry for that. So lets get that in and worry about the other bits later on.
Sebastian