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