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