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