1 /* -*- Mode: C; tab-width: 8; c-basic-offset: 8 -*- */ 2 /* vim:set softtabstop=8 shiftwidth=8: */ 3 /*- 4 * Copyright (C) 2006-2008 Jason Evans <jasone (at) FreeBSD.org>. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice(s), this list of conditions and the following disclaimer as 12 * the first lines of this file unmodified other than the possible 13 * addition of one or more copyright notices. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice(s), this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE 23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 26 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 28 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 29 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 * 31 ******************************************************************************* 32 * 33 * This allocator implementation is designed to provide scalable performance 34 * for multi-threaded programs on multi-processor systems. The following 35 * features are included for this purpose: 36 * 37 * + Multiple arenas are used if there are multiple CPUs, which reduces lock 38 * contention and cache sloshing. 39 * 40 * + Cache line sharing between arenas is avoided for internal data 41 * structures. 42 * 43 * + Memory is managed in chunks and runs (chunks can be split into runs), 44 * rather than as individual pages. This provides a constant-time 45 * mechanism for associating allocations with particular arenas. 46 * 47 * Allocation requests are rounded up to the nearest size class, and no record 48 * of the original request size is maintained. Allocations are broken into 49 * categories according to size class. Assuming runtime defaults, 4 kB pages 50 * and a 16 byte quantum on a 32-bit system, the size classes in each category 51 * are as follows: 52 * 53 * |=====================================| 54 * | Category | Subcategory | Size | 55 * |=====================================| 56 * | Small | Tiny | 2 | 57 * | | | 4 | 58 * | | | 8 | 59 * | |----------------+---------| 60 * | | Quantum-spaced | 16 | 61 * | | | 32 | 62 * | | | 48 | 63 * | | | ... | 64 * | | | 480 | 65 * | | | 496 | 66 * | | | 512 | 67 * | |----------------+---------| 68 * | | Sub-page | 1 kB | 69 * | | | 2 kB | 70 * |=====================================| 71 * | Large | 4 kB | 72 * | | 8 kB | 73 * | | 12 kB | 74 * | | ... | 75 * | | 1012 kB | 76 * | | 1016 kB | 77 * | | 1020 kB | 78 * |=====================================| 79 * | Huge | 1 MB | 80 * | | 2 MB | 81 * | | 3 MB | 82 * | | ... | 83 * |=====================================| 84 * 85 * A different mechanism is used for each category: 86 * 87 * Small : Each size class is segregated into its own set of runs. Each run 88 * maintains a bitmap of which regions are free/allocated. 89 * 90 * Large : Each allocation is backed by a dedicated run. Metadata are stored 91 * in the associated arena chunk header maps. 92 * 93 * Huge : Each allocation is backed by a dedicated contiguous set of chunks. 94 * Metadata are stored in a separate red-black tree. 95 * 96 ******************************************************************************* 97 */ 98 99 /* 100 * MALLOC_PRODUCTION disables assertions and statistics gathering. It also 101 * defaults the A and J runtime options to off. These settings are appropriate 102 * for production systems. 103 */ 104 #ifndef MOZ_MEMORY_DEBUG 105 # define MALLOC_PRODUCTION 106 #endif 107 108 /* 109 * Use only one arena by default. Mozilla does not currently make extensive 110 * use of concurrent allocation, so the increased fragmentation associated with 111 * multiple arenas is not warranted. 112 */ 113 #define MOZ_MEMORY_NARENAS_DEFAULT_ONE 114 115 /* 116 * MALLOC_STATS enables statistics calculation, and is required for 117 * jemalloc_stats(). 118 */ 119 #define MALLOC_STATS 120 121 #ifndef MALLOC_PRODUCTION 122 /* 123 * MALLOC_DEBUG enables assertions and other sanity checks, and disables 124 * inline functions. 125 */ 126 # define MALLOC_DEBUG 127 128 /* Memory filling (junk/zero). */ 129 # define MALLOC_FILL 130 131 /* Allocation tracing. */ 132 # ifndef MOZ_MEMORY_WINDOWS 133 # define MALLOC_UTRACE 134 # endif 135 136 /* Support optional abort() on OOM. */ 137 # define MALLOC_XMALLOC 138 139 /* Support SYSV semantics. */ 140 # define MALLOC_SYSV 141 #endif 142 143 /* 144 * MALLOC_VALIDATE causes malloc_usable_size() to perform some pointer 145 * validation. There are many possible errors that validation does not even 146 * attempt to detect. 147 */ 148 #define MALLOC_VALIDATE 149 150 /* Embed no-op macros that support memory allocation tracking via valgrind. */ 151 #ifdef MOZ_VALGRIND 152 # define MALLOC_VALGRIND 153 #endif 154 #ifdef MALLOC_VALGRIND 155 # include <valgrind/valgrind.h> 156 #else 157 # define VALGRIND_MALLOCLIKE_BLOCK(addr, sizeB, rzB, is_zeroed) 158 # define VALGRIND_FREELIKE_BLOCK(addr, rzB) 159 #endif 160 161 /* 162 * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically 163 * re-balances arena load if exponentially averaged contention exceeds a 164 * certain threshold. 165 */ 166 /* #define MALLOC_BALANCE */ 167 168 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN)) 169 /* 170 * MALLOC_PAGEFILE causes all mmap()ed memory to be backed by temporary 171 * files, so that if a chunk is mapped, it is guaranteed to be swappable. 172 * This avoids asynchronous OOM failures that are due to VM over-commit. 173 * 174 * XXX OS X over-commits, so we should probably use mmap() instead of 175 * vm_allocate(), so that MALLOC_PAGEFILE works. 176 */ 177 #define MALLOC_PAGEFILE 178 #endif 179 180 #ifdef MALLOC_PAGEFILE 181 /* Write size when initializing a page file. */ 182 # define MALLOC_PAGEFILE_WRITE_SIZE 512 183 #endif 184 185 #ifdef MOZ_MEMORY_LINUX 186 #define _GNU_SOURCE /* For mremap(2). */ 187 #define issetugid() 0 188 #if 0 /* Enable in order to test decommit code on Linux. */ 189 # define MALLOC_DECOMMIT 190 #endif 191 #endif 192 193 #ifndef MOZ_MEMORY_WINCE 194 #include <sys/types.h> 195 196 #include <errno.h> 197 #include <stdlib.h> 198 #endif 199 #include <limits.h> 200 #include <stdarg.h> 201 #include <stdio.h> 202 #include <string.h> 203 204 #ifdef MOZ_MEMORY_WINDOWS 205 #ifndef MOZ_MEMORY_WINCE 206 #include <cruntime.h> 207 #include <internal.h> 208 #include <io.h> 209 #else 210 #include <cmnintrin.h> 211 #include <crtdefs.h> 212 #define SIZE_MAX UINT_MAX 213 #endif 214 #include <windows.h> 215 216 #pragma warning( disable: 4267 4996 4146 ) 217 218 #define false FALSE 219 #define true TRUE 220 #define inline __inline 221 #define SIZE_T_MAX SIZE_MAX 222 #define STDERR_FILENO 2 223 #define PATH_MAX MAX_PATH 224 #define vsnprintf _vsnprintf 225 226 #ifndef NO_TLS 227 static unsigned long tlsIndex = 0xffffffff; 228 #endif 229 230 #define __thread 231 #ifdef MOZ_MEMORY_WINCE 232 #define _pthread_self() GetCurrentThreadId() 233 #else 234 #define _pthread_self() __threadid() 235 #endif 236 #define issetugid() 0 237 238 #ifndef MOZ_MEMORY_WINCE 239 /* use MSVC intrinsics */ 240 #pragma intrinsic(_BitScanForward) 241 static __forceinline int 242 ffs(int x) 243 { 244 unsigned long i; 245 246 if (_BitScanForward(&i, x) != 0) 247 return (i + 1); 248 249 return (0); 250 } 251 252 /* Implement getenv without using malloc */ 253 static char mozillaMallocOptionsBuf[64]; 254 255 #define getenv xgetenv 256 static char * 257 getenv(const char *name) 258 { 259 260 if (GetEnvironmentVariableA(name, (LPSTR)&mozillaMallocOptionsBuf, 261 sizeof(mozillaMallocOptionsBuf)) > 0) 262 return (mozillaMallocOptionsBuf); 263 264 return (NULL); 265 } 266 267 #else /* WIN CE */ 268 269 #define ENOMEM 12 270 #define EINVAL 22 271 272 static __forceinline int 273 ffs(int x) 274 { 275 276 return 32 - _CountLeadingZeros((-x) & x); 277 } 278 #endif 279 280 typedef unsigned char uint8_t; 281 typedef unsigned uint32_t; 282 typedef unsigned long long uint64_t; 283 typedef unsigned long long uintmax_t; 284 typedef long ssize_t; 285 286 #define MALLOC_DECOMMIT 287 #endif 288 289 #ifndef MOZ_MEMORY_WINDOWS 290 #ifndef MOZ_MEMORY_SOLARIS 291 #include <sys/cdefs.h> 292 #endif 293 #ifndef __DECONST 294 # define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var)) 295 #endif 296 #ifndef MOZ_MEMORY 297 __FBSDID("$FreeBSD: head/lib/libc/stdlib/malloc.c 180599 2008-07-18 19:35:44Z jasone $"); 298 #include "libc_private.h" 299 #ifdef MALLOC_DEBUG 300 # define _LOCK_DEBUG 301 #endif 302 #include "spinlock.h" 303 #include "namespace.h" 304 #endif 305 #include <sys/mman.h> 306 #ifndef MADV_FREE 307 # define MADV_FREE MADV_DONTNEED 308 #endif 309 #ifndef MAP_NOSYNC 310 # define MAP_NOSYNC 0 311 #endif 312 #include <sys/param.h> 313 #ifndef MOZ_MEMORY 314 #include <sys/stddef.h> 315 #endif 316 #include <sys/time.h> 317 #include <sys/types.h> 318 #ifndef MOZ_MEMORY_SOLARIS 319 #include <sys/sysctl.h> 320 #endif 321 #include <sys/uio.h> 322 #ifndef MOZ_MEMORY 323 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */ 324 325 #include <machine/atomic.h> 326 #include <machine/cpufunc.h> 327 #include <machine/vmparam.h> 328 #endif 329 330 #include <errno.h> 331 #include <limits.h> 332 #ifndef SIZE_T_MAX 333 # define SIZE_T_MAX SIZE_MAX 334 #endif 335 #include <pthread.h> 336 #ifdef MOZ_MEMORY_DARWIN 337 #define _pthread_self pthread_self 338 #define _pthread_mutex_init pthread_mutex_init 339 #define _pthread_mutex_trylock pthread_mutex_trylock 340 #define _pthread_mutex_lock pthread_mutex_lock 341 #define _pthread_mutex_unlock pthread_mutex_unlock 342 #endif 343 #include <sched.h> 344 #include <stdarg.h> 345 #include <stdbool.h> 346 #include <stdio.h> 347 #include <stdint.h> 348 #include <stdlib.h> 349 #include <string.h> 350 #ifndef MOZ_MEMORY_DARWIN 351 #include <strings.h> 352 #endif 353 #include <unistd.h> 354 355 #ifdef MOZ_MEMORY_DARWIN 356 #include <libkern/OSAtomic.h> 357 #include <mach/mach_error.h> 358 #include <mach/mach_init.h> 359 #include <mach/vm_map.h> 360 #include <malloc/malloc.h> 361 #endif 362 363 #ifndef MOZ_MEMORY 364 #include "un-namespace.h" 365 #endif 366 367 #endif 368 369 #include "jemalloc.h" 370 371 #undef bool 372 #define bool jemalloc_bool 373 374 #ifdef MOZ_MEMORY_DARWIN 375 static const bool __isthreaded = true; 376 #endif 377 378 #if defined(MOZ_MEMORY_SOLARIS) && defined(MAP_ALIGN) && !defined(JEMALLOC_NEVER_USES_MAP_ALIGN) 379 #define JEMALLOC_USES_MAP_ALIGN /* Required on Solaris 10. Might improve performance elsewhere. */ 380 #endif 381 382 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6) 383 #define JEMALLOC_USES_MAP_ALIGN /* Required for Windows CE < 6 */ 384 #endif 385 386 #define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var)) 387 388 #include "qr.h" 389 #include "ql.h" 390 #ifdef MOZ_MEMORY_WINDOWS 391 /* MSVC++ does not support C99 variable-length arrays. */ 392 # define RB_NO_C99_VARARRAYS 393 #endif 394 #include "rb.h" 395 396 #ifdef MALLOC_DEBUG 397 /* Disable inlining to make debugging easier. */ 398 #ifdef inline 399 #undef inline 400 #endif 401 402 # define inline 403 #endif 404 405 /* Size of stack-allocated buffer passed to strerror_r(). */ 406 #define STRERROR_BUF 64 407 408 /* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */ 409 # define QUANTUM_2POW_MIN 4 410 #ifdef MOZ_MEMORY_SIZEOF_PTR_2POW 411 # define SIZEOF_PTR_2POW MOZ_MEMORY_SIZEOF_PTR_2POW 412 #else 413 # define SIZEOF_PTR_2POW 2 414 #endif 415 #define PIC 416 #ifndef MOZ_MEMORY_DARWIN 417 static const bool __isthreaded = true; 418 #else 419 # define NO_TLS 420 #endif 421 #if 0 422 #ifdef __i386__ 423 # define QUANTUM_2POW_MIN 4 424 # define SIZEOF_PTR_2POW 2 425 # define CPU_SPINWAIT __asm__ volatile("pause") 426 #endif 427 #ifdef __ia64__ 428 # define QUANTUM_2POW_MIN 4 429 # define SIZEOF_PTR_2POW 3 430 #endif 431 #ifdef __alpha__ 432 # define QUANTUM_2POW_MIN 4 433 # define SIZEOF_PTR_2POW 3 434 # define NO_TLS 435 #endif 436 #ifdef __sparc64__ 437 # define QUANTUM_2POW_MIN 4 438 # define SIZEOF_PTR_2POW 3 439 # define NO_TLS 440 #endif 441 #ifdef __amd64__ 442 # define QUANTUM_2POW_MIN 4 443 # define SIZEOF_PTR_2POW 3 444 # define CPU_SPINWAIT __asm__ volatile("pause") 445 #endif 446 #ifdef __arm__ 447 # define QUANTUM_2POW_MIN 3 448 # define SIZEOF_PTR_2POW 2 449 # define NO_TLS 450 #endif 451 #ifdef __mips__ 452 # define QUANTUM_2POW_MIN 3 453 # define SIZEOF_PTR_2POW 2 454 # define NO_TLS 455 #endif 456 #ifdef __powerpc__ 457 # define QUANTUM_2POW_MIN 4 458 # define SIZEOF_PTR_2POW 2 459 #endif 460 #endif 461 462 #define SIZEOF_PTR (1U << SIZEOF_PTR_2POW) 463 464 /* sizeof(int) == (1U << SIZEOF_INT_2POW). */ 465 #ifndef SIZEOF_INT_2POW 466 # define SIZEOF_INT_2POW 2 467 #endif 468 469 /* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */ 470 #if (!defined(PIC) && !defined(NO_TLS)) 471 # define NO_TLS 472 #endif 473 474 #ifdef NO_TLS 475 /* MALLOC_BALANCE requires TLS. */ 476 # ifdef MALLOC_BALANCE 477 # undef MALLOC_BALANCE 478 # endif 479 #endif 480 481 /* 482 * Size and alignment of memory chunks that are allocated by the OS's virtual 483 * memory system. 484 */ 485 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6) 486 #define CHUNK_2POW_DEFAULT 21 487 #else 488 #define CHUNK_2POW_DEFAULT 20 489 #endif 490 /* Maximum number of dirty pages per arena. */ 491 #define DIRTY_MAX_DEFAULT (1U << 10) 492 493 /* Default reserve chunks. */ 494 #define RESERVE_MIN_2POW_DEFAULT 1 495 /* 496 * Default range (in chunks) between reserve_min and reserve_max, in addition 497 * to the mandatory one chunk per arena. 498 */ 499 #ifdef MALLOC_PAGEFILE 500 # define RESERVE_RANGE_2POW_DEFAULT 5 501 #else 502 # define RESERVE_RANGE_2POW_DEFAULT 0 503 #endif 504 505 /* 506 * Maximum size of L1 cache line. This is used to avoid cache line aliasing, 507 * so over-estimates are okay (up to a point), but under-estimates will 508 * negatively affect performance. 509 */ 510 #define CACHELINE_2POW 6 511 #define CACHELINE ((size_t)(1U << CACHELINE_2POW)) 512 513 /* Smallest size class to support. */ 514 #define TINY_MIN_2POW 1 515 516 /* 517 * Maximum size class that is a multiple of the quantum, but not (necessarily) 518 * a power of 2. Above this size, allocations are rounded up to the nearest 519 * power of 2. 520 */ 521 #define SMALL_MAX_2POW_DEFAULT 9 522 #define SMALL_MAX_DEFAULT (1U << SMALL_MAX_2POW_DEFAULT) 523 524 /* 525 * RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized 526 * as small as possible such that this setting is still honored, without 527 * violating other constraints. The goal is to make runs as small as possible 528 * without exceeding a per run external fragmentation threshold. 529 * 530 * We use binary fixed point math for overhead computations, where the binary 531 * point is implicitly RUN_BFP bits to the left. 532 * 533 * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be 534 * honored for some/all object sizes, since there is one bit of header overhead 535 * per object (plus a constant). This constraint is relaxed (ignored) for runs 536 * that are so small that the per-region overhead is greater than: 537 * 538 * (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP)) 539 */ 540 #define RUN_BFP 12 541 /* \/ Implicit binary fixed point. */ 542 #define RUN_MAX_OVRHD 0x0000003dU 543 #define RUN_MAX_OVRHD_RELAX 0x00001800U 544 545 /* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */ 546 #define RUN_MAX_SMALL_2POW 15 547 #define RUN_MAX_SMALL (1U << RUN_MAX_SMALL_2POW) 548 549 /* 550 * Hyper-threaded CPUs may need a special instruction inside spin loops in 551 * order to yield to another virtual CPU. If no such instruction is defined 552 * above, make CPU_SPINWAIT a no-op. 553 */ 554 #ifndef CPU_SPINWAIT 555 # define CPU_SPINWAIT 556 #endif 557 558 /* 559 * Adaptive spinning must eventually switch to blocking, in order to avoid the 560 * potential for priority inversion deadlock. Backing off past a certain point 561 * can actually waste time. 562 */ 563 #define SPIN_LIMIT_2POW 11 564 565 /* 566 * Conversion from spinning to blocking is expensive; we use (1U << 567 * BLOCK_COST_2POW) to estimate how many more times costly blocking is than 568 * worst-case spinning. 569 */ 570 #define BLOCK_COST_2POW 4 571 572 #ifdef MALLOC_BALANCE 573 /* 574 * We use an exponential moving average to track recent lock contention, 575 * where the size of the history window is N, and alpha=2/(N+1). 576 * 577 * Due to integer math rounding, very small values here can cause 578 * substantial degradation in accuracy, thus making the moving average decay 579 * faster than it would with precise calculation. 580 */ 581 # define BALANCE_ALPHA_INV_2POW 9 582 583 /* 584 * Threshold value for the exponential moving contention average at which to 585 * re-assign a thread. 586 */ 587 # define BALANCE_THRESHOLD_DEFAULT (1U << (SPIN_LIMIT_2POW-4)) 588 #endif 589 590 /******************************************************************************/ 591 592 /* 593 * Mutexes based on spinlocks. We can't use normal pthread spinlocks in all 594 * places, because they require malloc()ed memory, which causes bootstrapping 595 * issues in some cases. 596 */ 597 #if defined(MOZ_MEMORY_WINDOWS) 598 #define malloc_mutex_t CRITICAL_SECTION 599 #define malloc_spinlock_t CRITICAL_SECTION 600 #elif defined(MOZ_MEMORY_DARWIN) 601 typedef struct { 602 OSSpinLock lock; 603 } malloc_mutex_t; 604 typedef struct { 605 OSSpinLock lock; 606 } malloc_spinlock_t; 607 #elif defined(MOZ_MEMORY) 608 typedef pthread_mutex_t malloc_mutex_t; 609 typedef pthread_mutex_t malloc_spinlock_t; 610 #else 611 /* XXX these should #ifdef these for freebsd (and linux?) only */ 612 typedef struct { 613 spinlock_t lock; 614 } malloc_mutex_t; 615 typedef malloc_spinlock_t malloc_mutex_t; 616 #endif 617 618 /* Set to true once the allocator has been initialized. */ 619 static bool malloc_initialized = false; 620 621 #if defined(MOZ_MEMORY_WINDOWS) 622 /* No init lock for Windows. */ 623 #elif defined(MOZ_MEMORY_DARWIN) 624 static malloc_mutex_t init_lock = {OS_SPINLOCK_INIT}; 625 #elif defined(MOZ_MEMORY_LINUX) 626 static malloc_mutex_t init_lock = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP; 627 #elif defined(MOZ_MEMORY) 628 static malloc_mutex_t init_lock = PTHREAD_MUTEX_INITIALIZER; 629 #else 630 static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER}; 631 #endif 632 633 /******************************************************************************/ 634 /* 635 * Statistics data structures. 636 */ 637 638 #ifdef MALLOC_STATS 639 640 typedef struct malloc_bin_stats_s malloc_bin_stats_t; 641 struct malloc_bin_stats_s { 642 /* 643 * Number of allocation requests that corresponded to the size of this 644 * bin. 645 */ 646 uint64_t nrequests; 647 648 /* Total number of runs created for this bin's size class. */ 649 uint64_t nruns; 650 651 /* 652 * Total number of runs reused by extracting them from the runs tree for 653 * this bin's size class. 654 */ 655 uint64_t reruns; 656 657 /* High-water mark for this bin. */ 658 unsigned long highruns; 659 660 /* Current number of runs in this bin. */ 661 unsigned long curruns; 662 }; 663 664 typedef struct arena_stats_s arena_stats_t; 665 struct arena_stats_s { 666 /* Number of bytes currently mapped. */ 667 size_t mapped; 668 669 /* 670 * Total number of purge sweeps, total number of madvise calls made, 671 * and total pages purged in order to keep dirty unused memory under 672 * control. 673 */ 674 uint64_t npurge; 675 uint64_t nmadvise; 676 uint64_t purged; 677 #ifdef MALLOC_DECOMMIT 678 /* 679 * Total number of decommit/commit operations, and total number of 680 * pages decommitted. 681 */ 682 uint64_t ndecommit; 683 uint64_t ncommit; 684 uint64_t decommitted; 685 #endif 686 687 /* Per-size-category statistics. */ 688 size_t allocated_small; 689 uint64_t nmalloc_small; 690 uint64_t ndalloc_small; 691 692 size_t allocated_large; 693 uint64_t nmalloc_large; 694 uint64_t ndalloc_large; 695 696 #ifdef MALLOC_BALANCE 697 /* Number of times this arena reassigned a thread due to contention. */ 698 uint64_t nbalance; 699 #endif 700 }; 701 702 typedef struct chunk_stats_s chunk_stats_t; 703 struct chunk_stats_s { 704 /* Number of chunks that were allocated. */ 705 uint64_t nchunks; 706 707 /* High-water mark for number of chunks allocated. */ 708 unsigned long highchunks; 709 710 /* 711 * Current number of chunks allocated. This value isn't maintained for 712 * any other purpose, so keep track of it in order to be able to set 713 * highchunks. 714 */ 715 unsigned long curchunks; 716 }; 717 718 #endif /* #ifdef MALLOC_STATS */ 719 720 /******************************************************************************/ 721 /* 722 * Extent data structures. 723 */ 724 725 /* Tree of extents. */ 726 typedef struct extent_node_s extent_node_t; 727 struct extent_node_s { 728 /* Linkage for the size/address-ordered tree. */ 729 rb_node(extent_node_t) link_szad; 730 731 /* Linkage for the address-ordered tree. */ 732 rb_node(extent_node_t) link_ad; 733 734 /* Pointer to the extent that this tree node is responsible for. */ 735 void *addr; 736 737 /* Total region size. */ 738 size_t size; 739 }; 740 typedef rb_tree(extent_node_t) extent_tree_t; 741 742 /******************************************************************************/ 743 /* 744 * Radix tree data structures. 745 */ 746 747 #ifdef MALLOC_VALIDATE 748 /* 749 * Size of each radix tree node (must be a power of 2). This impacts tree 750 * depth. 751 */ 752 # if (SIZEOF_PTR == 4) 753 # define MALLOC_RTREE_NODESIZE (1U << 14) 754 # else 755 # define MALLOC_RTREE_NODESIZE CACHELINE 756 # endif 757 758 typedef struct malloc_rtree_s malloc_rtree_t; 759 struct malloc_rtree_s { 760 malloc_spinlock_t lock; 761 void **root; 762 unsigned height; 763 unsigned level2bits[1]; /* Dynamically sized. */ 764 }; 765 #endif 766 767 /******************************************************************************/ 768 /* 769 * Reserve data structures. 770 */ 771 772 /* Callback registration. */ 773 typedef struct reserve_reg_s reserve_reg_t; 774 struct reserve_reg_s { 775 /* Linkage for list of all registered callbacks. */ 776 ql_elm(reserve_reg_t) link; 777 778 /* Callback function pointer. */ 779 reserve_cb_t *cb; 780 781 /* Opaque application data pointer. */ 782 void *ctx; 783 784 /* 785 * Sequence number of condition notification most recently sent to this 786 * callback. 787 */ 788 uint64_t seq; 789 }; 790 791 /******************************************************************************/ 792 /* 793 * Arena data structures. 794 */ 795 796 typedef struct arena_s arena_t; 797 typedef struct arena_bin_s arena_bin_t; 798 799 /* Each element of the chunk map corresponds to one page within the chunk. */ 800 typedef struct arena_chunk_map_s arena_chunk_map_t; 801 struct arena_chunk_map_s { 802 /* 803 * Linkage for run trees. There are two disjoint uses: 804 * 805 * 1) arena_t's runs_avail tree. 806 * 2) arena_run_t conceptually uses this linkage for in-use non-full 807 * runs, rather than directly embedding linkage. 808 */ 809 rb_node(arena_chunk_map_t) link; 810 811 /* 812 * Run address (or size) and various flags are stored together. The bit 813 * layout looks like (assuming 32-bit system): 814 * 815 * ???????? ???????? ????---- --ckdzla 816 * 817 * ? : Unallocated: Run address for first/last pages, unset for internal 818 * pages. 819 * Small: Run address. 820 * Large: Run size for first page, unset for trailing pages. 821 * - : Unused. 822 * c : decommitted? 823 * k : key? 824 * d : dirty? 825 * z : zeroed? 826 * l : large? 827 * a : allocated? 828 * 829 * Following are example bit patterns for the three types of runs. 830 * 831 * r : run address 832 * s : run size 833 * x : don't care 834 * - : 0 835 * [cdzla] : bit set 836 * 837 * Unallocated: 838 * ssssssss ssssssss ssss---- --c----- 839 * xxxxxxxx xxxxxxxx xxxx---- ----d--- 840 * ssssssss ssssssss ssss---- -----z-- 841 * 842 * Small: 843 * rrrrrrrr rrrrrrrr rrrr---- -------a 844 * rrrrrrrr rrrrrrrr rrrr---- -------a 845 * rrrrrrrr rrrrrrrr rrrr---- -------a 846 * 847 * Large: 848 * ssssssss ssssssss ssss---- ------la 849 * -------- -------- -------- ------la 850 * -------- -------- -------- ------la 851 */ 852 size_t bits; 853 #ifdef MALLOC_DECOMMIT 854 #define CHUNK_MAP_DECOMMITTED ((size_t)0x20U) 855 #endif 856 #define CHUNK_MAP_KEY ((size_t)0x10U) 857 #define CHUNK_MAP_DIRTY ((size_t)0x08U) 858 #define CHUNK_MAP_ZEROED ((size_t)0x04U) 859 #define CHUNK_MAP_LARGE ((size_t)0x02U) 860 #define CHUNK_MAP_ALLOCATED ((size_t)0x01U) 861 }; 862 typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t; 863 typedef rb_tree(arena_chunk_map_t) arena_run_tree_t; 864 865 /* Arena chunk header. */ 866 typedef struct arena_chunk_s arena_chunk_t; 867 struct arena_chunk_s { 868 /* Arena that owns the chunk. */ 869 arena_t *arena; 870 871 /* Linkage for the arena's chunks_dirty tree. */ 872 rb_node(arena_chunk_t) link_dirty; 873 874 /* Number of dirty pages. */ 875 size_t ndirty; 876 877 /* Map of pages within chunk that keeps track of free/large/small. */ 878 arena_chunk_map_t map[1]; /* Dynamically sized. */ 879 }; 880 typedef rb_tree(arena_chunk_t) arena_chunk_tree_t; 881 882 typedef struct arena_run_s arena_run_t; 883 struct arena_run_s { 884 #ifdef MALLOC_DEBUG 885 uint32_t magic; 886 # define ARENA_RUN_MAGIC 0x384adf93 887 #endif 888 889 /* Bin this run is associated with. */ 890 arena_bin_t *bin; 891 892 /* Index of first element that might have a free region. */ 893 unsigned regs_minelm; 894 895 /* Number of free regions in run. */ 896 unsigned nfree; 897 898 /* Bitmask of in-use regions (0: in use, 1: free). */ 899 unsigned regs_mask[1]; /* Dynamically sized. */ 900 }; 901 902 struct arena_bin_s { 903 /* 904 * Current run being used to service allocations of this bin's size 905 * class. 906 */ 907 arena_run_t *runcur; 908 909 /* 910 * Tree of non-full runs. This tree is used when looking for an 911 * existing run when runcur is no longer usable. We choose the 912 * non-full run that is lowest in memory; this policy tends to keep 913 * objects packed well, and it can also help reduce the number of 914 * almost-empty chunks. 915 */ 916 arena_run_tree_t runs; 917 918 /* Size of regions in a run for this bin's size class. */ 919 size_t reg_size; 920 921 /* Total size of a run for this bin's size class. */ 922 size_t run_size; 923 924 /* Total number of regions in a run for this bin's size class. */ 925 uint32_t nregs; 926 927 /* Number of elements in a run's regs_mask for this bin's size class. */ 928 uint32_t regs_mask_nelms; 929 930 /* Offset of first region in a run for this bin's size class. */ 931 uint32_t reg0_offset; 932 933 #ifdef MALLOC_STATS 934 /* Bin statistics. */ 935 malloc_bin_stats_t stats; 936 #endif 937 }; 938 939 struct arena_s { 940 #ifdef MALLOC_DEBUG 941 uint32_t magic; 942 # define ARENA_MAGIC 0x947d3d24 943 #endif 944 945 /* All operations on this arena require that lock be locked. */ 946 #ifdef MOZ_MEMORY 947 malloc_spinlock_t lock; 948 #else 949 pthread_mutex_t lock; 950 #endif 951 952 #ifdef MALLOC_STATS 953 arena_stats_t stats; 954 #endif 955 956 /* 957 * Chunk allocation sequence number, used to detect races with other 958 * threads during chunk allocation, and then discard unnecessary chunks. 959 */ 960 uint64_t chunk_seq; 961 962 /* Tree of dirty-page-containing chunks this arena manages. */ 963 arena_chunk_tree_t chunks_dirty; 964 965 /* 966 * In order to avoid rapid chunk allocation/deallocation when an arena 967 * oscillates right on the cusp of needing a new chunk, cache the most 968 * recently freed chunk. The spare is left in the arena's chunk trees 969 * until it is deleted. 970 * 971 * There is one spare chunk per arena, rather than one spare total, in 972 * order to avoid interactions between multiple threads that could make 973 * a single spare inadequate. 974 */ 975 arena_chunk_t *spare; 976 977 /* 978 * Current count of pages within unused runs that are potentially 979 * dirty, and for which madvise(... MADV_FREE) has not been called. By 980 * tracking this, we can institute a limit on how much dirty unused 981 * memory is mapped for each arena. 982 */ 983 size_t ndirty; 984 985 /* 986 * Size/address-ordered tree of this arena's available runs. This tree 987 * is used for first-best-fit run allocation. 988 */ 989 arena_avail_tree_t runs_avail; 990 991 #ifdef MALLOC_BALANCE 992 /* 993 * The arena load balancing machinery needs to keep track of how much 994 * lock contention there is. This value is exponentially averaged. 995 */ 996 uint32_t contention; 997 #endif 998 999 /* 1000 * bins is used to store rings of free regions of the following sizes, 1001 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS. 1002 * 1003 * bins[i] | size | 1004 * --------+------+ 1005 * 0 | 2 | 1006 * 1 | 4 | 1007 * 2 | 8 | 1008 * --------+------+ 1009 * 3 | 16 | 1010 * 4 | 32 | 1011 * 5 | 48 | 1012 * 6 | 64 | 1013 * : : 1014 * : : 1015 * 33 | 496 | 1016 * 34 | 512 | 1017 * --------+------+ 1018 * 35 | 1024 | 1019 * 36 | 2048 | 1020 * --------+------+ 1021 */ 1022 arena_bin_t bins[1]; /* Dynamically sized. */ 1023 }; 1024 1025 /******************************************************************************/ 1026 /* 1027 * Data. 1028 */ 1029 1030 /* Number of CPUs. */ 1031 static unsigned ncpus; 1032 1033 /* VM page size. */ 1034 static size_t pagesize; 1035 static size_t pagesize_mask; 1036 static size_t pagesize_2pow; 1037 1038 /* Various bin-related settings. */ 1039 static size_t bin_maxclass; /* Max size class for bins. */ 1040 static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */ 1041 static unsigned nqbins; /* Number of quantum-spaced bins. */ 1042 static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */ 1043 static size_t small_min; 1044 static size_t small_max; 1045 1046 /* Various quantum-related settings. */ 1047 static size_t quantum; 1048 static size_t quantum_mask; /* (quantum - 1). */ 1049 1050 /* Various chunk-related settings. */ 1051 static size_t chunksize; 1052 static size_t chunksize_mask; /* (chunksize - 1). */ 1053 static size_t chunk_npages; 1054 static size_t arena_chunk_header_npages; 1055 static size_t arena_maxclass; /* Max size class for arenas. */ 1056 1057 /********/ 1058 /* 1059 * Chunks. 1060 */ 1061 1062 #ifdef MALLOC_VALIDATE 1063 static malloc_rtree_t *chunk_rtree; 1064 #endif 1065 1066 /* Protects chunk-related data structures. */ 1067 static malloc_mutex_t huge_mtx; 1068 1069 /* Tree of chunks that are stand-alone huge allocations. */ 1070 static extent_tree_t huge; 1071 1072 #ifdef MALLOC_STATS 1073 /* Huge allocation statistics. */ 1074 static uint64_t huge_nmalloc; 1075 static uint64_t huge_ndalloc; 1076 static size_t huge_allocated; 1077 #endif 1078 1079 /****************/ 1080 /* 1081 * Memory reserve. 1082 */ 1083 1084 #ifdef MALLOC_PAGEFILE 1085 static char pagefile_templ[PATH_MAX]; 1086 #endif 1087 1088 /* Protects reserve-related data structures. */ 1089 static malloc_mutex_t reserve_mtx; 1090 1091 /* 1092 * Bounds on acceptable reserve size, and current reserve size. Reserve 1093 * depletion may cause (reserve_cur < reserve_min). 1094 */ 1095 static size_t reserve_min; 1096 static size_t reserve_cur; 1097 static size_t reserve_max; 1098 1099 /* List of registered callbacks. */ 1100 static ql_head(reserve_reg_t) reserve_regs; 1101 1102 /* 1103 * Condition notification sequence number, used to determine whether all 1104 * registered callbacks have been notified of the most current condition. 1105 */ 1106 static uint64_t reserve_seq; 1107 1108 /* 1109 * Trees of chunks currently in the memory reserve. Depending on function, 1110 * different tree orderings are needed, which is why there are two trees with 1111 * the same contents. 1112 */ 1113 static extent_tree_t reserve_chunks_szad; 1114 static extent_tree_t reserve_chunks_ad; 1115 1116 /****************************/ 1117 /* 1118 * base (internal allocation). 1119 */ 1120 1121 /* 1122 * Current pages that are being used for internal memory allocations. These 1123 * pages are carved up in cacheline-size quanta, so that there is no chance of 1124 * false cache line sharing. 1125 */ 1126 static void *base_pages; 1127 static void *base_next_addr; 1128 #ifdef MALLOC_DECOMMIT 1129 static void *base_next_decommitted; 1130 #endif 1131 static void *base_past_addr; /* Addr immediately past base_pages. */ 1132 static extent_node_t *base_nodes; 1133 static reserve_reg_t *base_reserve_regs; 1134 static malloc_mutex_t base_mtx; 1135 #ifdef MALLOC_STATS 1136 static size_t base_mapped; 1137 #endif 1138 1139 /********/ 1140 /* 1141 * Arenas. 1142 */ 1143 1144 /* 1145 * Arenas that are used to service external requests. Not all elements of the 1146 * arenas array are necessarily used; arenas are created lazily as needed. 1147 */ 1148 static arena_t **arenas; 1149 static unsigned narenas; 1150 static unsigned narenas_2pow; 1151 #ifndef NO_TLS 1152 # ifdef MALLOC_BALANCE 1153 static unsigned narenas_2pow; 1154 # else 1155 static unsigned next_arena; 1156 # endif 1157 #endif 1158 #ifdef MOZ_MEMORY 1159 static malloc_spinlock_t arenas_lock; /* Protects arenas initialization. */ 1160 #else 1161 static pthread_mutex_t arenas_lock; /* Protects arenas initialization. */ 1162 #endif 1163 1164 #ifndef NO_TLS 1165 /* 1166 * Map of pthread_self() --> arenas[???], used for selecting an arena to use 1167 * for allocations. 1168 */ 1169 #ifndef MOZ_MEMORY_WINDOWS 1170 static __thread arena_t *arenas_map; 1171 #endif 1172 #endif 1173 1174 #ifdef MALLOC_STATS 1175 /* Chunk statistics. */ 1176 static chunk_stats_t stats_chunks; 1177 #endif 1178 1179 /*******************************/ 1180 /* 1181 * Runtime configuration options. 1182 */ 1183 const char *_malloc_options; 1184 1185 #ifndef MALLOC_PRODUCTION 1186 static bool opt_abort = true; 1187 #ifdef MALLOC_FILL 1188 static bool opt_junk = true; 1189 #endif 1190 #else 1191 static bool opt_abort = false; 1192 #ifdef MALLOC_FILL 1193 static bool opt_junk = false; 1194 #endif 1195 #endif 1196 static size_t opt_dirty_max = DIRTY_MAX_DEFAULT; 1197 #ifdef MALLOC_BALANCE 1198 static uint64_t opt_balance_threshold = BALANCE_THRESHOLD_DEFAULT; 1199 #endif 1200 static bool opt_print_stats = false; 1201 static size_t opt_quantum_2pow = QUANTUM_2POW_MIN; 1202 static size_t opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT; 1203 static size_t opt_chunk_2pow = CHUNK_2POW_DEFAULT; 1204 static int opt_reserve_min_lshift = 0; 1205 static int opt_reserve_range_lshift = 0; 1206 #ifdef MALLOC_PAGEFILE 1207 static bool opt_pagefile = false; 1208 #endif 1209 #ifdef MALLOC_UTRACE 1210 static bool opt_utrace = false; 1211 #endif 1212 #ifdef MALLOC_SYSV 1213 static bool opt_sysv = false; 1214 #endif 1215 #ifdef MALLOC_XMALLOC 1216 static bool opt_xmalloc = false; 1217 #endif 1218 #ifdef MALLOC_FILL 1219 static bool opt_zero = false; 1220 #endif 1221 static int opt_narenas_lshift = 0; 1222 1223 #ifdef MALLOC_UTRACE 1224 typedef struct { 1225 void *p; 1226 size_t s; 1227 void *r; 1228 } malloc_utrace_t; 1229 1230 #define UTRACE(a, b, c) \ 1231 if (opt_utrace) { \ 1232 malloc_utrace_t ut; \ 1233 ut.p = (a); \ 1234 ut.s = (b); \ 1235 ut.r = (c); \ 1236 utrace(&ut, sizeof(ut)); \ 1237 } 1238 #else 1239 #define UTRACE(a, b, c) 1240 #endif 1241 1242 /******************************************************************************/ 1243 /* 1244 * Begin function prototypes for non-inline static functions. 1245 */ 1246 1247 static char *umax2s(uintmax_t x, char *s); 1248 static bool malloc_mutex_init(malloc_mutex_t *mutex); 1249 static bool malloc_spin_init(malloc_spinlock_t *lock); 1250 static void wrtmessage(const char *p1, const char *p2, const char *p3, 1251 const char *p4); 1252 #ifdef MALLOC_STATS 1253 #ifdef MOZ_MEMORY_DARWIN 1254 /* Avoid namespace collision with OS X's malloc APIs. */ 1255 #define malloc_printf moz_malloc_printf 1256 #endif 1257 static void malloc_printf(const char *format, ...); 1258 #endif 1259 static bool base_pages_alloc_mmap(size_t minsize); 1260 static bool base_pages_alloc(size_t minsize); 1261 static void *base_alloc(size_t size); 1262 static void *base_calloc(size_t number, size_t size); 1263 static extent_node_t *base_node_alloc(void); 1264 static void base_node_dealloc(extent_node_t *node); 1265 static reserve_reg_t *base_reserve_reg_alloc(void); 1266 static void base_reserve_reg_dealloc(reserve_reg_t *reg); 1267 #ifdef MALLOC_STATS 1268 static void stats_print(arena_t *arena); 1269 #endif 1270 static void *pages_map(void *addr, size_t size, int pfd); 1271 static void pages_unmap(void *addr, size_t size); 1272 static void *chunk_alloc_mmap(size_t size, bool pagefile); 1273 #ifdef MALLOC_PAGEFILE 1274 static int pagefile_init(size_t size); 1275 static void pagefile_close(int pfd); 1276 #endif 1277 static void *chunk_recycle_reserve(size_t size, bool zero); 1278 static void *chunk_alloc(size_t size, bool zero, bool pagefile); 1279 static extent_node_t *chunk_dealloc_reserve(void *chunk, size_t size); 1280 static void chunk_dealloc_mmap(void *chunk, size_t size); 1281 static void chunk_dealloc(void *chunk, size_t size); 1282 #ifndef NO_TLS 1283 static arena_t *choose_arena_hard(void); 1284 #endif 1285 static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size, 1286 bool large, bool zero); 1287 static void arena_chunk_init(arena_t *arena, arena_chunk_t *chunk); 1288 static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk); 1289 static arena_run_t *arena_run_alloc(arena_t *arena, arena_bin_t *bin, 1290 size_t size, bool large, bool zero); 1291 static void arena_purge(arena_t *arena); 1292 static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty); 1293 static void arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, 1294 arena_run_t *run, size_t oldsize, size_t newsize); 1295 static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, 1296 arena_run_t *run, size_t oldsize, size_t newsize, bool dirty); 1297 static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin); 1298 static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin); 1299 static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size); 1300 #ifdef MALLOC_BALANCE 1301 static void arena_lock_balance_hard(arena_t *arena); 1302 #endif 1303 static void *arena_malloc_large(arena_t *arena, size_t size, bool zero); 1304 static void *arena_palloc(arena_t *arena, size_t alignment, size_t size, 1305 size_t alloc_size); 1306 static size_t arena_salloc(const void *ptr); 1307 static void arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, 1308 void *ptr); 1309 static void arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, 1310 void *ptr, size_t size, size_t oldsize); 1311 static bool arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, 1312 void *ptr, size_t size, size_t oldsize); 1313 static bool arena_ralloc_large(void *ptr, size_t size, size_t oldsize); 1314 static void *arena_ralloc(void *ptr, size_t size, size_t oldsize); 1315 static bool arena_new(arena_t *arena); 1316 static arena_t *arenas_extend(unsigned ind); 1317 static void *huge_malloc(size_t size, bool zero); 1318 static void *huge_palloc(size_t alignment, size_t size); 1319 static void *huge_ralloc(void *ptr, size_t size, size_t oldsize); 1320 static void huge_dalloc(void *ptr); 1321 static void malloc_print_stats(void); 1322 #ifndef MOZ_MEMORY_WINDOWS 1323 static 1324 #endif 1325 bool malloc_init_hard(void); 1326 static void reserve_shrink(void); 1327 static uint64_t reserve_notify(reserve_cnd_t cnd, size_t size, uint64_t seq); 1328 static uint64_t reserve_crit(size_t size, const char *fname, uint64_t seq); 1329 static void reserve_fail(size_t size, const char *fname); 1330 1331 void _malloc_prefork(void); 1332 void _malloc_postfork(void); 1333 1334 /* 1335 * End function prototypes. 1336 */ 1337 /******************************************************************************/ 1338 1339 /* 1340 * umax2s() provides minimal integer printing functionality, which is 1341 * especially useful for situations where allocation in vsnprintf() calls would 1342 * potentially cause deadlock. 1343 */ 1344 #define UMAX2S_BUFSIZE 21 1345 static char * 1346 umax2s(uintmax_t x, char *s) 1347 { 1348 unsigned i; 1349 1350 i = UMAX2S_BUFSIZE - 1; 1351 s[i] = '\0'; 1352 do { 1353 i--; 1354 s[i] = "0123456789"[x % 10]; 1355 x /= 10; 1356 } while (x > 0); 1357 1358 return (&s[i]); 1359 } 1360 1361 static void 1362 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4) 1363 { 1364 #ifdef MOZ_MEMORY_WINCE 1365 wchar_t buf[1024]; 1366 #define WRT_PRINT(s) \ 1367 MultiByteToWideChar(CP_ACP, 0, s, -1, buf, 1024); \ 1368 OutputDebugStringW(buf) 1369 1370 WRT_PRINT(p1); 1371 WRT_PRINT(p2); 1372 WRT_PRINT(p3); 1373 WRT_PRINT(p4); 1374 #else 1375 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_WINDOWS) 1376 #define _write write 1377 #endif 1378 _write(STDERR_FILENO, p1, (unsigned int) strlen(p1)); 1379 _write(STDERR_FILENO, p2, (unsigned int) strlen(p2)); 1380 _write(STDERR_FILENO, p3, (unsigned int) strlen(p3)); 1381 _write(STDERR_FILENO, p4, (unsigned int) strlen(p4)); 1382 #endif 1383 1384 } 1385 1386 #define _malloc_message malloc_message 1387 1388 void (*_malloc_message)(const char *p1, const char *p2, const char *p3, 1389 const char *p4) = wrtmessage; 1390 1391 #ifdef MALLOC_DEBUG 1392 # define assert(e) do { \ 1393 if (!(e)) { \ 1394 char line_buf[UMAX2S_BUFSIZE]; \ 1395 _malloc_message(__FILE__, ":", umax2s(__LINE__, \ 1396 line_buf), ": Failed assertion: "); \ 1397 _malloc_message("\"", #e, "\"\n", ""); \ 1398 abort(); \ 1399 } \ 1400 } while (0) 1401 #else 1402 #define assert(e) 1403 #endif 1404 1405 /******************************************************************************/ 1406 /* 1407 * Begin mutex. We can't use normal pthread mutexes in all places, because 1408 * they require malloc()ed memory, which causes bootstrapping issues in some 1409 * cases. 1410 */ 1411 1412 static bool 1413 malloc_mutex_init(malloc_mutex_t *mutex) 1414 { 1415 #if defined(MOZ_MEMORY_WINCE) 1416 InitializeCriticalSection(mutex); 1417 #elif defined(MOZ_MEMORY_WINDOWS) 1418 if (__isthreaded) 1419 if (! __crtInitCritSecAndSpinCount(mutex, _CRT_SPINCOUNT)) 1420 return (true); 1421 #elif defined(MOZ_MEMORY_DARWIN) 1422 mutex->lock = OS_SPINLOCK_INIT; 1423 #elif defined(MOZ_MEMORY_LINUX) 1424 pthread_mutexattr_t attr; 1425 if (pthread_mutexattr_init(&attr) != 0) 1426 return (true); 1427 pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ADAPTIVE_NP); 1428 if (pthread_mutex_init(mutex, &attr) != 0) { 1429 pthread_mutexattr_destroy(&attr); 1430 return (true); 1431 } 1432 pthread_mutexattr_destroy(&attr); 1433 #elif defined(MOZ_MEMORY) 1434 if (pthread_mutex_init(mutex, NULL) != 0) 1435 return (true); 1436 #else 1437 static const spinlock_t lock = _SPINLOCK_INITIALIZER; 1438 1439 mutex->lock = lock; 1440 #endif 1441 return (false); 1442 } 1443 1444 static inline void 1445 malloc_mutex_lock(malloc_mutex_t *mutex) 1446 { 1447 1448 #if defined(MOZ_MEMORY_WINDOWS) 1449 EnterCriticalSection(mutex); 1450 #elif defined(MOZ_MEMORY_DARWIN) 1451 OSSpinLockLock(&mutex->lock); 1452 #elif defined(MOZ_MEMORY) 1453 pthread_mutex_lock(mutex); 1454 #else 1455 if (__isthreaded) 1456 _SPINLOCK(&mutex->lock); 1457 #endif 1458 } 1459 1460 static inline void 1461 malloc_mutex_unlock(malloc_mutex_t *mutex) 1462 { 1463 1464 #if defined(MOZ_MEMORY_WINDOWS) 1465 LeaveCriticalSection(mutex); 1466 #elif defined(MOZ_MEMORY_DARWIN) 1467 OSSpinLockUnlock(&mutex->lock); 1468 #elif defined(MOZ_MEMORY) 1469 pthread_mutex_unlock(mutex); 1470 #else 1471 if (__isthreaded) 1472 _SPINUNLOCK(&mutex->lock); 1473 #endif 1474 } 1475 1476 static bool 1477 malloc_spin_init(malloc_spinlock_t *lock) 1478 { 1479 #if defined(MOZ_MEMORY_WINCE) 1480 InitializeCriticalSection(lock); 1481 #elif defined(MOZ_MEMORY_WINDOWS) 1482 if (__isthreaded) 1483 if (! __crtInitCritSecAndSpinCount(lock, _CRT_SPINCOUNT)) 1484 return (true); 1485 #elif defined(MOZ_MEMORY_DARWIN) 1486 lock->lock = OS_SPINLOCK_INIT; 1487 #elif defined(MOZ_MEMORY_LINUX) 1488 pthread_mutexattr_t attr; 1489 if (pthread_mutexattr_init(&attr) != 0) 1490 return (true); 1491 pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ADAPTIVE_NP); 1492 if (pthread_mutex_init(lock, &attr) != 0) { 1493 pthread_mutexattr_destroy(&attr); 1494 return (true); 1495 } 1496 pthread_mutexattr_destroy(&attr); 1497 #elif defined(MOZ_MEMORY) 1498 if (pthread_mutex_init(lock, NULL) != 0) 1499 return (true); 1500 #else 1501 lock->lock = _SPINLOCK_INITIALIZER; 1502 #endif 1503 return (false); 1504 } 1505 1506 static inline void 1507 malloc_spin_lock(malloc_spinlock_t *lock) 1508 { 1509 1510 #if defined(MOZ_MEMORY_WINDOWS) 1511 EnterCriticalSection(lock); 1512 #elif defined(MOZ_MEMORY_DARWIN) 1513 OSSpinLockLock(&lock->lock); 1514 #elif defined(MOZ_MEMORY) 1515 pthread_mutex_lock(lock); 1516 #else 1517 if (__isthreaded) 1518 _SPINLOCK(&lock->lock); 1519 #endif 1520 } 1521 1522 static inline void 1523 malloc_spin_unlock(malloc_spinlock_t *lock) 1524 { 1525 #if defined(MOZ_MEMORY_WINDOWS) 1526 LeaveCriticalSection(lock); 1527 #elif defined(MOZ_MEMORY_DARWIN) 1528 OSSpinLockUnlock(&lock->lock); 1529 #elif defined(MOZ_MEMORY) 1530 pthread_mutex_unlock(lock); 1531 #else 1532 if (__isthreaded) 1533 _SPINUNLOCK(&lock->lock); 1534 #endif 1535 } 1536 1537 /* 1538 * End mutex. 1539 */ 1540 /******************************************************************************/ 1541 /* 1542 * Begin spin lock. Spin locks here are actually adaptive mutexes that block 1543 * after a period of spinning, because unbounded spinning would allow for 1544 * priority inversion. 1545 */ 1546 1547 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_DARWIN) 1548 # define malloc_spin_init malloc_mutex_init 1549 # define malloc_spin_lock malloc_mutex_lock 1550 # define malloc_spin_unlock malloc_mutex_unlock 1551 #endif 1552 1553 #ifndef MOZ_MEMORY 1554 /* 1555 * We use an unpublished interface to initialize pthread mutexes with an 1556 * allocation callback, in order to avoid infinite recursion. 1557 */ 1558 int _pthread_mutex_init_calloc_cb(pthread_mutex_t *mutex, 1559 void *(calloc_cb)(size_t, size_t)); 1560 1561 __weak_reference(_pthread_mutex_init_calloc_cb_stub, 1562 _pthread_mutex_init_calloc_cb); 1563 1564 int 1565 _pthread_mutex_init_calloc_cb_stub(pthread_mutex_t *mutex, 1566 void *(calloc_cb)(size_t, size_t)) 1567 { 1568 1569 return (0); 1570 } 1571 1572 static bool 1573 malloc_spin_init(pthread_mutex_t *lock) 1574 { 1575 1576 if (_pthread_mutex_init_calloc_cb(lock, base_calloc) != 0) 1577 return (true); 1578 1579 return (false); 1580 } 1581 1582 static inline unsigned 1583 malloc_spin_lock(pthread_mutex_t *lock) 1584 { 1585 unsigned ret = 0; 1586 1587 if (__isthreaded) { 1588 if (_pthread_mutex_trylock(lock) != 0) { 1589 unsigned i; 1590 volatile unsigned j; 1591 1592 /* Exponentially back off. */ 1593 for (i = 1; i <= SPIN_LIMIT_2POW; i++) { 1594 for (j = 0; j < (1U << i); j++) 1595 ret++; 1596 1597 CPU_SPINWAIT; 1598 if (_pthread_mutex_trylock(lock) == 0) 1599 return (ret); 1600 } 1601 1602 /* 1603 * Spinning failed. Block until the lock becomes 1604 * available, in order to avoid indefinite priority 1605 * inversion. 1606 */ 1607 _pthread_mutex_lock(lock); 1608 assert((ret << BLOCK_COST_2POW) != 0); 1609 return (ret << BLOCK_COST_2POW); 1610 } 1611 } 1612 1613 return (ret); 1614 } 1615 1616 static inline void 1617 malloc_spin_unlock(pthread_mutex_t *lock) 1618 { 1619 1620 if (__isthreaded) 1621 _pthread_mutex_unlock(lock); 1622 } 1623 #endif 1624 1625 /* 1626 * End spin lock. 1627 */ 1628 /******************************************************************************/ 1629 /* 1630 * Begin Utility functions/macros. 1631 */ 1632 1633 /* Return the chunk address for allocation address a. */ 1634 #define CHUNK_ADDR2BASE(a) \ 1635 ((void *)((uintptr_t)(a) & ~chunksize_mask)) 1636 1637 /* Return the chunk offset of address a. */ 1638 #define CHUNK_ADDR2OFFSET(a) \ 1639 ((size_t)((uintptr_t)(a) & chunksize_mask)) 1640 1641 /* Return the smallest chunk multiple that is >= s. */ 1642 #define CHUNK_CEILING(s) \ 1643 (((s) + chunksize_mask) & ~chunksize_mask) 1644 1645 /* Return the smallest cacheline multiple that is >= s. */ 1646 #define CACHELINE_CEILING(s) \ 1647 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1)) 1648 1649 /* Return the smallest quantum multiple that is >= a. */ 1650 #define QUANTUM_CEILING(a) \ 1651 (((a) + quantum_mask) & ~quantum_mask) 1652 1653 /* Return the smallest pagesize multiple that is >= s. */ 1654 #define PAGE_CEILING(s) \ 1655 (((s) + pagesize_mask) & ~pagesize_mask) 1656 1657 /* Compute the smallest power of 2 that is >= x. */ 1658 static inline size_t 1659 pow2_ceil(size_t x) 1660 { 1661 1662 x--; 1663 x |= x >> 1; 1664 x |= x >> 2; 1665 x |= x >> 4; 1666 x |= x >> 8; 1667 x |= x >> 16; 1668 #if (SIZEOF_PTR == 8) 1669 x |= x >> 32; 1670 #endif 1671 x++; 1672 return (x); 1673 } 1674 1675 #ifdef MALLOC_BALANCE 1676 /* 1677 * Use a simple linear congruential pseudo-random number generator: 1678 * 1679 * prn(y) = (a*x + c) % m 1680 * 1681 * where the following constants ensure maximal period: 1682 * 1683 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4. 1684 * c == Odd number (relatively prime to 2^n). 1685 * m == 2^32 1686 * 1687 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints. 1688 * 1689 * This choice of m has the disadvantage that the quality of the bits is 1690 * proportional to bit position. For example. the lowest bit has a cycle of 2, 1691 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper 1692 * bits. 1693 */ 1694 # define PRN_DEFINE(suffix, var, a, c) \ 1695 static inline void \ 1696 sprn_##suffix(uint32_t seed) \ 1697 { \ 1698 var = seed; \ 1699 } \ 1700 \ 1701 static inline uint32_t \ 1702 prn_##suffix(uint32_t lg_range) \ 1703 { \ 1704 uint32_t ret, x; \ 1705 \ 1706 assert(lg_range > 0); \ 1707 assert(lg_range <= 32); \ 1708 \ 1709 x = (var * (a)) + (c); \ 1710 var = x; \ 1711 ret = x >> (32 - lg_range); \ 1712 \ 1713 return (ret); \ 1714 } 1715 # define SPRN(suffix, seed) sprn_##suffix(seed) 1716 # define PRN(suffix, lg_range) prn_##suffix(lg_range) 1717 #endif 1718 1719 #ifdef MALLOC_BALANCE 1720 /* Define the PRNG used for arena assignment. */ 1721 static __thread uint32_t balance_x; 1722 PRN_DEFINE(balance, balance_x, 1297, 1301) 1723 #endif 1724 1725 #ifdef MALLOC_UTRACE 1726 static int 1727 utrace(const void *addr, size_t len) 1728 { 1729 malloc_utrace_t *ut = (malloc_utrace_t *)addr; 1730 1731 assert(len == sizeof(malloc_utrace_t)); 1732 1733 if (ut->p == NULL && ut->s == 0 && ut->r == NULL) 1734 malloc_printf("%d x USER malloc_init()\n", getpid()); 1735 else if (ut->p == NULL && ut->r != NULL) { 1736 malloc_printf("%d x USER %p = malloc(%zu)\n", getpid(), ut->r, 1737 ut->s); 1738 } else if (ut->p != NULL && ut->r != NULL) { 1739 malloc_printf("%d x USER %p = realloc(%p, %zu)\n", getpid(), 1740 ut->r, ut->p, ut->s); 1741 } else 1742 malloc_printf("%d x USER free(%p)\n", getpid(), ut->p); 1743 1744 return (0); 1745 } 1746 #endif 1747 1748 static inline const char * 1749 _getprogname(void) 1750 { 1751 1752 return ("<jemalloc>"); 1753 } 1754 1755 #ifdef MALLOC_STATS 1756 /* 1757 * Print to stderr in such a way as to (hopefully) avoid memory allocation. 1758 */ 1759 static void 1760 malloc_printf(const char *format, ...) 1761 { 1762 #ifndef WINCE 1763 char buf[4096]; 1764 va_list ap; 1765 1766 va_start(ap, format); 1767 vsnprintf(buf, sizeof(buf), format, ap); 1768 va_end(ap); 1769 _malloc_message(buf, "", "", ""); 1770 #endif 1771 } 1772 #endif 1773 1774 /******************************************************************************/ 1775 1776 #ifdef MALLOC_DECOMMIT 1777 static inline void 1778 pages_decommit(void *addr, size_t size) 1779 { 1780 1781 #ifdef MOZ_MEMORY_WINDOWS 1782 VirtualFree(addr, size, MEM_DECOMMIT); 1783 #else 1784 if (mmap(addr, size, PROT_NONE, MAP_FIXED | MAP_PRIVATE | MAP_ANON, -1, 1785 0) == MAP_FAILED) 1786 abort(); 1787 #endif 1788 } 1789 1790 static inline void 1791 pages_commit(void *addr, size_t size) 1792 { 1793 1794 # ifdef MOZ_MEMORY_WINDOWS 1795 VirtualAlloc(addr, size, MEM_COMMIT, PAGE_READWRITE); 1796 # else 1797 if (mmap(addr, size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_PRIVATE | 1798 MAP_ANON, -1, 0) == MAP_FAILED) 1799 abort(); 1800 # endif 1801 } 1802 #endif 1803 1804 static bool 1805 base_pages_alloc_mmap(size_t minsize) 1806 { 1807 bool ret; 1808 size_t csize; 1809 #ifdef MALLOC_DECOMMIT 1810 size_t pminsize; 1811 #endif 1812 int pfd; 1813 1814 assert(minsize != 0); 1815 csize = CHUNK_CEILING(minsize); 1816 #ifdef MALLOC_PAGEFILE 1817 if (opt_pagefile) { 1818 pfd = pagefile_init(csize); 1819 if (pfd == -1) 1820 return (true); 1821 } else 1822 #endif 1823 pfd = -1; 1824 base_pages = pages_map(NULL, csize, pfd); 1825 if (base_pages == NULL) { 1826 ret = true; 1827 goto RETURN; 1828 } 1829 base_next_addr = base_pages; 1830 base_past_addr = (void *)((uintptr_t)base_pages + csize); 1831 #ifdef MALLOC_DECOMMIT 1832 /* 1833 * Leave enough pages for minsize committed, since otherwise they would 1834 * have to be immediately recommitted. 1835 */ 1836 pminsize = PAGE_CEILING(minsize); 1837 base_next_decommitted = (void *)((uintptr_t)base_pages + pminsize); 1838 if (pminsize < csize) 1839 pages_decommit(base_next_decommitted, csize - pminsize); 1840 #endif 1841 #ifdef MALLOC_STATS 1842 base_mapped += csize; 1843 #endif 1844 1845 ret = false; 1846 RETURN: 1847 #ifdef MALLOC_PAGEFILE 1848 if (pfd != -1) 1849 pagefile_close(pfd); 1850 #endif 1851 return (false); 1852 } 1853 1854 static bool 1855 base_pages_alloc(size_t minsize) 1856 { 1857 1858 if (base_pages_alloc_mmap(minsize) == false) 1859 return (false); 1860 1861 return (true); 1862 } 1863 1864 static void * 1865 base_alloc(size_t size) 1866 { 1867 void *ret; 1868 size_t csize; 1869 1870 /* Round size up to nearest multiple of the cacheline size. */ 1871 csize = CACHELINE_CEILING(size); 1872 1873 malloc_mutex_lock(&base_mtx); 1874 /* Make sure there's enough space for the allocation. */ 1875 if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) { 1876 if (base_pages_alloc(csize)) { 1877 malloc_mutex_unlock(&base_mtx); 1878 return (NULL); 1879 } 1880 } 1881 /* Allocate. */ 1882 ret = base_next_addr; 1883 base_next_addr = (void *)((uintptr_t)base_next_addr + csize); 1884 #ifdef MALLOC_DECOMMIT 1885 /* Make sure enough pages are committed for the new allocation. */ 1886 if ((uintptr_t)base_next_addr > (uintptr_t)base_next_decommitted) { 1887 void *pbase_next_addr = 1888 (void *)(PAGE_CEILING((uintptr_t)base_next_addr)); 1889 1890 pages_commit(base_next_decommitted, (uintptr_t)pbase_next_addr - 1891 (uintptr_t)base_next_decommitted); 1892 base_next_decommitted = pbase_next_addr; 1893 } 1894 #endif 1895 malloc_mutex_unlock(&base_mtx); 1896 VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, false); 1897 1898 return (ret); 1899 } 1900 1901 static void * 1902 base_calloc(size_t number, size_t size) 1903 { 1904 void *ret; 1905 1906 ret = base_alloc(number * size); 1907 #ifdef MALLOC_VALGRIND 1908 if (ret != NULL) { 1909 VALGRIND_FREELIKE_BLOCK(ret, 0); 1910 VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, true); 1911 } 1912 #endif 1913 memset(ret, 0, number * size); 1914 1915 return (ret); 1916 } 1917 1918 static extent_node_t * 1919 base_node_alloc(void) 1920 { 1921 extent_node_t *ret; 1922 1923 malloc_mutex_lock(&base_mtx); 1924 if (base_nodes != NULL) { 1925 ret = base_nodes; 1926 base_nodes = *(extent_node_t **)ret; 1927 VALGRIND_FREELIKE_BLOCK(ret, 0); 1928 VALGRIND_MALLOCLIKE_BLOCK(ret, sizeof(extent_node_t), 0, false); 1929 malloc_mutex_unlock(&base_mtx); 1930 } else { 1931 malloc_mutex_unlock(&base_mtx); 1932 ret = (extent_node_t *)base_alloc(sizeof(extent_node_t)); 1933 } 1934 1935 return (ret); 1936 } 1937 1938 static void 1939 base_node_dealloc(extent_node_t *node) 1940 { 1941 1942 malloc_mutex_lock(&base_mtx); 1943 VALGRIND_FREELIKE_BLOCK(node, 0); 1944 VALGRIND_MALLOCLIKE_BLOCK(node, sizeof(extent_node_t *), 0, false); 1945 *(extent_node_t **)node = base_nodes; 1946 base_nodes = node; 1947 malloc_mutex_unlock(&base_mtx); 1948 } 1949 1950 static reserve_reg_t * 1951 base_reserve_reg_alloc(void) 1952 { 1953 reserve_reg_t *ret; 1954 1955 malloc_mutex_lock(&base_mtx); 1956 if (base_reserve_regs != NULL) { 1957 ret = base_reserve_regs; 1958 base_reserve_regs = *(reserve_reg_t **)ret; 1959 VALGRIND_FREELIKE_BLOCK(ret, 0); 1960 VALGRIND_MALLOCLIKE_BLOCK(ret, sizeof(reserve_reg_t), 0, false); 1961 malloc_mutex_unlock(&base_mtx); 1962 } else { 1963 malloc_mutex_unlock(&base_mtx); 1964 ret = (reserve_reg_t *)base_alloc(sizeof(reserve_reg_t)); 1965 } 1966 1967 return (ret); 1968 } 1969 1970 static void 1971 base_reserve_reg_dealloc(reserve_reg_t *reg) 1972 { 1973 1974 malloc_mutex_lock(&base_mtx); 1975 VALGRIND_FREELIKE_BLOCK(reg, 0); 1976 VALGRIND_MALLOCLIKE_BLOCK(reg, sizeof(reserve_reg_t *), 0, false); 1977 *(reserve_reg_t **)reg = base_reserve_regs; 1978 base_reserve_regs = reg; 1979 malloc_mutex_unlock(&base_mtx); 1980 } 1981 1982 /******************************************************************************/ 1983 1984 #ifdef MALLOC_STATS 1985 static void 1986 stats_print(arena_t *arena) 1987 { 1988 unsigned i, gap_start; 1989 1990 #ifdef MOZ_MEMORY_WINDOWS 1991 malloc_printf("dirty: %Iu page%s dirty, %I64u sweep%s," 1992 " %I64u madvise%s, %I64u page%s purged\n", 1993 arena->ndirty, arena->ndirty == 1 ? "" : "s", 1994 arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s", 1995 arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s", 1996 arena->stats.purged, arena->stats.purged == 1 ? "" : "s"); 1997 # ifdef MALLOC_DECOMMIT 1998 malloc_printf("decommit: %I64u decommit%s, %I64u commit%s," 1999 " %I64u page%s decommitted\n", 2000 arena->stats.ndecommit, (arena->stats.ndecommit == 1) ? "" : "s", 2001 arena->stats.ncommit, (arena->stats.ncommit == 1) ? "" : "s", 2002 arena->stats.decommitted, 2003 (arena->stats.decommitted == 1) ? "" : "s"); 2004 # endif 2005 2006 malloc_printf(" allocated nmalloc ndalloc\n"); 2007 malloc_printf("small: %12Iu %12I64u %12I64u\n", 2008 arena->stats.allocated_small, arena->stats.nmalloc_small, 2009 arena->stats.ndalloc_small); 2010 malloc_printf("large: %12Iu %12I64u %12I64u\n", 2011 arena->stats.allocated_large, arena->stats.nmalloc_large, 2012 arena->stats.ndalloc_large); 2013 malloc_printf("total: %12Iu %12I64u %12I64u\n", 2014 arena->stats.allocated_small + arena->stats.allocated_large, 2015 arena->stats.nmalloc_small + arena->stats.nmalloc_large, 2016 arena->stats.ndalloc_small + arena->stats.ndalloc_large); 2017 malloc_printf("mapped: %12Iu\n", arena->stats.mapped); 2018 #else 2019 malloc_printf("dirty: %zu page%s dirty, %llu sweep%s," 2020 " %llu madvise%s, %llu page%s purged\n", 2021 arena->ndirty, arena->ndirty == 1 ? "" : "s", 2022 arena->stats.npurge, arena->stats.npurge == 1 ? "" : "s", 2023 arena->stats.nmadvise, arena->stats.nmadvise == 1 ? "" : "s", 2024 arena->stats.purged, arena->stats.purged == 1 ? "" : "s"); 2025 # ifdef MALLOC_DECOMMIT 2026 malloc_printf("decommit: %llu decommit%s, %llu commit%s," 2027 " %llu page%s decommitted\n", 2028 arena->stats.ndecommit, (arena->stats.ndecommit == 1) ? "" : "s", 2029 arena->stats.ncommit, (arena->stats.ncommit == 1) ? "" : "s", 2030 arena->stats.decommitted, 2031 (arena->stats.decommitted == 1) ? "" : "s"); 2032 # endif 2033 2034 malloc_printf(" allocated nmalloc ndalloc\n"); 2035 malloc_printf("small: %12zu %12llu %12llu\n", 2036 arena->stats.allocated_small, arena->stats.nmalloc_small, 2037 arena->stats.ndalloc_small); 2038 malloc_printf("large: %12zu %12llu %12llu\n", 2039 arena->stats.allocated_large, arena->stats.nmalloc_large, 2040 arena->stats.ndalloc_large); 2041 malloc_printf("total: %12zu %12llu %12llu\n", 2042 arena->stats.allocated_small + arena->stats.allocated_large, 2043 arena->stats.nmalloc_small + arena->stats.nmalloc_large, 2044 arena->stats.ndalloc_small + arena->stats.ndalloc_large); 2045 malloc_printf("mapped: %12zu\n", arena->stats.mapped); 2046 #endif 2047 malloc_printf("bins: bin size regs pgs requests newruns" 2048 " reruns maxruns curruns\n"); 2049 for (i = 0, gap_start = UINT_MAX; i < ntbins + nqbins + nsbins; i++) { 2050 if (arena->bins[i].stats.nrequests == 0) { 2051 if (gap_start == UINT_MAX) 2052 gap_start = i; 2053 } else { 2054 if (gap_start != UINT_MAX) { 2055 if (i > gap_start + 1) { 2056 /* Gap of more than one size class. */ 2057 malloc_printf("[%u..%u]\n", 2058 gap_start, i - 1); 2059 } else { 2060 /* Gap of one size class. */ 2061 malloc_printf("[%u]\n", gap_start); 2062 } 2063 gap_start = UINT_MAX; 2064 } 2065 malloc_printf( 2066 #if defined(MOZ_MEMORY_WINDOWS) 2067 "%13u %1s %4u %4u %3u %9I64u %9I64u" 2068 " %9I64u %7u %7u\n", 2069 #else 2070 "%13u %1s %4u %4u %3u %9llu %9llu" 2071 " %9llu %7lu %7lu\n", 2072 #endif 2073 i, 2074 i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S", 2075 arena->bins[i].reg_size, 2076 arena->bins[i].nregs, 2077 arena->bins[i].run_size >> pagesize_2pow, 2078 arena->bins[i].stats.nrequests, 2079 arena->bins[i].stats.nruns, 2080 arena->bins[i].stats.reruns, 2081 arena->bins[i].stats.highruns, 2082 arena->bins[i].stats.curruns); 2083 } 2084 } 2085 if (gap_start != UINT_MAX) { 2086 if (i > gap_start + 1) { 2087 /* Gap of more than one size class. */ 2088 malloc_printf("[%u..%u]\n", gap_start, i - 1); 2089 } else { 2090 /* Gap of one size class. */ 2091 malloc_printf("[%u]\n", gap_start); 2092 } 2093 } 2094 } 2095 #endif 2096 2097 /* 2098 * End Utility functions/macros. 2099 */ 2100 /******************************************************************************/ 2101 /* 2102 * Begin extent tree code. 2103 */ 2104 2105 static inline int 2106 extent_szad_comp(extent_node_t *a, extent_node_t *b) 2107 { 2108 int ret; 2109 size_t a_size = a->size; 2110 size_t b_size = b->size; 2111 2112 ret = (a_size > b_size) - (a_size < b_size); 2113 if (ret == 0) { 2114 uintptr_t a_addr = (uintptr_t)a->addr; 2115 uintptr_t b_addr = (uintptr_t)b->addr; 2116 2117 ret = (a_addr > b_addr) - (a_addr < b_addr); 2118 } 2119 2120 return (ret); 2121 } 2122 2123 /* Wrap red-black tree macros in functions. */ 2124 rb_wrap(static, extent_tree_szad_, extent_tree_t, extent_node_t, 2125 link_szad, extent_szad_comp) 2126 2127 static inline int 2128 extent_ad_comp(extent_node_t *a, extent_node_t *b) 2129 { 2130 uintptr_t a_addr = (uintptr_t)a->addr; 2131 uintptr_t b_addr = (uintptr_t)b->addr; 2132 2133 return ((a_addr > b_addr) - (a_addr < b_addr)); 2134 } 2135 2136 /* Wrap red-black tree macros in functions. */ 2137 rb_wrap(static, extent_tree_ad_, extent_tree_t, extent_node_t, link_ad, 2138 extent_ad_comp) 2139 2140 /* 2141 * End extent tree code. 2142 */ 2143 /******************************************************************************/ 2144 /* 2145 * Begin chunk management functions. 2146 */ 2147 2148 #ifdef MOZ_MEMORY_WINDOWS 2149 #ifdef MOZ_MEMORY_WINCE 2150 #define ALIGN_ADDR2OFFSET(al, ad) \ 2151 ((uintptr_t)ad & (al - 1)) 2152 static void * 2153 pages_map_align(size_t size, int pfd, size_t alignment) 2154 { 2155 2156 void *ret; 2157 int offset; 2158 if (size % alignment) 2159 size += (alignment - (size % alignment)); 2160 assert(size >= alignment); 2161 ret = pages_map(NULL, size, pfd); 2162 offset = ALIGN_ADDR2OFFSET(alignment, ret); 2163 if (offset) { 2164 /* try to over allocate by the ammount we're offset */ 2165 void *tmp; 2166 pages_unmap(ret, size); 2167 tmp = VirtualAlloc(NULL, size + alignment - offset, 2168 MEM_RESERVE, PAGE_NOACCESS); 2169 if (offset == ALIGN_ADDR2OFFSET(alignment, tmp)) 2170 ret = VirtualAlloc((void*)((intptr_t)tmp + alignment 2171 - offset), size, MEM_COMMIT, 2172 PAGE_READWRITE); 2173 else 2174 VirtualFree(tmp, 0, MEM_RELEASE); 2175 offset = ALIGN_ADDR2OFFSET(alignment, ret); 2176 2177 2178 if (offset) { 2179 /* over allocate to ensure we have an aligned region */ 2180 ret = VirtualAlloc(NULL, size + alignment, MEM_RESERVE, 2181 PAGE_NOACCESS); 2182 offset = ALIGN_ADDR2OFFSET(alignment, ret); 2183 ret = VirtualAlloc((void*)((intptr_t)ret + 2184 alignment - offset), 2185 size, MEM_COMMIT, PAGE_READWRITE); 2186 } 2187 } 2188 return (ret); 2189 } 2190 #endif 2191 2192 static void * 2193 pages_map(void *addr, size_t size, int pfd) 2194 { 2195 void *ret = NULL; 2196 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6) 2197 void *va_ret; 2198 assert(addr == NULL); 2199 va_ret = VirtualAlloc(addr, size, MEM_RESERVE, PAGE_NOACCESS); 2200 if (va_ret) 2201 ret = VirtualAlloc(va_ret, size, MEM_COMMIT, PAGE_READWRITE); 2202 assert(va_ret == ret); 2203 #else 2204 ret = VirtualAlloc(addr, size, MEM_COMMIT | MEM_RESERVE, 2205 PAGE_READWRITE); 2206 #endif 2207 return (ret); 2208 } 2209 2210 static void 2211 pages_unmap(void *addr, size_t size) 2212 { 2213 if (VirtualFree(addr, 0, MEM_RELEASE) == 0) { 2214 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6) 2215 if (GetLastError() == ERROR_INVALID_PARAMETER) { 2216 MEMORY_BASIC_INFORMATION info; 2217 VirtualQuery(addr, &info, sizeof(info)); 2218 if (VirtualFree(info.AllocationBase, 0, MEM_RELEASE)) 2219 return; 2220 } 2221 #endif 2222 _malloc_message(_getprogname(), 2223 ": (malloc) Error in VirtualFree()\n", "", ""); 2224 if (opt_abort) 2225 abort(); 2226 } 2227 } 2228 #elif (defined(MOZ_MEMORY_DARWIN)) 2229 static void * 2230 pages_map(void *addr, size_t size, int pfd) 2231 { 2232 void *ret; 2233 kern_return_t err; 2234 int flags; 2235 2236 if (addr != NULL) { 2237 ret = addr; 2238 flags = 0; 2239 } else 2240 flags = VM_FLAGS_ANYWHERE; 2241 2242 err = vm_allocate((vm_map_t)mach_task_self(), (vm_address_t *)&ret, 2243 (vm_size_t)size, flags); 2244 if (err != KERN_SUCCESS) 2245 ret = NULL; 2246 2247 assert(ret == NULL || (addr == NULL && ret != addr) 2248 || (addr != NULL && ret == addr)); 2249 return (ret); 2250 } 2251 2252 static void 2253 pages_unmap(void *addr, size_t size) 2254 { 2255 kern_return_t err; 2256 2257 err = vm_deallocate((vm_map_t)mach_task_self(), (vm_address_t)addr, 2258 (vm_size_t)size); 2259 if (err != KERN_SUCCESS) { 2260 malloc_message(_getprogname(), 2261 ": (malloc) Error in vm_deallocate(): ", 2262 mach_error_string(err), "\n"); 2263 if (opt_abort) 2264 abort(); 2265 } 2266 } 2267 2268 #define VM_COPY_MIN (pagesize << 5) 2269 static inline void 2270 pages_copy(void *dest, const void *src, size_t n) 2271 { 2272 2273 assert((void *)((uintptr_t)dest & ~pagesize_mask) == dest); 2274 assert(n >= VM_COPY_MIN); 2275 assert((void *)((uintptr_t)src & ~pagesize_mask) == src); 2276 2277 vm_copy(mach_task_self(), (vm_address_t)src, (vm_size_t)n, 2278 (vm_address_t)dest); 2279 } 2280 #else /* MOZ_MEMORY_DARWIN */ 2281 #ifdef JEMALLOC_USES_MAP_ALIGN 2282 static void * 2283 pages_map_align(size_t size, int pfd, size_t alignment) 2284 { 2285 void *ret; 2286 2287 /* 2288 * We don't use MAP_FIXED here, because it can cause the *replacement* 2289 * of existing mappings, and we only want to create new mappings. 2290 */ 2291 #ifdef MALLOC_PAGEFILE 2292 if (pfd != -1) { 2293 ret = mmap((void *)alignment, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | 2294 MAP_NOSYNC | MAP_ALIGN, pfd, 0); 2295 } else 2296 #endif 2297 { 2298 ret = mmap((void *)alignment, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | 2299 MAP_NOSYNC | MAP_ALIGN | MAP_ANON, -1, 0); 2300 } 2301 assert(ret != NULL); 2302 2303 if (ret == MAP_FAILED) 2304 ret = NULL; 2305 return (ret); 2306 } 2307 #endif 2308 2309 static void * 2310 pages_map(void *addr, size_t size, int pfd) 2311 { 2312 void *ret; 2313 2314 /* 2315 * We don't use MAP_FIXED here, because it can cause the *replacement* 2316 * of existing mappings, and we only want to create new mappings. 2317 */ 2318 #ifdef MALLOC_PAGEFILE 2319 if (pfd != -1) { 2320 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | 2321 MAP_NOSYNC, pfd, 0); 2322 } else 2323 #endif 2324 { 2325 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | 2326 MAP_ANON, -1, 0); 2327 } 2328 assert(ret != NULL); 2329 2330 if (ret == MAP_FAILED) 2331 ret = NULL; 2332 else if (addr != NULL && ret != addr) { 2333 /* 2334 * We succeeded in mapping memory, but not in the right place. 2335 */ 2336 if (munmap(ret, size) == -1) { 2337 char buf[STRERROR_BUF]; 2338 2339 strerror_r(errno, buf, sizeof(buf)); 2340 _malloc_message(_getprogname(), 2341 ": (malloc) Error in munmap(): ", buf, "\n"); 2342 if (opt_abort) 2343 abort(); 2344 } 2345 ret = NULL; 2346 } 2347 2348 assert(ret == NULL || (addr == NULL && ret != addr) 2349 || (addr != NULL && ret == addr)); 2350 return (ret); 2351 } 2352 2353 static void 2354 pages_unmap(void *addr, size_t size) 2355 { 2356 2357 if (munmap(addr, size) == -1) { 2358 char buf[STRERROR_BUF]; 2359 2360 strerror_r(errno, buf, sizeof(buf)); 2361 _malloc_message(_getprogname(), 2362 ": (malloc) Error in munmap(): ", buf, "\n"); 2363 if (opt_abort) 2364 abort(); 2365 } 2366 } 2367 #endif 2368 2369 #ifdef MALLOC_VALIDATE 2370 static inline malloc_rtree_t * 2371 malloc_rtree_new(unsigned bits) 2372 { 2373 malloc_rtree_t *ret; 2374 unsigned bits_per_level, height, i; 2375 2376 bits_per_level = ffs(pow2_ceil((MALLOC_RTREE_NODESIZE / 2377 sizeof(void *)))) - 1; 2378 height = bits / bits_per_level; 2379 if (height * bits_per_level != bits) 2380 height++; 2381 assert(height * bits_per_level >= bits); 2382 2383 ret = (malloc_rtree_t*)base_calloc(1, sizeof(malloc_rtree_t) + (sizeof(unsigned) * 2384 (height - 1))); 2385 if (ret == NULL) 2386 return (NULL); 2387 2388 malloc_spin_init(&ret->lock); 2389 ret->height = height; 2390 if (bits_per_level * height > bits) 2391 ret->level2bits[0] = bits % bits_per_level; 2392 else 2393 ret->level2bits[0] = bits_per_level; 2394 for (i = 1; i < height; i++) 2395 ret->level2bits[i] = bits_per_level; 2396 2397 ret->root = (void**)base_calloc(1, sizeof(void *) << ret->level2bits[0]); 2398 if (ret->root == NULL) { 2399 /* 2400 * We leak the rtree here, since there's no generic base 2401 * deallocation. 2402 */ 2403 return (NULL); 2404 } 2405 2406 return (ret); 2407 } 2408 2409 /* The least significant bits of the key are ignored. */ 2410 static inline void * 2411 malloc_rtree_get(malloc_rtree_t *rtree, uintptr_t key) 2412 { 2413 void *ret; 2414 uintptr_t subkey; 2415 unsigned i, lshift, height, bits; 2416 void **node, **child; 2417 2418 malloc_spin_lock(&rtree->lock); 2419 for (i = lshift = 0, height = rtree->height, node = rtree->root; 2420 i < height - 1; 2421 i++, lshift += bits, node = child) { 2422 bits = rtree->level2bits[i]; 2423 subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits); 2424 child = (void**)node[subkey]; 2425 if (child == NULL) { 2426 malloc_spin_unlock(&rtree->lock); 2427 return (NULL); 2428 } 2429 } 2430 2431 /* node is a leaf, so it contains values rather than node pointers. */ 2432 bits = rtree->level2bits[i]; 2433 subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits); 2434 ret = node[subkey]; 2435 malloc_spin_unlock(&rtree->lock); 2436 2437 return (ret); 2438 } 2439 2440 static inline bool 2441 malloc_rtree_set(malloc_rtree_t *rtree, uintptr_t key, void *val) 2442 { 2443 uintptr_t subkey; 2444 unsigned i, lshift, height, bits; 2445 void **node, **child; 2446 2447 malloc_spin_lock(&rtree->lock); 2448 for (i = lshift = 0, height = rtree->height, node = rtree->root; 2449 i < height - 1; 2450 i++, lshift += bits, node = child) { 2451 bits = rtree->level2bits[i]; 2452 subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits); 2453 child = (void**)node[subkey]; 2454 if (child == NULL) { 2455 child = (void**)base_calloc(1, sizeof(void *) << 2456 rtree->level2bits[i+1]); 2457 if (child == NULL) { 2458 malloc_spin_unlock(&rtree->lock); 2459 return (true); 2460 } 2461 node[subkey] = child; 2462 } 2463 } 2464 2465 /* node is a leaf, so it contains values rather than node pointers. */ 2466 bits = rtree->level2bits[i]; 2467 subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits); 2468 node[subkey] = val; 2469 malloc_spin_unlock(&rtree->lock); 2470 2471 return (false); 2472 } 2473 #endif 2474 2475 static void * 2476 chunk_alloc_mmap(size_t size, bool pagefile) 2477 { 2478 void *ret; 2479 #ifndef JEMALLOC_USES_MAP_ALIGN 2480 size_t offset; 2481 #endif 2482 int pfd; 2483 2484 #ifdef MALLOC_PAGEFILE 2485 if (opt_pagefile && pagefile) { 2486 pfd = pagefile_init(size); 2487 if (pfd == -1) 2488 return (NULL); 2489 } else 2490 #endif 2491 pfd = -1; 2492 2493 /* 2494 * Windows requires that there be a 1:1 mapping between VM 2495 * allocation/deallocation operations. Therefore, take care here to 2496 * acquire the final result via one mapping operation. This means 2497 * unmapping any preliminary result that is not correctly aligned. 2498 * 2499 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm, 2500 * since it reduces the number of page files. 2501 */ 2502 2503 #ifdef JEMALLOC_USES_MAP_ALIGN 2504 ret = pages_map_align(size, pfd, chunksize); 2505 #else 2506 ret = pages_map(NULL, size, pfd); 2507 if (ret == NULL) 2508 goto RETURN; 2509 2510 offset = CHUNK_ADDR2OFFSET(ret); 2511 if (offset != 0) { 2512 /* Deallocate, then try to allocate at (ret + size - offset). */ 2513 pages_unmap(ret, size); 2514 ret = pages_map((void *)((uintptr_t)ret + size - offset), size, 2515 pfd); 2516 while (ret == NULL) { 2517 /* 2518 * Over-allocate in order to map a memory region that 2519 * is definitely large enough. 2520 */ 2521 ret = pages_map(NULL, size + chunksize, -1); 2522 if (ret == NULL) 2523 goto RETURN; 2524 /* 2525 * Deallocate, then allocate the correct size, within 2526 * the over-sized mapping. 2527 */ 2528 offset = CHUNK_ADDR2OFFSET(ret); 2529 pages_unmap(ret, size + chunksize); 2530 if (offset == 0) 2531 ret = pages_map(ret, size, pfd); 2532 else { 2533 ret = pages_map((void *)((uintptr_t)ret + 2534 chunksize - offset), size, pfd); 2535 } 2536 /* 2537 * Failure here indicates a race with another thread, so 2538 * try again. 2539 */ 2540 } 2541 } 2542 RETURN: 2543 #endif 2544 #ifdef MALLOC_PAGEFILE 2545 if (pfd != -1) 2546 pagefile_close(pfd); 2547 #endif 2548 #ifdef MALLOC_STATS 2549 if (ret != NULL) 2550 stats_chunks.nchunks += (size / chunksize); 2551 #endif 2552 return (ret); 2553 } 2554 2555 #ifdef MALLOC_PAGEFILE 2556 static int 2557 pagefile_init(size_t size) 2558 { 2559 int ret; 2560 size_t i; 2561 char pagefile_path[PATH_MAX]; 2562 char zbuf[MALLOC_PAGEFILE_WRITE_SIZE]; 2563 2564 /* 2565 * Create a temporary file, then immediately unlink it so that it will 2566 * not persist. 2567 */ 2568 strcpy(pagefile_path, pagefile_templ); 2569 ret = mkstemp(pagefile_path); 2570 if (ret == -1) 2571 return (ret); 2572 if (unlink(pagefile_path)) { 2573 char buf[STRERROR_BUF]; 2574 2575 strerror_r(errno, buf, sizeof(buf)); 2576 _malloc_message(_getprogname(), ": (malloc) Error in unlink(\"", 2577 pagefile_path, "\"):"); 2578 _malloc_message(buf, "\n", "", ""); 2579 if (opt_abort) 2580 abort(); 2581 } 2582 2583 /* 2584 * Write sequential zeroes to the file in order to assure that disk 2585 * space is committed, with minimal fragmentation. It would be 2586 * sufficient to write one zero per disk block, but that potentially 2587 * results in more system calls, for no real gain. 2588 */ 2589 memset(zbuf, 0, sizeof(zbuf)); 2590 for (i = 0; i < size; i += sizeof(zbuf)) { 2591 if (write(ret, zbuf, sizeof(zbuf)) != sizeof(zbuf)) { 2592 if (errno != ENOSPC) { 2593 char buf[STRERROR_BUF]; 2594 2595 strerror_r(errno, buf, sizeof(buf)); 2596 _malloc_message(_getprogname(), 2597 ": (malloc) Error in write(): ", buf, "\n"); 2598 if (opt_abort) 2599 abort(); 2600 } 2601 pagefile_close(ret); 2602 return (-1); 2603 } 2604 } 2605 2606 return (ret); 2607 } 2608 2609 static void 2610 pagefile_close(int pfd) 2611 { 2612 2613 if (close(pfd)) { 2614 char buf[STRERROR_BUF]; 2615 2616 strerror_r(errno, buf, sizeof(buf)); 2617 _malloc_message(_getprogname(), 2618 ": (malloc) Error in close(): ", buf, "\n"); 2619 if (opt_abort) 2620 abort(); 2621 } 2622 } 2623 #endif 2624 2625 static void * 2626 chunk_recycle_reserve(size_t size, bool zero) 2627 { 2628 extent_node_t *node, key; 2629 2630 #ifdef MALLOC_DECOMMIT 2631 if (size != chunksize) 2632 return (NULL); 2633 #endif 2634 2635 key.addr = NULL; 2636 key.size = size; 2637 malloc_mutex_lock(&reserve_mtx); 2638 node = extent_tree_szad_nsearch(&reserve_chunks_szad, &key); 2639 if (node != NULL) { 2640 void *ret = node->addr; 2641 2642 /* Remove node from the tree. */ 2643 extent_tree_szad_remove(&reserve_chunks_szad, node); 2644 #ifndef MALLOC_DECOMMIT 2645 if (node->size == size) { 2646 #else 2647 assert(node->size == size); 2648 #endif 2649 extent_tree_ad_remove(&reserve_chunks_ad, node); 2650 base_node_dealloc(node); 2651 #ifndef MALLOC_DECOMMIT 2652 } else { 2653 /* 2654 * Insert the remainder of node's address range as a 2655 * smaller chunk. Its position within reserve_chunks_ad 2656 * does not change. 2657 */ 2658 assert(node->size > size); 2659 node->addr = (void *)((uintptr_t)node->addr + size); 2660 node->size -= size; 2661 extent_tree_szad_insert(&reserve_chunks_szad, node); 2662 } 2663 #endif 2664 reserve_cur -= size; 2665 /* 2666 * Try to replenish the reserve if this allocation depleted it. 2667 */ 2668 #ifndef MALLOC_DECOMMIT 2669 if (reserve_cur < reserve_min) { 2670 size_t diff = reserve_min - reserve_cur; 2671 #else 2672 while (reserve_cur < reserve_min) { 2673 # define diff chunksize 2674 #endif 2675 void *chunk; 2676 2677 malloc_mutex_unlock(&reserve_mtx); 2678 chunk = chunk_alloc_mmap(diff, true); 2679 malloc_mutex_lock(&reserve_mtx); 2680 if (chunk == NULL) { 2681 uint64_t seq = 0; 2682 2683 do { 2684 seq = reserve_notify(RESERVE_CND_LOW, 2685 size, seq); 2686 if (seq == 0) 2687 goto MALLOC_OUT; 2688 } while (reserve_cur < reserve_min); 2689 } else { 2690 extent_node_t *node; 2691 2692 node = chunk_dealloc_reserve(chunk, diff); 2693 if (node == NULL) { 2694 uint64_t seq = 0; 2695 2696 pages_unmap(chunk, diff); 2697 do { 2698 seq = reserve_notify( 2699 RESERVE_CND_LOW, size, seq); 2700 if (seq == 0) 2701 goto MALLOC_OUT; 2702 } while (reserve_cur < reserve_min); 2703 } 2704 } 2705 } 2706 MALLOC_OUT: 2707 malloc_mutex_unlock(&reserve_mtx); 2708 2709 #ifdef MALLOC_DECOMMIT 2710 pages_commit(ret, size); 2711 # undef diff 2712 #else 2713 if (zero) 2714 memset(ret, 0, size); 2715 #endif 2716 return (ret); 2717 } 2718 malloc_mutex_unlock(&reserve_mtx); 2719 2720 return (NULL); 2721 } 2722 2723 static void * 2724 chunk_alloc(size_t size, bool zero, bool pagefile) 2725 { 2726 void *ret; 2727 2728 assert(size != 0); 2729 assert((size & chunksize_mask) == 0); 2730 2731 ret = chunk_recycle_reserve(size, zero); 2732 if (ret != NULL) 2733 goto RETURN; 2734 2735 ret = chunk_alloc_mmap(size, pagefile); 2736 if (ret != NULL) { 2737 goto RETURN; 2738 } 2739 2740 /* All strategies for allocation failed. */ 2741 ret = NULL; 2742 RETURN: 2743 #ifdef MALLOC_STATS 2744 if (ret != NULL) 2745 stats_chunks.curchunks += (size / chunksize); 2746 if (stats_chunks.curchunks > stats_chunks.highchunks) 2747 stats_chunks.highchunks = stats_chunks.curchunks; 2748 #endif 2749 2750 #ifdef MALLOC_VALIDATE 2751 if (ret != NULL) { 2752 if (malloc_rtree_set(chunk_rtree, (uintptr_t)ret, ret)) { 2753 chunk_dealloc(ret, size); 2754 return (NULL); 2755 } 2756 } 2757 #endif 2758 2759 assert(CHUNK_ADDR2BASE(ret) == ret); 2760 return (ret); 2761 } 2762 2763 static extent_node_t * 2764 chunk_dealloc_reserve(void *chunk, size_t size) 2765 { 2766 extent_node_t *node; 2767 2768 #ifdef MALLOC_DECOMMIT 2769 if (size != chunksize) 2770 return (NULL); 2771 #else 2772 extent_node_t *prev, key; 2773 2774 key.addr = (void *)((uintptr_t)chunk + size); 2775 node = extent_tree_ad_nsearch(&reserve_chunks_ad, &key); 2776 /* Try to coalesce forward. */ 2777 if (node != NULL && node->addr == key.addr) { 2778 /* 2779 * Coalesce chunk with the following address range. This does 2780 * not change the position within reserve_chunks_ad, so only 2781 * remove/insert from/into reserve_chunks_szad. 2782 */ 2783 extent_tree_szad_remove(&reserve_chunks_szad, node); 2784 node->addr = chunk; 2785 node->size += size; 2786 extent_tree_szad_insert(&reserve_chunks_szad, node); 2787 } else { 2788 #endif 2789 /* Coalescing forward failed, so insert a new node. */ 2790 node = base_node_alloc(); 2791 if (node == NULL) 2792 return (NULL); 2793 node->addr = chunk; 2794 node->size = size; 2795 extent_tree_ad_insert(&reserve_chunks_ad, node); 2796 extent_tree_szad_insert(&reserve_chunks_szad, node); 2797 #ifndef MALLOC_DECOMMIT 2798 } 2799 2800 /* Try to coalesce backward. */ 2801 prev = extent_tree_ad_prev(&reserve_chunks_ad, node); 2802 if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) == 2803 chunk) { 2804 /* 2805 * Coalesce chunk with the previous address range. This does 2806 * not change the position within reserve_chunks_ad, so only 2807 * remove/insert node from/into reserve_chunks_szad. 2808 */ 2809 extent_tree_szad_remove(&reserve_chunks_szad, prev); 2810 extent_tree_ad_remove(&reserve_chunks_ad, prev); 2811 2812 extent_tree_szad_remove(&reserve_chunks_szad, node); 2813 node->addr = prev->addr; 2814 node->size += prev->size; 2815 extent_tree_szad_insert(&reserve_chunks_szad, node); 2816 2817 base_node_dealloc(prev); 2818 } 2819 #endif 2820 2821 #ifdef MALLOC_DECOMMIT 2822 pages_decommit(chunk, size); 2823 #else 2824 madvise(chunk, size, MADV_FREE); 2825 #endif 2826 2827 reserve_cur += size; 2828 if (reserve_cur > reserve_max) 2829 reserve_shrink(); 2830 2831 return (node); 2832 } 2833 2834 static void 2835 chunk_dealloc_mmap(void *chunk, size_t size) 2836 { 2837 2838 pages_unmap(chunk, size); 2839 } 2840 2841 static void 2842 chunk_dealloc(void *chunk, size_t size) 2843 { 2844 extent_node_t *node; 2845 2846 assert(chunk != NULL); 2847 assert(CHUNK_ADDR2BASE(chunk) == chunk); 2848 assert(size != 0); 2849 assert((size & chunksize_mask) == 0); 2850 2851 #ifdef MALLOC_STATS 2852 stats_chunks.curchunks -= (size / chunksize); 2853 #endif 2854 #ifdef MALLOC_VALIDATE 2855 malloc_rtree_set(chunk_rtree, (uintptr_t)chunk, NULL); 2856 #endif 2857 2858 /* Try to merge chunk into the reserve. */ 2859 malloc_mutex_lock(&reserve_mtx); 2860 node = chunk_dealloc_reserve(chunk, size); 2861 malloc_mutex_unlock(&reserve_mtx); 2862 if (node == NULL) 2863 chunk_dealloc_mmap(chunk, size); 2864 } 2865 2866 /* 2867 * End chunk management functions. 2868 */ 2869 /******************************************************************************/ 2870 /* 2871 * Begin arena. 2872 */ 2873 2874 /* 2875 * Choose an arena based on a per-thread value (fast-path code, calls slow-path 2876 * code if necessary). 2877 */ 2878 static inline arena_t * 2879 choose_arena(void) 2880 { 2881 arena_t *ret; 2882 2883 /* 2884 * We can only use TLS if this is a PIC library, since for the static 2885 * library version, libc's malloc is used by TLS allocation, which 2886 * introduces a bootstrapping issue. 2887 */ 2888 #ifndef NO_TLS 2889 if (__isthreaded == false) { 2890 /* Avoid the overhead of TLS for single-threaded operation. */ 2891 return (arenas[0]); 2892 } 2893 2894 # ifdef MOZ_MEMORY_WINDOWS 2895 ret = (arena_t*)TlsGetValue(tlsIndex); 2896 # else 2897 ret = arenas_map; 2898 # endif 2899 2900 if (ret == NULL) { 2901 ret = choose_arena_hard(); 2902 assert(ret != NULL); 2903 } 2904 #else 2905 if (__isthreaded && narenas > 1) { 2906 unsigned long ind; 2907 2908 /* 2909 * Hash _pthread_self() to one of the arenas. There is a prime 2910 * number of arenas, so this has a reasonable chance of 2911 * working. Even so, the hashing can be easily thwarted by 2912 * inconvenient _pthread_self() values. Without specific 2913 * knowledge of how _pthread_self() calculates values, we can't 2914 * easily do much better than this. 2915 */ 2916 ind = (unsigned long) _pthread_self() % narenas; 2917 2918 /* 2919 * Optimistially assume that arenas[ind] has been initialized. 2920 * At worst, we find out that some other thread has already 2921 * done so, after acquiring the lock in preparation. Note that 2922 * this lazy locking also has the effect of lazily forcing 2923 * cache coherency; without the lock acquisition, there's no 2924 * guarantee that modification of arenas[ind] by another thread 2925 * would be seen on this CPU for an arbitrary amount of time. 2926 * 2927 * In general, this approach to modifying a synchronized value 2928 * isn't a good idea, but in this case we only ever modify the 2929 * value once, so things work out well. 2930 */ 2931 ret = arenas[ind]; 2932 if (ret == NULL) { 2933 /* 2934 * Avoid races with another thread that may have already 2935 * initialized arenas[ind]. 2936 */ 2937 malloc_spin_lock(&arenas_lock); 2938 if (arenas[ind] == NULL) 2939 ret = arenas_extend((unsigned)ind); 2940 else 2941 ret = arenas[ind]; 2942 malloc_spin_unlock(&arenas_lock); 2943 } 2944 } else 2945 ret = arenas[0]; 2946 #endif 2947 2948 assert(ret != NULL); 2949 return (ret); 2950 } 2951 2952 #ifndef NO_TLS 2953 /* 2954 * Choose an arena based on a per-thread value (slow-path code only, called 2955 * only by choose_arena()). 2956 */ 2957 static arena_t * 2958 choose_arena_hard(void) 2959 { 2960 arena_t *ret; 2961 2962 assert(__isthreaded); 2963 2964 #ifdef MALLOC_BALANCE 2965 /* Seed the PRNG used for arena load balancing. */ 2966 SPRN(balance, (uint32_t)(uintptr_t)(_pthread_self())); 2967 #endif 2968 2969 if (narenas > 1) { 2970 #ifdef MALLOC_BALANCE 2971 unsigned ind; 2972 2973 ind = PRN(balance, narenas_2pow); 2974 if ((ret = arenas[ind]) == NULL) { 2975 malloc_spin_lock(&arenas_lock); 2976 if ((ret = arenas[ind]) == NULL) 2977 ret = arenas_extend(ind); 2978 malloc_spin_unlock(&arenas_lock); 2979 } 2980 #else 2981 malloc_spin_lock(&arenas_lock); 2982 if ((ret = arenas[next_arena]) == NULL) 2983 ret = arenas_extend(next_arena); 2984 next_arena = (next_arena + 1) % narenas; 2985 malloc_spin_unlock(&arenas_lock); 2986 #endif 2987 } else 2988 ret = arenas[0]; 2989 2990 #ifdef MOZ_MEMORY_WINDOWS 2991 TlsSetValue(tlsIndex, ret); 2992 #else 2993 arenas_map = ret; 2994 #endif 2995 2996 return (ret); 2997 } 2998 #endif 2999 3000 static inline int 3001 arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b) 3002 { 3003 uintptr_t a_chunk = (uintptr_t)a; 3004 uintptr_t b_chunk = (uintptr_t)b; 3005 3006 assert(a != NULL); 3007 assert(b != NULL); 3008 3009 return ((a_chunk > b_chunk) - (a_chunk < b_chunk)); 3010 } 3011 3012 /* Wrap red-black tree macros in functions. */ 3013 rb_wrap(static, arena_chunk_tree_dirty_, arena_chunk_tree_t, 3014 arena_chunk_t, link_dirty, arena_chunk_comp) 3015 3016 static inline int 3017 arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 3018 { 3019 uintptr_t a_mapelm = (uintptr_t)a; 3020 uintptr_t b_mapelm = (uintptr_t)b; 3021 3022 assert(a != NULL); 3023 assert(b != NULL); 3024 3025 return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm)); 3026 } 3027 3028 /* Wrap red-black tree macros in functions. */ 3029 rb_wrap(static, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, link, 3030 arena_run_comp) 3031 3032 static inline int 3033 arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) 3034 { 3035 int ret; 3036 size_t a_size = a->bits & ~pagesize_mask; 3037 size_t b_size = b->bits & ~pagesize_mask; 3038 3039 ret = (a_size > b_size) - (a_size < b_size); 3040 if (ret == 0) { 3041 uintptr_t a_mapelm, b_mapelm; 3042 3043 if ((a->bits & CHUNK_MAP_KEY) == 0) 3044 a_mapelm = (uintptr_t)a; 3045 else { 3046 /* 3047 * Treat keys as though they are lower than anything 3048 * else. 3049 */ 3050 a_mapelm = 0; 3051 } 3052 b_mapelm = (uintptr_t)b; 3053 3054 ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm); 3055 } 3056 3057 return (ret); 3058 } 3059 3060 /* Wrap red-black tree macros in functions. */ 3061 rb_wrap(static, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, link, 3062 arena_avail_comp) 3063 3064 static inline void * 3065 arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin) 3066 { 3067 void *ret; 3068 unsigned i, mask, bit, regind; 3069 3070 assert(run->magic == ARENA_RUN_MAGIC); 3071 assert(run->regs_minelm < bin->regs_mask_nelms); 3072 3073 /* 3074 * Move the first check outside the loop, so that run->regs_minelm can 3075 * be updated unconditionally, without the possibility of updating it 3076 * multiple times. 3077 */ 3078 i = run->regs_minelm; 3079 mask = run->regs_mask[i]; 3080 if (mask != 0) { 3081 /* Usable allocation found. */ 3082 bit = ffs((int)mask) - 1; 3083 3084 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit); 3085 assert(regind < bin->nregs); 3086 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 3087 + (bin->reg_size * regind)); 3088 3089 /* Clear bit. */ 3090 mask ^= (1U << bit); 3091 run->regs_mask[i] = mask; 3092 3093 return (ret); 3094 } 3095 3096 for (i++; i < bin->regs_mask_nelms; i++) { 3097 mask = run->regs_mask[i]; 3098 if (mask != 0) { 3099 /* Usable allocation found. */ 3100 bit = ffs((int)mask) - 1; 3101 3102 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit); 3103 assert(regind < bin->nregs); 3104 ret = (void *)(((uintptr_t)run) + bin->reg0_offset 3105 + (bin->reg_size * regind)); 3106 3107 /* Clear bit. */ 3108 mask ^= (1U << bit); 3109 run->regs_mask[i] = mask; 3110 3111 /* 3112 * Make a note that nothing before this element 3113 * contains a free region. 3114 */ 3115 run->regs_minelm = i; /* Low payoff: + (mask == 0); */ 3116 3117 return (ret); 3118 } 3119 } 3120 /* Not reached. */ 3121 assert(0); 3122 return (NULL); 3123 } 3124 3125 static inline void 3126 arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size) 3127 { 3128 /* 3129 * To divide by a number D that is not a power of two we multiply 3130 * by (2^21 / D) and then right shift by 21 positions. 3131 * 3132 * X / D 3133 * 3134 * becomes 3135 * 3136 * (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT 3137 */ 3138 #define SIZE_INV_SHIFT 21 3139 #define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1) 3140 static const unsigned size_invs[] = { 3141 SIZE_INV(3), 3142 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7), 3143 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11), 3144 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15), 3145 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19), 3146 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23), 3147 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27), 3148 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31) 3149 #if (QUANTUM_2POW_MIN < 4) 3150 , 3151 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35), 3152 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39), 3153 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43), 3154 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47), 3155 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51), 3156 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55), 3157 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59), 3158 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63) 3159 #endif 3160 }; 3161 unsigned diff, regind, elm, bit; 3162 3163 assert(run->magic == ARENA_RUN_MAGIC); 3164 assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3 3165 >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN)); 3166 3167 /* 3168 * Avoid doing division with a variable divisor if possible. Using 3169 * actual division here can reduce allocator throughput by over 20%! 3170 */ 3171 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset); 3172 if ((size & (size - 1)) == 0) { 3173 /* 3174 * log2_table allows fast division of a power of two in the 3175 * [1..128] range. 3176 * 3177 * (x / divisor) becomes (x >> log2_table[divisor - 1]). 3178 */ 3179 static const unsigned char log2_table[] = { 3180 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 3181 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 3182 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3183 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 3184 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3185 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3186 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3187 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7 3188 }; 3189 3190 if (size <= 128) 3191 regind = (diff >> log2_table[size - 1]); 3192 else if (size <= 32768) 3193 regind = diff >> (8 + log2_table[(size >> 8) - 1]); 3194 else { 3195 /* 3196 * The run size is too large for us to use the lookup 3197 * table. Use real division. 3198 */ 3199 regind = diff / size; 3200 } 3201 } else if (size <= ((sizeof(size_invs) / sizeof(unsigned)) 3202 << QUANTUM_2POW_MIN) + 2) { 3203 regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff; 3204 regind >>= SIZE_INV_SHIFT; 3205 } else { 3206 /* 3207 * size_invs isn't large enough to handle this size class, so 3208 * calculate regind using actual division. This only happens 3209 * if the user increases small_max via the 'S' runtime 3210 * configuration option. 3211 */ 3212 regind = diff / size; 3213 }; 3214 assert(diff == regind * size); 3215 assert(regind < bin->nregs); 3216 3217 elm = regind >> (SIZEOF_INT_2POW + 3); 3218 if (elm < run->regs_minelm) 3219 run->regs_minelm = elm; 3220 bit = regind - (elm << (SIZEOF_INT_2POW + 3)); 3221 assert((run->regs_mask[elm] & (1U << bit)) == 0); 3222 run->regs_mask[elm] |= (1U << bit); 3223 #undef SIZE_INV 3224 #undef SIZE_INV_SHIFT 3225 } 3226 3227 static void 3228 arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large, 3229 bool zero) 3230 { 3231 arena_chunk_t *chunk; 3232 size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i; 3233 3234 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 3235 old_ndirty = chunk->ndirty; 3236 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) 3237 >> pagesize_2pow); 3238 total_pages = (chunk->map[run_ind].bits & ~pagesize_mask) >> 3239 pagesize_2pow; 3240 need_pages = (size >> pagesize_2pow); 3241 assert(need_pages > 0); 3242 assert(need_pages <= total_pages); 3243 rem_pages = total_pages - need_pages; 3244 3245 arena_avail_tree_remove(&arena->runs_avail, &chunk->map[run_ind]); 3246 3247 /* Keep track of trailing unused pages for later use. */ 3248 if (rem_pages > 0) { 3249 chunk->map[run_ind+need_pages].bits = (rem_pages << 3250 pagesize_2pow) | (chunk->map[run_ind+need_pages].bits & 3251 pagesize_mask); 3252 chunk->map[run_ind+total_pages-1].bits = (rem_pages << 3253 pagesize_2pow) | (chunk->map[run_ind+total_pages-1].bits & 3254 pagesize_mask); 3255 arena_avail_tree_insert(&arena->runs_avail, 3256 &chunk->map[run_ind+need_pages]); 3257 } 3258 3259 for (i = 0; i < need_pages; i++) { 3260 #ifdef MALLOC_DECOMMIT 3261 /* 3262 * Commit decommitted pages if necessary. If a decommitted 3263 * page is encountered, commit all needed adjacent decommitted 3264 * pages in one operation, in order to reduce system call 3265 * overhead. 3266 */ 3267 if (chunk->map[run_ind + i].bits & CHUNK_MAP_DECOMMITTED) { 3268 size_t j; 3269 3270 /* 3271 * Advance i+j to just past the index of the last page 3272 * to commit. Clear CHUNK_MAP_DECOMMITTED along the 3273 * way. 3274 */ 3275 for (j = 0; i + j < need_pages && (chunk->map[run_ind + 3276 i + j].bits & CHUNK_MAP_DECOMMITTED); j++) { 3277 chunk->map[run_ind + i + j].bits ^= 3278 CHUNK_MAP_DECOMMITTED; 3279 } 3280 3281 pages_commit((void *)((uintptr_t)chunk + ((run_ind + i) 3282 << pagesize_2pow)), (j << pagesize_2pow)); 3283 # ifdef MALLOC_STATS 3284 arena->stats.ncommit++; 3285 # endif 3286 } else /* No need to zero since commit zeros. */ 3287 #endif 3288 3289 /* Zero if necessary. */ 3290 if (zero) { 3291 if ((chunk->map[run_ind + i].bits & CHUNK_MAP_ZEROED) 3292 == 0) { 3293 VALGRIND_MALLOCLIKE_BLOCK((void *)((uintptr_t) 3294 chunk + ((run_ind + i) << pagesize_2pow)), 3295 pagesize, 0, false); 3296 memset((void *)((uintptr_t)chunk + ((run_ind 3297 + i) << pagesize_2pow)), 0, pagesize); 3298 VALGRIND_FREELIKE_BLOCK((void *)((uintptr_t) 3299 chunk + ((run_ind + i) << pagesize_2pow)), 3300 0); 3301 /* CHUNK_MAP_ZEROED is cleared below. */ 3302 } 3303 } 3304 3305 /* Update dirty page accounting. */ 3306 if (chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) { 3307 chunk->ndirty--; 3308 arena->ndirty--; 3309 /* CHUNK_MAP_DIRTY is cleared below. */ 3310 } 3311 3312 /* Initialize the chunk map. */ 3313 if (large) { 3314 chunk->map[run_ind + i].bits = CHUNK_MAP_LARGE 3315 | CHUNK_MAP_ALLOCATED; 3316 } else { 3317 chunk->map[run_ind + i].bits = (size_t)run 3318 | CHUNK_MAP_ALLOCATED; 3319 } 3320 } 3321 3322 /* 3323 * Set the run size only in the first element for large runs. This is 3324 * primarily a debugging aid, since the lack of size info for trailing 3325 * pages only matters if the application tries to operate on an 3326 * interior pointer. 3327 */ 3328 if (large) 3329 chunk->map[run_ind].bits |= size; 3330 3331 if (chunk->ndirty == 0 && old_ndirty > 0) 3332 arena_chunk_tree_dirty_remove(&arena->chunks_dirty, chunk); 3333 } 3334 3335 static void 3336 arena_chunk_init(arena_t *arena, arena_chunk_t *chunk) 3337 { 3338 arena_run_t *run; 3339 size_t i; 3340 3341 VALGRIND_MALLOCLIKE_BLOCK(chunk, (arena_chunk_header_npages << 3342 pagesize_2pow), 0, false); 3343 #ifdef MALLOC_STATS 3344 arena->stats.mapped += chunksize; 3345 #endif 3346 3347 chunk->arena = arena; 3348 3349 /* 3350 * Claim that no pages are in use, since the header is merely overhead. 3351 */ 3352 chunk->ndirty = 0; 3353 3354 /* Initialize the map to contain one maximal free untouched run. */ 3355 run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages << 3356 pagesize_2pow)); 3357 for (i = 0; i < arena_chunk_header_npages; i++) 3358 chunk->map[i].bits = 0; 3359 chunk->map[i].bits = arena_maxclass 3360 #ifdef MALLOC_DECOMMIT 3361 | CHUNK_MAP_DECOMMITTED 3362 #endif 3363 | CHUNK_MAP_ZEROED; 3364 for (i++; i < chunk_npages-1; i++) { 3365 chunk->map[i].bits = 3366 #ifdef MALLOC_DECOMMIT 3367 CHUNK_MAP_DECOMMITTED | 3368 #endif 3369 CHUNK_MAP_ZEROED; 3370 } 3371 chunk->map[chunk_npages-1].bits = arena_maxclass 3372 #ifdef MALLOC_DECOMMIT 3373 | CHUNK_MAP_DECOMMITTED 3374 #endif 3375 | CHUNK_MAP_ZEROED; 3376 3377 #ifdef MALLOC_DECOMMIT 3378 /* 3379 * Start out decommitted, in order to force a closer correspondence 3380 * between dirty pages and committed untouched pages. 3381 */ 3382 pages_decommit(run, arena_maxclass); 3383 # ifdef MALLOC_STATS 3384 arena->stats.ndecommit++; 3385 arena->stats.decommitted += (chunk_npages - arena_chunk_header_npages); 3386 # endif 3387 #endif 3388 3389 /* Insert the run into the runs_avail tree. */ 3390 arena_avail_tree_insert(&arena->runs_avail, 3391 &chunk->map[arena_chunk_header_npages]); 3392 } 3393 3394 static void 3395 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) 3396 { 3397 3398 if (arena->spare != NULL) { 3399 if (arena->spare->ndirty > 0) { 3400 arena_chunk_tree_dirty_remove( 3401 &chunk->arena->chunks_dirty, arena->spare); 3402 arena->ndirty -= arena->spare->ndirty; 3403 } 3404 VALGRIND_FREELIKE_BLOCK(arena->spare, 0); 3405 chunk_dealloc((void *)arena->spare, chunksize); 3406 #ifdef MALLOC_STATS 3407 arena->stats.mapped -= chunksize; 3408 #endif 3409 } 3410 3411 /* 3412 * Remove run from runs_avail, regardless of whether this chunk 3413 * will be cached, so that the arena does not use it. Dirty page 3414 * flushing only uses the chunks_dirty tree, so leaving this chunk in 3415 * the chunks_* trees is sufficient for that purpose. 3416 */ 3417 arena_avail_tree_remove(&arena->runs_avail, 3418 &chunk->map[arena_chunk_header_npages]); 3419 3420 arena->spare = chunk; 3421 } 3422 3423 static arena_run_t * 3424 arena_run_alloc(arena_t *arena, arena_bin_t *bin, size_t size, bool large, 3425 bool zero) 3426 { 3427 arena_chunk_t *chunk; 3428 arena_run_t *run; 3429 arena_chunk_map_t *mapelm, key; 3430 3431 assert(size <= arena_maxclass); 3432 assert((size & pagesize_mask) == 0); 3433 3434 chunk = NULL; 3435 while (true) { 3436 /* Search the arena's chunks for the lowest best fit. */ 3437 key.bits = size | CHUNK_MAP_KEY; 3438 mapelm = arena_avail_tree_nsearch(&arena->runs_avail, &key); 3439 if (mapelm != NULL) { 3440 arena_chunk_t *run_chunk = (arena_chunk_t*)CHUNK_ADDR2BASE(mapelm); 3441 size_t pageind = ((uintptr_t)mapelm - 3442 (uintptr_t)run_chunk->map) / 3443 sizeof(arena_chunk_map_t); 3444 3445 if (chunk != NULL) 3446 chunk_dealloc(chunk, chunksize); 3447 run = (arena_run_t *)((uintptr_t)run_chunk + (pageind 3448 << pagesize_2pow)); 3449 arena_run_split(arena, run, size, large, zero); 3450 return (run); 3451 } 3452 3453 if (arena->spare != NULL) { 3454 /* Use the spare. */ 3455 chunk = arena->spare; 3456 arena->spare = NULL; 3457 run = (arena_run_t *)((uintptr_t)chunk + 3458 (arena_chunk_header_npages << pagesize_2pow)); 3459 /* Insert the run into the runs_avail tree. */ 3460 arena_avail_tree_insert(&arena->runs_avail, 3461 &chunk->map[arena_chunk_header_npages]); 3462 arena_run_split(arena, run, size, large, zero); 3463 return (run); 3464 } 3465 3466 /* 3467 * No usable runs. Create a new chunk from which to allocate 3468 * the run. 3469 */ 3470 if (chunk == NULL) { 3471 uint64_t chunk_seq; 3472 3473 /* 3474 * Record the chunk allocation sequence number in order 3475 * to detect races. 3476 */ 3477 arena->chunk_seq++; 3478 chunk_seq = arena->chunk_seq; 3479 3480 /* 3481 * Drop the arena lock while allocating a chunk, since 3482 * reserve notifications may cause recursive 3483 * allocation. Dropping the lock here opens an 3484 * allocataion race, but we recover. 3485 */ 3486 malloc_mutex_unlock(&arena->lock); 3487 chunk = (arena_chunk_t *)chunk_alloc(chunksize, true, 3488 true); 3489 malloc_mutex_lock(&arena->lock); 3490 3491 /* 3492 * Check whether a race allowed a usable run to appear. 3493 */ 3494 if (bin != NULL && (run = bin->runcur) != NULL && 3495 run->nfree > 0) { 3496 if (chunk != NULL) 3497 chunk_dealloc(chunk, chunksize); 3498 return (run); 3499 } 3500 3501 /* 3502 * If this thread raced with another such that multiple 3503 * chunks were allocated, make sure that there is still 3504 * inadequate space before using this chunk. 3505 */ 3506 if (chunk_seq != arena->chunk_seq) 3507 continue; 3508 3509 /* 3510 * Check for an error *after* checking for a race, 3511 * since a race could also cause a transient OOM 3512 * condition. 3513 */ 3514 if (chunk == NULL) 3515 return (NULL); 3516 } 3517 3518 arena_chunk_init(arena, chunk); 3519 run = (arena_run_t *)((uintptr_t)chunk + 3520 (arena_chunk_header_npages << pagesize_2pow)); 3521 /* Update page map. */ 3522 arena_run_split(arena, run, size, large, zero); 3523 return (run); 3524 } 3525 } 3526 3527 static void 3528 arena_purge(arena_t *arena) 3529 { 3530 arena_chunk_t *chunk; 3531 size_t i, npages; 3532 #ifdef MALLOC_DEBUG 3533 size_t ndirty = 0; 3534 rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty, 3535 chunk) { 3536 ndirty += chunk->ndirty; 3537 } rb_foreach_end(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk) 3538 assert(ndirty == arena->ndirty); 3539 #endif 3540 assert(arena->ndirty > opt_dirty_max); 3541 3542 #ifdef MALLOC_STATS 3543 arena->stats.npurge++; 3544 #endif 3545 3546 /* 3547 * Iterate downward through chunks until enough dirty memory has been 3548 * purged. Terminate as soon as possible in order to minimize the 3549 * number of system calls, even if a chunk has only been partially 3550 * purged. 3551 */ 3552 while (arena->ndirty > (opt_dirty_max >> 1)) { 3553 chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty); 3554 assert(chunk != NULL); 3555 3556 for (i = chunk_npages - 1; chunk->ndirty > 0; i--) { 3557 assert(i >= arena_chunk_header_npages); 3558 3559 if (chunk->map[i].bits & CHUNK_MAP_DIRTY) { 3560 #ifdef MALLOC_DECOMMIT 3561 assert((chunk->map[i].bits & 3562 CHUNK_MAP_DECOMMITTED) == 0); 3563 #endif 3564 chunk->map[i].bits ^= 3565 #ifdef MALLOC_DECOMMIT 3566 CHUNK_MAP_DECOMMITTED | 3567 #endif 3568 CHUNK_MAP_DIRTY; 3569 /* Find adjacent dirty run(s). */ 3570 for (npages = 1; i > arena_chunk_header_npages 3571 && (chunk->map[i - 1].bits & 3572 CHUNK_MAP_DIRTY); npages++) { 3573 i--; 3574 #ifdef MALLOC_DECOMMIT 3575 assert((chunk->map[i].bits & 3576 CHUNK_MAP_DECOMMITTED) == 0); 3577 #endif 3578 chunk->map[i].bits ^= 3579 #ifdef MALLOC_DECOMMIT 3580 CHUNK_MAP_DECOMMITTED | 3581 #endif 3582 CHUNK_MAP_DIRTY; 3583 } 3584 chunk->ndirty -= npages; 3585 arena->ndirty -= npages; 3586 3587 #ifdef MALLOC_DECOMMIT 3588 pages_decommit((void *)((uintptr_t) 3589 chunk + (i << pagesize_2pow)), 3590 (npages << pagesize_2pow)); 3591 # ifdef MALLOC_STATS 3592 arena->stats.ndecommit++; 3593 arena->stats.decommitted += npages; 3594 # endif 3595 #else 3596 madvise((void *)((uintptr_t)chunk + (i << 3597 pagesize_2pow)), (npages << pagesize_2pow), 3598 MADV_FREE); 3599 #endif 3600 #ifdef MALLOC_STATS 3601 arena->stats.nmadvise++; 3602 arena->stats.purged += npages; 3603 #endif 3604 if (arena->ndirty <= (opt_dirty_max >> 1)) 3605 break; 3606 } 3607 } 3608 3609 if (chunk->ndirty == 0) { 3610 arena_chunk_tree_dirty_remove(&arena->chunks_dirty, 3611 chunk); 3612 } 3613 } 3614 } 3615 3616 static void 3617 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) 3618 { 3619 arena_chunk_t *chunk; 3620 size_t size, run_ind, run_pages; 3621 3622 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); 3623 run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) 3624 >> pagesize_2pow); 3625 assert(run_ind >= arena_chunk_header_npages); 3626 assert(run_ind < chunk_npages); 3627 if ((chunk->map[run_ind].bits & CHUNK_MAP_LARGE) != 0) 3628 size = chunk->map[run_ind].bits & ~pagesize_mask; 3629 else 3630 size = run->bin->run_size; 3631 run_pages = (size >> pagesize_2pow); 3632 3633 /* Mark pages as unallocated in the chunk map. */ 3634 if (dirty) { 3635 size_t i; 3636 3637 for (i = 0; i < run_pages; i++) { 3638 assert((chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) 3639 == 0); 3640 chunk->map[run_ind + i].bits = CHUNK_MAP_DIRTY; 3641 } 3642 3643 if (chunk->ndirty == 0) { 3644 arena_chunk_tree_dirty_insert(&arena->chunks_dirty, 3645 chunk); 3646 } 3647 chunk->ndirty += run_pages; 3648 arena->ndirty += run_pages; 3649 } else { 3650 size_t i; 3651 3652 for (i = 0; i < run_pages; i++) { 3653 chunk->map[run_ind + i].bits &= ~(CHUNK_MAP_LARGE | 3654 CHUNK_MAP_ALLOCATED); 3655 } 3656 } 3657 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 3658 pagesize_mask); 3659 chunk->map[run_ind+run_pages-1].bits = size | 3660 (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); 3661 3662 /* Try to coalesce forward. */ 3663 if (run_ind + run_pages < chunk_npages && 3664 (chunk->map[run_ind+run_pages].bits & CHUNK_MAP_ALLOCATED) == 0) { 3665 size_t nrun_size = chunk->map[run_ind+run_pages].bits & 3666 ~pagesize_mask; 3667 3668 /* 3669 * Remove successor from runs_avail; the coalesced run is 3670 * inserted later. 3671 */ 3672 arena_avail_tree_remove(&arena->runs_avail, 3673 &chunk->map[run_ind+run_pages]); 3674 3675 size += nrun_size; 3676 run_pages = size >> pagesize_2pow; 3677 3678 assert((chunk->map[run_ind+run_pages-1].bits & ~pagesize_mask) 3679 == nrun_size); 3680 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 3681 pagesize_mask); 3682 chunk->map[run_ind+run_pages-1].bits = size | 3683 (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); 3684 } 3685 3686 /* Try to coalesce backward. */ 3687 if (run_ind > arena_chunk_header_npages && (chunk->map[run_ind-1].bits & 3688 CHUNK_MAP_ALLOCATED) == 0) { 3689 size_t prun_size = chunk->map[run_ind-1].bits & ~pagesize_mask; 3690 3691 run_ind -= prun_size >> pagesize_2pow; 3692 3693 /* 3694 * Remove predecessor from runs_avail; the coalesced run is 3695 * inserted later. 3696 */ 3697 arena_avail_tree_remove(&arena->runs_avail, 3698 &chunk->map[run_ind]); 3699 3700 size += prun_size; 3701 run_pages = size >> pagesize_2pow; 3702 3703 assert((chunk->map[run_ind].bits & ~pagesize_mask) == 3704 prun_size); 3705 chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & 3706 pagesize_mask); 3707 chunk->map[run_ind+run_pages-1].bits = size | 3708 (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); 3709 } 3710 3711 /* Insert into runs_avail, now that coalescing is complete. */ 3712 arena_avail_tree_insert(&arena->runs_avail, &chunk->map[run_ind]); 3713 3714 /* Deallocate chunk if it is now completely unused. */ 3715 if ((chunk->map[arena_chunk_header_npages].bits & (~pagesize_mask | 3716 CHUNK_MAP_ALLOCATED)) == arena_maxclass) 3717 arena_chunk_dealloc(arena, chunk); 3718 3719 /* Enforce opt_dirty_max. */ 3720 if (arena->ndirty > opt_dirty_max) 3721 arena_purge(arena); 3722 } 3723 3724 static void 3725 arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 3726 size_t oldsize, size_t newsize) 3727 { 3728 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow; 3729 size_t head_npages = (oldsize - newsize) >> pagesize_2pow; 3730 3731 assert(oldsize > newsize); 3732 3733 /* 3734 * Update the chunk map so that arena_run_dalloc() can treat the 3735 * leading run as separately allocated. 3736 */ 3737 chunk->map[pageind].bits = (oldsize - newsize) | CHUNK_MAP_LARGE | 3738 CHUNK_MAP_ALLOCATED; 3739 chunk->map[pageind+head_npages].bits = newsize | CHUNK_MAP_LARGE | 3740 CHUNK_MAP_ALLOCATED; 3741 3742 arena_run_dalloc(arena, run, false); 3743 } 3744 3745 static void 3746 arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, 3747 size_t oldsize, size_t newsize, bool dirty) 3748 { 3749 size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow; 3750 size_t npages = newsize >> pagesize_2pow; 3751 3752 assert(oldsize > newsize); 3753 3754 /* 3755 * Update the chunk map so that arena_run_dalloc() can treat the 3756 * trailing run as separately allocated. 3757 */ 3758 chunk->map[pageind].bits = newsize | CHUNK_MAP_LARGE | 3759 CHUNK_MAP_ALLOCATED; 3760 chunk->map[pageind+npages].bits = (oldsize - newsize) | CHUNK_MAP_LARGE 3761 | CHUNK_MAP_ALLOCATED; 3762 3763 arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize), 3764 dirty); 3765 } 3766 3767 static arena_run_t * 3768 arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin) 3769 { 3770 arena_chunk_map_t *mapelm; 3771 arena_run_t *run; 3772 unsigned i, remainder; 3773 3774 /* Look for a usable run. */ 3775 mapelm = arena_run_tree_first(&bin->runs); 3776 if (mapelm != NULL) { 3777 /* run is guaranteed to have available space. */ 3778 arena_run_tree_remove(&bin->runs, mapelm); 3779 run = (arena_run_t *)(mapelm->bits & ~pagesize_mask); 3780 #ifdef MALLOC_STATS 3781 bin->stats.reruns++; 3782 #endif 3783 return (run); 3784 } 3785 /* No existing runs have any space available. */ 3786 3787 /* Allocate a new run. */ 3788 run = arena_run_alloc(arena, bin, bin->run_size, false, false); 3789 if (run == NULL) 3790 return (NULL); 3791 /* 3792 * Don't initialize if a race in arena_run_alloc() allowed an existing 3793 * run to become usable. 3794 */ 3795 if (run == bin->runcur) 3796 return (run); 3797 3798 VALGRIND_MALLOCLIKE_BLOCK(run, sizeof(arena_run_t) + (sizeof(unsigned) * 3799 (bin->regs_mask_nelms - 1)), 0, false); 3800 3801 /* Initialize run internals. */ 3802 run->bin = bin; 3803 3804 for (i = 0; i < bin->regs_mask_nelms - 1; i++) 3805 run->regs_mask[i] = UINT_MAX; 3806 remainder = bin->nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1); 3807 if (remainder == 0) 3808 run->regs_mask[i] = UINT_MAX; 3809 else { 3810 /* The last element has spare bits that need to be unset. */ 3811 run->regs_mask[i] = (UINT_MAX >> ((1U << (SIZEOF_INT_2POW + 3)) 3812 - remainder)); 3813 } 3814 3815 run->regs_minelm = 0; 3816 3817 run->nfree = bin->nregs; 3818 #ifdef MALLOC_DEBUG 3819 run->magic = ARENA_RUN_MAGIC; 3820 #endif 3821 3822 #ifdef MALLOC_STATS 3823 bin->stats.nruns++; 3824 bin->stats.curruns++; 3825 if (bin->stats.curruns > bin->stats.highruns) 3826 bin->stats.highruns = bin->stats.curruns; 3827 #endif 3828 return (run); 3829 } 3830 3831 /* bin->runcur must have space available before this function is called. */ 3832 static inline void * 3833 arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run) 3834 { 3835 void *ret; 3836 3837 assert(run->magic == ARENA_RUN_MAGIC); 3838 assert(run->nfree > 0); 3839 3840 ret = arena_run_reg_alloc(run, bin); 3841 assert(ret != NULL); 3842 run->nfree--; 3843 3844 return (ret); 3845 } 3846 3847 /* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */ 3848 static void * 3849 arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin) 3850 { 3851 3852 bin->runcur = arena_bin_nonfull_run_get(arena, bin); 3853 if (bin->runcur == NULL) 3854 return (NULL); 3855 assert(bin->runcur->magic == ARENA_RUN_MAGIC); 3856 assert(bin->runcur->nfree > 0); 3857 3858 return (arena_bin_malloc_easy(arena, bin, bin->runcur)); 3859 } 3860 3861 /* 3862 * Calculate bin->run_size such that it meets the following constraints: 3863 * 3864 * *) bin->run_size >= min_run_size 3865 * *) bin->run_size <= arena_maxclass 3866 * *) bin->run_size <= RUN_MAX_SMALL 3867 * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed). 3868 * 3869 * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are 3870 * also calculated here, since these settings are all interdependent. 3871 */ 3872 static size_t 3873 arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size) 3874 { 3875 size_t try_run_size, good_run_size; 3876 unsigned good_nregs, good_mask_nelms, good_reg0_offset; 3877 unsigned try_nregs, try_mask_nelms, try_reg0_offset; 3878 3879 assert(min_run_size >= pagesize); 3880 assert(min_run_size <= arena_maxclass); 3881 assert(min_run_size <= RUN_MAX_SMALL); 3882 3883 /* 3884 * Calculate known-valid settings before entering the run_size 3885 * expansion loop, so that the first part of the loop always copies 3886 * valid settings. 3887 * 3888 * The do..while loop iteratively reduces the number of regions until 3889 * the run header and the regions no longer overlap. A closed formula 3890 * would be quite messy, since there is an interdependency between the 3891 * header's mask length and the number of regions. 3892 */ 3893 try_run_size = min_run_size; 3894 try_nregs = ((try_run_size - sizeof(arena_run_t)) / bin->reg_size) 3895 + 1; /* Counter-act try_nregs-- in loop. */ 3896 do { 3897 try_nregs--; 3898 try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) + 3899 ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0); 3900 try_reg0_offset = try_run_size - (try_nregs * bin->reg_size); 3901 } while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1)) 3902 > try_reg0_offset); 3903 3904 /* run_size expansion loop. */ 3905 do { 3906 /* 3907 * Copy valid settings before trying more aggressive settings. 3908 */ 3909 good_run_size = try_run_size; 3910 good_nregs = try_nregs; 3911 good_mask_nelms = try_mask_nelms; 3912 good_reg0_offset = try_reg0_offset; 3913 3914 /* Try more aggressive settings. */ 3915 try_run_size += pagesize; 3916 try_nregs = ((try_run_size - sizeof(arena_run_t)) / 3917 bin->reg_size) + 1; /* Counter-act try_nregs-- in loop. */ 3918 do { 3919 try_nregs--; 3920 try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) + 3921 ((try_nregs & ((1U << (SIZEOF_INT_2POW + 3)) - 1)) ? 3922 1 : 0); 3923 try_reg0_offset = try_run_size - (try_nregs * 3924 bin->reg_size); 3925 } while (sizeof(arena_run_t) + (sizeof(unsigned) * 3926 (try_mask_nelms - 1)) > try_reg0_offset); 3927 } while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL 3928 && RUN_MAX_OVRHD * (bin->reg_size << 3) > RUN_MAX_OVRHD_RELAX 3929 && (try_reg0_offset << RUN_BFP) > RUN_MAX_OVRHD * try_run_size); 3930 3931 assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1)) 3932 <= good_reg0_offset); 3933 assert((good_mask_nelms << (SIZEOF_INT_2POW + 3)) >= good_nregs); 3934 3935 /* Copy final settings. */ 3936 bin->run_size = good_run_size; 3937 bin->nregs = good_nregs; 3938 bin->regs_mask_nelms = good_mask_nelms; 3939 bin->reg0_offset = good_reg0_offset; 3940 3941 return (good_run_size); 3942 } 3943 3944 #ifdef MALLOC_BALANCE 3945 static inline void 3946 arena_lock_balance(arena_t *arena) 3947 { 3948 unsigned contention; 3949 3950 contention = malloc_spin_lock(&arena->lock); 3951 if (narenas > 1) { 3952 /* 3953 * Calculate the exponentially averaged contention for this 3954 * arena. Due to integer math always rounding down, this value 3955 * decays somewhat faster then normal. 3956 */ 3957 arena->contention = (((uint64_t)arena->contention 3958 * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW)-1)) 3959 + (uint64_t)contention) >> BALANCE_ALPHA_INV_2POW; 3960 if (arena->contention >= opt_balance_threshold) 3961 arena_lock_balance_hard(arena); 3962 } 3963 } 3964 3965 static void 3966 arena_lock_balance_hard(arena_t *arena) 3967 { 3968 uint32_t ind; 3969 3970 arena->contention = 0; 3971 #ifdef MALLOC_STATS 3972 arena->stats.nbalance++; 3973 #endif 3974 ind = PRN(balance, narenas_2pow); 3975 if (arenas[ind] != NULL) { 3976 #ifdef MOZ_MEMORY_WINDOWS 3977 TlsSetValue(tlsIndex, arenas[ind]); 3978 #else 3979 arenas_map = arenas[ind]; 3980 #endif 3981 } else { 3982 malloc_spin_lock(&arenas_lock); 3983 if (arenas[ind] != NULL) { 3984 #ifdef MOZ_MEMORY_WINDOWS 3985 TlsSetValue(tlsIndex, arenas[ind]); 3986 #else 3987 arenas_map = arenas[ind]; 3988 #endif 3989 } else { 3990 #ifdef MOZ_MEMORY_WINDOWS 3991 TlsSetValue(tlsIndex, arenas_extend(ind)); 3992 #else 3993 arenas_map = arenas_extend(ind); 3994 #endif 3995 } 3996 malloc_spin_unlock(&arenas_lock); 3997 } 3998 } 3999 #endif 4000 4001 static inline void * 4002 arena_malloc_small(arena_t *arena, size_t size, bool zero) 4003 { 4004 void *ret; 4005 arena_bin_t *bin; 4006 arena_run_t *run; 4007 4008 if (size < small_min) { 4009 /* Tiny. */ 4010 size = pow2_ceil(size); 4011 bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW + 4012 1)))]; 4013 #if (!defined(NDEBUG) || defined(MALLOC_STATS)) 4014 /* 4015 * Bin calculation is always correct, but we may need 4016 * to fix size for the purposes of assertions and/or 4017 * stats accuracy. 4018 */ 4019 if (size < (1U << TINY_MIN_2POW)) 4020 size = (1U << TINY_MIN_2POW); 4021 #endif 4022 } else if (size <= small_max) { 4023 /* Quantum-spaced. */ 4024 size = QUANTUM_CEILING(size); 4025 bin = &arena->bins[ntbins + (size >> opt_quantum_2pow) 4026 - 1]; 4027 } else { 4028 /* Sub-page. */ 4029 size = pow2_ceil(size); 4030 bin = &arena->bins[ntbins + nqbins 4031 + (ffs((int)(size >> opt_small_max_2pow)) - 2)]; 4032 } 4033 assert(size == bin->reg_size); 4034 4035 #ifdef MALLOC_BALANCE 4036 arena_lock_balance(arena); 4037 #else 4038 malloc_spin_lock(&arena->lock); 4039 #endif 4040 if ((run = bin->runcur) != NULL && run->nfree > 0) 4041 ret = arena_bin_malloc_easy(arena, bin, run); 4042 else 4043 ret = arena_bin_malloc_hard(arena, bin); 4044 4045 if (ret == NULL) { 4046 malloc_spin_unlock(&arena->lock); 4047 return (NULL); 4048 } 4049 4050 #ifdef MALLOC_STATS 4051 bin->stats.nrequests++; 4052 arena->stats.nmalloc_small++; 4053 arena->stats.allocated_small += size; 4054 #endif 4055 malloc_spin_unlock(&arena->lock); 4056 4057 VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, zero); 4058 if (zero == false) { 4059 #ifdef MALLOC_FILL 4060 if (opt_junk) 4061 memset(ret, 0xa5, size); 4062 else if (opt_zero) 4063 memset(ret, 0, size); 4064 #endif 4065 } else 4066 memset(ret, 0, size); 4067 4068 return (ret); 4069 } 4070 4071 static void * 4072 arena_malloc_large(arena_t *arena, size_t size, bool zero) 4073 { 4074 void *ret; 4075 4076 /* Large allocation. */ 4077 size = PAGE_CEILING(size); 4078 #ifdef MALLOC_BALANCE 4079 arena_lock_balance(arena); 4080 #else 4081 malloc_spin_lock(&arena->lock); 4082 #endif 4083 ret = (void *)arena_run_alloc(arena, NULL, size, true, zero); 4084 if (ret == NULL) { 4085 malloc_spin_unlock(&arena->lock); 4086 return (NULL); 4087 } 4088 #ifdef MALLOC_STATS 4089 arena->stats.nmalloc_large++; 4090 arena->stats.allocated_large += size; 4091 #endif 4092 malloc_spin_unlock(&arena->lock); 4093 4094 VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, zero); 4095 if (zero == false) { 4096 #ifdef MALLOC_FILL 4097 if (opt_junk) 4098 memset(ret, 0xa5, size); 4099 else if (opt_zero) 4100 memset(ret, 0, size); 4101 #endif 4102 } 4103 4104 return (ret); 4105 } 4106 4107 static inline void * 4108 arena_malloc(arena_t *arena, size_t size, bool zero) 4109 { 4110 4111 assert(arena != NULL); 4112 assert(arena->magic == ARENA_MAGIC); 4113 assert(size != 0); 4114 assert(QUANTUM_CEILING(size) <= arena_maxclass); 4115 4116 if (size <= bin_maxclass) { 4117 return (arena_malloc_small(arena, size, zero)); 4118 } else 4119 return (arena_malloc_large(arena, size, zero)); 4120 } 4121 4122 static inline void * 4123 imalloc(size_t size) 4124 { 4125 4126 assert(size != 0); 4127 4128 if (size <= arena_maxclass) 4129 return (arena_malloc(choose_arena(), size, false)); 4130 else 4131 return (huge_malloc(size, false)); 4132 } 4133 4134 static inline void * 4135 icalloc(size_t size) 4136 { 4137 4138 if (size <= arena_maxclass) 4139 return (arena_malloc(choose_arena(), size, true)); 4140 else 4141 return (huge_malloc(size, true)); 4142 } 4143 4144 /* Only handles large allocations that require more than page alignment. */ 4145 static void * 4146 arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size) 4147 { 4148 void *ret; 4149 size_t offset; 4150 arena_chunk_t *chunk; 4151 4152 assert((size & pagesize_mask) == 0); 4153 assert((alignment & pagesize_mask) == 0); 4154 4155 #ifdef MALLOC_BALANCE 4156 arena_lock_balance(arena); 4157 #else 4158 malloc_spin_lock(&arena->lock); 4159 #endif 4160 ret = (void *)arena_run_alloc(arena, NULL, alloc_size, true, false); 4161 if (ret == NULL) { 4162 malloc_spin_unlock(&arena->lock); 4163 return (NULL); 4164 } 4165 4166 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret); 4167 4168 offset = (uintptr_t)ret & (alignment - 1); 4169 assert((offset & pagesize_mask) == 0); 4170 assert(offset < alloc_size); 4171 if (offset == 0) 4172 arena_run_trim_tail(arena, chunk, (arena_run_t*)ret, alloc_size, size, false); 4173 else { 4174 size_t leadsize, trailsize; 4175 4176 leadsize = alignment - offset; 4177 if (leadsize > 0) { 4178 arena_run_trim_head(arena, chunk, (arena_run_t*)ret, alloc_size, 4179 alloc_size - leadsize); 4180 ret = (void *)((uintptr_t)ret + leadsize); 4181 } 4182 4183 trailsize = alloc_size - leadsize - size; 4184 if (trailsize != 0) { 4185 /* Trim trailing space. */ 4186 assert(trailsize < alloc_size); 4187 arena_run_trim_tail(arena, chunk, (arena_run_t*)ret, size + trailsize, 4188 size, false); 4189 } 4190 } 4191 4192 #ifdef MALLOC_STATS 4193 arena->stats.nmalloc_large++; 4194 arena->stats.allocated_large += size; 4195 #endif 4196 malloc_spin_unlock(&arena->lock); 4197 4198 VALGRIND_MALLOCLIKE_BLOCK(ret, size, 0, false); 4199 #ifdef MALLOC_FILL 4200 if (opt_junk) 4201 memset(ret, 0xa5, size); 4202 else if (opt_zero) 4203 memset(ret, 0, size); 4204 #endif 4205 return (ret); 4206 } 4207 4208 static inline void * 4209 ipalloc(size_t alignment, size_t size) 4210 { 4211 void *ret; 4212 size_t ceil_size; 4213 4214 /* 4215 * Round size up to the nearest multiple of alignment. 4216 * 4217 * This done, we can take advantage of the fact that for each small 4218 * size class, every object is aligned at the smallest power of two 4219 * that is non-zero in the base two representation of the size. For 4220 * example: 4221 * 4222 * Size | Base 2 | Minimum alignment 4223 * -----+----------+------------------ 4224 * 96 | 1100000 | 32 4225 * 144 | 10100000 | 32 4226 * 192 | 11000000 | 64 4227 * 4228 * Depending on runtime settings, it is possible that arena_malloc() 4229 * will further round up to a power of two, but that never causes 4230 * correctness issues. 4231 */ 4232 ceil_size = (size + (alignment - 1)) & (-alignment); 4233 /* 4234 * (ceil_size < size) protects against the combination of maximal 4235 * alignment and size greater than maximal alignment. 4236 */ 4237 if (ceil_size < size) { 4238 /* size_t overflow. */ 4239 return (NULL); 4240 } 4241 4242 if (ceil_size <= pagesize || (alignment <= pagesize 4243 && ceil_size <= arena_maxclass)) 4244 ret = arena_malloc(choose_arena(), ceil_size, false); 4245 else { 4246 size_t run_size; 4247 4248 /* 4249 * We can't achieve sub-page alignment, so round up alignment 4250 * permanently; it makes later calculations simpler. 4251 */ 4252 alignment = PAGE_CEILING(alignment); 4253 ceil_size = PAGE_CEILING(size); 4254 /* 4255 * (ceil_size < size) protects against very large sizes within 4256 * pagesize of SIZE_T_MAX. 4257 * 4258 * (ceil_size + alignment < ceil_size) protects against the 4259 * combination of maximal alignment and ceil_size large enough 4260 * to cause overflow. This is similar to the first overflow 4261 * check above, but it needs to be repeated due to the new 4262 * ceil_size value, which may now be *equal* to maximal 4263 * alignment, whereas before we only detected overflow if the 4264 * original size was *greater* than maximal alignment. 4265 */ 4266 if (ceil_size < size || ceil_size + alignment < ceil_size) { 4267 /* size_t overflow. */ 4268 return (NULL); 4269 } 4270 4271 /* 4272 * Calculate the size of the over-size run that arena_palloc() 4273 * would need to allocate in order to guarantee the alignment. 4274 */ 4275 if (ceil_size >= alignment) 4276 run_size = ceil_size + alignment - pagesize; 4277 else { 4278 /* 4279 * It is possible that (alignment << 1) will cause 4280 * overflow, but it doesn't matter because we also 4281 * subtract pagesize, which in the case of overflow 4282 * leaves us with a very large run_size. That causes 4283 * the first conditional below to fail, which means 4284 * that the bogus run_size value never gets used for 4285 * anything important. 4286 */ 4287 run_size = (alignment << 1) - pagesize; 4288 } 4289 4290 if (run_size <= arena_maxclass) { 4291 ret = arena_palloc(choose_arena(), alignment, ceil_size, 4292 run_size); 4293 } else if (alignment <= chunksize) 4294 ret = huge_malloc(ceil_size, false); 4295 else 4296 ret = huge_palloc(alignment, ceil_size); 4297 } 4298 4299 assert(((uintptr_t)ret & (alignment - 1)) == 0); 4300 return (ret); 4301 } 4302 4303 /* Return the size of the allocation pointed to by ptr. */ 4304 static size_t 4305 arena_salloc(const void *ptr) 4306 { 4307 size_t ret; 4308 arena_chunk_t *chunk; 4309 size_t pageind, mapbits; 4310 4311 assert(ptr != NULL); 4312 assert(CHUNK_ADDR2BASE(ptr) != ptr); 4313 4314 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 4315 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow); 4316 mapbits = chunk->map[pageind].bits; 4317 assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); 4318 if ((mapbits & CHUNK_MAP_LARGE) == 0) { 4319 arena_run_t *run = (arena_run_t *)(mapbits & ~pagesize_mask); 4320 assert(run->magic == ARENA_RUN_MAGIC); 4321 ret = run->bin->reg_size; 4322 } else { 4323 ret = mapbits & ~pagesize_mask; 4324 assert(ret != 0); 4325 } 4326 4327 return (ret); 4328 } 4329 4330 #if (defined(MALLOC_VALIDATE) || defined(MOZ_MEMORY_DARWIN)) 4331 /* 4332 * Validate ptr before assuming that it points to an allocation. Currently, 4333 * the following validation is performed: 4334 * 4335 * + Check that ptr is not NULL. 4336 * 4337 * + Check that ptr lies within a mapped chunk. 4338 */ 4339 static inline size_t 4340 isalloc_validate(const void *ptr) 4341 { 4342 arena_chunk_t *chunk; 4343 4344 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 4345 if (chunk == NULL) 4346 return (0); 4347 4348 if (malloc_rtree_get(chunk_rtree, (uintptr_t)chunk) == NULL) 4349 return (0); 4350 4351 if (chunk != ptr) { 4352 assert(chunk->arena->magic == ARENA_MAGIC); 4353 return (arena_salloc(ptr)); 4354 } else { 4355 size_t ret; 4356 extent_node_t *node; 4357 extent_node_t key; 4358 4359 /* Chunk. */ 4360 key.addr = (void *)chunk; 4361 malloc_mutex_lock(&huge_mtx); 4362 node = extent_tree_ad_search(&huge, &key); 4363 if (node != NULL) 4364 ret = node->size; 4365 else 4366 ret = 0; 4367 malloc_mutex_unlock(&huge_mtx); 4368 return (ret); 4369 } 4370 } 4371 #endif 4372 4373 static inline size_t 4374 isalloc(const void *ptr) 4375 { 4376 size_t ret; 4377 arena_chunk_t *chunk; 4378 4379 assert(ptr != NULL); 4380 4381 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 4382 if (chunk != ptr) { 4383 /* Region. */ 4384 assert(chunk->arena->magic == ARENA_MAGIC); 4385 4386 ret = arena_salloc(ptr); 4387 } else { 4388 extent_node_t *node, key; 4389 4390 /* Chunk (huge allocation). */ 4391 4392 malloc_mutex_lock(&huge_mtx); 4393 4394 /* Extract from tree of huge allocations. */ 4395 key.addr = __DECONST(void *, ptr); 4396 node = extent_tree_ad_search(&huge, &key); 4397 assert(node != NULL); 4398 4399 ret = node->size; 4400 4401 malloc_mutex_unlock(&huge_mtx); 4402 } 4403 4404 return (ret); 4405 } 4406 4407 static inline void 4408 arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr, 4409 arena_chunk_map_t *mapelm) 4410 { 4411 arena_run_t *run; 4412 arena_bin_t *bin; 4413 size_t size; 4414 4415 run = (arena_run_t *)(mapelm->bits & ~pagesize_mask); 4416 assert(run->magic == ARENA_RUN_MAGIC); 4417 bin = run->bin; 4418 size = bin->reg_size; 4419 4420 #ifdef MALLOC_FILL 4421 if (opt_junk) 4422 memset(ptr, 0x5a, size); 4423 #endif 4424 4425 arena_run_reg_dalloc(run, bin, ptr, size); 4426 run->nfree++; 4427 4428 if (run->nfree == bin->nregs) { 4429 /* Deallocate run. */ 4430 if (run == bin->runcur) 4431 bin->runcur = NULL; 4432 else if (bin->nregs != 1) { 4433 size_t run_pageind = (((uintptr_t)run - 4434 (uintptr_t)chunk)) >> pagesize_2pow; 4435 arena_chunk_map_t *run_mapelm = 4436 &chunk->map[run_pageind]; 4437 /* 4438 * This block's conditional is necessary because if the 4439 * run only contains one region, then it never gets 4440 * inserted into the non-full runs tree. 4441 */ 4442 assert(arena_run_tree_search(&bin->runs, run_mapelm) == 4443 run_mapelm); 4444 arena_run_tree_remove(&bin->runs, run_mapelm); 4445 } 4446 #ifdef MALLOC_DEBUG 4447 run->magic = 0; 4448 #endif 4449 VALGRIND_FREELIKE_BLOCK(run, 0); 4450 arena_run_dalloc(arena, run, true); 4451 #ifdef MALLOC_STATS 4452 bin->stats.curruns--; 4453 #endif 4454 } else if (run->nfree == 1 && run != bin->runcur) { 4455 /* 4456 * Make sure that bin->runcur always refers to the lowest 4457 * non-full run, if one exists. 4458 */ 4459 if (bin->runcur == NULL) 4460 bin->runcur = run; 4461 else if ((uintptr_t)run < (uintptr_t)bin->runcur) { 4462 /* Switch runcur. */ 4463 if (bin->runcur->nfree > 0) { 4464 arena_chunk_t *runcur_chunk = 4465 (arena_chunk_t*)CHUNK_ADDR2BASE(bin->runcur); 4466 size_t runcur_pageind = 4467 (((uintptr_t)bin->runcur - 4468 (uintptr_t)runcur_chunk)) >> pagesize_2pow; 4469 arena_chunk_map_t *runcur_mapelm = 4470 &runcur_chunk->map[runcur_pageind]; 4471 4472 /* Insert runcur. */ 4473 assert(arena_run_tree_search(&bin->runs, 4474 runcur_mapelm) == NULL); 4475 arena_run_tree_insert(&bin->runs, 4476 runcur_mapelm); 4477 } 4478 bin->runcur = run; 4479 } else { 4480 size_t run_pageind = (((uintptr_t)run - 4481 (uintptr_t)chunk)) >> pagesize_2pow; 4482 arena_chunk_map_t *run_mapelm = 4483 &chunk->map[run_pageind]; 4484 4485 assert(arena_run_tree_search(&bin->runs, run_mapelm) == 4486 NULL); 4487 arena_run_tree_insert(&bin->runs, run_mapelm); 4488 } 4489 } 4490 #ifdef MALLOC_STATS 4491 arena->stats.allocated_small -= size; 4492 arena->stats.ndalloc_small++; 4493 #endif 4494 } 4495 4496 static void 4497 arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr) 4498 { 4499 /* Large allocation. */ 4500 malloc_spin_lock(&arena->lock); 4501 4502 #ifdef MALLOC_FILL 4503 #ifndef MALLOC_STATS 4504 if (opt_junk) 4505 #endif 4506 #endif 4507 { 4508 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> 4509 pagesize_2pow; 4510 size_t size = chunk->map[pageind].bits & ~pagesize_mask; 4511 4512 #ifdef MALLOC_FILL 4513 #ifdef MALLOC_STATS 4514 if (opt_junk) 4515 #endif 4516 memset(ptr, 0x5a, size); 4517 #endif 4518 #ifdef MALLOC_STATS 4519 arena->stats.allocated_large -= size; 4520 #endif 4521 } 4522 #ifdef MALLOC_STATS 4523 arena->stats.ndalloc_large++; 4524 #endif 4525 4526 arena_run_dalloc(arena, (arena_run_t *)ptr, true); 4527 malloc_spin_unlock(&arena->lock); 4528 } 4529 4530 static inline void 4531 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr) 4532 { 4533 size_t pageind; 4534 arena_chunk_map_t *mapelm; 4535 4536 assert(arena != NULL); 4537 assert(arena->magic == ARENA_MAGIC); 4538 assert(chunk->arena == arena); 4539 assert(ptr != NULL); 4540 assert(CHUNK_ADDR2BASE(ptr) != ptr); 4541 4542 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow); 4543 mapelm = &chunk->map[pageind]; 4544 assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0); 4545 if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) { 4546 /* Small allocation. */ 4547 malloc_spin_lock(&arena->lock); 4548 arena_dalloc_small(arena, chunk, ptr, mapelm); 4549 malloc_spin_unlock(&arena->lock); 4550 } else 4551 arena_dalloc_large(arena, chunk, ptr); 4552 VALGRIND_FREELIKE_BLOCK(ptr, 0); 4553 } 4554 4555 static inline void 4556 idalloc(void *ptr) 4557 { 4558 arena_chunk_t *chunk; 4559 4560 assert(ptr != NULL); 4561 4562 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 4563 if (chunk != ptr) 4564 arena_dalloc(chunk->arena, chunk, ptr); 4565 else 4566 huge_dalloc(ptr); 4567 } 4568 4569 static void 4570 arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr, 4571 size_t size, size_t oldsize) 4572 { 4573 4574 assert(size < oldsize); 4575 4576 /* 4577 * Shrink the run, and make trailing pages available for other 4578 * allocations. 4579 */ 4580 #ifdef MALLOC_BALANCE 4581 arena_lock_balance(arena); 4582 #else 4583 malloc_spin_lock(&arena->lock); 4584 #endif 4585 arena_run_trim_tail(arena, chunk, (arena_run_t *)ptr, oldsize, size, 4586 true); 4587 #ifdef MALLOC_STATS 4588 arena->stats.allocated_large -= oldsize - size; 4589 #endif 4590 malloc_spin_unlock(&arena->lock); 4591 } 4592 4593 static bool 4594 arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr, 4595 size_t size, size_t oldsize) 4596 { 4597 size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow; 4598 size_t npages = oldsize >> pagesize_2pow; 4599 4600 assert(oldsize == (chunk->map[pageind].bits & ~pagesize_mask)); 4601 4602 /* Try to extend the run. */ 4603 assert(size > oldsize); 4604 #ifdef MALLOC_BALANCE 4605 arena_lock_balance(arena); 4606 #else 4607 malloc_spin_lock(&arena->lock); 4608 #endif 4609 if (pageind + npages < chunk_npages && (chunk->map[pageind+npages].bits 4610 & CHUNK_MAP_ALLOCATED) == 0 && (chunk->map[pageind+npages].bits & 4611 ~pagesize_mask) >= size - oldsize) { 4612 /* 4613 * The next run is available and sufficiently large. Split the 4614 * following run, then merge the first part with the existing 4615 * allocation. 4616 */ 4617 arena_run_split(arena, (arena_run_t *)((uintptr_t)chunk + 4618 ((pageind+npages) << pagesize_2pow)), size - oldsize, true, 4619 false); 4620 4621 chunk->map[pageind].bits = size | CHUNK_MAP_LARGE | 4622 CHUNK_MAP_ALLOCATED; 4623 chunk->map[pageind+npages].bits = CHUNK_MAP_LARGE | 4624 CHUNK_MAP_ALLOCATED; 4625 4626 #ifdef MALLOC_STATS 4627 arena->stats.allocated_large += size - oldsize; 4628 #endif 4629 malloc_spin_unlock(&arena->lock); 4630 return (false); 4631 } 4632 malloc_spin_unlock(&arena->lock); 4633 4634 return (true); 4635 } 4636 4637 /* 4638 * Try to resize a large allocation, in order to avoid copying. This will 4639 * always fail if growing an object, and the following run is already in use. 4640 */ 4641 static bool 4642 arena_ralloc_large(void *ptr, size_t size, size_t oldsize) 4643 { 4644 size_t psize; 4645 4646 psize = PAGE_CEILING(size); 4647 if (psize == oldsize) { 4648 /* Same size class. */ 4649 #ifdef MALLOC_FILL 4650 if (opt_junk && size < oldsize) { 4651 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - 4652 size); 4653 } 4654 #endif 4655 return (false); 4656 } else { 4657 arena_chunk_t *chunk; 4658 arena_t *arena; 4659 4660 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 4661 arena = chunk->arena; 4662 assert(arena->magic == ARENA_MAGIC); 4663 4664 if (psize < oldsize) { 4665 #ifdef MALLOC_FILL 4666 /* Fill before shrinking in order avoid a race. */ 4667 if (opt_junk) { 4668 memset((void *)((uintptr_t)ptr + size), 0x5a, 4669 oldsize - size); 4670 } 4671 #endif 4672 arena_ralloc_large_shrink(arena, chunk, ptr, psize, 4673 oldsize); 4674 return (false); 4675 } else { 4676 bool ret = arena_ralloc_large_grow(arena, chunk, ptr, 4677 psize, oldsize); 4678 #ifdef MALLOC_FILL 4679 if (ret == false && opt_zero) { 4680 memset((void *)((uintptr_t)ptr + oldsize), 0, 4681 size - oldsize); 4682 } 4683 #endif 4684 return (ret); 4685 } 4686 } 4687 } 4688 4689 static void * 4690 arena_ralloc(void *ptr, size_t size, size_t oldsize) 4691 { 4692 void *ret; 4693 size_t copysize; 4694 4695 /* Try to avoid moving the allocation. */ 4696 if (size < small_min) { 4697 if (oldsize < small_min && 4698 ffs((int)(pow2_ceil(size) >> (TINY_MIN_2POW + 1))) 4699 == ffs((int)(pow2_ceil(oldsize) >> (TINY_MIN_2POW + 1)))) 4700 goto IN_PLACE; /* Same size class. */ 4701 } else if (size <= small_max) { 4702 if (oldsize >= small_min && oldsize <= small_max && 4703 (QUANTUM_CEILING(size) >> opt_quantum_2pow) 4704 == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow)) 4705 goto IN_PLACE; /* Same size class. */ 4706 } else if (size <= bin_maxclass) { 4707 if (oldsize > small_max && oldsize <= bin_maxclass && 4708 pow2_ceil(size) == pow2_ceil(oldsize)) 4709 goto IN_PLACE; /* Same size class. */ 4710 } else if (oldsize > bin_maxclass && oldsize <= arena_maxclass) { 4711 assert(size > bin_maxclass); 4712 if (arena_ralloc_large(ptr, size, oldsize) == false) 4713 return (ptr); 4714 } 4715 4716 /* 4717 * If we get here, then size and oldsize are different enough that we 4718 * need to move the object. In that case, fall back to allocating new 4719 * space and copying. 4720 */ 4721 ret = arena_malloc(choose_arena(), size, false); 4722 if (ret == NULL) 4723 return (NULL); 4724 4725 /* Junk/zero-filling were already done by arena_malloc(). */ 4726 copysize = (size < oldsize) ? size : oldsize; 4727 #ifdef VM_COPY_MIN 4728 if (copysize >= VM_COPY_MIN) 4729 pages_copy(ret, ptr, copysize); 4730 else 4731 #endif 4732 memcpy(ret, ptr, copysize); 4733 idalloc(ptr); 4734 return (ret); 4735 IN_PLACE: 4736 #ifdef MALLOC_FILL 4737 if (opt_junk && size < oldsize) 4738 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size); 4739 else if (opt_zero && size > oldsize) 4740 memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize); 4741 #endif 4742 return (ptr); 4743 } 4744 4745 static inline void * 4746 iralloc(void *ptr, size_t size) 4747 { 4748 size_t oldsize; 4749 4750 assert(ptr != NULL); 4751 assert(size != 0); 4752 4753 oldsize = isalloc(ptr); 4754 4755 #ifndef MALLOC_VALGRIND 4756 if (size <= arena_maxclass) 4757 return (arena_ralloc(ptr, size, oldsize)); 4758 else 4759 return (huge_ralloc(ptr, size, oldsize)); 4760 #else 4761 /* 4762 * Valgrind does not provide a public interface for modifying an 4763 * existing allocation, so use malloc/memcpy/free instead. 4764 */ 4765 { 4766 void *ret = imalloc(size); 4767 if (ret != NULL) { 4768 if (oldsize < size) 4769 memcpy(ret, ptr, oldsize); 4770 else 4771 memcpy(ret, ptr, size); 4772 idalloc(ptr); 4773 } 4774 return (ret); 4775 } 4776 #endif 4777 } 4778 4779 static bool 4780 arena_new(arena_t *arena) 4781 { 4782 unsigned i; 4783 arena_bin_t *bin; 4784 size_t pow2_size, prev_run_size; 4785 4786 if (malloc_spin_init(&arena->lock)) 4787 return (true); 4788 4789 #ifdef MALLOC_STATS 4790 memset(&arena->stats, 0, sizeof(arena_stats_t)); 4791 #endif 4792 4793 arena->chunk_seq = 0; 4794 4795 /* Initialize chunks. */ 4796 arena_chunk_tree_dirty_new(&arena->chunks_dirty); 4797 arena->spare = NULL; 4798 4799 arena->ndirty = 0; 4800 4801 arena_avail_tree_new(&arena->runs_avail); 4802 4803 #ifdef MALLOC_BALANCE 4804 arena->contention = 0; 4805 #endif 4806 4807 /* Initialize bins. */ 4808 prev_run_size = pagesize; 4809 4810 /* (2^n)-spaced tiny bins. */ 4811 for (i = 0; i < ntbins; i++) { 4812 bin = &arena->bins[i]; 4813 bin->runcur = NULL; 4814 arena_run_tree_new(&bin->runs); 4815 4816 bin->reg_size = (1U << (TINY_MIN_2POW + i)); 4817 4818 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 4819 4820 #ifdef MALLOC_STATS 4821 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 4822 #endif 4823 } 4824 4825 /* Quantum-spaced bins. */ 4826 for (; i < ntbins + nqbins; i++) { 4827 bin = &arena->bins[i]; 4828 bin->runcur = NULL; 4829 arena_run_tree_new(&bin->runs); 4830 4831 bin->reg_size = quantum * (i - ntbins + 1); 4832 4833 pow2_size = pow2_ceil(quantum * (i - ntbins + 1)); 4834 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 4835 4836 #ifdef MALLOC_STATS 4837 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 4838 #endif 4839 } 4840 4841 /* (2^n)-spaced sub-page bins. */ 4842 for (; i < ntbins + nqbins + nsbins; i++) { 4843 bin = &arena->bins[i]; 4844 bin->runcur = NULL; 4845 arena_run_tree_new(&bin->runs); 4846 4847 bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1)); 4848 4849 prev_run_size = arena_bin_run_size_calc(bin, prev_run_size); 4850 4851 #ifdef MALLOC_STATS 4852 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t)); 4853 #endif 4854 } 4855 4856 #ifdef MALLOC_DEBUG 4857 arena->magic = ARENA_MAGIC; 4858 #endif 4859 4860 return (false); 4861 } 4862 4863 /* Create a new arena and insert it into the arenas array at index ind. */ 4864 static arena_t * 4865 arenas_extend(unsigned ind) 4866 { 4867 arena_t *ret; 4868 4869 /* Allocate enough space for trailing bins. */ 4870 ret = (arena_t *)base_alloc(sizeof(arena_t) 4871 + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1))); 4872 if (ret != NULL && arena_new(ret) == false) { 4873 arenas[ind] = ret; 4874 return (ret); 4875 } 4876 /* Only reached if there is an OOM error. */ 4877 4878 /* 4879 * OOM here is quite inconvenient to propagate, since dealing with it 4880 * would require a check for failure in the fast path. Instead, punt 4881 * by using arenas[0]. In practice, this is an extremely unlikely 4882 * failure. 4883 */ 4884 _malloc_message(_getprogname(), 4885 ": (malloc) Error initializing arena\n", "", ""); 4886 if (opt_abort) 4887 abort(); 4888 4889 return (arenas[0]); 4890 } 4891 4892 /* 4893 * End arena. 4894 */ 4895 /******************************************************************************/ 4896 /* 4897 * Begin general internal functions. 4898 */ 4899 4900 static void * 4901 huge_malloc(size_t size, bool zero) 4902 { 4903 void *ret; 4904 size_t csize; 4905 #ifdef MALLOC_DECOMMIT 4906 size_t psize; 4907 #endif 4908 extent_node_t *node; 4909 4910 /* Allocate one or more contiguous chunks for this request. */ 4911 4912 csize = CHUNK_CEILING(size); 4913 if (csize == 0) { 4914 /* size is large enough to cause size_t wrap-around. */ 4915 return (NULL); 4916 } 4917 4918 /* Allocate an extent node with which to track the chunk. */ 4919 node = base_node_alloc(); 4920 if (node == NULL) 4921 return (NULL); 4922 4923 ret = chunk_alloc(csize, zero, true); 4924 if (ret == NULL) { 4925 base_node_dealloc(node); 4926 return (NULL); 4927 } 4928 4929 /* Insert node into huge. */ 4930 node->addr = ret; 4931 #ifdef MALLOC_DECOMMIT 4932 psize = PAGE_CEILING(size); 4933 node->size = psize; 4934 #else 4935 node->size = csize; 4936 #endif 4937 4938 malloc_mutex_lock(&huge_mtx); 4939 extent_tree_ad_insert(&huge, node); 4940 #ifdef MALLOC_STATS 4941 huge_nmalloc++; 4942 # ifdef MALLOC_DECOMMIT 4943 huge_allocated += psize; 4944 # else 4945 huge_allocated += csize; 4946 # endif 4947 #endif 4948 malloc_mutex_unlock(&huge_mtx); 4949 4950 #ifdef MALLOC_DECOMMIT 4951 if (csize - psize > 0) 4952 pages_decommit((void *)((uintptr_t)ret + psize), csize - psize); 4953 #endif 4954 4955 #ifdef MALLOC_DECOMMIT 4956 VALGRIND_MALLOCLIKE_BLOCK(ret, psize, 0, zero); 4957 #else 4958 VALGRIND_MALLOCLIKE_BLOCK(ret, csize, 0, zero); 4959 #endif 4960 4961 #ifdef MALLOC_FILL 4962 if (zero == false) { 4963 if (opt_junk) 4964 # ifdef MALLOC_DECOMMIT 4965 memset(ret, 0xa5, psize); 4966 # else 4967 memset(ret, 0xa5, csize); 4968 # endif 4969 else if (opt_zero) 4970 # ifdef MALLOC_DECOMMIT 4971 memset(ret, 0, psize); 4972 # else 4973 memset(ret, 0, csize); 4974 # endif 4975 } 4976 #endif 4977 4978 return (ret); 4979 } 4980 4981 /* Only handles large allocations that require more than chunk alignment. */ 4982 static void * 4983 huge_palloc(size_t alignment, size_t size) 4984 { 4985 void *ret; 4986 size_t alloc_size, chunk_size, offset; 4987 #ifdef MALLOC_DECOMMIT 4988 size_t psize; 4989 #endif 4990 extent_node_t *node; 4991 int pfd; 4992 4993 /* 4994 * This allocation requires alignment that is even larger than chunk 4995 * alignment. This means that huge_malloc() isn't good enough. 4996 * 4997 * Allocate almost twice as many chunks as are demanded by the size or 4998 * alignment, in order to assure the alignment can be achieved, then 4999 * unmap leading and trailing chunks. 5000 */ 5001 assert(alignment >= chunksize); 5002 5003 chunk_size = CHUNK_CEILING(size); 5004 5005 if (size >= alignment) 5006 alloc_size = chunk_size + alignment - chunksize; 5007 else 5008 alloc_size = (alignment << 1) - chunksize; 5009 5010 /* Allocate an extent node with which to track the chunk. */ 5011 node = base_node_alloc(); 5012 if (node == NULL) 5013 return (NULL); 5014 5015 /* 5016 * Windows requires that there be a 1:1 mapping between VM 5017 * allocation/deallocation operations. Therefore, take care here to 5018 * acquire the final result via one mapping operation. 5019 * 5020 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm, 5021 * since it reduces the number of page files. 5022 */ 5023 #ifdef MALLOC_PAGEFILE 5024 if (opt_pagefile) { 5025 pfd = pagefile_init(size); 5026 if (pfd == -1) 5027 return (NULL); 5028 } else 5029 #endif 5030 pfd = -1; 5031 #ifdef JEMALLOC_USES_MAP_ALIGN 5032 ret = pages_map_align(chunk_size, pfd, alignment); 5033 #else 5034 do { 5035 void *over; 5036 5037 over = chunk_alloc(alloc_size, false, false); 5038 if (over == NULL) { 5039 base_node_dealloc(node); 5040 ret = NULL; 5041 goto RETURN; 5042 } 5043 5044 offset = (uintptr_t)over & (alignment - 1); 5045 assert((offset & chunksize_mask) == 0); 5046 assert(offset < alloc_size); 5047 ret = (void *)((uintptr_t)over + offset); 5048 chunk_dealloc(over, alloc_size); 5049 ret = pages_map(ret, chunk_size, pfd); 5050 /* 5051 * Failure here indicates a race with another thread, so try 5052 * again. 5053 */ 5054 } while (ret == NULL); 5055 #endif 5056 /* Insert node into huge. */ 5057 node->addr = ret; 5058 #ifdef MALLOC_DECOMMIT 5059 psize = PAGE_CEILING(size); 5060 node->size = psize; 5061 #else 5062 node->size = chunk_size; 5063 #endif 5064 5065 malloc_mutex_lock(&huge_mtx); 5066 extent_tree_ad_insert(&huge, node); 5067 #ifdef MALLOC_STATS 5068 huge_nmalloc++; 5069 # ifdef MALLOC_DECOMMIT 5070 huge_allocated += psize; 5071 # else 5072 huge_allocated += chunk_size; 5073 # endif 5074 #endif 5075 malloc_mutex_unlock(&huge_mtx); 5076 5077 #ifdef MALLOC_DECOMMIT 5078 if (chunk_size - psize > 0) { 5079 pages_decommit((void *)((uintptr_t)ret + psize), 5080 chunk_size - psize); 5081 } 5082 #endif 5083 5084 #ifdef MALLOC_DECOMMIT 5085 VALGRIND_MALLOCLIKE_BLOCK(ret, psize, 0, false); 5086 #else 5087 VALGRIND_MALLOCLIKE_BLOCK(ret, chunk_size, 0, false); 5088 #endif 5089 5090 #ifdef MALLOC_FILL 5091 if (opt_junk) 5092 # ifdef MALLOC_DECOMMIT 5093 memset(ret, 0xa5, psize); 5094 # else 5095 memset(ret, 0xa5, chunk_size); 5096 # endif 5097 else if (opt_zero) 5098 # ifdef MALLOC_DECOMMIT 5099 memset(ret, 0, psize); 5100 # else 5101 memset(ret, 0, chunk_size); 5102 # endif 5103 #endif 5104 5105 RETURN: 5106 #ifdef MALLOC_PAGEFILE 5107 if (pfd != -1) 5108 pagefile_close(pfd); 5109 #endif 5110 return (ret); 5111 } 5112 5113 static void * 5114 huge_ralloc(void *ptr, size_t size, size_t oldsize) 5115 { 5116 void *ret; 5117 size_t copysize; 5118 5119 /* Avoid moving the allocation if the size class would not change. */ 5120 5121 if (oldsize > arena_maxclass && 5122 CHUNK_CEILING(size) == CHUNK_CEILING(oldsize)) { 5123 #ifdef MALLOC_DECOMMIT 5124 size_t psize = PAGE_CEILING(size); 5125 #endif 5126 #ifdef MALLOC_FILL 5127 if (opt_junk && size < oldsize) { 5128 memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize 5129 - size); 5130 } 5131 #endif 5132 #ifdef MALLOC_DECOMMIT 5133 if (psize < oldsize) { 5134 extent_node_t *node, key; 5135 5136 pages_decommit((void *)((uintptr_t)ptr + psize), 5137 oldsize - psize); 5138 5139 /* Update recorded size. */ 5140 malloc_mutex_lock(&huge_mtx); 5141 key.addr = __DECONST(void *, ptr); 5142 node = extent_tree_ad_search(&huge, &key); 5143 assert(node != NULL); 5144 assert(node->size == oldsize); 5145 # ifdef MALLOC_STATS 5146 huge_allocated -= oldsize - psize; 5147 # endif 5148 node->size = psize; 5149 malloc_mutex_unlock(&huge_mtx); 5150 } else if (psize > oldsize) { 5151 extent_node_t *node, key; 5152 5153 pages_commit((void *)((uintptr_t)ptr + oldsize), 5154 psize - oldsize); 5155 5156 /* Update recorded size. */ 5157 malloc_mutex_lock(&huge_mtx); 5158 key.addr = __DECONST(void *, ptr); 5159 node = extent_tree_ad_search(&huge, &key); 5160 assert(node != NULL); 5161 assert(node->size == oldsize); 5162 # ifdef MALLOC_STATS 5163 huge_allocated += psize - oldsize; 5164 # endif 5165 node->size = psize; 5166 malloc_mutex_unlock(&huge_mtx); 5167 } 5168 #endif 5169 #ifdef MALLOC_FILL 5170 if (opt_zero && size > oldsize) { 5171 memset((void *)((uintptr_t)ptr + oldsize), 0, size 5172 - oldsize); 5173 } 5174 #endif 5175 return (ptr); 5176 } 5177 5178 /* 5179 * If we get here, then size and oldsize are different enough that we 5180 * need to use a different size class. In that case, fall back to 5181 * allocating new space and copying. 5182 */ 5183 ret = huge_malloc(size, false); 5184 if (ret == NULL) 5185 return (NULL); 5186 5187 copysize = (size < oldsize) ? size : oldsize; 5188 #ifdef VM_COPY_MIN 5189 if (copysize >= VM_COPY_MIN) 5190 pages_copy(ret, ptr, copysize); 5191 else 5192 #endif 5193 memcpy(ret, ptr, copysize); 5194 idalloc(ptr); 5195 return (ret); 5196 } 5197 5198 static void 5199 huge_dalloc(void *ptr) 5200 { 5201 extent_node_t *node, key; 5202 5203 malloc_mutex_lock(&huge_mtx); 5204 5205 /* Extract from tree of huge allocations. */ 5206 key.addr = ptr; 5207 node = extent_tree_ad_search(&huge, &key); 5208 assert(node != NULL); 5209 assert(node->addr == ptr); 5210 extent_tree_ad_remove(&huge, node); 5211 5212 #ifdef MALLOC_STATS 5213 huge_ndalloc++; 5214 huge_allocated -= node->size; 5215 #endif 5216 5217 malloc_mutex_unlock(&huge_mtx); 5218 5219 /* Unmap chunk. */ 5220 #ifdef MALLOC_FILL 5221 if (opt_junk) 5222 memset(node->addr, 0x5a, node->size); 5223 #endif 5224 #ifdef MALLOC_DECOMMIT 5225 chunk_dealloc(node->addr, CHUNK_CEILING(node->size)); 5226 #else 5227 chunk_dealloc(node->addr, node->size); 5228 #endif 5229 VALGRIND_FREELIKE_BLOCK(node->addr, 0); 5230 5231 base_node_dealloc(node); 5232 } 5233 5234 #ifdef MOZ_MEMORY_BSD 5235 static inline unsigned 5236 malloc_ncpus(void) 5237 { 5238 unsigned ret; 5239 int mib[2]; 5240 size_t len; 5241 5242 mib[0] = CTL_HW; 5243 mib[1] = HW_NCPU; 5244 len = sizeof(ret); 5245 if (sysctl(mib, 2, &ret, &len, (void *) 0, 0) == -1) { 5246 /* Error. */ 5247 return (1); 5248 } 5249 5250 return (ret); 5251 } 5252 #elif (defined(MOZ_MEMORY_LINUX)) 5253 #include <fcntl.h> 5254 5255 static inline unsigned 5256 malloc_ncpus(void) 5257 { 5258 unsigned ret; 5259 int fd, nread, column; 5260 char buf[1024]; 5261 static const char matchstr[] = "processor\t:"; 5262 int i; 5263 5264 /* 5265 * sysconf(3) would be the preferred method for determining the number 5266 * of CPUs, but it uses malloc internally, which causes untennable 5267 * recursion during malloc initialization. 5268 */ 5269 fd = open("/proc/cpuinfo", O_RDONLY); 5270 if (fd == -1) 5271 return (1); /* Error. */ 5272 /* 5273 * Count the number of occurrences of matchstr at the beginnings of 5274 * lines. This treats hyperthreaded CPUs as multiple processors. 5275 */ 5276 column = 0; 5277 ret = 0; 5278 while (true) { 5279 nread = read(fd, &buf, sizeof(buf)); 5280 if (nread <= 0) 5281 break; /* EOF or error. */ 5282 for (i = 0;i < nread;i++) { 5283 char c = buf[i]; 5284 if (c == '\n') 5285 column = 0; 5286 else if (column != -1) { 5287 if (c == matchstr[column]) { 5288 column++; 5289 if (column == sizeof(matchstr) - 1) { 5290 column = -1; 5291 ret++; 5292 } 5293 } else 5294 column = -1; 5295 } 5296 } 5297 } 5298 5299 if (ret == 0) 5300 ret = 1; /* Something went wrong in the parser. */ 5301 close(fd); 5302 5303 return (ret); 5304 } 5305 #elif (defined(MOZ_MEMORY_DARWIN)) 5306 #include <mach/mach_init.h> 5307 #include <mach/mach_host.h> 5308 5309 static inline unsigned 5310 malloc_ncpus(void) 5311 { 5312 kern_return_t error; 5313 natural_t n; 5314 processor_info_array_t pinfo; 5315 mach_msg_type_number_t pinfocnt; 5316 5317 error = host_processor_info(mach_host_self(), PROCESSOR_BASIC_INFO, 5318 &n, &pinfo, &pinfocnt); 5319 if (error != KERN_SUCCESS) 5320 return (1); /* Error. */ 5321 else 5322 return (n); 5323 } 5324 #elif (defined(MOZ_MEMORY_SOLARIS)) 5325 5326 static inline unsigned 5327 malloc_ncpus(void) 5328 { 5329 return sysconf(_SC_NPROCESSORS_ONLN); 5330 } 5331 #else 5332 static inline unsigned 5333 malloc_ncpus(void) 5334 { 5335 5336 /* 5337 * We lack a way to determine the number of CPUs on this platform, so 5338 * assume 1 CPU. 5339 */ 5340 return (1); 5341 } 5342 #endif 5343 5344 static void 5345 malloc_print_stats(void) 5346 { 5347 5348 if (opt_print_stats) { 5349 char s[UMAX2S_BUFSIZE]; 5350 _malloc_message("___ Begin malloc statistics ___\n", "", "", 5351 ""); 5352 _malloc_message("Assertions ", 5353 #ifdef NDEBUG 5354 "disabled", 5355 #else 5356 "enabled", 5357 #endif 5358 "\n", ""); 5359 _malloc_message("Boolean MALLOC_OPTIONS: ", 5360 opt_abort ? "A" : "a", "", ""); 5361 #ifdef MALLOC_FILL 5362 _malloc_message(opt_junk ? "J" : "j", "", "", ""); 5363 #endif 5364 #ifdef MALLOC_PAGEFILE 5365 _malloc_message(opt_pagefile ? "o" : "O", "", "", ""); 5366 #endif 5367 _malloc_message("P", "", "", ""); 5368 #ifdef MALLOC_UTRACE 5369 _malloc_message(opt_utrace ? "U" : "u", "", "", ""); 5370 #endif 5371 #ifdef MALLOC_SYSV 5372 _malloc_message(opt_sysv ? "V" : "v", "", "", ""); 5373 #endif 5374 #ifdef MALLOC_XMALLOC 5375 _malloc_message(opt_xmalloc ? "X" : "x", "", "", ""); 5376 #endif 5377 #ifdef MALLOC_FILL 5378 _malloc_message(opt_zero ? "Z" : "z", "", "", ""); 5379 #endif 5380 _malloc_message("\n", "", "", ""); 5381 5382 _malloc_message("CPUs: ", umax2s(ncpus, s), "\n", ""); 5383 _malloc_message("Max arenas: ", umax2s(narenas, s), "\n", ""); 5384 #ifdef MALLOC_BALANCE 5385 _malloc_message("Arena balance threshold: ", 5386 umax2s(opt_balance_threshold, s), "\n", ""); 5387 #endif 5388 _malloc_message("Pointer size: ", umax2s(sizeof(void *), s), 5389 "\n", ""); 5390 _malloc_message("Quantum size: ", umax2s(quantum, s), "\n", ""); 5391 _malloc_message("Max small size: ", umax2s(small_max, s), "\n", 5392 ""); 5393 _malloc_message("Max dirty pages per arena: ", 5394 umax2s(opt_dirty_max, s), "\n", ""); 5395 5396 _malloc_message("Chunk size: ", umax2s(chunksize, s), "", ""); 5397 _malloc_message(" (2^", umax2s(opt_chunk_2pow, s), ")\n", ""); 5398 5399 #ifdef MALLOC_STATS 5400 { 5401 size_t allocated, mapped; 5402 #ifdef MALLOC_BALANCE 5403 uint64_t nbalance = 0; 5404 #endif 5405 unsigned i; 5406 arena_t *arena; 5407 5408 /* Calculate and print allocated/mapped stats. */ 5409 5410 /* arenas. */ 5411 for (i = 0, allocated = 0; i < narenas; i++) { 5412 if (arenas[i] != NULL) { 5413 malloc_spin_lock(&arenas[i]->lock); 5414 allocated += 5415 arenas[i]->stats.allocated_small; 5416 allocated += 5417 arenas[i]->stats.allocated_large; 5418 #ifdef MALLOC_BALANCE 5419 nbalance += arenas[i]->stats.nbalance; 5420 #endif 5421 malloc_spin_unlock(&arenas[i]->lock); 5422 } 5423 } 5424 5425 /* huge/base. */ 5426 malloc_mutex_lock(&huge_mtx); 5427 allocated += huge_allocated; 5428 mapped = stats_chunks.curchunks * chunksize; 5429 malloc_mutex_unlock(&huge_mtx); 5430 5431 malloc_mutex_lock(&base_mtx); 5432 mapped += base_mapped; 5433 malloc_mutex_unlock(&base_mtx); 5434 5435 #ifdef MOZ_MEMORY_WINDOWS 5436 malloc_printf("Allocated: %lu, mapped: %lu\n", 5437 allocated, mapped); 5438 #else 5439 malloc_printf("Allocated: %zu, mapped: %zu\n", 5440 allocated, mapped); 5441 #endif 5442 5443 malloc_mutex_lock(&reserve_mtx); 5444 malloc_printf("Reserve: min " 5445 "cur max\n"); 5446 #ifdef MOZ_MEMORY_WINDOWS 5447 malloc_printf(" %12lu %12lu %12lu\n", 5448 CHUNK_CEILING(reserve_min) >> opt_chunk_2pow, 5449 reserve_cur >> opt_chunk_2pow, 5450 reserve_max >> opt_chunk_2pow); 5451 #else 5452 malloc_printf(" %12zu %12zu %12zu\n", 5453 CHUNK_CEILING(reserve_min) >> opt_chunk_2pow, 5454 reserve_cur >> opt_chunk_2pow, 5455 reserve_max >> opt_chunk_2pow); 5456 #endif 5457 malloc_mutex_unlock(&reserve_mtx); 5458 5459 #ifdef MALLOC_BALANCE 5460 malloc_printf("Arena balance reassignments: %llu\n", 5461 nbalance); 5462 #endif 5463 5464 /* Print chunk stats. */ 5465 { 5466 chunk_stats_t chunks_stats; 5467 5468 malloc_mutex_lock(&huge_mtx); 5469 chunks_stats = stats_chunks; 5470 malloc_mutex_unlock(&huge_mtx); 5471 5472 malloc_printf("chunks: nchunks " 5473 "highchunks curchunks\n"); 5474 malloc_printf(" %13llu%13lu%13lu\n", 5475 chunks_stats.nchunks, 5476 chunks_stats.highchunks, 5477 chunks_stats.curchunks); 5478 } 5479 5480 /* Print chunk stats. */ 5481 malloc_printf( 5482 "huge: nmalloc ndalloc allocated\n"); 5483 #ifdef MOZ_MEMORY_WINDOWS 5484 malloc_printf(" %12llu %12llu %12lu\n", 5485 huge_nmalloc, huge_ndalloc, huge_allocated); 5486 #else 5487 malloc_printf(" %12llu %12llu %12zu\n", 5488 huge_nmalloc, huge_ndalloc, huge_allocated); 5489 #endif 5490 /* Print stats for each arena. */ 5491 for (i = 0; i < narenas; i++) { 5492 arena = arenas[i]; 5493 if (arena != NULL) { 5494 malloc_printf( 5495 "\narenas[%u]:\n", i); 5496 malloc_spin_lock(&arena->lock); 5497 stats_print(arena); 5498 malloc_spin_unlock(&arena->lock); 5499 } 5500 } 5501 } 5502 #endif /* #ifdef MALLOC_STATS */ 5503 _malloc_message("--- End malloc statistics ---\n", "", "", ""); 5504 } 5505 } 5506 5507 /* 5508 * FreeBSD's pthreads implementation calls malloc(3), so the malloc 5509 * implementation has to take pains to avoid infinite recursion during 5510 * initialization. 5511 */ 5512 #if (defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_DARWIN)) && !defined(MOZ_MEMORY_WINCE) 5513 #define malloc_init() false 5514 #else 5515 static inline bool 5516 malloc_init(void) 5517 { 5518 5519 if (malloc_initialized == false) 5520 return (malloc_init_hard()); 5521 5522 return (false); 5523 } 5524 #endif 5525 5526 #if !defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_WINCE) 5527 static 5528 #endif 5529 bool 5530 malloc_init_hard(void) 5531 { 5532 unsigned i; 5533 char buf[PATH_MAX + 1]; 5534 const char *opts; 5535 long result; 5536 #ifndef MOZ_MEMORY_WINDOWS 5537 int linklen; 5538 #endif 5539 5540 #ifndef MOZ_MEMORY_WINDOWS 5541 malloc_mutex_lock(&init_lock); 5542 #endif 5543 5544 if (malloc_initialized) { 5545 /* 5546 * Another thread initialized the allocator before this one 5547 * acquired init_lock. 5548 */ 5549 #ifndef MOZ_MEMORY_WINDOWS 5550 malloc_mutex_unlock(&init_lock); 5551 #endif 5552 return (false); 5553 } 5554 5555 #ifdef MOZ_MEMORY_WINDOWS 5556 /* get a thread local storage index */ 5557 tlsIndex = TlsAlloc(); 5558 #endif 5559 5560 /* Get page size and number of CPUs */ 5561 #ifdef MOZ_MEMORY_WINDOWS 5562 { 5563 SYSTEM_INFO info; 5564 5565 GetSystemInfo(&info); 5566 result = info.dwPageSize; 5567 5568 pagesize = (unsigned) result; 5569 5570 ncpus = info.dwNumberOfProcessors; 5571 } 5572 #else 5573 ncpus = malloc_ncpus(); 5574 5575 result = sysconf(_SC_PAGESIZE); 5576 assert(result != -1); 5577 5578 pagesize = (unsigned) result; 5579 #endif 5580 5581 /* 5582 * We assume that pagesize is a power of 2 when calculating 5583 * pagesize_mask and pagesize_2pow. 5584 */ 5585 assert(((result - 1) & result) == 0); 5586 pagesize_mask = result - 1; 5587 pagesize_2pow = ffs((int)result) - 1; 5588 5589 #ifdef MALLOC_PAGEFILE 5590 /* 5591 * Determine where to create page files. It is insufficient to 5592 * unconditionally use P_tmpdir (typically "/tmp"), since for some 5593 * operating systems /tmp is a separate filesystem that is rather small. 5594 * Therefore prefer, in order, the following locations: 5595 * 5596 * 1) MALLOC_TMPDIR 5597 * 2) TMPDIR 5598 * 3) P_tmpdir 5599 */ 5600 { 5601 char *s; 5602 size_t slen; 5603 static const char suffix[] = "/jemalloc.XXXXXX"; 5604 5605 if ((s = getenv("MALLOC_TMPDIR")) == NULL && (s = 5606 getenv("TMPDIR")) == NULL) 5607 s = P_tmpdir; 5608 slen = strlen(s); 5609 if (slen + sizeof(suffix) > sizeof(pagefile_templ)) { 5610 _malloc_message(_getprogname(), 5611 ": (malloc) Page file path too long\n", 5612 "", ""); 5613 abort(); 5614 } 5615 memcpy(pagefile_templ, s, slen); 5616 memcpy(&pagefile_templ[slen], suffix, sizeof(suffix)); 5617 } 5618 #endif 5619 5620 for (i = 0; i < 3; i++) { 5621 unsigned j; 5622 5623 /* Get runtime configuration. */ 5624 switch (i) { 5625 case 0: 5626 #ifndef MOZ_MEMORY_WINDOWS 5627 if ((linklen = readlink("/etc/malloc.conf", buf, 5628 sizeof(buf) - 1)) != -1) { 5629 /* 5630 * Use the contents of the "/etc/malloc.conf" 5631 * symbolic link's name. 5632 */ 5633 buf[linklen] = '\0'; 5634 opts = buf; 5635 } else 5636 #endif 5637 { 5638 /* No configuration specified. */ 5639 buf[0] = '\0'; 5640 opts = buf; 5641 } 5642 break; 5643 case 1: 5644 if (issetugid() == 0 && (opts = 5645 getenv("MALLOC_OPTIONS")) != NULL) { 5646 /* 5647 * Do nothing; opts is already initialized to 5648 * the value of the MALLOC_OPTIONS environment 5649 * variable. 5650 */ 5651 } else { 5652 /* No configuration specified. */ 5653 buf[0] = '\0'; 5654 opts = buf; 5655 } 5656 break; 5657 case 2: 5658 if (_malloc_options != NULL) { 5659 /* 5660 * Use options that were compiled into the 5661 * program. 5662 */ 5663 opts = _malloc_options; 5664 } else { 5665 /* No configuration specified. */ 5666 buf[0] = '\0'; 5667 opts = buf; 5668 } 5669 break; 5670 default: 5671 /* NOTREACHED */ 5672 buf[0] = '\0'; 5673 opts = buf; 5674 assert(false); 5675 } 5676 5677 for (j = 0; opts[j] != '\0'; j++) { 5678 unsigned k, nreps; 5679 bool nseen; 5680 5681 /* Parse repetition count, if any. */ 5682 for (nreps = 0, nseen = false;; j++, nseen = true) { 5683 switch (opts[j]) { 5684 case '0': case '1': case '2': case '3': 5685 case '4': case '5': case '6': case '7': 5686 case '8': case '9': 5687 nreps *= 10; 5688 nreps += opts[j] - '0'; 5689 break; 5690 default: 5691 goto MALLOC_OUT; 5692 } 5693 } 5694 MALLOC_OUT: 5695 if (nseen == false) 5696 nreps = 1; 5697 5698 for (k = 0; k < nreps; k++) { 5699 switch (opts[j]) { 5700 case 'a': 5701 opt_abort = false; 5702 break; 5703 case 'A': 5704 opt_abort = true; 5705 break; 5706 case 'b': 5707 #ifdef MALLOC_BALANCE 5708 opt_balance_threshold >>= 1; 5709 #endif 5710 break; 5711 case 'B': 5712 #ifdef MALLOC_BALANCE 5713 if (opt_balance_threshold == 0) 5714 opt_balance_threshold = 1; 5715 else if ((opt_balance_threshold << 1) 5716 > opt_balance_threshold) 5717 opt_balance_threshold <<= 1; 5718 #endif 5719 break; 5720 case 'f': 5721 opt_dirty_max >>= 1; 5722 break; 5723 case 'F': 5724 if (opt_dirty_max == 0) 5725 opt_dirty_max = 1; 5726 else if ((opt_dirty_max << 1) != 0) 5727 opt_dirty_max <<= 1; 5728 break; 5729 case 'g': 5730 opt_reserve_range_lshift--; 5731 break; 5732 case 'G': 5733 opt_reserve_range_lshift++; 5734 break; 5735 #ifdef MALLOC_FILL 5736 case 'j': 5737 opt_junk = false; 5738 break; 5739 case 'J': 5740 opt_junk = true; 5741 break; 5742 #endif 5743 case 'k': 5744 /* 5745 * Chunks always require at least one 5746 * header page, so chunks can never be 5747 * smaller than two pages. 5748 */ 5749 if (opt_chunk_2pow > pagesize_2pow + 1) 5750 opt_chunk_2pow--; 5751 break; 5752 case 'K': 5753 if (opt_chunk_2pow + 1 < 5754 (sizeof(size_t) << 3)) 5755 opt_chunk_2pow++; 5756 break; 5757 case 'n': 5758 opt_narenas_lshift--; 5759 break; 5760 case 'N': 5761 opt_narenas_lshift++; 5762 break; 5763 #ifdef MALLOC_PAGEFILE 5764 case 'o': 5765 /* Do not over-commit. */ 5766 opt_pagefile = true; 5767 break; 5768 case 'O': 5769 /* Allow over-commit. */ 5770 opt_pagefile = false; 5771 break; 5772 #endif 5773 case 'p': 5774 opt_print_stats = false; 5775 break; 5776 case 'P': 5777 opt_print_stats = true; 5778 break; 5779 case 'q': 5780 if (opt_quantum_2pow > QUANTUM_2POW_MIN) 5781 opt_quantum_2pow--; 5782 break; 5783 case 'Q': 5784 if (opt_quantum_2pow < pagesize_2pow - 5785 1) 5786 opt_quantum_2pow++; 5787 break; 5788 case 'r': 5789 opt_reserve_min_lshift--; 5790 break; 5791 case 'R': 5792 opt_reserve_min_lshift++; 5793 break; 5794 case 's': 5795 if (opt_small_max_2pow > 5796 QUANTUM_2POW_MIN) 5797 opt_small_max_2pow--; 5798 break; 5799 case 'S': 5800 if (opt_small_max_2pow < pagesize_2pow 5801 - 1) 5802 opt_small_max_2pow++; 5803 break; 5804 #ifdef MALLOC_UTRACE 5805 case 'u': 5806 opt_utrace = false; 5807 break; 5808 case 'U': 5809 opt_utrace = true; 5810 break; 5811 #endif 5812 #ifdef MALLOC_SYSV 5813 case 'v': 5814 opt_sysv = false; 5815 break; 5816 case 'V': 5817 opt_sysv = true; 5818 break; 5819 #endif 5820 #ifdef MALLOC_XMALLOC 5821 case 'x': 5822 opt_xmalloc = false; 5823 break; 5824 case 'X': 5825 opt_xmalloc = true; 5826 break; 5827 #endif 5828 #ifdef MALLOC_FILL 5829 case 'z': 5830 opt_zero = false; 5831 break; 5832 case 'Z': 5833 opt_zero = true; 5834 break; 5835 #endif 5836 default: { 5837 char cbuf[2]; 5838 5839 cbuf[0] = opts[j]; 5840 cbuf[1] = '\0'; 5841 _malloc_message(_getprogname(), 5842 ": (malloc) Unsupported character " 5843 "in malloc options: '", cbuf, 5844 "'\n"); 5845 } 5846 } 5847 } 5848 } 5849 } 5850 5851 /* Take care to call atexit() only once. */ 5852 if (opt_print_stats) { 5853 #ifndef MOZ_MEMORY_WINDOWS 5854 /* Print statistics at exit. */ 5855 atexit(malloc_print_stats); 5856 #endif 5857 } 5858 5859 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN)) 5860 /* Prevent potential deadlock on malloc locks after fork. */ 5861 pthread_atfork(_malloc_prefork, _malloc_postfork, _malloc_postfork); 5862 #endif 5863 5864 /* Set variables according to the value of opt_small_max_2pow. */ 5865 if (opt_small_max_2pow < opt_quantum_2pow) 5866 opt_small_max_2pow = opt_quantum_2pow; 5867 small_max = (1U << opt_small_max_2pow); 5868 5869 /* Set bin-related variables. */ 5870 bin_maxclass = (pagesize >> 1); 5871 assert(opt_quantum_2pow >= TINY_MIN_2POW); 5872 ntbins = opt_quantum_2pow - TINY_MIN_2POW; 5873 assert(ntbins <= opt_quantum_2pow); 5874 nqbins = (small_max >> opt_quantum_2pow); 5875 nsbins = pagesize_2pow - opt_small_max_2pow - 1; 5876 5877 /* Set variables according to the value of opt_quantum_2pow. */ 5878 quantum = (1U << opt_quantum_2pow); 5879 quantum_mask = quantum - 1; 5880 if (ntbins > 0) 5881 small_min = (quantum >> 1) + 1; 5882 else 5883 small_min = 1; 5884 assert(small_min <= quantum); 5885 5886 /* Set variables according to the value of opt_chunk_2pow. */ 5887 chunksize = (1LU << opt_chunk_2pow); 5888 chunksize_mask = chunksize - 1; 5889 chunk_npages = (chunksize >> pagesize_2pow); 5890 { 5891 size_t header_size; 5892 5893 /* 5894 * Compute the header size such that it is large 5895 * enough to contain the page map and enough nodes for the 5896 * worst case: one node per non-header page plus one extra for 5897 * situations where we briefly have one more node allocated 5898 * than we will need. 5899 */ 5900 header_size = sizeof(arena_chunk_t) + 5901 (sizeof(arena_chunk_map_t) * (chunk_npages - 1)); 5902 arena_chunk_header_npages = (header_size >> pagesize_2pow) + 5903 ((header_size & pagesize_mask) != 0); 5904 } 5905 arena_maxclass = chunksize - (arena_chunk_header_npages << 5906 pagesize_2pow); 5907 5908 #ifdef JEMALLOC_USES_MAP_ALIGN 5909 /* 5910 * When using MAP_ALIGN, the alignment parameter must be a power of two 5911 * multiple of the system pagesize, or mmap will fail. 5912 */ 5913 assert((chunksize % pagesize) == 0); 5914 assert((1 << (ffs(chunksize / pagesize) - 1)) == (chunksize/pagesize)); 5915 #endif 5916 5917 UTRACE(0, 0, 0); 5918 5919 #ifdef MALLOC_STATS 5920 memset(&stats_chunks, 0, sizeof(chunk_stats_t)); 5921 #endif 5922 5923 /* Various sanity checks that regard configuration. */ 5924 assert(quantum >= sizeof(void *)); 5925 assert(quantum <= pagesize); 5926 assert(chunksize >= pagesize); 5927 assert(quantum * 4 <= chunksize); 5928 5929 /* Initialize chunks data. */ 5930 malloc_mutex_init(&huge_mtx); 5931 extent_tree_ad_new(&huge); 5932 #ifdef MALLOC_STATS 5933 huge_nmalloc = 0; 5934 huge_ndalloc = 0; 5935 huge_allocated = 0; 5936 #endif 5937 5938 /* Initialize base allocation data structures. */ 5939 #ifdef MALLOC_STATS 5940 base_mapped = 0; 5941 #endif 5942 base_nodes = NULL; 5943 base_reserve_regs = NULL; 5944 malloc_mutex_init(&base_mtx); 5945 5946 #ifdef MOZ_MEMORY_NARENAS_DEFAULT_ONE 5947 narenas = 1; 5948 #else 5949 if (ncpus > 1) { 5950 /* 5951 * For SMP systems, create four times as many arenas as there 5952 * are CPUs by default. 5953 */ 5954 opt_narenas_lshift += 2; 5955 } 5956 5957 /* Determine how many arenas to use. */ 5958 narenas = ncpus; 5959 #endif 5960 if (opt_narenas_lshift > 0) { 5961 if ((narenas << opt_narenas_lshift) > narenas) 5962 narenas <<= opt_narenas_lshift; 5963 /* 5964 * Make sure not to exceed the limits of what base_alloc() can 5965 * handle. 5966 */ 5967 if (narenas * sizeof(arena_t *) > chunksize) 5968 narenas = chunksize / sizeof(arena_t *); 5969 } else if (opt_narenas_lshift < 0) { 5970 if ((narenas >> -opt_narenas_lshift) < narenas) 5971 narenas >>= -opt_narenas_lshift; 5972 /* Make sure there is at least one arena. */ 5973 if (narenas == 0) 5974 narenas = 1; 5975 } 5976 #ifdef MALLOC_BALANCE 5977 assert(narenas != 0); 5978 for (narenas_2pow = 0; 5979 (narenas >> (narenas_2pow + 1)) != 0; 5980 narenas_2pow++); 5981 #endif 5982 5983 #ifdef NO_TLS 5984 if (narenas > 1) { 5985 static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19, 5986 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 5987 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 5988 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 5989 223, 227, 229, 233, 239, 241, 251, 257, 263}; 5990 unsigned nprimes, parenas; 5991 5992 /* 5993 * Pick a prime number of hash arenas that is more than narenas 5994 * so that direct hashing of pthread_self() pointers tends to 5995 * spread allocations evenly among the arenas. 5996 */ 5997 assert((narenas & 1) == 0); /* narenas must be even. */ 5998 nprimes = (sizeof(primes) >> SIZEOF_INT_2POW); 5999 parenas = primes[nprimes - 1]; /* In case not enough primes. */ 6000 for (i = 1; i < nprimes; i++) { 6001 if (primes[i] > narenas) { 6002 parenas = primes[i]; 6003 break; 6004 } 6005 } 6006 narenas = parenas; 6007 } 6008 #endif 6009 6010 #ifndef NO_TLS 6011 # ifndef MALLOC_BALANCE 6012 next_arena = 0; 6013 # endif 6014 #endif 6015 6016 /* Allocate and initialize arenas. */ 6017 arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas); 6018 if (arenas == NULL) { 6019 #ifndef MOZ_MEMORY_WINDOWS 6020 malloc_mutex_unlock(&init_lock); 6021 #endif 6022 return (true); 6023 } 6024 /* 6025 * Zero the array. In practice, this should always be pre-zeroed, 6026 * since it was just mmap()ed, but let's be sure. 6027 */ 6028 memset(arenas, 0, sizeof(arena_t *) * narenas); 6029 6030 /* 6031 * Initialize one arena here. The rest are lazily created in 6032 * choose_arena_hard(). 6033 */ 6034 arenas_extend(0); 6035 if (arenas[0] == NULL) { 6036 #ifndef MOZ_MEMORY_WINDOWS 6037 malloc_mutex_unlock(&init_lock); 6038 #endif 6039 return (true); 6040 } 6041 #ifndef NO_TLS 6042 /* 6043 * Assign the initial arena to the initial thread, in order to avoid 6044 * spurious creation of an extra arena if the application switches to 6045 * threaded mode. 6046 */ 6047 #ifdef MOZ_MEMORY_WINDOWS 6048 TlsSetValue(tlsIndex, arenas[0]); 6049 #else 6050 arenas_map = arenas[0]; 6051 #endif 6052 #endif 6053 6054 /* 6055 * Seed here for the initial thread, since choose_arena_hard() is only 6056 * called for other threads. The seed value doesn't really matter. 6057 */ 6058 #ifdef MALLOC_BALANCE 6059 SPRN(balance, 42); 6060 #endif 6061 6062 malloc_spin_init(&arenas_lock); 6063 6064 #ifdef MALLOC_VALIDATE 6065 chunk_rtree = malloc_rtree_new((SIZEOF_PTR << 3) - opt_chunk_2pow); 6066 if (chunk_rtree == NULL) 6067 return (true); 6068 #endif 6069 6070 /* 6071 * Configure and initialize the memory reserve. This needs to happen 6072 * late during initialization, since chunks are allocated. 6073 */ 6074 malloc_mutex_init(&reserve_mtx); 6075 reserve_min = 0; 6076 reserve_cur = 0; 6077 reserve_max = 0; 6078 if (RESERVE_RANGE_2POW_DEFAULT + opt_reserve_range_lshift >= 0) { 6079 reserve_max += chunksize << (RESERVE_RANGE_2POW_DEFAULT + 6080 opt_reserve_range_lshift); 6081 } 6082 ql_new(&reserve_regs); 6083 reserve_seq = 0; 6084 extent_tree_szad_new(&reserve_chunks_szad); 6085 extent_tree_ad_new(&reserve_chunks_ad); 6086 if (RESERVE_MIN_2POW_DEFAULT + opt_reserve_min_lshift >= 0) { 6087 reserve_min_set(chunksize << (RESERVE_MIN_2POW_DEFAULT + 6088 opt_reserve_min_lshift)); 6089 } 6090 6091 malloc_initialized = true; 6092 #ifndef MOZ_MEMORY_WINDOWS 6093 malloc_mutex_unlock(&init_lock); 6094 #endif 6095 return (false); 6096 } 6097 6098 /* XXX Why not just expose malloc_print_stats()? */ 6099 #ifdef MOZ_MEMORY_WINDOWS 6100 void 6101 malloc_shutdown() 6102 { 6103 6104 malloc_print_stats(); 6105 } 6106 #endif 6107 6108 /* 6109 * End general internal functions. 6110 */ 6111 /******************************************************************************/ 6112 /* 6113 * Begin malloc(3)-compatible functions. 6114 */ 6115 6116 /* 6117 * Inline the standard malloc functions if they are being subsumed by Darwin's 6118 * zone infrastructure. 6119 */ 6120 #ifdef MOZ_MEMORY_DARWIN 6121 # define ZONE_INLINE inline 6122 #else 6123 # define ZONE_INLINE 6124 #endif 6125 6126 /* Mangle standard interfaces on Darwin and Windows CE, 6127 in order to avoid linking problems. */ 6128 #if defined(MOZ_MEMORY_DARWIN) 6129 #define malloc(a) moz_malloc(a) 6130 #define valloc(a) moz_valloc(a) 6131 #define calloc(a, b) moz_calloc(a, b) 6132 #define realloc(a, b) moz_realloc(a, b) 6133 #define free(a) moz_free(a) 6134 #endif 6135 6136 ZONE_INLINE 6137 void * 6138 malloc(size_t size) 6139 { 6140 void *ret; 6141 6142 if (malloc_init()) { 6143 ret = NULL; 6144 goto RETURN; 6145 } 6146 6147 if (size == 0) { 6148 #ifdef MALLOC_SYSV 6149 if (opt_sysv == false) 6150 #endif 6151 size = 1; 6152 #ifdef MALLOC_SYSV 6153 else { 6154 ret = NULL; 6155 goto RETURN; 6156 } 6157 #endif 6158 } 6159 6160 ret = imalloc(size); 6161 6162 RETURN: 6163 if (ret == NULL) { 6164 #ifdef MALLOC_XMALLOC 6165 if (opt_xmalloc) { 6166 _malloc_message(_getprogname(), 6167 ": (malloc) Error in malloc(): out of memory\n", "", 6168 ""); 6169 abort(); 6170 } 6171 #endif 6172 errno = ENOMEM; 6173 } 6174 6175 UTRACE(0, size, ret); 6176 return (ret); 6177 } 6178 6179 #ifdef MOZ_MEMORY_SOLARIS 6180 # ifdef __SUNPRO_C 6181 void * 6182 memalign(size_t alignment, size_t size); 6183 #pragma no_inline(memalign) 6184 # elif (defined(__GNU_C__)) 6185 __attribute__((noinline)) 6186 # endif 6187 #else 6188 inline 6189 #endif 6190 void * 6191 memalign(size_t alignment, size_t size) 6192 { 6193 void *ret; 6194 6195 assert(((alignment - 1) & alignment) == 0 && alignment >= 6196 sizeof(void *)); 6197 6198 if (malloc_init()) { 6199 ret = NULL; 6200 goto RETURN; 6201 } 6202 6203 ret = ipalloc(alignment, size); 6204 6205 RETURN: 6206 #ifdef MALLOC_XMALLOC 6207 if (opt_xmalloc && ret == NULL) { 6208 _malloc_message(_getprogname(), 6209 ": (malloc) Error in memalign(): out of memory\n", "", ""); 6210 abort(); 6211 } 6212 #endif 6213 UTRACE(0, size, ret); 6214 return (ret); 6215 } 6216 6217 ZONE_INLINE 6218 int 6219 posix_memalign(void **memptr, size_t alignment, size_t size) 6220 { 6221 void *result; 6222 6223 /* Make sure that alignment is a large enough power of 2. */ 6224 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) { 6225 #ifdef MALLOC_XMALLOC 6226 if (opt_xmalloc) { 6227 _malloc_message(_getprogname(), 6228 ": (malloc) Error in posix_memalign(): " 6229 "invalid alignment\n", "", ""); 6230 abort(); 6231 } 6232 #endif 6233 return (EINVAL); 6234 } 6235 6236 #ifdef MOZ_MEMORY_DARWIN 6237 result = moz_memalign(alignment, size); 6238 #else 6239 result = memalign(alignment, size); 6240 #endif 6241 if (result == NULL) 6242 return (ENOMEM); 6243 6244 *memptr = result; 6245 return (0); 6246 } 6247 6248 ZONE_INLINE 6249 void * 6250 valloc(size_t size) 6251 { 6252 #ifdef MOZ_MEMORY_DARWIN 6253 return (moz_memalign(pagesize, size)); 6254 #else 6255 return (memalign(pagesize, size)); 6256 #endif 6257 } 6258 6259 ZONE_INLINE 6260 void * 6261 calloc(size_t num, size_t size) 6262 { 6263 void *ret; 6264 size_t num_size; 6265 6266 if (malloc_init()) { 6267 num_size = 0; 6268 ret = NULL; 6269 goto RETURN; 6270 } 6271 6272 num_size = num * size; 6273 if (num_size == 0) { 6274 #ifdef MALLOC_SYSV 6275 if ((opt_sysv == false) && ((num == 0) || (size == 0))) 6276 #endif 6277 num_size = 1; 6278 #ifdef MALLOC_SYSV 6279 else { 6280 ret = NULL; 6281 goto RETURN; 6282 } 6283 #endif 6284 /* 6285 * Try to avoid division here. We know that it isn't possible to 6286 * overflow during multiplication if neither operand uses any of the 6287 * most significant half of the bits in a size_t. 6288 */ 6289 } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2))) 6290 && (num_size / size != num)) { 6291 /* size_t overflow. */ 6292 ret = NULL; 6293 goto RETURN; 6294 } 6295 6296 ret = icalloc(num_size); 6297 6298 RETURN: 6299 if (ret == NULL) { 6300 #ifdef MALLOC_XMALLOC 6301 if (opt_xmalloc) { 6302 _malloc_message(_getprogname(), 6303 ": (malloc) Error in calloc(): out of memory\n", "", 6304 ""); 6305 abort(); 6306 } 6307 #endif 6308 errno = ENOMEM; 6309 } 6310 6311 UTRACE(0, num_size, ret); 6312 return (ret); 6313 } 6314 6315 ZONE_INLINE 6316 void * 6317 realloc(void *ptr, size_t size) 6318 { 6319 void *ret; 6320 6321 if (size == 0) { 6322 #ifdef MALLOC_SYSV 6323 if (opt_sysv == false) 6324 #endif 6325 size = 1; 6326 #ifdef MALLOC_SYSV 6327 else { 6328 if (ptr != NULL) 6329 idalloc(ptr); 6330 ret = NULL; 6331 goto RETURN; 6332 } 6333 #endif 6334 } 6335 6336 if (ptr != NULL) { 6337 assert(malloc_initialized); 6338 6339 ret = iralloc(ptr, size); 6340 6341 if (ret == NULL) { 6342 #ifdef MALLOC_XMALLOC 6343 if (opt_xmalloc) { 6344 _malloc_message(_getprogname(), 6345 ": (malloc) Error in realloc(): out of " 6346 "memory\n", "", ""); 6347 abort(); 6348 } 6349 #endif 6350 errno = ENOMEM; 6351 } 6352 } else { 6353 if (malloc_init()) 6354 ret = NULL; 6355 else 6356 ret = imalloc(size); 6357 6358 if (ret == NULL) { 6359 #ifdef MALLOC_XMALLOC 6360 if (opt_xmalloc) { 6361 _malloc_message(_getprogname(), 6362 ": (malloc) Error in realloc(): out of " 6363 "memory\n", "", ""); 6364 abort(); 6365 } 6366 #endif 6367 errno = ENOMEM; 6368 } 6369 } 6370 6371 #ifdef MALLOC_SYSV 6372 RETURN: 6373 #endif 6374 UTRACE(ptr, size, ret); 6375 return (ret); 6376 } 6377 6378 ZONE_INLINE 6379 void 6380 free(void *ptr) 6381 { 6382 6383 UTRACE(ptr, 0, 0); 6384 if (ptr != NULL) { 6385 assert(malloc_initialized); 6386 6387 idalloc(ptr); 6388 } 6389 } 6390 6391 /* 6392 * End malloc(3)-compatible functions. 6393 */ 6394 /******************************************************************************/ 6395 /* 6396 * Begin non-standard functions. 6397 */ 6398 6399 size_t 6400 malloc_usable_size(const void *ptr) 6401 { 6402 6403 #ifdef MALLOC_VALIDATE 6404 return (isalloc_validate(ptr)); 6405 #else 6406 assert(ptr != NULL); 6407 6408 return (isalloc(ptr)); 6409 #endif 6410 } 6411 6412 void 6413 jemalloc_stats(jemalloc_stats_t *stats) 6414 { 6415 size_t i; 6416 6417 assert(stats != NULL); 6418 6419 /* 6420 * Gather runtime settings. 6421 */ 6422 stats->opt_abort = opt_abort; 6423 stats->opt_junk = 6424 #ifdef MALLOC_FILL 6425 opt_junk ? true : 6426 #endif 6427 false; 6428 stats->opt_utrace = 6429 #ifdef MALLOC_UTRACE 6430 opt_utrace ? true : 6431 #endif 6432 false; 6433 stats->opt_sysv = 6434 #ifdef MALLOC_SYSV 6435 opt_sysv ? true : 6436 #endif 6437 false; 6438 stats->opt_xmalloc = 6439 #ifdef MALLOC_XMALLOC 6440 opt_xmalloc ? true : 6441 #endif 6442 false; 6443 stats->opt_zero = 6444 #ifdef MALLOC_FILL 6445 opt_zero ? true : 6446 #endif 6447 false; 6448 stats->narenas = narenas; 6449 stats->balance_threshold = 6450 #ifdef MALLOC_BALANCE 6451 opt_balance_threshold 6452 #else 6453 SIZE_T_MAX 6454 #endif 6455 ; 6456 stats->quantum = quantum; 6457 stats->small_max = small_max; 6458 stats->large_max = arena_maxclass; 6459 stats->chunksize = chunksize; 6460 stats->dirty_max = opt_dirty_max; 6461 6462 malloc_mutex_lock(&reserve_mtx); 6463 stats->reserve_min = reserve_min; 6464 stats->reserve_max = reserve_max; 6465 stats->reserve_cur = reserve_cur; 6466 malloc_mutex_unlock(&reserve_mtx); 6467 6468 /* 6469 * Gather current memory usage statistics. 6470 */ 6471 stats->mapped = 0; 6472 stats->committed = 0; 6473 stats->allocated = 0; 6474 stats->dirty = 0; 6475 6476 /* Get huge mapped/allocated. */ 6477 malloc_mutex_lock(&huge_mtx); 6478 stats->mapped += stats_chunks.curchunks * chunksize; 6479 #ifdef MALLOC_DECOMMIT 6480 stats->committed += huge_allocated; 6481 #endif 6482 stats->allocated += huge_allocated; 6483 malloc_mutex_unlock(&huge_mtx); 6484 6485 /* Get base mapped. */ 6486 malloc_mutex_lock(&base_mtx); 6487 stats->mapped += base_mapped; 6488 #ifdef MALLOC_DECOMMIT 6489 stats->committed += base_mapped; 6490 #endif 6491 malloc_mutex_unlock(&base_mtx); 6492 6493 /* Iterate over arenas and their chunks. */ 6494 for (i = 0; i < narenas; i++) { 6495 arena_t *arena = arenas[i]; 6496 if (arena != NULL) { 6497 arena_chunk_t *chunk; 6498 6499 malloc_spin_lock(&arena->lock); 6500 stats->allocated += arena->stats.allocated_small; 6501 stats->allocated += arena->stats.allocated_large; 6502 #ifdef MALLOC_DECOMMIT 6503 rb_foreach_begin(arena_chunk_t, link_dirty, 6504 &arena->chunks_dirty, chunk) { 6505 size_t j; 6506 6507 for (j = 0; j < chunk_npages; j++) { 6508 if ((chunk->map[j].bits & 6509 CHUNK_MAP_DECOMMITTED) == 0) 6510 stats->committed += pagesize; 6511 } 6512 } rb_foreach_end(arena_chunk_t, link_dirty, 6513 &arena->chunks_dirty, chunk) 6514 #endif 6515 stats->dirty += (arena->ndirty << pagesize_2pow); 6516 malloc_spin_unlock(&arena->lock); 6517 } 6518 } 6519 6520 #ifndef MALLOC_DECOMMIT 6521 stats->committed = stats->mapped; 6522 #endif 6523 } 6524 6525 void * 6526 xmalloc(size_t size) 6527 { 6528 void *ret; 6529 6530 if (malloc_init()) 6531 reserve_fail(size, "xmalloc"); 6532 6533 if (size == 0) { 6534 #ifdef MALLOC_SYSV 6535 if (opt_sysv == false) 6536 #endif 6537 size = 1; 6538 #ifdef MALLOC_SYSV 6539 else { 6540 _malloc_message(_getprogname(), 6541 ": (malloc) Error in xmalloc(): ", 6542 "invalid size 0", "\n"); 6543 abort(); 6544 } 6545 #endif 6546 } 6547 6548 ret = imalloc(size); 6549 if (ret == NULL) { 6550 uint64_t seq = 0; 6551 6552 do { 6553 seq = reserve_crit(size, "xmalloc", seq); 6554 ret = imalloc(size); 6555 } while (ret == NULL); 6556 } 6557 6558 UTRACE(0, size, ret); 6559 return (ret); 6560 } 6561 6562 void * 6563 xcalloc(size_t num, size_t size) 6564 { 6565 void *ret; 6566 size_t num_size; 6567 6568 num_size = num * size; 6569 if (malloc_init()) 6570 reserve_fail(num_size, "xcalloc"); 6571 6572 if (num_size == 0) { 6573 #ifdef MALLOC_SYSV 6574 if ((opt_sysv == false) && ((num == 0) || (size == 0))) 6575 #endif 6576 num_size = 1; 6577 #ifdef MALLOC_SYSV 6578 else { 6579 _malloc_message(_getprogname(), 6580 ": (malloc) Error in xcalloc(): ", 6581 "invalid size 0", "\n"); 6582 abort(); 6583 } 6584 #endif 6585 /* 6586 * Try to avoid division here. We know that it isn't possible to 6587 * overflow during multiplication if neither operand uses any of the 6588 * most significant half of the bits in a size_t. 6589 */ 6590 } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2))) 6591 && (num_size / size != num)) { 6592 /* size_t overflow. */ 6593 _malloc_message(_getprogname(), 6594 ": (malloc) Error in xcalloc(): ", 6595 "size overflow", "\n"); 6596 abort(); 6597 } 6598 6599 ret = icalloc(num_size); 6600 if (ret == NULL) { 6601 uint64_t seq = 0; 6602 6603 do { 6604 seq = reserve_crit(num_size, "xcalloc", seq); 6605 ret = icalloc(num_size); 6606 } while (ret == NULL); 6607 } 6608 6609 UTRACE(0, num_size, ret); 6610 return (ret); 6611 } 6612 6613 void * 6614 xrealloc(void *ptr, size_t size) 6615 { 6616 void *ret; 6617 6618 if (size == 0) { 6619 #ifdef MALLOC_SYSV 6620 if (opt_sysv == false) 6621 #endif 6622 size = 1; 6623 #ifdef MALLOC_SYSV 6624 else { 6625 if (ptr != NULL) 6626 idalloc(ptr); 6627 _malloc_message(_getprogname(), 6628 ": (malloc) Error in xrealloc(): ", 6629 "invalid size 0", "\n"); 6630 abort(); 6631 } 6632 #endif 6633 } 6634 6635 if (ptr != NULL) { 6636 assert(malloc_initialized); 6637 6638 ret = iralloc(ptr, size); 6639 if (ret == NULL) { 6640 uint64_t seq = 0; 6641 6642 do { 6643 seq = reserve_crit(size, "xrealloc", seq); 6644 ret = iralloc(ptr, size); 6645 } while (ret == NULL); 6646 } 6647 } else { 6648 if (malloc_init()) 6649 reserve_fail(size, "xrealloc"); 6650 6651 ret = imalloc(size); 6652 if (ret == NULL) { 6653 uint64_t seq = 0; 6654 6655 do { 6656 seq = reserve_crit(size, "xrealloc", seq); 6657 ret = imalloc(size); 6658 } while (ret == NULL); 6659 } 6660 } 6661 6662 UTRACE(ptr, size, ret); 6663 return (ret); 6664 } 6665 6666 void * 6667 xmemalign(size_t alignment, size_t size) 6668 { 6669 void *ret; 6670 6671 assert(((alignment - 1) & alignment) == 0 && alignment >= 6672 sizeof(void *)); 6673 6674 if (malloc_init()) 6675 reserve_fail(size, "xmemalign"); 6676 6677 ret = ipalloc(alignment, size); 6678 if (ret == NULL) { 6679 uint64_t seq = 0; 6680 6681 do { 6682 seq = reserve_crit(size, "xmemalign", seq); 6683 ret = ipalloc(alignment, size); 6684 } while (ret == NULL); 6685 } 6686 6687 UTRACE(0, size, ret); 6688 return (ret); 6689 } 6690 6691 static void 6692 reserve_shrink(void) 6693 { 6694 extent_node_t *node; 6695 6696 assert(reserve_cur > reserve_max); 6697 #ifdef MALLOC_DEBUG 6698 { 6699 extent_node_t *node; 6700 size_t reserve_size; 6701 6702 reserve_size = 0; 6703 rb_foreach_begin(extent_node_t, link_szad, &reserve_chunks_szad, 6704 node) { 6705 reserve_size += node->size; 6706 } rb_foreach_end(extent_node_t, link_szad, &reserve_chunks_szad, 6707 node) 6708 assert(reserve_size == reserve_cur); 6709 6710 reserve_size = 0; 6711 rb_foreach_begin(extent_node_t, link_ad, &reserve_chunks_ad, 6712 node) { 6713 reserve_size += node->size; 6714 } rb_foreach_end(extent_node_t, link_ad, &reserve_chunks_ad, 6715 node) 6716 assert(reserve_size == reserve_cur); 6717 } 6718 #endif 6719 6720 /* Discard chunks until the the reserve is below the size limit. */ 6721 rb_foreach_reverse_begin(extent_node_t, link_ad, &reserve_chunks_ad, 6722 node) { 6723 #ifndef MALLOC_DECOMMIT 6724 if (node->size <= reserve_cur - reserve_max) { 6725 #endif 6726 extent_node_t *tnode = extent_tree_ad_prev( 6727 &reserve_chunks_ad, node); 6728 6729 #ifdef MALLOC_DECOMMIT 6730 assert(node->size <= reserve_cur - reserve_max); 6731 #endif 6732 6733 /* Discard the entire [multi-]chunk. */ 6734 extent_tree_szad_remove(&reserve_chunks_szad, node); 6735 extent_tree_ad_remove(&reserve_chunks_ad, node); 6736 reserve_cur -= node->size; 6737 pages_unmap(node->addr, node->size); 6738 #ifdef MALLOC_STATS 6739 stats_chunks.curchunks -= (node->size / chunksize); 6740 #endif 6741 base_node_dealloc(node); 6742 if (reserve_cur == reserve_max) 6743 break; 6744 6745 rb_foreach_reverse_prev(extent_node_t, link_ad, 6746 extent_ad_comp, &reserve_chunks_ad, tnode); 6747 #ifndef MALLOC_DECOMMIT 6748 } else { 6749 /* Discard the end of the multi-chunk. */ 6750 extent_tree_szad_remove(&reserve_chunks_szad, node); 6751 node->size -= reserve_cur - reserve_max; 6752 extent_tree_szad_insert(&reserve_chunks_szad, node); 6753 pages_unmap((void *)((uintptr_t)node->addr + 6754 node->size), reserve_cur - reserve_max); 6755 #ifdef MALLOC_STATS 6756 stats_chunks.curchunks -= ((reserve_cur - reserve_max) / 6757 chunksize); 6758 #endif 6759 reserve_cur = reserve_max; 6760 break; 6761 } 6762 #endif 6763 assert(reserve_cur > reserve_max); 6764 } rb_foreach_reverse_end(extent_node_t, link_ad, &reserve_chunks_ad, 6765 node) 6766 } 6767 6768 /* Send a condition notification. */ 6769 static uint64_t 6770 reserve_notify(reserve_cnd_t cnd, size_t size, uint64_t seq) 6771 { 6772 reserve_reg_t *reg; 6773 6774 /* seq is used to keep track of distinct condition-causing events. */ 6775 if (seq == 0) { 6776 /* Allocate new sequence number. */ 6777 reserve_seq++; 6778 seq = reserve_seq; 6779 } 6780 6781 /* 6782 * Advance to the next callback registration and send a notification, 6783 * unless one has already been sent for this condition-causing event. 6784 */ 6785 reg = ql_first(&reserve_regs); 6786 if (reg == NULL) 6787 return (0); 6788 ql_first(&reserve_regs) = ql_next(&reserve_regs, reg, link); 6789 if (reg->seq == seq) 6790 return (0); 6791 reg->seq = seq; 6792 malloc_mutex_unlock(&reserve_mtx); 6793 reg->cb(reg->ctx, cnd, size); 6794 malloc_mutex_lock(&reserve_mtx); 6795 6796 return (seq); 6797 } 6798 6799 /* Allocation failure due to OOM. Try to free some memory via callbacks. */ 6800 static uint64_t 6801 reserve_crit(size_t size, const char *fname, uint64_t seq) 6802 { 6803 6804 /* 6805 * Send one condition notification. Iteration is handled by the 6806 * caller of this function. 6807 */ 6808 malloc_mutex_lock(&reserve_mtx); 6809 seq = reserve_notify(RESERVE_CND_CRIT, size, seq); 6810 malloc_mutex_unlock(&reserve_mtx); 6811 6812 /* If no notification could be sent, then no further recourse exists. */ 6813 if (seq == 0) 6814 reserve_fail(size, fname); 6815 6816 return (seq); 6817 } 6818 6819 /* Permanent allocation failure due to OOM. */ 6820 static void 6821 reserve_fail(size_t size, const char *fname) 6822 { 6823 uint64_t seq = 0; 6824 6825 /* Send fail notifications. */ 6826 malloc_mutex_lock(&reserve_mtx); 6827 do { 6828 seq = reserve_notify(RESERVE_CND_FAIL, size, seq); 6829 } while (seq != 0); 6830 malloc_mutex_unlock(&reserve_mtx); 6831 6832 /* Terminate the application. */ 6833 _malloc_message(_getprogname(), 6834 ": (malloc) Error in ", fname, "(): out of memory\n"); 6835 abort(); 6836 } 6837 6838 bool 6839 reserve_cb_register(reserve_cb_t *cb, void *ctx) 6840 { 6841 reserve_reg_t *reg = base_reserve_reg_alloc(); 6842 if (reg == NULL) 6843 return (true); 6844 6845 ql_elm_new(reg, link); 6846 reg->cb = cb; 6847 reg->ctx = ctx; 6848 reg->seq = 0; 6849 6850 malloc_mutex_lock(&reserve_mtx); 6851 ql_head_insert(&reserve_regs, reg, link); 6852 malloc_mutex_unlock(&reserve_mtx); 6853 6854 return (false); 6855 } 6856 6857 bool 6858 reserve_cb_unregister(reserve_cb_t *cb, void *ctx) 6859 { 6860 reserve_reg_t *reg = NULL; 6861 6862 malloc_mutex_lock(&reserve_mtx); 6863 ql_foreach(reg, &reserve_regs, link) { 6864 if (reg->cb == cb && reg->ctx == ctx) { 6865 ql_remove(&reserve_regs, reg, link); 6866 break; 6867 } 6868 } 6869 malloc_mutex_unlock(&reserve_mtx); 6870 6871 if (reg != NULL) 6872 base_reserve_reg_dealloc(reg); 6873 return (false); 6874 return (true); 6875 } 6876 6877 size_t 6878 reserve_cur_get(void) 6879 { 6880 size_t ret; 6881 6882 malloc_mutex_lock(&reserve_mtx); 6883 ret = reserve_cur; 6884 malloc_mutex_unlock(&reserve_mtx); 6885 6886 return (ret); 6887 } 6888 6889 size_t 6890 reserve_min_get(void) 6891 { 6892 size_t ret; 6893 6894 malloc_mutex_lock(&reserve_mtx); 6895 ret = reserve_min; 6896 malloc_mutex_unlock(&reserve_mtx); 6897 6898 return (ret); 6899 } 6900 6901 bool 6902 reserve_min_set(size_t min) 6903 { 6904 6905 min = CHUNK_CEILING(min); 6906 6907 malloc_mutex_lock(&reserve_mtx); 6908 /* Keep |reserve_max - reserve_min| the same. */ 6909 if (min < reserve_min) { 6910 reserve_max -= reserve_min - min; 6911 reserve_min = min; 6912 } else { 6913 /* Protect against wrap-around. */ 6914 if (reserve_max + min - reserve_min < reserve_max) { 6915 reserve_min = SIZE_T_MAX - (reserve_max - reserve_min) 6916 - chunksize + 1; 6917 reserve_max = SIZE_T_MAX - chunksize + 1; 6918 } else { 6919 reserve_max += min - reserve_min; 6920 reserve_min = min; 6921 } 6922 } 6923 6924 /* Resize the reserve if necessary. */ 6925 if (reserve_cur < reserve_min) { 6926 size_t size = reserve_min - reserve_cur; 6927 6928 /* Force the reserve to grow by allocating/deallocating. */ 6929 malloc_mutex_unlock(&reserve_mtx); 6930 #ifdef MALLOC_DECOMMIT 6931 { 6932 void **chunks; 6933 size_t i, n; 6934 6935 n = size >> opt_chunk_2pow; 6936 chunks = (void**)imalloc(n * sizeof(void *)); 6937 if (chunks == NULL) 6938 return (true); 6939 for (i = 0; i < n; i++) { 6940 chunks[i] = huge_malloc(chunksize, false); 6941 if (chunks[i] == NULL) { 6942 size_t j; 6943 6944 for (j = 0; j < i; j++) { 6945 huge_dalloc(chunks[j]); 6946 } 6947 idalloc(chunks); 6948 return (true); 6949 } 6950 } 6951 for (i = 0; i < n; i++) 6952 huge_dalloc(chunks[i]); 6953 idalloc(chunks); 6954 } 6955 #else 6956 { 6957 void *x = huge_malloc(size, false); 6958 if (x == NULL) { 6959 return (true); 6960 } 6961 huge_dalloc(x); 6962 } 6963 #endif 6964 } else if (reserve_cur > reserve_max) { 6965 reserve_shrink(); 6966 malloc_mutex_unlock(&reserve_mtx); 6967 } else 6968 malloc_mutex_unlock(&reserve_mtx); 6969 6970 return (false); 6971 } 6972 6973 #ifdef MOZ_MEMORY_WINDOWS 6974 void* 6975 _recalloc(void *ptr, size_t count, size_t size) 6976 { 6977 size_t oldsize = (ptr != NULL) ? isalloc(ptr) : 0; 6978 size_t newsize = count * size; 6979 6980 /* 6981 * In order for all trailing bytes to be zeroed, the caller needs to 6982 * use calloc(), followed by recalloc(). However, the current calloc() 6983 * implementation only zeros the bytes requested, so if recalloc() is 6984 * to work 100% correctly, calloc() will need to change to zero 6985 * trailing bytes. 6986 */ 6987 6988 ptr = realloc(ptr, newsize); 6989 if (ptr != NULL && oldsize < newsize) { 6990 memset((void *)((uintptr_t)ptr + oldsize), 0, newsize - 6991 oldsize); 6992 } 6993 6994 return ptr; 6995 } 6996 6997 /* 6998 * This impl of _expand doesn't ever actually expand or shrink blocks: it 6999 * simply replies that you may continue using a shrunk block. 7000 */ 7001 void* 7002 _expand(void *ptr, size_t newsize) 7003 { 7004 if (isalloc(ptr) >= newsize) 7005 return ptr; 7006 7007 return NULL; 7008 } 7009 7010 size_t 7011 _msize(const void *ptr) 7012 { 7013 7014 return malloc_usable_size(ptr); 7015 } 7016 #endif 7017 7018 /* 7019 * End non-standard functions. 7020 */ 7021 /******************************************************************************/ 7022 /* 7023 * Begin library-private functions, used by threading libraries for protection 7024 * of malloc during fork(). These functions are only called if the program is 7025 * running in threaded mode, so there is no need to check whether the program 7026 * is threaded here. 7027 */ 7028 7029 void 7030 _malloc_prefork(void) 7031 { 7032 unsigned i; 7033 7034 /* Acquire all mutexes in a safe order. */ 7035 7036 malloc_spin_lock(&arenas_lock); 7037 for (i = 0; i < narenas; i++) { 7038 if (arenas[i] != NULL) 7039 malloc_spin_lock(&arenas[i]->lock); 7040 } 7041 malloc_spin_unlock(&arenas_lock); 7042 7043 malloc_mutex_lock(&base_mtx); 7044 7045 malloc_mutex_lock(&huge_mtx); 7046 } 7047 7048 void 7049 _malloc_postfork(void) 7050 { 7051 unsigned i; 7052 7053 /* Release all mutexes, now that fork() has completed. */ 7054 7055 malloc_mutex_unlock(&huge_mtx); 7056 7057 malloc_mutex_unlock(&base_mtx); 7058 7059 malloc_spin_lock(&arenas_lock); 7060 for (i = 0; i < narenas; i++) { 7061 if (arenas[i] != NULL) 7062 malloc_spin_unlock(&arenas[i]->lock); 7063 } 7064 malloc_spin_unlock(&arenas_lock); 7065 } 7066 7067 /* 7068 * End library-private functions. 7069 */ 7070 /******************************************************************************/ 7071 7072 #ifdef HAVE_LIBDL 7073 # include <dlfcn.h> 7074 #endif 7075 7076 #ifdef MOZ_MEMORY_DARWIN 7077 static malloc_zone_t zone; 7078 static struct malloc_introspection_t zone_introspect; 7079 7080 static size_t 7081 zone_size(malloc_zone_t *zone, void *ptr) 7082 { 7083 7084 /* 7085 * There appear to be places within Darwin (such as setenv(3)) that 7086 * cause calls to this function with pointers that *no* zone owns. If 7087 * we knew that all pointers were owned by *some* zone, we could split 7088 * our zone into two parts, and use one as the default allocator and 7089 * the other as the default deallocator/reallocator. Since that will 7090 * not work in practice, we must check all pointers to assure that they 7091 * reside within a mapped chunk before determining size. 7092 */ 7093 return (isalloc_validate(ptr)); 7094 } 7095 7096 static void * 7097 zone_malloc(malloc_zone_t *zone, size_t size) 7098 { 7099 7100 return (malloc(size)); 7101 } 7102 7103 static void * 7104 zone_calloc(malloc_zone_t *zone, size_t num, size_t size) 7105 { 7106 7107 return (calloc(num, size)); 7108 } 7109 7110 static void * 7111 zone_valloc(malloc_zone_t *zone, size_t size) 7112 { 7113 void *ret = NULL; /* Assignment avoids useless compiler warning. */ 7114 7115 posix_memalign(&ret, pagesize, size); 7116 7117 return (ret); 7118 } 7119 7120 static void 7121 zone_free(malloc_zone_t *zone, void *ptr) 7122 { 7123 7124 free(ptr); 7125 } 7126 7127 static void * 7128 zone_realloc(malloc_zone_t *zone, void *ptr, size_t size) 7129 { 7130 7131 return (realloc(ptr, size)); 7132 } 7133 7134 static void * 7135 zone_destroy(malloc_zone_t *zone) 7136 { 7137 7138 /* This function should never be called. */ 7139 assert(false); 7140 return (NULL); 7141 } 7142 7143 static size_t 7144 zone_good_size(malloc_zone_t *zone, size_t size) 7145 { 7146 size_t ret; 7147 void *p; 7148 7149 /* 7150 * Actually create an object of the appropriate size, then find out 7151 * how large it could have been without moving up to the next size 7152 * class. 7153 */ 7154 p = malloc(size); 7155 if (p != NULL) { 7156 ret = isalloc(p); 7157 free(p); 7158 } else 7159 ret = size; 7160 7161 return (ret); 7162 } 7163 7164 static void 7165 zone_force_lock(malloc_zone_t *zone) 7166 { 7167 7168 _malloc_prefork(); 7169 } 7170 7171 static void 7172 zone_force_unlock(malloc_zone_t *zone) 7173 { 7174 7175 _malloc_postfork(); 7176 } 7177 7178 static malloc_zone_t * 7179 create_zone(void) 7180 { 7181 7182 assert(malloc_initialized); 7183 7184 zone.size = (void *)zone_size; 7185 zone.malloc = (void *)zone_malloc; 7186 zone.calloc = (void *)zone_calloc; 7187 zone.valloc = (void *)zone_valloc; 7188 zone.free = (void *)zone_free; 7189 zone.realloc = (void *)zone_realloc; 7190 zone.destroy = (void *)zone_destroy; 7191 zone.zone_name = "jemalloc_zone"; 7192 zone.batch_malloc = NULL; 7193 zone.batch_free = NULL; 7194 zone.introspect = &zone_introspect; 7195 7196 zone_introspect.enumerator = NULL; 7197 zone_introspect.good_size = (void *)zone_good_size; 7198 zone_introspect.check = NULL; 7199 zone_introspect.print = NULL; 7200 zone_introspect.log = NULL; 7201 zone_introspect.force_lock = (void *)zone_force_lock; 7202 zone_introspect.force_unlock = (void *)zone_force_unlock; 7203 zone_introspect.statistics = NULL; 7204 7205 return (&zone); 7206 } 7207 7208 __attribute__((constructor)) 7209 void 7210 jemalloc_darwin_init(void) 7211 { 7212 extern unsigned malloc_num_zones; 7213 extern malloc_zone_t **malloc_zones; 7214 7215 if (malloc_init_hard()) 7216 abort(); 7217 7218 /* 7219 * The following code is *not* thread-safe, so it's critical that 7220 * initialization be manually triggered. 7221 */ 7222 7223 /* Register the custom zones. */ 7224 malloc_zone_register(create_zone()); 7225 assert(malloc_zones[malloc_num_zones - 1] == &zone); 7226 7227 /* 7228 * Shift malloc_zones around so that zone is first, which makes it the 7229 * default zone. 7230 */ 7231 assert(malloc_num_zones > 1); 7232 memmove(&malloc_zones[1], &malloc_zones[0], 7233 sizeof(malloc_zone_t *) * (malloc_num_zones - 1)); 7234 malloc_zones[0] = &zone; 7235 } 7236 7237 #elif defined(__GLIBC__) && !defined(__UCLIBC__) 7238 /* 7239 * glibc provides the RTLD_DEEPBIND flag for dlopen which can make it possible 7240 * to inconsistently reference libc's malloc(3)-compatible functions 7241 * (bug 493541). 7242 * 7243 * These definitions interpose hooks in glibc. The functions are actually 7244 * passed an extra argument for the caller return address, which will be 7245 * ignored. 7246 */ 7247 void (*__free_hook)(void *ptr) = free; 7248 void *(*__malloc_hook)(size_t size) = malloc; 7249 void *(*__realloc_hook)(void *ptr, size_t size) = realloc; 7250 void *(*__memalign_hook)(size_t alignment, size_t size) = memalign; 7251 7252 #elif defined(RTLD_DEEPBIND) 7253 /* 7254 * XXX On systems that support RTLD_GROUP or DF_1_GROUP, do their 7255 * implementations permit similar inconsistencies? Should STV_SINGLETON 7256 * visibility be used for interposition where available? 7257 */ 7258 # error "Interposing malloc is unsafe on this system without libc malloc hooks." 7259 #endif 7260