1#include "jemalloc/internal/jemalloc_preamble.h"
2#include "jemalloc/internal/jemalloc_internal_includes.h"
3
4#include "jemalloc/internal/thread_event.h"
5
6/*
7 * Signatures for event specific functions. These functions should be defined
8 * by the modules owning each event. The signatures here verify that the
9 * definitions follow the right format.
10 *
11 * The first two are functions computing new / postponed event wait time. New
12 * event wait time is the time till the next event if an event is currently
13 * being triggered; postponed event wait time is the time till the next event
14 * if an event should be triggered but needs to be postponed, e.g. when the TSD
15 * is not nominal or during reentrancy.
16 *
17 * The third is the event handler function, which is called whenever an event
18 * is triggered. The parameter is the elapsed time since the last time an
19 * event of the same type was triggered.
20 */
21#define E(event, condition_unused, is_alloc_event_unused) \
22uint64_t event##_new_event_wait(tsd_t *tsd); \
23uint64_t event##_postponed_event_wait(tsd_t *tsd); \
24void event##_event_handler(tsd_t *tsd, uint64_t elapsed);
25
26ITERATE_OVER_ALL_EVENTS
27#undef E
28
29/* Signatures for internal functions fetching elapsed time. */
30#define E(event, condition_unused, is_alloc_event_unused) \
31static uint64_t event##_fetch_elapsed(tsd_t *tsd);
32
33ITERATE_OVER_ALL_EVENTS
34#undef E
35
36static uint64_t
37tcache_gc_fetch_elapsed(tsd_t *tsd) {
38 return TE_INVALID_ELAPSED;
39}
40
41static uint64_t
42tcache_gc_dalloc_fetch_elapsed(tsd_t *tsd) {
43 return TE_INVALID_ELAPSED;
44}
45
46static uint64_t
47prof_sample_fetch_elapsed(tsd_t *tsd) {
48 uint64_t last_event = thread_allocated_last_event_get(tsd);
49 uint64_t last_sample_event = prof_sample_last_event_get(tsd);
50 prof_sample_last_event_set(tsd, last_event);
51 return last_event - last_sample_event;
52}
53
54static uint64_t
55stats_interval_fetch_elapsed(tsd_t *tsd) {
56 uint64_t last_event = thread_allocated_last_event_get(tsd);
57 uint64_t last_stats_event = stats_interval_last_event_get(tsd);
58 stats_interval_last_event_set(tsd, last_event);
59 return last_event - last_stats_event;
60}
61
62static uint64_t
63peak_alloc_fetch_elapsed(tsd_t *tsd) {
64 return TE_INVALID_ELAPSED;
65}
66
67static uint64_t
68peak_dalloc_fetch_elapsed(tsd_t *tsd) {
69 return TE_INVALID_ELAPSED;
70}
71
72/* Per event facilities done. */
73
74static bool
75te_ctx_has_active_events(te_ctx_t *ctx) {
76 assert(config_debug);
77#define E(event, condition, alloc_event) \
78 if (condition && alloc_event == ctx->is_alloc) { \
79 return true; \
80 }
81 ITERATE_OVER_ALL_EVENTS
82#undef E
83 return false;
84}
85
86static uint64_t
87te_next_event_compute(tsd_t *tsd, bool is_alloc) {
88 uint64_t wait = TE_MAX_START_WAIT;
89#define E(event, condition, alloc_event) \
90 if (is_alloc == alloc_event && condition) { \
91 uint64_t event_wait = \
92 event##_event_wait_get(tsd); \
93 assert(event_wait <= TE_MAX_START_WAIT); \
94 if (event_wait > 0U && event_wait < wait) { \
95 wait = event_wait; \
96 } \
97 }
98
99 ITERATE_OVER_ALL_EVENTS
100#undef E
101 assert(wait <= TE_MAX_START_WAIT);
102 return wait;
103}
104
105static void
106te_assert_invariants_impl(tsd_t *tsd, te_ctx_t *ctx) {
107 uint64_t current_bytes = te_ctx_current_bytes_get(ctx);
108 uint64_t last_event = te_ctx_last_event_get(ctx);
109 uint64_t next_event = te_ctx_next_event_get(ctx);
110 uint64_t next_event_fast = te_ctx_next_event_fast_get(ctx);
111
112 assert(last_event != next_event);
113 if (next_event > TE_NEXT_EVENT_FAST_MAX || !tsd_fast(tsd)) {
114 assert(next_event_fast == 0U);
115 } else {
116 assert(next_event_fast == next_event);
117 }
118
119 /* The subtraction is intentionally susceptible to underflow. */
120 uint64_t interval = next_event - last_event;
121
122 /* The subtraction is intentionally susceptible to underflow. */
123 assert(current_bytes - last_event < interval);
124 uint64_t min_wait = te_next_event_compute(tsd, te_ctx_is_alloc(ctx));
125 /*
126 * next_event should have been pushed up only except when no event is
127 * on and the TSD is just initialized. The last_event == 0U guard
128 * below is stronger than needed, but having an exactly accurate guard
129 * is more complicated to implement.
130 */
131 assert((!te_ctx_has_active_events(ctx) && last_event == 0U) ||
132 interval == min_wait ||
133 (interval < min_wait && interval == TE_MAX_INTERVAL));
134}
135
136void
137te_assert_invariants_debug(tsd_t *tsd) {
138 te_ctx_t ctx;
139 te_ctx_get(tsd, &ctx, true);
140 te_assert_invariants_impl(tsd, &ctx);
141
142 te_ctx_get(tsd, &ctx, false);
143 te_assert_invariants_impl(tsd, &ctx);
144}
145
146/*
147 * Synchronization around the fast threshold in tsd --
148 * There are two threads to consider in the synchronization here:
149 * - The owner of the tsd being updated by a slow path change
150 * - The remote thread, doing that slow path change.
151 *
152 * As a design constraint, we want to ensure that a slow-path transition cannot
153 * be ignored for arbitrarily long, and that if the remote thread causes a
154 * slow-path transition and then communicates with the owner thread that it has
155 * occurred, then the owner will go down the slow path on the next allocator
156 * operation (so that we don't want to just wait until the owner hits its slow
157 * path reset condition on its own).
158 *
159 * Here's our strategy to do that:
160 *
161 * The remote thread will update the slow-path stores to TSD variables, issue a
162 * SEQ_CST fence, and then update the TSD next_event_fast counter. The owner
163 * thread will update next_event_fast, issue an SEQ_CST fence, and then check
164 * its TSD to see if it's on the slow path.
165
166 * This is fairly straightforward when 64-bit atomics are supported. Assume that
167 * the remote fence is sandwiched between two owner fences in the reset pathway.
168 * The case where there is no preceding or trailing owner fence (i.e. because
169 * the owner thread is near the beginning or end of its life) can be analyzed
170 * similarly. The owner store to next_event_fast preceding the earlier owner
171 * fence will be earlier in coherence order than the remote store to it, so that
172 * the owner thread will go down the slow path once the store becomes visible to
173 * it, which is no later than the time of the second fence.
174
175 * The case where we don't support 64-bit atomics is trickier, since word
176 * tearing is possible. We'll repeat the same analysis, and look at the two
177 * owner fences sandwiching the remote fence. The next_event_fast stores done
178 * alongside the earlier owner fence cannot overwrite any of the remote stores
179 * (since they precede the earlier owner fence in sb, which precedes the remote
180 * fence in sc, which precedes the remote stores in sb). After the second owner
181 * fence there will be a re-check of the slow-path variables anyways, so the
182 * "owner will notice that it's on the slow path eventually" guarantee is
183 * satisfied. To make sure that the out-of-band-messaging constraint is as well,
184 * note that either the message passing is sequenced before the second owner
185 * fence (in which case the remote stores happen before the second set of owner
186 * stores, so malloc sees a value of zero for next_event_fast and goes down the
187 * slow path), or it is not (in which case the owner sees the tsd slow-path
188 * writes on its previous update). This leaves open the possibility that the
189 * remote thread will (at some arbitrary point in the future) zero out one half
190 * of the owner thread's next_event_fast, but that's always safe (it just sends
191 * it down the slow path earlier).
192 */
193static void
194te_ctx_next_event_fast_update(te_ctx_t *ctx) {
195 uint64_t next_event = te_ctx_next_event_get(ctx);
196 uint64_t next_event_fast = (next_event <= TE_NEXT_EVENT_FAST_MAX) ?
197 next_event : 0U;
198 te_ctx_next_event_fast_set(ctx, next_event_fast);
199}
200
201void
202te_recompute_fast_threshold(tsd_t *tsd) {
203 if (tsd_state_get(tsd) != tsd_state_nominal) {
204 /* Check first because this is also called on purgatory. */
205 te_next_event_fast_set_non_nominal(tsd);
206 return;
207 }
208
209 te_ctx_t ctx;
210 te_ctx_get(tsd, &ctx, true);
211 te_ctx_next_event_fast_update(&ctx);
212 te_ctx_get(tsd, &ctx, false);
213 te_ctx_next_event_fast_update(&ctx);
214
215 atomic_fence(ATOMIC_SEQ_CST);
216 if (tsd_state_get(tsd) != tsd_state_nominal) {
217 te_next_event_fast_set_non_nominal(tsd);
218 }
219}
220
221static void
222te_adjust_thresholds_helper(tsd_t *tsd, te_ctx_t *ctx,
223 uint64_t wait) {
224 /*
225 * The next threshold based on future events can only be adjusted after
226 * progressing the last_event counter (which is set to current).
227 */
228 assert(te_ctx_current_bytes_get(ctx) == te_ctx_last_event_get(ctx));
229 assert(wait <= TE_MAX_START_WAIT);
230
231 uint64_t next_event = te_ctx_last_event_get(ctx) + (wait <=
232 TE_MAX_INTERVAL ? wait : TE_MAX_INTERVAL);
233 te_ctx_next_event_set(tsd, ctx, next_event);
234}
235
236static uint64_t
237te_clip_event_wait(uint64_t event_wait) {
238 assert(event_wait > 0U);
239 if (TE_MIN_START_WAIT > 1U &&
240 unlikely(event_wait < TE_MIN_START_WAIT)) {
241 event_wait = TE_MIN_START_WAIT;
242 }
243 if (TE_MAX_START_WAIT < UINT64_MAX &&
244 unlikely(event_wait > TE_MAX_START_WAIT)) {
245 event_wait = TE_MAX_START_WAIT;
246 }
247 return event_wait;
248}
249
250void
251te_event_trigger(tsd_t *tsd, te_ctx_t *ctx) {
252 /* usize has already been added to thread_allocated. */
253 uint64_t bytes_after = te_ctx_current_bytes_get(ctx);
254 /* The subtraction is intentionally susceptible to underflow. */
255 uint64_t accumbytes = bytes_after - te_ctx_last_event_get(ctx);
256
257 te_ctx_last_event_set(ctx, bytes_after);
258
259 bool allow_event_trigger = tsd_nominal(tsd) &&
260 tsd_reentrancy_level_get(tsd) == 0;
261 bool is_alloc = ctx->is_alloc;
262 uint64_t wait = TE_MAX_START_WAIT;
263
264#define E(event, condition, alloc_event) \
265 bool is_##event##_triggered = false; \
266 if (is_alloc == alloc_event && condition) { \
267 uint64_t event_wait = event##_event_wait_get(tsd); \
268 assert(event_wait <= TE_MAX_START_WAIT); \
269 if (event_wait > accumbytes) { \
270 event_wait -= accumbytes; \
271 } else if (!allow_event_trigger) { \
272 event_wait = event##_postponed_event_wait(tsd); \
273 } else { \
274 is_##event##_triggered = true; \
275 event_wait = event##_new_event_wait(tsd); \
276 } \
277 event_wait = te_clip_event_wait(event_wait); \
278 event##_event_wait_set(tsd, event_wait); \
279 if (event_wait < wait) { \
280 wait = event_wait; \
281 } \
282 }
283
284 ITERATE_OVER_ALL_EVENTS
285#undef E
286
287 assert(wait <= TE_MAX_START_WAIT);
288 te_adjust_thresholds_helper(tsd, ctx, wait);
289 te_assert_invariants(tsd);
290
291#define E(event, condition, alloc_event) \
292 if (is_alloc == alloc_event && condition && \
293 is_##event##_triggered) { \
294 assert(allow_event_trigger); \
295 uint64_t elapsed = event##_fetch_elapsed(tsd); \
296 event##_event_handler(tsd, elapsed); \
297 }
298
299 ITERATE_OVER_ALL_EVENTS
300#undef E
301
302 te_assert_invariants(tsd);
303}
304
305static void
306te_init(tsd_t *tsd, bool is_alloc) {
307 te_ctx_t ctx;
308 te_ctx_get(tsd, &ctx, is_alloc);
309 /*
310 * Reset the last event to current, which starts the events from a clean
311 * state. This is necessary when re-init the tsd event counters.
312 *
313 * The event counters maintain a relationship with the current bytes:
314 * last_event <= current < next_event. When a reinit happens (e.g.
315 * reincarnated tsd), the last event needs progressing because all
316 * events start fresh from the current bytes.
317 */
318 te_ctx_last_event_set(&ctx, te_ctx_current_bytes_get(&ctx));
319
320 uint64_t wait = TE_MAX_START_WAIT;
321#define E(event, condition, alloc_event) \
322 if (is_alloc == alloc_event && condition) { \
323 uint64_t event_wait = event##_new_event_wait(tsd); \
324 event_wait = te_clip_event_wait(event_wait); \
325 event##_event_wait_set(tsd, event_wait); \
326 if (event_wait < wait) { \
327 wait = event_wait; \
328 } \
329 }
330
331 ITERATE_OVER_ALL_EVENTS
332#undef E
333 te_adjust_thresholds_helper(tsd, &ctx, wait);
334}
335
336void
337tsd_te_init(tsd_t *tsd) {
338 /* Make sure no overflow for the bytes accumulated on event_trigger. */
339 assert(TE_MAX_INTERVAL <= UINT64_MAX - SC_LARGE_MAXCLASS + 1);
340 te_init(tsd, true);
341 te_init(tsd, false);
342 te_assert_invariants(tsd);
343}
344