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