1 /******************************************************************************/ 2 #ifdef JEMALLOC_H_TYPES 3 4 /* 5 * Simple linear congruential pseudo-random number generator: 6 * 7 * prng(y) = (a*x + c) % m 8 * 9 * where the following constants ensure maximal period: 10 * 11 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4. 12 * c == Odd number (relatively prime to 2^n). 13 * m == 2^32 14 * 15 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints. 16 * 17 * This choice of m has the disadvantage that the quality of the bits is 18 * proportional to bit position. For example, the lowest bit has a cycle of 2, 19 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper 20 * bits. 21 */ 22 23 #define PRNG_A_32 UINT32_C(1103515241) 24 #define PRNG_C_32 UINT32_C(12347) 25 26 #define PRNG_A_64 UINT64_C(6364136223846793005) 27 #define PRNG_C_64 UINT64_C(1442695040888963407) 28 29 #endif /* JEMALLOC_H_TYPES */ 30 /******************************************************************************/ 31 #ifdef JEMALLOC_H_STRUCTS 32 33 #endif /* JEMALLOC_H_STRUCTS */ 34 /******************************************************************************/ 35 #ifdef JEMALLOC_H_EXTERNS 36 37 #endif /* JEMALLOC_H_EXTERNS */ 38 /******************************************************************************/ 39 #ifdef JEMALLOC_H_INLINES 40 41 #ifndef JEMALLOC_ENABLE_INLINE 42 uint32_t prng_state_next_u32(uint32_t state); 43 uint64_t prng_state_next_u64(uint64_t state); 44 size_t prng_state_next_zu(size_t state); 45 46 uint32_t prng_lg_range_u32(uint32_t *state, unsigned lg_range, 47 bool atomic); 48 uint64_t prng_lg_range_u64(uint64_t *state, unsigned lg_range); 49 size_t prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic); 50 51 uint32_t prng_range_u32(uint32_t *state, uint32_t range, bool atomic); 52 uint64_t prng_range_u64(uint64_t *state, uint64_t range); 53 size_t prng_range_zu(size_t *state, size_t range, bool atomic); 54 #endif 55 56 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_)) 57 JEMALLOC_ALWAYS_INLINE uint32_t 58 prng_state_next_u32(uint32_t state) 59 { 60 61 return ((state * PRNG_A_32) + PRNG_C_32); 62 } 63 64 JEMALLOC_ALWAYS_INLINE uint64_t 65 prng_state_next_u64(uint64_t state) 66 { 67 68 return ((state * PRNG_A_64) + PRNG_C_64); 69 } 70 71 JEMALLOC_ALWAYS_INLINE size_t 72 prng_state_next_zu(size_t state) 73 { 74 75 #if LG_SIZEOF_PTR == 2 76 return ((state * PRNG_A_32) + PRNG_C_32); 77 #elif LG_SIZEOF_PTR == 3 78 return ((state * PRNG_A_64) + PRNG_C_64); 79 #else 80 #error Unsupported pointer size 81 #endif 82 } 83 84 JEMALLOC_ALWAYS_INLINE uint32_t 85 prng_lg_range_u32(uint32_t *state, unsigned lg_range, bool atomic) 86 { 87 uint32_t ret, state1; 88 89 assert(lg_range > 0); 90 assert(lg_range <= 32); 91 92 if (atomic) { 93 uint32_t state0; 94 95 do { 96 state0 = atomic_read_uint32(state); 97 state1 = prng_state_next_u32(state0); 98 } while (atomic_cas_uint32(state, state0, state1)); 99 } else { 100 state1 = prng_state_next_u32(*state); 101 *state = state1; 102 } 103 ret = state1 >> (32 - lg_range); 104 105 return (ret); 106 } 107 108 /* 64-bit atomic operations cannot be supported on all relevant platforms. */ 109 JEMALLOC_ALWAYS_INLINE uint64_t 110 prng_lg_range_u64(uint64_t *state, unsigned lg_range) 111 { 112 uint64_t ret, state1; 113 114 assert(lg_range > 0); 115 assert(lg_range <= 64); 116 117 state1 = prng_state_next_u64(*state); 118 *state = state1; 119 ret = state1 >> (64 - lg_range); 120 121 return (ret); 122 } 123 124 JEMALLOC_ALWAYS_INLINE size_t 125 prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic) 126 { 127 size_t ret, state1; 128 129 assert(lg_range > 0); 130 assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR)); 131 132 if (atomic) { 133 size_t state0; 134 135 do { 136 state0 = atomic_read_z(state); 137 state1 = prng_state_next_zu(state0); 138 } while (atomic_cas_z(state, state0, state1)); 139 } else { 140 state1 = prng_state_next_zu(*state); 141 *state = state1; 142 } 143 ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range); 144 145 return (ret); 146 } 147 148 JEMALLOC_ALWAYS_INLINE uint32_t 149 prng_range_u32(uint32_t *state, uint32_t range, bool atomic) 150 { 151 uint32_t ret; 152 unsigned lg_range; 153 154 assert(range > 1); 155 156 /* Compute the ceiling of lg(range). */ 157 lg_range = ffs_u32(pow2_ceil_u32(range)) - 1; 158 159 /* Generate a result in [0..range) via repeated trial. */ 160 do { 161 ret = prng_lg_range_u32(state, lg_range, atomic); 162 } while (ret >= range); 163 164 return (ret); 165 } 166 167 JEMALLOC_ALWAYS_INLINE uint64_t 168 prng_range_u64(uint64_t *state, uint64_t range) 169 { 170 uint64_t ret; 171 unsigned lg_range; 172 173 assert(range > 1); 174 175 /* Compute the ceiling of lg(range). */ 176 lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 177 178 /* Generate a result in [0..range) via repeated trial. */ 179 do { 180 ret = prng_lg_range_u64(state, lg_range); 181 } while (ret >= range); 182 183 return (ret); 184 } 185 186 JEMALLOC_ALWAYS_INLINE size_t 187 prng_range_zu(size_t *state, size_t range, bool atomic) 188 { 189 size_t ret; 190 unsigned lg_range; 191 192 assert(range > 1); 193 194 /* Compute the ceiling of lg(range). */ 195 lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 196 197 /* Generate a result in [0..range) via repeated trial. */ 198 do { 199 ret = prng_lg_range_zu(state, lg_range, atomic); 200 } while (ret >= range); 201 202 return (ret); 203 } 204 #endif 205 206 #endif /* JEMALLOC_H_INLINES */ 207 /******************************************************************************/ 208
