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) \ |
22 | uint64_t event##_new_event_wait(tsd_t *tsd); \ |
23 | uint64_t event##_postponed_event_wait(tsd_t *tsd); \ |
24 | void event##_event_handler(tsd_t *tsd, uint64_t elapsed); |
25 | |
26 | ITERATE_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) \ |
31 | static uint64_t event##_fetch_elapsed(tsd_t *tsd); |
32 | |
33 | ITERATE_OVER_ALL_EVENTS |
34 | #undef E |
35 | |
36 | static uint64_t |
37 | tcache_gc_fetch_elapsed(tsd_t *tsd) { |
38 | return TE_INVALID_ELAPSED; |
39 | } |
40 | |
41 | static uint64_t |
42 | tcache_gc_dalloc_fetch_elapsed(tsd_t *tsd) { |
43 | return TE_INVALID_ELAPSED; |
44 | } |
45 | |
46 | static uint64_t |
47 | prof_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 | |
54 | static uint64_t |
55 | stats_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 | |
62 | static uint64_t |
63 | peak_alloc_fetch_elapsed(tsd_t *tsd) { |
64 | return TE_INVALID_ELAPSED; |
65 | } |
66 | |
67 | static uint64_t |
68 | peak_dalloc_fetch_elapsed(tsd_t *tsd) { |
69 | return TE_INVALID_ELAPSED; |
70 | } |
71 | |
72 | /* Per event facilities done. */ |
73 | |
74 | static bool |
75 | te_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 | |
86 | static uint64_t |
87 | te_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 | |
105 | static void |
106 | te_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 | |
136 | void |
137 | te_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 | */ |
193 | static void |
194 | te_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 | |
201 | void |
202 | te_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 | |
221 | static void |
222 | te_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 | |
236 | static uint64_t |
237 | te_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 | |
250 | void |
251 | te_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 | |
305 | static void |
306 | te_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 | |
336 | void |
337 | tsd_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 | |