1 #define JEMALLOC_ARENA_C_ 2 #include "jemalloc/internal/jemalloc_internal.h" 3 4 /******************************************************************************/ 5 /* Data. */ 6 7 ssize_t opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT; 8 arena_bin_info_t arena_bin_info[NBINS]; 9 10 JEMALLOC_ALIGNED(CACHELINE) 11 const uint32_t small_bin2size_tab[NBINS] = { 12 #define B2S_bin_yes(size) \ 13 size, 14 #define B2S_bin_no(size) 15 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \ 16 B2S_bin_##bin((ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta)) 17 SIZE_CLASSES 18 #undef B2S_bin_yes 19 #undef B2S_bin_no 20 #undef SC 21 }; 22 23 JEMALLOC_ALIGNED(CACHELINE) 24 const uint8_t small_size2bin_tab[] = { 25 #define S2B_3(i) i, 26 #define S2B_4(i) S2B_3(i) S2B_3(i) 27 #define S2B_5(i) S2B_4(i) S2B_4(i) 28 #define S2B_6(i) S2B_5(i) S2B_5(i) 29 #define S2B_7(i) S2B_6(i) S2B_6(i) 30 #define S2B_8(i) S2B_7(i) S2B_7(i) 31 #define S2B_9(i) S2B_8(i) S2B_8(i) 32 #define S2B_no(i) 33 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \ 34 S2B_##lg_delta_lookup(index) 35 SIZE_CLASSES 36 #undef S2B_3 37 #undef S2B_4 38 #undef S2B_5 39 #undef S2B_6 40 #undef S2B_7 41 #undef S2B_8 42 #undef S2B_9 43 #undef S2B_no 44 #undef SC 45 }; 46 47 /******************************************************************************/ 48 /* 49 * Function prototypes for static functions that are referenced prior to 50 * definition. 51 */ 52 53 static void arena_purge(arena_t *arena, bool all); 54 static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, 55 bool cleaned); 56 static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, 57 arena_run_t *run, arena_bin_t *bin); 58 static void arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, 59 arena_run_t *run, arena_bin_t *bin); 60 61 /******************************************************************************/ 62 63 JEMALLOC_INLINE_C size_t 64 arena_mapelm_to_pageind(arena_chunk_map_t *mapelm) 65 { 66 uintptr_t map_offset = 67 CHUNK_ADDR2OFFSET(mapelm) - offsetof(arena_chunk_t, map); 68 69 return ((map_offset / sizeof(arena_chunk_map_t)) + map_bias); 70 } 71 72 JEMALLOC_INLINE_C size_t 73 arena_mapelm_to_bits(arena_chunk_map_t *mapelm) 74 { 75 76 return (mapelm->bits); 77 } 78 79 static inline int 80 arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 81 { 82 uintptr_t a_mapelm = (uintptr_t)a; 83 uintptr_t b_mapelm = (uintptr_t)b; 84 85 assert(a != NULL); 86 assert(b != NULL); 87 88 return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm)); 89 } 90 91 /* Generate red-black tree functions. */ 92 rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, 93 u.rb_link, arena_run_comp) 94 95 static inline int 96 arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 97 { 98 int ret; 99 size_t a_size; 100 size_t b_size = arena_mapelm_to_bits(b) & ~PAGE_MASK; 101 uintptr_t a_mapelm = (uintptr_t)a; 102 uintptr_t b_mapelm = (uintptr_t)b; 103 104 if (a_mapelm & CHUNK_MAP_KEY) 105 a_size = a_mapelm & ~PAGE_MASK; 106 else 107 a_size = arena_mapelm_to_bits(a) & ~PAGE_MASK; 108 109 ret = (a_size > b_size) - (a_size < b_size); 110 if (ret == 0 && (!(a_mapelm & CHUNK_MAP_KEY))) 111 ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm); 112 113 return (ret); 114 } 115 116 /* Generate red-black tree functions. */ 117 rb_gen(static UNUSED, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, 118 u.rb_link, arena_avail_comp) 119 120 static inline int 121 arena_chunk_dirty_comp(arena_chunk_t *a, arena_chunk_t *b) 122 { 123 124 assert(a != NULL); 125 assert(b != NULL); 126 127 /* 128 * Short-circuit for self comparison. The following comparison code 129 * would come to the same result, but at the cost of executing the slow 130 * path. 131 */ 132 if (a == b) 133 return (0); 134 135 /* 136 * Order such that chunks with higher fragmentation are "less than" 137 * those with lower fragmentation -- purging order is from "least" to 138 * "greatest". Fragmentation is measured as: 139 * 140 * mean current avail run size 141 * -------------------------------- 142 * mean defragmented avail run size 143 * 144 * navail 145 * ----------- 146 * nruns_avail nruns_avail-nruns_adjac 147 * = ========================= = ----------------------- 148 * navail nruns_avail 149 * ----------------------- 150 * nruns_avail-nruns_adjac 151 * 152 * The following code multiplies away the denominator prior to 153 * comparison, in order to avoid division. 154 * 155 */ 156 { 157 size_t a_val = (a->nruns_avail - a->nruns_adjac) * 158 b->nruns_avail; 159 size_t b_val = (b->nruns_avail - b->nruns_adjac) * 160 a->nruns_avail; 161 162 if (a_val < b_val) 163 return (1); 164 if (a_val > b_val) 165 return (-1); 166 } 167 /* 168 * Break ties by chunk address. For fragmented chunks, report lower 169 * addresses as "lower", so that fragmentation reduction happens first 170 * at lower addresses. However, use the opposite ordering for 171 * unfragmented chunks, in order to increase the chances of 172 * re-allocating dirty runs. 173 */ 174 { 175 uintptr_t a_chunk = (uintptr_t)a; 176 uintptr_t b_chunk = (uintptr_t)b; 177 int ret = ((a_chunk > b_chunk) - (a_chunk < b_chunk)); 178 if (a->nruns_adjac == 0) { 179 assert(b->nruns_adjac == 0); 180 ret = -ret; 181 } 182 return (ret); 183 } 184 } 185 186 /* Generate red-black tree functions. */ 187 rb_gen(static UNUSED, arena_chunk_dirty_, arena_chunk_tree_t, arena_chunk_t, 188 dirty_link, arena_chunk_dirty_comp) 189 190 static inline bool 191 arena_avail_adjac_pred(arena_chunk_t *chunk, size_t pageind) 192 { 193 bool ret; 194 195 if (pageind-1 < map_bias) 196 ret = false; 197 else { 198 ret = (arena_mapbits_allocated_get(chunk, pageind-1) == 0); 199 assert(ret == false || arena_mapbits_dirty_get(chunk, 200 pageind-1) != arena_mapbits_dirty_get(chunk, pageind)); 201 } 202 return (ret); 203 } 204 205 static inline bool 206 arena_avail_adjac_succ(arena_chunk_t *chunk, size_t pageind, size_t npages) 207 { 208 bool ret; 209 210 if (pageind+npages == chunk_npages) 211 ret = false; 212 else { 213 assert(pageind+npages < chunk_npages); 214 ret = (arena_mapbits_allocated_get(chunk, pageind+npages) == 0); 215 assert(ret == false || arena_mapbits_dirty_get(chunk, pageind) 216 != arena_mapbits_dirty_get(chunk, pageind+npages)); 217 } 218 return (ret); 219 } 220 221 static inline bool 222 arena_avail_adjac(arena_chunk_t *chunk, size_t pageind, size_t npages) 223 { 224 225 return (arena_avail_adjac_pred(chunk, pageind) || 226 arena_avail_adjac_succ(chunk, pageind, npages)); 227 } 228 229 static void 230 arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind, 231 size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ) 232 { 233 234 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> 235 LG_PAGE)); 236 237 /* 238 * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be 239 * removed and reinserted even if the run to be inserted is clean. 240 */ 241 if (chunk->ndirty != 0) 242 arena_chunk_dirty_remove(&arena->chunks_dirty, chunk); 243 244 if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind)) 245 chunk->nruns_adjac++; 246 if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages)) 247 chunk->nruns_adjac++; 248 chunk->nruns_avail++; 249 assert(chunk->nruns_avail > chunk->nruns_adjac); 250 251 if (arena_mapbits_dirty_get(chunk, pageind) != 0) { 252 arena->ndirty += npages; 253 chunk->ndirty += npages; 254 } 255 if (chunk->ndirty != 0) 256 arena_chunk_dirty_insert(&arena->chunks_dirty, chunk); 257 258 arena_avail_tree_insert(&arena->runs_avail, arena_mapp_get(chunk, 259 pageind)); 260 } 261 262 static void 263 arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind, 264 size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ) 265 { 266 267 assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >> 268 LG_PAGE)); 269 270 /* 271 * chunks_dirty is keyed by nruns_{avail,adjac}, so the chunk must be 272 * removed and reinserted even if the run to be removed is clean. 273 */ 274 if (chunk->ndirty != 0) 275 arena_chunk_dirty_remove(&arena->chunks_dirty, chunk); 276 277 if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind)) 278 chunk->nruns_adjac--; 279 if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages)) 280 chunk->nruns_adjac--; 281 chunk->nruns_avail--; 282 assert(chunk->nruns_avail > chunk->nruns_adjac || (chunk->nruns_avail 283 == 0 && chunk->nruns_adjac == 0)); 284 285 if (arena_mapbits_dirty_get(chunk, pageind) != 0) { 286 arena->ndirty -= npages; 287 chunk->ndirty -= npages; 288 } 289 if (chunk->ndirty != 0) 290 arena_chunk_dirty_insert(&arena->chunks_dirty, chunk); 291 292 arena_avail_tree_remove(&arena->runs_avail, arena_mapp_get(chunk, 293 pageind)); 294 } 295 296 static inline void * 297 arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info) 298 { 299 void *ret; 300 unsigned regind; 301 bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + 302 (uintptr_t)bin_info->bitmap_offset); 303 304 assert(run->nfree > 0); 305 assert(bitmap_full(bitmap, &bin_info->bitmap_info) == false); 306 307 regind = bitmap_sfu(bitmap, &bin_info->bitmap_info); 308 ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset + 309 (uintptr_t)(bin_info->reg_interval * regind)); 310 run->nfree--; 311 if (regind == run->nextind) 312 run->nextind++; 313 assert(regind < run->nextind); 314 return (ret); 315 } 316 317 static inline void 318 arena_run_reg_dalloc(arena_run_t *run, void *ptr) 319 { 320 arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 321 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; 322 size_t mapbits = arena_mapbits_get(chunk, pageind); 323 size_t binind = arena_ptr_small_binind_get(ptr, mapbits); 324 arena_bin_info_t *bin_info = &arena_bin_info[binind]; 325 unsigned regind = arena_run_regind(run, bin_info, ptr); 326 bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + 327 (uintptr_t)bin_info->bitmap_offset); 328 329 assert(run->nfree < bin_info->nregs); 330 /* Freeing an interior pointer can cause assertion failure. */ 331 assert(((uintptr_t)ptr - ((uintptr_t)run + 332 (uintptr_t)bin_info->reg0_offset)) % 333 (uintptr_t)bin_info->reg_interval == 0); 334 assert((uintptr_t)ptr >= (uintptr_t)run + 335 (uintptr_t)bin_info->reg0_offset); 336 /* Freeing an unallocated pointer can cause assertion failure. */ 337 assert(bitmap_get(bitmap, &bin_info->bitmap_info, regind)); 338 339 bitmap_unset(bitmap, &bin_info->bitmap_info, regind); 340 run->nfree++; 341 } 342 343 static inline void 344 arena_run_zero(arena_chunk_t *chunk, size_t run_ind, size_t npages) 345 { 346 347 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + 348 (run_ind << LG_PAGE)), (npages << LG_PAGE)); 349 memset((void *)((uintptr_t)chunk + (run_ind << LG_PAGE)), 0, 350 (npages << LG_PAGE)); 351 } 352 353 static inline void 354 arena_run_page_mark_zeroed(arena_chunk_t *chunk, size_t run_ind) 355 { 356 357 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)((uintptr_t)chunk + (run_ind 358 << LG_PAGE)), PAGE); 359 } 360 361 static inline void 362 arena_run_page_validate_zeroed(arena_chunk_t *chunk, size_t run_ind) 363 { 364 size_t i; 365 UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << LG_PAGE)); 366 367 arena_run_page_mark_zeroed(chunk, run_ind); 368 for (i = 0; i < PAGE / sizeof(size_t); i++) 369 assert(p[i] == 0); 370 } 371 372 static void 373 arena_cactive_update(arena_t *arena, size_t add_pages, size_t sub_pages) 374 { 375 376 if (config_stats) { 377 ssize_t cactive_diff = CHUNK_CEILING((arena->nactive + 378 add_pages) << LG_PAGE) - CHUNK_CEILING((arena->nactive - 379 sub_pages) << LG_PAGE); 380 if (cactive_diff != 0) 381 stats_cactive_add(cactive_diff); 382 } 383 } 384 385 static void 386 arena_run_split_remove(arena_t *arena, arena_chunk_t *chunk, size_t run_ind, 387 size_t flag_dirty, size_t need_pages) 388 { 389 size_t total_pages, rem_pages; 390 391 total_pages = arena_mapbits_unallocated_size_get(chunk, run_ind) >> 392 LG_PAGE; 393 assert(arena_mapbits_dirty_get(chunk, run_ind+total_pages-1) == 394 flag_dirty); 395 assert(need_pages <= total_pages); 396 rem_pages = total_pages - need_pages; 397 398 arena_avail_remove(arena, chunk, run_ind, total_pages, true, true); 399 arena_cactive_update(arena, need_pages, 0); 400 arena->nactive += need_pages; 401 402 /* Keep track of trailing unused pages for later use. */ 403 if (rem_pages > 0) { 404 if (flag_dirty != 0) { 405 arena_mapbits_unallocated_set(chunk, 406 run_ind+need_pages, (rem_pages << LG_PAGE), 407 flag_dirty); 408 arena_mapbits_unallocated_set(chunk, 409 run_ind+total_pages-1, (rem_pages << LG_PAGE), 410 flag_dirty); 411 } else { 412 arena_mapbits_unallocated_set(chunk, run_ind+need_pages, 413 (rem_pages << LG_PAGE), 414 arena_mapbits_unzeroed_get(chunk, 415 run_ind+need_pages)); 416 arena_mapbits_unallocated_set(chunk, 417 run_ind+total_pages-1, (rem_pages << LG_PAGE), 418 arena_mapbits_unzeroed_get(chunk, 419 run_ind+total_pages-1)); 420 } 421 arena_avail_insert(arena, chunk, run_ind+need_pages, rem_pages, 422 false, true); 423 } 424 } 425 426 static void 427 arena_run_split_large_helper(arena_t *arena, arena_run_t *run, size_t size, 428 bool remove, bool zero) 429 { 430 arena_chunk_t *chunk; 431 size_t flag_dirty, run_ind, need_pages, i; 432 433 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 434 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE); 435 flag_dirty = arena_mapbits_dirty_get(chunk, run_ind); 436 need_pages = (size >> LG_PAGE); 437 assert(need_pages > 0); 438 439 if (remove) { 440 arena_run_split_remove(arena, chunk, run_ind, flag_dirty, 441 need_pages); 442 } 443 444 if (zero) { 445 if (flag_dirty == 0) { 446 /* 447 * The run is clean, so some pages may be zeroed (i.e. 448 * never before touched). 449 */ 450 for (i = 0; i < need_pages; i++) { 451 if (arena_mapbits_unzeroed_get(chunk, run_ind+i) 452 != 0) 453 arena_run_zero(chunk, run_ind+i, 1); 454 else if (config_debug) { 455 arena_run_page_validate_zeroed(chunk, 456 run_ind+i); 457 } else { 458 arena_run_page_mark_zeroed(chunk, 459 run_ind+i); 460 } 461 } 462 } else { 463 /* The run is dirty, so all pages must be zeroed. */ 464 arena_run_zero(chunk, run_ind, need_pages); 465 } 466 } else { 467 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + 468 (run_ind << LG_PAGE)), (need_pages << LG_PAGE)); 469 } 470 471 /* 472 * Set the last element first, in case the run only contains one page 473 * (i.e. both statements set the same element). 474 */ 475 arena_mapbits_large_set(chunk, run_ind+need_pages-1, 0, flag_dirty); 476 arena_mapbits_large_set(chunk, run_ind, size, flag_dirty); 477 } 478 479 static void 480 arena_run_split_large(arena_t *arena, arena_run_t *run, size_t size, bool zero) 481 { 482 483 arena_run_split_large_helper(arena, run, size, true, zero); 484 } 485 486 static void 487 arena_run_init_large(arena_t *arena, arena_run_t *run, size_t size, bool zero) 488 { 489 490 arena_run_split_large_helper(arena, run, size, false, zero); 491 } 492 493 static void 494 arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size, 495 size_t binind) 496 { 497 arena_chunk_t *chunk; 498 size_t flag_dirty, run_ind, need_pages, i; 499 500 assert(binind != BININD_INVALID); 501 502 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 503 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE); 504 flag_dirty = arena_mapbits_dirty_get(chunk, run_ind); 505 need_pages = (size >> LG_PAGE); 506 assert(need_pages > 0); 507 508 arena_run_split_remove(arena, chunk, run_ind, flag_dirty, need_pages); 509 510 /* 511 * Propagate the dirty and unzeroed flags to the allocated small run, 512 * so that arena_dalloc_bin_run() has the ability to conditionally trim 513 * clean pages. 514 */ 515 arena_mapbits_small_set(chunk, run_ind, 0, binind, flag_dirty); 516 /* 517 * The first page will always be dirtied during small run 518 * initialization, so a validation failure here would not actually 519 * cause an observable failure. 520 */ 521 if (config_debug && flag_dirty == 0 && arena_mapbits_unzeroed_get(chunk, 522 run_ind) == 0) 523 arena_run_page_validate_zeroed(chunk, run_ind); 524 for (i = 1; i < need_pages - 1; i++) { 525 arena_mapbits_small_set(chunk, run_ind+i, i, binind, 0); 526 if (config_debug && flag_dirty == 0 && 527 arena_mapbits_unzeroed_get(chunk, run_ind+i) == 0) 528 arena_run_page_validate_zeroed(chunk, run_ind+i); 529 } 530 arena_mapbits_small_set(chunk, run_ind+need_pages-1, need_pages-1, 531 binind, flag_dirty); 532 if (config_debug && flag_dirty == 0 && arena_mapbits_unzeroed_get(chunk, 533 run_ind+need_pages-1) == 0) 534 arena_run_page_validate_zeroed(chunk, run_ind+need_pages-1); 535 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk + 536 (run_ind << LG_PAGE)), (need_pages << LG_PAGE)); 537 } 538 539 static arena_chunk_t * 540 arena_chunk_init_spare(arena_t *arena) 541 { 542 arena_chunk_t *chunk; 543 544 assert(arena->spare != NULL); 545 546 chunk = arena->spare; 547 arena->spare = NULL; 548 549 assert(arena_mapbits_allocated_get(chunk, map_bias) == 0); 550 assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0); 551 assert(arena_mapbits_unallocated_size_get(chunk, map_bias) == 552 arena_maxclass); 553 assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) == 554 arena_maxclass); 555 assert(arena_mapbits_dirty_get(chunk, map_bias) == 556 arena_mapbits_dirty_get(chunk, chunk_npages-1)); 557 558 return (chunk); 559 } 560 561 static arena_chunk_t * 562 arena_chunk_alloc_internal(arena_t *arena, size_t size, size_t alignment, 563 bool *zero) 564 { 565 arena_chunk_t *chunk; 566 chunk_alloc_t *chunk_alloc; 567 chunk_dalloc_t *chunk_dalloc; 568 569 chunk_alloc = arena->chunk_alloc; 570 chunk_dalloc = arena->chunk_dalloc; 571 malloc_mutex_unlock(&arena->lock); 572 chunk = (arena_chunk_t *)chunk_alloc_arena(chunk_alloc, chunk_dalloc, 573 arena->ind, size, alignment, zero); 574 malloc_mutex_lock(&arena->lock); 575 if (config_stats && chunk != NULL) 576 arena->stats.mapped += chunksize; 577 578 return (chunk); 579 } 580 581 void * 582 arena_chunk_alloc_huge(arena_t *arena, size_t size, size_t alignment, 583 bool *zero) 584 { 585 void *ret; 586 chunk_alloc_t *chunk_alloc; 587 chunk_dalloc_t *chunk_dalloc; 588 589 malloc_mutex_lock(&arena->lock); 590 chunk_alloc = arena->chunk_alloc; 591 chunk_dalloc = arena->chunk_dalloc; 592 if (config_stats) { 593 /* Optimistically update stats prior to unlocking. */ 594 arena->stats.mapped += size; 595 arena->stats.allocated_huge += size; 596 arena->stats.nmalloc_huge++; 597 arena->stats.nrequests_huge++; 598 } 599 arena->nactive += (size >> LG_PAGE); 600 malloc_mutex_unlock(&arena->lock); 601 602 ret = chunk_alloc_arena(chunk_alloc, chunk_dalloc, arena->ind, 603 size, alignment, zero); 604 if (config_stats) { 605 if (ret != NULL) 606 stats_cactive_add(size); 607 else { 608 /* Revert optimistic stats updates. */ 609 malloc_mutex_lock(&arena->lock); 610 arena->stats.mapped -= size; 611 arena->stats.allocated_huge -= size; 612 arena->stats.nmalloc_huge--; 613 malloc_mutex_unlock(&arena->lock); 614 } 615 } 616 617 return (ret); 618 } 619 620 static arena_chunk_t * 621 arena_chunk_init_hard(arena_t *arena) 622 { 623 arena_chunk_t *chunk; 624 bool zero; 625 size_t unzeroed, i; 626 627 assert(arena->spare == NULL); 628 629 zero = false; 630 chunk = arena_chunk_alloc_internal(arena, chunksize, chunksize, &zero); 631 if (chunk == NULL) 632 return (NULL); 633 634 chunk->arena = arena; 635 636 /* 637 * Claim that no pages are in use, since the header is merely overhead. 638 */ 639 chunk->ndirty = 0; 640 641 chunk->nruns_avail = 0; 642 chunk->nruns_adjac = 0; 643 644 /* 645 * Initialize the map to contain one maximal free untouched run. Mark 646 * the pages as zeroed iff chunk_alloc() returned a zeroed chunk. 647 */ 648 unzeroed = zero ? 0 : CHUNK_MAP_UNZEROED; 649 arena_mapbits_unallocated_set(chunk, map_bias, arena_maxclass, 650 unzeroed); 651 /* 652 * There is no need to initialize the internal page map entries unless 653 * the chunk is not zeroed. 654 */ 655 if (zero == false) { 656 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED( 657 (void *)arena_mapp_get(chunk, map_bias+1), 658 (size_t)((uintptr_t) arena_mapp_get(chunk, chunk_npages-1) - 659 (uintptr_t)arena_mapp_get(chunk, map_bias+1))); 660 for (i = map_bias+1; i < chunk_npages-1; i++) 661 arena_mapbits_unzeroed_set(chunk, i, unzeroed); 662 } else { 663 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)arena_mapp_get(chunk, 664 map_bias+1), (size_t)((uintptr_t) arena_mapp_get(chunk, 665 chunk_npages-1) - (uintptr_t)arena_mapp_get(chunk, 666 map_bias+1))); 667 if (config_debug) { 668 for (i = map_bias+1; i < chunk_npages-1; i++) { 669 assert(arena_mapbits_unzeroed_get(chunk, i) == 670 unzeroed); 671 } 672 } 673 } 674 arena_mapbits_unallocated_set(chunk, chunk_npages-1, arena_maxclass, 675 unzeroed); 676 677 return (chunk); 678 } 679 680 static arena_chunk_t * 681 arena_chunk_alloc(arena_t *arena) 682 { 683 arena_chunk_t *chunk; 684 685 if (arena->spare != NULL) 686 chunk = arena_chunk_init_spare(arena); 687 else { 688 chunk = arena_chunk_init_hard(arena); 689 if (chunk == NULL) 690 return (NULL); 691 } 692 693 /* Insert the run into the runs_avail tree. */ 694 arena_avail_insert(arena, chunk, map_bias, chunk_npages-map_bias, 695 false, false); 696 697 return (chunk); 698 } 699 700 static void 701 arena_chunk_dalloc_internal(arena_t *arena, arena_chunk_t *chunk) 702 { 703 chunk_dalloc_t *chunk_dalloc; 704 705 chunk_dalloc = arena->chunk_dalloc; 706 malloc_mutex_unlock(&arena->lock); 707 chunk_dalloc((void *)chunk, chunksize, arena->ind); 708 malloc_mutex_lock(&arena->lock); 709 if (config_stats) 710 arena->stats.mapped -= chunksize; 711 } 712 713 void 714 arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t size) 715 { 716 chunk_dalloc_t *chunk_dalloc; 717 718 malloc_mutex_lock(&arena->lock); 719 chunk_dalloc = arena->chunk_dalloc; 720 if (config_stats) { 721 arena->stats.mapped -= size; 722 arena->stats.allocated_huge -= size; 723 arena->stats.ndalloc_huge++; 724 stats_cactive_sub(size); 725 } 726 arena->nactive -= (size >> LG_PAGE); 727 malloc_mutex_unlock(&arena->lock); 728 chunk_dalloc(chunk, size, arena->ind); 729 } 730 731 static void 732 arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk) 733 { 734 assert(arena_mapbits_allocated_get(chunk, map_bias) == 0); 735 assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0); 736 assert(arena_mapbits_unallocated_size_get(chunk, map_bias) == 737 arena_maxclass); 738 assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) == 739 arena_maxclass); 740 assert(arena_mapbits_dirty_get(chunk, map_bias) == 741 arena_mapbits_dirty_get(chunk, chunk_npages-1)); 742 743 /* 744 * Remove run from the runs_avail tree, so that the arena does not use 745 * it. 746 */ 747 arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias, 748 false, false); 749 750 if (arena->spare != NULL) { 751 arena_chunk_t *spare = arena->spare; 752 753 arena->spare = chunk; 754 arena_chunk_dalloc_internal(arena, spare); 755 } else 756 arena->spare = chunk; 757 } 758 759 static arena_run_t * 760 arena_run_alloc_large_helper(arena_t *arena, size_t size, bool zero) 761 { 762 arena_run_t *run; 763 arena_chunk_map_t *mapelm; 764 arena_chunk_map_t *key; 765 766 key = (arena_chunk_map_t *)(size | CHUNK_MAP_KEY); 767 mapelm = arena_avail_tree_nsearch(&arena->runs_avail, key); 768 if (mapelm != NULL) { 769 arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); 770 size_t pageind = arena_mapelm_to_pageind(mapelm); 771 772 run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << 773 LG_PAGE)); 774 arena_run_split_large(arena, run, size, zero); 775 return (run); 776 } 777 778 return (NULL); 779 } 780 781 static arena_run_t * 782 arena_run_alloc_large(arena_t *arena, size_t size, bool zero) 783 { 784 arena_chunk_t *chunk; 785 arena_run_t *run; 786 787 assert(size <= arena_maxclass); 788 assert((size & PAGE_MASK) == 0); 789 790 /* Search the arena's chunks for the lowest best fit. */ 791 run = arena_run_alloc_large_helper(arena, size, zero); 792 if (run != NULL) 793 return (run); 794 795 /* 796 * No usable runs. Create a new chunk from which to allocate the run. 797 */ 798 chunk = arena_chunk_alloc(arena); 799 if (chunk != NULL) { 800 run = (arena_run_t *)((uintptr_t)chunk + (map_bias << LG_PAGE)); 801 arena_run_split_large(arena, run, size, zero); 802 return (run); 803 } 804 805 /* 806 * arena_chunk_alloc() failed, but another thread may have made 807 * sufficient memory available while this one dropped arena->lock in 808 * arena_chunk_alloc(), so search one more time. 809 */ 810 return (arena_run_alloc_large_helper(arena, size, zero)); 811 } 812 813 static arena_run_t * 814 arena_run_alloc_small_helper(arena_t *arena, size_t size, size_t binind) 815 { 816 arena_run_t *run; 817 arena_chunk_map_t *mapelm; 818 arena_chunk_map_t *key; 819 820 key = (arena_chunk_map_t *)(size | CHUNK_MAP_KEY); 821 mapelm = arena_avail_tree_nsearch(&arena->runs_avail, key); 822 if (mapelm != NULL) { 823 arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); 824 size_t pageind = arena_mapelm_to_pageind(mapelm); 825 826 run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << 827 LG_PAGE)); 828 arena_run_split_small(arena, run, size, binind); 829 return (run); 830 } 831 832 return (NULL); 833 } 834 835 static arena_run_t * 836 arena_run_alloc_small(arena_t *arena, size_t size, size_t binind) 837 { 838 arena_chunk_t *chunk; 839 arena_run_t *run; 840 841 assert(size <= arena_maxclass); 842 assert((size & PAGE_MASK) == 0); 843 assert(binind != BININD_INVALID); 844 845 /* Search the arena's chunks for the lowest best fit. */ 846 run = arena_run_alloc_small_helper(arena, size, binind); 847 if (run != NULL) 848 return (run); 849 850 /* 851 * No usable runs. Create a new chunk from which to allocate the run. 852 */ 853 chunk = arena_chunk_alloc(arena); 854 if (chunk != NULL) { 855 run = (arena_run_t *)((uintptr_t)chunk + (map_bias << LG_PAGE)); 856 arena_run_split_small(arena, run, size, binind); 857 return (run); 858 } 859 860 /* 861 * arena_chunk_alloc() failed, but another thread may have made 862 * sufficient memory available while this one dropped arena->lock in 863 * arena_chunk_alloc(), so search one more time. 864 */ 865 return (arena_run_alloc_small_helper(arena, size, binind)); 866 } 867 868 static inline void 869 arena_maybe_purge(arena_t *arena) 870 { 871 #if !defined(ANDROID_ALWAYS_PURGE) 872 size_t npurgeable, threshold; 873 874 /* Don't purge if the option is disabled. */ 875 if (opt_lg_dirty_mult < 0) 876 return; 877 #endif 878 /* Don't purge if all dirty pages are already being purged. */ 879 if (arena->ndirty <= arena->npurgatory) 880 return; 881 #if !defined(ANDROID_ALWAYS_PURGE) 882 npurgeable = arena->ndirty - arena->npurgatory; 883 threshold = (arena->nactive >> opt_lg_dirty_mult); 884 /* 885 * Don't purge unless the number of purgeable pages exceeds the 886 * threshold. 887 */ 888 if (npurgeable <= threshold) 889 return; 890 #endif 891 892 arena_purge(arena, false); 893 } 894 895 static arena_chunk_t * 896 chunks_dirty_iter_cb(arena_chunk_tree_t *tree, arena_chunk_t *chunk, void *arg) 897 { 898 size_t *ndirty = (size_t *)arg; 899 900 assert(chunk->ndirty != 0); 901 *ndirty += chunk->ndirty; 902 return (NULL); 903 } 904 905 static size_t 906 arena_compute_npurgatory(arena_t *arena, bool all) 907 { 908 size_t npurgatory, npurgeable; 909 910 /* 911 * Compute the minimum number of pages that this thread should try to 912 * purge. 913 */ 914 npurgeable = arena->ndirty - arena->npurgatory; 915 916 if (all == false) { 917 size_t threshold = (arena->nactive >> opt_lg_dirty_mult); 918 919 npurgatory = npurgeable - threshold; 920 } else 921 npurgatory = npurgeable; 922 923 return (npurgatory); 924 } 925 926 static void 927 arena_chunk_stash_dirty(arena_t *arena, arena_chunk_t *chunk, bool all, 928 arena_chunk_mapelms_t *mapelms) 929 { 930 size_t pageind, npages; 931 932 /* 933 * Temporarily allocate free dirty runs within chunk. If all is false, 934 * only operate on dirty runs that are fragments; otherwise operate on 935 * all dirty runs. 936 */ 937 for (pageind = map_bias; pageind < chunk_npages; pageind += npages) { 938 arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind); 939 if (arena_mapbits_allocated_get(chunk, pageind) == 0) { 940 size_t run_size = 941 arena_mapbits_unallocated_size_get(chunk, pageind); 942 943 npages = run_size >> LG_PAGE; 944 assert(pageind + npages <= chunk_npages); 945 assert(arena_mapbits_dirty_get(chunk, pageind) == 946 arena_mapbits_dirty_get(chunk, pageind+npages-1)); 947 948 if (arena_mapbits_dirty_get(chunk, pageind) != 0 && 949 (all || arena_avail_adjac(chunk, pageind, 950 npages))) { 951 arena_run_t *run = (arena_run_t *)((uintptr_t) 952 chunk + (uintptr_t)(pageind << LG_PAGE)); 953 954 arena_run_split_large(arena, run, run_size, 955 false); 956 /* Append to list for later processing. */ 957 ql_elm_new(mapelm, u.ql_link); 958 ql_tail_insert(mapelms, mapelm, u.ql_link); 959 } 960 } else { 961 /* Skip run. */ 962 if (arena_mapbits_large_get(chunk, pageind) != 0) { 963 npages = arena_mapbits_large_size_get(chunk, 964 pageind) >> LG_PAGE; 965 } else { 966 size_t binind; 967 arena_bin_info_t *bin_info; 968 arena_run_t *run = (arena_run_t *)((uintptr_t) 969 chunk + (uintptr_t)(pageind << LG_PAGE)); 970 971 assert(arena_mapbits_small_runind_get(chunk, 972 pageind) == 0); 973 binind = arena_bin_index(arena, run->bin); 974 bin_info = &arena_bin_info[binind]; 975 npages = bin_info->run_size >> LG_PAGE; 976 } 977 } 978 } 979 assert(pageind == chunk_npages); 980 assert(chunk->ndirty == 0 || all == false); 981 assert(chunk->nruns_adjac == 0); 982 } 983 984 static size_t 985 arena_chunk_purge_stashed(arena_t *arena, arena_chunk_t *chunk, 986 arena_chunk_mapelms_t *mapelms) 987 { 988 size_t npurged, pageind, npages, nmadvise; 989 arena_chunk_map_t *mapelm; 990 991 malloc_mutex_unlock(&arena->lock); 992 if (config_stats) 993 nmadvise = 0; 994 npurged = 0; 995 ql_foreach(mapelm, mapelms, u.ql_link) { 996 bool unzeroed; 997 size_t flag_unzeroed, i; 998 999 pageind = arena_mapelm_to_pageind(mapelm); 1000 npages = arena_mapbits_large_size_get(chunk, pageind) >> 1001 LG_PAGE; 1002 assert(pageind + npages <= chunk_npages); 1003 unzeroed = pages_purge((void *)((uintptr_t)chunk + (pageind << 1004 LG_PAGE)), (npages << LG_PAGE)); 1005 flag_unzeroed = unzeroed ? CHUNK_MAP_UNZEROED : 0; 1006 /* 1007 * Set the unzeroed flag for all pages, now that pages_purge() 1008 * has returned whether the pages were zeroed as a side effect 1009 * of purging. This chunk map modification is safe even though 1010 * the arena mutex isn't currently owned by this thread, 1011 * because the run is marked as allocated, thus protecting it 1012 * from being modified by any other thread. As long as these 1013 * writes don't perturb the first and last elements' 1014 * CHUNK_MAP_ALLOCATED bits, behavior is well defined. 1015 */ 1016 for (i = 0; i < npages; i++) { 1017 arena_mapbits_unzeroed_set(chunk, pageind+i, 1018 flag_unzeroed); 1019 } 1020 npurged += npages; 1021 if (config_stats) 1022 nmadvise++; 1023 } 1024 malloc_mutex_lock(&arena->lock); 1025 if (config_stats) 1026 arena->stats.nmadvise += nmadvise; 1027 1028 return (npurged); 1029 } 1030 1031 static void 1032 arena_chunk_unstash_purged(arena_t *arena, arena_chunk_t *chunk, 1033 arena_chunk_mapelms_t *mapelms) 1034 { 1035 arena_chunk_map_t *mapelm; 1036 size_t pageind; 1037 1038 /* Deallocate runs. */ 1039 for (mapelm = ql_first(mapelms); mapelm != NULL; 1040 mapelm = ql_first(mapelms)) { 1041 arena_run_t *run; 1042 1043 pageind = arena_mapelm_to_pageind(mapelm); 1044 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)(pageind << 1045 LG_PAGE)); 1046 ql_remove(mapelms, mapelm, u.ql_link); 1047 arena_run_dalloc(arena, run, false, true); 1048 } 1049 } 1050 1051 static inline size_t 1052 arena_chunk_purge(arena_t *arena, arena_chunk_t *chunk, bool all) 1053 { 1054 size_t npurged; 1055 arena_chunk_mapelms_t mapelms; 1056 1057 ql_new(&mapelms); 1058 1059 /* 1060 * If chunk is the spare, temporarily re-allocate it, 1) so that its 1061 * run is reinserted into runs_avail, and 2) so that it cannot be 1062 * completely discarded by another thread while arena->lock is dropped 1063 * by this thread. Note that the arena_run_dalloc() call will 1064 * implicitly deallocate the chunk, so no explicit action is required 1065 * in this function to deallocate the chunk. 1066 * 1067 * Note that once a chunk contains dirty pages, it cannot again contain 1068 * a single run unless 1) it is a dirty run, or 2) this function purges 1069 * dirty pages and causes the transition to a single clean run. Thus 1070 * (chunk == arena->spare) is possible, but it is not possible for 1071 * this function to be called on the spare unless it contains a dirty 1072 * run. 1073 */ 1074 if (chunk == arena->spare) { 1075 assert(arena_mapbits_dirty_get(chunk, map_bias) != 0); 1076 assert(arena_mapbits_dirty_get(chunk, chunk_npages-1) != 0); 1077 1078 arena_chunk_alloc(arena); 1079 } 1080 1081 if (config_stats) 1082 arena->stats.purged += chunk->ndirty; 1083 1084 /* 1085 * Operate on all dirty runs if there is no clean/dirty run 1086 * fragmentation. 1087 */ 1088 if (chunk->nruns_adjac == 0) 1089 all = true; 1090 1091 arena_chunk_stash_dirty(arena, chunk, all, &mapelms); 1092 npurged = arena_chunk_purge_stashed(arena, chunk, &mapelms); 1093 arena_chunk_unstash_purged(arena, chunk, &mapelms); 1094 1095 return (npurged); 1096 } 1097 1098 static void 1099 arena_purge(arena_t *arena, bool all) 1100 { 1101 arena_chunk_t *chunk; 1102 size_t npurgatory; 1103 if (config_debug) { 1104 size_t ndirty = 0; 1105 1106 arena_chunk_dirty_iter(&arena->chunks_dirty, NULL, 1107 chunks_dirty_iter_cb, (void *)&ndirty); 1108 assert(ndirty == arena->ndirty); 1109 } 1110 assert(arena->ndirty > arena->npurgatory || all); 1111 assert((arena->nactive >> opt_lg_dirty_mult) < (arena->ndirty - 1112 arena->npurgatory) || all); 1113 1114 if (config_stats) 1115 arena->stats.npurge++; 1116 1117 /* 1118 * Add the minimum number of pages this thread should try to purge to 1119 * arena->npurgatory. This will keep multiple threads from racing to 1120 * reduce ndirty below the threshold. 1121 */ 1122 npurgatory = arena_compute_npurgatory(arena, all); 1123 arena->npurgatory += npurgatory; 1124 1125 while (npurgatory > 0) { 1126 size_t npurgeable, npurged, nunpurged; 1127 1128 /* Get next chunk with dirty pages. */ 1129 chunk = arena_chunk_dirty_first(&arena->chunks_dirty); 1130 if (chunk == NULL) { 1131 /* 1132 * This thread was unable to purge as many pages as 1133 * originally intended, due to races with other threads 1134 * that either did some of the purging work, or re-used 1135 * dirty pages. 1136 */ 1137 arena->npurgatory -= npurgatory; 1138 return; 1139 } 1140 npurgeable = chunk->ndirty; 1141 assert(npurgeable != 0); 1142 1143 if (npurgeable > npurgatory && chunk->nruns_adjac == 0) { 1144 /* 1145 * This thread will purge all the dirty pages in chunk, 1146 * so set npurgatory to reflect this thread's intent to 1147 * purge the pages. This tends to reduce the chances 1148 * of the following scenario: 1149 * 1150 * 1) This thread sets arena->npurgatory such that 1151 * (arena->ndirty - arena->npurgatory) is at the 1152 * threshold. 1153 * 2) This thread drops arena->lock. 1154 * 3) Another thread causes one or more pages to be 1155 * dirtied, and immediately determines that it must 1156 * purge dirty pages. 1157 * 1158 * If this scenario *does* play out, that's okay, 1159 * because all of the purging work being done really 1160 * needs to happen. 1161 */ 1162 arena->npurgatory += npurgeable - npurgatory; 1163 npurgatory = npurgeable; 1164 } 1165 1166 /* 1167 * Keep track of how many pages are purgeable, versus how many 1168 * actually get purged, and adjust counters accordingly. 1169 */ 1170 arena->npurgatory -= npurgeable; 1171 npurgatory -= npurgeable; 1172 npurged = arena_chunk_purge(arena, chunk, all); 1173 nunpurged = npurgeable - npurged; 1174 arena->npurgatory += nunpurged; 1175 npurgatory += nunpurged; 1176 } 1177 } 1178 1179 void 1180 arena_purge_all(arena_t *arena) 1181 { 1182 1183 malloc_mutex_lock(&arena->lock); 1184 arena_purge(arena, true); 1185 malloc_mutex_unlock(&arena->lock); 1186 } 1187 1188 static void 1189 arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size, 1190 size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty) 1191 { 1192 size_t size = *p_size; 1193 size_t run_ind = *p_run_ind; 1194 size_t run_pages = *p_run_pages; 1195 1196 /* Try to coalesce forward. */ 1197 if (run_ind + run_pages < chunk_npages && 1198 arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 && 1199 arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty) { 1200 size_t nrun_size = arena_mapbits_unallocated_size_get(chunk, 1201 run_ind+run_pages); 1202 size_t nrun_pages = nrun_size >> LG_PAGE; 1203 1204 /* 1205 * Remove successor from runs_avail; the coalesced run is 1206 * inserted later. 1207 */ 1208 assert(arena_mapbits_unallocated_size_get(chunk, 1209 run_ind+run_pages+nrun_pages-1) == nrun_size); 1210 assert(arena_mapbits_dirty_get(chunk, 1211 run_ind+run_pages+nrun_pages-1) == flag_dirty); 1212 arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages, 1213 false, true); 1214 1215 size += nrun_size; 1216 run_pages += nrun_pages; 1217 1218 arena_mapbits_unallocated_size_set(chunk, run_ind, size); 1219 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1, 1220 size); 1221 } 1222 1223 /* Try to coalesce backward. */ 1224 if (run_ind > map_bias && arena_mapbits_allocated_get(chunk, 1225 run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) == 1226 flag_dirty) { 1227 size_t prun_size = arena_mapbits_unallocated_size_get(chunk, 1228 run_ind-1); 1229 size_t prun_pages = prun_size >> LG_PAGE; 1230 1231 run_ind -= prun_pages; 1232 1233 /* 1234 * Remove predecessor from runs_avail; the coalesced run is 1235 * inserted later. 1236 */ 1237 assert(arena_mapbits_unallocated_size_get(chunk, run_ind) == 1238 prun_size); 1239 assert(arena_mapbits_dirty_get(chunk, run_ind) == flag_dirty); 1240 arena_avail_remove(arena, chunk, run_ind, prun_pages, true, 1241 false); 1242 1243 size += prun_size; 1244 run_pages += prun_pages; 1245 1246 arena_mapbits_unallocated_size_set(chunk, run_ind, size); 1247 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1, 1248 size); 1249 } 1250 1251 *p_size = size; 1252 *p_run_ind = run_ind; 1253 *p_run_pages = run_pages; 1254 } 1255 1256 static void 1257 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned) 1258 { 1259 arena_chunk_t *chunk; 1260 size_t size, run_ind, run_pages, flag_dirty; 1261 1262 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1263 run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE); 1264 assert(run_ind >= map_bias); 1265 assert(run_ind < chunk_npages); 1266 if (arena_mapbits_large_get(chunk, run_ind) != 0) { 1267 size = arena_mapbits_large_size_get(chunk, run_ind); 1268 assert(size == PAGE || 1269 arena_mapbits_large_size_get(chunk, 1270 run_ind+(size>>LG_PAGE)-1) == 0); 1271 } else { 1272 size_t binind = arena_bin_index(arena, run->bin); 1273 arena_bin_info_t *bin_info = &arena_bin_info[binind]; 1274 size = bin_info->run_size; 1275 } 1276 run_pages = (size >> LG_PAGE); 1277 arena_cactive_update(arena, 0, run_pages); 1278 arena->nactive -= run_pages; 1279 1280 /* 1281 * The run is dirty if the caller claims to have dirtied it, as well as 1282 * if it was already dirty before being allocated and the caller 1283 * doesn't claim to have cleaned it. 1284 */ 1285 assert(arena_mapbits_dirty_get(chunk, run_ind) == 1286 arena_mapbits_dirty_get(chunk, run_ind+run_pages-1)); 1287 if (cleaned == false && arena_mapbits_dirty_get(chunk, run_ind) != 0) 1288 dirty = true; 1289 flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0; 1290 1291 /* Mark pages as unallocated in the chunk map. */ 1292 if (dirty) { 1293 arena_mapbits_unallocated_set(chunk, run_ind, size, 1294 CHUNK_MAP_DIRTY); 1295 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size, 1296 CHUNK_MAP_DIRTY); 1297 } else { 1298 arena_mapbits_unallocated_set(chunk, run_ind, size, 1299 arena_mapbits_unzeroed_get(chunk, run_ind)); 1300 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size, 1301 arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1)); 1302 } 1303 1304 arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages, 1305 flag_dirty); 1306 1307 /* Insert into runs_avail, now that coalescing is complete. */ 1308 assert(arena_mapbits_unallocated_size_get(chunk, run_ind) == 1309 arena_mapbits_unallocated_size_get(chunk, run_ind+run_pages-1)); 1310 assert(arena_mapbits_dirty_get(chunk, run_ind) == 1311 arena_mapbits_dirty_get(chunk, run_ind+run_pages-1)); 1312 arena_avail_insert(arena, chunk, run_ind, run_pages, true, true); 1313 1314 /* Deallocate chunk if it is now completely unused. */ 1315 if (size == arena_maxclass) { 1316 assert(run_ind == map_bias); 1317 assert(run_pages == (arena_maxclass >> LG_PAGE)); 1318 arena_chunk_dalloc(arena, chunk); 1319 } 1320 1321 /* 1322 * It is okay to do dirty page processing here even if the chunk was 1323 * deallocated above, since in that case it is the spare. Waiting 1324 * until after possible chunk deallocation to do dirty processing 1325 * allows for an old spare to be fully deallocated, thus decreasing the 1326 * chances of spuriously crossing the dirty page purging threshold. 1327 */ 1328 if (dirty) 1329 arena_maybe_purge(arena); 1330 } 1331 1332 static void 1333 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 1334 size_t oldsize, size_t newsize) 1335 { 1336 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE; 1337 size_t head_npages = (oldsize - newsize) >> LG_PAGE; 1338 size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind); 1339 1340 assert(oldsize > newsize); 1341 1342 /* 1343 * Update the chunk map so that arena_run_dalloc() can treat the 1344 * leading run as separately allocated. Set the last element of each 1345 * run first, in case of single-page runs. 1346 */ 1347 assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize); 1348 arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty); 1349 arena_mapbits_large_set(chunk, pageind, oldsize-newsize, flag_dirty); 1350 1351 if (config_debug) { 1352 UNUSED size_t tail_npages = newsize >> LG_PAGE; 1353 assert(arena_mapbits_large_size_get(chunk, 1354 pageind+head_npages+tail_npages-1) == 0); 1355 assert(arena_mapbits_dirty_get(chunk, 1356 pageind+head_npages+tail_npages-1) == flag_dirty); 1357 } 1358 arena_mapbits_large_set(chunk, pageind+head_npages, newsize, 1359 flag_dirty); 1360 1361 arena_run_dalloc(arena, run, false, false); 1362 } 1363 1364 static void 1365 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 1366 size_t oldsize, size_t newsize, bool dirty) 1367 { 1368 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE; 1369 size_t head_npages = newsize >> LG_PAGE; 1370 size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind); 1371 1372 assert(oldsize > newsize); 1373 1374 /* 1375 * Update the chunk map so that arena_run_dalloc() can treat the 1376 * trailing run as separately allocated. Set the last element of each 1377 * run first, in case of single-page runs. 1378 */ 1379 assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize); 1380 arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty); 1381 arena_mapbits_large_set(chunk, pageind, newsize, flag_dirty); 1382 1383 if (config_debug) { 1384 UNUSED size_t tail_npages = (oldsize - newsize) >> LG_PAGE; 1385 assert(arena_mapbits_large_size_get(chunk, 1386 pageind+head_npages+tail_npages-1) == 0); 1387 assert(arena_mapbits_dirty_get(chunk, 1388 pageind+head_npages+tail_npages-1) == flag_dirty); 1389 } 1390 arena_mapbits_large_set(chunk, pageind+head_npages, oldsize-newsize, 1391 flag_dirty); 1392 1393 arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize), 1394 dirty, false); 1395 } 1396 1397 static arena_run_t * 1398 arena_bin_runs_first(arena_bin_t *bin) 1399 { 1400 arena_chunk_map_t *mapelm = arena_run_tree_first(&bin->runs); 1401 if (mapelm != NULL) { 1402 arena_chunk_t *chunk; 1403 size_t pageind; 1404 arena_run_t *run; 1405 1406 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm); 1407 pageind = arena_mapelm_to_pageind(mapelm); 1408 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - 1409 arena_mapbits_small_runind_get(chunk, pageind)) << 1410 LG_PAGE)); 1411 return (run); 1412 } 1413 1414 return (NULL); 1415 } 1416 1417 static void 1418 arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run) 1419 { 1420 arena_chunk_t *chunk = CHUNK_ADDR2BASE(run); 1421 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE; 1422 arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind); 1423 1424 assert(arena_run_tree_search(&bin->runs, mapelm) == NULL); 1425 1426 arena_run_tree_insert(&bin->runs, mapelm); 1427 } 1428 1429 static void 1430 arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run) 1431 { 1432 arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1433 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE; 1434 arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind); 1435 1436 assert(arena_run_tree_search(&bin->runs, mapelm) != NULL); 1437 1438 arena_run_tree_remove(&bin->runs, mapelm); 1439 } 1440 1441 static arena_run_t * 1442 arena_bin_nonfull_run_tryget(arena_bin_t *bin) 1443 { 1444 arena_run_t *run = arena_bin_runs_first(bin); 1445 if (run != NULL) { 1446 arena_bin_runs_remove(bin, run); 1447 if (config_stats) 1448 bin->stats.reruns++; 1449 } 1450 return (run); 1451 } 1452 1453 static arena_run_t * 1454 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) 1455 { 1456 arena_run_t *run; 1457 size_t binind; 1458 arena_bin_info_t *bin_info; 1459 1460 /* Look for a usable run. */ 1461 run = arena_bin_nonfull_run_tryget(bin); 1462 if (run != NULL) 1463 return (run); 1464 /* No existing runs have any space available. */ 1465 1466 binind = arena_bin_index(arena, bin); 1467 bin_info = &arena_bin_info[binind]; 1468 1469 /* Allocate a new run. */ 1470 malloc_mutex_unlock(&bin->lock); 1471 /******************************/ 1472 malloc_mutex_lock(&arena->lock); 1473 run = arena_run_alloc_small(arena, bin_info->run_size, binind); 1474 if (run != NULL) { 1475 bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run + 1476 (uintptr_t)bin_info->bitmap_offset); 1477 1478 /* Initialize run internals. */ 1479 run->bin = bin; 1480 run->nextind = 0; 1481 run->nfree = bin_info->nregs; 1482 bitmap_init(bitmap, &bin_info->bitmap_info); 1483 } 1484 malloc_mutex_unlock(&arena->lock); 1485 /********************************/ 1486 malloc_mutex_lock(&bin->lock); 1487 if (run != NULL) { 1488 if (config_stats) { 1489 bin->stats.nruns++; 1490 bin->stats.curruns++; 1491 } 1492 return (run); 1493 } 1494 1495 /* 1496 * arena_run_alloc_small() failed, but another thread may have made 1497 * sufficient memory available while this one dropped bin->lock above, 1498 * so search one more time. 1499 */ 1500 run = arena_bin_nonfull_run_tryget(bin); 1501 if (run != NULL) 1502 return (run); 1503 1504 return (NULL); 1505 } 1506 1507 /* Re-fill bin->runcur, then call arena_run_reg_alloc(). */ 1508 static void * 1509 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) 1510 { 1511 void *ret; 1512 size_t binind; 1513 arena_bin_info_t *bin_info; 1514 arena_run_t *run; 1515 1516 binind = arena_bin_index(arena, bin); 1517 bin_info = &arena_bin_info[binind]; 1518 bin->runcur = NULL; 1519 run = arena_bin_nonfull_run_get(arena, bin); 1520 if (bin->runcur != NULL && bin->runcur->nfree > 0) { 1521 /* 1522 * Another thread updated runcur while this one ran without the 1523 * bin lock in arena_bin_nonfull_run_get(). 1524 */ 1525 assert(bin->runcur->nfree > 0); 1526 ret = arena_run_reg_alloc(bin->runcur, bin_info); 1527 if (run != NULL) { 1528 arena_chunk_t *chunk; 1529 1530 /* 1531 * arena_run_alloc_small() may have allocated run, or 1532 * it may have pulled run from the bin's run tree. 1533 * Therefore it is unsafe to make any assumptions about 1534 * how run has previously been used, and 1535 * arena_bin_lower_run() must be called, as if a region 1536 * were just deallocated from the run. 1537 */ 1538 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1539 if (run->nfree == bin_info->nregs) 1540 arena_dalloc_bin_run(arena, chunk, run, bin); 1541 else 1542 arena_bin_lower_run(arena, chunk, run, bin); 1543 } 1544 return (ret); 1545 } 1546 1547 if (run == NULL) 1548 return (NULL); 1549 1550 bin->runcur = run; 1551 1552 assert(bin->runcur->nfree > 0); 1553 1554 return (arena_run_reg_alloc(bin->runcur, bin_info)); 1555 } 1556 1557 void 1558 arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, size_t binind, 1559 uint64_t prof_accumbytes) 1560 { 1561 unsigned i, nfill; 1562 arena_bin_t *bin; 1563 arena_run_t *run; 1564 void *ptr; 1565 1566 assert(tbin->ncached == 0); 1567 1568 if (config_prof && arena_prof_accum(arena, prof_accumbytes)) 1569 prof_idump(); 1570 bin = &arena->bins[binind]; 1571 malloc_mutex_lock(&bin->lock); 1572 for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >> 1573 tbin->lg_fill_div); i < nfill; i++) { 1574 if ((run = bin->runcur) != NULL && run->nfree > 0) 1575 ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]); 1576 else 1577 ptr = arena_bin_malloc_hard(arena, bin); 1578 if (ptr == NULL) 1579 break; 1580 if (config_fill && opt_junk) { 1581 arena_alloc_junk_small(ptr, &arena_bin_info[binind], 1582 true); 1583 } 1584 /* Insert such that low regions get used first. */ 1585 tbin->avail[nfill - 1 - i] = ptr; 1586 } 1587 if (config_stats) { 1588 bin->stats.allocated += i * arena_bin_info[binind].reg_size; 1589 bin->stats.nmalloc += i; 1590 bin->stats.nrequests += tbin->tstats.nrequests; 1591 bin->stats.nfills++; 1592 tbin->tstats.nrequests = 0; 1593 } 1594 malloc_mutex_unlock(&bin->lock); 1595 tbin->ncached = i; 1596 } 1597 1598 void 1599 arena_alloc_junk_small(void *ptr, arena_bin_info_t *bin_info, bool zero) 1600 { 1601 1602 if (zero) { 1603 size_t redzone_size = bin_info->redzone_size; 1604 memset((void *)((uintptr_t)ptr - redzone_size), 0xa5, 1605 redzone_size); 1606 memset((void *)((uintptr_t)ptr + bin_info->reg_size), 0xa5, 1607 redzone_size); 1608 } else { 1609 memset((void *)((uintptr_t)ptr - bin_info->redzone_size), 0xa5, 1610 bin_info->reg_interval); 1611 } 1612 } 1613 1614 #ifdef JEMALLOC_JET 1615 #undef arena_redzone_corruption 1616 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption_impl) 1617 #endif 1618 static void 1619 arena_redzone_corruption(void *ptr, size_t usize, bool after, 1620 size_t offset, uint8_t byte) 1621 { 1622 1623 malloc_printf("<jemalloc>: Corrupt redzone %zu byte%s %s %p " 1624 "(size %zu), byte=%#x\n", offset, (offset == 1) ? "" : "s", 1625 after ? "after" : "before", ptr, usize, byte); 1626 } 1627 #ifdef JEMALLOC_JET 1628 #undef arena_redzone_corruption 1629 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption) 1630 arena_redzone_corruption_t *arena_redzone_corruption = 1631 JEMALLOC_N(arena_redzone_corruption_impl); 1632 #endif 1633 1634 static void 1635 arena_redzones_validate(void *ptr, arena_bin_info_t *bin_info, bool reset) 1636 { 1637 size_t size = bin_info->reg_size; 1638 size_t redzone_size = bin_info->redzone_size; 1639 size_t i; 1640 bool error = false; 1641 1642 for (i = 1; i <= redzone_size; i++) { 1643 uint8_t *byte = (uint8_t *)((uintptr_t)ptr - i); 1644 if (*byte != 0xa5) { 1645 error = true; 1646 arena_redzone_corruption(ptr, size, false, i, *byte); 1647 if (reset) 1648 *byte = 0xa5; 1649 } 1650 } 1651 for (i = 0; i < redzone_size; i++) { 1652 uint8_t *byte = (uint8_t *)((uintptr_t)ptr + size + i); 1653 if (*byte != 0xa5) { 1654 error = true; 1655 arena_redzone_corruption(ptr, size, true, i, *byte); 1656 if (reset) 1657 *byte = 0xa5; 1658 } 1659 } 1660 if (opt_abort && error) 1661 abort(); 1662 } 1663 1664 #ifdef JEMALLOC_JET 1665 #undef arena_dalloc_junk_small 1666 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small_impl) 1667 #endif 1668 void 1669 arena_dalloc_junk_small(void *ptr, arena_bin_info_t *bin_info) 1670 { 1671 size_t redzone_size = bin_info->redzone_size; 1672 1673 arena_redzones_validate(ptr, bin_info, false); 1674 memset((void *)((uintptr_t)ptr - redzone_size), 0x5a, 1675 bin_info->reg_interval); 1676 } 1677 #ifdef JEMALLOC_JET 1678 #undef arena_dalloc_junk_small 1679 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small) 1680 arena_dalloc_junk_small_t *arena_dalloc_junk_small = 1681 JEMALLOC_N(arena_dalloc_junk_small_impl); 1682 #endif 1683 1684 void 1685 arena_quarantine_junk_small(void *ptr, size_t usize) 1686 { 1687 size_t binind; 1688 arena_bin_info_t *bin_info; 1689 cassert(config_fill); 1690 assert(opt_junk); 1691 assert(opt_quarantine); 1692 assert(usize <= SMALL_MAXCLASS); 1693 1694 binind = small_size2bin(usize); 1695 bin_info = &arena_bin_info[binind]; 1696 arena_redzones_validate(ptr, bin_info, true); 1697 } 1698 1699 void * 1700 arena_malloc_small(arena_t *arena, size_t size, bool zero) 1701 { 1702 void *ret; 1703 arena_bin_t *bin; 1704 arena_run_t *run; 1705 size_t binind; 1706 1707 binind = small_size2bin(size); 1708 assert(binind < NBINS); 1709 bin = &arena->bins[binind]; 1710 size = small_bin2size(binind); 1711 1712 malloc_mutex_lock(&bin->lock); 1713 if ((run = bin->runcur) != NULL && run->nfree > 0) 1714 ret = arena_run_reg_alloc(run, &arena_bin_info[binind]); 1715 else 1716 ret = arena_bin_malloc_hard(arena, bin); 1717 1718 if (ret == NULL) { 1719 malloc_mutex_unlock(&bin->lock); 1720 return (NULL); 1721 } 1722 1723 if (config_stats) { 1724 bin->stats.allocated += size; 1725 bin->stats.nmalloc++; 1726 bin->stats.nrequests++; 1727 } 1728 malloc_mutex_unlock(&bin->lock); 1729 if (config_prof && isthreaded == false && arena_prof_accum(arena, size)) 1730 prof_idump(); 1731 1732 if (zero == false) { 1733 if (config_fill) { 1734 if (opt_junk) { 1735 arena_alloc_junk_small(ret, 1736 &arena_bin_info[binind], false); 1737 } else if (opt_zero) 1738 memset(ret, 0, size); 1739 } 1740 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 1741 } else { 1742 if (config_fill && opt_junk) { 1743 arena_alloc_junk_small(ret, &arena_bin_info[binind], 1744 true); 1745 } 1746 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size); 1747 memset(ret, 0, size); 1748 } 1749 1750 return (ret); 1751 } 1752 1753 void * 1754 arena_malloc_large(arena_t *arena, size_t size, bool zero) 1755 { 1756 void *ret; 1757 UNUSED bool idump; 1758 1759 /* Large allocation. */ 1760 size = PAGE_CEILING(size); 1761 malloc_mutex_lock(&arena->lock); 1762 ret = (void *)arena_run_alloc_large(arena, size, zero); 1763 if (ret == NULL) { 1764 malloc_mutex_unlock(&arena->lock); 1765 return (NULL); 1766 } 1767 if (config_stats) { 1768 arena->stats.nmalloc_large++; 1769 arena->stats.nrequests_large++; 1770 arena->stats.allocated_large += size; 1771 arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++; 1772 arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++; 1773 arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++; 1774 } 1775 if (config_prof) 1776 idump = arena_prof_accum_locked(arena, size); 1777 malloc_mutex_unlock(&arena->lock); 1778 if (config_prof && idump) 1779 prof_idump(); 1780 1781 if (zero == false) { 1782 if (config_fill) { 1783 if (opt_junk) 1784 memset(ret, 0xa5, size); 1785 else if (opt_zero) 1786 memset(ret, 0, size); 1787 } 1788 } 1789 1790 return (ret); 1791 } 1792 1793 /* Only handles large allocations that require more than page alignment. */ 1794 void * 1795 arena_palloc(arena_t *arena, size_t size, size_t alignment, bool zero) 1796 { 1797 void *ret; 1798 size_t alloc_size, leadsize, trailsize; 1799 arena_run_t *run; 1800 arena_chunk_t *chunk; 1801 1802 assert((size & PAGE_MASK) == 0); 1803 1804 alignment = PAGE_CEILING(alignment); 1805 alloc_size = size + alignment - PAGE; 1806 1807 malloc_mutex_lock(&arena->lock); 1808 run = arena_run_alloc_large(arena, alloc_size, false); 1809 if (run == NULL) { 1810 malloc_mutex_unlock(&arena->lock); 1811 return (NULL); 1812 } 1813 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1814 1815 leadsize = ALIGNMENT_CEILING((uintptr_t)run, alignment) - 1816 (uintptr_t)run; 1817 assert(alloc_size >= leadsize + size); 1818 trailsize = alloc_size - leadsize - size; 1819 ret = (void *)((uintptr_t)run + leadsize); 1820 if (leadsize != 0) { 1821 arena_run_trim_head(arena, chunk, run, alloc_size, alloc_size - 1822 leadsize); 1823 } 1824 if (trailsize != 0) { 1825 arena_run_trim_tail(arena, chunk, ret, size + trailsize, size, 1826 false); 1827 } 1828 arena_run_init_large(arena, (arena_run_t *)ret, size, zero); 1829 1830 if (config_stats) { 1831 arena->stats.nmalloc_large++; 1832 arena->stats.nrequests_large++; 1833 arena->stats.allocated_large += size; 1834 arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++; 1835 arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++; 1836 arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++; 1837 } 1838 malloc_mutex_unlock(&arena->lock); 1839 1840 if (config_fill && zero == false) { 1841 if (opt_junk) 1842 memset(ret, 0xa5, size); 1843 else if (opt_zero) 1844 memset(ret, 0, size); 1845 } 1846 return (ret); 1847 } 1848 1849 void 1850 arena_prof_promoted(const void *ptr, size_t size) 1851 { 1852 arena_chunk_t *chunk; 1853 size_t pageind, binind; 1854 1855 cassert(config_prof); 1856 assert(ptr != NULL); 1857 assert(CHUNK_ADDR2BASE(ptr) != ptr); 1858 assert(isalloc(ptr, false) == PAGE); 1859 assert(isalloc(ptr, true) == PAGE); 1860 assert(size <= SMALL_MAXCLASS); 1861 1862 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 1863 pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; 1864 binind = small_size2bin(size); 1865 assert(binind < NBINS); 1866 arena_mapbits_large_binind_set(chunk, pageind, binind); 1867 1868 assert(isalloc(ptr, false) == PAGE); 1869 assert(isalloc(ptr, true) == size); 1870 } 1871 1872 static void 1873 arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run, 1874 arena_bin_t *bin) 1875 { 1876 1877 /* Dissociate run from bin. */ 1878 if (run == bin->runcur) 1879 bin->runcur = NULL; 1880 else { 1881 size_t binind = arena_bin_index(chunk->arena, bin); 1882 arena_bin_info_t *bin_info = &arena_bin_info[binind]; 1883 1884 if (bin_info->nregs != 1) { 1885 /* 1886 * This block's conditional is necessary because if the 1887 * run only contains one region, then it never gets 1888 * inserted into the non-full runs tree. 1889 */ 1890 arena_bin_runs_remove(bin, run); 1891 } 1892 } 1893 } 1894 1895 static void 1896 arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 1897 arena_bin_t *bin) 1898 { 1899 size_t binind; 1900 arena_bin_info_t *bin_info; 1901 size_t npages, run_ind, past; 1902 1903 assert(run != bin->runcur); 1904 assert(arena_run_tree_search(&bin->runs, 1905 arena_mapp_get(chunk, ((uintptr_t)run-(uintptr_t)chunk)>>LG_PAGE)) 1906 == NULL); 1907 1908 binind = arena_bin_index(chunk->arena, run->bin); 1909 bin_info = &arena_bin_info[binind]; 1910 1911 malloc_mutex_unlock(&bin->lock); 1912 /******************************/ 1913 npages = bin_info->run_size >> LG_PAGE; 1914 run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE); 1915 past = (size_t)(PAGE_CEILING((uintptr_t)run + 1916 (uintptr_t)bin_info->reg0_offset + (uintptr_t)(run->nextind * 1917 bin_info->reg_interval - bin_info->redzone_size) - 1918 (uintptr_t)chunk) >> LG_PAGE); 1919 malloc_mutex_lock(&arena->lock); 1920 1921 /* 1922 * If the run was originally clean, and some pages were never touched, 1923 * trim the clean pages before deallocating the dirty portion of the 1924 * run. 1925 */ 1926 assert(arena_mapbits_dirty_get(chunk, run_ind) == 1927 arena_mapbits_dirty_get(chunk, run_ind+npages-1)); 1928 if (arena_mapbits_dirty_get(chunk, run_ind) == 0 && past - run_ind < 1929 npages) { 1930 /* Trim clean pages. Convert to large run beforehand. */ 1931 assert(npages > 0); 1932 arena_mapbits_large_set(chunk, run_ind, bin_info->run_size, 0); 1933 arena_mapbits_large_set(chunk, run_ind+npages-1, 0, 0); 1934 arena_run_trim_tail(arena, chunk, run, (npages << LG_PAGE), 1935 ((past - run_ind) << LG_PAGE), false); 1936 /* npages = past - run_ind; */ 1937 } 1938 arena_run_dalloc(arena, run, true, false); 1939 malloc_mutex_unlock(&arena->lock); 1940 /****************************/ 1941 malloc_mutex_lock(&bin->lock); 1942 if (config_stats) 1943 bin->stats.curruns--; 1944 } 1945 1946 static void 1947 arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 1948 arena_bin_t *bin) 1949 { 1950 1951 /* 1952 * Make sure that if bin->runcur is non-NULL, it refers to the lowest 1953 * non-full run. It is okay to NULL runcur out rather than proactively 1954 * keeping it pointing at the lowest non-full run. 1955 */ 1956 if ((uintptr_t)run < (uintptr_t)bin->runcur) { 1957 /* Switch runcur. */ 1958 if (bin->runcur->nfree > 0) 1959 arena_bin_runs_insert(bin, bin->runcur); 1960 bin->runcur = run; 1961 if (config_stats) 1962 bin->stats.reruns++; 1963 } else 1964 arena_bin_runs_insert(bin, run); 1965 } 1966 1967 void 1968 arena_dalloc_bin_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr, 1969 arena_chunk_map_t *mapelm) 1970 { 1971 size_t pageind; 1972 arena_run_t *run; 1973 arena_bin_t *bin; 1974 arena_bin_info_t *bin_info; 1975 size_t size, binind; 1976 1977 pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; 1978 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - 1979 arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE)); 1980 bin = run->bin; 1981 binind = arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk, pageind)); 1982 bin_info = &arena_bin_info[binind]; 1983 if (config_fill || config_stats) 1984 size = bin_info->reg_size; 1985 1986 if (config_fill && opt_junk) 1987 arena_dalloc_junk_small(ptr, bin_info); 1988 1989 arena_run_reg_dalloc(run, ptr); 1990 if (run->nfree == bin_info->nregs) { 1991 arena_dissociate_bin_run(chunk, run, bin); 1992 arena_dalloc_bin_run(arena, chunk, run, bin); 1993 } else if (run->nfree == 1 && run != bin->runcur) 1994 arena_bin_lower_run(arena, chunk, run, bin); 1995 1996 if (config_stats) { 1997 bin->stats.allocated -= size; 1998 bin->stats.ndalloc++; 1999 } 2000 } 2001 2002 void 2003 arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr, 2004 size_t pageind, arena_chunk_map_t *mapelm) 2005 { 2006 arena_run_t *run; 2007 arena_bin_t *bin; 2008 2009 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - 2010 arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE)); 2011 bin = run->bin; 2012 malloc_mutex_lock(&bin->lock); 2013 arena_dalloc_bin_locked(arena, chunk, ptr, mapelm); 2014 malloc_mutex_unlock(&bin->lock); 2015 } 2016 2017 void 2018 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr, 2019 size_t pageind) 2020 { 2021 arena_chunk_map_t *mapelm; 2022 2023 if (config_debug) { 2024 /* arena_ptr_small_binind_get() does extra sanity checking. */ 2025 assert(arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk, 2026 pageind)) != BININD_INVALID); 2027 } 2028 mapelm = arena_mapp_get(chunk, pageind); 2029 arena_dalloc_bin(arena, chunk, ptr, pageind, mapelm); 2030 } 2031 2032 #ifdef JEMALLOC_JET 2033 #undef arena_dalloc_junk_large 2034 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large_impl) 2035 #endif 2036 static void 2037 arena_dalloc_junk_large(void *ptr, size_t usize) 2038 { 2039 2040 if (config_fill && opt_junk) 2041 memset(ptr, 0x5a, usize); 2042 } 2043 #ifdef JEMALLOC_JET 2044 #undef arena_dalloc_junk_large 2045 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large) 2046 arena_dalloc_junk_large_t *arena_dalloc_junk_large = 2047 JEMALLOC_N(arena_dalloc_junk_large_impl); 2048 #endif 2049 2050 void 2051 arena_dalloc_large_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr) 2052 { 2053 2054 if (config_fill || config_stats) { 2055 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; 2056 size_t usize = arena_mapbits_large_size_get(chunk, pageind); 2057 2058 arena_dalloc_junk_large(ptr, usize); 2059 if (config_stats) { 2060 arena->stats.ndalloc_large++; 2061 arena->stats.allocated_large -= usize; 2062 arena->stats.lstats[(usize >> LG_PAGE) - 1].ndalloc++; 2063 arena->stats.lstats[(usize >> LG_PAGE) - 1].curruns--; 2064 } 2065 } 2066 2067 arena_run_dalloc(arena, (arena_run_t *)ptr, true, false); 2068 } 2069 2070 void 2071 arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) 2072 { 2073 2074 malloc_mutex_lock(&arena->lock); 2075 arena_dalloc_large_locked(arena, chunk, ptr); 2076 malloc_mutex_unlock(&arena->lock); 2077 } 2078 2079 static void 2080 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, 2081 size_t oldsize, size_t size) 2082 { 2083 2084 assert(size < oldsize); 2085 2086 /* 2087 * Shrink the run, and make trailing pages available for other 2088 * allocations. 2089 */ 2090 malloc_mutex_lock(&arena->lock); 2091 arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size, 2092 true); 2093 if (config_stats) { 2094 arena->stats.ndalloc_large++; 2095 arena->stats.allocated_large -= oldsize; 2096 arena->stats.lstats[(oldsize >> LG_PAGE) - 1].ndalloc++; 2097 arena->stats.lstats[(oldsize >> LG_PAGE) - 1].curruns--; 2098 2099 arena->stats.nmalloc_large++; 2100 arena->stats.nrequests_large++; 2101 arena->stats.allocated_large += size; 2102 arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++; 2103 arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++; 2104 arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++; 2105 } 2106 malloc_mutex_unlock(&arena->lock); 2107 } 2108 2109 static bool 2110 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, 2111 size_t oldsize, size_t size, size_t extra, bool zero) 2112 { 2113 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE; 2114 size_t npages = oldsize >> LG_PAGE; 2115 size_t followsize; 2116 2117 assert(oldsize == arena_mapbits_large_size_get(chunk, pageind)); 2118 2119 /* Try to extend the run. */ 2120 assert(size + extra > oldsize); 2121 malloc_mutex_lock(&arena->lock); 2122 if (pageind + npages < chunk_npages && 2123 arena_mapbits_allocated_get(chunk, pageind+npages) == 0 && 2124 (followsize = arena_mapbits_unallocated_size_get(chunk, 2125 pageind+npages)) >= size - oldsize) { 2126 /* 2127 * The next run is available and sufficiently large. Split the 2128 * following run, then merge the first part with the existing 2129 * allocation. 2130 */ 2131 size_t flag_dirty; 2132 size_t splitsize = (oldsize + followsize <= size + extra) 2133 ? followsize : size + extra - oldsize; 2134 arena_run_split_large(arena, (arena_run_t *)((uintptr_t)chunk + 2135 ((pageind+npages) << LG_PAGE)), splitsize, zero); 2136 2137 size = oldsize + splitsize; 2138 npages = size >> LG_PAGE; 2139 2140 /* 2141 * Mark the extended run as dirty if either portion of the run 2142 * was dirty before allocation. This is rather pedantic, 2143 * because there's not actually any sequence of events that 2144 * could cause the resulting run to be passed to 2145 * arena_run_dalloc() with the dirty argument set to false 2146 * (which is when dirty flag consistency would really matter). 2147 */ 2148 flag_dirty = arena_mapbits_dirty_get(chunk, pageind) | 2149 arena_mapbits_dirty_get(chunk, pageind+npages-1); 2150 arena_mapbits_large_set(chunk, pageind, size, flag_dirty); 2151 arena_mapbits_large_set(chunk, pageind+npages-1, 0, flag_dirty); 2152 2153 if (config_stats) { 2154 arena->stats.ndalloc_large++; 2155 arena->stats.allocated_large -= oldsize; 2156 arena->stats.lstats[(oldsize >> LG_PAGE) - 1].ndalloc++; 2157 arena->stats.lstats[(oldsize >> LG_PAGE) - 1].curruns--; 2158 2159 arena->stats.nmalloc_large++; 2160 arena->stats.nrequests_large++; 2161 arena->stats.allocated_large += size; 2162 arena->stats.lstats[(size >> LG_PAGE) - 1].nmalloc++; 2163 arena->stats.lstats[(size >> LG_PAGE) - 1].nrequests++; 2164 arena->stats.lstats[(size >> LG_PAGE) - 1].curruns++; 2165 } 2166 malloc_mutex_unlock(&arena->lock); 2167 return (false); 2168 } 2169 malloc_mutex_unlock(&arena->lock); 2170 2171 return (true); 2172 } 2173 2174 #ifdef JEMALLOC_JET 2175 #undef arena_ralloc_junk_large 2176 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large_impl) 2177 #endif 2178 static void 2179 arena_ralloc_junk_large(void *ptr, size_t old_usize, size_t usize) 2180 { 2181 2182 if (config_fill && opt_junk) { 2183 memset((void *)((uintptr_t)ptr + usize), 0x5a, 2184 old_usize - usize); 2185 } 2186 } 2187 #ifdef JEMALLOC_JET 2188 #undef arena_ralloc_junk_large 2189 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large) 2190 arena_ralloc_junk_large_t *arena_ralloc_junk_large = 2191 JEMALLOC_N(arena_ralloc_junk_large_impl); 2192 #endif 2193 2194 /* 2195 * Try to resize a large allocation, in order to avoid copying. This will 2196 * always fail if growing an object, and the following run is already in use. 2197 */ 2198 static bool 2199 arena_ralloc_large(void *ptr, size_t oldsize, size_t size, size_t extra, 2200 bool zero) 2201 { 2202 size_t psize; 2203 2204 psize = PAGE_CEILING(size + extra); 2205 if (psize == oldsize) { 2206 /* Same size class. */ 2207 return (false); 2208 } else { 2209 arena_chunk_t *chunk; 2210 arena_t *arena; 2211 2212 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 2213 arena = chunk->arena; 2214 2215 if (psize < oldsize) { 2216 /* Fill before shrinking in order avoid a race. */ 2217 arena_ralloc_junk_large(ptr, oldsize, psize); 2218 arena_ralloc_large_shrink(arena, chunk, ptr, oldsize, 2219 psize); 2220 return (false); 2221 } else { 2222 bool ret = arena_ralloc_large_grow(arena, chunk, ptr, 2223 oldsize, PAGE_CEILING(size), 2224 psize - PAGE_CEILING(size), zero); 2225 if (config_fill && ret == false && zero == false) { 2226 if (opt_junk) { 2227 memset((void *)((uintptr_t)ptr + 2228 oldsize), 0xa5, isalloc(ptr, 2229 config_prof) - oldsize); 2230 } else if (opt_zero) { 2231 memset((void *)((uintptr_t)ptr + 2232 oldsize), 0, isalloc(ptr, 2233 config_prof) - oldsize); 2234 } 2235 } 2236 return (ret); 2237 } 2238 } 2239 } 2240 2241 bool 2242 arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra, 2243 bool zero) 2244 { 2245 2246 /* 2247 * Avoid moving the allocation if the size class can be left the same. 2248 */ 2249 if (oldsize <= arena_maxclass) { 2250 if (oldsize <= SMALL_MAXCLASS) { 2251 assert(arena_bin_info[small_size2bin(oldsize)].reg_size 2252 == oldsize); 2253 if ((size + extra <= SMALL_MAXCLASS && 2254 small_size2bin(size + extra) == 2255 small_size2bin(oldsize)) || (size <= oldsize && 2256 size + extra >= oldsize)) 2257 return (false); 2258 } else { 2259 assert(size <= arena_maxclass); 2260 if (size + extra > SMALL_MAXCLASS) { 2261 if (arena_ralloc_large(ptr, oldsize, size, 2262 extra, zero) == false) 2263 return (false); 2264 } 2265 } 2266 } 2267 2268 /* Reallocation would require a move. */ 2269 return (true); 2270 } 2271 2272 void * 2273 arena_ralloc(arena_t *arena, void *ptr, size_t oldsize, size_t size, 2274 size_t extra, size_t alignment, bool zero, bool try_tcache_alloc, 2275 bool try_tcache_dalloc) 2276 { 2277 void *ret; 2278 size_t copysize; 2279 2280 /* Try to avoid moving the allocation. */ 2281 if (arena_ralloc_no_move(ptr, oldsize, size, extra, zero) == false) 2282 return (ptr); 2283 2284 /* 2285 * size and oldsize are different enough that we need to move the 2286 * object. In that case, fall back to allocating new space and 2287 * copying. 2288 */ 2289 if (alignment != 0) { 2290 size_t usize = sa2u(size + extra, alignment); 2291 if (usize == 0) 2292 return (NULL); 2293 ret = ipalloct(usize, alignment, zero, try_tcache_alloc, arena); 2294 } else 2295 ret = arena_malloc(arena, size + extra, zero, try_tcache_alloc); 2296 2297 if (ret == NULL) { 2298 if (extra == 0) 2299 return (NULL); 2300 /* Try again, this time without extra. */ 2301 if (alignment != 0) { 2302 size_t usize = sa2u(size, alignment); 2303 if (usize == 0) 2304 return (NULL); 2305 ret = ipalloct(usize, alignment, zero, try_tcache_alloc, 2306 arena); 2307 } else 2308 ret = arena_malloc(arena, size, zero, try_tcache_alloc); 2309 2310 if (ret == NULL) 2311 return (NULL); 2312 } 2313 2314 /* Junk/zero-filling were already done by ipalloc()/arena_malloc(). */ 2315 2316 /* 2317 * Copy at most size bytes (not size+extra), since the caller has no 2318 * expectation that the extra bytes will be reliably preserved. 2319 */ 2320 copysize = (size < oldsize) ? size : oldsize; 2321 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, copysize); 2322 memcpy(ret, ptr, copysize); 2323 iqalloct(ptr, try_tcache_dalloc); 2324 return (ret); 2325 } 2326 2327 dss_prec_t 2328 arena_dss_prec_get(arena_t *arena) 2329 { 2330 dss_prec_t ret; 2331 2332 malloc_mutex_lock(&arena->lock); 2333 ret = arena->dss_prec; 2334 malloc_mutex_unlock(&arena->lock); 2335 return (ret); 2336 } 2337 2338 bool 2339 arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec) 2340 { 2341 2342 if (have_dss == false) 2343 return (dss_prec != dss_prec_disabled); 2344 malloc_mutex_lock(&arena->lock); 2345 arena->dss_prec = dss_prec; 2346 malloc_mutex_unlock(&arena->lock); 2347 return (false); 2348 } 2349 2350 void 2351 arena_stats_merge(arena_t *arena, const char **dss, size_t *nactive, 2352 size_t *ndirty, arena_stats_t *astats, malloc_bin_stats_t *bstats, 2353 malloc_large_stats_t *lstats) 2354 { 2355 unsigned i; 2356 2357 malloc_mutex_lock(&arena->lock); 2358 *dss = dss_prec_names[arena->dss_prec]; 2359 *nactive += arena->nactive; 2360 *ndirty += arena->ndirty; 2361 2362 astats->mapped += arena->stats.mapped; 2363 astats->npurge += arena->stats.npurge; 2364 astats->nmadvise += arena->stats.nmadvise; 2365 astats->purged += arena->stats.purged; 2366 astats->allocated_large += arena->stats.allocated_large; 2367 astats->nmalloc_large += arena->stats.nmalloc_large; 2368 astats->ndalloc_large += arena->stats.ndalloc_large; 2369 astats->nrequests_large += arena->stats.nrequests_large; 2370 astats->allocated_huge += arena->stats.allocated_huge; 2371 astats->nmalloc_huge += arena->stats.nmalloc_huge; 2372 astats->ndalloc_huge += arena->stats.ndalloc_huge; 2373 astats->nrequests_huge += arena->stats.nrequests_huge; 2374 2375 for (i = 0; i < nlclasses; i++) { 2376 lstats[i].nmalloc += arena->stats.lstats[i].nmalloc; 2377 lstats[i].ndalloc += arena->stats.lstats[i].ndalloc; 2378 lstats[i].nrequests += arena->stats.lstats[i].nrequests; 2379 lstats[i].curruns += arena->stats.lstats[i].curruns; 2380 } 2381 malloc_mutex_unlock(&arena->lock); 2382 2383 for (i = 0; i < NBINS; i++) { 2384 arena_bin_t *bin = &arena->bins[i]; 2385 2386 malloc_mutex_lock(&bin->lock); 2387 bstats[i].allocated += bin->stats.allocated; 2388 bstats[i].nmalloc += bin->stats.nmalloc; 2389 bstats[i].ndalloc += bin->stats.ndalloc; 2390 bstats[i].nrequests += bin->stats.nrequests; 2391 if (config_tcache) { 2392 bstats[i].nfills += bin->stats.nfills; 2393 bstats[i].nflushes += bin->stats.nflushes; 2394 } 2395 bstats[i].nruns += bin->stats.nruns; 2396 bstats[i].reruns += bin->stats.reruns; 2397 bstats[i].curruns += bin->stats.curruns; 2398 malloc_mutex_unlock(&bin->lock); 2399 } 2400 } 2401 2402 bool 2403 arena_new(arena_t *arena, unsigned ind) 2404 { 2405 unsigned i; 2406 arena_bin_t *bin; 2407 2408 arena->ind = ind; 2409 arena->nthreads = 0; 2410 arena->chunk_alloc = chunk_alloc_default; 2411 arena->chunk_dalloc = chunk_dalloc_default; 2412 2413 if (malloc_mutex_init(&arena->lock)) 2414 return (true); 2415 2416 if (config_stats) { 2417 memset(&arena->stats, 0, sizeof(arena_stats_t)); 2418 arena->stats.lstats = 2419 (malloc_large_stats_t *)base_alloc(nlclasses * 2420 sizeof(malloc_large_stats_t)); 2421 if (arena->stats.lstats == NULL) 2422 return (true); 2423 memset(arena->stats.lstats, 0, nlclasses * 2424 sizeof(malloc_large_stats_t)); 2425 if (config_tcache) 2426 ql_new(&arena->tcache_ql); 2427 } 2428 2429 if (config_prof) 2430 arena->prof_accumbytes = 0; 2431 2432 arena->dss_prec = chunk_dss_prec_get(); 2433 2434 /* Initialize chunks. */ 2435 arena_chunk_dirty_new(&arena->chunks_dirty); 2436 arena->spare = NULL; 2437 2438 arena->nactive = 0; 2439 arena->ndirty = 0; 2440 arena->npurgatory = 0; 2441 2442 arena_avail_tree_new(&arena->runs_avail); 2443 2444 /* Initialize bins. */ 2445 for (i = 0; i < NBINS; i++) { 2446 bin = &arena->bins[i]; 2447 if (malloc_mutex_init(&bin->lock)) 2448 return (true); 2449 bin->runcur = NULL; 2450 arena_run_tree_new(&bin->runs); 2451 if (config_stats) 2452 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2453 } 2454 2455 return (false); 2456 } 2457 2458 /* 2459 * Calculate bin_info->run_size such that it meets the following constraints: 2460 * 2461 * *) bin_info->run_size >= min_run_size 2462 * *) bin_info->run_size <= arena_maxclass 2463 * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed). 2464 * *) bin_info->nregs <= RUN_MAXREGS 2465 * 2466 * bin_info->nregs, bin_info->bitmap_offset, and bin_info->reg0_offset are also 2467 * calculated here, since these settings are all interdependent. 2468 */ 2469 static size_t 2470 bin_info_run_size_calc(arena_bin_info_t *bin_info, size_t min_run_size) 2471 { 2472 size_t pad_size; 2473 size_t try_run_size, good_run_size; 2474 uint32_t try_nregs, good_nregs; 2475 uint32_t try_hdr_size, good_hdr_size; 2476 uint32_t try_bitmap_offset, good_bitmap_offset; 2477 uint32_t try_redzone0_offset, good_redzone0_offset; 2478 2479 assert(min_run_size >= PAGE); 2480 assert(min_run_size <= arena_maxclass); 2481 2482 /* 2483 * Determine redzone size based on minimum alignment and minimum 2484 * redzone size. Add padding to the end of the run if it is needed to 2485 * align the regions. The padding allows each redzone to be half the 2486 * minimum alignment; without the padding, each redzone would have to 2487 * be twice as large in order to maintain alignment. 2488 */ 2489 if (config_fill && opt_redzone) { 2490 size_t align_min = ZU(1) << (jemalloc_ffs(bin_info->reg_size) - 1); 2491 if (align_min <= REDZONE_MINSIZE) { 2492 bin_info->redzone_size = REDZONE_MINSIZE; 2493 pad_size = 0; 2494 } else { 2495 bin_info->redzone_size = align_min >> 1; 2496 pad_size = bin_info->redzone_size; 2497 } 2498 } else { 2499 bin_info->redzone_size = 0; 2500 pad_size = 0; 2501 } 2502 bin_info->reg_interval = bin_info->reg_size + 2503 (bin_info->redzone_size << 1); 2504 2505 /* 2506 * Calculate known-valid settings before entering the run_size 2507 * expansion loop, so that the first part of the loop always copies 2508 * valid settings. 2509 * 2510 * The do..while loop iteratively reduces the number of regions until 2511 * the run header and the regions no longer overlap. A closed formula 2512 * would be quite messy, since there is an interdependency between the 2513 * header's mask length and the number of regions. 2514 */ 2515 try_run_size = min_run_size; 2516 try_nregs = ((try_run_size - sizeof(arena_run_t)) / 2517 bin_info->reg_interval) 2518 + 1; /* Counter-act try_nregs-- in loop. */ 2519 if (try_nregs > RUN_MAXREGS) { 2520 try_nregs = RUN_MAXREGS 2521 + 1; /* Counter-act try_nregs-- in loop. */ 2522 } 2523 do { 2524 try_nregs--; 2525 try_hdr_size = sizeof(arena_run_t); 2526 /* Pad to a long boundary. */ 2527 try_hdr_size = LONG_CEILING(try_hdr_size); 2528 try_bitmap_offset = try_hdr_size; 2529 /* Add space for bitmap. */ 2530 try_hdr_size += bitmap_size(try_nregs); 2531 try_redzone0_offset = try_run_size - (try_nregs * 2532 bin_info->reg_interval) - pad_size; 2533 } while (try_hdr_size > try_redzone0_offset); 2534 2535 /* run_size expansion loop. */ 2536 do { 2537 /* 2538 * Copy valid settings before trying more aggressive settings. 2539 */ 2540 good_run_size = try_run_size; 2541 good_nregs = try_nregs; 2542 good_hdr_size = try_hdr_size; 2543 good_bitmap_offset = try_bitmap_offset; 2544 good_redzone0_offset = try_redzone0_offset; 2545 2546 /* Try more aggressive settings. */ 2547 try_run_size += PAGE; 2548 try_nregs = ((try_run_size - sizeof(arena_run_t) - pad_size) / 2549 bin_info->reg_interval) 2550 + 1; /* Counter-act try_nregs-- in loop. */ 2551 if (try_nregs > RUN_MAXREGS) { 2552 try_nregs = RUN_MAXREGS 2553 + 1; /* Counter-act try_nregs-- in loop. */ 2554 } 2555 do { 2556 try_nregs--; 2557 try_hdr_size = sizeof(arena_run_t); 2558 /* Pad to a long boundary. */ 2559 try_hdr_size = LONG_CEILING(try_hdr_size); 2560 try_bitmap_offset = try_hdr_size; 2561 /* Add space for bitmap. */ 2562 try_hdr_size += bitmap_size(try_nregs); 2563 try_redzone0_offset = try_run_size - (try_nregs * 2564 bin_info->reg_interval) - pad_size; 2565 } while (try_hdr_size > try_redzone0_offset); 2566 } while (try_run_size <= arena_maxclass 2567 && RUN_MAX_OVRHD * (bin_info->reg_interval << 3) > 2568 RUN_MAX_OVRHD_RELAX 2569 && (try_redzone0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size 2570 && try_nregs < RUN_MAXREGS); 2571 2572 assert(good_hdr_size <= good_redzone0_offset); 2573 2574 /* Copy final settings. */ 2575 bin_info->run_size = good_run_size; 2576 bin_info->nregs = good_nregs; 2577 bin_info->bitmap_offset = good_bitmap_offset; 2578 bin_info->reg0_offset = good_redzone0_offset + bin_info->redzone_size; 2579 2580 assert(bin_info->reg0_offset - bin_info->redzone_size + (bin_info->nregs 2581 * bin_info->reg_interval) + pad_size == bin_info->run_size); 2582 2583 return (good_run_size); 2584 } 2585 2586 static void 2587 bin_info_init(void) 2588 { 2589 arena_bin_info_t *bin_info; 2590 size_t prev_run_size = PAGE; 2591 2592 #define BIN_INFO_INIT_bin_yes(index, size) \ 2593 bin_info = &arena_bin_info[index]; \ 2594 bin_info->reg_size = size; \ 2595 prev_run_size = bin_info_run_size_calc(bin_info, prev_run_size);\ 2596 bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs); 2597 #define BIN_INFO_INIT_bin_no(index, size) 2598 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \ 2599 BIN_INFO_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta)) 2600 SIZE_CLASSES 2601 #undef BIN_INFO_INIT_bin_yes 2602 #undef BIN_INFO_INIT_bin_no 2603 #undef SC 2604 } 2605 2606 void 2607 arena_boot(void) 2608 { 2609 size_t header_size; 2610 unsigned i; 2611 2612 /* 2613 * Compute the header size such that it is large enough to contain the 2614 * page map. The page map is biased to omit entries for the header 2615 * itself, so some iteration is necessary to compute the map bias. 2616 * 2617 * 1) Compute safe header_size and map_bias values that include enough 2618 * space for an unbiased page map. 2619 * 2) Refine map_bias based on (1) to omit the header pages in the page 2620 * map. The resulting map_bias may be one too small. 2621 * 3) Refine map_bias based on (2). The result will be >= the result 2622 * from (2), and will always be correct. 2623 */ 2624 map_bias = 0; 2625 for (i = 0; i < 3; i++) { 2626 header_size = offsetof(arena_chunk_t, map) + 2627 (sizeof(arena_chunk_map_t) * (chunk_npages-map_bias)); 2628 map_bias = (header_size >> LG_PAGE) + ((header_size & PAGE_MASK) 2629 != 0); 2630 } 2631 assert(map_bias > 0); 2632 2633 arena_maxclass = chunksize - (map_bias << LG_PAGE); 2634 2635 bin_info_init(); 2636 } 2637 2638 void 2639 arena_prefork(arena_t *arena) 2640 { 2641 unsigned i; 2642 2643 malloc_mutex_prefork(&arena->lock); 2644 for (i = 0; i < NBINS; i++) 2645 malloc_mutex_prefork(&arena->bins[i].lock); 2646 } 2647 2648 void 2649 arena_postfork_parent(arena_t *arena) 2650 { 2651 unsigned i; 2652 2653 for (i = 0; i < NBINS; i++) 2654 malloc_mutex_postfork_parent(&arena->bins[i].lock); 2655 malloc_mutex_postfork_parent(&arena->lock); 2656 } 2657 2658 void 2659 arena_postfork_child(arena_t *arena) 2660 { 2661 unsigned i; 2662 2663 for (i = 0; i < NBINS; i++) 2664 malloc_mutex_postfork_child(&arena->bins[i].lock); 2665 malloc_mutex_postfork_child(&arena->lock); 2666 } 2667