1 /* $NetBSD: jemalloc.c,v 1.64 2023/12/13 23:53:50 mrg Exp $ */ 2 3 /*- 4 * Copyright (C) 2006,2007 Jason Evans <jasone@FreeBSD.org>. 5 * Copyright (C) 2023 Andrew Doran <ad@NetBSD.org>. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice(s), this list of conditions and the following disclaimer as 13 * the first lines of this file unmodified other than the possible 14 * addition of one or more copyright notices. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice(s), this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY 21 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE 24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 27 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 28 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 29 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 * 32 ******************************************************************************* 33 * 34 * This allocator implementation is designed to provide scalable performance 35 * for multi-threaded programs on multi-processor systems. The following 36 * features are included for this purpose: 37 * 38 * + Multiple arenas are used if there are multiple CPUs, which reduces lock 39 * contention and cache sloshing. 40 * 41 * + Cache line sharing between arenas is avoided for internal data 42 * structures. 43 * 44 * + Memory is managed in chunks and runs (chunks can be split into runs), 45 * rather than as individual pages. This provides a constant-time 46 * mechanism for associating allocations with particular arenas. 47 * 48 * Allocation requests are rounded up to the nearest size class, and no record 49 * of the original request size is maintained. Allocations are broken into 50 * categories according to size class. Assuming runtime defaults, 4 kB pages 51 * and a 16 byte quantum, the size classes in each category are as follows: 52 * 53 * |=====================================| 54 * | Category | Subcategory | Size | 55 * |=====================================| 56 * | Small | Tiny | 2 | 57 * | | | 4 | 58 * | | | 8 | 59 * | |----------------+---------| 60 * | | Quantum-spaced | 16 | 61 * | | | 32 | 62 * | | | 48 | 63 * | | | ... | 64 * | | | 480 | 65 * | | | 496 | 66 * | | | 512 | 67 * | |----------------+---------| 68 * | | Sub-page | 1 kB | 69 * | | | 2 kB | 70 * |=====================================| 71 * | Large | 4 kB | 72 * | | 8 kB | 73 * | | 12 kB | 74 * | | ... | 75 * | | 1012 kB | 76 * | | 1016 kB | 77 * | | 1020 kB | 78 * |=====================================| 79 * | Huge | 1 MB | 80 * | | 2 MB | 81 * | | 3 MB | 82 * | | ... | 83 * |=====================================| 84 * 85 * A different mechanism is used for each category: 86 * 87 * Small : Each size class is segregated into its own set of runs. Each run 88 * maintains a bitmap of which regions are free/allocated. 89 * 90 * Large : Each allocation is backed by a dedicated run. Metadata are stored 91 * in the associated arena chunk header maps. 92 * 93 * Huge : Each allocation is backed by a dedicated contiguous set of chunks. 94 * Metadata are stored in a separate red-black tree. 95 * 96 ******************************************************************************* 97 */ 98 99 /* LINTLIBRARY */ 100 101 /* 102 * MALLOC_PRODUCTION disables assertions and statistics gathering. It also 103 * defaults the A and J runtime options to off. These settings are appropriate 104 * for production systems. 105 */ 106 #define MALLOC_PRODUCTION 107 108 #ifndef MALLOC_PRODUCTION 109 # define MALLOC_DEBUG 110 #endif 111 112 #include <sys/cdefs.h> 113 /* __FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.147 2007/06/15 22:00:16 jasone Exp $"); */ 114 __RCSID("$NetBSD: jemalloc.c,v 1.64 2023/12/13 23:53:50 mrg Exp $"); 115 116 #include "namespace.h" 117 #include <sys/mman.h> 118 #include <sys/param.h> 119 #include <sys/time.h> 120 #include <sys/types.h> 121 #include <sys/sysctl.h> 122 #include <sys/rbtree.h> 123 #include <sys/uio.h> 124 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */ 125 126 #include <errno.h> 127 #include <limits.h> 128 #include <pthread.h> 129 #include <sched.h> 130 #include <stdarg.h> 131 #include <stdbool.h> 132 #include <stdio.h> 133 #include <stdint.h> 134 #include <stdlib.h> 135 #include <string.h> 136 #include <strings.h> 137 #include <unistd.h> 138 #include <malloc.h> 139 140 #include <reentrant.h> 141 #include "extern.h" 142 143 #define STRERROR_R(a, b, c) strerror_r_ss(a, b, c); 144 145 /* MALLOC_STATS enables statistics calculation. */ 146 #ifndef MALLOC_PRODUCTION 147 # define MALLOC_STATS 148 #endif 149 150 #ifdef MALLOC_DEBUG 151 # ifdef NDEBUG 152 # undef NDEBUG 153 # endif 154 #else 155 # ifndef NDEBUG 156 # define NDEBUG 157 # endif 158 #endif 159 #include <assert.h> 160 161 #ifdef MALLOC_DEBUG 162 /* Disable inlining to make debugging easier. */ 163 # define inline 164 #endif 165 166 /* 167 * Compare two pointers of 64/32 bit width and produce a ternary 32-bit 168 * indicator without using conditionals that maintains the expected 169 * ordering: [negative, equal, positive]. 170 * 171 * XXX it depends on twos complement arithemetic. 172 * XXX maybe should be a built-in for rbtree? 173 */ 174 static inline int 175 ptrcmp(const void *pa, const void *pb) 176 { 177 #ifdef _LP64 178 const uintptr_t a = (uintptr_t)pa, b = (uintptr_t)pb; 179 const uintptr_t diff = a - b; 180 assert(((a | b) & 1) == 0); 181 return (int)(diff >> 32) | ((unsigned)diff >> 1); 182 #else 183 return (intptr_t)pa - (intptr_t)pb; 184 #endif 185 } 186 187 /* Size of stack-allocated buffer passed to strerror_r(). */ 188 #define STRERROR_BUF 64 189 190 /* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */ 191 192 /* 193 * If you touch the TINY_MIN_2POW definition for any architecture, please 194 * make sure to adjust the corresponding definition for JEMALLOC_TINY_MIN_2POW 195 * in the gcc 4.8 tree in dist/gcc/tree-ssa-ccp.c and verify that a native 196 * gcc is still buildable! 197 */ 198 199 #ifdef __i386__ 200 # define QUANTUM_2POW_MIN 4 201 # define SIZEOF_PTR_2POW 2 202 # define USE_BRK 203 #endif 204 #ifdef __ia64__ 205 # define QUANTUM_2POW_MIN 4 206 # define SIZEOF_PTR_2POW 3 207 #endif 208 #ifdef __aarch64__ 209 # define QUANTUM_2POW_MIN 4 210 # define SIZEOF_PTR_2POW 3 211 # define TINY_MIN_2POW 3 212 #endif 213 #ifdef __alpha__ 214 # define QUANTUM_2POW_MIN 4 215 # define SIZEOF_PTR_2POW 3 216 # define TINY_MIN_2POW 3 217 #endif 218 #ifdef __sparc64__ 219 # define QUANTUM_2POW_MIN 4 220 # define SIZEOF_PTR_2POW 3 221 # define TINY_MIN_2POW 3 222 #endif 223 #ifdef __amd64__ 224 # define QUANTUM_2POW_MIN 4 225 # define SIZEOF_PTR_2POW 3 226 # define TINY_MIN_2POW 3 227 #endif 228 #ifdef __arm__ 229 # define QUANTUM_2POW_MIN 3 230 # define SIZEOF_PTR_2POW 2 231 # define USE_BRK 232 # ifdef __ARM_EABI__ 233 # define TINY_MIN_2POW 3 234 # endif 235 #endif 236 #ifdef __powerpc__ 237 # define QUANTUM_2POW_MIN 4 238 # define SIZEOF_PTR_2POW 2 239 # define USE_BRK 240 # define TINY_MIN_2POW 3 241 #endif 242 #if defined(__sparc__) && !defined(__sparc64__) 243 # define QUANTUM_2POW_MIN 4 244 # define SIZEOF_PTR_2POW 2 245 # define USE_BRK 246 #endif 247 #ifdef __or1k__ 248 # define QUANTUM_2POW_MIN 4 249 # define SIZEOF_PTR_2POW 2 250 # define USE_BRK 251 #endif 252 #ifdef __vax__ 253 # define QUANTUM_2POW_MIN 4 254 # define SIZEOF_PTR_2POW 2 255 # define USE_BRK 256 #endif 257 #ifdef __sh__ 258 # define QUANTUM_2POW_MIN 4 259 # define SIZEOF_PTR_2POW 2 260 # define USE_BRK 261 #endif 262 #ifdef __m68k__ 263 # define QUANTUM_2POW_MIN 4 264 # define SIZEOF_PTR_2POW 2 265 # define USE_BRK 266 #endif 267 #if defined(__mips__) 268 # ifdef _LP64 269 # define SIZEOF_PTR_2POW 3 270 # define TINY_MIN_2POW 3 271 # else 272 # define SIZEOF_PTR_2POW 2 273 # endif 274 # define QUANTUM_2POW_MIN 4 275 # define USE_BRK 276 #endif 277 #if defined(__riscv__) 278 # ifdef _LP64 279 # define SIZEOF_PTR_2POW 3 280 # define TINY_MIN_2POW 3 281 # else 282 # define SIZEOF_PTR_2POW 2 283 # endif 284 # define QUANTUM_2POW_MIN 4 285 # define USE_BRK 286 #endif 287 #ifdef __hppa__ 288 # define QUANTUM_2POW_MIN 4 289 # define TINY_MIN_2POW 4 290 # define SIZEOF_PTR_2POW 2 291 # define USE_BRK 292 #endif 293 294 #define SIZEOF_PTR (1 << SIZEOF_PTR_2POW) 295 296 /* sizeof(int) == (1 << SIZEOF_INT_2POW). */ 297 #ifndef SIZEOF_INT_2POW 298 # define SIZEOF_INT_2POW 2 299 #endif 300 301 /* 302 * Size and alignment of memory chunks that are allocated by the OS's virtual 303 * memory system. 304 */ 305 #define CHUNK_2POW_DEFAULT 20 306 307 /* 308 * Maximum size of L1 cache line. This is used to avoid cache line aliasing, 309 * so over-estimates are okay (up to a point), but under-estimates will 310 * negatively affect performance. 311 */ 312 #define CACHELINE_2POW 6 313 #define CACHELINE ((size_t)(1 << CACHELINE_2POW)) 314 315 /* Smallest size class to support. */ 316 #ifndef TINY_MIN_2POW 317 #define TINY_MIN_2POW 2 318 #endif 319 320 /* 321 * Maximum size class that is a multiple of the quantum, but not (necessarily) 322 * a power of 2. Above this size, allocations are rounded up to the nearest 323 * power of 2. 324 */ 325 #define SMALL_MAX_2POW_DEFAULT 9 326 #define SMALL_MAX_DEFAULT (1 << SMALL_MAX_2POW_DEFAULT) 327 328 /* 329 * RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized 330 * as small as possible such that this setting is still honored, without 331 * violating other constraints. The goal is to make runs as small as possible 332 * without exceeding a per run external fragmentation threshold. 333 * 334 * We use binary fixed point math for overhead computations, where the binary 335 * point is implicitly RUN_BFP bits to the left. 336 * 337 * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be 338 * honored for some/all object sizes, since there is one bit of header overhead 339 * per object (plus a constant). This constraint is relaxed (ignored) for runs 340 * that are so small that the per-region overhead is greater than: 341 * 342 * (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP)) 343 */ 344 #define RUN_BFP 12 345 /* \/ Implicit binary fixed point. */ 346 #define RUN_MAX_OVRHD 0x0000003dU 347 #define RUN_MAX_OVRHD_RELAX 0x00001800U 348 349 /* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */ 350 #define RUN_MAX_SMALL_2POW 15 351 #define RUN_MAX_SMALL (1 << RUN_MAX_SMALL_2POW) 352 353 /******************************************************************************/ 354 355 #define malloc_mutex_t mutex_t 356 357 /* Set to true once the allocator has been initialized. */ 358 static bool malloc_initialized = false; 359 360 #ifdef _REENTRANT 361 /* Used to avoid initialization races. */ 362 static mutex_t init_lock = MUTEX_INITIALIZER; 363 #endif 364 365 /******************************************************************************/ 366 /* 367 * Statistics data structures. 368 */ 369 370 #ifdef MALLOC_STATS 371 372 typedef struct malloc_bin_stats_s malloc_bin_stats_t; 373 struct malloc_bin_stats_s { 374 /* 375 * Number of allocation requests that corresponded to the size of this 376 * bin. 377 */ 378 uint64_t nrequests; 379 380 /* Total number of runs created for this bin's size class. */ 381 uint64_t nruns; 382 383 /* 384 * Total number of runs reused by extracting them from the runs tree for 385 * this bin's size class. 386 */ 387 uint64_t reruns; 388 389 /* High-water mark for this bin. */ 390 unsigned long highruns; 391 392 /* Current number of runs in this bin. */ 393 unsigned long curruns; 394 }; 395 396 typedef struct arena_stats_s arena_stats_t; 397 struct arena_stats_s { 398 /* Number of bytes currently mapped. */ 399 size_t mapped; 400 401 /* Per-size-category statistics. */ 402 size_t allocated_small; 403 uint64_t nmalloc_small; 404 uint64_t ndalloc_small; 405 406 size_t allocated_large; 407 uint64_t nmalloc_large; 408 uint64_t ndalloc_large; 409 }; 410 411 typedef struct chunk_stats_s chunk_stats_t; 412 struct chunk_stats_s { 413 /* Number of chunks that were allocated. */ 414 uint64_t nchunks; 415 416 /* High-water mark for number of chunks allocated. */ 417 unsigned long highchunks; 418 419 /* 420 * Current number of chunks allocated. This value isn't maintained for 421 * any other purpose, so keep track of it in order to be able to set 422 * highchunks. 423 */ 424 unsigned long curchunks; 425 }; 426 427 #endif /* #ifdef MALLOC_STATS */ 428 429 /******************************************************************************/ 430 /* 431 * Chunk data structures. 432 */ 433 434 /* Tree of chunks. */ 435 typedef struct chunk_node_s chunk_node_t; 436 struct chunk_node_s { 437 /* Linkage for the chunk tree. */ 438 rb_node_t link; 439 440 /* 441 * Pointer to the chunk that this tree node is responsible for. In some 442 * (but certainly not all) cases, this data structure is placed at the 443 * beginning of the corresponding chunk, so this field may point to this 444 * node. 445 */ 446 void *chunk; 447 448 /* Total chunk size. */ 449 size_t size; 450 }; 451 typedef struct chunk_tree_s chunk_tree_t; 452 453 static int chunk_comp(void *, const void *, const void *); 454 455 static const rb_tree_ops_t chunk_tree_ops = { 456 .rbto_compare_nodes = chunk_comp, 457 .rbto_compare_key = chunk_comp, 458 .rbto_node_offset = offsetof(struct chunk_node_s, link), 459 }; 460 461 /******************************************************************************/ 462 /* 463 * Arena data structures. 464 */ 465 466 typedef struct arena_s arena_t; 467 typedef struct arena_bin_s arena_bin_t; 468 469 typedef struct arena_chunk_map_s arena_chunk_map_t; 470 struct arena_chunk_map_s { 471 /* Number of pages in run. */ 472 uint32_t npages; 473 /* 474 * Position within run. For a free run, this is POS_FREE for the first 475 * and last pages. The POS_FREE special value makes it possible to 476 * quickly coalesce free runs. 477 * 478 * This is the limiting factor for chunksize; there can be at most 2^31 479 * pages in a run. 480 */ 481 #define POS_FREE ((uint32_t)0xffffffffU) 482 uint32_t pos; 483 }; 484 485 /* Arena chunk header. */ 486 typedef struct arena_chunk_s arena_chunk_t; 487 struct arena_chunk_s { 488 /* Linkage for the arena's chunk tree. */ 489 rb_node_t link; 490 491 /* Arena that owns the chunk. */ 492 arena_t *arena; 493 494 /* 495 * Number of pages in use. This is maintained in order to make 496 * detection of empty chunks fast. 497 */ 498 uint32_t pages_used; 499 500 /* 501 * Every time a free run larger than this value is created/coalesced, 502 * this value is increased. The only way that the value decreases is if 503 * arena_run_alloc() fails to find a free run as large as advertised by 504 * this value. 505 */ 506 uint32_t max_frun_npages; 507 508 /* 509 * Every time a free run that starts at an earlier page than this value 510 * is created/coalesced, this value is decreased. It is reset in a 511 * similar fashion to max_frun_npages. 512 */ 513 uint32_t min_frun_ind; 514 515 /* 516 * Map of pages within chunk that keeps track of free/large/small. For 517 * free runs, only the map entries for the first and last pages are 518 * kept up to date, so that free runs can be quickly coalesced. 519 */ 520 arena_chunk_map_t map[1]; /* Dynamically sized. */ 521 }; 522 typedef struct arena_chunk_tree_s arena_chunk_tree_t; 523 524 static int arena_chunk_comp(void *, const void *, const void *); 525 526 static const rb_tree_ops_t arena_chunk_tree_ops = { 527 .rbto_compare_nodes = arena_chunk_comp, 528 .rbto_compare_key = arena_chunk_comp, 529 .rbto_node_offset = offsetof(struct arena_chunk_s, link), 530 }; 531 532 typedef struct arena_run_s arena_run_t; 533 struct arena_run_s { 534 /* Linkage for run trees. */ 535 rb_node_t link; 536 537 #ifdef MALLOC_DEBUG 538 uint32_t magic; 539 # define ARENA_RUN_MAGIC 0x384adf93 540 #endif 541 542 /* Bin this run is associated with. */ 543 arena_bin_t *bin; 544 545 /* Index of first element that might have a free region. */ 546 unsigned regs_minelm; 547 548 /* Number of free regions in run. */ 549 unsigned nfree; 550 551 /* Bitmask of in-use regions (0: in use, 1: free). */ 552 unsigned regs_mask[1]; /* Dynamically sized. */ 553 }; 554 typedef struct arena_run_tree_s arena_run_tree_t; 555 556 static int arena_run_comp(void *, const void *, const void *); 557 558 static const rb_tree_ops_t arena_run_tree_ops = { 559 .rbto_compare_nodes = arena_run_comp, 560 .rbto_compare_key = arena_run_comp, 561 .rbto_node_offset = offsetof(struct arena_run_s, link), 562 }; 563 564 struct arena_bin_s { 565 /* 566 * Current run being used to service allocations of this bin's size 567 * class. 568 */ 569 arena_run_t *runcur; 570 571 /* 572 * Tree of non-full runs. This tree is used when looking for an 573 * existing run when runcur is no longer usable. We choose the 574 * non-full run that is lowest in memory; this policy tends to keep 575 * objects packed well, and it can also help reduce the number of 576 * almost-empty chunks. 577 */ 578 rb_tree_t runs; 579 580 /* Size of regions in a run for this bin's size class. */ 581 size_t reg_size; 582 583 /* Total size of a run for this bin's size class. */ 584 size_t run_size; 585 586 /* Total number of regions in a run for this bin's size class. */ 587 uint32_t nregs; 588 589 /* Number of elements in a run's regs_mask for this bin's size class. */ 590 uint32_t regs_mask_nelms; 591 592 /* Offset of first region in a run for this bin's size class. */ 593 uint32_t reg0_offset; 594 595 #ifdef MALLOC_STATS 596 /* Bin statistics. */ 597 malloc_bin_stats_t stats; 598 #endif 599 }; 600 601 struct arena_s { 602 #ifdef MALLOC_DEBUG 603 uint32_t magic; 604 # define ARENA_MAGIC 0x947d3d24 605 #endif 606 607 /* All operations on this arena require that mtx be locked. */ 608 malloc_mutex_t mtx; 609 610 #ifdef MALLOC_STATS 611 arena_stats_t stats; 612 #endif 613 614 /* 615 * Tree of chunks this arena manages. 616 */ 617 rb_tree_t chunks; 618 619 /* 620 * In order to avoid rapid chunk allocation/deallocation when an arena 621 * oscillates right on the cusp of needing a new chunk, cache the most 622 * recently freed chunk. This caching is disabled by opt_hint. 623 * 624 * There is one spare chunk per arena, rather than one spare total, in 625 * order to avoid interactions between multiple threads that could make 626 * a single spare inadequate. 627 */ 628 arena_chunk_t *spare; 629 630 /* 631 * bins is used to store rings of free regions of the following sizes, 632 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS. 633 * 634 * bins[i] | size | 635 * --------+------+ 636 * 0 | 2 | 637 * 1 | 4 | 638 * 2 | 8 | 639 * --------+------+ 640 * 3 | 16 | 641 * 4 | 32 | 642 * 5 | 48 | 643 * 6 | 64 | 644 * : : 645 * : : 646 * 33 | 496 | 647 * 34 | 512 | 648 * --------+------+ 649 * 35 | 1024 | 650 * 36 | 2048 | 651 * --------+------+ 652 */ 653 arena_bin_t bins[1]; /* Dynamically sized. */ 654 }; 655 656 /******************************************************************************/ 657 /* 658 * Data. 659 */ 660 661 /* Number of CPUs. */ 662 static unsigned ncpus; 663 664 /* VM page size. */ 665 static size_t pagesize; 666 static size_t pagesize_mask; 667 static int pagesize_2pow; 668 669 /* Various bin-related settings. */ 670 static size_t bin_maxclass; /* Max size class for bins. */ 671 static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */ 672 static unsigned nqbins; /* Number of quantum-spaced bins. */ 673 static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */ 674 static size_t small_min; 675 static size_t small_max; 676 677 /* Various quantum-related settings. */ 678 static size_t quantum; 679 static size_t quantum_mask; /* (quantum - 1). */ 680 681 /* Various chunk-related settings. */ 682 static size_t chunksize; 683 static size_t chunksize_mask; /* (chunksize - 1). */ 684 static int chunksize_2pow; 685 static unsigned chunk_npages; 686 static unsigned arena_chunk_header_npages; 687 static size_t arena_maxclass; /* Max size class for arenas. */ 688 689 /********/ 690 /* 691 * Chunks. 692 */ 693 694 #ifdef _REENTRANT 695 /* Protects chunk-related data structures. */ 696 static malloc_mutex_t chunks_mtx; 697 #endif 698 699 /* Tree of chunks that are stand-alone huge allocations. */ 700 static rb_tree_t huge; 701 702 #ifdef USE_BRK 703 /* 704 * Try to use brk for chunk-size allocations, due to address space constraints. 705 */ 706 /* 707 * Protects sbrk() calls. This must be separate from chunks_mtx, since 708 * base_pages_alloc() also uses sbrk(), but cannot lock chunks_mtx (doing so 709 * could cause recursive lock acquisition). 710 */ 711 #ifdef _REENTRANT 712 static malloc_mutex_t brk_mtx; 713 #endif 714 /* Result of first sbrk(0) call. */ 715 static void *brk_base; 716 /* Current end of brk, or ((void *)-1) if brk is exhausted. */ 717 static void *brk_prev; 718 /* Current upper limit on brk addresses. */ 719 static void *brk_max; 720 #endif 721 722 #ifdef MALLOC_STATS 723 /* Huge allocation statistics. */ 724 static uint64_t huge_nmalloc; 725 static uint64_t huge_ndalloc; 726 static uint64_t huge_nralloc; 727 static size_t huge_allocated; 728 #endif 729 730 /* 731 * Tree of chunks that were previously allocated. This is used when allocating 732 * chunks, in an attempt to re-use address space. 733 */ 734 static rb_tree_t old_chunks; 735 736 /****************************/ 737 /* 738 * base (internal allocation). 739 */ 740 741 /* 742 * Current pages that are being used for internal memory allocations. These 743 * pages are carved up in cacheline-size quanta, so that there is no chance of 744 * false cache line sharing. 745 */ 746 static void *base_pages; 747 static void *base_next_addr; 748 static void *base_past_addr; /* Addr immediately past base_pages. */ 749 static chunk_node_t *base_chunk_nodes; /* LIFO cache of chunk nodes. */ 750 #ifdef _REENTRANT 751 static malloc_mutex_t base_mtx; 752 #endif 753 #ifdef MALLOC_STATS 754 static size_t base_mapped; 755 #endif 756 757 /********/ 758 /* 759 * Arenas. 760 */ 761 762 /* 763 * Arenas that are used to service external requests. Not all elements of the 764 * arenas array are necessarily used; arenas are created lazily as needed. 765 */ 766 static arena_t **arenas; 767 #ifdef _REENTRANT 768 static malloc_mutex_t arenas_mtx; /* Protects arenas initialization. */ 769 #endif 770 771 #ifdef MALLOC_STATS 772 /* Chunk statistics. */ 773 static chunk_stats_t stats_chunks; 774 #endif 775 776 /*******************************/ 777 /* 778 * Runtime configuration options. 779 */ 780 const char *_malloc_options; 781 782 #ifndef MALLOC_PRODUCTION 783 static bool opt_abort = true; 784 static bool opt_junk = true; 785 #else 786 static bool opt_abort = false; 787 static bool opt_junk = false; 788 #endif 789 static bool opt_hint = false; 790 static bool opt_print_stats = false; 791 static int opt_quantum_2pow = QUANTUM_2POW_MIN; 792 static int opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT; 793 static int opt_chunk_2pow = CHUNK_2POW_DEFAULT; 794 static bool opt_utrace = false; 795 static bool opt_sysv = false; 796 static bool opt_xmalloc = false; 797 static bool opt_zero = false; 798 799 typedef struct { 800 void *p; 801 size_t s; 802 void *r; 803 } malloc_utrace_t; 804 805 /* Sprinkle branch hints for the compiler and CPU. */ 806 #define OPT(a) __predict_false(opt_##a) 807 #define NOT_OPT(a) __predict_true(!opt_##a) 808 809 /* Trace malloc/free for ktrace/kdump. */ 810 #define UTRACE(a, b, c) \ 811 if (OPT(utrace)) { \ 812 malloc_utrace_t ut; \ 813 ut.p = a; \ 814 ut.s = b; \ 815 ut.r = c; \ 816 utrace("malloc", &ut, sizeof(ut)); \ 817 } 818 819 /******************************************************************************/ 820 /* 821 * Begin function prototypes for non-inline static functions. 822 */ 823 824 static void wrtmessage(const char *p1, const char *p2, const char *p3, 825 const char *p4); 826 #ifdef MALLOC_STATS 827 static void malloc_printf(const char *format, ...); 828 #endif 829 static char *size_t2s(size_t x, char *s); 830 static bool base_pages_alloc(size_t minsize); 831 static void *base_alloc(size_t size); 832 static chunk_node_t *base_chunk_node_alloc(void); 833 static void base_chunk_node_dealloc(chunk_node_t *node); 834 #ifdef MALLOC_STATS 835 static void stats_print(arena_t *arena); 836 #endif 837 static void *pages_map(void *addr, size_t size); 838 static void *pages_map_align(void *addr, size_t size, int align); 839 static void pages_unmap(void *addr, size_t size); 840 static void *chunk_alloc(size_t size); 841 static void chunk_dealloc(void *chunk, size_t size); 842 static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size); 843 static arena_chunk_t *arena_chunk_alloc(arena_t *arena); 844 static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk); 845 static arena_run_t *arena_run_alloc(arena_t *arena, size_t size); 846 static void arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size); 847 static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin); 848 static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin); 849 static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size); 850 static void *arena_malloc(arena_t *arena, size_t size); 851 static void *arena_palloc(arena_t *arena, size_t alignment, size_t size, 852 size_t alloc_size); 853 static size_t arena_salloc(const void *ptr); 854 static void *arena_ralloc(void *ptr, size_t size, size_t oldsize); 855 static void arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr); 856 static void arena_new(arena_t *arena); 857 static arena_t *arenas_extend(void); 858 static void *huge_malloc(size_t size); 859 static void *huge_palloc(size_t alignment, size_t size); 860 static void *huge_ralloc(void *ptr, size_t size, size_t oldsize); 861 static void huge_dalloc(void *ptr); 862 static void *imalloc(size_t size); 863 static void *ipalloc(size_t alignment, size_t size); 864 static void *icalloc(size_t size); 865 static size_t isalloc(const void *ptr); 866 static void *iralloc(void *ptr, size_t size); 867 static void idalloc(void *ptr); 868 static void malloc_print_stats(void); 869 static bool malloc_init_hard(void); 870 871 /* 872 * End function prototypes. 873 */ 874 /******************************************************************************/ 875 /* 876 * Begin mutex. 877 */ 878 879 #define malloc_mutex_init(m) mutex_init(m, NULL) 880 #define malloc_mutex_lock(m) mutex_lock(m) 881 #define malloc_mutex_unlock(m) mutex_unlock(m) 882 883 /* 884 * End mutex. 885 */ 886 /******************************************************************************/ 887 /* 888 * Begin Utility functions/macros. 889 */ 890 891 /* Return the chunk address for allocation address a. */ 892 #define CHUNK_ADDR2BASE(a) \ 893 ((void *)((uintptr_t)(a) & ~chunksize_mask)) 894 895 /* Return the chunk offset of address a. */ 896 #define CHUNK_ADDR2OFFSET(a) \ 897 ((size_t)((uintptr_t)(a) & chunksize_mask)) 898 899 /* Return the smallest chunk multiple that is >= s. */ 900 #define CHUNK_CEILING(s) \ 901 (((s) + chunksize_mask) & ~chunksize_mask) 902 903 /* Return the smallest cacheline multiple that is >= s. */ 904 #define CACHELINE_CEILING(s) \ 905 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1)) 906 907 /* Return the smallest quantum multiple that is >= a. */ 908 #define QUANTUM_CEILING(a) \ 909 (((a) + quantum_mask) & ~quantum_mask) 910 911 /* Return the smallest pagesize multiple that is >= s. */ 912 #define PAGE_CEILING(s) \ 913 (((s) + pagesize_mask) & ~pagesize_mask) 914 915 /* Compute the smallest power of 2 that is >= x. */ 916 static inline size_t 917 pow2_ceil(size_t x) 918 { 919 920 x--; 921 x |= x >> 1; 922 x |= x >> 2; 923 x |= x >> 4; 924 x |= x >> 8; 925 x |= x >> 16; 926 #if (SIZEOF_PTR == 8) 927 x |= x >> 32; 928 #endif 929 x++; 930 return (x); 931 } 932 933 static void 934 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4) 935 { 936 937 write(STDERR_FILENO, p1, strlen(p1)); 938 write(STDERR_FILENO, p2, strlen(p2)); 939 write(STDERR_FILENO, p3, strlen(p3)); 940 write(STDERR_FILENO, p4, strlen(p4)); 941 } 942 943 void (*_malloc_message)(const char *p1, const char *p2, const char *p3, 944 const char *p4) = wrtmessage; 945 946 #ifdef MALLOC_STATS 947 /* 948 * Print to stderr in such a way as to (hopefully) avoid memory allocation. 949 */ 950 static void 951 malloc_printf(const char *format, ...) 952 { 953 char buf[4096]; 954 va_list ap; 955 956 va_start(ap, format); 957 vsnprintf(buf, sizeof(buf), format, ap); 958 va_end(ap); 959 _malloc_message(buf, "", "", ""); 960 } 961 #endif 962 963 /* 964 * We don't want to depend on vsnprintf() for production builds, since that can 965 * cause unnecessary bloat for static binaries. size_t2s() provides minimal 966 * integer printing functionality, so that malloc_printf() use can be limited to 967 * MALLOC_STATS code. 968 */ 969 #define UMAX2S_BUFSIZE 21 970 static char * 971 size_t2s(size_t x, char *s) 972 { 973 unsigned i; 974 975 /* Make sure UMAX2S_BUFSIZE is large enough. */ 976 /* LINTED */ 977 assert(sizeof(size_t) <= 8); 978 979 i = UMAX2S_BUFSIZE - 1; 980 s[i] = '\0'; 981 do { 982 i--; 983 s[i] = "0123456789"[(int)x % 10]; 984 x /= (uintmax_t)10LL; 985 } while (x > 0); 986 987 return (&s[i]); 988 } 989 990 /******************************************************************************/ 991 992 static bool 993 base_pages_alloc(size_t minsize) 994 { 995 size_t csize = 0; 996 997 #ifdef USE_BRK 998 /* 999 * Do special brk allocation here, since base allocations don't need to 1000 * be chunk-aligned. 1001 */ 1002 if (brk_prev != (void *)-1) { 1003 void *brk_cur; 1004 intptr_t incr; 1005 1006 if (minsize != 0) 1007 csize = CHUNK_CEILING(minsize); 1008 1009 malloc_mutex_lock(&brk_mtx); 1010 do { 1011 /* Get the current end of brk. */ 1012 brk_cur = sbrk(0); 1013 1014 /* 1015 * Calculate how much padding is necessary to 1016 * chunk-align the end of brk. Don't worry about 1017 * brk_cur not being chunk-aligned though. 1018 */ 1019 incr = (intptr_t)chunksize 1020 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur); 1021 assert(incr >= 0); 1022 if ((size_t)incr < minsize) 1023 incr += csize; 1024 1025 brk_prev = sbrk(incr); 1026 if (brk_prev == brk_cur) { 1027 /* Success. */ 1028 malloc_mutex_unlock(&brk_mtx); 1029 base_pages = brk_cur; 1030 base_next_addr = base_pages; 1031 base_past_addr = (void *)((uintptr_t)base_pages 1032 + incr); 1033 #ifdef MALLOC_STATS 1034 base_mapped += incr; 1035 #endif 1036 return (false); 1037 } 1038 } while (brk_prev != (void *)-1); 1039 malloc_mutex_unlock(&brk_mtx); 1040 } 1041 if (minsize == 0) { 1042 /* 1043 * Failure during initialization doesn't matter, so avoid 1044 * falling through to the mmap-based page mapping code. 1045 */ 1046 return (true); 1047 } 1048 #endif 1049 assert(minsize != 0); 1050 csize = PAGE_CEILING(minsize); 1051 base_pages = pages_map(NULL, csize); 1052 if (base_pages == NULL) 1053 return (true); 1054 base_next_addr = base_pages; 1055 base_past_addr = (void *)((uintptr_t)base_pages + csize); 1056 #ifdef MALLOC_STATS 1057 base_mapped += csize; 1058 #endif 1059 return (false); 1060 } 1061 1062 static void * 1063 base_alloc(size_t size) 1064 { 1065 void *ret; 1066 size_t csize; 1067 1068 /* Round size up to nearest multiple of the cacheline size. */ 1069 csize = CACHELINE_CEILING(size); 1070 1071 malloc_mutex_lock(&base_mtx); 1072 1073 /* Make sure there's enough space for the allocation. */ 1074 if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) { 1075 if (base_pages_alloc(csize)) { 1076 ret = NULL; 1077 goto RETURN; 1078 } 1079 } 1080 1081 /* Allocate. */ 1082 ret = base_next_addr; 1083 base_next_addr = (void *)((uintptr_t)base_next_addr + csize); 1084 1085 RETURN: 1086 malloc_mutex_unlock(&base_mtx); 1087 return (ret); 1088 } 1089 1090 static chunk_node_t * 1091 base_chunk_node_alloc(void) 1092 { 1093 chunk_node_t *ret; 1094 1095 malloc_mutex_lock(&base_mtx); 1096 if (base_chunk_nodes != NULL) { 1097 ret = base_chunk_nodes; 1098 /* LINTED */ 1099 base_chunk_nodes = *(chunk_node_t **)ret; 1100 malloc_mutex_unlock(&base_mtx); 1101 } else { 1102 malloc_mutex_unlock(&base_mtx); 1103 ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t)); 1104 } 1105 1106 return (ret); 1107 } 1108 1109 static void 1110 base_chunk_node_dealloc(chunk_node_t *node) 1111 { 1112 1113 malloc_mutex_lock(&base_mtx); 1114 /* LINTED */ 1115 *(chunk_node_t **)node = base_chunk_nodes; 1116 base_chunk_nodes = node; 1117 malloc_mutex_unlock(&base_mtx); 1118 } 1119 1120 /******************************************************************************/ 1121 1122 #ifdef MALLOC_STATS 1123 static void 1124 stats_print(arena_t *arena) 1125 { 1126 const unsigned minusone = (unsigned)-1; 1127 unsigned i, gap_start; 1128 1129 malloc_printf( 1130 " allocated/mapped nmalloc ndalloc\n"); 1131 1132 malloc_printf("small: %12zu %-12s %12llu %12llu\n", 1133 arena->stats.allocated_small, "", arena->stats.nmalloc_small, 1134 arena->stats.ndalloc_small); 1135 malloc_printf("large: %12zu %-12s %12llu %12llu\n", 1136 arena->stats.allocated_large, "", arena->stats.nmalloc_large, 1137 arena->stats.ndalloc_large); 1138 malloc_printf("total: %12zu/%-12zu %12llu %12llu\n", 1139 arena->stats.allocated_small + arena->stats.allocated_large, 1140 arena->stats.mapped, 1141 arena->stats.nmalloc_small + arena->stats.nmalloc_large, 1142 arena->stats.ndalloc_small + arena->stats.ndalloc_large); 1143 1144 malloc_printf("bins: bin size regs pgs requests newruns" 1145 " reruns maxruns curruns\n"); 1146 for (i = 0, gap_start = minusone; i < ntbins + nqbins + nsbins; i++) { 1147 if (arena->bins[i].stats.nrequests == 0) { 1148 if (gap_start == minusone) 1149 gap_start = i; 1150 } else { 1151 if (gap_start != minusone) { 1152 if (i > gap_start + 1) { 1153 /* Gap of more than one size class. */ 1154 malloc_printf("[%u..%u]\n", 1155 gap_start, i - 1); 1156 } else { 1157 /* Gap of one size class. */ 1158 malloc_printf("[%u]\n", gap_start); 1159 } 1160 gap_start = minusone; 1161 } 1162 malloc_printf( 1163 "%13u %1s %4u %4u %3u %9llu %9llu" 1164 " %9llu %7lu %7lu\n", 1165 i, 1166 i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S", 1167 arena->bins[i].reg_size, 1168 arena->bins[i].nregs, 1169 arena->bins[i].run_size >> pagesize_2pow, 1170 arena->bins[i].stats.nrequests, 1171 arena->bins[i].stats.nruns, 1172 arena->bins[i].stats.reruns, 1173 arena->bins[i].stats.highruns, 1174 arena->bins[i].stats.curruns); 1175 } 1176 } 1177 if (gap_start != minusone) { 1178 if (i > gap_start + 1) { 1179 /* Gap of more than one size class. */ 1180 malloc_printf("[%u..%u]\n", gap_start, i - 1); 1181 } else { 1182 /* Gap of one size class. */ 1183 malloc_printf("[%u]\n", gap_start); 1184 } 1185 } 1186 } 1187 #endif 1188 1189 /* 1190 * End Utility functions/macros. 1191 */ 1192 /******************************************************************************/ 1193 /* 1194 * Begin chunk management functions. 1195 */ 1196 1197 static int 1198 chunk_comp(void *context, const void *va, const void *vb) 1199 { 1200 const chunk_node_t *a = va, *b = vb; 1201 1202 assert(a != NULL); 1203 assert(b != NULL); 1204 1205 return ptrcmp(a->chunk, b->chunk); 1206 } 1207 1208 static void * 1209 pages_map_align(void *addr, size_t size, int align) 1210 { 1211 void *ret; 1212 1213 /* 1214 * We don't use MAP_FIXED here, because it can cause the *replacement* 1215 * of existing mappings, and we only want to create new mappings. 1216 */ 1217 ret = mmap(addr, size, PROT_READ | PROT_WRITE, 1218 MAP_PRIVATE | MAP_ANON | MAP_ALIGNED(align), -1, 0); 1219 assert(ret != NULL); 1220 1221 if (ret == MAP_FAILED) 1222 ret = NULL; 1223 else if (addr != NULL && ret != addr) { 1224 /* 1225 * We succeeded in mapping memory, but not in the right place. 1226 */ 1227 if (munmap(ret, size) == -1) { 1228 char buf[STRERROR_BUF]; 1229 1230 STRERROR_R(errno, buf, sizeof(buf)); 1231 _malloc_message(getprogname(), 1232 ": (malloc) Error in munmap(): ", buf, "\n"); 1233 if (OPT(abort)) 1234 abort(); 1235 } 1236 ret = NULL; 1237 } 1238 1239 assert(ret == NULL || (addr == NULL && ret != addr) 1240 || (addr != NULL && ret == addr)); 1241 return (ret); 1242 } 1243 1244 static void * 1245 pages_map(void *addr, size_t size) 1246 { 1247 1248 return pages_map_align(addr, size, 0); 1249 } 1250 1251 static void 1252 pages_unmap(void *addr, size_t size) 1253 { 1254 1255 if (munmap(addr, size) == -1) { 1256 char buf[STRERROR_BUF]; 1257 1258 STRERROR_R(errno, buf, sizeof(buf)); 1259 _malloc_message(getprogname(), 1260 ": (malloc) Error in munmap(): ", buf, "\n"); 1261 if (OPT(abort)) 1262 abort(); 1263 } 1264 } 1265 1266 static void * 1267 chunk_alloc(size_t size) 1268 { 1269 void *ret, *chunk; 1270 chunk_node_t *tchunk, *delchunk; 1271 1272 assert(size != 0); 1273 assert((size & chunksize_mask) == 0); 1274 1275 malloc_mutex_lock(&chunks_mtx); 1276 1277 if (size == chunksize) { 1278 /* 1279 * Check for address ranges that were previously chunks and try 1280 * to use them. 1281 */ 1282 1283 tchunk = RB_TREE_MIN(&old_chunks); 1284 while (tchunk != NULL) { 1285 /* Found an address range. Try to recycle it. */ 1286 1287 chunk = tchunk->chunk; 1288 delchunk = tchunk; 1289 tchunk = RB_TREE_NEXT(&old_chunks, delchunk); 1290 1291 /* Remove delchunk from the tree. */ 1292 rb_tree_remove_node(&old_chunks, delchunk); 1293 base_chunk_node_dealloc(delchunk); 1294 1295 #ifdef USE_BRK 1296 if ((uintptr_t)chunk >= (uintptr_t)brk_base 1297 && (uintptr_t)chunk < (uintptr_t)brk_max) { 1298 /* Re-use a previously freed brk chunk. */ 1299 ret = chunk; 1300 goto RETURN; 1301 } 1302 #endif 1303 if ((ret = pages_map(chunk, size)) != NULL) { 1304 /* Success. */ 1305 goto RETURN; 1306 } 1307 } 1308 } 1309 1310 /* 1311 * Try to over-allocate, but allow the OS to place the allocation 1312 * anywhere. Beware of size_t wrap-around. 1313 */ 1314 if (size + chunksize > size) { 1315 if ((ret = pages_map_align(NULL, size, chunksize_2pow)) 1316 != NULL) { 1317 goto RETURN; 1318 } 1319 } 1320 1321 #ifdef USE_BRK 1322 /* 1323 * Try to create allocations in brk, in order to make full use of 1324 * limited address space. 1325 */ 1326 if (brk_prev != (void *)-1) { 1327 void *brk_cur; 1328 intptr_t incr; 1329 1330 /* 1331 * The loop is necessary to recover from races with other 1332 * threads that are using brk for something other than malloc. 1333 */ 1334 malloc_mutex_lock(&brk_mtx); 1335 do { 1336 /* Get the current end of brk. */ 1337 brk_cur = sbrk(0); 1338 1339 /* 1340 * Calculate how much padding is necessary to 1341 * chunk-align the end of brk. 1342 */ 1343 incr = (intptr_t)size 1344 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur); 1345 if (incr == (intptr_t)size) { 1346 ret = brk_cur; 1347 } else { 1348 ret = (void *)((intptr_t)brk_cur + incr); 1349 incr += size; 1350 } 1351 1352 brk_prev = sbrk(incr); 1353 if (brk_prev == brk_cur) { 1354 /* Success. */ 1355 malloc_mutex_unlock(&brk_mtx); 1356 brk_max = (void *)((intptr_t)ret + size); 1357 goto RETURN; 1358 } 1359 } while (brk_prev != (void *)-1); 1360 malloc_mutex_unlock(&brk_mtx); 1361 } 1362 #endif 1363 1364 /* All strategies for allocation failed. */ 1365 ret = NULL; 1366 RETURN: 1367 if (ret != NULL) { 1368 chunk_node_t key; 1369 /* 1370 * Clean out any entries in old_chunks that overlap with the 1371 * memory we just allocated. 1372 */ 1373 key.chunk = ret; 1374 tchunk = rb_tree_find_node_geq(&old_chunks, &key); 1375 while (tchunk != NULL 1376 && (uintptr_t)tchunk->chunk >= (uintptr_t)ret 1377 && (uintptr_t)tchunk->chunk < (uintptr_t)ret + size) { 1378 delchunk = tchunk; 1379 tchunk = RB_TREE_NEXT(&old_chunks, delchunk); 1380 rb_tree_remove_node(&old_chunks, delchunk); 1381 base_chunk_node_dealloc(delchunk); 1382 } 1383 1384 } 1385 #ifdef MALLOC_STATS 1386 if (ret != NULL) { 1387 stats_chunks.nchunks += (size / chunksize); 1388 stats_chunks.curchunks += (size / chunksize); 1389 } 1390 if (stats_chunks.curchunks > stats_chunks.highchunks) 1391 stats_chunks.highchunks = stats_chunks.curchunks; 1392 #endif 1393 malloc_mutex_unlock(&chunks_mtx); 1394 1395 assert(CHUNK_ADDR2BASE(ret) == ret); 1396 return (ret); 1397 } 1398 1399 static void 1400 chunk_dealloc(void *chunk, size_t size) 1401 { 1402 chunk_node_t *node; 1403 1404 assert(chunk != NULL); 1405 assert(CHUNK_ADDR2BASE(chunk) == chunk); 1406 assert(size != 0); 1407 assert((size & chunksize_mask) == 0); 1408 1409 malloc_mutex_lock(&chunks_mtx); 1410 1411 #ifdef USE_BRK 1412 if ((uintptr_t)chunk >= (uintptr_t)brk_base 1413 && (uintptr_t)chunk < (uintptr_t)brk_max) { 1414 void *brk_cur; 1415 1416 malloc_mutex_lock(&brk_mtx); 1417 /* Get the current end of brk. */ 1418 brk_cur = sbrk(0); 1419 1420 /* 1421 * Try to shrink the data segment if this chunk is at the end 1422 * of the data segment. The sbrk() call here is subject to a 1423 * race condition with threads that use brk(2) or sbrk(2) 1424 * directly, but the alternative would be to leak memory for 1425 * the sake of poorly designed multi-threaded programs. 1426 */ 1427 if (brk_cur == brk_max 1428 && (void *)((uintptr_t)chunk + size) == brk_max 1429 && sbrk(-(intptr_t)size) == brk_max) { 1430 malloc_mutex_unlock(&brk_mtx); 1431 if (brk_prev == brk_max) { 1432 /* Success. */ 1433 brk_prev = (void *)((intptr_t)brk_max 1434 - (intptr_t)size); 1435 brk_max = brk_prev; 1436 } 1437 } else { 1438 size_t offset; 1439 1440 malloc_mutex_unlock(&brk_mtx); 1441 madvise(chunk, size, MADV_FREE); 1442 1443 /* 1444 * Iteratively create records of each chunk-sized 1445 * memory region that 'chunk' is comprised of, so that 1446 * the address range can be recycled if memory usage 1447 * increases later on. 1448 */ 1449 for (offset = 0; offset < size; offset += chunksize) { 1450 node = base_chunk_node_alloc(); 1451 if (node == NULL) 1452 break; 1453 1454 node->chunk = (void *)((uintptr_t)chunk 1455 + (uintptr_t)offset); 1456 node->size = chunksize; 1457 rb_tree_insert_node(&old_chunks, node); 1458 } 1459 } 1460 } else { 1461 #endif 1462 pages_unmap(chunk, size); 1463 1464 /* 1465 * Make a record of the chunk's address, so that the address 1466 * range can be recycled if memory usage increases later on. 1467 * Don't bother to create entries if (size > chunksize), since 1468 * doing so could cause scalability issues for truly gargantuan 1469 * objects (many gigabytes or larger). 1470 */ 1471 if (size == chunksize) { 1472 node = base_chunk_node_alloc(); 1473 if (node != NULL) { 1474 node->chunk = (void *)(uintptr_t)chunk; 1475 node->size = chunksize; 1476 rb_tree_insert_node(&old_chunks, node); 1477 } 1478 } 1479 #ifdef USE_BRK 1480 } 1481 #endif 1482 1483 #ifdef MALLOC_STATS 1484 stats_chunks.curchunks -= (size / chunksize); 1485 #endif 1486 malloc_mutex_unlock(&chunks_mtx); 1487 } 1488 1489 /* 1490 * End chunk management functions. 1491 */ 1492 /******************************************************************************/ 1493 /* 1494 * Begin arena. 1495 */ 1496 1497 /* 1498 * Choose a per-CPU arena. 1499 */ 1500 static __noinline arena_t * 1501 choose_arena_hard(void) 1502 { 1503 1504 assert(arenas[0] != NULL); 1505 1506 malloc_mutex_lock(&arenas_mtx); 1507 for (unsigned i = 1; i < ncpus; i++) 1508 if (arenas[i] == NULL) 1509 arenas[i] = arenas_extend(); 1510 malloc_mutex_unlock(&arenas_mtx); 1511 1512 return arenas[thr_curcpu()]; 1513 } 1514 1515 static inline arena_t * 1516 choose_arena(void) 1517 { 1518 arena_t *arena; 1519 1520 /* NB: when libpthread is absent, thr_curcpu() always returns zero. */ 1521 arena = arenas[thr_curcpu()]; 1522 if (__predict_true(arena != NULL)) 1523 return arena; 1524 1525 return choose_arena_hard(); 1526 } 1527 1528 static int 1529 arena_chunk_comp(void *context, const void *va, const void *vb) 1530 { 1531 const arena_chunk_t *a = va, *b = vb; 1532 int diff; 1533 1534 assert(a != NULL); 1535 assert(b != NULL); 1536 1537 if ((diff = a->max_frun_npages - b->max_frun_npages) != 0) 1538 return diff; 1539 return ptrcmp(a, b); 1540 } 1541 1542 static int 1543 arena_run_comp(void *context, const void *a, const void *b) 1544 { 1545 1546 assert(a != NULL); 1547 assert(b != NULL); 1548 1549 return ptrcmp(a, b); 1550 } 1551 1552 static inline void * 1553 arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin) 1554 { 1555 void *ret; 1556 unsigned i, mask, bit, regind; 1557 1558 assert(run->magic == ARENA_RUN_MAGIC); 1559 assert(run->regs_minelm < bin->regs_mask_nelms); 1560 1561 /* 1562 * Move the first check outside the loop, so that run->regs_minelm can 1563 * be updated unconditionally, without the possibility of updating it 1564 * multiple times. 1565 */ 1566 i = run->regs_minelm; 1567 mask = run->regs_mask[i]; 1568 if (mask != 0) { 1569 /* Usable allocation found. */ 1570 bit = ffs((int)mask) - 1; 1571 1572 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit); 1573 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 1574 + (bin->reg_size * regind)); 1575 1576 /* Clear bit. */ 1577 mask ^= (1U << bit); 1578 run->regs_mask[i] = mask; 1579 1580 return (ret); 1581 } 1582 1583 for (i++; i < bin->regs_mask_nelms; i++) { 1584 mask = run->regs_mask[i]; 1585 if (mask != 0) { 1586 /* Usable allocation found. */ 1587 bit = ffs((int)mask) - 1; 1588 1589 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit); 1590 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 1591 + (bin->reg_size * regind)); 1592 1593 /* Clear bit. */ 1594 mask ^= (1U << bit); 1595 run->regs_mask[i] = mask; 1596 1597 /* 1598 * Make a note that nothing before this element 1599 * contains a free region. 1600 */ 1601 run->regs_minelm = i; /* Low payoff: + (mask == 0); */ 1602 1603 return (ret); 1604 } 1605 } 1606 /* Not reached. */ 1607 /* LINTED */ 1608 assert(0); 1609 return (NULL); 1610 } 1611 1612 static inline void 1613 arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size) 1614 { 1615 /* 1616 * To divide by a number D that is not a power of two we multiply 1617 * by (2^21 / D) and then right shift by 21 positions. 1618 * 1619 * X / D 1620 * 1621 * becomes 1622 * 1623 * (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT 1624 */ 1625 #define SIZE_INV_SHIFT 21 1626 #define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1) 1627 static const unsigned size_invs[] = { 1628 SIZE_INV(3), 1629 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7), 1630 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11), 1631 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15), 1632 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19), 1633 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23), 1634 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27), 1635 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31) 1636 #if (QUANTUM_2POW_MIN < 4) 1637 , 1638 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35), 1639 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39), 1640 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43), 1641 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47), 1642 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51), 1643 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55), 1644 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59), 1645 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63) 1646 #endif 1647 }; 1648 unsigned diff, regind, elm, bit; 1649 1650 /* LINTED */ 1651 assert(run->magic == ARENA_RUN_MAGIC); 1652 assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3 1653 >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN)); 1654 1655 /* 1656 * Avoid doing division with a variable divisor if possible. Using 1657 * actual division here can reduce allocator throughput by over 20%! 1658 */ 1659 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset); 1660 if ((size & (size - 1)) == 0) { 1661 /* 1662 * log2_table allows fast division of a power of two in the 1663 * [1..128] range. 1664 * 1665 * (x / divisor) becomes (x >> log2_table[divisor - 1]). 1666 */ 1667 static const unsigned char log2_table[] = { 1668 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 1669 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 1670 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1671 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 1672 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1673 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1674 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1675 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7 1676 }; 1677 1678 if (size <= 128) 1679 regind = (diff >> log2_table[size - 1]); 1680 else if (size <= 32768) 1681 regind = diff >> (8 + log2_table[(size >> 8) - 1]); 1682 else { 1683 /* 1684 * The page size is too large for us to use the lookup 1685 * table. Use real division. 1686 */ 1687 regind = (unsigned)(diff / size); 1688 } 1689 } else if (size <= (((sizeof(size_invs) / sizeof(unsigned)) + 2) 1690 << QUANTUM_2POW_MIN)) { 1691 regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff; 1692 regind >>= SIZE_INV_SHIFT; 1693 } else { 1694 /* 1695 * size_invs isn't large enough to handle this size class, so 1696 * calculate regind using actual division. This only happens 1697 * if the user increases small_max via the 'S' runtime 1698 * configuration option. 1699 */ 1700 regind = (unsigned)(diff / size); 1701 }; 1702 assert(diff == regind * size); 1703 assert(regind < bin->nregs); 1704 1705 elm = regind >> (SIZEOF_INT_2POW + 3); 1706 if (elm < run->regs_minelm) 1707 run->regs_minelm = elm; 1708 bit = regind - (elm << (SIZEOF_INT_2POW + 3)); 1709 assert((run->regs_mask[elm] & (1U << bit)) == 0); 1710 run->regs_mask[elm] |= (1U << bit); 1711 #undef SIZE_INV 1712 #undef SIZE_INV_SHIFT 1713 } 1714 1715 static void 1716 arena_run_split(arena_t *arena, arena_run_t *run, size_t size) 1717 { 1718 arena_chunk_t *chunk; 1719 unsigned run_ind, map_offset, total_pages, need_pages, rem_pages; 1720 unsigned i; 1721 1722 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1723 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) 1724 >> pagesize_2pow); 1725 total_pages = chunk->map[run_ind].npages; 1726 need_pages = (unsigned)(size >> pagesize_2pow); 1727 assert(need_pages <= total_pages); 1728 rem_pages = total_pages - need_pages; 1729 1730 /* Split enough pages from the front of run to fit allocation size. */ 1731 map_offset = run_ind; 1732 for (i = 0; i < need_pages; i++) { 1733 chunk->map[map_offset + i].npages = need_pages; 1734 chunk->map[map_offset + i].pos = i; 1735 } 1736 1737 /* Keep track of trailing unused pages for later use. */ 1738 if (rem_pages > 0) { 1739 /* Update map for trailing pages. */ 1740 map_offset += need_pages; 1741 chunk->map[map_offset].npages = rem_pages; 1742 chunk->map[map_offset].pos = POS_FREE; 1743 chunk->map[map_offset + rem_pages - 1].npages = rem_pages; 1744 chunk->map[map_offset + rem_pages - 1].pos = POS_FREE; 1745 } 1746 1747 chunk->pages_used += need_pages; 1748 } 1749 1750 static arena_chunk_t * 1751 arena_chunk_alloc(arena_t *arena) 1752 { 1753 arena_chunk_t *chunk; 1754 1755 if (arena->spare != NULL) { 1756 chunk = arena->spare; 1757 arena->spare = NULL; 1758 1759 rb_tree_insert_node(&arena->chunks, chunk); 1760 } else { 1761 chunk = (arena_chunk_t *)chunk_alloc(chunksize); 1762 if (chunk == NULL) 1763 return (NULL); 1764 #ifdef MALLOC_STATS 1765 arena->stats.mapped += chunksize; 1766 #endif 1767 1768 chunk->arena = arena; 1769 1770 /* 1771 * Claim that no pages are in use, since the header is merely 1772 * overhead. 1773 */ 1774 chunk->pages_used = 0; 1775 1776 chunk->max_frun_npages = chunk_npages - 1777 arena_chunk_header_npages; 1778 chunk->min_frun_ind = arena_chunk_header_npages; 1779 1780 /* 1781 * Initialize enough of the map to support one maximal free run. 1782 */ 1783 chunk->map[arena_chunk_header_npages].npages = chunk_npages - 1784 arena_chunk_header_npages; 1785 chunk->map[arena_chunk_header_npages].pos = POS_FREE; 1786 chunk->map[chunk_npages - 1].npages = chunk_npages - 1787 arena_chunk_header_npages; 1788 chunk->map[chunk_npages - 1].pos = POS_FREE; 1789 1790 rb_tree_insert_node(&arena->chunks, chunk); 1791 } 1792 1793 return (chunk); 1794 } 1795 1796 static void 1797 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) 1798 { 1799 1800 /* 1801 * Remove chunk from the chunk tree, regardless of whether this chunk 1802 * will be cached, so that the arena does not use it. 1803 */ 1804 rb_tree_remove_node(&chunk->arena->chunks, chunk); 1805 1806 if (NOT_OPT(hint)) { 1807 if (arena->spare != NULL) { 1808 chunk_dealloc((void *)arena->spare, chunksize); 1809 #ifdef MALLOC_STATS 1810 arena->stats.mapped -= chunksize; 1811 #endif 1812 } 1813 arena->spare = chunk; 1814 } else { 1815 assert(arena->spare == NULL); 1816 chunk_dealloc((void *)chunk, chunksize); 1817 #ifdef MALLOC_STATS 1818 arena->stats.mapped -= chunksize; 1819 #endif 1820 } 1821 } 1822 1823 static arena_run_t * 1824 arena_run_alloc(arena_t *arena, size_t size) 1825 { 1826 arena_chunk_t *chunk; 1827 arena_run_t *run; 1828 unsigned need_npages; 1829 1830 assert(size <= (chunksize - (arena_chunk_header_npages << 1831 pagesize_2pow))); 1832 assert((size & pagesize_mask) == 0); 1833 1834 /* 1835 * Search through the arena chunk tree for a large enough free run. 1836 * Tree order ensures that any exact fit is picked immediately or 1837 * otherwise the lowest address of the next size. 1838 */ 1839 need_npages = (unsigned)(size >> pagesize_2pow); 1840 /* LINTED */ 1841 for (;;) { 1842 rb_node_t *node = arena->chunks.rbt_root; 1843 chunk = NULL; 1844 while (!RB_SENTINEL_P(node)) { 1845 assert(offsetof(struct arena_chunk_s, link) == 0); 1846 arena_chunk_t *chunk_tmp = (arena_chunk_t *)node; 1847 if (chunk_tmp->max_frun_npages == need_npages) { 1848 chunk = chunk_tmp; 1849 break; 1850 } 1851 if (chunk_tmp->max_frun_npages < need_npages) { 1852 node = node->rb_nodes[1]; 1853 continue; 1854 } 1855 chunk = chunk_tmp; 1856 node = node->rb_nodes[0]; 1857 } 1858 if (chunk == NULL) 1859 break; 1860 /* 1861 * At this point, the chunk must have a cached run size large 1862 * enough to fit the allocation. 1863 */ 1864 assert(need_npages <= chunk->max_frun_npages); 1865 { 1866 arena_chunk_map_t *mapelm; 1867 unsigned i; 1868 unsigned max_frun_npages = 0; 1869 unsigned min_frun_ind = chunk_npages; 1870 1871 assert(chunk->min_frun_ind >= 1872 arena_chunk_header_npages); 1873 for (i = chunk->min_frun_ind; i < chunk_npages;) { 1874 mapelm = &chunk->map[i]; 1875 if (mapelm->pos == POS_FREE) { 1876 if (mapelm->npages >= need_npages) { 1877 run = (arena_run_t *) 1878 ((uintptr_t)chunk + (i << 1879 pagesize_2pow)); 1880 /* Update page map. */ 1881 arena_run_split(arena, run, 1882 size); 1883 return (run); 1884 } 1885 if (mapelm->npages > 1886 max_frun_npages) { 1887 max_frun_npages = 1888 mapelm->npages; 1889 } 1890 if (i < min_frun_ind) { 1891 min_frun_ind = i; 1892 if (i < chunk->min_frun_ind) 1893 chunk->min_frun_ind = i; 1894 } 1895 } 1896 i += mapelm->npages; 1897 } 1898 /* 1899 * Search failure. Reset cached chunk->max_frun_npages. 1900 * chunk->min_frun_ind was already reset above (if 1901 * necessary). 1902 */ 1903 rb_tree_remove_node(&arena->chunks, chunk); 1904 chunk->max_frun_npages = max_frun_npages; 1905 rb_tree_insert_node(&arena->chunks, chunk); 1906 } 1907 } 1908 1909 /* 1910 * No usable runs. Create a new chunk from which to allocate the run. 1911 */ 1912 chunk = arena_chunk_alloc(arena); 1913 if (chunk == NULL) 1914 return (NULL); 1915 run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages << 1916 pagesize_2pow)); 1917 /* Update page map. */ 1918 arena_run_split(arena, run, size); 1919 return (run); 1920 } 1921 1922 static void 1923 arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size) 1924 { 1925 arena_chunk_t *chunk; 1926 unsigned run_ind, run_pages; 1927 1928 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 1929 1930 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) 1931 >> pagesize_2pow); 1932 assert(run_ind >= arena_chunk_header_npages); 1933 assert(run_ind < (chunksize >> pagesize_2pow)); 1934 run_pages = (unsigned)(size >> pagesize_2pow); 1935 assert(run_pages == chunk->map[run_ind].npages); 1936 1937 /* Subtract pages from count of pages used in chunk. */ 1938 chunk->pages_used -= run_pages; 1939 1940 /* Mark run as deallocated. */ 1941 assert(chunk->map[run_ind].npages == run_pages); 1942 chunk->map[run_ind].pos = POS_FREE; 1943 assert(chunk->map[run_ind + run_pages - 1].npages == run_pages); 1944 chunk->map[run_ind + run_pages - 1].pos = POS_FREE; 1945 1946 /* 1947 * Tell the kernel that we don't need the data in this run, but only if 1948 * requested via runtime configuration. 1949 */ 1950 if (OPT(hint)) 1951 madvise(run, size, MADV_FREE); 1952 1953 /* Try to coalesce with neighboring runs. */ 1954 if (run_ind > arena_chunk_header_npages && 1955 chunk->map[run_ind - 1].pos == POS_FREE) { 1956 unsigned prev_npages; 1957 1958 /* Coalesce with previous run. */ 1959 prev_npages = chunk->map[run_ind - 1].npages; 1960 run_ind -= prev_npages; 1961 assert(chunk->map[run_ind].npages == prev_npages); 1962 assert(chunk->map[run_ind].pos == POS_FREE); 1963 run_pages += prev_npages; 1964 1965 chunk->map[run_ind].npages = run_pages; 1966 assert(chunk->map[run_ind].pos == POS_FREE); 1967 chunk->map[run_ind + run_pages - 1].npages = run_pages; 1968 assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE); 1969 } 1970 1971 if (run_ind + run_pages < chunk_npages && 1972 chunk->map[run_ind + run_pages].pos == POS_FREE) { 1973 unsigned next_npages; 1974 1975 /* Coalesce with next run. */ 1976 next_npages = chunk->map[run_ind + run_pages].npages; 1977 run_pages += next_npages; 1978 assert(chunk->map[run_ind + run_pages - 1].npages == 1979 next_npages); 1980 assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE); 1981 1982 chunk->map[run_ind].npages = run_pages; 1983 chunk->map[run_ind].pos = POS_FREE; 1984 chunk->map[run_ind + run_pages - 1].npages = run_pages; 1985 assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE); 1986 } 1987 1988 if (chunk->map[run_ind].npages > chunk->max_frun_npages) { 1989 rb_tree_remove_node(&arena->chunks, chunk); 1990 chunk->max_frun_npages = chunk->map[run_ind].npages; 1991 rb_tree_insert_node(&arena->chunks, chunk); 1992 } 1993 if (run_ind < chunk->min_frun_ind) 1994 chunk->min_frun_ind = run_ind; 1995 1996 /* Deallocate chunk if it is now completely unused. */ 1997 if (chunk->pages_used == 0) 1998 arena_chunk_dealloc(arena, chunk); 1999 } 2000 2001 static arena_run_t * 2002 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) 2003 { 2004 arena_run_t *run; 2005 unsigned i, remainder; 2006 2007 /* Look for a usable run. */ 2008 if ((run = RB_TREE_MIN(&bin->runs)) != NULL) { 2009 /* run is guaranteed to have available space. */ 2010 rb_tree_remove_node(&bin->runs, run); 2011 #ifdef MALLOC_STATS 2012 bin->stats.reruns++; 2013 #endif 2014 return (run); 2015 } 2016 /* No existing runs have any space available. */ 2017 2018 /* Allocate a new run. */ 2019 run = arena_run_alloc(arena, bin->run_size); 2020 if (run == NULL) 2021 return (NULL); 2022 2023 /* Initialize run internals. */ 2024 run->bin = bin; 2025 2026 for (i = 0; i < bin->regs_mask_nelms; i++) 2027 run->regs_mask[i] = UINT_MAX; 2028 remainder = bin->nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1); 2029 if (remainder != 0) { 2030 /* The last element has spare bits that need to be unset. */ 2031 run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3)) 2032 - remainder)); 2033 } 2034 2035 run->regs_minelm = 0; 2036 2037 run->nfree = bin->nregs; 2038 #ifdef MALLOC_DEBUG 2039 run->magic = ARENA_RUN_MAGIC; 2040 #endif 2041 2042 #ifdef MALLOC_STATS 2043 bin->stats.nruns++; 2044 bin->stats.curruns++; 2045 if (bin->stats.curruns > bin->stats.highruns) 2046 bin->stats.highruns = bin->stats.curruns; 2047 #endif 2048 return (run); 2049 } 2050 2051 /* bin->runcur must have space available before this function is called. */ 2052 static inline void * 2053 arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run) 2054 { 2055 void *ret; 2056 2057 assert(run->magic == ARENA_RUN_MAGIC); 2058 assert(run->nfree > 0); 2059 2060 ret = arena_run_reg_alloc(run, bin); 2061 assert(ret != NULL); 2062 run->nfree--; 2063 2064 return (ret); 2065 } 2066 2067 /* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */ 2068 static void * 2069 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) 2070 { 2071 2072 bin->runcur = arena_bin_nonfull_run_get(arena, bin); 2073 if (bin->runcur == NULL) 2074 return (NULL); 2075 assert(bin->runcur->magic == ARENA_RUN_MAGIC); 2076 assert(bin->runcur->nfree > 0); 2077 2078 return (arena_bin_malloc_easy(arena, bin, bin->runcur)); 2079 } 2080 2081 /* 2082 * Calculate bin->run_size such that it meets the following constraints: 2083 * 2084 * *) bin->run_size >= min_run_size 2085 * *) bin->run_size <= arena_maxclass 2086 * *) bin->run_size <= RUN_MAX_SMALL 2087 * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed). 2088 * 2089 * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are 2090 * also calculated here, since these settings are all interdependent. 2091 */ 2092 static size_t 2093 arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size) 2094 { 2095 size_t try_run_size, good_run_size; 2096 unsigned good_nregs, good_mask_nelms, good_reg0_offset; 2097 unsigned try_nregs, try_mask_nelms, try_reg0_offset; 2098 2099 assert(min_run_size >= pagesize); 2100 assert(min_run_size <= arena_maxclass); 2101 assert(min_run_size <= RUN_MAX_SMALL); 2102 2103 /* 2104 * Calculate known-valid settings before entering the run_size 2105 * expansion loop, so that the first part of the loop always copies 2106 * valid settings. 2107 * 2108 * The do..while loop iteratively reduces the number of regions until 2109 * the run header and the regions no longer overlap. A closed formula 2110 * would be quite messy, since there is an interdependency between the 2111 * header's mask length and the number of regions. 2112 */ 2113 try_run_size = min_run_size; 2114 try_nregs = (unsigned)(((try_run_size - sizeof(arena_run_t)) / 2115 bin->reg_size) + 1); /* Counter-act try_nregs-- in loop. */ 2116 do { 2117 try_nregs--; 2118 try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) + 2119 ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0); 2120 try_reg0_offset = (unsigned)(try_run_size - 2121 (try_nregs * bin->reg_size)); 2122 } while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1)) 2123 > try_reg0_offset); 2124 2125 /* run_size expansion loop. */ 2126 do { 2127 /* 2128 * Copy valid settings before trying more aggressive settings. 2129 */ 2130 good_run_size = try_run_size; 2131 good_nregs = try_nregs; 2132 good_mask_nelms = try_mask_nelms; 2133 good_reg0_offset = try_reg0_offset; 2134 2135 /* Try more aggressive settings. */ 2136 try_run_size += pagesize; 2137 try_nregs = (unsigned)(((try_run_size - sizeof(arena_run_t)) / 2138 bin->reg_size) + 1); /* Counter-act try_nregs-- in loop. */ 2139 do { 2140 try_nregs--; 2141 try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) + 2142 ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ? 2143 1 : 0); 2144 try_reg0_offset = (unsigned)(try_run_size - (try_nregs * 2145 bin->reg_size)); 2146 } while (sizeof(arena_run_t) + (sizeof(unsigned) * 2147 (try_mask_nelms - 1)) > try_reg0_offset); 2148 } while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL 2149 && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX 2150 && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size); 2151 2152 assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1)) 2153 <= good_reg0_offset); 2154 assert((good_mask_nelms << (SIZEOF_INT_2POW + 3)) >= good_nregs); 2155 2156 /* Copy final settings. */ 2157 bin->run_size = good_run_size; 2158 bin->nregs = good_nregs; 2159 bin->regs_mask_nelms = good_mask_nelms; 2160 bin->reg0_offset = good_reg0_offset; 2161 2162 return (good_run_size); 2163 } 2164 2165 static void * 2166 arena_malloc(arena_t *arena, size_t size) 2167 { 2168 void *ret; 2169 2170 assert(arena != NULL); 2171 assert(arena->magic == ARENA_MAGIC); 2172 assert(size != 0); 2173 assert(QUANTUM_CEILING(size) <= arena_maxclass); 2174 2175 if (size <= bin_maxclass) { 2176 arena_bin_t *bin; 2177 arena_run_t *run; 2178 2179 /* Small allocation. */ 2180 2181 if (size < small_min) { 2182 /* Tiny. */ 2183 size = pow2_ceil(size); 2184 bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW + 2185 1)))]; 2186 #if (!defined(NDEBUG) || defined(MALLOC_STATS)) 2187 /* 2188 * Bin calculation is always correct, but we may need 2189 * to fix size for the purposes of assertions and/or 2190 * stats accuracy. 2191 */ 2192 if (size < (1 << TINY_MIN_2POW)) 2193 size = (1 << TINY_MIN_2POW); 2194 #endif 2195 } else if (size <= small_max) { 2196 /* Quantum-spaced. */ 2197 size = QUANTUM_CEILING(size); 2198 bin = &arena->bins[ntbins + (size >> opt_quantum_2pow) 2199 - 1]; 2200 } else { 2201 /* Sub-page. */ 2202 size = pow2_ceil(size); 2203 bin = &arena->bins[ntbins + nqbins 2204 + (ffs((int)(size >> opt_small_max_2pow)) - 2)]; 2205 } 2206 assert(size == bin->reg_size); 2207 2208 malloc_mutex_lock(&arena->mtx); 2209 if ((run = bin->runcur) != NULL && run->nfree > 0) 2210 ret = arena_bin_malloc_easy(arena, bin, run); 2211 else 2212 ret = arena_bin_malloc_hard(arena, bin); 2213 2214 if (ret == NULL) { 2215 malloc_mutex_unlock(&arena->mtx); 2216 return (NULL); 2217 } 2218 2219 #ifdef MALLOC_STATS 2220 bin->stats.nrequests++; 2221 arena->stats.nmalloc_small++; 2222 arena->stats.allocated_small += size; 2223 #endif 2224 } else { 2225 /* Large allocation. */ 2226 size = PAGE_CEILING(size); 2227 malloc_mutex_lock(&arena->mtx); 2228 ret = (void *)arena_run_alloc(arena, size); 2229 if (ret == NULL) { 2230 malloc_mutex_unlock(&arena->mtx); 2231 return (NULL); 2232 } 2233 #ifdef MALLOC_STATS 2234 arena->stats.nmalloc_large++; 2235 arena->stats.allocated_large += size; 2236 #endif 2237 } 2238 2239 malloc_mutex_unlock(&arena->mtx); 2240 2241 if (OPT(junk)) 2242 memset(ret, 0xa5, size); 2243 else if (OPT(zero)) 2244 memset(ret, 0, size); 2245 return (ret); 2246 } 2247 2248 static inline void 2249 arena_palloc_trim(arena_t *arena, arena_chunk_t *chunk, unsigned pageind, 2250 unsigned npages) 2251 { 2252 unsigned i; 2253 2254 assert(npages > 0); 2255 2256 /* 2257 * Modifiy the map such that arena_run_dalloc() sees the run as 2258 * separately allocated. 2259 */ 2260 for (i = 0; i < npages; i++) { 2261 chunk->map[pageind + i].npages = npages; 2262 chunk->map[pageind + i].pos = i; 2263 } 2264 arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)chunk + (pageind << 2265 pagesize_2pow)), npages << pagesize_2pow); 2266 } 2267 2268 /* Only handles large allocations that require more than page alignment. */ 2269 static void * 2270 arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size) 2271 { 2272 void *ret; 2273 size_t offset; 2274 arena_chunk_t *chunk; 2275 unsigned pageind, i, npages; 2276 2277 assert((size & pagesize_mask) == 0); 2278 assert((alignment & pagesize_mask) == 0); 2279 2280 npages = (unsigned)(size >> pagesize_2pow); 2281 2282 malloc_mutex_lock(&arena->mtx); 2283 ret = (void *)arena_run_alloc(arena, alloc_size); 2284 if (ret == NULL) { 2285 malloc_mutex_unlock(&arena->mtx); 2286 return (NULL); 2287 } 2288 2289 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret); 2290 2291 offset = (uintptr_t)ret & (alignment - 1); 2292 assert((offset & pagesize_mask) == 0); 2293 assert(offset < alloc_size); 2294 if (offset == 0) { 2295 pageind = (unsigned)(((uintptr_t)ret - (uintptr_t)chunk) >> 2296 pagesize_2pow); 2297 2298 /* Update the map for the run to be kept. */ 2299 for (i = 0; i < npages; i++) { 2300 chunk->map[pageind + i].npages = npages; 2301 assert(chunk->map[pageind + i].pos == i); 2302 } 2303 2304 /* Trim trailing space. */ 2305 arena_palloc_trim(arena, chunk, pageind + npages, 2306 (unsigned)((alloc_size - size) >> pagesize_2pow)); 2307 } else { 2308 size_t leadsize, trailsize; 2309 2310 leadsize = alignment - offset; 2311 ret = (void *)((uintptr_t)ret + leadsize); 2312 pageind = (unsigned)(((uintptr_t)ret - (uintptr_t)chunk) >> 2313 pagesize_2pow); 2314 2315 /* Update the map for the run to be kept. */ 2316 for (i = 0; i < npages; i++) { 2317 chunk->map[pageind + i].npages = npages; 2318 chunk->map[pageind + i].pos = i; 2319 } 2320 2321 /* Trim leading space. */ 2322 arena_palloc_trim(arena, chunk, 2323 (unsigned)(pageind - (leadsize >> pagesize_2pow)), 2324 (unsigned)(leadsize >> pagesize_2pow)); 2325 2326 trailsize = alloc_size - leadsize - size; 2327 if (trailsize != 0) { 2328 /* Trim trailing space. */ 2329 assert(trailsize < alloc_size); 2330 arena_palloc_trim(arena, chunk, pageind + npages, 2331 (unsigned)(trailsize >> pagesize_2pow)); 2332 } 2333 } 2334 2335 #ifdef MALLOC_STATS 2336 arena->stats.nmalloc_large++; 2337 arena->stats.allocated_large += size; 2338 #endif 2339 malloc_mutex_unlock(&arena->mtx); 2340 2341 if (OPT(junk)) 2342 memset(ret, 0xa5, size); 2343 else if (OPT(zero)) 2344 memset(ret, 0, size); 2345 return (ret); 2346 } 2347 2348 /* Return the size of the allocation pointed to by ptr. */ 2349 static size_t 2350 arena_salloc(const void *ptr) 2351 { 2352 size_t ret; 2353 arena_chunk_t *chunk; 2354 arena_chunk_map_t *mapelm; 2355 unsigned pageind; 2356 2357 assert(ptr != NULL); 2358 assert(CHUNK_ADDR2BASE(ptr) != ptr); 2359 2360 /* 2361 * No arena data structures that we query here can change in a way that 2362 * affects this function, so we don't need to lock. 2363 */ 2364 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 2365 pageind = (unsigned)(((uintptr_t)ptr - (uintptr_t)chunk) >> 2366 pagesize_2pow); 2367 mapelm = &chunk->map[pageind]; 2368 if (mapelm->pos != 0 || ptr != (char *)((uintptr_t)chunk) + (pageind << 2369 pagesize_2pow)) { 2370 arena_run_t *run; 2371 2372 pageind -= mapelm->pos; 2373 2374 run = (arena_run_t *)((uintptr_t)chunk + (pageind << 2375 pagesize_2pow)); 2376 assert(run->magic == ARENA_RUN_MAGIC); 2377 ret = run->bin->reg_size; 2378 } else 2379 ret = mapelm->npages << pagesize_2pow; 2380 2381 return (ret); 2382 } 2383 2384 static void * 2385 arena_ralloc(void *ptr, size_t size, size_t oldsize) 2386 { 2387 void *ret; 2388 2389 /* Avoid moving the allocation if the size class would not change. */ 2390 if (size < small_min) { 2391 if (oldsize < small_min && 2392 ffs((int)(pow2_ceil(size) >> (TINY_MIN_2POW + 1))) 2393 == ffs((int)(pow2_ceil(oldsize) >> (TINY_MIN_2POW + 1)))) 2394 goto IN_PLACE; 2395 } else if (size <= small_max) { 2396 if (oldsize >= small_min && oldsize <= small_max && 2397 (QUANTUM_CEILING(size) >> opt_quantum_2pow) 2398 == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow)) 2399 goto IN_PLACE; 2400 } else { 2401 /* 2402 * We make no attempt to resize runs here, though it would be 2403 * possible to do so. 2404 */ 2405 if (oldsize > small_max && PAGE_CEILING(size) == oldsize) 2406 goto IN_PLACE; 2407 } 2408 2409 /* 2410 * If we get here, then size and oldsize are different enough that we 2411 * need to use a different size class. In that case, fall back to 2412 * allocating new space and copying. 2413 */ 2414 ret = arena_malloc(choose_arena(), size); 2415 if (ret == NULL) 2416 return (NULL); 2417 2418 /* Junk/zero-filling were already done by arena_malloc(). */ 2419 if (size < oldsize) 2420 memcpy(ret, ptr, size); 2421 else 2422 memcpy(ret, ptr, oldsize); 2423 idalloc(ptr); 2424 return (ret); 2425 IN_PLACE: 2426 if (OPT(junk) && size < oldsize) 2427 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); 2428 else if (OPT(zero) && size > oldsize) 2429 memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize); 2430 return (ptr); 2431 } 2432 2433 static void 2434 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr) 2435 { 2436 unsigned pageind; 2437 arena_chunk_map_t *mapelm; 2438 size_t size; 2439 2440 assert(arena != NULL); 2441 assert(arena->magic == ARENA_MAGIC); 2442 assert(chunk->arena == arena); 2443 assert(ptr != NULL); 2444 assert(CHUNK_ADDR2BASE(ptr) != ptr); 2445 2446 pageind = (unsigned)(((uintptr_t)ptr - (uintptr_t)chunk) >> 2447 pagesize_2pow); 2448 mapelm = &chunk->map[pageind]; 2449 if (mapelm->pos != 0 || ptr != (char *)((uintptr_t)chunk) + (pageind << 2450 pagesize_2pow)) { 2451 arena_run_t *run; 2452 arena_bin_t *bin; 2453 2454 /* Small allocation. */ 2455 2456 pageind -= mapelm->pos; 2457 2458 run = (arena_run_t *)((uintptr_t)chunk + (pageind << 2459 pagesize_2pow)); 2460 assert(run->magic == ARENA_RUN_MAGIC); 2461 bin = run->bin; 2462 size = bin->reg_size; 2463 2464 if (OPT(junk)) 2465 memset(ptr, 0x5a, size); 2466 2467 malloc_mutex_lock(&arena->mtx); 2468 arena_run_reg_dalloc(run, bin, ptr, size); 2469 run->nfree++; 2470 2471 if (run->nfree == bin->nregs) { 2472 /* Deallocate run. */ 2473 if (run == bin->runcur) 2474 bin->runcur = NULL; 2475 else if (bin->nregs != 1) { 2476 /* 2477 * This block's conditional is necessary because 2478 * if the run only contains one region, then it 2479 * never gets inserted into the non-full runs 2480 * tree. 2481 */ 2482 rb_tree_remove_node(&bin->runs, run); 2483 } 2484 #ifdef MALLOC_DEBUG 2485 run->magic = 0; 2486 #endif 2487 arena_run_dalloc(arena, run, bin->run_size); 2488 #ifdef MALLOC_STATS 2489 bin->stats.curruns--; 2490 #endif 2491 } else if (run->nfree == 1 && run != bin->runcur) { 2492 /* 2493 * Make sure that bin->runcur always refers to the 2494 * lowest non-full run, if one exists. 2495 */ 2496 if (bin->runcur == NULL) 2497 bin->runcur = run; 2498 else if ((uintptr_t)run < (uintptr_t)bin->runcur) { 2499 /* Switch runcur. */ 2500 if (bin->runcur->nfree > 0) { 2501 /* Insert runcur. */ 2502 rb_tree_insert_node(&bin->runs, bin->runcur); 2503 } 2504 bin->runcur = run; 2505 } else { 2506 rb_tree_insert_node(&bin->runs, run); 2507 } 2508 } 2509 #ifdef MALLOC_STATS 2510 arena->stats.allocated_small -= size; 2511 arena->stats.ndalloc_small++; 2512 #endif 2513 } else { 2514 /* Large allocation. */ 2515 2516 size = mapelm->npages << pagesize_2pow; 2517 assert((((uintptr_t)ptr) & pagesize_mask) == 0); 2518 2519 if (OPT(junk)) 2520 memset(ptr, 0x5a, size); 2521 2522 malloc_mutex_lock(&arena->mtx); 2523 arena_run_dalloc(arena, (arena_run_t *)ptr, size); 2524 #ifdef MALLOC_STATS 2525 arena->stats.allocated_large -= size; 2526 arena->stats.ndalloc_large++; 2527 #endif 2528 } 2529 2530 malloc_mutex_unlock(&arena->mtx); 2531 } 2532 2533 static void 2534 arena_new(arena_t *arena) 2535 { 2536 unsigned i; 2537 arena_bin_t *bin; 2538 size_t prev_run_size; 2539 2540 malloc_mutex_init(&arena->mtx); 2541 2542 #ifdef MALLOC_STATS 2543 memset(&arena->stats, 0, sizeof(arena_stats_t)); 2544 #endif 2545 2546 /* Initialize chunks. */ 2547 rb_tree_init(&arena->chunks, &arena_chunk_tree_ops); 2548 arena->spare = NULL; 2549 2550 /* Initialize bins. */ 2551 prev_run_size = pagesize; 2552 2553 /* (2^n)-spaced tiny bins. */ 2554 for (i = 0; i < ntbins; i++) { 2555 bin = &arena->bins[i]; 2556 bin->runcur = NULL; 2557 rb_tree_init(&bin->runs, &arena_run_tree_ops); 2558 2559 bin->reg_size = (1 << (TINY_MIN_2POW + i)); 2560 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2561 2562 #ifdef MALLOC_STATS 2563 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2564 #endif 2565 } 2566 2567 /* Quantum-spaced bins. */ 2568 for (; i < ntbins + nqbins; i++) { 2569 bin = &arena->bins[i]; 2570 bin->runcur = NULL; 2571 rb_tree_init(&bin->runs, &arena_run_tree_ops); 2572 2573 bin->reg_size = quantum * (i - ntbins + 1); 2574 /* 2575 pow2_size = pow2_ceil(quantum * (i - ntbins + 1)); 2576 */ 2577 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2578 2579 #ifdef MALLOC_STATS 2580 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2581 #endif 2582 } 2583 2584 /* (2^n)-spaced sub-page bins. */ 2585 for (; i < ntbins + nqbins + nsbins; i++) { 2586 bin = &arena->bins[i]; 2587 bin->runcur = NULL; 2588 rb_tree_init(&bin->runs, &arena_run_tree_ops); 2589 2590 bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1)); 2591 2592 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 2593 2594 #ifdef MALLOC_STATS 2595 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 2596 #endif 2597 } 2598 2599 #ifdef MALLOC_DEBUG 2600 arena->magic = ARENA_MAGIC; 2601 #endif 2602 } 2603 2604 /* Create a new arena and insert it into the arenas array at index ind. */ 2605 static arena_t * 2606 arenas_extend(void) 2607 { 2608 arena_t *ret; 2609 2610 /* Allocate enough space for trailing bins. */ 2611 ret = (arena_t *)base_alloc(sizeof(arena_t) 2612 + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1))); 2613 if (ret != NULL) { 2614 arena_new(ret); 2615 return (ret); 2616 } 2617 /* Only reached if there is an OOM error. */ 2618 2619 /* 2620 * OOM here is quite inconvenient to propagate, since dealing with it 2621 * would require a check for failure in the fast path. Instead, punt 2622 * by using arenas[0]. In practice, this is an extremely unlikely 2623 * failure. 2624 */ 2625 _malloc_message(getprogname(), 2626 ": (malloc) Error initializing arena\n", "", ""); 2627 if (OPT(abort)) 2628 abort(); 2629 2630 return (arenas[0]); 2631 } 2632 2633 /* 2634 * End arena. 2635 */ 2636 /******************************************************************************/ 2637 /* 2638 * Begin general internal functions. 2639 */ 2640 2641 static void * 2642 huge_malloc(size_t size) 2643 { 2644 void *ret; 2645 size_t csize; 2646 chunk_node_t *node; 2647 2648 /* Allocate one or more contiguous chunks for this request. */ 2649 2650 csize = CHUNK_CEILING(size); 2651 if (csize == 0) { 2652 /* size is large enough to cause size_t wrap-around. */ 2653 return (NULL); 2654 } 2655 2656 /* Allocate a chunk node with which to track the chunk. */ 2657 node = base_chunk_node_alloc(); 2658 if (node == NULL) 2659 return (NULL); 2660 2661 ret = chunk_alloc(csize); 2662 if (ret == NULL) { 2663 base_chunk_node_dealloc(node); 2664 return (NULL); 2665 } 2666 2667 /* Insert node into huge. */ 2668 node->chunk = ret; 2669 node->size = csize; 2670 2671 malloc_mutex_lock(&chunks_mtx); 2672 rb_tree_insert_node(&huge, node); 2673 #ifdef MALLOC_STATS 2674 huge_nmalloc++; 2675 huge_allocated += csize; 2676 #endif 2677 malloc_mutex_unlock(&chunks_mtx); 2678 2679 if (OPT(junk)) 2680 memset(ret, 0xa5, csize); 2681 else if (OPT(zero)) 2682 memset(ret, 0, csize); 2683 2684 return (ret); 2685 } 2686 2687 /* Only handles large allocations that require more than chunk alignment. */ 2688 static void * 2689 huge_palloc(size_t alignment, size_t size) 2690 { 2691 void *ret; 2692 size_t alloc_size, chunk_size, offset; 2693 chunk_node_t *node; 2694 2695 /* 2696 * This allocation requires alignment that is even larger than chunk 2697 * alignment. This means that huge_malloc() isn't good enough. 2698 * 2699 * Allocate almost twice as many chunks as are demanded by the size or 2700 * alignment, in order to assure the alignment can be achieved, then 2701 * unmap leading and trailing chunks. 2702 */ 2703 assert(alignment >= chunksize); 2704 2705 chunk_size = CHUNK_CEILING(size); 2706 2707 if (size >= alignment) 2708 alloc_size = chunk_size + alignment - chunksize; 2709 else 2710 alloc_size = (alignment << 1) - chunksize; 2711 2712 /* Allocate a chunk node with which to track the chunk. */ 2713 node = base_chunk_node_alloc(); 2714 if (node == NULL) 2715 return (NULL); 2716 2717 ret = chunk_alloc(alloc_size); 2718 if (ret == NULL) { 2719 base_chunk_node_dealloc(node); 2720 return (NULL); 2721 } 2722 2723 offset = (uintptr_t)ret & (alignment - 1); 2724 assert((offset & chunksize_mask) == 0); 2725 assert(offset < alloc_size); 2726 if (offset == 0) { 2727 /* Trim trailing space. */ 2728 chunk_dealloc((void *)((uintptr_t)ret + chunk_size), alloc_size 2729 - chunk_size); 2730 } else { 2731 size_t trailsize; 2732 2733 /* Trim leading space. */ 2734 chunk_dealloc(ret, alignment - offset); 2735 2736 ret = (void *)((uintptr_t)ret + (alignment - offset)); 2737 2738 trailsize = alloc_size - (alignment - offset) - chunk_size; 2739 if (trailsize != 0) { 2740 /* Trim trailing space. */ 2741 assert(trailsize < alloc_size); 2742 chunk_dealloc((void *)((uintptr_t)ret + chunk_size), 2743 trailsize); 2744 } 2745 } 2746 2747 /* Insert node into huge. */ 2748 node->chunk = ret; 2749 node->size = chunk_size; 2750 2751 malloc_mutex_lock(&chunks_mtx); 2752 rb_tree_insert_node(&huge, node); 2753 #ifdef MALLOC_STATS 2754 huge_nmalloc++; 2755 huge_allocated += chunk_size; 2756 #endif 2757 malloc_mutex_unlock(&chunks_mtx); 2758 2759 if (OPT(junk)) 2760 memset(ret, 0xa5, chunk_size); 2761 else if (OPT(zero)) 2762 memset(ret, 0, chunk_size); 2763 2764 return (ret); 2765 } 2766 2767 static void * 2768 huge_ralloc(void *ptr, size_t size, size_t oldsize) 2769 { 2770 void *ret; 2771 2772 /* Avoid moving the allocation if the size class would not change. */ 2773 if (oldsize > arena_maxclass && 2774 CHUNK_CEILING(size) == CHUNK_CEILING(oldsize)) { 2775 if (OPT(junk) && size < oldsize) { 2776 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize 2777 - size); 2778 } else if (OPT(zero) && size > oldsize) { 2779 memset((void *)((uintptr_t)ptr + oldsize), 0, size 2780 - oldsize); 2781 } 2782 return (ptr); 2783 } 2784 2785 if (CHUNK_ADDR2BASE(ptr) == ptr 2786 #ifdef USE_BRK 2787 && ((uintptr_t)ptr < (uintptr_t)brk_base 2788 || (uintptr_t)ptr >= (uintptr_t)brk_max) 2789 #endif 2790 ) { 2791 chunk_node_t *node, key; 2792 void *newptr; 2793 size_t oldcsize; 2794 size_t newcsize; 2795 2796 newcsize = CHUNK_CEILING(size); 2797 oldcsize = CHUNK_CEILING(oldsize); 2798 assert(oldcsize != newcsize); 2799 if (newcsize == 0) { 2800 /* size_t wrap-around */ 2801 return (NULL); 2802 } 2803 2804 /* 2805 * Remove the old region from the tree now. If mremap() 2806 * returns the region to the system, other thread may 2807 * map it for same huge allocation and insert it to the 2808 * tree before we acquire the mutex lock again. 2809 */ 2810 malloc_mutex_lock(&chunks_mtx); 2811 key.chunk = __UNCONST(ptr); 2812 node = rb_tree_find_node(&huge, &key); 2813 assert(node != NULL); 2814 assert(node->chunk == ptr); 2815 assert(node->size == oldcsize); 2816 rb_tree_remove_node(&huge, node); 2817 malloc_mutex_unlock(&chunks_mtx); 2818 2819 newptr = mremap(ptr, oldcsize, NULL, newcsize, 2820 MAP_ALIGNED(chunksize_2pow)); 2821 if (newptr == MAP_FAILED) { 2822 /* We still own the old region. */ 2823 malloc_mutex_lock(&chunks_mtx); 2824 rb_tree_insert_node(&huge, node); 2825 malloc_mutex_unlock(&chunks_mtx); 2826 } else { 2827 assert(CHUNK_ADDR2BASE(newptr) == newptr); 2828 2829 /* Insert new or resized old region. */ 2830 malloc_mutex_lock(&chunks_mtx); 2831 node->size = newcsize; 2832 node->chunk = newptr; 2833 rb_tree_insert_node(&huge, node); 2834 #ifdef MALLOC_STATS 2835 huge_nralloc++; 2836 huge_allocated += newcsize - oldcsize; 2837 if (newcsize > oldcsize) { 2838 stats_chunks.curchunks += 2839 (newcsize - oldcsize) / chunksize; 2840 if (stats_chunks.curchunks > 2841 stats_chunks.highchunks) 2842 stats_chunks.highchunks = 2843 stats_chunks.curchunks; 2844 } else { 2845 stats_chunks.curchunks -= 2846 (oldcsize - newcsize) / chunksize; 2847 } 2848 #endif 2849 malloc_mutex_unlock(&chunks_mtx); 2850 2851 if (OPT(junk) && size < oldsize) { 2852 memset((void *)((uintptr_t)newptr + size), 0x5a, 2853 newcsize - size); 2854 } else if (OPT(zero) && size > oldsize) { 2855 memset((void *)((uintptr_t)newptr + oldsize), 0, 2856 size - oldsize); 2857 } 2858 return (newptr); 2859 } 2860 } 2861 2862 /* 2863 * If we get here, then size and oldsize are different enough that we 2864 * need to use a different size class. In that case, fall back to 2865 * allocating new space and copying. 2866 */ 2867 ret = huge_malloc(size); 2868 if (ret == NULL) 2869 return (NULL); 2870 2871 if (CHUNK_ADDR2BASE(ptr) == ptr) { 2872 /* The old allocation is a chunk. */ 2873 if (size < oldsize) 2874 memcpy(ret, ptr, size); 2875 else 2876 memcpy(ret, ptr, oldsize); 2877 } else { 2878 /* The old allocation is a region. */ 2879 assert(oldsize < size); 2880 memcpy(ret, ptr, oldsize); 2881 } 2882 idalloc(ptr); 2883 return (ret); 2884 } 2885 2886 static void 2887 huge_dalloc(void *ptr) 2888 { 2889 chunk_node_t key; 2890 chunk_node_t *node; 2891 2892 malloc_mutex_lock(&chunks_mtx); 2893 2894 /* Extract from tree of huge allocations. */ 2895 key.chunk = ptr; 2896 node = rb_tree_find_node(&huge, &key); 2897 assert(node != NULL); 2898 assert(node->chunk == ptr); 2899 rb_tree_remove_node(&huge, node); 2900 2901 #ifdef MALLOC_STATS 2902 huge_ndalloc++; 2903 huge_allocated -= node->size; 2904 #endif 2905 2906 malloc_mutex_unlock(&chunks_mtx); 2907 2908 /* Unmap chunk. */ 2909 #ifdef USE_BRK 2910 if (OPT(junk)) 2911 memset(node->chunk, 0x5a, node->size); 2912 #endif 2913 chunk_dealloc(node->chunk, node->size); 2914 2915 base_chunk_node_dealloc(node); 2916 } 2917 2918 static void * 2919 imalloc(size_t size) 2920 { 2921 void *ret; 2922 2923 assert(size != 0); 2924 2925 if (size <= arena_maxclass) 2926 ret = arena_malloc(choose_arena(), size); 2927 else 2928 ret = huge_malloc(size); 2929 2930 return (ret); 2931 } 2932 2933 static void * 2934 ipalloc(size_t alignment, size_t size) 2935 { 2936 void *ret; 2937 size_t ceil_size; 2938 2939 /* 2940 * Round size up to the nearest multiple of alignment. 2941 * 2942 * This done, we can take advantage of the fact that for each small 2943 * size class, every object is aligned at the smallest power of two 2944 * that is non-zero in the base two representation of the size. For 2945 * example: 2946 * 2947 * Size | Base 2 | Minimum alignment 2948 * -----+----------+------------------ 2949 * 96 | 1100000 | 32 2950 * 144 | 10100000 | 32 2951 * 192 | 11000000 | 64 2952 * 2953 * Depending on runtime settings, it is possible that arena_malloc() 2954 * will further round up to a power of two, but that never causes 2955 * correctness issues. 2956 */ 2957 ceil_size = (size + (alignment - 1)) & (-alignment); 2958 /* 2959 * (ceil_size < size) protects against the combination of maximal 2960 * alignment and size greater than maximal alignment. 2961 */ 2962 if (ceil_size < size) { 2963 /* size_t overflow. */ 2964 return (NULL); 2965 } 2966 2967 if (ceil_size <= pagesize || (alignment <= pagesize 2968 && ceil_size <= arena_maxclass)) 2969 ret = arena_malloc(choose_arena(), ceil_size); 2970 else { 2971 size_t run_size; 2972 2973 /* 2974 * We can't achieve sub-page alignment, so round up alignment 2975 * permanently; it makes later calculations simpler. 2976 */ 2977 alignment = PAGE_CEILING(alignment); 2978 ceil_size = PAGE_CEILING(size); 2979 /* 2980 * (ceil_size < size) protects against very large sizes within 2981 * pagesize of SIZE_T_MAX. 2982 * 2983 * (ceil_size + alignment < ceil_size) protects against the 2984 * combination of maximal alignment and ceil_size large enough 2985 * to cause overflow. This is similar to the first overflow 2986 * check above, but it needs to be repeated due to the new 2987 * ceil_size value, which may now be *equal* to maximal 2988 * alignment, whereas before we only detected overflow if the 2989 * original size was *greater* than maximal alignment. 2990 */ 2991 if (ceil_size < size || ceil_size + alignment < ceil_size) { 2992 /* size_t overflow. */ 2993 return (NULL); 2994 } 2995 2996 /* 2997 * Calculate the size of the over-size run that arena_palloc() 2998 * would need to allocate in order to guarantee the alignment. 2999 */ 3000 if (ceil_size >= alignment) 3001 run_size = ceil_size + alignment - pagesize; 3002 else { 3003 /* 3004 * It is possible that (alignment << 1) will cause 3005 * overflow, but it doesn't matter because we also 3006 * subtract pagesize, which in the case of overflow 3007 * leaves us with a very large run_size. That causes 3008 * the first conditional below to fail, which means 3009 * that the bogus run_size value never gets used for 3010 * anything important. 3011 */ 3012 run_size = (alignment << 1) - pagesize; 3013 } 3014 3015 if (run_size <= arena_maxclass) { 3016 ret = arena_palloc(choose_arena(), alignment, ceil_size, 3017 run_size); 3018 } else if (alignment <= chunksize) 3019 ret = huge_malloc(ceil_size); 3020 else 3021 ret = huge_palloc(alignment, ceil_size); 3022 } 3023 3024 assert(((uintptr_t)ret & (alignment - 1)) == 0); 3025 return (ret); 3026 } 3027 3028 static void * 3029 icalloc(size_t size) 3030 { 3031 void *ret; 3032 3033 if (size <= arena_maxclass) { 3034 ret = arena_malloc(choose_arena(), size); 3035 if (ret == NULL) 3036 return (NULL); 3037 memset(ret, 0, size); 3038 } else { 3039 /* 3040 * The virtual memory system provides zero-filled pages, so 3041 * there is no need to do so manually, unless opt_junk is 3042 * enabled, in which case huge_malloc() fills huge allocations 3043 * with junk. 3044 */ 3045 ret = huge_malloc(size); 3046 if (ret == NULL) 3047 return (NULL); 3048 3049 if (OPT(junk)) 3050 memset(ret, 0, size); 3051 #ifdef USE_BRK 3052 else if ((uintptr_t)ret >= (uintptr_t)brk_base 3053 && (uintptr_t)ret < (uintptr_t)brk_max) { 3054 /* 3055 * This may be a re-used brk chunk. Therefore, zero 3056 * the memory. 3057 */ 3058 memset(ret, 0, size); 3059 } 3060 #endif 3061 } 3062 3063 return (ret); 3064 } 3065 3066 static size_t 3067 isalloc(const void *ptr) 3068 { 3069 size_t ret; 3070 arena_chunk_t *chunk; 3071 3072 assert(ptr != NULL); 3073 3074 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 3075 if (chunk != ptr) { 3076 /* Region. */ 3077 assert(chunk->arena->magic == ARENA_MAGIC); 3078 3079 ret = arena_salloc(ptr); 3080 } else { 3081 chunk_node_t *node, key; 3082 3083 /* Chunk (huge allocation). */ 3084 3085 malloc_mutex_lock(&chunks_mtx); 3086 3087 /* Extract from tree of huge allocations. */ 3088 key.chunk = __UNCONST(ptr); 3089 node = rb_tree_find_node(&huge, &key); 3090 assert(node != NULL); 3091 3092 ret = node->size; 3093 3094 malloc_mutex_unlock(&chunks_mtx); 3095 } 3096 3097 return (ret); 3098 } 3099 3100 static void * 3101 iralloc(void *ptr, size_t size) 3102 { 3103 void *ret; 3104 size_t oldsize; 3105 3106 assert(ptr != NULL); 3107 assert(size != 0); 3108 3109 oldsize = isalloc(ptr); 3110 3111 if (size <= arena_maxclass) 3112 ret = arena_ralloc(ptr, size, oldsize); 3113 else 3114 ret = huge_ralloc(ptr, size, oldsize); 3115 3116 return (ret); 3117 } 3118 3119 static void 3120 idalloc(void *ptr) 3121 { 3122 arena_chunk_t *chunk; 3123 3124 assert(ptr != NULL); 3125 3126 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 3127 if (chunk != ptr) { 3128 /* Region. */ 3129 arena_dalloc(chunk->arena, chunk, ptr); 3130 } else 3131 huge_dalloc(ptr); 3132 } 3133 3134 static void 3135 malloc_print_stats(void) 3136 { 3137 3138 if (OPT(print_stats)) { 3139 char s[UMAX2S_BUFSIZE]; 3140 _malloc_message("___ Begin malloc statistics ___\n", "", "", 3141 ""); 3142 _malloc_message("Assertions ", 3143 #ifdef NDEBUG 3144 "disabled", 3145 #else 3146 "enabled", 3147 #endif 3148 "\n", ""); 3149 _malloc_message("Boolean MALLOC_OPTIONS: ", 3150 opt_abort ? "A" : "a", 3151 opt_junk ? "J" : "j", 3152 opt_hint ? "H" : "h"); 3153 _malloc_message(OPT(utrace) ? "PU" : "Pu", 3154 opt_sysv ? "V" : "v", 3155 opt_xmalloc ? "X" : "x", 3156 opt_zero ? "Z\n" : "z\n"); 3157 3158 _malloc_message("CPUs: ", size_t2s(ncpus, s), "\n", ""); 3159 _malloc_message("Pointer size: ", size_t2s(sizeof(void *), s), 3160 "\n", ""); 3161 _malloc_message("Quantum size: ", size_t2s(quantum, s), "\n", ""); 3162 _malloc_message("Max small size: ", size_t2s(small_max, s), "\n", 3163 ""); 3164 3165 _malloc_message("Chunk size: ", size_t2s(chunksize, s), "", ""); 3166 _malloc_message(" (2^", size_t2s((size_t)opt_chunk_2pow, s), 3167 ")\n", ""); 3168 3169 #ifdef MALLOC_STATS 3170 { 3171 size_t allocated, mapped; 3172 unsigned i; 3173 arena_t *arena; 3174 3175 /* Calculate and print allocated/mapped stats. */ 3176 3177 /* arenas. */ 3178 for (i = 0, allocated = 0; i < ncpus; i++) { 3179 if (arenas[i] != NULL) { 3180 malloc_mutex_lock(&arenas[i]->mtx); 3181 allocated += 3182 arenas[i]->stats.allocated_small; 3183 allocated += 3184 arenas[i]->stats.allocated_large; 3185 malloc_mutex_unlock(&arenas[i]->mtx); 3186 } 3187 } 3188 3189 /* huge/base. */ 3190 malloc_mutex_lock(&chunks_mtx); 3191 allocated += huge_allocated; 3192 mapped = stats_chunks.curchunks * chunksize; 3193 malloc_mutex_unlock(&chunks_mtx); 3194 3195 malloc_mutex_lock(&base_mtx); 3196 mapped += base_mapped; 3197 malloc_mutex_unlock(&base_mtx); 3198 3199 malloc_printf("Allocated: %zu, mapped: %zu\n", 3200 allocated, mapped); 3201 3202 /* Print chunk stats. */ 3203 { 3204 chunk_stats_t chunks_stats; 3205 3206 malloc_mutex_lock(&chunks_mtx); 3207 chunks_stats = stats_chunks; 3208 malloc_mutex_unlock(&chunks_mtx); 3209 3210 malloc_printf("chunks: nchunks " 3211 "highchunks curchunks\n"); 3212 malloc_printf(" %13llu%13lu%13lu\n", 3213 chunks_stats.nchunks, 3214 chunks_stats.highchunks, 3215 chunks_stats.curchunks); 3216 } 3217 3218 /* Print chunk stats. */ 3219 malloc_printf( 3220 "huge: nmalloc ndalloc " 3221 "nralloc allocated\n"); 3222 malloc_printf(" %12llu %12llu %12llu %12zu\n", 3223 huge_nmalloc, huge_ndalloc, huge_nralloc, 3224 huge_allocated); 3225 3226 /* Print stats for each arena. */ 3227 for (i = 0; i < ncpus; i++) { 3228 arena = arenas[i]; 3229 if (arena != NULL) { 3230 malloc_printf( 3231 "\narenas[%u] @ %p\n", i, arena); 3232 malloc_mutex_lock(&arena->mtx); 3233 stats_print(arena); 3234 malloc_mutex_unlock(&arena->mtx); 3235 } 3236 } 3237 } 3238 #endif /* #ifdef MALLOC_STATS */ 3239 _malloc_message("--- End malloc statistics ---\n", "", "", ""); 3240 } 3241 } 3242 3243 /* 3244 * libpthread might call malloc(3), so the malloc implementation has to take 3245 * pains to avoid infinite recursion during initialization. 3246 */ 3247 static inline bool 3248 malloc_init(void) 3249 { 3250 3251 if (__predict_false(malloc_initialized == false)) 3252 return (malloc_init_hard()); 3253 3254 return (false); 3255 } 3256 3257 static bool 3258 malloc_init_hard(void) 3259 { 3260 unsigned i, j; 3261 ssize_t linklen; 3262 char buf[PATH_MAX + 1]; 3263 const char *opts = ""; 3264 int serrno; 3265 3266 malloc_mutex_lock(&init_lock); 3267 if (malloc_initialized) { 3268 /* 3269 * Another thread initialized the allocator before this one 3270 * acquired init_lock. 3271 */ 3272 malloc_mutex_unlock(&init_lock); 3273 return (false); 3274 } 3275 3276 serrno = errno; 3277 /* Get number of CPUs. */ 3278 { 3279 int mib[2]; 3280 size_t len; 3281 3282 mib[0] = CTL_HW; 3283 mib[1] = HW_NCPU; 3284 len = sizeof(ncpus); 3285 if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) { 3286 /* Error. */ 3287 ncpus = 1; 3288 } 3289 } 3290 3291 /* Get page size. */ 3292 { 3293 long result; 3294 3295 result = getpagesize(); 3296 assert(result != -1); 3297 pagesize = (unsigned) result; 3298 3299 /* 3300 * We assume that pagesize is a power of 2 when calculating 3301 * pagesize_mask and pagesize_2pow. 3302 */ 3303 assert(((result - 1) & result) == 0); 3304 pagesize_mask = result - 1; 3305 pagesize_2pow = ffs((int)result) - 1; 3306 } 3307 3308 for (i = 0; i < 3; i++) { 3309 /* Get runtime configuration. */ 3310 switch (i) { 3311 case 0: 3312 if ((linklen = readlink("/etc/malloc.conf", buf, 3313 sizeof(buf) - 1)) != -1) { 3314 /* 3315 * Use the contents of the "/etc/malloc.conf" 3316 * symbolic link's name. 3317 */ 3318 buf[linklen] = '\0'; 3319 opts = buf; 3320 } else { 3321 /* No configuration specified. */ 3322 buf[0] = '\0'; 3323 opts = buf; 3324 } 3325 break; 3326 case 1: 3327 if ((opts = getenv("MALLOC_OPTIONS")) != NULL && 3328 issetugid() == 0) { 3329 /* 3330 * Do nothing; opts is already initialized to 3331 * the value of the MALLOC_OPTIONS environment 3332 * variable. 3333 */ 3334 } else { 3335 /* No configuration specified. */ 3336 buf[0] = '\0'; 3337 opts = buf; 3338 } 3339 break; 3340 case 2: 3341 if (_malloc_options != NULL) { 3342 /* 3343 * Use options that were compiled into the program. 3344 */ 3345 opts = _malloc_options; 3346 } else { 3347 /* No configuration specified. */ 3348 buf[0] = '\0'; 3349 opts = buf; 3350 } 3351 break; 3352 default: 3353 /* NOTREACHED */ 3354 /* LINTED */ 3355 assert(false); 3356 } 3357 3358 for (j = 0; opts[j] != '\0'; j++) { 3359 switch (opts[j]) { 3360 case 'a': 3361 opt_abort = false; 3362 break; 3363 case 'A': 3364 opt_abort = true; 3365 break; 3366 case 'h': 3367 opt_hint = false; 3368 break; 3369 case 'H': 3370 opt_hint = true; 3371 break; 3372 case 'j': 3373 opt_junk = false; 3374 break; 3375 case 'J': 3376 opt_junk = true; 3377 break; 3378 case 'k': 3379 /* 3380 * Chunks always require at least one header 3381 * page, so chunks can never be smaller than 3382 * two pages. 3383 */ 3384 if (opt_chunk_2pow > pagesize_2pow + 1) 3385 opt_chunk_2pow--; 3386 break; 3387 case 'K': 3388 if (opt_chunk_2pow + 1 < 3389 (int)(sizeof(size_t) << 3)) 3390 opt_chunk_2pow++; 3391 break; 3392 case 'p': 3393 opt_print_stats = false; 3394 break; 3395 case 'P': 3396 opt_print_stats = true; 3397 break; 3398 case 'q': 3399 if (opt_quantum_2pow > QUANTUM_2POW_MIN) 3400 opt_quantum_2pow--; 3401 break; 3402 case 'Q': 3403 if (opt_quantum_2pow < pagesize_2pow - 1) 3404 opt_quantum_2pow++; 3405 break; 3406 case 's': 3407 if (opt_small_max_2pow > QUANTUM_2POW_MIN) 3408 opt_small_max_2pow--; 3409 break; 3410 case 'S': 3411 if (opt_small_max_2pow < pagesize_2pow - 1) 3412 opt_small_max_2pow++; 3413 break; 3414 case 'u': 3415 opt_utrace = false; 3416 break; 3417 case 'U': 3418 opt_utrace = true; 3419 break; 3420 case 'v': 3421 opt_sysv = false; 3422 break; 3423 case 'V': 3424 opt_sysv = true; 3425 break; 3426 case 'x': 3427 opt_xmalloc = false; 3428 break; 3429 case 'X': 3430 opt_xmalloc = true; 3431 break; 3432 case 'z': 3433 opt_zero = false; 3434 break; 3435 case 'Z': 3436 opt_zero = true; 3437 break; 3438 default: { 3439 char cbuf[2]; 3440 3441 cbuf[0] = opts[j]; 3442 cbuf[1] = '\0'; 3443 _malloc_message(getprogname(), 3444 ": (malloc) Unsupported character in " 3445 "malloc options: '", cbuf, "'\n"); 3446 } 3447 } 3448 } 3449 } 3450 errno = serrno; 3451 3452 /* Take care to call atexit() only once. */ 3453 if (OPT(print_stats)) { 3454 /* Print statistics at exit. */ 3455 atexit(malloc_print_stats); 3456 } 3457 3458 /* Set variables according to the value of opt_small_max_2pow. */ 3459 if (opt_small_max_2pow < opt_quantum_2pow) 3460 opt_small_max_2pow = opt_quantum_2pow; 3461 small_max = (1U << opt_small_max_2pow); 3462 3463 /* Set bin-related variables. */ 3464 bin_maxclass = (pagesize >> 1); 3465 assert(opt_quantum_2pow >= TINY_MIN_2POW); 3466 ntbins = (unsigned)(opt_quantum_2pow - TINY_MIN_2POW); 3467 assert(ntbins <= (unsigned)opt_quantum_2pow); 3468 nqbins = (unsigned)(small_max >> opt_quantum_2pow); 3469 nsbins = (unsigned)(pagesize_2pow - opt_small_max_2pow - 1); 3470 3471 /* Set variables according to the value of opt_quantum_2pow. */ 3472 quantum = (1 << opt_quantum_2pow); 3473 quantum_mask = quantum - 1; 3474 if (ntbins > 0) 3475 small_min = (quantum >> 1) + 1; 3476 else 3477 small_min = 1; 3478 assert(small_min <= quantum); 3479 3480 /* Set variables according to the value of opt_chunk_2pow. */ 3481 chunksize = (1LU << opt_chunk_2pow); 3482 chunksize_mask = chunksize - 1; 3483 chunksize_2pow = (unsigned)opt_chunk_2pow; 3484 chunk_npages = (unsigned)(chunksize >> pagesize_2pow); 3485 { 3486 unsigned header_size; 3487 3488 header_size = (unsigned)(sizeof(arena_chunk_t) + 3489 (sizeof(arena_chunk_map_t) * (chunk_npages - 1))); 3490 arena_chunk_header_npages = (header_size >> pagesize_2pow); 3491 if ((header_size & pagesize_mask) != 0) 3492 arena_chunk_header_npages++; 3493 } 3494 arena_maxclass = chunksize - (arena_chunk_header_npages << 3495 pagesize_2pow); 3496 3497 UTRACE(0, 0, 0); 3498 3499 #ifdef MALLOC_STATS 3500 memset(&stats_chunks, 0, sizeof(chunk_stats_t)); 3501 #endif 3502 3503 /* Various sanity checks that regard configuration. */ 3504 assert(quantum >= sizeof(void *)); 3505 assert(quantum <= pagesize); 3506 assert(chunksize >= pagesize); 3507 assert(quantum * 4 <= chunksize); 3508 3509 /* Initialize chunks data. */ 3510 malloc_mutex_init(&chunks_mtx); 3511 rb_tree_init(&huge, &chunk_tree_ops); 3512 #ifdef USE_BRK 3513 malloc_mutex_init(&brk_mtx); 3514 brk_base = sbrk(0); 3515 brk_prev = brk_base; 3516 brk_max = brk_base; 3517 #endif 3518 #ifdef MALLOC_STATS 3519 huge_nmalloc = 0; 3520 huge_ndalloc = 0; 3521 huge_nralloc = 0; 3522 huge_allocated = 0; 3523 #endif 3524 rb_tree_init(&old_chunks, &chunk_tree_ops); 3525 3526 /* Initialize base allocation data structures. */ 3527 #ifdef MALLOC_STATS 3528 base_mapped = 0; 3529 #endif 3530 #ifdef USE_BRK 3531 /* 3532 * Allocate a base chunk here, since it doesn't actually have to be 3533 * chunk-aligned. Doing this before allocating any other chunks allows 3534 * the use of space that would otherwise be wasted. 3535 */ 3536 base_pages_alloc(0); 3537 #endif 3538 base_chunk_nodes = NULL; 3539 malloc_mutex_init(&base_mtx); 3540 3541 /* Allocate and initialize arenas. */ 3542 arenas = (arena_t **)base_alloc(sizeof(arena_t *) * ncpus); 3543 if (arenas == NULL) { 3544 malloc_mutex_unlock(&init_lock); 3545 return (true); 3546 } 3547 /* 3548 * Zero the array. In practice, this should always be pre-zeroed, 3549 * since it was just mmap()ed, but let's be sure. 3550 */ 3551 memset(arenas, 0, sizeof(arena_t *) * ncpus); 3552 3553 /* 3554 * Initialize one arena here. The rest are lazily created in 3555 * arena_choose_hard(). 3556 */ 3557 if ((arenas[0] = arenas_extend()) == NULL) { 3558 malloc_mutex_unlock(&init_lock); 3559 return (true); 3560 } 3561 3562 malloc_mutex_init(&arenas_mtx); 3563 3564 malloc_initialized = true; 3565 malloc_mutex_unlock(&init_lock); 3566 return (false); 3567 } 3568 3569 /* 3570 * End general internal functions. 3571 */ 3572 /******************************************************************************/ 3573 /* 3574 * Begin malloc(3)-compatible functions. 3575 */ 3576 3577 void * 3578 malloc(size_t size) 3579 { 3580 void *ret; 3581 3582 if (__predict_false(malloc_init())) { 3583 ret = NULL; 3584 goto RETURN; 3585 } 3586 3587 if (__predict_false(size == 0)) { 3588 if (NOT_OPT(sysv)) 3589 size = 1; 3590 else { 3591 ret = NULL; 3592 goto RETURN; 3593 } 3594 } 3595 3596 ret = imalloc(size); 3597 3598 RETURN: 3599 if (__predict_false(ret == NULL)) { 3600 if (OPT(xmalloc)) { 3601 _malloc_message(getprogname(), 3602 ": (malloc) Error in malloc(): out of memory\n", "", 3603 ""); 3604 abort(); 3605 } 3606 errno = ENOMEM; 3607 } 3608 3609 UTRACE(0, size, ret); 3610 return (ret); 3611 } 3612 3613 int 3614 posix_memalign(void **memptr, size_t alignment, size_t size) 3615 { 3616 int ret; 3617 void *result; 3618 3619 if (__predict_false(malloc_init())) 3620 result = NULL; 3621 else { 3622 /* Make sure that alignment is a large enough power of 2. */ 3623 if (((alignment - 1) & alignment) != 0 3624 || alignment < sizeof(void *)) { 3625 if (OPT(xmalloc)) { 3626 _malloc_message(getprogname(), 3627 ": (malloc) Error in posix_memalign(): " 3628 "invalid alignment\n", "", ""); 3629 abort(); 3630 } 3631 result = NULL; 3632 ret = EINVAL; 3633 goto RETURN; 3634 } 3635 3636 if (size == 0) { 3637 if (NOT_OPT(sysv)) 3638 size = 1; 3639 else { 3640 result = NULL; 3641 ret = 0; 3642 goto RETURN; 3643 } 3644 } 3645 result = ipalloc(alignment, size); 3646 } 3647 3648 if (__predict_false(result == NULL)) { 3649 if (OPT(xmalloc)) { 3650 _malloc_message(getprogname(), 3651 ": (malloc) Error in posix_memalign(): out of memory\n", 3652 "", ""); 3653 abort(); 3654 } 3655 ret = ENOMEM; 3656 goto RETURN; 3657 } 3658 3659 *memptr = result; 3660 ret = 0; 3661 3662 RETURN: 3663 UTRACE(0, size, result); 3664 return (ret); 3665 } 3666 3667 void * 3668 calloc(size_t num, size_t size) 3669 { 3670 void *ret; 3671 size_t num_size; 3672 3673 if (__predict_false(malloc_init())) { 3674 num_size = 0; 3675 ret = NULL; 3676 goto RETURN; 3677 } 3678 3679 num_size = num * size; 3680 if (__predict_false(num_size == 0)) { 3681 if (NOT_OPT(sysv) && ((num == 0) || (size == 0))) 3682 num_size = 1; 3683 else { 3684 ret = NULL; 3685 goto RETURN; 3686 } 3687 /* 3688 * Try to avoid division here. We know that it isn't possible to 3689 * overflow during multiplication if neither operand uses any of the 3690 * most significant half of the bits in a size_t. 3691 */ 3692 } else if ((unsigned long long)((num | size) & 3693 ((unsigned long long)SIZE_T_MAX << (sizeof(size_t) << 2))) && 3694 (num_size / size != num)) { 3695 /* size_t overflow. */ 3696 ret = NULL; 3697 goto RETURN; 3698 } 3699 3700 ret = icalloc(num_size); 3701 3702 RETURN: 3703 if (__predict_false(ret == NULL)) { 3704 if (OPT(xmalloc)) { 3705 _malloc_message(getprogname(), 3706 ": (malloc) Error in calloc(): out of memory\n", "", 3707 ""); 3708 abort(); 3709 } 3710 errno = ENOMEM; 3711 } 3712 3713 UTRACE(0, num_size, ret); 3714 return (ret); 3715 } 3716 3717 void * 3718 realloc(void *ptr, size_t size) 3719 { 3720 void *ret; 3721 3722 if (__predict_false(size == 0)) { 3723 if (NOT_OPT(sysv)) 3724 size = 1; 3725 else { 3726 if (ptr != NULL) 3727 idalloc(ptr); 3728 ret = NULL; 3729 goto RETURN; 3730 } 3731 } 3732 3733 if (__predict_true(ptr != NULL)) { 3734 assert(malloc_initialized); 3735 3736 ret = iralloc(ptr, size); 3737 3738 if (__predict_false(ret == NULL)) { 3739 if (OPT(xmalloc)) { 3740 _malloc_message(getprogname(), 3741 ": (malloc) Error in realloc(): out of " 3742 "memory\n", "", ""); 3743 abort(); 3744 } 3745 errno = ENOMEM; 3746 } 3747 } else { 3748 if (__predict_false(malloc_init())) 3749 ret = NULL; 3750 else 3751 ret = imalloc(size); 3752 3753 if (__predict_false(ret == NULL)) { 3754 if (OPT(xmalloc)) { 3755 _malloc_message(getprogname(), 3756 ": (malloc) Error in realloc(): out of " 3757 "memory\n", "", ""); 3758 abort(); 3759 } 3760 errno = ENOMEM; 3761 } 3762 } 3763 3764 RETURN: 3765 UTRACE(ptr, size, ret); 3766 return (ret); 3767 } 3768 3769 void 3770 free(void *ptr) 3771 { 3772 3773 UTRACE(ptr, 0, 0); 3774 if (__predict_true(ptr != NULL)) { 3775 assert(malloc_initialized); 3776 3777 idalloc(ptr); 3778 } 3779 } 3780 3781 /* 3782 * End malloc(3)-compatible functions. 3783 */ 3784 /******************************************************************************/ 3785 /* 3786 * Begin non-standard functions. 3787 */ 3788 size_t 3789 malloc_usable_size(const void *ptr) 3790 { 3791 3792 assert(ptr != NULL); 3793 3794 return (isalloc(ptr)); 3795 } 3796 3797 /* 3798 * End non-standard functions. 3799 */ 3800 /******************************************************************************/ 3801 /* 3802 * Begin library-private functions, used by threading libraries for protection 3803 * of malloc during fork(). These functions are only called if the program is 3804 * running in threaded mode, so there is no need to check whether the program 3805 * is threaded here. 3806 */ 3807 3808 void 3809 _malloc_prefork(void) 3810 { 3811 unsigned i; 3812 3813 /* Acquire all mutexes in a safe order. */ 3814 malloc_mutex_lock(&init_lock); 3815 malloc_mutex_lock(&arenas_mtx); 3816 for (i = 0; i < ncpus; i++) { 3817 if (arenas[i] != NULL) 3818 malloc_mutex_lock(&arenas[i]->mtx); 3819 } 3820 malloc_mutex_lock(&chunks_mtx); 3821 malloc_mutex_lock(&base_mtx); 3822 #ifdef USE_BRK 3823 malloc_mutex_lock(&brk_mtx); 3824 #endif 3825 } 3826 3827 void 3828 _malloc_postfork(void) 3829 { 3830 unsigned i; 3831 3832 /* Release all mutexes, now that fork() has completed. */ 3833 #ifdef USE_BRK 3834 malloc_mutex_unlock(&brk_mtx); 3835 #endif 3836 malloc_mutex_unlock(&base_mtx); 3837 malloc_mutex_unlock(&chunks_mtx); 3838 3839 for (i = ncpus; i-- > 0; ) { 3840 if (arenas[i] != NULL) 3841 malloc_mutex_unlock(&arenas[i]->mtx); 3842 } 3843 malloc_mutex_unlock(&arenas_mtx); 3844 malloc_mutex_unlock(&init_lock); 3845 } 3846 3847 void 3848 _malloc_postfork_child(void) 3849 { 3850 unsigned i; 3851 3852 /* Release all mutexes, now that fork() has completed. */ 3853 #ifdef USE_BRK 3854 malloc_mutex_init(&brk_mtx); 3855 #endif 3856 malloc_mutex_init(&base_mtx); 3857 malloc_mutex_init(&chunks_mtx); 3858 3859 for (i = ncpus; i-- > 0; ) { 3860 if (arenas[i] != NULL) 3861 malloc_mutex_init(&arenas[i]->mtx); 3862 } 3863 malloc_mutex_init(&arenas_mtx); 3864 malloc_mutex_init(&init_lock); 3865 } 3866 3867 /* 3868 * End library-private functions. 3869 */ 3870 /******************************************************************************/ 3871