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