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/* Needed for initialization only. */
39#define RTREE_LEAFKEY_INVALID ((uintptr_t)1)
40
41typedef struct rtree_node_elm_s rtree_node_elm_t;
42struct rtree_node_elm_s {
43 atomic_p_t child; /* (rtree_{node,leaf}_elm_t *) */
44};
45
46struct rtree_leaf_elm_s {
47#ifdef RTREE_LEAF_COMPACT
48 /*
49 * Single pointer-width field containing all three leaf element fields.
50 * For example, on a 64-bit x64 system with 48 significant virtual
51 * memory address bits, the index, extent, and slab fields are packed as
52 * such:
53 *
54 * x: index
55 * e: extent
56 * b: slab
57 *
58 * 00000000 xxxxxxxx eeeeeeee [...] eeeeeeee eeee000b
59 */
60 atomic_p_t le_bits;
61#else
62 atomic_p_t le_extent; /* (extent_t *) */
63 atomic_u_t le_szind; /* (szind_t) */
64 atomic_b_t le_slab; /* (bool) */
65#endif
66};
67
68typedef struct rtree_level_s rtree_level_t;
69struct rtree_level_s {
70 /* Number of key bits distinguished by this level. */
71 unsigned bits;
72 /*
73 * Cumulative number of key bits distinguished by traversing to
74 * corresponding tree level.
75 */
76 unsigned cumbits;
77};
78
79typedef struct rtree_s rtree_t;
80struct rtree_s {
81 malloc_mutex_t init_lock;
82 /* Number of elements based on rtree_levels[0].bits. */
83#if RTREE_HEIGHT > 1
84 rtree_node_elm_t root[1U << (RTREE_NSB/RTREE_HEIGHT)];
85#else
86 rtree_leaf_elm_t root[1U << (RTREE_NSB/RTREE_HEIGHT)];
87#endif
88};
89
90/*
91 * Split the bits into one to three partitions depending on number of
92 * significant bits. It the number of bits does not divide evenly into the
93 * number of levels, place one remainder bit per level starting at the leaf
94 * level.
95 */
96static const rtree_level_t rtree_levels[] = {
97#if RTREE_HEIGHT == 1
98 {RTREE_NSB, RTREE_NHIB + RTREE_NSB}
99#elif RTREE_HEIGHT == 2
100 {RTREE_NSB/2, RTREE_NHIB + RTREE_NSB/2},
101 {RTREE_NSB/2 + RTREE_NSB%2, RTREE_NHIB + RTREE_NSB}
102#elif RTREE_HEIGHT == 3
103 {RTREE_NSB/3, RTREE_NHIB + RTREE_NSB/3},
104 {RTREE_NSB/3 + RTREE_NSB%3/2,
105 RTREE_NHIB + RTREE_NSB/3*2 + RTREE_NSB%3/2},
106 {RTREE_NSB/3 + RTREE_NSB%3 - RTREE_NSB%3/2, RTREE_NHIB + RTREE_NSB}
107#else
108# error Unsupported rtree height
109#endif
110};
111
112bool rtree_new(rtree_t *rtree, bool zeroed);
113
114typedef rtree_node_elm_t *(rtree_node_alloc_t)(tsdn_t *, rtree_t *, size_t);
115extern rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc;
116
117typedef rtree_leaf_elm_t *(rtree_leaf_alloc_t)(tsdn_t *, rtree_t *, size_t);
118extern rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc;
119
120typedef void (rtree_node_dalloc_t)(tsdn_t *, rtree_t *, rtree_node_elm_t *);
121extern rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc;
122
123typedef void (rtree_leaf_dalloc_t)(tsdn_t *, rtree_t *, rtree_leaf_elm_t *);
124extern rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc;
125#ifdef JEMALLOC_JET
126void rtree_delete(tsdn_t *tsdn, rtree_t *rtree);
127#endif
128rtree_leaf_elm_t *rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree,
129 rtree_ctx_t *rtree_ctx, uintptr_t key, bool dependent, bool init_missing);
130
131JEMALLOC_ALWAYS_INLINE uintptr_t
132rtree_leafkey(uintptr_t key) {
133 unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
134 unsigned cumbits = (rtree_levels[RTREE_HEIGHT-1].cumbits -
135 rtree_levels[RTREE_HEIGHT-1].bits);
136 unsigned maskbits = ptrbits - cumbits;
137 uintptr_t mask = ~((ZU(1) << maskbits) - 1);
138 return (key & mask);
139}
140
141JEMALLOC_ALWAYS_INLINE size_t
142rtree_cache_direct_map(uintptr_t key) {
143 unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
144 unsigned cumbits = (rtree_levels[RTREE_HEIGHT-1].cumbits -
145 rtree_levels[RTREE_HEIGHT-1].bits);
146 unsigned maskbits = ptrbits - cumbits;
147 return (size_t)((key >> maskbits) & (RTREE_CTX_NCACHE - 1));
148}
149
150JEMALLOC_ALWAYS_INLINE uintptr_t
151rtree_subkey(uintptr_t key, unsigned level) {
152 unsigned ptrbits = ZU(1) << (LG_SIZEOF_PTR+3);
153 unsigned cumbits = rtree_levels[level].cumbits;
154 unsigned shiftbits = ptrbits - cumbits;
155 unsigned maskbits = rtree_levels[level].bits;
156 uintptr_t mask = (ZU(1) << maskbits) - 1;
157 return ((key >> shiftbits) & mask);
158}
159
160/*
161 * Atomic getters.
162 *
163 * dependent: Reading a value on behalf of a pointer to a valid allocation
164 * is guaranteed to be a clean read even without synchronization,
165 * because the rtree update became visible in memory before the
166 * pointer came into existence.
167 * !dependent: An arbitrary read, e.g. on behalf of ivsalloc(), may not be
168 * dependent on a previous rtree write, which means a stale read
169 * could result if synchronization were omitted here.
170 */
171# ifdef RTREE_LEAF_COMPACT
172JEMALLOC_ALWAYS_INLINE uintptr_t
173rtree_leaf_elm_bits_read(tsdn_t *tsdn, rtree_t *rtree,
174 rtree_leaf_elm_t *elm, bool dependent) {
175 return (uintptr_t)atomic_load_p(&elm->le_bits, dependent
176 ? ATOMIC_RELAXED : ATOMIC_ACQUIRE);
177}
178
179JEMALLOC_ALWAYS_INLINE extent_t *
180rtree_leaf_elm_bits_extent_get(uintptr_t bits) {
181# ifdef __aarch64__
182 /*
183 * aarch64 doesn't sign extend the highest virtual address bit to set
184 * the higher ones. Instead, the high bits gets zeroed.
185 */
186 uintptr_t high_bit_mask = ((uintptr_t)1 << LG_VADDR) - 1;
187 /* Mask off the slab bit. */
188 uintptr_t low_bit_mask = ~(uintptr_t)1;
189 uintptr_t mask = high_bit_mask & low_bit_mask;
190 return (extent_t *)(bits & mask);
191# else
192 /* Restore sign-extended high bits, mask slab bit. */
193 return (extent_t *)((uintptr_t)((intptr_t)(bits << RTREE_NHIB) >>
194 RTREE_NHIB) & ~((uintptr_t)0x1));
195# endif
196}
197
198JEMALLOC_ALWAYS_INLINE szind_t
199rtree_leaf_elm_bits_szind_get(uintptr_t bits) {
200 return (szind_t)(bits >> LG_VADDR);
201}
202
203JEMALLOC_ALWAYS_INLINE bool
204rtree_leaf_elm_bits_slab_get(uintptr_t bits) {
205 return (bool)(bits & (uintptr_t)0x1);
206}
207
208# endif
209
210JEMALLOC_ALWAYS_INLINE extent_t *
211rtree_leaf_elm_extent_read(tsdn_t *tsdn, rtree_t *rtree,
212 rtree_leaf_elm_t *elm, bool dependent) {
213#ifdef RTREE_LEAF_COMPACT
214 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
215 return rtree_leaf_elm_bits_extent_get(bits);
216#else
217 extent_t *extent = (extent_t *)atomic_load_p(&elm->le_extent, dependent
218 ? ATOMIC_RELAXED : ATOMIC_ACQUIRE);
219 return extent;
220#endif
221}
222
223JEMALLOC_ALWAYS_INLINE szind_t
224rtree_leaf_elm_szind_read(tsdn_t *tsdn, rtree_t *rtree,
225 rtree_leaf_elm_t *elm, bool dependent) {
226#ifdef RTREE_LEAF_COMPACT
227 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
228 return rtree_leaf_elm_bits_szind_get(bits);
229#else
230 return (szind_t)atomic_load_u(&elm->le_szind, dependent ? ATOMIC_RELAXED
231 : ATOMIC_ACQUIRE);
232#endif
233}
234
235JEMALLOC_ALWAYS_INLINE bool
236rtree_leaf_elm_slab_read(tsdn_t *tsdn, rtree_t *rtree,
237 rtree_leaf_elm_t *elm, bool dependent) {
238#ifdef RTREE_LEAF_COMPACT
239 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
240 return rtree_leaf_elm_bits_slab_get(bits);
241#else
242 return atomic_load_b(&elm->le_slab, dependent ? ATOMIC_RELAXED :
243 ATOMIC_ACQUIRE);
244#endif
245}
246
247static inline void
248rtree_leaf_elm_extent_write(tsdn_t *tsdn, rtree_t *rtree,
249 rtree_leaf_elm_t *elm, extent_t *extent) {
250#ifdef RTREE_LEAF_COMPACT
251 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, true);
252 uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) <<
253 LG_VADDR) | ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1))
254 | ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits));
255 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
256#else
257 atomic_store_p(&elm->le_extent, extent, ATOMIC_RELEASE);
258#endif
259}
260
261static inline void
262rtree_leaf_elm_szind_write(tsdn_t *tsdn, rtree_t *rtree,
263 rtree_leaf_elm_t *elm, szind_t szind) {
264 assert(szind <= SC_NSIZES);
265
266#ifdef RTREE_LEAF_COMPACT
267 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm,
268 true);
269 uintptr_t bits = ((uintptr_t)szind << LG_VADDR) |
270 ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) &
271 (((uintptr_t)0x1 << LG_VADDR) - 1)) |
272 ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits));
273 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
274#else
275 atomic_store_u(&elm->le_szind, szind, ATOMIC_RELEASE);
276#endif
277}
278
279static inline void
280rtree_leaf_elm_slab_write(tsdn_t *tsdn, rtree_t *rtree,
281 rtree_leaf_elm_t *elm, bool slab) {
282#ifdef RTREE_LEAF_COMPACT
283 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm,
284 true);
285 uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) <<
286 LG_VADDR) | ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) &
287 (((uintptr_t)0x1 << LG_VADDR) - 1)) | ((uintptr_t)slab);
288 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
289#else
290 atomic_store_b(&elm->le_slab, slab, ATOMIC_RELEASE);
291#endif
292}
293
294static inline void
295rtree_leaf_elm_write(tsdn_t *tsdn, rtree_t *rtree,
296 rtree_leaf_elm_t *elm, extent_t *extent, szind_t szind, bool slab) {
297#ifdef RTREE_LEAF_COMPACT
298 uintptr_t bits = ((uintptr_t)szind << LG_VADDR) |
299 ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1)) |
300 ((uintptr_t)slab);
301 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE);
302#else
303 rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab);
304 rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind);
305 /*
306 * Write extent last, since the element is atomically considered valid
307 * as soon as the extent field is non-NULL.
308 */
309 rtree_leaf_elm_extent_write(tsdn, rtree, elm, extent);
310#endif
311}
312
313static inline void
314rtree_leaf_elm_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree,
315 rtree_leaf_elm_t *elm, szind_t szind, bool slab) {
316 assert(!slab || szind < SC_NBINS);
317
318 /*
319 * The caller implicitly assures that it is the only writer to the szind
320 * and slab fields, and that the extent field cannot currently change.
321 */
322 rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab);
323 rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind);
324}
325
326JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
327rtree_leaf_elm_lookup(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
328 uintptr_t key, bool dependent, bool init_missing) {
329 assert(key != 0);
330 assert(!dependent || !init_missing);
331
332 size_t slot = rtree_cache_direct_map(key);
333 uintptr_t leafkey = rtree_leafkey(key);
334 assert(leafkey != RTREE_LEAFKEY_INVALID);
335
336 /* Fast path: L1 direct mapped cache. */
337 if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) {
338 rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf;
339 assert(leaf != NULL);
340 uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);
341 return &leaf[subkey];
342 }
343 /*
344 * Search the L2 LRU cache. On hit, swap the matching element into the
345 * slot in L1 cache, and move the position in L2 up by 1.
346 */
347#define RTREE_CACHE_CHECK_L2(i) do { \
348 if (likely(rtree_ctx->l2_cache[i].leafkey == leafkey)) { \
349 rtree_leaf_elm_t *leaf = rtree_ctx->l2_cache[i].leaf; \
350 assert(leaf != NULL); \
351 if (i > 0) { \
352 /* Bubble up by one. */ \
353 rtree_ctx->l2_cache[i].leafkey = \
354 rtree_ctx->l2_cache[i - 1].leafkey; \
355 rtree_ctx->l2_cache[i].leaf = \
356 rtree_ctx->l2_cache[i - 1].leaf; \
357 rtree_ctx->l2_cache[i - 1].leafkey = \
358 rtree_ctx->cache[slot].leafkey; \
359 rtree_ctx->l2_cache[i - 1].leaf = \
360 rtree_ctx->cache[slot].leaf; \
361 } else { \
362 rtree_ctx->l2_cache[0].leafkey = \
363 rtree_ctx->cache[slot].leafkey; \
364 rtree_ctx->l2_cache[0].leaf = \
365 rtree_ctx->cache[slot].leaf; \
366 } \
367 rtree_ctx->cache[slot].leafkey = leafkey; \
368 rtree_ctx->cache[slot].leaf = leaf; \
369 uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); \
370 return &leaf[subkey]; \
371 } \
372} while (0)
373 /* Check the first cache entry. */
374 RTREE_CACHE_CHECK_L2(0);
375 /* Search the remaining cache elements. */
376 for (unsigned i = 1; i < RTREE_CTX_NCACHE_L2; i++) {
377 RTREE_CACHE_CHECK_L2(i);
378 }
379#undef RTREE_CACHE_CHECK_L2
380
381 return rtree_leaf_elm_lookup_hard(tsdn, rtree, rtree_ctx, key,
382 dependent, init_missing);
383}
384
385static inline bool
386rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
387 extent_t *extent, szind_t szind, bool slab) {
388 /* Use rtree_clear() to set the extent to NULL. */
389 assert(extent != NULL);
390
391 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
392 key, false, true);
393 if (elm == NULL) {
394 return true;
395 }
396
397 assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) == NULL);
398 rtree_leaf_elm_write(tsdn, rtree, elm, extent, szind, slab);
399
400 return false;
401}
402
403JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
404rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
405 bool dependent) {
406 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
407 key, dependent, false);
408 if (!dependent && elm == NULL) {
409 return NULL;
410 }
411 assert(elm != NULL);
412 return elm;
413}
414
415JEMALLOC_ALWAYS_INLINE extent_t *
416rtree_extent_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
417 uintptr_t key, bool dependent) {
418 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
419 dependent);
420 if (!dependent && elm == NULL) {
421 return NULL;
422 }
423 return rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
424}
425
426JEMALLOC_ALWAYS_INLINE szind_t
427rtree_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
428 uintptr_t key, bool dependent) {
429 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
430 dependent);
431 if (!dependent && elm == NULL) {
432 return SC_NSIZES;
433 }
434 return rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
435}
436
437/*
438 * rtree_slab_read() is intentionally omitted because slab is always read in
439 * conjunction with szind, which makes rtree_szind_slab_read() a better choice.
440 */
441
442JEMALLOC_ALWAYS_INLINE bool
443rtree_extent_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
444 uintptr_t key, bool dependent, extent_t **r_extent, szind_t *r_szind) {
445 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
446 dependent);
447 if (!dependent && elm == NULL) {
448 return true;
449 }
450 *r_extent = rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
451 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
452 return false;
453}
454
455/*
456 * Try to read szind_slab from the L1 cache. Returns true on a hit,
457 * and fills in r_szind and r_slab. Otherwise returns false.
458 *
459 * Key is allowed to be NULL in order to save an extra branch on the
460 * fastpath. returns false in this case.
461 */
462JEMALLOC_ALWAYS_INLINE bool
463rtree_szind_slab_read_fast(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
464 uintptr_t key, szind_t *r_szind, bool *r_slab) {
465 rtree_leaf_elm_t *elm;
466
467 size_t slot = rtree_cache_direct_map(key);
468 uintptr_t leafkey = rtree_leafkey(key);
469 assert(leafkey != RTREE_LEAFKEY_INVALID);
470
471 if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) {
472 rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf;
473 assert(leaf != NULL);
474 uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);
475 elm = &leaf[subkey];
476
477#ifdef RTREE_LEAF_COMPACT
478 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree,
479 elm, true);
480 *r_szind = rtree_leaf_elm_bits_szind_get(bits);
481 *r_slab = rtree_leaf_elm_bits_slab_get(bits);
482#else
483 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, true);
484 *r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, true);
485#endif
486 return true;
487 } else {
488 return false;
489 }
490}
491JEMALLOC_ALWAYS_INLINE bool
492rtree_szind_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
493 uintptr_t key, bool dependent, szind_t *r_szind, bool *r_slab) {
494 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
495 dependent);
496 if (!dependent && elm == NULL) {
497 return true;
498 }
499#ifdef RTREE_LEAF_COMPACT
500 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
501 *r_szind = rtree_leaf_elm_bits_szind_get(bits);
502 *r_slab = rtree_leaf_elm_bits_slab_get(bits);
503#else
504 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
505 *r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, dependent);
506#endif
507 return false;
508}
509
510static inline void
511rtree_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
512 uintptr_t key, szind_t szind, bool slab) {
513 assert(!slab || szind < SC_NBINS);
514
515 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
516 rtree_leaf_elm_szind_slab_update(tsdn, rtree, elm, szind, slab);
517}
518
519static inline void
520rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
521 uintptr_t key) {
522 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
523 assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) !=
524 NULL);
525 rtree_leaf_elm_write(tsdn, rtree, elm, NULL, SC_NSIZES, false);
526}
527
528#endif /* JEMALLOC_INTERNAL_RTREE_H */
529