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