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