1 files changed, 386 insertions, 0 deletions
diff --git a/js/src/gc/ArenaList.h b/js/src/gc/ArenaList.h
new file mode 100644
index 0000000000..4ae4afde71
--- /dev/null
+++ b/js/src/gc/ArenaList.h
@@ -0,0 +1,386 @@
+/* -*- 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/. */
+
+/*
+ * GC-internal definitions of ArenaList and associated heap data structures.
+ */
+
+#ifndef gc_ArenaList_h
+#define gc_ArenaList_h
+
+#include "gc/AllocKind.h"
+#include "js/GCAPI.h"
+#include "js/HeapAPI.h"
+#include "js/TypeDecls.h"
+#include "threading/ProtectedData.h"
+
+namespace js {
+
+class Nursery;
+class SliceBudget;
+
+namespace gcstats {
+struct Statistics;
+}
+
+namespace gc {
+
+class Arena;
+class BackgroundUnmarkTask;
+struct FinalizePhase;
+class FreeSpan;
+class TenuredCell;
+class TenuringTracer;
+
+/*
+ * A single segment of a SortedArenaList. Each segment has a head and a tail,
+ * which track the start and end of a segment for O(1) append and concatenation.
+ */
+struct SortedArenaListSegment {
+  Arena* head;
+  Arena** tailp;
+
+  void clear() {
+    head = nullptr;
+    tailp = &head;
+  }
+
+  bool isEmpty() const { return tailp == &head; }
+
+  // Appends |arena| to this segment.
+  inline void append(Arena* arena);
+
+  // Points the tail of this segment at |arena|, which may be null. Note
+  // that this does not change the tail itself, but merely which arena
+  // follows it. This essentially turns the tail into a cursor (see also the
+  // description of ArenaList), but from the perspective of a SortedArenaList
+  // this makes no difference.
+  void linkTo(Arena* arena) { *tailp = arena; }
+};
+
+/*
+ * Arena lists contain a singly linked lists of arenas starting from a head
+ * pointer.
+ *
+ * They also have a cursor, which conceptually lies on arena boundaries,
+ * i.e. before the first arena, between two arenas, or after the last arena.
+ *
+ * Arenas are usually sorted in order of increasing free space, with the cursor
+ * following the Arena currently being allocated from. This ordering should not
+ * be treated as an invariant, however, as the free lists may be cleared,
+ * leaving arenas previously used for allocation partially full. Sorting order
+ * is restored during sweeping.
+ *
+ * Arenas following the cursor should not be full.
+ */
+class ArenaList {
+  // The cursor is implemented via an indirect pointer, |cursorp_|, to allow
+  // for efficient list insertion at the cursor point and other list
+  // manipulations.
+  //
+  // - If the list is empty: |head| is null, |cursorp_| points to |head|, and
+  //   therefore |*cursorp_| is null.
+  //
+  // - If the list is not empty: |head| is non-null, and...
+  //
+  //   - If the cursor is at the start of the list: |cursorp_| points to
+  //     |head|, and therefore |*cursorp_| points to the first arena.
+  //
+  //   - If cursor is at the end of the list: |cursorp_| points to the |next|
+  //     field of the last arena, and therefore |*cursorp_| is null.
+  //
+  //   - If the cursor is at neither the start nor the end of the list:
+  //     |cursorp_| points to the |next| field of the arena preceding the
+  //     cursor, and therefore |*cursorp_| points to the arena following the
+  //     cursor.
+  //
+  // |cursorp_| is never null.
+  //
+  Arena* head_;
+  Arena** cursorp_;
+
+  // Transfers the contents of |other| to this list and clears |other|.
+  inline void moveFrom(ArenaList& other);
+
+ public:
+  inline ArenaList();
+  inline ArenaList(ArenaList&& other);
+  inline ~ArenaList();
+
+  inline ArenaList& operator=(ArenaList&& other);
+
+  // It doesn't make sense for arenas to be present in more than one list, so
+  // list copy operations are not provided.
+  ArenaList(const ArenaList& other) = delete;
+  ArenaList& operator=(const ArenaList& other) = delete;
+
+  inline explicit ArenaList(const SortedArenaListSegment& segment);
+
+  inline void check() const;
+
+  inline void clear();
+  inline bool isEmpty() const;
+
+  // This returns nullptr if the list is empty.
+  inline Arena* head() const;
+
+  inline bool isCursorAtHead() const;
+  inline bool isCursorAtEnd() const;
+
+  // This can return nullptr.
+  inline Arena* arenaAfterCursor() const;
+
+  // This returns the arena after the cursor and moves the cursor past it.
+  inline Arena* takeNextArena();
+
+  // This does two things.
+  // - Inserts |a| at the cursor.
+  // - Leaves the cursor sitting just before |a|, if |a| is not full, or just
+  //   after |a|, if |a| is full.
+  inline void insertAtCursor(Arena* a);
+
+  // Inserts |a| at the cursor, then moves the cursor past it.
+  inline void insertBeforeCursor(Arena* a);
+
+  // This inserts the contents of |other|, which must be full, at the cursor of
+  // |this| and clears |other|.
+  inline ArenaList& insertListWithCursorAtEnd(ArenaList& other);
+
+  inline Arena* takeFirstArena();
+
+  Arena* removeRemainingArenas(Arena** arenap);
+  Arena** pickArenasToRelocate(size_t& arenaTotalOut, size_t& relocTotalOut);
+  Arena* relocateArenas(Arena* toRelocate, Arena* relocated,
+                        js::SliceBudget& sliceBudget,
+                        gcstats::Statistics& stats);
+
+#ifdef DEBUG
+  void dump();
+#endif
+};
+
+/*
+ * A class that holds arenas in sorted order by appending arenas to specific
+ * segments. Each segment has a head and a tail, which can be linked up to
+ * other segments to create a contiguous ArenaList.
+ */
+class SortedArenaList {
+ public:
+  // The minimum size, in bytes, of a GC thing.
+  static const size_t MinThingSize = 16;
+
+  static_assert(ArenaSize <= 4096,
+                "When increasing the Arena size, please consider how"
+                " this will affect the size of a SortedArenaList.");
+
+  static_assert(MinThingSize >= 16,
+                "When decreasing the minimum thing size, please consider"
+                " how this will affect the size of a SortedArenaList.");
+
+ private:
+  // The maximum number of GC things that an arena can hold.
+  static const size_t MaxThingsPerArena =
+      (ArenaSize - ArenaHeaderSize) / MinThingSize;
+
+  size_t thingsPerArena_;
+  SortedArenaListSegment segments[MaxThingsPerArena + 1];
+
+  // Convenience functions to get the nth head and tail.
+  Arena* headAt(size_t n) { return segments[n].head; }
+  Arena** tailAt(size_t n) { return segments[n].tailp; }
+
+ public:
+  inline explicit SortedArenaList(size_t thingsPerArena = MaxThingsPerArena);
+
+  inline void setThingsPerArena(size_t thingsPerArena);
+
+  // Resets the first |thingsPerArena| segments of this list for further use.
+  inline void reset(size_t thingsPerArena = MaxThingsPerArena);
+
+  // Inserts an arena, which has room for |nfree| more things, in its segment.
+  inline void insertAt(Arena* arena, size_t nfree);
+
+  // Remove all empty arenas, inserting them as a linked list.
+  inline void extractEmpty(Arena** empty);
+
+  // Links up the tail of each non-empty segment to the head of the next
+  // non-empty segment, creating a contiguous list that is returned as an
+  // ArenaList. This is not a destructive operation: neither the head nor tail
+  // of any segment is modified. However, note that the Arenas in the
+  // resulting ArenaList should be treated as read-only unless the
+  // SortedArenaList is no longer needed: inserting or removing arenas would
+  // invalidate the SortedArenaList.
+  inline ArenaList toArenaList();
+};
+
+enum class ShouldCheckThresholds {
+  DontCheckThresholds = 0,
+  CheckThresholds = 1
+};
+
+// For each arena kind its free list is represented as the first span with free
+// things. Initially all the spans are initialized as empty. After we find a new
+// arena with available things we move its first free span into the list and set
+// the arena as fully allocated. That way we do not need to update the arena
+// after the initial allocation. When starting the GC we only move the head of
+// the of the list of spans back to the arena only for the arena that was not
+// fully allocated.
+class FreeLists {
+  AllAllocKindArray<FreeSpan*> freeLists_;
+
+ public:
+  // Because the JITs can allocate from the free lists, they cannot be null.
+  // We use a placeholder FreeSpan that is empty (and wihout an associated
+  // Arena) so the JITs can fall back gracefully.
+  static FreeSpan emptySentinel;
+
+  FreeLists();
+
+#ifdef DEBUG
+  inline bool allEmpty() const;
+  inline bool isEmpty(AllocKind kind) const;
+#endif
+
+  inline void clear();
+
+  MOZ_ALWAYS_INLINE TenuredCell* allocate(AllocKind kind);
+
+  inline void* setArenaAndAllocate(Arena* arena, AllocKind kind);
+
+  inline void unmarkPreMarkedFreeCells(AllocKind kind);
+
+  FreeSpan** addressOfFreeList(AllocKind thingKind) {
+    return &freeLists_[thingKind];
+  }
+};
+
+class ArenaLists {
+  enum class ConcurrentUse : uint32_t { None, BackgroundFinalize };
+
+  using ConcurrentUseState =
+      mozilla::Atomic<ConcurrentUse, mozilla::SequentiallyConsistent>;
+
+  JS::Zone* zone_;
+
+  // Whether this structure can be accessed by other threads.
+  UnprotectedData<AllAllocKindArray<ConcurrentUseState>> concurrentUseState_;
+
+  MainThreadData<FreeLists> freeLists_;
+
+  /* The main list of arenas for each alloc kind. */
+  MainThreadOrGCTaskData<AllAllocKindArray<ArenaList>> arenaLists_;
+
+  /*
+   * Arenas which are currently being collected. The collector can move arenas
+   * from arenaLists_ here and back again at various points in collection.
+   */
+  MainThreadOrGCTaskData<AllAllocKindArray<ArenaList>> collectingArenaLists_;
+
+  /* During incremental sweeping, a list of the arenas already swept. */
+  MainThreadOrGCTaskData<AllocKind> incrementalSweptArenaKind;
+  MainThreadOrGCTaskData<ArenaList> incrementalSweptArenas;
+
+  // Arena lists which have yet to be swept, but need additional foreground
+  // processing before they are swept.
+  MainThreadData<Arena*> gcCompactPropMapArenasToUpdate;
+  MainThreadData<Arena*> gcNormalPropMapArenasToUpdate;
+
+  // The list of empty arenas which are collected during the sweep phase and
+  // released at the end of sweeping every sweep group.
+  MainThreadOrGCTaskData<Arena*> savedEmptyArenas;
+
+ public:
+  explicit ArenaLists(JS::Zone* zone);
+  ~ArenaLists();
+
+  FreeLists& freeLists() { return freeLists_.ref(); }
+  const FreeLists& freeLists() const { return freeLists_.ref(); }
+
+  FreeSpan** addressOfFreeList(AllocKind thingKind) {
+    return freeLists_.refNoCheck().addressOfFreeList(thingKind);
+  }
+
+  inline Arena* getFirstArena(AllocKind thingKind) const;
+  inline Arena* getFirstCollectingArena(AllocKind thingKind) const;
+  inline Arena* getFirstSweptArena(AllocKind thingKind) const;
+  inline Arena* getArenaAfterCursor(AllocKind thingKind) const;
+
+  inline bool arenaListsAreEmpty() const;
+
+  inline bool doneBackgroundFinalize(AllocKind kind) const;
+  inline bool needBackgroundFinalizeWait(AllocKind kind) const;
+
+  /* Clear the free lists so we won't try to allocate from swept arenas. */
+  inline void clearFreeLists();
+
+  inline void unmarkPreMarkedFreeCells();
+
+  MOZ_ALWAYS_INLINE TenuredCell* allocateFromFreeList(AllocKind thingKind);
+
+  inline void checkEmptyFreeLists();
+  inline void checkEmptyArenaLists();
+  inline void checkEmptyFreeList(AllocKind kind);
+
+  void checkEmptyArenaList(AllocKind kind);
+
+  bool relocateArenas(Arena*& relocatedListOut, JS::GCReason reason,
+                      js::SliceBudget& sliceBudget, gcstats::Statistics& stats);
+
+  void queueForegroundObjectsForSweep(JS::GCContext* gcx);
+  void queueForegroundThingsForSweep();
+
+  Arena* takeSweptEmptyArenas();
+
+  void setIncrementalSweptArenas(AllocKind kind, SortedArenaList& arenas);
+  void clearIncrementalSweptArenas();
+
+  void mergeFinalizedArenas(AllocKind thingKind,
+                            SortedArenaList& finalizedArenas);
+
+  void moveArenasToCollectingLists();
+  void mergeArenasFromCollectingLists();
+
+  void checkGCStateNotInUse();
+  void checkSweepStateNotInUse();
+  void checkNoArenasToUpdate();
+  void checkNoArenasToUpdateForKind(AllocKind kind);
+
+ private:
+  ArenaList& arenaList(AllocKind i) { return arenaLists_.ref()[i]; }
+  const ArenaList& arenaList(AllocKind i) const { return arenaLists_.ref()[i]; }
+
+  ArenaList& collectingArenaList(AllocKind i) {
+    return collectingArenaLists_.ref()[i];
+  }
+  const ArenaList& collectingArenaList(AllocKind i) const {
+    return collectingArenaLists_.ref()[i];
+  }
+
+  ConcurrentUseState& concurrentUse(AllocKind i) {
+    return concurrentUseState_.ref()[i];
+  }
+  ConcurrentUse concurrentUse(AllocKind i) const {
+    return concurrentUseState_.ref()[i];
+  }
+
+  inline JSRuntime* runtime();
+  inline JSRuntime* runtimeFromAnyThread();
+
+  void initBackgroundSweep(AllocKind thingKind);
+
+  void* refillFreeListAndAllocate(AllocKind thingKind,
+                                  ShouldCheckThresholds checkThresholds);
+
+  friend class BackgroundUnmarkTask;
+  friend class GCRuntime;
+  friend class js::Nursery;
+  friend class TenuringTracer;
+};
+
+} /* namespace gc */
+} /* namespace js */
+
+#endif /* gc_ArenaList_h */