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