lib/eal/common/rte_random.c

   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
  26 __rte_rand_lcg32(uint32_t *seed)
  27 {
  28         *seed = 1103515245U * *seed + 12345U;
  29
  30         return *seed;
  31 }
  32
  33 static uint64_t
  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
  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
  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
  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
  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
  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
 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
 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
 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
 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
 201 RTE_INIT(rte_rand_init)
 202 {
 203         uint64_t seed;
 204
 205         seed = __rte_random_initial_seed();
 206
 207         rte_srand(seed);
 208 }