linux-kernel - [RFC PATCH v1 34/50] mm/slub.c: Use cheaper prandom source in shuffle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-Id: <202003281643.02SGhKpM009093@sdf.org>
Date:   Thu, 3 Oct 2019 04:55:27 -0400
From:   George Spelvin <lkml@....org>
To:     linux-kernel@...r.kernel.org, lkml@....org
Cc:     Thomas Garnier <thgarnie@...omium.org>,
        Yu Zhao <yuzhao@...gle.com>, Sean Rees <sean@...fax.org>
Subject: [RFC PATCH v1 34/50] mm/slub.c: Use cheaper prandom source in
 shuffle_freelist

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@....org>
Cc: Thomas Garnier <thgarnie@...omium.org>
Cc: Yu Zhao <yuzhao@...gle.com>
Cc: Sean Rees <sean@...fax.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