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