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