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