From: Alexander Duyck <alexander.duyck@gmail.com>
To: George Spelvin <lkml@sdf.org>
Cc: Kees Cook <keescook@chromium.org>,
Dan Williams <dan.j.williams@intel.com>,
linux-mm <linux-mm@kvack.org>,
Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random()
Date: Wed, 18 Mar 2020 08:26:06 -0700 [thread overview]
Message-ID: <CAKgT0UdFoQmq4aQ9AkqSoPRoOJOVOxamOio5BaY8qQSxkWQ7uw@mail.gmail.com> (raw)
In-Reply-To: <20200318014410.GA2281@SDF.ORG>
On Tue, Mar 17, 2020 at 6:44 PM George Spelvin <lkml@sdf.org> wrote:
>
> The old code had separate "rand" and "rand_count" variables,
> which could get out of sync with bad results.
>
> In the worst case, two threads would see rand_count == 1 and
> both decrement it, resultint in rand_count = 255 and rand being
> filled with zeros for the next 255 calls.
>
> Instead, pack them both into a single, atomically updatable,
> variable. This makes it a lot easier to reason about race
> conditions. They are still there - the code deliberately eschews
> locking - but basically harmless on the rare occasions that
> they happen.
>
> Second, use READ_ONCE and WRITE_ONCE. Without them, we are deep
> in the land of nasal demons. The compiler would be free to spill
> temporaries to the static variables in arbitrary perverse ways
> and create hard-to-find bugs.
>
> (Alternatively, we could declare the static variable "volatile",
> one of the few places in the Linux kernel that would be correct,
> but it would probably annoy Linus.)
>
> Third, use long rather than u64. This not only keeps the
> state atomically updatable, it also speeds up the fast path
> on 32-bit machines. Saving at least three instructions on
> the fast path (one load, one add-with-carry, and one store)
> is worth exchanging one call to get_random_u64 for two
> calls to get_random_u32. The fast path of get_random_* is
> less than the 3*64 = 192 instructions saved, and the slow
> path happens every 64 bytes so isn't affectrd by the change.
>
> I've tried a few variants. Keeping random lsbits with
> a most-significant end marker, and using an explicit bool
> flag rather than testing r both increase code size slightly.
>
> x86_64 i386
> This code 94 95
> Explicit bool 103 99
> Lsbits 99 101
> Both 96 100
>
> Signed-off-by: George Spelvin <lkml@sdf.org>
> Cc: Dan Williams <dan.j.williams@intel.com>
> Cc: Kees Cook <keescook@chromium.org>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: linux-mm@kvack.org
> ---
> mm/shuffle.c | 26 ++++++++++++++++----------
> 1 file changed, 16 insertions(+), 10 deletions(-)
>
> diff --git a/mm/shuffle.c b/mm/shuffle.c
> index e0ed247f8d90..4ba3ba84764d 100644
> --- a/mm/shuffle.c
> +++ b/mm/shuffle.c
> @@ -186,22 +186,28 @@ void __meminit __shuffle_free_memory(pg_data_t *pgdat)
> void add_to_free_area_random(struct page *page, struct free_area *area,
> int migratetype)
> {
> - static u64 rand;
> - static u8 rand_bits;
> + static long rand; /* 0..BITS_PER_LONG-1 buffered random bits */
> + unsigned long r = READ_ONCE(rand), rshift = r << 1;;
>
> /*
> - * The lack of locking is deliberate. If 2 threads race to
> - * update the rand state it just adds to the entropy.
> + * rand holds some random msbits, with a 1 bit appended, followed
> + * by zero-padding in the lsbits. This allows us to maintain
> + * the pre-generated bits and the count of bits in a single,
> + * atomically updatable, variable.
> + *
> + * The lack of locking is deliberate. If two threads race to
> + * update the rand state it just adds to the entropy. The
> + * worst that can happen is a random bit is used twice, or
> + * get_random_long is called redundantly.
> */
> - if (rand_bits == 0) {
> - rand_bits = 64;
> - rand = get_random_u64();
> + if (unlikely(rshift == 0)) {
> + r = get_random_long();
> + rshift = r << 1 | 1;
You might want to wrap the "r << 1" in parenthesis. Also you could
probably use a + 1 instead of an | 1.
> }
> + WRITE_ONCE(rand, rshift);
>
> - if (rand & 1)
> + if ((long)r < 0)
One trick you might be able to get away with here is to actually
compare r to rshift. "If (rshift <= r)" should give you the same
result. This works since what you are essentially doing is just adding
r to itself so if you overflow rshift will be equal to at most r - 1.
However with the addition of the single bit in the rshift == 0 case it
could potentially be equal in the unlikely case of r being all 1's.
> add_to_free_area(page, area, migratetype);
> else
> add_to_free_area_tail(page, area, migratetype);
> - rand_bits--;
> - rand >>= 1;
> }
> --
> 2.26.0.rc2
>
next prev parent reply other threads:[~2020-03-18 15:26 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-17 13:50 [PATCH] mm/shuffle.c: optimize add_to_free_area_random() George Spelvin
2020-03-17 21:44 ` Kees Cook
2020-03-17 23:06 ` George Spelvin
2020-03-17 23:38 ` Kees Cook
2020-03-18 1:44 ` [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random() George Spelvin
2020-03-18 1:49 ` Randy Dunlap
2020-03-18 3:53 ` Dan Williams
2020-03-18 8:20 ` George Spelvin
2020-03-18 17:36 ` Dan Williams
2020-03-18 19:29 ` George Spelvin
2020-03-18 19:40 ` Dan Williams
2020-03-18 21:02 ` George Spelvin
2020-03-18 3:58 ` Kees Cook
2020-03-18 15:26 ` Alexander Duyck [this message]
2020-03-18 18:35 ` George Spelvin
2020-03-18 19:17 ` Alexander Duyck
2020-03-18 20:06 ` George Spelvin
2020-03-18 20:39 ` [PATCH v3] " George Spelvin
2020-03-18 21:34 ` Alexander Duyck
2020-03-18 22:49 ` George Spelvin
2020-03-18 22:57 ` Dan Williams
2020-03-18 23:18 ` George Spelvin
2020-03-19 12:05 ` [PATCH v4] " George Spelvin
2020-03-19 17:49 ` Alexander Duyck
2020-03-20 17:58 ` Kees Cook
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAKgT0UdFoQmq4aQ9AkqSoPRoOJOVOxamOio5BaY8qQSxkWQ7uw@mail.gmail.com \
--to=alexander.duyck@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=dan.j.williams@intel.com \
--cc=keescook@chromium.org \
--cc=linux-mm@kvack.org \
--cc=lkml@sdf.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).