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.
I've tried a few variants. Keeping random lsbits with a most-
significant end marker, or using an explicit bool variable 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@xxxxxxx>
Cc: Dan Williams <dan.j.williams@xxxxxxxxx>
Cc: Kees Cook <keescook@xxxxxxxxxxxx>
Cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Cc: linux-mm@xxxxxxxxx
---
mm/shuffle.c | 21 ++++++++++++---------
1 file changed, 12 insertions(+), 9 deletions(-)
diff --git a/mm/shuffle.c b/mm/shuffle.c
index b3fe97fd6654..0e4bf6a8da52 100644
--- a/mm/shuffle.c
+++ b/mm/shuffle.c
@@ -186,22 +186,25 @@ 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 */
+ long r = READ_ONCE(rand), rshift = r << 1;;
/*
- * The lack of locking is deliberate. If 2 threads race to
+ * rand holds some random msbits, with the end marked by a 1 bit.
+ * 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.
*/
- 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 (r < 0)
add_to_free_area(page, area, migratetype);
else
add_to_free_area_tail(page, area, migratetype);
- rand_bits--;
- rand >>= 1;
}
--
2.25.1
