summaryrefslogtreecommitdiffstats
path: root/js/src/gc/ArenaList.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/gc/ArenaList.h')
-rw-r--r--js/src/gc/ArenaList.h386
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..9d46ec01de
--- /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;
+class TenuringTracer;
+
+namespace gcstats {
+struct Statistics;
+}
+
+namespace gc {
+
+class Arena;
+class BackgroundUnmarkTask;
+struct FinalizePhase;
+class FreeSpan;
+class TenuredCell;
+
+/*
+ * 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 TenuredCell* 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);
+
+ TenuredCell* refillFreeListAndAllocate(AllocKind thingKind,
+ ShouldCheckThresholds checkThresholds);
+
+ friend class BackgroundUnmarkTask;
+ friend class GCRuntime;
+ friend class js::Nursery;
+ friend class js::TenuringTracer;
+};
+
+} /* namespace gc */
+} /* namespace js */
+
+#endif /* gc_ArenaList_h */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-29 04:01:07 +0000