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