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