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