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