1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
8 * GC-internal definitions of ArenaList and associated heap data structures.
11 #ifndef gc_ArenaList_h
12 #define gc_ArenaList_h
14 #include "ds/SinglyLinkedList.h"
15 #include "gc/AllocKind.h"
17 #include "js/HeapAPI.h"
18 #include "js/TypeDecls.h"
19 #include "threading/ProtectedData.h"
33 class AutoGatherSweptArenas
;
34 class BackgroundUnmarkTask
;
41 * Arena lists contain a singly linked lists of arenas starting from a head
44 * They also have a cursor, which conceptually lies on arena boundaries,
45 * i.e. before the first arena, between two arenas, or after the last arena.
47 * Arenas are sorted in order of increasing free space, with the cursor before
48 * the first arena with any free space. This provides a convenient way of
49 * getting the next arena with free space when allocating. The cursor is updated
50 * when this happens to point to the following arena.
52 * The ordering is chosen to try and fill up arenas as much as possible and
53 * leave more empty arenas to be reclaimed when their contents die.
55 * The ordering should not be treated as an invariant, however, as the free
56 * lists may be cleared, leaving arenas previously used for allocation partially
57 * full. Sorting order is restored during sweeping.
60 // The cursor is implemented via an indirect pointer, |cursorp_|, to allow
61 // for efficient list insertion at the cursor point and other list
64 // - If the list is empty: |head| is null, |cursorp_| points to |head|, and
65 // therefore |*cursorp_| is null.
67 // - If the list is not empty: |head| is non-null, and...
69 // - If the cursor is at the start of the list: |cursorp_| points to
70 // |head|, and therefore |*cursorp_| points to the first arena.
72 // - If cursor is at the end of the list: |cursorp_| points to the |next|
73 // field of the last arena, and therefore |*cursorp_| is null.
75 // - If the cursor is at neither the start nor the end of the list:
76 // |cursorp_| points to the |next| field of the arena preceding the
77 // cursor, and therefore |*cursorp_| points to the arena following the
80 // |cursorp_| is never null.
85 // Transfers the contents of |other| to this list and clears |other|.
86 inline void moveFrom(ArenaList
& other
);
90 inline ArenaList(ArenaList
&& other
);
93 inline ArenaList
& operator=(ArenaList
&& other
);
95 // It doesn't make sense for arenas to be present in more than one list, so
96 // list copy operations are not provided.
97 ArenaList(const ArenaList
& other
) = delete;
98 ArenaList
& operator=(const ArenaList
& other
) = delete;
100 inline ArenaList(Arena
* head
, Arena
* arenaBeforeCursor
);
102 inline void check() const;
105 inline bool isEmpty() const;
107 // This returns nullptr if the list is empty.
108 inline Arena
* head() const;
110 inline bool isCursorAtHead() const;
111 inline bool isCursorAtEnd() const;
113 // This can return nullptr.
114 inline Arena
* arenaAfterCursor() const;
116 // This returns the arena after the cursor and moves the cursor past it.
117 inline Arena
* takeNextArena();
119 // This does two things.
120 // - Inserts |a| at the cursor.
121 // - Leaves the cursor sitting just before |a|, if |a| is not full, or just
122 // after |a|, if |a| is full.
123 inline void insertAtCursor(Arena
* a
);
125 // Inserts |a| at the cursor, then moves the cursor past it.
126 inline void insertBeforeCursor(Arena
* a
);
128 // This inserts the contents of |other|, which must be full, at the cursor of
129 // |this| and clears |other|.
130 inline ArenaList
& insertListWithCursorAtEnd(ArenaList
& other
);
132 inline Arena
* takeFirstArena();
134 Arena
* removeRemainingArenas(Arena
** arenap
);
135 Arena
** pickArenasToRelocate(size_t& arenaTotalOut
, size_t& relocTotalOut
);
136 Arena
* relocateArenas(Arena
* toRelocate
, Arena
* relocated
,
137 js::SliceBudget
& sliceBudget
,
138 gcstats::Statistics
& stats
);
146 * A class that is used to sort arenas of a single AllocKind into increasing
147 * order of free space.
149 * It works by adding arenas to a bucket corresponding to the number of free
150 * things in the arena. Each bucket is an independent linked list.
152 * The buckets can be linked up to form a sorted ArenaList.
154 class SortedArenaList
{
156 static_assert(ArenaSize
<= 4096,
157 "When increasing the Arena size, please consider how"
158 " this will affect the size of a SortedArenaList.");
160 static_assert(MinCellSize
>= 16,
161 "When decreasing the minimum thing size, please consider"
162 " how this will affect the size of a SortedArenaList.");
164 // The maximum number of GC things that an arena can hold.
165 static const size_t MaxThingsPerArena
=
166 (ArenaSize
- ArenaHeaderSize
) / MinCellSize
;
168 // The number of buckets required: one full arenas, one for empty arenas and
169 // half the number of remaining size classes.
170 static const size_t BucketCount
= HowMany(MaxThingsPerArena
- 1, 2) + 2;
173 using Bucket
= SinglyLinkedList
<Arena
>;
175 const size_t thingsPerArena_
;
176 Bucket buckets
[BucketCount
];
179 AllocKind allocKind_
;
180 bool isConvertedToArenaList
= false;
184 inline explicit SortedArenaList(AllocKind allocKind
);
186 size_t thingsPerArena() const { return thingsPerArena_
; }
188 // Inserts an arena, which has room for |nfree| more things, in its bucket.
189 inline void insertAt(Arena
* arena
, size_t nfree
);
191 // Remove any empty arenas and prepend them to the list pointed to by
192 // |destListHeadPtr|.
193 inline void extractEmptyTo(Arena
** destListHeadPtr
);
195 // Converts the contents of this data structure to a single list, by linking
196 // up the tail of each non-empty bucket to the head of the next non-empty
199 // Optionally saves internal state to |maybeBucketLastOut| so that it can be
200 // restored later by calling restoreFromArenaList. It is not valid to use this
201 // class in the meantime.
202 inline ArenaList
convertToArenaList(
203 Arena
* maybeBucketLastOut
[BucketCount
] = nullptr);
205 // Restore the internal state of this class following conversion to an
206 // ArenaList by the previous method.
207 inline void restoreFromArenaList(ArenaList
& list
,
208 Arena
* bucketLast
[BucketCount
]);
211 AllocKind
allocKind() const { return allocKind_
; }
215 inline size_t index(size_t nfree
, bool* frontOut
) const;
216 inline size_t emptyIndex() const;
217 inline size_t bucketsUsed() const;
219 inline void check() const;
222 // Gather together any swept arenas for the given zone and alloc kind.
223 class MOZ_RAII AutoGatherSweptArenas
{
224 SortedArenaList
* sortedList
= nullptr;
226 // Internal state from SortedArenaList so we can restore it later.
227 Arena
* bucketLastPointers
[SortedArenaList::BucketCount
];
229 // Single result list.
233 AutoGatherSweptArenas(JS::Zone
* zone
, AllocKind kind
);
234 ~AutoGatherSweptArenas();
236 Arena
* sweptArenas() const;
239 enum class ShouldCheckThresholds
{
240 DontCheckThresholds
= 0,
244 // For each arena kind its free list is represented as the first span with free
245 // things. Initially all the spans are initialized as empty. After we find a new
246 // arena with available things we move its first free span into the list and set
247 // the arena as fully allocated. That way we do not need to update the arena
248 // after the initial allocation. When starting the GC we only move the head of
249 // the of the list of spans back to the arena only for the arena that was not
252 AllAllocKindArray
<FreeSpan
*> freeLists_
;
255 // Because the JITs can allocate from the free lists, they cannot be null.
256 // We use a placeholder FreeSpan that is empty (and wihout an associated
257 // Arena) so the JITs can fall back gracefully.
258 static FreeSpan emptySentinel
;
263 inline bool allEmpty() const;
264 inline bool isEmpty(AllocKind kind
) const;
269 MOZ_ALWAYS_INLINE TenuredCell
* allocate(AllocKind kind
);
271 inline void* setArenaAndAllocate(Arena
* arena
, AllocKind kind
);
273 inline void unmarkPreMarkedFreeCells(AllocKind kind
);
275 FreeSpan
** addressOfFreeList(AllocKind thingKind
) {
276 return &freeLists_
[thingKind
];
281 enum class ConcurrentUse
: uint32_t { None
, BackgroundFinalize
};
283 using ConcurrentUseState
=
284 mozilla::Atomic
<ConcurrentUse
, mozilla::SequentiallyConsistent
>;
288 // Whether this structure can be accessed by other threads.
289 UnprotectedData
<AllAllocKindArray
<ConcurrentUseState
>> concurrentUseState_
;
291 MainThreadData
<FreeLists
> freeLists_
;
293 /* The main list of arenas for each alloc kind. */
294 MainThreadOrGCTaskData
<AllAllocKindArray
<ArenaList
>> arenaLists_
;
297 * Arenas which are currently being collected. The collector can move arenas
298 * from arenaLists_ here and back again at various points in collection.
300 MainThreadOrGCTaskData
<AllAllocKindArray
<ArenaList
>> collectingArenaLists_
;
302 // Arena lists which have yet to be swept, but need additional foreground
303 // processing before they are swept.
304 MainThreadData
<Arena
*> gcCompactPropMapArenasToUpdate
;
305 MainThreadData
<Arena
*> gcNormalPropMapArenasToUpdate
;
307 // The list of empty arenas which are collected during the sweep phase and
308 // released at the end of sweeping every sweep group.
309 MainThreadOrGCTaskData
<Arena
*> savedEmptyArenas
;
312 explicit ArenaLists(JS::Zone
* zone
);
315 FreeLists
& freeLists() { return freeLists_
.ref(); }
316 const FreeLists
& freeLists() const { return freeLists_
.ref(); }
318 FreeSpan
** addressOfFreeList(AllocKind thingKind
) {
319 return freeLists_
.refNoCheck().addressOfFreeList(thingKind
);
322 inline Arena
* getFirstArena(AllocKind thingKind
) const;
323 inline Arena
* getFirstCollectingArena(AllocKind thingKind
) const;
324 inline Arena
* getArenaAfterCursor(AllocKind thingKind
) const;
326 inline bool arenaListsAreEmpty() const;
328 inline bool doneBackgroundFinalize(AllocKind kind
) const;
329 inline bool needBackgroundFinalizeWait(AllocKind kind
) const;
331 /* Clear the free lists so we won't try to allocate from swept arenas. */
332 inline void clearFreeLists();
334 inline void unmarkPreMarkedFreeCells();
336 MOZ_ALWAYS_INLINE TenuredCell
* allocateFromFreeList(AllocKind thingKind
);
338 inline void checkEmptyFreeLists();
339 inline void checkEmptyArenaLists();
340 inline void checkEmptyFreeList(AllocKind kind
);
342 void checkEmptyArenaList(AllocKind kind
);
344 bool relocateArenas(Arena
*& relocatedListOut
, JS::GCReason reason
,
345 js::SliceBudget
& sliceBudget
, gcstats::Statistics
& stats
);
347 void queueForegroundObjectsForSweep(JS::GCContext
* gcx
);
348 void queueForegroundThingsForSweep();
350 Arena
* takeSweptEmptyArenas();
352 void mergeFinalizedArenas(AllocKind thingKind
,
353 SortedArenaList
& finalizedArenas
);
355 void moveArenasToCollectingLists();
356 void mergeArenasFromCollectingLists();
358 void checkGCStateNotInUse();
359 void checkSweepStateNotInUse();
360 void checkNoArenasToUpdate();
361 void checkNoArenasToUpdateForKind(AllocKind kind
);
364 ArenaList
& arenaList(AllocKind i
) { return arenaLists_
.ref()[i
]; }
365 const ArenaList
& arenaList(AllocKind i
) const { return arenaLists_
.ref()[i
]; }
367 ArenaList
& collectingArenaList(AllocKind i
) {
368 return collectingArenaLists_
.ref()[i
];
370 const ArenaList
& collectingArenaList(AllocKind i
) const {
371 return collectingArenaLists_
.ref()[i
];
374 ConcurrentUseState
& concurrentUse(AllocKind i
) {
375 return concurrentUseState_
.ref()[i
];
377 ConcurrentUse
concurrentUse(AllocKind i
) const {
378 return concurrentUseState_
.ref()[i
];
381 inline JSRuntime
* runtime();
382 inline JSRuntime
* runtimeFromAnyThread();
384 void initBackgroundSweep(AllocKind thingKind
);
386 void* refillFreeListAndAllocate(AllocKind thingKind
,
387 ShouldCheckThresholds checkThresholds
);
389 friend class BackgroundUnmarkTask
;
390 friend class GCRuntime
;
391 friend class js::Nursery
;
392 friend class TenuringTracer
;
398 #endif /* gc_ArenaList_h */