1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#ifndef JEMALLOC_INTERNAL_PRNG_INLINES_H
#define JEMALLOC_INTERNAL_PRNG_INLINES_H
#include "jemalloc/internal/atomic.h"
#include "jemalloc/internal/bit_util.h"
#ifndef JEMALLOC_ENABLE_INLINE
uint32_t prng_state_next_u32(uint32_t state);
uint64_t prng_state_next_u64(uint64_t state);
size_t prng_state_next_zu(size_t state);
uint32_t prng_lg_range_u32(atomic_u32_t *state, unsigned lg_range,
bool atomic);
uint64_t prng_lg_range_u64(uint64_t *state, unsigned lg_range);
size_t prng_lg_range_zu(atomic_zu_t *state, unsigned lg_range, bool atomic);
uint32_t prng_range_u32(atomic_u32_t *state, uint32_t range,
bool atomic);
uint64_t prng_range_u64(uint64_t *state, uint64_t range);
size_t prng_range_zu(atomic_zu_t *state, size_t range, bool atomic);
#endif
#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_))
JEMALLOC_ALWAYS_INLINE uint32_t
prng_state_next_u32(uint32_t state) {
return (state * PRNG_A_32) + PRNG_C_32;
}
JEMALLOC_ALWAYS_INLINE uint64_t
prng_state_next_u64(uint64_t state) {
return (state * PRNG_A_64) + PRNG_C_64;
}
JEMALLOC_ALWAYS_INLINE size_t
prng_state_next_zu(size_t state) {
#if LG_SIZEOF_PTR == 2
return (state * PRNG_A_32) + PRNG_C_32;
#elif LG_SIZEOF_PTR == 3
return (state * PRNG_A_64) + PRNG_C_64;
#else
#error Unsupported pointer size
#endif
}
JEMALLOC_ALWAYS_INLINE uint32_t
prng_lg_range_u32(atomic_u32_t *state, unsigned lg_range, bool atomic) {
uint32_t ret, state0, state1;
assert(lg_range > 0);
assert(lg_range <= 32);
state0 = atomic_load_u32(state, ATOMIC_RELAXED);
if (atomic) {
do {
state1 = prng_state_next_u32(state0);
} while (!atomic_compare_exchange_weak_u32(state, &state0,
state1, ATOMIC_RELAXED, ATOMIC_RELAXED));
} else {
state1 = prng_state_next_u32(state0);
atomic_store_u32(state, state1, ATOMIC_RELAXED);
}
ret = state1 >> (32 - lg_range);
return ret;
}
/* 64-bit atomic operations cannot be supported on all relevant platforms. */
JEMALLOC_ALWAYS_INLINE uint64_t
prng_lg_range_u64(uint64_t *state, unsigned lg_range) {
uint64_t ret, state1;
assert(lg_range > 0);
assert(lg_range <= 64);
state1 = prng_state_next_u64(*state);
*state = state1;
ret = state1 >> (64 - lg_range);
return ret;
}
JEMALLOC_ALWAYS_INLINE size_t
prng_lg_range_zu(atomic_zu_t *state, unsigned lg_range, bool atomic) {
size_t ret, state0, state1;
assert(lg_range > 0);
assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR));
state0 = atomic_load_zu(state, ATOMIC_RELAXED);
if (atomic) {
do {
state1 = prng_state_next_zu(state0);
} while (atomic_compare_exchange_weak_zu(state, &state0,
state1, ATOMIC_RELAXED, ATOMIC_RELAXED));
} else {
state1 = prng_state_next_zu(state0);
atomic_store_zu(state, state1, ATOMIC_RELAXED);
}
ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range);
return ret;
}
JEMALLOC_ALWAYS_INLINE uint32_t
prng_range_u32(atomic_u32_t *state, uint32_t range, bool atomic) {
uint32_t ret;
unsigned lg_range;
assert(range > 1);
/* Compute the ceiling of lg(range). */
lg_range = ffs_u32(pow2_ceil_u32(range)) - 1;
/* Generate a result in [0..range) via repeated trial. */
do {
ret = prng_lg_range_u32(state, lg_range, atomic);
} while (ret >= range);
return ret;
}
JEMALLOC_ALWAYS_INLINE uint64_t
prng_range_u64(uint64_t *state, uint64_t range) {
uint64_t ret;
unsigned lg_range;
assert(range > 1);
/* Compute the ceiling of lg(range). */
lg_range = ffs_u64(pow2_ceil_u64(range)) - 1;
/* Generate a result in [0..range) via repeated trial. */
do {
ret = prng_lg_range_u64(state, lg_range);
} while (ret >= range);
return ret;
}
JEMALLOC_ALWAYS_INLINE size_t
prng_range_zu(atomic_zu_t *state, size_t range, bool atomic) {
size_t ret;
unsigned lg_range;
assert(range > 1);
/* Compute the ceiling of lg(range). */
lg_range = ffs_u64(pow2_ceil_u64(range)) - 1;
/* Generate a result in [0..range) via repeated trial. */
do {
ret = prng_lg_range_zu(state, lg_range, atomic);
} while (ret >= range);
return ret;
}
#endif
#endif /* JEMALLOC_INTERNAL_PRNG_INLINES_H */
|
