diff options
Diffstat (limited to 'js/src/gc/Heap.cpp')
| -rw-r--r-- | js/src/gc/Heap.cpp | 635 |
1 files changed, 635 insertions, 0 deletions
diff --git a/js/src/gc/Heap.cpp b/js/src/gc/Heap.cpp new file mode 100644 index 0000000000..fdf24fbb7c --- /dev/null +++ b/js/src/gc/Heap.cpp @@ -0,0 +1,635 @@ +/* -*- 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/. */ + +/* + * Tenured heap management. + * + * This file contains method definitions for the following classes for code that + * is not specific to a particular phase of GC: + * + * - Arena + * - ArenaList + * - FreeLists + * - ArenaLists + * - TenuredChunk + * - ChunkPool + */ + +#include "gc/Heap-inl.h" + +#include "gc/GCLock.h" +#include "gc/Memory.h" +#include "jit/Assembler.h" +#include "vm/BigIntType.h" +#include "vm/RegExpShared.h" +#include "vm/Scope.h" + +#include "gc/ArenaList-inl.h" +#include "gc/PrivateIterators-inl.h" + +using namespace js; +using namespace js::gc; + +// Check that reserved bits of a Cell are compatible with our typical allocators +// since most derived classes will store a pointer in the first word. +static const size_t MinFirstWordAlignment = 1u << CellFlagBitsReservedForGC; +static_assert(js::detail::LIFO_ALLOC_ALIGN >= MinFirstWordAlignment, + "CellFlagBitsReservedForGC should support LifoAlloc"); +static_assert(CellAlignBytes >= MinFirstWordAlignment, + "CellFlagBitsReservedForGC should support gc::Cell"); +static_assert(js::jit::CodeAlignment >= MinFirstWordAlignment, + "CellFlagBitsReservedForGC should support JIT code"); +static_assert(js::gc::JSClassAlignBytes >= MinFirstWordAlignment, + "CellFlagBitsReservedForGC should support JSClass pointers"); +static_assert(js::ScopeDataAlignBytes >= MinFirstWordAlignment, + "CellFlagBitsReservedForGC should support scope data pointers"); + +#define CHECK_THING_SIZE(allocKind, traceKind, type, sizedType, bgFinal, \ + nursery, compact) \ + static_assert(sizeof(sizedType) >= SortedArenaList::MinThingSize, \ + #sizedType " is smaller than SortedArenaList::MinThingSize!"); \ + static_assert(sizeof(sizedType) >= sizeof(FreeSpan), \ + #sizedType " is smaller than FreeSpan"); \ + static_assert(sizeof(sizedType) % CellAlignBytes == 0, \ + "Size of " #sizedType " is not a multiple of CellAlignBytes"); \ + static_assert(sizeof(sizedType) >= MinCellSize, \ + "Size of " #sizedType " is smaller than the minimum size"); +FOR_EACH_ALLOCKIND(CHECK_THING_SIZE); +#undef CHECK_THING_SIZE + +FreeSpan FreeLists::emptySentinel; + +template <typename T> +struct ArenaLayout { + static constexpr size_t thingSize() { return sizeof(T); } + static constexpr size_t thingsPerArena() { + return (ArenaSize - ArenaHeaderSize) / thingSize(); + } + static constexpr size_t firstThingOffset() { + return ArenaSize - thingSize() * thingsPerArena(); + } +}; + +const uint8_t Arena::ThingSizes[] = { +#define EXPAND_THING_SIZE(_1, _2, _3, sizedType, _4, _5, _6) \ + ArenaLayout<sizedType>::thingSize(), + FOR_EACH_ALLOCKIND(EXPAND_THING_SIZE) +#undef EXPAND_THING_SIZE +}; + +const uint8_t Arena::FirstThingOffsets[] = { +#define EXPAND_FIRST_THING_OFFSET(_1, _2, _3, sizedType, _4, _5, _6) \ + ArenaLayout<sizedType>::firstThingOffset(), + FOR_EACH_ALLOCKIND(EXPAND_FIRST_THING_OFFSET) +#undef EXPAND_FIRST_THING_OFFSET +}; + +const uint8_t Arena::ThingsPerArena[] = { +#define EXPAND_THINGS_PER_ARENA(_1, _2, _3, sizedType, _4, _5, _6) \ + ArenaLayout<sizedType>::thingsPerArena(), + FOR_EACH_ALLOCKIND(EXPAND_THINGS_PER_ARENA) +#undef EXPAND_THINGS_PER_ARENA +}; + +void Arena::unmarkAll() { + MarkBitmapWord* arenaBits = chunk()->markBits.arenaBits(this); + for (size_t i = 0; i < ArenaBitmapWords; i++) { + arenaBits[i] = 0; + } +} + +void Arena::unmarkPreMarkedFreeCells() { + for (ArenaFreeCellIter cell(this); !cell.done(); cell.next()) { + MOZ_ASSERT(cell->isMarkedBlack()); + cell->unmark(); + } +} + +#ifdef DEBUG + +void Arena::checkNoMarkedFreeCells() { + for (ArenaFreeCellIter cell(this); !cell.done(); cell.next()) { + MOZ_ASSERT(!cell->isMarkedAny()); + } +} + +void Arena::checkAllCellsMarkedBlack() { + for (ArenaCellIter cell(this); !cell.done(); cell.next()) { + MOZ_ASSERT(cell->isMarkedBlack()); + } +} + +#endif + +#if defined(DEBUG) || defined(JS_GC_ZEAL) +void Arena::checkNoMarkedCells() { + for (ArenaCellIter cell(this); !cell.done(); cell.next()) { + MOZ_ASSERT(!cell->isMarkedAny()); + } +} +#endif + +/* static */ +void Arena::staticAsserts() { + static_assert(size_t(AllocKind::LIMIT) <= 255, + "All AllocKinds and AllocKind::LIMIT must fit in a uint8_t."); + static_assert(std::size(ThingSizes) == AllocKindCount, + "We haven't defined all thing sizes."); + static_assert(std::size(FirstThingOffsets) == AllocKindCount, + "We haven't defined all offsets."); + static_assert(std::size(ThingsPerArena) == AllocKindCount, + "We haven't defined all counts."); +} + +/* static */ +void Arena::checkLookupTables() { +#ifdef DEBUG + for (size_t i = 0; i < AllocKindCount; i++) { + MOZ_ASSERT( + FirstThingOffsets[i] + ThingsPerArena[i] * ThingSizes[i] == ArenaSize, + "Inconsistent arena lookup table data"); + } +#endif +} + +#ifdef DEBUG +void js::gc::ArenaList::dump() { + fprintf(stderr, "ArenaList %p:", this); + if (cursorp_ == &head_) { + fprintf(stderr, " *"); + } + for (Arena* arena = head(); arena; arena = arena->next) { + fprintf(stderr, " %p", arena); + if (cursorp_ == &arena->next) { + fprintf(stderr, " *"); + } + } + fprintf(stderr, "\n"); +} +#endif + +Arena* ArenaList::removeRemainingArenas(Arena** arenap) { + // This is only ever called to remove arenas that are after the cursor, so + // we don't need to update it. +#ifdef DEBUG + for (Arena* arena = *arenap; arena; arena = arena->next) { + MOZ_ASSERT(cursorp_ != &arena->next); + } +#endif + Arena* remainingArenas = *arenap; + *arenap = nullptr; + check(); + return remainingArenas; +} + +FreeLists::FreeLists() { + for (auto i : AllAllocKinds()) { + freeLists_[i] = &emptySentinel; + } +} + +ArenaLists::ArenaLists(Zone* zone) + : zone_(zone), + incrementalSweptArenaKind(AllocKind::LIMIT), + gcCompactPropMapArenasToUpdate(nullptr), + gcNormalPropMapArenasToUpdate(nullptr), + savedEmptyArenas(nullptr) { + for (auto i : AllAllocKinds()) { + concurrentUse(i) = ConcurrentUse::None; + } +} + +void ReleaseArenas(JSRuntime* rt, Arena* arena, const AutoLockGC& lock) { + Arena* next; + for (; arena; arena = next) { + next = arena->next; + rt->gc.releaseArena(arena, lock); + } +} + +void ReleaseArenaList(JSRuntime* rt, ArenaList& arenaList, + const AutoLockGC& lock) { + ReleaseArenas(rt, arenaList.head(), lock); + arenaList.clear(); +} + +ArenaLists::~ArenaLists() { + AutoLockGC lock(runtime()); + + for (auto i : AllAllocKinds()) { + /* + * We can only call this during the shutdown after the last GC when + * the background finalization is disabled. + */ + MOZ_ASSERT(concurrentUse(i) == ConcurrentUse::None); + ReleaseArenaList(runtime(), arenaList(i), lock); + } + ReleaseArenaList(runtime(), incrementalSweptArenas.ref(), lock); + + ReleaseArenas(runtime(), savedEmptyArenas, lock); +} + +void ArenaLists::moveArenasToCollectingLists() { + checkEmptyFreeLists(); + for (AllocKind kind : AllAllocKinds()) { + MOZ_ASSERT(collectingArenaList(kind).isEmpty()); + collectingArenaList(kind) = std::move(arenaList(kind)); + MOZ_ASSERT(arenaList(kind).isEmpty()); + } +} + +void ArenaLists::mergeArenasFromCollectingLists() { + for (AllocKind kind : AllAllocKinds()) { + collectingArenaList(kind).insertListWithCursorAtEnd(arenaList(kind)); + arenaList(kind) = std::move(collectingArenaList(kind)); + MOZ_ASSERT(collectingArenaList(kind).isEmpty()); + } +} + +Arena* ArenaLists::takeSweptEmptyArenas() { + Arena* arenas = savedEmptyArenas; + savedEmptyArenas = nullptr; + return arenas; +} + +void ArenaLists::setIncrementalSweptArenas(AllocKind kind, + SortedArenaList& arenas) { + incrementalSweptArenaKind = kind; + incrementalSweptArenas.ref().clear(); + incrementalSweptArenas = arenas.toArenaList(); +} + +void ArenaLists::clearIncrementalSweptArenas() { + incrementalSweptArenaKind = AllocKind::LIMIT; + incrementalSweptArenas.ref().clear(); +} + +void ArenaLists::checkGCStateNotInUse() { + // Called before and after collection to check the state is as expected. +#ifdef DEBUG + checkSweepStateNotInUse(); + for (auto i : AllAllocKinds()) { + MOZ_ASSERT(collectingArenaList(i).isEmpty()); + } +#endif +} + +void ArenaLists::checkSweepStateNotInUse() { +#ifdef DEBUG + checkNoArenasToUpdate(); + MOZ_ASSERT(incrementalSweptArenaKind == AllocKind::LIMIT); + MOZ_ASSERT(incrementalSweptArenas.ref().isEmpty()); + MOZ_ASSERT(!savedEmptyArenas); + for (auto i : AllAllocKinds()) { + MOZ_ASSERT(concurrentUse(i) == ConcurrentUse::None); + } +#endif +} + +void ArenaLists::checkNoArenasToUpdate() { + MOZ_ASSERT(!gcCompactPropMapArenasToUpdate); + MOZ_ASSERT(!gcNormalPropMapArenasToUpdate); +} + +void ArenaLists::checkNoArenasToUpdateForKind(AllocKind kind) { +#ifdef DEBUG + switch (kind) { + case AllocKind::COMPACT_PROP_MAP: + MOZ_ASSERT(!gcCompactPropMapArenasToUpdate); + break; + case AllocKind::NORMAL_PROP_MAP: + MOZ_ASSERT(!gcNormalPropMapArenasToUpdate); + break; + default: + break; + } +#endif +} + +inline bool TenuredChunk::canDecommitPage(size_t pageIndex) const { + if (decommittedPages[pageIndex]) { + return false; + } + + size_t arenaIndex = pageIndex * ArenasPerPage; + for (size_t i = 0; i < ArenasPerPage; i++) { + if (!freeCommittedArenas[arenaIndex + i]) { + return false; + } + } + + return true; +} + +void TenuredChunk::decommitFreeArenas(GCRuntime* gc, const bool& cancel, + AutoLockGC& lock) { + MOZ_ASSERT(DecommitEnabled()); + + for (size_t i = 0; i < PagesPerChunk; i++) { + if (cancel) { + break; + } + + if (canDecommitPage(i) && !decommitOneFreePage(gc, i, lock)) { + break; + } + } +} + +void TenuredChunk::recycleArena(Arena* arena, SortedArenaList& dest, + size_t thingsPerArena) { + arena->setAsFullyUnused(); + dest.insertAt(arena, thingsPerArena); +} + +void TenuredChunk::releaseArena(GCRuntime* gc, Arena* arena, + const AutoLockGC& lock) { + MOZ_ASSERT(!arena->allocated()); + MOZ_ASSERT(!freeCommittedArenas[arenaIndex(arena)]); + + freeCommittedArenas[arenaIndex(arena)] = true; + ++info.numArenasFreeCommitted; + ++info.numArenasFree; + gc->updateOnArenaFree(); + + verify(); + + updateChunkListAfterFree(gc, 1, lock); +} + +bool TenuredChunk::decommitOneFreePage(GCRuntime* gc, size_t pageIndex, + AutoLockGC& lock) { + MOZ_ASSERT(DecommitEnabled()); + MOZ_ASSERT(canDecommitPage(pageIndex)); + MOZ_ASSERT(info.numArenasFreeCommitted >= ArenasPerPage); + + // Temporarily mark the page as allocated while we decommit. + for (size_t i = 0; i < ArenasPerPage; i++) { + size_t arenaIndex = pageIndex * ArenasPerPage + i; + MOZ_ASSERT(freeCommittedArenas[arenaIndex]); + freeCommittedArenas[arenaIndex] = false; + } + info.numArenasFreeCommitted -= ArenasPerPage; + info.numArenasFree -= ArenasPerPage; + updateChunkListAfterAlloc(gc, lock); + + verify(); + + bool ok; + { + AutoUnlockGC unlock(lock); + ok = !oom::ShouldFailWithOOM() && + MarkPagesUnusedSoft(pageAddress(pageIndex), PageSize); + } + + // Mark the page as decommited if successful or restore the original free + // state. + if (ok) { + decommittedPages[pageIndex] = true; + } else { + for (size_t i = 0; i < ArenasPerPage; i++) { + size_t arenaIndex = pageIndex * ArenasPerPage + i; + MOZ_ASSERT(!freeCommittedArenas[arenaIndex]); + freeCommittedArenas[arenaIndex] = true; + } + info.numArenasFreeCommitted += ArenasPerPage; + } + + info.numArenasFree += ArenasPerPage; + updateChunkListAfterFree(gc, ArenasPerPage, lock); + + verify(); + + return ok; +} + +void TenuredChunk::decommitFreeArenasWithoutUnlocking(const AutoLockGC& lock) { + MOZ_ASSERT(DecommitEnabled()); + + for (size_t i = 0; i < PagesPerChunk; i++) { + if (!canDecommitPage(i)) { + continue; + } + + MOZ_ASSERT(!decommittedPages[i]); + MOZ_ASSERT(info.numArenasFreeCommitted >= ArenasPerPage); + + if (js::oom::ShouldFailWithOOM() || + !MarkPagesUnusedSoft(pageAddress(i), SystemPageSize())) { + break; + } + + decommittedPages[i] = true; + for (size_t j = 0; j < ArenasPerPage; ++j) { + size_t arenaIndex = i * ArenasPerPage + j; + MOZ_ASSERT(freeCommittedArenas[arenaIndex]); + freeCommittedArenas[arenaIndex] = false; + } + info.numArenasFreeCommitted -= ArenasPerPage; + } + + verify(); +} + +void TenuredChunk::updateChunkListAfterAlloc(GCRuntime* gc, + const AutoLockGC& lock) { + if (MOZ_UNLIKELY(!hasAvailableArenas())) { + gc->availableChunks(lock).remove(this); + gc->fullChunks(lock).push(this); + } +} + +void TenuredChunk::updateChunkListAfterFree(GCRuntime* gc, size_t numArenasFree, + const AutoLockGC& lock) { + if (info.numArenasFree == numArenasFree) { + gc->fullChunks(lock).remove(this); + gc->availableChunks(lock).push(this); + } else if (!unused()) { + MOZ_ASSERT(gc->availableChunks(lock).contains(this)); + } else { + MOZ_ASSERT(unused()); + gc->availableChunks(lock).remove(this); + gc->recycleChunk(this, lock); + } +} + +TenuredChunk* ChunkPool::pop() { + MOZ_ASSERT(bool(head_) == bool(count_)); + if (!count_) { + return nullptr; + } + return remove(head_); +} + +void ChunkPool::push(TenuredChunk* chunk) { + MOZ_ASSERT(!chunk->info.next); + MOZ_ASSERT(!chunk->info.prev); + + chunk->info.next = head_; + if (head_) { + head_->info.prev = chunk; + } + head_ = chunk; + ++count_; +} + +TenuredChunk* ChunkPool::remove(TenuredChunk* chunk) { + MOZ_ASSERT(count_ > 0); + MOZ_ASSERT(contains(chunk)); + + if (head_ == chunk) { + head_ = chunk->info.next; + } + if (chunk->info.prev) { + chunk->info.prev->info.next = chunk->info.next; + } + if (chunk->info.next) { + chunk->info.next->info.prev = chunk->info.prev; + } + chunk->info.next = chunk->info.prev = nullptr; + --count_; + + return chunk; +} + +// We could keep the chunk pool sorted, but that's likely to be more expensive. +// This sort is nlogn, but keeping it sorted is likely to be m*n, with m being +// the number of operations (likely higher than n). +void ChunkPool::sort() { + // Only sort if the list isn't already sorted. + if (!isSorted()) { + head_ = mergeSort(head(), count()); + + // Fixup prev pointers. + TenuredChunk* prev = nullptr; + for (TenuredChunk* cur = head_; cur; cur = cur->info.next) { + cur->info.prev = prev; + prev = cur; + } + } + + MOZ_ASSERT(verify()); + MOZ_ASSERT(isSorted()); +} + +TenuredChunk* ChunkPool::mergeSort(TenuredChunk* list, size_t count) { + MOZ_ASSERT(bool(list) == bool(count)); + + if (count < 2) { + return list; + } + + size_t half = count / 2; + + // Split; + TenuredChunk* front = list; + TenuredChunk* back; + { + TenuredChunk* cur = list; + for (size_t i = 0; i < half - 1; i++) { + MOZ_ASSERT(cur); + cur = cur->info.next; + } + back = cur->info.next; + cur->info.next = nullptr; + } + + front = mergeSort(front, half); + back = mergeSort(back, count - half); + + // Merge + list = nullptr; + TenuredChunk** cur = &list; + while (front || back) { + if (!front) { + *cur = back; + break; + } + if (!back) { + *cur = front; + break; + } + + // Note that the sort is stable due to the <= here. Nothing depends on + // this but it could. + if (front->info.numArenasFree <= back->info.numArenasFree) { + *cur = front; + front = front->info.next; + cur = &(*cur)->info.next; + } else { + *cur = back; + back = back->info.next; + cur = &(*cur)->info.next; + } + } + + return list; +} + +bool ChunkPool::isSorted() const { + uint32_t last = 1; + for (TenuredChunk* cursor = head_; cursor; cursor = cursor->info.next) { + if (cursor->info.numArenasFree < last) { + return false; + } + last = cursor->info.numArenasFree; + } + return true; +} + +#ifdef DEBUG + +bool ChunkPool::contains(TenuredChunk* chunk) const { + verify(); + for (TenuredChunk* cursor = head_; cursor; cursor = cursor->info.next) { + if (cursor == chunk) { + return true; + } + } + return false; +} + +bool ChunkPool::verify() const { + MOZ_ASSERT(bool(head_) == bool(count_)); + uint32_t count = 0; + for (TenuredChunk* cursor = head_; cursor; + cursor = cursor->info.next, ++count) { + MOZ_ASSERT_IF(cursor->info.prev, cursor->info.prev->info.next == cursor); + MOZ_ASSERT_IF(cursor->info.next, cursor->info.next->info.prev == cursor); + } + MOZ_ASSERT(count_ == count); + return true; +} + +void ChunkPool::verifyChunks() const { + for (TenuredChunk* chunk = head_; chunk; chunk = chunk->info.next) { + chunk->verify(); + } +} + +void TenuredChunk::verify() const { + MOZ_ASSERT(info.numArenasFree <= ArenasPerChunk); + MOZ_ASSERT(info.numArenasFreeCommitted <= info.numArenasFree); + + size_t decommittedCount = decommittedPages.Count() * ArenasPerPage; + size_t freeCommittedCount = freeCommittedArenas.Count(); + size_t freeCount = freeCommittedCount + decommittedCount; + + MOZ_ASSERT(freeCount == info.numArenasFree); + MOZ_ASSERT(freeCommittedCount == info.numArenasFreeCommitted); + + for (size_t i = 0; i < ArenasPerChunk; ++i) { + MOZ_ASSERT(!(decommittedPages[pageIndex(i)] && freeCommittedArenas[i])); + MOZ_ASSERT_IF(freeCommittedArenas[i], !arenas[i].allocated()); + } +} + +#endif + +void ChunkPool::Iter::next() { + MOZ_ASSERT(!done()); + current_ = current_->info.next; +} |