Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Message-Id: <202003281643.02SGhKpM009093@sdf.org>
From:   George Spelvin <lkml@sdf.org>
Date:   Thu, 3 Oct 2019 04:55:27 -0400
Subject: [RFC PATCH v1 34/50] mm/slub.c: Use cheaper prandom source in
 shuffle_freelist
To:     linux-kernel@vger.kernel.org, lkml@sdf.org
Cc:     Thomas Garnier <thgarnie@chromium.org>,
        Yu Zhao <yuzhao@google.com>, Sean Rees <sean@erifax.org>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

The pre-generated permutation which we're choosing a random starting
offset into was itself generated with prandom (in freelist_randomize()),
so there's not much point using a crypto-quality generator here.

Also, prandom_u32_max() uses a multiplicative algorithm for generating
random integers in a range, which is faster than modulo.

TODO: Figure out a better algorithm for the whole thing.  A single
permutation with a random starting point is a bit limiting.
Can we make a full shuffle fast enough. or do we need to stick
with something less general?

We could easily add an outer offset: off2 + random_seq[off1 + i]

Perhaps instead of just a random starting point, a random start
and step?  Unfortunately, the step must be relatively prime to the
count, and the latter is not chosen to make things convenient.
But it's easy enough to precompute a list of possible steps.
Or we could at least allow steps of +1 and -1.

Should random_seq be changed periodically?  It's a separately
allocated structure, so it's easy to allocate a new one and swap
it out atomically.

or even an Enigma-style double rotor:
page[i] = off3 + random_seq2[off2 + random_seq1[off1 + i]]

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Thomas Garnier <thgarnie@chromium.org>
Cc: Yu Zhao <yuzhao@google.com>
Cc: Sean Rees <sean@erifax.org>
---
 mm/slub.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/slub.c b/mm/slub.c
index 8eafccf759409..94d765666cff0 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1580,7 +1580,7 @@ static bool shuffle_freelist(struct kmem_cache *s, struct page *page)
 		return false;
 
 	freelist_count = oo_objects(s->oo);
-	pos = get_random_int() % freelist_count;
+	pos = prandom_u32_max(freelist_count);
 
 	page_limit = page->objects * s->size;
 	start = fixup_red_left(s, page_address(page));
-- 
2.26.0