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_random.h> 15 16 struct rte_rand_state { 17 uint64_t z1; 18 uint64_t z2; 19 uint64_t z3; 20 uint64_t z4; 21 uint64_t z5; 22 } __rte_cache_aligned; 23 24 /* One instance each for every lcore id-equipped thread, and one 25 * additional instance to be shared by all others threads (i.e., all 26 * unregistered non-EAL threads). 27 */ 28 static struct rte_rand_state rand_states[RTE_MAX_LCORE + 1]; 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_DIM(rand_states); lcore_id++) 88 __rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]); 89 } 90 91 static __rte_always_inline uint64_t 92 __rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c, 93 uint64_t d) 94 { 95 return ((z & c) << d) ^ (((z << a) ^ z) >> b); 96 } 97 98 /* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined 99 * LFSR generators. 100 */ 101 102 static __rte_always_inline uint64_t 103 __rte_rand_lfsr258(struct rte_rand_state *state) 104 { 105 state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL, 106 18446744073709551614UL, 10UL); 107 state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL, 108 18446744073709551104UL, 5UL); 109 state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL, 110 18446744073709547520UL, 29UL); 111 state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL, 112 18446744073709420544UL, 23UL); 113 state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL, 114 18446744073701163008UL, 8UL); 115 116 return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5; 117 } 118 119 static __rte_always_inline 120 struct rte_rand_state *__rte_rand_get_state(void) 121 { 122 unsigned int idx; 123 124 idx = rte_lcore_id(); 125 126 /* last instance reserved for unregistered non-EAL threads */ 127 if (unlikely(idx == LCORE_ID_ANY)) 128 idx = RTE_MAX_LCORE; 129 130 return &rand_states[idx]; 131 } 132 133 uint64_t 134 rte_rand(void) 135 { 136 struct rte_rand_state *state; 137 138 state = __rte_rand_get_state(); 139 140 return __rte_rand_lfsr258(state); 141 } 142 143 uint64_t 144 rte_rand_max(uint64_t upper_bound) 145 { 146 struct rte_rand_state *state; 147 uint8_t ones; 148 uint8_t leading_zeros; 149 uint64_t mask = ~((uint64_t)0); 150 uint64_t res; 151 152 if (unlikely(upper_bound < 2)) 153 return 0; 154 155 state = __rte_rand_get_state(); 156 157 ones = rte_popcount64(upper_bound); 158 159 /* Handle power-of-2 upper_bound as a special case, since it 160 * has no bias issues. 161 */ 162 if (unlikely(ones == 1)) 163 return __rte_rand_lfsr258(state) & (upper_bound - 1); 164 165 /* The approach to avoiding bias is to create a mask that 166 * stretches beyond the request value range, and up to the 167 * next power-of-2. In case the masked generated random value 168 * is equal to or greater than the upper bound, just discard 169 * the value and generate a new one. 170 */ 171 172 leading_zeros = rte_clz64(upper_bound); 173 mask >>= leading_zeros; 174 175 do { 176 res = __rte_rand_lfsr258(state) & mask; 177 } while (unlikely(res >= upper_bound)); 178 179 return res; 180 } 181 182 double 183 rte_drand(void) 184 { 185 static const uint64_t denom = (uint64_t)1 << 53; 186 uint64_t rand64 = rte_rand(); 187 188 /* 189 * The double mantissa only has 53 bits, so we uniformly mask off the 190 * high 11 bits and then floating-point divide by 2^53 to achieve a 191 * result in [0, 1). 192 * 193 * We are not allowed to emit 1.0, so denom must be one greater than 194 * the possible range of the preceding step. 195 */ 196 197 rand64 &= denom - 1; 198 return (double)rand64 / denom; 199 } 200 201 static uint64_t 202 __rte_random_initial_seed(void) 203 { 204 #ifdef RTE_LIBEAL_USE_GETENTROPY 205 int ge_rc; 206 uint64_t ge_seed; 207 208 ge_rc = getentropy(&ge_seed, sizeof(ge_seed)); 209 210 if (ge_rc == 0) 211 return ge_seed; 212 #endif 213 #ifdef __RDSEED__ 214 unsigned int rdseed_low; 215 unsigned int rdseed_high; 216 217 /* first fallback: rdseed instruction, if available */ 218 if (_rdseed32_step(&rdseed_low) == 1 && 219 _rdseed32_step(&rdseed_high) == 1) 220 return (uint64_t)rdseed_low | ((uint64_t)rdseed_high << 32); 221 #endif 222 /* second fallback: seed using rdtsc */ 223 return rte_get_tsc_cycles(); 224 } 225 226 RTE_INIT(rte_rand_init) 227 { 228 uint64_t seed; 229 230 seed = __rte_random_initial_seed(); 231 232 rte_srand(seed); 233 } 234