1 #ifndef JEMALLOC_INTERNAL_PRNG_H 2 #define JEMALLOC_INTERNAL_PRNG_H 3 4 #include "jemalloc/internal/atomic.h" 5 #include "jemalloc/internal/bit_util.h" 6 7 /* 8 * Simple linear congruential pseudo-random number generator: 9 * 10 * prng(y) = (a*x + c) % m 11 * 12 * where the following constants ensure maximal period: 13 * 14 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4. 15 * c == Odd number (relatively prime to 2^n). 16 * m == 2^32 17 * 18 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints. 19 * 20 * This choice of m has the disadvantage that the quality of the bits is 21 * proportional to bit position. For example, the lowest bit has a cycle of 2, 22 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper 23 * bits. 24 */ 25 26 /******************************************************************************/ 27 /* INTERNAL DEFINITIONS -- IGNORE */ 28 /******************************************************************************/ 29 #define PRNG_A_32 UINT32_C(1103515241) 30 #define PRNG_C_32 UINT32_C(12347) 31 32 #define PRNG_A_64 UINT64_C(6364136223846793005) 33 #define PRNG_C_64 UINT64_C(1442695040888963407) 34 35 JEMALLOC_ALWAYS_INLINE uint32_t 36 prng_state_next_u32(uint32_t state) { 37 return (state * PRNG_A_32) + PRNG_C_32; 38 } 39 40 JEMALLOC_ALWAYS_INLINE uint64_t 41 prng_state_next_u64(uint64_t state) { 42 return (state * PRNG_A_64) + PRNG_C_64; 43 } 44 45 JEMALLOC_ALWAYS_INLINE size_t 46 prng_state_next_zu(size_t state) { 47 #if LG_SIZEOF_PTR == 2 48 return (state * PRNG_A_32) + PRNG_C_32; 49 #elif LG_SIZEOF_PTR == 3 50 return (state * PRNG_A_64) + PRNG_C_64; 51 #else 52 #error Unsupported pointer size 53 #endif 54 } 55 56 /******************************************************************************/ 57 /* BEGIN PUBLIC API */ 58 /******************************************************************************/ 59 60 /* 61 * The prng_lg_range functions give a uniform int in the half-open range [0, 62 * 2**lg_range). If atomic is true, they do so safely from multiple threads. 63 * Multithreaded 64-bit prngs aren't supported. 64 */ 65 66 JEMALLOC_ALWAYS_INLINE uint32_t 67 prng_lg_range_u32(atomic_u32_t *state, unsigned lg_range, bool atomic) { 68 uint32_t ret, state0, state1; 69 70 assert(lg_range > 0); 71 assert(lg_range <= 32); 72 73 state0 = atomic_load_u32(state, ATOMIC_RELAXED); 74 75 if (atomic) { 76 do { 77 state1 = prng_state_next_u32(state0); 78 } while (!atomic_compare_exchange_weak_u32(state, &state0, 79 state1, ATOMIC_RELAXED, ATOMIC_RELAXED)); 80 } else { 81 state1 = prng_state_next_u32(state0); 82 atomic_store_u32(state, state1, ATOMIC_RELAXED); 83 } 84 ret = state1 >> (32 - lg_range); 85 86 return ret; 87 } 88 89 JEMALLOC_ALWAYS_INLINE uint64_t 90 prng_lg_range_u64(uint64_t *state, unsigned lg_range) { 91 uint64_t ret, state1; 92 93 assert(lg_range > 0); 94 assert(lg_range <= 64); 95 96 state1 = prng_state_next_u64(*state); 97 *state = state1; 98 ret = state1 >> (64 - lg_range); 99 100 return ret; 101 } 102 103 JEMALLOC_ALWAYS_INLINE size_t 104 prng_lg_range_zu(atomic_zu_t *state, unsigned lg_range, bool atomic) { 105 size_t ret, state0, state1; 106 107 assert(lg_range > 0); 108 assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR)); 109 110 state0 = atomic_load_zu(state, ATOMIC_RELAXED); 111 112 if (atomic) { 113 do { 114 state1 = prng_state_next_zu(state0); 115 } while (atomic_compare_exchange_weak_zu(state, &state0, 116 state1, ATOMIC_RELAXED, ATOMIC_RELAXED)); 117 } else { 118 state1 = prng_state_next_zu(state0); 119 atomic_store_zu(state, state1, ATOMIC_RELAXED); 120 } 121 ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range); 122 123 return ret; 124 } 125 126 /* 127 * The prng_range functions behave like the prng_lg_range, but return a result 128 * in [0, range) instead of [0, 2**lg_range). 129 */ 130 131 JEMALLOC_ALWAYS_INLINE uint32_t 132 prng_range_u32(atomic_u32_t *state, uint32_t range, bool atomic) { 133 uint32_t ret; 134 unsigned lg_range; 135 136 assert(range > 1); 137 138 /* Compute the ceiling of lg(range). */ 139 lg_range = ffs_u32(pow2_ceil_u32(range)) - 1; 140 141 /* Generate a result in [0..range) via repeated trial. */ 142 do { 143 ret = prng_lg_range_u32(state, lg_range, atomic); 144 } while (ret >= range); 145 146 return ret; 147 } 148 149 JEMALLOC_ALWAYS_INLINE uint64_t 150 prng_range_u64(uint64_t *state, uint64_t range) { 151 uint64_t ret; 152 unsigned lg_range; 153 154 assert(range > 1); 155 156 /* Compute the ceiling of lg(range). */ 157 lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 158 159 /* Generate a result in [0..range) via repeated trial. */ 160 do { 161 ret = prng_lg_range_u64(state, lg_range); 162 } while (ret >= range); 163 164 return ret; 165 } 166 167 JEMALLOC_ALWAYS_INLINE size_t 168 prng_range_zu(atomic_zu_t *state, size_t range, bool atomic) { 169 size_t ret; 170 unsigned lg_range; 171 172 assert(range > 1); 173 174 /* Compute the ceiling of lg(range). */ 175 lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 176 177 /* Generate a result in [0..range) via repeated trial. */ 178 do { 179 ret = prng_lg_range_zu(state, lg_range, atomic); 180 } while (ret >= range); 181 182 return ret; 183 } 184 185 #endif /* JEMALLOC_INTERNAL_PRNG_H */ 186
