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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 | |