[v3] random: spread out jitter callback to different CPUs
Commit Message
Rather than merely hoping that the callback gets called on another CPU,
arrange for that to actually happen, by round robining which CPU the
timer fires on. This way, on multiprocessor machines, we exacerbate
jitter by touching the same memory from multiple different cores.
It's necessary to call [try_to_]del_timer_sync() before calling
add_timer_on(), so that the final call to del_timer_sync() at the end of
the function actually succeeds at making sure no handlers are running.
Cc: Sultan Alsawaf <sultan@kerneltoast.com>
Cc: Dominik Brodowski <linux@dominikbrodowski.net>
Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
Changes v2->v3:
- Thomas convinced me try_to_del_timer_sync() was fine.
drivers/char/random.c | 36 +++++++++++++++++++++++++++---------
1 file changed, 27 insertions(+), 9 deletions(-)
Comments
Hi Hillf,
On Wed, Nov 30, 2022 at 2:45 AM Hillf Danton <hdanton@sina.com> wrote:
>
> On 29 Nov 2022 19:27:52 +0100 Jason A. Donenfeld <Jason@zx2c4.com>
> > Rather than merely hoping that the callback gets called on another CPU,
> > arrange for that to actually happen, by round robining which CPU the
> > timer fires on. This way, on multiprocessor machines, we exacerbate
> > jitter by touching the same memory from multiple different cores.
> >
> > It's necessary to call [try_to_]del_timer_sync() before calling
> > add_timer_on(), so that the final call to del_timer_sync() at the end of
> > the function actually succeeds at making sure no handlers are running.
> >
> > Cc: Sultan Alsawaf <sultan@kerneltoast.com>
> > Cc: Dominik Brodowski <linux@dominikbrodowski.net>
> > Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> > Cc: Thomas Gleixner <tglx@linutronix.de>
> > Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> > ---
> > Changes v2->v3:
> > - Thomas convinced me try_to_del_timer_sync() was fine.
> >
> > drivers/char/random.c | 36 +++++++++++++++++++++++++++---------
> > 1 file changed, 27 insertions(+), 9 deletions(-)
> >
> > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > index 7b71cea6a6ab..4cb1d606a492 100644
> > --- a/drivers/char/random.c
> > +++ b/drivers/char/random.c
> > @@ -1232,7 +1232,8 @@ 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;
> > };
> >
> > /*
> > @@ -1250,10 +1251,8 @@ static void __cold entropy_timer(struct timer_list *timer)
> > {
> > struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);
> >
> > - if (++state->samples == state->samples_per_bit) {
> > + if (atomic_inc_return(&state->samples) % state->samples_per_bit == 0)
> > credit_init_bits(1);
> > - state->samples = 0;
> > - }
> > }
> >
> > /*
> > @@ -1263,9 +1262,10 @@ static void __cold entropy_timer(struct timer_list *timer)
> > static void __cold try_to_generate_entropy(void)
> > {
> > enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 15 };
> > - struct entropy_timer_state stack;
> > + struct entropy_timer_state stack = { 0 };
> > 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();
> > @@ -1277,19 +1277,37 @@ static void __cold try_to_generate_entropy(void)
> > if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT)
> > return;
> >
> > - 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);
> > + /*
> > + * 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) {
>
> If CPU RR is moved to the timer callback, timer game like this one that hurts
> brain can be avoided.
There's a comment in the code from Linus about this:
* 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.
> What sense made by trying to delete a non-pending timer?
If the timer is no longer pending, but has not completed executing its
callback, and add_timer_on() is called, subsequent calls to
del_timer_sync() will stop the second add_timer_on(), but the first
one that has not completed executing its callback will not be touched.
Take a look at this example: https://א.cc/xBdEiIKO/c
Jason
@@ -1232,7 +1232,8 @@ 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;
};
/*
@@ -1250,10 +1251,8 @@ static void __cold entropy_timer(struct timer_list *timer)
{
struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);
- if (++state->samples == state->samples_per_bit) {
+ if (atomic_inc_return(&state->samples) % state->samples_per_bit == 0)
credit_init_bits(1);
- state->samples = 0;
- }
}
/*
@@ -1263,9 +1262,10 @@ static void __cold entropy_timer(struct timer_list *timer)
static void __cold try_to_generate_entropy(void)
{
enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 15 };
- struct entropy_timer_state stack;
+ struct entropy_timer_state stack = { 0 };
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();
@@ -1277,19 +1277,37 @@ static void __cold try_to_generate_entropy(void)
if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT)
return;
- 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);
+ /*
+ * 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) {
+ preempt_disable();
+
+ /* Basic CPU round-robin, which avoids the current CPU. */
+ do {
+ cpu = cpumask_next(cpu, cpu_online_mask);
+ if (cpu == nr_cpumask_bits)
+ cpu = cpumask_first(cpu_online_mask);
+ } while (cpu == smp_processor_id() && cpumask_weight(cpu_online_mask) > 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();
}
+ 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));
}