• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/size_classes.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_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, rtree_leaf_elm_t *elm,
174     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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)211 rtree_leaf_elm_extent_read(UNUSED tsdn_t *tsdn, UNUSED 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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)224 rtree_leaf_elm_szind_read(UNUSED tsdn_t *tsdn, UNUSED 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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,bool dependent)236 rtree_leaf_elm_slab_read(UNUSED tsdn_t *tsdn, UNUSED 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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,extent_t * extent)248 rtree_leaf_elm_extent_write(UNUSED tsdn_t *tsdn, UNUSED 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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,szind_t szind)262 rtree_leaf_elm_szind_write(UNUSED tsdn_t *tsdn, UNUSED rtree_t *rtree,
263     rtree_leaf_elm_t *elm, szind_t szind) {
264 	assert(szind <= 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(UNUSED tsdn_t * tsdn,UNUSED rtree_t * rtree,rtree_leaf_elm_t * elm,bool slab)280 rtree_leaf_elm_slab_write(UNUSED tsdn_t *tsdn, UNUSED 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, rtree_leaf_elm_t *elm,
296     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 < 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 		/* ANDROID CHANGE: Bad pointers return NULL */
340 		/* assert(leaf != NULL); */
341 		if (leaf == NULL) {
342 			return NULL;
343 		}
344 		/* ANDROID END CHANGE */
345 		uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);
346 		return &leaf[subkey];
347 	}
348 	/*
349 	 * Search the L2 LRU cache.  On hit, swap the matching element into the
350 	 * slot in L1 cache, and move the position in L2 up by 1.
351 	 */
352 #define RTREE_CACHE_CHECK_L2(i) do {					\
353 	if (likely(rtree_ctx->l2_cache[i].leafkey == leafkey)) {	\
354 		rtree_leaf_elm_t *leaf = rtree_ctx->l2_cache[i].leaf;	\
355 		/* ANDROID CHANGE: Bad pointers return NULL */		\
356 		/* assert(leaf != NULL); */				\
357 		if (leaf == NULL) {					\
358 			return NULL;					\
359 		}							\
360 		/* ANDROID END CHANGE */				\
361 		if (i > 0) {						\
362 			/* Bubble up by one. */				\
363 			rtree_ctx->l2_cache[i].leafkey =		\
364 				rtree_ctx->l2_cache[i - 1].leafkey;	\
365 			rtree_ctx->l2_cache[i].leaf =			\
366 				rtree_ctx->l2_cache[i - 1].leaf;	\
367 			rtree_ctx->l2_cache[i - 1].leafkey =		\
368 			    rtree_ctx->cache[slot].leafkey;		\
369 			rtree_ctx->l2_cache[i - 1].leaf =		\
370 			    rtree_ctx->cache[slot].leaf;		\
371 		} else {						\
372 			rtree_ctx->l2_cache[0].leafkey =		\
373 			    rtree_ctx->cache[slot].leafkey;		\
374 			rtree_ctx->l2_cache[0].leaf =			\
375 			    rtree_ctx->cache[slot].leaf;		\
376 		}							\
377 		rtree_ctx->cache[slot].leafkey = leafkey;		\
378 		rtree_ctx->cache[slot].leaf = leaf;			\
379 		uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1);	\
380 		return &leaf[subkey];					\
381 	}								\
382 } while (0)
383 	/* Check the first cache entry. */
384 	RTREE_CACHE_CHECK_L2(0);
385 	/* Search the remaining cache elements. */
386 	for (unsigned i = 1; i < RTREE_CTX_NCACHE_L2; i++) {
387 		RTREE_CACHE_CHECK_L2(i);
388 	}
389 #undef RTREE_CACHE_CHECK_L2
390 
391 	return rtree_leaf_elm_lookup_hard(tsdn, rtree, rtree_ctx, key,
392 	    dependent, init_missing);
393 }
394 
395 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)396 rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
397     extent_t *extent, szind_t szind, bool slab) {
398 	/* Use rtree_clear() to set the extent to NULL. */
399 	assert(extent != NULL);
400 
401 	rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
402 	    key, false, true);
403 	if (elm == NULL) {
404 		return true;
405 	}
406 
407 	assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) == NULL);
408 	rtree_leaf_elm_write(tsdn, rtree, elm, extent, szind, slab);
409 
410 	return false;
411 }
412 
413 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)414 rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key,
415     bool dependent) {
416 	rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx,
417 	    key, dependent, false);
418 	/* ANDROID CHANGE: Bad pointers return NULL */
419 	/* if (!dependent && elm == NULL) { */
420 	if (elm == NULL) {
421 	/* ANDROID END CHANGE */
422 		return NULL;
423 	}
424 	assert(elm != NULL);
425 	return elm;
426 }
427 
428 JEMALLOC_ALWAYS_INLINE extent_t *
rtree_extent_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)429 rtree_extent_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
430     uintptr_t key, bool dependent) {
431 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
432 	    dependent);
433 	/* ANDROID CHANGE: Bad pointers return NULL */
434 	/* if (!dependent && elm == NULL) { */
435 	if (elm == NULL) {
436 	/* ANDROID END CHANGE */
437 		return NULL;
438 	}
439 	return rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
440 }
441 
442 JEMALLOC_ALWAYS_INLINE szind_t
rtree_szind_read(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key,bool dependent)443 rtree_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
444     uintptr_t key, bool dependent) {
445 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
446 	    dependent);
447 	/* ANDROID CHANGE: Bad pointers return NULL */
448 	/* if (!dependent && elm == NULL) { */
449 	if (elm == NULL) {
450 		return NSIZES;
451 	}
452 	return rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
453 }
454 
455 /*
456  * rtree_slab_read() is intentionally omitted because slab is always read in
457  * conjunction with szind, which makes rtree_szind_slab_read() a better choice.
458  */
459 
460 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)461 rtree_extent_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
462     uintptr_t key, bool dependent, extent_t **r_extent, szind_t *r_szind) {
463 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
464 	    dependent);
465 	/* ANDROID CHANGE: Bad pointers return NULL */
466 	/* if (!dependent && elm == NULL) { */
467 	if (elm == NULL) {
468 	/* ANDROID END CHANGE */
469 		return true;
470 	}
471 	*r_extent = rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent);
472 	*r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
473 	return false;
474 }
475 
476 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)477 rtree_szind_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
478     uintptr_t key, bool dependent, szind_t *r_szind, bool *r_slab) {
479 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key,
480 	    dependent);
481 	/* ANDROID CHANGE: Bad pointers return NULL */
482 	/* if (!dependent && elm == NULL) { */
483 	if (elm == NULL) {
484 	/* ANDROID END CHANGE */
485 		return true;
486 	}
487 #ifdef RTREE_LEAF_COMPACT
488 	uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent);
489 	*r_szind = rtree_leaf_elm_bits_szind_get(bits);
490 	*r_slab = rtree_leaf_elm_bits_slab_get(bits);
491 #else
492 	*r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent);
493 	*r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, dependent);
494 #endif
495 	return false;
496 }
497 
498 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)499 rtree_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
500     uintptr_t key, szind_t szind, bool slab) {
501 	assert(!slab || szind < NBINS);
502 
503 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
504 	rtree_leaf_elm_szind_slab_update(tsdn, rtree, elm, szind, slab);
505 }
506 
507 static inline void
rtree_clear(tsdn_t * tsdn,rtree_t * rtree,rtree_ctx_t * rtree_ctx,uintptr_t key)508 rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
509     uintptr_t key) {
510 	rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true);
511 	assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) !=
512 	    NULL);
513 	rtree_leaf_elm_write(tsdn, rtree, elm, NULL, NSIZES, false);
514 }
515 
516 #endif /* JEMALLOC_INTERNAL_RTREE_H */
517