Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random()

From: George Spelvin <lkml@SDF.ORG>
To: Alexander Duyck <alexander.duyck@gmail.com>
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>,
	lkml@sdf.org
Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random()
Date: Wed, 18 Mar 2020 18:35:00 +0000	[thread overview]
Message-ID: <20200318183500.GC2281@SDF.ORG> (raw)
In-Reply-To: <CAKgT0UdFoQmq4aQ9AkqSoPRoOJOVOxamOio5BaY8qQSxkWQ7uw@mail.gmail.com>

On Wed, Mar 18, 2020 at 08:26:06AM -0700, Alexander Duyck wrote:
> On Tue, Mar 17, 2020 at 6:44 PM George Spelvin <lkml@sdf.org> wrote:
>> +       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.

I could, but what would it matter?  I have just confirmed that all of:
	x << 1 | 1;
	(x << 1) + 1;
	x + x + 1;
	x + x | 1;
	2*x + 1;
	2*x | 1;
compile to
	leal	1(%rdi,%rdi), %eax

on x86, and two instructions on every other processor I can think of. 

Since this is concpetually a bit-manipulation operation where carry
propagation is undesirable, the logical operation form seems the most
natural way to write it.

As for the parens, all C programmers are forced to remember that the
boolean operators have weirdly low precedence (below < <= == >= >),
so there's no risk of confusion.

>>         }
>> +       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.

Er... but why would I want to?  On most processors, "branch on sign bit"
is a single instruction, and that's the instruction I'm hoping the 
compiler will generate.

That's why I changed the shift direction from the original right (testing
the lsbit) to left (testing the msbit): slight code size reduction.

Anything else produces larger and slower object code, for no benefit.