src/third_party/jemalloc/vendor/jemalloc.c

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