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
38typedef struct rtree_node_elm_s rtree_node_elm_t;
39struct rtree_node_elm_s {
40 atomic_p_t child; /* (rtree_{node,leaf}_elm_t *) */
41};
42
43typedef struct rtree_metadata_s rtree_metadata_t;
44struct 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
51typedef struct rtree_contents_s rtree_contents_t;
52struct 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
61struct 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
87typedef struct rtree_level_s rtree_level_t;
88struct 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
98typedef struct rtree_s rtree_t;
99struct 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 */
116static 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
132bool rtree_new(rtree_t *rtree, base_t *base, bool zeroed);
133
134rtree_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
137JEMALLOC_ALWAYS_INLINE unsigned
138rtree_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
145JEMALLOC_ALWAYS_INLINE uintptr_t
146rtree_leafkey(uintptr_t key) {
147 uintptr_t mask = ~((ZU(1) << rtree_leaf_maskbits()) - 1);
148 return (key & mask);
149}
150
151JEMALLOC_ALWAYS_INLINE size_t
152rtree_cache_direct_map(uintptr_t key) {
153 return (size_t)((key >> rtree_leaf_maskbits()) &
154 (RTREE_CTX_NCACHE - 1));
155}
156
157JEMALLOC_ALWAYS_INLINE uintptr_t
158rtree_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
179JEMALLOC_ALWAYS_INLINE uintptr_t
180rtree_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
186JEMALLOC_ALWAYS_INLINE uintptr_t
187rtree_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
204JEMALLOC_ALWAYS_INLINE rtree_contents_t
205rtree_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
238JEMALLOC_ALWAYS_INLINE rtree_contents_t
239rtree_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
266JEMALLOC_ALWAYS_INLINE void
267rtree_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
281JEMALLOC_ALWAYS_INLINE void
282rtree_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
296JEMALLOC_ALWAYS_INLINE void
297rtree_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). */
308JEMALLOC_ALWAYS_INLINE void
309rtree_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 */
337JEMALLOC_ALWAYS_INLINE bool
338rtree_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
356JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
357rtree_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 */
418static inline bool
419rtree_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
431static inline rtree_contents_t
432rtree_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
440static inline rtree_metadata_t
441rtree_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 */
453static inline bool
454rtree_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
472JEMALLOC_ALWAYS_INLINE void
473rtree_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
503JEMALLOC_ALWAYS_INLINE void
504rtree_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
510JEMALLOC_ALWAYS_INLINE bool
511rtree_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
524static inline void
525rtree_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
541static inline void
542rtree_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