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