Date:   Fri, 7 Oct 2022 19:28:59 -0600
From:   "Jason A. Donenfeld" <Jason@...c4.com>
To:     "Darrick J. Wong" <djwong@...nel.org>
Cc:     linux-kernel@...r.kernel.org, patches@...ts.linux.dev,
        Andreas Noever <andreas.noever@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Borislav Petkov <bp@...en8.de>,
        Catalin Marinas <catalin.marinas@....com>,
        Christoph Böhmwalder 
        <christoph.boehmwalder@...bit.com>, Christoph Hellwig <hch@....de>,
        Christophe Leroy <christophe.leroy@...roup.eu>,
        Daniel Borkmann <daniel@...earbox.net>,
        Dave Airlie <airlied@...hat.com>,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        "David S . Miller" <davem@...emloft.net>,
        Eric Dumazet <edumazet@...gle.com>,
        Florian Westphal <fw@...len.de>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        "H . Peter Anvin" <hpa@...or.com>,
        Heiko Carstens <hca@...ux.ibm.com>,
        Helge Deller <deller@....de>,
        Herbert Xu <herbert@...dor.apana.org.au>,
        Huacai Chen <chenhuacai@...nel.org>,
        Hugh Dickins <hughd@...gle.com>,
        Jakub Kicinski <kuba@...nel.org>,
        "James E . J . Bottomley" <jejb@...ux.ibm.com>,
        Jan Kara <jack@...e.com>, Jason Gunthorpe <jgg@...pe.ca>,
        Jens Axboe <axboe@...nel.dk>,
        Johannes Berg <johannes@...solutions.net>,
        Jonathan Corbet <corbet@....net>,
        Jozsef Kadlecsik <kadlec@...filter.org>,
        KP Singh <kpsingh@...nel.org>,
        Kees Cook <keescook@...omium.org>,
        Marco Elver <elver@...gle.com>,
        Mauro Carvalho Chehab <mchehab@...nel.org>,
        Michael Ellerman <mpe@...erman.id.au>,
        Pablo Neira Ayuso <pablo@...filter.org>,
        Paolo Abeni <pabeni@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Richard Weinberger <richard@....at>,
        Russell King <linux@...linux.org.uk>,
        Theodore Ts'o <tytso@....edu>,
        Thomas Bogendoerfer <tsbogend@...ha.franken.de>,
        Thomas Gleixner <tglx@...utronix.de>,
        Thomas Graf <tgraf@...g.ch>,
        Ulf Hansson <ulf.hansson@...aro.org>,
        Vignesh Raghavendra <vigneshr@...com>,
        WANG Xuerui <kernel@...0n.name>, Will Deacon <will@...nel.org>,
        Yury Norov <yury.norov@...il.com>,
        dri-devel@...ts.freedesktop.org, kasan-dev@...glegroups.com,
        kernel-janitors@...r.kernel.org,
        linux-arm-kernel@...ts.infradead.org, linux-block@...r.kernel.org,
        linux-crypto@...r.kernel.org, linux-doc@...r.kernel.org,
        linux-fsdevel@...r.kernel.org, linux-media@...r.kernel.org,
        linux-mips@...r.kernel.org, linux-mm@...ck.org,
        linux-mmc@...r.kernel.org, linux-mtd@...ts.infradead.org,
        linux-nvme@...ts.infradead.org, linux-parisc@...r.kernel.org,
        linux-rdma@...r.kernel.org, linux-s390@...r.kernel.org,
        linux-um@...ts.infradead.org, linux-usb@...r.kernel.org,
        linux-wireless@...r.kernel.org, linuxppc-dev@...ts.ozlabs.org,
        loongarch@...ts.linux.dev, netdev@...r.kernel.org,
        sparclinux@...r.kernel.org, x86@...nel.org, Jan Kara <jack@...e.cz>
Subject: Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible

On Fri, Oct 07, 2022 at 02:17:22PM -0700, Darrick J. Wong wrote:
> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
> > Rather than incurring a division or requesting too many random bytes for
> > the given range, use the prandom_u32_max() function, which only takes
> > the minimum required bytes from the RNG and avoids divisions.
> > 
> > Reviewed-by: Kees Cook <keescook@...omium.org>
> > Reviewed-by: KP Singh <kpsingh@...nel.org>
> > Reviewed-by: Christoph Böhmwalder <christoph.boehmwalder@...bit.com> # for drbd
> > Reviewed-by: Jan Kara <jack@...e.cz> # for ext2, ext4, and sbitmap
> > Signed-off-by: Jason A. Donenfeld <Jason@...c4.com>
> > ---
> 
> <snip, skip to the xfs part>
> 
> > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
> > index e2bdf089c0a3..6261599bb389 100644
> > --- a/fs/xfs/libxfs/xfs_alloc.c
> > +++ b/fs/xfs/libxfs/xfs_alloc.c
> > @@ -1520,7 +1520,7 @@ xfs_alloc_ag_vextent_lastblock(
> >  
> >  #ifdef DEBUG
> >  	/* Randomly don't execute the first algorithm. */
> > -	if (prandom_u32() & 1)
> > +	if (prandom_u32_max(2))
> 
> I wonder if these usecases (picking 0 or 1 randomly) ought to have a
> trivial wrapper to make it more obvious that we want boolean semantics:
> 
> static inline bool prandom_bool(void)
> {
> 	return prandom_u32_max(2);
> }
> 
> 	if (prandom_bool())
> 		use_crazy_algorithm(...);
> 

Yea, I've had a lot of similar ideas there. Part of doing this (initial)
patchset is to get an intuitive sense of what's actually used and how
often. On my list for investigation are a get_random_u32_max() to return
uniform numbers by rejection sampling (prandom_u32_max() doesn't do
that uniformly) and adding a function for booleans or bits < 8. Possible
ideas for the latter include:

   bool get_random_bool(void);
   bool get_random_bool(unsigned int probability);
   bool get_random_bits(u8 bits_less_than_eight);

With the core of all of those involving the same batching as the current
get_random_u{8,16,32,64}() functions, but also buffering the latest byte
and managing how many bits are left in it that haven't been shifted out
yet.

So API-wise, there are a few ways to go, so hopefully this series will
start to give a good picture of what's needed.

One thing I've noticed is that most of the prandom_u32_max(2)
invocations are in debug or test code, so that doesn't need to be
optimized. But kfence does that too in its hot path, so a
get_random_bool() function there would in theory lead to an 8x speed-up.
But I guess I just have to try some things and see.

Anyway, that is a long way to say, I share you curiosity on the matter
and I'm looking into it.

Jason

Powered by blists - more mailing lists