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