Re: [PATCH v3] random: spread out jitter callback to different CPUs

[Jason A. Donenfeld]

Hi Hillf,

On Wed, Nov 30, 2022 at 2:45 AM Hillf Danton <hdanton@xxxxxxxx> wrote:
>
> On 29 Nov 2022 19:27:52 +0100 Jason A. Donenfeld <Jason@xxxxxxxxx>
> > 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@xxxxxxxxxxxxxxx>
> > Cc: Dominik Brodowski <linux@xxxxxxxxxxxxxxxxxxxx>
> > Cc: Sebastian Andrzej Siewior <bigeasy@xxxxxxxxxxxxx>
> > Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
> > Signed-off-by: Jason A. Donenfeld <Jason@xxxxxxxxx>
> > ---
> > 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