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