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 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, 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 * 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(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 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 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 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 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 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 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 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 * 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 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 JEMALLOC_ALWAYS_INLINE bool 456 rtree_szind_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 457 uintptr_t key, bool dependent, szind_t *r_szind, bool *r_slab) { 458 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, 459 dependent); 460 if (!dependent && elm == NULL) { 461 return true; 462 } 463 #ifdef RTREE_LEAF_COMPACT 464 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent); 465 *r_szind = rtree_leaf_elm_bits_szind_get(bits); 466 *r_slab = rtree_leaf_elm_bits_slab_get(bits); 467 #else 468 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent); 469 *r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, dependent); 470 #endif 471 return false; 472 } 473 474 static inline void 475 rtree_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 476 uintptr_t key, szind_t szind, bool slab) { 477 assert(!slab || szind < NBINS); 478 479 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true); 480 rtree_leaf_elm_szind_slab_update(tsdn, rtree, elm, szind, slab); 481 } 482 483 static inline void 484 rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 485 uintptr_t key) { 486 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true); 487 assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) != 488 NULL); 489 rtree_leaf_elm_write(tsdn, rtree, elm, NULL, NSIZES, false); 490 } 491 492 #endif /* JEMALLOC_INTERNAL_RTREE_H */ 493