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 /* Restore sign-extended high bits, mask slab bit. */ 182 return (extent_t *)((uintptr_t)((intptr_t)(bits << RTREE_NHIB) >> 183 RTREE_NHIB) & ~((uintptr_t)0x1)); 184 } 185 186 JEMALLOC_ALWAYS_INLINE szind_t 187 rtree_leaf_elm_bits_szind_get(uintptr_t bits) { 188 return (szind_t)(bits >> LG_VADDR); 189 } 190 191 JEMALLOC_ALWAYS_INLINE bool 192 rtree_leaf_elm_bits_slab_get(uintptr_t bits) { 193 return (bool)(bits & (uintptr_t)0x1); 194 } 195 196 # endif 197 198 JEMALLOC_ALWAYS_INLINE extent_t * 199 rtree_leaf_elm_extent_read(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 200 bool dependent) { 201 #ifdef RTREE_LEAF_COMPACT 202 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent); 203 return rtree_leaf_elm_bits_extent_get(bits); 204 #else 205 extent_t *extent = (extent_t *)atomic_load_p(&elm->le_extent, dependent 206 ? ATOMIC_RELAXED : ATOMIC_ACQUIRE); 207 return extent; 208 #endif 209 } 210 211 JEMALLOC_ALWAYS_INLINE szind_t 212 rtree_leaf_elm_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 213 bool dependent) { 214 #ifdef RTREE_LEAF_COMPACT 215 uintptr_t bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, dependent); 216 return rtree_leaf_elm_bits_szind_get(bits); 217 #else 218 return (szind_t)atomic_load_u(&elm->le_szind, dependent ? ATOMIC_RELAXED 219 : ATOMIC_ACQUIRE); 220 #endif 221 } 222 223 JEMALLOC_ALWAYS_INLINE bool 224 rtree_leaf_elm_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 225 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_slab_get(bits); 229 #else 230 return atomic_load_b(&elm->le_slab, dependent ? ATOMIC_RELAXED : 231 ATOMIC_ACQUIRE); 232 #endif 233 } 234 235 static inline void 236 rtree_leaf_elm_extent_write(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 237 extent_t *extent) { 238 #ifdef RTREE_LEAF_COMPACT 239 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, true); 240 uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) << 241 LG_VADDR) | ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1)) 242 | ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits)); 243 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE); 244 #else 245 atomic_store_p(&elm->le_extent, extent, ATOMIC_RELEASE); 246 #endif 247 } 248 249 static inline void 250 rtree_leaf_elm_szind_write(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 251 szind_t szind) { 252 assert(szind <= NSIZES); 253 254 #ifdef RTREE_LEAF_COMPACT 255 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, 256 true); 257 uintptr_t bits = ((uintptr_t)szind << LG_VADDR) | 258 ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) & 259 (((uintptr_t)0x1 << LG_VADDR) - 1)) | 260 ((uintptr_t)rtree_leaf_elm_bits_slab_get(old_bits)); 261 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE); 262 #else 263 atomic_store_u(&elm->le_szind, szind, ATOMIC_RELEASE); 264 #endif 265 } 266 267 static inline void 268 rtree_leaf_elm_slab_write(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 269 bool slab) { 270 #ifdef RTREE_LEAF_COMPACT 271 uintptr_t old_bits = rtree_leaf_elm_bits_read(tsdn, rtree, elm, 272 true); 273 uintptr_t bits = ((uintptr_t)rtree_leaf_elm_bits_szind_get(old_bits) << 274 LG_VADDR) | ((uintptr_t)rtree_leaf_elm_bits_extent_get(old_bits) & 275 (((uintptr_t)0x1 << LG_VADDR) - 1)) | ((uintptr_t)slab); 276 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE); 277 #else 278 atomic_store_b(&elm->le_slab, slab, ATOMIC_RELEASE); 279 #endif 280 } 281 282 static inline void 283 rtree_leaf_elm_write(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *elm, 284 extent_t *extent, szind_t szind, bool slab) { 285 #ifdef RTREE_LEAF_COMPACT 286 uintptr_t bits = ((uintptr_t)szind << LG_VADDR) | 287 ((uintptr_t)extent & (((uintptr_t)0x1 << LG_VADDR) - 1)) | 288 ((uintptr_t)slab); 289 atomic_store_p(&elm->le_bits, (void *)bits, ATOMIC_RELEASE); 290 #else 291 rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab); 292 rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind); 293 /* 294 * Write extent last, since the element is atomically considered valid 295 * as soon as the extent field is non-NULL. 296 */ 297 rtree_leaf_elm_extent_write(tsdn, rtree, elm, extent); 298 #endif 299 } 300 301 static inline void 302 rtree_leaf_elm_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, 303 rtree_leaf_elm_t *elm, szind_t szind, bool slab) { 304 assert(!slab || szind < NBINS); 305 306 /* 307 * The caller implicitly assures that it is the only writer to the szind 308 * and slab fields, and that the extent field cannot currently change. 309 */ 310 rtree_leaf_elm_slab_write(tsdn, rtree, elm, slab); 311 rtree_leaf_elm_szind_write(tsdn, rtree, elm, szind); 312 } 313 314 JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t * 315 rtree_leaf_elm_lookup(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 316 uintptr_t key, bool dependent, bool init_missing) { 317 assert(key != 0); 318 assert(!dependent || !init_missing); 319 320 size_t slot = rtree_cache_direct_map(key); 321 uintptr_t leafkey = rtree_leafkey(key); 322 assert(leafkey != RTREE_LEAFKEY_INVALID); 323 324 /* Fast path: L1 direct mapped cache. */ 325 if (likely(rtree_ctx->cache[slot].leafkey == leafkey)) { 326 rtree_leaf_elm_t *leaf = rtree_ctx->cache[slot].leaf; 327 assert(leaf != NULL); 328 uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); 329 return &leaf[subkey]; 330 } 331 /* 332 * Search the L2 LRU cache. On hit, swap the matching element into the 333 * slot in L1 cache, and move the position in L2 up by 1. 334 */ 335 #define RTREE_CACHE_CHECK_L2(i) do { \ 336 if (likely(rtree_ctx->l2_cache[i].leafkey == leafkey)) { \ 337 rtree_leaf_elm_t *leaf = rtree_ctx->l2_cache[i].leaf; \ 338 assert(leaf != NULL); \ 339 if (i > 0) { \ 340 /* Bubble up by one. */ \ 341 rtree_ctx->l2_cache[i].leafkey = \ 342 rtree_ctx->l2_cache[i - 1].leafkey; \ 343 rtree_ctx->l2_cache[i].leaf = \ 344 rtree_ctx->l2_cache[i - 1].leaf; \ 345 rtree_ctx->l2_cache[i - 1].leafkey = \ 346 rtree_ctx->cache[slot].leafkey; \ 347 rtree_ctx->l2_cache[i - 1].leaf = \ 348 rtree_ctx->cache[slot].leaf; \ 349 } else { \ 350 rtree_ctx->l2_cache[0].leafkey = \ 351 rtree_ctx->cache[slot].leafkey; \ 352 rtree_ctx->l2_cache[0].leaf = \ 353 rtree_ctx->cache[slot].leaf; \ 354 } \ 355 rtree_ctx->cache[slot].leafkey = leafkey; \ 356 rtree_ctx->cache[slot].leaf = leaf; \ 357 uintptr_t subkey = rtree_subkey(key, RTREE_HEIGHT-1); \ 358 return &leaf[subkey]; \ 359 } \ 360 } while (0) 361 /* Check the first cache entry. */ 362 RTREE_CACHE_CHECK_L2(0); 363 /* Search the remaining cache elements. */ 364 for (unsigned i = 1; i < RTREE_CTX_NCACHE_L2; i++) { 365 RTREE_CACHE_CHECK_L2(i); 366 } 367 #undef RTREE_CACHE_CHECK_L2 368 369 return rtree_leaf_elm_lookup_hard(tsdn, rtree, rtree_ctx, key, 370 dependent, init_missing); 371 } 372 373 static inline bool 374 rtree_write(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key, 375 extent_t *extent, szind_t szind, bool slab) { 376 /* Use rtree_clear() to set the extent to NULL. */ 377 assert(extent != NULL); 378 379 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, 380 key, false, true); 381 if (elm == NULL) { 382 return true; 383 } 384 385 assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) == NULL); 386 rtree_leaf_elm_write(tsdn, rtree, elm, extent, szind, slab); 387 388 return false; 389 } 390 391 JEMALLOC_ALWAYS_INLINE rtree_leaf_elm_t * 392 rtree_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, uintptr_t key, 393 bool dependent) { 394 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, rtree_ctx, 395 key, dependent, false); 396 if (!dependent && elm == NULL) { 397 return NULL; 398 } 399 assert(elm != NULL); 400 return elm; 401 } 402 403 JEMALLOC_ALWAYS_INLINE extent_t * 404 rtree_extent_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 405 uintptr_t key, bool dependent) { 406 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, 407 dependent); 408 if (!dependent && elm == NULL) { 409 return NULL; 410 } 411 return rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent); 412 } 413 414 JEMALLOC_ALWAYS_INLINE szind_t 415 rtree_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 416 uintptr_t key, bool dependent) { 417 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, 418 dependent); 419 if (!dependent && elm == NULL) { 420 return NSIZES; 421 } 422 return rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent); 423 } 424 425 /* 426 * rtree_slab_read() is intentionally omitted because slab is always read in 427 * conjunction with szind, which makes rtree_szind_slab_read() a better choice. 428 */ 429 430 JEMALLOC_ALWAYS_INLINE bool 431 rtree_extent_szind_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 432 uintptr_t key, bool dependent, extent_t **r_extent, szind_t *r_szind) { 433 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, 434 dependent); 435 if (!dependent && elm == NULL) { 436 return true; 437 } 438 *r_extent = rtree_leaf_elm_extent_read(tsdn, rtree, elm, dependent); 439 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent); 440 return false; 441 } 442 443 JEMALLOC_ALWAYS_INLINE bool 444 rtree_szind_slab_read(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 445 uintptr_t key, bool dependent, szind_t *r_szind, bool *r_slab) { 446 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, 447 dependent); 448 if (!dependent && elm == NULL) { 449 return true; 450 } 451 *r_szind = rtree_leaf_elm_szind_read(tsdn, rtree, elm, dependent); 452 *r_slab = rtree_leaf_elm_slab_read(tsdn, rtree, elm, dependent); 453 return false; 454 } 455 456 static inline void 457 rtree_szind_slab_update(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 458 uintptr_t key, szind_t szind, bool slab) { 459 assert(!slab || szind < NBINS); 460 461 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true); 462 rtree_leaf_elm_szind_slab_update(tsdn, rtree, elm, szind, slab); 463 } 464 465 static inline void 466 rtree_clear(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 467 uintptr_t key) { 468 rtree_leaf_elm_t *elm = rtree_read(tsdn, rtree, rtree_ctx, key, true); 469 assert(rtree_leaf_elm_extent_read(tsdn, rtree, elm, false) != 470 NULL); 471 rtree_leaf_elm_write(tsdn, rtree, elm, NULL, NSIZES, false); 472 } 473 474 #endif /* JEMALLOC_INTERNAL_RTREE_H */ 475