Source code

Revision control

Other Tools

/* -*- 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 */