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 static uint64_t 177 __rte_random_initial_seed(void) 178 { 179 #ifdef RTE_LIBEAL_USE_GETENTROPY 180 int ge_rc; 181 uint64_t ge_seed; 182 183 ge_rc = getentropy(&ge_seed, sizeof(ge_seed)); 184 185 if (ge_rc == 0) 186 return ge_seed; 187 #endif 188 #ifdef __RDSEED__ 189 unsigned int rdseed_low; 190 unsigned int rdseed_high; 191 192 /* first fallback: rdseed instruction, if available */ 193 if (_rdseed32_step(&rdseed_low) == 1 && 194 _rdseed32_step(&rdseed_high) == 1) 195 return (uint64_t)rdseed_low | ((uint64_t)rdseed_high << 32); 196 #endif 197 /* second fallback: seed using rdtsc */ 198 return rte_get_tsc_cycles(); 199 } 200 201 RTE_INIT(rte_rand_init) 202 { 203 uint64_t seed; 204 205 seed = __rte_random_initial_seed(); 206 207 rte_srand(seed); 208 } 209