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