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 35JEMALLOC_ALWAYS_INLINE uint32_t 36prng_state_next_u32(uint32_t state) { 37 return (state * PRNG_A_32) + PRNG_C_32; 38} 39 40JEMALLOC_ALWAYS_INLINE uint64_t 41prng_state_next_u64(uint64_t state) { 42 return (state * PRNG_A_64) + PRNG_C_64; 43} 44 45JEMALLOC_ALWAYS_INLINE size_t 46prng_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 66JEMALLOC_ALWAYS_INLINE uint32_t 67prng_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 89JEMALLOC_ALWAYS_INLINE uint64_t 90prng_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 103JEMALLOC_ALWAYS_INLINE size_t 104prng_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 131JEMALLOC_ALWAYS_INLINE uint32_t 132prng_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 149JEMALLOC_ALWAYS_INLINE uint64_t 150prng_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 167JEMALLOC_ALWAYS_INLINE size_t 168prng_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