Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <CAHmME9pb9A4SN6TTjNvvxKqw1L3gXVOX7KKihfEH4AgKGNGZ2A@mail.gmail.com>
 <20220128153344.34211-1-Jason@zx2c4.com>
In-Reply-To: <20220128153344.34211-1-Jason@zx2c4.com>
From:   "Jason A. Donenfeld" <Jason@zx2c4.com>
Date:   Fri, 28 Jan 2022 16:48:17 +0100
Message-ID: <CAHmME9pe2BEJV4WiZNHmDmH_XK621Qqr1JCBdgTNZmr4JGBA4w@mail.gmail.com>
Subject: Re: [PATCH] random: remove batched entropy locking
To:     Andy Lutomirski <luto@amacapital.net>,
        =?UTF-8?Q?Jonathan_Neusch=C3=A4fer?= <j.neuschaefer@gmx.net>,
        "Theodore Ts'o" <tytso@mit.edu>,
        LKML <linux-kernel@vger.kernel.org>,
        Sebastian Andrzej Siewior <bigeasy@linutronix.de>,
        Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>, Will Deacon <will@kernel.org>,
        Waiman Long <longman@redhat.com>,
        Boqun Feng <boqun.feng@gmail.com>
Cc:     Andy Lutomirski <luto@kernel.org>, stable <stable@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

Hi Andy,

On Fri, Jan 28, 2022 at 4:34 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Andy - could you take a look at this and let me know if it's still
> correct after I've ported it out of your series and into a standalone
> thing here? I'd prefer to hold off on moving forward on this until I
> receive our green light. I'm also still a bit uncertain about your NB:
> comment regarding the acceptable race. If you could elaborate on that
> argument, it might save me a few cycles with my thinking cap on.
[...]
> +       position = READ_ONCE(batch->position);
> +       /* NB: position can change to ARRAY_SIZE(batch->entropy_u64) out
> +        * from under us -- see invalidate_batched_entropy().  If this,
> +        * happens it's okay if we still return the data in the batch. */
> +       if (unlikely(position + 1 > ARRAY_SIZE(batch->entropy_u64))) {
>                 extract_crng((u8 *)batch->entropy_u64);
> -               batch->position = 0;
> +               position = 0;

So the argument for this is something along the lines of -- if the
pool is invalidated _after_ the position value is read, in the worst
case, we read old data, and then we set position to value 1, so the
remaining reads _also_ are of invalidated data, and then eventually
this depletes and we get newly extracted data? So this means that in
some racey situations, we're lengthening the window during which
get_random_u{32,64}() returns bad randomness, right?

Couldn't that race be avoided entirely by something like the below?

Jason

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 50c50a59847e..664f1a7eb293 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2082,14 +2082,15 @@ u64 get_random_u64(void)
  u64 ret;
  unsigned long flags;
  struct batched_entropy *batch;
- unsigned int position;
+ unsigned int position, original;
  static void *previous;

  warn_unseeded_randomness(&previous);

  local_irq_save(flags);
  batch = this_cpu_ptr(&batched_entropy_u64);
- position = READ_ONCE(batch->position);
+try_again:
+ original = position = READ_ONCE(batch->position);
  /* NB: position can change to ARRAY_SIZE(batch->entropy_u64) out
  * from under us -- see invalidate_batched_entropy().  If this
  * happens it's okay if we still return the data in the batch. */
@@ -2098,6 +2099,8 @@ u64 get_random_u64(void)
  position = 0;
  }
  ret = batch->entropy_u64[position++];
+ if (unlikely(cmpxchg(&batch->position, original, batch) != original))
+ goto try_again;
  WRITE_ONCE(batch->position, position);
  local_irq_restore(flags);
  return ret;