kernel/linux.git/include/linux/prandom.h, branch v6.19.11

prandom: remove next_pseudo_random32

2025-10-30T17:35:26+00:00

next_pseudo_random32 implements a LCG with known bad statistical properties and was only used in two pieces of testing code. With no remaining users now, remove it. Signed-off-by: Markus Theil Reviewed-by: Krzysztof Karas Signed-off-by: Jason A. Donenfeld

prandom: Include in

2024-10-03T16:21:07+00:00

include was removed from in d9f29deb7fe8 ("prandom: Remove unused include") because this inclusion broke arm64 due to a circular dependency on include files. __percpu tag is defined in include/linux/compiler_types.h, so there is currently no direct need for the inclusion of . However, in [1] we would like to repurpose __percpu tag as a named address space qualifier, where __percpu macro uses defines from . The circular dependency was removed in ddd8e37ebaa1 ("random: Do not include in ") and it cleared the path for the inclusion of in . This patch is basically a revert of d9f29deb7fe8 ("prandom: Remove unused include"). [1] https://lore.kernel.org/lkml/20240812115945.484051-4-ubizjak@gmail.com/ Signed-off-by: Uros Bizjak Cc: Theodore Ts'o Cc: Jason A. Donenfeld Cc: Kent Overstreet Signed-off-by: Jason A. Donenfeld

prandom: Remove unused include

2023-12-21T00:26:30+00:00

prandom.h doesn't use percpu.h - this fixes some circular header issues. Signed-off-by: Kent Overstreet Signed-off-by: Suren Baghdasaryan

prandom: remove prandom_u32_max()

2022-12-20T02:13:45+00:00

Convert the final two users of prandom_u32_max() that slipped in during 6.2-rc1 to use get_random_u32_below(). Then, with no more users left, we can finally remove the deprecated function. Signed-off-by: Jason A. Donenfeld

random: include in the right header

2022-12-04T13:37:08+00:00

uses DO_ONCE(), so it should include directly. In contrast, does not use code from , so it should be removed. Move the `#include ` line into the right file. Signed-off-by: Christophe JAILLET Fixes: c0842fbc1b18 ("random32: move the pseudo-random 32-bit definitions to prandom.h") Signed-off-by: Jason A. Donenfeld

random: use rejection sampling for uniform bounded random integers

2022-11-17T16:36:47+00:00

Until the very recent commits, many bounded random integers were calculated using `get_random_u32() % max_plus_one`, which not only incurs the price of a division -- indicating performance mostly was not a real issue -- but also does not result in a uniformly distributed output if max_plus_one is not a power of two. Recent commits moved to using `prandom_u32_max(max_plus_one)`, which replaces the division with a faster multiplication, but still does not solve the issue with non-uniform output. For some users, maybe this isn't a problem, and for others, maybe it is, but for the majority of users, probably the question has never been posed and analyzed, and nobody thought much about it, probably assuming random is random is random. In other words, the unthinking expectation of most users is likely that the resultant numbers are uniform. So we implement here an efficient way of generating uniform bounded random integers. Through use of compile-time evaluation, and avoiding divisions as much as possible, this commit introduces no measurable overhead. At least for hot-path uses tested, any potential difference was lost in the noise. On both clang and gcc, code generation is pretty small. The new function, get_random_u32_below(), lives in random.h, rather than prandom.h, and has a "get_random_xxx" function name, because it is suitable for all uses, including cryptography. In order to be efficient, we implement a kernel-specific variant of Daniel Lemire's algorithm from "Fast Random Integer Generation in an Interval", linked below. The kernel's variant takes advantage of constant folding to avoid divisions entirely in the vast majority of cases, works on both 32-bit and 64-bit architectures, and requests a minimal amount of bytes from the RNG. Link: https://arxiv.org/pdf/1805.10941.pdf Cc: stable@vger.kernel.org # to ease future backports that use this api Signed-off-by: Jason A. Donenfeld

prandom: remove unused functions

2022-10-11T23:42:58+00:00

With no callers left of prandom_u32() and prandom_bytes(), as well as get_random_int(), remove these deprecated wrappers, in favor of get_random_u32() and get_random_bytes(). Reviewed-by: Greg Kroah-Hartman Reviewed-by: Kees Cook Reviewed-by: Yury Norov Acked-by: Jakub Kicinski Signed-off-by: Jason A. Donenfeld

prandom: make use of smaller types in prandom_u32_max

2022-09-29T19:37:27+00:00

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: Dominik Brodowski Acked-by: Marco Elver Signed-off-by: Jason A. Donenfeld

random32: use real rng for non-deterministic randomness

2022-05-18T13:53:52+00:00

random32.c has two random number generators in it: one that is meant to be used deterministically, with some predefined seed, and one that does the same exact thing as random.c, except does it poorly. The first one has some use cases. The second one no longer does and can be replaced with calls to random.c's proper random number generator. The relatively recent siphash-based bad random32.c code was added in response to concerns that the prior random32.c was too deterministic. Out of fears that random.c was (at the time) too slow, this code was anonymously contributed. Then out of that emerged a kind of shadow entropy gathering system, with its own tentacles throughout various net code, added willy nilly. Stop👏making👏bespoke👏random👏number👏generators👏. Fortunately, recent advances in random.c mean that we can stop playing with this sketchiness, and just use get_random_u32(), which is now fast enough. In micro benchmarks using RDPMC, I'm seeing the same median cycle count between the two functions, with the mean being _slightly_ higher due to batches refilling (which we can optimize further need be). However, when doing *real* benchmarks of the net functions that actually use these random numbers, the mean cycles actually *decreased* slightly (with the median still staying the same), likely because the additional prandom code means icache misses and complexity, whereas random.c is generally already being used by something else nearby. The biggest benefit of this is that there are many users of prandom who probably should be using cryptographically secure random numbers. This makes all of those accidental cases become secure by just flipping a switch. Later on, we can do a tree-wide cleanup to remove the static inline wrapper functions that this commit adds. There are also some low-ish hanging fruits for making this even faster in the future: a get_random_u16() function for use in the networking stack will give a 2x performance boost there, using SIMD for ChaCha20 will let us compute 4 or 8 or 16 blocks of output in parallel, instead of just one, giving us large buffers for cheap, and introducing a get_random_*_bh() function that assumes irqs are already disabled will shave off a few cycles for ordinary calls. These are things we can chip away at down the road. Acked-by: Jakub Kicinski Acked-by: Theodore Ts'o Signed-off-by: Jason A. Donenfeld

siphash: use one source of truth for siphash permutations

2022-05-18T13:53:52+00:00

The SipHash family of permutations is currently used in three places: - siphash.c itself, used in the ordinary way it was intended. - random32.c, in a construction from an anonymous contributor. - random.c, as part of its fast_mix function. Each one of these places reinvents the wheel with the same C code, same rotation constants, and same symmetry-breaking constants. This commit tidies things up a bit by placing macros for the permutations and constants into siphash.h, where each of the three .c users can access them. It also leaves a note dissuading more users of them from emerging. Signed-off-by: Jason A. Donenfeld