Source code

Revision control

Other Tools

/* -*- 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 */
* 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/SliceBudget.h"
#include "js/TypeDecls.h"
#include "threading/ProtectedData.h"
namespace js {
class Nursery;
class TenuringTracer;
namespace gcstats {
struct Statistics;
namespace gc {
class Arena;
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 have a head and a cursor. The cursor 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_;
inline void copy(const ArenaList& other);
inline ArenaList();
inline ArenaList(const ArenaList& other);
inline ArenaList& operator=(const ArenaList& other);
inline explicit ArenaList(const SortedArenaListSegment& segment);
inline void check() const;
inline void clear();
inline ArenaList copyAndClear();
inline bool isEmpty() const;
// This returns nullptr if the list is empty.
inline Arena* head() const;
inline bool isCursorAtHead() const;
inline bool isCursorAtEnd() const;
inline void moveCursorToEnd();
// 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 |other|, which must be full, at the cursor of |this|.
inline ArenaList& insertListWithCursorAtEnd(const ArenaList& other);
Arena* removeRemainingArenas(Arena** arenap);
Arena** pickArenasToRelocate(size_t& arenaTotalOut, size_t& relocTotalOut);
Arena* relocateArenas(Arena* toRelocate, Arena* relocated,
js::SliceBudget& sliceBudget,
gcstats::Statistics& stats);
* 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 {
// 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.");
// 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; }
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_;
// 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;
#ifdef DEBUG
inline bool allEmpty() const;
inline bool isEmpty(AllocKind kind) const;
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 {
using ConcurrentUseState =
mozilla::Atomic<ConcurrentUse, mozilla::SequentiallyConsistent>;
JS::Zone* zone_;
// Whether this structure can be accessed by other threads.
UnprotectedData<AllAllocKindArray<ConcurrentUseState>> concurrentUseState_;
ZoneData<FreeLists> freeLists_;
/* The main list of arenas for each alloc kind. */
ArenaListData<AllAllocKindArray<ArenaList>> arenaLists_;
/* For each arena kind, a list of arenas allocated during marking. */
ArenaListData<AllAllocKindArray<ArenaList>> newArenasInMarkPhase_;
/* For each arena kind, a list of arenas remaining to be swept. */
MainThreadOrGCTaskData<AllAllocKindArray<Arena*>> arenasToSweep_;
/* During incremental sweeping, a list of the arenas already swept. */
ZoneOrGCTaskData<AllocKind> incrementalSweptArenaKind;
ZoneOrGCTaskData<ArenaList> incrementalSweptArenas;
// Arena lists which have yet to be swept, but need additional foreground
// processing before they are swept.
ZoneData<Arena*> gcShapeArenasToUpdate;
ZoneData<Arena*> gcAccessorShapeArenasToUpdate;
ZoneData<Arena*> gcScriptArenasToUpdate;
ZoneData<Arena*> gcNewScriptArenasToUpdate;
ZoneData<Arena*> gcObjectGroupArenasToUpdate;
ZoneData<Arena*> gcNewObjectGroupArenasToUpdate;
// The list of empty arenas which are collected during the sweep phase and
// released at the end of sweeping every sweep group.
ZoneData<Arena*> savedEmptyArenas;
explicit ArenaLists(JS::Zone* zone);
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* getFirstArenaToSweep(AllocKind thingKind) const;
inline Arena* getFirstSweptArena(AllocKind thingKind) const;
inline Arena* getFirstNewArenaInMarkPhase(AllocKind thingKind) const;
inline Arena* getArenaAfterCursor(AllocKind thingKind) const;
inline bool arenaListsAreEmpty() const;
inline void unmarkAll();
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);
/* Moves all arenas from |fromArenaLists| into |this|. */
void adoptArenas(ArenaLists* fromArenaLists, bool targetZoneIsCollecting);
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(JSFreeOp* fop);
void queueForegroundThingsForSweep();
void releaseForegroundSweptEmptyArenas();
bool foregroundFinalize(JSFreeOp* fop, AllocKind thingKind,
js::SliceBudget& sliceBudget,
SortedArenaList& sweepList);
static void backgroundFinalize(JSFreeOp* fop, Arena* listHead, Arena** empty);
void setParallelAllocEnabled(bool enabled);
inline void mergeNewArenasInMarkPhase();
void checkGCStateNotInUse();
void checkSweepStateNotInUse();
void checkNoArenasToUpdate();
void checkNoArenasToUpdateForKind(AllocKind kind);
ArenaList& arenaList(AllocKind i) { return arenaLists_.ref()[i]; }
const ArenaList& arenaList(AllocKind i) const { return arenaLists_.ref()[i]; }
ArenaList& newArenasInMarkPhase(AllocKind i) {
return newArenasInMarkPhase_.ref()[i];
const ArenaList& newArenasInMarkPhase(AllocKind i) const {
return newArenasInMarkPhase_.ref()[i];
ConcurrentUseState& concurrentUse(AllocKind i) {
return concurrentUseState_.ref()[i];
ConcurrentUse concurrentUse(AllocKind i) const {
return concurrentUseState_.ref()[i];
Arena*& arenasToSweep(AllocKind i) { return arenasToSweep_.ref()[i]; }
Arena* arenasToSweep(AllocKind i) const { return arenasToSweep_.ref()[i]; }
inline JSRuntime* runtime();
inline JSRuntime* runtimeFromAnyThread();
inline void queueForForegroundSweep(JSFreeOp* fop,
const FinalizePhase& phase);
inline void queueForBackgroundSweep(JSFreeOp* fop,
const FinalizePhase& phase);
inline void queueForForegroundSweep(AllocKind thingKind);
inline void queueForBackgroundSweep(AllocKind thingKind);
TenuredCell* refillFreeListAndAllocate(FreeLists& freeLists,
AllocKind thingKind,
ShouldCheckThresholds checkThresholds);
void addNewArena(Arena* arena, AllocKind thingKind);
friend class GCRuntime;
friend class js::Nursery;
friend class js::TenuringTracer;
} /* namespace gc */
} /* namespace js */
#endif /* gc_ArenaList_h */