1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2019 Ericsson AB 3 */ 4 5 #ifdef __RDSEED__ 6 #include <x86intrin.h> 7 #endif 8 #include <unistd.h> 9 10 #include <rte_bitops.h> 11 #include <rte_branch_prediction.h> 12 #include <rte_cycles.h> 13 #include <rte_lcore.h> 14 #include <rte_lcore_var.h> 15 #include <rte_random.h> 16 17 struct __rte_cache_aligned rte_rand_state { 18 uint64_t z1; 19 uint64_t z2; 20 uint64_t z3; 21 uint64_t z4; 22 uint64_t z5; 23 }; 24 25 RTE_LCORE_VAR_HANDLE(struct rte_rand_state, rand_state); 26 27 /* instance to be shared by all unregistered non-EAL threads */ 28 static struct rte_rand_state unregistered_rand_state; 29 30 static uint32_t 31 __rte_rand_lcg32(uint32_t *seed) 32 { 33 *seed = 1103515245U * *seed + 12345U; 34 35 return *seed; 36 } 37 38 static uint64_t 39 __rte_rand_lcg64(uint32_t *seed) 40 { 41 uint64_t low; 42 uint64_t high; 43 44 /* A 64-bit LCG would have been much cleaner, but good 45 * multiplier/increments for such seem hard to come by. 46 */ 47 48 low = __rte_rand_lcg32(seed); 49 high = __rte_rand_lcg32(seed); 50 51 return low | (high << 32); 52 } 53 54 static uint64_t 55 __rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value) 56 { 57 uint64_t res; 58 59 res = __rte_rand_lcg64(seed); 60 61 if (res < min_value) 62 res += min_value; 63 64 return res; 65 } 66 67 static void 68 __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state) 69 { 70 uint32_t lcg_seed; 71 72 lcg_seed = (uint32_t)(seed ^ (seed >> 32)); 73 74 state->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL); 75 state->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL); 76 state->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL); 77 state->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL); 78 state->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL); 79 } 80 81 void 82 rte_srand(uint64_t seed) 83 { 84 unsigned int lcore_id; 85 86 /* add lcore_id to seed to avoid having the same sequence */ 87 for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++) { 88 struct rte_rand_state *lcore_state = 89 RTE_LCORE_VAR_LCORE(lcore_id, rand_state); 90 91 __rte_srand_lfsr258(seed + lcore_id, lcore_state); 92 } 93 94 __rte_srand_lfsr258(seed + lcore_id, &unregistered_rand_state); 95 } 96 97 static __rte_always_inline uint64_t 98 __rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c, 99 uint64_t d) 100 { 101 return ((z & c) << d) ^ (((z << a) ^ z) >> b); 102 } 103 104 /* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined 105 * LFSR generators. 106 */ 107 108 static __rte_always_inline uint64_t 109 __rte_rand_lfsr258(struct rte_rand_state *state) 110 { 111 state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL, 112 18446744073709551614UL, 10UL); 113 state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL, 114 18446744073709551104UL, 5UL); 115 state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL, 116 18446744073709547520UL, 29UL); 117 state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL, 118 18446744073709420544UL, 23UL); 119 state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL, 120 18446744073701163008UL, 8UL); 121 122 return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5; 123 } 124 125 static __rte_always_inline 126 struct rte_rand_state *__rte_rand_get_state(void) 127 { 128 unsigned int idx; 129 130 idx = rte_lcore_id(); 131 132 if (unlikely(idx == LCORE_ID_ANY)) 133 return &unregistered_rand_state; 134 135 return RTE_LCORE_VAR(rand_state); 136 } 137 138 uint64_t 139 rte_rand(void) 140 { 141 struct rte_rand_state *state; 142 143 state = __rte_rand_get_state(); 144 145 return __rte_rand_lfsr258(state); 146 } 147 148 uint64_t 149 rte_rand_max(uint64_t upper_bound) 150 { 151 struct rte_rand_state *state; 152 uint8_t ones; 153 uint8_t leading_zeros; 154 uint64_t mask = ~((uint64_t)0); 155 uint64_t res; 156 157 if (unlikely(upper_bound < 2)) 158 return 0; 159 160 state = __rte_rand_get_state(); 161 162 ones = rte_popcount64(upper_bound); 163 164 /* Handle power-of-2 upper_bound as a special case, since it 165 * has no bias issues. 166 */ 167 if (unlikely(ones == 1)) 168 return __rte_rand_lfsr258(state) & (upper_bound - 1); 169 170 /* The approach to avoiding bias is to create a mask that 171 * stretches beyond the request value range, and up to the 172 * next power-of-2. In case the masked generated random value 173 * is equal to or greater than the upper bound, just discard 174 * the value and generate a new one. 175 */ 176 177 leading_zeros = rte_clz64(upper_bound); 178 mask >>= leading_zeros; 179 180 do { 181 res = __rte_rand_lfsr258(state) & mask; 182 } while (unlikely(res >= upper_bound)); 183 184 return res; 185 } 186 187 double 188 rte_drand(void) 189 { 190 static const uint64_t denom = (uint64_t)1 << 53; 191 uint64_t rand64 = rte_rand(); 192 193 /* 194 * The double mantissa only has 53 bits, so we uniformly mask off the 195 * high 11 bits and then floating-point divide by 2^53 to achieve a 196 * result in [0, 1). 197 * 198 * We are not allowed to emit 1.0, so denom must be one greater than 199 * the possible range of the preceding step. 200 */ 201 202 rand64 &= denom - 1; 203 return (double)rand64 / denom; 204 } 205 206 static uint64_t 207 __rte_random_initial_seed(void) 208 { 209 #ifdef RTE_LIBEAL_USE_GETENTROPY 210 int ge_rc; 211 uint64_t ge_seed; 212 213 ge_rc = getentropy(&ge_seed, sizeof(ge_seed)); 214 215 if (ge_rc == 0) 216 return ge_seed; 217 #endif 218 #ifdef __RDSEED__ 219 unsigned int rdseed_low; 220 unsigned int rdseed_high; 221 222 /* first fallback: rdseed instruction, if available */ 223 if (_rdseed32_step(&rdseed_low) == 1 && 224 _rdseed32_step(&rdseed_high) == 1) 225 return (uint64_t)rdseed_low | ((uint64_t)rdseed_high << 32); 226 #endif 227 /* second fallback: seed using rdtsc */ 228 return rte_get_tsc_cycles(); 229 } 230 231 RTE_INIT(rte_rand_init) 232 { 233 uint64_t seed; 234 235 RTE_LCORE_VAR_ALLOC(rand_state); 236 237 seed = __rte_random_initial_seed(); 238 239 rte_srand(seed); 240 } 241