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
41 typedef struct rtree_node_elm_s rtree_node_elm_t;
42 struct rtree_node_elm_s {
43 atomic_p_t child; /* (rtree_{node,leaf}_elm_t *) */
44 };
45
46 struct 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
68 typedef struct rtree_level_s rtree_level_t;
69 struct 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
79 typedef struct rtree_s rtree_t;
80 struct 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 */
96 static 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
112 bool rtree_new(rtree_t *rtree, bool zeroed);
113
114 typedef rtree_node_elm_t *(rtree_node_alloc_t)(tsdn_t *, rtree_t *, size_t);
115 extern rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc;
116
117 typedef rtree_leaf_elm_t *(rtree_leaf_alloc_t)(tsdn_t *, rtree_t *, size_t);
118 extern rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc;
119
120 typedef void (rtree_node_dalloc_t)(tsdn_t *, rtree_t *, rtree_node_elm_t *);
121 extern rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc;
122
123 typedef void (rtree_leaf_dalloc_t)(tsdn_t *, rtree_t *, rtree_leaf_elm_t *);
124 extern rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc;
125 #ifdef JEMALLOC_JET
126 void rtree_delete(tsdn_t *tsdn, rtree_t *rtree);
127 #endif
128 rtree_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
131 JEMALLOC_ALWAYS_INLINE uintptr_t
rtree_leafkey(uintptr_t key)132 rtree_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
141 JEMALLOC_ALWAYS_INLINE size_t
rtree_cache_direct_map(uintptr_t key)142 rtree_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
150 JEMALLOC_ALWAYS_INLINE uintptr_t
rtree_subkey(uintptr_t key,unsigned level)151 rtree_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
172 JEMALLOC_ALWAYS_INLINE uintptr_t
rtree_leaf_elm_bits_read(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)173 rtree_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
179 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_leaf_elm_bits_extent_get(uintptr_t bits)180 rtree_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
198 JEMALLOC_ALWAYS_INLINE szind_t
rtree_leaf_elm_bits_szind_get(uintptr_t bits)199 rtree_leaf_elm_bits_szind_get(uintptr_t bits) {
200 return (szind_t)(bits >> LG_VADDR);
201 }
202
203 JEMALLOC_ALWAYS_INLINE bool
rtree_leaf_elm_bits_slab_get(uintptr_t bits)204 rtree_leaf_elm_bits_slab_get(uintptr_t bits) {
205 return (bool)(bits & (uintptr_t)0x1);
206 }
207
208 # endif
209
210 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_leaf_elm_extent_read(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)211 rtree_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
223 JEMALLOC_ALWAYS_INLINE szind_t
rtree_leaf_elm_szind_read(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)224 rtree_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
235 JEMALLOC_ALWAYS_INLINE bool
rtree_leaf_elm_slab_read(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)236 rtree_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
247 static inline void
rtree_leaf_elm_extent_write(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,extent_t * extent)248 rtree_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
261 static inline void
rtree_leaf_elm_szind_write(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,szind_t szind)262 rtree_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
279 static inline void
rtree_leaf_elm_slab_write(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,bool slab)280 rtree_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
294 static inline void
rtree_leaf_elm_write(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,extent_t * extent,szind_t szind,bool slab)295 rtree_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
313 static inline void
rtree_leaf_elm_szind_slab_update(tsdn_t * tsdn,rtree_t * rtree,rtree_leaf_elm_t * elm,szind_t szind,bool slab)314 rtree_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
326 JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
rtree_leaf_elm_lookup(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent,bool init_missing)327 rtree_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
385 static inline bool
rtree_write(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,extent_t * extent,szind_t szind,bool slab)386 rtree_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
403 JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t *
rtree_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)404 rtree_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
415 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_extent_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)416 rtree_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
426 JEMALLOC_ALWAYS_INLINE szind_t
rtree_szind_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)427 rtree_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
442 JEMALLOC_ALWAYS_INLINE bool
rtree_extent_szind_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent,extent_t ** r_extent,szind_t * r_szind)443 rtree_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 */
462 JEMALLOC_ALWAYS_INLINE bool
rtree_szind_slab_read_fast(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,szind_t * r_szind,bool * r_slab)463 rtree_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 }
491 JEMALLOC_ALWAYS_INLINE bool
rtree_szind_slab_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent,szind_t * r_szind,bool * r_slab)492 rtree_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
510 static inline void
rtree_szind_slab_update(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,szind_t szind,bool slab)511 rtree_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
519 static inline void
rtree_clear(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key)520 rtree_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