1 #ifndef JEMALLOC_INTERNAL_ARENA_INLINES_B_H 2 #define JEMALLOC_INTERNAL_ARENA_INLINES_B_H 3 4 #include "jemalloc/internal/div.h" 5 #include "jemalloc/internal/emap.h" 6 #include "jemalloc/internal/jemalloc_internal_types.h" 7 #include "jemalloc/internal/mutex.h" 8 #include "jemalloc/internal/rtree.h" 9 #include "jemalloc/internal/safety_check.h" 10 #include "jemalloc/internal/sc.h" 11 #include "jemalloc/internal/sz.h" 12 #include "jemalloc/internal/ticker.h" 13 14 static inline arena_t * 15 arena_get_from_edata(edata_t *edata) { 16 return (arena_t *)atomic_load_p(&arenas[edata_arena_ind_get(edata)], 17 ATOMIC_RELAXED); 18 } 19 20 JEMALLOC_ALWAYS_INLINE arena_t * 21 arena_choose_maybe_huge(tsd_t *tsd, arena_t *arena, size_t size) { 22 if (arena != NULL) { 23 return arena; 24 } 25 26 /* 27 * For huge allocations, use the dedicated huge arena if both are true: 28 * 1) is using auto arena selection (i.e. arena == NULL), and 2) the 29 * thread is not assigned to a manual arena. 30 */ 31 if (unlikely(size >= oversize_threshold)) { 32 arena_t *tsd_arena = tsd_arena_get(tsd); 33 if (tsd_arena == NULL || arena_is_auto(tsd_arena)) { 34 return arena_choose_huge(tsd); 35 } 36 } 37 38 return arena_choose(tsd, NULL); 39 } 40 41 JEMALLOC_ALWAYS_INLINE void 42 arena_prof_info_get(tsd_t *tsd, const void *ptr, emap_alloc_ctx_t *alloc_ctx, 43 prof_info_t *prof_info, bool reset_recent) { 44 cassert(config_prof); 45 assert(ptr != NULL); 46 assert(prof_info != NULL); 47 48 edata_t *edata = NULL; 49 bool is_slab; 50 51 /* Static check. */ 52 if (alloc_ctx == NULL) { 53 edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global, 54 ptr); 55 is_slab = edata_slab_get(edata); 56 } else if (unlikely(!(is_slab = alloc_ctx->slab))) { 57 edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global, 58 ptr); 59 } 60 61 if (unlikely(!is_slab)) { 62 /* edata must have been initialized at this point. */ 63 assert(edata != NULL); 64 large_prof_info_get(tsd, edata, prof_info, reset_recent); 65 } else { 66 prof_info->alloc_tctx = (prof_tctx_t *)(uintptr_t)1U; 67 /* 68 * No need to set other fields in prof_info; they will never be 69 * accessed if (uintptr_t)alloc_tctx == (uintptr_t)1U. 70 */ 71 } 72 } 73 74 JEMALLOC_ALWAYS_INLINE void 75 arena_prof_tctx_reset(tsd_t *tsd, const void *ptr, 76 emap_alloc_ctx_t *alloc_ctx) { 77 cassert(config_prof); 78 assert(ptr != NULL); 79 80 /* Static check. */ 81 if (alloc_ctx == NULL) { 82 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd), 83 &arena_emap_global, ptr); 84 if (unlikely(!edata_slab_get(edata))) { 85 large_prof_tctx_reset(edata); 86 } 87 } else { 88 if (unlikely(!alloc_ctx->slab)) { 89 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd), 90 &arena_emap_global, ptr); 91 large_prof_tctx_reset(edata); 92 } 93 } 94 } 95 96 JEMALLOC_ALWAYS_INLINE void 97 arena_prof_tctx_reset_sampled(tsd_t *tsd, const void *ptr) { 98 cassert(config_prof); 99 assert(ptr != NULL); 100 101 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global, 102 ptr); 103 assert(!edata_slab_get(edata)); 104 105 large_prof_tctx_reset(edata); 106 } 107 108 JEMALLOC_ALWAYS_INLINE void 109 arena_prof_info_set(tsd_t *tsd, edata_t *edata, prof_tctx_t *tctx, 110 size_t size) { 111 cassert(config_prof); 112 113 assert(!edata_slab_get(edata)); 114 large_prof_info_set(edata, tctx, size); 115 } 116 117 JEMALLOC_ALWAYS_INLINE void 118 arena_decay_ticks(tsdn_t *tsdn, arena_t *arena, unsigned nticks) { 119 if (unlikely(tsdn_null(tsdn))) { 120 return; 121 } 122 tsd_t *tsd = tsdn_tsd(tsdn); 123 /* 124 * We use the ticker_geom_t to avoid having per-arena state in the tsd. 125 * Instead of having a countdown-until-decay timer running for every 126 * arena in every thread, we flip a coin once per tick, whose 127 * probability of coming up heads is 1/nticks; this is effectively the 128 * operation of the ticker_geom_t. Each arena has the same chance of a 129 * coinflip coming up heads (1/ARENA_DECAY_NTICKS_PER_UPDATE), so we can 130 * use a single ticker for all of them. 131 */ 132 ticker_geom_t *decay_ticker = tsd_arena_decay_tickerp_get(tsd); 133 uint64_t *prng_state = tsd_prng_statep_get(tsd); 134 if (unlikely(ticker_geom_ticks(decay_ticker, prng_state, nticks))) { 135 arena_decay(tsdn, arena, false, false); 136 } 137 } 138 139 JEMALLOC_ALWAYS_INLINE void 140 arena_decay_tick(tsdn_t *tsdn, arena_t *arena) { 141 arena_decay_ticks(tsdn, arena, 1); 142 } 143 144 JEMALLOC_ALWAYS_INLINE void * 145 arena_malloc(tsdn_t *tsdn, arena_t *arena, size_t size, szind_t ind, bool zero, 146 tcache_t *tcache, bool slow_path) { 147 assert(!tsdn_null(tsdn) || tcache == NULL); 148 149 if (likely(tcache != NULL)) { 150 if (likely(size <= SC_SMALL_MAXCLASS)) { 151 return tcache_alloc_small(tsdn_tsd(tsdn), arena, 152 tcache, size, ind, zero, slow_path); 153 } 154 if (likely(size <= tcache_maxclass)) { 155 return tcache_alloc_large(tsdn_tsd(tsdn), arena, 156 tcache, size, ind, zero, slow_path); 157 } 158 /* (size > tcache_maxclass) case falls through. */ 159 assert(size > tcache_maxclass); 160 } 161 162 return arena_malloc_hard(tsdn, arena, size, ind, zero); 163 } 164 165 JEMALLOC_ALWAYS_INLINE arena_t * 166 arena_aalloc(tsdn_t *tsdn, const void *ptr) { 167 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, ptr); 168 unsigned arena_ind = edata_arena_ind_get(edata); 169 return (arena_t *)atomic_load_p(&arenas[arena_ind], ATOMIC_RELAXED); 170 } 171 172 JEMALLOC_ALWAYS_INLINE size_t 173 arena_salloc(tsdn_t *tsdn, const void *ptr) { 174 assert(ptr != NULL); 175 emap_alloc_ctx_t alloc_ctx; 176 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, &alloc_ctx); 177 assert(alloc_ctx.szind != SC_NSIZES); 178 179 return sz_index2size(alloc_ctx.szind); 180 } 181 182 JEMALLOC_ALWAYS_INLINE size_t 183 arena_vsalloc(tsdn_t *tsdn, const void *ptr) { 184 /* 185 * Return 0 if ptr is not within an extent managed by jemalloc. This 186 * function has two extra costs relative to isalloc(): 187 * - The rtree calls cannot claim to be dependent lookups, which induces 188 * rtree lookup load dependencies. 189 * - The lookup may fail, so there is an extra branch to check for 190 * failure. 191 */ 192 193 emap_full_alloc_ctx_t full_alloc_ctx; 194 bool missing = emap_full_alloc_ctx_try_lookup(tsdn, &arena_emap_global, 195 ptr, &full_alloc_ctx); 196 if (missing) { 197 return 0; 198 } 199 200 if (full_alloc_ctx.edata == NULL) { 201 return 0; 202 } 203 assert(edata_state_get(full_alloc_ctx.edata) == extent_state_active); 204 /* Only slab members should be looked up via interior pointers. */ 205 assert(edata_addr_get(full_alloc_ctx.edata) == ptr 206 || edata_slab_get(full_alloc_ctx.edata)); 207 208 assert(full_alloc_ctx.szind != SC_NSIZES); 209 210 return sz_index2size(full_alloc_ctx.szind); 211 } 212 213 JEMALLOC_ALWAYS_INLINE bool 214 large_dalloc_safety_checks(edata_t *edata, void *ptr, szind_t szind) { 215 if (!config_opt_safety_checks) { 216 return false; 217 } 218 219 /* 220 * Eagerly detect double free and sized dealloc bugs for large sizes. 221 * The cost is low enough (as edata will be accessed anyway) to be 222 * enabled all the time. 223 */ 224 if (unlikely(edata == NULL || 225 edata_state_get(edata) != extent_state_active)) { 226 safety_check_fail("Invalid deallocation detected: " 227 "pages being freed (%p) not currently active, " 228 "possibly caused by double free bugs.", 229 (uintptr_t)edata_addr_get(edata)); 230 return true; 231 } 232 size_t input_size = sz_index2size(szind); 233 if (unlikely(input_size != edata_usize_get(edata))) { 234 safety_check_fail_sized_dealloc(/* current_dealloc */ true, ptr, 235 /* true_size */ edata_usize_get(edata), input_size); 236 return true; 237 } 238 239 return false; 240 } 241 242 static inline void 243 arena_dalloc_large_no_tcache(tsdn_t *tsdn, void *ptr, szind_t szind) { 244 if (config_prof && unlikely(szind < SC_NBINS)) { 245 arena_dalloc_promoted(tsdn, ptr, NULL, true); 246 } else { 247 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, 248 ptr); 249 if (large_dalloc_safety_checks(edata, ptr, szind)) { 250 /* See the comment in isfree. */ 251 return; 252 } 253 large_dalloc(tsdn, edata); 254 } 255 } 256 257 static inline void 258 arena_dalloc_no_tcache(tsdn_t *tsdn, void *ptr) { 259 assert(ptr != NULL); 260 261 emap_alloc_ctx_t alloc_ctx; 262 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, &alloc_ctx); 263 264 if (config_debug) { 265 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, 266 ptr); 267 assert(alloc_ctx.szind == edata_szind_get(edata)); 268 assert(alloc_ctx.szind < SC_NSIZES); 269 assert(alloc_ctx.slab == edata_slab_get(edata)); 270 } 271 272 if (likely(alloc_ctx.slab)) { 273 /* Small allocation. */ 274 arena_dalloc_small(tsdn, ptr); 275 } else { 276 arena_dalloc_large_no_tcache(tsdn, ptr, alloc_ctx.szind); 277 } 278 } 279 280 JEMALLOC_ALWAYS_INLINE void 281 arena_dalloc_large(tsdn_t *tsdn, void *ptr, tcache_t *tcache, szind_t szind, 282 bool slow_path) { 283 if (szind < nhbins) { 284 if (config_prof && unlikely(szind < SC_NBINS)) { 285 arena_dalloc_promoted(tsdn, ptr, tcache, slow_path); 286 } else { 287 tcache_dalloc_large(tsdn_tsd(tsdn), tcache, ptr, szind, 288 slow_path); 289 } 290 } else { 291 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, 292 ptr); 293 if (large_dalloc_safety_checks(edata, ptr, szind)) { 294 /* See the comment in isfree. */ 295 return; 296 } 297 large_dalloc(tsdn, edata); 298 } 299 } 300 301 JEMALLOC_ALWAYS_INLINE void 302 arena_dalloc(tsdn_t *tsdn, void *ptr, tcache_t *tcache, 303 emap_alloc_ctx_t *caller_alloc_ctx, bool slow_path) { 304 assert(!tsdn_null(tsdn) || tcache == NULL); 305 assert(ptr != NULL); 306 307 if (unlikely(tcache == NULL)) { 308 arena_dalloc_no_tcache(tsdn, ptr); 309 return; 310 } 311 312 emap_alloc_ctx_t alloc_ctx; 313 if (caller_alloc_ctx != NULL) { 314 alloc_ctx = *caller_alloc_ctx; 315 } else { 316 util_assume(!tsdn_null(tsdn)); 317 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, 318 &alloc_ctx); 319 } 320 321 if (config_debug) { 322 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, 323 ptr); 324 assert(alloc_ctx.szind == edata_szind_get(edata)); 325 assert(alloc_ctx.szind < SC_NSIZES); 326 assert(alloc_ctx.slab == edata_slab_get(edata)); 327 } 328 329 if (likely(alloc_ctx.slab)) { 330 /* Small allocation. */ 331 tcache_dalloc_small(tsdn_tsd(tsdn), tcache, ptr, 332 alloc_ctx.szind, slow_path); 333 } else { 334 arena_dalloc_large(tsdn, ptr, tcache, alloc_ctx.szind, 335 slow_path); 336 } 337 } 338 339 static inline void 340 arena_sdalloc_no_tcache(tsdn_t *tsdn, void *ptr, size_t size) { 341 assert(ptr != NULL); 342 assert(size <= SC_LARGE_MAXCLASS); 343 344 emap_alloc_ctx_t alloc_ctx; 345 if (!config_prof || !opt_prof) { 346 /* 347 * There is no risk of being confused by a promoted sampled 348 * object, so base szind and slab on the given size. 349 */ 350 alloc_ctx.szind = sz_size2index(size); 351 alloc_ctx.slab = (alloc_ctx.szind < SC_NBINS); 352 } 353 354 if ((config_prof && opt_prof) || config_debug) { 355 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, 356 &alloc_ctx); 357 358 assert(alloc_ctx.szind == sz_size2index(size)); 359 assert((config_prof && opt_prof) 360 || alloc_ctx.slab == (alloc_ctx.szind < SC_NBINS)); 361 362 if (config_debug) { 363 edata_t *edata = emap_edata_lookup(tsdn, 364 &arena_emap_global, ptr); 365 assert(alloc_ctx.szind == edata_szind_get(edata)); 366 assert(alloc_ctx.slab == edata_slab_get(edata)); 367 } 368 } 369 370 if (likely(alloc_ctx.slab)) { 371 /* Small allocation. */ 372 arena_dalloc_small(tsdn, ptr); 373 } else { 374 arena_dalloc_large_no_tcache(tsdn, ptr, alloc_ctx.szind); 375 } 376 } 377 378 JEMALLOC_ALWAYS_INLINE void 379 arena_sdalloc(tsdn_t *tsdn, void *ptr, size_t size, tcache_t *tcache, 380 emap_alloc_ctx_t *caller_alloc_ctx, bool slow_path) { 381 assert(!tsdn_null(tsdn) || tcache == NULL); 382 assert(ptr != NULL); 383 assert(size <= SC_LARGE_MAXCLASS); 384 385 if (unlikely(tcache == NULL)) { 386 arena_sdalloc_no_tcache(tsdn, ptr, size); 387 return; 388 } 389 390 emap_alloc_ctx_t alloc_ctx; 391 if (config_prof && opt_prof) { 392 if (caller_alloc_ctx == NULL) { 393 /* Uncommon case and should be a static check. */ 394 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, 395 &alloc_ctx); 396 assert(alloc_ctx.szind == sz_size2index(size)); 397 } else { 398 alloc_ctx = *caller_alloc_ctx; 399 } 400 } else { 401 /* 402 * There is no risk of being confused by a promoted sampled 403 * object, so base szind and slab on the given size. 404 */ 405 alloc_ctx.szind = sz_size2index(size); 406 alloc_ctx.slab = (alloc_ctx.szind < SC_NBINS); 407 } 408 409 if (config_debug) { 410 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, 411 ptr); 412 assert(alloc_ctx.szind == edata_szind_get(edata)); 413 assert(alloc_ctx.slab == edata_slab_get(edata)); 414 } 415 416 if (likely(alloc_ctx.slab)) { 417 /* Small allocation. */ 418 tcache_dalloc_small(tsdn_tsd(tsdn), tcache, ptr, 419 alloc_ctx.szind, slow_path); 420 } else { 421 arena_dalloc_large(tsdn, ptr, tcache, alloc_ctx.szind, 422 slow_path); 423 } 424 } 425 426 static inline void 427 arena_cache_oblivious_randomize(tsdn_t *tsdn, arena_t *arena, edata_t *edata, 428 size_t alignment) { 429 assert(edata_base_get(edata) == edata_addr_get(edata)); 430 431 if (alignment < PAGE) { 432 unsigned lg_range = LG_PAGE - 433 lg_floor(CACHELINE_CEILING(alignment)); 434 size_t r; 435 if (!tsdn_null(tsdn)) { 436 tsd_t *tsd = tsdn_tsd(tsdn); 437 r = (size_t)prng_lg_range_u64( 438 tsd_prng_statep_get(tsd), lg_range); 439 } else { 440 uint64_t stack_value = (uint64_t)(uintptr_t)&r; 441 r = (size_t)prng_lg_range_u64(&stack_value, lg_range); 442 } 443 uintptr_t random_offset = ((uintptr_t)r) << (LG_PAGE - 444 lg_range); 445 edata->e_addr = (void *)((uintptr_t)edata->e_addr + 446 random_offset); 447 assert(ALIGNMENT_ADDR2BASE(edata->e_addr, alignment) == 448 edata->e_addr); 449 } 450 } 451 452 /* 453 * The dalloc bin info contains just the information that the common paths need 454 * during tcache flushes. By force-inlining these paths, and using local copies 455 * of data (so that the compiler knows it's constant), we avoid a whole bunch of 456 * redundant loads and stores by leaving this information in registers. 457 */ 458 typedef struct arena_dalloc_bin_locked_info_s arena_dalloc_bin_locked_info_t; 459 struct arena_dalloc_bin_locked_info_s { 460 div_info_t div_info; 461 uint32_t nregs; 462 uint64_t ndalloc; 463 }; 464 465 JEMALLOC_ALWAYS_INLINE size_t 466 arena_slab_regind(arena_dalloc_bin_locked_info_t *info, szind_t binind, 467 edata_t *slab, const void *ptr) { 468 size_t diff, regind; 469 470 /* Freeing a pointer outside the slab can cause assertion failure. */ 471 assert((uintptr_t)ptr >= (uintptr_t)edata_addr_get(slab)); 472 assert((uintptr_t)ptr < (uintptr_t)edata_past_get(slab)); 473 /* Freeing an interior pointer can cause assertion failure. */ 474 assert(((uintptr_t)ptr - (uintptr_t)edata_addr_get(slab)) % 475 (uintptr_t)bin_infos[binind].reg_size == 0); 476 477 diff = (size_t)((uintptr_t)ptr - (uintptr_t)edata_addr_get(slab)); 478 479 /* Avoid doing division with a variable divisor. */ 480 regind = div_compute(&info->div_info, diff); 481 482 assert(regind < bin_infos[binind].nregs); 483 484 return regind; 485 } 486 487 JEMALLOC_ALWAYS_INLINE void 488 arena_dalloc_bin_locked_begin(arena_dalloc_bin_locked_info_t *info, 489 szind_t binind) { 490 info->div_info = arena_binind_div_info[binind]; 491 info->nregs = bin_infos[binind].nregs; 492 info->ndalloc = 0; 493 } 494 495 /* 496 * Does the deallocation work associated with freeing a single pointer (a 497 * "step") in between a arena_dalloc_bin_locked begin and end call. 498 * 499 * Returns true if arena_slab_dalloc must be called on slab. Doesn't do 500 * stats updates, which happen during finish (this lets running counts get left 501 * in a register). 502 */ 503 JEMALLOC_ALWAYS_INLINE bool 504 arena_dalloc_bin_locked_step(tsdn_t *tsdn, arena_t *arena, bin_t *bin, 505 arena_dalloc_bin_locked_info_t *info, szind_t binind, edata_t *slab, 506 void *ptr) { 507 const bin_info_t *bin_info = &bin_infos[binind]; 508 size_t regind = arena_slab_regind(info, binind, slab, ptr); 509 slab_data_t *slab_data = edata_slab_data_get(slab); 510 511 assert(edata_nfree_get(slab) < bin_info->nregs); 512 /* Freeing an unallocated pointer can cause assertion failure. */ 513 assert(bitmap_get(slab_data->bitmap, &bin_info->bitmap_info, regind)); 514 515 bitmap_unset(slab_data->bitmap, &bin_info->bitmap_info, regind); 516 edata_nfree_inc(slab); 517 518 if (config_stats) { 519 info->ndalloc++; 520 } 521 522 unsigned nfree = edata_nfree_get(slab); 523 if (nfree == bin_info->nregs) { 524 arena_dalloc_bin_locked_handle_newly_empty(tsdn, arena, slab, 525 bin); 526 return true; 527 } else if (nfree == 1 && slab != bin->slabcur) { 528 arena_dalloc_bin_locked_handle_newly_nonempty(tsdn, arena, slab, 529 bin); 530 } 531 return false; 532 } 533 534 JEMALLOC_ALWAYS_INLINE void 535 arena_dalloc_bin_locked_finish(tsdn_t *tsdn, arena_t *arena, bin_t *bin, 536 arena_dalloc_bin_locked_info_t *info) { 537 if (config_stats) { 538 bin->stats.ndalloc += info->ndalloc; 539 assert(bin->stats.curregs >= (size_t)info->ndalloc); 540 bin->stats.curregs -= (size_t)info->ndalloc; 541 } 542 } 543 544 static inline bin_t * 545 arena_get_bin(arena_t *arena, szind_t binind, unsigned binshard) { 546 bin_t *shard0 = (bin_t *)((uintptr_t)arena + arena_bin_offsets[binind]); 547 return shard0 + binshard; 548 } 549 550 #endif /* JEMALLOC_INTERNAL_ARENA_INLINES_B_H */ 551