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