Re: [PATCH] mm/shuffle.c: optimize add_to_free_area_random()

[Kees Cook <keescook@chromium.org>]

On Tue, Mar 17, 2020 at 01:50:35PM +0000, George Spelvin wrote:
> First, use long rather than u64 for the bit buffer type, which
> is significantly more efficient on 32-bit processors.

Why? This is twice as many get_random_*() calls for 32-bit: it'll save
whatever bits it doesn't use. (Speaking to word-sized stores, yes, that
makes sense, but see below...)

> Second, avoid the need for a separate rand_bits counter.
> rand_bits is never more than 63, so there's always room in rand
> for a bit to mark the end of the available bits.  This makes the
> shared state atomically updatable, which makes it a lot easier
> to reason about race conditions.

What are the race conditions? I had to go look at I see that
add_to_free_area_random() is called under __free_one_page() which is
under &zone->lock. Would it make more sense to store the randomness
per-zone and entirely side-step the issues?

> Third, use READ_ONCE and WRITE_ONCE.  Without them, the compiler
> may spill to the shared static in arbitrarily perverse ways,
> and combined with the fact that the code eschews locking, that
> is a recipe for hard-to-find bugs.  Now, a race might cause a bit
> to be used twice, or get_random_long() to be called redundantly,
> but it can't summon nasal daemons.

All these things might make the results less predictable, too. :) But,
yes, if there was deterministic sharing of random values, that'd be
bad. But this patch doesn't really solve the "use the same random bits"
problem, which is the very thing that might get us into a predictable
state. If two zones both call READ_ONCE(), use the same value (eek),
and then both call WRITE_ONCE(), one of them wins the write (no big deal).

-- 
Kees Cook