1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
use std::cell::Cell;
cfg_rt! {
use std::sync::Mutex;
/// A deterministic generator for seeds (and other generators).
///
/// Given the same initial seed, the generator will output the same sequence of seeds.
///
/// Since the seed generator will be kept in a runtime handle, we need to wrap `FastRand`
/// in a Mutex to make it thread safe. Different to the `FastRand` that we keep in a
/// thread local store, the expectation is that seed generation will not need to happen
/// very frequently, so the cost of the mutex should be minimal.
#[derive(Debug)]
pub(crate) struct RngSeedGenerator {
/// Internal state for the seed generator. We keep it in a Mutex so that we can safely
/// use it across multiple threads.
state: Mutex<FastRand>,
}
impl RngSeedGenerator {
/// Returns a new generator from the provided seed.
pub(crate) fn new(seed: RngSeed) -> Self {
Self {
state: Mutex::new(FastRand::new(seed)),
}
}
/// Returns the next seed in the sequence.
pub(crate) fn next_seed(&self) -> RngSeed {
let rng = self
.state
.lock()
.expect("RNG seed generator is internally corrupt");
let s = rng.fastrand();
let r = rng.fastrand();
RngSeed::from_pair(s, r)
}
/// Directly creates a generator using the next seed.
pub(crate) fn next_generator(&self) -> Self {
RngSeedGenerator::new(self.next_seed())
}
}
}
/// A seed for random number generation.
///
/// In order to make certain functions within a runtime deterministic, a seed
/// can be specified at the time of creation.
#[allow(unreachable_pub)]
#[derive(Clone, Debug)]
pub struct RngSeed {
s: u32,
r: u32,
}
impl RngSeed {
/// Creates a random seed using loom internally.
pub(crate) fn new() -> Self {
Self::from_u64(crate::loom::rand::seed())
}
cfg_unstable! {
/// Generates a seed from the provided byte slice.
///
/// # Example
///
/// ```
/// # use tokio::runtime::RngSeed;
/// let seed = RngSeed::from_bytes(b"make me a seed");
/// ```
#[cfg(feature = "rt")]
pub fn from_bytes(bytes: &[u8]) -> Self {
use std::{collections::hash_map::DefaultHasher, hash::Hasher};
let mut hasher = DefaultHasher::default();
hasher.write(bytes);
Self::from_u64(hasher.finish())
}
}
fn from_u64(seed: u64) -> Self {
let one = (seed >> 32) as u32;
let mut two = seed as u32;
if two == 0 {
// This value cannot be zero
two = 1;
}
Self::from_pair(one, two)
}
fn from_pair(s: u32, r: u32) -> Self {
Self { s, r }
}
}
/// Fast random number generate.
///
/// Implement xorshift64+: 2 32-bit xorshift sequences added together.
/// Shift triplet `[17,7,16]` was calculated as indicated in Marsaglia's
/// Xorshift paper: <https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf>
/// This generator passes the SmallCrush suite, part of TestU01 framework:
/// <http://simul.iro.umontreal.ca/testu01/tu01.html>
#[derive(Debug)]
pub(crate) struct FastRand {
one: Cell<u32>,
two: Cell<u32>,
}
impl FastRand {
/// Initializes a new, thread-local, fast random number generator.
pub(crate) fn new(seed: RngSeed) -> FastRand {
FastRand {
one: Cell::new(seed.s),
two: Cell::new(seed.r),
}
}
/// Replaces the state of the random number generator with the provided seed, returning
/// the seed that represents the previous state of the random number generator.
///
/// The random number generator will become equivalent to one created with
/// the same seed.
#[cfg(feature = "rt")]
pub(crate) fn replace_seed(&self, seed: RngSeed) -> RngSeed {
let old_seed = RngSeed::from_pair(self.one.get(), self.two.get());
self.one.replace(seed.s);
self.two.replace(seed.r);
old_seed
}
#[cfg(any(
feature = "macros",
feature = "rt-multi-thread",
all(feature = "sync", feature = "rt")
))]
pub(crate) fn fastrand_n(&self, n: u32) -> u32 {
// This is similar to fastrand() % n, but faster.
// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
let mul = (self.fastrand() as u64).wrapping_mul(n as u64);
(mul >> 32) as u32
}
fn fastrand(&self) -> u32 {
let mut s1 = self.one.get();
let s0 = self.two.get();
s1 ^= s1 << 17;
s1 = s1 ^ s0 ^ s1 >> 7 ^ s0 >> 16;
self.one.set(s0);
self.two.set(s1);
s0.wrapping_add(s1)
}
}