mm/shuffle.c: optimize add_to_free_area_random()

First, use long rather than u64 for the bit buffer type, which is significantly more efficient on 32-bit processors.

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.

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.

Quoted 2 lines · George Spelvin

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...)

Quoted 5 lines

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?

Quoted 6 lines

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).

The most serious is that if two threads simultaneously observe rand_bits == 1, but do their decrements separately, you end up with rand_bits = 255 and you generate 255 consecutive 0 bits before refilling the buffer.

Since we're only generating random bits, a screwed-up answer occasionally doesn't really matter (like the comment says "lack of locking is deliberate"), but 255 screwed up bits is a bit much.

I avoided changing the underlying locking model because I didn't feel up to such an invasive change; I managed to fix the problems I saw without going there. And shrink the code; tht seemed like enough of a win to justify it to me.

The compiler is allowed to (in John Woods' memorable explanation) produce code that makes demons fly out of your nose. (More plausibly, it may simply crash.)

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 <[email protected]>

Cc Dan Williams <[email protected]>

Cc Kees Cook <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
 mm/shuffle.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

mm/shuffle.c +6 -4

index e0ed247f8d90..4ba3ba84764d 100644
@@ -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.

mm/shuffle.c +4 -4

+               r = get_random_long();
+               rshift = r << 1 | 1;
        }
+       WRITE_ONCE(rand, rshift);
 
-       if (rand & 1)
+       if ((long)r < 0)
                add_to_free_area(page, area, migratetype);
        else
                add_to_free_area_tail(page, area, migratetype);
-       rand_bits--;
-       rand >>= 1;
 }
--

2.26.0.rc2

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 <[email protected]>

Cc Dan Williams <[email protected]>

Cc Kees Cook <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
 mm/shuffle.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

mm/shuffle.c +16 -10

index e0ed247f8d90..4ba3ba84764d 100644
@@ -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;
 	}
+	WRITE_ONCE(rand, rshift);
 
-	if (rand & 1)
+	if ((long)r < 0)
 		add_to_free_area(page, area, migratetype);
 	else
 		add_to_free_area_tail(page, area, migratetype);
-	rand_bits--;
-	rand >>= 1;
 }

Signature · 1 line

2.26.0.rc2

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 203

Quoted 4 lines · George Spelvin

mm/shuffle.c +1 -3

-       if (rand_bits == 0) {
-               rand_bits = 64;
-               rand = get_random_u64();
+       if (unlikely(rshift == 0)) {

I had the impression that unless unlikely is "mostly never" then it can do more harm than good. Is a branch guaranteed to be taken every BITS_PER_LONG'th occurrence really a candidate for unlikely() annotation?

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 <[email protected]>

Cc Dan Williams <[email protected]>

Cc Kees Cook <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
 mm/shuffle.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

mm/shuffle.c +8 -4

index e0ed247f8d90..4ba3ba84764d 100644
@@ -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

mm/shuffle.c +0 -3

                add_to_free_area(page, area, migratetype);
        else
                add_to_free_area_tail(page, area, migratetype);
-       rand_bits--;
-       rand >>= 1;
 }
--

2.26.0.rc2

Quoted 10 lines · Dan Williams

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 203

Quoted 4 lines · George Spelvin

mm/shuffle.c +1 -3

-       if (rand_bits == 0) {
-               rand_bits = 64;
-               rand = get_random_u64();
+       if (unlikely(rshift == 0)) {

I had the impression that unless unlikely is "mostly never" then it can do more harm than good. Is a branch guaranteed to be taken every BITS_PER_LONG'th occurrence really a candidate for unlikely() annotation?

I had to look this up. GCC manual:

For the purposes of branch prediction optimizations, the probability that a '__builtin_expect' expression is 'true' is controlled by GCC's 'builtin-expect-probability' parameter, which defaults to 90%. You can also use '__builtin_expect_with_probability' to explicitly assign a probability value to individual expressions.

So I think that <= 10% is good enough, which is true in this case.

I was tring to encourage the compiler to:
* Place this code path out of line, and
* Not do the stack manipulations (build a frame, spill registers) needed for a non-leaf function if this path isn't taken.

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 205

Quoted 3 lines · George Spelvin

mm/shuffle.c +3 -0

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

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 209

Quoted 5 lines

        }

mm/shuffle.c +2 -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.

Quoted 7 lines · Alexander Duyck

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 205

Quoted 3 lines · George Spelvin

mm/shuffle.c +3 -0

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

Quoted 6 lines

mm/shuffle.c void __meminit __shuffle_free_memory(pg_data_t *pgdat) · line 209

Quoted 5 lines

        }

mm/shuffle.c +2 -1

+       WRITE_ONCE(rand, rshift);
 
-       if (rand & 1)
+       if ((long)r < 0)

Quoted 6 lines

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.

Quoted 14 lines · George Spelvin

Quoted 4 lines · Dan Williams

I had the impression that unless unlikely is "mostly never" then it can do more harm than good. Is a branch guaranteed to be taken every BITS_PER_LONG'th occurrence really a candidate for unlikely() annotation?

I had to look this up. GCC manual:

For the purposes of branch prediction optimizations, the probability that a '__builtin_expect' expression is 'true' is controlled by GCC's 'builtin-expect-probability' parameter, which defaults to 90%. You can also use '__builtin_expect_with_probability' to explicitly assign a probability value to individual expressions.

Quoted 6 lines

So I think that <= 10% is good enough, which is true in this case.

I was tring to encourage the compiler to:
* Place this code path out of line, and
* Not do the stack manipulations (build a frame, spill registers) needed for a non-leaf function if this path isn't taken.

Understood, I think it's ok in this case because the shuffling only happens for order-10 page free events by default so it will be difficult to measure the perf impact either way. But in other kernel contexts I think unlikely() annotation should come with numbers, 90% not taken is not sufficient in and of itself.

You can add:

Acked-by Dan Williams <[email protected]>

Quoted 22 lines · Dan Williams

Quoted 14 lines · George Spelvin

Quoted 4 lines · Dan Williams

I had the impression that unless unlikely is "mostly never" then it can do more harm than good. Is a branch guaranteed to be taken every BITS_PER_LONG'th occurrence really a candidate for unlikely() annotation?

I had to look this up. GCC manual:

For the purposes of branch prediction optimizations, the probability that a '__builtin_expect' expression is 'true' is controlled by GCC's 'builtin-expect-probability' parameter, which defaults to 90%. You can also use '__builtin_expect_with_probability' to explicitly assign a probability value to individual expressions.

Quoted 6 lines

So I think that <= 10% is good enough, which is true in this case.

I was tring to encourage the compiler to:
* Place this code path out of line, and
* Not do the stack manipulations (build a frame, spill registers) needed for a non-leaf function if this path isn't taken.

Quoted 5 lines

Understood, I think it's ok in this case because the shuffling only happens for order-10 page free events by default so it will be difficult to measure the perf impact either way. But in other kernel contexts I think unlikely() annotation should come with numbers, 90% not taken is not sufficient in and of itself.

I'm not sure I fully understand your point. I *think* you're editorializing on unlikely() in general and not this specific code, but it's a little hard to follow.

Your mention of "order-10 page free events" is confusing. Do you mean "(order-10 page) free events", i.e. freeing of 1024 consecutive pages? Or are you using "order" as a synonym for "approximately" and you mean "approximately 10 (page free event)s"?

We both agree (I hope) that the number here is obvious on brief
inspection: 1/BITS_PER_LONG.

GCC's heuristics are tuned to value cycles on the fast path 9x as much as cycles on the slow path, so it will spend up to 9 cycles on the slow path to save a cycle on the fast path.

I've found one comment (https://pastebin.com/S8Y8tqZy) saying that GCC < 9.x was a lot sloppier on the cost ratio and could pessimize the code if the branch was more than ~ 1% taken. Perhaps that's what you're remembering?

Fortunately, 1/64 = 1.56% is fairly close to 1%. so I'm not too worried.

I was just putting it out there as a possibility. What I have seen in the past is that under some circumstances gcc can be smart enough to interpret that as a "branch on carry". My thought was you are likely having to test the value against itself and then you might be able to make use of shift and carry flag to avoid that. In addition you could get away from having to recast a unsigned value as a signed one in order to perform the bit test.

Yes, editorializing on unlikely(). Specifically I would normally ask for perf numbers to show that the hint is worth it, but I talked myself out of asking for that in this case.

I'm referring to this:

      if (is_shuffle_order(order))
                add_to_free_area_random(page, &zone->free_area[order],

Where shuffle order is MAX_ORDER-1. I.e. this code is only triggered when we might be releasing a 4MB buddy-page.

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, resulting in rand_count = 255 and rand being filled with zeros for the next 255 calls.

Instead, pack them both into a single, atomically updateable, 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 arbitrarily 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 updateable, 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 a second call to get_random_u*() per 64 bits. The fast path of get_random_u* is less than the 3*64 = 192 instructions saved, and the slow path happens every 64 bytes so isn't affected by the change.

Fourth, use left-shift rather than right. Testing the sign bit produces slightly smaller/faster code than testing the lsbit.

I've tried shifting both ways, and copying the desired bit to a boolean before shifting rather than keeping separate full-width r and rshift variables, but both produce larger code:

                x86_64  i386
This code        94      95
Explicit bool   103      99
Lsbits           99     101
Both             96     100

In a perfect world, the x86-64 object code would be tiny, and dominated by the unavoidable unpredictable branch, but this function doesn't warrant arch-specific optimization.

add_to_free_area_random:
shlq rand(%rip)
jz 3f
1:
jnc 2f
jmp add_to_free_area # tail call
2:
jmp add_to_free_area_tail
3:

        pushq   %rdx
        pushq   %rsi
        pushq   %rdi
        call    get_random_u64
        popq    %rdi
        popq    %rsi
        popq    %rdx

stc
adcq %rax,%rax # not lea because we need carry out
movq %rax, rand(%rip)
jmp 1b

Signed-off-by George Spelvin <[email protected]>

Acked-by Kees Cook <[email protected]>

Acked-by Dan Williams <[email protected]>

Cc Alexander Duyck <[email protected]>

Cc Randy Dunlap <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
v2: Rewrote commit message to explain existing races better.
Made local variables unsigned to avoid (technically undefined) signed overflow.
v3: Typos fixed, Acked-by, expanded commit message.

 mm/shuffle.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

mm/shuffle.c +16 -11

index e0ed247f8d90..16c5fddc292f 100644
@@ -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 unsigned long rand;      /* 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 0..BITS_PER_LONG-1 random msbits, followed by a
+        * 1 bit, then 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;
        }
+       WRITE_ONCE(rand, rshift);
 
-       if (rand & 1)
+       if ((long)r < 0)
                add_to_free_area(page, area, migratetype);
        else
                add_to_free_area_tail(page, area, migratetype);
-       rand_bits--;
-       rand >>= 1;
 }
--

2.26.0.rc2

What kernel is this based on? You might want to rebase on the latest linux-next as it occurs to me that this function was renamed to shuffle_pick_tail as I had incorporated a few bits of it into the logic for placing buddy pages and reported pages on the tail of the list.

Quoted 5 lines · Alexander Duyck

What kernel is this based on? You might want to rebase on the latest linux-next as it occurs to me that this function was renamed to shuffle_pick_tail as I had incorporated a few bits of it into the logic for placing buddy pages and reported pages on the tail of the list.

5.5.8. I didn't realize it made much difference, but I see it does. Due to the different return type, the best variant has probably changed and I'll have to re-check.

Since there's only one call site, should the function be moved to page_alloc.c and inlined?

Quoted 2 lines · George Spelvin

Since there's only one call site, should the function be moved to page_alloc.c and inlined?

The intent was to make it compile-away on CONFIG_SHUFFLE_PAGE_ALLOCATOR=n builds. However, CONFIG_SHUFFLE_PAGE_ALLOCATOR=y is now the common case for distros. So, it's not serving much purpose being in mm/shuffle.c. I'd support moving it.

The separate "rand" and "rand_count" variables could get out of sync with bad results.

In the worst case, two threads would see rand_count=1 and both decrement it, resulting in rand_count=255 and rand being filled with zeros for the next 255 calls.

Instead, pack them both into a single, atomically updateable, 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. Because the random bit buffer is accessed by multiple threads concurrently without locking, omitting those puts us deep in the land of nasal demons. The compiler would be free to spill to the static variable in arbitrarily perverse ways and create hard-to-find bugs.

(I'm torn between this and just declaring the buffer "volatile". Linux tends to prefer marking accesses rather than variables, but in this case, every access to the buffer is volatile. It makes no difference to the generated code.)

Third, use long rather than u64. This not only keeps the state atomically updateable, 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 a second call to get_random_u*() per 64 bits. The fast path of get_random_u* is less than the 3*64 = 192 instructions saved, and the slow path happens every 64 bytes so isn't affected by the change.

Fourth, make the function inline. It's small, and there's only one caller (in mm/page_alloc.c:__free_one_page()), so avoid the function call overhead.

Fifth, use the msbits of the buffer first (left shift) rather than the lsbits (right shift). Testing the sign bit produces slightly smaller/faster code than testing the lsbit.

I've tried shifting both ways, and copying the desired bit to a boolean before shifting rather than keeping separate full-width r and rshift variables, but both produce larger code:

        x86-64 text size
Msbit           42236
Lsbit           42242 (+6)
Lsbit+bool      42258 (+22)
Msbit+bool      42284 (+52)

(Since this is straight-line code, size is a good proxy for number of instructions and execution time. Using READ/WRITE_ONCE instead of volatile makes no difference.)

In a perfect world, on x86-64 the fast path would be:
shlq rand(%eip)
jz refill
refill_complete:
jc add_to_tail

but I don't see how to get gcc to generate that, and this function isn't worth arch-specific implementation.

Signed-off-by George Spelvin <[email protected]>

Acked-by Kees Cook <[email protected]>

Acked-by Dan Williams <[email protected]>

Cc Alexander Duyck <[email protected]>

Cc Randy Dunlap <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
v2: Rewrote commit message to explain existing races better.
Made local variables unsigned to avoid (technically undefined) signed overflow.
v3: Typos fixed, Acked-by, expanded commit message.
v4: Rebase against -next; function has changed from
add_to_free_area_random() to shuffle_pick_tail. Move to inline function in shuffle.h.
Not sure if it's okay to keep Acked-by: after such a significant change.

 mm/shuffle.c | 23 -----------------------
 mm/shuffle.h | 26 +++++++++++++++++++++++++-
 2 files changed, 25 insertions(+), 24 deletions(-)

mm/shuffle.c +0 -23

index 44406d9977c7..ea281d5e1f23 100644
@@ -182,26 +182,3 @@ void __meminit __shuffle_free_memory(pg_data_t *pgdat)
        for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
                shuffle_zone(z);
 }
-
-bool shuffle_pick_tail(void)
-{
-       static u64 rand;
-       static u8 rand_bits;
-       bool ret;
-
-       /*
-        * The lack of locking is deliberate. If 2 threads race to
-        * update the rand state it just adds to the entropy.
-        */
-       if (rand_bits == 0) {
-               rand_bits = 64;
-               rand = get_random_u64();
-       }
-
-       ret = rand & 1;
-
-       rand_bits--;
-       rand >>= 1;
-
-       return ret;
-}

mm/shuffle.h +25 -1

index 4d79f03b6658..fb79e05cd86d 100644
@@ -22,7 +22,31 @@ enum mm_shuffle_ctl {
 DECLARE_STATIC_KEY_FALSE(page_alloc_shuffle_key);
 extern void page_alloc_shuffle(enum mm_shuffle_ctl ctl);
 extern void __shuffle_free_memory(pg_data_t *pgdat);
-extern bool shuffle_pick_tail(void);
+static inline bool shuffle_pick_tail(void)
+{
+       static unsigned long rand;      /* buffered random bits */
+       unsigned long r = READ_ONCE(rand), rshift = r << 1;
+
+       /*
+        * rand holds 0..BITS_PER_LONG-1 random msbits, followed by a
+        * 1 bit, then 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 (unlikely(rshift == 0)) {
+               r = get_random_long();
+               rshift = r << 1 | 1;
+       }
+       WRITE_ONCE(rand, rshift);
+
+       return (long)r < 0;
+}
+
 static inline void shuffle_free_memory(pg_data_t *pgdat)
 {
        if (!static_branch_unlikely(&page_alloc_shuffle_key))

base-commit: 47780d7892b77e922bbe19b5dea99cde06b2f0e5 --
2.26.0.rc2

The separate "rand" and "rand_count" variables could get out of sync with bad results.

In the worst case, two threads would see rand_count=1 and both decrement it, resulting in rand_count=255 and rand being filled with zeros for the next 255 calls.

Instead, pack them both into a single, atomically updateable, 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. Because the random bit buffer is accessed by multiple threads concurrently without locking, omitting those puts us deep in the land of nasal demons. The compiler would be free to spill to the static variable in arbitrarily perverse ways and create hard-to-find bugs.

(I'm torn between this and just declaring the buffer "volatile". Linux tends to prefer marking accesses rather than variables, but in this case, every access to the buffer is volatile. It makes no difference to the generated code.)

Third, use long rather than u64. This not only keeps the state atomically updateable, 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 a second call to get_random_u*() per 64 bits. The fast path of get_random_u* is less than the 3*64 = 192 instructions saved, and the slow path happens every 64 bytes so isn't affected by the change.

Fourth, make the function inline. It's small, and there's only one caller (in mm/page_alloc.c:__free_one_page()), so avoid the function call overhead.

Fifth, use the msbits of the buffer first (left shift) rather than the lsbits (right shift). Testing the sign bit produces slightly smaller/faster code than testing the lsbit.

I've tried shifting both ways, and copying the desired bit to a boolean before shifting rather than keeping separate full-width r and rshift variables, but both produce larger code:

	x86-64 text size

Msbit 42236
Lsbit 42242 (+6)
Lsbit+bool 42258 (+22)
Msbit+bool 42284 (+52)

(Since this is straight-line code, size is a good proxy for number of instructions and execution time. Using READ/WRITE_ONCE instead of volatile makes no difference.)

In a perfect world, on x86-64 the fast path would be:

	shlq	rand(%eip)
	jz	refill

refill_complete:
jc add_to_tail

but I don't see how to get gcc to generate that, and this function isn't worth arch-specific implementation.

Signed-off-by George Spelvin <[email protected]>

Acked-by Kees Cook <[email protected]>

Acked-by Dan Williams <[email protected]>

Cc Alexander Duyck <[email protected]>

Cc Randy Dunlap <[email protected]>

Cc Andrew Morton <[email protected]>

Cc [email protected]

---
v2: Rewrote commit message to explain existing races better.
Made local variables unsigned to avoid (technically undefined) signed overflow.
v3: Typos fixed, Acked-by, expanded commit message.
v4: Rebase against -next; function has changed from
add_to_free_area_random() to shuffle_pick_tail. Move to inline function in shuffle.h.
Not sure if it's okay to keep Acked-by: after such a significant change.