arena.c revision 4201af05425b69ee37ffca437aca0cdd604d1e51
1#define JEMALLOC_ARENA_C_ 2#include "internal/jemalloc_internal.h" 3 4/******************************************************************************/ 5/* Data. */ 6 7size_t opt_lg_qspace_max = LG_QSPACE_MAX_DEFAULT; 8size_t opt_lg_cspace_max = LG_CSPACE_MAX_DEFAULT; 9size_t opt_lg_medium_max = LG_MEDIUM_MAX_DEFAULT; 10ssize_t opt_lg_dirty_mult = LG_DIRTY_MULT_DEFAULT; 11uint8_t const *small_size2bin; 12 13/* Various bin-related settings. */ 14unsigned nqbins; 15unsigned ncbins; 16unsigned nsbins; 17unsigned nmbins; 18unsigned nbins; 19unsigned mbin0; 20size_t qspace_max; 21size_t cspace_min; 22size_t cspace_max; 23size_t sspace_min; 24size_t sspace_max; 25size_t medium_max; 26 27size_t lg_mspace; 28size_t mspace_mask; 29 30/* 31 * const_small_size2bin is a static constant lookup table that in the common 32 * case can be used as-is for small_size2bin. For dynamically linked programs, 33 * this avoids a page of memory overhead per process. 34 */ 35#define S2B_1(i) i, 36#define S2B_2(i) S2B_1(i) S2B_1(i) 37#define S2B_4(i) S2B_2(i) S2B_2(i) 38#define S2B_8(i) S2B_4(i) S2B_4(i) 39#define S2B_16(i) S2B_8(i) S2B_8(i) 40#define S2B_32(i) S2B_16(i) S2B_16(i) 41#define S2B_64(i) S2B_32(i) S2B_32(i) 42#define S2B_128(i) S2B_64(i) S2B_64(i) 43#define S2B_256(i) S2B_128(i) S2B_128(i) 44/* 45 * The number of elements in const_small_size2bin is dependent on page size 46 * and on the definition for SUBPAGE. If SUBPAGE changes, the '- 255' must also 47 * change, along with the addition/removal of static lookup table element 48 * definitions. 49 */ 50static const uint8_t const_small_size2bin[STATIC_PAGE_SIZE - 255] = { 51 S2B_1(0xffU) /* 0 */ 52#if (LG_QUANTUM == 4) 53/* 64-bit system ************************/ 54# ifdef JEMALLOC_TINY 55 S2B_2(0) /* 2 */ 56 S2B_2(1) /* 4 */ 57 S2B_4(2) /* 8 */ 58 S2B_8(3) /* 16 */ 59# define S2B_QMIN 3 60# else 61 S2B_16(0) /* 16 */ 62# define S2B_QMIN 0 63# endif 64 S2B_16(S2B_QMIN + 1) /* 32 */ 65 S2B_16(S2B_QMIN + 2) /* 48 */ 66 S2B_16(S2B_QMIN + 3) /* 64 */ 67 S2B_16(S2B_QMIN + 4) /* 80 */ 68 S2B_16(S2B_QMIN + 5) /* 96 */ 69 S2B_16(S2B_QMIN + 6) /* 112 */ 70 S2B_16(S2B_QMIN + 7) /* 128 */ 71# define S2B_CMIN (S2B_QMIN + 8) 72#else 73/* 32-bit system ************************/ 74# ifdef JEMALLOC_TINY 75 S2B_2(0) /* 2 */ 76 S2B_2(1) /* 4 */ 77 S2B_4(2) /* 8 */ 78# define S2B_QMIN 2 79# else 80 S2B_8(0) /* 8 */ 81# define S2B_QMIN 0 82# endif 83 S2B_8(S2B_QMIN + 1) /* 16 */ 84 S2B_8(S2B_QMIN + 2) /* 24 */ 85 S2B_8(S2B_QMIN + 3) /* 32 */ 86 S2B_8(S2B_QMIN + 4) /* 40 */ 87 S2B_8(S2B_QMIN + 5) /* 48 */ 88 S2B_8(S2B_QMIN + 6) /* 56 */ 89 S2B_8(S2B_QMIN + 7) /* 64 */ 90 S2B_8(S2B_QMIN + 8) /* 72 */ 91 S2B_8(S2B_QMIN + 9) /* 80 */ 92 S2B_8(S2B_QMIN + 10) /* 88 */ 93 S2B_8(S2B_QMIN + 11) /* 96 */ 94 S2B_8(S2B_QMIN + 12) /* 104 */ 95 S2B_8(S2B_QMIN + 13) /* 112 */ 96 S2B_8(S2B_QMIN + 14) /* 120 */ 97 S2B_8(S2B_QMIN + 15) /* 128 */ 98# define S2B_CMIN (S2B_QMIN + 16) 99#endif 100/****************************************/ 101 S2B_64(S2B_CMIN + 0) /* 192 */ 102 S2B_64(S2B_CMIN + 1) /* 256 */ 103 S2B_64(S2B_CMIN + 2) /* 320 */ 104 S2B_64(S2B_CMIN + 3) /* 384 */ 105 S2B_64(S2B_CMIN + 4) /* 448 */ 106 S2B_64(S2B_CMIN + 5) /* 512 */ 107# define S2B_SMIN (S2B_CMIN + 6) 108 S2B_256(S2B_SMIN + 0) /* 768 */ 109 S2B_256(S2B_SMIN + 1) /* 1024 */ 110 S2B_256(S2B_SMIN + 2) /* 1280 */ 111 S2B_256(S2B_SMIN + 3) /* 1536 */ 112 S2B_256(S2B_SMIN + 4) /* 1792 */ 113 S2B_256(S2B_SMIN + 5) /* 2048 */ 114 S2B_256(S2B_SMIN + 6) /* 2304 */ 115 S2B_256(S2B_SMIN + 7) /* 2560 */ 116 S2B_256(S2B_SMIN + 8) /* 2816 */ 117 S2B_256(S2B_SMIN + 9) /* 3072 */ 118 S2B_256(S2B_SMIN + 10) /* 3328 */ 119 S2B_256(S2B_SMIN + 11) /* 3584 */ 120 S2B_256(S2B_SMIN + 12) /* 3840 */ 121#if (STATIC_PAGE_SHIFT == 13) 122 S2B_256(S2B_SMIN + 13) /* 4096 */ 123 S2B_256(S2B_SMIN + 14) /* 4352 */ 124 S2B_256(S2B_SMIN + 15) /* 4608 */ 125 S2B_256(S2B_SMIN + 16) /* 4864 */ 126 S2B_256(S2B_SMIN + 17) /* 5120 */ 127 S2B_256(S2B_SMIN + 18) /* 5376 */ 128 S2B_256(S2B_SMIN + 19) /* 5632 */ 129 S2B_256(S2B_SMIN + 20) /* 5888 */ 130 S2B_256(S2B_SMIN + 21) /* 6144 */ 131 S2B_256(S2B_SMIN + 22) /* 6400 */ 132 S2B_256(S2B_SMIN + 23) /* 6656 */ 133 S2B_256(S2B_SMIN + 24) /* 6912 */ 134 S2B_256(S2B_SMIN + 25) /* 7168 */ 135 S2B_256(S2B_SMIN + 26) /* 7424 */ 136 S2B_256(S2B_SMIN + 27) /* 7680 */ 137 S2B_256(S2B_SMIN + 28) /* 7936 */ 138#endif 139}; 140#undef S2B_1 141#undef S2B_2 142#undef S2B_4 143#undef S2B_8 144#undef S2B_16 145#undef S2B_32 146#undef S2B_64 147#undef S2B_128 148#undef S2B_256 149#undef S2B_QMIN 150#undef S2B_CMIN 151#undef S2B_SMIN 152 153/******************************************************************************/ 154/* Function prototypes for non-inline static functions. */ 155 156static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size, 157 bool large, bool zero); 158static arena_chunk_t *arena_chunk_alloc(arena_t *arena); 159static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk); 160static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool large, 161 bool zero); 162static void arena_purge(arena_t *arena); 163static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty); 164static void arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, 165 arena_run_t *run, size_t oldsize, size_t newsize); 166static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, 167 arena_run_t *run, size_t oldsize, size_t newsize, bool dirty); 168static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin); 169static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin); 170static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size); 171static void *arena_malloc_large(arena_t *arena, size_t size, bool zero); 172static bool arena_is_large(const void *ptr); 173static void arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, 174 arena_run_t *run, arena_bin_t *bin); 175#ifdef JEMALLOC_STATS 176static void arena_stats_aprint(size_t nactive, size_t ndirty, 177 const arena_stats_t *astats, 178 void (*write4)(void *, const char *, const char *, const char *, 179 const char *), void *w4opaque); 180static void arena_stats_bprint(arena_t *arena, 181 const malloc_bin_stats_t *bstats, 182 void (*write4)(void *, const char *, const char *, const char *, 183 const char *), void *w4opaque); 184static void arena_stats_lprint(const malloc_large_stats_t *lstats, 185 void (*write4)(void *, const char *, const char *, const char *, 186 const char *), void *w4opaque); 187#endif 188static void arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, 189 void *ptr, size_t size, size_t oldsize); 190static bool arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, 191 void *ptr, size_t size, size_t oldsize); 192static bool arena_ralloc_large(void *ptr, size_t size, size_t oldsize); 193#ifdef JEMALLOC_TINY 194static size_t pow2_ceil(size_t x); 195#endif 196static bool small_size2bin_init(void); 197#ifdef JEMALLOC_DEBUG 198static void small_size2bin_validate(void); 199#endif 200static bool small_size2bin_init_hard(void); 201 202/******************************************************************************/ 203 204static inline int 205arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b) 206{ 207 uintptr_t a_chunk = (uintptr_t)a; 208 uintptr_t b_chunk = (uintptr_t)b; 209 210 assert(a != NULL); 211 assert(b != NULL); 212 213 return ((a_chunk > b_chunk) - (a_chunk < b_chunk)); 214} 215 216/* Wrap red-black tree macros in functions. */ 217rb_wrap(static JEMALLOC_ATTR(unused), arena_chunk_tree_dirty_, 218 arena_chunk_tree_t, arena_chunk_t, link_dirty, arena_chunk_comp) 219 220static inline int 221arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 222{ 223 uintptr_t a_mapelm = (uintptr_t)a; 224 uintptr_t b_mapelm = (uintptr_t)b; 225 226 assert(a != NULL); 227 assert(b != NULL); 228 229 return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm)); 230} 231 232/* Wrap red-black tree macros in functions. */ 233rb_wrap(static JEMALLOC_ATTR(unused), arena_run_tree_, arena_run_tree_t, 234 arena_chunk_map_t, link, arena_run_comp) 235 236static inline int 237arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 238{ 239 int ret; 240 size_t a_size = a->bits & ~PAGE_MASK; 241 size_t b_size = b->bits & ~PAGE_MASK; 242 243 ret = (a_size > b_size) - (a_size < b_size); 244 if (ret == 0) { 245 uintptr_t a_mapelm, b_mapelm; 246 247 if ((a->bits & CHUNK_MAP_KEY) != CHUNK_MAP_KEY) 248 a_mapelm = (uintptr_t)a; 249 else { 250 /* 251 * Treat keys as though they are lower than anything 252 * else. 253 */ 254 a_mapelm = 0; 255 } 256 b_mapelm = (uintptr_t)b; 257 258 ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm); 259 } 260 261 return (ret); 262} 263 264/* Wrap red-black tree macros in functions. */ 265rb_wrap(static JEMALLOC_ATTR(unused), arena_avail_tree_, arena_avail_tree_t, 266 arena_chunk_map_t, link, arena_avail_comp) 267 268static inline void 269arena_run_rc_incr(arena_run_t *run, arena_bin_t *bin, const void *ptr) 270{ 271 arena_chunk_t *chunk; 272 arena_t *arena; 273 size_t pagebeg, pageend, i; 274 275 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 276 arena = chunk->arena; 277 pagebeg = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 278 pageend = ((uintptr_t)ptr + (uintptr_t)(bin->reg_size - 1) - 279 (uintptr_t)chunk) >> PAGE_SHIFT; 280 281 for (i = pagebeg; i <= pageend; i++) { 282 size_t mapbits = chunk->map[i].bits; 283 284 if (mapbits & CHUNK_MAP_DIRTY) { 285 assert((mapbits & CHUNK_MAP_RC_MASK) == 0); 286 chunk->ndirty--; 287 arena->ndirty--; 288 mapbits ^= CHUNK_MAP_DIRTY; 289 } 290 assert((mapbits & CHUNK_MAP_RC_MASK) != CHUNK_MAP_RC_MASK); 291 mapbits += CHUNK_MAP_RC_ONE; 292 chunk->map[i].bits = mapbits; 293 } 294} 295 296static inline void 297arena_run_rc_decr(arena_run_t *run, arena_bin_t *bin, const void *ptr) 298{ 299 arena_chunk_t *chunk; 300 arena_t *arena; 301 size_t pagebeg, pageend, mapbits, i; 302 bool dirtier = false; 303 304 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 305 arena = chunk->arena; 306 pagebeg = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 307 pageend = ((uintptr_t)ptr + (uintptr_t)(bin->reg_size - 1) - 308 (uintptr_t)chunk) >> PAGE_SHIFT; 309 310 /* First page. */ 311 mapbits = chunk->map[pagebeg].bits; 312 mapbits -= CHUNK_MAP_RC_ONE; 313 if ((mapbits & CHUNK_MAP_RC_MASK) == 0) { 314 dirtier = true; 315 assert((mapbits & CHUNK_MAP_DIRTY) == 0); 316 mapbits |= CHUNK_MAP_DIRTY; 317 chunk->ndirty++; 318 arena->ndirty++; 319 } 320 chunk->map[pagebeg].bits = mapbits; 321 322 if (pageend - pagebeg >= 1) { 323 /* 324 * Interior pages are completely consumed by the object being 325 * deallocated, which means that the pages can be 326 * unconditionally marked dirty. 327 */ 328 for (i = pagebeg + 1; i < pageend; i++) { 329 mapbits = chunk->map[i].bits; 330 mapbits -= CHUNK_MAP_RC_ONE; 331 assert((mapbits & CHUNK_MAP_RC_MASK) == 0); 332 dirtier = true; 333 assert((mapbits & CHUNK_MAP_DIRTY) == 0); 334 mapbits |= CHUNK_MAP_DIRTY; 335 chunk->ndirty++; 336 arena->ndirty++; 337 chunk->map[i].bits = mapbits; 338 } 339 340 /* Last page. */ 341 mapbits = chunk->map[pageend].bits; 342 mapbits -= CHUNK_MAP_RC_ONE; 343 if ((mapbits & CHUNK_MAP_RC_MASK) == 0) { 344 dirtier = true; 345 assert((mapbits & CHUNK_MAP_DIRTY) == 0); 346 mapbits |= CHUNK_MAP_DIRTY; 347 chunk->ndirty++; 348 arena->ndirty++; 349 } 350 chunk->map[pageend].bits = mapbits; 351 } 352 353 if (dirtier) { 354 if (chunk->dirtied == false) { 355 arena_chunk_tree_dirty_insert(&arena->chunks_dirty, 356 chunk); 357 chunk->dirtied = true; 358 } 359 360 /* Enforce opt_lg_dirty_mult. */ 361 if (opt_lg_dirty_mult >= 0 && (arena->nactive >> 362 opt_lg_dirty_mult) < arena->ndirty) 363 arena_purge(arena); 364 } 365} 366 367static inline void * 368arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin) 369{ 370 void *ret; 371 unsigned i, mask, bit, regind; 372 373 assert(run->magic == ARENA_RUN_MAGIC); 374 assert(run->regs_minelm < bin->regs_mask_nelms); 375 376 /* 377 * Move the first check outside the loop, so that run->regs_minelm can 378 * be updated unconditionally, without the possibility of updating it 379 * multiple times. 380 */ 381 i = run->regs_minelm; 382 mask = run->regs_mask[i]; 383 if (mask != 0) { 384 /* Usable allocation found. */ 385 bit = ffs((int)mask) - 1; 386 387 regind = ((i << (LG_SIZEOF_INT + 3)) + bit); 388 assert(regind < bin->nregs); 389 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 390 + (bin->reg_size * regind)); 391 392 /* Clear bit. */ 393 mask ^= (1U << bit); 394 run->regs_mask[i] = mask; 395 396 arena_run_rc_incr(run, bin, ret); 397 398 return (ret); 399 } 400 401 for (i++; i < bin->regs_mask_nelms; i++) { 402 mask = run->regs_mask[i]; 403 if (mask != 0) { 404 /* Usable allocation found. */ 405 bit = ffs((int)mask) - 1; 406 407 regind = ((i << (LG_SIZEOF_INT + 3)) + bit); 408 assert(regind < bin->nregs); 409 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 410 + (bin->reg_size * regind)); 411 412 /* Clear bit. */ 413 mask ^= (1U << bit); 414 run->regs_mask[i] = mask; 415 416 /* 417 * Make a note that nothing before this element 418 * contains a free region. 419 */ 420 run->regs_minelm = i; /* Low payoff: + (mask == 0); */ 421 422 arena_run_rc_incr(run, bin, ret); 423 424 return (ret); 425 } 426 } 427 /* Not reached. */ 428 assert(0); 429 return (NULL); 430} 431 432static inline void 433arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size) 434{ 435 unsigned shift, diff, regind, elm, bit; 436 437 assert(run->magic == ARENA_RUN_MAGIC); 438 439 /* 440 * Avoid doing division with a variable divisor if possible. Using 441 * actual division here can reduce allocator throughput by over 20%! 442 */ 443 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset); 444 445 /* Rescale (factor powers of 2 out of the numerator and denominator). */ 446 shift = ffs(size) - 1; 447 diff >>= shift; 448 size >>= shift; 449 450 if (size == 1) { 451 /* The divisor was a power of 2. */ 452 regind = diff; 453 } else { 454 /* 455 * To divide by a number D that is not a power of two we 456 * multiply by (2^21 / D) and then right shift by 21 positions. 457 * 458 * X / D 459 * 460 * becomes 461 * 462 * (X * size_invs[D - 3]) >> SIZE_INV_SHIFT 463 * 464 * We can omit the first three elements, because we never 465 * divide by 0, and 1 and 2 are both powers of two, which are 466 * handled above. 467 */ 468#define SIZE_INV_SHIFT 21 469#define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s)) + 1) 470 static const unsigned size_invs[] = { 471 SIZE_INV(3), 472 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7), 473 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11), 474 SIZE_INV(12), SIZE_INV(13), SIZE_INV(14), SIZE_INV(15), 475 SIZE_INV(16), SIZE_INV(17), SIZE_INV(18), SIZE_INV(19), 476 SIZE_INV(20), SIZE_INV(21), SIZE_INV(22), SIZE_INV(23), 477 SIZE_INV(24), SIZE_INV(25), SIZE_INV(26), SIZE_INV(27), 478 SIZE_INV(28), SIZE_INV(29), SIZE_INV(30), SIZE_INV(31) 479 }; 480 481 if (size <= ((sizeof(size_invs) / sizeof(unsigned)) + 2)) 482 regind = (diff * size_invs[size - 3]) >> SIZE_INV_SHIFT; 483 else 484 regind = diff / size; 485#undef SIZE_INV 486#undef SIZE_INV_SHIFT 487 } 488 assert(diff == regind * size); 489 assert(regind < bin->nregs); 490 491 elm = regind >> (LG_SIZEOF_INT + 3); 492 if (elm < run->regs_minelm) 493 run->regs_minelm = elm; 494 bit = regind - (elm << (LG_SIZEOF_INT + 3)); 495 assert((run->regs_mask[elm] & (1U << bit)) == 0); 496 run->regs_mask[elm] |= (1U << bit); 497 498 arena_run_rc_decr(run, bin, ptr); 499} 500 501static void 502arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large, 503 bool zero) 504{ 505 arena_chunk_t *chunk; 506 size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i; 507 508 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 509 old_ndirty = chunk->ndirty; 510 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) 511 >> PAGE_SHIFT); 512 total_pages = (chunk->map[run_ind].bits & ~PAGE_MASK) >> 513 PAGE_SHIFT; 514 need_pages = (size >> PAGE_SHIFT); 515 assert(need_pages > 0); 516 assert(need_pages <= total_pages); 517 rem_pages = total_pages - need_pages; 518 519 arena_avail_tree_remove(&arena->runs_avail, &chunk->map[run_ind]); 520 arena->nactive += need_pages; 521 522 /* Keep track of trailing unused pages for later use. */ 523 if (rem_pages > 0) { 524 chunk->map[run_ind+need_pages].bits = (rem_pages << 525 PAGE_SHIFT) | (chunk->map[run_ind+need_pages].bits & 526 CHUNK_MAP_FLAGS_MASK); 527 chunk->map[run_ind+total_pages-1].bits = (rem_pages << 528 PAGE_SHIFT) | (chunk->map[run_ind+total_pages-1].bits & 529 CHUNK_MAP_FLAGS_MASK); 530 arena_avail_tree_insert(&arena->runs_avail, 531 &chunk->map[run_ind+need_pages]); 532 } 533 534 for (i = 0; i < need_pages; i++) { 535 /* Zero if necessary. */ 536 if (zero) { 537 if ((chunk->map[run_ind + i].bits & CHUNK_MAP_ZEROED) 538 == 0) { 539 memset((void *)((uintptr_t)chunk + ((run_ind 540 + i) << PAGE_SHIFT)), 0, PAGE_SIZE); 541 /* CHUNK_MAP_ZEROED is cleared below. */ 542 } 543 } 544 545 /* Update dirty page accounting. */ 546 if (chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) { 547 chunk->ndirty--; 548 arena->ndirty--; 549 /* CHUNK_MAP_DIRTY is cleared below. */ 550 } 551 552 /* Initialize the chunk map. */ 553 if (large) { 554 chunk->map[run_ind + i].bits = CHUNK_MAP_LARGE 555 | CHUNK_MAP_ALLOCATED; 556 } else { 557 chunk->map[run_ind + i].bits = (i << CHUNK_MAP_PG_SHIFT) 558 | CHUNK_MAP_ALLOCATED; 559 } 560 } 561 562 if (large) { 563 /* 564 * Set the run size only in the first element for large runs. 565 * This is primarily a debugging aid, since the lack of size 566 * info for trailing pages only matters if the application 567 * tries to operate on an interior pointer. 568 */ 569 chunk->map[run_ind].bits |= size; 570 } else { 571 /* 572 * Initialize the first page's refcount to 1, so that the run 573 * header is protected from dirty page purging. 574 */ 575 chunk->map[run_ind].bits += CHUNK_MAP_RC_ONE; 576 } 577} 578 579static arena_chunk_t * 580arena_chunk_alloc(arena_t *arena) 581{ 582 arena_chunk_t *chunk; 583 size_t i; 584 585 if (arena->spare != NULL) { 586 chunk = arena->spare; 587 arena->spare = NULL; 588 } else { 589 chunk = (arena_chunk_t *)chunk_alloc(chunksize, true); 590 if (chunk == NULL) 591 return (NULL); 592#ifdef JEMALLOC_STATS 593 arena->stats.mapped += chunksize; 594#endif 595 596 chunk->arena = arena; 597 chunk->dirtied = false; 598 599 /* 600 * Claim that no pages are in use, since the header is merely 601 * overhead. 602 */ 603 chunk->ndirty = 0; 604 605 /* 606 * Initialize the map to contain one maximal free untouched run. 607 */ 608 for (i = 0; i < arena_chunk_header_npages; i++) 609 chunk->map[i].bits = 0; 610 chunk->map[i].bits = arena_maxclass | CHUNK_MAP_ZEROED; 611 for (i++; i < chunk_npages-1; i++) { 612 chunk->map[i].bits = CHUNK_MAP_ZEROED; 613 } 614 chunk->map[chunk_npages-1].bits = arena_maxclass | 615 CHUNK_MAP_ZEROED; 616 } 617 618 /* Insert the run into the runs_avail tree. */ 619 arena_avail_tree_insert(&arena->runs_avail, 620 &chunk->map[arena_chunk_header_npages]); 621 622 return (chunk); 623} 624 625static void 626arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) 627{ 628 629 if (arena->spare != NULL) { 630 if (arena->spare->dirtied) { 631 arena_chunk_tree_dirty_remove( 632 &chunk->arena->chunks_dirty, arena->spare); 633 arena->ndirty -= arena->spare->ndirty; 634 } 635 chunk_dealloc((void *)arena->spare, chunksize); 636#ifdef JEMALLOC_STATS 637 arena->stats.mapped -= chunksize; 638#endif 639 } 640 641 /* 642 * Remove run from runs_avail, regardless of whether this chunk 643 * will be cached, so that the arena does not use it. Dirty page 644 * flushing only uses the chunks_dirty tree, so leaving this chunk in 645 * the chunks_* trees is sufficient for that purpose. 646 */ 647 arena_avail_tree_remove(&arena->runs_avail, 648 &chunk->map[arena_chunk_header_npages]); 649 650 arena->spare = chunk; 651} 652 653static arena_run_t * 654arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero) 655{ 656 arena_chunk_t *chunk; 657 arena_run_t *run; 658 arena_chunk_map_t *mapelm, key; 659 660 assert(size <= arena_maxclass); 661 assert((size & PAGE_MASK) == 0); 662 663 /* Search the arena's chunks for the lowest best fit. */ 664 key.bits = size | CHUNK_MAP_KEY; 665 mapelm = arena_avail_tree_nsearch(&arena->runs_avail, &key); 666 if (mapelm != NULL) { 667 arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); 668 size_t pageind = ((uintptr_t)mapelm - (uintptr_t)run_chunk->map) 669 / sizeof(arena_chunk_map_t); 670 671 run = (arena_run_t *)((uintptr_t)run_chunk + (pageind 672 << PAGE_SHIFT)); 673 arena_run_split(arena, run, size, large, zero); 674 return (run); 675 } 676 677 /* 678 * No usable runs. Create a new chunk from which to allocate the run. 679 */ 680 chunk = arena_chunk_alloc(arena); 681 if (chunk == NULL) 682 return (NULL); 683 run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages << 684 PAGE_SHIFT)); 685 /* Update page map. */ 686 arena_run_split(arena, run, size, large, zero); 687 return (run); 688} 689 690static void 691arena_purge(arena_t *arena) 692{ 693 arena_chunk_t *chunk; 694 size_t i, npages; 695#ifdef JEMALLOC_DEBUG 696 size_t ndirty = 0; 697 698 rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty, 699 chunk) { 700 assert(chunk->dirtied); 701 ndirty += chunk->ndirty; 702 } rb_foreach_end(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk) 703 assert(ndirty == arena->ndirty); 704#endif 705 assert((arena->nactive >> opt_lg_dirty_mult) < arena->ndirty); 706 707#ifdef JEMALLOC_STATS 708 arena->stats.npurge++; 709#endif 710 711 /* 712 * Iterate downward through chunks until enough dirty memory has been 713 * purged. Terminate as soon as possible in order to minimize the 714 * number of system calls, even if a chunk has only been partially 715 * purged. 716 */ 717 718 while ((arena->nactive >> (opt_lg_dirty_mult + 1)) < arena->ndirty) { 719 chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty); 720 assert(chunk != NULL); 721 722 for (i = chunk_npages - 1; chunk->ndirty > 0; i--) { 723 assert(i >= arena_chunk_header_npages); 724 if (chunk->map[i].bits & CHUNK_MAP_DIRTY) { 725 chunk->map[i].bits ^= CHUNK_MAP_DIRTY; 726 /* Find adjacent dirty run(s). */ 727 for (npages = 1; i > arena_chunk_header_npages 728 && (chunk->map[i - 1].bits & 729 CHUNK_MAP_DIRTY); npages++) { 730 i--; 731 chunk->map[i].bits ^= CHUNK_MAP_DIRTY; 732 } 733 chunk->ndirty -= npages; 734 arena->ndirty -= npages; 735 736 madvise((void *)((uintptr_t)chunk + (i << 737 PAGE_SHIFT)), (npages << PAGE_SHIFT), 738 MADV_DONTNEED); 739#ifdef JEMALLOC_STATS 740 arena->stats.nmadvise++; 741 arena->stats.purged += npages; 742#endif 743 if ((arena->nactive >> (opt_lg_dirty_mult + 1)) 744 >= arena->ndirty) 745 break; 746 } 747 } 748 749 if (chunk->ndirty == 0) { 750 arena_chunk_tree_dirty_remove(&arena->chunks_dirty, 751 chunk); 752 chunk->dirtied = false; 753 } 754 } 755} 756 757static void 758arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) 759{ 760 arena_chunk_t *chunk; 761 size_t size, run_ind, run_pages; 762 763 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 764 run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) 765 >> PAGE_SHIFT); 766 assert(run_ind >= arena_chunk_header_npages); 767 assert(run_ind < chunk_npages); 768 if ((chunk->map[run_ind].bits & CHUNK_MAP_LARGE) != 0) 769 size = chunk->map[run_ind].bits & ~PAGE_MASK; 770 else 771 size = run->bin->run_size; 772 run_pages = (size >> PAGE_SHIFT); 773 arena->nactive -= run_pages; 774 775 /* Mark pages as unallocated in the chunk map. */ 776 if (dirty) { 777 size_t i; 778 779 for (i = 0; i < run_pages; i++) { 780 /* 781 * When (dirty == true), *all* pages within the run 782 * need to have their dirty bits set, because only 783 * small runs can create a mixture of clean/dirty 784 * pages, but such runs are passed to this function 785 * with (dirty == false). 786 */ 787 assert((chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) 788 == 0); 789 chunk->ndirty++; 790 arena->ndirty++; 791 chunk->map[run_ind + i].bits = CHUNK_MAP_DIRTY; 792 } 793 } else { 794 size_t i; 795 796 for (i = 0; i < run_pages; i++) { 797 chunk->map[run_ind + i].bits &= ~(CHUNK_MAP_LARGE | 798 CHUNK_MAP_ALLOCATED); 799 } 800 } 801 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 802 CHUNK_MAP_FLAGS_MASK); 803 chunk->map[run_ind+run_pages-1].bits = size | 804 (chunk->map[run_ind+run_pages-1].bits & CHUNK_MAP_FLAGS_MASK); 805 806 /* Try to coalesce forward. */ 807 if (run_ind + run_pages < chunk_npages && 808 (chunk->map[run_ind+run_pages].bits & CHUNK_MAP_ALLOCATED) == 0) { 809 size_t nrun_size = chunk->map[run_ind+run_pages].bits & 810 ~PAGE_MASK; 811 812 /* 813 * Remove successor from runs_avail; the coalesced run is 814 * inserted later. 815 */ 816 arena_avail_tree_remove(&arena->runs_avail, 817 &chunk->map[run_ind+run_pages]); 818 819 size += nrun_size; 820 run_pages = size >> PAGE_SHIFT; 821 822 assert((chunk->map[run_ind+run_pages-1].bits & ~PAGE_MASK) 823 == nrun_size); 824 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 825 CHUNK_MAP_FLAGS_MASK); 826 chunk->map[run_ind+run_pages-1].bits = size | 827 (chunk->map[run_ind+run_pages-1].bits & 828 CHUNK_MAP_FLAGS_MASK); 829 } 830 831 /* Try to coalesce backward. */ 832 if (run_ind > arena_chunk_header_npages && (chunk->map[run_ind-1].bits & 833 CHUNK_MAP_ALLOCATED) == 0) { 834 size_t prun_size = chunk->map[run_ind-1].bits & ~PAGE_MASK; 835 836 run_ind -= prun_size >> PAGE_SHIFT; 837 838 /* 839 * Remove predecessor from runs_avail; the coalesced run is 840 * inserted later. 841 */ 842 arena_avail_tree_remove(&arena->runs_avail, 843 &chunk->map[run_ind]); 844 845 size += prun_size; 846 run_pages = size >> PAGE_SHIFT; 847 848 assert((chunk->map[run_ind].bits & ~PAGE_MASK) == prun_size); 849 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 850 CHUNK_MAP_FLAGS_MASK); 851 chunk->map[run_ind+run_pages-1].bits = size | 852 (chunk->map[run_ind+run_pages-1].bits & 853 CHUNK_MAP_FLAGS_MASK); 854 } 855 856 /* Insert into runs_avail, now that coalescing is complete. */ 857 arena_avail_tree_insert(&arena->runs_avail, &chunk->map[run_ind]); 858 859 /* Deallocate chunk if it is now completely unused. */ 860 if ((chunk->map[arena_chunk_header_npages].bits & (~PAGE_MASK | 861 CHUNK_MAP_ALLOCATED)) == arena_maxclass) 862 arena_chunk_dealloc(arena, chunk); 863 864 if (dirty) { 865 if (chunk->dirtied == false) { 866 arena_chunk_tree_dirty_insert(&arena->chunks_dirty, 867 chunk); 868 chunk->dirtied = true; 869 } 870 871 /* Enforce opt_lg_dirty_mult. */ 872 if (opt_lg_dirty_mult >= 0 && (arena->nactive >> 873 opt_lg_dirty_mult) < arena->ndirty) 874 arena_purge(arena); 875 } 876} 877 878static void 879arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 880 size_t oldsize, size_t newsize) 881{ 882 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT; 883 size_t head_npages = (oldsize - newsize) >> PAGE_SHIFT; 884 885 assert(oldsize > newsize); 886 887 /* 888 * Update the chunk map so that arena_run_dalloc() can treat the 889 * leading run as separately allocated. 890 */ 891 assert((chunk->map[pageind].bits & CHUNK_MAP_DIRTY) == 0); 892 chunk->map[pageind].bits = (oldsize - newsize) | CHUNK_MAP_LARGE | 893 CHUNK_MAP_ALLOCATED; 894 assert((chunk->map[pageind+head_npages].bits & CHUNK_MAP_DIRTY) == 0); 895 chunk->map[pageind+head_npages].bits = newsize | CHUNK_MAP_LARGE | 896 CHUNK_MAP_ALLOCATED; 897 898 arena_run_dalloc(arena, run, false); 899} 900 901static void 902arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 903 size_t oldsize, size_t newsize, bool dirty) 904{ 905 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT; 906 size_t npages = newsize >> PAGE_SHIFT; 907 908 assert(oldsize > newsize); 909 910 /* 911 * Update the chunk map so that arena_run_dalloc() can treat the 912 * trailing run as separately allocated. 913 */ 914 assert((chunk->map[pageind].bits & CHUNK_MAP_DIRTY) == 0); 915 chunk->map[pageind].bits = newsize | CHUNK_MAP_LARGE | 916 CHUNK_MAP_ALLOCATED; 917 assert((chunk->map[pageind+npages].bits & CHUNK_MAP_DIRTY) == 0); 918 chunk->map[pageind+npages].bits = (oldsize - newsize) | CHUNK_MAP_LARGE 919 | CHUNK_MAP_ALLOCATED; 920 921 arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize), 922 dirty); 923} 924 925static arena_run_t * 926arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) 927{ 928 arena_chunk_map_t *mapelm; 929 arena_run_t *run; 930 unsigned i, remainder; 931 932 /* Look for a usable run. */ 933 mapelm = arena_run_tree_first(&bin->runs); 934 if (mapelm != NULL) { 935 arena_chunk_t *chunk; 936 size_t pageind; 937 938 /* run is guaranteed to have available space. */ 939 arena_run_tree_remove(&bin->runs, mapelm); 940 941 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(mapelm); 942 pageind = (((uintptr_t)mapelm - (uintptr_t)chunk->map) / 943 sizeof(arena_chunk_map_t)); 944 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - 945 ((mapelm->bits & CHUNK_MAP_PG_MASK) >> CHUNK_MAP_PG_SHIFT)) 946 << PAGE_SHIFT)); 947#ifdef JEMALLOC_STATS 948 bin->stats.reruns++; 949#endif 950 return (run); 951 } 952 /* No existing runs have any space available. */ 953 954 /* Allocate a new run. */ 955 run = arena_run_alloc(arena, bin->run_size, false, false); 956 if (run == NULL) 957 return (NULL); 958 959 /* Initialize run internals. */ 960 run->bin = bin; 961 962 for (i = 0; i < bin->regs_mask_nelms - 1; i++) 963 run->regs_mask[i] = UINT_MAX; 964 remainder = bin->nregs & ((1U << (LG_SIZEOF_INT + 3)) - 1); 965 if (remainder == 0) 966 run->regs_mask[i] = UINT_MAX; 967 else { 968 /* The last element has spare bits that need to be unset. */ 969 run->regs_mask[i] = (UINT_MAX >> ((1U << (LG_SIZEOF_INT + 3)) 970 - remainder)); 971 } 972 973 run->regs_minelm = 0; 974 975 run->nfree = bin->nregs; 976#ifdef JEMALLOC_DEBUG 977 run->magic = ARENA_RUN_MAGIC; 978#endif 979 980#ifdef JEMALLOC_STATS 981 bin->stats.nruns++; 982 bin->stats.curruns++; 983 if (bin->stats.curruns > bin->stats.highruns) 984 bin->stats.highruns = bin->stats.curruns; 985#endif 986 return (run); 987} 988 989/* bin->runcur must have space available before this function is called. */ 990static inline void * 991arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run) 992{ 993 void *ret; 994 995 assert(run->magic == ARENA_RUN_MAGIC); 996 assert(run->nfree > 0); 997 998 ret = arena_run_reg_alloc(run, bin); 999 assert(ret != NULL); 1000 run->nfree--; 1001 1002 return (ret); 1003} 1004 1005/* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */ 1006static void * 1007arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) 1008{ 1009 1010 bin->runcur = arena_bin_nonfull_run_get(arena, bin); 1011 if (bin->runcur == NULL) 1012 return (NULL); 1013 assert(bin->runcur->magic == ARENA_RUN_MAGIC); 1014 assert(bin->runcur->nfree > 0); 1015 1016 return (arena_bin_malloc_easy(arena, bin, bin->runcur)); 1017} 1018 1019#ifdef JEMALLOC_TCACHE 1020void 1021arena_tcache_fill(arena_t *arena, tcache_bin_t *tbin, size_t binind) 1022{ 1023 unsigned i, nfill; 1024 arena_bin_t *bin; 1025 arena_run_t *run; 1026 void *ptr; 1027 1028 assert(tbin->ncached == 0); 1029 1030 bin = &arena->bins[binind]; 1031 malloc_mutex_lock(&arena->lock); 1032 for (i = 0, nfill = (tcache_nslots >> 1); i < nfill; i++) { 1033 if ((run = bin->runcur) != NULL && run->nfree > 0) 1034 ptr = arena_bin_malloc_easy(arena, bin, run); 1035 else 1036 ptr = arena_bin_malloc_hard(arena, bin); 1037 if (ptr == NULL) { 1038 if (i > 0) { 1039 /* 1040 * Move valid pointers to the base of 1041 * tbin->slots. 1042 */ 1043 memmove(&tbin->slots[0], 1044 &tbin->slots[nfill - i], 1045 i * sizeof(void *)); 1046 } 1047 break; 1048 } 1049 /* 1050 * Fill slots such that the objects lowest in memory come last. 1051 * This causes tcache to use low objects first. 1052 */ 1053 tbin->slots[nfill - 1 - i] = ptr; 1054 } 1055#ifdef JEMALLOC_STATS 1056 bin->stats.nfills++; 1057 bin->stats.nrequests += tbin->tstats.nrequests; 1058 if (bin->reg_size <= small_maxclass) { 1059 arena->stats.nmalloc_small += (i - tbin->ncached); 1060 arena->stats.allocated_small += (i - tbin->ncached) * 1061 bin->reg_size; 1062 arena->stats.nmalloc_small += tbin->tstats.nrequests; 1063 } else { 1064 arena->stats.nmalloc_medium += (i - tbin->ncached); 1065 arena->stats.allocated_medium += (i - tbin->ncached) * 1066 bin->reg_size; 1067 arena->stats.nmalloc_medium += tbin->tstats.nrequests; 1068 } 1069 tbin->tstats.nrequests = 0; 1070#endif 1071 malloc_mutex_unlock(&arena->lock); 1072 tbin->ncached = i; 1073 if (tbin->ncached > tbin->high_water) 1074 tbin->high_water = tbin->ncached; 1075} 1076#endif 1077 1078/* 1079 * Calculate bin->run_size such that it meets the following constraints: 1080 * 1081 * *) bin->run_size >= min_run_size 1082 * *) bin->run_size <= arena_maxclass 1083 * *) bin->run_size <= RUN_MAX_SMALL 1084 * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed). 1085 * *) run header size < PAGE_SIZE 1086 * 1087 * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are 1088 * also calculated here, since these settings are all interdependent. 1089 */ 1090static size_t 1091arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size) 1092{ 1093 size_t try_run_size, good_run_size; 1094 unsigned good_nregs, good_mask_nelms, good_reg0_offset; 1095 unsigned try_nregs, try_mask_nelms, try_reg0_offset; 1096 1097 assert(min_run_size >= PAGE_SIZE); 1098 assert(min_run_size <= arena_maxclass); 1099 assert(min_run_size <= RUN_MAX_SMALL); 1100 1101 /* 1102 * Calculate known-valid settings before entering the run_size 1103 * expansion loop, so that the first part of the loop always copies 1104 * valid settings. 1105 * 1106 * The do..while loop iteratively reduces the number of regions until 1107 * the run header and the regions no longer overlap. A closed formula 1108 * would be quite messy, since there is an interdependency between the 1109 * header's mask length and the number of regions. 1110 */ 1111 try_run_size = min_run_size; 1112 try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin->reg_size) 1113 + 1; /* Counter-act try_nregs-- in loop. */ 1114 do { 1115 try_nregs--; 1116 try_mask_nelms = (try_nregs >> (LG_SIZEOF_INT + 3)) + 1117 ((try_nregs & ((1U << (LG_SIZEOF_INT + 3)) - 1)) ? 1 : 0); 1118 try_reg0_offset = try_run_size - (try_nregs * bin->reg_size); 1119 } while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1)) 1120 > try_reg0_offset); 1121 1122 /* run_size expansion loop. */ 1123 do { 1124 /* 1125 * Copy valid settings before trying more aggressive settings. 1126 */ 1127 good_run_size = try_run_size; 1128 good_nregs = try_nregs; 1129 good_mask_nelms = try_mask_nelms; 1130 good_reg0_offset = try_reg0_offset; 1131 1132 /* Try more aggressive settings. */ 1133 try_run_size += PAGE_SIZE; 1134 try_nregs = ((try_run_size - sizeof(arena_run_t)) / 1135 bin->reg_size) + 1; /* Counter-act try_nregs-- in loop. */ 1136 do { 1137 try_nregs--; 1138 try_mask_nelms = (try_nregs >> (LG_SIZEOF_INT + 3)) + 1139 ((try_nregs & ((1U << (LG_SIZEOF_INT + 3)) - 1)) ? 1140 1 : 0); 1141 try_reg0_offset = try_run_size - (try_nregs * 1142 bin->reg_size); 1143 } while (sizeof(arena_run_t) + (sizeof(unsigned) * 1144 (try_mask_nelms - 1)) > try_reg0_offset); 1145 } while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL 1146 && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX 1147 && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size 1148 && (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1))) 1149 < PAGE_SIZE); 1150 1151 assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1)) 1152 <= good_reg0_offset); 1153 assert((good_mask_nelms << (LG_SIZEOF_INT + 3)) >= good_nregs); 1154 1155 /* Copy final settings. */ 1156 bin->run_size = good_run_size; 1157 bin->nregs = good_nregs; 1158 bin->regs_mask_nelms = good_mask_nelms; 1159 bin->reg0_offset = good_reg0_offset; 1160 1161 return (good_run_size); 1162} 1163 1164void * 1165arena_malloc_small(arena_t *arena, size_t size, bool zero) 1166{ 1167 void *ret; 1168 arena_bin_t *bin; 1169 arena_run_t *run; 1170 size_t binind; 1171 1172 binind = small_size2bin[size]; 1173 assert(binind < mbin0); 1174 bin = &arena->bins[binind]; 1175 size = bin->reg_size; 1176 1177 malloc_mutex_lock(&arena->lock); 1178 if ((run = bin->runcur) != NULL && run->nfree > 0) 1179 ret = arena_bin_malloc_easy(arena, bin, run); 1180 else 1181 ret = arena_bin_malloc_hard(arena, bin); 1182 1183 if (ret == NULL) { 1184 malloc_mutex_unlock(&arena->lock); 1185 return (NULL); 1186 } 1187 1188#ifdef JEMALLOC_STATS 1189# ifdef JEMALLOC_TCACHE 1190 if (isthreaded == false) { 1191# endif 1192 bin->stats.nrequests++; 1193 arena->stats.nmalloc_small++; 1194# ifdef JEMALLOC_TCACHE 1195 } 1196# endif 1197 arena->stats.allocated_small += size; 1198#endif 1199 malloc_mutex_unlock(&arena->lock); 1200 1201 if (zero == false) { 1202#ifdef JEMALLOC_FILL 1203 if (opt_junk) 1204 memset(ret, 0xa5, size); 1205 else if (opt_zero) 1206 memset(ret, 0, size); 1207#endif 1208 } else 1209 memset(ret, 0, size); 1210 1211 return (ret); 1212} 1213 1214void * 1215arena_malloc_medium(arena_t *arena, size_t size, bool zero) 1216{ 1217 void *ret; 1218 arena_bin_t *bin; 1219 arena_run_t *run; 1220 size_t binind; 1221 1222 size = MEDIUM_CEILING(size); 1223 binind = mbin0 + ((size - medium_min) >> lg_mspace); 1224 assert(binind < nbins); 1225 bin = &arena->bins[binind]; 1226 assert(bin->reg_size == size); 1227 1228 malloc_mutex_lock(&arena->lock); 1229 if ((run = bin->runcur) != NULL && run->nfree > 0) 1230 ret = arena_bin_malloc_easy(arena, bin, run); 1231 else 1232 ret = arena_bin_malloc_hard(arena, bin); 1233 1234 if (ret == NULL) { 1235 malloc_mutex_unlock(&arena->lock); 1236 return (NULL); 1237 } 1238 1239#ifdef JEMALLOC_STATS 1240# ifdef JEMALLOC_TCACHE 1241 if (isthreaded == false) { 1242# endif 1243 bin->stats.nrequests++; 1244 arena->stats.nmalloc_medium++; 1245# ifdef JEMALLOC_TCACHE 1246 } 1247# endif 1248 arena->stats.allocated_medium += size; 1249#endif 1250 malloc_mutex_unlock(&arena->lock); 1251 1252 if (zero == false) { 1253#ifdef JEMALLOC_FILL 1254 if (opt_junk) 1255 memset(ret, 0xa5, size); 1256 else if (opt_zero) 1257 memset(ret, 0, size); 1258#endif 1259 } else 1260 memset(ret, 0, size); 1261 1262 return (ret); 1263} 1264 1265static void * 1266arena_malloc_large(arena_t *arena, size_t size, bool zero) 1267{ 1268 void *ret; 1269 1270 /* Large allocation. */ 1271 size = PAGE_CEILING(size); 1272 malloc_mutex_lock(&arena->lock); 1273 ret = (void *)arena_run_alloc(arena, size, true, zero); 1274 if (ret == NULL) { 1275 malloc_mutex_unlock(&arena->lock); 1276 return (NULL); 1277 } 1278#ifdef JEMALLOC_STATS 1279 arena->stats.nmalloc_large++; 1280 arena->stats.allocated_large += size; 1281 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; 1282 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; 1283 if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > 1284 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { 1285 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = 1286 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; 1287 } 1288#endif 1289 malloc_mutex_unlock(&arena->lock); 1290 1291 if (zero == false) { 1292#ifdef JEMALLOC_FILL 1293 if (opt_junk) 1294 memset(ret, 0xa5, size); 1295 else if (opt_zero) 1296 memset(ret, 0, size); 1297#endif 1298 } 1299 1300 return (ret); 1301} 1302 1303void * 1304arena_malloc(size_t size, bool zero) 1305{ 1306 1307 assert(size != 0); 1308 assert(QUANTUM_CEILING(size) <= arena_maxclass); 1309 1310 if (size <= bin_maxclass) { 1311#ifdef JEMALLOC_TCACHE 1312 tcache_t *tcache; 1313 1314 if ((tcache = tcache_get()) != NULL) 1315 return (tcache_alloc(tcache, size, zero)); 1316#endif 1317 if (size <= small_maxclass) 1318 return (arena_malloc_small(choose_arena(), size, zero)); 1319 else { 1320 return (arena_malloc_medium(choose_arena(), size, 1321 zero)); 1322 } 1323 } else 1324 return (arena_malloc_large(choose_arena(), size, zero)); 1325} 1326 1327/* Only handles large allocations that require more than page alignment. */ 1328void * 1329arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size) 1330{ 1331 void *ret; 1332 size_t offset; 1333 arena_chunk_t *chunk; 1334 1335 assert((size & PAGE_MASK) == 0); 1336 assert((alignment & PAGE_MASK) == 0); 1337 1338 malloc_mutex_lock(&arena->lock); 1339 ret = (void *)arena_run_alloc(arena, alloc_size, true, false); 1340 if (ret == NULL) { 1341 malloc_mutex_unlock(&arena->lock); 1342 return (NULL); 1343 } 1344 1345 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret); 1346 1347 offset = (uintptr_t)ret & (alignment - 1); 1348 assert((offset & PAGE_MASK) == 0); 1349 assert(offset < alloc_size); 1350 if (offset == 0) 1351 arena_run_trim_tail(arena, chunk, ret, alloc_size, size, false); 1352 else { 1353 size_t leadsize, trailsize; 1354 1355 leadsize = alignment - offset; 1356 if (leadsize > 0) { 1357 arena_run_trim_head(arena, chunk, ret, alloc_size, 1358 alloc_size - leadsize); 1359 ret = (void *)((uintptr_t)ret + leadsize); 1360 } 1361 1362 trailsize = alloc_size - leadsize - size; 1363 if (trailsize != 0) { 1364 /* Trim trailing space. */ 1365 assert(trailsize < alloc_size); 1366 arena_run_trim_tail(arena, chunk, ret, size + trailsize, 1367 size, false); 1368 } 1369 } 1370 1371#ifdef JEMALLOC_STATS 1372 arena->stats.nmalloc_large++; 1373 arena->stats.allocated_large += size; 1374 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].nrequests++; 1375 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns++; 1376 if (arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns > 1377 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns) { 1378 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].highruns = 1379 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns; 1380 } 1381#endif 1382 malloc_mutex_unlock(&arena->lock); 1383 1384#ifdef JEMALLOC_FILL 1385 if (opt_junk) 1386 memset(ret, 0xa5, size); 1387 else if (opt_zero) 1388 memset(ret, 0, size); 1389#endif 1390 return (ret); 1391} 1392 1393static bool 1394arena_is_large(const void *ptr) 1395{ 1396 arena_chunk_t *chunk; 1397 size_t pageind, mapbits; 1398 1399 assert(ptr != NULL); 1400 assert(CHUNK_ADDR2BASE(ptr) != ptr); 1401 1402 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 1403 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT); 1404 mapbits = chunk->map[pageind].bits; 1405 assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); 1406 return ((mapbits & CHUNK_MAP_LARGE) != 0); 1407} 1408 1409/* Return the size of the allocation pointed to by ptr. */ 1410size_t 1411arena_salloc(const void *ptr) 1412{ 1413 size_t ret; 1414 arena_chunk_t *chunk; 1415 size_t pageind, mapbits; 1416 1417 assert(ptr != NULL); 1418 assert(CHUNK_ADDR2BASE(ptr) != ptr); 1419 1420 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 1421 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT); 1422 mapbits = chunk->map[pageind].bits; 1423 assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); 1424 if ((mapbits & CHUNK_MAP_LARGE) == 0) { 1425 arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + 1426 (uintptr_t)((pageind - ((mapbits & CHUNK_MAP_PG_MASK) >> 1427 CHUNK_MAP_PG_SHIFT)) << PAGE_SHIFT)); 1428 assert(run->magic == ARENA_RUN_MAGIC); 1429 ret = run->bin->reg_size; 1430 } else { 1431 ret = mapbits & ~PAGE_MASK; 1432 assert(ret != 0); 1433 } 1434 1435 return (ret); 1436} 1437 1438static void 1439arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 1440 arena_bin_t *bin) 1441{ 1442 size_t run_ind; 1443 1444 /* Deallocate run. */ 1445 if (run == bin->runcur) 1446 bin->runcur = NULL; 1447 else if (bin->nregs != 1) { 1448 size_t run_pageind = (((uintptr_t)run - 1449 (uintptr_t)chunk)) >> PAGE_SHIFT; 1450 arena_chunk_map_t *run_mapelm = 1451 &chunk->map[run_pageind]; 1452 /* 1453 * This block's conditional is necessary because if the 1454 * run only contains one region, then it never gets 1455 * inserted into the non-full runs tree. 1456 */ 1457 arena_run_tree_remove(&bin->runs, run_mapelm); 1458 } 1459 /* 1460 * Mark the first page as dirty. The dirty bit for every other page in 1461 * the run is already properly set, which means we can call 1462 * arena_run_dalloc(..., false), thus potentially avoiding the needless 1463 * creation of many dirty pages. 1464 */ 1465 run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT); 1466 assert((chunk->map[run_ind].bits & CHUNK_MAP_DIRTY) == 0); 1467 chunk->map[run_ind].bits |= CHUNK_MAP_DIRTY; 1468 chunk->ndirty++; 1469 arena->ndirty++; 1470 1471#ifdef JEMALLOC_DEBUG 1472 run->magic = 0; 1473#endif 1474 arena_run_dalloc(arena, run, false); 1475#ifdef JEMALLOC_STATS 1476 bin->stats.curruns--; 1477#endif 1478 1479 if (chunk->dirtied == false) { 1480 arena_chunk_tree_dirty_insert(&arena->chunks_dirty, chunk); 1481 chunk->dirtied = true; 1482 } 1483 /* Enforce opt_lg_dirty_mult. */ 1484 if (opt_lg_dirty_mult >= 0 && (arena->nactive >> opt_lg_dirty_mult) < 1485 arena->ndirty) 1486 arena_purge(arena); 1487} 1488 1489void 1490arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr, 1491 arena_chunk_map_t *mapelm) 1492{ 1493 size_t pageind; 1494 arena_run_t *run; 1495 arena_bin_t *bin; 1496 size_t size; 1497 1498 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT); 1499 run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind - 1500 ((mapelm->bits & CHUNK_MAP_PG_MASK) >> CHUNK_MAP_PG_SHIFT)) << 1501 PAGE_SHIFT)); 1502 assert(run->magic == ARENA_RUN_MAGIC); 1503 bin = run->bin; 1504 size = bin->reg_size; 1505 1506#ifdef JEMALLOC_FILL 1507 if (opt_junk) 1508 memset(ptr, 0x5a, size); 1509#endif 1510 1511 arena_run_reg_dalloc(run, bin, ptr, size); 1512 run->nfree++; 1513 1514 if (run->nfree == bin->nregs) 1515 arena_dalloc_bin_run(arena, chunk, run, bin); 1516 else if (run->nfree == 1 && run != bin->runcur) { 1517 /* 1518 * Make sure that bin->runcur always refers to the lowest 1519 * non-full run, if one exists. 1520 */ 1521 if (bin->runcur == NULL) 1522 bin->runcur = run; 1523 else if ((uintptr_t)run < (uintptr_t)bin->runcur) { 1524 /* Switch runcur. */ 1525 if (bin->runcur->nfree > 0) { 1526 arena_chunk_t *runcur_chunk = 1527 CHUNK_ADDR2BASE(bin->runcur); 1528 size_t runcur_pageind = 1529 (((uintptr_t)bin->runcur - 1530 (uintptr_t)runcur_chunk)) >> PAGE_SHIFT; 1531 arena_chunk_map_t *runcur_mapelm = 1532 &runcur_chunk->map[runcur_pageind]; 1533 1534 /* Insert runcur. */ 1535 arena_run_tree_insert(&bin->runs, 1536 runcur_mapelm); 1537 } 1538 bin->runcur = run; 1539 } else { 1540 size_t run_pageind = (((uintptr_t)run - 1541 (uintptr_t)chunk)) >> PAGE_SHIFT; 1542 arena_chunk_map_t *run_mapelm = 1543 &chunk->map[run_pageind]; 1544 1545 assert(arena_run_tree_search(&bin->runs, run_mapelm) == 1546 NULL); 1547 arena_run_tree_insert(&bin->runs, run_mapelm); 1548 } 1549 } 1550 1551#ifdef JEMALLOC_STATS 1552 if (size <= small_maxclass) { 1553 arena->stats.allocated_small -= size; 1554 arena->stats.ndalloc_small++; 1555 } else { 1556 arena->stats.allocated_medium -= size; 1557 arena->stats.ndalloc_medium++; 1558 } 1559#endif 1560} 1561 1562#ifdef JEMALLOC_STATS 1563void 1564arena_stats_merge(arena_t *arena, size_t *nactive, size_t *ndirty, 1565 arena_stats_t *astats, malloc_bin_stats_t *bstats, 1566 malloc_large_stats_t *lstats) 1567{ 1568 unsigned i, nlclasses; 1569 1570 *nactive += arena->nactive; 1571 *ndirty += arena->ndirty; 1572 1573 astats->mapped += arena->stats.mapped; 1574 astats->npurge += arena->stats.npurge; 1575 astats->nmadvise += arena->stats.nmadvise; 1576 astats->purged += arena->stats.purged; 1577 astats->allocated_small += arena->stats.allocated_small; 1578 astats->nmalloc_small += arena->stats.nmalloc_small; 1579 astats->ndalloc_small += arena->stats.ndalloc_small; 1580 astats->allocated_medium += arena->stats.allocated_medium; 1581 astats->nmalloc_medium += arena->stats.nmalloc_medium; 1582 astats->ndalloc_medium += arena->stats.ndalloc_medium; 1583 astats->allocated_large += arena->stats.allocated_large; 1584 astats->nmalloc_large += arena->stats.nmalloc_large; 1585 astats->ndalloc_large += arena->stats.ndalloc_large; 1586 1587 for (i = 0; i < nbins; i++) { 1588 bstats[i].nrequests += arena->bins[i].stats.nrequests; 1589#ifdef JEMALLOC_TCACHE 1590 bstats[i].nfills += arena->bins[i].stats.nfills; 1591 bstats[i].nflushes += arena->bins[i].stats.nflushes; 1592#endif 1593 bstats[i].nruns += arena->bins[i].stats.nruns; 1594 bstats[i].reruns += arena->bins[i].stats.reruns; 1595 bstats[i].highruns += arena->bins[i].stats.highruns; 1596 bstats[i].curruns += arena->bins[i].stats.curruns; 1597 } 1598 1599 for (i = 0, nlclasses = (chunksize - PAGE_SIZE) >> PAGE_SHIFT; 1600 i < nlclasses; 1601 i++) { 1602 lstats[i].nrequests += arena->stats.lstats[i].nrequests; 1603 lstats[i].highruns += arena->stats.lstats[i].highruns; 1604 lstats[i].curruns += arena->stats.lstats[i].curruns; 1605 } 1606} 1607 1608static void 1609arena_stats_aprint(size_t nactive, size_t ndirty, const arena_stats_t *astats, 1610 void (*write4)(void *, const char *, const char *, const char *, 1611 const char *), void *w4opaque) 1612{ 1613 1614 malloc_cprintf(write4, w4opaque, 1615 "dirty pages: %zu:%zu active:dirty, %llu sweep%s," 1616 " %llu madvise%s, %llu purged\n", 1617 nactive, ndirty, 1618 astats->npurge, astats->npurge == 1 ? "" : "s", 1619 astats->nmadvise, astats->nmadvise == 1 ? "" : "s", 1620 astats->purged); 1621 1622 malloc_cprintf(write4, w4opaque, 1623 " allocated nmalloc ndalloc\n"); 1624 malloc_cprintf(write4, w4opaque, "small: %12zu %12llu %12llu\n", 1625 astats->allocated_small, astats->nmalloc_small, 1626 astats->ndalloc_small); 1627 malloc_cprintf(write4, w4opaque, "medium: %12zu %12llu %12llu\n", 1628 astats->allocated_medium, astats->nmalloc_medium, 1629 astats->ndalloc_medium); 1630 malloc_cprintf(write4, w4opaque, "large: %12zu %12llu %12llu\n", 1631 astats->allocated_large, astats->nmalloc_large, 1632 astats->ndalloc_large); 1633 malloc_cprintf(write4, w4opaque, "total: %12zu %12llu %12llu\n", 1634 astats->allocated_small + astats->allocated_medium + 1635 astats->allocated_large, astats->nmalloc_small + 1636 astats->nmalloc_medium + astats->nmalloc_large, 1637 astats->ndalloc_small + astats->ndalloc_medium + 1638 astats->ndalloc_large); 1639 malloc_cprintf(write4, w4opaque, "mapped: %12zu\n", astats->mapped); 1640} 1641 1642static void 1643arena_stats_bprint(arena_t *arena, const malloc_bin_stats_t *bstats, 1644 void (*write4)(void *, const char *, const char *, const char *, 1645 const char *), void *w4opaque) 1646{ 1647 unsigned i, gap_start; 1648 1649#ifdef JEMALLOC_TCACHE 1650 malloc_cprintf(write4, w4opaque, 1651 "bins: bin size regs pgs requests " 1652 "nfills nflushes newruns reruns maxruns curruns\n"); 1653#else 1654 malloc_cprintf(write4, w4opaque, 1655 "bins: bin size regs pgs requests " 1656 "newruns reruns maxruns curruns\n"); 1657#endif 1658 for (i = 0, gap_start = UINT_MAX; i < nbins; i++) { 1659 if (bstats[i].nruns == 0) { 1660 if (gap_start == UINT_MAX) 1661 gap_start = i; 1662 } else { 1663 if (gap_start != UINT_MAX) { 1664 if (i > gap_start + 1) { 1665 /* Gap of more than one size class. */ 1666 malloc_cprintf(write4, w4opaque, 1667 "[%u..%u]\n", gap_start, 1668 i - 1); 1669 } else { 1670 /* Gap of one size class. */ 1671 malloc_cprintf(write4, w4opaque, 1672 "[%u]\n", gap_start); 1673 } 1674 gap_start = UINT_MAX; 1675 } 1676 malloc_cprintf(write4, w4opaque, 1677 "%13u %1s %5u %4u %3u %9llu %9llu" 1678#ifdef JEMALLOC_TCACHE 1679 " %9llu %9llu" 1680#endif 1681 " %9llu %7zu %7zu\n", 1682 i, 1683 i < ntbins ? "T" : i < ntbins + nqbins ? 1684 "Q" : i < ntbins + nqbins + ncbins ? "C" : 1685 i < ntbins + nqbins + ncbins + nsbins ? "S" 1686 : "M", 1687 arena->bins[i].reg_size, 1688 arena->bins[i].nregs, 1689 arena->bins[i].run_size >> PAGE_SHIFT, 1690 bstats[i].nrequests, 1691#ifdef JEMALLOC_TCACHE 1692 bstats[i].nfills, 1693 bstats[i].nflushes, 1694#endif 1695 bstats[i].nruns, 1696 bstats[i].reruns, 1697 bstats[i].highruns, 1698 bstats[i].curruns); 1699 } 1700 } 1701 if (gap_start != UINT_MAX) { 1702 if (i > gap_start + 1) { 1703 /* Gap of more than one size class. */ 1704 malloc_cprintf(write4, w4opaque, "[%u..%u]\n", 1705 gap_start, i - 1); 1706 } else { 1707 /* Gap of one size class. */ 1708 malloc_cprintf(write4, w4opaque, "[%u]\n", gap_start); 1709 } 1710 } 1711} 1712 1713static void 1714arena_stats_lprint(const malloc_large_stats_t *lstats, 1715 void (*write4)(void *, const char *, const char *, const char *, 1716 const char *), void *w4opaque) 1717{ 1718 size_t i; 1719 ssize_t gap_start; 1720 size_t nlclasses = (chunksize - PAGE_SIZE) >> PAGE_SHIFT; 1721 1722 malloc_cprintf(write4, w4opaque, 1723 "large: size pages nrequests maxruns curruns\n"); 1724 1725 for (i = 0, gap_start = -1; i < nlclasses; i++) { 1726 if (lstats[i].nrequests == 0) { 1727 if (gap_start == -1) 1728 gap_start = i; 1729 } else { 1730 if (gap_start != -1) { 1731 malloc_cprintf(write4, w4opaque, "[%zu]\n", 1732 i - gap_start); 1733 gap_start = -1; 1734 } 1735 malloc_cprintf(write4, w4opaque, 1736 "%13zu %5zu %9llu %9zu %9zu\n", 1737 (i+1) << PAGE_SHIFT, i+1, 1738 lstats[i].nrequests, 1739 lstats[i].highruns, 1740 lstats[i].curruns); 1741 } 1742 } 1743 if (gap_start != -1) 1744 malloc_cprintf(write4, w4opaque, "[%zu]\n", i - gap_start); 1745} 1746 1747void 1748arena_stats_mprint(arena_t *arena, size_t nactive, size_t ndirty, 1749 const arena_stats_t *astats, const malloc_bin_stats_t *bstats, 1750 const malloc_large_stats_t *lstats, bool bins, bool large, 1751 void (*write4)(void *, const char *, const char *, const char *, 1752 const char *), void *w4opaque) 1753{ 1754 1755 arena_stats_aprint(nactive, ndirty, astats, write4, w4opaque); 1756 if (bins && astats->nmalloc_small + astats->nmalloc_medium > 0) 1757 arena_stats_bprint(arena, bstats, write4, w4opaque); 1758 if (large && astats->nmalloc_large > 0) 1759 arena_stats_lprint(lstats, write4, w4opaque); 1760} 1761 1762void 1763arena_stats_print(arena_t *arena, bool bins, bool large, 1764 void (*write4)(void *, const char *, const char *, const char *, 1765 const char *), void *w4opaque) 1766{ 1767 size_t nactive, ndirty; 1768 arena_stats_t astats; 1769 malloc_bin_stats_t bstats[nbins]; 1770 malloc_large_stats_t lstats[((chunksize - PAGE_SIZE) >> PAGE_SHIFT)]; 1771 1772 nactive = 0; 1773 ndirty = 0; 1774 memset(&astats, 0, sizeof(astats)); 1775 memset(bstats, 0, sizeof(bstats)); 1776 memset(lstats, 0, sizeof(lstats)); 1777 1778 arena_stats_merge(arena, &nactive, &ndirty, &astats, bstats, lstats); 1779 arena_stats_mprint(arena, nactive, ndirty, &astats, bstats, lstats, 1780 bins, large, write4, w4opaque); 1781} 1782#endif 1783 1784void 1785arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) 1786{ 1787 /* Large allocation. */ 1788 malloc_mutex_lock(&arena->lock); 1789 1790#ifdef JEMALLOC_FILL 1791#ifndef JEMALLOC_STATS 1792 if (opt_junk) 1793#endif 1794#endif 1795 { 1796#if (defined(JEMALLOC_FILL) || defined(JEMALLOC_STATS)) 1797 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> 1798 PAGE_SHIFT; 1799 size_t size = chunk->map[pageind].bits & ~PAGE_MASK; 1800#endif 1801 1802#ifdef JEMALLOC_FILL 1803#ifdef JEMALLOC_STATS 1804 if (opt_junk) 1805#endif 1806 memset(ptr, 0x5a, size); 1807#endif 1808#ifdef JEMALLOC_STATS 1809 arena->stats.allocated_large -= size; 1810 arena->stats.lstats[(size >> PAGE_SHIFT) - 1].curruns--; 1811#endif 1812 } 1813#ifdef JEMALLOC_STATS 1814 arena->stats.ndalloc_large++; 1815#endif 1816 1817 arena_run_dalloc(arena, (arena_run_t *)ptr, true); 1818 malloc_mutex_unlock(&arena->lock); 1819} 1820 1821static void 1822arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, 1823 size_t size, size_t oldsize) 1824{ 1825 1826 assert(size < oldsize); 1827 1828 /* 1829 * Shrink the run, and make trailing pages available for other 1830 * allocations. 1831 */ 1832 malloc_mutex_lock(&arena->lock); 1833 arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size, 1834 true); 1835#ifdef JEMALLOC_STATS 1836 arena->stats.allocated_large -= oldsize - size; 1837 arena->stats.lstats[size >> PAGE_SHIFT].nrequests++; 1838 arena->stats.lstats[size >> PAGE_SHIFT].curruns++; 1839 if (arena->stats.lstats[size >> PAGE_SHIFT].curruns > 1840 arena->stats.lstats[size >> PAGE_SHIFT].highruns) { 1841 arena->stats.lstats[size >> PAGE_SHIFT].highruns = 1842 arena->stats.lstats[size >> PAGE_SHIFT].curruns; 1843 } 1844 arena->stats.lstats[oldsize >> PAGE_SHIFT].curruns--; 1845#endif 1846 malloc_mutex_unlock(&arena->lock); 1847} 1848 1849static bool 1850arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, 1851 size_t size, size_t oldsize) 1852{ 1853 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 1854 size_t npages = oldsize >> PAGE_SHIFT; 1855 1856 assert(oldsize == (chunk->map[pageind].bits & ~PAGE_MASK)); 1857 1858 /* Try to extend the run. */ 1859 assert(size > oldsize); 1860 malloc_mutex_lock(&arena->lock); 1861 if (pageind + npages < chunk_npages && (chunk->map[pageind+npages].bits 1862 & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[pageind+npages].bits & 1863 ~PAGE_MASK) >= size - oldsize) { 1864 /* 1865 * The next run is available and sufficiently large. Split the 1866 * following run, then merge the first part with the existing 1867 * allocation. 1868 */ 1869 arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk + 1870 ((pageind+npages) << PAGE_SHIFT)), size - oldsize, true, 1871 false); 1872 1873 chunk->map[pageind].bits = size | CHUNK_MAP_LARGE | 1874 CHUNK_MAP_ALLOCATED; 1875 chunk->map[pageind+npages].bits = CHUNK_MAP_LARGE | 1876 CHUNK_MAP_ALLOCATED; 1877 1878#ifdef JEMALLOC_STATS 1879 arena->stats.allocated_large += size - oldsize; 1880 arena->stats.lstats[size >> PAGE_SHIFT].nrequests++; 1881 arena->stats.lstats[size >> PAGE_SHIFT].curruns++; 1882 if (arena->stats.lstats[size >> PAGE_SHIFT].curruns > 1883 arena->stats.lstats[size >> PAGE_SHIFT].highruns) { 1884 arena->stats.lstats[size >> PAGE_SHIFT].highruns = 1885 arena->stats.lstats[size >> PAGE_SHIFT].curruns; 1886 } 1887 arena->stats.lstats[oldsize >> PAGE_SHIFT].curruns--; 1888#endif 1889 malloc_mutex_unlock(&arena->lock); 1890 return (false); 1891 } 1892 malloc_mutex_unlock(&arena->lock); 1893 1894 return (true); 1895} 1896 1897/* 1898 * Try to resize a large allocation, in order to avoid copying. This will 1899 * always fail if growing an object, and the following run is already in use. 1900 */ 1901static bool 1902arena_ralloc_large(void *ptr, size_t size, size_t oldsize) 1903{ 1904 size_t psize; 1905 1906 psize = PAGE_CEILING(size); 1907 if (psize == oldsize) { 1908 /* Same size class. */ 1909#ifdef JEMALLOC_FILL 1910 if (opt_junk && size < oldsize) { 1911 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - 1912 size); 1913 } 1914#endif 1915 return (false); 1916 } else { 1917 arena_chunk_t *chunk; 1918 arena_t *arena; 1919 1920 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 1921 arena = chunk->arena; 1922 assert(arena->magic == ARENA_MAGIC); 1923 1924 if (psize < oldsize) { 1925#ifdef JEMALLOC_FILL 1926 /* Fill before shrinking in order avoid a race. */ 1927 if (opt_junk) { 1928 memset((void *)((uintptr_t)ptr + size), 0x5a, 1929 oldsize - size); 1930 } 1931#endif 1932 arena_ralloc_large_shrink(arena, chunk, ptr, psize, 1933 oldsize); 1934 return (false); 1935 } else { 1936 bool ret = arena_ralloc_large_grow(arena, chunk, ptr, 1937 psize, oldsize); 1938#ifdef JEMALLOC_FILL 1939 if (ret == false && opt_zero) { 1940 memset((void *)((uintptr_t)ptr + oldsize), 0, 1941 size - oldsize); 1942 } 1943#endif 1944 return (ret); 1945 } 1946 } 1947} 1948 1949void * 1950arena_ralloc(void *ptr, size_t size, size_t oldsize) 1951{ 1952 void *ret; 1953 size_t copysize; 1954 1955 /* 1956 * Try to avoid moving the allocation. 1957 * 1958 * posix_memalign() can cause allocation of "large" objects that are 1959 * smaller than bin_maxclass (in order to meet alignment requirements). 1960 * Therefore, do not assume that (oldsize <= bin_maxclass) indicates 1961 * ptr refers to a bin-allocated object. 1962 */ 1963 if (oldsize <= arena_maxclass) { 1964 if (arena_is_large(ptr) == false ) { 1965 if (size <= small_maxclass) { 1966 if (oldsize <= small_maxclass && 1967 small_size2bin[size] == 1968 small_size2bin[oldsize]) 1969 goto IN_PLACE; 1970 } else if (size <= bin_maxclass) { 1971 if (small_maxclass < oldsize && oldsize <= 1972 bin_maxclass && MEDIUM_CEILING(size) == 1973 MEDIUM_CEILING(oldsize)) 1974 goto IN_PLACE; 1975 } 1976 } else { 1977 assert(size <= arena_maxclass); 1978 if (size > bin_maxclass) { 1979 if (arena_ralloc_large(ptr, size, oldsize) == 1980 false) 1981 return (ptr); 1982 } 1983 } 1984 } 1985 1986 /* Try to avoid moving the allocation. */ 1987 if (size <= small_maxclass) { 1988 if (oldsize <= small_maxclass && small_size2bin[size] == 1989 small_size2bin[oldsize]) 1990 goto IN_PLACE; 1991 } else if (size <= bin_maxclass) { 1992 if (small_maxclass < oldsize && oldsize <= bin_maxclass && 1993 MEDIUM_CEILING(size) == MEDIUM_CEILING(oldsize)) 1994 goto IN_PLACE; 1995 } else { 1996 if (bin_maxclass < oldsize && oldsize <= arena_maxclass) { 1997 assert(size > bin_maxclass); 1998 if (arena_ralloc_large(ptr, size, oldsize) == false) 1999 return (ptr); 2000 } 2001 } 2002 2003 /* 2004 * If we get here, then size and oldsize are different enough that we 2005 * need to move the object. In that case, fall back to allocating new 2006 * space and copying. 2007 */ 2008 ret = arena_malloc(size, false); 2009 if (ret == NULL) 2010 return (NULL); 2011 2012 /* Junk/zero-filling were already done by arena_malloc(). */ 2013 copysize = (size < oldsize) ? size : oldsize; 2014 memcpy(ret, ptr, copysize); 2015 idalloc(ptr); 2016 return (ret); 2017IN_PLACE: 2018#ifdef JEMALLOC_FILL 2019 if (opt_junk && size < oldsize) 2020 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); 2021 else if (opt_zero && size > oldsize) 2022 memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize); 2023#endif 2024 return (ptr); 2025} 2026 2027bool 2028arena_new(arena_t *arena, unsigned ind) 2029{ 2030 unsigned i; 2031 arena_bin_t *bin; 2032 size_t prev_run_size; 2033 2034 if (malloc_mutex_init(&arena->lock)) 2035 return (true); 2036 2037#ifdef JEMALLOC_STATS 2038 memset(&arena->stats, 0, sizeof(arena_stats_t)); 2039 arena->stats.lstats = (malloc_large_stats_t *)base_alloc( 2040 sizeof(malloc_large_stats_t) * ((chunksize - PAGE_SIZE) >> 2041 PAGE_SHIFT)); 2042 if (arena->stats.lstats == NULL) 2043 return (true); 2044 memset(arena->stats.lstats, 0, sizeof(malloc_large_stats_t) * 2045 ((chunksize - PAGE_SIZE) >> PAGE_SHIFT)); 2046# ifdef JEMALLOC_TCACHE 2047 ql_new(&arena->tcache_ql); 2048# endif 2049#endif 2050 2051#ifdef JEMALLOC_TRACE 2052 if (opt_trace) { 2053 /* "jemtr.<pid>.<arena>" */ 2054 char buf[UMAX2S_BUFSIZE]; 2055 char filename[6 + UMAX2S_BUFSIZE + 1 + UMAX2S_BUFSIZE + 1]; 2056 char *s; 2057 unsigned i, slen; 2058 2059 arena->trace_buf_end = 0; 2060 2061 i = 0; 2062 2063 s = "jemtr."; 2064 slen = strlen(s); 2065 memcpy(&filename[i], s, slen); 2066 i += slen; 2067 2068 s = umax2s(getpid(), 10, buf); 2069 slen = strlen(s); 2070 memcpy(&filename[i], s, slen); 2071 i += slen; 2072 2073 s = "."; 2074 slen = strlen(s); 2075 memcpy(&filename[i], s, slen); 2076 i += slen; 2077 2078 s = umax2s(ind, 10, buf); 2079 slen = strlen(s); 2080 memcpy(&filename[i], s, slen); 2081 i += slen; 2082 2083 filename[i] = '\0'; 2084 2085 arena->trace_fd = creat(filename, 0644); 2086 if (arena->trace_fd == -1) { 2087 malloc_write4("<jemalloc>", 2088 ": creat(\"", filename, "\", O_RDWR) failed\n"); 2089 abort(); 2090 } 2091 } 2092#endif 2093 2094 /* Initialize chunks. */ 2095 arena_chunk_tree_dirty_new(&arena->chunks_dirty); 2096 arena->spare = NULL; 2097 2098 arena->nactive = 0; 2099 arena->ndirty = 0; 2100 2101 arena_avail_tree_new(&arena->runs_avail); 2102 2103 /* Initialize bins. */ 2104 prev_run_size = PAGE_SIZE; 2105 2106 i = 0; 2107#ifdef JEMALLOC_TINY 2108 /* (2^n)-spaced tiny bins. */ 2109 for (; i < ntbins; i++) { 2110 bin = &arena->bins[i]; 2111 bin->runcur = NULL; 2112 arena_run_tree_new(&bin->runs); 2113 2114 bin->reg_size = (1U << (LG_TINY_MIN + i)); 2115 2116 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2117 2118#ifdef JEMALLOC_STATS 2119 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2120#endif 2121 } 2122#endif 2123 2124 /* Quantum-spaced bins. */ 2125 for (; i < ntbins + nqbins; i++) { 2126 bin = &arena->bins[i]; 2127 bin->runcur = NULL; 2128 arena_run_tree_new(&bin->runs); 2129 2130 bin->reg_size = (i - ntbins + 1) << LG_QUANTUM; 2131 2132 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2133 2134#ifdef JEMALLOC_STATS 2135 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2136#endif 2137 } 2138 2139 /* Cacheline-spaced bins. */ 2140 for (; i < ntbins + nqbins + ncbins; i++) { 2141 bin = &arena->bins[i]; 2142 bin->runcur = NULL; 2143 arena_run_tree_new(&bin->runs); 2144 2145 bin->reg_size = cspace_min + ((i - (ntbins + nqbins)) << 2146 LG_CACHELINE); 2147 2148 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2149 2150#ifdef JEMALLOC_STATS 2151 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2152#endif 2153 } 2154 2155 /* Subpage-spaced bins. */ 2156 for (; i < ntbins + nqbins + ncbins + nsbins; i++) { 2157 bin = &arena->bins[i]; 2158 bin->runcur = NULL; 2159 arena_run_tree_new(&bin->runs); 2160 2161 bin->reg_size = sspace_min + ((i - (ntbins + nqbins + ncbins)) 2162 << LG_SUBPAGE); 2163 2164 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2165 2166#ifdef JEMALLOC_STATS 2167 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2168#endif 2169 } 2170 2171 /* Medium bins. */ 2172 for (; i < nbins; i++) { 2173 bin = &arena->bins[i]; 2174 bin->runcur = NULL; 2175 arena_run_tree_new(&bin->runs); 2176 2177 bin->reg_size = medium_min + ((i - (ntbins + nqbins + ncbins + 2178 nsbins)) << lg_mspace); 2179 2180 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2181 2182#ifdef JEMALLOC_STATS 2183 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2184#endif 2185 } 2186 2187#ifdef JEMALLOC_DEBUG 2188 arena->magic = ARENA_MAGIC; 2189#endif 2190 2191 return (false); 2192} 2193 2194#ifdef JEMALLOC_TINY 2195/* Compute the smallest power of 2 that is >= x. */ 2196static size_t 2197pow2_ceil(size_t x) 2198{ 2199 2200 x--; 2201 x |= x >> 1; 2202 x |= x >> 2; 2203 x |= x >> 4; 2204 x |= x >> 8; 2205 x |= x >> 16; 2206#if (SIZEOF_PTR == 8) 2207 x |= x >> 32; 2208#endif 2209 x++; 2210 return (x); 2211} 2212#endif 2213 2214#ifdef JEMALLOC_DEBUG 2215static void 2216small_size2bin_validate(void) 2217{ 2218 size_t i, size, binind; 2219 2220 assert(small_size2bin[0] == 0xffU); 2221 i = 1; 2222# ifdef JEMALLOC_TINY 2223 /* Tiny. */ 2224 for (; i < (1U << LG_TINY_MIN); i++) { 2225 size = pow2_ceil(1U << LG_TINY_MIN); 2226 binind = ffs((int)(size >> (LG_TINY_MIN + 1))); 2227 assert(small_size2bin[i] == binind); 2228 } 2229 for (; i < qspace_min; i++) { 2230 size = pow2_ceil(i); 2231 binind = ffs((int)(size >> (LG_TINY_MIN + 1))); 2232 assert(small_size2bin[i] == binind); 2233 } 2234# endif 2235 /* Quantum-spaced. */ 2236 for (; i <= qspace_max; i++) { 2237 size = QUANTUM_CEILING(i); 2238 binind = ntbins + (size >> LG_QUANTUM) - 1; 2239 assert(small_size2bin[i] == binind); 2240 } 2241 /* Cacheline-spaced. */ 2242 for (; i <= cspace_max; i++) { 2243 size = CACHELINE_CEILING(i); 2244 binind = ntbins + nqbins + ((size - cspace_min) >> 2245 LG_CACHELINE); 2246 assert(small_size2bin[i] == binind); 2247 } 2248 /* Sub-page. */ 2249 for (; i <= sspace_max; i++) { 2250 size = SUBPAGE_CEILING(i); 2251 binind = ntbins + nqbins + ncbins + ((size - sspace_min) 2252 >> LG_SUBPAGE); 2253 assert(small_size2bin[i] == binind); 2254 } 2255} 2256#endif 2257 2258static bool 2259small_size2bin_init(void) 2260{ 2261 2262 if (opt_lg_qspace_max != LG_QSPACE_MAX_DEFAULT 2263 || opt_lg_cspace_max != LG_CSPACE_MAX_DEFAULT 2264 || sizeof(const_small_size2bin) != small_maxclass + 1) 2265 return (small_size2bin_init_hard()); 2266 2267 small_size2bin = const_small_size2bin; 2268#ifdef JEMALLOC_DEBUG 2269 assert(sizeof(const_small_size2bin) == small_maxclass + 1); 2270 small_size2bin_validate(); 2271#endif 2272 return (false); 2273} 2274 2275static bool 2276small_size2bin_init_hard(void) 2277{ 2278 size_t i, size, binind; 2279 uint8_t *custom_small_size2bin; 2280 2281 assert(opt_lg_qspace_max != LG_QSPACE_MAX_DEFAULT 2282 || opt_lg_cspace_max != LG_CSPACE_MAX_DEFAULT 2283 || sizeof(const_small_size2bin) != small_maxclass + 1); 2284 2285 custom_small_size2bin = (uint8_t *)base_alloc(small_maxclass + 1); 2286 if (custom_small_size2bin == NULL) 2287 return (true); 2288 2289 custom_small_size2bin[0] = 0xffU; 2290 i = 1; 2291#ifdef JEMALLOC_TINY 2292 /* Tiny. */ 2293 for (; i < (1U << LG_TINY_MIN); i++) { 2294 size = pow2_ceil(1U << LG_TINY_MIN); 2295 binind = ffs((int)(size >> (LG_TINY_MIN + 1))); 2296 custom_small_size2bin[i] = binind; 2297 } 2298 for (; i < qspace_min; i++) { 2299 size = pow2_ceil(i); 2300 binind = ffs((int)(size >> (LG_TINY_MIN + 1))); 2301 custom_small_size2bin[i] = binind; 2302 } 2303#endif 2304 /* Quantum-spaced. */ 2305 for (; i <= qspace_max; i++) { 2306 size = QUANTUM_CEILING(i); 2307 binind = ntbins + (size >> LG_QUANTUM) - 1; 2308 custom_small_size2bin[i] = binind; 2309 } 2310 /* Cacheline-spaced. */ 2311 for (; i <= cspace_max; i++) { 2312 size = CACHELINE_CEILING(i); 2313 binind = ntbins + nqbins + ((size - cspace_min) >> 2314 LG_CACHELINE); 2315 custom_small_size2bin[i] = binind; 2316 } 2317 /* Sub-page. */ 2318 for (; i <= sspace_max; i++) { 2319 size = SUBPAGE_CEILING(i); 2320 binind = ntbins + nqbins + ncbins + ((size - sspace_min) >> 2321 LG_SUBPAGE); 2322 custom_small_size2bin[i] = binind; 2323 } 2324 2325 small_size2bin = custom_small_size2bin; 2326#ifdef JEMALLOC_DEBUG 2327 small_size2bin_validate(); 2328#endif 2329 return (false); 2330} 2331 2332bool 2333arena_boot0(void) 2334{ 2335 2336 /* Set variables according to the value of opt_lg_[qc]space_max. */ 2337 qspace_max = (1U << opt_lg_qspace_max); 2338 cspace_min = CACHELINE_CEILING(qspace_max); 2339 if (cspace_min == qspace_max) 2340 cspace_min += CACHELINE; 2341 cspace_max = (1U << opt_lg_cspace_max); 2342 sspace_min = SUBPAGE_CEILING(cspace_max); 2343 if (sspace_min == cspace_max) 2344 sspace_min += SUBPAGE; 2345 assert(sspace_min < PAGE_SIZE); 2346 sspace_max = PAGE_SIZE - SUBPAGE; 2347 medium_max = (1U << opt_lg_medium_max); 2348 2349#ifdef JEMALLOC_TINY 2350 assert(LG_QUANTUM >= LG_TINY_MIN); 2351#endif 2352 assert(ntbins <= LG_QUANTUM); 2353 nqbins = qspace_max >> LG_QUANTUM; 2354 ncbins = ((cspace_max - cspace_min) >> LG_CACHELINE) + 1; 2355 nsbins = ((sspace_max - sspace_min) >> LG_SUBPAGE) + 1; 2356 2357 /* 2358 * Compute medium size class spacing and the number of medium size 2359 * classes. Limit spacing to no more than pagesize, but if possible 2360 * use the smallest spacing that does not exceed NMBINS_MAX medium size 2361 * classes. 2362 */ 2363 lg_mspace = LG_SUBPAGE; 2364 nmbins = ((medium_max - medium_min) >> lg_mspace) + 1; 2365 while (lg_mspace < PAGE_SHIFT && nmbins > NMBINS_MAX) { 2366 lg_mspace = lg_mspace + 1; 2367 nmbins = ((medium_max - medium_min) >> lg_mspace) + 1; 2368 } 2369 mspace_mask = (1U << lg_mspace) - 1U; 2370 2371 mbin0 = ntbins + nqbins + ncbins + nsbins; 2372 nbins = mbin0 + nmbins; 2373 /* 2374 * The small_size2bin lookup table uses uint8_t to encode each bin 2375 * index, so we cannot support more than 256 small size classes. This 2376 * limit is difficult to exceed (not even possible with 16B quantum and 2377 * 4KiB pages), and such configurations are impractical, but 2378 * nonetheless we need to protect against this case in order to avoid 2379 * undefined behavior. 2380 */ 2381 if (mbin0 > 256) { 2382 char line_buf[UMAX2S_BUFSIZE]; 2383 malloc_write4("<jemalloc>: Too many small size classes (", 2384 umax2s(mbin0, 10, line_buf), " > max 256)\n", ""); 2385 abort(); 2386 } 2387 2388 if (small_size2bin_init()) 2389 return (true); 2390 2391 return (false); 2392} 2393 2394void 2395arena_boot1(void) 2396{ 2397 size_t header_size; 2398 2399 /* 2400 * Compute the header size such that it is large enough to contain the 2401 * page map. 2402 */ 2403 header_size = sizeof(arena_chunk_t) + 2404 (sizeof(arena_chunk_map_t) * (chunk_npages - 1)); 2405 arena_chunk_header_npages = (header_size >> PAGE_SHIFT) + 2406 ((header_size & PAGE_MASK) != 0); 2407 arena_maxclass = chunksize - (arena_chunk_header_npages << PAGE_SHIFT); 2408} 2409