contrib/jemalloc/src/arena.c

   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 static ssize_t  lg_dirty_mult_default;
   9 arena_bin_info_t        arena_bin_info[NBINS];
  10
  11 size_t          map_bias;
  12 size_t          map_misc_offset;
  13 size_t          arena_maxrun; /* Max run size for arenas. */
  14 size_t          large_maxclass; /* Max large size class. */
  15 static size_t   small_maxrun; /* Max run size used for small size classes. */
  16 static bool     *small_run_tab; /* Valid small run page multiples. */
  17 unsigned        nlclasses; /* Number of large size classes. */
  18 unsigned        nhclasses; /* Number of huge size classes. */
  19
  20 /******************************************************************************/
  21 /*
  22  * Function prototypes for static functions that are referenced prior to
  23  * definition.
  24  */
  25
  26 static void     arena_purge(arena_t *arena, bool all);
  27 static void     arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty,
  28     bool cleaned, bool decommitted);
  29 static void     arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk,
  30     arena_run_t *run, arena_bin_t *bin);
  31 static void     arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk,
  32     arena_run_t *run, arena_bin_t *bin);
  33
  34 /******************************************************************************/
  35
  36 #define CHUNK_MAP_KEY           ((uintptr_t)0x1U)
  37
  38 JEMALLOC_INLINE_C arena_chunk_map_misc_t *
  39 arena_miscelm_key_create(size_t size)
  40 {
  41
  42         return ((arena_chunk_map_misc_t *)(arena_mapbits_size_encode(size) |
  43             CHUNK_MAP_KEY));
  44 }
  45
  46 JEMALLOC_INLINE_C bool
  47 arena_miscelm_is_key(const arena_chunk_map_misc_t *miscelm)
  48 {
  49
  50         return (((uintptr_t)miscelm & CHUNK_MAP_KEY) != 0);
  51 }
  52
  53 #undef CHUNK_MAP_KEY
  54
  55 JEMALLOC_INLINE_C size_t
  56 arena_miscelm_key_size_get(const arena_chunk_map_misc_t *miscelm)
  57 {
  58
  59         assert(arena_miscelm_is_key(miscelm));
  60
  61         return (arena_mapbits_size_decode((uintptr_t)miscelm));
  62 }
  63
  64 JEMALLOC_INLINE_C size_t
  65 arena_miscelm_size_get(arena_chunk_map_misc_t *miscelm)
  66 {
  67         arena_chunk_t *chunk;
  68         size_t pageind, mapbits;
  69
  70         assert(!arena_miscelm_is_key(miscelm));
  71
  72         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(miscelm);
  73         pageind = arena_miscelm_to_pageind(miscelm);
  74         mapbits = arena_mapbits_get(chunk, pageind);
  75         return (arena_mapbits_size_decode(mapbits));
  76 }
  77
  78 JEMALLOC_INLINE_C int
  79 arena_run_comp(arena_chunk_map_misc_t *a, arena_chunk_map_misc_t *b)
  80 {
  81         uintptr_t a_miscelm = (uintptr_t)a;
  82         uintptr_t b_miscelm = (uintptr_t)b;
  83
  84         assert(a != NULL);
  85         assert(b != NULL);
  86
  87         return ((a_miscelm > b_miscelm) - (a_miscelm < b_miscelm));
  88 }
  89
  90 /* Generate red-black tree functions. */
  91 rb_gen(static UNUSED, arena_run_tree_, arena_run_tree_t, arena_chunk_map_misc_t,
  92     rb_link, arena_run_comp)
  93
  94 static size_t
  95 run_quantize(size_t size)
  96 {
  97         size_t qsize;
  98
  99         assert(size != 0);
 100         assert(size == PAGE_CEILING(size));
 101
 102         /* Don't change sizes that are valid small run sizes. */
 103         if (size <= small_maxrun && small_run_tab[size >> LG_PAGE])
 104                 return (size);
 105
 106         /*
 107          * Round down to the nearest run size that can actually be requested
 108          * during normal large allocation.  Add large_pad so that cache index
 109          * randomization can offset the allocation from the page boundary.
 110          */
 111         qsize = index2size(size2index(size - large_pad + 1) - 1) + large_pad;
 112         if (qsize <= SMALL_MAXCLASS + large_pad)
 113                 return (run_quantize(size - large_pad));
 114         assert(qsize <= size);
 115         return (qsize);
 116 }
 117
 118 static size_t
 119 run_quantize_next(size_t size)
 120 {
 121         size_t large_run_size_next;
 122
 123         assert(size != 0);
 124         assert(size == PAGE_CEILING(size));
 125
 126         /*
 127          * Return the next quantized size greater than the input size.
 128          * Quantized sizes comprise the union of run sizes that back small
 129          * region runs, and run sizes that back large regions with no explicit
 130          * alignment constraints.
 131          */
 132
 133         if (size > SMALL_MAXCLASS) {
 134                 large_run_size_next = PAGE_CEILING(index2size(size2index(size -
 135                     large_pad) + 1) + large_pad);
 136         } else
 137                 large_run_size_next = SIZE_T_MAX;
 138         if (size >= small_maxrun)
 139                 return (large_run_size_next);
 140
 141         while (true) {
 142                 size += PAGE;
 143                 assert(size <= small_maxrun);
 144                 if (small_run_tab[size >> LG_PAGE]) {
 145                         if (large_run_size_next < size)
 146                                 return (large_run_size_next);
 147                         return (size);
 148                 }
 149         }
 150 }
 151
 152 static size_t
 153 run_quantize_first(size_t size)
 154 {
 155         size_t qsize = run_quantize(size);
 156
 157         if (qsize < size) {
 158                 /*
 159                  * Skip a quantization that may have an adequately large run,
 160                  * because under-sized runs may be mixed in.  This only happens
 161                  * when an unusual size is requested, i.e. for aligned
 162                  * allocation, and is just one of several places where linear
 163                  * search would potentially find sufficiently aligned available
 164                  * memory somewhere lower.
 165                  */
 166                 qsize = run_quantize_next(size);
 167         }
 168         return (qsize);
 169 }
 170
 171 JEMALLOC_INLINE_C int
 172 arena_avail_comp(arena_chunk_map_misc_t *a, arena_chunk_map_misc_t *b)
 173 {
 174         int ret;
 175         uintptr_t a_miscelm = (uintptr_t)a;
 176         size_t a_qsize = run_quantize(arena_miscelm_is_key(a) ?
 177             arena_miscelm_key_size_get(a) : arena_miscelm_size_get(a));
 178         size_t b_qsize = run_quantize(arena_miscelm_size_get(b));
 179
 180         /*
 181          * Compare based on quantized size rather than size, in order to sort
 182          * equally useful runs only by address.
 183          */
 184         ret = (a_qsize > b_qsize) - (a_qsize < b_qsize);
 185         if (ret == 0) {
 186                 if (!arena_miscelm_is_key(a)) {
 187                         uintptr_t b_miscelm = (uintptr_t)b;
 188
 189                         ret = (a_miscelm > b_miscelm) - (a_miscelm < b_miscelm);
 190                 } else {
 191                         /*
 192                          * Treat keys as if they are lower than anything else.
 193                          */
 194                         ret = -1;
 195                 }
 196         }
 197
 198         return (ret);
 199 }
 200
 201 /* Generate red-black tree functions. */
 202 rb_gen(static UNUSED, arena_avail_tree_, arena_avail_tree_t,
 203     arena_chunk_map_misc_t, rb_link, arena_avail_comp)
 204
 205 static void
 206 arena_avail_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
 207     size_t npages)
 208 {
 209
 210         assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
 211             LG_PAGE));
 212         arena_avail_tree_insert(&arena->runs_avail, arena_miscelm_get(chunk,
 213             pageind));
 214 }
 215
 216 static void
 217 arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
 218     size_t npages)
 219 {
 220
 221         assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
 222             LG_PAGE));
 223         arena_avail_tree_remove(&arena->runs_avail, arena_miscelm_get(chunk,
 224             pageind));
 225 }
 226
 227 static void
 228 arena_run_dirty_insert(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
 229     size_t npages)
 230 {
 231         arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
 232
 233         assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
 234             LG_PAGE));
 235         assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY);
 236         assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) ==
 237             CHUNK_MAP_DIRTY);
 238
 239         qr_new(&miscelm->rd, rd_link);
 240         qr_meld(&arena->runs_dirty, &miscelm->rd, rd_link);
 241         arena->ndirty += npages;
 242 }
 243
 244 static void
 245 arena_run_dirty_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
 246     size_t npages)
 247 {
 248         arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
 249
 250         assert(npages == (arena_mapbits_unallocated_size_get(chunk, pageind) >>
 251             LG_PAGE));
 252         assert(arena_mapbits_dirty_get(chunk, pageind) == CHUNK_MAP_DIRTY);
 253         assert(arena_mapbits_dirty_get(chunk, pageind+npages-1) ==
 254             CHUNK_MAP_DIRTY);
 255
 256         qr_remove(&miscelm->rd, rd_link);
 257         assert(arena->ndirty >= npages);
 258         arena->ndirty -= npages;
 259 }
 260
 261 static size_t
 262 arena_chunk_dirty_npages(const extent_node_t *node)
 263 {
 264
 265         return (extent_node_size_get(node) >> LG_PAGE);
 266 }
 267
 268 void
 269 arena_chunk_cache_maybe_insert(arena_t *arena, extent_node_t *node, bool cache)
 270 {
 271
 272         if (cache) {
 273                 extent_node_dirty_linkage_init(node);
 274                 extent_node_dirty_insert(node, &arena->runs_dirty,
 275                     &arena->chunks_cache);
 276                 arena->ndirty += arena_chunk_dirty_npages(node);
 277         }
 278 }
 279
 280 void
 281 arena_chunk_cache_maybe_remove(arena_t *arena, extent_node_t *node, bool dirty)
 282 {
 283
 284         if (dirty) {
 285                 extent_node_dirty_remove(node);
 286                 assert(arena->ndirty >= arena_chunk_dirty_npages(node));
 287                 arena->ndirty -= arena_chunk_dirty_npages(node);
 288         }
 289 }
 290
 291 JEMALLOC_INLINE_C void *
 292 arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info)
 293 {
 294         void *ret;
 295         unsigned regind;
 296         arena_chunk_map_misc_t *miscelm;
 297         void *rpages;
 298
 299         assert(run->nfree > 0);
 300         assert(!bitmap_full(run->bitmap, &bin_info->bitmap_info));
 301
 302         regind = bitmap_sfu(run->bitmap, &bin_info->bitmap_info);
 303         miscelm = arena_run_to_miscelm(run);
 304         rpages = arena_miscelm_to_rpages(miscelm);
 305         ret = (void *)((uintptr_t)rpages + (uintptr_t)bin_info->reg0_offset +
 306             (uintptr_t)(bin_info->reg_interval * regind));
 307         run->nfree--;
 308         return (ret);
 309 }
 310
 311 JEMALLOC_INLINE_C void
 312 arena_run_reg_dalloc(arena_run_t *run, void *ptr)
 313 {
 314         arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
 315         size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
 316         size_t mapbits = arena_mapbits_get(chunk, pageind);
 317         szind_t binind = arena_ptr_small_binind_get(ptr, mapbits);
 318         arena_bin_info_t *bin_info = &arena_bin_info[binind];
 319         unsigned regind = arena_run_regind(run, bin_info, ptr);
 320
 321         assert(run->nfree < bin_info->nregs);
 322         /* Freeing an interior pointer can cause assertion failure. */
 323         assert(((uintptr_t)ptr -
 324             ((uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) +
 325             (uintptr_t)bin_info->reg0_offset)) %
 326             (uintptr_t)bin_info->reg_interval == 0);
 327         assert((uintptr_t)ptr >=
 328             (uintptr_t)arena_miscelm_to_rpages(arena_run_to_miscelm(run)) +
 329             (uintptr_t)bin_info->reg0_offset);
 330         /* Freeing an unallocated pointer can cause assertion failure. */
 331         assert(bitmap_get(run->bitmap, &bin_info->bitmap_info, regind));
 332
 333         bitmap_unset(run->bitmap, &bin_info->bitmap_info, regind);
 334         run->nfree++;
 335 }
 336
 337 JEMALLOC_INLINE_C void
 338 arena_run_zero(arena_chunk_t *chunk, size_t run_ind, size_t npages)
 339 {
 340
 341         JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
 342             (run_ind << LG_PAGE)), (npages << LG_PAGE));
 343         memset((void *)((uintptr_t)chunk + (run_ind << LG_PAGE)), 0,
 344             (npages << LG_PAGE));
 345 }
 346
 347 JEMALLOC_INLINE_C void
 348 arena_run_page_mark_zeroed(arena_chunk_t *chunk, size_t run_ind)
 349 {
 350
 351         JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void *)((uintptr_t)chunk + (run_ind
 352             << LG_PAGE)), PAGE);
 353 }
 354
 355 JEMALLOC_INLINE_C void
 356 arena_run_page_validate_zeroed(arena_chunk_t *chunk, size_t run_ind)
 357 {
 358         size_t i;
 359         UNUSED size_t *p = (size_t *)((uintptr_t)chunk + (run_ind << LG_PAGE));
 360
 361         arena_run_page_mark_zeroed(chunk, run_ind);
 362         for (i = 0; i < PAGE / sizeof(size_t); i++)
 363                 assert(p[i] == 0);
 364 }
 365
 366 static void
 367 arena_cactive_update(arena_t *arena, size_t add_pages, size_t sub_pages)
 368 {
 369
 370         if (config_stats) {
 371                 ssize_t cactive_diff = CHUNK_CEILING((arena->nactive + add_pages
 372                     - sub_pages) << LG_PAGE) - CHUNK_CEILING(arena->nactive <<
 373                     LG_PAGE);
 374                 if (cactive_diff != 0)
 375                         stats_cactive_add(cactive_diff);
 376         }
 377 }
 378
 379 static void
 380 arena_run_split_remove(arena_t *arena, arena_chunk_t *chunk, size_t run_ind,
 381     size_t flag_dirty, size_t flag_decommitted, size_t need_pages)
 382 {
 383         size_t total_pages, rem_pages;
 384
 385         assert(flag_dirty == 0 || flag_decommitted == 0);
 386
 387         total_pages = arena_mapbits_unallocated_size_get(chunk, run_ind) >>
 388             LG_PAGE;
 389         assert(arena_mapbits_dirty_get(chunk, run_ind+total_pages-1) ==
 390             flag_dirty);
 391         assert(need_pages <= total_pages);
 392         rem_pages = total_pages - need_pages;
 393
 394         arena_avail_remove(arena, chunk, run_ind, total_pages);
 395         if (flag_dirty != 0)
 396                 arena_run_dirty_remove(arena, chunk, run_ind, total_pages);
 397         arena_cactive_update(arena, need_pages, 0);
 398         arena->nactive += need_pages;
 399
 400         /* Keep track of trailing unused pages for later use. */
 401         if (rem_pages > 0) {
 402                 size_t flags = flag_dirty | flag_decommitted;
 403                 size_t flag_unzeroed_mask = (flags == 0) ?  CHUNK_MAP_UNZEROED :
 404                     0;
 405
 406                 arena_mapbits_unallocated_set(chunk, run_ind+need_pages,
 407                     (rem_pages << LG_PAGE), flags |
 408                     (arena_mapbits_unzeroed_get(chunk, run_ind+need_pages) &
 409                     flag_unzeroed_mask));
 410                 arena_mapbits_unallocated_set(chunk, run_ind+total_pages-1,
 411                     (rem_pages << LG_PAGE), flags |
 412                     (arena_mapbits_unzeroed_get(chunk, run_ind+total_pages-1) &
 413                     flag_unzeroed_mask));
 414                 if (flag_dirty != 0) {
 415                         arena_run_dirty_insert(arena, chunk, run_ind+need_pages,
 416                             rem_pages);
 417                 }
 418                 arena_avail_insert(arena, chunk, run_ind+need_pages, rem_pages);
 419         }
 420 }
 421
 422 static bool
 423 arena_run_split_large_helper(arena_t *arena, arena_run_t *run, size_t size,
 424     bool remove, bool zero)
 425 {
 426         arena_chunk_t *chunk;
 427         arena_chunk_map_misc_t *miscelm;
 428         size_t flag_dirty, flag_decommitted, run_ind, need_pages;
 429         size_t flag_unzeroed_mask;
 430
 431         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
 432         miscelm = arena_run_to_miscelm(run);
 433         run_ind = arena_miscelm_to_pageind(miscelm);
 434         flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
 435         flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind);
 436         need_pages = (size >> LG_PAGE);
 437         assert(need_pages > 0);
 438
 439         if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize,
 440             run_ind << LG_PAGE, size, arena->ind))
 441                 return (true);
 442
 443         if (remove) {
 444                 arena_run_split_remove(arena, chunk, run_ind, flag_dirty,
 445                     flag_decommitted, need_pages);
 446         }
 447
 448         if (zero) {
 449                 if (flag_decommitted != 0) {
 450                         /* The run is untouched, and therefore zeroed. */
 451                         JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void
 452                             *)((uintptr_t)chunk + (run_ind << LG_PAGE)),
 453                             (need_pages << LG_PAGE));
 454                 } else if (flag_dirty != 0) {
 455                         /* The run is dirty, so all pages must be zeroed. */
 456                         arena_run_zero(chunk, run_ind, need_pages);
 457                 } else {
 458                         /*
 459                          * The run is clean, so some pages may be zeroed (i.e.
 460                          * never before touched).
 461                          */
 462                         size_t i;
 463                         for (i = 0; i < need_pages; i++) {
 464                                 if (arena_mapbits_unzeroed_get(chunk, run_ind+i)
 465                                     != 0)
 466                                         arena_run_zero(chunk, run_ind+i, 1);
 467                                 else if (config_debug) {
 468                                         arena_run_page_validate_zeroed(chunk,
 469                                             run_ind+i);
 470                                 } else {
 471                                         arena_run_page_mark_zeroed(chunk,
 472                                             run_ind+i);
 473                                 }
 474                         }
 475                 }
 476         } else {
 477                 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
 478                     (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
 479         }
 480
 481         /*
 482          * Set the last element first, in case the run only contains one page
 483          * (i.e. both statements set the same element).
 484          */
 485         flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
 486             CHUNK_MAP_UNZEROED : 0;
 487         arena_mapbits_large_set(chunk, run_ind+need_pages-1, 0, flag_dirty |
 488             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
 489             run_ind+need_pages-1)));
 490         arena_mapbits_large_set(chunk, run_ind, size, flag_dirty |
 491             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, run_ind)));
 492         return (false);
 493 }
 494
 495 static bool
 496 arena_run_split_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
 497 {
 498
 499         return (arena_run_split_large_helper(arena, run, size, true, zero));
 500 }
 501
 502 static bool
 503 arena_run_init_large(arena_t *arena, arena_run_t *run, size_t size, bool zero)
 504 {
 505
 506         return (arena_run_split_large_helper(arena, run, size, false, zero));
 507 }
 508
 509 static bool
 510 arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size,
 511     szind_t binind)
 512 {
 513         arena_chunk_t *chunk;
 514         arena_chunk_map_misc_t *miscelm;
 515         size_t flag_dirty, flag_decommitted, run_ind, need_pages, i;
 516
 517         assert(binind != BININD_INVALID);
 518
 519         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
 520         miscelm = arena_run_to_miscelm(run);
 521         run_ind = arena_miscelm_to_pageind(miscelm);
 522         flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
 523         flag_decommitted = arena_mapbits_decommitted_get(chunk, run_ind);
 524         need_pages = (size >> LG_PAGE);
 525         assert(need_pages > 0);
 526
 527         if (flag_decommitted != 0 && arena->chunk_hooks.commit(chunk, chunksize,
 528             run_ind << LG_PAGE, size, arena->ind))
 529                 return (true);
 530
 531         arena_run_split_remove(arena, chunk, run_ind, flag_dirty,
 532             flag_decommitted, need_pages);
 533
 534         for (i = 0; i < need_pages; i++) {
 535                 size_t flag_unzeroed = arena_mapbits_unzeroed_get(chunk,
 536                     run_ind+i);
 537                 arena_mapbits_small_set(chunk, run_ind+i, i, binind,
 538                     flag_unzeroed);
 539                 if (config_debug && flag_dirty == 0 && flag_unzeroed == 0)
 540                         arena_run_page_validate_zeroed(chunk, run_ind+i);
 541         }
 542         JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED((void *)((uintptr_t)chunk +
 543             (run_ind << LG_PAGE)), (need_pages << LG_PAGE));
 544         return (false);
 545 }
 546
 547 static arena_chunk_t *
 548 arena_chunk_init_spare(arena_t *arena)
 549 {
 550         arena_chunk_t *chunk;
 551
 552         assert(arena->spare != NULL);
 553
 554         chunk = arena->spare;
 555         arena->spare = NULL;
 556
 557         assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
 558         assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
 559         assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
 560             arena_maxrun);
 561         assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
 562             arena_maxrun);
 563         assert(arena_mapbits_dirty_get(chunk, map_bias) ==
 564             arena_mapbits_dirty_get(chunk, chunk_npages-1));
 565
 566         return (chunk);
 567 }
 568
 569 static bool
 570 arena_chunk_register(arena_t *arena, arena_chunk_t *chunk, bool zero)
 571 {
 572
 573         /*
 574          * The extent node notion of "committed" doesn't directly apply to
 575          * arena chunks.  Arbitrarily mark them as committed.  The commit state
 576          * of runs is tracked individually, and upon chunk deallocation the
 577          * entire chunk is in a consistent commit state.
 578          */
 579         extent_node_init(&chunk->node, arena, chunk, chunksize, zero, true);
 580         extent_node_achunk_set(&chunk->node, true);
 581         return (chunk_register(chunk, &chunk->node));
 582 }
 583
 584 static arena_chunk_t *
 585 arena_chunk_alloc_internal_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
 586     bool *zero, bool *commit)
 587 {
 588         arena_chunk_t *chunk;
 589
 590         malloc_mutex_unlock(&arena->lock);
 591
 592         chunk = (arena_chunk_t *)chunk_alloc_wrapper(arena, chunk_hooks, NULL,
 593             chunksize, chunksize, zero, commit);
 594         if (chunk != NULL && !*commit) {
 595                 /* Commit header. */
 596                 if (chunk_hooks->commit(chunk, chunksize, 0, map_bias <<
 597                     LG_PAGE, arena->ind)) {
 598                         chunk_dalloc_wrapper(arena, chunk_hooks,
 599                             (void *)chunk, chunksize, *commit);
 600                         chunk = NULL;
 601                 }
 602         }
 603         if (chunk != NULL && arena_chunk_register(arena, chunk, *zero)) {
 604                 if (!*commit) {
 605                         /* Undo commit of header. */
 606                         chunk_hooks->decommit(chunk, chunksize, 0, map_bias <<
 607                             LG_PAGE, arena->ind);
 608                 }
 609                 chunk_dalloc_wrapper(arena, chunk_hooks, (void *)chunk,
 610                     chunksize, *commit);
 611                 chunk = NULL;
 612         }
 613
 614         malloc_mutex_lock(&arena->lock);
 615         return (chunk);
 616 }
 617
 618 static arena_chunk_t *
 619 arena_chunk_alloc_internal(arena_t *arena, bool *zero, bool *commit)
 620 {
 621         arena_chunk_t *chunk;
 622         chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
 623
 624         chunk = chunk_alloc_cache(arena, &chunk_hooks, NULL, chunksize,
 625             chunksize, zero, true);
 626         if (chunk != NULL) {
 627                 if (arena_chunk_register(arena, chunk, *zero)) {
 628                         chunk_dalloc_cache(arena, &chunk_hooks, chunk,
 629                             chunksize, true);
 630                         return (NULL);
 631                 }
 632                 *commit = true;
 633         }
 634         if (chunk == NULL) {
 635                 chunk = arena_chunk_alloc_internal_hard(arena, &chunk_hooks,
 636                     zero, commit);
 637         }
 638
 639         if (config_stats && chunk != NULL) {
 640                 arena->stats.mapped += chunksize;
 641                 arena->stats.metadata_mapped += (map_bias << LG_PAGE);
 642         }
 643
 644         return (chunk);
 645 }
 646
 647 static arena_chunk_t *
 648 arena_chunk_init_hard(arena_t *arena)
 649 {
 650         arena_chunk_t *chunk;
 651         bool zero, commit;
 652         size_t flag_unzeroed, flag_decommitted, i;
 653
 654         assert(arena->spare == NULL);
 655
 656         zero = false;
 657         commit = false;
 658         chunk = arena_chunk_alloc_internal(arena, &zero, &commit);
 659         if (chunk == NULL)
 660                 return (NULL);
 661
 662         /*
 663          * Initialize the map to contain one maximal free untouched run.  Mark
 664          * the pages as zeroed if chunk_alloc() returned a zeroed or decommitted
 665          * chunk.
 666          */
 667         flag_unzeroed = (zero || !commit) ? 0 : CHUNK_MAP_UNZEROED;
 668         flag_decommitted = commit ? 0 : CHUNK_MAP_DECOMMITTED;
 669         arena_mapbits_unallocated_set(chunk, map_bias, arena_maxrun,
 670             flag_unzeroed | flag_decommitted);
 671         /*
 672          * There is no need to initialize the internal page map entries unless
 673          * the chunk is not zeroed.
 674          */
 675         if (!zero) {
 676                 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(
 677                     (void *)arena_bitselm_get(chunk, map_bias+1),
 678                     (size_t)((uintptr_t) arena_bitselm_get(chunk,
 679                     chunk_npages-1) - (uintptr_t)arena_bitselm_get(chunk,
 680                     map_bias+1)));
 681                 for (i = map_bias+1; i < chunk_npages-1; i++)
 682                         arena_mapbits_internal_set(chunk, i, flag_unzeroed);
 683         } else {
 684                 JEMALLOC_VALGRIND_MAKE_MEM_DEFINED((void
 685                     *)arena_bitselm_get(chunk, map_bias+1), (size_t)((uintptr_t)
 686                     arena_bitselm_get(chunk, chunk_npages-1) -
 687                     (uintptr_t)arena_bitselm_get(chunk, map_bias+1)));
 688                 if (config_debug) {
 689                         for (i = map_bias+1; i < chunk_npages-1; i++) {
 690                                 assert(arena_mapbits_unzeroed_get(chunk, i) ==
 691                                     flag_unzeroed);
 692                         }
 693                 }
 694         }
 695         arena_mapbits_unallocated_set(chunk, chunk_npages-1, arena_maxrun,
 696             flag_unzeroed);
 697
 698         return (chunk);
 699 }
 700
 701 static arena_chunk_t *
 702 arena_chunk_alloc(arena_t *arena)
 703 {
 704         arena_chunk_t *chunk;
 705
 706         if (arena->spare != NULL)
 707                 chunk = arena_chunk_init_spare(arena);
 708         else {
 709                 chunk = arena_chunk_init_hard(arena);
 710                 if (chunk == NULL)
 711                         return (NULL);
 712         }
 713
 714         /* Insert the run into the runs_avail tree. */
 715         arena_avail_insert(arena, chunk, map_bias, chunk_npages-map_bias);
 716
 717         return (chunk);
 718 }
 719
 720 static void
 721 arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk)
 722 {
 723
 724         assert(arena_mapbits_allocated_get(chunk, map_bias) == 0);
 725         assert(arena_mapbits_allocated_get(chunk, chunk_npages-1) == 0);
 726         assert(arena_mapbits_unallocated_size_get(chunk, map_bias) ==
 727             arena_maxrun);
 728         assert(arena_mapbits_unallocated_size_get(chunk, chunk_npages-1) ==
 729             arena_maxrun);
 730         assert(arena_mapbits_dirty_get(chunk, map_bias) ==
 731             arena_mapbits_dirty_get(chunk, chunk_npages-1));
 732         assert(arena_mapbits_decommitted_get(chunk, map_bias) ==
 733             arena_mapbits_decommitted_get(chunk, chunk_npages-1));
 734
 735         /*
 736          * Remove run from the runs_avail tree, so that the arena does not use
 737          * it.
 738          */
 739         arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias);
 740
 741         if (arena->spare != NULL) {
 742                 arena_chunk_t *spare = arena->spare;
 743                 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
 744                 bool committed;
 745
 746                 arena->spare = chunk;
 747                 if (arena_mapbits_dirty_get(spare, map_bias) != 0) {
 748                         arena_run_dirty_remove(arena, spare, map_bias,
 749                             chunk_npages-map_bias);
 750                 }
 751
 752                 chunk_deregister(spare, &spare->node);
 753
 754                 committed = (arena_mapbits_decommitted_get(spare, map_bias) ==
 755                     0);
 756                 if (!committed) {
 757                         /*
 758                          * Decommit the header.  Mark the chunk as decommitted
 759                          * even if header decommit fails, since treating a
 760                          * partially committed chunk as committed has a high
 761                          * potential for causing later access of decommitted
 762                          * memory.
 763                          */
 764                         chunk_hooks = chunk_hooks_get(arena);
 765                         chunk_hooks.decommit(spare, chunksize, 0, map_bias <<
 766                             LG_PAGE, arena->ind);
 767                 }
 768
 769                 chunk_dalloc_cache(arena, &chunk_hooks, (void *)spare,
 770                     chunksize, committed);
 771
 772                 if (config_stats) {
 773                         arena->stats.mapped -= chunksize;
 774                         arena->stats.metadata_mapped -= (map_bias << LG_PAGE);
 775                 }
 776         } else
 777                 arena->spare = chunk;
 778 }
 779
 780 static void
 781 arena_huge_malloc_stats_update(arena_t *arena, size_t usize)
 782 {
 783         szind_t index = size2index(usize) - nlclasses - NBINS;
 784
 785         cassert(config_stats);
 786
 787         arena->stats.nmalloc_huge++;
 788         arena->stats.allocated_huge += usize;
 789         arena->stats.hstats[index].nmalloc++;
 790         arena->stats.hstats[index].curhchunks++;
 791 }
 792
 793 static void
 794 arena_huge_malloc_stats_update_undo(arena_t *arena, size_t usize)
 795 {
 796         szind_t index = size2index(usize) - nlclasses - NBINS;
 797
 798         cassert(config_stats);
 799
 800         arena->stats.nmalloc_huge--;
 801         arena->stats.allocated_huge -= usize;
 802         arena->stats.hstats[index].nmalloc--;
 803         arena->stats.hstats[index].curhchunks--;
 804 }
 805
 806 static void
 807 arena_huge_dalloc_stats_update(arena_t *arena, size_t usize)
 808 {
 809         szind_t index = size2index(usize) - nlclasses - NBINS;
 810
 811         cassert(config_stats);
 812
 813         arena->stats.ndalloc_huge++;
 814         arena->stats.allocated_huge -= usize;
 815         arena->stats.hstats[index].ndalloc++;
 816         arena->stats.hstats[index].curhchunks--;
 817 }
 818
 819 static void
 820 arena_huge_dalloc_stats_update_undo(arena_t *arena, size_t usize)
 821 {
 822         szind_t index = size2index(usize) - nlclasses - NBINS;
 823
 824         cassert(config_stats);
 825
 826         arena->stats.ndalloc_huge--;
 827         arena->stats.allocated_huge += usize;
 828         arena->stats.hstats[index].ndalloc--;
 829         arena->stats.hstats[index].curhchunks++;
 830 }
 831
 832 static void
 833 arena_huge_ralloc_stats_update(arena_t *arena, size_t oldsize, size_t usize)
 834 {
 835
 836         arena_huge_dalloc_stats_update(arena, oldsize);
 837         arena_huge_malloc_stats_update(arena, usize);
 838 }
 839
 840 static void
 841 arena_huge_ralloc_stats_update_undo(arena_t *arena, size_t oldsize,
 842     size_t usize)
 843 {
 844
 845         arena_huge_dalloc_stats_update_undo(arena, oldsize);
 846         arena_huge_malloc_stats_update_undo(arena, usize);
 847 }
 848
 849 extent_node_t *
 850 arena_node_alloc(arena_t *arena)
 851 {
 852         extent_node_t *node;
 853
 854         malloc_mutex_lock(&arena->node_cache_mtx);
 855         node = ql_last(&arena->node_cache, ql_link);
 856         if (node == NULL) {
 857                 malloc_mutex_unlock(&arena->node_cache_mtx);
 858                 return (base_alloc(sizeof(extent_node_t)));
 859         }
 860         ql_tail_remove(&arena->node_cache, extent_node_t, ql_link);
 861         malloc_mutex_unlock(&arena->node_cache_mtx);
 862         return (node);
 863 }
 864
 865 void
 866 arena_node_dalloc(arena_t *arena, extent_node_t *node)
 867 {
 868
 869         malloc_mutex_lock(&arena->node_cache_mtx);
 870         ql_elm_new(node, ql_link);
 871         ql_tail_insert(&arena->node_cache, node, ql_link);
 872         malloc_mutex_unlock(&arena->node_cache_mtx);
 873 }
 874
 875 static void *
 876 arena_chunk_alloc_huge_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
 877     size_t usize, size_t alignment, bool *zero, size_t csize)
 878 {
 879         void *ret;
 880         bool commit = true;
 881
 882         ret = chunk_alloc_wrapper(arena, chunk_hooks, NULL, csize, alignment,
 883             zero, &commit);
 884         if (ret == NULL) {
 885                 /* Revert optimistic stats updates. */
 886                 malloc_mutex_lock(&arena->lock);
 887                 if (config_stats) {
 888                         arena_huge_malloc_stats_update_undo(arena, usize);
 889                         arena->stats.mapped -= usize;
 890                 }
 891                 arena->nactive -= (usize >> LG_PAGE);
 892                 malloc_mutex_unlock(&arena->lock);
 893         }
 894
 895         return (ret);
 896 }
 897
 898 void *
 899 arena_chunk_alloc_huge(arena_t *arena, size_t usize, size_t alignment,
 900     bool *zero)
 901 {
 902         void *ret;
 903         chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
 904         size_t csize = CHUNK_CEILING(usize);
 905
 906         malloc_mutex_lock(&arena->lock);
 907
 908         /* Optimistically update stats. */
 909         if (config_stats) {
 910                 arena_huge_malloc_stats_update(arena, usize);
 911                 arena->stats.mapped += usize;
 912         }
 913         arena->nactive += (usize >> LG_PAGE);
 914
 915         ret = chunk_alloc_cache(arena, &chunk_hooks, NULL, csize, alignment,
 916             zero, true);
 917         malloc_mutex_unlock(&arena->lock);
 918         if (ret == NULL) {
 919                 ret = arena_chunk_alloc_huge_hard(arena, &chunk_hooks, usize,
 920                     alignment, zero, csize);
 921         }
 922
 923         if (config_stats && ret != NULL)
 924                 stats_cactive_add(usize);
 925         return (ret);
 926 }
 927
 928 void
 929 arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t usize)
 930 {
 931         chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
 932         size_t csize;
 933
 934         csize = CHUNK_CEILING(usize);
 935         malloc_mutex_lock(&arena->lock);
 936         if (config_stats) {
 937                 arena_huge_dalloc_stats_update(arena, usize);
 938                 arena->stats.mapped -= usize;
 939                 stats_cactive_sub(usize);
 940         }
 941         arena->nactive -= (usize >> LG_PAGE);
 942
 943         chunk_dalloc_cache(arena, &chunk_hooks, chunk, csize, true);
 944         malloc_mutex_unlock(&arena->lock);
 945 }
 946
 947 void
 948 arena_chunk_ralloc_huge_similar(arena_t *arena, void *chunk, size_t oldsize,
 949     size_t usize)
 950 {
 951
 952         assert(CHUNK_CEILING(oldsize) == CHUNK_CEILING(usize));
 953         assert(oldsize != usize);
 954
 955         malloc_mutex_lock(&arena->lock);
 956         if (config_stats)
 957                 arena_huge_ralloc_stats_update(arena, oldsize, usize);
 958         if (oldsize < usize) {
 959                 size_t udiff = usize - oldsize;
 960                 arena->nactive += udiff >> LG_PAGE;
 961                 if (config_stats)
 962                         stats_cactive_add(udiff);
 963         } else {
 964                 size_t udiff = oldsize - usize;
 965                 arena->nactive -= udiff >> LG_PAGE;
 966                 if (config_stats)
 967                         stats_cactive_sub(udiff);
 968         }
 969         malloc_mutex_unlock(&arena->lock);
 970 }
 971
 972 void
 973 arena_chunk_ralloc_huge_shrink(arena_t *arena, void *chunk, size_t oldsize,
 974     size_t usize)
 975 {
 976         size_t udiff = oldsize - usize;
 977         size_t cdiff = CHUNK_CEILING(oldsize) - CHUNK_CEILING(usize);
 978
 979         malloc_mutex_lock(&arena->lock);
 980         if (config_stats) {
 981                 arena_huge_ralloc_stats_update(arena, oldsize, usize);
 982                 if (cdiff != 0) {
 983                         arena->stats.mapped -= cdiff;
 984                         stats_cactive_sub(udiff);
 985                 }
 986         }
 987         arena->nactive -= udiff >> LG_PAGE;
 988
 989         if (cdiff != 0) {
 990                 chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;
 991                 void *nchunk = (void *)((uintptr_t)chunk +
 992                     CHUNK_CEILING(usize));
 993
 994                 chunk_dalloc_cache(arena, &chunk_hooks, nchunk, cdiff, true);
 995         }
 996         malloc_mutex_unlock(&arena->lock);
 997 }
 998
 999 static bool
1000 arena_chunk_ralloc_huge_expand_hard(arena_t *arena, chunk_hooks_t *chunk_hooks,
1001     void *chunk, size_t oldsize, size_t usize, bool *zero, void *nchunk,
1002     size_t udiff, size_t cdiff)
1003 {
1004         bool err;
1005         bool commit = true;
1006
1007         err = (chunk_alloc_wrapper(arena, chunk_hooks, nchunk, cdiff, chunksize,
1008             zero, &commit) == NULL);
1009         if (err) {
1010                 /* Revert optimistic stats updates. */
1011                 malloc_mutex_lock(&arena->lock);
1012                 if (config_stats) {
1013                         arena_huge_ralloc_stats_update_undo(arena, oldsize,
1014                             usize);
1015                         arena->stats.mapped -= cdiff;
1016                 }
1017                 arena->nactive -= (udiff >> LG_PAGE);
1018                 malloc_mutex_unlock(&arena->lock);
1019         } else if (chunk_hooks->merge(chunk, CHUNK_CEILING(oldsize), nchunk,
1020             cdiff, true, arena->ind)) {
1021                 chunk_dalloc_arena(arena, chunk_hooks, nchunk, cdiff, *zero,
1022                     true);
1023                 err = true;
1024         }
1025         return (err);
1026 }
1027
1028 bool
1029 arena_chunk_ralloc_huge_expand(arena_t *arena, void *chunk, size_t oldsize,
1030     size_t usize, bool *zero)
1031 {
1032         bool err;
1033         chunk_hooks_t chunk_hooks = chunk_hooks_get(arena);
1034         void *nchunk = (void *)((uintptr_t)chunk + CHUNK_CEILING(oldsize));
1035         size_t udiff = usize - oldsize;
1036         size_t cdiff = CHUNK_CEILING(usize) - CHUNK_CEILING(oldsize);
1037
1038         malloc_mutex_lock(&arena->lock);
1039
1040         /* Optimistically update stats. */
1041         if (config_stats) {
1042                 arena_huge_ralloc_stats_update(arena, oldsize, usize);
1043                 arena->stats.mapped += cdiff;
1044         }
1045         arena->nactive += (udiff >> LG_PAGE);
1046
1047         err = (chunk_alloc_cache(arena, &arena->chunk_hooks, nchunk, cdiff,
1048             chunksize, zero, true) == NULL);
1049         malloc_mutex_unlock(&arena->lock);
1050         if (err) {
1051                 err = arena_chunk_ralloc_huge_expand_hard(arena, &chunk_hooks,
1052                     chunk, oldsize, usize, zero, nchunk, udiff,
1053                     cdiff);
1054         } else if (chunk_hooks.merge(chunk, CHUNK_CEILING(oldsize), nchunk,
1055             cdiff, true, arena->ind)) {
1056                 chunk_dalloc_arena(arena, &chunk_hooks, nchunk, cdiff, *zero,
1057                     true);
1058                 err = true;
1059         }
1060
1061         if (config_stats && !err)
1062                 stats_cactive_add(udiff);
1063         return (err);
1064 }
1065
1066 /*
1067  * Do first-best-fit run selection, i.e. select the lowest run that best fits.
1068  * Run sizes are quantized, so not all candidate runs are necessarily exactly
1069  * the same size.
1070  */
1071 static arena_run_t *
1072 arena_run_first_best_fit(arena_t *arena, size_t size)
1073 {
1074         size_t search_size = run_quantize_first(size);
1075         arena_chunk_map_misc_t *key = arena_miscelm_key_create(search_size);
1076         arena_chunk_map_misc_t *miscelm =
1077             arena_avail_tree_nsearch(&arena->runs_avail, key);
1078         if (miscelm == NULL)
1079                 return (NULL);
1080         return (&miscelm->run);
1081 }
1082
1083 static arena_run_t *
1084 arena_run_alloc_large_helper(arena_t *arena, size_t size, bool zero)
1085 {
1086         arena_run_t *run = arena_run_first_best_fit(arena, s2u(size));
1087         if (run != NULL) {
1088                 if (arena_run_split_large(arena, run, size, zero))
1089                         run = NULL;
1090         }
1091         return (run);
1092 }
1093
1094 static arena_run_t *
1095 arena_run_alloc_large(arena_t *arena, size_t size, bool zero)
1096 {
1097         arena_chunk_t *chunk;
1098         arena_run_t *run;
1099
1100         assert(size <= arena_maxrun);
1101         assert(size == PAGE_CEILING(size));
1102
1103         /* Search the arena's chunks for the lowest best fit. */
1104         run = arena_run_alloc_large_helper(arena, size, zero);
1105         if (run != NULL)
1106                 return (run);
1107
1108         /*
1109          * No usable runs.  Create a new chunk from which to allocate the run.
1110          */
1111         chunk = arena_chunk_alloc(arena);
1112         if (chunk != NULL) {
1113                 run = &arena_miscelm_get(chunk, map_bias)->run;
1114                 if (arena_run_split_large(arena, run, size, zero))
1115                         run = NULL;
1116                 return (run);
1117         }
1118
1119         /*
1120          * arena_chunk_alloc() failed, but another thread may have made
1121          * sufficient memory available while this one dropped arena->lock in
1122          * arena_chunk_alloc(), so search one more time.
1123          */
1124         return (arena_run_alloc_large_helper(arena, size, zero));
1125 }
1126
1127 static arena_run_t *
1128 arena_run_alloc_small_helper(arena_t *arena, size_t size, szind_t binind)
1129 {
1130         arena_run_t *run = arena_run_first_best_fit(arena, size);
1131         if (run != NULL) {
1132                 if (arena_run_split_small(arena, run, size, binind))
1133                         run = NULL;
1134         }
1135         return (run);
1136 }
1137
1138 static arena_run_t *
1139 arena_run_alloc_small(arena_t *arena, size_t size, szind_t binind)
1140 {
1141         arena_chunk_t *chunk;
1142         arena_run_t *run;
1143
1144         assert(size <= arena_maxrun);
1145         assert(size == PAGE_CEILING(size));
1146         assert(binind != BININD_INVALID);
1147
1148         /* Search the arena's chunks for the lowest best fit. */
1149         run = arena_run_alloc_small_helper(arena, size, binind);
1150         if (run != NULL)
1151                 return (run);
1152
1153         /*
1154          * No usable runs.  Create a new chunk from which to allocate the run.
1155          */
1156         chunk = arena_chunk_alloc(arena);
1157         if (chunk != NULL) {
1158                 run = &arena_miscelm_get(chunk, map_bias)->run;
1159                 if (arena_run_split_small(arena, run, size, binind))
1160                         run = NULL;
1161                 return (run);
1162         }
1163
1164         /*
1165          * arena_chunk_alloc() failed, but another thread may have made
1166          * sufficient memory available while this one dropped arena->lock in
1167          * arena_chunk_alloc(), so search one more time.
1168          */
1169         return (arena_run_alloc_small_helper(arena, size, binind));
1170 }
1171
1172 static bool
1173 arena_lg_dirty_mult_valid(ssize_t lg_dirty_mult)
1174 {
1175
1176         return (lg_dirty_mult >= -1 && lg_dirty_mult < (ssize_t)(sizeof(size_t)
1177             << 3));
1178 }
1179
1180 ssize_t
1181 arena_lg_dirty_mult_get(arena_t *arena)
1182 {
1183         ssize_t lg_dirty_mult;
1184
1185         malloc_mutex_lock(&arena->lock);
1186         lg_dirty_mult = arena->lg_dirty_mult;
1187         malloc_mutex_unlock(&arena->lock);
1188
1189         return (lg_dirty_mult);
1190 }
1191
1192 bool
1193 arena_lg_dirty_mult_set(arena_t *arena, ssize_t lg_dirty_mult)
1194 {
1195
1196         if (!arena_lg_dirty_mult_valid(lg_dirty_mult))
1197                 return (true);
1198
1199         malloc_mutex_lock(&arena->lock);
1200         arena->lg_dirty_mult = lg_dirty_mult;
1201         arena_maybe_purge(arena);
1202         malloc_mutex_unlock(&arena->lock);
1203
1204         return (false);
1205 }
1206
1207 void
1208 arena_maybe_purge(arena_t *arena)
1209 {
1210
1211         /* Don't purge if the option is disabled. */
1212         if (arena->lg_dirty_mult < 0)
1213                 return;
1214         /* Don't recursively purge. */
1215         if (arena->purging)
1216                 return;
1217         /*
1218          * Iterate, since preventing recursive purging could otherwise leave too
1219          * many dirty pages.
1220          */
1221         while (true) {
1222                 size_t threshold = (arena->nactive >> arena->lg_dirty_mult);
1223                 if (threshold < chunk_npages)
1224                         threshold = chunk_npages;
1225                 /*
1226                  * Don't purge unless the number of purgeable pages exceeds the
1227                  * threshold.
1228                  */
1229                 if (arena->ndirty <= threshold)
1230                         return;
1231                 arena_purge(arena, false);
1232         }
1233 }
1234
1235 static size_t
1236 arena_dirty_count(arena_t *arena)
1237 {
1238         size_t ndirty = 0;
1239         arena_runs_dirty_link_t *rdelm;
1240         extent_node_t *chunkselm;
1241
1242         for (rdelm = qr_next(&arena->runs_dirty, rd_link),
1243             chunkselm = qr_next(&arena->chunks_cache, cc_link);
1244             rdelm != &arena->runs_dirty; rdelm = qr_next(rdelm, rd_link)) {
1245                 size_t npages;
1246
1247                 if (rdelm == &chunkselm->rd) {
1248                         npages = extent_node_size_get(chunkselm) >> LG_PAGE;
1249                         chunkselm = qr_next(chunkselm, cc_link);
1250                 } else {
1251                         arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(
1252                             rdelm);
1253                         arena_chunk_map_misc_t *miscelm =
1254                             arena_rd_to_miscelm(rdelm);
1255                         size_t pageind = arena_miscelm_to_pageind(miscelm);
1256                         assert(arena_mapbits_allocated_get(chunk, pageind) ==
1257                             0);
1258                         assert(arena_mapbits_large_get(chunk, pageind) == 0);
1259                         assert(arena_mapbits_dirty_get(chunk, pageind) != 0);
1260                         npages = arena_mapbits_unallocated_size_get(chunk,
1261                             pageind) >> LG_PAGE;
1262                 }
1263                 ndirty += npages;
1264         }
1265
1266         return (ndirty);
1267 }
1268
1269 static size_t
1270 arena_compute_npurge(arena_t *arena, bool all)
1271 {
1272         size_t npurge;
1273
1274         /*
1275          * Compute the minimum number of pages that this thread should try to
1276          * purge.
1277          */
1278         if (!all) {
1279                 size_t threshold = (arena->nactive >> arena->lg_dirty_mult);
1280                 threshold = threshold < chunk_npages ? chunk_npages : threshold;
1281
1282                 npurge = arena->ndirty - threshold;
1283         } else
1284                 npurge = arena->ndirty;
1285
1286         return (npurge);
1287 }
1288
1289 static size_t
1290 arena_stash_dirty(arena_t *arena, chunk_hooks_t *chunk_hooks, bool all,
1291     size_t npurge, arena_runs_dirty_link_t *purge_runs_sentinel,
1292     extent_node_t *purge_chunks_sentinel)
1293 {
1294         arena_runs_dirty_link_t *rdelm, *rdelm_next;
1295         extent_node_t *chunkselm;
1296         size_t nstashed = 0;
1297
1298         /* Stash at least npurge pages. */
1299         for (rdelm = qr_next(&arena->runs_dirty, rd_link),
1300             chunkselm = qr_next(&arena->chunks_cache, cc_link);
1301             rdelm != &arena->runs_dirty; rdelm = rdelm_next) {
1302                 size_t npages;
1303                 rdelm_next = qr_next(rdelm, rd_link);
1304
1305                 if (rdelm == &chunkselm->rd) {
1306                         extent_node_t *chunkselm_next;
1307                         bool zero;
1308                         UNUSED void *chunk;
1309
1310                         chunkselm_next = qr_next(chunkselm, cc_link);
1311                         /*
1312                          * Allocate.  chunkselm remains valid due to the
1313                          * dalloc_node=false argument to chunk_alloc_cache().
1314                          */
1315                         zero = false;
1316                         chunk = chunk_alloc_cache(arena, chunk_hooks,
1317                             extent_node_addr_get(chunkselm),
1318                             extent_node_size_get(chunkselm), chunksize, &zero,
1319                             false);
1320                         assert(chunk == extent_node_addr_get(chunkselm));
1321                         assert(zero == extent_node_zeroed_get(chunkselm));
1322                         extent_node_dirty_insert(chunkselm, purge_runs_sentinel,
1323                             purge_chunks_sentinel);
1324                         npages = extent_node_size_get(chunkselm) >> LG_PAGE;
1325                         chunkselm = chunkselm_next;
1326                 } else {
1327                         arena_chunk_t *chunk =
1328                             (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1329                         arena_chunk_map_misc_t *miscelm =
1330                             arena_rd_to_miscelm(rdelm);
1331                         size_t pageind = arena_miscelm_to_pageind(miscelm);
1332                         arena_run_t *run = &miscelm->run;
1333                         size_t run_size =
1334                             arena_mapbits_unallocated_size_get(chunk, pageind);
1335
1336                         npages = run_size >> LG_PAGE;
1337
1338                         assert(pageind + npages <= chunk_npages);
1339                         assert(arena_mapbits_dirty_get(chunk, pageind) ==
1340                             arena_mapbits_dirty_get(chunk, pageind+npages-1));
1341
1342                         /*
1343                          * If purging the spare chunk's run, make it available
1344                          * prior to allocation.
1345                          */
1346                         if (chunk == arena->spare)
1347                                 arena_chunk_alloc(arena);
1348
1349                         /* Temporarily allocate the free dirty run. */
1350                         arena_run_split_large(arena, run, run_size, false);
1351                         /* Stash. */
1352                         if (false)
1353                                 qr_new(rdelm, rd_link); /* Redundant. */
1354                         else {
1355                                 assert(qr_next(rdelm, rd_link) == rdelm);
1356                                 assert(qr_prev(rdelm, rd_link) == rdelm);
1357                         }
1358                         qr_meld(purge_runs_sentinel, rdelm, rd_link);
1359                 }
1360
1361                 nstashed += npages;
1362                 if (!all && nstashed >= npurge)
1363                         break;
1364         }
1365
1366         return (nstashed);
1367 }
1368
1369 static size_t
1370 arena_purge_stashed(arena_t *arena, chunk_hooks_t *chunk_hooks,
1371     arena_runs_dirty_link_t *purge_runs_sentinel,
1372     extent_node_t *purge_chunks_sentinel)
1373 {
1374         size_t npurged, nmadvise;
1375         arena_runs_dirty_link_t *rdelm;
1376         extent_node_t *chunkselm;
1377
1378         if (config_stats)
1379                 nmadvise = 0;
1380         npurged = 0;
1381
1382         malloc_mutex_unlock(&arena->lock);
1383         for (rdelm = qr_next(purge_runs_sentinel, rd_link),
1384             chunkselm = qr_next(purge_chunks_sentinel, cc_link);
1385             rdelm != purge_runs_sentinel; rdelm = qr_next(rdelm, rd_link)) {
1386                 size_t npages;
1387
1388                 if (rdelm == &chunkselm->rd) {
1389                         /*
1390                          * Don't actually purge the chunk here because 1)
1391                          * chunkselm is embedded in the chunk and must remain
1392                          * valid, and 2) we deallocate the chunk in
1393                          * arena_unstash_purged(), where it is destroyed,
1394                          * decommitted, or purged, depending on chunk
1395                          * deallocation policy.
1396                          */
1397                         size_t size = extent_node_size_get(chunkselm);
1398                         npages = size >> LG_PAGE;
1399                         chunkselm = qr_next(chunkselm, cc_link);
1400                 } else {
1401                         size_t pageind, run_size, flag_unzeroed, flags, i;
1402                         bool decommitted;
1403                         arena_chunk_t *chunk =
1404                             (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1405                         arena_chunk_map_misc_t *miscelm =
1406                             arena_rd_to_miscelm(rdelm);
1407                         pageind = arena_miscelm_to_pageind(miscelm);
1408                         run_size = arena_mapbits_large_size_get(chunk, pageind);
1409                         npages = run_size >> LG_PAGE;
1410
1411                         assert(pageind + npages <= chunk_npages);
1412                         assert(!arena_mapbits_decommitted_get(chunk, pageind));
1413                         assert(!arena_mapbits_decommitted_get(chunk,
1414                             pageind+npages-1));
1415                         decommitted = !chunk_hooks->decommit(chunk, chunksize,
1416                             pageind << LG_PAGE, npages << LG_PAGE, arena->ind);
1417                         if (decommitted) {
1418                                 flag_unzeroed = 0;
1419                                 flags = CHUNK_MAP_DECOMMITTED;
1420                         } else {
1421                                 flag_unzeroed = chunk_purge_wrapper(arena,
1422                                     chunk_hooks, chunk, chunksize, pageind <<
1423                                     LG_PAGE, run_size) ? CHUNK_MAP_UNZEROED : 0;
1424                                 flags = flag_unzeroed;
1425                         }
1426                         arena_mapbits_large_set(chunk, pageind+npages-1, 0,
1427                             flags);
1428                         arena_mapbits_large_set(chunk, pageind, run_size,
1429                             flags);
1430
1431                         /*
1432                          * Set the unzeroed flag for internal pages, now that
1433                          * chunk_purge_wrapper() has returned whether the pages
1434                          * were zeroed as a side effect of purging.  This chunk
1435                          * map modification is safe even though the arena mutex
1436                          * isn't currently owned by this thread, because the run
1437                          * is marked as allocated, thus protecting it from being
1438                          * modified by any other thread.  As long as these
1439                          * writes don't perturb the first and last elements'
1440                          * CHUNK_MAP_ALLOCATED bits, behavior is well defined.
1441                          */
1442                         for (i = 1; i < npages-1; i++) {
1443                                 arena_mapbits_internal_set(chunk, pageind+i,
1444                                     flag_unzeroed);
1445                         }
1446                 }
1447
1448                 npurged += npages;
1449                 if (config_stats)
1450                         nmadvise++;
1451         }
1452         malloc_mutex_lock(&arena->lock);
1453
1454         if (config_stats) {
1455                 arena->stats.nmadvise += nmadvise;
1456                 arena->stats.purged += npurged;
1457         }
1458
1459         return (npurged);
1460 }
1461
1462 static void
1463 arena_unstash_purged(arena_t *arena, chunk_hooks_t *chunk_hooks,
1464     arena_runs_dirty_link_t *purge_runs_sentinel,
1465     extent_node_t *purge_chunks_sentinel)
1466 {
1467         arena_runs_dirty_link_t *rdelm, *rdelm_next;
1468         extent_node_t *chunkselm;
1469
1470         /* Deallocate chunks/runs. */
1471         for (rdelm = qr_next(purge_runs_sentinel, rd_link),
1472             chunkselm = qr_next(purge_chunks_sentinel, cc_link);
1473             rdelm != purge_runs_sentinel; rdelm = rdelm_next) {
1474                 rdelm_next = qr_next(rdelm, rd_link);
1475                 if (rdelm == &chunkselm->rd) {
1476                         extent_node_t *chunkselm_next = qr_next(chunkselm,
1477                             cc_link);
1478                         void *addr = extent_node_addr_get(chunkselm);
1479                         size_t size = extent_node_size_get(chunkselm);
1480                         bool zeroed = extent_node_zeroed_get(chunkselm);
1481                         bool committed = extent_node_committed_get(chunkselm);
1482                         extent_node_dirty_remove(chunkselm);
1483                         arena_node_dalloc(arena, chunkselm);
1484                         chunkselm = chunkselm_next;
1485                         chunk_dalloc_arena(arena, chunk_hooks, addr, size,
1486                             zeroed, committed);
1487                 } else {
1488                         arena_chunk_t *chunk =
1489                             (arena_chunk_t *)CHUNK_ADDR2BASE(rdelm);
1490                         arena_chunk_map_misc_t *miscelm =
1491                             arena_rd_to_miscelm(rdelm);
1492                         size_t pageind = arena_miscelm_to_pageind(miscelm);
1493                         bool decommitted = (arena_mapbits_decommitted_get(chunk,
1494                             pageind) != 0);
1495                         arena_run_t *run = &miscelm->run;
1496                         qr_remove(rdelm, rd_link);
1497                         arena_run_dalloc(arena, run, false, true, decommitted);
1498                 }
1499         }
1500 }
1501
1502 static void
1503 arena_purge(arena_t *arena, bool all)
1504 {
1505         chunk_hooks_t chunk_hooks = chunk_hooks_get(arena);
1506         size_t npurge, npurgeable, npurged;
1507         arena_runs_dirty_link_t purge_runs_sentinel;
1508         extent_node_t purge_chunks_sentinel;
1509
1510         arena->purging = true;
1511
1512         /*
1513          * Calls to arena_dirty_count() are disabled even for debug builds
1514          * because overhead grows nonlinearly as memory usage increases.
1515          */
1516         if (false && config_debug) {
1517                 size_t ndirty = arena_dirty_count(arena);
1518                 assert(ndirty == arena->ndirty);
1519         }
1520         assert((arena->nactive >> arena->lg_dirty_mult) < arena->ndirty || all);
1521
1522         if (config_stats)
1523                 arena->stats.npurge++;
1524
1525         npurge = arena_compute_npurge(arena, all);
1526         qr_new(&purge_runs_sentinel, rd_link);
1527         extent_node_dirty_linkage_init(&purge_chunks_sentinel);
1528
1529         npurgeable = arena_stash_dirty(arena, &chunk_hooks, all, npurge,
1530             &purge_runs_sentinel, &purge_chunks_sentinel);
1531         assert(npurgeable >= npurge);
1532         npurged = arena_purge_stashed(arena, &chunk_hooks, &purge_runs_sentinel,
1533             &purge_chunks_sentinel);
1534         assert(npurged == npurgeable);
1535         arena_unstash_purged(arena, &chunk_hooks, &purge_runs_sentinel,
1536             &purge_chunks_sentinel);
1537
1538         arena->purging = false;
1539 }
1540
1541 void
1542 arena_purge_all(arena_t *arena)
1543 {
1544
1545         malloc_mutex_lock(&arena->lock);
1546         arena_purge(arena, true);
1547         malloc_mutex_unlock(&arena->lock);
1548 }
1549
1550 static void
1551 arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size,
1552     size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty,
1553     size_t flag_decommitted)
1554 {
1555         size_t size = *p_size;
1556         size_t run_ind = *p_run_ind;
1557         size_t run_pages = *p_run_pages;
1558
1559         /* Try to coalesce forward. */
1560         if (run_ind + run_pages < chunk_npages &&
1561             arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 &&
1562             arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty &&
1563             arena_mapbits_decommitted_get(chunk, run_ind+run_pages) ==
1564             flag_decommitted) {
1565                 size_t nrun_size = arena_mapbits_unallocated_size_get(chunk,
1566                     run_ind+run_pages);
1567                 size_t nrun_pages = nrun_size >> LG_PAGE;
1568
1569                 /*
1570                  * Remove successor from runs_avail; the coalesced run is
1571                  * inserted later.
1572                  */
1573                 assert(arena_mapbits_unallocated_size_get(chunk,
1574                     run_ind+run_pages+nrun_pages-1) == nrun_size);
1575                 assert(arena_mapbits_dirty_get(chunk,
1576                     run_ind+run_pages+nrun_pages-1) == flag_dirty);
1577                 assert(arena_mapbits_decommitted_get(chunk,
1578                     run_ind+run_pages+nrun_pages-1) == flag_decommitted);
1579                 arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages);
1580
1581                 /*
1582                  * If the successor is dirty, remove it from the set of dirty
1583                  * pages.
1584                  */
1585                 if (flag_dirty != 0) {
1586                         arena_run_dirty_remove(arena, chunk, run_ind+run_pages,
1587                             nrun_pages);
1588                 }
1589
1590                 size += nrun_size;
1591                 run_pages += nrun_pages;
1592
1593                 arena_mapbits_unallocated_size_set(chunk, run_ind, size);
1594                 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
1595                     size);
1596         }
1597
1598         /* Try to coalesce backward. */
1599         if (run_ind > map_bias && arena_mapbits_allocated_get(chunk,
1600             run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) ==
1601             flag_dirty && arena_mapbits_decommitted_get(chunk, run_ind-1) ==
1602             flag_decommitted) {
1603                 size_t prun_size = arena_mapbits_unallocated_size_get(chunk,
1604                     run_ind-1);
1605                 size_t prun_pages = prun_size >> LG_PAGE;
1606
1607                 run_ind -= prun_pages;
1608
1609                 /*
1610                  * Remove predecessor from runs_avail; the coalesced run is
1611                  * inserted later.
1612                  */
1613                 assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
1614                     prun_size);
1615                 assert(arena_mapbits_dirty_get(chunk, run_ind) == flag_dirty);
1616                 assert(arena_mapbits_decommitted_get(chunk, run_ind) ==
1617                     flag_decommitted);
1618                 arena_avail_remove(arena, chunk, run_ind, prun_pages);
1619
1620                 /*
1621                  * If the predecessor is dirty, remove it from the set of dirty
1622                  * pages.
1623                  */
1624                 if (flag_dirty != 0) {
1625                         arena_run_dirty_remove(arena, chunk, run_ind,
1626                             prun_pages);
1627                 }
1628
1629                 size += prun_size;
1630                 run_pages += prun_pages;
1631
1632                 arena_mapbits_unallocated_size_set(chunk, run_ind, size);
1633                 arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1,
1634                     size);
1635         }
1636
1637         *p_size = size;
1638         *p_run_ind = run_ind;
1639         *p_run_pages = run_pages;
1640 }
1641
1642 static size_t
1643 arena_run_size_get(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
1644     size_t run_ind)
1645 {
1646         size_t size;
1647
1648         assert(run_ind >= map_bias);
1649         assert(run_ind < chunk_npages);
1650
1651         if (arena_mapbits_large_get(chunk, run_ind) != 0) {
1652                 size = arena_mapbits_large_size_get(chunk, run_ind);
1653                 assert(size == PAGE || arena_mapbits_large_size_get(chunk,
1654                     run_ind+(size>>LG_PAGE)-1) == 0);
1655         } else {
1656                 arena_bin_info_t *bin_info = &arena_bin_info[run->binind];
1657                 size = bin_info->run_size;
1658         }
1659
1660         return (size);
1661 }
1662
1663 static bool
1664 arena_run_decommit(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run)
1665 {
1666         arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1667         size_t run_ind = arena_miscelm_to_pageind(miscelm);
1668         size_t offset = run_ind << LG_PAGE;
1669         size_t length = arena_run_size_get(arena, chunk, run, run_ind);
1670
1671         return (arena->chunk_hooks.decommit(chunk, chunksize, offset, length,
1672             arena->ind));
1673 }
1674
1675 static void
1676 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned,
1677     bool decommitted)
1678 {
1679         arena_chunk_t *chunk;
1680         arena_chunk_map_misc_t *miscelm;
1681         size_t size, run_ind, run_pages, flag_dirty, flag_decommitted;
1682
1683         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1684         miscelm = arena_run_to_miscelm(run);
1685         run_ind = arena_miscelm_to_pageind(miscelm);
1686         assert(run_ind >= map_bias);
1687         assert(run_ind < chunk_npages);
1688         size = arena_run_size_get(arena, chunk, run, run_ind);
1689         run_pages = (size >> LG_PAGE);
1690         arena_cactive_update(arena, 0, run_pages);
1691         arena->nactive -= run_pages;
1692
1693         /*
1694          * The run is dirty if the caller claims to have dirtied it, as well as
1695          * if it was already dirty before being allocated and the caller
1696          * doesn't claim to have cleaned it.
1697          */
1698         assert(arena_mapbits_dirty_get(chunk, run_ind) ==
1699             arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
1700         if (!cleaned && !decommitted && arena_mapbits_dirty_get(chunk, run_ind)
1701             != 0)
1702                 dirty = true;
1703         flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0;
1704         flag_decommitted = decommitted ? CHUNK_MAP_DECOMMITTED : 0;
1705
1706         /* Mark pages as unallocated in the chunk map. */
1707         if (dirty || decommitted) {
1708                 size_t flags = flag_dirty | flag_decommitted;
1709                 arena_mapbits_unallocated_set(chunk, run_ind, size, flags);
1710                 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
1711                     flags);
1712         } else {
1713                 arena_mapbits_unallocated_set(chunk, run_ind, size,
1714                     arena_mapbits_unzeroed_get(chunk, run_ind));
1715                 arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
1716                     arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1));
1717         }
1718
1719         arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages,
1720             flag_dirty, flag_decommitted);
1721
1722         /* Insert into runs_avail, now that coalescing is complete. */
1723         assert(arena_mapbits_unallocated_size_get(chunk, run_ind) ==
1724             arena_mapbits_unallocated_size_get(chunk, run_ind+run_pages-1));
1725         assert(arena_mapbits_dirty_get(chunk, run_ind) ==
1726             arena_mapbits_dirty_get(chunk, run_ind+run_pages-1));
1727         assert(arena_mapbits_decommitted_get(chunk, run_ind) ==
1728             arena_mapbits_decommitted_get(chunk, run_ind+run_pages-1));
1729         arena_avail_insert(arena, chunk, run_ind, run_pages);
1730
1731         if (dirty)
1732                 arena_run_dirty_insert(arena, chunk, run_ind, run_pages);
1733
1734         /* Deallocate chunk if it is now completely unused. */
1735         if (size == arena_maxrun) {
1736                 assert(run_ind == map_bias);
1737                 assert(run_pages == (arena_maxrun >> LG_PAGE));
1738                 arena_chunk_dalloc(arena, chunk);
1739         }
1740
1741         /*
1742          * It is okay to do dirty page processing here even if the chunk was
1743          * deallocated above, since in that case it is the spare.  Waiting
1744          * until after possible chunk deallocation to do dirty processing
1745          * allows for an old spare to be fully deallocated, thus decreasing the
1746          * chances of spuriously crossing the dirty page purging threshold.
1747          */
1748         if (dirty)
1749                 arena_maybe_purge(arena);
1750 }
1751
1752 static void
1753 arena_run_dalloc_decommit(arena_t *arena, arena_chunk_t *chunk,
1754     arena_run_t *run)
1755 {
1756         bool committed = arena_run_decommit(arena, chunk, run);
1757
1758         arena_run_dalloc(arena, run, committed, false, !committed);
1759 }
1760
1761 static void
1762 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
1763     size_t oldsize, size_t newsize)
1764 {
1765         arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1766         size_t pageind = arena_miscelm_to_pageind(miscelm);
1767         size_t head_npages = (oldsize - newsize) >> LG_PAGE;
1768         size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
1769         size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind);
1770         size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
1771             CHUNK_MAP_UNZEROED : 0;
1772
1773         assert(oldsize > newsize);
1774
1775         /*
1776          * Update the chunk map so that arena_run_dalloc() can treat the
1777          * leading run as separately allocated.  Set the last element of each
1778          * run first, in case of single-page runs.
1779          */
1780         assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
1781         arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty |
1782             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
1783             pageind+head_npages-1)));
1784         arena_mapbits_large_set(chunk, pageind, oldsize-newsize, flag_dirty |
1785             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind)));
1786
1787         if (config_debug) {
1788                 UNUSED size_t tail_npages = newsize >> LG_PAGE;
1789                 assert(arena_mapbits_large_size_get(chunk,
1790                     pageind+head_npages+tail_npages-1) == 0);
1791                 assert(arena_mapbits_dirty_get(chunk,
1792                     pageind+head_npages+tail_npages-1) == flag_dirty);
1793         }
1794         arena_mapbits_large_set(chunk, pageind+head_npages, newsize,
1795             flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
1796             pageind+head_npages)));
1797
1798         arena_run_dalloc(arena, run, false, false, (flag_decommitted != 0));
1799 }
1800
1801 static void
1802 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
1803     size_t oldsize, size_t newsize, bool dirty)
1804 {
1805         arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1806         size_t pageind = arena_miscelm_to_pageind(miscelm);
1807         size_t head_npages = newsize >> LG_PAGE;
1808         size_t flag_dirty = arena_mapbits_dirty_get(chunk, pageind);
1809         size_t flag_decommitted = arena_mapbits_decommitted_get(chunk, pageind);
1810         size_t flag_unzeroed_mask = (flag_dirty | flag_decommitted) == 0 ?
1811             CHUNK_MAP_UNZEROED : 0;
1812         arena_chunk_map_misc_t *tail_miscelm;
1813         arena_run_t *tail_run;
1814
1815         assert(oldsize > newsize);
1816
1817         /*
1818          * Update the chunk map so that arena_run_dalloc() can treat the
1819          * trailing run as separately allocated.  Set the last element of each
1820          * run first, in case of single-page runs.
1821          */
1822         assert(arena_mapbits_large_size_get(chunk, pageind) == oldsize);
1823         arena_mapbits_large_set(chunk, pageind+head_npages-1, 0, flag_dirty |
1824             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
1825             pageind+head_npages-1)));
1826         arena_mapbits_large_set(chunk, pageind, newsize, flag_dirty |
1827             (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk, pageind)));
1828
1829         if (config_debug) {
1830                 UNUSED size_t tail_npages = (oldsize - newsize) >> LG_PAGE;
1831                 assert(arena_mapbits_large_size_get(chunk,
1832                     pageind+head_npages+tail_npages-1) == 0);
1833                 assert(arena_mapbits_dirty_get(chunk,
1834                     pageind+head_npages+tail_npages-1) == flag_dirty);
1835         }
1836         arena_mapbits_large_set(chunk, pageind+head_npages, oldsize-newsize,
1837             flag_dirty | (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
1838             pageind+head_npages)));
1839
1840         tail_miscelm = arena_miscelm_get(chunk, pageind + head_npages);
1841         tail_run = &tail_miscelm->run;
1842         arena_run_dalloc(arena, tail_run, dirty, false, (flag_decommitted !=
1843             0));
1844 }
1845
1846 static arena_run_t *
1847 arena_bin_runs_first(arena_bin_t *bin)
1848 {
1849         arena_chunk_map_misc_t *miscelm = arena_run_tree_first(&bin->runs);
1850         if (miscelm != NULL)
1851                 return (&miscelm->run);
1852
1853         return (NULL);
1854 }
1855
1856 static void
1857 arena_bin_runs_insert(arena_bin_t *bin, arena_run_t *run)
1858 {
1859         arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1860
1861         assert(arena_run_tree_search(&bin->runs, miscelm) == NULL);
1862
1863         arena_run_tree_insert(&bin->runs, miscelm);
1864 }
1865
1866 static void
1867 arena_bin_runs_remove(arena_bin_t *bin, arena_run_t *run)
1868 {
1869         arena_chunk_map_misc_t *miscelm = arena_run_to_miscelm(run);
1870
1871         assert(arena_run_tree_search(&bin->runs, miscelm) != NULL);
1872
1873         arena_run_tree_remove(&bin->runs, miscelm);
1874 }
1875
1876 static arena_run_t *
1877 arena_bin_nonfull_run_tryget(arena_bin_t *bin)
1878 {
1879         arena_run_t *run = arena_bin_runs_first(bin);
1880         if (run != NULL) {
1881                 arena_bin_runs_remove(bin, run);
1882                 if (config_stats)
1883                         bin->stats.reruns++;
1884         }
1885         return (run);
1886 }
1887
1888 static arena_run_t *
1889 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
1890 {
1891         arena_run_t *run;
1892         szind_t binind;
1893         arena_bin_info_t *bin_info;
1894
1895         /* Look for a usable run. */
1896         run = arena_bin_nonfull_run_tryget(bin);
1897         if (run != NULL)
1898                 return (run);
1899         /* No existing runs have any space available. */
1900
1901         binind = arena_bin_index(arena, bin);
1902         bin_info = &arena_bin_info[binind];
1903
1904         /* Allocate a new run. */
1905         malloc_mutex_unlock(&bin->lock);
1906         /******************************/
1907         malloc_mutex_lock(&arena->lock);
1908         run = arena_run_alloc_small(arena, bin_info->run_size, binind);
1909         if (run != NULL) {
1910                 /* Initialize run internals. */
1911                 run->binind = binind;
1912                 run->nfree = bin_info->nregs;
1913                 bitmap_init(run->bitmap, &bin_info->bitmap_info);
1914         }
1915         malloc_mutex_unlock(&arena->lock);
1916         /********************************/
1917         malloc_mutex_lock(&bin->lock);
1918         if (run != NULL) {
1919                 if (config_stats) {
1920                         bin->stats.nruns++;
1921                         bin->stats.curruns++;
1922                 }
1923                 return (run);
1924         }
1925
1926         /*
1927          * arena_run_alloc_small() failed, but another thread may have made
1928          * sufficient memory available while this one dropped bin->lock above,
1929          * so search one more time.
1930          */
1931         run = arena_bin_nonfull_run_tryget(bin);
1932         if (run != NULL)
1933                 return (run);
1934
1935         return (NULL);
1936 }
1937
1938 /* Re-fill bin->runcur, then call arena_run_reg_alloc(). */
1939 static void *
1940 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
1941 {
1942         szind_t binind;
1943         arena_bin_info_t *bin_info;
1944         arena_run_t *run;
1945
1946         binind = arena_bin_index(arena, bin);
1947         bin_info = &arena_bin_info[binind];
1948         bin->runcur = NULL;
1949         run = arena_bin_nonfull_run_get(arena, bin);
1950         if (bin->runcur != NULL && bin->runcur->nfree > 0) {
1951                 /*
1952                  * Another thread updated runcur while this one ran without the
1953                  * bin lock in arena_bin_nonfull_run_get().
1954                  */
1955                 void *ret;
1956                 assert(bin->runcur->nfree > 0);
1957                 ret = arena_run_reg_alloc(bin->runcur, bin_info);
1958                 if (run != NULL) {
1959                         arena_chunk_t *chunk;
1960
1961                         /*
1962                          * arena_run_alloc_small() may have allocated run, or
1963                          * it may have pulled run from the bin's run tree.
1964                          * Therefore it is unsafe to make any assumptions about
1965                          * how run has previously been used, and
1966                          * arena_bin_lower_run() must be called, as if a region
1967                          * were just deallocated from the run.
1968                          */
1969                         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1970                         if (run->nfree == bin_info->nregs)
1971                                 arena_dalloc_bin_run(arena, chunk, run, bin);
1972                         else
1973                                 arena_bin_lower_run(arena, chunk, run, bin);
1974                 }
1975                 return (ret);
1976         }
1977
1978         if (run == NULL)
1979                 return (NULL);
1980
1981         bin->runcur = run;
1982
1983         assert(bin->runcur->nfree > 0);
1984
1985         return (arena_run_reg_alloc(bin->runcur, bin_info));
1986 }
1987
1988 void
1989 arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, szind_t binind,
1990     uint64_t prof_accumbytes)
1991 {
1992         unsigned i, nfill;
1993         arena_bin_t *bin;
1994
1995         assert(tbin->ncached == 0);
1996
1997         if (config_prof && arena_prof_accum(arena, prof_accumbytes))
1998                 prof_idump();
1999         bin = &arena->bins[binind];
2000         malloc_mutex_lock(&bin->lock);
2001         for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >>
2002             tbin->lg_fill_div); i < nfill; i++) {
2003                 arena_run_t *run;
2004                 void *ptr;
2005                 if ((run = bin->runcur) != NULL && run->nfree > 0)
2006                         ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]);
2007                 else
2008                         ptr = arena_bin_malloc_hard(arena, bin);
2009                 if (ptr == NULL) {
2010                         /*
2011                          * OOM.  tbin->avail isn't yet filled down to its first
2012                          * element, so the successful allocations (if any) must
2013                          * be moved to the base of tbin->avail before bailing
2014                          * out.
2015                          */
2016                         if (i > 0) {
2017                                 memmove(tbin->avail, &tbin->avail[nfill - i],
2018                                     i * sizeof(void *));
2019                         }
2020                         break;
2021                 }
2022                 if (config_fill && unlikely(opt_junk_alloc)) {
2023                         arena_alloc_junk_small(ptr, &arena_bin_info[binind],
2024                             true);
2025                 }
2026                 /* Insert such that low regions get used first. */
2027                 tbin->avail[nfill - 1 - i] = ptr;
2028         }
2029         if (config_stats) {
2030                 bin->stats.nmalloc += i;
2031                 bin->stats.nrequests += tbin->tstats.nrequests;
2032                 bin->stats.curregs += i;
2033                 bin->stats.nfills++;
2034                 tbin->tstats.nrequests = 0;
2035         }
2036         malloc_mutex_unlock(&bin->lock);
2037         tbin->ncached = i;
2038 }
2039
2040 void
2041 arena_alloc_junk_small(void *ptr, arena_bin_info_t *bin_info, bool zero)
2042 {
2043
2044         if (zero) {
2045                 size_t redzone_size = bin_info->redzone_size;
2046                 memset((void *)((uintptr_t)ptr - redzone_size), 0xa5,
2047                     redzone_size);
2048                 memset((void *)((uintptr_t)ptr + bin_info->reg_size), 0xa5,
2049                     redzone_size);
2050         } else {
2051                 memset((void *)((uintptr_t)ptr - bin_info->redzone_size), 0xa5,
2052                     bin_info->reg_interval);
2053         }
2054 }
2055
2056 #ifdef JEMALLOC_JET
2057 #undef arena_redzone_corruption
2058 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption_impl)
2059 #endif
2060 static void
2061 arena_redzone_corruption(void *ptr, size_t usize, bool after,
2062     size_t offset, uint8_t byte)
2063 {
2064
2065         malloc_printf("<jemalloc>: Corrupt redzone %zu byte%s %s %p "
2066             "(size %zu), byte=%#x\n", offset, (offset == 1) ? "" : "s",
2067             after ? "after" : "before", ptr, usize, byte);
2068 }
2069 #ifdef JEMALLOC_JET
2070 #undef arena_redzone_corruption
2071 #define arena_redzone_corruption JEMALLOC_N(arena_redzone_corruption)
2072 arena_redzone_corruption_t *arena_redzone_corruption =
2073     JEMALLOC_N(arena_redzone_corruption_impl);
2074 #endif
2075
2076 static void
2077 arena_redzones_validate(void *ptr, arena_bin_info_t *bin_info, bool reset)
2078 {
2079         bool error = false;
2080
2081         if (opt_junk_alloc) {
2082                 size_t size = bin_info->reg_size;
2083                 size_t redzone_size = bin_info->redzone_size;
2084                 size_t i;
2085
2086                 for (i = 1; i <= redzone_size; i++) {
2087                         uint8_t *byte = (uint8_t *)((uintptr_t)ptr - i);
2088                         if (*byte != 0xa5) {
2089                                 error = true;
2090                                 arena_redzone_corruption(ptr, size, false, i,
2091                                     *byte);
2092                                 if (reset)
2093                                         *byte = 0xa5;
2094                         }
2095                 }
2096                 for (i = 0; i < redzone_size; i++) {
2097                         uint8_t *byte = (uint8_t *)((uintptr_t)ptr + size + i);
2098                         if (*byte != 0xa5) {
2099                                 error = true;
2100                                 arena_redzone_corruption(ptr, size, true, i,
2101                                     *byte);
2102                                 if (reset)
2103                                         *byte = 0xa5;
2104                         }
2105                 }
2106         }
2107
2108         if (opt_abort && error)
2109                 abort();
2110 }
2111
2112 #ifdef JEMALLOC_JET
2113 #undef arena_dalloc_junk_small
2114 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small_impl)
2115 #endif
2116 void
2117 arena_dalloc_junk_small(void *ptr, arena_bin_info_t *bin_info)
2118 {
2119         size_t redzone_size = bin_info->redzone_size;
2120
2121         arena_redzones_validate(ptr, bin_info, false);
2122         memset((void *)((uintptr_t)ptr - redzone_size), 0x5a,
2123             bin_info->reg_interval);
2124 }
2125 #ifdef JEMALLOC_JET
2126 #undef arena_dalloc_junk_small
2127 #define arena_dalloc_junk_small JEMALLOC_N(arena_dalloc_junk_small)
2128 arena_dalloc_junk_small_t *arena_dalloc_junk_small =
2129     JEMALLOC_N(arena_dalloc_junk_small_impl);
2130 #endif
2131
2132 void
2133 arena_quarantine_junk_small(void *ptr, size_t usize)
2134 {
2135         szind_t binind;
2136         arena_bin_info_t *bin_info;
2137         cassert(config_fill);
2138         assert(opt_junk_free);
2139         assert(opt_quarantine);
2140         assert(usize <= SMALL_MAXCLASS);
2141
2142         binind = size2index(usize);
2143         bin_info = &arena_bin_info[binind];
2144         arena_redzones_validate(ptr, bin_info, true);
2145 }
2146
2147 void *
2148 arena_malloc_small(arena_t *arena, size_t size, bool zero)
2149 {
2150         void *ret;
2151         arena_bin_t *bin;
2152         arena_run_t *run;
2153         szind_t binind;
2154
2155         binind = size2index(size);
2156         assert(binind < NBINS);
2157         bin = &arena->bins[binind];
2158         size = index2size(binind);
2159
2160         malloc_mutex_lock(&bin->lock);
2161         if ((run = bin->runcur) != NULL && run->nfree > 0)
2162                 ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
2163         else
2164                 ret = arena_bin_malloc_hard(arena, bin);
2165
2166         if (ret == NULL) {
2167                 malloc_mutex_unlock(&bin->lock);
2168                 return (NULL);
2169         }
2170
2171         if (config_stats) {
2172                 bin->stats.nmalloc++;
2173                 bin->stats.nrequests++;
2174                 bin->stats.curregs++;
2175         }
2176         malloc_mutex_unlock(&bin->lock);
2177         if (config_prof && !isthreaded && arena_prof_accum(arena, size))
2178                 prof_idump();
2179
2180         if (!zero) {
2181                 if (config_fill) {
2182                         if (unlikely(opt_junk_alloc)) {
2183                                 arena_alloc_junk_small(ret,
2184                                     &arena_bin_info[binind], false);
2185                         } else if (unlikely(opt_zero))
2186                                 memset(ret, 0, size);
2187                 }
2188                 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
2189         } else {
2190                 if (config_fill && unlikely(opt_junk_alloc)) {
2191                         arena_alloc_junk_small(ret, &arena_bin_info[binind],
2192                             true);
2193                 }
2194                 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
2195                 memset(ret, 0, size);
2196         }
2197
2198         return (ret);
2199 }
2200
2201 void *
2202 arena_malloc_large(arena_t *arena, size_t size, bool zero)
2203 {
2204         void *ret;
2205         size_t usize;
2206         uintptr_t random_offset;
2207         arena_run_t *run;
2208         arena_chunk_map_misc_t *miscelm;
2209         UNUSED bool idump;
2210
2211         /* Large allocation. */
2212         usize = s2u(size);
2213         malloc_mutex_lock(&arena->lock);
2214         if (config_cache_oblivious) {
2215                 uint64_t r;
2216
2217                 /*
2218                  * Compute a uniformly distributed offset within the first page
2219                  * that is a multiple of the cacheline size, e.g. [0 .. 63) * 64
2220                  * for 4 KiB pages and 64-byte cachelines.
2221                  */
2222                 prng64(r, LG_PAGE - LG_CACHELINE, arena->offset_state,
2223                     UINT64_C(6364136223846793009),
2224                     UINT64_C(1442695040888963409));
2225                 random_offset = ((uintptr_t)r) << LG_CACHELINE;
2226         } else
2227                 random_offset = 0;
2228         run = arena_run_alloc_large(arena, usize + large_pad, zero);
2229         if (run == NULL) {
2230                 malloc_mutex_unlock(&arena->lock);
2231                 return (NULL);
2232         }
2233         miscelm = arena_run_to_miscelm(run);
2234         ret = (void *)((uintptr_t)arena_miscelm_to_rpages(miscelm) +
2235             random_offset);
2236         if (config_stats) {
2237                 szind_t index = size2index(usize) - NBINS;
2238
2239                 arena->stats.nmalloc_large++;
2240                 arena->stats.nrequests_large++;
2241                 arena->stats.allocated_large += usize;
2242                 arena->stats.lstats[index].nmalloc++;
2243                 arena->stats.lstats[index].nrequests++;
2244                 arena->stats.lstats[index].curruns++;
2245         }
2246         if (config_prof)
2247                 idump = arena_prof_accum_locked(arena, usize);
2248         malloc_mutex_unlock(&arena->lock);
2249         if (config_prof && idump)
2250                 prof_idump();
2251
2252         if (!zero) {
2253                 if (config_fill) {
2254                         if (unlikely(opt_junk_alloc))
2255                                 memset(ret, 0xa5, usize);
2256                         else if (unlikely(opt_zero))
2257                                 memset(ret, 0, usize);
2258                 }
2259         }
2260
2261         return (ret);
2262 }
2263
2264 /* Only handles large allocations that require more than page alignment. */
2265 static void *
2266 arena_palloc_large(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment,
2267     bool zero)
2268 {
2269         void *ret;
2270         size_t alloc_size, leadsize, trailsize;
2271         arena_run_t *run;
2272         arena_chunk_t *chunk;
2273         arena_chunk_map_misc_t *miscelm;
2274         void *rpages;
2275
2276         assert(usize == PAGE_CEILING(usize));
2277
2278         arena = arena_choose(tsd, arena);
2279         if (unlikely(arena == NULL))
2280                 return (NULL);
2281
2282         alignment = PAGE_CEILING(alignment);
2283         alloc_size = usize + large_pad + alignment - PAGE;
2284
2285         malloc_mutex_lock(&arena->lock);
2286         run = arena_run_alloc_large(arena, alloc_size, false);
2287         if (run == NULL) {
2288                 malloc_mutex_unlock(&arena->lock);
2289                 return (NULL);
2290         }
2291         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
2292         miscelm = arena_run_to_miscelm(run);
2293         rpages = arena_miscelm_to_rpages(miscelm);
2294
2295         leadsize = ALIGNMENT_CEILING((uintptr_t)rpages, alignment) -
2296             (uintptr_t)rpages;
2297         assert(alloc_size >= leadsize + usize);
2298         trailsize = alloc_size - leadsize - usize - large_pad;
2299         if (leadsize != 0) {
2300                 arena_chunk_map_misc_t *head_miscelm = miscelm;
2301                 arena_run_t *head_run = run;
2302
2303                 miscelm = arena_miscelm_get(chunk,
2304                     arena_miscelm_to_pageind(head_miscelm) + (leadsize >>
2305                     LG_PAGE));
2306                 run = &miscelm->run;
2307
2308                 arena_run_trim_head(arena, chunk, head_run, alloc_size,
2309                     alloc_size - leadsize);
2310         }
2311         if (trailsize != 0) {
2312                 arena_run_trim_tail(arena, chunk, run, usize + large_pad +
2313                     trailsize, usize + large_pad, false);
2314         }
2315         if (arena_run_init_large(arena, run, usize + large_pad, zero)) {
2316                 size_t run_ind =
2317                     arena_miscelm_to_pageind(arena_run_to_miscelm(run));
2318                 bool dirty = (arena_mapbits_dirty_get(chunk, run_ind) != 0);
2319                 bool decommitted = (arena_mapbits_decommitted_get(chunk,
2320                     run_ind) != 0);
2321
2322                 assert(decommitted); /* Cause of OOM. */
2323                 arena_run_dalloc(arena, run, dirty, false, decommitted);
2324                 malloc_mutex_unlock(&arena->lock);
2325                 return (NULL);
2326         }
2327         ret = arena_miscelm_to_rpages(miscelm);
2328
2329         if (config_stats) {
2330                 szind_t index = size2index(usize) - NBINS;
2331
2332                 arena->stats.nmalloc_large++;
2333                 arena->stats.nrequests_large++;
2334                 arena->stats.allocated_large += usize;
2335                 arena->stats.lstats[index].nmalloc++;
2336                 arena->stats.lstats[index].nrequests++;
2337                 arena->stats.lstats[index].curruns++;
2338         }
2339         malloc_mutex_unlock(&arena->lock);
2340
2341         if (config_fill && !zero) {
2342                 if (unlikely(opt_junk_alloc))
2343                         memset(ret, 0xa5, usize);
2344                 else if (unlikely(opt_zero))
2345                         memset(ret, 0, usize);
2346         }
2347         return (ret);
2348 }
2349
2350 void *
2351 arena_palloc(tsd_t *tsd, arena_t *arena, size_t usize, size_t alignment,
2352     bool zero, tcache_t *tcache)
2353 {
2354         void *ret;
2355
2356         if (usize <= SMALL_MAXCLASS && (alignment < PAGE || (alignment == PAGE
2357             && (usize & PAGE_MASK) == 0))) {
2358                 /* Small; alignment doesn't require special run placement. */
2359                 ret = arena_malloc(tsd, arena, usize, zero, tcache);
2360         } else if (usize <= large_maxclass && alignment <= PAGE) {
2361                 /*
2362                  * Large; alignment doesn't require special run placement.
2363                  * However, the cached pointer may be at a random offset from
2364                  * the base of the run, so do some bit manipulation to retrieve
2365                  * the base.
2366                  */
2367                 ret = arena_malloc(tsd, arena, usize, zero, tcache);
2368                 if (config_cache_oblivious)
2369                         ret = (void *)((uintptr_t)ret & ~PAGE_MASK);
2370         } else {
2371                 if (likely(usize <= large_maxclass)) {
2372                         ret = arena_palloc_large(tsd, arena, usize, alignment,
2373                             zero);
2374                 } else if (likely(alignment <= chunksize))
2375                         ret = huge_malloc(tsd, arena, usize, zero, tcache);
2376                 else {
2377                         ret = huge_palloc(tsd, arena, usize, alignment, zero,
2378                             tcache);
2379                 }
2380         }
2381         return (ret);
2382 }
2383
2384 void
2385 arena_prof_promoted(const void *ptr, size_t size)
2386 {
2387         arena_chunk_t *chunk;
2388         size_t pageind;
2389         szind_t binind;
2390
2391         cassert(config_prof);
2392         assert(ptr != NULL);
2393         assert(CHUNK_ADDR2BASE(ptr) != ptr);
2394         assert(isalloc(ptr, false) == LARGE_MINCLASS);
2395         assert(isalloc(ptr, true) == LARGE_MINCLASS);
2396         assert(size <= SMALL_MAXCLASS);
2397
2398         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2399         pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2400         binind = size2index(size);
2401         assert(binind < NBINS);
2402         arena_mapbits_large_binind_set(chunk, pageind, binind);
2403
2404         assert(isalloc(ptr, false) == LARGE_MINCLASS);
2405         assert(isalloc(ptr, true) == size);
2406 }
2407
2408 static void
2409 arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
2410     arena_bin_t *bin)
2411 {
2412
2413         /* Dissociate run from bin. */
2414         if (run == bin->runcur)
2415                 bin->runcur = NULL;
2416         else {
2417                 szind_t binind = arena_bin_index(extent_node_arena_get(
2418                     &chunk->node), bin);
2419                 arena_bin_info_t *bin_info = &arena_bin_info[binind];
2420
2421                 if (bin_info->nregs != 1) {
2422                         /*
2423                          * This block's conditional is necessary because if the
2424                          * run only contains one region, then it never gets
2425                          * inserted into the non-full runs tree.
2426                          */
2427                         arena_bin_runs_remove(bin, run);
2428                 }
2429         }
2430 }
2431
2432 static void
2433 arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2434     arena_bin_t *bin)
2435 {
2436
2437         assert(run != bin->runcur);
2438         assert(arena_run_tree_search(&bin->runs, arena_run_to_miscelm(run)) ==
2439             NULL);
2440
2441         malloc_mutex_unlock(&bin->lock);
2442         /******************************/
2443         malloc_mutex_lock(&arena->lock);
2444         arena_run_dalloc_decommit(arena, chunk, run);
2445         malloc_mutex_unlock(&arena->lock);
2446         /****************************/
2447         malloc_mutex_lock(&bin->lock);
2448         if (config_stats)
2449                 bin->stats.curruns--;
2450 }
2451
2452 static void
2453 arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
2454     arena_bin_t *bin)
2455 {
2456
2457         /*
2458          * Make sure that if bin->runcur is non-NULL, it refers to the lowest
2459          * non-full run.  It is okay to NULL runcur out rather than proactively
2460          * keeping it pointing at the lowest non-full run.
2461          */
2462         if ((uintptr_t)run < (uintptr_t)bin->runcur) {
2463                 /* Switch runcur. */
2464                 if (bin->runcur->nfree > 0)
2465                         arena_bin_runs_insert(bin, bin->runcur);
2466                 bin->runcur = run;
2467                 if (config_stats)
2468                         bin->stats.reruns++;
2469         } else
2470                 arena_bin_runs_insert(bin, run);
2471 }
2472
2473 static void
2474 arena_dalloc_bin_locked_impl(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2475     arena_chunk_map_bits_t *bitselm, bool junked)
2476 {
2477         size_t pageind, rpages_ind;
2478         arena_run_t *run;
2479         arena_bin_t *bin;
2480         arena_bin_info_t *bin_info;
2481         szind_t binind;
2482
2483         pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2484         rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind);
2485         run = &arena_miscelm_get(chunk, rpages_ind)->run;
2486         binind = run->binind;
2487         bin = &arena->bins[binind];
2488         bin_info = &arena_bin_info[binind];
2489
2490         if (!junked && config_fill && unlikely(opt_junk_free))
2491                 arena_dalloc_junk_small(ptr, bin_info);
2492
2493         arena_run_reg_dalloc(run, ptr);
2494         if (run->nfree == bin_info->nregs) {
2495                 arena_dissociate_bin_run(chunk, run, bin);
2496                 arena_dalloc_bin_run(arena, chunk, run, bin);
2497         } else if (run->nfree == 1 && run != bin->runcur)
2498                 arena_bin_lower_run(arena, chunk, run, bin);
2499
2500         if (config_stats) {
2501                 bin->stats.ndalloc++;
2502                 bin->stats.curregs--;
2503         }
2504 }
2505
2506 void
2507 arena_dalloc_bin_junked_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2508     arena_chunk_map_bits_t *bitselm)
2509 {
2510
2511         arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, true);
2512 }
2513
2514 void
2515 arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2516     size_t pageind, arena_chunk_map_bits_t *bitselm)
2517 {
2518         arena_run_t *run;
2519         arena_bin_t *bin;
2520         size_t rpages_ind;
2521
2522         rpages_ind = pageind - arena_mapbits_small_runind_get(chunk, pageind);
2523         run = &arena_miscelm_get(chunk, rpages_ind)->run;
2524         bin = &arena->bins[run->binind];
2525         malloc_mutex_lock(&bin->lock);
2526         arena_dalloc_bin_locked_impl(arena, chunk, ptr, bitselm, false);
2527         malloc_mutex_unlock(&bin->lock);
2528 }
2529
2530 void
2531 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2532     size_t pageind)
2533 {
2534         arena_chunk_map_bits_t *bitselm;
2535
2536         if (config_debug) {
2537                 /* arena_ptr_small_binind_get() does extra sanity checking. */
2538                 assert(arena_ptr_small_binind_get(ptr, arena_mapbits_get(chunk,
2539                     pageind)) != BININD_INVALID);
2540         }
2541         bitselm = arena_bitselm_get(chunk, pageind);
2542         arena_dalloc_bin(arena, chunk, ptr, pageind, bitselm);
2543 }
2544
2545 #ifdef JEMALLOC_JET
2546 #undef arena_dalloc_junk_large
2547 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large_impl)
2548 #endif
2549 void
2550 arena_dalloc_junk_large(void *ptr, size_t usize)
2551 {
2552
2553         if (config_fill && unlikely(opt_junk_free))
2554                 memset(ptr, 0x5a, usize);
2555 }
2556 #ifdef JEMALLOC_JET
2557 #undef arena_dalloc_junk_large
2558 #define arena_dalloc_junk_large JEMALLOC_N(arena_dalloc_junk_large)
2559 arena_dalloc_junk_large_t *arena_dalloc_junk_large =
2560     JEMALLOC_N(arena_dalloc_junk_large_impl);
2561 #endif
2562
2563 static void
2564 arena_dalloc_large_locked_impl(arena_t *arena, arena_chunk_t *chunk,
2565     void *ptr, bool junked)
2566 {
2567         size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2568         arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
2569         arena_run_t *run = &miscelm->run;
2570
2571         if (config_fill || config_stats) {
2572                 size_t usize = arena_mapbits_large_size_get(chunk, pageind) -
2573                     large_pad;
2574
2575                 if (!junked)
2576                         arena_dalloc_junk_large(ptr, usize);
2577                 if (config_stats) {
2578                         szind_t index = size2index(usize) - NBINS;
2579
2580                         arena->stats.ndalloc_large++;
2581                         arena->stats.allocated_large -= usize;
2582                         arena->stats.lstats[index].ndalloc++;
2583                         arena->stats.lstats[index].curruns--;
2584                 }
2585         }
2586
2587         arena_run_dalloc_decommit(arena, chunk, run);
2588 }
2589
2590 void
2591 arena_dalloc_large_junked_locked(arena_t *arena, arena_chunk_t *chunk,
2592     void *ptr)
2593 {
2594
2595         arena_dalloc_large_locked_impl(arena, chunk, ptr, true);
2596 }
2597
2598 void
2599 arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
2600 {
2601
2602         malloc_mutex_lock(&arena->lock);
2603         arena_dalloc_large_locked_impl(arena, chunk, ptr, false);
2604         malloc_mutex_unlock(&arena->lock);
2605 }
2606
2607 static void
2608 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2609     size_t oldsize, size_t size)
2610 {
2611         size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2612         arena_chunk_map_misc_t *miscelm = arena_miscelm_get(chunk, pageind);
2613         arena_run_t *run = &miscelm->run;
2614
2615         assert(size < oldsize);
2616
2617         /*
2618          * Shrink the run, and make trailing pages available for other
2619          * allocations.
2620          */
2621         malloc_mutex_lock(&arena->lock);
2622         arena_run_trim_tail(arena, chunk, run, oldsize + large_pad, size +
2623             large_pad, true);
2624         if (config_stats) {
2625                 szind_t oldindex = size2index(oldsize) - NBINS;
2626                 szind_t index = size2index(size) - NBINS;
2627
2628                 arena->stats.ndalloc_large++;
2629                 arena->stats.allocated_large -= oldsize;
2630                 arena->stats.lstats[oldindex].ndalloc++;
2631                 arena->stats.lstats[oldindex].curruns--;
2632
2633                 arena->stats.nmalloc_large++;
2634                 arena->stats.nrequests_large++;
2635                 arena->stats.allocated_large += size;
2636                 arena->stats.lstats[index].nmalloc++;
2637                 arena->stats.lstats[index].nrequests++;
2638                 arena->stats.lstats[index].curruns++;
2639         }
2640         malloc_mutex_unlock(&arena->lock);
2641 }
2642
2643 static bool
2644 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
2645     size_t oldsize, size_t usize_min, size_t usize_max, bool zero)
2646 {
2647         size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
2648         size_t npages = (oldsize + large_pad) >> LG_PAGE;
2649         size_t followsize;
2650
2651         assert(oldsize == arena_mapbits_large_size_get(chunk, pageind) -
2652             large_pad);
2653
2654         /* Try to extend the run. */
2655         malloc_mutex_lock(&arena->lock);
2656         if (pageind+npages >= chunk_npages || arena_mapbits_allocated_get(chunk,
2657             pageind+npages) != 0)
2658                 goto label_fail;
2659         followsize = arena_mapbits_unallocated_size_get(chunk, pageind+npages);
2660         if (oldsize + followsize >= usize_min) {
2661                 /*
2662                  * The next run is available and sufficiently large.  Split the
2663                  * following run, then merge the first part with the existing
2664                  * allocation.
2665                  */
2666                 arena_run_t *run;
2667                 size_t usize, splitsize, size, flag_dirty, flag_unzeroed_mask;
2668
2669                 usize = usize_max;
2670                 while (oldsize + followsize < usize)
2671                         usize = index2size(size2index(usize)-1);
2672                 assert(usize >= usize_min);
2673                 assert(usize >= oldsize);
2674                 splitsize = usize - oldsize;
2675                 if (splitsize == 0)
2676                         goto label_fail;
2677
2678                 run = &arena_miscelm_get(chunk, pageind+npages)->run;
2679                 if (arena_run_split_large(arena, run, splitsize, zero))
2680                         goto label_fail;
2681
2682                 if (config_cache_oblivious && zero) {
2683                         /*
2684                          * Zero the trailing bytes of the original allocation's
2685                          * last page, since they are in an indeterminate state.
2686                          * There will always be trailing bytes, because ptr's
2687                          * offset from the beginning of the run is a multiple of
2688                          * CACHELINE in [0 .. PAGE).
2689                          */
2690                         void *zbase = (void *)((uintptr_t)ptr + oldsize);
2691                         void *zpast = PAGE_ADDR2BASE((void *)((uintptr_t)zbase +
2692                             PAGE));
2693                         size_t nzero = (uintptr_t)zpast - (uintptr_t)zbase;
2694                         assert(nzero > 0);
2695                         memset(zbase, 0, nzero);
2696                 }
2697
2698                 size = oldsize + splitsize;
2699                 npages = (size + large_pad) >> LG_PAGE;
2700
2701                 /*
2702                  * Mark the extended run as dirty if either portion of the run
2703                  * was dirty before allocation.  This is rather pedantic,
2704                  * because there's not actually any sequence of events that
2705                  * could cause the resulting run to be passed to
2706                  * arena_run_dalloc() with the dirty argument set to false
2707                  * (which is when dirty flag consistency would really matter).
2708                  */
2709                 flag_dirty = arena_mapbits_dirty_get(chunk, pageind) |
2710                     arena_mapbits_dirty_get(chunk, pageind+npages-1);
2711                 flag_unzeroed_mask = flag_dirty == 0 ? CHUNK_MAP_UNZEROED : 0;
2712                 arena_mapbits_large_set(chunk, pageind, size + large_pad,
2713                     flag_dirty | (flag_unzeroed_mask &
2714                     arena_mapbits_unzeroed_get(chunk, pageind)));
2715                 arena_mapbits_large_set(chunk, pageind+npages-1, 0, flag_dirty |
2716                     (flag_unzeroed_mask & arena_mapbits_unzeroed_get(chunk,
2717                     pageind+npages-1)));
2718
2719                 if (config_stats) {
2720                         szind_t oldindex = size2index(oldsize) - NBINS;
2721                         szind_t index = size2index(size) - NBINS;
2722
2723                         arena->stats.ndalloc_large++;
2724                         arena->stats.allocated_large -= oldsize;
2725                         arena->stats.lstats[oldindex].ndalloc++;
2726                         arena->stats.lstats[oldindex].curruns--;
2727
2728                         arena->stats.nmalloc_large++;
2729                         arena->stats.nrequests_large++;
2730                         arena->stats.allocated_large += size;
2731                         arena->stats.lstats[index].nmalloc++;
2732                         arena->stats.lstats[index].nrequests++;
2733                         arena->stats.lstats[index].curruns++;
2734                 }
2735                 malloc_mutex_unlock(&arena->lock);
2736                 return (false);
2737         }
2738 label_fail:
2739         malloc_mutex_unlock(&arena->lock);
2740         return (true);
2741 }
2742
2743 #ifdef JEMALLOC_JET
2744 #undef arena_ralloc_junk_large
2745 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large_impl)
2746 #endif
2747 static void
2748 arena_ralloc_junk_large(void *ptr, size_t old_usize, size_t usize)
2749 {
2750
2751         if (config_fill && unlikely(opt_junk_free)) {
2752                 memset((void *)((uintptr_t)ptr + usize), 0x5a,
2753                     old_usize - usize);
2754         }
2755 }
2756 #ifdef JEMALLOC_JET
2757 #undef arena_ralloc_junk_large
2758 #define arena_ralloc_junk_large JEMALLOC_N(arena_ralloc_junk_large)
2759 arena_ralloc_junk_large_t *arena_ralloc_junk_large =
2760     JEMALLOC_N(arena_ralloc_junk_large_impl);
2761 #endif
2762
2763 /*
2764  * Try to resize a large allocation, in order to avoid copying.  This will
2765  * always fail if growing an object, and the following run is already in use.
2766  */
2767 static bool
2768 arena_ralloc_large(void *ptr, size_t oldsize, size_t usize_min,
2769     size_t usize_max, bool zero)
2770 {
2771         arena_chunk_t *chunk;
2772         arena_t *arena;
2773
2774         if (oldsize == usize_max) {
2775                 /* Current size class is compatible and maximal. */
2776                 return (false);
2777         }
2778
2779         chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2780         arena = extent_node_arena_get(&chunk->node);
2781
2782         if (oldsize < usize_max) {
2783                 bool ret = arena_ralloc_large_grow(arena, chunk, ptr, oldsize,
2784                     usize_min, usize_max, zero);
2785                 if (config_fill && !ret && !zero) {
2786                         if (unlikely(opt_junk_alloc)) {
2787                                 memset((void *)((uintptr_t)ptr + oldsize), 0xa5,
2788                                     isalloc(ptr, config_prof) - oldsize);
2789                         } else if (unlikely(opt_zero)) {
2790                                 memset((void *)((uintptr_t)ptr + oldsize), 0,
2791                                     isalloc(ptr, config_prof) - oldsize);
2792                         }
2793                 }
2794                 return (ret);
2795         }
2796
2797         assert(oldsize > usize_max);
2798         /* Fill before shrinking in order avoid a race. */
2799         arena_ralloc_junk_large(ptr, oldsize, usize_max);
2800         arena_ralloc_large_shrink(arena, chunk, ptr, oldsize, usize_max);
2801         return (false);
2802 }
2803
2804 bool
2805 arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, size_t extra,
2806     bool zero)
2807 {
2808         size_t usize_min, usize_max;
2809
2810         usize_min = s2u(size);
2811         usize_max = s2u(size + extra);
2812         if (likely(oldsize <= large_maxclass && usize_min <= large_maxclass)) {
2813                 /*
2814                  * Avoid moving the allocation if the size class can be left the
2815                  * same.
2816                  */
2817                 if (oldsize <= SMALL_MAXCLASS) {
2818                         assert(arena_bin_info[size2index(oldsize)].reg_size ==
2819                             oldsize);
2820                         if ((usize_max <= SMALL_MAXCLASS &&
2821                             size2index(usize_max) == size2index(oldsize)) ||
2822                             (size <= oldsize && usize_max >= oldsize))
2823                                 return (false);
2824                 } else {
2825                         if (usize_max > SMALL_MAXCLASS) {
2826                                 if (!arena_ralloc_large(ptr, oldsize, usize_min,
2827                                     usize_max, zero))
2828                                         return (false);
2829                         }
2830                 }
2831
2832                 /* Reallocation would require a move. */
2833                 return (true);
2834         } else {
2835                 return (huge_ralloc_no_move(ptr, oldsize, usize_min, usize_max,
2836                     zero));
2837         }
2838 }
2839
2840 static void *
2841 arena_ralloc_move_helper(tsd_t *tsd, arena_t *arena, size_t usize,
2842     size_t alignment, bool zero, tcache_t *tcache)
2843 {
2844
2845         if (alignment == 0)
2846                 return (arena_malloc(tsd, arena, usize, zero, tcache));
2847         usize = sa2u(usize, alignment);
2848         if (usize == 0)
2849                 return (NULL);
2850         return (ipalloct(tsd, usize, alignment, zero, tcache, arena));
2851 }
2852
2853 void *
2854 arena_ralloc(tsd_t *tsd, arena_t *arena, void *ptr, size_t oldsize, size_t size,
2855     size_t alignment, bool zero, tcache_t *tcache)
2856 {
2857         void *ret;
2858         size_t usize;
2859
2860         usize = s2u(size);
2861         if (usize == 0)
2862                 return (NULL);
2863
2864         if (likely(usize <= large_maxclass)) {
2865                 size_t copysize;
2866
2867                 /* Try to avoid moving the allocation. */
2868                 if (!arena_ralloc_no_move(ptr, oldsize, usize, 0, zero))
2869                         return (ptr);
2870
2871                 /*
2872                  * size and oldsize are different enough that we need to move
2873                  * the object.  In that case, fall back to allocating new space
2874                  * and copying.
2875                  */
2876                 ret = arena_ralloc_move_helper(tsd, arena, usize, alignment,
2877                     zero, tcache);
2878                 if (ret == NULL)
2879                         return (NULL);
2880
2881                 /*
2882                  * Junk/zero-filling were already done by
2883                  * ipalloc()/arena_malloc().
2884                  */
2885
2886                 copysize = (usize < oldsize) ? usize : oldsize;
2887                 JEMALLOC_VALGRIND_MAKE_MEM_UNDEFINED(ret, copysize);
2888                 memcpy(ret, ptr, copysize);
2889                 isqalloc(tsd, ptr, oldsize, tcache);
2890         } else {
2891                 ret = huge_ralloc(tsd, arena, ptr, oldsize, usize, alignment,
2892                     zero, tcache);
2893         }
2894         return (ret);
2895 }
2896
2897 dss_prec_t
2898 arena_dss_prec_get(arena_t *arena)
2899 {
2900         dss_prec_t ret;
2901
2902         malloc_mutex_lock(&arena->lock);
2903         ret = arena->dss_prec;
2904         malloc_mutex_unlock(&arena->lock);
2905         return (ret);
2906 }
2907
2908 bool
2909 arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec)
2910 {
2911
2912         if (!have_dss)
2913                 return (dss_prec != dss_prec_disabled);
2914         malloc_mutex_lock(&arena->lock);
2915         arena->dss_prec = dss_prec;
2916         malloc_mutex_unlock(&arena->lock);
2917         return (false);
2918 }
2919
2920 ssize_t
2921 arena_lg_dirty_mult_default_get(void)
2922 {
2923
2924         return ((ssize_t)atomic_read_z((size_t *)&lg_dirty_mult_default));
2925 }
2926
2927 bool
2928 arena_lg_dirty_mult_default_set(ssize_t lg_dirty_mult)
2929 {
2930
2931         if (!arena_lg_dirty_mult_valid(lg_dirty_mult))
2932                 return (true);
2933         atomic_write_z((size_t *)&lg_dirty_mult_default, (size_t)lg_dirty_mult);
2934         return (false);
2935 }
2936
2937 void
2938 arena_stats_merge(arena_t *arena, const char **dss, ssize_t *lg_dirty_mult,
2939     size_t *nactive, size_t *ndirty, arena_stats_t *astats,
2940     malloc_bin_stats_t *bstats, malloc_large_stats_t *lstats,
2941     malloc_huge_stats_t *hstats)
2942 {
2943         unsigned i;
2944
2945         malloc_mutex_lock(&arena->lock);
2946         *dss = dss_prec_names[arena->dss_prec];
2947         *lg_dirty_mult = arena->lg_dirty_mult;
2948         *nactive += arena->nactive;
2949         *ndirty += arena->ndirty;
2950
2951         astats->mapped += arena->stats.mapped;
2952         astats->npurge += arena->stats.npurge;
2953         astats->nmadvise += arena->stats.nmadvise;
2954         astats->purged += arena->stats.purged;
2955         astats->metadata_mapped += arena->stats.metadata_mapped;
2956         astats->metadata_allocated += arena_metadata_allocated_get(arena);
2957         astats->allocated_large += arena->stats.allocated_large;
2958         astats->nmalloc_large += arena->stats.nmalloc_large;
2959         astats->ndalloc_large += arena->stats.ndalloc_large;
2960         astats->nrequests_large += arena->stats.nrequests_large;
2961         astats->allocated_huge += arena->stats.allocated_huge;
2962         astats->nmalloc_huge += arena->stats.nmalloc_huge;
2963         astats->ndalloc_huge += arena->stats.ndalloc_huge;
2964
2965         for (i = 0; i < nlclasses; i++) {
2966                 lstats[i].nmalloc += arena->stats.lstats[i].nmalloc;
2967                 lstats[i].ndalloc += arena->stats.lstats[i].ndalloc;
2968                 lstats[i].nrequests += arena->stats.lstats[i].nrequests;
2969                 lstats[i].curruns += arena->stats.lstats[i].curruns;
2970         }
2971
2972         for (i = 0; i < nhclasses; i++) {
2973                 hstats[i].nmalloc += arena->stats.hstats[i].nmalloc;
2974                 hstats[i].ndalloc += arena->stats.hstats[i].ndalloc;
2975                 hstats[i].curhchunks += arena->stats.hstats[i].curhchunks;
2976         }
2977         malloc_mutex_unlock(&arena->lock);
2978
2979         for (i = 0; i < NBINS; i++) {
2980                 arena_bin_t *bin = &arena->bins[i];
2981
2982                 malloc_mutex_lock(&bin->lock);
2983                 bstats[i].nmalloc += bin->stats.nmalloc;
2984                 bstats[i].ndalloc += bin->stats.ndalloc;
2985                 bstats[i].nrequests += bin->stats.nrequests;
2986                 bstats[i].curregs += bin->stats.curregs;
2987                 if (config_tcache) {
2988                         bstats[i].nfills += bin->stats.nfills;
2989                         bstats[i].nflushes += bin->stats.nflushes;
2990                 }
2991                 bstats[i].nruns += bin->stats.nruns;
2992                 bstats[i].reruns += bin->stats.reruns;
2993                 bstats[i].curruns += bin->stats.curruns;
2994                 malloc_mutex_unlock(&bin->lock);
2995         }
2996 }
2997
2998 arena_t *
2999 arena_new(unsigned ind)
3000 {
3001         arena_t *arena;
3002         unsigned i;
3003         arena_bin_t *bin;
3004
3005         /*
3006          * Allocate arena, arena->lstats, and arena->hstats contiguously, mainly
3007          * because there is no way to clean up if base_alloc() OOMs.
3008          */
3009         if (config_stats) {
3010                 arena = (arena_t *)base_alloc(CACHELINE_CEILING(sizeof(arena_t))
3011                     + QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t) +
3012                     nhclasses) * sizeof(malloc_huge_stats_t));
3013         } else
3014                 arena = (arena_t *)base_alloc(sizeof(arena_t));
3015         if (arena == NULL)
3016                 return (NULL);
3017
3018         arena->ind = ind;
3019         arena->nthreads = 0;
3020         if (malloc_mutex_init(&arena->lock))
3021                 return (NULL);
3022
3023         if (config_stats) {
3024                 memset(&arena->stats, 0, sizeof(arena_stats_t));
3025                 arena->stats.lstats = (malloc_large_stats_t *)((uintptr_t)arena
3026                     + CACHELINE_CEILING(sizeof(arena_t)));
3027                 memset(arena->stats.lstats, 0, nlclasses *
3028                     sizeof(malloc_large_stats_t));
3029                 arena->stats.hstats = (malloc_huge_stats_t *)((uintptr_t)arena
3030                     + CACHELINE_CEILING(sizeof(arena_t)) +
3031                     QUANTUM_CEILING(nlclasses * sizeof(malloc_large_stats_t)));
3032                 memset(arena->stats.hstats, 0, nhclasses *
3033                     sizeof(malloc_huge_stats_t));
3034                 if (config_tcache)
3035                         ql_new(&arena->tcache_ql);
3036         }
3037
3038         if (config_prof)
3039                 arena->prof_accumbytes = 0;
3040
3041         if (config_cache_oblivious) {
3042                 /*
3043                  * A nondeterministic seed based on the address of arena reduces
3044                  * the likelihood of lockstep non-uniform cache index
3045                  * utilization among identical concurrent processes, but at the
3046                  * cost of test repeatability.  For debug builds, instead use a
3047                  * deterministic seed.
3048                  */
3049                 arena->offset_state = config_debug ? ind :
3050                     (uint64_t)(uintptr_t)arena;
3051         }
3052
3053         arena->dss_prec = chunk_dss_prec_get();
3054
3055         arena->spare = NULL;
3056
3057         arena->lg_dirty_mult = arena_lg_dirty_mult_default_get();
3058         arena->purging = false;
3059         arena->nactive = 0;
3060         arena->ndirty = 0;
3061
3062         arena_avail_tree_new(&arena->runs_avail);
3063         qr_new(&arena->runs_dirty, rd_link);
3064         qr_new(&arena->chunks_cache, cc_link);
3065
3066         ql_new(&arena->huge);
3067         if (malloc_mutex_init(&arena->huge_mtx))
3068                 return (NULL);
3069
3070         extent_tree_szad_new(&arena->chunks_szad_cached);
3071         extent_tree_ad_new(&arena->chunks_ad_cached);
3072         extent_tree_szad_new(&arena->chunks_szad_retained);
3073         extent_tree_ad_new(&arena->chunks_ad_retained);
3074         if (malloc_mutex_init(&arena->chunks_mtx))
3075                 return (NULL);
3076         ql_new(&arena->node_cache);
3077         if (malloc_mutex_init(&arena->node_cache_mtx))
3078                 return (NULL);
3079
3080         arena->chunk_hooks = chunk_hooks_default;
3081
3082         /* Initialize bins. */
3083         for (i = 0; i < NBINS; i++) {
3084                 bin = &arena->bins[i];
3085                 if (malloc_mutex_init(&bin->lock))
3086                         return (NULL);
3087                 bin->runcur = NULL;
3088                 arena_run_tree_new(&bin->runs);
3089                 if (config_stats)
3090                         memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
3091         }
3092
3093         return (arena);
3094 }
3095
3096 /*
3097  * Calculate bin_info->run_size such that it meets the following constraints:
3098  *
3099  *   *) bin_info->run_size <= arena_maxrun
3100  *   *) bin_info->nregs <= RUN_MAXREGS
3101  *
3102  * bin_info->nregs and bin_info->reg0_offset are also calculated here, since
3103  * these settings are all interdependent.
3104  */
3105 static void
3106 bin_info_run_size_calc(arena_bin_info_t *bin_info)
3107 {
3108         size_t pad_size;
3109         size_t try_run_size, perfect_run_size, actual_run_size;
3110         uint32_t try_nregs, perfect_nregs, actual_nregs;
3111
3112         /*
3113          * Determine redzone size based on minimum alignment and minimum
3114          * redzone size.  Add padding to the end of the run if it is needed to
3115          * align the regions.  The padding allows each redzone to be half the
3116          * minimum alignment; without the padding, each redzone would have to
3117          * be twice as large in order to maintain alignment.
3118          */
3119         if (config_fill && unlikely(opt_redzone)) {
3120                 size_t align_min = ZU(1) << (jemalloc_ffs(bin_info->reg_size) -
3121                     1);
3122                 if (align_min <= REDZONE_MINSIZE) {
3123                         bin_info->redzone_size = REDZONE_MINSIZE;
3124                         pad_size = 0;
3125                 } else {
3126                         bin_info->redzone_size = align_min >> 1;
3127                         pad_size = bin_info->redzone_size;
3128                 }
3129         } else {
3130                 bin_info->redzone_size = 0;
3131                 pad_size = 0;
3132         }
3133         bin_info->reg_interval = bin_info->reg_size +
3134             (bin_info->redzone_size << 1);
3135
3136         /*
3137          * Compute run size under ideal conditions (no redzones, no limit on run
3138          * size).
3139          */
3140         try_run_size = PAGE;
3141         try_nregs = try_run_size / bin_info->reg_size;
3142         do {
3143                 perfect_run_size = try_run_size;
3144                 perfect_nregs = try_nregs;
3145
3146                 try_run_size += PAGE;
3147                 try_nregs = try_run_size / bin_info->reg_size;
3148         } while (perfect_run_size != perfect_nregs * bin_info->reg_size);
3149         assert(perfect_nregs <= RUN_MAXREGS);
3150
3151         actual_run_size = perfect_run_size;
3152         actual_nregs = (actual_run_size - pad_size) / bin_info->reg_interval;
3153
3154         /*
3155          * Redzones can require enough padding that not even a single region can
3156          * fit within the number of pages that would normally be dedicated to a
3157          * run for this size class.  Increase the run size until at least one
3158          * region fits.
3159          */
3160         while (actual_nregs == 0) {
3161                 assert(config_fill && unlikely(opt_redzone));
3162
3163                 actual_run_size += PAGE;
3164                 actual_nregs = (actual_run_size - pad_size) /
3165                     bin_info->reg_interval;
3166         }
3167
3168         /*
3169          * Make sure that the run will fit within an arena chunk.
3170          */
3171         while (actual_run_size > arena_maxrun) {
3172                 actual_run_size -= PAGE;
3173                 actual_nregs = (actual_run_size - pad_size) /
3174                     bin_info->reg_interval;
3175         }
3176         assert(actual_nregs > 0);
3177         assert(actual_run_size == s2u(actual_run_size));
3178
3179         /* Copy final settings. */
3180         bin_info->run_size = actual_run_size;
3181         bin_info->nregs = actual_nregs;
3182         bin_info->reg0_offset = actual_run_size - (actual_nregs *
3183             bin_info->reg_interval) - pad_size + bin_info->redzone_size;
3184
3185         if (actual_run_size > small_maxrun)
3186                 small_maxrun = actual_run_size;
3187
3188         assert(bin_info->reg0_offset - bin_info->redzone_size + (bin_info->nregs
3189             * bin_info->reg_interval) + pad_size == bin_info->run_size);
3190 }
3191
3192 static void
3193 bin_info_init(void)
3194 {
3195         arena_bin_info_t *bin_info;
3196
3197 #define BIN_INFO_INIT_bin_yes(index, size)                              \
3198         bin_info = &arena_bin_info[index];                              \
3199         bin_info->reg_size = size;                                      \
3200         bin_info_run_size_calc(bin_info);                               \
3201         bitmap_info_init(&bin_info->bitmap_info, bin_info->nregs);
3202 #define BIN_INFO_INIT_bin_no(index, size)
3203 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup)       \
3204         BIN_INFO_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
3205         SIZE_CLASSES
3206 #undef BIN_INFO_INIT_bin_yes
3207 #undef BIN_INFO_INIT_bin_no
3208 #undef SC
3209 }
3210
3211 static bool
3212 small_run_size_init(void)
3213 {
3214
3215         assert(small_maxrun != 0);
3216
3217         small_run_tab = (bool *)base_alloc(sizeof(bool) * (small_maxrun >>
3218             LG_PAGE));
3219         if (small_run_tab == NULL)
3220                 return (true);
3221
3222 #define TAB_INIT_bin_yes(index, size) {                                 \
3223                 arena_bin_info_t *bin_info = &arena_bin_info[index];    \
3224                 small_run_tab[bin_info->run_size >> LG_PAGE] = true;    \
3225         }
3226 #define TAB_INIT_bin_no(index, size)
3227 #define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup)       \
3228         TAB_INIT_bin_##bin(index, (ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta))
3229         SIZE_CLASSES
3230 #undef TAB_INIT_bin_yes
3231 #undef TAB_INIT_bin_no
3232 #undef SC
3233
3234         return (false);
3235 }
3236
3237 bool
3238 arena_boot(void)
3239 {
3240         unsigned i;
3241
3242         arena_lg_dirty_mult_default_set(opt_lg_dirty_mult);
3243
3244         /*
3245          * Compute the header size such that it is large enough to contain the
3246          * page map.  The page map is biased to omit entries for the header
3247          * itself, so some iteration is necessary to compute the map bias.
3248          *
3249          * 1) Compute safe header_size and map_bias values that include enough
3250          *    space for an unbiased page map.
3251          * 2) Refine map_bias based on (1) to omit the header pages in the page
3252          *    map.  The resulting map_bias may be one too small.
3253          * 3) Refine map_bias based on (2).  The result will be >= the result
3254          *    from (2), and will always be correct.
3255          */
3256         map_bias = 0;
3257         for (i = 0; i < 3; i++) {
3258                 size_t header_size = offsetof(arena_chunk_t, map_bits) +
3259                     ((sizeof(arena_chunk_map_bits_t) +
3260                     sizeof(arena_chunk_map_misc_t)) * (chunk_npages-map_bias));
3261                 map_bias = (header_size + PAGE_MASK) >> LG_PAGE;
3262         }
3263         assert(map_bias > 0);
3264
3265         map_misc_offset = offsetof(arena_chunk_t, map_bits) +
3266             sizeof(arena_chunk_map_bits_t) * (chunk_npages-map_bias);
3267
3268         arena_maxrun = chunksize - (map_bias << LG_PAGE);
3269         assert(arena_maxrun > 0);
3270         large_maxclass = index2size(size2index(chunksize)-1);
3271         if (large_maxclass > arena_maxrun) {
3272                 /*
3273                  * For small chunk sizes it's possible for there to be fewer
3274                  * non-header pages available than are necessary to serve the
3275                  * size classes just below chunksize.
3276                  */
3277                 large_maxclass = arena_maxrun;
3278         }
3279         assert(large_maxclass > 0);
3280         nlclasses = size2index(large_maxclass) - size2index(SMALL_MAXCLASS);
3281         nhclasses = NSIZES - nlclasses - NBINS;
3282
3283         bin_info_init();
3284         return (small_run_size_init());
3285 }
3286
3287 void
3288 arena_prefork(arena_t *arena)
3289 {
3290         unsigned i;
3291
3292         malloc_mutex_prefork(&arena->lock);
3293         malloc_mutex_prefork(&arena->huge_mtx);
3294         malloc_mutex_prefork(&arena->chunks_mtx);
3295         malloc_mutex_prefork(&arena->node_cache_mtx);
3296         for (i = 0; i < NBINS; i++)
3297                 malloc_mutex_prefork(&arena->bins[i].lock);
3298 }
3299
3300 void
3301 arena_postfork_parent(arena_t *arena)
3302 {
3303         unsigned i;
3304
3305         for (i = 0; i < NBINS; i++)
3306                 malloc_mutex_postfork_parent(&arena->bins[i].lock);
3307         malloc_mutex_postfork_parent(&arena->node_cache_mtx);
3308         malloc_mutex_postfork_parent(&arena->chunks_mtx);
3309         malloc_mutex_postfork_parent(&arena->huge_mtx);
3310         malloc_mutex_postfork_parent(&arena->lock);
3311 }
3312
3313 void
3314 arena_postfork_child(arena_t *arena)
3315 {
3316         unsigned i;
3317
3318         for (i = 0; i < NBINS; i++)
3319                 malloc_mutex_postfork_child(&arena->bins[i].lock);
3320         malloc_mutex_postfork_child(&arena->node_cache_mtx);
3321         malloc_mutex_postfork_child(&arena->chunks_mtx);
3322         malloc_mutex_postfork_child(&arena->huge_mtx);
3323         malloc_mutex_postfork_child(&arena->lock);
3324 }