1 /* -*- Mode: C; tab-width: 8; c-basic-offset: 8; indent-tabs-mode: t -*- */
2 /* vim:set softtabstop=8 shiftwidth=8: */
4 * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
31 *******************************************************************************
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:
37 * + Multiple arenas are used if there are multiple CPUs, which reduces lock
38 * contention and cache sloshing.
40 * + Cache line sharing between arenas is avoided for internal data
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.
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
53 * |=====================================|
54 * | Category | Subcategory | Size |
55 * |=====================================|
56 * | Small | Tiny | 2 |
59 * | |----------------+---------|
60 * | | Quantum-spaced | 16 |
67 * | |----------------+---------|
68 * | | Sub-page | 1 kB |
70 * |=====================================|
78 * |=====================================|
83 * |=====================================|
85 * A different mechanism is used for each category:
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.
90 * Large : Each allocation is backed by a dedicated run. Metadata are stored
91 * in the associated arena chunk header maps.
93 * Huge : Each allocation is backed by a dedicated contiguous set of chunks.
94 * Metadata are stored in a separate red-black tree.
96 *******************************************************************************
98 #include "jemalloc_gnash.h"
100 #ifdef MOZ_MEMORY_ANDROID
102 #define _pthread_self() pthread_self()
106 * MALLOC_PRODUCTION disables assertions and statistics gathering. It also
107 * defaults the A and J runtime options to off. These settings are appropriate
108 * for production systems.
110 #ifndef MOZ_MEMORY_DEBUG
111 # define MALLOC_PRODUCTION
115 * Use only one arena by default. Mozilla does not currently make extensive
116 * use of concurrent allocation, so the increased fragmentation associated with
117 * multiple arenas is not warranted.
119 #define MOZ_MEMORY_NARENAS_DEFAULT_ONE
121 #ifndef MALLOC_PRODUCTION
123 * MALLOC_DEBUG enables assertions and other sanity checks, and disables
126 # define MALLOC_DEBUG
129 * MALLOC_STATS enables statistics calculation, and is required for
132 # define MALLOC_STATS
134 /* Memory filling (junk/zero). */
137 /* Allocation tracing. */
138 # ifndef MOZ_MEMORY_WINDOWS
139 # define MALLOC_UTRACE
142 /* Support optional abort() on OOM. */
143 # define MALLOC_XMALLOC
145 /* Support SYSV semantics. */
150 * MALLOC_VALIDATE causes malloc_usable_size() to perform some pointer
151 * validation. There are many possible errors that validation does not even
154 #define MALLOC_VALIDATE
156 /* Embed no-op macros that support memory allocation tracking via valgrind. */
158 # define MALLOC_VALGRIND
160 #ifdef MALLOC_VALGRIND
161 # include <valgrind/valgrind.h>
163 # define VALGRIND_MALLOCLIKE_BLOCK(addr, sizeB, rzB, is_zeroed)
164 # define VALGRIND_FREELIKE_BLOCK(addr, rzB)
168 * MALLOC_BALANCE enables monitoring of arena lock contention and dynamically
169 * re-balances arena load if exponentially averaged contention exceeds a
172 /* #define MALLOC_BALANCE */
174 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN))
176 * MALLOC_PAGEFILE causes all mmap()ed memory to be backed by temporary
177 * files, so that if a chunk is mapped, it is guaranteed to be swappable.
178 * This avoids asynchronous OOM failures that are due to VM over-commit.
180 * XXX OS X over-commits, so we should probably use mmap() instead of
181 * vm_allocate(), so that MALLOC_PAGEFILE works.
183 #define MALLOC_PAGEFILE
186 #ifdef MALLOC_PAGEFILE
187 /* Write size when initializing a page file. */
188 # define MALLOC_PAGEFILE_WRITE_SIZE 512
191 #if defined(MOZ_MEMORY_LINUX) && !defined(MOZ_MEMORY_ANDROID)
192 #define _GNU_SOURCE /* For mremap(2). */
193 #define issetugid() 0
194 #if 0 /* Enable in order to test decommit code on Linux. */
195 # define MALLOC_DECOMMIT
199 #ifndef MOZ_MEMORY_WINCE
200 #include <sys/types.h>
210 #ifdef MOZ_MEMORY_WINDOWS
211 #ifndef MOZ_MEMORY_WINCE
212 #include <cruntime.h>
213 #include <internal.h>
216 #include <cmnintrin.h>
218 #define SIZE_MAX UINT_MAX
222 #pragma warning( disable: 4267 4996 4146 )
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
234 static unsigned long tlsIndex
= 0xffffffff;
238 #ifdef MOZ_MEMORY_WINCE
239 #define _pthread_self() GetCurrentThreadId()
241 #define _pthread_self() __threadid()
243 #define issetugid() 0
245 #ifndef MOZ_MEMORY_WINCE
246 /* use MSVC intrinsics */
247 #pragma intrinsic(_BitScanForward)
248 static __forceinline
int
253 if (_BitScanForward(&i
, x
) != 0)
259 /* Implement getenv without using malloc */
260 static char mozillaMallocOptionsBuf
[64];
262 #define getenv xgetenv
264 getenv(const char *name
)
267 if (GetEnvironmentVariableA(name
, (LPSTR
)&mozillaMallocOptionsBuf
,
268 sizeof(mozillaMallocOptionsBuf
)) > 0)
269 return (mozillaMallocOptionsBuf
);
279 static __forceinline
int
283 return 32 - _CountLeadingZeros((-x
) & x
);
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 #if defined(MOZ_MEMORY_SIZEOF_PTR_2POW) && (MOZ_MEMORY_SIZEOF_PTR_2POW == 3)
292 typedef long long ssize_t
;
294 typedef long ssize_t
;
297 #define MALLOC_DECOMMIT
300 #ifndef MOZ_MEMORY_WINDOWS
301 #ifndef MOZ_MEMORY_SOLARIS
302 #include <sys/cdefs.h>
305 # define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var))
308 __FBSDID("$FreeBSD: head/lib/libc/stdlib/malloc.c 180599 2008-07-18 19:35:44Z jasone $");
309 #include "libc_private.h"
313 #include "spinlock.h"
314 #include "namespace.h"
316 #include <sys/mman.h>
318 # define MADV_FREE MADV_DONTNEED
321 # define MAP_NOSYNC 0
323 #include <sys/param.h>
325 #include <sys/stddef.h>
327 #include <sys/time.h>
328 #include <sys/types.h>
329 #if !defined(MOZ_MEMORY_SOLARIS) && !defined(MOZ_MEMORY_ANDROID)
330 #include <sys/sysctl.h>
334 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */
336 #include <machine/atomic.h>
337 #include <machine/cpufunc.h>
338 #include <machine/vmparam.h>
344 # define SIZE_T_MAX SIZE_MAX
347 #ifdef MOZ_MEMORY_DARWIN
348 #define _pthread_self pthread_self
349 #define _pthread_mutex_init pthread_mutex_init
350 #define _pthread_mutex_trylock pthread_mutex_trylock
351 #define _pthread_mutex_lock pthread_mutex_lock
352 #define _pthread_mutex_unlock pthread_mutex_unlock
361 #ifndef MOZ_MEMORY_DARWIN
366 #ifdef MOZ_MEMORY_DARWIN
367 #include <libkern/OSAtomic.h>
368 #include <mach/mach_error.h>
369 #include <mach/mach_init.h>
370 #include <mach/vm_map.h>
371 #include <malloc/malloc.h>
375 #include "un-namespace.h"
381 /* Some tools, such as /dev/dsp wrappers, LD_PRELOAD libraries that
382 * happen to override mmap() and call dlsym() from their overridden
383 * mmap(). The problem is that dlsym() calls malloc(), and this ends
384 * up in a dead lock in jemalloc.
385 * On these systems, we prefer to directly use the system call.
386 * We do that for Linux systems and kfreebsd with GNU userland.
387 * Note sanity checks are not done (alignment of offset, ...) because
388 * the uses of mmap are pretty limited, in jemalloc.
390 * On Alpha, glibc has a bug that prevents syscall() to work for system
391 * calls with 6 arguments
393 #if (defined(MOZ_MEMORY_LINUX) && !defined(__alpha__)) || \
394 (defined(MOZ_MEMORY_BSD) && defined(__GLIBC__))
395 #include <sys/syscall.h>
396 #if defined(SYS_mmap) || defined(SYS_mmap2)
398 void *_mmap(void *addr
, size_t length
, int prot
, int flags
,
399 int fd
, off_t offset
)
401 /* S390 only passes one argument to the mmap system call, which is a
402 * pointer to a structure containing the arguments */
411 } args
= { addr
, length
, prot
, flags
, fd
, offset
};
412 return (void *) syscall(SYS_mmap
, &args
);
415 return (void *) syscall(SYS_mmap2
, addr
, length
, prot
, flags
,
418 return (void *) syscall(SYS_mmap
, addr
, length
, prot
, flags
,
424 #define munmap(a, l) syscall(SYS_munmap, a, l)
428 #ifdef MOZ_MEMORY_DARWIN
429 static const bool __isthreaded
= true;
432 #if defined(MOZ_MEMORY_SOLARIS) && defined(MAP_ALIGN) && !defined(JEMALLOC_NEVER_USES_MAP_ALIGN)
433 #define JEMALLOC_USES_MAP_ALIGN /* Required on Solaris 10. Might improve performance elsewhere. */
436 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
437 #define JEMALLOC_USES_MAP_ALIGN /* Required for Windows CE < 6 */
440 #define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var))
442 #ifdef MOZ_MEMORY_WINDOWS
443 /* MSVC++ does not support C99 variable-length arrays. */
444 # define RB_NO_C99_VARARRAYS
446 #include "jemalloc_rb.h"
449 /* Disable inlining to make debugging easier. */
457 /* Size of stack-allocated buffer passed to strerror_r(). */
458 #define STRERROR_BUF 64
460 /* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
461 # define QUANTUM_2POW_MIN 4
462 #ifdef MOZ_MEMORY_SIZEOF_PTR_2POW
463 # define SIZEOF_PTR_2POW MOZ_MEMORY_SIZEOF_PTR_2POW
465 # define SIZEOF_PTR_2POW 2
470 #ifndef MOZ_MEMORY_DARWIN
471 static const bool __isthreaded
= true;
477 # define QUANTUM_2POW_MIN 4
478 # define SIZEOF_PTR_2POW 2
479 # define CPU_SPINWAIT __asm__ volatile("pause")
482 # define QUANTUM_2POW_MIN 4
483 # define SIZEOF_PTR_2POW 3
486 # define QUANTUM_2POW_MIN 4
487 # define SIZEOF_PTR_2POW 3
491 # define QUANTUM_2POW_MIN 4
492 # define SIZEOF_PTR_2POW 3
496 # define QUANTUM_2POW_MIN 4
497 # define SIZEOF_PTR_2POW 3
498 # define CPU_SPINWAIT __asm__ volatile("pause")
501 # define QUANTUM_2POW_MIN 3
502 # define SIZEOF_PTR_2POW 2
506 # define QUANTUM_2POW_MIN 3
507 # define SIZEOF_PTR_2POW 2
511 # define QUANTUM_2POW_MIN 4
512 # define SIZEOF_PTR_2POW 2
516 #define SIZEOF_PTR (1U << SIZEOF_PTR_2POW)
518 /* sizeof(int) == (1U << SIZEOF_INT_2POW). */
519 #ifndef SIZEOF_INT_2POW
520 # define SIZEOF_INT_2POW 2
523 /* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
524 #if (!defined(PIC) && !defined(NO_TLS))
529 /* MALLOC_BALANCE requires TLS. */
530 # ifdef MALLOC_BALANCE
531 # undef MALLOC_BALANCE
536 * Size and alignment of memory chunks that are allocated by the OS's virtual
539 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
540 #define CHUNK_2POW_DEFAULT 21
542 #define CHUNK_2POW_DEFAULT 20
544 /* Maximum number of dirty pages per arena. */
545 #define DIRTY_MAX_DEFAULT (1U << 10)
548 * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
549 * so over-estimates are okay (up to a point), but under-estimates will
550 * negatively affect performance.
552 #define CACHELINE_2POW 6
553 #define CACHELINE ((size_t)(1U << CACHELINE_2POW))
555 /* Smallest size class to support. */
556 #define TINY_MIN_2POW 1
559 * Maximum size class that is a multiple of the quantum, but not (necessarily)
560 * a power of 2. Above this size, allocations are rounded up to the nearest
563 #define SMALL_MAX_2POW_DEFAULT 9
564 #define SMALL_MAX_DEFAULT (1U << SMALL_MAX_2POW_DEFAULT)
567 * RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized
568 * as small as possible such that this setting is still honored, without
569 * violating other constraints. The goal is to make runs as small as possible
570 * without exceeding a per run external fragmentation threshold.
572 * We use binary fixed point math for overhead computations, where the binary
573 * point is implicitly RUN_BFP bits to the left.
575 * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
576 * honored for some/all object sizes, since there is one bit of header overhead
577 * per object (plus a constant). This constraint is relaxed (ignored) for runs
578 * that are so small that the per-region overhead is greater than:
580 * (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
583 /* \/ Implicit binary fixed point. */
584 #define RUN_MAX_OVRHD 0x0000003dU
585 #define RUN_MAX_OVRHD_RELAX 0x00001800U
587 /* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */
588 #define RUN_MAX_SMALL_2POW 15
589 #define RUN_MAX_SMALL (1U << RUN_MAX_SMALL_2POW)
592 * Hyper-threaded CPUs may need a special instruction inside spin loops in
593 * order to yield to another virtual CPU. If no such instruction is defined
594 * above, make CPU_SPINWAIT a no-op.
597 # define CPU_SPINWAIT
601 * Adaptive spinning must eventually switch to blocking, in order to avoid the
602 * potential for priority inversion deadlock. Backing off past a certain point
603 * can actually waste time.
605 #define SPIN_LIMIT_2POW 11
608 * Conversion from spinning to blocking is expensive; we use (1U <<
609 * BLOCK_COST_2POW) to estimate how many more times costly blocking is than
610 * worst-case spinning.
612 #define BLOCK_COST_2POW 4
614 #ifdef MALLOC_BALANCE
616 * We use an exponential moving average to track recent lock contention,
617 * where the size of the history window is N, and alpha=2/(N+1).
619 * Due to integer math rounding, very small values here can cause
620 * substantial degradation in accuracy, thus making the moving average decay
621 * faster than it would with precise calculation.
623 # define BALANCE_ALPHA_INV_2POW 9
626 * Threshold value for the exponential moving contention average at which to
627 * re-assign a thread.
629 # define BALANCE_THRESHOLD_DEFAULT (1U << (SPIN_LIMIT_2POW-4))
632 /******************************************************************************/
635 * Mutexes based on spinlocks. We can't use normal pthread spinlocks in all
636 * places, because they require malloc()ed memory, which causes bootstrapping
637 * issues in some cases.
639 #if defined(MOZ_MEMORY_WINDOWS)
640 #define malloc_mutex_t CRITICAL_SECTION
641 #define malloc_spinlock_t CRITICAL_SECTION
642 #elif defined(MOZ_MEMORY_DARWIN)
649 #elif defined(MOZ_MEMORY)
650 typedef pthread_mutex_t malloc_mutex_t
;
651 typedef pthread_mutex_t malloc_spinlock_t
;
653 /* XXX these should #ifdef these for freebsd (and linux?) only */
657 typedef malloc_spinlock_t malloc_mutex_t
;
660 /* Set to true once the allocator has been initialized. */
661 static bool malloc_initialized
= false;
663 #if defined(MOZ_MEMORY_WINDOWS)
664 /* No init lock for Windows. */
665 #elif defined(MOZ_MEMORY_DARWIN)
666 static malloc_mutex_t init_lock
= {OS_SPINLOCK_INIT
};
667 #elif defined(MOZ_MEMORY_LINUX) && !defined(MOZ_MEMORY_ANDROID)
668 static malloc_mutex_t init_lock
= PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
;
669 #elif defined(MOZ_MEMORY)
670 static malloc_mutex_t init_lock
= PTHREAD_MUTEX_INITIALIZER
;
672 static malloc_mutex_t init_lock
= {_SPINLOCK_INITIALIZER
};
675 /******************************************************************************/
677 * Statistics data structures.
682 typedef struct malloc_bin_stats_s malloc_bin_stats_t
;
683 struct malloc_bin_stats_s
{
685 * Number of allocation requests that corresponded to the size of this
690 /* Total number of runs created for this bin's size class. */
694 * Total number of runs reused by extracting them from the runs tree for
695 * this bin's size class.
699 /* High-water mark for this bin. */
700 unsigned long highruns
;
702 /* Current number of runs in this bin. */
703 unsigned long curruns
;
706 typedef struct arena_stats_s arena_stats_t
;
707 struct arena_stats_s
{
708 /* Number of bytes currently mapped. */
712 * Total number of purge sweeps, total number of madvise calls made,
713 * and total pages purged in order to keep dirty unused memory under
719 #ifdef MALLOC_DECOMMIT
721 * Total number of decommit/commit operations, and total number of
726 uint64_t decommitted
;
728 /* Current number of committed pages. */
732 /* Per-size-category statistics. */
733 size_t allocated_small
;
734 uint64_t nmalloc_small
;
735 uint64_t ndalloc_small
;
737 size_t allocated_large
;
738 uint64_t nmalloc_large
;
739 uint64_t ndalloc_large
;
741 #ifdef MALLOC_BALANCE
742 /* Number of times this arena reassigned a thread due to contention. */
747 typedef struct chunk_stats_s chunk_stats_t
;
748 struct chunk_stats_s
{
749 /* Number of chunks that were allocated. */
752 /* High-water mark for number of chunks allocated. */
753 unsigned long highchunks
;
756 * Current number of chunks allocated. This value isn't maintained for
757 * any other purpose, so keep track of it in order to be able to set
760 unsigned long curchunks
;
763 #endif /* #ifdef MALLOC_STATS */
765 /******************************************************************************/
767 * Extent data structures.
770 /* Tree of extents. */
771 typedef struct extent_node_s extent_node_t
;
772 struct extent_node_s
{
773 /* Linkage for the size/address-ordered tree. */
774 rb_node(extent_node_t
) link_szad
;
776 /* Linkage for the address-ordered tree. */
777 rb_node(extent_node_t
) link_ad
;
779 /* Pointer to the extent that this tree node is responsible for. */
782 /* Total region size. */
785 typedef rb_tree(extent_node_t
) extent_tree_t
;
787 /******************************************************************************/
789 * Radix tree data structures.
792 #ifdef MALLOC_VALIDATE
794 * Size of each radix tree node (must be a power of 2). This impacts tree
797 # if (SIZEOF_PTR == 4)
798 # define MALLOC_RTREE_NODESIZE (1U << 14)
800 # define MALLOC_RTREE_NODESIZE CACHELINE
803 typedef struct malloc_rtree_s malloc_rtree_t
;
804 struct malloc_rtree_s
{
805 malloc_spinlock_t lock
;
808 unsigned level2bits
[1]; /* Dynamically sized. */
812 /******************************************************************************/
814 * Arena data structures.
817 typedef struct arena_s arena_t
;
818 typedef struct arena_bin_s arena_bin_t
;
820 /* Each element of the chunk map corresponds to one page within the chunk. */
821 typedef struct arena_chunk_map_s arena_chunk_map_t
;
822 struct arena_chunk_map_s
{
824 * Linkage for run trees. There are two disjoint uses:
826 * 1) arena_t's runs_avail tree.
827 * 2) arena_run_t conceptually uses this linkage for in-use non-full
828 * runs, rather than directly embedding linkage.
830 rb_node(arena_chunk_map_t
) link
;
833 * Run address (or size) and various flags are stored together. The bit
834 * layout looks like (assuming 32-bit system):
836 * ???????? ???????? ????---- --ckdzla
838 * ? : Unallocated: Run address for first/last pages, unset for internal
840 * Small: Run address.
841 * Large: Run size for first page, unset for trailing pages.
850 * Following are example bit patterns for the three types of runs.
859 * ssssssss ssssssss ssss---- --c-----
860 * xxxxxxxx xxxxxxxx xxxx---- ----d---
861 * ssssssss ssssssss ssss---- -----z--
864 * rrrrrrrr rrrrrrrr rrrr---- -------a
865 * rrrrrrrr rrrrrrrr rrrr---- -------a
866 * rrrrrrrr rrrrrrrr rrrr---- -------a
869 * ssssssss ssssssss ssss---- ------la
870 * -------- -------- -------- ------la
871 * -------- -------- -------- ------la
874 #ifdef MALLOC_DECOMMIT
875 #define CHUNK_MAP_DECOMMITTED ((size_t)0x20U)
877 #define CHUNK_MAP_KEY ((size_t)0x10U)
878 #define CHUNK_MAP_DIRTY ((size_t)0x08U)
879 #define CHUNK_MAP_ZEROED ((size_t)0x04U)
880 #define CHUNK_MAP_LARGE ((size_t)0x02U)
881 #define CHUNK_MAP_ALLOCATED ((size_t)0x01U)
883 typedef rb_tree(arena_chunk_map_t
) arena_avail_tree_t
;
884 typedef rb_tree(arena_chunk_map_t
) arena_run_tree_t
;
886 /* Arena chunk header. */
887 typedef struct arena_chunk_s arena_chunk_t
;
888 struct arena_chunk_s
{
889 /* Arena that owns the chunk. */
892 /* Linkage for the arena's chunks_dirty tree. */
893 rb_node(arena_chunk_t
) link_dirty
;
895 /* Number of dirty pages. */
898 /* Map of pages within chunk that keeps track of free/large/small. */
899 arena_chunk_map_t map
[1]; /* Dynamically sized. */
901 typedef rb_tree(arena_chunk_t
) arena_chunk_tree_t
;
903 typedef struct arena_run_s arena_run_t
;
907 # define ARENA_RUN_MAGIC 0x384adf93
910 /* Bin this run is associated with. */
913 /* Index of first element that might have a free region. */
914 unsigned regs_minelm
;
916 /* Number of free regions in run. */
919 /* Bitmask of in-use regions (0: in use, 1: free). */
920 unsigned regs_mask
[1]; /* Dynamically sized. */
925 * Current run being used to service allocations of this bin's size
931 * Tree of non-full runs. This tree is used when looking for an
932 * existing run when runcur is no longer usable. We choose the
933 * non-full run that is lowest in memory; this policy tends to keep
934 * objects packed well, and it can also help reduce the number of
935 * almost-empty chunks.
937 arena_run_tree_t runs
;
939 /* Size of regions in a run for this bin's size class. */
942 /* Total size of a run for this bin's size class. */
945 /* Total number of regions in a run for this bin's size class. */
948 /* Number of elements in a run's regs_mask for this bin's size class. */
949 uint32_t regs_mask_nelms
;
951 /* Offset of first region in a run for this bin's size class. */
952 uint32_t reg0_offset
;
955 /* Bin statistics. */
956 malloc_bin_stats_t stats
;
963 # define ARENA_MAGIC 0x947d3d24
966 /* All operations on this arena require that lock be locked. */
968 malloc_spinlock_t lock
;
970 pthread_mutex_t lock
;
977 /* Tree of dirty-page-containing chunks this arena manages. */
978 arena_chunk_tree_t chunks_dirty
;
981 * In order to avoid rapid chunk allocation/deallocation when an arena
982 * oscillates right on the cusp of needing a new chunk, cache the most
983 * recently freed chunk. The spare is left in the arena's chunk trees
984 * until it is deleted.
986 * There is one spare chunk per arena, rather than one spare total, in
987 * order to avoid interactions between multiple threads that could make
988 * a single spare inadequate.
990 arena_chunk_t
*spare
;
993 * Current count of pages within unused runs that are potentially
994 * dirty, and for which madvise(... MADV_FREE) has not been called. By
995 * tracking this, we can institute a limit on how much dirty unused
996 * memory is mapped for each arena.
1001 * Size/address-ordered tree of this arena's available runs. This tree
1002 * is used for first-best-fit run allocation.
1004 arena_avail_tree_t runs_avail
;
1006 #ifdef MALLOC_BALANCE
1008 * The arena load balancing machinery needs to keep track of how much
1009 * lock contention there is. This value is exponentially averaged.
1011 uint32_t contention
;
1015 * bins is used to store rings of free regions of the following sizes,
1016 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
1037 arena_bin_t bins
[1]; /* Dynamically sized. */
1040 /******************************************************************************/
1045 #ifndef MOZ_MEMORY_NARENAS_DEFAULT_ONE
1046 /* Number of CPUs. */
1047 static unsigned ncpus
;
1051 static size_t pagesize
;
1052 static size_t pagesize_mask
;
1053 static size_t pagesize_2pow
;
1055 /* Various bin-related settings. */
1056 static size_t bin_maxclass
; /* Max size class for bins. */
1057 static unsigned ntbins
; /* Number of (2^n)-spaced tiny bins. */
1058 static unsigned nqbins
; /* Number of quantum-spaced bins. */
1059 static unsigned nsbins
; /* Number of (2^n)-spaced sub-page bins. */
1060 static size_t small_min
;
1061 static size_t small_max
;
1063 /* Various quantum-related settings. */
1064 static size_t quantum
;
1065 static size_t quantum_mask
; /* (quantum - 1). */
1067 /* Various chunk-related settings. */
1068 static size_t chunksize
;
1069 static size_t chunksize_mask
; /* (chunksize - 1). */
1070 static size_t chunk_npages
;
1071 static size_t arena_chunk_header_npages
;
1072 static size_t arena_maxclass
; /* Max size class for arenas. */
1079 #ifdef MALLOC_VALIDATE
1080 static malloc_rtree_t
*chunk_rtree
;
1083 /* Protects chunk-related data structures. */
1084 static malloc_mutex_t huge_mtx
;
1086 /* Tree of chunks that are stand-alone huge allocations. */
1087 static extent_tree_t huge
;
1090 /* Huge allocation statistics. */
1091 static uint64_t huge_nmalloc
;
1092 static uint64_t huge_ndalloc
;
1093 static size_t huge_allocated
;
1096 #ifdef MALLOC_PAGEFILE
1097 static char pagefile_templ
[PATH_MAX
];
1100 /****************************/
1102 * base (internal allocation).
1106 * Current pages that are being used for internal memory allocations. These
1107 * pages are carved up in cacheline-size quanta, so that there is no chance of
1108 * false cache line sharing.
1110 static void *base_pages
;
1111 static void *base_next_addr
;
1112 #ifdef MALLOC_DECOMMIT
1113 static void *base_next_decommitted
;
1115 static void *base_past_addr
; /* Addr immediately past base_pages. */
1116 static extent_node_t
*base_nodes
;
1117 static malloc_mutex_t base_mtx
;
1119 static size_t base_mapped
;
1120 # ifdef MALLOC_DECOMMIT
1121 static size_t base_committed
;
1131 * Arenas that are used to service external requests. Not all elements of the
1132 * arenas array are necessarily used; arenas are created lazily as needed.
1134 static arena_t
**arenas
;
1135 static unsigned narenas
;
1137 # ifdef MALLOC_BALANCE
1138 static unsigned narenas_2pow
;
1140 static unsigned next_arena
;
1144 static malloc_spinlock_t arenas_lock
; /* Protects arenas initialization. */
1146 static pthread_mutex_t arenas_lock
; /* Protects arenas initialization. */
1151 * Map of pthread_self() --> arenas[???], used for selecting an arena to use
1154 #ifndef MOZ_MEMORY_WINDOWS
1155 static __thread arena_t
*arenas_map
;
1160 /* Chunk statistics. */
1161 static chunk_stats_t stats_chunks
;
1164 /*******************************/
1166 * Runtime configuration options.
1168 const char *_malloc_options
;
1170 #ifndef MALLOC_PRODUCTION
1171 static bool opt_abort
= true;
1173 static bool opt_junk
= true;
1176 static bool opt_abort
= false;
1178 static bool opt_junk
= false;
1181 static size_t opt_dirty_max
= DIRTY_MAX_DEFAULT
;
1182 #ifdef MALLOC_BALANCE
1183 static uint64_t opt_balance_threshold
= BALANCE_THRESHOLD_DEFAULT
;
1185 static bool opt_print_stats
= false;
1186 static size_t opt_quantum_2pow
= QUANTUM_2POW_MIN
;
1187 static size_t opt_small_max_2pow
= SMALL_MAX_2POW_DEFAULT
;
1188 static size_t opt_chunk_2pow
= CHUNK_2POW_DEFAULT
;
1189 #ifdef MALLOC_PAGEFILE
1190 static bool opt_pagefile
= false;
1192 #ifdef MALLOC_UTRACE
1193 static bool opt_utrace
= false;
1196 static bool opt_sysv
= false;
1198 #ifdef MALLOC_XMALLOC
1199 static bool opt_xmalloc
= false;
1202 static bool opt_zero
= false;
1204 static int opt_narenas_lshift
= 0;
1206 #ifdef MALLOC_UTRACE
1213 #define UTRACE(a, b, c) \
1215 malloc_utrace_t ut; \
1219 utrace(&ut, sizeof(ut)); \
1222 #define UTRACE(a, b, c)
1225 /******************************************************************************/
1227 * Begin function prototypes for non-inline static functions.
1230 static char *umax2s(uintmax_t x
, char *s
);
1231 static bool malloc_mutex_init(malloc_mutex_t
*mutex
);
1232 static bool malloc_spin_init(malloc_spinlock_t
*lock
);
1233 static void wrtmessage(const char *p1
, const char *p2
, const char *p3
,
1236 #ifdef MOZ_MEMORY_DARWIN
1237 /* Avoid namespace collision with OS X's malloc APIs. */
1238 #define malloc_printf moz_malloc_printf
1240 static void malloc_printf(const char *format
, ...);
1242 static bool base_pages_alloc_mmap(size_t minsize
);
1243 static bool base_pages_alloc(size_t minsize
);
1244 static void *base_alloc(size_t size
);
1245 static void *base_calloc(size_t number
, size_t size
);
1246 static extent_node_t
*base_node_alloc(void);
1247 static void base_node_dealloc(extent_node_t
*node
);
1249 static void stats_print(arena_t
*arena
);
1251 static void *pages_map(void *addr
, size_t size
, int pfd
);
1252 static void pages_unmap(void *addr
, size_t size
);
1253 static void *chunk_alloc_mmap(size_t size
, bool pagefile
);
1254 #ifdef MALLOC_PAGEFILE
1255 static int pagefile_init(size_t size
);
1256 static void pagefile_close(int pfd
);
1258 static void *chunk_alloc(size_t size
, bool zero
, bool pagefile
);
1259 static void chunk_dealloc_mmap(void *chunk
, size_t size
);
1260 static void chunk_dealloc(void *chunk
, size_t size
);
1262 static arena_t
*choose_arena_hard(void);
1264 static void arena_run_split(arena_t
*arena
, arena_run_t
*run
, size_t size
,
1265 bool large
, bool zero
);
1266 static void arena_chunk_init(arena_t
*arena
, arena_chunk_t
*chunk
);
1267 static void arena_chunk_dealloc(arena_t
*arena
, arena_chunk_t
*chunk
);
1268 static arena_run_t
*arena_run_alloc(arena_t
*arena
, arena_bin_t
*bin
,
1269 size_t size
, bool large
, bool zero
);
1270 static void arena_purge(arena_t
*arena
);
1271 static void arena_run_dalloc(arena_t
*arena
, arena_run_t
*run
, bool dirty
);
1272 static void arena_run_trim_head(arena_t
*arena
, arena_chunk_t
*chunk
,
1273 arena_run_t
*run
, size_t oldsize
, size_t newsize
);
1274 static void arena_run_trim_tail(arena_t
*arena
, arena_chunk_t
*chunk
,
1275 arena_run_t
*run
, size_t oldsize
, size_t newsize
, bool dirty
);
1276 static arena_run_t
*arena_bin_nonfull_run_get(arena_t
*arena
, arena_bin_t
*bin
);
1277 static void *arena_bin_malloc_hard(arena_t
*arena
, arena_bin_t
*bin
);
1278 static size_t arena_bin_run_size_calc(arena_bin_t
*bin
, size_t min_run_size
);
1279 #ifdef MALLOC_BALANCE
1280 static void arena_lock_balance_hard(arena_t
*arena
);
1282 static void *arena_malloc_large(arena_t
*arena
, size_t size
, bool zero
);
1283 static void *arena_palloc(arena_t
*arena
, size_t alignment
, size_t size
,
1285 static size_t arena_salloc(const void *ptr
);
1286 static void arena_dalloc_large(arena_t
*arena
, arena_chunk_t
*chunk
,
1288 static void arena_ralloc_large_shrink(arena_t
*arena
, arena_chunk_t
*chunk
,
1289 void *ptr
, size_t size
, size_t oldsize
);
1290 static bool arena_ralloc_large_grow(arena_t
*arena
, arena_chunk_t
*chunk
,
1291 void *ptr
, size_t size
, size_t oldsize
);
1292 static bool arena_ralloc_large(void *ptr
, size_t size
, size_t oldsize
);
1293 static void *arena_ralloc(void *ptr
, size_t size
, size_t oldsize
);
1294 static bool arena_new(arena_t
*arena
);
1295 static arena_t
*arenas_extend(unsigned ind
);
1296 static void *huge_malloc(size_t size
, bool zero
);
1297 static void *huge_palloc(size_t alignment
, size_t size
);
1298 static void *huge_ralloc(void *ptr
, size_t size
, size_t oldsize
);
1299 static void huge_dalloc(void *ptr
);
1300 static void malloc_print_stats(void);
1301 #ifndef MOZ_MEMORY_WINDOWS
1304 bool malloc_init_hard(void);
1306 void _malloc_prefork(void);
1307 void _malloc_postfork(void);
1310 * End function prototypes.
1312 /******************************************************************************/
1315 * umax2s() provides minimal integer printing functionality, which is
1316 * especially useful for situations where allocation in vsnprintf() calls would
1317 * potentially cause deadlock.
1319 #define UMAX2S_BUFSIZE 21
1321 umax2s(uintmax_t x
, char *s
)
1325 i
= UMAX2S_BUFSIZE
- 1;
1329 s
[i
] = "0123456789"[x
% 10];
1337 wrtmessage(const char *p1
, const char *p2
, const char *p3
, const char *p4
)
1339 #ifdef MOZ_MEMORY_WINCE
1341 #define WRT_PRINT(s) \
1342 MultiByteToWideChar(CP_ACP, 0, s, -1, buf, 1024); \
1343 OutputDebugStringW(buf)
1350 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_WINDOWS)
1351 #define _write write
1353 _write(STDERR_FILENO
, p1
, (unsigned int) strlen(p1
));
1354 _write(STDERR_FILENO
, p2
, (unsigned int) strlen(p2
));
1355 _write(STDERR_FILENO
, p3
, (unsigned int) strlen(p3
));
1356 _write(STDERR_FILENO
, p4
, (unsigned int) strlen(p4
));
1361 #define _malloc_message malloc_message
1363 void (*_malloc_message
)(const char *p1
, const char *p2
, const char *p3
,
1364 const char *p4
) = wrtmessage
;
1367 # define assert(e) do { \
1369 char line_buf[UMAX2S_BUFSIZE]; \
1370 _malloc_message(__FILE__, ":", umax2s(__LINE__, \
1371 line_buf), ": Failed assertion: "); \
1372 _malloc_message("\"", #e, "\"\n", ""); \
1380 /******************************************************************************/
1382 * Begin mutex. We can't use normal pthread mutexes in all places, because
1383 * they require malloc()ed memory, which causes bootstrapping issues in some
1388 malloc_mutex_init(malloc_mutex_t
*mutex
)
1390 #if defined(MOZ_MEMORY_WINCE)
1391 InitializeCriticalSection(mutex
);
1392 #elif defined(MOZ_MEMORY_WINDOWS)
1394 if (! __crtInitCritSecAndSpinCount(mutex
, _CRT_SPINCOUNT
))
1396 #elif defined(MOZ_MEMORY_DARWIN)
1397 mutex
->lock
= OS_SPINLOCK_INIT
;
1398 #elif defined(MOZ_MEMORY_LINUX) && !defined(MOZ_MEMORY_ANDROID)
1399 pthread_mutexattr_t attr
;
1400 if (pthread_mutexattr_init(&attr
) != 0)
1402 pthread_mutexattr_settype(&attr
, PTHREAD_MUTEX_ADAPTIVE_NP
);
1403 if (pthread_mutex_init(mutex
, &attr
) != 0) {
1404 pthread_mutexattr_destroy(&attr
);
1407 pthread_mutexattr_destroy(&attr
);
1408 #elif defined(MOZ_MEMORY)
1409 if (pthread_mutex_init(mutex
, NULL
) != 0)
1412 static const spinlock_t lock
= _SPINLOCK_INITIALIZER
;
1420 malloc_mutex_lock(malloc_mutex_t
*mutex
)
1423 #if defined(MOZ_MEMORY_WINDOWS)
1424 EnterCriticalSection(mutex
);
1425 #elif defined(MOZ_MEMORY_DARWIN)
1426 OSSpinLockLock(&mutex
->lock
);
1427 #elif defined(MOZ_MEMORY)
1428 pthread_mutex_lock(mutex
);
1431 _SPINLOCK(&mutex
->lock
);
1436 malloc_mutex_unlock(malloc_mutex_t
*mutex
)
1439 #if defined(MOZ_MEMORY_WINDOWS)
1440 LeaveCriticalSection(mutex
);
1441 #elif defined(MOZ_MEMORY_DARWIN)
1442 OSSpinLockUnlock(&mutex
->lock
);
1443 #elif defined(MOZ_MEMORY)
1444 pthread_mutex_unlock(mutex
);
1447 _SPINUNLOCK(&mutex
->lock
);
1452 malloc_spin_init(malloc_spinlock_t
*lock
)
1454 #if defined(MOZ_MEMORY_WINCE)
1455 InitializeCriticalSection(lock
);
1456 #elif defined(MOZ_MEMORY_WINDOWS)
1458 if (! __crtInitCritSecAndSpinCount(lock
, _CRT_SPINCOUNT
))
1460 #elif defined(MOZ_MEMORY_DARWIN)
1461 lock
->lock
= OS_SPINLOCK_INIT
;
1462 #elif defined(MOZ_MEMORY_LINUX) && !defined(MOZ_MEMORY_ANDROID)
1463 pthread_mutexattr_t attr
;
1464 if (pthread_mutexattr_init(&attr
) != 0)
1466 pthread_mutexattr_settype(&attr
, PTHREAD_MUTEX_ADAPTIVE_NP
);
1467 if (pthread_mutex_init(lock
, &attr
) != 0) {
1468 pthread_mutexattr_destroy(&attr
);
1471 pthread_mutexattr_destroy(&attr
);
1472 #elif defined(MOZ_MEMORY)
1473 if (pthread_mutex_init(lock
, NULL
) != 0)
1476 lock
->lock
= _SPINLOCK_INITIALIZER
;
1482 malloc_spin_lock(malloc_spinlock_t
*lock
)
1485 #if defined(MOZ_MEMORY_WINDOWS)
1486 EnterCriticalSection(lock
);
1487 #elif defined(MOZ_MEMORY_DARWIN)
1488 OSSpinLockLock(&lock
->lock
);
1489 #elif defined(MOZ_MEMORY)
1490 pthread_mutex_lock(lock
);
1493 _SPINLOCK(&lock
->lock
);
1498 malloc_spin_unlock(malloc_spinlock_t
*lock
)
1500 #if defined(MOZ_MEMORY_WINDOWS)
1501 LeaveCriticalSection(lock
);
1502 #elif defined(MOZ_MEMORY_DARWIN)
1503 OSSpinLockUnlock(&lock
->lock
);
1504 #elif defined(MOZ_MEMORY)
1505 pthread_mutex_unlock(lock
);
1508 _SPINUNLOCK(&lock
->lock
);
1515 /******************************************************************************/
1517 * Begin spin lock. Spin locks here are actually adaptive mutexes that block
1518 * after a period of spinning, because unbounded spinning would allow for
1519 * priority inversion.
1522 #if defined(MOZ_MEMORY) && !defined(MOZ_MEMORY_DARWIN)
1523 # define malloc_spin_init malloc_mutex_init
1524 # define malloc_spin_lock malloc_mutex_lock
1525 # define malloc_spin_unlock malloc_mutex_unlock
1530 * We use an unpublished interface to initialize pthread mutexes with an
1531 * allocation callback, in order to avoid infinite recursion.
1533 int _pthread_mutex_init_calloc_cb(pthread_mutex_t
*mutex
,
1534 void *(calloc_cb
)(size_t, size_t));
1536 __weak_reference(_pthread_mutex_init_calloc_cb_stub
,
1537 _pthread_mutex_init_calloc_cb
);
1540 _pthread_mutex_init_calloc_cb_stub(pthread_mutex_t
*mutex
,
1541 void *(calloc_cb
)(size_t, size_t))
1548 malloc_spin_init(pthread_mutex_t
*lock
)
1551 if (_pthread_mutex_init_calloc_cb(lock
, base_calloc
) != 0)
1557 static inline unsigned
1558 malloc_spin_lock(pthread_mutex_t
*lock
)
1563 if (_pthread_mutex_trylock(lock
) != 0) {
1565 volatile unsigned j
;
1567 /* Exponentially back off. */
1568 for (i
= 1; i
<= SPIN_LIMIT_2POW
; i
++) {
1569 for (j
= 0; j
< (1U << i
); j
++)
1573 if (_pthread_mutex_trylock(lock
) == 0)
1578 * Spinning failed. Block until the lock becomes
1579 * available, in order to avoid indefinite priority
1582 _pthread_mutex_lock(lock
);
1583 assert((ret
<< BLOCK_COST_2POW
) != 0);
1584 return (ret
<< BLOCK_COST_2POW
);
1592 malloc_spin_unlock(pthread_mutex_t
*lock
)
1596 _pthread_mutex_unlock(lock
);
1603 /******************************************************************************/
1605 * Begin Utility functions/macros.
1608 /* Return the chunk address for allocation address a. */
1609 #define CHUNK_ADDR2BASE(a) \
1610 ((void *)((uintptr_t)(a) & ~chunksize_mask))
1612 /* Return the chunk offset of address a. */
1613 #define CHUNK_ADDR2OFFSET(a) \
1614 ((size_t)((uintptr_t)(a) & chunksize_mask))
1616 /* Return the smallest chunk multiple that is >= s. */
1617 #define CHUNK_CEILING(s) \
1618 (((s) + chunksize_mask) & ~chunksize_mask)
1620 /* Return the smallest cacheline multiple that is >= s. */
1621 #define CACHELINE_CEILING(s) \
1622 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
1624 /* Return the smallest quantum multiple that is >= a. */
1625 #define QUANTUM_CEILING(a) \
1626 (((a) + quantum_mask) & ~quantum_mask)
1628 /* Return the smallest pagesize multiple that is >= s. */
1629 #define PAGE_CEILING(s) \
1630 (((s) + pagesize_mask) & ~pagesize_mask)
1632 /* Compute the smallest power of 2 that is >= x. */
1633 static inline size_t
1643 #if (SIZEOF_PTR == 8)
1650 #ifdef MALLOC_BALANCE
1652 * Use a simple linear congruential pseudo-random number generator:
1654 * prn(y) = (a*x + c) % m
1656 * where the following constants ensure maximal period:
1658 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4.
1659 * c == Odd number (relatively prime to 2^n).
1662 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints.
1664 * This choice of m has the disadvantage that the quality of the bits is
1665 * proportional to bit position. For example. the lowest bit has a cycle of 2,
1666 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper
1669 # define PRN_DEFINE(suffix, var, a, c) \
1670 static inline void \
1671 sprn_##suffix(uint32_t seed) \
1676 static inline uint32_t \
1677 prn_##suffix(uint32_t lg_range) \
1681 assert(lg_range > 0); \
1682 assert(lg_range <= 32); \
1684 x = (var * (a)) + (c); \
1686 ret = x >> (32 - lg_range); \
1690 # define SPRN(suffix, seed) sprn_##suffix(seed)
1691 # define PRN(suffix, lg_range) prn_##suffix(lg_range)
1694 #ifdef MALLOC_BALANCE
1695 /* Define the PRNG used for arena assignment. */
1696 static __thread
uint32_t balance_x
;
1697 PRN_DEFINE(balance
, balance_x
, 1297, 1301)
1700 #ifdef MALLOC_UTRACE
1702 utrace(const void *addr
, size_t len
)
1704 malloc_utrace_t
*ut
= (malloc_utrace_t
*)addr
;
1706 assert(len
== sizeof(malloc_utrace_t
));
1708 if (ut
->p
== NULL
&& ut
->s
== 0 && ut
->r
== NULL
)
1709 malloc_printf("%d x USER malloc_init()\n", getpid());
1710 else if (ut
->p
== NULL
&& ut
->r
!= NULL
) {
1711 malloc_printf("%d x USER %p = malloc(%zu)\n", getpid(), ut
->r
,
1713 } else if (ut
->p
!= NULL
&& ut
->r
!= NULL
) {
1714 malloc_printf("%d x USER %p = realloc(%p, %zu)\n", getpid(),
1715 ut
->r
, ut
->p
, ut
->s
);
1717 malloc_printf("%d x USER free(%p)\n", getpid(), ut
->p
);
1723 static inline const char *
1727 return ("<jemalloc>");
1732 * Print to stderr in such a way as to (hopefully) avoid memory allocation.
1735 malloc_printf(const char *format
, ...)
1741 va_start(ap
, format
);
1742 vsnprintf(buf
, sizeof(buf
), format
, ap
);
1744 _malloc_message(buf
, "", "", "");
1749 /******************************************************************************/
1751 #ifdef MALLOC_DECOMMIT
1753 pages_decommit(void *addr
, size_t size
)
1756 #ifdef MOZ_MEMORY_WINDOWS
1757 VirtualFree(addr
, size
, MEM_DECOMMIT
);
1759 if (mmap(addr
, size
, PROT_NONE
, MAP_FIXED
| MAP_PRIVATE
| MAP_ANON
, -1,
1766 pages_commit(void *addr
, size_t size
)
1769 # ifdef MOZ_MEMORY_WINDOWS
1770 VirtualAlloc(addr
, size
, MEM_COMMIT
, PAGE_READWRITE
);
1772 if (mmap(addr
, size
, PROT_READ
| PROT_WRITE
, MAP_FIXED
| MAP_PRIVATE
|
1773 MAP_ANON
, -1, 0) == MAP_FAILED
)
1780 base_pages_alloc_mmap(size_t minsize
)
1784 #ifdef MALLOC_DECOMMIT
1789 assert(minsize
!= 0);
1790 csize
= CHUNK_CEILING(minsize
);
1791 #ifdef MALLOC_PAGEFILE
1793 pfd
= pagefile_init(csize
);
1799 base_pages
= pages_map(NULL
, csize
, pfd
);
1800 if (base_pages
== NULL
) {
1804 base_next_addr
= base_pages
;
1805 base_past_addr
= (void *)((uintptr_t)base_pages
+ csize
);
1806 #ifdef MALLOC_DECOMMIT
1808 * Leave enough pages for minsize committed, since otherwise they would
1809 * have to be immediately recommitted.
1811 pminsize
= PAGE_CEILING(minsize
);
1812 base_next_decommitted
= (void *)((uintptr_t)base_pages
+ pminsize
);
1813 if (pminsize
< csize
)
1814 pages_decommit(base_next_decommitted
, csize
- pminsize
);
1817 base_mapped
+= csize
;
1818 # ifdef MALLOC_DECOMMIT
1819 base_committed
+= pminsize
;
1825 #ifdef MALLOC_PAGEFILE
1827 pagefile_close(pfd
);
1833 base_pages_alloc(size_t minsize
)
1836 if (base_pages_alloc_mmap(minsize
) == false)
1843 base_alloc(size_t size
)
1848 /* Round size up to nearest multiple of the cacheline size. */
1849 csize
= CACHELINE_CEILING(size
);
1851 malloc_mutex_lock(&base_mtx
);
1852 /* Make sure there's enough space for the allocation. */
1853 if ((uintptr_t)base_next_addr
+ csize
> (uintptr_t)base_past_addr
) {
1854 if (base_pages_alloc(csize
)) {
1855 malloc_mutex_unlock(&base_mtx
);
1860 ret
= base_next_addr
;
1861 base_next_addr
= (void *)((uintptr_t)base_next_addr
+ csize
);
1862 #ifdef MALLOC_DECOMMIT
1863 /* Make sure enough pages are committed for the new allocation. */
1864 if ((uintptr_t)base_next_addr
> (uintptr_t)base_next_decommitted
) {
1865 void *pbase_next_addr
=
1866 (void *)(PAGE_CEILING((uintptr_t)base_next_addr
));
1868 pages_commit(base_next_decommitted
, (uintptr_t)pbase_next_addr
-
1869 (uintptr_t)base_next_decommitted
);
1870 base_next_decommitted
= pbase_next_addr
;
1871 # ifdef MALLOC_STATS
1872 base_committed
+= (uintptr_t)pbase_next_addr
-
1873 (uintptr_t)base_next_decommitted
;
1877 malloc_mutex_unlock(&base_mtx
);
1878 VALGRIND_MALLOCLIKE_BLOCK(ret
, size
, 0, false);
1884 base_calloc(size_t number
, size_t size
)
1888 ret
= base_alloc(number
* size
);
1889 #ifdef MALLOC_VALGRIND
1891 VALGRIND_FREELIKE_BLOCK(ret
, 0);
1892 VALGRIND_MALLOCLIKE_BLOCK(ret
, size
, 0, true);
1895 memset(ret
, 0, number
* size
);
1900 static extent_node_t
*
1901 base_node_alloc(void)
1905 malloc_mutex_lock(&base_mtx
);
1906 if (base_nodes
!= NULL
) {
1908 base_nodes
= *(extent_node_t
**)ret
;
1909 VALGRIND_FREELIKE_BLOCK(ret
, 0);
1910 VALGRIND_MALLOCLIKE_BLOCK(ret
, sizeof(extent_node_t
), 0, false);
1911 malloc_mutex_unlock(&base_mtx
);
1913 malloc_mutex_unlock(&base_mtx
);
1914 ret
= (extent_node_t
*)base_alloc(sizeof(extent_node_t
));
1921 base_node_dealloc(extent_node_t
*node
)
1924 malloc_mutex_lock(&base_mtx
);
1925 VALGRIND_FREELIKE_BLOCK(node
, 0);
1926 VALGRIND_MALLOCLIKE_BLOCK(node
, sizeof(extent_node_t
*), 0, false);
1927 *(extent_node_t
**)node
= base_nodes
;
1929 malloc_mutex_unlock(&base_mtx
);
1932 /******************************************************************************/
1936 stats_print(arena_t
*arena
)
1938 unsigned i
, gap_start
;
1940 #ifdef MOZ_MEMORY_WINDOWS
1941 malloc_printf("dirty: %Iu page%s dirty, %I64u sweep%s,"
1942 " %I64u madvise%s, %I64u page%s purged\n",
1943 arena
->ndirty
, arena
->ndirty
== 1 ? "" : "s",
1944 arena
->stats
.npurge
, arena
->stats
.npurge
== 1 ? "" : "s",
1945 arena
->stats
.nmadvise
, arena
->stats
.nmadvise
== 1 ? "" : "s",
1946 arena
->stats
.purged
, arena
->stats
.purged
== 1 ? "" : "s");
1947 # ifdef MALLOC_DECOMMIT
1948 malloc_printf("decommit: %I64u decommit%s, %I64u commit%s,"
1949 " %I64u page%s decommitted\n",
1950 arena
->stats
.ndecommit
, (arena
->stats
.ndecommit
== 1) ? "" : "s",
1951 arena
->stats
.ncommit
, (arena
->stats
.ncommit
== 1) ? "" : "s",
1952 arena
->stats
.decommitted
,
1953 (arena
->stats
.decommitted
== 1) ? "" : "s");
1956 malloc_printf(" allocated nmalloc ndalloc\n");
1957 malloc_printf("small: %12Iu %12I64u %12I64u\n",
1958 arena
->stats
.allocated_small
, arena
->stats
.nmalloc_small
,
1959 arena
->stats
.ndalloc_small
);
1960 malloc_printf("large: %12Iu %12I64u %12I64u\n",
1961 arena
->stats
.allocated_large
, arena
->stats
.nmalloc_large
,
1962 arena
->stats
.ndalloc_large
);
1963 malloc_printf("total: %12Iu %12I64u %12I64u\n",
1964 arena
->stats
.allocated_small
+ arena
->stats
.allocated_large
,
1965 arena
->stats
.nmalloc_small
+ arena
->stats
.nmalloc_large
,
1966 arena
->stats
.ndalloc_small
+ arena
->stats
.ndalloc_large
);
1967 malloc_printf("mapped: %12Iu\n", arena
->stats
.mapped
);
1969 malloc_printf("dirty: %zu page%s dirty, %llu sweep%s,"
1970 " %llu madvise%s, %llu page%s purged\n",
1971 arena
->ndirty
, arena
->ndirty
== 1 ? "" : "s",
1972 arena
->stats
.npurge
, arena
->stats
.npurge
== 1 ? "" : "s",
1973 arena
->stats
.nmadvise
, arena
->stats
.nmadvise
== 1 ? "" : "s",
1974 arena
->stats
.purged
, arena
->stats
.purged
== 1 ? "" : "s");
1975 # ifdef MALLOC_DECOMMIT
1976 malloc_printf("decommit: %llu decommit%s, %llu commit%s,"
1977 " %llu page%s decommitted\n",
1978 arena
->stats
.ndecommit
, (arena
->stats
.ndecommit
== 1) ? "" : "s",
1979 arena
->stats
.ncommit
, (arena
->stats
.ncommit
== 1) ? "" : "s",
1980 arena
->stats
.decommitted
,
1981 (arena
->stats
.decommitted
== 1) ? "" : "s");
1984 malloc_printf(" allocated nmalloc ndalloc\n");
1985 malloc_printf("small: %12zu %12llu %12llu\n",
1986 arena
->stats
.allocated_small
, arena
->stats
.nmalloc_small
,
1987 arena
->stats
.ndalloc_small
);
1988 malloc_printf("large: %12zu %12llu %12llu\n",
1989 arena
->stats
.allocated_large
, arena
->stats
.nmalloc_large
,
1990 arena
->stats
.ndalloc_large
);
1991 malloc_printf("total: %12zu %12llu %12llu\n",
1992 arena
->stats
.allocated_small
+ arena
->stats
.allocated_large
,
1993 arena
->stats
.nmalloc_small
+ arena
->stats
.nmalloc_large
,
1994 arena
->stats
.ndalloc_small
+ arena
->stats
.ndalloc_large
);
1995 malloc_printf("mapped: %12zu\n", arena
->stats
.mapped
);
1997 malloc_printf("bins: bin size regs pgs requests newruns"
1998 " reruns maxruns curruns\n");
1999 for (i
= 0, gap_start
= UINT_MAX
; i
< ntbins
+ nqbins
+ nsbins
; i
++) {
2000 if (arena
->bins
[i
].stats
.nrequests
== 0) {
2001 if (gap_start
== UINT_MAX
)
2004 if (gap_start
!= UINT_MAX
) {
2005 if (i
> gap_start
+ 1) {
2006 /* Gap of more than one size class. */
2007 malloc_printf("[%u..%u]\n",
2010 /* Gap of one size class. */
2011 malloc_printf("[%u]\n", gap_start
);
2013 gap_start
= UINT_MAX
;
2016 #if defined(MOZ_MEMORY_WINDOWS)
2017 "%13u %1s %4u %4u %3u %9I64u %9I64u"
2018 " %9I64u %7u %7u\n",
2020 "%13u %1s %4u %4u %3u %9llu %9llu"
2021 " %9llu %7lu %7lu\n",
2024 i
< ntbins
? "T" : i
< ntbins
+ nqbins
? "Q" : "S",
2025 arena
->bins
[i
].reg_size
,
2026 arena
->bins
[i
].nregs
,
2027 arena
->bins
[i
].run_size
>> pagesize_2pow
,
2028 arena
->bins
[i
].stats
.nrequests
,
2029 arena
->bins
[i
].stats
.nruns
,
2030 arena
->bins
[i
].stats
.reruns
,
2031 arena
->bins
[i
].stats
.highruns
,
2032 arena
->bins
[i
].stats
.curruns
);
2035 if (gap_start
!= UINT_MAX
) {
2036 if (i
> gap_start
+ 1) {
2037 /* Gap of more than one size class. */
2038 malloc_printf("[%u..%u]\n", gap_start
, i
- 1);
2040 /* Gap of one size class. */
2041 malloc_printf("[%u]\n", gap_start
);
2048 * End Utility functions/macros.
2050 /******************************************************************************/
2052 * Begin extent tree code.
2056 extent_szad_comp(extent_node_t
*a
, extent_node_t
*b
)
2059 size_t a_size
= a
->size
;
2060 size_t b_size
= b
->size
;
2062 ret
= (a_size
> b_size
) - (a_size
< b_size
);
2064 uintptr_t a_addr
= (uintptr_t)a
->addr
;
2065 uintptr_t b_addr
= (uintptr_t)b
->addr
;
2067 ret
= (a_addr
> b_addr
) - (a_addr
< b_addr
);
2073 /* Wrap red-black tree macros in functions. */
2074 rb_wrap(static, extent_tree_szad_
, extent_tree_t
, extent_node_t
,
2075 link_szad
, extent_szad_comp
)
2078 extent_ad_comp(extent_node_t
*a
, extent_node_t
*b
)
2080 uintptr_t a_addr
= (uintptr_t)a
->addr
;
2081 uintptr_t b_addr
= (uintptr_t)b
->addr
;
2083 return ((a_addr
> b_addr
) - (a_addr
< b_addr
));
2086 /* Wrap red-black tree macros in functions. */
2087 rb_wrap(static, extent_tree_ad_
, extent_tree_t
, extent_node_t
, link_ad
,
2091 * End extent tree code.
2093 /******************************************************************************/
2095 * Begin chunk management functions.
2098 #ifdef MOZ_MEMORY_WINDOWS
2099 #ifdef MOZ_MEMORY_WINCE
2100 #define ALIGN_ADDR2OFFSET(al, ad) \
2101 ((uintptr_t)ad & (al - 1))
2103 pages_map_align(size_t size
, int pfd
, size_t alignment
)
2108 if (size
% alignment
)
2109 size
+= (alignment
- (size
% alignment
));
2110 assert(size
>= alignment
);
2111 ret
= pages_map(NULL
, size
, pfd
);
2112 offset
= ALIGN_ADDR2OFFSET(alignment
, ret
);
2114 /* try to over allocate by the ammount we're offset */
2116 pages_unmap(ret
, size
);
2117 tmp
= VirtualAlloc(NULL
, size
+ alignment
- offset
,
2118 MEM_RESERVE
, PAGE_NOACCESS
);
2119 if (offset
== ALIGN_ADDR2OFFSET(alignment
, tmp
))
2120 ret
= VirtualAlloc((void*)((intptr_t)tmp
+ alignment
2121 - offset
), size
, MEM_COMMIT
,
2124 VirtualFree(tmp
, 0, MEM_RELEASE
);
2125 offset
= ALIGN_ADDR2OFFSET(alignment
, ret
);
2129 /* over allocate to ensure we have an aligned region */
2130 ret
= VirtualAlloc(NULL
, size
+ alignment
, MEM_RESERVE
,
2132 offset
= ALIGN_ADDR2OFFSET(alignment
, ret
);
2133 ret
= VirtualAlloc((void*)((intptr_t)ret
+
2134 alignment
- offset
),
2135 size
, MEM_COMMIT
, PAGE_READWRITE
);
2143 pages_map(void *addr
, size_t size
, int pfd
)
2146 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
2148 assert(addr
== NULL
);
2149 va_ret
= VirtualAlloc(addr
, size
, MEM_RESERVE
, PAGE_NOACCESS
);
2151 ret
= VirtualAlloc(va_ret
, size
, MEM_COMMIT
, PAGE_READWRITE
);
2152 assert(va_ret
== ret
);
2154 ret
= VirtualAlloc(addr
, size
, MEM_COMMIT
| MEM_RESERVE
,
2161 pages_unmap(void *addr
, size_t size
)
2163 if (VirtualFree(addr
, 0, MEM_RELEASE
) == 0) {
2164 #if defined(MOZ_MEMORY_WINCE) && !defined(MOZ_MEMORY_WINCE6)
2165 if (GetLastError() == ERROR_INVALID_PARAMETER
) {
2166 MEMORY_BASIC_INFORMATION info
;
2167 VirtualQuery(addr
, &info
, sizeof(info
));
2168 if (VirtualFree(info
.AllocationBase
, 0, MEM_RELEASE
))
2172 _malloc_message(_getprogname(),
2173 ": (malloc) Error in VirtualFree()\n", "", "");
2178 #elif (defined(MOZ_MEMORY_DARWIN))
2180 pages_map(void *addr
, size_t size
, int pfd
)
2190 flags
= VM_FLAGS_ANYWHERE
;
2192 err
= vm_allocate((vm_map_t
)mach_task_self(), (vm_address_t
*)&ret
,
2193 (vm_size_t
)size
, flags
);
2194 if (err
!= KERN_SUCCESS
)
2197 assert(ret
== NULL
|| (addr
== NULL
&& ret
!= addr
)
2198 || (addr
!= NULL
&& ret
== addr
));
2203 pages_unmap(void *addr
, size_t size
)
2207 err
= vm_deallocate((vm_map_t
)mach_task_self(), (vm_address_t
)addr
,
2209 if (err
!= KERN_SUCCESS
) {
2210 malloc_message(_getprogname(),
2211 ": (malloc) Error in vm_deallocate(): ",
2212 mach_error_string(err
), "\n");
2218 #define VM_COPY_MIN (pagesize << 5)
2220 pages_copy(void *dest
, const void *src
, size_t n
)
2223 assert((void *)((uintptr_t)dest
& ~pagesize_mask
) == dest
);
2224 assert(n
>= VM_COPY_MIN
);
2225 assert((void *)((uintptr_t)src
& ~pagesize_mask
) == src
);
2227 vm_copy(mach_task_self(), (vm_address_t
)src
, (vm_size_t
)n
,
2228 (vm_address_t
)dest
);
2230 #else /* MOZ_MEMORY_DARWIN */
2231 #ifdef JEMALLOC_USES_MAP_ALIGN
2233 pages_map_align(size_t size
, int pfd
, size_t alignment
)
2238 * We don't use MAP_FIXED here, because it can cause the *replacement*
2239 * of existing mappings, and we only want to create new mappings.
2241 #ifdef MALLOC_PAGEFILE
2243 ret
= mmap((void *)alignment
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
|
2244 MAP_NOSYNC
| MAP_ALIGN
, pfd
, 0);
2248 ret
= mmap((void *)alignment
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
|
2249 MAP_NOSYNC
| MAP_ALIGN
| MAP_ANON
, -1, 0);
2251 assert(ret
!= NULL
);
2253 if (ret
== MAP_FAILED
)
2260 pages_map(void *addr
, size_t size
, int pfd
)
2265 * We don't use MAP_FIXED here, because it can cause the *replacement*
2266 * of existing mappings, and we only want to create new mappings.
2268 #ifdef MALLOC_PAGEFILE
2270 ret
= mmap(addr
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
|
2271 MAP_NOSYNC
, pfd
, 0);
2275 ret
= mmap(addr
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
|
2278 assert(ret
!= NULL
);
2280 if (ret
== MAP_FAILED
)
2282 else if (addr
!= NULL
&& ret
!= addr
) {
2284 * We succeeded in mapping memory, but not in the right place.
2286 if (munmap(ret
, size
) == -1) {
2287 char buf
[STRERROR_BUF
];
2289 strerror_r(errno
, buf
, sizeof(buf
));
2290 _malloc_message(_getprogname(),
2291 ": (malloc) Error in munmap(): ", buf
, "\n");
2298 assert(ret
== NULL
|| (addr
== NULL
&& ret
!= addr
)
2299 || (addr
!= NULL
&& ret
== addr
));
2304 pages_unmap(void *addr
, size_t size
)
2307 if (munmap(addr
, size
) == -1) {
2308 char buf
[STRERROR_BUF
];
2310 strerror_r(errno
, buf
, sizeof(buf
));
2311 _malloc_message(_getprogname(),
2312 ": (malloc) Error in munmap(): ", buf
, "\n");
2319 #ifdef MALLOC_VALIDATE
2320 static inline malloc_rtree_t
*
2321 malloc_rtree_new(unsigned bits
)
2323 malloc_rtree_t
*ret
;
2324 unsigned bits_per_level
, height
, i
;
2326 bits_per_level
= ffs(pow2_ceil((MALLOC_RTREE_NODESIZE
/
2327 sizeof(void *)))) - 1;
2328 height
= bits
/ bits_per_level
;
2329 if (height
* bits_per_level
!= bits
)
2331 assert(height
* bits_per_level
>= bits
);
2333 ret
= (malloc_rtree_t
*)base_calloc(1, sizeof(malloc_rtree_t
) + (sizeof(unsigned) *
2338 malloc_spin_init(&ret
->lock
);
2339 ret
->height
= height
;
2340 if (bits_per_level
* height
> bits
)
2341 ret
->level2bits
[0] = bits
% bits_per_level
;
2343 ret
->level2bits
[0] = bits_per_level
;
2344 for (i
= 1; i
< height
; i
++)
2345 ret
->level2bits
[i
] = bits_per_level
;
2347 ret
->root
= (void**)base_calloc(1, sizeof(void *) << ret
->level2bits
[0]);
2348 if (ret
->root
== NULL
) {
2350 * We leak the rtree here, since there's no generic base
2359 /* The least significant bits of the key are ignored. */
2360 static inline void *
2361 malloc_rtree_get(malloc_rtree_t
*rtree
, uintptr_t key
)
2365 unsigned i
, lshift
, height
, bits
;
2366 void **node
, **child
;
2368 malloc_spin_lock(&rtree
->lock
);
2369 for (i
= lshift
= 0, height
= rtree
->height
, node
= rtree
->root
;
2371 i
++, lshift
+= bits
, node
= child
) {
2372 bits
= rtree
->level2bits
[i
];
2373 subkey
= (key
<< lshift
) >> ((SIZEOF_PTR
<< 3) - bits
);
2374 child
= (void**)node
[subkey
];
2375 if (child
== NULL
) {
2376 malloc_spin_unlock(&rtree
->lock
);
2381 /* node is a leaf, so it contains values rather than node pointers. */
2382 bits
= rtree
->level2bits
[i
];
2383 subkey
= (key
<< lshift
) >> ((SIZEOF_PTR
<< 3) - bits
);
2385 malloc_spin_unlock(&rtree
->lock
);
2391 malloc_rtree_set(malloc_rtree_t
*rtree
, uintptr_t key
, void *val
)
2394 unsigned i
, lshift
, height
, bits
;
2395 void **node
, **child
;
2397 malloc_spin_lock(&rtree
->lock
);
2398 for (i
= lshift
= 0, height
= rtree
->height
, node
= rtree
->root
;
2400 i
++, lshift
+= bits
, node
= child
) {
2401 bits
= rtree
->level2bits
[i
];
2402 subkey
= (key
<< lshift
) >> ((SIZEOF_PTR
<< 3) - bits
);
2403 child
= (void**)node
[subkey
];
2404 if (child
== NULL
) {
2405 child
= (void**)base_calloc(1, sizeof(void *) <<
2406 rtree
->level2bits
[i
+1]);
2407 if (child
== NULL
) {
2408 malloc_spin_unlock(&rtree
->lock
);
2411 node
[subkey
] = child
;
2415 /* node is a leaf, so it contains values rather than node pointers. */
2416 bits
= rtree
->level2bits
[i
];
2417 subkey
= (key
<< lshift
) >> ((SIZEOF_PTR
<< 3) - bits
);
2419 malloc_spin_unlock(&rtree
->lock
);
2426 chunk_alloc_mmap(size_t size
, bool pagefile
)
2429 #ifndef JEMALLOC_USES_MAP_ALIGN
2434 #ifdef MALLOC_PAGEFILE
2435 if (opt_pagefile
&& pagefile
) {
2436 pfd
= pagefile_init(size
);
2444 * Windows requires that there be a 1:1 mapping between VM
2445 * allocation/deallocation operations. Therefore, take care here to
2446 * acquire the final result via one mapping operation. This means
2447 * unmapping any preliminary result that is not correctly aligned.
2449 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm,
2450 * since it reduces the number of page files.
2453 #ifdef JEMALLOC_USES_MAP_ALIGN
2454 ret
= pages_map_align(size
, pfd
, chunksize
);
2456 ret
= pages_map(NULL
, size
, pfd
);
2460 offset
= CHUNK_ADDR2OFFSET(ret
);
2462 /* Deallocate, then try to allocate at (ret + size - offset). */
2463 pages_unmap(ret
, size
);
2464 ret
= pages_map((void *)((uintptr_t)ret
+ size
- offset
), size
,
2466 while (ret
== NULL
) {
2468 * Over-allocate in order to map a memory region that
2469 * is definitely large enough.
2471 ret
= pages_map(NULL
, size
+ chunksize
, -1);
2475 * Deallocate, then allocate the correct size, within
2476 * the over-sized mapping.
2478 offset
= CHUNK_ADDR2OFFSET(ret
);
2479 pages_unmap(ret
, size
+ chunksize
);
2481 ret
= pages_map(ret
, size
, pfd
);
2483 ret
= pages_map((void *)((uintptr_t)ret
+
2484 chunksize
- offset
), size
, pfd
);
2487 * Failure here indicates a race with another thread, so
2494 #ifdef MALLOC_PAGEFILE
2496 pagefile_close(pfd
);
2500 stats_chunks
.nchunks
+= (size
/ chunksize
);
2505 #ifdef MALLOC_PAGEFILE
2507 pagefile_init(size_t size
)
2511 char pagefile_path
[PATH_MAX
];
2512 char zbuf
[MALLOC_PAGEFILE_WRITE_SIZE
];
2515 * Create a temporary file, then immediately unlink it so that it will
2518 strcpy(pagefile_path
, pagefile_templ
);
2519 ret
= mkstemp(pagefile_path
);
2522 if (unlink(pagefile_path
)) {
2523 char buf
[STRERROR_BUF
];
2525 strerror_r(errno
, buf
, sizeof(buf
));
2526 _malloc_message(_getprogname(), ": (malloc) Error in unlink(\"",
2527 pagefile_path
, "\"):");
2528 _malloc_message(buf
, "\n", "", "");
2534 * Write sequential zeroes to the file in order to assure that disk
2535 * space is committed, with minimal fragmentation. It would be
2536 * sufficient to write one zero per disk block, but that potentially
2537 * results in more system calls, for no real gain.
2539 memset(zbuf
, 0, sizeof(zbuf
));
2540 for (i
= 0; i
< size
; i
+= sizeof(zbuf
)) {
2541 if (write(ret
, zbuf
, sizeof(zbuf
)) != sizeof(zbuf
)) {
2542 if (errno
!= ENOSPC
) {
2543 char buf
[STRERROR_BUF
];
2545 strerror_r(errno
, buf
, sizeof(buf
));
2546 _malloc_message(_getprogname(),
2547 ": (malloc) Error in write(): ", buf
, "\n");
2551 pagefile_close(ret
);
2560 pagefile_close(int pfd
)
2564 char buf
[STRERROR_BUF
];
2566 strerror_r(errno
, buf
, sizeof(buf
));
2567 _malloc_message(_getprogname(),
2568 ": (malloc) Error in close(): ", buf
, "\n");
2576 chunk_alloc(size_t size
, bool zero
, bool pagefile
)
2581 assert((size
& chunksize_mask
) == 0);
2583 ret
= chunk_alloc_mmap(size
, pagefile
);
2588 /* All strategies for allocation failed. */
2593 stats_chunks
.curchunks
+= (size
/ chunksize
);
2594 if (stats_chunks
.curchunks
> stats_chunks
.highchunks
)
2595 stats_chunks
.highchunks
= stats_chunks
.curchunks
;
2598 #ifdef MALLOC_VALIDATE
2600 if (malloc_rtree_set(chunk_rtree
, (uintptr_t)ret
, ret
)) {
2601 chunk_dealloc(ret
, size
);
2607 assert(CHUNK_ADDR2BASE(ret
) == ret
);
2612 chunk_dealloc_mmap(void *chunk
, size_t size
)
2615 pages_unmap(chunk
, size
);
2619 chunk_dealloc(void *chunk
, size_t size
)
2622 assert(chunk
!= NULL
);
2623 assert(CHUNK_ADDR2BASE(chunk
) == chunk
);
2625 assert((size
& chunksize_mask
) == 0);
2628 stats_chunks
.curchunks
-= (size
/ chunksize
);
2630 #ifdef MALLOC_VALIDATE
2631 malloc_rtree_set(chunk_rtree
, (uintptr_t)chunk
, NULL
);
2634 chunk_dealloc_mmap(chunk
, size
);
2638 * End chunk management functions.
2640 /******************************************************************************/
2646 * Choose an arena based on a per-thread value (fast-path code, calls slow-path
2647 * code if necessary).
2649 static inline arena_t
*
2655 * We can only use TLS if this is a PIC library, since for the static
2656 * library version, libc's malloc is used by TLS allocation, which
2657 * introduces a bootstrapping issue.
2660 if (__isthreaded
== false) {
2661 /* Avoid the overhead of TLS for single-threaded operation. */
2665 # ifdef MOZ_MEMORY_WINDOWS
2666 ret
= (arena_t
*)TlsGetValue(tlsIndex
);
2672 ret
= choose_arena_hard();
2673 assert(ret
!= NULL
);
2676 if (__isthreaded
&& narenas
> 1) {
2680 * Hash _pthread_self() to one of the arenas. There is a prime
2681 * number of arenas, so this has a reasonable chance of
2682 * working. Even so, the hashing can be easily thwarted by
2683 * inconvenient _pthread_self() values. Without specific
2684 * knowledge of how _pthread_self() calculates values, we can't
2685 * easily do much better than this.
2687 ind
= (unsigned long) _pthread_self() % narenas
;
2690 * Optimistially assume that arenas[ind] has been initialized.
2691 * At worst, we find out that some other thread has already
2692 * done so, after acquiring the lock in preparation. Note that
2693 * this lazy locking also has the effect of lazily forcing
2694 * cache coherency; without the lock acquisition, there's no
2695 * guarantee that modification of arenas[ind] by another thread
2696 * would be seen on this CPU for an arbitrary amount of time.
2698 * In general, this approach to modifying a synchronized value
2699 * isn't a good idea, but in this case we only ever modify the
2700 * value once, so things work out well.
2705 * Avoid races with another thread that may have already
2706 * initialized arenas[ind].
2708 malloc_spin_lock(&arenas_lock
);
2709 if (arenas
[ind
] == NULL
)
2710 ret
= arenas_extend((unsigned)ind
);
2713 malloc_spin_unlock(&arenas_lock
);
2719 assert(ret
!= NULL
);
2725 * Choose an arena based on a per-thread value (slow-path code only, called
2726 * only by choose_arena()).
2729 choose_arena_hard(void)
2733 assert(__isthreaded
);
2735 #ifdef MALLOC_BALANCE
2736 /* Seed the PRNG used for arena load balancing. */
2737 SPRN(balance
, (uint32_t)(uintptr_t)(_pthread_self()));
2741 #ifdef MALLOC_BALANCE
2744 ind
= PRN(balance
, narenas_2pow
);
2745 if ((ret
= arenas
[ind
]) == NULL
) {
2746 malloc_spin_lock(&arenas_lock
);
2747 if ((ret
= arenas
[ind
]) == NULL
)
2748 ret
= arenas_extend(ind
);
2749 malloc_spin_unlock(&arenas_lock
);
2752 malloc_spin_lock(&arenas_lock
);
2753 if ((ret
= arenas
[next_arena
]) == NULL
)
2754 ret
= arenas_extend(next_arena
);
2755 next_arena
= (next_arena
+ 1) % narenas
;
2756 malloc_spin_unlock(&arenas_lock
);
2761 #ifdef MOZ_MEMORY_WINDOWS
2762 TlsSetValue(tlsIndex
, ret
);
2772 arena_chunk_comp(arena_chunk_t
*a
, arena_chunk_t
*b
)
2774 uintptr_t a_chunk
= (uintptr_t)a
;
2775 uintptr_t b_chunk
= (uintptr_t)b
;
2780 return ((a_chunk
> b_chunk
) - (a_chunk
< b_chunk
));
2783 /* Wrap red-black tree macros in functions. */
2784 rb_wrap(static, arena_chunk_tree_dirty_
, arena_chunk_tree_t
,
2785 arena_chunk_t
, link_dirty
, arena_chunk_comp
)
2788 arena_run_comp(arena_chunk_map_t
*a
, arena_chunk_map_t
*b
)
2790 uintptr_t a_mapelm
= (uintptr_t)a
;
2791 uintptr_t b_mapelm
= (uintptr_t)b
;
2796 return ((a_mapelm
> b_mapelm
) - (a_mapelm
< b_mapelm
));
2799 /* Wrap red-black tree macros in functions. */
2800 rb_wrap(static, arena_run_tree_
, arena_run_tree_t
, arena_chunk_map_t
, link
,
2804 arena_avail_comp(arena_chunk_map_t
*a
, arena_chunk_map_t
*b
)
2807 size_t a_size
= a
->bits
& ~pagesize_mask
;
2808 size_t b_size
= b
->bits
& ~pagesize_mask
;
2810 ret
= (a_size
> b_size
) - (a_size
< b_size
);
2812 uintptr_t a_mapelm
, b_mapelm
;
2814 if ((a
->bits
& CHUNK_MAP_KEY
) == 0)
2815 a_mapelm
= (uintptr_t)a
;
2818 * Treat keys as though they are lower than anything
2823 b_mapelm
= (uintptr_t)b
;
2825 ret
= (a_mapelm
> b_mapelm
) - (a_mapelm
< b_mapelm
);
2831 /* Wrap red-black tree macros in functions. */
2832 rb_wrap(static, arena_avail_tree_
, arena_avail_tree_t
, arena_chunk_map_t
, link
,
2835 static inline void *
2836 arena_run_reg_alloc(arena_run_t
*run
, arena_bin_t
*bin
)
2839 unsigned i
, mask
, bit
, regind
;
2841 assert(run
->magic
== ARENA_RUN_MAGIC
);
2842 assert(run
->regs_minelm
< bin
->regs_mask_nelms
);
2845 * Move the first check outside the loop, so that run->regs_minelm can
2846 * be updated unconditionally, without the possibility of updating it
2849 i
= run
->regs_minelm
;
2850 mask
= run
->regs_mask
[i
];
2852 /* Usable allocation found. */
2853 bit
= ffs((int)mask
) - 1;
2855 regind
= ((i
<< (SIZEOF_INT_2POW
+ 3)) + bit
);
2856 assert(regind
< bin
->nregs
);
2857 ret
= (void *)(((uintptr_t)run
) + bin
->reg0_offset
2858 + (bin
->reg_size
* regind
));
2861 mask
^= (1U << bit
);
2862 run
->regs_mask
[i
] = mask
;
2867 for (i
++; i
< bin
->regs_mask_nelms
; i
++) {
2868 mask
= run
->regs_mask
[i
];
2870 /* Usable allocation found. */
2871 bit
= ffs((int)mask
) - 1;
2873 regind
= ((i
<< (SIZEOF_INT_2POW
+ 3)) + bit
);
2874 assert(regind
< bin
->nregs
);
2875 ret
= (void *)(((uintptr_t)run
) + bin
->reg0_offset
2876 + (bin
->reg_size
* regind
));
2879 mask
^= (1U << bit
);
2880 run
->regs_mask
[i
] = mask
;
2883 * Make a note that nothing before this element
2884 * contains a free region.
2886 run
->regs_minelm
= i
; /* Low payoff: + (mask == 0); */
2897 arena_run_reg_dalloc(arena_run_t
*run
, arena_bin_t
*bin
, void *ptr
, size_t size
)
2900 * To divide by a number D that is not a power of two we multiply
2901 * by (2^21 / D) and then right shift by 21 positions.
2907 * (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT
2909 #define SIZE_INV_SHIFT 21
2910 #define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
2911 static const unsigned size_invs
[] = {
2913 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
2914 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
2915 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
2916 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
2917 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
2918 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
2919 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
2920 #if (QUANTUM_2POW_MIN < 4)
2922 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
2923 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
2924 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
2925 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
2926 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
2927 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
2928 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
2929 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
2932 unsigned diff
, regind
, elm
, bit
;
2934 assert(run
->magic
== ARENA_RUN_MAGIC
);
2935 assert(((sizeof(size_invs
)) / sizeof(unsigned)) + 3
2936 >= (SMALL_MAX_DEFAULT
>> QUANTUM_2POW_MIN
));
2939 * Avoid doing division with a variable divisor if possible. Using
2940 * actual division here can reduce allocator throughput by over 20%!
2942 diff
= (unsigned)((uintptr_t)ptr
- (uintptr_t)run
- bin
->reg0_offset
);
2943 if ((size
& (size
- 1)) == 0) {
2945 * log2_table allows fast division of a power of two in the
2948 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
2950 static const unsigned char log2_table
[] = {
2951 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
2952 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
2953 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2954 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
2955 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2956 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2957 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2958 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
2962 regind
= (diff
>> log2_table
[size
- 1]);
2963 else if (size
<= 32768)
2964 regind
= diff
>> (8 + log2_table
[(size
>> 8) - 1]);
2967 * The run size is too large for us to use the lookup
2968 * table. Use real division.
2970 regind
= diff
/ size
;
2972 } else if (size
<= ((sizeof(size_invs
) / sizeof(unsigned))
2973 << QUANTUM_2POW_MIN
) + 2) {
2974 regind
= size_invs
[(size
>> QUANTUM_2POW_MIN
) - 3] * diff
;
2975 regind
>>= SIZE_INV_SHIFT
;
2978 * size_invs isn't large enough to handle this size class, so
2979 * calculate regind using actual division. This only happens
2980 * if the user increases small_max via the 'S' runtime
2981 * configuration option.
2983 regind
= diff
/ size
;
2985 assert(diff
== regind
* size
);
2986 assert(regind
< bin
->nregs
);
2988 elm
= regind
>> (SIZEOF_INT_2POW
+ 3);
2989 if (elm
< run
->regs_minelm
)
2990 run
->regs_minelm
= elm
;
2991 bit
= regind
- (elm
<< (SIZEOF_INT_2POW
+ 3));
2992 assert((run
->regs_mask
[elm
] & (1U << bit
)) == 0);
2993 run
->regs_mask
[elm
] |= (1U << bit
);
2995 #undef SIZE_INV_SHIFT
2999 arena_run_split(arena_t
*arena
, arena_run_t
*run
, size_t size
, bool large
,
3002 arena_chunk_t
*chunk
;
3003 size_t old_ndirty
, run_ind
, total_pages
, need_pages
, rem_pages
, i
;
3005 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(run
);
3006 old_ndirty
= chunk
->ndirty
;
3007 run_ind
= (unsigned)(((uintptr_t)run
- (uintptr_t)chunk
)
3009 total_pages
= (chunk
->map
[run_ind
].bits
& ~pagesize_mask
) >>
3011 need_pages
= (size
>> pagesize_2pow
);
3012 assert(need_pages
> 0);
3013 assert(need_pages
<= total_pages
);
3014 rem_pages
= total_pages
- need_pages
;
3016 arena_avail_tree_remove(&arena
->runs_avail
, &chunk
->map
[run_ind
]);
3018 /* Keep track of trailing unused pages for later use. */
3019 if (rem_pages
> 0) {
3020 chunk
->map
[run_ind
+need_pages
].bits
= (rem_pages
<<
3021 pagesize_2pow
) | (chunk
->map
[run_ind
+need_pages
].bits
&
3023 chunk
->map
[run_ind
+total_pages
-1].bits
= (rem_pages
<<
3024 pagesize_2pow
) | (chunk
->map
[run_ind
+total_pages
-1].bits
&
3026 arena_avail_tree_insert(&arena
->runs_avail
,
3027 &chunk
->map
[run_ind
+need_pages
]);
3030 for (i
= 0; i
< need_pages
; i
++) {
3031 #ifdef MALLOC_DECOMMIT
3033 * Commit decommitted pages if necessary. If a decommitted
3034 * page is encountered, commit all needed adjacent decommitted
3035 * pages in one operation, in order to reduce system call
3038 if (chunk
->map
[run_ind
+ i
].bits
& CHUNK_MAP_DECOMMITTED
) {
3042 * Advance i+j to just past the index of the last page
3043 * to commit. Clear CHUNK_MAP_DECOMMITTED along the
3046 for (j
= 0; i
+ j
< need_pages
&& (chunk
->map
[run_ind
+
3047 i
+ j
].bits
& CHUNK_MAP_DECOMMITTED
); j
++) {
3048 chunk
->map
[run_ind
+ i
+ j
].bits
^=
3049 CHUNK_MAP_DECOMMITTED
;
3052 pages_commit((void *)((uintptr_t)chunk
+ ((run_ind
+ i
)
3053 << pagesize_2pow
)), (j
<< pagesize_2pow
));
3054 # ifdef MALLOC_STATS
3055 arena
->stats
.ncommit
++;
3056 arena
->stats
.committed
+= j
;
3058 } else /* No need to zero since commit zeros. */
3061 /* Zero if necessary. */
3063 if ((chunk
->map
[run_ind
+ i
].bits
& CHUNK_MAP_ZEROED
)
3065 VALGRIND_MALLOCLIKE_BLOCK((void *)((uintptr_t)
3066 chunk
+ ((run_ind
+ i
) << pagesize_2pow
)),
3067 pagesize
, 0, false);
3068 memset((void *)((uintptr_t)chunk
+ ((run_ind
3069 + i
) << pagesize_2pow
)), 0, pagesize
);
3070 VALGRIND_FREELIKE_BLOCK((void *)((uintptr_t)
3071 chunk
+ ((run_ind
+ i
) << pagesize_2pow
)),
3073 /* CHUNK_MAP_ZEROED is cleared below. */
3077 /* Update dirty page accounting. */
3078 if (chunk
->map
[run_ind
+ i
].bits
& CHUNK_MAP_DIRTY
) {
3081 /* CHUNK_MAP_DIRTY is cleared below. */
3084 /* Initialize the chunk map. */
3086 chunk
->map
[run_ind
+ i
].bits
= CHUNK_MAP_LARGE
3087 | CHUNK_MAP_ALLOCATED
;
3089 chunk
->map
[run_ind
+ i
].bits
= (size_t)run
3090 | CHUNK_MAP_ALLOCATED
;
3095 * Set the run size only in the first element for large runs. This is
3096 * primarily a debugging aid, since the lack of size info for trailing
3097 * pages only matters if the application tries to operate on an
3101 chunk
->map
[run_ind
].bits
|= size
;
3103 if (chunk
->ndirty
== 0 && old_ndirty
> 0)
3104 arena_chunk_tree_dirty_remove(&arena
->chunks_dirty
, chunk
);
3108 arena_chunk_init(arena_t
*arena
, arena_chunk_t
*chunk
)
3113 VALGRIND_MALLOCLIKE_BLOCK(chunk
, (arena_chunk_header_npages
<<
3114 pagesize_2pow
), 0, false);
3116 arena
->stats
.mapped
+= chunksize
;
3119 chunk
->arena
= arena
;
3122 * Claim that no pages are in use, since the header is merely overhead.
3126 /* Initialize the map to contain one maximal free untouched run. */
3127 run
= (arena_run_t
*)((uintptr_t)chunk
+ (arena_chunk_header_npages
<<
3129 for (i
= 0; i
< arena_chunk_header_npages
; i
++)
3130 chunk
->map
[i
].bits
= 0;
3131 chunk
->map
[i
].bits
= arena_maxclass
3132 #ifdef MALLOC_DECOMMIT
3133 | CHUNK_MAP_DECOMMITTED
3136 for (i
++; i
< chunk_npages
-1; i
++) {
3137 chunk
->map
[i
].bits
=
3138 #ifdef MALLOC_DECOMMIT
3139 CHUNK_MAP_DECOMMITTED
|
3143 chunk
->map
[chunk_npages
-1].bits
= arena_maxclass
3144 #ifdef MALLOC_DECOMMIT
3145 | CHUNK_MAP_DECOMMITTED
3149 #ifdef MALLOC_DECOMMIT
3151 * Start out decommitted, in order to force a closer correspondence
3152 * between dirty pages and committed untouched pages.
3154 pages_decommit(run
, arena_maxclass
);
3155 # ifdef MALLOC_STATS
3156 arena
->stats
.ndecommit
++;
3157 arena
->stats
.decommitted
+= (chunk_npages
- arena_chunk_header_npages
);
3158 arena
->stats
.committed
+= arena_chunk_header_npages
;
3162 /* Insert the run into the runs_avail tree. */
3163 arena_avail_tree_insert(&arena
->runs_avail
,
3164 &chunk
->map
[arena_chunk_header_npages
]);
3168 arena_chunk_dealloc(arena_t
*arena
, arena_chunk_t
*chunk
)
3171 if (arena
->spare
!= NULL
) {
3172 if (arena
->spare
->ndirty
> 0) {
3173 arena_chunk_tree_dirty_remove(
3174 &chunk
->arena
->chunks_dirty
, arena
->spare
);
3175 arena
->ndirty
-= arena
->spare
->ndirty
;
3176 #if (defined(MALLOC_STATS) && defined(MALLOC_DECOMMIT))
3177 arena
->stats
.committed
-= arena
->spare
->ndirty
;
3180 VALGRIND_FREELIKE_BLOCK(arena
->spare
, 0);
3181 chunk_dealloc((void *)arena
->spare
, chunksize
);
3183 arena
->stats
.mapped
-= chunksize
;
3184 # ifdef MALLOC_DECOMMIT
3185 arena
->stats
.committed
-= arena_chunk_header_npages
;
3191 * Remove run from runs_avail, so that the arena does not use it.
3192 * Dirty page flushing only uses the chunks_dirty tree, so leaving this
3193 * chunk in the chunks_* trees is sufficient for that purpose.
3195 arena_avail_tree_remove(&arena
->runs_avail
,
3196 &chunk
->map
[arena_chunk_header_npages
]);
3198 arena
->spare
= chunk
;
3201 static arena_run_t
*
3202 arena_run_alloc(arena_t
*arena
, arena_bin_t
*bin
, size_t size
, bool large
,
3205 arena_chunk_t
*chunk
;
3207 arena_chunk_map_t
*mapelm
, key
;
3209 assert(size
<= arena_maxclass
);
3210 assert((size
& pagesize_mask
) == 0);
3214 /* Search the arena's chunks for the lowest best fit. */
3215 key
.bits
= size
| CHUNK_MAP_KEY
;
3216 mapelm
= arena_avail_tree_nsearch(&arena
->runs_avail
, &key
);
3217 if (mapelm
!= NULL
) {
3218 arena_chunk_t
*run_chunk
=
3219 (arena_chunk_t
*)CHUNK_ADDR2BASE(mapelm
);
3220 size_t pageind
= ((uintptr_t)mapelm
-
3221 (uintptr_t)run_chunk
->map
) /
3222 sizeof(arena_chunk_map_t
);
3225 chunk_dealloc(chunk
, chunksize
);
3226 run
= (arena_run_t
*)((uintptr_t)run_chunk
+ (pageind
3228 arena_run_split(arena
, run
, size
, large
, zero
);
3232 if (arena
->spare
!= NULL
) {
3233 /* Use the spare. */
3234 chunk
= arena
->spare
;
3235 arena
->spare
= NULL
;
3236 run
= (arena_run_t
*)((uintptr_t)chunk
+
3237 (arena_chunk_header_npages
<< pagesize_2pow
));
3238 /* Insert the run into the runs_avail tree. */
3239 arena_avail_tree_insert(&arena
->runs_avail
,
3240 &chunk
->map
[arena_chunk_header_npages
]);
3241 arena_run_split(arena
, run
, size
, large
, zero
);
3246 * No usable runs. Create a new chunk from which to allocate
3249 if (chunk
== NULL
) {
3250 chunk
= (arena_chunk_t
*)chunk_alloc(chunksize
, true,
3256 arena_chunk_init(arena
, chunk
);
3257 run
= (arena_run_t
*)((uintptr_t)chunk
+
3258 (arena_chunk_header_npages
<< pagesize_2pow
));
3259 /* Update page map. */
3260 arena_run_split(arena
, run
, size
, large
, zero
);
3266 arena_purge(arena_t
*arena
)
3268 arena_chunk_t
*chunk
;
3272 rb_foreach_begin(arena_chunk_t
, link_dirty
, &arena
->chunks_dirty
,
3274 ndirty
+= chunk
->ndirty
;
3275 } rb_foreach_end(arena_chunk_t
, link_dirty
, &arena
->chunks_dirty
, chunk
)
3276 assert(ndirty
== arena
->ndirty
);
3278 assert(arena
->ndirty
> opt_dirty_max
);
3281 arena
->stats
.npurge
++;
3285 * Iterate downward through chunks until enough dirty memory has been
3286 * purged. Terminate as soon as possible in order to minimize the
3287 * number of system calls, even if a chunk has only been partially
3290 while (arena
->ndirty
> (opt_dirty_max
>> 1)) {
3291 chunk
= arena_chunk_tree_dirty_last(&arena
->chunks_dirty
);
3292 assert(chunk
!= NULL
);
3294 for (i
= chunk_npages
- 1; chunk
->ndirty
> 0; i
--) {
3295 assert(i
>= arena_chunk_header_npages
);
3297 if (chunk
->map
[i
].bits
& CHUNK_MAP_DIRTY
) {
3298 #ifdef MALLOC_DECOMMIT
3299 assert((chunk
->map
[i
].bits
&
3300 CHUNK_MAP_DECOMMITTED
) == 0);
3302 chunk
->map
[i
].bits
^=
3303 #ifdef MALLOC_DECOMMIT
3304 CHUNK_MAP_DECOMMITTED
|
3307 /* Find adjacent dirty run(s). */
3308 for (npages
= 1; i
> arena_chunk_header_npages
3309 && (chunk
->map
[i
- 1].bits
&
3310 CHUNK_MAP_DIRTY
); npages
++) {
3312 #ifdef MALLOC_DECOMMIT
3313 assert((chunk
->map
[i
].bits
&
3314 CHUNK_MAP_DECOMMITTED
) == 0);
3316 chunk
->map
[i
].bits
^=
3317 #ifdef MALLOC_DECOMMIT
3318 CHUNK_MAP_DECOMMITTED
|
3322 chunk
->ndirty
-= npages
;
3323 arena
->ndirty
-= npages
;
3325 #ifdef MALLOC_DECOMMIT
3326 pages_decommit((void *)((uintptr_t)
3327 chunk
+ (i
<< pagesize_2pow
)),
3328 (npages
<< pagesize_2pow
));
3329 # ifdef MALLOC_STATS
3330 arena
->stats
.ndecommit
++;
3331 arena
->stats
.decommitted
+= npages
;
3332 arena
->stats
.committed
-= npages
;
3335 madvise((void *)((uintptr_t)chunk
+ (i
<<
3336 pagesize_2pow
)), (npages
<< pagesize_2pow
),
3340 arena
->stats
.nmadvise
++;
3341 arena
->stats
.purged
+= npages
;
3343 if (arena
->ndirty
<= (opt_dirty_max
>> 1))
3348 if (chunk
->ndirty
== 0) {
3349 arena_chunk_tree_dirty_remove(&arena
->chunks_dirty
,
3356 arena_run_dalloc(arena_t
*arena
, arena_run_t
*run
, bool dirty
)
3358 arena_chunk_t
*chunk
;
3359 size_t size
, run_ind
, run_pages
;
3361 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(run
);
3362 run_ind
= (size_t)(((uintptr_t)run
- (uintptr_t)chunk
)
3364 assert(run_ind
>= arena_chunk_header_npages
);
3365 assert(run_ind
< chunk_npages
);
3366 if ((chunk
->map
[run_ind
].bits
& CHUNK_MAP_LARGE
) != 0)
3367 size
= chunk
->map
[run_ind
].bits
& ~pagesize_mask
;
3369 size
= run
->bin
->run_size
;
3370 run_pages
= (size
>> pagesize_2pow
);
3372 /* Mark pages as unallocated in the chunk map. */
3376 for (i
= 0; i
< run_pages
; i
++) {
3377 assert((chunk
->map
[run_ind
+ i
].bits
& CHUNK_MAP_DIRTY
)
3379 chunk
->map
[run_ind
+ i
].bits
= CHUNK_MAP_DIRTY
;
3382 if (chunk
->ndirty
== 0) {
3383 arena_chunk_tree_dirty_insert(&arena
->chunks_dirty
,
3386 chunk
->ndirty
+= run_pages
;
3387 arena
->ndirty
+= run_pages
;
3391 for (i
= 0; i
< run_pages
; i
++) {
3392 chunk
->map
[run_ind
+ i
].bits
&= ~(CHUNK_MAP_LARGE
|
3393 CHUNK_MAP_ALLOCATED
);
3396 chunk
->map
[run_ind
].bits
= size
| (chunk
->map
[run_ind
].bits
&
3398 chunk
->map
[run_ind
+run_pages
-1].bits
= size
|
3399 (chunk
->map
[run_ind
+run_pages
-1].bits
& pagesize_mask
);
3401 /* Try to coalesce forward. */
3402 if (run_ind
+ run_pages
< chunk_npages
&&
3403 (chunk
->map
[run_ind
+run_pages
].bits
& CHUNK_MAP_ALLOCATED
) == 0) {
3404 size_t nrun_size
= chunk
->map
[run_ind
+run_pages
].bits
&
3408 * Remove successor from runs_avail; the coalesced run is
3411 arena_avail_tree_remove(&arena
->runs_avail
,
3412 &chunk
->map
[run_ind
+run_pages
]);
3415 run_pages
= size
>> pagesize_2pow
;
3417 assert((chunk
->map
[run_ind
+run_pages
-1].bits
& ~pagesize_mask
)
3419 chunk
->map
[run_ind
].bits
= size
| (chunk
->map
[run_ind
].bits
&
3421 chunk
->map
[run_ind
+run_pages
-1].bits
= size
|
3422 (chunk
->map
[run_ind
+run_pages
-1].bits
& pagesize_mask
);
3425 /* Try to coalesce backward. */
3426 if (run_ind
> arena_chunk_header_npages
&& (chunk
->map
[run_ind
-1].bits
&
3427 CHUNK_MAP_ALLOCATED
) == 0) {
3428 size_t prun_size
= chunk
->map
[run_ind
-1].bits
& ~pagesize_mask
;
3430 run_ind
-= prun_size
>> pagesize_2pow
;
3433 * Remove predecessor from runs_avail; the coalesced run is
3436 arena_avail_tree_remove(&arena
->runs_avail
,
3437 &chunk
->map
[run_ind
]);
3440 run_pages
= size
>> pagesize_2pow
;
3442 assert((chunk
->map
[run_ind
].bits
& ~pagesize_mask
) ==
3444 chunk
->map
[run_ind
].bits
= size
| (chunk
->map
[run_ind
].bits
&
3446 chunk
->map
[run_ind
+run_pages
-1].bits
= size
|
3447 (chunk
->map
[run_ind
+run_pages
-1].bits
& pagesize_mask
);
3450 /* Insert into runs_avail, now that coalescing is complete. */
3451 arena_avail_tree_insert(&arena
->runs_avail
, &chunk
->map
[run_ind
]);
3453 /* Deallocate chunk if it is now completely unused. */
3454 if ((chunk
->map
[arena_chunk_header_npages
].bits
& (~pagesize_mask
|
3455 CHUNK_MAP_ALLOCATED
)) == arena_maxclass
)
3456 arena_chunk_dealloc(arena
, chunk
);
3458 /* Enforce opt_dirty_max. */
3459 if (arena
->ndirty
> opt_dirty_max
)
3464 arena_run_trim_head(arena_t
*arena
, arena_chunk_t
*chunk
, arena_run_t
*run
,
3465 size_t oldsize
, size_t newsize
)
3467 size_t pageind
= ((uintptr_t)run
- (uintptr_t)chunk
) >> pagesize_2pow
;
3468 size_t head_npages
= (oldsize
- newsize
) >> pagesize_2pow
;
3470 assert(oldsize
> newsize
);
3473 * Update the chunk map so that arena_run_dalloc() can treat the
3474 * leading run as separately allocated.
3476 chunk
->map
[pageind
].bits
= (oldsize
- newsize
) | CHUNK_MAP_LARGE
|
3477 CHUNK_MAP_ALLOCATED
;
3478 chunk
->map
[pageind
+head_npages
].bits
= newsize
| CHUNK_MAP_LARGE
|
3479 CHUNK_MAP_ALLOCATED
;
3481 arena_run_dalloc(arena
, run
, false);
3485 arena_run_trim_tail(arena_t
*arena
, arena_chunk_t
*chunk
, arena_run_t
*run
,
3486 size_t oldsize
, size_t newsize
, bool dirty
)
3488 size_t pageind
= ((uintptr_t)run
- (uintptr_t)chunk
) >> pagesize_2pow
;
3489 size_t npages
= newsize
>> pagesize_2pow
;
3491 assert(oldsize
> newsize
);
3494 * Update the chunk map so that arena_run_dalloc() can treat the
3495 * trailing run as separately allocated.
3497 chunk
->map
[pageind
].bits
= newsize
| CHUNK_MAP_LARGE
|
3498 CHUNK_MAP_ALLOCATED
;
3499 chunk
->map
[pageind
+npages
].bits
= (oldsize
- newsize
) | CHUNK_MAP_LARGE
3500 | CHUNK_MAP_ALLOCATED
;
3502 arena_run_dalloc(arena
, (arena_run_t
*)((uintptr_t)run
+ newsize
),
3506 static arena_run_t
*
3507 arena_bin_nonfull_run_get(arena_t
*arena
, arena_bin_t
*bin
)
3509 arena_chunk_map_t
*mapelm
;
3511 unsigned i
, remainder
;
3513 /* Look for a usable run. */
3514 mapelm
= arena_run_tree_first(&bin
->runs
);
3515 if (mapelm
!= NULL
) {
3516 /* run is guaranteed to have available space. */
3517 arena_run_tree_remove(&bin
->runs
, mapelm
);
3518 run
= (arena_run_t
*)(mapelm
->bits
& ~pagesize_mask
);
3520 bin
->stats
.reruns
++;
3524 /* No existing runs have any space available. */
3526 /* Allocate a new run. */
3527 run
= arena_run_alloc(arena
, bin
, bin
->run_size
, false, false);
3531 * Don't initialize if a race in arena_run_alloc() allowed an existing
3532 * run to become usable.
3534 if (run
== bin
->runcur
)
3537 VALGRIND_MALLOCLIKE_BLOCK(run
, sizeof(arena_run_t
) + (sizeof(unsigned) *
3538 (bin
->regs_mask_nelms
- 1)), 0, false);
3540 /* Initialize run internals. */
3543 for (i
= 0; i
< bin
->regs_mask_nelms
- 1; i
++)
3544 run
->regs_mask
[i
] = UINT_MAX
;
3545 remainder
= bin
->nregs
& ((1U << (SIZEOF_INT_2POW
+ 3)) - 1);
3547 run
->regs_mask
[i
] = UINT_MAX
;
3549 /* The last element has spare bits that need to be unset. */
3550 run
->regs_mask
[i
] = (UINT_MAX
>> ((1U << (SIZEOF_INT_2POW
+ 3))
3554 run
->regs_minelm
= 0;
3556 run
->nfree
= bin
->nregs
;
3558 run
->magic
= ARENA_RUN_MAGIC
;
3563 bin
->stats
.curruns
++;
3564 if (bin
->stats
.curruns
> bin
->stats
.highruns
)
3565 bin
->stats
.highruns
= bin
->stats
.curruns
;
3570 /* bin->runcur must have space available before this function is called. */
3571 static inline void *
3572 arena_bin_malloc_easy(arena_t
*arena
, arena_bin_t
*bin
, arena_run_t
*run
)
3576 assert(run
->magic
== ARENA_RUN_MAGIC
);
3577 assert(run
->nfree
> 0);
3579 ret
= arena_run_reg_alloc(run
, bin
);
3580 assert(ret
!= NULL
);
3586 /* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
3588 arena_bin_malloc_hard(arena_t
*arena
, arena_bin_t
*bin
)
3591 bin
->runcur
= arena_bin_nonfull_run_get(arena
, bin
);
3592 if (bin
->runcur
== NULL
)
3594 assert(bin
->runcur
->magic
== ARENA_RUN_MAGIC
);
3595 assert(bin
->runcur
->nfree
> 0);
3597 return (arena_bin_malloc_easy(arena
, bin
, bin
->runcur
));
3601 * Calculate bin->run_size such that it meets the following constraints:
3603 * *) bin->run_size >= min_run_size
3604 * *) bin->run_size <= arena_maxclass
3605 * *) bin->run_size <= RUN_MAX_SMALL
3606 * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
3608 * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are
3609 * also calculated here, since these settings are all interdependent.
3612 arena_bin_run_size_calc(arena_bin_t
*bin
, size_t min_run_size
)
3614 size_t try_run_size
, good_run_size
;
3615 unsigned good_nregs
, good_mask_nelms
, good_reg0_offset
;
3616 unsigned try_nregs
, try_mask_nelms
, try_reg0_offset
;
3618 assert(min_run_size
>= pagesize
);
3619 assert(min_run_size
<= arena_maxclass
);
3620 assert(min_run_size
<= RUN_MAX_SMALL
);
3623 * Calculate known-valid settings before entering the run_size
3624 * expansion loop, so that the first part of the loop always copies
3627 * The do..while loop iteratively reduces the number of regions until
3628 * the run header and the regions no longer overlap. A closed formula
3629 * would be quite messy, since there is an interdependency between the
3630 * header's mask length and the number of regions.
3632 try_run_size
= min_run_size
;
3633 try_nregs
= ((try_run_size
- sizeof(arena_run_t
)) / bin
->reg_size
)
3634 + 1; /* Counter-act try_nregs-- in loop. */
3637 try_mask_nelms
= (try_nregs
>> (SIZEOF_INT_2POW
+ 3)) +
3638 ((try_nregs
& ((1U << (SIZEOF_INT_2POW
+ 3)) - 1)) ? 1 : 0);
3639 try_reg0_offset
= try_run_size
- (try_nregs
* bin
->reg_size
);
3640 } while (sizeof(arena_run_t
) + (sizeof(unsigned) * (try_mask_nelms
- 1))
3643 /* run_size expansion loop. */
3646 * Copy valid settings before trying more aggressive settings.
3648 good_run_size
= try_run_size
;
3649 good_nregs
= try_nregs
;
3650 good_mask_nelms
= try_mask_nelms
;
3651 good_reg0_offset
= try_reg0_offset
;
3653 /* Try more aggressive settings. */
3654 try_run_size
+= pagesize
;
3655 try_nregs
= ((try_run_size
- sizeof(arena_run_t
)) /
3656 bin
->reg_size
) + 1; /* Counter-act try_nregs-- in loop. */
3659 try_mask_nelms
= (try_nregs
>> (SIZEOF_INT_2POW
+ 3)) +
3660 ((try_nregs
& ((1U << (SIZEOF_INT_2POW
+ 3)) - 1)) ?
3662 try_reg0_offset
= try_run_size
- (try_nregs
*
3664 } while (sizeof(arena_run_t
) + (sizeof(unsigned) *
3665 (try_mask_nelms
- 1)) > try_reg0_offset
);
3666 } while (try_run_size
<= arena_maxclass
&& try_run_size
<= RUN_MAX_SMALL
3667 && RUN_MAX_OVRHD
* (bin
->reg_size
<< 3) > RUN_MAX_OVRHD_RELAX
3668 && (try_reg0_offset
<< RUN_BFP
) > RUN_MAX_OVRHD
* try_run_size
);
3670 assert(sizeof(arena_run_t
) + (sizeof(unsigned) * (good_mask_nelms
- 1))
3671 <= good_reg0_offset
);
3672 assert((good_mask_nelms
<< (SIZEOF_INT_2POW
+ 3)) >= good_nregs
);
3674 /* Copy final settings. */
3675 bin
->run_size
= good_run_size
;
3676 bin
->nregs
= good_nregs
;
3677 bin
->regs_mask_nelms
= good_mask_nelms
;
3678 bin
->reg0_offset
= good_reg0_offset
;
3680 return (good_run_size
);
3683 #ifdef MALLOC_BALANCE
3685 arena_lock_balance(arena_t
*arena
)
3687 unsigned contention
;
3689 contention
= malloc_spin_lock(&arena
->lock
);
3692 * Calculate the exponentially averaged contention for this
3693 * arena. Due to integer math always rounding down, this value
3694 * decays somewhat faster then normal.
3696 arena
->contention
= (((uint64_t)arena
->contention
3697 * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW
)-1))
3698 + (uint64_t)contention
) >> BALANCE_ALPHA_INV_2POW
;
3699 if (arena
->contention
>= opt_balance_threshold
)
3700 arena_lock_balance_hard(arena
);
3705 arena_lock_balance_hard(arena_t
*arena
)
3709 arena
->contention
= 0;
3711 arena
->stats
.nbalance
++;
3713 ind
= PRN(balance
, narenas_2pow
);
3714 if (arenas
[ind
] != NULL
) {
3715 #ifdef MOZ_MEMORY_WINDOWS
3716 TlsSetValue(tlsIndex
, arenas
[ind
]);
3718 arenas_map
= arenas
[ind
];
3721 malloc_spin_lock(&arenas_lock
);
3722 if (arenas
[ind
] != NULL
) {
3723 #ifdef MOZ_MEMORY_WINDOWS
3724 TlsSetValue(tlsIndex
, arenas
[ind
]);
3726 arenas_map
= arenas
[ind
];
3729 #ifdef MOZ_MEMORY_WINDOWS
3730 TlsSetValue(tlsIndex
, arenas_extend(ind
));
3732 arenas_map
= arenas_extend(ind
);
3735 malloc_spin_unlock(&arenas_lock
);
3740 static inline void *
3741 arena_malloc_small(arena_t
*arena
, size_t size
, bool zero
)
3747 if (size
< small_min
) {
3749 size
= pow2_ceil(size
);
3750 bin
= &arena
->bins
[ffs((int)(size
>> (TINY_MIN_2POW
+
3752 #if (!defined(NDEBUG) || defined(MALLOC_STATS))
3754 * Bin calculation is always correct, but we may need
3755 * to fix size for the purposes of assertions and/or
3758 if (size
< (1U << TINY_MIN_2POW
))
3759 size
= (1U << TINY_MIN_2POW
);
3761 } else if (size
<= small_max
) {
3762 /* Quantum-spaced. */
3763 size
= QUANTUM_CEILING(size
);
3764 bin
= &arena
->bins
[ntbins
+ (size
>> opt_quantum_2pow
)
3768 size
= pow2_ceil(size
);
3769 bin
= &arena
->bins
[ntbins
+ nqbins
3770 + (ffs((int)(size
>> opt_small_max_2pow
)) - 2)];
3772 assert(size
== bin
->reg_size
);
3774 #ifdef MALLOC_BALANCE
3775 arena_lock_balance(arena
);
3777 malloc_spin_lock(&arena
->lock
);
3779 if ((run
= bin
->runcur
) != NULL
&& run
->nfree
> 0)
3780 ret
= arena_bin_malloc_easy(arena
, bin
, run
);
3782 ret
= arena_bin_malloc_hard(arena
, bin
);
3785 malloc_spin_unlock(&arena
->lock
);
3790 bin
->stats
.nrequests
++;
3791 arena
->stats
.nmalloc_small
++;
3792 arena
->stats
.allocated_small
+= size
;
3794 malloc_spin_unlock(&arena
->lock
);
3796 VALGRIND_MALLOCLIKE_BLOCK(ret
, size
, 0, zero
);
3797 if (zero
== false) {
3800 memset(ret
, 0xa5, size
);
3802 memset(ret
, 0, size
);
3805 memset(ret
, 0, size
);
3811 arena_malloc_large(arena_t
*arena
, size_t size
, bool zero
)
3815 /* Large allocation. */
3816 size
= PAGE_CEILING(size
);
3817 #ifdef MALLOC_BALANCE
3818 arena_lock_balance(arena
);
3820 malloc_spin_lock(&arena
->lock
);
3822 ret
= (void *)arena_run_alloc(arena
, NULL
, size
, true, zero
);
3824 malloc_spin_unlock(&arena
->lock
);
3828 arena
->stats
.nmalloc_large
++;
3829 arena
->stats
.allocated_large
+= size
;
3831 malloc_spin_unlock(&arena
->lock
);
3833 VALGRIND_MALLOCLIKE_BLOCK(ret
, size
, 0, zero
);
3834 if (zero
== false) {
3837 memset(ret
, 0xa5, size
);
3839 memset(ret
, 0, size
);
3846 static inline void *
3847 arena_malloc(arena_t
*arena
, size_t size
, bool zero
)
3850 assert(arena
!= NULL
);
3851 assert(arena
->magic
== ARENA_MAGIC
);
3853 assert(QUANTUM_CEILING(size
) <= arena_maxclass
);
3855 if (size
<= bin_maxclass
) {
3856 return (arena_malloc_small(arena
, size
, zero
));
3858 return (arena_malloc_large(arena
, size
, zero
));
3861 static inline void *
3862 imalloc(size_t size
)
3867 if (size
<= arena_maxclass
)
3868 return (arena_malloc(choose_arena(), size
, false));
3870 return (huge_malloc(size
, false));
3873 static inline void *
3874 icalloc(size_t size
)
3877 if (size
<= arena_maxclass
)
3878 return (arena_malloc(choose_arena(), size
, true));
3880 return (huge_malloc(size
, true));
3883 /* Only handles large allocations that require more than page alignment. */
3885 arena_palloc(arena_t
*arena
, size_t alignment
, size_t size
, size_t alloc_size
)
3889 arena_chunk_t
*chunk
;
3891 assert((size
& pagesize_mask
) == 0);
3892 assert((alignment
& pagesize_mask
) == 0);
3894 #ifdef MALLOC_BALANCE
3895 arena_lock_balance(arena
);
3897 malloc_spin_lock(&arena
->lock
);
3899 ret
= (void *)arena_run_alloc(arena
, NULL
, alloc_size
, true, false);
3901 malloc_spin_unlock(&arena
->lock
);
3905 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ret
);
3907 offset
= (uintptr_t)ret
& (alignment
- 1);
3908 assert((offset
& pagesize_mask
) == 0);
3909 assert(offset
< alloc_size
);
3911 arena_run_trim_tail(arena
, chunk
, (arena_run_t
*)ret
, alloc_size
, size
, false);
3913 size_t leadsize
, trailsize
;
3915 leadsize
= alignment
- offset
;
3917 arena_run_trim_head(arena
, chunk
, (arena_run_t
*)ret
, alloc_size
,
3918 alloc_size
- leadsize
);
3919 ret
= (void *)((uintptr_t)ret
+ leadsize
);
3922 trailsize
= alloc_size
- leadsize
- size
;
3923 if (trailsize
!= 0) {
3924 /* Trim trailing space. */
3925 assert(trailsize
< alloc_size
);
3926 arena_run_trim_tail(arena
, chunk
, (arena_run_t
*)ret
, size
+ trailsize
,
3932 arena
->stats
.nmalloc_large
++;
3933 arena
->stats
.allocated_large
+= size
;
3935 malloc_spin_unlock(&arena
->lock
);
3937 VALGRIND_MALLOCLIKE_BLOCK(ret
, size
, 0, false);
3940 memset(ret
, 0xa5, size
);
3942 memset(ret
, 0, size
);
3947 static inline void *
3948 ipalloc(size_t alignment
, size_t size
)
3954 * Round size up to the nearest multiple of alignment.
3956 * This done, we can take advantage of the fact that for each small
3957 * size class, every object is aligned at the smallest power of two
3958 * that is non-zero in the base two representation of the size. For
3961 * Size | Base 2 | Minimum alignment
3962 * -----+----------+------------------
3964 * 144 | 10100000 | 32
3965 * 192 | 11000000 | 64
3967 * Depending on runtime settings, it is possible that arena_malloc()
3968 * will further round up to a power of two, but that never causes
3969 * correctness issues.
3971 ceil_size
= (size
+ (alignment
- 1)) & (-alignment
);
3973 * (ceil_size < size) protects against the combination of maximal
3974 * alignment and size greater than maximal alignment.
3976 if (ceil_size
< size
) {
3977 /* size_t overflow. */
3981 if (ceil_size
<= pagesize
|| (alignment
<= pagesize
3982 && ceil_size
<= arena_maxclass
))
3983 ret
= arena_malloc(choose_arena(), ceil_size
, false);
3988 * We can't achieve sub-page alignment, so round up alignment
3989 * permanently; it makes later calculations simpler.
3991 alignment
= PAGE_CEILING(alignment
);
3992 ceil_size
= PAGE_CEILING(size
);
3994 * (ceil_size < size) protects against very large sizes within
3995 * pagesize of SIZE_T_MAX.
3997 * (ceil_size + alignment < ceil_size) protects against the
3998 * combination of maximal alignment and ceil_size large enough
3999 * to cause overflow. This is similar to the first overflow
4000 * check above, but it needs to be repeated due to the new
4001 * ceil_size value, which may now be *equal* to maximal
4002 * alignment, whereas before we only detected overflow if the
4003 * original size was *greater* than maximal alignment.
4005 if (ceil_size
< size
|| ceil_size
+ alignment
< ceil_size
) {
4006 /* size_t overflow. */
4011 * Calculate the size of the over-size run that arena_palloc()
4012 * would need to allocate in order to guarantee the alignment.
4014 if (ceil_size
>= alignment
)
4015 run_size
= ceil_size
+ alignment
- pagesize
;
4018 * It is possible that (alignment << 1) will cause
4019 * overflow, but it doesn't matter because we also
4020 * subtract pagesize, which in the case of overflow
4021 * leaves us with a very large run_size. That causes
4022 * the first conditional below to fail, which means
4023 * that the bogus run_size value never gets used for
4024 * anything important.
4026 run_size
= (alignment
<< 1) - pagesize
;
4029 if (run_size
<= arena_maxclass
) {
4030 ret
= arena_palloc(choose_arena(), alignment
, ceil_size
,
4032 } else if (alignment
<= chunksize
)
4033 ret
= huge_malloc(ceil_size
, false);
4035 ret
= huge_palloc(alignment
, ceil_size
);
4038 assert(((uintptr_t)ret
& (alignment
- 1)) == 0);
4042 /* Return the size of the allocation pointed to by ptr. */
4044 arena_salloc(const void *ptr
)
4047 arena_chunk_t
*chunk
;
4048 size_t pageind
, mapbits
;
4050 assert(ptr
!= NULL
);
4051 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
4053 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
4054 pageind
= (((uintptr_t)ptr
- (uintptr_t)chunk
) >> pagesize_2pow
);
4055 mapbits
= chunk
->map
[pageind
].bits
;
4056 assert((mapbits
& CHUNK_MAP_ALLOCATED
) != 0);
4057 if ((mapbits
& CHUNK_MAP_LARGE
) == 0) {
4058 arena_run_t
*run
= (arena_run_t
*)(mapbits
& ~pagesize_mask
);
4059 assert(run
->magic
== ARENA_RUN_MAGIC
);
4060 ret
= run
->bin
->reg_size
;
4062 ret
= mapbits
& ~pagesize_mask
;
4069 #if (defined(MALLOC_VALIDATE) || defined(MOZ_MEMORY_DARWIN))
4071 * Validate ptr before assuming that it points to an allocation. Currently,
4072 * the following validation is performed:
4074 * + Check that ptr is not NULL.
4076 * + Check that ptr lies within a mapped chunk.
4078 static inline size_t
4079 isalloc_validate(const void *ptr
)
4081 arena_chunk_t
*chunk
;
4083 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
4087 if (malloc_rtree_get(chunk_rtree
, (uintptr_t)chunk
) == NULL
)
4091 assert(chunk
->arena
->magic
== ARENA_MAGIC
);
4092 return (arena_salloc(ptr
));
4095 extent_node_t
*node
;
4099 key
.addr
= (void *)chunk
;
4100 malloc_mutex_lock(&huge_mtx
);
4101 node
= extent_tree_ad_search(&huge
, &key
);
4106 malloc_mutex_unlock(&huge_mtx
);
4112 static inline size_t
4113 isalloc(const void *ptr
)
4116 arena_chunk_t
*chunk
;
4118 assert(ptr
!= NULL
);
4120 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
4123 assert(chunk
->arena
->magic
== ARENA_MAGIC
);
4125 ret
= arena_salloc(ptr
);
4127 extent_node_t
*node
, key
;
4129 /* Chunk (huge allocation). */
4131 malloc_mutex_lock(&huge_mtx
);
4133 /* Extract from tree of huge allocations. */
4134 key
.addr
= __DECONST(void *, ptr
);
4135 node
= extent_tree_ad_search(&huge
, &key
);
4136 assert(node
!= NULL
);
4140 malloc_mutex_unlock(&huge_mtx
);
4147 arena_dalloc_small(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
4148 arena_chunk_map_t
*mapelm
)
4154 run
= (arena_run_t
*)(mapelm
->bits
& ~pagesize_mask
);
4155 assert(run
->magic
== ARENA_RUN_MAGIC
);
4157 size
= bin
->reg_size
;
4161 memset(ptr
, 0x5a, size
);
4164 arena_run_reg_dalloc(run
, bin
, ptr
, size
);
4167 if (run
->nfree
== bin
->nregs
) {
4168 /* Deallocate run. */
4169 if (run
== bin
->runcur
)
4171 else if (bin
->nregs
!= 1) {
4172 size_t run_pageind
= (((uintptr_t)run
-
4173 (uintptr_t)chunk
)) >> pagesize_2pow
;
4174 arena_chunk_map_t
*run_mapelm
=
4175 &chunk
->map
[run_pageind
];
4177 * This block's conditional is necessary because if the
4178 * run only contains one region, then it never gets
4179 * inserted into the non-full runs tree.
4181 assert(arena_run_tree_search(&bin
->runs
, run_mapelm
) ==
4183 arena_run_tree_remove(&bin
->runs
, run_mapelm
);
4188 VALGRIND_FREELIKE_BLOCK(run
, 0);
4189 arena_run_dalloc(arena
, run
, true);
4191 bin
->stats
.curruns
--;
4193 } else if (run
->nfree
== 1 && run
!= bin
->runcur
) {
4195 * Make sure that bin->runcur always refers to the lowest
4196 * non-full run, if one exists.
4198 if (bin
->runcur
== NULL
)
4200 else if ((uintptr_t)run
< (uintptr_t)bin
->runcur
) {
4201 /* Switch runcur. */
4202 if (bin
->runcur
->nfree
> 0) {
4203 arena_chunk_t
*runcur_chunk
=
4204 (arena_chunk_t
*)CHUNK_ADDR2BASE(bin
->runcur
);
4205 size_t runcur_pageind
=
4206 (((uintptr_t)bin
->runcur
-
4207 (uintptr_t)runcur_chunk
)) >> pagesize_2pow
;
4208 arena_chunk_map_t
*runcur_mapelm
=
4209 &runcur_chunk
->map
[runcur_pageind
];
4211 /* Insert runcur. */
4212 assert(arena_run_tree_search(&bin
->runs
,
4213 runcur_mapelm
) == NULL
);
4214 arena_run_tree_insert(&bin
->runs
,
4219 size_t run_pageind
= (((uintptr_t)run
-
4220 (uintptr_t)chunk
)) >> pagesize_2pow
;
4221 arena_chunk_map_t
*run_mapelm
=
4222 &chunk
->map
[run_pageind
];
4224 assert(arena_run_tree_search(&bin
->runs
, run_mapelm
) ==
4226 arena_run_tree_insert(&bin
->runs
, run_mapelm
);
4230 arena
->stats
.allocated_small
-= size
;
4231 arena
->stats
.ndalloc_small
++;
4236 arena_dalloc_large(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
)
4238 /* Large allocation. */
4239 malloc_spin_lock(&arena
->lock
);
4242 #ifndef MALLOC_STATS
4247 size_t pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >>
4249 size_t size
= chunk
->map
[pageind
].bits
& ~pagesize_mask
;
4255 memset(ptr
, 0x5a, size
);
4258 arena
->stats
.allocated_large
-= size
;
4262 arena
->stats
.ndalloc_large
++;
4265 arena_run_dalloc(arena
, (arena_run_t
*)ptr
, true);
4266 malloc_spin_unlock(&arena
->lock
);
4270 arena_dalloc(void *ptr
, size_t offset
)
4272 arena_chunk_t
*chunk
;
4275 arena_chunk_map_t
*mapelm
;
4277 assert(ptr
!= NULL
);
4278 assert(offset
!= 0);
4279 assert(CHUNK_ADDR2OFFSET(ptr
) == offset
);
4281 chunk
= (arena_chunk_t
*) ((uintptr_t)ptr
- offset
);
4282 arena
= chunk
->arena
;
4283 assert(arena
!= NULL
);
4284 assert(arena
->magic
== ARENA_MAGIC
);
4286 pageind
= offset
>> pagesize_2pow
;
4287 mapelm
= &chunk
->map
[pageind
];
4288 assert((mapelm
->bits
& CHUNK_MAP_ALLOCATED
) != 0);
4289 if ((mapelm
->bits
& CHUNK_MAP_LARGE
) == 0) {
4290 /* Small allocation. */
4291 malloc_spin_lock(&arena
->lock
);
4292 arena_dalloc_small(arena
, chunk
, ptr
, mapelm
);
4293 malloc_spin_unlock(&arena
->lock
);
4295 arena_dalloc_large(arena
, chunk
, ptr
);
4296 VALGRIND_FREELIKE_BLOCK(ptr
, 0);
4304 assert(ptr
!= NULL
);
4306 offset
= CHUNK_ADDR2OFFSET(ptr
);
4308 arena_dalloc(ptr
, offset
);
4314 arena_ralloc_large_shrink(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
4315 size_t size
, size_t oldsize
)
4318 assert(size
< oldsize
);
4321 * Shrink the run, and make trailing pages available for other
4324 #ifdef MALLOC_BALANCE
4325 arena_lock_balance(arena
);
4327 malloc_spin_lock(&arena
->lock
);
4329 arena_run_trim_tail(arena
, chunk
, (arena_run_t
*)ptr
, oldsize
, size
,
4332 arena
->stats
.allocated_large
-= oldsize
- size
;
4334 malloc_spin_unlock(&arena
->lock
);
4338 arena_ralloc_large_grow(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
4339 size_t size
, size_t oldsize
)
4341 size_t pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> pagesize_2pow
;
4342 size_t npages
= oldsize
>> pagesize_2pow
;
4344 assert(oldsize
== (chunk
->map
[pageind
].bits
& ~pagesize_mask
));
4346 /* Try to extend the run. */
4347 assert(size
> oldsize
);
4348 #ifdef MALLOC_BALANCE
4349 arena_lock_balance(arena
);
4351 malloc_spin_lock(&arena
->lock
);
4353 if (pageind
+ npages
< chunk_npages
&& (chunk
->map
[pageind
+npages
].bits
4354 & CHUNK_MAP_ALLOCATED
) == 0 && (chunk
->map
[pageind
+npages
].bits
&
4355 ~pagesize_mask
) >= size
- oldsize
) {
4357 * The next run is available and sufficiently large. Split the
4358 * following run, then merge the first part with the existing
4361 arena_run_split(arena
, (arena_run_t
*)((uintptr_t)chunk
+
4362 ((pageind
+npages
) << pagesize_2pow
)), size
- oldsize
, true,
4365 chunk
->map
[pageind
].bits
= size
| CHUNK_MAP_LARGE
|
4366 CHUNK_MAP_ALLOCATED
;
4367 chunk
->map
[pageind
+npages
].bits
= CHUNK_MAP_LARGE
|
4368 CHUNK_MAP_ALLOCATED
;
4371 arena
->stats
.allocated_large
+= size
- oldsize
;
4373 malloc_spin_unlock(&arena
->lock
);
4376 malloc_spin_unlock(&arena
->lock
);
4382 * Try to resize a large allocation, in order to avoid copying. This will
4383 * always fail if growing an object, and the following run is already in use.
4386 arena_ralloc_large(void *ptr
, size_t size
, size_t oldsize
)
4390 psize
= PAGE_CEILING(size
);
4391 if (psize
== oldsize
) {
4392 /* Same size class. */
4394 if (opt_junk
&& size
< oldsize
) {
4395 memset((void *)((uintptr_t)ptr
+ size
), 0x5a, oldsize
-
4401 arena_chunk_t
*chunk
;
4404 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
4405 arena
= chunk
->arena
;
4406 assert(arena
->magic
== ARENA_MAGIC
);
4408 if (psize
< oldsize
) {
4410 /* Fill before shrinking in order avoid a race. */
4412 memset((void *)((uintptr_t)ptr
+ size
), 0x5a,
4416 arena_ralloc_large_shrink(arena
, chunk
, ptr
, psize
,
4420 bool ret
= arena_ralloc_large_grow(arena
, chunk
, ptr
,
4423 if (ret
== false && opt_zero
) {
4424 memset((void *)((uintptr_t)ptr
+ oldsize
), 0,
4434 arena_ralloc(void *ptr
, size_t size
, size_t oldsize
)
4439 /* Try to avoid moving the allocation. */
4440 if (size
< small_min
) {
4441 if (oldsize
< small_min
&&
4442 ffs((int)(pow2_ceil(size
) >> (TINY_MIN_2POW
+ 1)))
4443 == ffs((int)(pow2_ceil(oldsize
) >> (TINY_MIN_2POW
+ 1))))
4444 goto IN_PLACE
; /* Same size class. */
4445 } else if (size
<= small_max
) {
4446 if (oldsize
>= small_min
&& oldsize
<= small_max
&&
4447 (QUANTUM_CEILING(size
) >> opt_quantum_2pow
)
4448 == (QUANTUM_CEILING(oldsize
) >> opt_quantum_2pow
))
4449 goto IN_PLACE
; /* Same size class. */
4450 } else if (size
<= bin_maxclass
) {
4451 if (oldsize
> small_max
&& oldsize
<= bin_maxclass
&&
4452 pow2_ceil(size
) == pow2_ceil(oldsize
))
4453 goto IN_PLACE
; /* Same size class. */
4454 } else if (oldsize
> bin_maxclass
&& oldsize
<= arena_maxclass
) {
4455 assert(size
> bin_maxclass
);
4456 if (arena_ralloc_large(ptr
, size
, oldsize
) == false)
4461 * If we get here, then size and oldsize are different enough that we
4462 * need to move the object. In that case, fall back to allocating new
4463 * space and copying.
4465 ret
= arena_malloc(choose_arena(), size
, false);
4469 /* Junk/zero-filling were already done by arena_malloc(). */
4470 copysize
= (size
< oldsize
) ? size
: oldsize
;
4472 if (copysize
>= VM_COPY_MIN
)
4473 pages_copy(ret
, ptr
, copysize
);
4476 memcpy(ret
, ptr
, copysize
);
4481 if (opt_junk
&& size
< oldsize
)
4482 memset((void *)((uintptr_t)ptr
+ size
), 0x5a, oldsize
- size
);
4483 else if (opt_zero
&& size
> oldsize
)
4484 memset((void *)((uintptr_t)ptr
+ oldsize
), 0, size
- oldsize
);
4489 static inline void *
4490 iralloc(void *ptr
, size_t size
)
4494 assert(ptr
!= NULL
);
4497 oldsize
= isalloc(ptr
);
4499 #ifndef MALLOC_VALGRIND
4500 if (size
<= arena_maxclass
)
4501 return (arena_ralloc(ptr
, size
, oldsize
));
4503 return (huge_ralloc(ptr
, size
, oldsize
));
4506 * Valgrind does not provide a public interface for modifying an
4507 * existing allocation, so use malloc/memcpy/free instead.
4510 void *ret
= imalloc(size
);
4513 memcpy(ret
, ptr
, oldsize
);
4515 memcpy(ret
, ptr
, size
);
4524 arena_new(arena_t
*arena
)
4528 size_t pow2_size
, prev_run_size
;
4530 if (malloc_spin_init(&arena
->lock
))
4534 memset(&arena
->stats
, 0, sizeof(arena_stats_t
));
4537 /* Initialize chunks. */
4538 arena_chunk_tree_dirty_new(&arena
->chunks_dirty
);
4539 arena
->spare
= NULL
;
4543 arena_avail_tree_new(&arena
->runs_avail
);
4545 #ifdef MALLOC_BALANCE
4546 arena
->contention
= 0;
4549 /* Initialize bins. */
4550 prev_run_size
= pagesize
;
4552 /* (2^n)-spaced tiny bins. */
4553 for (i
= 0; i
< ntbins
; i
++) {
4554 bin
= &arena
->bins
[i
];
4556 arena_run_tree_new(&bin
->runs
);
4558 bin
->reg_size
= (1U << (TINY_MIN_2POW
+ i
));
4560 prev_run_size
= arena_bin_run_size_calc(bin
, prev_run_size
);
4563 memset(&bin
->stats
, 0, sizeof(malloc_bin_stats_t
));
4567 /* Quantum-spaced bins. */
4568 for (; i
< ntbins
+ nqbins
; i
++) {
4569 bin
= &arena
->bins
[i
];
4571 arena_run_tree_new(&bin
->runs
);
4573 bin
->reg_size
= quantum
* (i
- ntbins
+ 1);
4575 pow2_size
= pow2_ceil(quantum
* (i
- ntbins
+ 1));
4576 prev_run_size
= arena_bin_run_size_calc(bin
, prev_run_size
);
4579 memset(&bin
->stats
, 0, sizeof(malloc_bin_stats_t
));
4583 /* (2^n)-spaced sub-page bins. */
4584 for (; i
< ntbins
+ nqbins
+ nsbins
; i
++) {
4585 bin
= &arena
->bins
[i
];
4587 arena_run_tree_new(&bin
->runs
);
4589 bin
->reg_size
= (small_max
<< (i
- (ntbins
+ nqbins
) + 1));
4591 prev_run_size
= arena_bin_run_size_calc(bin
, prev_run_size
);
4594 memset(&bin
->stats
, 0, sizeof(malloc_bin_stats_t
));
4599 arena
->magic
= ARENA_MAGIC
;
4605 /* Create a new arena and insert it into the arenas array at index ind. */
4607 arenas_extend(unsigned ind
)
4611 /* Allocate enough space for trailing bins. */
4612 ret
= (arena_t
*)base_alloc(sizeof(arena_t
)
4613 + (sizeof(arena_bin_t
) * (ntbins
+ nqbins
+ nsbins
- 1)));
4614 if (ret
!= NULL
&& arena_new(ret
) == false) {
4618 /* Only reached if there is an OOM error. */
4621 * OOM here is quite inconvenient to propagate, since dealing with it
4622 * would require a check for failure in the fast path. Instead, punt
4623 * by using arenas[0]. In practice, this is an extremely unlikely
4626 _malloc_message(_getprogname(),
4627 ": (malloc) Error initializing arena\n", "", "");
4637 /******************************************************************************/
4639 * Begin general internal functions.
4643 huge_malloc(size_t size
, bool zero
)
4647 #ifdef MALLOC_DECOMMIT
4650 extent_node_t
*node
;
4652 /* Allocate one or more contiguous chunks for this request. */
4654 csize
= CHUNK_CEILING(size
);
4656 /* size is large enough to cause size_t wrap-around. */
4660 /* Allocate an extent node with which to track the chunk. */
4661 node
= base_node_alloc();
4665 ret
= chunk_alloc(csize
, zero
, true);
4667 base_node_dealloc(node
);
4671 /* Insert node into huge. */
4673 #ifdef MALLOC_DECOMMIT
4674 psize
= PAGE_CEILING(size
);
4680 malloc_mutex_lock(&huge_mtx
);
4681 extent_tree_ad_insert(&huge
, node
);
4684 # ifdef MALLOC_DECOMMIT
4685 huge_allocated
+= psize
;
4687 huge_allocated
+= csize
;
4690 malloc_mutex_unlock(&huge_mtx
);
4692 #ifdef MALLOC_DECOMMIT
4693 if (csize
- psize
> 0)
4694 pages_decommit((void *)((uintptr_t)ret
+ psize
), csize
- psize
);
4697 #ifdef MALLOC_DECOMMIT
4698 VALGRIND_MALLOCLIKE_BLOCK(ret
, psize
, 0, zero
);
4700 VALGRIND_MALLOCLIKE_BLOCK(ret
, csize
, 0, zero
);
4704 if (zero
== false) {
4706 # ifdef MALLOC_DECOMMIT
4707 memset(ret
, 0xa5, psize
);
4709 memset(ret
, 0xa5, csize
);
4712 # ifdef MALLOC_DECOMMIT
4713 memset(ret
, 0, psize
);
4715 memset(ret
, 0, csize
);
4723 /* Only handles large allocations that require more than chunk alignment. */
4725 huge_palloc(size_t alignment
, size_t size
)
4728 size_t alloc_size
, chunk_size
, offset
;
4729 #ifdef MALLOC_DECOMMIT
4732 extent_node_t
*node
;
4736 * This allocation requires alignment that is even larger than chunk
4737 * alignment. This means that huge_malloc() isn't good enough.
4739 * Allocate almost twice as many chunks as are demanded by the size or
4740 * alignment, in order to assure the alignment can be achieved, then
4741 * unmap leading and trailing chunks.
4743 assert(alignment
>= chunksize
);
4745 chunk_size
= CHUNK_CEILING(size
);
4747 if (size
>= alignment
)
4748 alloc_size
= chunk_size
+ alignment
- chunksize
;
4750 alloc_size
= (alignment
<< 1) - chunksize
;
4752 /* Allocate an extent node with which to track the chunk. */
4753 node
= base_node_alloc();
4758 * Windows requires that there be a 1:1 mapping between VM
4759 * allocation/deallocation operations. Therefore, take care here to
4760 * acquire the final result via one mapping operation.
4762 * The MALLOC_PAGEFILE code also benefits from this mapping algorithm,
4763 * since it reduces the number of page files.
4765 #ifdef MALLOC_PAGEFILE
4767 pfd
= pagefile_init(size
);
4773 #ifdef JEMALLOC_USES_MAP_ALIGN
4774 ret
= pages_map_align(chunk_size
, pfd
, alignment
);
4779 over
= chunk_alloc(alloc_size
, false, false);
4781 base_node_dealloc(node
);
4786 offset
= (uintptr_t)over
& (alignment
- 1);
4787 assert((offset
& chunksize_mask
) == 0);
4788 assert(offset
< alloc_size
);
4789 ret
= (void *)((uintptr_t)over
+ offset
);
4790 chunk_dealloc(over
, alloc_size
);
4791 ret
= pages_map(ret
, chunk_size
, pfd
);
4793 * Failure here indicates a race with another thread, so try
4796 } while (ret
== NULL
);
4798 /* Insert node into huge. */
4800 #ifdef MALLOC_DECOMMIT
4801 psize
= PAGE_CEILING(size
);
4804 node
->size
= chunk_size
;
4807 malloc_mutex_lock(&huge_mtx
);
4808 extent_tree_ad_insert(&huge
, node
);
4811 # ifdef MALLOC_DECOMMIT
4812 huge_allocated
+= psize
;
4814 huge_allocated
+= chunk_size
;
4817 malloc_mutex_unlock(&huge_mtx
);
4819 #ifdef MALLOC_DECOMMIT
4820 if (chunk_size
- psize
> 0) {
4821 pages_decommit((void *)((uintptr_t)ret
+ psize
),
4822 chunk_size
- psize
);
4826 #ifdef MALLOC_DECOMMIT
4827 VALGRIND_MALLOCLIKE_BLOCK(ret
, psize
, 0, false);
4829 VALGRIND_MALLOCLIKE_BLOCK(ret
, chunk_size
, 0, false);
4834 # ifdef MALLOC_DECOMMIT
4835 memset(ret
, 0xa5, psize
);
4837 memset(ret
, 0xa5, chunk_size
);
4840 # ifdef MALLOC_DECOMMIT
4841 memset(ret
, 0, psize
);
4843 memset(ret
, 0, chunk_size
);
4848 #ifdef MALLOC_PAGEFILE
4850 pagefile_close(pfd
);
4856 huge_ralloc(void *ptr
, size_t size
, size_t oldsize
)
4861 /* Avoid moving the allocation if the size class would not change. */
4863 if (oldsize
> arena_maxclass
&&
4864 CHUNK_CEILING(size
) == CHUNK_CEILING(oldsize
)) {
4865 #ifdef MALLOC_DECOMMIT
4866 size_t psize
= PAGE_CEILING(size
);
4869 if (opt_junk
&& size
< oldsize
) {
4870 memset((void *)((uintptr_t)ptr
+ size
), 0x5a, oldsize
4874 #ifdef MALLOC_DECOMMIT
4875 if (psize
< oldsize
) {
4876 extent_node_t
*node
, key
;
4878 pages_decommit((void *)((uintptr_t)ptr
+ psize
),
4881 /* Update recorded size. */
4882 malloc_mutex_lock(&huge_mtx
);
4883 key
.addr
= __DECONST(void *, ptr
);
4884 node
= extent_tree_ad_search(&huge
, &key
);
4885 assert(node
!= NULL
);
4886 assert(node
->size
== oldsize
);
4887 # ifdef MALLOC_STATS
4888 huge_allocated
-= oldsize
- psize
;
4891 malloc_mutex_unlock(&huge_mtx
);
4892 } else if (psize
> oldsize
) {
4893 extent_node_t
*node
, key
;
4895 pages_commit((void *)((uintptr_t)ptr
+ oldsize
),
4898 /* Update recorded size. */
4899 malloc_mutex_lock(&huge_mtx
);
4900 key
.addr
= __DECONST(void *, ptr
);
4901 node
= extent_tree_ad_search(&huge
, &key
);
4902 assert(node
!= NULL
);
4903 assert(node
->size
== oldsize
);
4904 # ifdef MALLOC_STATS
4905 huge_allocated
+= psize
- oldsize
;
4908 malloc_mutex_unlock(&huge_mtx
);
4912 if (opt_zero
&& size
> oldsize
) {
4913 memset((void *)((uintptr_t)ptr
+ oldsize
), 0, size
4921 * If we get here, then size and oldsize are different enough that we
4922 * need to use a different size class. In that case, fall back to
4923 * allocating new space and copying.
4925 ret
= huge_malloc(size
, false);
4929 copysize
= (size
< oldsize
) ? size
: oldsize
;
4931 if (copysize
>= VM_COPY_MIN
)
4932 pages_copy(ret
, ptr
, copysize
);
4935 memcpy(ret
, ptr
, copysize
);
4941 huge_dalloc(void *ptr
)
4943 extent_node_t
*node
, key
;
4945 malloc_mutex_lock(&huge_mtx
);
4947 /* Extract from tree of huge allocations. */
4949 node
= extent_tree_ad_search(&huge
, &key
);
4950 assert(node
!= NULL
);
4951 assert(node
->addr
== ptr
);
4952 extent_tree_ad_remove(&huge
, node
);
4956 huge_allocated
-= node
->size
;
4959 malloc_mutex_unlock(&huge_mtx
);
4964 memset(node
->addr
, 0x5a, node
->size
);
4966 #ifdef MALLOC_DECOMMIT
4967 chunk_dealloc(node
->addr
, CHUNK_CEILING(node
->size
));
4969 chunk_dealloc(node
->addr
, node
->size
);
4971 VALGRIND_FREELIKE_BLOCK(node
->addr
, 0);
4973 base_node_dealloc(node
);
4976 #ifndef MOZ_MEMORY_NARENAS_DEFAULT_ONE
4977 #ifdef MOZ_MEMORY_BSD
4978 static inline unsigned
4988 if (sysctl(mib
, 2, &ret
, &len
, (void *) 0, 0) == -1) {
4995 #elif (defined(MOZ_MEMORY_LINUX))
4998 static inline unsigned
5002 int fd
, nread
, column
;
5004 static const char matchstr
[] = "processor\t:";
5008 * sysconf(3) would be the preferred method for determining the number
5009 * of CPUs, but it uses malloc internally, which causes untennable
5010 * recursion during malloc initialization.
5012 fd
= open("/proc/cpuinfo", O_RDONLY
);
5014 return (1); /* Error. */
5016 * Count the number of occurrences of matchstr at the beginnings of
5017 * lines. This treats hyperthreaded CPUs as multiple processors.
5022 nread
= read(fd
, &buf
, sizeof(buf
));
5024 break; /* EOF or error. */
5025 for (i
= 0;i
< nread
;i
++) {
5029 else if (column
!= -1) {
5030 if (c
== matchstr
[column
]) {
5032 if (column
== sizeof(matchstr
) - 1) {
5043 ret
= 1; /* Something went wrong in the parser. */
5048 #elif (defined(MOZ_MEMORY_DARWIN))
5049 #include <mach/mach_init.h>
5050 #include <mach/mach_host.h>
5052 static inline unsigned
5055 kern_return_t error
;
5057 processor_info_array_t pinfo
;
5058 mach_msg_type_number_t pinfocnt
;
5060 error
= host_processor_info(mach_host_self(), PROCESSOR_BASIC_INFO
,
5061 &n
, &pinfo
, &pinfocnt
);
5062 if (error
!= KERN_SUCCESS
)
5063 return (1); /* Error. */
5067 #elif (defined(MOZ_MEMORY_SOLARIS))
5069 static inline unsigned
5072 return sysconf(_SC_NPROCESSORS_ONLN
);
5075 static inline unsigned
5080 * We lack a way to determine the number of CPUs on this platform, so
5089 malloc_print_stats(void)
5092 if (opt_print_stats
) {
5093 char s
[UMAX2S_BUFSIZE
];
5094 _malloc_message("___ Begin malloc statistics ___\n", "", "",
5096 _malloc_message("Assertions ",
5103 _malloc_message("Boolean MALLOC_OPTIONS: ",
5104 opt_abort
? "A" : "a", "", "");
5106 _malloc_message(opt_junk
? "J" : "j", "", "", "");
5108 #ifdef MALLOC_PAGEFILE
5109 _malloc_message(opt_pagefile
? "o" : "O", "", "", "");
5111 _malloc_message("P", "", "", "");
5112 #ifdef MALLOC_UTRACE
5113 _malloc_message(opt_utrace
? "U" : "u", "", "", "");
5116 _malloc_message(opt_sysv
? "V" : "v", "", "", "");
5118 #ifdef MALLOC_XMALLOC
5119 _malloc_message(opt_xmalloc
? "X" : "x", "", "", "");
5122 _malloc_message(opt_zero
? "Z" : "z", "", "", "");
5124 _malloc_message("\n", "", "", "");
5126 #ifndef MOZ_MEMORY_NARENAS_DEFAULT_ONE
5127 _malloc_message("CPUs: ", umax2s(ncpus
, s
), "\n", "");
5129 _malloc_message("Max arenas: ", umax2s(narenas
, s
), "\n", "");
5130 #ifdef MALLOC_BALANCE
5131 _malloc_message("Arena balance threshold: ",
5132 umax2s(opt_balance_threshold
, s
), "\n", "");
5134 _malloc_message("Pointer size: ", umax2s(sizeof(void *), s
),
5136 _malloc_message("Quantum size: ", umax2s(quantum
, s
), "\n", "");
5137 _malloc_message("Max small size: ", umax2s(small_max
, s
), "\n",
5139 _malloc_message("Max dirty pages per arena: ",
5140 umax2s(opt_dirty_max
, s
), "\n", "");
5142 _malloc_message("Chunk size: ", umax2s(chunksize
, s
), "", "");
5143 _malloc_message(" (2^", umax2s(opt_chunk_2pow
, s
), ")\n", "");
5147 size_t allocated
, mapped
;
5148 #ifdef MALLOC_BALANCE
5149 uint64_t nbalance
= 0;
5154 /* Calculate and print allocated/mapped stats. */
5157 for (i
= 0, allocated
= 0; i
< narenas
; i
++) {
5158 if (arenas
[i
] != NULL
) {
5159 malloc_spin_lock(&arenas
[i
]->lock
);
5161 arenas
[i
]->stats
.allocated_small
;
5163 arenas
[i
]->stats
.allocated_large
;
5164 #ifdef MALLOC_BALANCE
5165 nbalance
+= arenas
[i
]->stats
.nbalance
;
5167 malloc_spin_unlock(&arenas
[i
]->lock
);
5172 malloc_mutex_lock(&huge_mtx
);
5173 allocated
+= huge_allocated
;
5174 mapped
= stats_chunks
.curchunks
* chunksize
;
5175 malloc_mutex_unlock(&huge_mtx
);
5177 malloc_mutex_lock(&base_mtx
);
5178 mapped
+= base_mapped
;
5179 malloc_mutex_unlock(&base_mtx
);
5181 #ifdef MOZ_MEMORY_WINDOWS
5182 malloc_printf("Allocated: %lu, mapped: %lu\n",
5185 malloc_printf("Allocated: %zu, mapped: %zu\n",
5189 #ifdef MALLOC_BALANCE
5190 malloc_printf("Arena balance reassignments: %llu\n",
5194 /* Print chunk stats. */
5196 chunk_stats_t chunks_stats
;
5198 malloc_mutex_lock(&huge_mtx
);
5199 chunks_stats
= stats_chunks
;
5200 malloc_mutex_unlock(&huge_mtx
);
5202 malloc_printf("chunks: nchunks "
5203 "highchunks curchunks\n");
5204 malloc_printf(" %13llu%13lu%13lu\n",
5205 chunks_stats
.nchunks
,
5206 chunks_stats
.highchunks
,
5207 chunks_stats
.curchunks
);
5210 /* Print chunk stats. */
5212 "huge: nmalloc ndalloc allocated\n");
5213 #ifdef MOZ_MEMORY_WINDOWS
5214 malloc_printf(" %12llu %12llu %12lu\n",
5215 huge_nmalloc
, huge_ndalloc
, huge_allocated
);
5217 malloc_printf(" %12llu %12llu %12zu\n",
5218 huge_nmalloc
, huge_ndalloc
, huge_allocated
);
5220 /* Print stats for each arena. */
5221 for (i
= 0; i
< narenas
; i
++) {
5223 if (arena
!= NULL
) {
5225 "\narenas[%u]:\n", i
);
5226 malloc_spin_lock(&arena
->lock
);
5228 malloc_spin_unlock(&arena
->lock
);
5232 #endif /* #ifdef MALLOC_STATS */
5233 _malloc_message("--- End malloc statistics ---\n", "", "", "");
5238 * FreeBSD's pthreads implementation calls malloc(3), so the malloc
5239 * implementation has to take pains to avoid infinite recursion during
5242 #if (defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_DARWIN)) && !defined(MOZ_MEMORY_WINCE)
5243 #define malloc_init() false
5249 if (malloc_initialized
== false)
5250 return (malloc_init_hard());
5256 #if !defined(MOZ_MEMORY_WINDOWS) || defined(MOZ_MEMORY_WINCE)
5260 malloc_init_hard(void)
5263 char buf
[PATH_MAX
+ 1];
5266 #ifndef MOZ_MEMORY_WINDOWS
5270 #ifndef MOZ_MEMORY_WINDOWS
5271 malloc_mutex_lock(&init_lock
);
5274 if (malloc_initialized
) {
5276 * Another thread initialized the allocator before this one
5277 * acquired init_lock.
5279 #ifndef MOZ_MEMORY_WINDOWS
5280 malloc_mutex_unlock(&init_lock
);
5285 #ifdef MOZ_MEMORY_WINDOWS
5286 /* get a thread local storage index */
5287 tlsIndex
= TlsAlloc();
5290 /* Get page size and number of CPUs */
5291 #ifdef MOZ_MEMORY_WINDOWS
5295 GetSystemInfo(&info
);
5296 result
= info
.dwPageSize
;
5298 pagesize
= (unsigned) result
;
5300 #ifndef MOZ_MEMORY_NARENAS_DEFAULT_ONE
5301 ncpus
= info
.dwNumberOfProcessors
;
5305 #ifndef MOZ_MEMORY_NARENAS_DEFAULT_ONE
5306 ncpus
= malloc_ncpus();
5309 result
= sysconf(_SC_PAGESIZE
);
5310 assert(result
!= -1);
5312 pagesize
= (unsigned) result
;
5316 * We assume that pagesize is a power of 2 when calculating
5317 * pagesize_mask and pagesize_2pow.
5319 assert(((result
- 1) & result
) == 0);
5320 pagesize_mask
= result
- 1;
5321 pagesize_2pow
= ffs((int)result
) - 1;
5323 #ifdef MALLOC_PAGEFILE
5325 * Determine where to create page files. It is insufficient to
5326 * unconditionally use P_tmpdir (typically "/tmp"), since for some
5327 * operating systems /tmp is a separate filesystem that is rather small.
5328 * Therefore prefer, in order, the following locations:
5337 static const char suffix
[] = "/jemalloc.XXXXXX";
5339 if ((s
= getenv("MALLOC_TMPDIR")) == NULL
&& (s
=
5340 getenv("TMPDIR")) == NULL
)
5343 if (slen
+ sizeof(suffix
) > sizeof(pagefile_templ
)) {
5344 _malloc_message(_getprogname(),
5345 ": (malloc) Page file path too long\n",
5349 memcpy(pagefile_templ
, s
, slen
);
5350 memcpy(&pagefile_templ
[slen
], suffix
, sizeof(suffix
));
5354 for (i
= 0; i
< 3; i
++) {
5357 /* Get runtime configuration. */
5360 #ifndef MOZ_MEMORY_WINDOWS
5361 if ((linklen
= readlink("/etc/malloc.conf", buf
,
5362 sizeof(buf
) - 1)) != -1) {
5364 * Use the contents of the "/etc/malloc.conf"
5365 * symbolic link's name.
5367 buf
[linklen
] = '\0';
5372 /* No configuration specified. */
5378 if (issetugid() == 0 && (opts
=
5379 getenv("MALLOC_OPTIONS")) != NULL
) {
5381 * Do nothing; opts is already initialized to
5382 * the value of the MALLOC_OPTIONS environment
5386 /* No configuration specified. */
5392 if (_malloc_options
!= NULL
) {
5394 * Use options that were compiled into the
5397 opts
= _malloc_options
;
5399 /* No configuration specified. */
5411 for (j
= 0; opts
[j
] != '\0'; j
++) {
5415 /* Parse repetition count, if any. */
5416 for (nreps
= 0, nseen
= false;; j
++, nseen
= true) {
5418 case '0': case '1': case '2': case '3':
5419 case '4': case '5': case '6': case '7':
5422 nreps
+= opts
[j
] - '0';
5432 for (k
= 0; k
< nreps
; k
++) {
5441 #ifdef MALLOC_BALANCE
5442 opt_balance_threshold
>>= 1;
5446 #ifdef MALLOC_BALANCE
5447 if (opt_balance_threshold
== 0)
5448 opt_balance_threshold
= 1;
5449 else if ((opt_balance_threshold
<< 1)
5450 > opt_balance_threshold
)
5451 opt_balance_threshold
<<= 1;
5455 opt_dirty_max
>>= 1;
5458 if (opt_dirty_max
== 0)
5460 else if ((opt_dirty_max
<< 1) != 0)
5461 opt_dirty_max
<<= 1;
5473 * Chunks always require at least one
5474 * header page, so chunks can never be
5475 * smaller than two pages.
5477 if (opt_chunk_2pow
> pagesize_2pow
+ 1)
5481 if (opt_chunk_2pow
+ 1 <
5482 (sizeof(size_t) << 3))
5486 opt_narenas_lshift
--;
5489 opt_narenas_lshift
++;
5491 #ifdef MALLOC_PAGEFILE
5493 /* Do not over-commit. */
5494 opt_pagefile
= true;
5497 /* Allow over-commit. */
5498 opt_pagefile
= false;
5502 opt_print_stats
= false;
5505 opt_print_stats
= true;
5508 if (opt_quantum_2pow
> QUANTUM_2POW_MIN
)
5512 if (opt_quantum_2pow
< pagesize_2pow
-
5517 if (opt_small_max_2pow
>
5519 opt_small_max_2pow
--;
5522 if (opt_small_max_2pow
< pagesize_2pow
5524 opt_small_max_2pow
++;
5526 #ifdef MALLOC_UTRACE
5542 #ifdef MALLOC_XMALLOC
5544 opt_xmalloc
= false;
5563 _malloc_message(_getprogname(),
5564 ": (malloc) Unsupported character "
5565 "in malloc options: '", cbuf
,
5573 /* Take care to call atexit() only once. */
5574 if (opt_print_stats
) {
5575 #ifndef MOZ_MEMORY_WINDOWS
5576 /* Print statistics at exit. */
5577 atexit(malloc_print_stats
);
5581 #if (!defined(MOZ_MEMORY_WINDOWS) && !defined(MOZ_MEMORY_DARWIN) && !defined(MOZ_MEMORY_ANDROID))
5582 /* Prevent potential deadlock on malloc locks after fork. */
5583 pthread_atfork(_malloc_prefork
, _malloc_postfork
, _malloc_postfork
);
5586 /* Set variables according to the value of opt_small_max_2pow. */
5587 if (opt_small_max_2pow
< opt_quantum_2pow
)
5588 opt_small_max_2pow
= opt_quantum_2pow
;
5589 small_max
= (1U << opt_small_max_2pow
);
5591 /* Set bin-related variables. */
5592 bin_maxclass
= (pagesize
>> 1);
5593 assert(opt_quantum_2pow
>= TINY_MIN_2POW
);
5594 ntbins
= opt_quantum_2pow
- TINY_MIN_2POW
;
5595 assert(ntbins
<= opt_quantum_2pow
);
5596 nqbins
= (small_max
>> opt_quantum_2pow
);
5597 nsbins
= pagesize_2pow
- opt_small_max_2pow
- 1;
5599 /* Set variables according to the value of opt_quantum_2pow. */
5600 quantum
= (1U << opt_quantum_2pow
);
5601 quantum_mask
= quantum
- 1;
5603 small_min
= (quantum
>> 1) + 1;
5606 assert(small_min
<= quantum
);
5608 /* Set variables according to the value of opt_chunk_2pow. */
5609 chunksize
= (1LU << opt_chunk_2pow
);
5610 chunksize_mask
= chunksize
- 1;
5611 chunk_npages
= (chunksize
>> pagesize_2pow
);
5616 * Compute the header size such that it is large
5617 * enough to contain the page map and enough nodes for the
5618 * worst case: one node per non-header page plus one extra for
5619 * situations where we briefly have one more node allocated
5620 * than we will need.
5622 header_size
= sizeof(arena_chunk_t
) +
5623 (sizeof(arena_chunk_map_t
) * (chunk_npages
- 1));
5624 arena_chunk_header_npages
= (header_size
>> pagesize_2pow
) +
5625 ((header_size
& pagesize_mask
) != 0);
5627 arena_maxclass
= chunksize
- (arena_chunk_header_npages
<<
5630 #ifdef JEMALLOC_USES_MAP_ALIGN
5632 * When using MAP_ALIGN, the alignment parameter must be a power of two
5633 * multiple of the system pagesize, or mmap will fail.
5635 assert((chunksize
% pagesize
) == 0);
5636 assert((1 << (ffs(chunksize
/ pagesize
) - 1)) == (chunksize
/pagesize
));
5642 memset(&stats_chunks
, 0, sizeof(chunk_stats_t
));
5645 /* Various sanity checks that regard configuration. */
5646 assert(quantum
>= sizeof(void *));
5647 assert(quantum
<= pagesize
);
5648 assert(chunksize
>= pagesize
);
5649 assert(quantum
* 4 <= chunksize
);
5651 /* Initialize chunks data. */
5652 malloc_mutex_init(&huge_mtx
);
5653 extent_tree_ad_new(&huge
);
5660 /* Initialize base allocation data structures. */
5663 # ifdef MALLOC_DECOMMIT
5668 malloc_mutex_init(&base_mtx
);
5670 #ifdef MOZ_MEMORY_NARENAS_DEFAULT_ONE
5675 * For SMP systems, create four times as many arenas as there
5676 * are CPUs by default.
5678 opt_narenas_lshift
+= 2;
5681 /* Determine how many arenas to use. */
5684 if (opt_narenas_lshift
> 0) {
5685 if ((narenas
<< opt_narenas_lshift
) > narenas
)
5686 narenas
<<= opt_narenas_lshift
;
5688 * Make sure not to exceed the limits of what base_alloc() can
5691 if (narenas
* sizeof(arena_t
*) > chunksize
)
5692 narenas
= chunksize
/ sizeof(arena_t
*);
5693 } else if (opt_narenas_lshift
< 0) {
5694 if ((narenas
>> -opt_narenas_lshift
) < narenas
)
5695 narenas
>>= -opt_narenas_lshift
;
5696 /* Make sure there is at least one arena. */
5700 #ifdef MALLOC_BALANCE
5701 assert(narenas
!= 0);
5702 for (narenas_2pow
= 0;
5703 (narenas
>> (narenas_2pow
+ 1)) != 0;
5709 static const unsigned primes
[] = {1, 3, 5, 7, 11, 13, 17, 19,
5710 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
5711 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
5712 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
5713 223, 227, 229, 233, 239, 241, 251, 257, 263};
5714 unsigned nprimes
, parenas
;
5717 * Pick a prime number of hash arenas that is more than narenas
5718 * so that direct hashing of pthread_self() pointers tends to
5719 * spread allocations evenly among the arenas.
5721 assert((narenas
& 1) == 0); /* narenas must be even. */
5722 nprimes
= (sizeof(primes
) >> SIZEOF_INT_2POW
);
5723 parenas
= primes
[nprimes
- 1]; /* In case not enough primes. */
5724 for (i
= 1; i
< nprimes
; i
++) {
5725 if (primes
[i
] > narenas
) {
5726 parenas
= primes
[i
];
5735 # ifndef MALLOC_BALANCE
5740 /* Allocate and initialize arenas. */
5741 arenas
= (arena_t
**)base_alloc(sizeof(arena_t
*) * narenas
);
5742 if (arenas
== NULL
) {
5743 #ifndef MOZ_MEMORY_WINDOWS
5744 malloc_mutex_unlock(&init_lock
);
5749 * Zero the array. In practice, this should always be pre-zeroed,
5750 * since it was just mmap()ed, but let's be sure.
5752 memset(arenas
, 0, sizeof(arena_t
*) * narenas
);
5755 * Initialize one arena here. The rest are lazily created in
5756 * choose_arena_hard().
5759 if (arenas
[0] == NULL
) {
5760 #ifndef MOZ_MEMORY_WINDOWS
5761 malloc_mutex_unlock(&init_lock
);
5767 * Assign the initial arena to the initial thread, in order to avoid
5768 * spurious creation of an extra arena if the application switches to
5771 #ifdef MOZ_MEMORY_WINDOWS
5772 TlsSetValue(tlsIndex
, arenas
[0]);
5774 arenas_map
= arenas
[0];
5779 * Seed here for the initial thread, since choose_arena_hard() is only
5780 * called for other threads. The seed value doesn't really matter.
5782 #ifdef MALLOC_BALANCE
5786 malloc_spin_init(&arenas_lock
);
5788 #ifdef MALLOC_VALIDATE
5789 chunk_rtree
= malloc_rtree_new((SIZEOF_PTR
<< 3) - opt_chunk_2pow
);
5790 if (chunk_rtree
== NULL
)
5794 malloc_initialized
= true;
5795 #ifndef MOZ_MEMORY_WINDOWS
5796 malloc_mutex_unlock(&init_lock
);
5801 /* XXX Why not just expose malloc_print_stats()? */
5802 #ifdef MOZ_MEMORY_WINDOWS
5807 malloc_print_stats();
5812 * End general internal functions.
5814 /******************************************************************************/
5816 * Begin malloc(3)-compatible functions.
5820 * Inline the standard malloc functions if they are being subsumed by Darwin's
5821 * zone infrastructure.
5823 #ifdef MOZ_MEMORY_DARWIN
5824 # define ZONE_INLINE inline
5826 # define ZONE_INLINE
5829 /* Mangle standard interfaces on Darwin and Android,
5830 in order to avoid linking problems. */
5831 #if defined(MOZ_MEMORY_DARWIN)
5832 #define malloc(a) moz_malloc(a)
5833 #define valloc(a) moz_valloc(a)
5834 #define calloc(a, b) moz_calloc(a, b)
5835 #define realloc(a, b) moz_realloc(a, b)
5836 #define free(a) moz_free(a)
5839 #if defined(MOZ_MEMORY_ANDROID) || defined(WRAP_MALLOC)
5840 inline void sys_free(void* ptr
) {return free(ptr
);}
5841 #define malloc(a) je_malloc(a)
5842 #define valloc(a) je_valloc(a)
5843 #define calloc(a, b) je_calloc(a, b)
5844 #define realloc(a, b) je_realloc(a, b)
5845 #define free(a) je_free(a)
5846 #define posix_memalign(a, b, c) je_posix_memalign(a, b, c)
5848 char *je_strndup(const char *src
, size_t len
) {
5849 char* dst
= (char*)je_malloc(len
+ 1);
5851 strncpy(dst
, src
, len
+ 1);
5854 char *je_strdup(const char *src
) {
5855 size_t len
= strlen(src
);
5856 return je_strndup(src
, len
);
5866 if (malloc_init()) {
5873 if (opt_sysv
== false)
5884 ret
= imalloc(size
);
5888 #ifdef MALLOC_XMALLOC
5890 _malloc_message(_getprogname(),
5891 ": (malloc) Error in malloc(): out of memory\n", "",
5899 UTRACE(0, size
, ret
);
5903 #ifdef MOZ_MEMORY_SOLARIS
5906 memalign(size_t alignment
, size_t size
);
5907 #pragma no_inline(memalign)
5908 # elif (defined(__GNU_C__))
5909 __attribute__((noinline
))
5915 memalign(size_t alignment
, size_t size
)
5919 assert(((alignment
- 1) & alignment
) == 0);
5921 if (malloc_init()) {
5928 if (opt_sysv
== false)
5939 alignment
= alignment
< sizeof(void*) ? sizeof(void*) : alignment
;
5940 ret
= ipalloc(alignment
, size
);
5943 #ifdef MALLOC_XMALLOC
5944 if (opt_xmalloc
&& ret
== NULL
) {
5945 _malloc_message(_getprogname(),
5946 ": (malloc) Error in memalign(): out of memory\n", "", "");
5950 UTRACE(0, size
, ret
);
5956 posix_memalign(void **memptr
, size_t alignment
, size_t size
)
5960 /* Make sure that alignment is a large enough power of 2. */
5961 if (((alignment
- 1) & alignment
) != 0 || alignment
< sizeof(void *)) {
5962 #ifdef MALLOC_XMALLOC
5964 _malloc_message(_getprogname(),
5965 ": (malloc) Error in posix_memalign(): "
5966 "invalid alignment\n", "", "");
5973 /* The 0-->1 size promotion is done in the memalign() call below */
5975 #ifdef MOZ_MEMORY_DARWIN
5976 result
= moz_memalign(alignment
, size
);
5978 result
= memalign(alignment
, size
);
5991 #ifdef MOZ_MEMORY_DARWIN
5992 return (moz_memalign(pagesize
, size
));
5994 return (memalign(pagesize
, size
));
6000 calloc(size_t num
, size_t size
)
6005 if (malloc_init()) {
6011 num_size
= num
* size
;
6012 if (num_size
== 0) {
6014 if ((opt_sysv
== false) && ((num
== 0) || (size
== 0)))
6024 * Try to avoid division here. We know that it isn't possible to
6025 * overflow during multiplication if neither operand uses any of the
6026 * most significant half of the bits in a size_t.
6028 } else if (((num
| size
) & (SIZE_T_MAX
<< (sizeof(size_t) << 2)))
6029 && (num_size
/ size
!= num
)) {
6030 /* size_t overflow. */
6035 ret
= icalloc(num_size
);
6039 #ifdef MALLOC_XMALLOC
6041 _malloc_message(_getprogname(),
6042 ": (malloc) Error in calloc(): out of memory\n", "",
6050 UTRACE(0, num_size
, ret
);
6056 realloc(void *ptr
, size_t size
)
6062 if (opt_sysv
== false)
6076 assert(malloc_initialized
);
6078 ret
= iralloc(ptr
, size
);
6081 #ifdef MALLOC_XMALLOC
6083 _malloc_message(_getprogname(),
6084 ": (malloc) Error in realloc(): out of "
6085 "memory\n", "", "");
6095 ret
= imalloc(size
);
6098 #ifdef MALLOC_XMALLOC
6100 _malloc_message(_getprogname(),
6101 ": (malloc) Error in realloc(): out of "
6102 "memory\n", "", "");
6113 UTRACE(ptr
, size
, ret
);
6126 * A version of idalloc that checks for NULL pointer but only for
6127 * huge allocations assuming that CHUNK_ADDR2OFFSET(NULL) == 0.
6129 assert(CHUNK_ADDR2OFFSET(NULL
) == 0);
6130 offset
= CHUNK_ADDR2OFFSET(ptr
);
6132 arena_dalloc(ptr
, offset
);
6133 else if (ptr
!= NULL
)
6138 * End malloc(3)-compatible functions.
6140 /******************************************************************************/
6142 * Begin non-standard functions.
6144 #ifdef MOZ_MEMORY_ANDROID
6146 malloc_usable_size(void *ptr
)
6149 malloc_usable_size(const void *ptr
)
6153 #ifdef MALLOC_VALIDATE
6154 return (isalloc_validate(ptr
));
6156 assert(ptr
!= NULL
);
6158 return (isalloc(ptr
));
6164 jemalloc_stats(jemalloc_stats_t
*stats
)
6168 assert(stats
!= NULL
);
6171 * Gather runtime settings.
6173 stats
->opt_abort
= opt_abort
;
6180 #ifdef MALLOC_UTRACE
6189 stats
->opt_xmalloc
=
6190 #ifdef MALLOC_XMALLOC
6191 opt_xmalloc
? true :
6199 stats
->narenas
= narenas
;
6200 stats
->balance_threshold
=
6201 #ifdef MALLOC_BALANCE
6202 opt_balance_threshold
6207 stats
->quantum
= quantum
;
6208 stats
->small_max
= small_max
;
6209 stats
->large_max
= arena_maxclass
;
6210 stats
->chunksize
= chunksize
;
6211 stats
->dirty_max
= opt_dirty_max
;
6214 * Gather current memory usage statistics.
6217 stats
->committed
= 0;
6218 stats
->allocated
= 0;
6221 /* Get huge mapped/allocated. */
6222 malloc_mutex_lock(&huge_mtx
);
6223 stats
->mapped
+= stats_chunks
.curchunks
* chunksize
;
6224 #ifdef MALLOC_DECOMMIT
6225 stats
->committed
+= huge_allocated
;
6227 stats
->allocated
+= huge_allocated
;
6228 malloc_mutex_unlock(&huge_mtx
);
6230 /* Get base mapped. */
6231 malloc_mutex_lock(&base_mtx
);
6232 stats
->mapped
+= base_mapped
;
6233 #ifdef MALLOC_DECOMMIT
6234 assert(base_committed
<= base_mapped
);
6235 stats
->committed
+= base_committed
;
6237 malloc_mutex_unlock(&base_mtx
);
6239 /* Iterate over arenas and their chunks. */
6240 for (i
= 0; i
< narenas
; i
++) {
6241 arena_t
*arena
= arenas
[i
];
6242 if (arena
!= NULL
) {
6243 arena_chunk_t
*chunk
;
6245 malloc_spin_lock(&arena
->lock
);
6246 stats
->allocated
+= arena
->stats
.allocated_small
;
6247 stats
->allocated
+= arena
->stats
.allocated_large
;
6248 #ifdef MALLOC_DECOMMIT
6249 stats
->committed
+= (arena
->stats
.committed
<<
6252 stats
->dirty
+= (arena
->ndirty
<< pagesize_2pow
);
6253 malloc_spin_unlock(&arena
->lock
);
6257 #ifndef MALLOC_DECOMMIT
6258 stats
->committed
= stats
->mapped
;
6260 assert(stats
->mapped
>= stats
->committed
);
6261 assert(stats
->committed
>= stats
->allocated
);
6263 #endif /* MALLOC_STATS */
6265 #ifdef MOZ_MEMORY_WINDOWS
6267 _recalloc(void *ptr
, size_t count
, size_t size
)
6269 size_t oldsize
= (ptr
!= NULL
) ? isalloc(ptr
) : 0;
6270 size_t newsize
= count
* size
;
6273 * In order for all trailing bytes to be zeroed, the caller needs to
6274 * use calloc(), followed by recalloc(). However, the current calloc()
6275 * implementation only zeros the bytes requested, so if recalloc() is
6276 * to work 100% correctly, calloc() will need to change to zero
6280 ptr
= realloc(ptr
, newsize
);
6281 if (ptr
!= NULL
&& oldsize
< newsize
) {
6282 memset((void *)((uintptr_t)ptr
+ oldsize
), 0, newsize
-
6290 * This impl of _expand doesn't ever actually expand or shrink blocks: it
6291 * simply replies that you may continue using a shrunk block.
6294 _expand(void *ptr
, size_t newsize
)
6296 if (isalloc(ptr
) >= newsize
)
6303 _msize(const void *ptr
)
6306 return malloc_usable_size(ptr
);
6311 * End non-standard functions.
6313 /******************************************************************************/
6315 * Begin library-private functions, used by threading libraries for protection
6316 * of malloc during fork(). These functions are only called if the program is
6317 * running in threaded mode, so there is no need to check whether the program
6322 _malloc_prefork(void)
6326 /* Acquire all mutexes in a safe order. */
6328 malloc_spin_lock(&arenas_lock
);
6329 for (i
= 0; i
< narenas
; i
++) {
6330 if (arenas
[i
] != NULL
)
6331 malloc_spin_lock(&arenas
[i
]->lock
);
6334 malloc_mutex_lock(&base_mtx
);
6336 malloc_mutex_lock(&huge_mtx
);
6340 _malloc_postfork(void)
6344 /* Release all mutexes, now that fork() has completed. */
6346 malloc_mutex_unlock(&huge_mtx
);
6348 malloc_mutex_unlock(&base_mtx
);
6350 for (i
= 0; i
< narenas
; i
++) {
6351 if (arenas
[i
] != NULL
)
6352 malloc_spin_unlock(&arenas
[i
]->lock
);
6354 malloc_spin_unlock(&arenas_lock
);
6358 * End library-private functions.
6360 /******************************************************************************/
6366 #ifdef MOZ_MEMORY_DARWIN
6367 static malloc_zone_t zone
;
6368 static struct malloc_introspection_t zone_introspect
;
6371 zone_size(malloc_zone_t
*zone
, void *ptr
)
6375 * There appear to be places within Darwin (such as setenv(3)) that
6376 * cause calls to this function with pointers that *no* zone owns. If
6377 * we knew that all pointers were owned by *some* zone, we could split
6378 * our zone into two parts, and use one as the default allocator and
6379 * the other as the default deallocator/reallocator. Since that will
6380 * not work in practice, we must check all pointers to assure that they
6381 * reside within a mapped chunk before determining size.
6383 return (isalloc_validate(ptr
));
6387 zone_malloc(malloc_zone_t
*zone
, size_t size
)
6390 return (malloc(size
));
6394 zone_calloc(malloc_zone_t
*zone
, size_t num
, size_t size
)
6397 return (calloc(num
, size
));
6401 zone_valloc(malloc_zone_t
*zone
, size_t size
)
6403 void *ret
= NULL
; /* Assignment avoids useless compiler warning. */
6405 posix_memalign(&ret
, pagesize
, size
);
6411 zone_free(malloc_zone_t
*zone
, void *ptr
)
6418 zone_realloc(malloc_zone_t
*zone
, void *ptr
, size_t size
)
6421 return (realloc(ptr
, size
));
6425 zone_destroy(malloc_zone_t
*zone
)
6428 /* This function should never be called. */
6434 zone_good_size(malloc_zone_t
*zone
, size_t size
)
6440 * Actually create an object of the appropriate size, then find out
6441 * how large it could have been without moving up to the next size
6455 zone_force_lock(malloc_zone_t
*zone
)
6462 zone_force_unlock(malloc_zone_t
*zone
)
6468 static malloc_zone_t
*
6472 assert(malloc_initialized
);
6474 zone
.size
= (void *)zone_size
;
6475 zone
.malloc
= (void *)zone_malloc
;
6476 zone
.calloc
= (void *)zone_calloc
;
6477 zone
.valloc
= (void *)zone_valloc
;
6478 zone
.free
= (void *)zone_free
;
6479 zone
.realloc
= (void *)zone_realloc
;
6480 zone
.destroy
= (void *)zone_destroy
;
6481 zone
.zone_name
= "jemalloc_zone";
6482 zone
.batch_malloc
= NULL
;
6483 zone
.batch_free
= NULL
;
6484 zone
.introspect
= &zone_introspect
;
6486 zone_introspect
.enumerator
= NULL
;
6487 zone_introspect
.good_size
= (void *)zone_good_size
;
6488 zone_introspect
.check
= NULL
;
6489 zone_introspect
.print
= NULL
;
6490 zone_introspect
.log
= NULL
;
6491 zone_introspect
.force_lock
= (void *)zone_force_lock
;
6492 zone_introspect
.force_unlock
= (void *)zone_force_unlock
;
6493 zone_introspect
.statistics
= NULL
;
6498 __attribute__((constructor
))
6500 jemalloc_darwin_init(void)
6502 extern unsigned malloc_num_zones
;
6503 extern malloc_zone_t
**malloc_zones
;
6505 if (malloc_init_hard())
6509 * The following code is *not* thread-safe, so it's critical that
6510 * initialization be manually triggered.
6513 /* Register the custom zones. */
6514 malloc_zone_register(create_zone());
6515 assert(malloc_zones
[malloc_num_zones
- 1] == &zone
);
6518 * Shift malloc_zones around so that zone is first, which makes it the
6521 assert(malloc_num_zones
> 1);
6522 memmove(&malloc_zones
[1], &malloc_zones
[0],
6523 sizeof(malloc_zone_t
*) * (malloc_num_zones
- 1));
6524 malloc_zones
[0] = &zone
;
6527 #elif defined(__GLIBC__) && !defined(__UCLIBC__)
6529 * glibc provides the RTLD_DEEPBIND flag for dlopen which can make it possible
6530 * to inconsistently reference libc's malloc(3)-compatible functions
6533 * These definitions interpose hooks in glibc. The functions are actually
6534 * passed an extra argument for the caller return address, which will be
6538 void (*__free_hook
)(void *ptr
) = free
;
6539 void *(*__malloc_hook
)(size_t size
) = malloc
;
6540 void *(*__realloc_hook
)(void *ptr
, size_t size
) = realloc
;
6541 void *(*__memalign_hook
)(size_t alignment
, size_t size
) = memalign
;
6544 #elif defined(RTLD_DEEPBIND)
6546 * XXX On systems that support RTLD_GROUP or DF_1_GROUP, do their
6547 * implementations permit similar inconsistencies? Should STV_SINGLETON
6548 * visibility be used for interposition where available?
6550 # error "Interposing malloc is unsafe on this system without libc malloc hooks."