summaryrefslogtreecommitdiffstats
path: root/js/src/ds/LifoAlloc.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/ds/LifoAlloc.h')
-rw-r--r--js/src/ds/LifoAlloc.h1031
1 files changed, 1031 insertions, 0 deletions
diff --git a/js/src/ds/LifoAlloc.h b/js/src/ds/LifoAlloc.h
new file mode 100644
index 0000000000..9fe77ac748
--- /dev/null
+++ b/js/src/ds/LifoAlloc.h
@@ -0,0 +1,1031 @@
+/* -*- 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>
+
+// This data structure supports stacky LIFO allocation (mark/release and
+// LifoAllocScope). It does not maintain one contiguous segment; instead, it
+// maintains a bunch of linked memory segments. In order to prevent malloc/free
+// thrashing, unused segments are deallocated when garbage collection occurs.
+
+#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(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_|.
+ static inline MOZ_MUST_USE 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);
+
+/* static */ inline MOZ_MUST_USE 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.
+ MOZ_MUST_USE 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.
+ MOZ_ALWAYS_INLINE
+ MOZ_MUST_USE 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(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 {}
+ MOZ_MUST_USE bool checkSimulatedOOM() const {
+ return fb == Infallible || !js::oom::ShouldFailWithOOM();
+ }
+};
+
+} // namespace js
+
+#endif /* ds_LifoAlloc_h */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-18 22:18:52 +0000