From e9a688bcb19348862afe30d7c85bc37c4c293471 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sat, 8 Oct 2022 20:42:54 -0600 Subject: random: use rejection sampling for uniform bounded random integers 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 --- drivers/char/random.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 69754155300e..6f323344d0b9 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -160,6 +160,7 @@ EXPORT_SYMBOL(wait_for_random_bytes); * u8 get_random_u8() * u16 get_random_u16() * u32 get_random_u32() + * u32 get_random_u32_below(u32 ceil) * u64 get_random_u64() * unsigned long get_random_long() * @@ -510,6 +511,27 @@ DEFINE_BATCHED_ENTROPY(u16) DEFINE_BATCHED_ENTROPY(u32) DEFINE_BATCHED_ENTROPY(u64) +u32 __get_random_u32_below(u32 ceil) +{ + /* + * This is the slow path for variable ceil. It is still fast, most of + * the time, by doing traditional reciprocal multiplication and + * opportunistically comparing the lower half to ceil itself, before + * falling back to computing a larger bound, and then rejecting samples + * whose lower half would indicate a range indivisible by ceil. The use + * of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable + * in 32-bits. + */ + u64 mult = (u64)ceil * get_random_u32(); + if (unlikely((u32)mult < ceil)) { + u32 bound = -ceil % ceil; + while (unlikely((u32)mult < bound)) + mult = (u64)ceil * get_random_u32(); + } + return mult >> 32; +} +EXPORT_SYMBOL(__get_random_u32_below); + #ifdef CONFIG_SMP /* * This function is called when the CPU is coming up, with entry -- cgit From 7f576b2593a978451416424e75f69ad1e3ae4efe Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 19 Oct 2022 23:19:35 -0600 Subject: random: add helpers for random numbers with given floor or range Now that we have get_random_u32_below(), it's nearly trivial to make inline helpers to compute get_random_u32_above() and get_random_u32_inclusive(), which will help clean up open coded loops and manual computations throughout the tree. One snag is that in order to make get_random_u32_inclusive() operate on closed intervals, we have to do some (unlikely) special case handling if get_random_u32_inclusive(0, U32_MAX) is called. The least expensive way of doing this is actually to adjust the slowpath of get_random_u32_below() to have its undefined 0 result just return the output of get_random_u32(). We can make this basically free by calling get_random_u32() before the branch, so that the branch latency gets interleaved. Cc: stable@vger.kernel.org # to ease future backports that use this api Reviewed-by: Kees Cook Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 6f323344d0b9..f5868dddbb61 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -161,6 +161,8 @@ EXPORT_SYMBOL(wait_for_random_bytes); * u16 get_random_u16() * u32 get_random_u32() * u32 get_random_u32_below(u32 ceil) + * u32 get_random_u32_above(u32 floor) + * u32 get_random_u32_inclusive(u32 floor, u32 ceil) * u64 get_random_u64() * unsigned long get_random_long() * @@ -522,7 +524,21 @@ u32 __get_random_u32_below(u32 ceil) * of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable * in 32-bits. */ - u64 mult = (u64)ceil * get_random_u32(); + u32 rand = get_random_u32(); + u64 mult; + + /* + * This function is technically undefined for ceil == 0, and in fact + * for the non-underscored constant version in the header, we build bug + * on that. But for the non-constant case, it's convenient to have that + * evaluate to being a straight call to get_random_u32(), so that + * get_random_u32_inclusive() can work over its whole range without + * undefined behavior. + */ + if (unlikely(!ceil)) + return rand; + + mult = (u64)ceil * rand; if (unlikely((u32)mult < ceil)) { u32 bound = -ceil % ceil; while (unlikely((u32)mult < bound)) -- cgit From 8032bf1233a74627ce69b803608e650f3f35971c Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sun, 9 Oct 2022 20:44:02 -0600 Subject: treewide: use get_random_u32_below() instead of deprecated function This is a simple mechanical transformation done by: @@ expression E; @@ - prandom_u32_max + get_random_u32_below (E) Reviewed-by: Kees Cook Reviewed-by: Greg Kroah-Hartman Acked-by: Darrick J. Wong # for xfs Reviewed-by: SeongJae Park # for damon Reviewed-by: Jason Gunthorpe # for infiniband Reviewed-by: Russell King (Oracle) # for arm Acked-by: Ulf Hansson # for mmc Signed-off-by: Jason A. Donenfeld --- drivers/block/drbd/drbd_receiver.c | 4 ++-- drivers/bus/mhi/host/internal.h | 2 +- drivers/dma-buf/st-dma-fence-chain.c | 6 +++--- drivers/gpu/drm/i915/gem/i915_gem_execbuffer.c | 2 +- drivers/gpu/drm/i915/gt/intel_execlists_submission.c | 2 +- drivers/gpu/drm/i915/intel_memory_region.c | 4 ++-- drivers/infiniband/core/cma.c | 2 +- drivers/infiniband/hw/cxgb4/id_table.c | 4 ++-- drivers/infiniband/hw/hns/hns_roce_ah.c | 4 ++-- drivers/infiniband/ulp/rtrs/rtrs-clt.c | 2 +- drivers/md/bcache/request.c | 2 +- drivers/media/common/v4l2-tpg/v4l2-tpg-core.c | 8 ++++---- drivers/media/test-drivers/vidtv/vidtv_demod.c | 8 ++++---- drivers/media/test-drivers/vivid/vivid-kthread-cap.c | 2 +- drivers/media/test-drivers/vivid/vivid-kthread-out.c | 2 +- drivers/media/test-drivers/vivid/vivid-radio-rx.c | 4 ++-- drivers/media/test-drivers/vivid/vivid-sdr-cap.c | 2 +- drivers/media/test-drivers/vivid/vivid-touch-cap.c | 2 +- drivers/mmc/core/core.c | 4 ++-- drivers/mmc/host/dw_mmc.c | 2 +- drivers/mtd/nand/raw/nandsim.c | 4 ++-- drivers/mtd/tests/mtd_nandecctest.c | 10 +++++----- drivers/mtd/tests/stresstest.c | 8 ++++---- drivers/mtd/ubi/debug.c | 2 +- drivers/mtd/ubi/debug.h | 6 +++--- drivers/net/ethernet/broadcom/cnic.c | 2 +- .../ethernet/chelsio/inline_crypto/chtls/chtls_io.c | 4 ++-- drivers/net/phy/at803x.c | 2 +- drivers/net/team/team_mode_random.c | 2 +- drivers/net/wireguard/selftest/allowedips.c | 20 ++++++++++---------- drivers/net/wireguard/timers.c | 4 ++-- .../net/wireless/broadcom/brcm80211/brcmfmac/p2p.c | 2 +- drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c | 2 +- drivers/pci/p2pdma.c | 2 +- drivers/s390/scsi/zfcp_fc.c | 2 +- drivers/scsi/fcoe/fcoe_ctlr.c | 4 ++-- drivers/scsi/qedi/qedi_main.c | 2 +- drivers/scsi/scsi_debug.c | 6 +++--- 38 files changed, 76 insertions(+), 76 deletions(-) (limited to 'drivers') diff --git a/drivers/block/drbd/drbd_receiver.c b/drivers/block/drbd/drbd_receiver.c index ee69d50ba4fd..3eccc6cd5004 100644 --- a/drivers/block/drbd/drbd_receiver.c +++ b/drivers/block/drbd/drbd_receiver.c @@ -781,7 +781,7 @@ static struct socket *drbd_wait_for_connect(struct drbd_connection *connection, timeo = connect_int * HZ; /* 28.5% random jitter */ - timeo += prandom_u32_max(2) ? timeo / 7 : -timeo / 7; + timeo += get_random_u32_below(2) ? timeo / 7 : -timeo / 7; err = wait_for_completion_interruptible_timeout(&ad->door_bell, timeo); if (err <= 0) @@ -1004,7 +1004,7 @@ retry: drbd_warn(connection, "Error receiving initial packet\n"); sock_release(s); randomize: - if (prandom_u32_max(2)) + if (get_random_u32_below(2)) goto retry; } } diff --git a/drivers/bus/mhi/host/internal.h b/drivers/bus/mhi/host/internal.h index 01fd10a399b6..c73621aabbd1 100644 --- a/drivers/bus/mhi/host/internal.h +++ b/drivers/bus/mhi/host/internal.h @@ -129,7 +129,7 @@ enum mhi_pm_state { #define PRIMARY_CMD_RING 0 #define MHI_DEV_WAKE_DB 127 #define MHI_MAX_MTU 0xffff -#define MHI_RANDOM_U32_NONZERO(bmsk) (prandom_u32_max(bmsk) + 1) +#define MHI_RANDOM_U32_NONZERO(bmsk) (get_random_u32_below(bmsk) + 1) enum mhi_er_type { MHI_ER_TYPE_INVALID = 0x0, diff --git a/drivers/dma-buf/st-dma-fence-chain.c b/drivers/dma-buf/st-dma-fence-chain.c index 0a9b099d0518..9fbad7317d9b 100644 --- a/drivers/dma-buf/st-dma-fence-chain.c +++ b/drivers/dma-buf/st-dma-fence-chain.c @@ -400,7 +400,7 @@ static int __find_race(void *arg) struct dma_fence *fence = dma_fence_get(data->fc.tail); int seqno; - seqno = prandom_u32_max(data->fc.chain_length) + 1; + seqno = get_random_u32_below(data->fc.chain_length) + 1; err = dma_fence_chain_find_seqno(&fence, seqno); if (err) { @@ -429,7 +429,7 @@ static int __find_race(void *arg) dma_fence_put(fence); signal: - seqno = prandom_u32_max(data->fc.chain_length - 1); + seqno = get_random_u32_below(data->fc.chain_length - 1); dma_fence_signal(data->fc.fences[seqno]); cond_resched(); } @@ -637,7 +637,7 @@ static void randomise_fences(struct fence_chains *fc) while (--count) { unsigned int swp; - swp = prandom_u32_max(count + 1); + swp = get_random_u32_below(count + 1); if (swp == count) continue; diff --git a/drivers/gpu/drm/i915/gem/i915_gem_execbuffer.c b/drivers/gpu/drm/i915/gem/i915_gem_execbuffer.c index 845023c14eb3..29d2459bcc90 100644 --- a/drivers/gpu/drm/i915/gem/i915_gem_execbuffer.c +++ b/drivers/gpu/drm/i915/gem/i915_gem_execbuffer.c @@ -2424,7 +2424,7 @@ gen8_dispatch_bsd_engine(struct drm_i915_private *dev_priv, /* Check whether the file_priv has already selected one ring. */ if ((int)file_priv->bsd_engine < 0) file_priv->bsd_engine = - prandom_u32_max(num_vcs_engines(dev_priv)); + get_random_u32_below(num_vcs_engines(dev_priv)); return file_priv->bsd_engine; } diff --git a/drivers/gpu/drm/i915/gt/intel_execlists_submission.c b/drivers/gpu/drm/i915/gt/intel_execlists_submission.c index c718e6dc40b5..45b605e32c87 100644 --- a/drivers/gpu/drm/i915/gt/intel_execlists_submission.c +++ b/drivers/gpu/drm/i915/gt/intel_execlists_submission.c @@ -3689,7 +3689,7 @@ static void virtual_engine_initial_hint(struct virtual_engine *ve) * NB This does not force us to execute on this engine, it will just * typically be the first we inspect for submission. */ - swp = prandom_u32_max(ve->num_siblings); + swp = get_random_u32_below(ve->num_siblings); if (swp) swap(ve->siblings[swp], ve->siblings[0]); } diff --git a/drivers/gpu/drm/i915/intel_memory_region.c b/drivers/gpu/drm/i915/intel_memory_region.c index 9a4a7fb55582..b9a164efd6ae 100644 --- a/drivers/gpu/drm/i915/intel_memory_region.c +++ b/drivers/gpu/drm/i915/intel_memory_region.c @@ -38,7 +38,7 @@ static int __iopagetest(struct intel_memory_region *mem, u8 value, resource_size_t offset, const void *caller) { - int byte = prandom_u32_max(pagesize); + int byte = get_random_u32_below(pagesize); u8 result[3]; memset_io(va, value, pagesize); /* or GPF! */ @@ -92,7 +92,7 @@ static int iopagetest(struct intel_memory_region *mem, static resource_size_t random_page(resource_size_t last) { /* Limited to low 44b (16TiB), but should suffice for a spot check */ - return prandom_u32_max(last >> PAGE_SHIFT) << PAGE_SHIFT; + return get_random_u32_below(last >> PAGE_SHIFT) << PAGE_SHIFT; } static int iomemtest(struct intel_memory_region *mem, diff --git a/drivers/infiniband/core/cma.c b/drivers/infiniband/core/cma.c index 26d1772179b8..dd1c703b10df 100644 --- a/drivers/infiniband/core/cma.c +++ b/drivers/infiniband/core/cma.c @@ -3807,7 +3807,7 @@ static int cma_alloc_any_port(enum rdma_ucm_port_space ps, inet_get_local_port_range(net, &low, &high); remaining = (high - low) + 1; - rover = prandom_u32_max(remaining) + low; + rover = get_random_u32_below(remaining) + low; retry: if (last_used_port != rover) { struct rdma_bind_list *bind_list; diff --git a/drivers/infiniband/hw/cxgb4/id_table.c b/drivers/infiniband/hw/cxgb4/id_table.c index 280d61466855..e2188b335e76 100644 --- a/drivers/infiniband/hw/cxgb4/id_table.c +++ b/drivers/infiniband/hw/cxgb4/id_table.c @@ -54,7 +54,7 @@ u32 c4iw_id_alloc(struct c4iw_id_table *alloc) if (obj < alloc->max) { if (alloc->flags & C4IW_ID_TABLE_F_RANDOM) - alloc->last += prandom_u32_max(RANDOM_SKIP); + alloc->last += get_random_u32_below(RANDOM_SKIP); else alloc->last = obj + 1; if (alloc->last >= alloc->max) @@ -85,7 +85,7 @@ int c4iw_id_table_alloc(struct c4iw_id_table *alloc, u32 start, u32 num, alloc->start = start; alloc->flags = flags; if (flags & C4IW_ID_TABLE_F_RANDOM) - alloc->last = prandom_u32_max(RANDOM_SKIP); + alloc->last = get_random_u32_below(RANDOM_SKIP); else alloc->last = 0; alloc->max = num; diff --git a/drivers/infiniband/hw/hns/hns_roce_ah.c b/drivers/infiniband/hw/hns/hns_roce_ah.c index 480c062dd04f..b37d2a81584d 100644 --- a/drivers/infiniband/hw/hns/hns_roce_ah.c +++ b/drivers/infiniband/hw/hns/hns_roce_ah.c @@ -41,8 +41,8 @@ static inline u16 get_ah_udp_sport(const struct rdma_ah_attr *ah_attr) u16 sport; if (!fl) - sport = prandom_u32_max(IB_ROCE_UDP_ENCAP_VALID_PORT_MAX + 1 - - IB_ROCE_UDP_ENCAP_VALID_PORT_MIN) + + sport = get_random_u32_below(IB_ROCE_UDP_ENCAP_VALID_PORT_MAX + + 1 - IB_ROCE_UDP_ENCAP_VALID_PORT_MIN) + IB_ROCE_UDP_ENCAP_VALID_PORT_MIN; else sport = rdma_flow_label_to_udp_sport(fl); diff --git a/drivers/infiniband/ulp/rtrs/rtrs-clt.c b/drivers/infiniband/ulp/rtrs/rtrs-clt.c index 8546b8816524..ab75b690ad08 100644 --- a/drivers/infiniband/ulp/rtrs/rtrs-clt.c +++ b/drivers/infiniband/ulp/rtrs/rtrs-clt.c @@ -1517,7 +1517,7 @@ static void rtrs_clt_err_recovery_work(struct work_struct *work) rtrs_clt_stop_and_destroy_conns(clt_path); queue_delayed_work(rtrs_wq, &clt_path->reconnect_dwork, msecs_to_jiffies(delay_ms + - prandom_u32_max(RTRS_RECONNECT_SEED))); + get_random_u32_below(RTRS_RECONNECT_SEED))); } static struct rtrs_clt_path *alloc_path(struct rtrs_clt_sess *clt, diff --git a/drivers/md/bcache/request.c b/drivers/md/bcache/request.c index 3427555b0cca..32e21ba64357 100644 --- a/drivers/md/bcache/request.c +++ b/drivers/md/bcache/request.c @@ -401,7 +401,7 @@ static bool check_should_bypass(struct cached_dev *dc, struct bio *bio) } if (bypass_torture_test(dc)) { - if (prandom_u32_max(4) == 3) + if (get_random_u32_below(4) == 3) goto skip; else goto rescale; diff --git a/drivers/media/common/v4l2-tpg/v4l2-tpg-core.c b/drivers/media/common/v4l2-tpg/v4l2-tpg-core.c index 303d02b1d71c..a366566f22c3 100644 --- a/drivers/media/common/v4l2-tpg/v4l2-tpg-core.c +++ b/drivers/media/common/v4l2-tpg/v4l2-tpg-core.c @@ -872,7 +872,7 @@ static void precalculate_color(struct tpg_data *tpg, int k) } else if (tpg->pattern == TPG_PAT_NOISE) { r = g = b = get_random_u8(); } else if (k == TPG_COLOR_RANDOM) { - r = g = b = tpg->qual_offset + prandom_u32_max(196); + r = g = b = tpg->qual_offset + get_random_u32_below(196); } else if (k >= TPG_COLOR_RAMP) { r = g = b = k - TPG_COLOR_RAMP; } @@ -2286,7 +2286,7 @@ static void tpg_fill_params_extras(const struct tpg_data *tpg, params->wss_width = tpg->crop.width; params->wss_width = tpg_hscale_div(tpg, p, params->wss_width); params->wss_random_offset = - params->twopixsize * prandom_u32_max(tpg->src_width / 2); + params->twopixsize * get_random_u32_below(tpg->src_width / 2); if (tpg->crop.left < tpg->border.left) { left_pillar_width = tpg->border.left - tpg->crop.left; @@ -2495,9 +2495,9 @@ static void tpg_fill_plane_pattern(const struct tpg_data *tpg, linestart_newer = tpg->black_line[p]; } else if (tpg->pattern == TPG_PAT_NOISE || tpg->qual == TPG_QUAL_NOISE) { linestart_older = tpg->random_line[p] + - twopixsize * prandom_u32_max(tpg->src_width / 2); + twopixsize * get_random_u32_below(tpg->src_width / 2); linestart_newer = tpg->random_line[p] + - twopixsize * prandom_u32_max(tpg->src_width / 2); + twopixsize * get_random_u32_below(tpg->src_width / 2); } else { unsigned frame_line_old = (frame_line + mv_vert_old) % tpg->src_height; diff --git a/drivers/media/test-drivers/vidtv/vidtv_demod.c b/drivers/media/test-drivers/vidtv/vidtv_demod.c index e7959ab1add8..d60c6d16beea 100644 --- a/drivers/media/test-drivers/vidtv/vidtv_demod.c +++ b/drivers/media/test-drivers/vidtv/vidtv_demod.c @@ -188,11 +188,11 @@ static void vidtv_demod_update_stats(struct dvb_frontend *fe) * Also, usually, signal strength is a negative number in dBm. */ c->strength.stat[0].svalue = state->tuner_cnr; - c->strength.stat[0].svalue -= prandom_u32_max(state->tuner_cnr / 50); + c->strength.stat[0].svalue -= get_random_u32_below(state->tuner_cnr / 50); c->strength.stat[0].svalue -= 68000; /* Adjust to a better range */ c->cnr.stat[0].svalue = state->tuner_cnr; - c->cnr.stat[0].svalue -= prandom_u32_max(state->tuner_cnr / 50); + c->cnr.stat[0].svalue -= get_random_u32_below(state->tuner_cnr / 50); } static int vidtv_demod_read_status(struct dvb_frontend *fe, @@ -213,11 +213,11 @@ static int vidtv_demod_read_status(struct dvb_frontend *fe, if (snr < cnr2qual->cnr_ok) { /* eventually lose the TS lock */ - if (prandom_u32_max(100) < config->drop_tslock_prob_on_low_snr) + if (get_random_u32_below(100) < config->drop_tslock_prob_on_low_snr) state->status = 0; } else { /* recover if the signal improves */ - if (prandom_u32_max(100) < + if (get_random_u32_below(100) < config->recover_tslock_prob_on_good_snr) state->status = FE_HAS_SIGNAL | FE_HAS_CARRIER | diff --git a/drivers/media/test-drivers/vivid/vivid-kthread-cap.c b/drivers/media/test-drivers/vivid/vivid-kthread-cap.c index 690daada7db4..ee65d20314d3 100644 --- a/drivers/media/test-drivers/vivid/vivid-kthread-cap.c +++ b/drivers/media/test-drivers/vivid/vivid-kthread-cap.c @@ -693,7 +693,7 @@ static noinline_for_stack void vivid_thread_vid_cap_tick(struct vivid_dev *dev, /* Drop a certain percentage of buffers. */ if (dev->perc_dropped_buffers && - prandom_u32_max(100) < dev->perc_dropped_buffers) + get_random_u32_below(100) < dev->perc_dropped_buffers) goto update_mv; spin_lock(&dev->slock); diff --git a/drivers/media/test-drivers/vivid/vivid-kthread-out.c b/drivers/media/test-drivers/vivid/vivid-kthread-out.c index 0833e021bb11..fac6208b51da 100644 --- a/drivers/media/test-drivers/vivid/vivid-kthread-out.c +++ b/drivers/media/test-drivers/vivid/vivid-kthread-out.c @@ -51,7 +51,7 @@ static void vivid_thread_vid_out_tick(struct vivid_dev *dev) /* Drop a certain percentage of buffers. */ if (dev->perc_dropped_buffers && - prandom_u32_max(100) < dev->perc_dropped_buffers) + get_random_u32_below(100) < dev->perc_dropped_buffers) return; spin_lock(&dev->slock); diff --git a/drivers/media/test-drivers/vivid/vivid-radio-rx.c b/drivers/media/test-drivers/vivid/vivid-radio-rx.c index 8bd09589fb15..79c1723bd84c 100644 --- a/drivers/media/test-drivers/vivid/vivid-radio-rx.c +++ b/drivers/media/test-drivers/vivid/vivid-radio-rx.c @@ -94,8 +94,8 @@ retry: if (data_blk == 0 && dev->radio_rds_loop) vivid_radio_rds_init(dev); - if (perc && prandom_u32_max(100) < perc) { - switch (prandom_u32_max(4)) { + if (perc && get_random_u32_below(100) < perc) { + switch (get_random_u32_below(4)) { case 0: rds.block |= V4L2_RDS_BLOCK_CORRECTED; break; diff --git a/drivers/media/test-drivers/vivid/vivid-sdr-cap.c b/drivers/media/test-drivers/vivid/vivid-sdr-cap.c index 0ae5628b86c9..a81f26b76988 100644 --- a/drivers/media/test-drivers/vivid/vivid-sdr-cap.c +++ b/drivers/media/test-drivers/vivid/vivid-sdr-cap.c @@ -90,7 +90,7 @@ static void vivid_thread_sdr_cap_tick(struct vivid_dev *dev) /* Drop a certain percentage of buffers. */ if (dev->perc_dropped_buffers && - prandom_u32_max(100) < dev->perc_dropped_buffers) + get_random_u32_below(100) < dev->perc_dropped_buffers) return; spin_lock(&dev->slock); diff --git a/drivers/media/test-drivers/vivid/vivid-touch-cap.c b/drivers/media/test-drivers/vivid/vivid-touch-cap.c index 6cc32eb54f9d..c7f6e23df51e 100644 --- a/drivers/media/test-drivers/vivid/vivid-touch-cap.c +++ b/drivers/media/test-drivers/vivid/vivid-touch-cap.c @@ -221,7 +221,7 @@ static void vivid_fill_buff_noise(__s16 *tch_buf, int size) static inline int get_random_pressure(void) { - return prandom_u32_max(VIVID_PRESSURE_LIMIT); + return get_random_u32_below(VIVID_PRESSURE_LIMIT); } static void vivid_tch_buf_set(struct v4l2_pix_format *f, diff --git a/drivers/mmc/core/core.c b/drivers/mmc/core/core.c index 95fa8fb1d45f..a1efda85c6f2 100644 --- a/drivers/mmc/core/core.c +++ b/drivers/mmc/core/core.c @@ -97,8 +97,8 @@ static void mmc_should_fail_request(struct mmc_host *host, !should_fail(&host->fail_mmc_request, data->blksz * data->blocks)) return; - data->error = data_errors[prandom_u32_max(ARRAY_SIZE(data_errors))]; - data->bytes_xfered = prandom_u32_max(data->bytes_xfered >> 9) << 9; + data->error = data_errors[get_random_u32_below(ARRAY_SIZE(data_errors))]; + data->bytes_xfered = get_random_u32_below(data->bytes_xfered >> 9) << 9; } #else /* CONFIG_FAIL_MMC_REQUEST */ diff --git a/drivers/mmc/host/dw_mmc.c b/drivers/mmc/host/dw_mmc.c index c78bbc22e0d1..6ef410053037 100644 --- a/drivers/mmc/host/dw_mmc.c +++ b/drivers/mmc/host/dw_mmc.c @@ -1858,7 +1858,7 @@ static void dw_mci_start_fault_timer(struct dw_mci *host) * Try to inject the error at random points during the data transfer. */ hrtimer_start(&host->fault_timer, - ms_to_ktime(prandom_u32_max(25)), + ms_to_ktime(get_random_u32_below(25)), HRTIMER_MODE_REL); } diff --git a/drivers/mtd/nand/raw/nandsim.c b/drivers/mtd/nand/raw/nandsim.c index 672719023241..274a31b93100 100644 --- a/drivers/mtd/nand/raw/nandsim.c +++ b/drivers/mtd/nand/raw/nandsim.c @@ -1405,9 +1405,9 @@ static void ns_do_bit_flips(struct nandsim *ns, int num) if (bitflips && get_random_u16() < (1 << 6)) { int flips = 1; if (bitflips > 1) - flips = prandom_u32_max(bitflips) + 1; + flips = get_random_u32_below(bitflips) + 1; while (flips--) { - int pos = prandom_u32_max(num * 8); + int pos = get_random_u32_below(num * 8); ns->buf.byte[pos / 8] ^= (1 << (pos % 8)); NS_WARN("read_page: flipping bit %d in page %d " "reading from %d ecc: corrected=%u failed=%u\n", diff --git a/drivers/mtd/tests/mtd_nandecctest.c b/drivers/mtd/tests/mtd_nandecctest.c index 440988562cfd..824cc1c03b6a 100644 --- a/drivers/mtd/tests/mtd_nandecctest.c +++ b/drivers/mtd/tests/mtd_nandecctest.c @@ -47,7 +47,7 @@ struct nand_ecc_test { static void single_bit_error_data(void *error_data, void *correct_data, size_t size) { - unsigned int offset = prandom_u32_max(size * BITS_PER_BYTE); + unsigned int offset = get_random_u32_below(size * BITS_PER_BYTE); memcpy(error_data, correct_data, size); __change_bit_le(offset, error_data); @@ -58,9 +58,9 @@ static void double_bit_error_data(void *error_data, void *correct_data, { unsigned int offset[2]; - offset[0] = prandom_u32_max(size * BITS_PER_BYTE); + offset[0] = get_random_u32_below(size * BITS_PER_BYTE); do { - offset[1] = prandom_u32_max(size * BITS_PER_BYTE); + offset[1] = get_random_u32_below(size * BITS_PER_BYTE); } while (offset[0] == offset[1]); memcpy(error_data, correct_data, size); @@ -71,7 +71,7 @@ static void double_bit_error_data(void *error_data, void *correct_data, static unsigned int random_ecc_bit(size_t size) { - unsigned int offset = prandom_u32_max(3 * BITS_PER_BYTE); + unsigned int offset = get_random_u32_below(3 * BITS_PER_BYTE); if (size == 256) { /* @@ -79,7 +79,7 @@ static unsigned int random_ecc_bit(size_t size) * and 17th bit) in ECC code for 256 byte data block */ while (offset == 16 || offset == 17) - offset = prandom_u32_max(3 * BITS_PER_BYTE); + offset = get_random_u32_below(3 * BITS_PER_BYTE); } return offset; diff --git a/drivers/mtd/tests/stresstest.c b/drivers/mtd/tests/stresstest.c index 75b6ddc5dc4d..8062098930d6 100644 --- a/drivers/mtd/tests/stresstest.c +++ b/drivers/mtd/tests/stresstest.c @@ -46,7 +46,7 @@ static int rand_eb(void) again: /* Read or write up 2 eraseblocks at a time - hence 'ebcnt - 1' */ - eb = prandom_u32_max(ebcnt - 1); + eb = get_random_u32_below(ebcnt - 1); if (bbt[eb]) goto again; return eb; @@ -54,12 +54,12 @@ again: static int rand_offs(void) { - return prandom_u32_max(bufsize); + return get_random_u32_below(bufsize); } static int rand_len(int offs) { - return prandom_u32_max(bufsize - offs); + return get_random_u32_below(bufsize - offs); } static int do_read(void) @@ -118,7 +118,7 @@ static int do_write(void) static int do_operation(void) { - if (prandom_u32_max(2)) + if (get_random_u32_below(2)) return do_read(); else return do_write(); diff --git a/drivers/mtd/ubi/debug.c b/drivers/mtd/ubi/debug.c index 908d0e088557..fcca6942dbdd 100644 --- a/drivers/mtd/ubi/debug.c +++ b/drivers/mtd/ubi/debug.c @@ -590,7 +590,7 @@ int ubi_dbg_power_cut(struct ubi_device *ubi, int caller) if (ubi->dbg.power_cut_max > ubi->dbg.power_cut_min) { range = ubi->dbg.power_cut_max - ubi->dbg.power_cut_min; - ubi->dbg.power_cut_counter += prandom_u32_max(range); + ubi->dbg.power_cut_counter += get_random_u32_below(range); } return 0; } diff --git a/drivers/mtd/ubi/debug.h b/drivers/mtd/ubi/debug.h index dc8d8f83657a..23676f32b681 100644 --- a/drivers/mtd/ubi/debug.h +++ b/drivers/mtd/ubi/debug.h @@ -73,7 +73,7 @@ static inline int ubi_dbg_is_bgt_disabled(const struct ubi_device *ubi) static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi) { if (ubi->dbg.emulate_bitflips) - return !prandom_u32_max(200); + return !get_random_u32_below(200); return 0; } @@ -87,7 +87,7 @@ static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi) static inline int ubi_dbg_is_write_failure(const struct ubi_device *ubi) { if (ubi->dbg.emulate_io_failures) - return !prandom_u32_max(500); + return !get_random_u32_below(500); return 0; } @@ -101,7 +101,7 @@ static inline int ubi_dbg_is_write_failure(const struct ubi_device *ubi) static inline int ubi_dbg_is_erase_failure(const struct ubi_device *ubi) { if (ubi->dbg.emulate_io_failures) - return !prandom_u32_max(400); + return !get_random_u32_below(400); return 0; } diff --git a/drivers/net/ethernet/broadcom/cnic.c b/drivers/net/ethernet/broadcom/cnic.c index 2198e35d9e18..74bc053a2078 100644 --- a/drivers/net/ethernet/broadcom/cnic.c +++ b/drivers/net/ethernet/broadcom/cnic.c @@ -4105,7 +4105,7 @@ static int cnic_cm_alloc_mem(struct cnic_dev *dev) for (i = 0; i < MAX_CM_SK_TBL_SZ; i++) atomic_set(&cp->csk_tbl[i].ref_count, 0); - port_id = prandom_u32_max(CNIC_LOCAL_PORT_RANGE); + port_id = get_random_u32_below(CNIC_LOCAL_PORT_RANGE); if (cnic_init_id_tbl(&cp->csk_port_tbl, CNIC_LOCAL_PORT_RANGE, CNIC_LOCAL_PORT_MIN, port_id)) { cnic_cm_free_mem(dev); diff --git a/drivers/net/ethernet/chelsio/inline_crypto/chtls/chtls_io.c b/drivers/net/ethernet/chelsio/inline_crypto/chtls/chtls_io.c index a4256087ac82..ae6b17b96bf1 100644 --- a/drivers/net/ethernet/chelsio/inline_crypto/chtls/chtls_io.c +++ b/drivers/net/ethernet/chelsio/inline_crypto/chtls/chtls_io.c @@ -919,8 +919,8 @@ static int csk_wait_memory(struct chtls_dev *cdev, current_timeo = *timeo_p; noblock = (*timeo_p ? false : true); if (csk_mem_free(cdev, sk)) { - current_timeo = prandom_u32_max(HZ / 5) + 2; - vm_wait = prandom_u32_max(HZ / 5) + 2; + current_timeo = get_random_u32_below(HZ / 5) + 2; + vm_wait = get_random_u32_below(HZ / 5) + 2; } add_wait_queue(sk_sleep(sk), &wait); diff --git a/drivers/net/phy/at803x.c b/drivers/net/phy/at803x.c index 349b7b1dbbf2..b07513c61c35 100644 --- a/drivers/net/phy/at803x.c +++ b/drivers/net/phy/at803x.c @@ -1758,7 +1758,7 @@ static int qca808x_phy_fast_retrain_config(struct phy_device *phydev) static int qca808x_phy_ms_random_seed_set(struct phy_device *phydev) { - u16 seed_value = prandom_u32_max(QCA808X_MASTER_SLAVE_SEED_RANGE); + u16 seed_value = get_random_u32_below(QCA808X_MASTER_SLAVE_SEED_RANGE); return at803x_debug_reg_mask(phydev, QCA808X_PHY_DEBUG_LOCAL_SEED, QCA808X_MASTER_SLAVE_SEED_CFG, diff --git a/drivers/net/team/team_mode_random.c b/drivers/net/team/team_mode_random.c index f3f8dd428402..53d0ce34b8ce 100644 --- a/drivers/net/team/team_mode_random.c +++ b/drivers/net/team/team_mode_random.c @@ -16,7 +16,7 @@ static bool rnd_transmit(struct team *team, struct sk_buff *skb) struct team_port *port; int port_index; - port_index = prandom_u32_max(team->en_port_count); + port_index = get_random_u32_below(team->en_port_count); port = team_get_port_by_index_rcu(team, port_index); if (unlikely(!port)) goto drop; diff --git a/drivers/net/wireguard/selftest/allowedips.c b/drivers/net/wireguard/selftest/allowedips.c index 19eac00b2381..78a916f30c82 100644 --- a/drivers/net/wireguard/selftest/allowedips.c +++ b/drivers/net/wireguard/selftest/allowedips.c @@ -285,8 +285,8 @@ static __init bool randomized_test(void) for (i = 0; i < NUM_RAND_ROUTES; ++i) { get_random_bytes(ip, 4); - cidr = prandom_u32_max(32) + 1; - peer = peers[prandom_u32_max(NUM_PEERS)]; + cidr = get_random_u32_below(32) + 1; + peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v4(&t, (struct in_addr *)ip, cidr, peer, &mutex) < 0) { pr_err("allowedips random self-test malloc: FAIL\n"); @@ -300,7 +300,7 @@ static __init bool randomized_test(void) for (j = 0; j < NUM_MUTATED_ROUTES; ++j) { memcpy(mutated, ip, 4); get_random_bytes(mutate_mask, 4); - mutate_amount = prandom_u32_max(32); + mutate_amount = get_random_u32_below(32); for (k = 0; k < mutate_amount / 8; ++k) mutate_mask[k] = 0xff; mutate_mask[k] = 0xff @@ -311,8 +311,8 @@ static __init bool randomized_test(void) mutated[k] = (mutated[k] & mutate_mask[k]) | (~mutate_mask[k] & get_random_u8()); - cidr = prandom_u32_max(32) + 1; - peer = peers[prandom_u32_max(NUM_PEERS)]; + cidr = get_random_u32_below(32) + 1; + peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v4(&t, (struct in_addr *)mutated, cidr, peer, &mutex) < 0) { @@ -329,8 +329,8 @@ static __init bool randomized_test(void) for (i = 0; i < NUM_RAND_ROUTES; ++i) { get_random_bytes(ip, 16); - cidr = prandom_u32_max(128) + 1; - peer = peers[prandom_u32_max(NUM_PEERS)]; + cidr = get_random_u32_below(128) + 1; + peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v6(&t, (struct in6_addr *)ip, cidr, peer, &mutex) < 0) { pr_err("allowedips random self-test malloc: FAIL\n"); @@ -344,7 +344,7 @@ static __init bool randomized_test(void) for (j = 0; j < NUM_MUTATED_ROUTES; ++j) { memcpy(mutated, ip, 16); get_random_bytes(mutate_mask, 16); - mutate_amount = prandom_u32_max(128); + mutate_amount = get_random_u32_below(128); for (k = 0; k < mutate_amount / 8; ++k) mutate_mask[k] = 0xff; mutate_mask[k] = 0xff @@ -355,8 +355,8 @@ static __init bool randomized_test(void) mutated[k] = (mutated[k] & mutate_mask[k]) | (~mutate_mask[k] & get_random_u8()); - cidr = prandom_u32_max(128) + 1; - peer = peers[prandom_u32_max(NUM_PEERS)]; + cidr = get_random_u32_below(128) + 1; + peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v6(&t, (struct in6_addr *)mutated, cidr, peer, &mutex) < 0) { diff --git a/drivers/net/wireguard/timers.c b/drivers/net/wireguard/timers.c index d54d32ac9bc4..b5706b6718b1 100644 --- a/drivers/net/wireguard/timers.c +++ b/drivers/net/wireguard/timers.c @@ -147,7 +147,7 @@ void wg_timers_data_sent(struct wg_peer *peer) if (!timer_pending(&peer->timer_new_handshake)) mod_peer_timer(peer, &peer->timer_new_handshake, jiffies + (KEEPALIVE_TIMEOUT + REKEY_TIMEOUT) * HZ + - prandom_u32_max(REKEY_TIMEOUT_JITTER_MAX_JIFFIES)); + get_random_u32_below(REKEY_TIMEOUT_JITTER_MAX_JIFFIES)); } /* Should be called after an authenticated data packet is received. */ @@ -183,7 +183,7 @@ void wg_timers_handshake_initiated(struct wg_peer *peer) { mod_peer_timer(peer, &peer->timer_retransmit_handshake, jiffies + REKEY_TIMEOUT * HZ + - prandom_u32_max(REKEY_TIMEOUT_JITTER_MAX_JIFFIES)); + get_random_u32_below(REKEY_TIMEOUT_JITTER_MAX_JIFFIES)); } /* Should be called after a handshake response message is received and processed diff --git a/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c b/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c index 10d9d9c63b28..23c971b77965 100644 --- a/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c +++ b/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c @@ -1128,7 +1128,7 @@ static void brcmf_p2p_afx_handler(struct work_struct *work) if (afx_hdl->is_listen && afx_hdl->my_listen_chan) /* 100ms ~ 300ms */ err = brcmf_p2p_discover_listen(p2p, afx_hdl->my_listen_chan, - 100 * (1 + prandom_u32_max(3))); + 100 * (1 + get_random_u32_below(3))); else err = brcmf_p2p_act_frm_search(p2p, afx_hdl->peer_listen_chan); diff --git a/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c b/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c index de0c545d50fd..1696fbf1009a 100644 --- a/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c +++ b/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c @@ -1099,7 +1099,7 @@ static void iwl_mvm_mac_ctxt_cmd_fill_ap(struct iwl_mvm *mvm, iwl_mvm_mac_ap_iterator, &data); if (data.beacon_device_ts) { - u32 rand = prandom_u32_max(64 - 36) + 36; + u32 rand = get_random_u32_below(64 - 36) + 36; mvmvif->ap_beacon_time = data.beacon_device_ts + ieee80211_tu_to_usec(data.beacon_int * rand / 100); diff --git a/drivers/pci/p2pdma.c b/drivers/pci/p2pdma.c index 88dc66ee1c46..5565f67d6537 100644 --- a/drivers/pci/p2pdma.c +++ b/drivers/pci/p2pdma.c @@ -673,7 +673,7 @@ struct pci_dev *pci_p2pmem_find_many(struct device **clients, int num_clients) } if (dev_cnt) - pdev = pci_dev_get(closest_pdevs[prandom_u32_max(dev_cnt)]); + pdev = pci_dev_get(closest_pdevs[get_random_u32_below(dev_cnt)]); for (i = 0; i < dev_cnt; i++) pci_dev_put(closest_pdevs[i]); diff --git a/drivers/s390/scsi/zfcp_fc.c b/drivers/s390/scsi/zfcp_fc.c index 77917b339870..f21307537829 100644 --- a/drivers/s390/scsi/zfcp_fc.c +++ b/drivers/s390/scsi/zfcp_fc.c @@ -48,7 +48,7 @@ unsigned int zfcp_fc_port_scan_backoff(void) { if (!port_scan_backoff) return 0; - return prandom_u32_max(port_scan_backoff); + return get_random_u32_below(port_scan_backoff); } static void zfcp_fc_port_scan_time(struct zfcp_adapter *adapter) diff --git a/drivers/scsi/fcoe/fcoe_ctlr.c b/drivers/scsi/fcoe/fcoe_ctlr.c index ddc048069af2..5c8d1ba3f8f3 100644 --- a/drivers/scsi/fcoe/fcoe_ctlr.c +++ b/drivers/scsi/fcoe/fcoe_ctlr.c @@ -2233,7 +2233,7 @@ static void fcoe_ctlr_vn_restart(struct fcoe_ctlr *fip) if (fip->probe_tries < FIP_VN_RLIM_COUNT) { fip->probe_tries++; - wait = prandom_u32_max(FIP_VN_PROBE_WAIT); + wait = get_random_u32_below(FIP_VN_PROBE_WAIT); } else wait = FIP_VN_RLIM_INT; mod_timer(&fip->timer, jiffies + msecs_to_jiffies(wait)); @@ -3125,7 +3125,7 @@ static void fcoe_ctlr_vn_timeout(struct fcoe_ctlr *fip) fcoe_all_vn2vn, 0); fip->port_ka_time = jiffies + msecs_to_jiffies(FIP_VN_BEACON_INT + - prandom_u32_max(FIP_VN_BEACON_FUZZ)); + get_random_u32_below(FIP_VN_BEACON_FUZZ)); } if (time_before(fip->port_ka_time, next_time)) next_time = fip->port_ka_time; diff --git a/drivers/scsi/qedi/qedi_main.c b/drivers/scsi/qedi/qedi_main.c index df2fe7bd26d1..f2ee49756df8 100644 --- a/drivers/scsi/qedi/qedi_main.c +++ b/drivers/scsi/qedi/qedi_main.c @@ -618,7 +618,7 @@ static int qedi_cm_alloc_mem(struct qedi_ctx *qedi) sizeof(struct qedi_endpoint *)), GFP_KERNEL); if (!qedi->ep_tbl) return -ENOMEM; - port_id = prandom_u32_max(QEDI_LOCAL_PORT_RANGE); + port_id = get_random_u32_below(QEDI_LOCAL_PORT_RANGE); if (qedi_init_id_tbl(&qedi->lcl_port_tbl, QEDI_LOCAL_PORT_RANGE, QEDI_LOCAL_PORT_MIN, port_id)) { qedi_cm_free_mem(qedi); diff --git a/drivers/scsi/scsi_debug.c b/drivers/scsi/scsi_debug.c index 629853662b82..a86db9761d00 100644 --- a/drivers/scsi/scsi_debug.c +++ b/drivers/scsi/scsi_debug.c @@ -5702,16 +5702,16 @@ static int schedule_resp(struct scsi_cmnd *cmnd, struct sdebug_dev_info *devip, u64 ns = jiffies_to_nsecs(delta_jiff); if (sdebug_random && ns < U32_MAX) { - ns = prandom_u32_max((u32)ns); + ns = get_random_u32_below((u32)ns); } else if (sdebug_random) { ns >>= 12; /* scale to 4 usec precision */ if (ns < U32_MAX) /* over 4 hours max */ - ns = prandom_u32_max((u32)ns); + ns = get_random_u32_below((u32)ns); ns <<= 12; } kt = ns_to_ktime(ns); } else { /* ndelay has a 4.2 second max */ - kt = sdebug_random ? prandom_u32_max((u32)ndelay) : + kt = sdebug_random ? get_random_u32_below((u32)ndelay) : (u32)ndelay; if (ndelay < INCLUSIVE_TIMING_MAX_NS) { u64 d = ktime_get_boottime_ns() - ns_from_boot; -- cgit From e8a533cbeb79809206f8724e89961e0079508c3c Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sun, 9 Oct 2022 20:44:02 -0600 Subject: treewide: use get_random_u32_inclusive() when possible These cases were done with this Coccinelle: @@ expression H; expression L; @@ - (get_random_u32_below(H) + L) + get_random_u32_inclusive(L, H + L - 1) @@ expression H; expression L; expression E; @@ get_random_u32_inclusive(L, H - + E - - E ) @@ expression H; expression L; expression E; @@ get_random_u32_inclusive(L, H - - E - + E ) @@ expression H; expression L; expression E; expression F; @@ get_random_u32_inclusive(L, H - - E + F - + E ) @@ expression H; expression L; expression E; expression F; @@ get_random_u32_inclusive(L, H - + E + F - - E ) And then subsequently cleaned up by hand, with several automatic cases rejected if it didn't make sense contextually. Reviewed-by: Kees Cook Reviewed-by: Greg Kroah-Hartman Reviewed-by: Jason Gunthorpe # for infiniband Signed-off-by: Jason A. Donenfeld --- drivers/bus/mhi/host/internal.h | 2 +- drivers/dma-buf/st-dma-fence-chain.c | 2 +- drivers/infiniband/core/cma.c | 2 +- drivers/infiniband/hw/hns/hns_roce_ah.c | 5 ++--- drivers/mtd/nand/raw/nandsim.c | 2 +- drivers/net/wireguard/selftest/allowedips.c | 8 ++++---- drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c | 2 +- drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c | 2 +- 8 files changed, 12 insertions(+), 13 deletions(-) (limited to 'drivers') diff --git a/drivers/bus/mhi/host/internal.h b/drivers/bus/mhi/host/internal.h index c73621aabbd1..2e139e76de4c 100644 --- a/drivers/bus/mhi/host/internal.h +++ b/drivers/bus/mhi/host/internal.h @@ -129,7 +129,7 @@ enum mhi_pm_state { #define PRIMARY_CMD_RING 0 #define MHI_DEV_WAKE_DB 127 #define MHI_MAX_MTU 0xffff -#define MHI_RANDOM_U32_NONZERO(bmsk) (get_random_u32_below(bmsk) + 1) +#define MHI_RANDOM_U32_NONZERO(bmsk) (get_random_u32_inclusive(1, bmsk)) enum mhi_er_type { MHI_ER_TYPE_INVALID = 0x0, diff --git a/drivers/dma-buf/st-dma-fence-chain.c b/drivers/dma-buf/st-dma-fence-chain.c index 9fbad7317d9b..c0979c8049b5 100644 --- a/drivers/dma-buf/st-dma-fence-chain.c +++ b/drivers/dma-buf/st-dma-fence-chain.c @@ -400,7 +400,7 @@ static int __find_race(void *arg) struct dma_fence *fence = dma_fence_get(data->fc.tail); int seqno; - seqno = get_random_u32_below(data->fc.chain_length) + 1; + seqno = get_random_u32_inclusive(1, data->fc.chain_length); err = dma_fence_chain_find_seqno(&fence, seqno); if (err) { diff --git a/drivers/infiniband/core/cma.c b/drivers/infiniband/core/cma.c index dd1c703b10df..aacd6254df77 100644 --- a/drivers/infiniband/core/cma.c +++ b/drivers/infiniband/core/cma.c @@ -3807,7 +3807,7 @@ static int cma_alloc_any_port(enum rdma_ucm_port_space ps, inet_get_local_port_range(net, &low, &high); remaining = (high - low) + 1; - rover = get_random_u32_below(remaining) + low; + rover = get_random_u32_inclusive(low, remaining + low - 1); retry: if (last_used_port != rover) { struct rdma_bind_list *bind_list; diff --git a/drivers/infiniband/hw/hns/hns_roce_ah.c b/drivers/infiniband/hw/hns/hns_roce_ah.c index b37d2a81584d..e77fcc74f15c 100644 --- a/drivers/infiniband/hw/hns/hns_roce_ah.c +++ b/drivers/infiniband/hw/hns/hns_roce_ah.c @@ -41,9 +41,8 @@ static inline u16 get_ah_udp_sport(const struct rdma_ah_attr *ah_attr) u16 sport; if (!fl) - sport = get_random_u32_below(IB_ROCE_UDP_ENCAP_VALID_PORT_MAX + - 1 - IB_ROCE_UDP_ENCAP_VALID_PORT_MIN) + - IB_ROCE_UDP_ENCAP_VALID_PORT_MIN; + sport = get_random_u32_inclusive(IB_ROCE_UDP_ENCAP_VALID_PORT_MIN, + IB_ROCE_UDP_ENCAP_VALID_PORT_MAX); else sport = rdma_flow_label_to_udp_sport(fl); diff --git a/drivers/mtd/nand/raw/nandsim.c b/drivers/mtd/nand/raw/nandsim.c index 274a31b93100..c21abf748948 100644 --- a/drivers/mtd/nand/raw/nandsim.c +++ b/drivers/mtd/nand/raw/nandsim.c @@ -1405,7 +1405,7 @@ static void ns_do_bit_flips(struct nandsim *ns, int num) if (bitflips && get_random_u16() < (1 << 6)) { int flips = 1; if (bitflips > 1) - flips = get_random_u32_below(bitflips) + 1; + flips = get_random_u32_inclusive(1, bitflips); while (flips--) { int pos = get_random_u32_below(num * 8); ns->buf.byte[pos / 8] ^= (1 << (pos % 8)); diff --git a/drivers/net/wireguard/selftest/allowedips.c b/drivers/net/wireguard/selftest/allowedips.c index 78a916f30c82..78ebe2892a78 100644 --- a/drivers/net/wireguard/selftest/allowedips.c +++ b/drivers/net/wireguard/selftest/allowedips.c @@ -285,7 +285,7 @@ static __init bool randomized_test(void) for (i = 0; i < NUM_RAND_ROUTES; ++i) { get_random_bytes(ip, 4); - cidr = get_random_u32_below(32) + 1; + cidr = get_random_u32_inclusive(1, 32); peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v4(&t, (struct in_addr *)ip, cidr, peer, &mutex) < 0) { @@ -311,7 +311,7 @@ static __init bool randomized_test(void) mutated[k] = (mutated[k] & mutate_mask[k]) | (~mutate_mask[k] & get_random_u8()); - cidr = get_random_u32_below(32) + 1; + cidr = get_random_u32_inclusive(1, 32); peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v4(&t, (struct in_addr *)mutated, @@ -329,7 +329,7 @@ static __init bool randomized_test(void) for (i = 0; i < NUM_RAND_ROUTES; ++i) { get_random_bytes(ip, 16); - cidr = get_random_u32_below(128) + 1; + cidr = get_random_u32_inclusive(1, 128); peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v6(&t, (struct in6_addr *)ip, cidr, peer, &mutex) < 0) { @@ -355,7 +355,7 @@ static __init bool randomized_test(void) mutated[k] = (mutated[k] & mutate_mask[k]) | (~mutate_mask[k] & get_random_u8()); - cidr = get_random_u32_below(128) + 1; + cidr = get_random_u32_inclusive(1, 128); peer = peers[get_random_u32_below(NUM_PEERS)]; if (wg_allowedips_insert_v6(&t, (struct in6_addr *)mutated, diff --git a/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c b/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c index 23c971b77965..c704ca752138 100644 --- a/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c +++ b/drivers/net/wireless/broadcom/brcm80211/brcmfmac/p2p.c @@ -1128,7 +1128,7 @@ static void brcmf_p2p_afx_handler(struct work_struct *work) if (afx_hdl->is_listen && afx_hdl->my_listen_chan) /* 100ms ~ 300ms */ err = brcmf_p2p_discover_listen(p2p, afx_hdl->my_listen_chan, - 100 * (1 + get_random_u32_below(3))); + 100 * get_random_u32_inclusive(1, 3)); else err = brcmf_p2p_act_frm_search(p2p, afx_hdl->peer_listen_chan); diff --git a/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c b/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c index 1696fbf1009a..3a7a44bb3c60 100644 --- a/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c +++ b/drivers/net/wireless/intel/iwlwifi/mvm/mac-ctxt.c @@ -1099,7 +1099,7 @@ static void iwl_mvm_mac_ctxt_cmd_fill_ap(struct iwl_mvm *mvm, iwl_mvm_mac_ap_iterator, &data); if (data.beacon_device_ts) { - u32 rand = get_random_u32_below(64 - 36) + 36; + u32 rand = get_random_u32_inclusive(36, 63); mvmvif->ap_beacon_time = data.beacon_device_ts + ieee80211_tu_to_usec(data.beacon_int * rand / 100); -- cgit From b9b01a5625b5a9e9d96d14d4a813a54e8a124f4b Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Tue, 1 Nov 2022 13:03:55 +0100 Subject: random: use random.trust_{bootloader,cpu} command line option only It's very unusual to have both a command line option and a compile time option, and apparently that's confusing to people. Also, basically everybody enables the compile time option now, which means people who want to disable this wind up having to use the command line option to ensure that anyway. So just reduce the number of moving pieces and nix the compile time option in favor of the more versatile command line option. Signed-off-by: Jason A. Donenfeld --- drivers/char/Kconfig | 36 ------------------------------------ drivers/char/random.c | 10 +++++----- 2 files changed, 5 insertions(+), 41 deletions(-) (limited to 'drivers') diff --git a/drivers/char/Kconfig b/drivers/char/Kconfig index 0f378d29dab0..30fe9848dac1 100644 --- a/drivers/char/Kconfig +++ b/drivers/char/Kconfig @@ -423,40 +423,4 @@ config ADI and SSM (Silicon Secured Memory). Intended consumers of this driver include crash and makedumpfile. -config RANDOM_TRUST_CPU - bool "Initialize RNG using CPU RNG instructions" - default y - help - Initialize the RNG using random numbers supplied by the CPU's - RNG instructions (e.g. RDRAND), if supported and available. These - random numbers are never used directly, but are rather hashed into - the main input pool, and this happens regardless of whether or not - this option is enabled. Instead, this option controls whether the - they are credited and hence can initialize the RNG. Additionally, - other sources of randomness are always used, regardless of this - setting. Enabling this implies trusting that the CPU can supply high - quality and non-backdoored random numbers. - - Say Y here unless you have reason to mistrust your CPU or believe - its RNG facilities may be faulty. This may also be configured at - boot time with "random.trust_cpu=on/off". - -config RANDOM_TRUST_BOOTLOADER - bool "Initialize RNG using bootloader-supplied seed" - default y - help - Initialize the RNG using a seed supplied by the bootloader or boot - environment (e.g. EFI or a bootloader-generated device tree). This - seed is not used directly, but is rather hashed into the main input - pool, and this happens regardless of whether or not this option is - enabled. Instead, this option controls whether the seed is credited - and hence can initialize the RNG. Additionally, other sources of - randomness are always used, regardless of this setting. Enabling - this implies trusting that the bootloader can supply high quality and - non-backdoored seeds. - - Say Y here unless you have reason to mistrust your bootloader or - believe its RNG facilities may be faulty. This may also be configured - at boot time with "random.trust_bootloader=on/off". - endmenu diff --git a/drivers/char/random.c b/drivers/char/random.c index f5868dddbb61..1c6fb89fc005 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -748,7 +748,7 @@ static void __cold _credit_init_bits(size_t bits) * * add_bootloader_randomness() is called by bootloader drivers, such as EFI * and device tree, and credits its input depending on whether or not the - * configuration option CONFIG_RANDOM_TRUST_BOOTLOADER is set. + * command line option 'random.trust_bootloader'. * * add_vmfork_randomness() adds a unique (but not necessarily secret) ID * representing the current instance of a VM to the pool, without crediting, @@ -774,8 +774,8 @@ static void __cold _credit_init_bits(size_t bits) * **********************************************************************/ -static bool trust_cpu __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_CPU); -static bool trust_bootloader __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_BOOTLOADER); +static bool trust_cpu __initdata = true; +static bool trust_bootloader __initdata = true; static int __init parse_trust_cpu(char *arg) { return kstrtobool(arg, &trust_cpu); @@ -926,8 +926,8 @@ void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy) EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); /* - * Handle random seed passed by bootloader, and credit it if - * CONFIG_RANDOM_TRUST_BOOTLOADER is set. + * Handle random seed passed by bootloader, and credit it depending + * on the command line option 'random.trust_bootloader'. */ void __init add_bootloader_randomness(const void *buf, size_t len) { -- cgit From 2c03e16f44993d45f064580adb0eb408b513ad72 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sat, 29 Oct 2022 01:18:04 +0200 Subject: random: remove early archrandom abstraction The arch_get_random*_early() abstraction is not completely useful and adds complexity, because it's not a given that there will be no calls to arch_get_random*() between random_init_early(), which uses arch_get_random*_early(), and init_cpu_features(). During that gap, crng_reseed() might be called, which uses arch_get_random*(), since it's mostly not init code. Instead we can test whether we're in the early phase in arch_get_random*() itself, and in doing so avoid all ambiguity about where we are. Fortunately, the only architecture that currently implements arch_get_random*_early() also has an alternatives-based cpu feature system, one flag of which determines whether the other flags have been initialized. This makes it possible to do the early check with zero cost once the system is initialized. Reviewed-by: Catalin Marinas Cc: Will Deacon Cc: Ard Biesheuvel Cc: Jean-Philippe Brucker Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 1c6fb89fc005..49dee3dcc3c4 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -829,13 +829,13 @@ void __init random_init_early(const char *command_line) #endif for (i = 0, arch_bits = sizeof(entropy) * 8; i < ARRAY_SIZE(entropy);) { - longs = arch_get_random_seed_longs_early(entropy, ARRAY_SIZE(entropy) - i); + longs = arch_get_random_seed_longs(entropy, ARRAY_SIZE(entropy) - i); if (longs) { _mix_pool_bytes(entropy, sizeof(*entropy) * longs); i += longs; continue; } - longs = arch_get_random_longs_early(entropy, ARRAY_SIZE(entropy) - i); + longs = arch_get_random_longs(entropy, ARRAY_SIZE(entropy) - i); if (longs) { _mix_pool_bytes(entropy, sizeof(*entropy) * longs); i += longs; -- cgit From b240bab51888d5c8e389dc179d7c67a869587148 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Tue, 1 Nov 2022 20:08:32 +0100 Subject: random: adjust comment to account for removed function Since de492c83cae0 ("prandom: remove unused functions"), get_random_int() no longer exists, so remove its reference from this comment. Fixes: de492c83cae0 ("prandom: remove unused functions") Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 49dee3dcc3c4..e5e66e8fc118 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -120,7 +120,7 @@ static void try_to_generate_entropy(void); * Wait for the input pool to be seeded and thus guaranteed to supply * cryptographically secure random numbers. This applies to: the /dev/urandom * device, the get_random_bytes function, and the get_random_{u8,u16,u32,u64, - * int,long} family of functions. Using any of these functions without first + * long} family of functions. Using any of these functions without first * calling this function forfeits the guarantee of security. * * Returns: 0 if the input pool has been seeded. -- cgit From 19258d05b619d26622bdcfa11eca1f457b69e4da Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Fri, 4 Nov 2022 12:47:43 +0100 Subject: random: modernize documentation comment on get_random_bytes() The prior text was very old and made outdated references to TCP sequence numbers, which should use one of the integer functions instead, since batched entropy was introduced. The current way of describing the quality of functions is just to say that it's as good as /dev/urandom, which now all the functions are. Fixes: f5b98461cb81 ("random: use chacha20 for get_random_int/long") Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index e5e66e8fc118..a8476154d47e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -386,11 +386,11 @@ static void _get_random_bytes(void *buf, size_t len) } /* - * This function is the exported kernel interface. It returns some number of - * good random numbers, suitable for key generation, seeding TCP sequence - * numbers, etc. In order to ensure that the randomness returned by this - * function is okay, the function wait_for_random_bytes() should be called and - * return 0 at least once at any point prior. + * This returns random bytes in arbitrary quantities. The quality of the + * random bytes is good as /dev/urandom. In order to ensure that the + * randomness provided by this function is okay, the function + * wait_for_random_bytes() should be called and return 0 at least once + * at any point prior. */ void get_random_bytes(void *buf, size_t len) { -- cgit From db516da95ce458f0cab5e7ae2db93fd821484d7d Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sun, 6 Nov 2022 16:02:43 +0100 Subject: hw_random: use add_hwgenerator_randomness() for early entropy Rather than calling add_device_randomness(), the add_early_randomness() function should use add_hwgenerator_randomness(), so that the early entropy can be potentially credited, which allows for the RNG to initialize earlier without having to wait for the kthread to come up. This requires some minor API refactoring, by adding a `sleep_after` parameter to add_hwgenerator_randomness(), so that we don't hit a blocking sleep from add_early_randomness(). Tested-by: AngeloGioacchino Del Regno Tested-by: Marek Szyprowski Reviewed-by: AngeloGioacchino Del Regno Reviewed-by: Dominik Brodowski Acked-by: Herbert Xu Signed-off-by: Jason A. Donenfeld --- drivers/char/hw_random/core.c | 8 +++++--- drivers/char/random.c | 12 ++++++------ 2 files changed, 11 insertions(+), 9 deletions(-) (limited to 'drivers') diff --git a/drivers/char/hw_random/core.c b/drivers/char/hw_random/core.c index cc002b0c2f0c..63a0a8e4505d 100644 --- a/drivers/char/hw_random/core.c +++ b/drivers/char/hw_random/core.c @@ -69,8 +69,10 @@ static void add_early_randomness(struct hwrng *rng) mutex_lock(&reading_mutex); bytes_read = rng_get_data(rng, rng_fillbuf, 32, 0); mutex_unlock(&reading_mutex); - if (bytes_read > 0) - add_device_randomness(rng_fillbuf, bytes_read); + if (bytes_read > 0) { + size_t entropy = bytes_read * 8 * rng->quality / 1024; + add_hwgenerator_randomness(rng_fillbuf, bytes_read, entropy, false); + } } static inline void cleanup_rng(struct kref *kref) @@ -528,7 +530,7 @@ static int hwrng_fillfn(void *unused) /* Outside lock, sure, but y'know: randomness. */ add_hwgenerator_randomness((void *)rng_fillbuf, rc, - entropy >> 10); + entropy >> 10, true); } hwrng_fill = NULL; return 0; diff --git a/drivers/char/random.c b/drivers/char/random.c index a8476154d47e..94990b052f58 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -727,7 +727,7 @@ static void __cold _credit_init_bits(size_t bits) * the above entropy accumulation routines: * * void add_device_randomness(const void *buf, size_t len); - * void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy); + * void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy, bool sleep_after); * void add_bootloader_randomness(const void *buf, size_t len); * void add_vmfork_randomness(const void *unique_vm_id, size_t len); * void add_interrupt_randomness(int irq); @@ -907,11 +907,11 @@ void add_device_randomness(const void *buf, size_t len) EXPORT_SYMBOL(add_device_randomness); /* - * Interface for in-kernel drivers of true hardware RNGs. - * Those devices may produce endless random bits and will be throttled - * when our pool is full. + * Interface for in-kernel drivers of true hardware RNGs. Those devices + * may produce endless random bits, so this function will sleep for + * some amount of time after, if the sleep_after parameter is true. */ -void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy) +void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy, bool sleep_after) { mix_pool_bytes(buf, len); credit_init_bits(entropy); @@ -920,7 +920,7 @@ void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy) * Throttle writing to once every reseed interval, unless we're not yet * initialized or no entropy is credited. */ - if (!kthread_should_stop() && (crng_ready() || !entropy)) + if (sleep_after && !kthread_should_stop() && (crng_ready() || !entropy)) schedule_timeout_interruptible(crng_reseed_interval()); } EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); -- cgit From 9148de3196edcba4045cfe717c8e6819fa5adeaf Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Thu, 17 Nov 2022 17:47:12 +0100 Subject: random: reseed in delayed work rather than on-demand Currently, we reseed when random bytes are requested, if the current seed is too old. Since random bytes can be requested from all contexts, including hard IRQ, this means sometimes we wind up adding a bit of latency to hard IRQ. This was so much of a problem on s390x that now s390x just doesn't provide its architectural RNG from hard IRQ context, so we miss out in that case. Instead, let's just schedule a persistent delayed work, so that the reseeding and potentially expensive operations will always happen from process context, reducing unexpected latencies from hard IRQ. This also has the nice effect of accumulating a transcript of random inputs over time, since it means that we amass more input values. And it should make future vDSO integration a bit easier. Cc: Harald Freudenberger Cc: Juergen Christ Cc: Alexander Gordeev Cc: Dominik Brodowski Cc: Sebastian Andrzej Siewior Cc: Tejun Heo Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 68 ++++++++++++++++++++++++--------------------------- 1 file changed, 32 insertions(+), 36 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 94990b052f58..65ee69896967 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -182,7 +182,6 @@ enum { static struct { u8 key[CHACHA_KEY_SIZE] __aligned(__alignof__(long)); - unsigned long birth; unsigned long generation; spinlock_t lock; } base_crng = { @@ -200,16 +199,41 @@ static DEFINE_PER_CPU(struct crng, crngs) = { .lock = INIT_LOCAL_LOCK(crngs.lock), }; +/* + * Return the interval until the next reseeding, which is normally + * CRNG_RESEED_INTERVAL, but during early boot, it is at an interval + * proportional to the uptime. + */ +static unsigned int crng_reseed_interval(void) +{ + static bool early_boot = true; + + if (unlikely(READ_ONCE(early_boot))) { + time64_t uptime = ktime_get_seconds(); + if (uptime >= CRNG_RESEED_INTERVAL / HZ * 2) + WRITE_ONCE(early_boot, false); + else + return max_t(unsigned int, CRNG_RESEED_START_INTERVAL, + (unsigned int)uptime / 2 * HZ); + } + return CRNG_RESEED_INTERVAL; +} + /* Used by crng_reseed() and crng_make_state() to extract a new seed from the input pool. */ static void extract_entropy(void *buf, size_t len); /* This extracts a new crng key from the input pool. */ -static void crng_reseed(void) +static void crng_reseed(struct work_struct *work) { + static DECLARE_DELAYED_WORK(next_reseed, crng_reseed); unsigned long flags; unsigned long next_gen; u8 key[CHACHA_KEY_SIZE]; + /* Immediately schedule the next reseeding, so that it fires sooner rather than later. */ + if (likely(system_unbound_wq)) + queue_delayed_work(system_unbound_wq, &next_reseed, crng_reseed_interval()); + extract_entropy(key, sizeof(key)); /* @@ -224,7 +248,6 @@ static void crng_reseed(void) if (next_gen == ULONG_MAX) ++next_gen; WRITE_ONCE(base_crng.generation, next_gen); - WRITE_ONCE(base_crng.birth, jiffies); if (!static_branch_likely(&crng_is_ready)) crng_init = CRNG_READY; spin_unlock_irqrestore(&base_crng.lock, flags); @@ -263,26 +286,6 @@ static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE], memzero_explicit(first_block, sizeof(first_block)); } -/* - * Return the interval until the next reseeding, which is normally - * CRNG_RESEED_INTERVAL, but during early boot, it is at an interval - * proportional to the uptime. - */ -static unsigned int crng_reseed_interval(void) -{ - static bool early_boot = true; - - if (unlikely(READ_ONCE(early_boot))) { - time64_t uptime = ktime_get_seconds(); - if (uptime >= CRNG_RESEED_INTERVAL / HZ * 2) - WRITE_ONCE(early_boot, false); - else - return max_t(unsigned int, CRNG_RESEED_START_INTERVAL, - (unsigned int)uptime / 2 * HZ); - } - return CRNG_RESEED_INTERVAL; -} - /* * This function returns a ChaCha state that you may use for generating * random data. It also returns up to 32 bytes on its own of random data @@ -318,13 +321,6 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS], return; } - /* - * If the base_crng is old enough, we reseed, which in turn bumps the - * generation counter that we check below. - */ - if (unlikely(time_is_before_jiffies(READ_ONCE(base_crng.birth) + crng_reseed_interval()))) - crng_reseed(); - local_lock_irqsave(&crngs.lock, flags); crng = raw_cpu_ptr(&crngs); @@ -698,7 +694,7 @@ static void __cold _credit_init_bits(size_t bits) } while (!try_cmpxchg(&input_pool.init_bits, &orig, new)); if (orig < POOL_READY_BITS && new >= POOL_READY_BITS) { - crng_reseed(); /* Sets crng_init to CRNG_READY under base_crng.lock. */ + crng_reseed(NULL); /* Sets crng_init to CRNG_READY under base_crng.lock. */ if (static_key_initialized) execute_in_process_context(crng_set_ready, &set_ready); wake_up_interruptible(&crng_init_wait); @@ -806,7 +802,7 @@ static int random_pm_notification(struct notifier_block *nb, unsigned long actio if (crng_ready() && (action == PM_RESTORE_PREPARE || (action == PM_POST_SUSPEND && !IS_ENABLED(CONFIG_PM_AUTOSLEEP) && !IS_ENABLED(CONFIG_PM_USERSPACE_AUTOSLEEP)))) { - crng_reseed(); + crng_reseed(NULL); pr_notice("crng reseeded on system resumption\n"); } return 0; @@ -850,7 +846,7 @@ void __init random_init_early(const char *command_line) /* Reseed if already seeded by earlier phases. */ if (crng_ready()) - crng_reseed(); + crng_reseed(NULL); else if (trust_cpu) _credit_init_bits(arch_bits); } @@ -878,7 +874,7 @@ void __init random_init(void) /* Reseed if already seeded by earlier phases. */ if (crng_ready()) - crng_reseed(); + crng_reseed(NULL); WARN_ON(register_pm_notifier(&pm_notifier)); @@ -948,7 +944,7 @@ void __cold add_vmfork_randomness(const void *unique_vm_id, size_t len) { add_device_randomness(unique_vm_id, len); if (crng_ready()) { - crng_reseed(); + crng_reseed(NULL); pr_notice("crng reseeded due to virtual machine fork\n"); } blocking_notifier_call_chain(&vmfork_chain, 0, NULL); @@ -1470,7 +1466,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) return -EPERM; if (!crng_ready()) return -ENODATA; - crng_reseed(); + crng_reseed(NULL); return 0; default: return -EINVAL; -- cgit From bbc7e1bed1f5297581325e739f0e47f650a386fa Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 16 Nov 2022 17:16:37 +0100 Subject: random: add back async readiness notifier This is required by vsprint, because it can't do things synchronously from hardirq context, and it will be useful for an EFI notifier as well. I didn't initially want to do this, but with two potential consumers now, it seems worth it. Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 65ee69896967..a2a18bd3d7d7 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -84,6 +84,7 @@ static DEFINE_STATIC_KEY_FALSE(crng_is_ready); /* Various types of waiters for crng_init->CRNG_READY transition. */ static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait); static struct fasync_struct *fasync; +static ATOMIC_NOTIFIER_HEAD(random_ready_notifier); /* Control how we warn userspace. */ static struct ratelimit_state urandom_warning = @@ -140,6 +141,26 @@ int wait_for_random_bytes(void) } EXPORT_SYMBOL(wait_for_random_bytes); +/* + * Add a callback function that will be invoked when the crng is initialised, + * or immediately if it already has been. Only use this is you are absolutely + * sure it is required. Most users should instead be able to test + * `rng_is_initialized()` on demand, or make use of `get_random_bytes_wait()`. + */ +int __cold execute_with_initialized_rng(struct notifier_block *nb) +{ + unsigned long flags; + int ret = 0; + + spin_lock_irqsave(&random_ready_notifier.lock, flags); + if (crng_ready()) + nb->notifier_call(nb, 0, NULL); + else + ret = raw_notifier_chain_register((struct raw_notifier_head *)&random_ready_notifier.head, nb); + spin_unlock_irqrestore(&random_ready_notifier.lock, flags); + return ret; +} + #define warn_unseeded_randomness() \ if (IS_ENABLED(CONFIG_WARN_ALL_UNSEEDED_RANDOM) && !crng_ready()) \ printk_deferred(KERN_NOTICE "random: %s called from %pS with crng_init=%d\n", \ @@ -697,6 +718,7 @@ static void __cold _credit_init_bits(size_t bits) crng_reseed(NULL); /* Sets crng_init to CRNG_READY under base_crng.lock. */ if (static_key_initialized) execute_in_process_context(crng_set_ready, &set_ready); + atomic_notifier_call_chain(&random_ready_notifier, 0, NULL); wake_up_interruptible(&crng_init_wait); kill_fasync(&fasync, SIGIO, POLL_IN); pr_notice("crng init done\n"); -- cgit From e7b813b32a42a3a6281a4fd9ae7700a0257c1d50 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 16 Nov 2022 17:16:42 +0100 Subject: efi: random: refresh non-volatile random seed when RNG is initialized EFI has a rather unique benefit that it has access to some limited non-volatile storage, where the kernel can store a random seed. Register a notification for when the RNG is initialized, and at that point, store a new random seed. Reviewed-by: Ard Biesheuvel Signed-off-by: Jason A. Donenfeld --- drivers/firmware/efi/efi.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'drivers') diff --git a/drivers/firmware/efi/efi.c b/drivers/firmware/efi/efi.c index a46df5d1d094..16dae588f0e3 100644 --- a/drivers/firmware/efi/efi.c +++ b/drivers/firmware/efi/efi.c @@ -337,6 +337,24 @@ static void __init efi_debugfs_init(void) static inline void efi_debugfs_init(void) {} #endif +static void refresh_nv_rng_seed(struct work_struct *work) +{ + u8 seed[EFI_RANDOM_SEED_SIZE]; + + get_random_bytes(seed, sizeof(seed)); + efi.set_variable(L"RandomSeed", &LINUX_EFI_RANDOM_SEED_TABLE_GUID, + EFI_VARIABLE_NON_VOLATILE | EFI_VARIABLE_BOOTSERVICE_ACCESS | + EFI_VARIABLE_RUNTIME_ACCESS, sizeof(seed), seed); + memzero_explicit(seed, sizeof(seed)); +} +static int refresh_nv_rng_seed_notification(struct notifier_block *nb, unsigned long action, void *data) +{ + static DECLARE_WORK(work, refresh_nv_rng_seed); + schedule_work(&work); + return NOTIFY_DONE; +} +static struct notifier_block refresh_nv_rng_seed_nb = { .notifier_call = refresh_nv_rng_seed_notification }; + /* * We register the efi subsystem with the firmware subsystem and the * efivars subsystem with the efi subsystem, if the system was booted with @@ -413,6 +431,7 @@ static int __init efisubsys_init(void) platform_device_register_simple("efi_secret", 0, NULL, 0); #endif + execute_with_initialized_rng(&refresh_nv_rng_seed_nb); return 0; err_remove_group: -- cgit From 0e42d14be23f4cdb68a06ea40106eccf7db0b4bc Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Tue, 29 Nov 2022 01:55:11 +0100 Subject: random: remove extraneous period and add a missing one in comments Just some trivial typo fixes, and reflowing of lines. Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index a2a18bd3d7d7..7b71cea6a6ab 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1236,15 +1236,13 @@ struct entropy_timer_state { }; /* - * Each time the timer fires, we expect that we got an unpredictable - * jump in the cycle counter. Even if the timer is running on another - * CPU, the timer activity will be touching the stack of the CPU that is - * generating entropy.. + * Each time the timer fires, we expect that we got an unpredictable jump in + * the cycle counter. Even if the timer is running on another CPU, the timer + * activity will be touching the stack of the CPU that is generating entropy. * - * Note that we don't re-arm the timer in the timer itself - we are - * happy to be scheduled away, since that just makes the load more - * complex, but we do not want the timer to keep ticking unless the - * entropy loop is running. + * Note that we don't re-arm the timer in the timer itself - we are happy to be + * scheduled away, since that just makes the load more complex, but we do not + * want the timer to keep ticking unless the entropy loop is running. * * So the re-arming always happens in the entropy loop itself. */ @@ -1259,8 +1257,8 @@ static void __cold entropy_timer(struct timer_list *timer) } /* - * If we have an actual cycle counter, see if we can - * generate enough entropy with timing noise + * If we have an actual cycle counter, see if we can generate enough entropy + * with timing noise. */ static void __cold try_to_generate_entropy(void) { -- cgit From 1c21fe00eda76e4081535c739cf9f4bbb5dcb0ce Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Sat, 1 Oct 2022 01:10:50 +0200 Subject: random: spread out jitter callback to different CPUs Rather than merely hoping that the callback gets called on another CPU, arrange for that to actually happen, by round robining which CPU the timer fires on. This way, on multiprocessor machines, we exacerbate jitter by touching the same memory from multiple different cores. There's a little bit of tricky bookkeeping involved here, because using timer_setup_on_stack() + add_timer_on() + del_timer_sync() will result in a use after free. See this sample code: . Instead, it's necessary to call [try_to_]del_timer_sync() before calling add_timer_on(), so that the final call to del_timer_sync() at the end of the function actually succeeds at making sure no handlers are running. Cc: Sultan Alsawaf Cc: Dominik Brodowski Cc: Sebastian Andrzej Siewior Cc: Thomas Gleixner Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 52 +++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 44 insertions(+), 8 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 7b71cea6a6ab..3db4bf6f9b43 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -53,6 +53,7 @@ #include #include #include +#include #include #include #include @@ -1232,7 +1233,8 @@ void __cold rand_initialize_disk(struct gendisk *disk) struct entropy_timer_state { unsigned long entropy; struct timer_list timer; - unsigned int samples, samples_per_bit; + atomic_t samples; + unsigned int samples_per_bit; }; /* @@ -1250,10 +1252,8 @@ static void __cold entropy_timer(struct timer_list *timer) { struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer); - if (++state->samples == state->samples_per_bit) { + if (atomic_inc_return(&state->samples) % state->samples_per_bit == 0) credit_init_bits(1); - state->samples = 0; - } } /* @@ -1266,6 +1266,7 @@ static void __cold try_to_generate_entropy(void) struct entropy_timer_state stack; unsigned int i, num_different = 0; unsigned long last = random_get_entropy(); + int cpu = -1; for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) { stack.entropy = random_get_entropy(); @@ -1277,19 +1278,54 @@ static void __cold try_to_generate_entropy(void) if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT) return; - stack.samples = 0; + atomic_set(&stack.samples, 0); timer_setup_on_stack(&stack.timer, entropy_timer, 0); while (!crng_ready() && !signal_pending(current)) { - if (!timer_pending(&stack.timer)) - mod_timer(&stack.timer, jiffies); + /* + * Check !timer_pending() and then ensure that any previous callback has finished + * executing by checking try_to_del_timer_sync(), before queueing the next one. + */ + if (!timer_pending(&stack.timer) && try_to_del_timer_sync(&stack.timer) >= 0) { + struct cpumask timer_cpus; + unsigned int num_cpus; + + /* + * Preemption must be disabled here, both to read the current CPU number + * and to avoid scheduling a timer on a dead CPU. + */ + preempt_disable(); + + /* Only schedule callbacks on timer CPUs that are online. */ + cpumask_and(&timer_cpus, housekeeping_cpumask(HK_TYPE_TIMER), cpu_online_mask); + num_cpus = cpumask_weight(&timer_cpus); + /* In very bizarre case of misconfiguration, fallback to all online. */ + if (unlikely(num_cpus == 0)) { + timer_cpus = *cpu_online_mask; + num_cpus = cpumask_weight(&timer_cpus); + } + + /* Basic CPU round-robin, which avoids the current CPU. */ + do { + cpu = cpumask_next(cpu, &timer_cpus); + if (cpu == nr_cpumask_bits) + cpu = cpumask_first(&timer_cpus); + } while (cpu == smp_processor_id() && num_cpus > 1); + + /* Expiring the timer at `jiffies` means it's the next tick. */ + stack.timer.expires = jiffies; + + add_timer_on(&stack.timer, cpu); + + preempt_enable(); + } mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); schedule(); stack.entropy = random_get_entropy(); } + mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); del_timer_sync(&stack.timer); destroy_timer_on_stack(&stack.timer); - mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); } -- cgit From b83e45fd065c3cfdb8cc0179bbddf296ce4d4fda Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 30 Nov 2022 03:14:15 +0100 Subject: random: mix in cycle counter when jitter timer fires Rather than just relying on interaction between cache lines of the timer and the main loop, also explicitly take into account the fact that the timer might fire at some time that's hard to predict, due to scheduling, interrupts, or cross-CPU conditions. Mix in a cycle counter during the firing of the timer, in addition to the existing one during the scheduling of the timer. It can't hurt and can only help. Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 3db4bf6f9b43..36d29da31af0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1251,7 +1251,9 @@ struct entropy_timer_state { static void __cold entropy_timer(struct timer_list *timer) { struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer); + unsigned long entropy = random_get_entropy(); + mix_pool_bytes(&entropy, sizeof(entropy)); if (atomic_inc_return(&state->samples) % state->samples_per_bit == 0) credit_init_bits(1); } -- cgit From 39ec9e6b141e5a9d7274f40531888f890385a013 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 30 Nov 2022 03:02:05 +0100 Subject: random: align entropy_timer_state to cache line The theory behind the jitter dance is that multiple things are poking at the same cache line. This only works, however, if what's being poked at is actually all in the same cache line. Ensure this is the case by aligning the struct on the stack to the cache line size. We can't use ____cacheline_aligned on a stack variable, because gcc assumes 16 byte alignment when only 8 byte alignment is provided by the kernel, which means gcc could technically do something pathological like `(rsp & ~48) - 64`. It doesn't, but rather than risk it, just do the stack alignment manually with PTR_ALIGN and an oversized buffer. Fixes: 50ee7529ec45 ("random: try to actively add entropy rather than passively wait for it") Cc: Eric Biggers Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 33 +++++++++++++++++---------------- 1 file changed, 17 insertions(+), 16 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index 36d29da31af0..e872acc1238f 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1265,29 +1265,30 @@ static void __cold entropy_timer(struct timer_list *timer) static void __cold try_to_generate_entropy(void) { enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 15 }; - struct entropy_timer_state stack; + u8 stack_bytes[sizeof(struct entropy_timer_state) + SMP_CACHE_BYTES - 1]; + struct entropy_timer_state *stack = PTR_ALIGN((void *)stack_bytes, SMP_CACHE_BYTES); unsigned int i, num_different = 0; unsigned long last = random_get_entropy(); int cpu = -1; for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) { - stack.entropy = random_get_entropy(); - if (stack.entropy != last) + stack->entropy = random_get_entropy(); + if (stack->entropy != last) ++num_different; - last = stack.entropy; + last = stack->entropy; } - stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1); - if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT) + stack->samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1); + if (stack->samples_per_bit > MAX_SAMPLES_PER_BIT) return; - atomic_set(&stack.samples, 0); - timer_setup_on_stack(&stack.timer, entropy_timer, 0); + atomic_set(&stack->samples, 0); + timer_setup_on_stack(&stack->timer, entropy_timer, 0); while (!crng_ready() && !signal_pending(current)) { /* * Check !timer_pending() and then ensure that any previous callback has finished * executing by checking try_to_del_timer_sync(), before queueing the next one. */ - if (!timer_pending(&stack.timer) && try_to_del_timer_sync(&stack.timer) >= 0) { + if (!timer_pending(&stack->timer) && try_to_del_timer_sync(&stack->timer) >= 0) { struct cpumask timer_cpus; unsigned int num_cpus; @@ -1314,20 +1315,20 @@ static void __cold try_to_generate_entropy(void) } while (cpu == smp_processor_id() && num_cpus > 1); /* Expiring the timer at `jiffies` means it's the next tick. */ - stack.timer.expires = jiffies; + stack->timer.expires = jiffies; - add_timer_on(&stack.timer, cpu); + add_timer_on(&stack->timer, cpu); preempt_enable(); } - mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); + mix_pool_bytes(&stack->entropy, sizeof(stack->entropy)); schedule(); - stack.entropy = random_get_entropy(); + stack->entropy = random_get_entropy(); } - mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); + mix_pool_bytes(&stack->entropy, sizeof(stack->entropy)); - del_timer_sync(&stack.timer); - destroy_timer_on_stack(&stack.timer); + del_timer_sync(&stack->timer); + destroy_timer_on_stack(&stack->timer); } -- cgit