* [RFC PATCH v1 34/50] mm/slub.c: Use cheaper prandom source in shuffle_freelist
@ 2019-10-03 8:55 George Spelvin
0 siblings, 0 replies; only message in thread
From: George Spelvin @ 2019-10-03 8:55 UTC (permalink / raw)
To: linux-kernel, lkml; +Cc: Thomas Garnier, Yu Zhao, Sean Rees
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
^ permalink raw reply related [flat|nested] only message in thread
only message in thread, other threads:[~2020-03-28 16:46 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-10-03 8:55 [RFC PATCH v1 34/50] mm/slub.c: Use cheaper prandom source in shuffle_freelist George Spelvin
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).