1#ifndef JEMALLOC_INTERNAL_EMAP_H
2#define JEMALLOC_INTERNAL_EMAP_H
3
4#include "jemalloc/internal/base.h"
5#include "jemalloc/internal/rtree.h"
6
7/*
8 * Note: Ends without at semicolon, so that
9 * EMAP_DECLARE_RTREE_CTX;
10 * in uses will avoid empty-statement warnings.
11 */
12#define EMAP_DECLARE_RTREE_CTX \
13 rtree_ctx_t rtree_ctx_fallback; \
14 rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback)
15
16typedef struct emap_s emap_t;
17struct emap_s {
18 rtree_t rtree;
19};
20
21/* Used to pass rtree lookup context down the path. */
22typedef struct emap_alloc_ctx_t emap_alloc_ctx_t;
23struct emap_alloc_ctx_t {
24 szind_t szind;
25 bool slab;
26};
27
28typedef struct emap_full_alloc_ctx_s emap_full_alloc_ctx_t;
29struct emap_full_alloc_ctx_s {
30 szind_t szind;
31 bool slab;
32 edata_t *edata;
33};
34
35bool emap_init(emap_t *emap, base_t *base, bool zeroed);
36
37void emap_remap(tsdn_t *tsdn, emap_t *emap, edata_t *edata, szind_t szind,
38 bool slab);
39
40void emap_update_edata_state(tsdn_t *tsdn, emap_t *emap, edata_t *edata,
41 extent_state_t state);
42
43/*
44 * The two acquire functions below allow accessing neighbor edatas, if it's safe
45 * and valid to do so (i.e. from the same arena, of the same state, etc.). This
46 * is necessary because the ecache locks are state based, and only protect
47 * edatas with the same state. Therefore the neighbor edata's state needs to be
48 * verified first, before chasing the edata pointer. The returned edata will be
49 * in an acquired state, meaning other threads will be prevented from accessing
50 * it, even if technically the edata can still be discovered from the rtree.
51 *
52 * This means, at any moment when holding pointers to edata, either one of the
53 * state based locks is held (and the edatas are all of the protected state), or
54 * the edatas are in an acquired state (e.g. in active or merging state). The
55 * acquire operation itself (changing the edata to an acquired state) is done
56 * under the state locks.
57 */
58edata_t *emap_try_acquire_edata_neighbor(tsdn_t *tsdn, emap_t *emap,
59 edata_t *edata, extent_pai_t pai, extent_state_t expected_state,
60 bool forward);
61edata_t *emap_try_acquire_edata_neighbor_expand(tsdn_t *tsdn, emap_t *emap,
62 edata_t *edata, extent_pai_t pai, extent_state_t expected_state);
63void emap_release_edata(tsdn_t *tsdn, emap_t *emap, edata_t *edata,
64 extent_state_t new_state);
65
66/*
67 * Associate the given edata with its beginning and end address, setting the
68 * szind and slab info appropriately.
69 * Returns true on error (i.e. resource exhaustion).
70 */
71bool emap_register_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata,
72 szind_t szind, bool slab);
73
74/*
75 * Does the same thing, but with the interior of the range, for slab
76 * allocations.
77 *
78 * You might wonder why we don't just have a single emap_register function that
79 * does both depending on the value of 'slab'. The answer is twofold:
80 * - As a practical matter, in places like the extract->split->commit pathway,
81 * we defer the interior operation until we're sure that the commit won't fail
82 * (but we have to register the split boundaries there).
83 * - In general, we're trying to move to a world where the page-specific
84 * allocator doesn't know as much about how the pages it allocates will be
85 * used, and passing a 'slab' parameter everywhere makes that more
86 * complicated.
87 *
88 * Unlike the boundary version, this function can't fail; this is because slabs
89 * can't get big enough to touch a new page that neither of the boundaries
90 * touched, so no allocation is necessary to fill the interior once the boundary
91 * has been touched.
92 */
93void emap_register_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata,
94 szind_t szind);
95
96void emap_deregister_boundary(tsdn_t *tsdn, emap_t *emap, edata_t *edata);
97void emap_deregister_interior(tsdn_t *tsdn, emap_t *emap, edata_t *edata);
98
99typedef struct emap_prepare_s emap_prepare_t;
100struct emap_prepare_s {
101 rtree_leaf_elm_t *lead_elm_a;
102 rtree_leaf_elm_t *lead_elm_b;
103 rtree_leaf_elm_t *trail_elm_a;
104 rtree_leaf_elm_t *trail_elm_b;
105};
106
107/**
108 * These functions the emap metadata management for merging, splitting, and
109 * reusing extents. In particular, they set the boundary mappings from
110 * addresses to edatas. If the result is going to be used as a slab, you
111 * still need to call emap_register_interior on it, though.
112 *
113 * Remap simply changes the szind and slab status of an extent's boundary
114 * mappings. If the extent is not a slab, it doesn't bother with updating the
115 * end mapping (since lookups only occur in the interior of an extent for
116 * slabs). Since the szind and slab status only make sense for active extents,
117 * this should only be called while activating or deactivating an extent.
118 *
119 * Split and merge have a "prepare" and a "commit" portion. The prepare portion
120 * does the operations that can be done without exclusive access to the extent
121 * in question, while the commit variant requires exclusive access to maintain
122 * the emap invariants. The only function that can fail is emap_split_prepare,
123 * and it returns true on failure (at which point the caller shouldn't commit).
124 *
125 * In all cases, "lead" refers to the lower-addressed extent, and trail to the
126 * higher-addressed one. It's the caller's responsibility to set the edata
127 * state appropriately.
128 */
129bool emap_split_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare,
130 edata_t *edata, size_t size_a, edata_t *trail, size_t size_b);
131void emap_split_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare,
132 edata_t *lead, size_t size_a, edata_t *trail, size_t size_b);
133void emap_merge_prepare(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare,
134 edata_t *lead, edata_t *trail);
135void emap_merge_commit(tsdn_t *tsdn, emap_t *emap, emap_prepare_t *prepare,
136 edata_t *lead, edata_t *trail);
137
138/* Assert that the emap's view of the given edata matches the edata's view. */
139void emap_do_assert_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata);
140static inline void
141emap_assert_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) {
142 if (config_debug) {
143 emap_do_assert_mapped(tsdn, emap, edata);
144 }
145}
146
147/* Assert that the given edata isn't in the map. */
148void emap_do_assert_not_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata);
149static inline void
150emap_assert_not_mapped(tsdn_t *tsdn, emap_t *emap, edata_t *edata) {
151 if (config_debug) {
152 emap_do_assert_not_mapped(tsdn, emap, edata);
153 }
154}
155
156JEMALLOC_ALWAYS_INLINE bool
157emap_edata_in_transition(tsdn_t *tsdn, emap_t *emap, edata_t *edata) {
158 assert(config_debug);
159 emap_assert_mapped(tsdn, emap, edata);
160
161 EMAP_DECLARE_RTREE_CTX;
162 rtree_contents_t contents = rtree_read(tsdn, &emap->rtree, rtree_ctx,
163 (uintptr_t)edata_base_get(edata));
164
165 return edata_state_in_transition(contents.metadata.state);
166}
167
168JEMALLOC_ALWAYS_INLINE bool
169emap_edata_is_acquired(tsdn_t *tsdn, emap_t *emap, edata_t *edata) {
170 if (!config_debug) {
171 /* For assertions only. */
172 return false;
173 }
174
175 /*
176 * The edata is considered acquired if no other threads will attempt to
177 * read / write any fields from it. This includes a few cases:
178 *
179 * 1) edata not hooked into emap yet -- This implies the edata just got
180 * allocated or initialized.
181 *
182 * 2) in an active or transition state -- In both cases, the edata can
183 * be discovered from the emap, however the state tracked in the rtree
184 * will prevent other threads from accessing the actual edata.
185 */
186 EMAP_DECLARE_RTREE_CTX;
187 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, &emap->rtree,
188 rtree_ctx, (uintptr_t)edata_base_get(edata), /* dependent */ true,
189 /* init_missing */ false);
190 if (elm == NULL) {
191 return true;
192 }
193 rtree_contents_t contents = rtree_leaf_elm_read(tsdn, &emap->rtree, elm,
194 /* dependent */ true);
195 if (contents.edata == NULL ||
196 contents.metadata.state == extent_state_active ||
197 edata_state_in_transition(contents.metadata.state)) {
198 return true;
199 }
200
201 return false;
202}
203
204JEMALLOC_ALWAYS_INLINE void
205extent_assert_can_coalesce(const edata_t *inner, const edata_t *outer) {
206 assert(edata_arena_ind_get(inner) == edata_arena_ind_get(outer));
207 assert(edata_pai_get(inner) == edata_pai_get(outer));
208 assert(edata_committed_get(inner) == edata_committed_get(outer));
209 assert(edata_state_get(inner) == extent_state_active);
210 assert(edata_state_get(outer) == extent_state_merging);
211 assert(!edata_guarded_get(inner) && !edata_guarded_get(outer));
212 assert(edata_base_get(inner) == edata_past_get(outer) ||
213 edata_base_get(outer) == edata_past_get(inner));
214}
215
216JEMALLOC_ALWAYS_INLINE void
217extent_assert_can_expand(const edata_t *original, const edata_t *expand) {
218 assert(edata_arena_ind_get(original) == edata_arena_ind_get(expand));
219 assert(edata_pai_get(original) == edata_pai_get(expand));
220 assert(edata_state_get(original) == extent_state_active);
221 assert(edata_state_get(expand) == extent_state_merging);
222 assert(edata_past_get(original) == edata_base_get(expand));
223}
224
225JEMALLOC_ALWAYS_INLINE edata_t *
226emap_edata_lookup(tsdn_t *tsdn, emap_t *emap, const void *ptr) {
227 EMAP_DECLARE_RTREE_CTX;
228
229 return rtree_read(tsdn, &emap->rtree, rtree_ctx, (uintptr_t)ptr).edata;
230}
231
232/* Fills in alloc_ctx with the info in the map. */
233JEMALLOC_ALWAYS_INLINE void
234emap_alloc_ctx_lookup(tsdn_t *tsdn, emap_t *emap, const void *ptr,
235 emap_alloc_ctx_t *alloc_ctx) {
236 EMAP_DECLARE_RTREE_CTX;
237
238 rtree_metadata_t metadata = rtree_metadata_read(tsdn, &emap->rtree,
239 rtree_ctx, (uintptr_t)ptr);
240 alloc_ctx->szind = metadata.szind;
241 alloc_ctx->slab = metadata.slab;
242}
243
244/* The pointer must be mapped. */
245JEMALLOC_ALWAYS_INLINE void
246emap_full_alloc_ctx_lookup(tsdn_t *tsdn, emap_t *emap, const void *ptr,
247 emap_full_alloc_ctx_t *full_alloc_ctx) {
248 EMAP_DECLARE_RTREE_CTX;
249
250 rtree_contents_t contents = rtree_read(tsdn, &emap->rtree, rtree_ctx,
251 (uintptr_t)ptr);
252 full_alloc_ctx->edata = contents.edata;
253 full_alloc_ctx->szind = contents.metadata.szind;
254 full_alloc_ctx->slab = contents.metadata.slab;
255}
256
257/*
258 * The pointer is allowed to not be mapped.
259 *
260 * Returns true when the pointer is not present.
261 */
262JEMALLOC_ALWAYS_INLINE bool
263emap_full_alloc_ctx_try_lookup(tsdn_t *tsdn, emap_t *emap, const void *ptr,
264 emap_full_alloc_ctx_t *full_alloc_ctx) {
265 EMAP_DECLARE_RTREE_CTX;
266
267 rtree_contents_t contents;
268 bool err = rtree_read_independent(tsdn, &emap->rtree, rtree_ctx,
269 (uintptr_t)ptr, &contents);
270 if (err) {
271 return true;
272 }
273 full_alloc_ctx->edata = contents.edata;
274 full_alloc_ctx->szind = contents.metadata.szind;
275 full_alloc_ctx->slab = contents.metadata.slab;
276 return false;
277}
278
279/*
280 * Only used on the fastpath of free. Returns true when cannot be fulfilled by
281 * fast path, e.g. when the metadata key is not cached.
282 */
283JEMALLOC_ALWAYS_INLINE bool
284emap_alloc_ctx_try_lookup_fast(tsd_t *tsd, emap_t *emap, const void *ptr,
285 emap_alloc_ctx_t *alloc_ctx) {
286 /* Use the unsafe getter since this may gets called during exit. */
287 rtree_ctx_t *rtree_ctx = tsd_rtree_ctxp_get_unsafe(tsd);
288
289 rtree_metadata_t metadata;
290 bool err = rtree_metadata_try_read_fast(tsd_tsdn(tsd), &emap->rtree,
291 rtree_ctx, (uintptr_t)ptr, &metadata);
292 if (err) {
293 return true;
294 }
295 alloc_ctx->szind = metadata.szind;
296 alloc_ctx->slab = metadata.slab;
297 return false;
298}
299
300/*
301 * We want to do batch lookups out of the cache bins, which use
302 * cache_bin_ptr_array_get to access the i'th element of the bin (since they
303 * invert usual ordering in deciding what to flush). This lets the emap avoid
304 * caring about its caller's ordering.
305 */
306typedef const void *(*emap_ptr_getter)(void *ctx, size_t ind);
307/*
308 * This allows size-checking assertions, which we can only do while we're in the
309 * process of edata lookups.
310 */
311typedef void (*emap_metadata_visitor)(void *ctx, emap_full_alloc_ctx_t *alloc_ctx);
312
313typedef union emap_batch_lookup_result_u emap_batch_lookup_result_t;
314union emap_batch_lookup_result_u {
315 edata_t *edata;
316 rtree_leaf_elm_t *rtree_leaf;
317};
318
319JEMALLOC_ALWAYS_INLINE void
320emap_edata_lookup_batch(tsd_t *tsd, emap_t *emap, size_t nptrs,
321 emap_ptr_getter ptr_getter, void *ptr_getter_ctx,
322 emap_metadata_visitor metadata_visitor, void *metadata_visitor_ctx,
323 emap_batch_lookup_result_t *result) {
324 /* Avoids null-checking tsdn in the loop below. */
325 util_assume(tsd != NULL);
326 rtree_ctx_t *rtree_ctx = tsd_rtree_ctxp_get(tsd);
327
328 for (size_t i = 0; i < nptrs; i++) {
329 const void *ptr = ptr_getter(ptr_getter_ctx, i);
330 /*
331 * Reuse the edatas array as a temp buffer, lying a little about
332 * the types.
333 */
334 result[i].rtree_leaf = rtree_leaf_elm_lookup(tsd_tsdn(tsd),
335 &emap->rtree, rtree_ctx, (uintptr_t)ptr,
336 /* dependent */ true, /* init_missing */ false);
337 }
338
339 for (size_t i = 0; i < nptrs; i++) {
340 rtree_leaf_elm_t *elm = result[i].rtree_leaf;
341 rtree_contents_t contents = rtree_leaf_elm_read(tsd_tsdn(tsd),
342 &emap->rtree, elm, /* dependent */ true);
343 result[i].edata = contents.edata;
344 emap_full_alloc_ctx_t alloc_ctx;
345 /*
346 * Not all these fields are read in practice by the metadata
347 * visitor. But the compiler can easily optimize away the ones
348 * that aren't, so no sense in being incomplete.
349 */
350 alloc_ctx.szind = contents.metadata.szind;
351 alloc_ctx.slab = contents.metadata.slab;
352 alloc_ctx.edata = contents.edata;
353 metadata_visitor(metadata_visitor_ctx, &alloc_ctx);
354 }
355}
356
357#endif /* JEMALLOC_INTERNAL_EMAP_H */
358