1 | #include "jemalloc/internal/jemalloc_preamble.h" |
2 | #include "jemalloc/internal/jemalloc_internal_includes.h" |
3 | |
4 | #include "jemalloc/internal/emap.h" |
5 | |
6 | enum emap_lock_result_e { |
7 | emap_lock_result_success, |
8 | emap_lock_result_failure, |
9 | emap_lock_result_no_extent |
10 | }; |
11 | typedef enum emap_lock_result_e emap_lock_result_t; |
12 | |
13 | bool |
14 | emap_init(emap_t *emap, base_t *base, bool zeroed) { |
15 | return rtree_new(&emap->rtree, base, zeroed); |
16 | } |
17 | |
18 | void |
19 | emap_update_edata_state(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
20 | extent_state_t state) { |
21 | witness_assert_positive_depth_to_rank(tsdn_witness_tsdp_get(tsdn), |
22 | WITNESS_RANK_CORE); |
23 | |
24 | edata_state_set(edata, state); |
25 | |
26 | EMAP_DECLARE_RTREE_CTX; |
27 | rtree_leaf_elm_t *elm1 = rtree_leaf_elm_lookup(tsdn, &emap->rtree, |
28 | rtree_ctx, (uintptr_t)edata_base_get(edata), /* dependent */ true, |
29 | /* init_missing */ false); |
30 | assert(elm1 != NULL); |
31 | rtree_leaf_elm_t *elm2 = edata_size_get(edata) == PAGE ? NULL : |
32 | rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, |
33 | (uintptr_t)edata_last_get(edata), /* dependent */ true, |
34 | /* init_missing */ false); |
35 | |
36 | rtree_leaf_elm_state_update(tsdn, &emap->rtree, elm1, elm2, state); |
37 | |
38 | emap_assert_mapped(tsdn, emap, edata); |
39 | } |
40 | |
41 | static inline edata_t * |
42 | emap_try_acquire_edata_neighbor_impl(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
43 | extent_pai_t pai, extent_state_t expected_state, bool forward, |
44 | bool expanding) { |
45 | witness_assert_positive_depth_to_rank(tsdn_witness_tsdp_get(tsdn), |
46 | WITNESS_RANK_CORE); |
47 | assert(!edata_guarded_get(edata)); |
48 | assert(!expanding || forward); |
49 | assert(!edata_state_in_transition(expected_state)); |
50 | assert(expected_state == extent_state_dirty || |
51 | expected_state == extent_state_muzzy || |
52 | expected_state == extent_state_retained); |
53 | |
54 | void *neighbor_addr = forward ? edata_past_get(edata) : |
55 | edata_before_get(edata); |
56 | /* |
57 | * This is subtle; the rtree code asserts that its input pointer is |
58 | * non-NULL, and this is a useful thing to check. But it's possible |
59 | * that edata corresponds to an address of (void *)PAGE (in practice, |
60 | * this has only been observed on FreeBSD when address-space |
61 | * randomization is on, but it could in principle happen anywhere). In |
62 | * this case, edata_before_get(edata) is NULL, triggering the assert. |
63 | */ |
64 | if (neighbor_addr == NULL) { |
65 | return NULL; |
66 | } |
67 | |
68 | EMAP_DECLARE_RTREE_CTX; |
69 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, &emap->rtree, |
70 | rtree_ctx, (uintptr_t)neighbor_addr, /* dependent*/ false, |
71 | /* init_missing */ false); |
72 | if (elm == NULL) { |
73 | return NULL; |
74 | } |
75 | |
76 | rtree_contents_t neighbor_contents = rtree_leaf_elm_read(tsdn, |
77 | &emap->rtree, elm, /* dependent */ true); |
78 | if (!extent_can_acquire_neighbor(edata, neighbor_contents, pai, |
79 | expected_state, forward, expanding)) { |
80 | return NULL; |
81 | } |
82 | |
83 | /* From this point, the neighbor edata can be safely acquired. */ |
84 | edata_t *neighbor = neighbor_contents.edata; |
85 | assert(edata_state_get(neighbor) == expected_state); |
86 | emap_update_edata_state(tsdn, emap, neighbor, extent_state_merging); |
87 | if (expanding) { |
88 | extent_assert_can_expand(edata, neighbor); |
89 | } else { |
90 | extent_assert_can_coalesce(edata, neighbor); |
91 | } |
92 | |
93 | return neighbor; |
94 | } |
95 | |
96 | edata_t * |
97 | emap_try_acquire_edata_neighbor(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
98 | extent_pai_t pai, extent_state_t expected_state, bool forward) { |
99 | return emap_try_acquire_edata_neighbor_impl(tsdn, emap, edata, pai, |
100 | expected_state, forward, /* expand */ false); |
101 | } |
102 | |
103 | edata_t * |
104 | emap_try_acquire_edata_neighbor_expand(tsdn_t *tsdn, emap_t *emap, |
105 | edata_t *edata, extent_pai_t pai, extent_state_t expected_state) { |
106 | /* Try expanding forward. */ |
107 | return emap_try_acquire_edata_neighbor_impl(tsdn, emap, edata, pai, |
108 | expected_state, /* forward */ true, /* expand */ true); |
109 | } |
110 | |
111 | void |
112 | emap_release_edata(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
113 | extent_state_t new_state) { |
114 | assert(emap_edata_in_transition(tsdn, emap, edata)); |
115 | assert(emap_edata_is_acquired(tsdn, emap, edata)); |
116 | |
117 | emap_update_edata_state(tsdn, emap, edata, new_state); |
118 | } |
119 | |
120 | static bool |
121 | emap_rtree_leaf_elms_lookup(tsdn_t *tsdn, emap_t *emap, rtree_ctx_t *rtree_ctx, |
122 | const edata_t *edata, bool dependent, bool init_missing, |
123 | rtree_leaf_elm_t **r_elm_a, rtree_leaf_elm_t **r_elm_b) { |
124 | *r_elm_a = rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, |
125 | (uintptr_t)edata_base_get(edata), dependent, init_missing); |
126 | if (!dependent && *r_elm_a == NULL) { |
127 | return true; |
128 | } |
129 | assert(*r_elm_a != NULL); |
130 | |
131 | *r_elm_b = rtree_leaf_elm_lookup(tsdn, &emap->rtree, rtree_ctx, |
132 | (uintptr_t)edata_last_get(edata), dependent, init_missing); |
133 | if (!dependent && *r_elm_b == NULL) { |
134 | return true; |
135 | } |
136 | assert(*r_elm_b != NULL); |
137 | |
138 | return false; |
139 | } |
140 | |
141 | static void |
142 | emap_rtree_write_acquired(tsdn_t *tsdn, emap_t *emap, rtree_leaf_elm_t *elm_a, |
143 | rtree_leaf_elm_t *elm_b, edata_t *edata, szind_t szind, bool slab) { |
144 | rtree_contents_t contents; |
145 | contents.edata = edata; |
146 | contents.metadata.szind = szind; |
147 | contents.metadata.slab = slab; |
148 | contents.metadata.is_head = (edata == NULL) ? false : |
149 | edata_is_head_get(edata); |
150 | contents.metadata.state = (edata == NULL) ? 0 : edata_state_get(edata); |
151 | rtree_leaf_elm_write(tsdn, &emap->rtree, elm_a, contents); |
152 | if (elm_b != NULL) { |
153 | rtree_leaf_elm_write(tsdn, &emap->rtree, elm_b, contents); |
154 | } |
155 | } |
156 | |
157 | bool |
158 | emap_register_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
159 | szind_t szind, bool slab) { |
160 | assert(edata_state_get(edata) == extent_state_active); |
161 | EMAP_DECLARE_RTREE_CTX; |
162 | |
163 | rtree_leaf_elm_t *elm_a, *elm_b; |
164 | bool err = emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, edata, |
165 | false, true, &elm_a, &elm_b); |
166 | if (err) { |
167 | return true; |
168 | } |
169 | assert(rtree_leaf_elm_read(tsdn, &emap->rtree, elm_a, |
170 | /* dependent */ false).edata == NULL); |
171 | assert(rtree_leaf_elm_read(tsdn, &emap->rtree, elm_b, |
172 | /* dependent */ false).edata == NULL); |
173 | emap_rtree_write_acquired(tsdn, emap, elm_a, elm_b, edata, szind, slab); |
174 | return false; |
175 | } |
176 | |
177 | /* Invoked *after* emap_register_boundary. */ |
178 | void |
179 | emap_register_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata, |
180 | szind_t szind) { |
181 | EMAP_DECLARE_RTREE_CTX; |
182 | |
183 | assert(edata_slab_get(edata)); |
184 | assert(edata_state_get(edata) == extent_state_active); |
185 | |
186 | if (config_debug) { |
187 | /* Making sure the boundary is registered already. */ |
188 | rtree_leaf_elm_t *elm_a, *elm_b; |
189 | bool err = emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, |
190 | edata, /* dependent */ true, /* init_missing */ false, |
191 | &elm_a, &elm_b); |
192 | assert(!err); |
193 | rtree_contents_t contents_a, contents_b; |
194 | contents_a = rtree_leaf_elm_read(tsdn, &emap->rtree, elm_a, |
195 | /* dependent */ true); |
196 | contents_b = rtree_leaf_elm_read(tsdn, &emap->rtree, elm_b, |
197 | /* dependent */ true); |
198 | assert(contents_a.edata == edata && contents_b.edata == edata); |
199 | assert(contents_a.metadata.slab && contents_b.metadata.slab); |
200 | } |
201 | |
202 | rtree_contents_t contents; |
203 | contents.edata = edata; |
204 | contents.metadata.szind = szind; |
205 | contents.metadata.slab = true; |
206 | contents.metadata.state = extent_state_active; |
207 | contents.metadata.is_head = false; /* Not allowed to access. */ |
208 | |
209 | assert(edata_size_get(edata) > (2 << LG_PAGE)); |
210 | rtree_write_range(tsdn, &emap->rtree, rtree_ctx, |
211 | (uintptr_t)edata_base_get(edata) + PAGE, |
212 | (uintptr_t)edata_last_get(edata) - PAGE, contents); |
213 | } |
214 | |
215 | void |
216 | emap_deregister_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { |
217 | /* |
218 | * The edata must be either in an acquired state, or protected by state |
219 | * based locks. |
220 | */ |
221 | if (!emap_edata_is_acquired(tsdn, emap, edata)) { |
222 | witness_assert_positive_depth_to_rank( |
223 | tsdn_witness_tsdp_get(tsdn), WITNESS_RANK_CORE); |
224 | } |
225 | |
226 | EMAP_DECLARE_RTREE_CTX; |
227 | rtree_leaf_elm_t *elm_a, *elm_b; |
228 | |
229 | emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, edata, |
230 | true, false, &elm_a, &elm_b); |
231 | emap_rtree_write_acquired(tsdn, emap, elm_a, elm_b, NULL, SC_NSIZES, |
232 | false); |
233 | } |
234 | |
235 | void |
236 | emap_deregister_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { |
237 | EMAP_DECLARE_RTREE_CTX; |
238 | |
239 | assert(edata_slab_get(edata)); |
240 | if (edata_size_get(edata) > (2 << LG_PAGE)) { |
241 | rtree_clear_range(tsdn, &emap->rtree, rtree_ctx, |
242 | (uintptr_t)edata_base_get(edata) + PAGE, |
243 | (uintptr_t)edata_last_get(edata) - PAGE); |
244 | } |
245 | } |
246 | |
247 | void |
248 | emap_remap(tsdn_t *tsdn, emap_t *emap, edata_t *edata, szind_t szind, |
249 | bool slab) { |
250 | EMAP_DECLARE_RTREE_CTX; |
251 | |
252 | if (szind != SC_NSIZES) { |
253 | rtree_contents_t contents; |
254 | contents.edata = edata; |
255 | contents.metadata.szind = szind; |
256 | contents.metadata.slab = slab; |
257 | contents.metadata.is_head = edata_is_head_get(edata); |
258 | contents.metadata.state = edata_state_get(edata); |
259 | |
260 | rtree_write(tsdn, &emap->rtree, rtree_ctx, |
261 | (uintptr_t)edata_addr_get(edata), contents); |
262 | /* |
263 | * Recall that this is called only for active->inactive and |
264 | * inactive->active transitions (since only active extents have |
265 | * meaningful values for szind and slab). Active, non-slab |
266 | * extents only need to handle lookups at their head (on |
267 | * deallocation), so we don't bother filling in the end |
268 | * boundary. |
269 | * |
270 | * For slab extents, we do the end-mapping change. This still |
271 | * leaves the interior unmodified; an emap_register_interior |
272 | * call is coming in those cases, though. |
273 | */ |
274 | if (slab && edata_size_get(edata) > PAGE) { |
275 | uintptr_t key = (uintptr_t)edata_past_get(edata) |
276 | - (uintptr_t)PAGE; |
277 | rtree_write(tsdn, &emap->rtree, rtree_ctx, key, |
278 | contents); |
279 | } |
280 | } |
281 | } |
282 | |
283 | bool |
284 | emap_split_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, |
285 | edata_t *edata, size_t size_a, edata_t *trail, size_t size_b) { |
286 | EMAP_DECLARE_RTREE_CTX; |
287 | |
288 | /* |
289 | * We use incorrect constants for things like arena ind, zero, ranged, |
290 | * and commit state, and head status. This is a fake edata_t, used to |
291 | * facilitate a lookup. |
292 | */ |
293 | edata_t lead = {0}; |
294 | edata_init(&lead, 0U, edata_addr_get(edata), size_a, false, 0, 0, |
295 | extent_state_active, false, false, EXTENT_PAI_PAC, EXTENT_NOT_HEAD); |
296 | |
297 | emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, &lead, false, true, |
298 | &prepare->lead_elm_a, &prepare->lead_elm_b); |
299 | emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, trail, false, true, |
300 | &prepare->trail_elm_a, &prepare->trail_elm_b); |
301 | |
302 | if (prepare->lead_elm_a == NULL || prepare->lead_elm_b == NULL |
303 | || prepare->trail_elm_a == NULL || prepare->trail_elm_b == NULL) { |
304 | return true; |
305 | } |
306 | return false; |
307 | } |
308 | |
309 | void |
310 | emap_split_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, |
311 | edata_t *lead, size_t size_a, edata_t *trail, size_t size_b) { |
312 | /* |
313 | * We should think about not writing to the lead leaf element. We can |
314 | * get into situations where a racing realloc-like call can disagree |
315 | * with a size lookup request. I think it's fine to declare that these |
316 | * situations are race bugs, but there's an argument to be made that for |
317 | * things like xallocx, a size lookup call should return either the old |
318 | * size or the new size, but not anything else. |
319 | */ |
320 | emap_rtree_write_acquired(tsdn, emap, prepare->lead_elm_a, |
321 | prepare->lead_elm_b, lead, SC_NSIZES, /* slab */ false); |
322 | emap_rtree_write_acquired(tsdn, emap, prepare->trail_elm_a, |
323 | prepare->trail_elm_b, trail, SC_NSIZES, /* slab */ false); |
324 | } |
325 | |
326 | void |
327 | emap_merge_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, |
328 | edata_t *lead, edata_t *trail) { |
329 | EMAP_DECLARE_RTREE_CTX; |
330 | emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, lead, true, false, |
331 | &prepare->lead_elm_a, &prepare->lead_elm_b); |
332 | emap_rtree_leaf_elms_lookup(tsdn, emap, rtree_ctx, trail, true, false, |
333 | &prepare->trail_elm_a, &prepare->trail_elm_b); |
334 | } |
335 | |
336 | void |
337 | emap_merge_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare, |
338 | edata_t *lead, edata_t *trail) { |
339 | rtree_contents_t clear_contents; |
340 | clear_contents.edata = NULL; |
341 | clear_contents.metadata.szind = SC_NSIZES; |
342 | clear_contents.metadata.slab = false; |
343 | clear_contents.metadata.is_head = false; |
344 | clear_contents.metadata.state = (extent_state_t)0; |
345 | |
346 | if (prepare->lead_elm_b != NULL) { |
347 | rtree_leaf_elm_write(tsdn, &emap->rtree, |
348 | prepare->lead_elm_b, clear_contents); |
349 | } |
350 | |
351 | rtree_leaf_elm_t *merged_b; |
352 | if (prepare->trail_elm_b != NULL) { |
353 | rtree_leaf_elm_write(tsdn, &emap->rtree, |
354 | prepare->trail_elm_a, clear_contents); |
355 | merged_b = prepare->trail_elm_b; |
356 | } else { |
357 | merged_b = prepare->trail_elm_a; |
358 | } |
359 | |
360 | emap_rtree_write_acquired(tsdn, emap, prepare->lead_elm_a, merged_b, |
361 | lead, SC_NSIZES, false); |
362 | } |
363 | |
364 | void |
365 | emap_do_assert_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { |
366 | EMAP_DECLARE_RTREE_CTX; |
367 | |
368 | rtree_contents_t contents = rtree_read(tsdn, &emap->rtree, rtree_ctx, |
369 | (uintptr_t)edata_base_get(edata)); |
370 | assert(contents.edata == edata); |
371 | assert(contents.metadata.is_head == edata_is_head_get(edata)); |
372 | assert(contents.metadata.state == edata_state_get(edata)); |
373 | } |
374 | |
375 | void |
376 | emap_do_assert_not_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) { |
377 | emap_full_alloc_ctx_t context1 = {0}; |
378 | emap_full_alloc_ctx_try_lookup(tsdn, emap, edata_base_get(edata), |
379 | &context1); |
380 | assert(context1.edata == NULL); |
381 | |
382 | emap_full_alloc_ctx_t context2 = {0}; |
383 | emap_full_alloc_ctx_try_lookup(tsdn, emap, edata_last_get(edata), |
384 | &context2); |
385 | assert(context2.edata == NULL); |
386 | } |
387 | |