lib/librte_eal/common/rte_random.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019 Ericsson AB
   3  */
   4
   5 #ifdef RTE_MACHINE_CPUFLAG_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
  29 __rte_rand_lcg32(uint32_t *seed)
  30 {
  31         *seed = 1103515245U * *seed + 12345U;
  32
  33         return *seed;
  34 }
  35
  36 static uint64_t
  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
  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
  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
  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
  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
 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
 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_master_lcore();
 126
 127         return &rand_states[lcore_id];
 128 }
 129
 130 uint64_t
 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
 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
 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 RTE_MACHINE_CPUFLAG_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_timer_cycles();
 202 }
 203
 204 RTE_INIT(rte_rand_init)
 205 {
 206         uint64_t seed;
 207
 208         seed = __rte_random_initial_seed();
 209
 210         rte_srand(seed);
 211 }