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