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