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