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
prng_state_next_u32(uint32_t state)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
prng_state_next_u64(uint64_t state)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
prng_state_next_zu(size_t state)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
prng_lg_range_u32(atomic_u32_t * state,unsigned lg_range,bool atomic)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
prng_lg_range_u64(uint64_t * state,unsigned lg_range)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
prng_lg_range_zu(atomic_zu_t * state,unsigned lg_range,bool atomic)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
prng_range_u32(atomic_u32_t * state,uint32_t range,bool atomic)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
prng_range_u64(uint64_t * state,uint64_t range)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
prng_range_zu(atomic_zu_t * state,size_t range,bool atomic)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