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