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 |
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 |
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 |
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 |
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 * |
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 |
199 | rtree_leaf_elm_bits_szind_get(uintptr_t bits) { |
200 | return (szind_t)(bits >> LG_VADDR); |
201 | } |
202 | |
203 | JEMALLOC_ALWAYS_INLINE bool |
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 * |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 * |
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 |
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 * |
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 * |
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 |
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 |
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 |
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 |
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 |
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 |
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 | |