1 | #ifndef JEMALLOC_INTERNAL_RTREE_H |
2 | #define JEMALLOC_INTERNAL_RTREE_H |
3 | |
4 | #include "jemalloc/internal/atomic.h" |
5 | #include "jemalloc/internal/mutex.h" |
6 | #include "jemalloc/internal/rtree_tsd.h" |
7 | #include "jemalloc/internal/sc.h" |
8 | #include "jemalloc/internal/tsd.h" |
9 | |
10 | /* |
11 | * This radix tree implementation is tailored to the singular purpose of |
12 | * associating metadata with extents that are currently owned by jemalloc. |
13 | * |
14 | ******************************************************************************* |
15 | */ |
16 | |
17 | /* Number of high insignificant bits. */ |
18 | #define RTREE_NHIB ((1U << (LG_SIZEOF_PTR+3)) - LG_VADDR) |
19 | /* Number of low insigificant bits. */ |
20 | #define RTREE_NLIB LG_PAGE |
21 | /* Number of significant bits. */ |
22 | #define RTREE_NSB (LG_VADDR - RTREE_NLIB) |
23 | /* Number of levels in radix tree. */ |
24 | #if RTREE_NSB <= 10 |
25 | # define RTREE_HEIGHT 1 |
26 | #elif RTREE_NSB <= 36 |
27 | # define RTREE_HEIGHT 2 |
28 | #elif RTREE_NSB <= 52 |
29 | # define RTREE_HEIGHT 3 |
30 | #else |
31 | # error Unsupported number of significant virtual address bits |
32 | #endif |
33 | /* Use compact leaf representation if virtual address encoding allows. */ |
34 | #if RTREE_NHIB >= LG_CEIL(SC_NSIZES) |
35 | # define RTREE_LEAF_COMPACT |
36 | #endif |
37 | |
38 | typedef struct rtree_node_elm_s rtree_node_elm_t; |
39 | struct rtree_node_elm_s { |
40 | atomic_p_t child; /* (rtree_{node,leaf}_elm_t *) */ |
41 | }; |
42 | |
43 | typedef struct rtree_metadata_s rtree_metadata_t; |
44 | struct rtree_metadata_s { |
45 | szind_t szind; |
46 | extent_state_t state; /* Mirrors edata->state. */ |
47 | bool is_head; /* Mirrors edata->is_head. */ |
48 | bool slab; |
49 | }; |
50 | |
51 | typedef struct rtree_contents_s rtree_contents_t; |
52 | struct rtree_contents_s { |
53 | edata_t *edata; |
54 | rtree_metadata_t metadata; |
55 | }; |
56 | |
57 | #define RTREE_LEAF_STATE_WIDTH EDATA_BITS_STATE_WIDTH |
58 | #define RTREE_LEAF_STATE_SHIFT 2 |
59 | #define RTREE_LEAF_STATE_MASK MASK(RTREE_LEAF_STATE_WIDTH, RTREE_LEAF_STATE_SHIFT) |
60 | |
61 | struct rtree_leaf_elm_s { |
62 | #ifdef RTREE_LEAF_COMPACT |
63 | /* |
64 | * Single pointer-width field containing all three leaf element fields. |
65 | * For example, on a 64-bit x64 system with 48 significant virtual |
66 | * memory address bits, the index, edata, and slab fields are packed as |
67 | * such: |
68 | * |
69 | * x: index |
70 | * e: edata |
71 | * s: state |
72 | * h: is_head |
73 | * b: slab |
74 | * |
75 | * 00000000 xxxxxxxx eeeeeeee [...] eeeeeeee e00ssshb |
76 | */ |
77 | atomic_p_t le_bits; |
78 | #else |
79 | atomic_p_t le_edata; /* (edata_t *) */ |
80 | /* |
81 | * From high to low bits: szind (8 bits), state (4 bits), is_head, slab |
82 | */ |
83 | atomic_u_t le_metadata; |
84 | #endif |
85 | }; |
86 | |
87 | typedef struct rtree_level_s rtree_level_t; |
88 | struct rtree_level_s { |
89 | /* Number of key bits distinguished by this level. */ |
90 | unsigned bits; |
91 | /* |
92 | * Cumulative number of key bits distinguished by traversing to |
93 | * corresponding tree level. |
94 | */ |
95 | unsigned cumbits; |
96 | }; |
97 | |
98 | typedef struct rtree_s rtree_t; |
99 | struct rtree_s { |
100 | base_t *base; |
101 | malloc_mutex_t init_lock; |
102 | /* Number of elements based on rtree_levels[0].bits. */ |
103 | #if RTREE_HEIGHT > 1 |
104 | rtree_node_elm_t root[1U << (RTREE_NSB/RTREE_HEIGHT)]; |
105 | #else |
106 | rtree_leaf_elm_t root[1U << (RTREE_NSB/RTREE_HEIGHT)]; |
107 | #endif |
108 | }; |
109 | |
110 | /* |
111 | * Split the bits into one to three partitions depending on number of |
112 | * significant bits. It the number of bits does not divide evenly into the |
113 | * number of levels, place one remainder bit per level starting at the leaf |
114 | * level. |
115 | */ |
116 | static const rtree_level_t rtree_levels[] = { |
117 | #if RTREE_HEIGHT == 1 |
118 | {RTREE_NSB, RTREE_NHIB + RTREE_NSB} |
119 | #elif RTREE_HEIGHT == 2 |
120 | {RTREE_NSB/2, RTREE_NHIB + RTREE_NSB/2}, |
121 | {RTREE_NSB/2 + RTREE_NSB%2, RTREE_NHIB + RTREE_NSB} |
122 | #elif RTREE_HEIGHT == 3 |
123 | {RTREE_NSB/3, RTREE_NHIB + RTREE_NSB/3}, |
124 | {RTREE_NSB/3 + RTREE_NSB%3/2, |
125 | RTREE_NHIB + RTREE_NSB/3*2 + RTREE_NSB%3/2}, |
126 | {RTREE_NSB/3 + RTREE_NSB%3 - RTREE_NSB%3/2, RTREE_NHIB + RTREE_NSB} |
127 | #else |
128 | # error Unsupported rtree height |
129 | #endif |
130 | }; |
131 | |
132 | bool rtree_new(rtree_t *rtree, base_t *base, bool zeroed); |
133 | |
134 | rtree_leaf_elm_t *rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, |
135 | rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent, bool init_missing); |
136 | |
137 | JEMALLOC_ALWAYS_INLINE unsigned |
138 | rtree_leaf_maskbits(void) { |
139 | unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3); |
140 | unsigned cumbits = (rtree_levels[RTREE_HEIGHT-1].cumbits - |
141 | rtree_levels[RTREE_HEIGHT-1].bits); |
142 | return ptrbits - cumbits; |
143 | } |
144 | |
145 | JEMALLOC_ALWAYS_INLINE uintptr_t |
146 | rtree_leafkey(uintptr_t key) { |
147 | uintptr_t mask = ~((ZU(1) << rtree_leaf_maskbits()) - 1); |
148 | return (key & mask); |
149 | } |
150 | |
151 | JEMALLOC_ALWAYS_INLINE size_t |
152 | rtree_cache_direct_map(uintptr_t key) { |
153 | return (size_t)((key >> rtree_leaf_maskbits()) & |
154 | (RTREE_CTX_NCACHE - 1)); |
155 | } |
156 | |
157 | JEMALLOC_ALWAYS_INLINE uintptr_t |
158 | rtree_subkey(uintptr_t key, unsigned level) { |
159 | unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3); |
160 | unsigned cumbits = rtree_levels[level].cumbits; |
161 | unsigned shiftbits = ptrbits - cumbits; |
162 | unsigned maskbits = rtree_levels[level].bits; |
163 | uintptr_t mask = (ZU(1) << maskbits) - 1; |
164 | return ((key >> shiftbits) & mask); |
165 | } |
166 | |
167 | /* |
168 | * Atomic getters. |
169 | * |
170 | * dependent: Reading a value on behalf of a pointer to a valid allocation |
171 | * is guaranteed to be a clean read even without synchronization, |
172 | * because the rtree update became visible in memory before the |
173 | * pointer came into existence. |
174 | * !dependent: An arbitrary read, e.g. on behalf of ivsalloc(), may not be |
175 | * dependent on a previous rtree write, which means a stale read |
176 | * could result if synchronization were omitted here. |
177 | */ |
178 | # ifdef RTREE_LEAF_COMPACT |
179 | JEMALLOC_ALWAYS_INLINE uintptr_t |
180 | rtree_leaf_elm_bits_read(tsdn_t *tsdn, rtree_t *rtree, |
181 | rtree_leaf_elm_t *elm, bool dependent) { |
182 | return (uintptr_t)atomic_load_p(&elm->le_bits, dependent |
183 | ? ATOMIC_RELAXED : ATOMIC_ACQUIRE); |
184 | } |
185 | |
186 | JEMALLOC_ALWAYS_INLINE uintptr_t |
187 | rtree_leaf_elm_bits_encode(rtree_contents_t contents) { |
188 | assert((uintptr_t)contents.edata % (uintptr_t)EDATA_ALIGNMENT == 0); |
189 | uintptr_t edata_bits = (uintptr_t)contents.edata |
190 | & (((uintptr_t)1 << LG_VADDR) - 1); |
191 | |
192 | uintptr_t szind_bits = (uintptr_t)contents.metadata.szind << LG_VADDR; |
193 | uintptr_t slab_bits = (uintptr_t)contents.metadata.slab; |
194 | uintptr_t is_head_bits = (uintptr_t)contents.metadata.is_head << 1; |
195 | uintptr_t state_bits = (uintptr_t)contents.metadata.state << |
196 | RTREE_LEAF_STATE_SHIFT; |
197 | uintptr_t metadata_bits = szind_bits | state_bits | is_head_bits | |
198 | slab_bits; |
199 | assert((edata_bits & metadata_bits) == 0); |
200 | |
201 | return edata_bits | metadata_bits; |
202 | } |
203 | |
204 | JEMALLOC_ALWAYS_INLINE rtree_contents_t |
205 | rtree_leaf_elm_bits_decode(uintptr_t bits) { |
206 | rtree_contents_t contents; |
207 | /* Do the easy things first. */ |
208 | contents.metadata.szind = bits >> LG_VADDR; |
209 | contents.metadata.slab = (bool)(bits & 1); |
210 | contents.metadata.is_head = (bool)(bits & (1 << 1)); |
211 | |
212 | uintptr_t state_bits = (bits & RTREE_LEAF_STATE_MASK) >> |
213 | RTREE_LEAF_STATE_SHIFT; |
214 | assert(state_bits <= extent_state_max); |
215 | contents.metadata.state = (extent_state_t)state_bits; |
216 | |
217 | uintptr_t low_bit_mask = ~((uintptr_t)EDATA_ALIGNMENT - 1); |
218 | # ifdef __aarch64__ |
219 | /* |
220 | * aarch64 doesn't sign extend the highest virtual address bit to set |
221 | * the higher ones. Instead, the high bits get zeroed. |
222 | */ |
223 | uintptr_t high_bit_mask = ((uintptr_t)1 << LG_VADDR) - 1; |
224 | /* Mask off metadata. */ |
225 | uintptr_t mask = high_bit_mask & low_bit_mask; |
226 | contents.edata = (edata_t *)(bits & mask); |
227 | # else |
228 | /* Restore sign-extended high bits, mask metadata bits. */ |
229 | contents.edata = (edata_t *)((uintptr_t)((intptr_t)(bits << RTREE_NHIB) |
230 | >> RTREE_NHIB) & low_bit_mask); |
231 | # endif |
232 | assert((uintptr_t)contents.edata % (uintptr_t)EDATA_ALIGNMENT == 0); |
233 | return contents; |
234 | } |
235 | |
236 | # endif /* RTREE_LEAF_COMPACT */ |
237 | |
238 | JEMALLOC_ALWAYS_INLINE rtree_contents_t |
239 | rtree_leaf_elm_read(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, |
240 | bool dependent) { |
241 | #ifdef RTREE_LEAF_COMPACT |
242 | uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent); |
243 | rtree_contents_t contents = rtree_leaf_elm_bits_decode(bits); |
244 | return contents; |
245 | #else |
246 | rtree_contents_t contents; |
247 | unsigned metadata_bits = atomic_load_u(&elm->le_metadata, dependent |
248 | ? ATOMIC_RELAXED : ATOMIC_ACQUIRE); |
249 | contents.metadata.slab = (bool)(metadata_bits & 1); |
250 | contents.metadata.is_head = (bool)(metadata_bits & (1 << 1)); |
251 | |
252 | uintptr_t state_bits = (metadata_bits & RTREE_LEAF_STATE_MASK) >> |
253 | RTREE_LEAF_STATE_SHIFT; |
254 | assert(state_bits <= extent_state_max); |
255 | contents.metadata.state = (extent_state_t)state_bits; |
256 | contents.metadata.szind = metadata_bits >> (RTREE_LEAF_STATE_SHIFT + |
257 | RTREE_LEAF_STATE_WIDTH); |
258 | |
259 | contents.edata = (edata_t *)atomic_load_p(&elm->le_edata, dependent |
260 | ? ATOMIC_RELAXED : ATOMIC_ACQUIRE); |
261 | |
262 | return contents; |
263 | #endif |
264 | } |
265 | |
266 | JEMALLOC_ALWAYS_INLINE void |
267 | rtree_contents_encode(rtree_contents_t contents, void **bits, |
268 | unsigned *additional) { |
269 | #ifdef RTREE_LEAF_COMPACT |
270 | *bits = (void *)rtree_leaf_elm_bits_encode(contents); |
271 | #else |
272 | *additional = (unsigned)contents.metadata.slab |
273 | | ((unsigned)contents.metadata.is_head << 1) |
274 | | ((unsigned)contents.metadata.state << RTREE_LEAF_STATE_SHIFT) |
275 | | ((unsigned)contents.metadata.szind << (RTREE_LEAF_STATE_SHIFT + |
276 | RTREE_LEAF_STATE_WIDTH)); |
277 | *bits = contents.edata; |
278 | #endif |
279 | } |
280 | |
281 | JEMALLOC_ALWAYS_INLINE void |
282 | rtree_leaf_elm_write_commit(tsdn_t *tsdn, rtree_t *rtree, |
283 | rtree_leaf_elm_t *elm, void *bits, unsigned additional) { |
284 | #ifdef RTREE_LEAF_COMPACT |
285 | atomic_store_p(&elm->le_bits, bits, ATOMIC_RELEASE); |
286 | #else |
287 | atomic_store_u(&elm->le_metadata, additional, ATOMIC_RELEASE); |
288 | /* |
289 | * Write edata last, since the element is atomically considered valid |
290 | * as soon as the edata field is non-NULL. |
291 | */ |
292 | atomic_store_p(&elm->le_edata, bits, ATOMIC_RELEASE); |
293 | #endif |
294 | } |
295 | |
296 | JEMALLOC_ALWAYS_INLINE void |
297 | rtree_leaf_elm_write(tsdn_t *tsdn, rtree_t *rtree, |
298 | rtree_leaf_elm_t *elm, rtree_contents_t contents) { |
299 | assert((uintptr_t)contents.edata % EDATA_ALIGNMENT == 0); |
300 | void *bits; |
301 | unsigned additional; |
302 | |
303 | rtree_contents_encode(contents, &bits, &additional); |
304 | rtree_leaf_elm_write_commit(tsdn, rtree, elm, bits, additional); |
305 | } |
306 | |
307 | /* The state field can be updated independently (and more frequently). */ |
308 | JEMALLOC_ALWAYS_INLINE void |
309 | rtree_leaf_elm_state_update(tsdn_t *tsdn, rtree_t *rtree, |
310 | rtree_leaf_elm_t *elm1, rtree_leaf_elm_t *elm2, extent_state_t state) { |
311 | assert(elm1 != NULL); |
312 | #ifdef RTREE_LEAF_COMPACT |
313 | uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm1, |
314 | /* dependent */ true); |
315 | bits &= ~RTREE_LEAF_STATE_MASK; |
316 | bits |= state << RTREE_LEAF_STATE_SHIFT; |
317 | atomic_store_p(&elm1->le_bits, (void *)bits, ATOMIC_RELEASE); |
318 | if (elm2 != NULL) { |
319 | atomic_store_p(&elm2->le_bits, (void *)bits, ATOMIC_RELEASE); |
320 | } |
321 | #else |
322 | unsigned bits = atomic_load_u(&elm1->le_metadata, ATOMIC_RELAXED); |
323 | bits &= ~RTREE_LEAF_STATE_MASK; |
324 | bits |= state << RTREE_LEAF_STATE_SHIFT; |
325 | atomic_store_u(&elm1->le_metadata, bits, ATOMIC_RELEASE); |
326 | if (elm2 != NULL) { |
327 | atomic_store_u(&elm2->le_metadata, bits, ATOMIC_RELEASE); |
328 | } |
329 | #endif |
330 | } |
331 | |
332 | /* |
333 | * Tries to look up the key in the L1 cache, returning false if there's a hit, or |
334 | * true if there's a miss. |
335 | * Key is allowed to be NULL; returns true in this case. |
336 | */ |
337 | JEMALLOC_ALWAYS_INLINE bool |
338 | rtree_leaf_elm_lookup_fast(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
339 | uintptr_t key, rtree_leaf_elm_t **elm) { |
340 | size_t slot = rtree_cache_direct_map(key); |
341 | uintptr_t leafkey = rtree_leafkey(key); |
342 | assert(leafkey != RTREE_LEAFKEY_INVALID); |
343 | |
344 | if (unlikely(rtree_ctx->cache[slot].leafkey != leafkey)) { |
345 | return true; |
346 | } |
347 | |
348 | rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf; |
349 | assert(leaf != NULL); |
350 | uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); |
351 | *elm = &leaf[subkey]; |
352 | |
353 | return false; |
354 | } |
355 | |
356 | JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t * |
357 | rtree_leaf_elm_lookup(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
358 | uintptr_t key, bool dependent, bool init_missing) { |
359 | assert(key != 0); |
360 | assert(!dependent || !init_missing); |
361 | |
362 | size_t slot = rtree_cache_direct_map(key); |
363 | uintptr_t leafkey = rtree_leafkey(key); |
364 | assert(leafkey != RTREE_LEAFKEY_INVALID); |
365 | |
366 | /* Fast path: L1 direct mapped cache. */ |
367 | if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) { |
368 | rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf; |
369 | assert(leaf != NULL); |
370 | uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); |
371 | return &leaf[subkey]; |
372 | } |
373 | /* |
374 | * Search the L2 LRU cache. On hit, swap the matching element into the |
375 | * slot in L1 cache, and move the position in L2 up by 1. |
376 | */ |
377 | #define RTREE_CACHE_CHECK_L2(i) do { \ |
378 | if (likely(rtree_ctx->l2_cache[i].leafkey == leafkey)) { \ |
379 | rtree_leaf_elm_t *leaf = rtree_ctx->l2_cache[i].leaf; \ |
380 | assert(leaf != NULL); \ |
381 | if (i > 0) { \ |
382 | /* Bubble up by one. */ \ |
383 | rtree_ctx->l2_cache[i].leafkey = \ |
384 | rtree_ctx->l2_cache[i - 1].leafkey; \ |
385 | rtree_ctx->l2_cache[i].leaf = \ |
386 | rtree_ctx->l2_cache[i - 1].leaf; \ |
387 | rtree_ctx->l2_cache[i - 1].leafkey = \ |
388 | rtree_ctx->cache[slot].leafkey; \ |
389 | rtree_ctx->l2_cache[i - 1].leaf = \ |
390 | rtree_ctx->cache[slot].leaf; \ |
391 | } else { \ |
392 | rtree_ctx->l2_cache[0].leafkey = \ |
393 | rtree_ctx->cache[slot].leafkey; \ |
394 | rtree_ctx->l2_cache[0].leaf = \ |
395 | rtree_ctx->cache[slot].leaf; \ |
396 | } \ |
397 | rtree_ctx->cache[slot].leafkey = leafkey; \ |
398 | rtree_ctx->cache[slot].leaf = leaf; \ |
399 | uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); \ |
400 | return &leaf[subkey]; \ |
401 | } \ |
402 | } while (0) |
403 | /* Check the first cache entry. */ |
404 | RTREE_CACHE_CHECK_L2(0); |
405 | /* Search the remaining cache elements. */ |
406 | for (unsigned i = 1; i < RTREE_CTX_NCACHE_L2; i++) { |
407 | RTREE_CACHE_CHECK_L2(i); |
408 | } |
409 | #undef RTREE_CACHE_CHECK_L2 |
410 | |
411 | return rtree_leaf_elm_lookup_hard(tsdn, rtree, rtree_ctx, key, |
412 | dependent, init_missing); |
413 | } |
414 | |
415 | /* |
416 | * Returns true on lookup failure. |
417 | */ |
418 | static inline bool |
419 | rtree_read_independent(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
420 | uintptr_t key, rtree_contents_t *r_contents) { |
421 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, |
422 | key, /* dependent */ false, /* init_missing */ false); |
423 | if (elm == NULL) { |
424 | return true; |
425 | } |
426 | *r_contents = rtree_leaf_elm_read(tsdn, rtree, elm, |
427 | /* dependent */ false); |
428 | return false; |
429 | } |
430 | |
431 | static inline rtree_contents_t |
432 | rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
433 | uintptr_t key) { |
434 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, |
435 | key, /* dependent */ true, /* init_missing */ false); |
436 | assert(elm != NULL); |
437 | return rtree_leaf_elm_read(tsdn, rtree, elm, /* dependent */ true); |
438 | } |
439 | |
440 | static inline rtree_metadata_t |
441 | rtree_metadata_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
442 | uintptr_t key) { |
443 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, |
444 | key, /* dependent */ true, /* init_missing */ false); |
445 | assert(elm != NULL); |
446 | return rtree_leaf_elm_read(tsdn, rtree, elm, |
447 | /* dependent */ true).metadata; |
448 | } |
449 | |
450 | /* |
451 | * Returns true when the request cannot be fulfilled by fastpath. |
452 | */ |
453 | static inline bool |
454 | rtree_metadata_try_read_fast(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
455 | uintptr_t key, rtree_metadata_t *r_rtree_metadata) { |
456 | rtree_leaf_elm_t *elm; |
457 | /* |
458 | * Should check the bool return value (lookup success or not) instead of |
459 | * elm == NULL (which will result in an extra branch). This is because |
460 | * when the cache lookup succeeds, there will never be a NULL pointer |
461 | * returned (which is unknown to the compiler). |
462 | */ |
463 | if (rtree_leaf_elm_lookup_fast(tsdn, rtree, rtree_ctx, key, &elm)) { |
464 | return true; |
465 | } |
466 | assert(elm != NULL); |
467 | *r_rtree_metadata = rtree_leaf_elm_read(tsdn, rtree, elm, |
468 | /* dependent */ true).metadata; |
469 | return false; |
470 | } |
471 | |
472 | JEMALLOC_ALWAYS_INLINE void |
473 | rtree_write_range_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
474 | uintptr_t base, uintptr_t end, rtree_contents_t contents, bool clearing) { |
475 | assert((base & PAGE_MASK) == 0 && (end & PAGE_MASK) == 0); |
476 | /* |
477 | * Only used for emap_(de)register_interior, which implies the |
478 | * boundaries have been registered already. Therefore all the lookups |
479 | * are dependent w/o init_missing, assuming the range spans across at |
480 | * most 2 rtree leaf nodes (each covers 1 GiB of vaddr). |
481 | */ |
482 | void *bits; |
483 | unsigned additional; |
484 | rtree_contents_encode(contents, &bits, &additional); |
485 | |
486 | rtree_leaf_elm_t *elm = NULL; /* Dead store. */ |
487 | for (uintptr_t addr = base; addr <= end; addr += PAGE) { |
488 | if (addr == base || |
489 | (addr & ((ZU(1) << rtree_leaf_maskbits()) - 1)) == 0) { |
490 | elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, addr, |
491 | /* dependent */ true, /* init_missing */ false); |
492 | assert(elm != NULL); |
493 | } |
494 | assert(elm == rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, addr, |
495 | /* dependent */ true, /* init_missing */ false)); |
496 | assert(!clearing || rtree_leaf_elm_read(tsdn, rtree, elm, |
497 | /* dependent */ true).edata != NULL); |
498 | rtree_leaf_elm_write_commit(tsdn, rtree, elm, bits, additional); |
499 | elm++; |
500 | } |
501 | } |
502 | |
503 | JEMALLOC_ALWAYS_INLINE void |
504 | rtree_write_range(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
505 | uintptr_t base, uintptr_t end, rtree_contents_t contents) { |
506 | rtree_write_range_impl(tsdn, rtree, rtree_ctx, base, end, contents, |
507 | /* clearing */ false); |
508 | } |
509 | |
510 | JEMALLOC_ALWAYS_INLINE bool |
511 | rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key, |
512 | rtree_contents_t contents) { |
513 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, |
514 | key, /* dependent */ false, /* init_missing */ true); |
515 | if (elm == NULL) { |
516 | return true; |
517 | } |
518 | |
519 | rtree_leaf_elm_write(tsdn, rtree, elm, contents); |
520 | |
521 | return false; |
522 | } |
523 | |
524 | static inline void |
525 | rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
526 | uintptr_t key) { |
527 | rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, |
528 | key, /* dependent */ true, /* init_missing */ false); |
529 | assert(elm != NULL); |
530 | assert(rtree_leaf_elm_read(tsdn, rtree, elm, |
531 | /* dependent */ true).edata != NULL); |
532 | rtree_contents_t contents; |
533 | contents.edata = NULL; |
534 | contents.metadata.szind = SC_NSIZES; |
535 | contents.metadata.slab = false; |
536 | contents.metadata.is_head = false; |
537 | contents.metadata.state = (extent_state_t)0; |
538 | rtree_leaf_elm_write(tsdn, rtree, elm, contents); |
539 | } |
540 | |
541 | static inline void |
542 | rtree_clear_range(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, |
543 | uintptr_t base, uintptr_t end) { |
544 | rtree_contents_t contents; |
545 | contents.edata = NULL; |
546 | contents.metadata.szind = SC_NSIZES; |
547 | contents.metadata.slab = false; |
548 | contents.metadata.is_head = false; |
549 | contents.metadata.state = (extent_state_t)0; |
550 | rtree_write_range_impl(tsdn, rtree, rtree_ctx, base, end, contents, |
551 | /* clearing */ true); |
552 | } |
553 | |
554 | #endif /* JEMALLOC_INTERNAL_RTREE_H */ |
555 | |