| Message ID | 20220929103059.277230-1-Jason@zx2c4.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Delegated to: | Herbert Xu |
| Headers | show |
| Series | prandom: make use of smaller types in prandom_u32_max | expand |
On Thu, 29 Sept 2022 at 12:31, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > When possible at compile-time, make use of smaller types in > prandom_u32_max(), so that we can use smaller batches from random.c, > which in turn leads to a 2x or 4x performance boost. This makes a > difference, for example, in kfence, which needs a fast stream of small > numbers (booleans). > > At the same time, we use the occasion to update the old documentation on > these functions. prandom_u32() and prandom_bytes() have direct > replacements now in random.h, while prandom_u32_max() remains useful as > a prandom.h function, since it's not cryptographically secure by virtue > of not being evenly distributed. > > Cc: Marco Elver <elver@google.com> > Cc: Dominik Brodowski <linux@dominikbrodowski.net> > Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Acked-by: Marco Elver <elver@google.com> > --- > include/linux/prandom.h | 17 +++++++++++------ > 1 file changed, 11 insertions(+), 6 deletions(-) > > diff --git a/include/linux/prandom.h b/include/linux/prandom.h > index deace5fb4e62..78db003bc290 100644 > --- a/include/linux/prandom.h > +++ b/include/linux/prandom.h > @@ -12,11 +12,13 @@ > #include <linux/percpu.h> > #include <linux/random.h> > > +/* Deprecated: use get_random_u32 instead. */ > static inline u32 prandom_u32(void) > { > return get_random_u32(); > } > > +/* Deprecated: use get_random_bytes instead. */ > static inline void prandom_bytes(void *buf, size_t nbytes) > { > return get_random_bytes(buf, nbytes); > @@ -37,17 +39,20 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state); > * prandom_u32_max - returns a pseudo-random number in interval [0, ep_ro) > * @ep_ro: right open interval endpoint > * > - * Returns a pseudo-random number that is in interval [0, ep_ro). Note > - * that the result depends on PRNG being well distributed in [0, ~0U] > - * u32 space. Here we use maximally equidistributed combined Tausworthe > - * generator, that is, prandom_u32(). This is useful when requesting a > - * random index of an array containing ep_ro elements, for example. > + * Returns a pseudo-random number that is in interval [0, ep_ro). This is > + * useful when requesting a random index of an array containing ep_ro elements, > + * for example. The result is somewhat biased when ep_ro is not a power of 2, > + * so do not use this for cryptographic purposes. > * > * Returns: pseudo-random number in interval [0, ep_ro) > */ > static inline u32 prandom_u32_max(u32 ep_ro) > { > - return (u32)(((u64) prandom_u32() * ep_ro) >> 32); > + if (__builtin_constant_p(ep_ro <= 1U << 8) && ep_ro <= 1U << 8) > + return (get_random_u8() * ep_ro) >> 8; > + if (__builtin_constant_p(ep_ro <= 1U << 16) && ep_ro <= 1U << 16) > + return (get_random_u16() * ep_ro) >> 16; > + return ((u64)get_random_u32() * ep_ro) >> 32; > } > > /* > -- > 2.37.3 >
diff --git a/include/linux/prandom.h b/include/linux/prandom.h index deace5fb4e62..78db003bc290 100644 --- a/include/linux/prandom.h +++ b/include/linux/prandom.h @@ -12,11 +12,13 @@ #include <linux/percpu.h> #include <linux/random.h> +/* Deprecated: use get_random_u32 instead. */ static inline u32 prandom_u32(void) { return get_random_u32(); } +/* Deprecated: use get_random_bytes instead. */ static inline void prandom_bytes(void *buf, size_t nbytes) { return get_random_bytes(buf, nbytes); @@ -37,17 +39,20 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state); * prandom_u32_max - returns a pseudo-random number in interval [0, ep_ro) * @ep_ro: right open interval endpoint * - * Returns a pseudo-random number that is in interval [0, ep_ro). Note - * that the result depends on PRNG being well distributed in [0, ~0U] - * u32 space. Here we use maximally equidistributed combined Tausworthe - * generator, that is, prandom_u32(). This is useful when requesting a - * random index of an array containing ep_ro elements, for example. + * Returns a pseudo-random number that is in interval [0, ep_ro). This is + * useful when requesting a random index of an array containing ep_ro elements, + * for example. The result is somewhat biased when ep_ro is not a power of 2, + * so do not use this for cryptographic purposes. * * Returns: pseudo-random number in interval [0, ep_ro) */ static inline u32 prandom_u32_max(u32 ep_ro) { - return (u32)(((u64) prandom_u32() * ep_ro) >> 32); + if (__builtin_constant_p(ep_ro <= 1U << 8) && ep_ro <= 1U << 8) + return (get_random_u8() * ep_ro) >> 8; + if (__builtin_constant_p(ep_ro <= 1U << 16) && ep_ro <= 1U << 16) + return (get_random_u16() * ep_ro) >> 16; + return ((u64)get_random_u32() * ep_ro) >> 32; } /*
When possible at compile-time, make use of smaller types in prandom_u32_max(), so that we can use smaller batches from random.c, which in turn leads to a 2x or 4x performance boost. This makes a difference, for example, in kfence, which needs a fast stream of small numbers (booleans). At the same time, we use the occasion to update the old documentation on these functions. prandom_u32() and prandom_bytes() have direct replacements now in random.h, while prandom_u32_max() remains useful as a prandom.h function, since it's not cryptographically secure by virtue of not being evenly distributed. Cc: Marco Elver <elver@google.com> Cc: Dominik Brodowski <linux@dominikbrodowski.net> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> --- include/linux/prandom.h | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-)