diff options
Diffstat (limited to 'js/src/ds/LifoAlloc.h')
| -rw-r--r-- | js/src/ds/LifoAlloc.h | 1196 |
1 files changed, 1196 insertions, 0 deletions
diff --git a/js/src/ds/LifoAlloc.h b/js/src/ds/LifoAlloc.h new file mode 100644 index 0000000000..872a10c86f --- /dev/null +++ b/js/src/ds/LifoAlloc.h @@ -0,0 +1,1196 @@ +/* -*- 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/. */ + +#ifndef ds_LifoAlloc_h +#define ds_LifoAlloc_h + +#include "mozilla/Attributes.h" +#include "mozilla/MathAlgorithms.h" +#include "mozilla/MemoryChecking.h" +#include "mozilla/MemoryReporting.h" +#include "mozilla/PodOperations.h" +#include "mozilla/TemplateLib.h" + +#include <algorithm> +#include <new> +#include <stddef.h> // size_t +#include <type_traits> +#include <utility> + +// [SMDOC] LifoAlloc bump allocator +// +// This file defines an allocator named LifoAlloc which is a Bump allocator, +// which has the property of making fast allocation but is not able to reclaim +// individual allocations. +// +// * Allocation principle +// +// In practice a LifoAlloc is implemented using a list of BumpChunks, which are +// contiguous memory areas which are chained in a single linked list. +// +// When an allocation is performed, we check if there is space in the last +// chunk. If there is we bump the pointer of the last chunk and return the +// previous value of the pointer. Otherwise we allocate a new chunk which is +// large enough and perform the allocation the same way. +// +// Each allocation is made with 2 main functions, called +// BumpChunk::nextAllocBase and BumpChunk::nextAllocEnd. These functions are +// made to avoid duplicating logic, such as allocating, checking if we can +// allocate or reserving a given buffer space. They are made to align the +// pointer for the next allocation (8-byte aligned), and also to reserve some +// red-zones to improve reports of our security instrumentation. (see Security +// features below) +// +// The Chunks sizes are following the heuristics implemented in NextSize +// (LifoAlloc.cpp), which doubles the size until we reach 1 MB and then +// continues with a smaller geometric series. This heuristic is meant to reduce +// the number of allocations, such that we spend less time allocating/freeing +// chunks of a few KB at a time. +// +// ** Oversize allocations +// +// When allocating with a LifoAlloc, we distinguish 2 different kinds of +// allocations, the small allocations and the large allocations. The reason for +// splitting in 2 sets is to avoid wasting memory. +// +// If you had a single linked list of chunks, then making oversized allocations +// can cause chunks to contain a lot of wasted space as new chunks would have to +// be allocated to fit these allocations, and the space of the previous chunk +// would remain unused. +// +// Oversize allocation size can be disabled or customized with disableOversize +// and setOversizeThreshold, which must be smaller than the default chunk size +// with which the LifoAlloc was initialized. +// +// ** LifoAllocScope (mark & release) +// +// As the memory cannot be reclaimed except when the LifoAlloc structure is +// deleted, the LifoAllocScope structure is used to create scopes, related to a +// stacked task. When going out of a LifoAllocScope the memory associated to the +// scope is marked as unused but not reclaimed. This implies that the memory +// allocated for one task can be reused for a similar task later on. (see +// Safety) +// +// LifoAllocScope is based on mark and release functions. The mark function is +// used to recall the offsets at which a LifoAllocScope got created. The release +// function takes the Mark as input and will flag all memory allocated after the +// mark creation as unused. +// +// When releasing all the memory of BumpChunks, these are moved to a list of +// unused chunks which will later be reused by new allocations. +// +// A bump chunk allocator normally has a single bump pointers, whereas we have +// 2. (see Oversize allocations) By doing so, we lose the ordering of allocation +// coming from a single linked list of allocation. +// +// However, we rely on the ordering of allocation with LifoAllocScope, i-e when +// mark and release functions are used. Thus the LifoAlloc::Mark is composed of +// 2 marks, One for each singled linked list of allocations, to keep both lists +// of allocations ordered. +// +// ** Infallible Allocator +// +// LifoAlloc can also be used as an infallible allocator. This requires the user +// to periodically ensure that enough space has been reserved to satisfy the +// upcoming set of allocations by calling LifoAlloc::ensureUnusedApproximate or +// LifoAlloc::allocEnsureUnused functions. Between 2 calls of these functions, +// functions such as allocInfallible can be used without checking against +// nullptr, as long as there is a bounded number of such calls and that all +// allocations including their red-zone fit in the reserved space. +// +// The infallible allocator mode can be toggle as being the default by calling +// setAsInfallibleByDefault, in which case an AutoFallibleScope should be used +// to make any large allocations. Failing to do so will raise an issue when +// running the LifoAlloc with the OOM Simulator. (see Security features) +// +// * LifoAlloc::Enum Iterator +// +// A LifoAlloc is used for backing the store-buffer of the Garbage Collector +// (GC). The store-buffer is appending data as it is being reported during +// incremental GC. The LifoAlloc::Enum class is used for iterating over the set +// of allocations made within the LifoAlloc. +// +// However, one must take extra care into having the proper associated types for +// the data which are being written and read out of the LifoAlloc. The iterator +// is reusing the same logic as the allocator in order to skip red-zones. +// +// At the moment, the iterator will cause a hard failure if any oversize +// allocation are made. +// +// * Safety +// +// A LifoAlloc is neither thread-safe nor interrupt-safe. It should only be +// manipulated in one thread of execution at a time. It can be transferred from +// one thread to another but should not be used concurrently. +// +// When using LifoAllocScope, no pointer to the data allocated within a +// LifoAllocScope should be stored in data allocated before the latest +// LifoAllocScope. This kind of issue can hide in different forms, such as +// appending to a Vector backed by a LifoAlloc, which can resize and move the +// data below the LifoAllocScope. Thus causing a use-after-free once leaving a +// LifoAllocScope. +// +// * Security features +// +// ** Single Linked List +// +// For sanity reasons this LifoAlloc implementation makes use of its own single +// linked list implementation based on unique pointers (UniquePtr). The reason +// for this is to ensure that a BumpChunk is owned only once, thus preventing +// use-after-free issues. +// +// ** OOM Simulator +// +// The OOM simulator is controlled by the JS_OOM_BREAKPOINT macro, and used to +// check any fallible allocation for potential OOM. Fallible functions are +// instrumented with JS_OOM_POSSIBLY_FAIL(); function calls, and are expected to +// return null on failures. +// +// Except for simulating OOMs, LifoAlloc is instrumented in DEBUG and OOM +// Simulator builds to checks for the correctness of the Infallible Allocator +// state. When using a LifoAlloc as an infallible allocator, enough space should +// always be reserved for the next allocations. Therefore, to check this +// invariant LifoAlloc::newChunkWithCapacity checks that any new chunks are +// allocated within a fallible scope, under AutoFallibleScope. +// +// ** Address Sanitizers & Valgrind +// +// When manipulating memory in a LifoAlloc, the memory remains contiguous and +// therefore subject to potential buffer overflow/underflow. To check for these +// memory corruptions, the macro LIFO_HAVE_MEM_CHECK is used to add red-zones +// with LIFO_MAKE_MEM_NOACCESS and LIFO_MAKE_MEM_UNDEFINED. +// +// The red-zone is a minimum space left in between 2 allocations. Any access to +// these red-zones should warn in both valgrind / ASan builds. +// +// The red-zone size is defined in BumpChunk::RedZoneSize and default to 0 if +// not instrumentation is expected, and 16 otherwise. +// +// ** Magic Number +// +// A simple sanity check is present in all BumpChunk under the form of a +// constant field which is never mutated. the BumpChunk::magic_ is initalized to +// the "Lif" string. Any mutation of this value indicate a memory corruption. +// +// This magic number is enabled in all MOZ_DIAGNOSTIC_ASSERT_ENABLED builds, +// which implies that all Nightly and dev-edition versions of +// Firefox/SpiderMonkey contain this instrumentation. +// +// ** Memory protection +// +// LifoAlloc chunks are holding a lot of memory. When the memory is known to be +// unused, unchanged for some period of time, such as moving from one thread to +// another. Then the memory can be set as read-only with LifoAlloc::setReadOnly +// and reset as read-write with LifoAlloc::setReadWrite. +// +// This code is guarded by LIFO_CHUNK_PROTECT and at the moment only enabled in +// DEBUG builds in order to avoid the fragmentation of the TLB which might run +// out-of-memory when calling mprotect. +// + +#include "js/UniquePtr.h" +#include "util/Memory.h" +#include "util/Poison.h" + +namespace js { + +namespace detail { + +template <typename T, typename D> +class SingleLinkedList; + +template <typename T, typename D = JS::DeletePolicy<T>> +class SingleLinkedListElement { + friend class SingleLinkedList<T, D>; + js::UniquePtr<T, D> next_; + + public: + SingleLinkedListElement() : next_(nullptr) {} + ~SingleLinkedListElement() { MOZ_ASSERT(!next_); } + + T* next() const { return next_.get(); } +}; + +// Single linked list which is using UniquePtr to hold the next pointers. +// UniquePtr are used to ensure that none of the elements are used +// silmutaneously in 2 different list. +template <typename T, typename D = JS::DeletePolicy<T>> +class SingleLinkedList { + private: + // First element of the list which owns the next element, and ensure that + // that this list is the only owner of the element. + UniquePtr<T, D> head_; + + // Weak pointer to the last element of the list. + T* last_; + + void assertInvariants() { + MOZ_ASSERT(bool(head_) == bool(last_)); + MOZ_ASSERT_IF(last_, !last_->next_); + } + + public: + SingleLinkedList() : head_(nullptr), last_(nullptr) { assertInvariants(); } + + SingleLinkedList(SingleLinkedList&& other) + : head_(std::move(other.head_)), last_(other.last_) { + other.last_ = nullptr; + assertInvariants(); + other.assertInvariants(); + } + + ~SingleLinkedList() { + MOZ_ASSERT(!head_); + MOZ_ASSERT(!last_); + } + + // Move the elements of the |other| list in the current one, and implicitly + // remove all the elements of the current list. + SingleLinkedList& operator=(SingleLinkedList&& other) { + head_ = std::move(other.head_); + last_ = other.last_; + other.last_ = nullptr; + assertInvariants(); + other.assertInvariants(); + return *this; + } + + bool empty() const { return !last_; } + + // Iterates over the elements of the list, this is used to avoid raw + // manipulation of pointers as much as possible. + class Iterator { + T* current_; + + public: + explicit Iterator(T* current) : current_(current) {} + + T& operator*() const { return *current_; } + T* operator->() const { return current_; } + T* get() const { return current_; } + + const Iterator& operator++() { + current_ = current_->next(); + return *this; + } + + bool operator!=(const Iterator& other) const { + return current_ != other.current_; + } + bool operator==(const Iterator& other) const { + return current_ == other.current_; + } + }; + + Iterator begin() const { return Iterator(head_.get()); } + Iterator end() const { return Iterator(nullptr); } + Iterator last() const { return Iterator(last_); } + + // Split the list in 2 single linked lists after the element given as + // argument. The front of the list remains in the current list, while the + // back goes in the newly create linked list. + // + // This is used for example to extract one element from a list. (see + // LifoAlloc::getOrCreateChunk) + SingleLinkedList splitAfter(T* newLast) { + MOZ_ASSERT(newLast); + SingleLinkedList result; + if (newLast->next_) { + result.head_ = std::move(newLast->next_); + result.last_ = last_; + last_ = newLast; + } + assertInvariants(); + result.assertInvariants(); + return result; + } + + void pushFront(UniquePtr<T, D>&& elem) { + if (!last_) { + last_ = elem.get(); + } + elem->next_ = std::move(head_); + head_ = std::move(elem); + assertInvariants(); + } + + void append(UniquePtr<T, D>&& elem) { + if (last_) { + last_->next_ = std::move(elem); + last_ = last_->next_.get(); + } else { + head_ = std::move(elem); + last_ = head_.get(); + } + assertInvariants(); + } + void appendAll(SingleLinkedList&& list) { + if (list.empty()) { + return; + } + if (last_) { + last_->next_ = std::move(list.head_); + } else { + head_ = std::move(list.head_); + } + last_ = list.last_; + list.last_ = nullptr; + assertInvariants(); + list.assertInvariants(); + } + void steal(SingleLinkedList&& list) { + head_ = std::move(list.head_); + last_ = list.last_; + list.last_ = nullptr; + assertInvariants(); + list.assertInvariants(); + } + void prependAll(SingleLinkedList&& list) { + list.appendAll(std::move(*this)); + steal(std::move(list)); + } + UniquePtr<T, D> popFirst() { + MOZ_ASSERT(head_); + UniquePtr<T, D> result = std::move(head_); + head_ = std::move(result->next_); + if (!head_) { + last_ = nullptr; + } + assertInvariants(); + return result; + } +}; + +static const size_t LIFO_ALLOC_ALIGN = 8; + +MOZ_ALWAYS_INLINE +uint8_t* AlignPtr(uint8_t* orig) { + static_assert(mozilla::IsPowerOfTwo(LIFO_ALLOC_ALIGN), + "LIFO_ALLOC_ALIGN must be a power of two"); + + uint8_t* result = (uint8_t*)AlignBytes(uintptr_t(orig), LIFO_ALLOC_ALIGN); + MOZ_ASSERT(uintptr_t(result) % LIFO_ALLOC_ALIGN == 0); + return result; +} + +// A Chunk represent a single memory allocation made with the system +// allocator. As the owner of the memory, it is responsible for the allocation +// and the deallocation. +// +// This structure is only move-able, but not copyable. +class BumpChunk : public SingleLinkedListElement<BumpChunk> { + private: + // Pointer to the last byte allocated in this chunk. + uint8_t* bump_; + // Pointer to the first byte after this chunk. + uint8_t* const capacity_; + +#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED + // Magic number used to check against poisoned values. + const uintptr_t magic_ : 24; + static constexpr uintptr_t magicNumber = uintptr_t(0x4c6966); +#endif + +#if defined(DEBUG) +# define LIFO_CHUNK_PROTECT 1 +#endif + + // Poison the memory with memset, in order to catch errors due to + // use-after-free, with JS_LIFO_UNDEFINED_PATTERN pattern, or to catch + // use-before-init with JS_LIFO_UNINITIALIZED_PATTERN. +#if defined(DEBUG) +# define LIFO_HAVE_MEM_CHECKS 1 +# define LIFO_MAKE_MEM_NOACCESS(addr, size) \ + do { \ + uint8_t* base = (addr); \ + size_t sz = (size); \ + MOZ_MAKE_MEM_UNDEFINED(base, sz); \ + memset(base, JS_LIFO_UNDEFINED_PATTERN, sz); \ + MOZ_MAKE_MEM_NOACCESS(base, sz); \ + } while (0) + +# define LIFO_MAKE_MEM_UNDEFINED(addr, size) \ + do { \ + uint8_t* base = (addr); \ + size_t sz = (size); \ + MOZ_MAKE_MEM_UNDEFINED(base, sz); \ + memset(base, JS_LIFO_UNINITIALIZED_PATTERN, sz); \ + MOZ_MAKE_MEM_UNDEFINED(base, sz); \ + } while (0) + +#elif defined(MOZ_HAVE_MEM_CHECKS) +# define LIFO_HAVE_MEM_CHECKS 1 +# define LIFO_MAKE_MEM_NOACCESS(addr, size) \ + MOZ_MAKE_MEM_NOACCESS((addr), (size)) +# define LIFO_MAKE_MEM_UNDEFINED(addr, size) \ + MOZ_MAKE_MEM_UNDEFINED((addr), (size)) +#endif + +#ifdef LIFO_HAVE_MEM_CHECKS + // Red zone reserved after each allocation. + static constexpr size_t RedZoneSize = 16; +#else + static constexpr size_t RedZoneSize = 0; +#endif + + void assertInvariants() { + MOZ_DIAGNOSTIC_ASSERT(magic_ == magicNumber); + MOZ_ASSERT(begin() <= end()); + MOZ_ASSERT(end() <= capacity_); + } + + BumpChunk& operator=(const BumpChunk&) = delete; + BumpChunk(const BumpChunk&) = delete; + + explicit BumpChunk(uintptr_t capacity) + : bump_(begin()), + capacity_(base() + capacity) +#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED + , + magic_(magicNumber) +#endif + { + assertInvariants(); +#if defined(LIFO_HAVE_MEM_CHECKS) + // The memory is freshly allocated and marked as undefined by the + // allocator of the BumpChunk. Instead, we mark this memory as + // no-access, as it has not been allocated within the BumpChunk. + LIFO_MAKE_MEM_NOACCESS(bump_, capacity_ - bump_); +#endif + } + + // Cast |this| into a uint8_t* pointer. + // + // Warning: Are you sure you do not want to use begin() instead? + const uint8_t* base() const { return reinterpret_cast<const uint8_t*>(this); } + uint8_t* base() { return reinterpret_cast<uint8_t*>(this); } + + // Update the bump pointer to any value contained in this chunk, which is + // above the private fields of this chunk. + // + // The memory is poisoned and flagged as no-access when the bump pointer is + // moving backward, such as when memory is released, or when a Mark is used + // to unwind previous allocations. + // + // The memory is flagged as undefined when the bump pointer is moving + // forward. + void setBump(uint8_t* newBump) { + assertInvariants(); + MOZ_ASSERT(begin() <= newBump); + MOZ_ASSERT(newBump <= capacity_); +#if defined(LIFO_HAVE_MEM_CHECKS) + // Poison/Unpoison memory that we just free'd/allocated. + if (bump_ > newBump) { + LIFO_MAKE_MEM_NOACCESS(newBump, bump_ - newBump); + } else if (newBump > bump_) { + MOZ_ASSERT(newBump - RedZoneSize >= bump_); + LIFO_MAKE_MEM_UNDEFINED(bump_, newBump - RedZoneSize - bump_); + // The area [newBump - RedZoneSize .. newBump[ is already flagged as + // no-access either with the previous if-branch or with the + // BumpChunk constructor. No need to mark it twice. + } +#endif + bump_ = newBump; + } + + public: + ~BumpChunk() { release(); } + + // Returns true if this chunk contains no allocated content. + bool empty() const { return end() == begin(); } + + // Returns the size in bytes of the number of allocated space. This includes + // the size consumed by the alignment of the allocations. + size_t used() const { return end() - begin(); } + + // These are used for manipulating a chunk as if it was a vector of bytes, + // and used for iterating over the content of the buffer (see + // LifoAlloc::Enum) + inline const uint8_t* begin() const; + inline uint8_t* begin(); + uint8_t* end() const { return bump_; } + + // This function is the only way to allocate and construct a chunk. It + // returns a UniquePtr to the newly allocated chunk. The size given as + // argument includes the space needed for the header of the chunk. + static UniquePtr<BumpChunk> newWithCapacity(size_t size); + + // Report allocation. + size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + return mallocSizeOf(this); + } + + // Report allocation size. + size_t computedSizeOfIncludingThis() const { return capacity_ - base(); } + + // Opaque type used to carry a pointer to the current location of the bump_ + // pointer, within a BumpChunk. + class Mark { + // Chunk which owns the pointer. + BumpChunk* chunk_; + // Recorded of the bump_ pointer of the BumpChunk. + uint8_t* bump_; + + friend class BumpChunk; + Mark(BumpChunk* chunk, uint8_t* bump) : chunk_(chunk), bump_(bump) {} + + public: + Mark() : chunk_(nullptr), bump_(nullptr) {} + + BumpChunk* markedChunk() const { return chunk_; } + }; + + // Return a mark to be able to unwind future allocations with the release + // function. (see LifoAllocScope) + Mark mark() { return Mark(this, end()); } + + // Check if a pointer is part of the allocated data of this chunk. + bool contains(const void* ptr) const { + // Note: We cannot check "ptr < end()" because the mark have a 0-size + // length. + return begin() <= ptr && ptr <= end(); + } + + // Check if a mark is part of the allocated data of this chunk. + bool contains(Mark m) const { + MOZ_ASSERT(m.chunk_ == this); + return contains(m.bump_); + } + + // Release the memory allocated in this chunk. This function does not call + // any of the destructors. + void release() { setBump(begin()); } + + // Release the memory allocated in this chunk since the corresponding mark + // got created. This function does not call any of the destructors. + void release(Mark m) { + MOZ_RELEASE_ASSERT(contains(m)); + setBump(m.bump_); + } + + // Given an amount, compute the total size of a chunk for it: reserved + // space before |begin()|, space for |amount| bytes, and red-zone space + // after those bytes that will ultimately end at |capacity_|. + [[nodiscard]] static inline bool allocSizeWithRedZone(size_t amount, + size_t* size); + + // Given a bump chunk pointer, find the next base/end pointers. This is + // useful for having consistent allocations, and iterating over known size + // allocations. + static uint8_t* nextAllocBase(uint8_t* e) { return detail::AlignPtr(e); } + static uint8_t* nextAllocEnd(uint8_t* b, size_t n) { + return b + n + RedZoneSize; + } + + // Returns true, if the unused space is large enough for an allocation of + // |n| bytes. + bool canAlloc(size_t n) const { + uint8_t* newBump = nextAllocEnd(nextAllocBase(end()), n); + // bump_ <= newBump, is necessary to catch overflow. + return bump_ <= newBump && newBump <= capacity_; + } + + // Space remaining in the current chunk. + size_t unused() const { + uint8_t* aligned = nextAllocBase(end()); + if (aligned < capacity_) { + return capacity_ - aligned; + } + return 0; + } + + // Try to perform an allocation of size |n|, returns nullptr if not possible. + MOZ_ALWAYS_INLINE + void* tryAlloc(size_t n) { + uint8_t* aligned = nextAllocBase(end()); + uint8_t* newBump = nextAllocEnd(aligned, n); + + if (newBump > capacity_) { + return nullptr; + } + + // Check for overflow. + if (MOZ_UNLIKELY(newBump < bump_)) { + return nullptr; + } + + MOZ_ASSERT(canAlloc(n)); // Ensure consistency between "can" and "try". + setBump(newBump); + return aligned; + } + +#ifdef LIFO_CHUNK_PROTECT + void setReadOnly(); + void setReadWrite(); +#else + void setReadOnly() const {} + void setReadWrite() const {} +#endif +}; + +// Space reserved for the BumpChunk internal data, and the alignment of the +// first allocation content. This can be used to ensure there is enough space +// for the next allocation (see LifoAlloc::newChunkWithCapacity). +static constexpr size_t BumpChunkReservedSpace = + AlignBytes(sizeof(BumpChunk), LIFO_ALLOC_ALIGN); + +[[nodiscard]] /* static */ inline bool BumpChunk::allocSizeWithRedZone( + size_t amount, size_t* size) { + constexpr size_t SpaceBefore = BumpChunkReservedSpace; + static_assert((SpaceBefore % LIFO_ALLOC_ALIGN) == 0, + "reserved space presumed already aligned"); + + constexpr size_t SpaceAfter = RedZoneSize; // may be zero + + constexpr size_t SpaceBeforeAndAfter = SpaceBefore + SpaceAfter; + static_assert(SpaceBeforeAndAfter >= SpaceBefore, + "intermediate addition must not overflow"); + + *size = SpaceBeforeAndAfter + amount; + return MOZ_LIKELY(*size >= SpaceBeforeAndAfter); +} + +inline const uint8_t* BumpChunk::begin() const { + return base() + BumpChunkReservedSpace; +} + +inline uint8_t* BumpChunk::begin() { return base() + BumpChunkReservedSpace; } + +} // namespace detail + +// LIFO bump allocator: used for phase-oriented and fast LIFO allocations. +// +// Note: We leave BumpChunks latent in the set of unused chunks after they've +// been released to avoid thrashing before a GC. +class LifoAlloc { + using UniqueBumpChunk = js::UniquePtr<detail::BumpChunk>; + using BumpChunkList = detail::SingleLinkedList<detail::BumpChunk>; + + // List of chunks containing allocated data of size smaller than the default + // chunk size. In the common case, the last chunk of this list is always + // used to perform the allocations. When the allocation cannot be performed, + // we move a Chunk from the unused set to the list of used chunks. + BumpChunkList chunks_; + + // List of chunks containing allocated data where each allocation is larger + // than the oversize threshold. Each chunk contains exactly one allocation. + // This reduces wasted space in the chunk list. + // + // Oversize chunks are allocated on demand and freed as soon as they are + // released, instead of being pushed to the unused list. + BumpChunkList oversize_; + + // Set of unused chunks, which can be reused for future allocations. + BumpChunkList unused_; + + size_t markCount; + size_t defaultChunkSize_; + size_t oversizeThreshold_; + + // Size of all chunks in chunks_, oversize_, unused_ lists. + size_t curSize_; + size_t peakSize_; + + // Size of all chunks containing small bump allocations. This heuristic is + // used to compute growth rate while ignoring chunks such as oversized, + // now-unused, or transferred (which followed their own growth patterns). + size_t smallAllocsSize_; + +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + bool fallibleScope_; +#endif + + void operator=(const LifoAlloc&) = delete; + LifoAlloc(const LifoAlloc&) = delete; + + // Return a BumpChunk that can perform an allocation of at least size |n|. + UniqueBumpChunk newChunkWithCapacity(size_t n, bool oversize); + + // Reuse or allocate a BumpChunk that can perform an allocation of at least + // size |n|, if successful it is placed at the end the list of |chunks_|. + UniqueBumpChunk getOrCreateChunk(size_t n); + + void reset(size_t defaultChunkSize); + + // Append unused chunks to the end of this LifoAlloc. + void appendUnused(BumpChunkList&& otherUnused) { +#ifdef DEBUG + for (detail::BumpChunk& bc : otherUnused) { + MOZ_ASSERT(bc.empty()); + } +#endif + unused_.appendAll(std::move(otherUnused)); + } + + // Append used chunks to the end of this LifoAlloc. We act as if all the + // chunks in |this| are used, even if they're not, so memory may be wasted. + void appendUsed(BumpChunkList&& otherChunks) { + chunks_.appendAll(std::move(otherChunks)); + } + + // Track the amount of space allocated in used and unused chunks. + void incrementCurSize(size_t size) { + curSize_ += size; + if (curSize_ > peakSize_) { + peakSize_ = curSize_; + } + } + void decrementCurSize(size_t size) { + MOZ_ASSERT(curSize_ >= size); + curSize_ -= size; + MOZ_ASSERT(curSize_ >= smallAllocsSize_); + } + + void* allocImplColdPath(size_t n); + void* allocImplOversize(size_t n); + + MOZ_ALWAYS_INLINE + void* allocImpl(size_t n) { + void* result; + // Give oversized allocations their own chunk instead of wasting space + // due to fragmentation at the end of normal chunk. + if (MOZ_UNLIKELY(n > oversizeThreshold_)) { + return allocImplOversize(n); + } + if (MOZ_LIKELY(!chunks_.empty() && + (result = chunks_.last()->tryAlloc(n)))) { + return result; + } + return allocImplColdPath(n); + } + + // Check for space in unused chunks or allocate a new unused chunk. + [[nodiscard]] bool ensureUnusedApproximateColdPath(size_t n, size_t total); + + public: + explicit LifoAlloc(size_t defaultChunkSize) + : peakSize_(0) +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + , + fallibleScope_(true) +#endif + { + reset(defaultChunkSize); + } + + // Set the threshold to allocate data in its own chunk outside the space for + // small allocations. + void disableOversize() { oversizeThreshold_ = SIZE_MAX; } + void setOversizeThreshold(size_t oversizeThreshold) { + MOZ_ASSERT(oversizeThreshold <= defaultChunkSize_); + oversizeThreshold_ = oversizeThreshold; + } + + // Steal allocated chunks from |other|. + void steal(LifoAlloc* other); + + // Append all chunks from |other|. They are removed from |other|. + void transferFrom(LifoAlloc* other); + + // Append unused chunks from |other|. They are removed from |other|. + void transferUnusedFrom(LifoAlloc* other); + + ~LifoAlloc() { freeAll(); } + + size_t defaultChunkSize() const { return defaultChunkSize_; } + + // Frees all held memory. + void freeAll(); + + static const unsigned HUGE_ALLOCATION = 50 * 1024 * 1024; + void freeAllIfHugeAndUnused() { + if (markCount == 0 && curSize_ > HUGE_ALLOCATION) { + freeAll(); + } + } + + MOZ_ALWAYS_INLINE + void* alloc(size_t n) { +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + // Only simulate OOMs when we are not using the LifoAlloc as an + // infallible allocator. + if (fallibleScope_) { + JS_OOM_POSSIBLY_FAIL(); + } +#endif + return allocImpl(n); + } + + // Allocates |n| bytes if we can guarantee that we will have + // |needed| unused bytes remaining. Returns nullptr if we can't. + // This is useful for maintaining our ballast invariants while + // attempting fallible allocations. + MOZ_ALWAYS_INLINE + void* allocEnsureUnused(size_t n, size_t needed) { + JS_OOM_POSSIBLY_FAIL(); + MOZ_ASSERT(fallibleScope_); + + Mark m = mark(); + void* result = allocImpl(n); + if (!ensureUnusedApproximate(needed)) { + release(m); + return nullptr; + } + cancelMark(m); + return result; + } + + template <typename T, typename... Args> + MOZ_ALWAYS_INLINE T* newWithSize(size_t n, Args&&... args) { + MOZ_ASSERT(n >= sizeof(T), "must request enough space to store a T"); + static_assert(alignof(T) <= detail::LIFO_ALLOC_ALIGN, + "LifoAlloc must provide enough alignment to store T"); + void* ptr = alloc(n); + if (!ptr) { + return nullptr; + } + + return new (ptr) T(std::forward<Args>(args)...); + } + + MOZ_ALWAYS_INLINE + void* allocInfallible(size_t n) { + AutoEnterOOMUnsafeRegion oomUnsafe; + if (void* result = allocImpl(n)) { + return result; + } + oomUnsafe.crash("LifoAlloc::allocInfallible"); + return nullptr; + } + + // Ensures that enough space exists to satisfy N bytes worth of + // allocation requests, not necessarily contiguous. Note that this does + // not guarantee a successful single allocation of N bytes. + [[nodiscard]] MOZ_ALWAYS_INLINE bool ensureUnusedApproximate(size_t n) { + AutoFallibleScope fallibleAllocator(this); + size_t total = 0; + if (!chunks_.empty()) { + total += chunks_.last()->unused(); + if (total >= n) { + return true; + } + } + + return ensureUnusedApproximateColdPath(n, total); + } + + MOZ_ALWAYS_INLINE + void setAsInfallibleByDefault() { +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + fallibleScope_ = false; +#endif + } + + class MOZ_NON_TEMPORARY_CLASS AutoFallibleScope { +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + LifoAlloc* lifoAlloc_; + bool prevFallibleScope_; + + public: + explicit AutoFallibleScope(LifoAlloc* lifoAlloc) { + lifoAlloc_ = lifoAlloc; + prevFallibleScope_ = lifoAlloc->fallibleScope_; + lifoAlloc->fallibleScope_ = true; + } + + ~AutoFallibleScope() { lifoAlloc_->fallibleScope_ = prevFallibleScope_; } +#else + public: + explicit AutoFallibleScope(LifoAlloc*) {} +#endif + }; + + template <typename T> + T* newArray(size_t count) { + static_assert(std::is_trivial_v<T>, + "T must be trivially constructible so that constructors need " + "not be called"); + static_assert(std::is_trivially_destructible_v<T>, + "T must be trivially destructible so destructors don't need " + "to be called when the LifoAlloc is freed"); + return newArrayUninitialized<T>(count); + } + + // Create an array with uninitialized elements of type |T|. + // The caller is responsible for initialization. + template <typename T> + T* newArrayUninitialized(size_t count) { + size_t bytes; + if (MOZ_UNLIKELY(!CalculateAllocSize<T>(count, &bytes))) { + return nullptr; + } + return static_cast<T*>(alloc(bytes)); + } + + class Mark { + friend class LifoAlloc; + detail::BumpChunk::Mark chunk; + detail::BumpChunk::Mark oversize; + }; + + // Note: MOZ_NEVER_INLINE is a work around for a Clang 9 (PGO) miscompilation. + // See bug 1583907. + MOZ_NEVER_INLINE Mark mark(); + + void release(Mark mark); + + private: + void cancelMark(Mark mark) { markCount--; } + + public: + void releaseAll() { + MOZ_ASSERT(!markCount); + + // When releasing all chunks, we can no longer determine which chunks were + // transferred and which were not, so simply clear the heuristic to zero + // right away. + smallAllocsSize_ = 0; + + for (detail::BumpChunk& bc : chunks_) { + bc.release(); + } + unused_.appendAll(std::move(chunks_)); + + // On release, we free any oversize allocations instead of keeping them + // in unused chunks. + while (!oversize_.empty()) { + UniqueBumpChunk bc = oversize_.popFirst(); + decrementCurSize(bc->computedSizeOfIncludingThis()); + } + } + + // Protect the content of the LifoAlloc chunks. +#ifdef LIFO_CHUNK_PROTECT + void setReadOnly(); + void setReadWrite(); +#else + void setReadOnly() const {} + void setReadWrite() const {} +#endif + + // Get the total "used" (occupied bytes) count for the arena chunks. + size_t used() const { + size_t accum = 0; + for (const detail::BumpChunk& chunk : chunks_) { + accum += chunk.used(); + } + return accum; + } + + // Return true if the LifoAlloc does not currently contain any allocations. + bool isEmpty() const { + bool empty = chunks_.empty() || + (chunks_.begin() == chunks_.last() && chunks_.last()->empty()); + MOZ_ASSERT_IF(!oversize_.empty(), !oversize_.last()->empty()); + return empty && oversize_.empty(); + } + + // Return the number of bytes remaining to allocate in the current chunk. + // e.g. How many bytes we can allocate before needing a new block. + size_t availableInCurrentChunk() const { + if (chunks_.empty()) { + return 0; + } + return chunks_.last()->unused(); + } + + // Get the total size of the arena chunks (including unused space). + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + size_t n = 0; + for (const detail::BumpChunk& chunk : chunks_) { + n += chunk.sizeOfIncludingThis(mallocSizeOf); + } + for (const detail::BumpChunk& chunk : oversize_) { + n += chunk.sizeOfIncludingThis(mallocSizeOf); + } + for (const detail::BumpChunk& chunk : unused_) { + n += chunk.sizeOfIncludingThis(mallocSizeOf); + } + return n; + } + + // Like sizeOfExcludingThis(), but includes the size of the LifoAlloc itself. + size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf); + } + + // Get the current size of the arena chunks (including unused space and + // bookkeeping space). + size_t computedSizeOfExcludingThis() const { return curSize_; } + + // Get the peak size of the arena chunks (including unused space and + // bookkeeping space). + size_t peakSizeOfExcludingThis() const { return peakSize_; } + + // Doesn't perform construction; useful for lazily-initialized POD types. + template <typename T> + MOZ_ALWAYS_INLINE T* pod_malloc() { + return static_cast<T*>(alloc(sizeof(T))); + } + + JS_DECLARE_NEW_METHODS(new_, alloc, MOZ_ALWAYS_INLINE) + JS_DECLARE_NEW_METHODS(newInfallible, allocInfallible, MOZ_ALWAYS_INLINE) + +#ifdef DEBUG + bool contains(const void* ptr) const { + for (const detail::BumpChunk& chunk : chunks_) { + if (chunk.contains(ptr)) { + return true; + } + } + for (const detail::BumpChunk& chunk : oversize_) { + if (chunk.contains(ptr)) { + return true; + } + } + return false; + } +#endif + + // Iterate over the data allocated in a LifoAlloc, and interpret it. + class Enum { + friend class LifoAlloc; + friend class detail::BumpChunk; + + // Iterator over the list of bump chunks. + BumpChunkList::Iterator chunkIt_; + BumpChunkList::Iterator chunkEnd_; + // Read head (must be within chunk_). + uint8_t* head_; + + // If there is not enough room in the remaining block for |size|, + // advance to the next block and update the position. + uint8_t* seekBaseAndAdvanceBy(size_t size) { + MOZ_ASSERT(!empty()); + + uint8_t* aligned = detail::BumpChunk::nextAllocBase(head_); + if (detail::BumpChunk::nextAllocEnd(aligned, size) > chunkIt_->end()) { + ++chunkIt_; + aligned = chunkIt_->begin(); + // The current code assumes that if we have a chunk, then we + // have allocated something it in. + MOZ_ASSERT(!chunkIt_->empty()); + } + head_ = detail::BumpChunk::nextAllocEnd(aligned, size); + MOZ_ASSERT(head_ <= chunkIt_->end()); + return aligned; + } + + public: + explicit Enum(LifoAlloc& alloc) + : chunkIt_(alloc.chunks_.begin()), + chunkEnd_(alloc.chunks_.end()), + head_(nullptr) { + MOZ_RELEASE_ASSERT(alloc.oversize_.empty()); + if (chunkIt_ != chunkEnd_) { + head_ = chunkIt_->begin(); + } + } + + // Return true if there are no more bytes to enumerate. + bool empty() { + return chunkIt_ == chunkEnd_ || + (chunkIt_->next() == chunkEnd_.get() && head_ >= chunkIt_->end()); + } + + // Move the read position forward by the size of one T. + template <typename T> + T* read(size_t size = sizeof(T)) { + return reinterpret_cast<T*>(read(size)); + } + + // Return a pointer to the item at the current position. This returns a + // pointer to the inline storage, not a copy, and moves the read-head by + // the requested |size|. + void* read(size_t size) { return seekBaseAndAdvanceBy(size); } + }; +}; + +class MOZ_NON_TEMPORARY_CLASS LifoAllocScope { + LifoAlloc* lifoAlloc; + LifoAlloc::Mark mark; + LifoAlloc::AutoFallibleScope fallibleScope; + + public: + explicit LifoAllocScope(LifoAlloc* lifoAlloc) + : lifoAlloc(lifoAlloc), + mark(lifoAlloc->mark()), + fallibleScope(lifoAlloc) {} + + ~LifoAllocScope() { + lifoAlloc->release(mark); + + /* + * The parser can allocate enormous amounts of memory for large functions. + * Eagerly free the memory now (which otherwise won't be freed until the + * next GC) to avoid unnecessary OOMs. + */ + lifoAlloc->freeAllIfHugeAndUnused(); + } + + LifoAlloc& alloc() { return *lifoAlloc; } +}; + +enum Fallibility { Fallible, Infallible }; + +template <Fallibility fb> +class LifoAllocPolicy { + LifoAlloc& alloc_; + + public: + MOZ_IMPLICIT LifoAllocPolicy(LifoAlloc& alloc) : alloc_(alloc) {} + template <typename T> + T* maybe_pod_malloc(size_t numElems) { + size_t bytes; + if (MOZ_UNLIKELY(!CalculateAllocSize<T>(numElems, &bytes))) { + return nullptr; + } + void* p = + fb == Fallible ? alloc_.alloc(bytes) : alloc_.allocInfallible(bytes); + return static_cast<T*>(p); + } + template <typename T> + T* maybe_pod_calloc(size_t numElems) { + T* p = maybe_pod_malloc<T>(numElems); + if (MOZ_UNLIKELY(!p)) { + return nullptr; + } + memset(p, 0, numElems * sizeof(T)); + return p; + } + template <typename T> + T* maybe_pod_realloc(T* p, size_t oldSize, size_t newSize) { + T* n = maybe_pod_malloc<T>(newSize); + if (MOZ_UNLIKELY(!n)) { + return nullptr; + } + MOZ_ASSERT(!(oldSize & mozilla::tl::MulOverflowMask<sizeof(T)>::value)); + memcpy(n, p, std::min(oldSize * sizeof(T), newSize * sizeof(T))); + return n; + } + template <typename T> + T* pod_malloc(size_t numElems) { + return maybe_pod_malloc<T>(numElems); + } + template <typename T> + T* pod_calloc(size_t numElems) { + return maybe_pod_calloc<T>(numElems); + } + template <typename T> + T* pod_realloc(T* p, size_t oldSize, size_t newSize) { + return maybe_pod_realloc<T>(p, oldSize, newSize); + } + template <typename T> + void free_(T* p, size_t numElems) {} + void reportAllocOverflow() const {} + [[nodiscard]] bool checkSimulatedOOM() const { + return fb == Infallible || !js::oom::ShouldFailWithOOM(); + } +}; + +} // namespace js + +#endif /* ds_LifoAlloc_h */ |