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;
+}