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