From 2aa4a82499d4becd2284cdb482213d541b8804dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 16:29:10 +0200 Subject: Adding upstream version 86.0.1. Signed-off-by: Daniel Baumann --- js/src/ds/BitArray.h | 114 +++ js/src/ds/Bitmap.cpp | 103 +++ js/src/ds/Bitmap.h | 176 ++++ js/src/ds/Fifo.h | 187 +++++ js/src/ds/FixedLengthVector.h | 112 +++ js/src/ds/IdValuePair.h | 35 + js/src/ds/InlineTable.h | 645 +++++++++++++++ js/src/ds/LifoAlloc.cpp | 430 ++++++++++ js/src/ds/LifoAlloc.h | 1031 ++++++++++++++++++++++++ js/src/ds/MemoryProtectionExceptionHandler.cpp | 789 ++++++++++++++++++ js/src/ds/MemoryProtectionExceptionHandler.h | 44 + js/src/ds/Nestable.h | 63 ++ js/src/ds/OrderedHashTable.h | 893 ++++++++++++++++++++ js/src/ds/PageProtectingVector.h | 502 ++++++++++++ js/src/ds/PriorityQueue.h | 125 +++ js/src/ds/Sort.h | 146 ++++ js/src/ds/SplayTree.h | 354 ++++++++ js/src/ds/TraceableFifo.h | 93 +++ 18 files changed, 5842 insertions(+) create mode 100644 js/src/ds/BitArray.h create mode 100644 js/src/ds/Bitmap.cpp create mode 100644 js/src/ds/Bitmap.h create mode 100644 js/src/ds/Fifo.h create mode 100644 js/src/ds/FixedLengthVector.h create mode 100644 js/src/ds/IdValuePair.h create mode 100644 js/src/ds/InlineTable.h create mode 100644 js/src/ds/LifoAlloc.cpp create mode 100644 js/src/ds/LifoAlloc.h create mode 100644 js/src/ds/MemoryProtectionExceptionHandler.cpp create mode 100644 js/src/ds/MemoryProtectionExceptionHandler.h create mode 100644 js/src/ds/Nestable.h create mode 100644 js/src/ds/OrderedHashTable.h create mode 100644 js/src/ds/PageProtectingVector.h create mode 100644 js/src/ds/PriorityQueue.h create mode 100644 js/src/ds/Sort.h create mode 100644 js/src/ds/SplayTree.h create mode 100644 js/src/ds/TraceableFifo.h (limited to 'js/src/ds') diff --git a/js/src/ds/BitArray.h b/js/src/ds/BitArray.h new file mode 100644 index 0000000000..bdd78873fd --- /dev/null +++ b/js/src/ds/BitArray.h @@ -0,0 +1,114 @@ +/* -*- 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_BitArray_h +#define ds_BitArray_h + +#include "mozilla/MathAlgorithms.h" +#include "mozilla/TemplateLib.h" + +#include +#include + +#include "jstypes.h" + +namespace js { + +namespace detail { + +template +inline uint_fast8_t CountTrailingZeroes(WordT word); + +template <> +inline uint_fast8_t CountTrailingZeroes(uint32_t word) { + return mozilla::CountTrailingZeroes32(word); +} + +template <> +inline uint_fast8_t CountTrailingZeroes(uint64_t word) { + return mozilla::CountTrailingZeroes64(word); +} + +} // namespace detail + +template +class BitArray { + public: + // Use a 32 bit word to make it easier to access a BitArray from JIT code. + using WordT = uint32_t; + + static const size_t bitsPerElement = sizeof(WordT) * CHAR_BIT; + static const size_t numSlots = + nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1); + + private: + static const size_t paddingBits = (numSlots * bitsPerElement) - nbits; + static_assert(paddingBits < bitsPerElement, + "More padding bits than expected."); + static const WordT paddingMask = WordT(-1) >> paddingBits; + + WordT map[numSlots]; + + public: + constexpr BitArray() : map(){}; + + void clear(bool value) { + memset(map, value ? 0xFF : 0, sizeof(map)); + if (value) { + map[numSlots - 1] &= paddingMask; + } + } + + inline bool get(size_t offset) const { + size_t index; + WordT mask; + getIndexAndMask(offset, &index, &mask); + MOZ_ASSERT(index < nbits); + return map[index] & mask; + } + + void set(size_t offset) { + size_t index; + WordT mask; + getIndexAndMask(offset, &index, &mask); + map[index] |= mask; + } + + void unset(size_t offset) { + size_t index; + WordT mask; + getIndexAndMask(offset, &index, &mask); + map[index] &= ~mask; + } + + bool isAllClear() const { + for (size_t i = 0; i < numSlots; i++) { + if (map[i]) { + return false; + } + } + return true; + } + + // For iterating over the set bits in the bit array, get a word at a time. + WordT getWord(size_t elementIndex) const { + MOZ_ASSERT(elementIndex < nbits); + return map[elementIndex]; + } + + static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) { + MOZ_ASSERT(offset < nbits); + static_assert(bitsPerElement == 32, "unexpected bitsPerElement value"); + *indexp = offset / bitsPerElement; + *maskp = WordT(1) << (offset % bitsPerElement); + } + + static size_t offsetOfMap() { return offsetof(BitArray, map); } +}; + +} /* namespace js */ + +#endif /* ds_BitArray_h */ diff --git a/js/src/ds/Bitmap.cpp b/js/src/ds/Bitmap.cpp new file mode 100644 index 0000000000..79f7969e01 --- /dev/null +++ b/js/src/ds/Bitmap.cpp @@ -0,0 +1,103 @@ +/* -*- 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/. */ + +#include "ds/Bitmap.h" + +#include + +#include "js/UniquePtr.h" + +using namespace js; + +SparseBitmap::~SparseBitmap() { + for (Data::Range r(data.all()); !r.empty(); r.popFront()) { + js_delete(r.front().value()); + } +} + +size_t SparseBitmap::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) { + size_t size = data.shallowSizeOfExcludingThis(mallocSizeOf); + for (Data::Range r(data.all()); !r.empty(); r.popFront()) { + size += mallocSizeOf(r.front().value()); + } + return size; +} + +SparseBitmap::BitBlock* SparseBitmap::createBlock(Data::AddPtr p, + size_t blockId) { + MOZ_ASSERT(!p); + auto block = js::MakeUnique(); + if (!block || !data.add(p, blockId, block.get())) { + return nullptr; + } + std::fill(block->begin(), block->end(), 0); + return block.release(); +} + +SparseBitmap::BitBlock& SparseBitmap::createBlock( + Data::AddPtr p, size_t blockId, AutoEnterOOMUnsafeRegion& oomUnsafe) { + BitBlock* block = createBlock(p, blockId); + if (!block) { + oomUnsafe.crash("Bitmap OOM"); + } + return *block; +} + +bool SparseBitmap::getBit(size_t bit) const { + size_t word = bit / JS_BITS_PER_WORD; + size_t blockWord = blockStartWord(word); + + BitBlock* block = getBlock(blockWord / WordsInBlock); + if (block) { + return (*block)[word - blockWord] & + (uintptr_t(1) << (bit % JS_BITS_PER_WORD)); + } + return false; +} + +void SparseBitmap::bitwiseAndWith(const DenseBitmap& other) { + for (Data::Enum e(data); !e.empty(); e.popFront()) { + BitBlock& block = *e.front().value(); + size_t blockWord = e.front().key() * WordsInBlock; + bool anySet = false; + size_t numWords = wordIntersectCount(blockWord, other); + for (size_t i = 0; i < numWords; i++) { + block[i] &= other.word(blockWord + i); + anySet |= !!block[i]; + } + if (!anySet) { + js_delete(&block); + e.removeFront(); + } + } +} + +void SparseBitmap::bitwiseOrWith(const SparseBitmap& other) { + for (Data::Range r(other.data.all()); !r.empty(); r.popFront()) { + const BitBlock& otherBlock = *r.front().value(); + BitBlock& block = getOrCreateBlock(r.front().key()); + for (size_t i = 0; i < WordsInBlock; i++) { + block[i] |= otherBlock[i]; + } + } +} + +void SparseBitmap::bitwiseOrInto(DenseBitmap& other) const { + for (Data::Range r(data.all()); !r.empty(); r.popFront()) { + BitBlock& block = *r.front().value(); + size_t blockWord = r.front().key() * WordsInBlock; + size_t numWords = wordIntersectCount(blockWord, other); +#ifdef DEBUG + // Any words out of range in other should be zero in this bitmap. + for (size_t i = numWords; i < WordsInBlock; i++) { + MOZ_ASSERT(!block[i]); + } +#endif + for (size_t i = 0; i < numWords; i++) { + other.word(blockWord + i) |= block[i]; + } + } +} diff --git a/js/src/ds/Bitmap.h b/js/src/ds/Bitmap.h new file mode 100644 index 0000000000..74b04bfe3f --- /dev/null +++ b/js/src/ds/Bitmap.h @@ -0,0 +1,176 @@ +/* -*- 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_Bitmap_h +#define ds_Bitmap_h + +#include "mozilla/Array.h" +#include "mozilla/Assertions.h" +#include "mozilla/Attributes.h" +#include "mozilla/MemoryChecking.h" + +#include +#include +#include + +#include "js/AllocPolicy.h" +#include "js/HashTable.h" +#include "js/HeapAPI.h" +#include "js/Vector.h" + +// This file provides two classes for representing bitmaps. +// +// DenseBitmap is an array of words of bits, with size linear in the maximum +// bit which has been set on it. +// +// SparseBitmap provides a reasonably simple, reasonably efficient (in time and +// space) implementation of a sparse bitmap. The basic representation is a hash +// table whose entries are fixed length malloc'ed blocks of bits. + +namespace js { + +class DenseBitmap { + using Data = Vector; + + Data data; + + public: + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) { + return data.sizeOfExcludingThis(mallocSizeOf); + } + + bool ensureSpace(size_t numWords) { + MOZ_ASSERT(data.empty()); + return data.appendN(0, numWords); + } + + size_t numWords() const { return data.length(); } + uintptr_t word(size_t i) const { return data[i]; } + uintptr_t& word(size_t i) { return data[i]; } + + template + typename std::enable_if_t, void> + copyBitsFrom(size_t wordStart, size_t numWords, T* source) { + MOZ_ASSERT(wordStart + numWords <= data.length()); + for (size_t i = 0; i < numWords; i++) { + data[wordStart + i] = source[i]; + } + } + + template + typename std::enable_if_t, void> + bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const { + for (size_t i = 0; i < numWords; i++) { + target[i] |= data[wordStart + i]; + } + } +}; + +class SparseBitmap { + // The number of words of bits to use for each block mainly affects the + // memory usage of the bitmap. To minimize overhead, bitmaps which are + // expected to be fairly dense should have a large block size, and bitmaps + // which are expected to be very sparse should have a small block size. + static const size_t WordsInBlock = 4096 / sizeof(uintptr_t); + + using BitBlock = mozilla::Array; + using Data = + HashMap, SystemAllocPolicy>; + + Data data; + + static size_t blockStartWord(size_t word) { + return word & ~(WordsInBlock - 1); + } + + // Return the number of words in a BitBlock starting at |blockWord| which + // are in |other|. + static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) { + long count = other.numWords() - blockWord; + return std::min((size_t)WordsInBlock, std::max(count, 0)); + } + + BitBlock& createBlock(Data::AddPtr p, size_t blockId, + AutoEnterOOMUnsafeRegion& oomUnsafe); + + BitBlock* createBlock(Data::AddPtr p, size_t blockId); + + MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const { + Data::Ptr p = data.lookup(blockId); + return p ? p->value() : nullptr; + } + + MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) { + // The lookupForAdd() needs protection against injected OOMs, as does + // the add() within createBlock(). + AutoEnterOOMUnsafeRegion oomUnsafe; + Data::AddPtr p = data.lookupForAdd(blockId); + if (p) { + return *p->value(); + } + return createBlock(p, blockId, oomUnsafe); + } + + MOZ_ALWAYS_INLINE BitBlock* getOrCreateBlockFallible(size_t blockId) { + Data::AddPtr p = data.lookupForAdd(blockId); + if (p) { + return p->value(); + } + return createBlock(p, blockId); + } + + public: + ~SparseBitmap(); + + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf); + + MOZ_ALWAYS_INLINE void setBit(size_t bit) { + size_t word = bit / JS_BITS_PER_WORD; + size_t blockWord = blockStartWord(word); + BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock); + block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD); + } + + MOZ_ALWAYS_INLINE bool setBitFallible(size_t bit) { + size_t word = bit / JS_BITS_PER_WORD; + size_t blockWord = blockStartWord(word); + BitBlock* block = getOrCreateBlockFallible(blockWord / WordsInBlock); + if (!block) { + return false; + } + (*block)[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD); + return true; + } + + bool getBit(size_t bit) const; + + void bitwiseAndWith(const DenseBitmap& other); + void bitwiseOrWith(const SparseBitmap& other); + void bitwiseOrInto(DenseBitmap& other) const; + + // Currently, this API only supports a range of words that is in a single bit + // block. + template + typename std::enable_if_t, void> + bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const { + size_t blockWord = blockStartWord(wordStart); + + // We only support using a single bit block in this API. + MOZ_ASSERT(numWords && + (blockWord == blockStartWord(wordStart + numWords - 1))); + + BitBlock* block = getBlock(blockWord / WordsInBlock); + if (block) { + for (size_t i = 0; i < numWords; i++) { + target[i] |= (*block)[wordStart - blockWord + i]; + } + } + } +}; + +} // namespace js + +#endif // ds_Bitmap_h diff --git a/js/src/ds/Fifo.h b/js/src/ds/Fifo.h new file mode 100644 index 0000000000..236412f2cc --- /dev/null +++ b/js/src/ds/Fifo.h @@ -0,0 +1,187 @@ +/* -*- 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 js_Fifo_h +#define js_Fifo_h + +#include +#include + +#include "js/Vector.h" + +namespace js { + +// A first-in-first-out queue container type. Fifo calls constructors and +// destructors of all elements added so non-PODs may be used safely. |Fifo| +// stores the first |MinInlineCapacity| elements in-place before resorting to +// dynamic allocation. +// +// T requirements: +// - Either movable or copyable. +// MinInlineCapacity requirements: +// - Must be even. +// AllocPolicy: +// - see "Allocation policies" in AllocPolicy.h +template +class Fifo { + static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!"); + + protected: + // An element A is "younger" than an element B if B was inserted into the + // |Fifo| before A was. + // + // Invariant 1: Every element within |front_| is older than every element + // within |rear_|. + // Invariant 2: Entries within |front_| are sorted from younger to older. + // Invariant 3: Entries within |rear_| are sorted from older to younger. + // Invariant 4: If the |Fifo| is not empty, then |front_| is not empty. + Vector front_; + Vector rear_; + + private: + // Maintain invariants after adding or removing entries. + void fixup() { + if (front_.empty() && !rear_.empty()) { + front_.swap(rear_); + std::reverse(front_.begin(), front_.end()); + } + } + + public: + explicit Fifo(AllocPolicy alloc = AllocPolicy()) + : front_(alloc), rear_(alloc) {} + + Fifo(Fifo&& rhs) + : front_(std::move(rhs.front_)), rear_(std::move(rhs.rear_)) {} + + Fifo& operator=(Fifo&& rhs) { + MOZ_ASSERT(&rhs != this, "self-move disallowed"); + this->~Fifo(); + new (this) Fifo(std::move(rhs)); + return *this; + } + + Fifo(const Fifo&) = delete; + Fifo& operator=(const Fifo&) = delete; + + size_t length() const { + MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4. + return front_.length() + rear_.length(); + } + + bool empty() const { + MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0); // Invariant 4. + return front_.empty(); + } + + // Iterator from oldest to yongest element. + struct ConstIterator { + const Fifo& self_; + size_t idx_; + + ConstIterator(const Fifo& self, size_t idx) : self_(self), idx_(idx) {} + + ConstIterator& operator++() { + ++idx_; + return *this; + } + + const T& operator*() const { + // Iterate front in reverse, then rear. + size_t split = self_.front_.length(); + return (idx_ < split) ? self_.front_[(split - 1) - idx_] + : self_.rear_[idx_ - split]; + } + + bool operator!=(const ConstIterator& other) const { + return (&self_ != &other.self_) || (idx_ != other.idx_); + } + }; + + ConstIterator begin() const { return ConstIterator(*this, 0); } + + ConstIterator end() const { return ConstIterator(*this, length()); } + + // Push an element to the back of the queue. This method can take either a + // |const T&| or a |T&&|. + template + MOZ_MUST_USE bool pushBack(U&& u) { + if (!rear_.append(std::forward(u))) { + return false; + } + fixup(); + return true; + } + + // Construct a T in-place at the back of the queue. + template + MOZ_MUST_USE bool emplaceBack(Args&&... args) { + if (!rear_.emplaceBack(std::forward(args)...)) { + return false; + } + fixup(); + return true; + } + + // Access the element at the front of the queue. + T& front() { + MOZ_ASSERT(!empty()); + return front_.back(); + } + const T& front() const { + MOZ_ASSERT(!empty()); + return front_.back(); + } + + // Remove the front element from the queue. + void popFront() { + MOZ_ASSERT(!empty()); + front_.popBack(); + fixup(); + } + + // Convenience utility. + T popCopyFront() { + T ret = front(); + popFront(); + return ret; + } + + // Clear all elements from the queue. + void clear() { + front_.clear(); + rear_.clear(); + } + + // Clear all elements for which the given predicate returns 'true'. Return + // the number of elements removed. + template + size_t eraseIf(Pred pred) { + size_t frontLength = front_.length(); + front_.eraseIf(pred); + size_t erased = frontLength - front_.length(); + + size_t rearLength = rear_.length(); + rear_.eraseIf(pred); + erased += rearLength - rear_.length(); + + fixup(); + return erased; + } + + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + return front_.sizeOfExcludingThis(mallocSizeOf) + + rear_.sizeOfExcludingThis(mallocSizeOf); + } + size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf); + } +}; + +} // namespace js + +#endif /* js_Fifo_h */ diff --git a/js/src/ds/FixedLengthVector.h b/js/src/ds/FixedLengthVector.h new file mode 100644 index 0000000000..fab8fb08aa --- /dev/null +++ b/js/src/ds/FixedLengthVector.h @@ -0,0 +1,112 @@ +/* -*- 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_FixedLengthVector_h +#define ds_FixedLengthVector_h + +#include "mozilla/Assertions.h" // MOZ_ASSERT +#include "mozilla/Attributes.h" // MOZ_MUST_USE +#include "mozilla/OperatorNewExtensions.h" // mozilla::KnownNotNull + +#include // size_t + +#include "js/Utility.h" // js_free +#include "vm/JSContext.h" // JSContext + +namespace js { + +// A dynamically-allocated fixed-length vector with bounds checking assertions. +template +class FixedLengthVector { + // The pointer to the storage. + T* data_ = nullptr; + + // The size of the storage. + size_t length_ = 0; + + public: + FixedLengthVector() = default; + + FixedLengthVector(FixedLengthVector&) = delete; + FixedLengthVector(FixedLengthVector&&) = default; + + ~FixedLengthVector() { + if (initialized()) { + js_free(data_); + } + } + + size_t length() const { return length_; } + + bool initialized() const { return !!data_; } + + // Allocate the storage with the given size, wihtout calling constructor. + // + // If the allocation fails, this returns false and sets the + // pending exception on the given context. + MOZ_MUST_USE bool allocateUninitialized(JSContext* cx, size_t length) { + MOZ_ASSERT(!initialized()); + + length_ = length; + data_ = cx->pod_malloc(length); + if (MOZ_UNLIKELY(!data_)) { + return false; + } + + return true; + } + + // Allocate the storage with the given size and call default constructor. + // + // If the allocation fails, this returns false and sets the + // pending exception on the given context. + MOZ_MUST_USE bool allocate(JSContext* cx, size_t length) { + if (!allocateUninitialized(cx, length)) { + return false; + } + + for (size_t i = 0; i < length; i++) { + new (mozilla::KnownNotNull, &data_[i]) T(); + } + return true; + } + + T* begin() { + MOZ_ASSERT(initialized()); + return data_; + } + + const T* begin() const { + MOZ_ASSERT(initialized()); + return data_; + } + + T* end() { + MOZ_ASSERT(initialized()); + return data_ + length_; + } + + const T* end() const { + MOZ_ASSERT(initialized()); + return data_ + length_; + } + + T& operator[](size_t index) { + MOZ_ASSERT(initialized()); + MOZ_ASSERT(index < length_); + return begin()[index]; + } + + const T& operator[](size_t index) const { + MOZ_ASSERT(initialized()); + MOZ_ASSERT(index < length_); + return begin()[index]; + } +}; + +} // namespace js + +#endif // ds_FixedLengthVector_h diff --git a/js/src/ds/IdValuePair.h b/js/src/ds/IdValuePair.h new file mode 100644 index 0000000000..acf6b8b5fa --- /dev/null +++ b/js/src/ds/IdValuePair.h @@ -0,0 +1,35 @@ +/* -*- 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_IdValuePair_h +#define ds_IdValuePair_h + +#include "gc/Tracer.h" +#include "js/GCVector.h" +#include "js/Id.h" +#include "js/Value.h" + +namespace js { + +struct IdValuePair { + JS::Value value; + jsid id; + + IdValuePair() : value(JS::UndefinedValue()), id(JSID_EMPTY) {} + explicit IdValuePair(jsid idArg) : value(JS::UndefinedValue()), id(idArg) {} + IdValuePair(jsid idArg, const Value& valueArg) : value(valueArg), id(idArg) {} + + void trace(JSTracer* trc) { + TraceRoot(trc, &value, "IdValuePair::value"); + TraceRoot(trc, &id, "IdValuePair::id"); + } +}; + +using IdValueVector = JS::GCVector; + +} /* namespace js */ + +#endif /* ds_IdValuePair_h */ diff --git a/js/src/ds/InlineTable.h b/js/src/ds/InlineTable.h new file mode 100644 index 0000000000..dc898b0c50 --- /dev/null +++ b/js/src/ds/InlineTable.h @@ -0,0 +1,645 @@ +/* -*- 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_InlineTable_h +#define ds_InlineTable_h + +#include "mozilla/Maybe.h" + +#include + +#include "js/AllocPolicy.h" +#include "js/HashTable.h" + +namespace js { + +namespace detail { + +// The InlineTable below needs an abstract way of testing keys for +// tombstone values, and to set a key in an entry to a tombstone. +// This is provided by the KeyPolicy generic type argument, which +// has a default implementation for pointers provided below. + +// A default implementation of a KeyPolicy for some types (only pointer +// types for now). +// +// The `KeyPolicy` type parameter informs an InlineTable of how to +// check for tombstone values and to set tombstone values within +// the domain of key (entry). +// +// A `KeyPolicy` for some key type `K` must provide two static methods: +// static bool isTombstone(const K& key); +// static void setToTombstone(K& key); +template +class DefaultKeyPolicy; + +template +class DefaultKeyPolicy { + DefaultKeyPolicy() = delete; + DefaultKeyPolicy(const T*&) = delete; + + public: + static bool isTombstone(T* const& ptr) { return ptr == nullptr; } + static void setToTombstone(T*& ptr) { ptr = nullptr; } +}; + +template +class InlineTable : private AllocPolicy { + private: + using TablePtr = typename Table::Ptr; + using TableAddPtr = typename Table::AddPtr; + using TableRange = typename Table::Range; + using Lookup = typename HashPolicy::Lookup; + + size_t inlNext_; + size_t inlCount_; + InlineEntry inl_[InlineEntries]; + Table table_; + +#ifdef DEBUG + template + static bool keyNonZero(const Key& key) { + // Zero as tombstone means zero keys are invalid. + return !!key; + } +#endif + + InlineEntry* inlineStart() { + MOZ_ASSERT(!usingTable()); + return inl_; + } + + const InlineEntry* inlineStart() const { + MOZ_ASSERT(!usingTable()); + return inl_; + } + + InlineEntry* inlineEnd() { + MOZ_ASSERT(!usingTable()); + return inl_ + inlNext_; + } + + const InlineEntry* inlineEnd() const { + MOZ_ASSERT(!usingTable()); + return inl_ + inlNext_; + } + + bool usingTable() const { return inlNext_ > InlineEntries; } + + MOZ_MUST_USE bool switchToTable() { + MOZ_ASSERT(inlNext_ == InlineEntries); + + table_.clear(); + + InlineEntry* end = inlineEnd(); + for (InlineEntry* it = inlineStart(); it != end; ++it) { + if (it->key && !it->moveTo(table_)) { + return false; + } + } + + inlNext_ = InlineEntries + 1; + MOZ_ASSERT(table_.count() == inlCount_); + MOZ_ASSERT(usingTable()); + return true; + } + + MOZ_NEVER_INLINE + MOZ_MUST_USE bool switchAndAdd(const InlineEntry& entry) { + if (!switchToTable()) { + return false; + } + + return entry.putNew(table_); + } + + public: + static const size_t SizeOfInlineEntries = sizeof(InlineEntry) * InlineEntries; + + explicit InlineTable(AllocPolicy a = AllocPolicy()) + : AllocPolicy(std::move(a)), inlNext_(0), inlCount_(0), table_(a) {} + + class Ptr { + friend class InlineTable; + + protected: + MOZ_INIT_OUTSIDE_CTOR Entry entry_; + MOZ_INIT_OUTSIDE_CTOR TablePtr tablePtr_; + MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlPtr_; + MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_; + + explicit Ptr(TablePtr p) + : entry_(p.found() ? &*p : nullptr), + tablePtr_(p), + isInlinePtr_(false) {} + + explicit Ptr(InlineEntry* inlineEntry) + : entry_(inlineEntry), inlPtr_(inlineEntry), isInlinePtr_(true) {} + + void operator==(const Ptr& other); + + public: + // Leaves Ptr uninitialized. + Ptr() { +#ifdef DEBUG + inlPtr_ = (InlineEntry*)0xbad; + isInlinePtr_ = true; +#endif + } + + // Default copy constructor works for this structure. + + bool found() const { + return isInlinePtr_ ? bool(inlPtr_) : tablePtr_.found(); + } + + explicit operator bool() const { return found(); } + + bool operator==(const Ptr& other) const { + MOZ_ASSERT(found() && other.found()); + if (isInlinePtr_ != other.isInlinePtr_) { + return false; + } + if (isInlinePtr_) { + return inlPtr_ == other.inlPtr_; + } + return tablePtr_ == other.tablePtr_; + } + + bool operator!=(const Ptr& other) const { return !(*this == other); } + + Entry& operator*() { + MOZ_ASSERT(found()); + return entry_; + } + + Entry* operator->() { + MOZ_ASSERT(found()); + return &entry_; + } + }; + + class AddPtr { + friend class InlineTable; + + protected: + MOZ_INIT_OUTSIDE_CTOR Entry entry_; + MOZ_INIT_OUTSIDE_CTOR TableAddPtr tableAddPtr_; + MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlAddPtr_; + MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_; + // Indicates whether inlAddPtr is a found result or an add pointer. + MOZ_INIT_OUTSIDE_CTOR bool inlPtrFound_; + + AddPtr(InlineEntry* ptr, bool found) + : entry_(ptr), + inlAddPtr_(ptr), + isInlinePtr_(true), + inlPtrFound_(found) {} + + explicit AddPtr(const TableAddPtr& p) + : entry_(p.found() ? &*p : nullptr), + tableAddPtr_(p), + isInlinePtr_(false) {} + + public: + AddPtr() = default; + + bool found() const { + return isInlinePtr_ ? inlPtrFound_ : tableAddPtr_.found(); + } + + explicit operator bool() const { return found(); } + + bool operator==(const AddPtr& other) const { + MOZ_ASSERT(found() && other.found()); + if (isInlinePtr_ != other.isInlinePtr_) { + return false; + } + if (isInlinePtr_) { + return inlAddPtr_ == other.inlAddPtr_; + } + return tableAddPtr_ == other.tableAddPtr_; + } + + bool operator!=(const AddPtr& other) const { return !(*this == other); } + + Entry& operator*() { + MOZ_ASSERT(found()); + return entry_; + } + + Entry* operator->() { + MOZ_ASSERT(found()); + return &entry_; + } + }; + + size_t count() const { return usingTable() ? table_.count() : inlCount_; } + + bool empty() const { return usingTable() ? table_.empty() : !inlCount_; } + + void clear() { + inlNext_ = 0; + inlCount_ = 0; + } + + MOZ_ALWAYS_INLINE + Ptr lookup(const Lookup& l) { + MOZ_ASSERT(keyNonZero(l)); + + if (usingTable()) { + return Ptr(table_.lookup(l)); + } + + InlineEntry* end = inlineEnd(); + for (InlineEntry* it = inlineStart(); it != end; ++it) { + if (it->key && HashPolicy::match(it->key, l)) { + return Ptr(it); + } + } + + return Ptr(nullptr); + } + + MOZ_ALWAYS_INLINE + AddPtr lookupForAdd(const Lookup& l) { + MOZ_ASSERT(keyNonZero(l)); + + if (usingTable()) { + return AddPtr(table_.lookupForAdd(l)); + } + + InlineEntry* end = inlineEnd(); + for (InlineEntry* it = inlineStart(); it != end; ++it) { + if (it->key && HashPolicy::match(it->key, l)) { + return AddPtr(it, true); + } + } + + // The add pointer that's returned here may indicate the limit entry of + // the linear space, in which case the |add| operation will initialize + // the table if necessary and add the entry there. + return AddPtr(inlineEnd(), false); + } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key, + Args&&... args) { + MOZ_ASSERT(!p); + MOZ_ASSERT(keyNonZero(key)); + + if (p.isInlinePtr_) { + InlineEntry* addPtr = p.inlAddPtr_; + MOZ_ASSERT(addPtr == inlineEnd()); + + // Switching to table mode before we add this pointer. + if (addPtr == inlineStart() + InlineEntries) { + if (!switchToTable()) { + return false; + } + return table_.putNew(std::forward(key), + std::forward(args)...); + } + + MOZ_ASSERT(!p.found()); + MOZ_ASSERT(uintptr_t(inlineEnd()) == uintptr_t(p.inlAddPtr_)); + + if (!this->checkSimulatedOOM()) { + return false; + } + + addPtr->update(std::forward(key), std::forward(args)...); + ++inlCount_; + ++inlNext_; + return true; + } + + return table_.add(p.tableAddPtr_, std::forward(key), + std::forward(args)...); + } + + void remove(Ptr& p) { + MOZ_ASSERT(p); + if (p.isInlinePtr_) { + MOZ_ASSERT(inlCount_ > 0); + MOZ_ASSERT(!KeyPolicy::isTombstone(p.inlPtr_->key)); + KeyPolicy::setToTombstone(p.inlPtr_->key); + --inlCount_; + return; + } + MOZ_ASSERT(usingTable()); + table_.remove(p.tablePtr_); + } + + void remove(const Lookup& l) { + if (Ptr p = lookup(l)) { + remove(p); + } + } + + class Range { + friend class InlineTable; + + protected: + mozilla::Maybe tableRange_; // `Nothing` if `isInline_==true` + InlineEntry* cur_; + InlineEntry* end_; + bool isInline_; + + explicit Range(TableRange r) + : tableRange_(mozilla::Some(r)), + cur_(nullptr), + end_(nullptr), + isInline_(false) { + MOZ_ASSERT(!isInlineRange()); + } + + Range(const InlineEntry* begin, const InlineEntry* end) + : tableRange_(mozilla::Nothing()), + cur_(const_cast(begin)), + end_(const_cast(end)), + isInline_(true) { + advancePastNulls(cur_); + MOZ_ASSERT(isInlineRange()); + } + + bool assertInlineRangeInvariants() const { + MOZ_ASSERT(uintptr_t(cur_) <= uintptr_t(end_)); + MOZ_ASSERT_IF(cur_ != end_, !KeyPolicy::isTombstone(cur_->key)); + return true; + } + + bool isInlineRange() const { + MOZ_ASSERT_IF(isInline_, assertInlineRangeInvariants()); + return isInline_; + } + + void advancePastNulls(InlineEntry* begin) { + InlineEntry* newCur = begin; + while (newCur < end_ && KeyPolicy::isTombstone(newCur->key)) { + ++newCur; + } + MOZ_ASSERT(uintptr_t(newCur) <= uintptr_t(end_)); + cur_ = newCur; + } + + void bumpCurPtr() { + MOZ_ASSERT(isInlineRange()); + advancePastNulls(cur_ + 1); + } + + public: + bool empty() const { + return isInlineRange() ? cur_ == end_ : tableRange_->empty(); + } + + Entry front() { + MOZ_ASSERT(!empty()); + if (isInlineRange()) { + return Entry(cur_); + } + return Entry(&tableRange_->front()); + } + + void popFront() { + MOZ_ASSERT(!empty()); + if (isInlineRange()) { + bumpCurPtr(); + } else { + tableRange_->popFront(); + } + } + }; + + Range all() const { + return usingTable() ? Range(table_.all()) + : Range(inlineStart(), inlineEnd()); + } +}; + +} // namespace detail + +// A map with InlineEntries number of entries kept inline in an array. +// +// The Key type must be zeroable as zeros are used as tombstone keys. +// The Value type must have a default constructor. +// +// The API is very much like HashMap's. +template , + typename AllocPolicy = TempAllocPolicy, + typename KeyPolicy = detail::DefaultKeyPolicy> +class InlineMap { + using Map = HashMap; + + struct InlineEntry { + Key key; + Value value; + + template + void update(KeyInput&& key, ValueInput&& value) { + this->key = std::forward(key); + this->value = std::forward(value); + } + + MOZ_MUST_USE bool moveTo(Map& map) { + return map.putNew(std::move(key), std::move(value)); + } + }; + + class Entry { + using MapEntry = typename Map::Entry; + + MapEntry* mapEntry_; + InlineEntry* inlineEntry_; + + public: + Entry() = default; + + explicit Entry(MapEntry* mapEntry) + : mapEntry_(mapEntry), inlineEntry_(nullptr) {} + + explicit Entry(InlineEntry* inlineEntry) + : mapEntry_(nullptr), inlineEntry_(inlineEntry) {} + + const Key& key() const { + MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_); + if (mapEntry_) { + return mapEntry_->key(); + } + return inlineEntry_->key; + } + + Value& value() { + MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_); + if (mapEntry_) { + return mapEntry_->value(); + } + return inlineEntry_->value; + } + }; + + using Impl = detail::InlineTable; + + Impl impl_; + + public: + using Table = Map; + using Ptr = typename Impl::Ptr; + using AddPtr = typename Impl::AddPtr; + using Range = typename Impl::Range; + using Lookup = typename HashPolicy::Lookup; + + static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries; + + explicit InlineMap(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {} + + size_t count() const { return impl_.count(); } + + bool empty() const { return impl_.empty(); } + + void clear() { impl_.clear(); } + + Range all() const { return impl_.all(); } + + MOZ_ALWAYS_INLINE + Ptr lookup(const Lookup& l) { return impl_.lookup(l); } + + MOZ_ALWAYS_INLINE + bool has(const Lookup& l) const { + return const_cast(this)->lookup(l).found(); + } + + MOZ_ALWAYS_INLINE + AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key, + ValueInput&& value) { + return impl_.add(p, std::forward(key), + std::forward(value)); + } + + template + MOZ_MUST_USE bool put(KeyInput&& key, ValueInput&& value) { + AddPtr p = lookupForAdd(key); + if (p) { + p->value() = std::forward(value); + return true; + } + return add(p, std::forward(key), std::forward(value)); + } + + void remove(Ptr& p) { impl_.remove(p); } + + void remove(const Lookup& l) { impl_.remove(l); } +}; + +// A set with InlineEntries number of entries kept inline in an array. +// +// The T type must be zeroable as zeros are used as tombstone keys. +// The T type must have a default constructor. +// +// The API is very much like HashMap's. +template , + typename AllocPolicy = TempAllocPolicy, + typename KeyPolicy = detail::DefaultKeyPolicy> +class InlineSet { + using Set = HashSet; + + struct InlineEntry { + T key; + + template + void update(TInput&& key) { + this->key = std::forward(key); + } + + MOZ_MUST_USE bool moveTo(Set& set) { return set.putNew(std::move(key)); } + }; + + class Entry { + using SetEntry = typename Set::Entry; + + SetEntry* setEntry_; + InlineEntry* inlineEntry_; + + public: + Entry() = default; + + explicit Entry(const SetEntry* setEntry) + : setEntry_(const_cast(setEntry)), inlineEntry_(nullptr) {} + + explicit Entry(InlineEntry* inlineEntry) + : setEntry_(nullptr), inlineEntry_(inlineEntry) {} + + operator T() const { + MOZ_ASSERT(!!setEntry_ != !!inlineEntry_); + if (setEntry_) { + return *setEntry_; + } + return inlineEntry_->key; + } + }; + + using Impl = detail::InlineTable; + + Impl impl_; + + public: + using Table = Set; + using Ptr = typename Impl::Ptr; + using AddPtr = typename Impl::AddPtr; + using Range = typename Impl::Range; + using Lookup = typename HashPolicy::Lookup; + + static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries; + + explicit InlineSet(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {} + + size_t count() const { return impl_.count(); } + + bool empty() const { return impl_.empty(); } + + void clear() { impl_.clear(); } + + Range all() const { return impl_.all(); } + + MOZ_ALWAYS_INLINE + Ptr lookup(const Lookup& l) { return impl_.lookup(l); } + + MOZ_ALWAYS_INLINE + bool has(const Lookup& l) const { + return const_cast(this)->lookup(l).found(); + } + + MOZ_ALWAYS_INLINE + AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, TInput&& key) { + return impl_.add(p, std::forward(key)); + } + + template + MOZ_MUST_USE bool put(TInput&& key) { + AddPtr p = lookupForAdd(key); + return p ? true : add(p, std::forward(key)); + } + + void remove(Ptr& p) { impl_.remove(p); } + + void remove(const Lookup& l) { impl_.remove(l); } +}; + +} // namespace js + +#endif // ds_InlineTable_h diff --git a/js/src/ds/LifoAlloc.cpp b/js/src/ds/LifoAlloc.cpp new file mode 100644 index 0000000000..dc0b172b65 --- /dev/null +++ b/js/src/ds/LifoAlloc.cpp @@ -0,0 +1,430 @@ +/* -*- 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/. */ + +#include "ds/LifoAlloc.h" + +#include "mozilla/Likely.h" +#include "mozilla/MathAlgorithms.h" + +#include + +#include "ds/MemoryProtectionExceptionHandler.h" + +#ifdef LIFO_CHUNK_PROTECT +# include "gc/Memory.h" +#endif + +using namespace js; + +using mozilla::RoundUpPow2; +using mozilla::tl::BitSize; + +namespace js { +namespace detail { + +/* static */ +UniquePtr BumpChunk::newWithCapacity(size_t size) { + MOZ_DIAGNOSTIC_ASSERT(size >= sizeof(BumpChunk)); + void* mem = js_malloc(size); + if (!mem) { + return nullptr; + } + + UniquePtr result(new (mem) BumpChunk(size)); + + // We assume that the alignment of LIFO_ALLOC_ALIGN is less than that of the + // underlying memory allocator -- creating a new BumpChunk should always + // satisfy the LIFO_ALLOC_ALIGN alignment constraint. + MOZ_ASSERT(AlignPtr(result->begin()) == result->begin()); + return result; +} + +#ifdef LIFO_CHUNK_PROTECT + +static uint8_t* AlignPtrUp(uint8_t* ptr, uintptr_t align) { + MOZ_ASSERT(mozilla::IsPowerOfTwo(align)); + uintptr_t uptr = uintptr_t(ptr); + uintptr_t diff = uptr & (align - 1); + diff = (align - diff) & (align - 1); + uptr = uptr + diff; + return (uint8_t*)uptr; +} + +static uint8_t* AlignPtrDown(uint8_t* ptr, uintptr_t align) { + MOZ_ASSERT(mozilla::IsPowerOfTwo(align)); + uintptr_t uptr = uintptr_t(ptr); + uptr = uptr & ~(align - 1); + return (uint8_t*)uptr; +} + +void BumpChunk::setReadOnly() { + uintptr_t pageSize = gc::SystemPageSize(); + // The allocated chunks might not be aligned on page boundaries. This code + // is used to ensure that we are changing the memory protection of pointers + // which are within the range of the BumpChunk, or that the range formed by + // [b .. e] is empty. + uint8_t* b = base(); + uint8_t* e = capacity_; + b = AlignPtrUp(b, pageSize); + e = AlignPtrDown(e, pageSize); + if (e <= b) { + return; + } + js::MemoryProtectionExceptionHandler::addRegion(base(), capacity_ - base()); + gc::MakePagesReadOnly(b, e - b); +} + +void BumpChunk::setReadWrite() { + uintptr_t pageSize = gc::SystemPageSize(); + // The allocated chunks might not be aligned on page boundaries. This code + // is used to ensure that we are changing the memory protection of pointers + // which are within the range of the BumpChunk, or that the range formed by + // [b .. e] is empty. + uint8_t* b = base(); + uint8_t* e = capacity_; + b = AlignPtrUp(b, pageSize); + e = AlignPtrDown(e, pageSize); + if (e <= b) { + return; + } + gc::UnprotectPages(b, e - b); + js::MemoryProtectionExceptionHandler::removeRegion(base()); +} + +#endif + +} // namespace detail +} // namespace js + +void LifoAlloc::reset(size_t defaultChunkSize) { + MOZ_ASSERT(mozilla::IsPowerOfTwo(defaultChunkSize)); + + while (!chunks_.empty()) { + chunks_.popFirst(); + } + while (!oversize_.empty()) { + oversize_.popFirst(); + } + while (!unused_.empty()) { + unused_.popFirst(); + } + defaultChunkSize_ = defaultChunkSize; + oversizeThreshold_ = defaultChunkSize; + markCount = 0; + curSize_ = 0; + smallAllocsSize_ = 0; +} + +void LifoAlloc::freeAll() { + // When free-ing 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; + + while (!chunks_.empty()) { + UniqueBumpChunk bc = chunks_.popFirst(); + decrementCurSize(bc->computedSizeOfIncludingThis()); + } + while (!oversize_.empty()) { + UniqueBumpChunk bc = oversize_.popFirst(); + decrementCurSize(bc->computedSizeOfIncludingThis()); + } + while (!unused_.empty()) { + UniqueBumpChunk bc = unused_.popFirst(); + decrementCurSize(bc->computedSizeOfIncludingThis()); + } + + // Nb: maintaining curSize_ correctly isn't easy. Fortunately, this is an + // excellent sanity check. + MOZ_ASSERT(curSize_ == 0); +} + +// Round at the same page granularity used by malloc. +static size_t MallocGoodSize(size_t aSize) { +#if defined(MOZ_MEMORY) + return malloc_good_size(aSize); +#else + return aSize; +#endif +} + +// Heuristic to choose the size of the next BumpChunk for small allocations. +// `start` is the size of the first chunk. `used` is the total size of all +// BumpChunks in this LifoAlloc so far. +static size_t NextSize(size_t start, size_t used) { + // Double the size, up to 1 MB. + const size_t mb = 1 * 1024 * 1024; + if (used < mb) { + return std::max(start, used); + } + + // After 1 MB, grow more gradually, to waste less memory. + // The sequence (in megabytes) begins: + // 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, ... + return RoundUp(used / 8, mb); +} + +LifoAlloc::UniqueBumpChunk LifoAlloc::newChunkWithCapacity(size_t n, + bool oversize) { + MOZ_ASSERT(fallibleScope_, + "[OOM] Cannot allocate a new chunk in an infallible scope."); + + // Compute the size which should be requested in order to be able to fit |n| + // bytes in a newly allocated chunk, or default to |defaultChunkSize_|. + + size_t minSize; + if (MOZ_UNLIKELY(!detail::BumpChunk::allocSizeWithRedZone(n, &minSize) || + (minSize & (size_t(1) << (BitSize::value - 1))))) { + return nullptr; + } + + // Note: When computing chunkSize growth, we only are interested in chunks + // used for small allocations. This excludes unused chunks, oversized chunks, + // and chunks transferred in from another LifoAlloc. + MOZ_ASSERT(curSize_ >= smallAllocsSize_); + const size_t chunkSize = (oversize || minSize > defaultChunkSize_) + ? MallocGoodSize(minSize) + : NextSize(defaultChunkSize_, smallAllocsSize_); + + // Create a new BumpChunk, and allocate space for it. + UniqueBumpChunk result = detail::BumpChunk::newWithCapacity(chunkSize); + if (!result) { + return nullptr; + } + MOZ_ASSERT(result->computedSizeOfIncludingThis() == chunkSize); + return result; +} + +LifoAlloc::UniqueBumpChunk LifoAlloc::getOrCreateChunk(size_t n) { + // Look for existing unused BumpChunks to satisfy the request, and pick the + // first one which is large enough, and move it into the list of used + // chunks. + if (!unused_.empty()) { + if (unused_.begin()->canAlloc(n)) { + return unused_.popFirst(); + } + + BumpChunkList::Iterator e(unused_.end()); + for (BumpChunkList::Iterator i(unused_.begin()); i->next() != e.get(); + ++i) { + detail::BumpChunk* elem = i->next(); + MOZ_ASSERT(elem->empty()); + if (elem->canAlloc(n)) { + BumpChunkList temp = unused_.splitAfter(i.get()); + UniqueBumpChunk newChunk = temp.popFirst(); + unused_.appendAll(std::move(temp)); + return newChunk; + } + } + } + + // Allocate a new BumpChunk with enough space for the next allocation. + UniqueBumpChunk newChunk = newChunkWithCapacity(n, false); + if (!newChunk) { + return newChunk; + } + incrementCurSize(newChunk->computedSizeOfIncludingThis()); + return newChunk; +} + +void* LifoAlloc::allocImplColdPath(size_t n) { + void* result; + UniqueBumpChunk newChunk = getOrCreateChunk(n); + if (!newChunk) { + return nullptr; + } + + // This new chunk is about to be used for small allocations. + smallAllocsSize_ += newChunk->computedSizeOfIncludingThis(); + + // Since we just created a large enough chunk, this can't fail. + chunks_.append(std::move(newChunk)); + result = chunks_.last()->tryAlloc(n); + MOZ_ASSERT(result); + return result; +} + +void* LifoAlloc::allocImplOversize(size_t n) { + void* result; + UniqueBumpChunk newChunk = newChunkWithCapacity(n, true); + if (!newChunk) { + return nullptr; + } + incrementCurSize(newChunk->computedSizeOfIncludingThis()); + + // Since we just created a large enough chunk, this can't fail. + oversize_.append(std::move(newChunk)); + result = oversize_.last()->tryAlloc(n); + MOZ_ASSERT(result); + return result; +} + +bool LifoAlloc::ensureUnusedApproximateColdPath(size_t n, size_t total) { + for (detail::BumpChunk& bc : unused_) { + total += bc.unused(); + if (total >= n) { + return true; + } + } + + UniqueBumpChunk newChunk = newChunkWithCapacity(n, false); + if (!newChunk) { + return false; + } + incrementCurSize(newChunk->computedSizeOfIncludingThis()); + unused_.pushFront(std::move(newChunk)); + return true; +} + +LifoAlloc::Mark LifoAlloc::mark() { + markCount++; + Mark res; + if (!chunks_.empty()) { + res.chunk = chunks_.last()->mark(); + } + if (!oversize_.empty()) { + res.oversize = oversize_.last()->mark(); + } + return res; +} + +void LifoAlloc::release(Mark mark) { + markCount--; +#ifdef DEBUG + auto assertIsContained = [](const detail::BumpChunk::Mark& m, + BumpChunkList& list) { + if (m.markedChunk()) { + bool contained = false; + for (const detail::BumpChunk& chunk : list) { + if (&chunk == m.markedChunk() && chunk.contains(m)) { + contained = true; + break; + } + } + MOZ_ASSERT(contained); + } + }; + assertIsContained(mark.chunk, chunks_); + assertIsContained(mark.oversize, oversize_); +#endif + + BumpChunkList released; + auto cutAtMark = [&released](const detail::BumpChunk::Mark& m, + BumpChunkList& list) { + // Move the blocks which are after the mark to the set released chunks. + if (!m.markedChunk()) { + released = std::move(list); + } else { + released = list.splitAfter(m.markedChunk()); + } + + // Release everything which follows the mark in the last chunk. + if (!list.empty()) { + list.last()->release(m); + } + }; + + // Release the content of all the blocks which are after the marks, and keep + // blocks as unused. + cutAtMark(mark.chunk, chunks_); + for (detail::BumpChunk& bc : released) { + bc.release(); + + // Chunks moved from (after a mark) in chunks_ to unused_ are no longer + // considered small allocations. + smallAllocsSize_ -= bc.computedSizeOfIncludingThis(); + } + unused_.appendAll(std::move(released)); + + // Free the content of all the blocks which are after the marks. + cutAtMark(mark.oversize, oversize_); + while (!released.empty()) { + UniqueBumpChunk bc = released.popFirst(); + decrementCurSize(bc->computedSizeOfIncludingThis()); + } +} + +void LifoAlloc::steal(LifoAlloc* other) { + MOZ_ASSERT(!other->markCount); + MOZ_DIAGNOSTIC_ASSERT(unused_.empty()); + MOZ_DIAGNOSTIC_ASSERT(chunks_.empty()); + MOZ_DIAGNOSTIC_ASSERT(oversize_.empty()); + + // Copy everything from |other| to |this| except for |peakSize_|, which + // requires some care. + chunks_ = std::move(other->chunks_); + oversize_ = std::move(other->oversize_); + unused_ = std::move(other->unused_); + markCount = other->markCount; + defaultChunkSize_ = other->defaultChunkSize_; + oversizeThreshold_ = other->oversizeThreshold_; + curSize_ = other->curSize_; + peakSize_ = std::max(peakSize_, other->peakSize_); + smallAllocsSize_ = other->smallAllocsSize_; +#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT) + fallibleScope_ = other->fallibleScope_; +#endif + + other->reset(defaultChunkSize_); +} + +void LifoAlloc::transferFrom(LifoAlloc* other) { + MOZ_ASSERT(!markCount); + MOZ_ASSERT(!other->markCount); + + // Transferred chunks are not counted as part of |smallAllocsSize| as this + // could introduce bias in the |NextSize| heuristics, leading to + // over-allocations in *this* LifoAlloc. As well, to avoid interference with + // small allocations made with |this|, the last chunk of the |chunks_| list + // should remain the last chunk. Therefore, the transferred chunks are + // prepended to the |chunks_| list. + incrementCurSize(other->curSize_); + + appendUnused(std::move(other->unused_)); + chunks_.prependAll(std::move(other->chunks_)); + oversize_.prependAll(std::move(other->oversize_)); + other->curSize_ = 0; + other->smallAllocsSize_ = 0; +} + +void LifoAlloc::transferUnusedFrom(LifoAlloc* other) { + MOZ_ASSERT(!markCount); + + size_t size = 0; + for (detail::BumpChunk& bc : other->unused_) { + size += bc.computedSizeOfIncludingThis(); + } + + appendUnused(std::move(other->unused_)); + incrementCurSize(size); + other->decrementCurSize(size); +} + +#ifdef LIFO_CHUNK_PROTECT +void LifoAlloc::setReadOnly() { + for (detail::BumpChunk& bc : chunks_) { + bc.setReadOnly(); + } + for (detail::BumpChunk& bc : oversize_) { + bc.setReadOnly(); + } + for (detail::BumpChunk& bc : unused_) { + bc.setReadOnly(); + } +} + +void LifoAlloc::setReadWrite() { + for (detail::BumpChunk& bc : chunks_) { + bc.setReadWrite(); + } + for (detail::BumpChunk& bc : oversize_) { + bc.setReadWrite(); + } + for (detail::BumpChunk& bc : unused_) { + bc.setReadWrite(); + } +} +#endif 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 +#include +#include // size_t +#include +#include + +// 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 +class SingleLinkedList; + +template > +class SingleLinkedListElement { + friend class SingleLinkedList; + js::UniquePtr 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 > +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 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&& elem) { + if (!last_) { + last_ = elem.get(); + } + elem->next_ = std::move(head_); + head_ = std::move(elem); + assertInvariants(); + } + + void append(UniquePtr&& 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 popFirst() { + MOZ_ASSERT(head_); + UniquePtr 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 { + 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(this); } + uint8_t* base() { return reinterpret_cast(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 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; + using BumpChunkList = detail::SingleLinkedList; + + // 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 + 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)...); + } + + 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 + T* newArray(size_t count) { + static_assert(std::is_trivial_v, + "T must be trivially constructible so that constructors need " + "not be called"); + static_assert(std::is_trivially_destructible_v, + "T must be trivially destructible so destructors don't need " + "to be called when the LifoAlloc is freed"); + return newArrayUninitialized(count); + } + + // Create an array with uninitialized elements of type |T|. + // The caller is responsible for initialization. + template + T* newArrayUninitialized(size_t count) { + size_t bytes; + if (MOZ_UNLIKELY(!CalculateAllocSize(count, &bytes))) { + return nullptr; + } + return static_cast(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 + MOZ_ALWAYS_INLINE T* pod_malloc() { + return static_cast(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 + T* read(size_t size = sizeof(T)) { + return reinterpret_cast(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 +class LifoAllocPolicy { + LifoAlloc& alloc_; + + public: + MOZ_IMPLICIT LifoAllocPolicy(LifoAlloc& alloc) : alloc_(alloc) {} + template + T* maybe_pod_malloc(size_t numElems) { + size_t bytes; + if (MOZ_UNLIKELY(!CalculateAllocSize(numElems, &bytes))) { + return nullptr; + } + void* p = + fb == Fallible ? alloc_.alloc(bytes) : alloc_.allocInfallible(bytes); + return static_cast(p); + } + template + T* maybe_pod_calloc(size_t numElems) { + T* p = maybe_pod_malloc(numElems); + if (MOZ_UNLIKELY(!p)) { + return nullptr; + } + memset(p, 0, numElems * sizeof(T)); + return p; + } + template + T* maybe_pod_realloc(T* p, size_t oldSize, size_t newSize) { + T* n = maybe_pod_malloc(newSize); + if (MOZ_UNLIKELY(!n)) { + return nullptr; + } + MOZ_ASSERT(!(oldSize & mozilla::tl::MulOverflowMask::value)); + memcpy(n, p, std::min(oldSize * sizeof(T), newSize * sizeof(T))); + return n; + } + template + T* pod_malloc(size_t numElems) { + return maybe_pod_malloc(numElems); + } + template + T* pod_calloc(size_t numElems) { + return maybe_pod_calloc(numElems); + } + template + T* pod_realloc(T* p, size_t oldSize, size_t newSize) { + return maybe_pod_realloc(p, oldSize, newSize); + } + template + 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 */ diff --git a/js/src/ds/MemoryProtectionExceptionHandler.cpp b/js/src/ds/MemoryProtectionExceptionHandler.cpp new file mode 100644 index 0000000000..3c4eb00c30 --- /dev/null +++ b/js/src/ds/MemoryProtectionExceptionHandler.cpp @@ -0,0 +1,789 @@ +/* -*- 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/. */ + +#include "ds/MemoryProtectionExceptionHandler.h" + +#include "mozilla/Assertions.h" +#include "mozilla/Atomics.h" + +#if defined(XP_WIN) +# include "util/Windows.h" +#elif defined(XP_UNIX) && !defined(XP_DARWIN) +# include +# include +# include +#elif defined(XP_DARWIN) +# include +# include +#endif + +#ifdef ANDROID +# include +#endif + +#include "ds/SplayTree.h" + +#include "threading/LockGuard.h" +#include "threading/Thread.h" +#include "vm/MutexIDs.h" +#include "vm/Runtime.h" + +namespace js { + +// Memory protection occurs at non-deterministic points when +// recording/replaying. +static mozilla::Atomic + sProtectedRegionsInit(false); + +/* + * A class to store the addresses of the regions recognized as protected + * by this exception handler. We use a splay tree to store these addresses. + */ +class ProtectedRegionTree { + struct Region { + uintptr_t first; + uintptr_t last; + + Region(uintptr_t addr, size_t size) + : first(addr), last(addr + (size - 1)) {} + + // This function compares 2 memory regions. If they overlap they are + // considered as identical. This is used for querying if an address is + // included in a range, or if an address is already registered as a + // protected region. + static int compare(const Region& A, const Region& B) { + if (A.last < B.first) { + return -1; + } + if (A.first > B.last) { + return 1; + } + return 0; + } + }; + + Mutex lock; + LifoAlloc alloc; + SplayTree tree; + + public: + ProtectedRegionTree() + : lock(mutexid::ProtectedRegionTree), + // Here "false" is used to not use the memory protection mechanism of + // LifoAlloc in order to prevent dead-locks. + alloc(4096), + tree(&alloc) { + sProtectedRegionsInit = true; + } + + ~ProtectedRegionTree() { sProtectedRegionsInit = false; } + + void insert(uintptr_t addr, size_t size) { + MOZ_ASSERT(addr && size); + LockGuard guard(lock); + AutoEnterOOMUnsafeRegion oomUnsafe; + if (!tree.insert(Region(addr, size))) { + oomUnsafe.crash("Failed to store allocation ID."); + } + } + + void remove(uintptr_t addr) { + MOZ_ASSERT(addr); + LockGuard guard(lock); + tree.remove(Region(addr, 1)); + } + + bool isProtected(uintptr_t addr) { + if (!addr) { + return false; + } + LockGuard guard(lock); + return tree.maybeLookup(Region(addr, 1)); + } +}; + +static bool sExceptionHandlerInstalled = false; + +static ProtectedRegionTree sProtectedRegions; + +bool MemoryProtectionExceptionHandler::isDisabled() { +#if defined(XP_WIN) && defined(MOZ_ASAN) + // Under Windows ASan, WasmFaultHandler registers itself at 'last' priority + // in order to let ASan's ShadowExceptionHandler stay at 'first' priority. + // Unfortunately that results in spurious wasm faults passing through the + // MemoryProtectionExceptionHandler, which breaks its assumption that any + // faults it sees are fatal. Just disable this handler in that case, as the + // crash annotations provided here are not critical for ASan builds. + return true; +#elif !defined(MOZ_DIAGNOSTIC_ASSERT_ENABLED) + // Disable the exception handler for Beta and Release builds. + return true; +#else + return false; +#endif +} + +void MemoryProtectionExceptionHandler::addRegion(void* addr, size_t size) { + if (sExceptionHandlerInstalled && sProtectedRegionsInit) { + sProtectedRegions.insert(uintptr_t(addr), size); + } +} + +void MemoryProtectionExceptionHandler::removeRegion(void* addr) { + if (sExceptionHandlerInstalled && sProtectedRegionsInit) { + sProtectedRegions.remove(uintptr_t(addr)); + } +} + +/* -------------------------------------------------------------------------- */ + +/* + * This helper function attempts to replicate the functionality of + * mozilla::MOZ_ReportCrash() in an async-signal-safe way. + */ +static MOZ_COLD MOZ_ALWAYS_INLINE void ReportCrashIfDebug(const char* aStr) + MOZ_PRETEND_NORETURN_FOR_STATIC_ANALYSIS { +#ifdef DEBUG +# if defined(XP_WIN) + DWORD bytesWritten; + BOOL ret = WriteFile(GetStdHandle(STD_ERROR_HANDLE), aStr, strlen(aStr) + 1, + &bytesWritten, nullptr); +# elif defined(ANDROID) + int ret = __android_log_write(ANDROID_LOG_FATAL, "MOZ_CRASH", aStr); +# else + ssize_t ret = write(STDERR_FILENO, aStr, strlen(aStr) + 1); +# endif + (void)ret; // Ignore failures; we're already crashing anyway. +#endif +} + +/* -------------------------------------------------------------------------- */ + +#if defined(XP_WIN) + +static void* sVectoredExceptionHandler = nullptr; + +/* + * We can only handle one exception. To guard against races and reentrancy, + * we set this value the first time we enter the exception handler and never + * touch it again. + */ +static mozilla::Atomic sHandlingException(false); + +static long __stdcall VectoredExceptionHandler( + EXCEPTION_POINTERS* ExceptionInfo) { + EXCEPTION_RECORD* ExceptionRecord = ExceptionInfo->ExceptionRecord; + + // We only handle one kind of exception; ignore all others. + if (ExceptionRecord->ExceptionCode == EXCEPTION_ACCESS_VIOLATION) { + // Make absolutely sure we can only get here once. + if (sHandlingException.compareExchange(false, true)) { + // Restore the previous handler. We're going to forward to it + // anyway, and if we crash while doing so we don't want to hang. + MOZ_ALWAYS_TRUE( + RemoveVectoredExceptionHandler(sVectoredExceptionHandler)); + sExceptionHandlerInstalled = false; + + // Get the address that the offending code tried to access. + uintptr_t address = uintptr_t(ExceptionRecord->ExceptionInformation[1]); + + // If the faulting address is in one of our protected regions, we + // want to annotate the crash to make it stand out from the crowd. + if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) { + ReportCrashIfDebug( + "Hit MOZ_CRASH(Tried to access a protected region!)\n"); + MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)"); + } + } + } + + // Forward to the previous handler which may be a debugger, + // the crash reporter or something else entirely. + return EXCEPTION_CONTINUE_SEARCH; +} + +bool MemoryProtectionExceptionHandler::install() { + MOZ_ASSERT(!sExceptionHandlerInstalled); + + // If the exception handler is disabled, report success anyway. + if (MemoryProtectionExceptionHandler::isDisabled()) { + return true; + } + + // Install our new exception handler. + sVectoredExceptionHandler = AddVectoredExceptionHandler( + /* FirstHandler = */ true, VectoredExceptionHandler); + + sExceptionHandlerInstalled = sVectoredExceptionHandler != nullptr; + return sExceptionHandlerInstalled; +} + +void MemoryProtectionExceptionHandler::uninstall() { + if (sExceptionHandlerInstalled) { + MOZ_ASSERT(!sHandlingException); + + // Restore the previous exception handler. + MOZ_ALWAYS_TRUE(RemoveVectoredExceptionHandler(sVectoredExceptionHandler)); + + sExceptionHandlerInstalled = false; + } +} + +#elif defined(XP_UNIX) && !defined(XP_DARWIN) + +static struct sigaction sPrevSEGVHandler = {}; + +/* + * We can only handle one exception. To guard against races and reentrancy, + * we set this value the first time we enter the exception handler and never + * touch it again. + */ +static mozilla::Atomic sHandlingException(false); + +static void UnixExceptionHandler(int signum, siginfo_t* info, void* context) { + // Make absolutely sure we can only get here once. + if (sHandlingException.compareExchange(false, true)) { + // Restore the previous handler. We're going to forward to it + // anyway, and if we crash while doing so we don't want to hang. + MOZ_ALWAYS_FALSE(sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr)); + + MOZ_ASSERT(signum == SIGSEGV && info->si_signo == SIGSEGV); + + if (info->si_code == SEGV_ACCERR) { + // Get the address that the offending code tried to access. + uintptr_t address = uintptr_t(info->si_addr); + + // If the faulting address is in one of our protected regions, we + // want to annotate the crash to make it stand out from the crowd. + if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) { + ReportCrashIfDebug( + "Hit MOZ_CRASH(Tried to access a protected region!)\n"); + MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)"); + } + } + } + + // Forward to the previous handler which may be a debugger, + // the crash reporter or something else entirely. + if (sPrevSEGVHandler.sa_flags & SA_SIGINFO) { + sPrevSEGVHandler.sa_sigaction(signum, info, context); + } else if (sPrevSEGVHandler.sa_handler == SIG_DFL || + sPrevSEGVHandler.sa_handler == SIG_IGN) { + sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr); + } else { + sPrevSEGVHandler.sa_handler(signum); + } + + // If we reach here, we're returning to let the default signal handler deal + // with the exception. This is technically undefined behavior, but + // everything seems to do it, and it removes us from the crash stack. +} + +bool MemoryProtectionExceptionHandler::install() { + MOZ_ASSERT(!sExceptionHandlerInstalled); + + // If the exception handler is disabled, report success anyway. + if (MemoryProtectionExceptionHandler::isDisabled()) { + return true; + } + + // Install our new exception handler and save the previous one. + struct sigaction faultHandler = {}; + faultHandler.sa_flags = SA_SIGINFO | SA_NODEFER | SA_ONSTACK; + faultHandler.sa_sigaction = UnixExceptionHandler; + sigemptyset(&faultHandler.sa_mask); + sExceptionHandlerInstalled = + !sigaction(SIGSEGV, &faultHandler, &sPrevSEGVHandler); + + return sExceptionHandlerInstalled; +} + +void MemoryProtectionExceptionHandler::uninstall() { + if (sExceptionHandlerInstalled) { + MOZ_ASSERT(!sHandlingException); + + // Restore the previous exception handler. + MOZ_ALWAYS_FALSE(sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr)); + + sExceptionHandlerInstalled = false; + } +} + +#elif defined(XP_DARWIN) + +/* + * The fact that we need to be able to forward to other exception handlers + * makes this code much more complicated. The forwarding logic and the + * structures required to make it work are heavily based on the code at + * www.ravenbrook.com/project/mps/prototype/2013-06-24/machtest/machtest/main.c + */ + +/* -------------------------------------------------------------------------- */ +/* Begin Mach definitions and helper functions */ +/* -------------------------------------------------------------------------- */ + +/* + * These are the message IDs associated with each exception type. + * We'll be using sIDRequest64, but we need the others for forwarding. + */ +static const mach_msg_id_t sIDRequest32 = 2401; +static const mach_msg_id_t sIDRequestState32 = 2402; +static const mach_msg_id_t sIDRequestStateIdentity32 = 2403; + +static const mach_msg_id_t sIDRequest64 = 2405; +static const mach_msg_id_t sIDRequestState64 = 2406; +static const mach_msg_id_t sIDRequestStateIdentity64 = 2407; + +/* + * Each message ID has an associated Mach message structure. + * We use the preprocessor to make defining them a little less arduous. + */ +# define REQUEST_HEADER_FIELDS mach_msg_header_t header; + +# define REQUEST_IDENTITY_FIELDS \ + mach_msg_body_t msgh_body; \ + mach_msg_port_descriptor_t thread; \ + mach_msg_port_descriptor_t task; + +# define REQUEST_GENERAL_FIELDS(bits) \ + NDR_record_t NDR; \ + exception_type_t exception; \ + mach_msg_type_number_t code_count; \ + int##bits##_t code[2]; + +# define REQUEST_STATE_FIELDS \ + int flavor; \ + mach_msg_type_number_t old_state_count; \ + natural_t old_state[THREAD_STATE_MAX]; + +# define REQUEST_TRAILER_FIELDS mach_msg_trailer_t trailer; + +# define EXCEPTION_REQUEST(bits) \ + struct ExceptionRequest##bits { \ + REQUEST_HEADER_FIELDS \ + REQUEST_IDENTITY_FIELDS \ + REQUEST_GENERAL_FIELDS(bits) \ + REQUEST_TRAILER_FIELDS \ + }; + +# define EXCEPTION_REQUEST_STATE(bits) \ + struct ExceptionRequestState##bits { \ + REQUEST_HEADER_FIELDS \ + REQUEST_GENERAL_FIELDS(bits) \ + REQUEST_STATE_FIELDS \ + REQUEST_TRAILER_FIELDS \ + }; + +# define EXCEPTION_REQUEST_STATE_IDENTITY(bits) \ + struct ExceptionRequestStateIdentity##bits { \ + REQUEST_HEADER_FIELDS \ + REQUEST_IDENTITY_FIELDS \ + REQUEST_GENERAL_FIELDS(bits) \ + REQUEST_STATE_FIELDS \ + REQUEST_TRAILER_FIELDS \ + }; + +/* This is needed because not all fields are naturally aligned on 64-bit. */ +# ifdef __MigPackStructs +# pragma pack(4) +# endif + +EXCEPTION_REQUEST(32) +EXCEPTION_REQUEST(64) +EXCEPTION_REQUEST_STATE(32) +EXCEPTION_REQUEST_STATE(64) +EXCEPTION_REQUEST_STATE_IDENTITY(32) +EXCEPTION_REQUEST_STATE_IDENTITY(64) + +/* We use this as a common base when forwarding to the previous handler. */ +union ExceptionRequestUnion { + mach_msg_header_t header; + ExceptionRequest32 r32; + ExceptionRequest64 r64; + ExceptionRequestState32 rs32; + ExceptionRequestState64 rs64; + ExceptionRequestStateIdentity32 rsi32; + ExceptionRequestStateIdentity64 rsi64; +}; + +/* This isn't really a full Mach message, but it's all we need to send. */ +struct ExceptionReply { + mach_msg_header_t header; + NDR_record_t NDR; + kern_return_t RetCode; +}; + +# ifdef __MigPackStructs +# pragma pack() +# endif + +# undef EXCEPTION_REQUEST_STATE_IDENTITY +# undef EXCEPTION_REQUEST_STATE +# undef EXCEPTION_REQUEST +# undef REQUEST_STATE_FIELDS +# undef REQUEST_GENERAL_FIELDS +# undef REQUEST_IDENTITY_FIELDS +# undef REQUEST_HEADER_FIELDS + +/* + * The exception handler we're forwarding to may not have the same behavior + * or thread state flavor as what we're using. These macros help populate + * the fields of the message we're about to send to the previous handler. + */ +# define COPY_REQUEST_COMMON(bits, id) \ + dst.header = src.header; \ + dst.header.msgh_id = id; \ + dst.header.msgh_size = \ + static_cast(sizeof(dst) - sizeof(dst.trailer)); \ + dst.NDR = src.NDR; \ + dst.exception = src.exception; \ + dst.code_count = src.code_count; \ + dst.code[0] = int##bits##_t(src.code[0]); \ + dst.code[1] = int##bits##_t(src.code[1]); + +# define COPY_REQUEST_IDENTITY \ + dst.msgh_body = src.msgh_body; \ + dst.thread = src.thread; \ + dst.task = src.task; + +# define COPY_REQUEST_STATE(flavor, stateCount, state) \ + mach_msg_size_t stateSize = stateCount * sizeof(natural_t); \ + dst.header.msgh_size = \ + static_cast(sizeof(dst) - sizeof(dst.trailer) - \ + sizeof(dst.old_state) + stateSize); \ + dst.flavor = flavor; \ + dst.old_state_count = stateCount; \ + memcpy(dst.old_state, state, stateSize); + +# define COPY_EXCEPTION_REQUEST(bits) \ + static void CopyExceptionRequest##bits(ExceptionRequest64& src, \ + ExceptionRequest##bits& dst) { \ + COPY_REQUEST_COMMON(bits, sIDRequest##bits) \ + COPY_REQUEST_IDENTITY \ + } + +# define COPY_EXCEPTION_REQUEST_STATE(bits) \ + static void CopyExceptionRequestState##bits( \ + ExceptionRequest64& src, ExceptionRequestState##bits& dst, \ + thread_state_flavor_t flavor, mach_msg_type_number_t stateCount, \ + thread_state_t state) { \ + COPY_REQUEST_COMMON(bits, sIDRequestState##bits) \ + COPY_REQUEST_STATE(flavor, stateCount, state) \ + } + +# define COPY_EXCEPTION_REQUEST_STATE_IDENTITY(bits) \ + static void CopyExceptionRequestStateIdentity##bits( \ + ExceptionRequest64& src, ExceptionRequestStateIdentity##bits& dst, \ + thread_state_flavor_t flavor, mach_msg_type_number_t stateCount, \ + thread_state_t state) { \ + COPY_REQUEST_COMMON(bits, sIDRequestStateIdentity##bits) \ + COPY_REQUEST_IDENTITY \ + COPY_REQUEST_STATE(flavor, stateCount, state) \ + } + +COPY_EXCEPTION_REQUEST(32) +COPY_EXCEPTION_REQUEST_STATE(32) +COPY_EXCEPTION_REQUEST_STATE_IDENTITY(32) +COPY_EXCEPTION_REQUEST(64) +COPY_EXCEPTION_REQUEST_STATE(64) +COPY_EXCEPTION_REQUEST_STATE_IDENTITY(64) + +# undef COPY_EXCEPTION_REQUEST_STATE_IDENTITY +# undef COPY_EXCEPTION_REQUEST_STATE +# undef COPY_EXCEPTION_REQUEST +# undef COPY_REQUEST_STATE +# undef COPY_REQUEST_IDENTITY +# undef COPY_REQUEST_COMMON + +/* -------------------------------------------------------------------------- */ +/* End Mach definitions and helper functions */ +/* -------------------------------------------------------------------------- */ + +/* Every Mach exception handler is parameterized by these four properties. */ +struct MachExceptionParameters { + exception_mask_t mask; + mach_port_t port; + exception_behavior_t behavior; + thread_state_flavor_t flavor; +}; + +struct ExceptionHandlerState { + MachExceptionParameters current; + MachExceptionParameters previous; + + /* Each Mach exception handler runs in its own thread. */ + Thread handlerThread; +}; + +/* This choice of ID is arbitrary, but must not match our exception ID. */ +static const mach_msg_id_t sIDQuit = 42; + +static ExceptionHandlerState* sMachExceptionState = nullptr; + +/* + * The meat of our exception handler. This thread waits for an exception + * message, annotates the exception if needed, then forwards it to the + * previously installed handler (which will likely terminate the process). + */ +static void MachExceptionHandler() { + ThisThread::SetName("JS MachExceptionHandler"); + kern_return_t ret; + MachExceptionParameters& current = sMachExceptionState->current; + MachExceptionParameters& previous = sMachExceptionState->previous; + + // We use the simplest kind of 64-bit exception message here. + ExceptionRequest64 request = {}; + request.header.msgh_local_port = current.port; + request.header.msgh_size = static_cast(sizeof(request)); + ret = mach_msg(&request.header, MACH_RCV_MSG, 0, request.header.msgh_size, + current.port, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL); + + // Restore the previous handler. We're going to forward to it + // anyway, and if we crash while doing so we don't want to hang. + task_set_exception_ports(mach_task_self(), previous.mask, previous.port, + previous.behavior, previous.flavor); + + // If we failed even receiving the message, just give up. + if (ret != MACH_MSG_SUCCESS) { + MOZ_CRASH("MachExceptionHandler: mach_msg failed to receive a message!"); + } + + // Terminate the thread if we're shutting down. + if (request.header.msgh_id == sIDQuit) { + return; + } + + // The only other valid message ID is the one associated with the + // EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES behavior we chose. + if (request.header.msgh_id != sIDRequest64) { + MOZ_CRASH("MachExceptionHandler: Unexpected Message ID!"); + } + + // Make sure we can understand the exception we received. + if (request.exception != EXC_BAD_ACCESS || request.code_count != 2) { + MOZ_CRASH("MachExceptionHandler: Unexpected exception type!"); + } + + // Get the address that the offending code tried to access. + uintptr_t address = uintptr_t(request.code[1]); + + // If the faulting address is inside one of our protected regions, we + // want to annotate the crash to make it stand out from the crowd. + if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) { + ReportCrashIfDebug("Hit MOZ_CRASH(Tried to access a protected region!)\n"); + MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)"); + } + + // Forward to the previous handler which may be a debugger, the unix + // signal handler, the crash reporter or something else entirely. + if (previous.port != MACH_PORT_NULL) { + mach_msg_type_number_t stateCount; + thread_state_data_t state; + if ((uint32_t(previous.behavior) & ~MACH_EXCEPTION_CODES) != + EXCEPTION_DEFAULT) { + // If the previous handler requested thread state, get it here. + stateCount = THREAD_STATE_MAX; + ret = thread_get_state(request.thread.name, previous.flavor, state, + &stateCount); + if (ret != KERN_SUCCESS) { + MOZ_CRASH( + "MachExceptionHandler: Could not get the thread state to forward!"); + } + } + + // Depending on the behavior of the previous handler, the forwarded + // exception message will have a different set of fields. + // Of particular note is that exception handlers that lack + // MACH_EXCEPTION_CODES will get 32-bit fields even on 64-bit + // systems. It appears that OSX simply truncates these fields. + ExceptionRequestUnion forward; + switch (uint32_t(previous.behavior)) { + case EXCEPTION_DEFAULT: + CopyExceptionRequest32(request, forward.r32); + break; + case EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES: + CopyExceptionRequest64(request, forward.r64); + break; + case EXCEPTION_STATE: + CopyExceptionRequestState32(request, forward.rs32, previous.flavor, + stateCount, state); + break; + case EXCEPTION_STATE | MACH_EXCEPTION_CODES: + CopyExceptionRequestState64(request, forward.rs64, previous.flavor, + stateCount, state); + break; + case EXCEPTION_STATE_IDENTITY: + CopyExceptionRequestStateIdentity32(request, forward.rsi32, + previous.flavor, stateCount, state); + break; + case EXCEPTION_STATE_IDENTITY | MACH_EXCEPTION_CODES: + CopyExceptionRequestStateIdentity64(request, forward.rsi64, + previous.flavor, stateCount, state); + break; + default: + MOZ_CRASH("MachExceptionHandler: Unknown previous handler behavior!"); + } + + // Forward the generated message to the old port. The local and remote + // port fields *and their rights* are swapped on arrival, so we need to + // swap them back first. + forward.header.msgh_bits = + (request.header.msgh_bits & ~MACH_MSGH_BITS_PORTS_MASK) | + MACH_MSGH_BITS(MACH_MSGH_BITS_LOCAL(request.header.msgh_bits), + MACH_MSGH_BITS_REMOTE(request.header.msgh_bits)); + forward.header.msgh_local_port = forward.header.msgh_remote_port; + forward.header.msgh_remote_port = previous.port; + ret = mach_msg(&forward.header, MACH_SEND_MSG, forward.header.msgh_size, 0, + MACH_PORT_NULL, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL); + if (ret != MACH_MSG_SUCCESS) { + MOZ_CRASH( + "MachExceptionHandler: Failed to forward to the previous handler!"); + } + } else { + // There was no previous task-level exception handler, so defer to the + // host level one instead. We set the return code to KERN_FAILURE to + // indicate that we did not handle the exception. + // The reply message ID is always the request ID + 100. + ExceptionReply reply = {}; + reply.header.msgh_bits = + MACH_MSGH_BITS(MACH_MSGH_BITS_REMOTE(request.header.msgh_bits), 0); + reply.header.msgh_size = static_cast(sizeof(reply)); + reply.header.msgh_remote_port = request.header.msgh_remote_port; + reply.header.msgh_local_port = MACH_PORT_NULL; + reply.header.msgh_id = request.header.msgh_id + 100; + reply.NDR = request.NDR; + reply.RetCode = KERN_FAILURE; + ret = mach_msg(&reply.header, MACH_SEND_MSG, reply.header.msgh_size, 0, + MACH_PORT_NULL, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL); + if (ret != MACH_MSG_SUCCESS) { + MOZ_CRASH("MachExceptionHandler: Failed to forward to the host level!"); + } + } +} + +static void TerminateMachExceptionHandlerThread() { + // Send a simple quit message to the exception handler thread. + mach_msg_header_t msg; + msg.msgh_bits = MACH_MSGH_BITS(MACH_MSG_TYPE_COPY_SEND, 0); + msg.msgh_size = static_cast(sizeof(msg)); + msg.msgh_remote_port = sMachExceptionState->current.port; + msg.msgh_local_port = MACH_PORT_NULL; + msg.msgh_reserved = 0; + msg.msgh_id = sIDQuit; + kern_return_t ret = + mach_msg(&msg, MACH_SEND_MSG, sizeof(msg), 0, MACH_PORT_NULL, + MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL); + + if (ret == MACH_MSG_SUCCESS) { + sMachExceptionState->handlerThread.join(); + } else { + MOZ_CRASH("MachExceptionHandler: Handler thread failed to terminate!"); + } +} + +bool MemoryProtectionExceptionHandler::install() { + MOZ_ASSERT(!sExceptionHandlerInstalled); + MOZ_ASSERT(!sMachExceptionState); + + // If the exception handler is disabled, report success anyway. + if (MemoryProtectionExceptionHandler::isDisabled()) { + return true; + } + + sMachExceptionState = js_new(); + if (!sMachExceptionState) { + return false; + } + + kern_return_t ret; + mach_port_t task = mach_task_self(); + + // Allocate a new exception port with receive rights. + sMachExceptionState->current = {}; + MachExceptionParameters& current = sMachExceptionState->current; + ret = mach_port_allocate(task, MACH_PORT_RIGHT_RECEIVE, ¤t.port); + if (ret != KERN_SUCCESS) { + return false; + } + + // Give the new port send rights as well. + ret = mach_port_insert_right(task, current.port, current.port, + MACH_MSG_TYPE_MAKE_SEND); + if (ret != KERN_SUCCESS) { + mach_port_deallocate(task, current.port); + current = {}; + return false; + } + + // Start the thread that will receive the messages from our exception port. + if (!sMachExceptionState->handlerThread.init(MachExceptionHandler)) { + mach_port_deallocate(task, current.port); + current = {}; + return false; + } + + // Set the other properties of our new exception handler. + current.mask = EXC_MASK_BAD_ACCESS; + current.behavior = + exception_behavior_t(EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES); + current.flavor = THREAD_STATE_NONE; + + // Tell the task to use our exception handler, and save the previous one. + sMachExceptionState->previous = {}; + MachExceptionParameters& previous = sMachExceptionState->previous; + mach_msg_type_number_t previousCount = 1; + ret = task_swap_exception_ports( + task, current.mask, current.port, current.behavior, current.flavor, + &previous.mask, &previousCount, &previous.port, &previous.behavior, + &previous.flavor); + if (ret != KERN_SUCCESS) { + TerminateMachExceptionHandlerThread(); + mach_port_deallocate(task, current.port); + previous = {}; + current = {}; + return false; + } + + // We should have info on the previous exception handler, even if it's null. + MOZ_ASSERT(previousCount == 1); + + sExceptionHandlerInstalled = true; + return sExceptionHandlerInstalled; +} + +void MemoryProtectionExceptionHandler::uninstall() { + if (sExceptionHandlerInstalled) { + MOZ_ASSERT(sMachExceptionState); + + mach_port_t task = mach_task_self(); + + // Restore the previous exception handler. + MachExceptionParameters& previous = sMachExceptionState->previous; + task_set_exception_ports(task, previous.mask, previous.port, + previous.behavior, previous.flavor); + + TerminateMachExceptionHandlerThread(); + + // Release the Mach IPC port we used. + mach_port_deallocate(task, sMachExceptionState->current.port); + + sMachExceptionState->current = {}; + sMachExceptionState->previous = {}; + + js_delete(sMachExceptionState); + sMachExceptionState = nullptr; + + sExceptionHandlerInstalled = false; + } +} + +#else + +# error "This platform is not supported!" + +#endif + +} /* namespace js */ diff --git a/js/src/ds/MemoryProtectionExceptionHandler.h b/js/src/ds/MemoryProtectionExceptionHandler.h new file mode 100644 index 0000000000..c6ba7514ba --- /dev/null +++ b/js/src/ds/MemoryProtectionExceptionHandler.h @@ -0,0 +1,44 @@ +/* -*- 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_MemoryProtectionExceptionHandler_h +#define ds_MemoryProtectionExceptionHandler_h + +#include "jstypes.h" + +namespace js { + +/* + * This structure allows you to annotate crashes resulting from unauthorized + * access to protected memory in regions of interest, to make them stand out + * from other heap corruption crashes. + */ + +struct MemoryProtectionExceptionHandler { + /* Installs the exception handler; called early during initialization. */ + static bool install(); + + /* If the exception handler is disabled, it won't be installed. */ + static bool isDisabled(); + + /* + * Marks a region of memory as important; if something tries to access this + * region in an unauthorized way (e.g. writing to read-only memory), + * the resulting crash will be annotated to stand out from other random + * heap corruption. + */ + static void addRegion(void* addr, size_t size); + + /* Removes a previously added region. */ + static void removeRegion(void* addr); + + /* Uninstalls the exception handler; called late during shutdown. */ + static void uninstall(); +}; + +} /* namespace js */ + +#endif /* ds_MemoryProtectionExceptionHandler_h */ diff --git a/js/src/ds/Nestable.h b/js/src/ds/Nestable.h new file mode 100644 index 0000000000..c27f7da534 --- /dev/null +++ b/js/src/ds/Nestable.h @@ -0,0 +1,63 @@ +/* -*- 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_Nestable_h +#define ds_Nestable_h + +#include "mozilla/Assertions.h" +#include "mozilla/Attributes.h" + +namespace js { + +// A base class for nestable structures. +template +class MOZ_STACK_CLASS Nestable { + Concrete** stack_; + Concrete* enclosing_; + + protected: + explicit Nestable(Concrete** stack) : stack_(stack), enclosing_(*stack) { + *stack_ = static_cast(this); + } + + // These method are protected. Some derived classes, such as ParseContext, + // do not expose the ability to walk the stack. + Concrete* enclosing() const { return enclosing_; } + + template bool */> + static Concrete* findNearest(Concrete* it, Predicate predicate) { + while (it && !predicate(it)) { + it = it->enclosing(); + } + return it; + } + + template + static T* findNearest(Concrete* it) { + while (it && !it->template is()) { + it = it->enclosing(); + } + return it ? &it->template as() : nullptr; + } + + template bool */> + static T* findNearest(Concrete* it, Predicate predicate) { + while (it && (!it->template is() || !predicate(&it->template as()))) { + it = it->enclosing(); + } + return it ? &it->template as() : nullptr; + } + + public: + ~Nestable() { + MOZ_ASSERT(*stack_ == static_cast(this)); + *stack_ = enclosing_; + } +}; + +} // namespace js + +#endif /* ds_Nestable_h */ diff --git a/js/src/ds/OrderedHashTable.h b/js/src/ds/OrderedHashTable.h new file mode 100644 index 0000000000..4044ee4d77 --- /dev/null +++ b/js/src/ds/OrderedHashTable.h @@ -0,0 +1,893 @@ +/* -*- 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_OrderedHashTable_h +#define ds_OrderedHashTable_h + +/* + * Define two collection templates, js::OrderedHashMap and js::OrderedHashSet. + * They are like js::HashMap and js::HashSet except that: + * + * - Iterating over an Ordered hash table visits the entries in the order in + * which they were inserted. This means that unlike a HashMap, the behavior + * of an OrderedHashMap is deterministic (as long as the HashPolicy methods + * are effect-free and consistent); the hashing is a pure performance + * optimization. + * + * - Range objects over Ordered tables remain valid even when entries are + * added or removed or the table is resized. (However in the case of + * removing entries, note the warning on class Range below.) + * + * - The API is a little different, so it's not a drop-in replacement. + * In particular, the hash policy is a little different. + * Also, the Ordered templates lack the Ptr and AddPtr types. + * + * Hash policies + * + * See the comment about "Hash policy" in HashTable.h for general features that + * hash policy classes must provide. Hash policies for OrderedHashMaps and Sets + * differ in that the hash() method takes an extra argument: + * static js::HashNumber hash(Lookup, const HashCodeScrambler&); + * They must additionally provide a distinguished "empty" key value and the + * following static member functions: + * bool isEmpty(const Key&); + * void makeEmpty(Key*); + */ + +#include "mozilla/HashFunctions.h" + +#include + +#include "js/HashTable.h" + +namespace js { + +namespace detail { + +/* + * detail::OrderedHashTable is the underlying data structure used to implement + * both OrderedHashMap and OrderedHashSet. Programs should use one of those two + * templates rather than OrderedHashTable. + */ +template +class OrderedHashTable { + public: + using Key = typename Ops::KeyType; + using Lookup = typename Ops::Lookup; + + struct Data { + T element; + Data* chain; + + Data(const T& e, Data* c) : element(e), chain(c) {} + Data(T&& e, Data* c) : element(std::move(e)), chain(c) {} + }; + + class Range; + friend class Range; + + private: + Data** hashTable; // hash table (has hashBuckets() elements) + Data* data; // data vector, an array of Data objects + // data[0:dataLength] are constructed + uint32_t dataLength; // number of constructed elements in data + uint32_t dataCapacity; // size of data, in elements + uint32_t liveCount; // dataLength less empty (removed) entries + uint32_t hashShift; // multiplicative hash shift + Range* ranges; // list of all live Ranges on this table in malloc memory + Range* + nurseryRanges; // list of all live Ranges on this table in the GC nursery + AllocPolicy alloc; + mozilla::HashCodeScrambler hcs; // don't reveal pointer hash codes + + // TODO: This should be templated on a functor type and receive lambda + // arguments but this causes problems for the hazard analysis builds. See + // bug 1398213. + template + void forEachRange(uint32_t arg = 0) { + Range* next; + for (Range* r = ranges; r; r = next) { + next = r->next; + f(r, arg); + } + for (Range* r = nurseryRanges; r; r = next) { + next = r->next; + f(r, arg); + } + } + + public: + OrderedHashTable(AllocPolicy ap, mozilla::HashCodeScrambler hcs) + : hashTable(nullptr), + data(nullptr), + dataLength(0), + dataCapacity(0), + liveCount(0), + hashShift(0), + ranges(nullptr), + nurseryRanges(nullptr), + alloc(std::move(ap)), + hcs(hcs) {} + + MOZ_MUST_USE bool init() { + MOZ_ASSERT(!hashTable, "init must be called at most once"); + + uint32_t buckets = initialBuckets(); + Data** tableAlloc = alloc.template pod_malloc(buckets); + if (!tableAlloc) { + return false; + } + for (uint32_t i = 0; i < buckets; i++) { + tableAlloc[i] = nullptr; + } + + uint32_t capacity = uint32_t(buckets * fillFactor()); + Data* dataAlloc = alloc.template pod_malloc(capacity); + if (!dataAlloc) { + alloc.free_(tableAlloc, buckets); + return false; + } + + // clear() requires that members are assigned only after all allocation + // has succeeded, and that this->ranges is left untouched. + hashTable = tableAlloc; + data = dataAlloc; + dataLength = 0; + dataCapacity = capacity; + liveCount = 0; + hashShift = js::kHashNumberBits - initialBucketsLog2(); + MOZ_ASSERT(hashBuckets() == buckets); + return true; + } + + ~OrderedHashTable() { + forEachRange(); + if (hashTable) { + // |hashBuckets()| isn't valid when |hashTable| hasn't been created. + alloc.free_(hashTable, hashBuckets()); + } + freeData(data, dataLength, dataCapacity); + } + + /* Return the number of elements in the table. */ + uint32_t count() const { return liveCount; } + + /* True if any element matches l. */ + bool has(const Lookup& l) const { return lookup(l) != nullptr; } + + /* Return a pointer to the element, if any, that matches l, or nullptr. */ + T* get(const Lookup& l) { + Data* e = lookup(l, prepareHash(l)); + return e ? &e->element : nullptr; + } + + /* Return a pointer to the element, if any, that matches l, or nullptr. */ + const T* get(const Lookup& l) const { + return const_cast(this)->get(l); + } + + /* + * If the table already contains an entry that matches |element|, + * replace that entry with |element|. Otherwise add a new entry. + * + * On success, return true, whether there was already a matching element or + * not. On allocation failure, return false. If this returns false, it + * means the element was not added to the table. + */ + template + MOZ_MUST_USE bool put(ElementInput&& element) { + HashNumber h = prepareHash(Ops::getKey(element)); + if (Data* e = lookup(Ops::getKey(element), h)) { + e->element = std::forward(element); + return true; + } + + if (dataLength == dataCapacity) { + // If the hashTable is more than 1/4 deleted data, simply rehash in + // place to free up some space. Otherwise, grow the table. + uint32_t newHashShift = + liveCount >= dataCapacity * 0.75 ? hashShift - 1 : hashShift; + if (!rehash(newHashShift)) { + return false; + } + } + + h >>= hashShift; + liveCount++; + Data* e = &data[dataLength++]; + new (e) Data(std::forward(element), hashTable[h]); + hashTable[h] = e; + return true; + } + + /* + * If the table contains an element matching l, remove it and set *foundp + * to true. Otherwise set *foundp to false. + * + * Return true on success, false if we tried to shrink the table and hit an + * allocation failure. Even if this returns false, *foundp is set correctly + * and the matching element was removed. Shrinking is an optimization and + * it's OK for it to fail. + */ + bool remove(const Lookup& l, bool* foundp) { + // Note: This could be optimized so that removing the last entry, + // data[dataLength - 1], decrements dataLength. LIFO use cases would + // benefit. + + // If a matching entry exists, empty it. + Data* e = lookup(l, prepareHash(l)); + if (e == nullptr) { + *foundp = false; + return true; + } + + *foundp = true; + liveCount--; + Ops::makeEmpty(&e->element); + + // Update active Ranges. + uint32_t pos = e - data; + forEachRange<&Range::onRemove>(pos); + + // If many entries have been removed, try to shrink the table. + if (hashBuckets() > initialBuckets() && + liveCount < dataLength * minDataFill()) { + if (!rehash(hashShift + 1)) { + return false; + } + } + return true; + } + + /* + * Remove all entries. + * + * Returns false on OOM, leaving the OrderedHashTable and any live Ranges + * in the old state. + * + * The effect on live Ranges is the same as removing all entries; in + * particular, those Ranges are still live and will see any entries added + * after a successful clear(). + */ + MOZ_MUST_USE bool clear() { + if (dataLength != 0) { + Data** oldHashTable = hashTable; + Data* oldData = data; + uint32_t oldHashBuckets = hashBuckets(); + uint32_t oldDataLength = dataLength; + uint32_t oldDataCapacity = dataCapacity; + + hashTable = nullptr; + if (!init()) { + // init() only mutates members on success; see comment above. + hashTable = oldHashTable; + return false; + } + + alloc.free_(oldHashTable, oldHashBuckets); + freeData(oldData, oldDataLength, oldDataCapacity); + forEachRange<&Range::onClear>(); + } + + MOZ_ASSERT(hashTable); + MOZ_ASSERT(data); + MOZ_ASSERT(dataLength == 0); + MOZ_ASSERT(liveCount == 0); + return true; + } + + /* + * Ranges are used to iterate over OrderedHashTables. + * + * Suppose 'Map' is some instance of OrderedHashMap, and 'map' is a Map. + * Then you can walk all the key-value pairs like this: + * + * for (Map::Range r = map.all(); !r.empty(); r.popFront()) { + * Map::Entry& pair = r.front(); + * ... do something with pair ... + * } + * + * Ranges remain valid for the lifetime of the OrderedHashTable, even if + * entries are added or removed or the table is resized. Don't do anything + * to a Range, except destroy it, after the OrderedHashTable has been + * destroyed. (We support destroying the two objects in either order to + * humor the GC, bless its nondeterministic heart.) + * + * Warning: The behavior when the current front() entry is removed from the + * table is subtly different from js::HashTable<>::Enum::removeFront()! + * HashTable::Enum doesn't skip any entries when you removeFront() and then + * popFront(). OrderedHashTable::Range does! (This is useful for using a + * Range to implement JS Map.prototype.iterator.) + * + * The workaround is to call popFront() as soon as possible, + * before there's any possibility of modifying the table: + * + * for (Map::Range r = map.all(); !r.empty(); ) { + * Key key = r.front().key; // this won't modify map + * Value val = r.front().value; // this won't modify map + * r.popFront(); + * // ...do things that might modify map... + * } + */ + class Range { + friend class OrderedHashTable; + + // Cannot be a reference since we need to be able to do + // |offsetof(Range, ht)|. + OrderedHashTable* ht; + + /* The index of front() within ht->data. */ + uint32_t i; + + /* + * The number of nonempty entries in ht->data to the left of front(). + * This is used when the table is resized or compacted. + */ + uint32_t count; + + /* + * Links in the doubly-linked list of active Ranges on ht. + * + * prevp points to the previous Range's .next field; + * or to ht->ranges if this is the first Range in the list. + * next points to the next Range; + * or nullptr if this is the last Range in the list. + * + * Invariant: *prevp == this. + */ + Range** prevp; + Range* next; + + /* + * Create a Range over all the entries in ht. + * (This is private on purpose. End users must use ht->all().) + */ + Range(OrderedHashTable* ht, Range** listp) + : ht(ht), i(0), count(0), prevp(listp), next(*listp) { + *prevp = this; + if (next) { + next->prevp = &next; + } + seek(); + } + + public: + Range(const Range& other) + : ht(other.ht), + i(other.i), + count(other.count), + prevp(&ht->ranges), + next(ht->ranges) { + *prevp = this; + if (next) { + next->prevp = &next; + } + } + + ~Range() { + *prevp = next; + if (next) { + next->prevp = prevp; + } + } + + private: + // Prohibit copy assignment. + Range& operator=(const Range& other) = delete; + + void seek() { + while (i < ht->dataLength && + Ops::isEmpty(Ops::getKey(ht->data[i].element))) { + i++; + } + } + + /* + * The hash table calls this when an entry is removed. + * j is the index of the removed entry. + */ + void onRemove(uint32_t j) { + MOZ_ASSERT(valid()); + if (j < i) { + count--; + } + if (j == i) { + seek(); + } + } + + /* + * The hash table calls this when the table is resized or compacted. + * Since |count| is the number of nonempty entries to the left of + * front(), discarding the empty entries will not affect count, and it + * will make i and count equal. + */ + void onCompact() { + MOZ_ASSERT(valid()); + i = count; + } + + /* The hash table calls this when cleared. */ + void onClear() { + MOZ_ASSERT(valid()); + i = count = 0; + } + + bool valid() const { return next != this; } + + void onTableDestroyed() { + MOZ_ASSERT(valid()); + prevp = &next; + next = this; + } + + public: + bool empty() const { + MOZ_ASSERT(valid()); + return i >= ht->dataLength; + } + + /* + * Return the first element in the range. This must not be called if + * this->empty(). + * + * Warning: Removing an entry from the table also removes it from any + * live Ranges, and a Range can become empty that way, rendering + * front() invalid. If in doubt, check empty() before calling front(). + */ + T& front() { + MOZ_ASSERT(valid()); + MOZ_ASSERT(!empty()); + return ht->data[i].element; + } + + /* + * Remove the first element from this range. + * This must not be called if this->empty(). + * + * Warning: Removing an entry from the table also removes it from any + * live Ranges, and a Range can become empty that way, rendering + * popFront() invalid. If in doubt, check empty() before calling + * popFront(). + */ + void popFront() { + MOZ_ASSERT(valid()); + MOZ_ASSERT(!empty()); + MOZ_ASSERT(!Ops::isEmpty(Ops::getKey(ht->data[i].element))); + count++; + i++; + seek(); + } + + /* + * Change the key of the front entry. + * + * This calls Ops::hash on both the current key and the new key. + * Ops::hash on the current key must return the same hash code as + * when the entry was added to the table. + */ + void rekeyFront(const Key& k) { + MOZ_ASSERT(valid()); + Data& entry = ht->data[i]; + HashNumber oldHash = + ht->prepareHash(Ops::getKey(entry.element)) >> ht->hashShift; + HashNumber newHash = ht->prepareHash(k) >> ht->hashShift; + Ops::setKey(entry.element, k); + if (newHash != oldHash) { + // Remove this entry from its old hash chain. (If this crashes + // reading nullptr, it would mean we did not find this entry on + // the hash chain where we expected it. That probably means the + // key's hash code changed since it was inserted, breaking the + // hash code invariant.) + Data** ep = &ht->hashTable[oldHash]; + while (*ep != &entry) { + ep = &(*ep)->chain; + } + *ep = entry.chain; + + // Add it to the new hash chain. We could just insert it at the + // beginning of the chain. Instead, we do a bit of work to + // preserve the invariant that hash chains always go in reverse + // insertion order (descending memory order). No code currently + // depends on this invariant, so it's fine to kill it if + // needed. + ep = &ht->hashTable[newHash]; + while (*ep && *ep > &entry) { + ep = &(*ep)->chain; + } + entry.chain = *ep; + *ep = &entry; + } + } + + static size_t offsetOfHashTable() { return offsetof(Range, ht); } + static size_t offsetOfI() { return offsetof(Range, i); } + static size_t offsetOfCount() { return offsetof(Range, count); } + static size_t offsetOfPrevP() { return offsetof(Range, prevp); } + static size_t offsetOfNext() { return offsetof(Range, next); } + + static void onTableDestroyed(Range* range, uint32_t arg) { + range->onTableDestroyed(); + } + static void onRemove(Range* range, uint32_t arg) { range->onRemove(arg); } + static void onClear(Range* range, uint32_t arg) { range->onClear(); } + static void onCompact(Range* range, uint32_t arg) { range->onCompact(); } + }; + + Range all() { return Range(this, &ranges); } + + /* + * Allocate a new Range, possibly in nursery memory. The buffer must be + * large enough to hold a Range object. + * + * All nursery-allocated ranges can be freed in one go by calling + * destroyNurseryRanges(). + */ + Range* createRange(void* buffer, bool inNursery) { + auto range = static_cast(buffer); + new (range) Range(this, inNursery ? &nurseryRanges : &ranges); + return range; + } + + void destroyNurseryRanges() { nurseryRanges = nullptr; } + + /* + * Change the value of the given key. + * + * This calls Ops::hash on both the current key and the new key. + * Ops::hash on the current key must return the same hash code as + * when the entry was added to the table. + */ + void rekeyOneEntry(const Key& current, const Key& newKey, const T& element) { + if (current == newKey) { + return; + } + + Data* entry = lookup(current, prepareHash(current)); + if (!entry) { + return; + } + + HashNumber oldHash = prepareHash(current) >> hashShift; + HashNumber newHash = prepareHash(newKey) >> hashShift; + + entry->element = element; + + // Remove this entry from its old hash chain. (If this crashes + // reading nullptr, it would mean we did not find this entry on + // the hash chain where we expected it. That probably means the + // key's hash code changed since it was inserted, breaking the + // hash code invariant.) + Data** ep = &hashTable[oldHash]; + while (*ep != entry) { + ep = &(*ep)->chain; + } + *ep = entry->chain; + + // Add it to the new hash chain. We could just insert it at the + // beginning of the chain. Instead, we do a bit of work to + // preserve the invariant that hash chains always go in reverse + // insertion order (descending memory order). No code currently + // depends on this invariant, so it's fine to kill it if + // needed. + ep = &hashTable[newHash]; + while (*ep && *ep > entry) { + ep = &(*ep)->chain; + } + entry->chain = *ep; + *ep = entry; + } + + static size_t offsetOfDataLength() { + return offsetof(OrderedHashTable, dataLength); + } + static size_t offsetOfData() { return offsetof(OrderedHashTable, data); } + static constexpr size_t offsetOfDataElement() { + static_assert(offsetof(Data, element) == 0, + "RangeFront and RangePopFront depend on offsetof(Data, " + "element) being 0"); + return offsetof(Data, element); + } + static constexpr size_t sizeofData() { return sizeof(Data); } + + private: + /* Logarithm base 2 of the number of buckets in the hash table initially. */ + static uint32_t initialBucketsLog2() { return 1; } + static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); } + + /* + * The maximum load factor (mean number of entries per bucket). + * It is an invariant that + * dataCapacity == floor(hashBuckets() * fillFactor()). + * + * The fill factor should be between 2 and 4, and it should be chosen so that + * the fill factor times sizeof(Data) is close to but <= a power of 2. + * This fixed fill factor was chosen to make the size of the data + * array, in bytes, close to a power of two when sizeof(T) is 16. + */ + static double fillFactor() { return 8.0 / 3.0; } + + /* + * The minimum permitted value of (liveCount / dataLength). + * If that ratio drops below this value, we shrink the table. + */ + static double minDataFill() { return 0.25; } + + public: + HashNumber prepareHash(const Lookup& l) const { + return mozilla::ScrambleHashCode(Ops::hash(l, hcs)); + } + + private: + /* The size of hashTable, in elements. Always a power of two. */ + uint32_t hashBuckets() const { + return 1 << (js::kHashNumberBits - hashShift); + } + + static void destroyData(Data* data, uint32_t length) { + for (Data* p = data + length; p != data;) { + (--p)->~Data(); + } + } + + void freeData(Data* data, uint32_t length, uint32_t capacity) { + destroyData(data, length); + alloc.free_(data, capacity); + } + + Data* lookup(const Lookup& l, HashNumber h) { + for (Data* e = hashTable[h >> hashShift]; e; e = e->chain) { + if (Ops::match(Ops::getKey(e->element), l)) { + return e; + } + } + return nullptr; + } + + const Data* lookup(const Lookup& l) const { + return const_cast(this)->lookup(l, prepareHash(l)); + } + + /* This is called after rehashing the table. */ + void compacted() { + // If we had any empty entries, compacting may have moved live entries + // to the left within |data|. Notify all live Ranges of the change. + forEachRange<&Range::onCompact>(); + } + + /* Compact the entries in |data| and rehash them. */ + void rehashInPlace() { + for (uint32_t i = 0, N = hashBuckets(); i < N; i++) { + hashTable[i] = nullptr; + } + Data* wp = data; + Data* end = data + dataLength; + for (Data* rp = data; rp != end; rp++) { + if (!Ops::isEmpty(Ops::getKey(rp->element))) { + HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift; + if (rp != wp) { + wp->element = std::move(rp->element); + } + wp->chain = hashTable[h]; + hashTable[h] = wp; + wp++; + } + } + MOZ_ASSERT(wp == data + liveCount); + + while (wp != end) { + (--end)->~Data(); + } + dataLength = liveCount; + compacted(); + } + + /* + * Grow, shrink, or compact both |hashTable| and |data|. + * + * On success, this returns true, dataLength == liveCount, and there are no + * empty elements in data[0:dataLength]. On allocation failure, this + * leaves everything as it was and returns false. + */ + MOZ_MUST_USE bool rehash(uint32_t newHashShift) { + // If the size of the table is not changing, rehash in place to avoid + // allocating memory. + if (newHashShift == hashShift) { + rehashInPlace(); + return true; + } + + size_t newHashBuckets = size_t(1) << (js::kHashNumberBits - newHashShift); + Data** newHashTable = alloc.template pod_malloc(newHashBuckets); + if (!newHashTable) { + return false; + } + for (uint32_t i = 0; i < newHashBuckets; i++) { + newHashTable[i] = nullptr; + } + + uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor()); + Data* newData = alloc.template pod_malloc(newCapacity); + if (!newData) { + alloc.free_(newHashTable, newHashBuckets); + return false; + } + + Data* wp = newData; + Data* end = data + dataLength; + for (Data* p = data; p != end; p++) { + if (!Ops::isEmpty(Ops::getKey(p->element))) { + HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift; + new (wp) Data(std::move(p->element), newHashTable[h]); + newHashTable[h] = wp; + wp++; + } + } + MOZ_ASSERT(wp == newData + liveCount); + + alloc.free_(hashTable, hashBuckets()); + freeData(data, dataLength, dataCapacity); + + hashTable = newHashTable; + data = newData; + dataLength = liveCount; + dataCapacity = newCapacity; + hashShift = newHashShift; + MOZ_ASSERT(hashBuckets() == newHashBuckets); + + compacted(); + return true; + } + + // Not copyable. + OrderedHashTable& operator=(const OrderedHashTable&) = delete; + OrderedHashTable(const OrderedHashTable&) = delete; +}; + +} // namespace detail + +template +class OrderedHashMap { + public: + class Entry { + template + friend class detail::OrderedHashTable; + void operator=(const Entry& rhs) { + const_cast(key) = rhs.key; + value = rhs.value; + } + + void operator=(Entry&& rhs) { + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); + const_cast(key) = std::move(rhs.key); + value = std::move(rhs.value); + } + + public: + Entry() : key(), value() {} + template + Entry(const Key& k, V&& v) : key(k), value(std::forward(v)) {} + Entry(Entry&& rhs) : key(std::move(rhs.key)), value(std::move(rhs.value)) {} + + const Key key; + Value value; + + static size_t offsetOfKey() { return offsetof(Entry, key); } + static size_t offsetOfValue() { return offsetof(Entry, value); } + }; + + private: + struct MapOps : OrderedHashPolicy { + using KeyType = Key; + static void makeEmpty(Entry* e) { + OrderedHashPolicy::makeEmpty(const_cast(&e->key)); + + // Clear the value. Destroying it is another possibility, but that + // would complicate class Entry considerably. + e->value = Value(); + } + static const Key& getKey(const Entry& e) { return e.key; } + static void setKey(Entry& e, const Key& k) { const_cast(e.key) = k; } + }; + + typedef detail::OrderedHashTable Impl; + Impl impl; + + public: + using Range = typename Impl::Range; + + OrderedHashMap(AllocPolicy ap, mozilla::HashCodeScrambler hcs) + : impl(std::move(ap), hcs) {} + MOZ_MUST_USE bool init() { return impl.init(); } + uint32_t count() const { return impl.count(); } + bool has(const Key& key) const { return impl.has(key); } + Range all() { return impl.all(); } + const Entry* get(const Key& key) const { return impl.get(key); } + Entry* get(const Key& key) { return impl.get(key); } + bool remove(const Key& key, bool* foundp) { return impl.remove(key, foundp); } + MOZ_MUST_USE bool clear() { return impl.clear(); } + + template + MOZ_MUST_USE bool put(const Key& key, V&& value) { + return impl.put(Entry(key, std::forward(value))); + } + + HashNumber hash(const Key& key) const { return impl.prepareHash(key); } + + void rekeyOneEntry(const Key& current, const Key& newKey) { + const Entry* e = get(current); + if (!e) { + return; + } + return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value)); + } + + Range* createRange(void* buffer, bool inNursery) { + return impl.createRange(buffer, inNursery); + } + + void destroyNurseryRanges() { impl.destroyNurseryRanges(); } + + static size_t offsetOfEntryKey() { return Entry::offsetOfKey(); } + static size_t offsetOfImplDataLength() { return Impl::offsetOfDataLength(); } + static size_t offsetOfImplData() { return Impl::offsetOfData(); } + static constexpr size_t offsetOfImplDataElement() { + return Impl::offsetOfDataElement(); + } + static constexpr size_t sizeofImplData() { return Impl::sizeofData(); } +}; + +template +class OrderedHashSet { + private: + struct SetOps : OrderedHashPolicy { + using KeyType = const T; + static const T& getKey(const T& v) { return v; } + static void setKey(const T& e, const T& v) { const_cast(e) = v; } + }; + + typedef detail::OrderedHashTable Impl; + Impl impl; + + public: + using Range = typename Impl::Range; + + explicit OrderedHashSet(AllocPolicy ap, mozilla::HashCodeScrambler hcs) + : impl(std::move(ap), hcs) {} + MOZ_MUST_USE bool init() { return impl.init(); } + uint32_t count() const { return impl.count(); } + bool has(const T& value) const { return impl.has(value); } + Range all() { return impl.all(); } + MOZ_MUST_USE bool put(const T& value) { return impl.put(value); } + bool remove(const T& value, bool* foundp) { + return impl.remove(value, foundp); + } + MOZ_MUST_USE bool clear() { return impl.clear(); } + + HashNumber hash(const T& value) const { return impl.prepareHash(value); } + + void rekeyOneEntry(const T& current, const T& newKey) { + return impl.rekeyOneEntry(current, newKey, newKey); + } + + Range* createRange(void* buffer, bool inNursery) { + return impl.createRange(buffer, inNursery); + } + + void destroyNurseryRanges() { impl.destroyNurseryRanges(); } + + static size_t offsetOfEntryKey() { return 0; } + static size_t offsetOfImplDataLength() { return Impl::offsetOfDataLength(); } + static size_t offsetOfImplData() { return Impl::offsetOfData(); } + static constexpr size_t offsetOfImplDataElement() { + return Impl::offsetOfDataElement(); + } + static constexpr size_t sizeofImplData() { return Impl::sizeofData(); } +}; + +} // namespace js + +#endif /* ds_OrderedHashTable_h */ diff --git a/js/src/ds/PageProtectingVector.h b/js/src/ds/PageProtectingVector.h new file mode 100644 index 0000000000..f7c4911db2 --- /dev/null +++ b/js/src/ds/PageProtectingVector.h @@ -0,0 +1,502 @@ +/* -*- 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_PageProtectingVector_h +#define ds_PageProtectingVector_h + +#include "mozilla/Atomics.h" +#include "mozilla/IntegerPrintfMacros.h" +#include "mozilla/PodOperations.h" +#include "mozilla/Types.h" +#include "mozilla/Vector.h" + +#include "ds/MemoryProtectionExceptionHandler.h" +#include "gc/Memory.h" + +namespace js { + +/* + * PageProtectingVector is a vector that can only grow or be cleared, restricts + * access to memory pages that haven't been used yet, and marks all of its fully + * used memory pages as read-only. It can be used to detect heap corruption in + * important buffers, since anything that tries to write into its protected + * pages will crash. On Nightly and Aurora, these crashes will additionally be + * annotated with a moz crash reason using MemoryProtectionExceptionHandler. + * + * PageProtectingVector's protection is limited to full pages. If the front + * of its buffer is not aligned on a page boundary, elems preceding the first + * page boundary will not be protected. Similarly, the end of the buffer will + * not be fully protected unless it is aligned on a page boundary. Altogether, + * up to two pages of memory may not be protected. + */ +template +class PageProtectingVector final { + mozilla::Vector vector; + + static constexpr size_t toShift(size_t v) { + return v <= 1 ? 0 : 1 + toShift(v >> 1); + } + + static_assert( + (sizeof(T) & (sizeof(T) - 1)) == 0, + "For performance reasons, " + "PageProtectingVector only works with power-of-2 sized elements!"); + + static const size_t elemShift = toShift(sizeof(T)); + static const size_t elemSize = 1 << elemShift; + static const size_t elemMask = elemSize - 1; + + /* We hardcode the page size here to minimize administrative overhead. */ + static const size_t pageShift = 12; + static const size_t pageSize = 1 << pageShift; + static const size_t pageMask = pageSize - 1; + + /* + * The number of elements that can be added before we need to either adjust + * the active page or resize the buffer. If |elemsUntilTest < 0| we will + * take the slow paths in the append calls. + */ + intptr_t elemsUntilTest; + + /* + * The offset of the currently 'active' page - that is, the page that is + * currently being written to. If both used and unused bytes are protected, + * this will be the only (fully owned) page with read and write access. + */ + size_t currPage; + + /* + * The first fully owned page. This is the first page that can + * be protected, but it may not be the first *active* page. + */ + size_t initPage; + + /* + * The last fully owned page. This is the last page that can + * be protected, but it may not be the last *active* page. + */ + size_t lastPage; + + /* + * The size in elems that a buffer needs to be before its pages will be + * protected. This is intended to reduce churn for small vectors while + * still offering protection when they grow large enough. + */ + size_t lowerBound; + +#ifdef DEBUG + bool regionUnprotected; +#endif + + bool usable; + bool enabled; + bool protectUsedEnabled; + bool protectUnusedEnabled; + + MOZ_ALWAYS_INLINE void resetTest() { + MOZ_ASSERT(protectUsedEnabled || protectUnusedEnabled); + size_t nextPage = + (pageSize - (uintptr_t(begin() + length()) & pageMask)) >> elemShift; + size_t nextResize = capacity() - length(); + if (MOZ_LIKELY(nextPage <= nextResize)) { + elemsUntilTest = intptr_t(nextPage); + } else { + elemsUntilTest = intptr_t(nextResize); + } + } + + MOZ_ALWAYS_INLINE void setTestInitial() { + if (MOZ_LIKELY(!protectUsedEnabled && !protectUnusedEnabled)) { + elemsUntilTest = intptr_t(capacity() - length()); + } else { + resetTest(); + } + } + + MOZ_ALWAYS_INLINE void resetForNewBuffer() { + initPage = (uintptr_t(begin() - 1) >> pageShift) + 1; + currPage = (uintptr_t(begin() + length()) >> pageShift); + lastPage = (uintptr_t(begin() + capacity()) >> pageShift) - 1; + protectUsedEnabled = + ProtectUsed && usable && enabled && initPage <= lastPage && + (uintptr_t(begin()) & elemMask) == 0 && capacity() >= lowerBound; + protectUnusedEnabled = + ProtectUnused && usable && enabled && initPage <= lastPage && + (uintptr_t(begin()) & elemMask) == 0 && capacity() >= lowerBound; + setTestInitial(); + } + + MOZ_ALWAYS_INLINE void poisonNewBuffer() { + if (!PoisonUnused) { + return; + } + T* addr = begin() + length(); + size_t toPoison = (capacity() - length()) * sizeof(T); + memset(addr, PoisonPattern, toPoison); + } + + MOZ_ALWAYS_INLINE void addExceptionHandler() { + if (MOZ_UNLIKELY(protectUsedEnabled || protectUnusedEnabled)) { + MemoryProtectionExceptionHandler::addRegion(begin(), capacity() + << elemShift); + } + } + + MOZ_ALWAYS_INLINE void removeExceptionHandler() { + if (MOZ_UNLIKELY(protectUsedEnabled || protectUnusedEnabled)) { + MemoryProtectionExceptionHandler::removeRegion(begin()); + } + } + + MOZ_ALWAYS_INLINE void protectUsed() { + if (MOZ_LIKELY(!protectUsedEnabled)) { + return; + } + if (MOZ_UNLIKELY(currPage <= initPage)) { + return; + } + T* addr = reinterpret_cast(initPage << pageShift); + size_t size = (currPage - initPage) << pageShift; + gc::MakePagesReadOnly(addr, size); + } + + MOZ_ALWAYS_INLINE void unprotectUsed() { + if (MOZ_LIKELY(!protectUsedEnabled)) { + return; + } + if (MOZ_UNLIKELY(currPage <= initPage)) { + return; + } + T* addr = reinterpret_cast(initPage << pageShift); + size_t size = (currPage - initPage) << pageShift; + gc::UnprotectPages(addr, size); + } + + MOZ_ALWAYS_INLINE void protectUnused() { + if (MOZ_LIKELY(!protectUnusedEnabled)) { + return; + } + if (MOZ_UNLIKELY(currPage >= lastPage)) { + return; + } + T* addr = reinterpret_cast((currPage + 1) << pageShift); + size_t size = (lastPage - currPage) << pageShift; + gc::ProtectPages(addr, size); + } + + MOZ_ALWAYS_INLINE void unprotectUnused() { + if (MOZ_LIKELY(!protectUnusedEnabled)) { + return; + } + if (MOZ_UNLIKELY(currPage >= lastPage)) { + return; + } + T* addr = reinterpret_cast((currPage + 1) << pageShift); + size_t size = (lastPage - currPage) << pageShift; + gc::UnprotectPages(addr, size); + } + + MOZ_ALWAYS_INLINE void protectNewBuffer() { + resetForNewBuffer(); + addExceptionHandler(); + poisonNewBuffer(); + protectUsed(); + protectUnused(); + } + + MOZ_ALWAYS_INLINE void unprotectOldBuffer() { + MOZ_ASSERT(!regionUnprotected); + unprotectUnused(); + unprotectUsed(); + removeExceptionHandler(); + } + + MOZ_ALWAYS_INLINE void protectUnusedPartial(size_t curr, size_t next) { + if (MOZ_LIKELY(!protectUnusedEnabled)) { + return; + } + if (MOZ_UNLIKELY(next > lastPage)) { + --next; + } + if (MOZ_UNLIKELY(next == curr)) { + return; + } + void* addr = reinterpret_cast((curr + 1) << pageShift); + size_t size = (next - curr) << pageShift; + gc::ProtectPages(addr, size); + } + + MOZ_ALWAYS_INLINE void unprotectUnusedPartial(size_t curr, size_t next) { + if (MOZ_LIKELY(!protectUnusedEnabled)) { + return; + } + if (MOZ_UNLIKELY(next > lastPage)) { + --next; + } + if (MOZ_UNLIKELY(next == curr)) { + return; + } + void* addr = reinterpret_cast((curr + 1) << pageShift); + size_t size = (next - curr) << pageShift; + gc::UnprotectPages(addr, size); + } + + MOZ_ALWAYS_INLINE void protectUsedPartial(size_t curr, size_t next) { + if (MOZ_LIKELY(!protectUsedEnabled)) { + return; + } + if (MOZ_UNLIKELY(curr < initPage)) { + ++curr; + } + if (MOZ_UNLIKELY(next == curr)) { + return; + } + void* addr = reinterpret_cast(curr << pageShift); + size_t size = (next - curr) << pageShift; + gc::MakePagesReadOnly(addr, size); + } + + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool reserveNewBuffer(size_t size) { + unprotectOldBuffer(); + bool ret = vector.reserve(size); + protectNewBuffer(); + return ret; + } + + template + MOZ_ALWAYS_INLINE void infallibleAppendNewPage(const U* values, size_t size) { + size_t nextPage = uintptr_t(begin() + length() + size) >> pageShift; + MOZ_ASSERT(currPage < nextPage); + unprotectUnusedPartial(currPage, nextPage); + vector.infallibleAppend(values, size); + protectUsedPartial(currPage, nextPage); + currPage = nextPage; + resetTest(); + } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool appendNewPage(const U* values, + size_t size) { + size_t nextPage = uintptr_t(begin() + length() + size) >> pageShift; + MOZ_ASSERT(currPage < nextPage); + unprotectUnusedPartial(currPage, nextPage); + bool ret = vector.append(values, size); + if (MOZ_LIKELY(ret)) { + protectUsedPartial(currPage, nextPage); + currPage = nextPage; + } else { + protectUnusedPartial(currPage, nextPage); + } + resetTest(); + return ret; + } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool appendNewBuffer(const U* values, + size_t size) { + unprotectOldBuffer(); + bool ret = vector.append(values, size); + protectNewBuffer(); + return ret; + } + + MOZ_NEVER_INLINE void unprotectRegionSlow(uintptr_t l, uintptr_t r); + MOZ_NEVER_INLINE void reprotectRegionSlow(uintptr_t l, uintptr_t r); + + MOZ_NEVER_INLINE MOZ_MUST_USE bool reserveSlow(size_t size); + + template + MOZ_NEVER_INLINE void infallibleAppendSlow(const U* values, size_t size); + + template + MOZ_NEVER_INLINE MOZ_MUST_USE bool appendSlow(const U* values, size_t size); + + public: + explicit PageProtectingVector(AllocPolicy policy = AllocPolicy()) + : vector(std::move(policy)), + elemsUntilTest(0), + currPage(0), + initPage(0), + lastPage(0), + lowerBound(InitialLowerBound), +#ifdef DEBUG + regionUnprotected(false), +#endif + usable(true), + enabled(true), + protectUsedEnabled(false), + protectUnusedEnabled(false) { + if (gc::SystemPageSize() != pageSize) { + usable = false; + } + protectNewBuffer(); + } + + ~PageProtectingVector() { unprotectOldBuffer(); } + + void disableProtection() { + MOZ_ASSERT(enabled); + unprotectOldBuffer(); + enabled = false; + resetForNewBuffer(); + } + + void enableProtection() { + MOZ_ASSERT(!enabled); + enabled = true; + protectNewBuffer(); + } + + /* + * Sets the lower bound on the size, in elems, that this vector's underlying + * capacity has to be before its used pages will be protected. + */ + void setLowerBoundForProtection(size_t elems) { + if (lowerBound != elems) { + unprotectOldBuffer(); + lowerBound = elems; + protectNewBuffer(); + } + } + + /* Disable protection on the smallest containing region. */ + MOZ_ALWAYS_INLINE void unprotectRegion(T* first, size_t size) { +#ifdef DEBUG + regionUnprotected = true; +#endif + if (MOZ_UNLIKELY(protectUsedEnabled)) { + uintptr_t l = uintptr_t(first) >> pageShift; + uintptr_t r = uintptr_t(first + size - 1) >> pageShift; + if (r >= initPage && l < currPage) { + unprotectRegionSlow(l, r); + } + } + } + + /* Re-enable protection on the smallest containing region. */ + MOZ_ALWAYS_INLINE void reprotectRegion(T* first, size_t size) { +#ifdef DEBUG + regionUnprotected = false; +#endif + if (MOZ_UNLIKELY(protectUsedEnabled)) { + uintptr_t l = uintptr_t(first) >> pageShift; + uintptr_t r = uintptr_t(first + size - 1) >> pageShift; + if (r >= initPage && l < currPage) { + reprotectRegionSlow(l, r); + } + } + } + + MOZ_ALWAYS_INLINE size_t capacity() const { return vector.capacity(); } + MOZ_ALWAYS_INLINE size_t length() const { return vector.length(); } + + MOZ_ALWAYS_INLINE T* begin() { return vector.begin(); } + MOZ_ALWAYS_INLINE const T* begin() const { return vector.begin(); } + + void clear() { + unprotectOldBuffer(); + vector.clear(); + protectNewBuffer(); + } + + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool reserve(size_t size) { + if (MOZ_LIKELY(size <= capacity())) { + return vector.reserve(size); + } + return reserveSlow(size); + } + + template + MOZ_ALWAYS_INLINE void infallibleAppend(const U* values, size_t size) { + elemsUntilTest -= size; + if (MOZ_LIKELY(elemsUntilTest >= 0)) { + return vector.infallibleAppend(values, size); + } + infallibleAppendSlow(values, size); + } + + template + MOZ_ALWAYS_INLINE MOZ_MUST_USE bool append(const U* values, size_t size) { + elemsUntilTest -= size; + if (MOZ_LIKELY(elemsUntilTest >= 0)) { + return vector.append(values, size); + } + return appendSlow(values, size); + } +}; + +template +MOZ_NEVER_INLINE void +PageProtectingVector::unprotectRegionSlow(uintptr_t l, + uintptr_t r) { + if (l < initPage) { + l = initPage; + } + if (r >= currPage) { + r = currPage - 1; + } + T* addr = reinterpret_cast(l << pageShift); + size_t size = (r - l + 1) << pageShift; + gc::UnprotectPages(addr, size); +} + +template +MOZ_NEVER_INLINE void +PageProtectingVector::reprotectRegionSlow(uintptr_t l, + uintptr_t r) { + if (l < initPage) { + l = initPage; + } + if (r >= currPage) { + r = currPage - 1; + } + T* addr = reinterpret_cast(l << pageShift); + size_t size = (r - l + 1) << pageShift; + gc::MakePagesReadOnly(addr, size); +} + +template +MOZ_NEVER_INLINE MOZ_MUST_USE bool +PageProtectingVector::reserveSlow(size_t size) { + return reserveNewBuffer(size); +} + +template +template +MOZ_NEVER_INLINE void +PageProtectingVector::infallibleAppendSlow( + const U* values, size_t size) { + // Ensure that we're here because we reached a page + // boundary and not because of a buffer overflow. + MOZ_RELEASE_ASSERT( + MOZ_LIKELY(length() + size <= capacity()), + "About to overflow our AssemblerBuffer using infallibleAppend!"); + infallibleAppendNewPage(values, size); +} + +template +template +MOZ_NEVER_INLINE MOZ_MUST_USE bool +PageProtectingVector::appendSlow(const U* values, + size_t size) { + if (MOZ_LIKELY(length() + size <= capacity())) { + return appendNewPage(values, size); + } + return appendNewBuffer(values, size); +} + +} /* namespace js */ + +#endif /* ds_PageProtectingVector_h */ diff --git a/js/src/ds/PriorityQueue.h b/js/src/ds/PriorityQueue.h new file mode 100644 index 0000000000..439c2075a4 --- /dev/null +++ b/js/src/ds/PriorityQueue.h @@ -0,0 +1,125 @@ +/* -*- 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_PriorityQueue_h +#define ds_PriorityQueue_h + +#include "js/Vector.h" + +namespace js { + +/* + * Class which represents a heap based priority queue using a vector. + * Inserting elements and removing the highest priority one are both O(log n). + * + * Template parameters are the same as for Vector, with the addition that P + * must have a static priority(const T&) method which returns higher numbers + * for higher priority elements. + */ +template +class PriorityQueue { + Vector heap; + + PriorityQueue(const PriorityQueue&) = delete; + PriorityQueue& operator=(const PriorityQueue&) = delete; + + public: + explicit PriorityQueue(AllocPolicy ap = AllocPolicy()) + : heap(std::move(ap)) {} + + MOZ_MUST_USE bool reserve(size_t capacity) { return heap.reserve(capacity); } + + size_t length() const { return heap.length(); } + + bool empty() const { return heap.empty(); } + + T removeHighest() { + T highest = heap[0]; + T last = heap.popCopy(); + if (!heap.empty()) { + heap[0] = last; + siftDown(0); + } + return highest; + } + + MOZ_MUST_USE bool insert(const T& v) { + if (!heap.append(v)) { + return false; + } + siftUp(heap.length() - 1); + return true; + } + + void infallibleInsert(const T& v) { + heap.infallibleAppend(v); + siftUp(heap.length() - 1); + } + + private: + /* + * Elements of the vector encode a binary tree: + * + * 0 + * 1 2 + * 3 4 5 6 + * + * The children of element N are (2N + 1) and (2N + 2). + * The parent of element N is (N - 1) / 2. + * + * Each element has higher priority than its children. + */ + + void siftDown(size_t n) { + while (true) { + size_t left = n * 2 + 1; + size_t right = n * 2 + 2; + + if (left < heap.length()) { + if (right < heap.length()) { + if (P::priority(heap[n]) < P::priority(heap[right]) && + P::priority(heap[left]) < P::priority(heap[right])) { + swap(n, right); + n = right; + continue; + } + } + + if (P::priority(heap[n]) < P::priority(heap[left])) { + swap(n, left); + n = left; + continue; + } + } + + break; + } + } + + void siftUp(size_t n) { + while (n > 0) { + size_t parent = (n - 1) / 2; + + if (P::priority(heap[parent]) > P::priority(heap[n])) { + break; + } + + swap(n, parent); + n = parent; + } + } + + void swap(size_t a, size_t b) { + T tmp = heap[a]; + heap[a] = heap[b]; + heap[b] = tmp; + } +}; + +} /* namespace js */ + +#endif /* ds_PriorityQueue_h */ diff --git a/js/src/ds/Sort.h b/js/src/ds/Sort.h new file mode 100644 index 0000000000..7841adf7e4 --- /dev/null +++ b/js/src/ds/Sort.h @@ -0,0 +1,146 @@ +/* -*- 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_Sort_h +#define ds_Sort_h + +#include "jstypes.h" + +namespace js { + +namespace detail { + +template +MOZ_ALWAYS_INLINE void CopyNonEmptyArray(T* dst, const T* src, size_t nelems) { + MOZ_ASSERT(nelems != 0); + const T* end = src + nelems; + do { + *dst++ = *src++; + } while (src != end); +} + +/* Helper function for MergeSort. */ +template +MOZ_ALWAYS_INLINE bool MergeArrayRuns(T* dst, const T* src, size_t run1, + size_t run2, Comparator c) { + MOZ_ASSERT(run1 >= 1); + MOZ_ASSERT(run2 >= 1); + + /* Copy runs already in sorted order. */ + const T* b = src + run1; + bool lessOrEqual; + if (!c(b[-1], b[0], &lessOrEqual)) { + return false; + } + + if (!lessOrEqual) { + /* Runs are not already sorted, merge them. */ + for (const T* a = src;;) { + if (!c(*a, *b, &lessOrEqual)) { + return false; + } + if (lessOrEqual) { + *dst++ = *a++; + if (!--run1) { + src = b; + break; + } + } else { + *dst++ = *b++; + if (!--run2) { + src = a; + break; + } + } + } + } + CopyNonEmptyArray(dst, src, run1 + run2); + return true; +} + +} /* namespace detail */ + +/* + * Sort the array using the merge sort algorithm. The scratch should point to + * a temporary storage that can hold nelems elements. + * + * The comparator must provide the () operator with the following signature: + * + * bool operator()(const T& a, const T& a, bool* lessOrEqualp); + * + * It should return true on success and set *lessOrEqualp to the result of + * a <= b operation. If it returns false, the sort terminates immediately with + * the false result. In this case the content of the array and scratch is + * arbitrary. + * + * Note: The merge sort algorithm is a stable sort, preserving relative ordering + * of entries that compare equal. This makes it a useful substitute for + * |std::stable_sort|, which can't be used in SpiderMonkey because it internally + * allocates memory without using SpiderMonkey's allocator. + */ +template +MOZ_MUST_USE bool MergeSort(T* array, size_t nelems, T* scratch, Comparator c) { + const size_t INS_SORT_LIMIT = 3; + + if (nelems <= 1) { + return true; + } + + /* + * Apply insertion sort to small chunks to reduce the number of merge + * passes needed. + */ + for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) { + size_t hi = lo + INS_SORT_LIMIT; + if (hi >= nelems) { + hi = nelems; + } + for (size_t i = lo + 1; i != hi; i++) { + for (size_t j = i;;) { + bool lessOrEqual; + if (!c(array[j - 1], array[j], &lessOrEqual)) { + return false; + } + if (lessOrEqual) { + break; + } + T tmp = array[j - 1]; + array[j - 1] = array[j]; + array[j] = tmp; + if (--j == lo) { + break; + } + } + } + } + + T* vec1 = array; + T* vec2 = scratch; + for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) { + for (size_t lo = 0; lo < nelems; lo += 2 * run) { + size_t hi = lo + run; + if (hi >= nelems) { + detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo); + break; + } + size_t run2 = (run <= nelems - hi) ? run : nelems - hi; + if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c)) { + return false; + } + } + T* swap = vec1; + vec1 = vec2; + vec2 = swap; + } + if (vec1 == scratch) { + detail::CopyNonEmptyArray(array, scratch, nelems); + } + return true; +} + +} /* namespace js */ + +#endif /* ds_Sort_h */ diff --git a/js/src/ds/SplayTree.h b/js/src/ds/SplayTree.h new file mode 100644 index 0000000000..ae4c1ca3d3 --- /dev/null +++ b/js/src/ds/SplayTree.h @@ -0,0 +1,354 @@ +/* -*- 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_SplayTree_h +#define ds_SplayTree_h + +#include "ds/LifoAlloc.h" + +namespace js { + +/* + * Class which represents a splay tree with nodes allocated from a LifoAlloc. + * Splay trees are balanced binary search trees for which search, insert and + * remove are all amortized O(log n). + * + * T indicates the type of tree elements, C must have a static + * compare(const T&, const T&) method ordering the elements. As for LifoAlloc + * objects, T objects stored in the tree will not be explicitly destroyed. + */ +template +class SplayTree { + struct Node { + T item; + Node* left; + Node* right; + Node* parent; + + explicit Node(const T& item) + : item(item), left(nullptr), right(nullptr), parent(nullptr) {} + }; + + LifoAlloc* alloc; + Node* root; + Node* freeList; + +#ifdef DEBUG + bool enableCheckCoherency; +#endif + + SplayTree(const SplayTree&) = delete; + SplayTree& operator=(const SplayTree&) = delete; + + public: + explicit SplayTree(LifoAlloc* alloc = nullptr) + : alloc(alloc), + root(nullptr), + freeList(nullptr) +#ifdef DEBUG + , + enableCheckCoherency(true) +#endif + { + } + + void setAllocator(LifoAlloc* alloc) { this->alloc = alloc; } + + void disableCheckCoherency() { +#ifdef DEBUG + enableCheckCoherency = false; +#endif + } + + bool empty() const { return !root; } + + T* maybeLookup(const T& v) { + if (!root) { + return nullptr; + } + Node* last = lookup(v); + return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr; + } + + bool contains(const T& v, T* res) { + if (!root) { + return false; + } + Node* last = lookup(v); + splay(last); + checkCoherency(); + if (C::compare(v, last->item) == 0) { + *res = last->item; + return true; + } + return false; + } + + MOZ_MUST_USE bool insert(const T& v) { + Node* element = allocateNode(v); + if (!element) { + return false; + } + + if (!root) { + root = element; + return true; + } + Node* last = lookup(v); + int cmp = C::compare(v, last->item); + + // Don't tolerate duplicate elements. + MOZ_DIAGNOSTIC_ASSERT(cmp); + + Node*& parentPointer = (cmp < 0) ? last->left : last->right; + MOZ_ASSERT(!parentPointer); + parentPointer = element; + element->parent = last; + + splay(element); + checkCoherency(); + return true; + } + + void remove(const T& v) { + Node* last = lookup(v); + MOZ_ASSERT(last && C::compare(v, last->item) == 0); + + splay(last); + MOZ_ASSERT(last == root); + + // Find another node which can be swapped in for the root: either the + // rightmost child of the root's left, or the leftmost child of the + // root's right. + Node* swap; + Node* swapChild; + if (root->left) { + swap = root->left; + while (swap->right) { + swap = swap->right; + } + swapChild = swap->left; + } else if (root->right) { + swap = root->right; + while (swap->left) { + swap = swap->left; + } + swapChild = swap->right; + } else { + freeNode(root); + root = nullptr; + return; + } + + // The selected node has at most one child, in swapChild. Detach it + // from the subtree by replacing it with that child. + if (swap == swap->parent->left) { + swap->parent->left = swapChild; + } else { + swap->parent->right = swapChild; + } + if (swapChild) { + swapChild->parent = swap->parent; + } + + root->item = swap->item; + freeNode(swap); + + checkCoherency(); + } + + template + void forEach(Op op) { + forEachInner(op, root); + } + + private: + Node* lookup(const T& v) { + MOZ_ASSERT(root); + Node* node = root; + Node* parent; + do { + parent = node; + int c = C::compare(v, node->item); + if (c == 0) { + return node; + } else if (c < 0) { + node = node->left; + } else { + node = node->right; + } + } while (node); + return parent; + } + + Node* allocateNode(const T& v) { + Node* node = freeList; + if (node) { + freeList = node->left; + new (node) Node(v); + return node; + } + return alloc->new_(v); + } + + void freeNode(Node* node) { + node->left = freeList; + freeList = node; + } + + void splay(Node* node) { + // Rotate the element until it is at the root of the tree. Performing + // the rotations in this fashion preserves the amortized balancing of + // the tree. + MOZ_ASSERT(node); + while (node != root) { + Node* parent = node->parent; + if (parent == root) { + // Zig rotation. + rotate(node); + MOZ_ASSERT(node == root); + return; + } + Node* grandparent = parent->parent; + if ((parent->left == node) == (grandparent->left == parent)) { + // Zig-zig rotation. + rotate(parent); + rotate(node); + } else { + // Zig-zag rotation. + rotate(node); + rotate(node); + } + } + } + + void rotate(Node* node) { + // Rearrange nodes so that node becomes the parent of its current + // parent, while preserving the sortedness of the tree. + Node* parent = node->parent; + if (parent->left == node) { + // x y + // y c ==> a x + // a b b c + parent->left = node->right; + if (node->right) { + node->right->parent = parent; + } + node->right = parent; + } else { + MOZ_ASSERT(parent->right == node); + // x y + // a y ==> x c + // b c a b + parent->right = node->left; + if (node->left) { + node->left->parent = parent; + } + node->left = parent; + } + node->parent = parent->parent; + parent->parent = node; + if (Node* grandparent = node->parent) { + if (grandparent->left == parent) { + grandparent->left = node; + } else { + grandparent->right = node; + } + } else { + root = node; + } + } + + template + void forEachInner(Op op, Node* node) { + if (!node) { + return; + } + + forEachInner(op, node->left); + op(node->item); + forEachInner(op, node->right); + } + + void checkCoherency() const { +#ifdef DEBUG + if (!enableCheckCoherency) { + return; + } + if (!root) { + return; + } + MOZ_ASSERT(root->parent == nullptr); + const Node* node = root; + const Node* minimum = nullptr; + MOZ_ASSERT_IF(node->left, node->left->parent == node); + MOZ_ASSERT_IF(node->right, node->right->parent == node); + + // This is doing a depth-first search and check that the values are + // ordered properly. + while (true) { + // Go to the left-most child. + while (node->left) { + MOZ_ASSERT_IF(node->left, node->left->parent == node); + MOZ_ASSERT_IF(node->right, node->right->parent == node); + node = node->left; + } + + MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0); + minimum = node; + + if (node->right) { + // Go once to the right and try again. + MOZ_ASSERT_IF(node->left, node->left->parent == node); + MOZ_ASSERT_IF(node->right, node->right->parent == node); + node = node->right; + } else { + // We reached a leaf node, move to the first branch to the right of + // our current left-most sub-tree. + MOZ_ASSERT(!node->left && !node->right); + const Node* prev = nullptr; + + // Visit the parent node, to find the right branch which we have + // not visited yet. Either we are coming back from the right + // branch, or we are coming back from the left branch with no + // right branch to visit. + while (node->parent) { + prev = node; + node = node->parent; + + // If we came back from the left branch, visit the value. + if (node->left == prev) { + MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0); + minimum = node; + } + + if (node->right != prev && node->right != nullptr) { + break; + } + } + + if (!node->parent) { + MOZ_ASSERT(node == root); + // We reached the root node either because we came back from + // the right hand side, or because the root node had a + // single child. + if (node->right == prev || node->right == nullptr) { + return; + } + } + + // Go to the right node which we have not visited yet. + MOZ_ASSERT(node->right != prev && node->right != nullptr); + node = node->right; + } + } +#endif + } +}; + +} /* namespace js */ + +#endif /* ds_SplayTree_h */ diff --git a/js/src/ds/TraceableFifo.h b/js/src/ds/TraceableFifo.h new file mode 100644 index 0000000000..a904610276 --- /dev/null +++ b/js/src/ds/TraceableFifo.h @@ -0,0 +1,93 @@ +/* -*- 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 js_TraceableFifo_h +#define js_TraceableFifo_h + +#include "ds/Fifo.h" +#include "js/RootingAPI.h" +#include "js/TracingAPI.h" + +namespace js { + +// A TraceableFifo is a Fifo with an additional trace method that knows how to +// visit all of the items stored in the Fifo. For Fifos that contain GC things, +// this is usually more convenient than manually iterating and marking the +// contents. +// +// Most types of GC pointers as keys and values can be traced with no extra +// infrastructure. For structs and non-gc-pointer members, ensure that there is +// a specialization of GCPolicy with an appropriate trace method available +// to handle the custom type. Generic helpers can be found in +// js/public/TracingAPI.h. Generic helpers can be found in +// js/public/TracingAPI.h. +// +// Note that although this Fifo's trace will deal correctly with moved items, it +// does not itself know when to barrier or trace items. To function properly it +// must either be used with Rooted, or barriered and traced manually. +template +class TraceableFifo : public js::Fifo { + using Base = js::Fifo; + + public: + explicit TraceableFifo(AllocPolicy alloc = AllocPolicy()) + : Base(std::move(alloc)) {} + + TraceableFifo(TraceableFifo&& rhs) : Base(std::move(rhs)) {} + TraceableFifo& operator=(TraceableFifo&& rhs) = default; + + TraceableFifo(const TraceableFifo&) = delete; + TraceableFifo& operator=(const TraceableFifo&) = delete; + + void trace(JSTracer* trc) { + for (size_t i = 0; i < this->front_.length(); ++i) { + JS::GCPolicy::trace(trc, &this->front_[i], "fifo element"); + } + for (size_t i = 0; i < this->rear_.length(); ++i) { + JS::GCPolicy::trace(trc, &this->rear_[i], "fifo element"); + } + } +}; + +template +class WrappedPtrOperations, Wrapper> { + using TF = TraceableFifo; + const TF& fifo() const { return static_cast(this)->get(); } + + public: + size_t length() const { return fifo().length(); } + bool empty() const { return fifo().empty(); } + const T& front() const { return fifo().front(); } +}; + +template +class MutableWrappedPtrOperations, + Wrapper> + : public WrappedPtrOperations, + Wrapper> { + using TF = TraceableFifo; + TF& fifo() { return static_cast(this)->get(); } + + public: + T& front() { return fifo().front(); } + + template + bool pushBack(U&& u) { + return fifo().pushBack(std::forward(u)); + } + template + bool emplaceBack(Args&&... args) { + return fifo().emplaceBack(std::forward(args...)); + } + + void popFront() { fifo().popFront(); } + void clear() { fifo().clear(); } +}; + +} // namespace js + +#endif // js_TraceableFifo_h -- cgit v1.2.3