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