/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ /* vim: set ts=8 sts=2 et sw=2 tw=80: */ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
// Portions of this file were originally under the following license: // // Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>. // All rights reserved. // Copyright (C) 2007-2017 Mozilla Foundation. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions // are met: // 1. Redistributions of source code must retain the above copyright // notice(s), this list of conditions and the following disclaimer as // the first lines of this file unmodified other than the possible // addition of one or more copyright notices. // 2. Redistributions in binary form must reproduce the above copyright // notice(s), this list of conditions and the following disclaimer in // the documentation and/or other materials provided with the // distribution. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR // BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE // OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // ***************************************************************************** // // This allocator implementation is designed to provide scalable performance // for multi-threaded programs on multi-processor systems. The following // features are included for this purpose: // // + Multiple arenas are used if there are multiple CPUs, which reduces lock // contention and cache sloshing. // // + Cache line sharing between arenas is avoided for internal data // structures. // // + Memory is managed in chunks and runs (chunks can be split into runs), // rather than as individual pages. This provides a constant-time // mechanism for associating allocations with particular arenas. // // Allocation requests are rounded up to the nearest size class, and no record // of the original request size is maintained. Allocations are broken into // categories according to size class. Assuming runtime defaults, the size // classes in each category are as follows (for x86, x86_64 and Apple Silicon): // // |=========================================================| // | Category | Subcategory | x86 | x86_64 | Mac ARM | // |---------------------------+---------+---------+---------| // | Word size | 32 bit | 64 bit | 64 bit | // | Page size | 4 Kb | 4 Kb | 16 Kb | // |=========================================================| // | Small | Tiny | 4/-w | -w | - | // | | | 8 | 8/-w | 8 | // | |----------------+---------|---------|---------| // | | Quantum-spaced | 16 | 16 | 16 | // | | | 32 | 32 | 32 | // | | | 48 | 48 | 48 | // | | | ... | ... | ... | // | | | 480 | 480 | 480 | // | | | 496 | 496 | 496 | // | |----------------+---------|---------|---------| // | | Quantum-wide- | 512 | 512 | 512 | // | | spaced | 768 | 768 | 768 | // | | | ... | ... | ... | // | | | 3584 | 3584 | 3584 | // | | | 3840 | 3840 | 3840 | // | |----------------+---------|---------|---------| // | | Sub-page | - | - | 4096 | // | | | - | - | 8 kB | // |=========================================================| // | Large | 4 kB | 4 kB | - | // | | 8 kB | 8 kB | - | // | | 12 kB | 12 kB | - | // | | 16 kB | 16 kB | 16 kB | // | | ... | ... | - | // | | 32 kB | 32 kB | 32 kB | // | | ... | ... | ... | // | | 1008 kB | 1008 kB | 1008 kB | // | | 1012 kB | 1012 kB | - | // | | 1016 kB | 1016 kB | - | // | | 1020 kB | 1020 kB | - | // |=========================================================| // | Huge | 1 MB | 1 MB | 1 MB | // | | 2 MB | 2 MB | 2 MB | // | | 3 MB | 3 MB | 3 MB | // | | ... | ... | ... | // |=========================================================| // // Legend: // n: Size class exists for this platform. // n/-w: This size class doesn't exist on Windows (see kMinTinyClass). // -: This size class doesn't exist for this platform. // ...: Size classes follow a pattern here. // // NOTE: Due to Mozilla bug 691003, we cannot reserve less than one word for an // allocation on Linux or Mac. So on 32-bit *nix, the smallest bucket size is // 4 bytes, and on 64-bit, the smallest bucket size is 8 bytes. // // A different mechanism is used for each category: // // Small : Each size class is segregated into its own set of runs. Each run // maintains a bitmap of which regions are free/allocated. // // Large : Each allocation is backed by a dedicated run. Metadata are stored // in the associated arena chunk header maps. // // Huge : Each allocation is backed by a dedicated contiguous set of chunks. // Metadata are stored in a separate red-black tree. // // *****************************************************************************
#include <cstring> #include <cerrno> #include <optional> #include <type_traits> #ifdef XP_WIN # include <io.h> # include <windows.h> #else # include <sys/mman.h> # include <unistd.h> #endif #ifdef XP_DARWIN # include <libkern/OSAtomic.h> # include <mach/mach_init.h> # include <mach/vm_map.h> #endif
#include"mozilla/Atomics.h" #include"mozilla/Alignment.h" #include"mozilla/ArrayUtils.h" #include"mozilla/Assertions.h" #include"mozilla/CheckedInt.h" #include"mozilla/DebugOnly.h" #include"mozilla/DoublyLinkedList.h" #include"mozilla/HelperMacros.h" #include"mozilla/Likely.h" #include"mozilla/Literals.h" #include"mozilla/MathAlgorithms.h" #include"mozilla/RandomNum.h" // Note: MozTaggedAnonymousMmap() could call an LD_PRELOADed mmap // instead of the one defined here; use only MozTagAnonymousMemory(). #include"mozilla/TaggedAnonymousMemory.h" #include"mozilla/ThreadLocal.h" #include"mozilla/UniquePtr.h" #include"mozilla/Unused.h" #include"mozilla/XorShift128PlusRNG.h" #include"mozilla/fallible.h" #include"rb.h" #include"Mutex.h" #include"PHC.h" #include"Utils.h"
#ifdefined(XP_WIN) # include "mozmemory_utils.h" #endif
// For GetGeckoProcessType(), when it's used. #ifdefined(XP_WIN) && !defined(JS_STANDALONE) # include "mozilla/ProcessType.h" #endif
usingnamespace mozilla;
// On Linux, we use madvise(MADV_DONTNEED) to release memory back to the // operating system. If we release 1MB of live pages with MADV_DONTNEED, our // RSS will decrease by 1MB (almost) immediately. // // On Mac, we use madvise(MADV_FREE). Unlike MADV_DONTNEED on Linux, MADV_FREE // on Mac doesn't cause the OS to release the specified pages immediately; the // OS keeps them in our process until the machine comes under memory pressure. // // It's therefore difficult to measure the process's RSS on Mac, since, in the // absence of memory pressure, the contribution from the heap to RSS will not // decrease due to our madvise calls. // // We therefore define MALLOC_DOUBLE_PURGE on Mac. This causes jemalloc to // track which pages have been MADV_FREE'd. You can then call // jemalloc_purge_freed_pages(), which will force the OS to release those // MADV_FREE'd pages, making the process's RSS reflect its true memory usage.
// Define MALLOC_RUNTIME_CONFIG depending on MOZ_DEBUG. Overriding this as // a build option allows us to build mozjemalloc/firefox without runtime asserts // but with runtime configuration. Making some testing easier.
// When MALLOC_STATIC_PAGESIZE is defined, the page size is fixed at // compile-time for better performance, as opposed to determined at // runtime. Some platforms can have different page sizes at runtime // depending on kernel configuration, so they are opted out by default. // Debug builds are opted out too, for test coverage. #ifndef MALLOC_RUNTIME_CONFIG # if !defined(__ia64__) && !defined(__sparc__) && !defined(__mips__) && \
!defined(__aarch64__) && !defined(__powerpc__) && !defined(XP_MACOSX) && \
!defined(__loongarch__) # define MALLOC_STATIC_PAGESIZE 1 # endif #endif
#ifdef XP_WIN # define STDERR_FILENO 2
// Implement getenv without using malloc. staticchar mozillaMallocOptionsBuf[64];
#ifndef XP_WIN // Newer Linux systems support MADV_FREE, but we're not supporting // that properly. bug #1406304. # ifdefined(XP_LINUX) && defined(MADV_FREE) # undef MADV_FREE # endif # ifndef MADV_FREE # define MADV_FREE MADV_DONTNEED # endif #endif
// Some tools, such as /dev/dsp wrappers, LD_PRELOAD libraries that // happen to override mmap() and call dlsym() from their overridden // mmap(). The problem is that dlsym() calls malloc(), and this ends // up in a dead lock in jemalloc. // On these systems, we prefer to directly use the system call. // We do that for Linux systems and kfreebsd with GNU userland. // Note sanity checks are not done (alignment of offset, ...) because // the uses of mmap are pretty limited, in jemalloc. // // On Alpha, glibc has a bug that prevents syscall() to work for system // calls with 6 arguments. #if (defined(XP_LINUX) && !defined(__alpha__)) || \
(defined(__FreeBSD_kernel__) && defined(__GLIBC__)) # include <sys/syscall.h> # ifdefined(SYS_mmap) || defined(SYS_mmap2) staticinlinevoid* _mmap(void* addr, size_t length, int prot, int flags, int fd, off_t offset) { // S390 only passes one argument to the mmap system call, which is a // pointer to a structure containing the arguments. # ifdef __s390__ struct { void* addr;
size_t length; long prot; long flags; long fd;
off_t offset;
} args = {addr, length, prot, flags, fd, offset}; return (void*)syscall(SYS_mmap, &args); # else # ifdefined(ANDROID) && defined(__aarch64__) && defined(SYS_mmap2) // Android NDK defines SYS_mmap2 for AArch64 despite it not supporting mmap2. # undef SYS_mmap2 # endif # ifdef SYS_mmap2 return (void*)syscall(SYS_mmap2, addr, length, prot, flags, fd, offset >> 12); # else return (void*)syscall(SYS_mmap, addr, length, prot, flags, fd, offset); # endif # endif
} # define mmap _mmap # define munmap(a, l) syscall(SYS_munmap, a, l) # endif #endif
// *************************************************************************** // Structures for chunk headers for chunks used for non-huge allocations.
struct arena_t;
// Each element of the chunk map corresponds to one page within the chunk. struct arena_chunk_map_t { // Linkage for run trees. Used for arena_t's tree or available runs.
RedBlackTreeNode<arena_chunk_map_t> link;
// Run address (or size) and various flags are stored together. The bit // layout looks like (assuming 32-bit system): // // ???????? ???????? ????---b fmckdzla // // ? : Unallocated: Run address for first/last pages, unset for internal // pages. // Small: Run address. // Large: Run size for first page, unset for trailing pages. // - : Unused. // b : Busy? // f : Fresh memory? // m : MADV_FREE/MADV_DONTNEED'ed? // c : decommitted? // k : key? // d : dirty? // z : zeroed? // l : large? // a : allocated? // // Following are example bit patterns for consecutive pages from the three // types of runs. // // r : run address // s : run size // x : don't care // - : 0 // [cdzla] : bit set // // Unallocated: // ssssssss ssssssss ssss---- --c----- // xxxxxxxx xxxxxxxx xxxx---- ----d--- // ssssssss ssssssss ssss---- -----z-- // // Note that the size fields are set for the first and last unallocated // page only. The pages in-between have invalid/"don't care" size fields, // they're not cleared during things such as coalescing free runs. // // Pages before the first or after the last page in a free run must be // allocated or busy. Run coalescing depends on the sizes being set in // the first and last page. Purging pages and releasing chunks require // that unallocated pages are always coalesced and the first page has a // correct size. // // Small: // rrrrrrrr rrrrrrrr rrrr---- -------a // rrrrrrrr rrrrrrrr rrrr---- -------a // rrrrrrrr rrrrrrrr rrrr---- -------a // // Large: // ssssssss ssssssss ssss---- ------la // -------- -------- -------- ------la // -------- -------- -------- ------la // // Note that only the first page has the size set. //
size_t bits;
// A page can be in one of several states. // // CHUNK_MAP_ALLOCATED marks allocated pages, the only other bit that can be // combined is CHUNK_MAP_LARGE. // // CHUNK_MAP_LARGE may be combined with CHUNK_MAP_ALLOCATED to show that the // allocation is a "large" allocation (see SizeClass), rather than a run of // small allocations. The interpretation of the gPageSizeMask bits depends onj // this bit, see the description above. // // CHUNK_MAP_DIRTY is used to mark pages that were allocated and are now freed. // They may contain their previous contents (or poison). CHUNK_MAP_DIRTY, when // set, must be the only set bit. // // CHUNK_MAP_MADVISED marks pages which are madvised (with either MADV_DONTNEED // or MADV_FREE). This is only valid if MALLOC_DECOMMIT is not defined. When // set, it must be the only bit set. // // CHUNK_MAP_DECOMMITTED is used if CHUNK_MAP_DECOMMITTED is defined. Unused // dirty pages may be decommitted and marked as CHUNK_MAP_DECOMMITTED. They // must be re-committed with pages_commit() before they can be touched. // // CHUNK_MAP_FRESH is set on pages that have never been used before (the chunk // is newly allocated or they were decommitted and have now been recommitted. // CHUNK_MAP_FRESH is also used for "double purged" pages meaning that they were // madvised and later were unmapped and remapped to force them out of the // program's resident set. This is enabled when MALLOC_DOUBLE_PURGE is defined // (eg on MacOS). // // CHUNK_MAP_BUSY is set by a thread when the thread wants to manipulate the // pages without holding a lock. Other threads must not touch these pages // regardless of whether they hold a lock. // // CHUNK_MAP_ZEROED is set on pages that are known to contain zeros. // // CHUNK_MAP_DIRTY, _DECOMMITED _MADVISED and _FRESH are always mutually // exclusive. // // CHUNK_MAP_KEY is never used on real pages, only on lookup keys. // #define CHUNK_MAP_BUSY ((size_t)0x100U) #define CHUNK_MAP_FRESH ((size_t)0x80U) #define CHUNK_MAP_MADVISED ((size_t)0x40U) #define CHUNK_MAP_DECOMMITTED ((size_t)0x20U) #define CHUNK_MAP_MADVISED_OR_DECOMMITTED \
(CHUNK_MAP_MADVISED | CHUNK_MAP_DECOMMITTED) #define CHUNK_MAP_FRESH_MADVISED_OR_DECOMMITTED \
(CHUNK_MAP_FRESH | CHUNK_MAP_MADVISED | CHUNK_MAP_DECOMMITTED) #define CHUNK_MAP_FRESH_MADVISED_DECOMMITTED_OR_BUSY \
(CHUNK_MAP_FRESH | CHUNK_MAP_MADVISED | CHUNK_MAP_DECOMMITTED | \
CHUNK_MAP_BUSY) #define CHUNK_MAP_KEY ((size_t)0x10U) #define CHUNK_MAP_DIRTY ((size_t)0x08U) #define CHUNK_MAP_ZEROED ((size_t)0x04U) #define CHUNK_MAP_LARGE ((size_t)0x02U) #define CHUNK_MAP_ALLOCATED ((size_t)0x01U)
};
// Arena chunk header. struct arena_chunk_t { // Arena that owns the chunk.
arena_t* arena;
// Linkage for the arena's tree of dirty chunks.
RedBlackTreeNode<arena_chunk_t> link_dirty;
#ifdef MALLOC_DOUBLE_PURGE // If we're double-purging, we maintain a linked list of chunks which // have pages which have been madvise(MADV_FREE)'d but not explicitly // purged. // // We're currently lazy and don't remove a chunk from this list when // all its madvised pages are recommitted.
DoublyLinkedListElement<arena_chunk_t> chunks_madvised_elem; #endif
// Number of dirty pages.
size_t ndirty;
bool mIsPurging; bool mDying;
// Map of pages within chunk that keeps track of free/large/small.
arena_chunk_map_t map[]; // Dynamically sized.
bool IsEmpty();
};
// *************************************************************************** // Constants defining allocator size classes and behavior.
// Our size classes are inclusive ranges of memory sizes. By describing the // minimums and how memory is allocated in each range the maximums can be // calculated.
// Smallest size class to support. On Windows the smallest allocation size // must be 8 bytes on 32-bit, 16 bytes on 64-bit. On Linux and Mac, even // malloc(1) must reserve a word's worth of memory (see Mozilla bug 691003). #ifdef XP_WIN staticconst size_t kMinTinyClass = sizeof(void*) * 2; #else staticconst size_t kMinTinyClass = sizeof(void*); #endif
// Maximum tiny size class. staticconst size_t kMaxTinyClass = 8;
// Smallest quantum-spaced size classes. It could actually also be labelled a // tiny allocation, and is spaced as such from the largest tiny size class. // Tiny classes being powers of 2, this is twice as large as the largest of // them. staticconst size_t kMinQuantumClass = kMaxTinyClass * 2; staticconst size_t kMinQuantumWideClass = 512; staticconst size_t kMinSubPageClass = 4_KiB;
// We can optimise some divisions to shifts if these are powers of two.
static_assert(mozilla::IsPowerOfTwo(kQuantum), "kQuantum is not a power of two");
static_assert(mozilla::IsPowerOfTwo(kQuantumWide), "kQuantumWide is not a power of two");
static_assert(kMaxQuantumClass % kQuantum == 0, "kMaxQuantumClass is not a multiple of kQuantum");
static_assert(kMaxQuantumWideClass % kQuantumWide == 0, "kMaxQuantumWideClass is not a multiple of kQuantumWide");
static_assert(kQuantum < kQuantumWide, "kQuantum must be smaller than kQuantumWide");
static_assert(mozilla::IsPowerOfTwo(kMinSubPageClass), "kMinSubPageClass is not a power of two");
// Number of (2^n)-spaced tiny classes. staticconst size_t kNumTinyClasses =
LOG2(kMaxTinyClass) - LOG2(kMinTinyClass) + 1;
// Number of quantum-spaced classes. We add kQuantum(Max) before subtracting to // avoid underflow when a class is empty (Max<Min). staticconst size_t kNumQuantumClasses =
(kMaxQuantumClass + kQuantum - kMinQuantumClass) / kQuantum; staticconst size_t kNumQuantumWideClasses =
(kMaxQuantumWideClass + kQuantumWide - kMinQuantumWideClass) / kQuantumWide;
// Size and alignment of memory chunks that are allocated by the OS's virtual // memory system. staticconst size_t kChunkSize = 1_MiB; staticconst size_t kChunkSizeMask = kChunkSize - 1;
#ifdef MALLOC_STATIC_PAGESIZE // VM page size. It must divide the runtime CPU page size or the code // will abort. // Platform specific page size conditions copied from js/public/HeapAPI.h # ifdefined(__powerpc64__) staticconst size_t gPageSize = 64_KiB; # elif defined(__loongarch64) staticconst size_t gPageSize = 16_KiB; # else staticconst size_t gPageSize = 4_KiB; # endif staticconst size_t gRealPageSize = gPageSize;
#else // When MALLOC_OPTIONS contains one or several `P`s, the page size used // across the allocator is multiplied by 2 for each `P`, but we also keep // the real page size for code paths that need it. gPageSize is thus a // power of two greater or equal to gRealPageSize. static size_t gRealPageSize; static size_t gPageSize; #endif
// Largest sub-page size class, or zero if there are none
DEFINE_GLOBAL(size_t)
gMaxSubPageClass = gPageSize / 2 >= kMinSubPageClass ? gPageSize / 2 : 0;
// Max size class for bins. #define gMaxBinClass \
(gMaxSubPageClass ? gMaxSubPageClass : kMaxQuantumWideClass)
// Number of sub-page bins.
DEFINE_GLOBAL(uint8_t)
gNumSubPageClasses = []() GLOBAL_CONSTEXPR -> uint8_t { if GLOBAL_CONSTEXPR (gMaxSubPageClass != 0) { return FloorLog2(gMaxSubPageClass) - LOG2(kMinSubPageClass) + 1;
} return 0;
}();
// Number of pages in a chunk.
DEFINE_GLOBAL(size_t) gChunkNumPages = kChunkSize >> gPageSize2Pow;
// Number of pages necessary for a chunk header plus a guard page.
DEFINE_GLOBAL(size_t)
gChunkHeaderNumPages =
1 + (((sizeof(arena_chunk_t) + sizeof(arena_chunk_map_t) * gChunkNumPages +
gPageSizeMask) &
~gPageSizeMask) >>
gPageSize2Pow);
// One chunk, minus the header, minus a guard page
DEFINE_GLOBAL(size_t)
gMaxLargeClass =
kChunkSize - gPageSize - (gChunkHeaderNumPages << gPageSize2Pow);
// Various sanity checks that regard configuration.
GLOBAL_ASSERT(1ULL << gPageSize2Pow == gPageSize, "Page size is not a power of two");
GLOBAL_ASSERT(kQuantum >= sizeof(void*));
GLOBAL_ASSERT(kQuantum <= kQuantumWide);
GLOBAL_ASSERT(!kNumQuantumWideClasses ||
kQuantumWide <= (kMinSubPageClass - kMaxQuantumClass));
// Recycle at most 128 MiB of chunks. This means we retain at most // 6.25% of the process address space on a 32-bit OS for later use. staticconst size_t gRecycleLimit = 128_MiB;
// The current amount of recycled bytes, updated atomically. static Atomic<size_t, ReleaseAcquire> gRecycledSize;
// Maximum number of dirty pages per arena. #define DIRTY_MAX_DEFAULT (1U << 8)
static size_t opt_dirty_max = DIRTY_MAX_DEFAULT;
// Return the smallest chunk multiple that is >= s. #define CHUNK_CEILING(s) (((s) + kChunkSizeMask) & ~kChunkSizeMask)
// Return the smallest cacheline multiple that is >= s. #define CACHELINE_CEILING(s) \
(((s) + (kCacheLineSize - 1)) & ~(kCacheLineSize - 1))
// Return the smallest quantum multiple that is >= a. #define QUANTUM_CEILING(a) (((a) + (kQuantumMask)) & ~(kQuantumMask)) #define QUANTUM_WIDE_CEILING(a) \
(((a) + (kQuantumWideMask)) & ~(kQuantumWideMask))
// Return the smallest sub page-size that is >= a. #define SUBPAGE_CEILING(a) (RoundUpPow2(a))
// Return the smallest pagesize multiple that is >= s. #define PAGE_CEILING(s) (((s) + gPageSizeMask) & ~gPageSizeMask)
// Number of all the small-allocated classes #define NUM_SMALL_CLASSES \
(kNumTinyClasses + kNumQuantumClasses + kNumQuantumWideClasses + \
gNumSubPageClasses)
// *************************************************************************** // MALLOC_DECOMMIT and MALLOC_DOUBLE_PURGE are mutually exclusive. #ifdefined(MALLOC_DECOMMIT) && defined(MALLOC_DOUBLE_PURGE) # error MALLOC_DECOMMIT and MALLOC_DOUBLE_PURGE are mutually exclusive. #endif
staticvoid* base_alloc(size_t aSize);
// Set to true once the allocator has been initialized. #ifdefined(_MSC_VER) && !defined(__clang__) // MSVC may create a static initializer for an Atomic<bool>, which may actually // run after `malloc_init` has been called once, which triggers multiple // initializations. // We work around the problem by not using an Atomic<bool> at all. There is a // theoretical problem with using `malloc_initialized` non-atomically, but // practically, this is only true if `malloc_init` is never called before // threads are created. staticbool malloc_initialized; #else static Atomic<bool, MemoryOrdering::ReleaseAcquire> malloc_initialized; #endif
// This lock must be held while bootstrapping us. static StaticMutex gInitLock MOZ_UNANNOTATED = {STATIC_MUTEX_INIT};
// *************************************************************************** // Statistics data structures.
struct arena_stats_t { // Number of bytes currently mapped.
size_t mapped;
// Current number of committed pages (non madvised/decommitted)
size_t committed;
// The number of "memory operations" aka mallocs/frees.
uint64_t operations;
};
// *************************************************************************** // Extent data structures.
enum ChunkType {
UNKNOWN_CHUNK,
ZEROED_CHUNK, // chunk only contains zeroes.
ARENA_CHUNK, // used to back arena runs created by arena_t::AllocRun.
HUGE_CHUNK, // used to back huge allocations (e.g. arena_t::MallocHuge).
RECYCLED_CHUNK, // chunk has been stored for future use by chunk_recycle.
};
// Tree of extents. struct extent_node_t { union { // Linkage for the size/address-ordered tree for chunk recycling.
RedBlackTreeNode<extent_node_t> mLinkBySize; // Arena id for huge allocations. It's meant to match mArena->mId, // which only holds true when the arena hasn't been disposed of.
arena_id_t mArenaId;
};
// Linkage for the address-ordered tree.
RedBlackTreeNode<extent_node_t> mLinkByAddr;
// Pointer to the extent that this tree node is responsible for. void* mAddr;
// Total region size.
size_t mSize;
union { // What type of chunk is there; used for chunk recycling.
ChunkType mChunkType;
// A pointer to the associated arena, for huge allocations.
arena_t* mArena;
};
};
// Describe size classes to which allocations are rounded up to. // TODO: add large and huge types when the arena allocation code // changes in a way that allows it to be beneficial. class SizeClass { public: enum ClassType {
Tiny,
Quantum,
QuantumWide,
SubPage,
Large,
};
// Fast division // // During deallocation we want to divide by the size class. This class // provides a routine and sets up a constant as follows. // // To divide by a number D that is not a power of two we multiply by (2^17 / // D) and then right shift by 17 positions. // // X / D // // becomes // // (X * m) >> p // // Where m is calculated during the FastDivisor constructor similarly to: // // m = 2^p / D // template <typename T> class FastDivisor { private: // The shift amount (p) is chosen to minimise the size of m while // working for divisors up to 65536 in steps of 16. I arrived at 17 // experimentally. I wanted a low number to minimise the range of m // so it can fit in a uint16_t, 16 didn't work but 17 worked perfectly. // // We'd need to increase this if we allocated memory on smaller boundaries // than 16. staticconstunsigned p = 17;
// We can fit the inverted divisor in 16 bits, but we template it here for // convenience.
T m;
public: // Needed so mBins can be constructed.
FastDivisor() : m(0) {}
// divide_inv_shift is large enough.
MOZ_ASSERT((1U << p) >= div);
// The calculation here for m is formula 26 from Section // 10-9 "Unsigned Division by Divisors >= 1" in // Henry S. Warren, Jr.'s Hacker's Delight, 2nd Ed. unsigned m_ = ((1U << p) + div - 1 - (((1U << p) - 1) % div)) / div;
// Make sure that max * m does not overflow.
MOZ_DIAGNOSTIC_ASSERT(max < UINT_MAX / m_);
MOZ_ASSERT(m_ <= std::numeric_limits<T>::max());
m = static_cast<T>(m_);
// Initialisation made m non-zero.
MOZ_ASSERT(m);
// Test that all the divisions in the range we expected would work. #ifdef MOZ_DEBUG for (unsigned num = 0; num < max; num += div) {
MOZ_ASSERT(num / div == divide(num));
} #endif
}
// Note that this always occurs in uint32_t regardless of m's type. If m is // a uint16_t it will be zero-extended before the multiplication. We also use // uint32_t rather than something that could possibly be larger because it is // most-likely the cheapest multiplication. inline uint32_t divide(uint32_t num) const { // Check that m was initialised.
MOZ_ASSERT(m); return (num * m) >> p;
}
};
// *************************************************************************** // Radix tree data structures. // // The number of bits passed to the template is the number of significant bits // in an address to do a radix lookup with. // // An address is looked up by splitting it in kBitsPerLevel bit chunks, except // the most significant bits, where the bit chunk is kBitsAtLevel1 which can be // different if Bits is not a multiple of kBitsPerLevel. // // With e.g. sizeof(void*)=4, Bits=16 and kBitsPerLevel=8, an address is split // like the following: // 0x12345678 -> mRoot[0x12][0x34] template <size_t Bits> class AddressRadixTree { // Size of each radix tree node (as a power of 2). // This impacts tree depth. #ifdef HAVE_64BIT_BUILD staticconst size_t kNodeSize = kCacheLineSize; #else staticconst size_t kNodeSize = 16_KiB; #endif staticconst size_t kBitsPerLevel = LOG2(kNodeSize) - LOG2(sizeof(void*)); staticconst size_t kBitsAtLevel1 =
(Bits % kBitsPerLevel) ? Bits % kBitsPerLevel : kBitsPerLevel; staticconst size_t kHeight = (Bits + kBitsPerLevel - 1) / kBitsPerLevel;
static_assert(kBitsAtLevel1 + (kHeight - 1) * kBitsPerLevel == Bits, "AddressRadixTree parameters don't work out");
Mutex mLock MOZ_UNANNOTATED; // We guard only the single slot creations and assume read-only is safe // at any time. void** mRoot;
// On 64-bit platforms, having the arena_bin_t pointer following // the mMagic field means there's padding between both fields, making // the run header larger than necessary. // But when MOZ_DIAGNOSTIC_ASSERT_ENABLED is not set, starting the // header with this field followed by the arena_bin_t pointer yields // the same padding. We do want the mMagic field to appear first, so // depending whether MOZ_DIAGNOSTIC_ASSERT_ENABLED is set or not, we // move some field to avoid padding.
// Number of free regions in run. unsigned mNumFree; #endif
// Used by arena_bin_t::mNonFullRuns.
DoublyLinkedListElement<arena_run_t> mRunListElem;
// Bin this run is associated with.
arena_bin_t* mBin;
// Index of first element that might have a free region. unsigned mRegionsMinElement;
#if !defined(MOZ_DIAGNOSTIC_ASSERT_ENABLED) // Number of free regions in run. unsigned mNumFree; #endif
// Bitmask of in-use regions (0: in use, 1: free). unsigned mRegionsMask[]; // Dynamically sized.
};
struct arena_bin_t { // We use a LIFO ("last-in-first-out") policy to refill non-full runs. // // This has the following reasons: // 1. It is cheap, as all our non-full-runs' book-keeping is O(1), no // tree-balancing or walking is needed. // 2. It also helps to increase the probability for CPU cache hits for the // book-keeping and the reused slots themselves, as the same memory was // most recently touched during free, especially when used from the same // core (or via the same shared cache, depending on the architecture).
DoublyLinkedList<arena_run_t> mNonFullRuns;
// Bin's size class.
size_t mSizeClass;
// Total number of regions in a run for this bin's size class.
uint32_t mRunNumRegions;
// Number of elements in a run's mRegionsMask for this bin's size class.
uint32_t mRunNumRegionsMask;
// Offset of first region in a run for this bin's size class.
uint32_t mRunFirstRegionOffset;
// Current number of runs in this bin, full or otherwise.
uint32_t mNumRuns;
// A constant for fast division by size class. This value is 16 bits wide so // it is placed last.
FastDivisor<uint16_t> mSizeDivisor;
// Total number of pages in a run for this bin's size class.
uint8_t mRunSizePages;
// Amount of overhead runs are allowed to have. static constexpr double kRunOverhead = 1.6_percent; static constexpr double kRunRelaxedOverhead = 2.4_percent;
// We try to keep the above structure aligned with common cache lines sizes, // often that's 64 bytes on x86 and ARM, we don't make assumptions for other // architectures. #ifdefined(__x86_64__) || defined(__aarch64__) // On 64bit platforms this structure is often 48 bytes // long, which means every other array element will be properly aligned.
static_assert(sizeof(arena_bin_t) == 48); #elifdefined(__x86__) || defined(__arm__)
static_assert(sizeof(arena_bin_t) == 32); #endif
// Linkage for the tree of arenas by id. // This just provides the memory to be used by the collection tree // and thus needs no arena_t::mLock.
RedBlackTreeNode<arena_t> mLink;
// Arena id, that we keep away from the beginning of the struct so that // free list pointers in TypedBaseAlloc<arena_t> don't overflow in it, // and it keeps the value it had after the destructor.
arena_id_t mId;
// Operations on this arena require that lock be locked. The MaybeMutex // class will elude locking if the arena is accessed from a single thread // only (currently only the main thread can be used like this). // Can be acquired while holding gArenas.mLock, but must not be acquired or // held while holding or acquiring gArenas.mPurgeListLock. //
MaybeMutex mLock MOZ_UNANNOTATED;
// The lock is required to write to fields of mStats, but it is not needed to // read them, so long as inconsistents reads are okay (fields might not make // sense together).
arena_stats_t mStats MOZ_GUARDED_BY(mLock);
// We can read the allocated counts from mStats without a lock:
size_t AllocatedBytes() const MOZ_NO_THREAD_SAFETY_ANALYSIS { return mStats.allocated_small + mStats.allocated_large;
}
// We can read the operations field from mStats without a lock:
uint64_t Operations() const MOZ_NO_THREAD_SAFETY_ANALYSIS { return mStats.operations;
}
private: // Tree of dirty-page-containing chunks this arena manages.
RedBlackTree<arena_chunk_t, ArenaDirtyChunkTrait> mChunksDirty
MOZ_GUARDED_BY(mLock);
#ifdef MALLOC_DOUBLE_PURGE // Head of a linked list of MADV_FREE'd-page-containing chunks this // arena manages.
DoublyLinkedList<arena_chunk_t> mChunksMAdvised MOZ_GUARDED_BY(mLock); #endif
// In order to avoid rapid chunk allocation/deallocation when an arena // oscillates right on the cusp of needing a new chunk, cache the most // recently freed chunk. The spare is left in the arena's chunk trees // until it is deleted. // // There is one spare chunk per arena, rather than one spare total, in // order to avoid interactions between multiple threads that could make // a single spare inadequate.
arena_chunk_t* mSpare MOZ_GUARDED_BY(mLock);
// A per-arena opt-in to randomize the offset of small allocations // Needs no lock, read-only. bool mRandomizeSmallAllocations;
// A pseudorandom number generator. Initially null, it gets initialized // on first use to avoid recursive malloc initialization (e.g. on OSX // arc4random allocates memory).
mozilla::non_crypto::XorShift128PlusRNG* mPRNG MOZ_GUARDED_BY(mLock); bool mIsPRNGInitializing MOZ_GUARDED_BY(mLock);
public: // Whether this is a private arena. Multiple public arenas are just a // performance optimization and not a safety feature. // // Since, for example, we don't want thread-local arenas to grow too much, we // use the default arena for bigger allocations. We use this member to allow // realloc() to switch out of our arena if needed (which is not allowed for // private arenas for security). // Needs no lock, read-only. bool mIsPrivate;
// Current count of pages within unused runs that are potentially // dirty, and for which madvise(... MADV_FREE) has not been called. By // tracking this, we can institute a limit on how much dirty unused // memory is mapped for each arena.
size_t mNumDirty MOZ_GUARDED_BY(mLock);
// Precalculated value for faster checks.
size_t mMaxDirty MOZ_GUARDED_BY(mLock);
// The current number of pages that are available without a system call (but // probably a page fault).
size_t mNumMAdvised MOZ_GUARDED_BY(mLock);
size_t mNumFresh MOZ_GUARDED_BY(mLock);
// Maximum value allowed for mNumDirty. // Needs no lock, read-only.
size_t mMaxDirtyBase;
// Needs no lock, read-only.
int32_t mMaxDirtyIncreaseOverride;
int32_t mMaxDirtyDecreaseOverride;
// The link to gArenas.mOutstandingPurges. // Note that this must only be accessed while holding gArenas.mPurgeListLock // (but not arena_t.mLock !) through gArenas.mOutstandingPurges.
DoublyLinkedListElement<arena_t> mPurgeListElem; // A flag that indicates if arena is (or will be) in mOutstandingPurges. // When set true a thread has committed to adding a purge request for this // arena. Cleared only by Purge when we know we are completely done. // This is necessary to avoid accessing the list (and list lock) on // every call to ShouldStartPurge(); bool mIsDeferredPurgePending MOZ_GUARDED_BY(mLock); // A mirror of ArenaCollection::mIsDeferredPurgeEnabled, here only to // optimize memory reads in ShouldStartPurge(). bool mIsDeferredPurgeEnabled MOZ_GUARDED_BY(mLock);
private: // Size/address-ordered tree of this arena's available runs. This tree // is used for first-best-fit run allocation.
RedBlackTree<arena_chunk_map_t, ArenaAvailTreeTrait> mRunsAvail
MOZ_GUARDED_BY(mLock);
// Remove the chunk from the arena. This removes it from all the page counts. // It assumes its run has already been removed and lets the caller clear // mSpare as necessary. bool RemoveChunk(arena_chunk_t* aChunk) MOZ_REQUIRES(mLock);
// This may return a chunk that should be destroyed with chunk_dealloc outside // of the arena lock. It is not the same chunk as was passed in (since that // chunk now becomes mSpare).
[[nodiscard]] arena_chunk_t* DemoteChunkToSpare(arena_chunk_t* aChunk)
MOZ_REQUIRES(mLock);
// Try to merge the run with its neighbours. Returns the new index of the run // (since it may have merged with an earlier one).
size_t TryCoalesce(arena_chunk_t* aChunk, size_t run_ind, size_t run_pages,
size_t size) MOZ_REQUIRES(mLock);
// This may return a chunk that should be destroyed with chunk_dealloc outside // of the arena lock. It is not the same chunk as was passed in (since that // chunk now becomes mSpare).
[[nodiscard]] inline arena_chunk_t* DallocSmall(arena_chunk_t* aChunk, void* aPtr,
arena_chunk_map_t* aMapElm)
MOZ_REQUIRES(mLock);
#ifdef MALLOC_DECOMMIT // During a commit operation (for aReqPages) we have the opportunity of // commiting at most aRemPages additional pages. How many should we commit to // amortise system calls?
size_t ExtraCommitPages(size_t aReqPages, size_t aRemainingPages)
MOZ_REQUIRES(mLock); #endif
// Purge some dirty pages. // // If this arena has more than mMaxDirty dirty pages or aForce is // true, then purge one run of dirty pages. // // This must be called without the mLock held (it'll take the lock). // // To release more than a single run of pages then it's best to call Purge // in a loop. It returns true if mNumDirty > mMaxDirty so that the // caller knows if the loop should continue. // bool Purge(bool aForce = false) MOZ_EXCLUDES(mLock);
// Purging memory is seperated into 3 phases. // * FindDirtyPages() which find the dirty pages in a chunk and marks the // run and chunk as busy while holding the lock. // * Release the pages (without the lock) // * UpdatePagesAndCounts() which marks the dirty pages as not-dirty and // updates other counters (while holding the lock). // // FindDirtyPages() will return false purging should not continue purging in // this chunk. Either because it has no dirty pages or is dying. bool FindDirtyPages(bool aPurgedOnce) MOZ_REQUIRES(mArena.mLock);
// Returns a pair, the first field indicates if there are more dirty pages // remaining in the current chunk. The second field if non-null points to a // chunk that must be released by the caller.
std::pair<bool, arena_chunk_t*> UpdatePagesAndCounts()
MOZ_REQUIRES(mArena.mLock);
// FinishPurgingInChunk() is used whenever we decide to stop purging in a // chunk, This could be because there are no more dirty pages, or the chunk // is dying, or we hit the arena-level threshold. void FinishPurgingInChunk(bool aAddToMAdvised) MOZ_REQUIRES(mArena.mLock);
// Check mNumDirty against EffectiveMaxDirty and return the appropriate // action to be taken by MayDoOrQueuePurge (outside mLock's scope). // // None: Nothing to do. // PurgeNow: Immediate synchronous purge. // Queue: Add a new purge request. // // Note that in the case of deferred purge this function takes into account // mIsDeferredPurgeNeeded to avoid useless operations on the purge list // that would require gArenas.mPurgeListLock. inline purge_action_t ShouldStartPurge() MOZ_REQUIRES(mLock);
// Take action according to ShouldStartPurge. inlinevoid MayDoOrQueuePurge(purge_action_t aAction) MOZ_EXCLUDES(mLock);
// Check the EffectiveHalfMaxDirty threshold to decide if we continue purge. // This threshold is lower than ShouldStartPurge to have some hysteresis. bool ShouldContinuePurge(bool aForce = false) MOZ_REQUIRES(mLock) { return (mNumDirty > ((aForce) ? 0 : mMaxDirty >> 1));
}
// Bookkeeping for all the arenas used by the allocator. // Arenas are separated in two categories: // - "private" arenas, used through the moz_arena_* API // - all the other arenas: the default arena, and thread-local arenas, // used by the standard API. class ArenaCollection { public: bool Init() MOZ_REQUIRES(gInitLock) MOZ_EXCLUDES(mLock) {
MOZ_PUSH_IGNORE_THREAD_SAFETY
mArenas.Init();
mPrivateArenas.Init();
mMainThreadArenas.Init();
MOZ_POP_THREAD_SAFETY
arena_params_t params; // The main arena allows more dirty pages than the default for other arenas.
params.mMaxDirty = opt_dirty_max;
mDefaultArena =
mLock.Init() ? CreateArena(/* aIsPrivate = */ false, ¶ms) : nullptr;
mPurgeListLock.Init();
mIsDeferredPurgeEnabled = false; returnbool(mDefaultArena);
}
// The requested arena must exist. inline arena_t* GetById(arena_id_t aArenaId, bool aIsPrivate)
MOZ_EXCLUDES(mLock);
void DisposeArena(arena_t* aArena) MOZ_EXCLUDES(mLock) { // This will not call MayPurge but only unlink the element in case.
RemoveObsoletePurgeFromList(aArena);
{
MutexAutoLock lock(mLock);
Tree& tree =
aArena->IsMainThreadOnly() ? mMainThreadArenas : mPrivateArenas;
MOZ_RELEASE_ASSERT(tree.Search(aArena), "Arena not in tree");
tree.Remove(aArena);
mNumOperationsDisposedArenas += aArena->Operations();
// Guards the collection of arenas. Must not be acquired while holding // a single arena's lock or mPurgeListLock.
Mutex mLock MOZ_UNANNOTATED;
// Guards only the list of outstanding purge requests. Can be acquired // while holding gArenas.mLock, but must not be acquired or held while // holding or acquiring a single arena's lock.
Mutex mPurgeListLock;
// We're running on the main thread which is set by a call to SetMainThread(). bool IsOnMainThread() const { return mMainThreadId.isSome() &&
ThreadIdEqual(mMainThreadId.value(), GetThreadId());
}
// We're running on the main thread or SetMainThread() has never been called. bool IsOnMainThreadWeak() const { return mMainThreadId.isNothing() || IsOnMainThread();
}
// After a fork set the new thread ID in the child. // This is done as the first thing after a fork, before mLock even re-inits. void ResetMainThread() MOZ_EXCLUDES(mLock) { // The post fork handler in the child can run from a MacOS worker thread, // so we can't set our main thread to it here. Instead we have to clear it.
mMainThreadId = Nothing();
}
// This requires the lock to get a consistent count across all the active // + disposed arenas.
uint64_t OperationsDisposedArenas() MOZ_REQUIRES(mLock) { return mNumOperationsDisposedArenas;
}
// Enable or disable the lazy purge. // // Returns the former state of enablement. // This is a global setting for all arenas. Changing it may cause an // immediate purge for all arenas. bool SetDeferredPurge(bool aEnable) {
MOZ_ASSERT(IsOnMainThreadWeak());
// Set aside a new purge request for aArena. void AddToOutstandingPurges(arena_t* aArena) MOZ_EXCLUDES(mPurgeListLock);
// Remove an unhandled purge request for aArena. void RemoveObsoletePurgeFromList(arena_t* aArena)
MOZ_EXCLUDES(mPurgeListLock);
// Execute all outstanding purge requests, if any. void MayPurgeAll(bool aForce);
// Execute at most one request and return, if there are more to process. // // aPeekOnly - If true, check only if there is work to do without doing it. // // Note that this executes at most one call to arena_t::Purge for at most // one arena, which will purge at most one chunk from that arena. This is the // smallest possible fraction we can purge currently. bool MayPurgeStep(bool aPeekOnly);
// Accessing mArenas and mPrivateArenas can only be done while holding mLock.
Tree mArenas MOZ_GUARDED_BY(mLock);
Tree mPrivateArenas MOZ_GUARDED_BY(mLock);
// Some mMainThreadArenas accesses to mMainThreadArenas can (and should) elude // the lock, see GetById().
Tree mMainThreadArenas MOZ_GUARDED_BY(mLock);
Atomic<int32_t, MemoryOrdering::Relaxed> mDefaultMaxDirtyPageModifier; // This is never changed except for forking, and it does not need mLock.
Maybe<ThreadId> mMainThreadId;
// The number of operations that happened in arenas that have since been // destroyed.
uint64_t mNumOperationsDisposedArenas = 0;
// Linked list of outstanding purges.
DoublyLinkedList<arena_t> mOutstandingPurges MOZ_GUARDED_BY(mPurgeListLock); // Flag if we should defer purge to later. Only ever set when holding the // collection lock.
Atomic<bool, Relaxed> mIsDeferredPurgeEnabled;
};
// Protects chunk-related data structures. static Mutex chunks_mtx;
// Trees of chunks that were previously allocated (trees differ only in node // ordering). These are used when allocating chunks, in an attempt to re-use // address space. Depending on function, different tree orderings are needed, // which is why there are two trees with the same contents. static RedBlackTree<extent_node_t, ExtentTreeSzTrait> gChunksBySize
MOZ_GUARDED_BY(chunks_mtx); static RedBlackTree<extent_node_t, ExtentTreeTrait> gChunksByAddress
MOZ_GUARDED_BY(chunks_mtx);
// Protects huge allocation-related data structures. static Mutex huge_mtx;
// Tree of chunks that are stand-alone huge allocations. static RedBlackTree<extent_node_t, ExtentTreeTrait> huge
MOZ_GUARDED_BY(huge_mtx);
// ************************** // base (internal allocation).
static Mutex base_mtx;
// Current pages that are being used for internal memory allocations. These // pages are carved up in cacheline-size quanta, so that there is no chance of // false cache line sharing. staticvoid* base_pages MOZ_GUARDED_BY(base_mtx); staticvoid* base_next_addr MOZ_GUARDED_BY(base_mtx); staticvoid* base_next_decommitted MOZ_GUARDED_BY(base_mtx); // Address immediately past base_pages. staticvoid* base_past_addr MOZ_GUARDED_BY(base_mtx); static size_t base_mapped MOZ_GUARDED_BY(base_mtx); static size_t base_committed MOZ_GUARDED_BY(base_mtx);
// ****** // Arenas.
// The arena associated with the current thread (per // jemalloc_thread_local_arena) On OSX, __thread/thread_local circles back // calling malloc to allocate storage on first access on each thread, which // leads to an infinite loop, but pthread-based TLS somehow doesn't have this // problem. #if !defined(XP_DARWIN) static MOZ_THREAD_LOCAL(arena_t*) thread_arena; #else static detail::ThreadLocal<arena_t*, detail::ThreadLocalKeyStorage>
thread_arena; #endif
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
