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
__rte_rand_lcg32(uint32_t * seed)26 __rte_rand_lcg32(uint32_t *seed)
27 {
28 *seed = 1103515245U * *seed + 12345U;
29
30 return *seed;
31 }
32
33 static uint64_t
__rte_rand_lcg64(uint32_t * seed)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
__rte_rand_lfsr258_gen_seed(uint32_t * seed,uint64_t min_value)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
__rte_srand_lfsr258(uint64_t seed,struct rte_rand_state * state)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
rte_srand(uint64_t seed)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
__rte_rand_lfsr258_comp(uint64_t z,uint64_t a,uint64_t b,uint64_t c,uint64_t d)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
__rte_rand_lfsr258(struct rte_rand_state * state)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
__rte_rand_get_state(void)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
rte_rand(void)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
rte_rand_max(uint64_t upper_bound)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
__rte_random_initial_seed(void)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
RTE_INIT(rte_rand_init)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