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"
36 class AutoGatherSweptArenas
;
37 class BackgroundUnmarkTask
;
44 * Arena lists contain a singly linked lists of arenas starting from a head
47 * They also have a cursor, which conceptually lies on arena boundaries,
48 * i.e. before the first arena, between two arenas, or after the last arena.
50 * Arenas are sorted in order of increasing free space, with the cursor before
51 * the first arena with any free space. This provides a convenient way of
52 * getting the next arena with free space when allocating. The cursor is updated
53 * when this happens to point to the following arena.
55 * The ordering is chosen to try and fill up arenas as much as possible and
56 * leave more empty arenas to be reclaimed when their contents die.
58 * The ordering should not be treated as an invariant, however, as the free
59 * lists may be cleared, leaving arenas previously used for allocation partially
60 * full. Sorting order is restored during sweeping.
63 // The cursor is implemented via an indirect pointer, |cursorp_|, to allow
64 // for efficient list insertion at the cursor point and other list
67 // - If the list is empty: |head| is null, |cursorp_| points to |head|, and
68 // therefore |*cursorp_| is null.
70 // - If the list is not empty: |head| is non-null, and...
72 // - If the cursor is at the start of the list: |cursorp_| points to
73 // |head|, and therefore |*cursorp_| points to the first arena.
75 // - If cursor is at the end of the list: |cursorp_| points to the |next|
76 // field of the last arena, and therefore |*cursorp_| is null.
78 // - If the cursor is at neither the start nor the end of the list:
79 // |cursorp_| points to the |next| field of the arena preceding the
80 // cursor, and therefore |*cursorp_| points to the arena following the
83 // |cursorp_| is never null.
88 // Transfers the contents of |other| to this list and clears |other|.
89 inline void moveFrom(ArenaList
& other
);
93 inline ArenaList(ArenaList
&& other
);
96 inline ArenaList
& operator=(ArenaList
&& other
);
98 // It doesn't make sense for arenas to be present in more than one list, so
99 // list copy operations are not provided.
100 ArenaList(const ArenaList
& other
) = delete;
101 ArenaList
& operator=(const ArenaList
& other
) = delete;
103 inline ArenaList(Arena
* head
, Arena
* arenaBeforeCursor
);
105 inline void check() const;
108 inline bool isEmpty() const;
110 // This returns nullptr if the list is empty.
111 inline Arena
* head() const;
113 inline bool isCursorAtHead() const;
114 inline bool isCursorAtEnd() const;
116 // This can return nullptr.
117 inline Arena
* arenaAfterCursor() const;
119 // This returns the arena after the cursor and moves the cursor past it.
120 inline Arena
* takeNextArena();
122 // This does two things.
123 // - Inserts |a| at the cursor.
124 // - Leaves the cursor sitting just before |a|, if |a| is not full, or just
125 // after |a|, if |a| is full.
126 inline void insertAtCursor(Arena
* a
);
128 // Inserts |a| at the cursor, then moves the cursor past it.
129 inline void insertBeforeCursor(Arena
* a
);
131 // This inserts the contents of |other|, which must be full, at the cursor of
132 // |this| and clears |other|.
133 inline ArenaList
& insertListWithCursorAtEnd(ArenaList
& other
);
135 inline Arena
* takeFirstArena();
137 Arena
* removeRemainingArenas(Arena
** arenap
);
138 Arena
** pickArenasToRelocate(size_t& arenaTotalOut
, size_t& relocTotalOut
);
139 Arena
* relocateArenas(Arena
* toRelocate
, Arena
* relocated
,
140 JS::SliceBudget
& sliceBudget
,
141 gcstats::Statistics
& stats
);
149 * A class that is used to sort arenas of a single AllocKind into increasing
150 * order of free space.
152 * It works by adding arenas to a bucket corresponding to the number of free
153 * things in the arena. Each bucket is an independent linked list.
155 * The buckets can be linked up to form a sorted ArenaList.
157 class SortedArenaList
{
159 static_assert(ArenaSize
<= 4096,
160 "When increasing the Arena size, please consider how"
161 " this will affect the size of a SortedArenaList.");
163 static_assert(MinCellSize
>= 16,
164 "When decreasing the minimum thing size, please consider"
165 " how this will affect the size of a SortedArenaList.");
167 // The maximum number of GC things that an arena can hold.
168 static const size_t MaxThingsPerArena
=
169 (ArenaSize
- ArenaHeaderSize
) / MinCellSize
;
171 // The number of buckets required: one full arenas, one for empty arenas and
172 // half the number of remaining size classes.
173 static const size_t BucketCount
= HowMany(MaxThingsPerArena
- 1, 2) + 2;
176 using Bucket
= SinglyLinkedList
<Arena
>;
178 const size_t thingsPerArena_
;
179 Bucket buckets
[BucketCount
];
182 AllocKind allocKind_
;
183 bool isConvertedToArenaList
= false;
187 inline explicit SortedArenaList(AllocKind allocKind
);
189 size_t thingsPerArena() const { return thingsPerArena_
; }
191 // Inserts an arena, which has room for |nfree| more things, in its bucket.
192 inline void insertAt(Arena
* arena
, size_t nfree
);
194 // Remove any empty arenas and prepend them to the list pointed to by
195 // |destListHeadPtr|.
196 inline void extractEmptyTo(Arena
** destListHeadPtr
);
198 // Converts the contents of this data structure to a single list, by linking
199 // up the tail of each non-empty bucket to the head of the next non-empty
202 // Optionally saves internal state to |maybeBucketLastOut| so that it can be
203 // restored later by calling restoreFromArenaList. It is not valid to use this
204 // class in the meantime.
205 inline ArenaList
convertToArenaList(
206 Arena
* maybeBucketLastOut
[BucketCount
] = nullptr);
208 // Restore the internal state of this class following conversion to an
209 // ArenaList by the previous method.
210 inline void restoreFromArenaList(ArenaList
& list
,
211 Arena
* bucketLast
[BucketCount
]);
214 AllocKind
allocKind() const { return allocKind_
; }
218 inline size_t index(size_t nfree
, bool* frontOut
) const;
219 inline size_t emptyIndex() const;
220 inline size_t bucketsUsed() const;
222 inline void check() const;
225 // Gather together any swept arenas for the given zone and alloc kind.
226 class MOZ_RAII AutoGatherSweptArenas
{
227 SortedArenaList
* sortedList
= nullptr;
229 // Internal state from SortedArenaList so we can restore it later.
230 Arena
* bucketLastPointers
[SortedArenaList::BucketCount
];
232 // Single result list.
236 AutoGatherSweptArenas(JS::Zone
* zone
, AllocKind kind
);
237 ~AutoGatherSweptArenas();
239 Arena
* sweptArenas() const;
242 enum class ShouldCheckThresholds
{
243 DontCheckThresholds
= 0,
247 // For each arena kind its free list is represented as the first span with free
248 // things. Initially all the spans are initialized as empty. After we find a new
249 // arena with available things we move its first free span into the list and set
250 // the arena as fully allocated. That way we do not need to update the arena
251 // after the initial allocation. When starting the GC we only move the head of
252 // the of the list of spans back to the arena only for the arena that was not
255 AllAllocKindArray
<FreeSpan
*> freeLists_
;
258 // Because the JITs can allocate from the free lists, they cannot be null.
259 // We use a placeholder FreeSpan that is empty (and wihout an associated
260 // Arena) so the JITs can fall back gracefully.
261 static FreeSpan emptySentinel
;
266 inline bool allEmpty() const;
267 inline bool isEmpty(AllocKind kind
) const;
272 MOZ_ALWAYS_INLINE TenuredCell
* allocate(AllocKind kind
);
274 inline void* setArenaAndAllocate(Arena
* arena
, AllocKind kind
);
276 inline void unmarkPreMarkedFreeCells(AllocKind kind
);
278 FreeSpan
** addressOfFreeList(AllocKind thingKind
) {
279 return &freeLists_
[thingKind
];
284 enum class ConcurrentUse
: uint32_t { None
, BackgroundFinalize
};
286 using ConcurrentUseState
=
287 mozilla::Atomic
<ConcurrentUse
, mozilla::SequentiallyConsistent
>;
291 // Whether this structure can be accessed by other threads.
292 UnprotectedData
<AllAllocKindArray
<ConcurrentUseState
>> concurrentUseState_
;
294 MainThreadData
<FreeLists
> freeLists_
;
296 /* The main list of arenas for each alloc kind. */
297 MainThreadOrGCTaskData
<AllAllocKindArray
<ArenaList
>> arenaLists_
;
300 * Arenas which are currently being collected. The collector can move arenas
301 * from arenaLists_ here and back again at various points in collection.
303 MainThreadOrGCTaskData
<AllAllocKindArray
<ArenaList
>> collectingArenaLists_
;
305 // Arena lists which have yet to be swept, but need additional foreground
306 // processing before they are swept.
307 MainThreadData
<Arena
*> gcCompactPropMapArenasToUpdate
;
308 MainThreadData
<Arena
*> gcNormalPropMapArenasToUpdate
;
310 // The list of empty arenas which are collected during the sweep phase and
311 // released at the end of sweeping every sweep group.
312 MainThreadOrGCTaskData
<Arena
*> savedEmptyArenas
;
315 explicit ArenaLists(JS::Zone
* zone
);
318 FreeLists
& freeLists() { return freeLists_
.ref(); }
319 const FreeLists
& freeLists() const { return freeLists_
.ref(); }
321 FreeSpan
** addressOfFreeList(AllocKind thingKind
) {
322 return freeLists_
.refNoCheck().addressOfFreeList(thingKind
);
325 inline Arena
* getFirstArena(AllocKind thingKind
) const;
326 inline Arena
* getFirstCollectingArena(AllocKind thingKind
) const;
327 inline Arena
* getArenaAfterCursor(AllocKind thingKind
) const;
329 inline bool arenaListsAreEmpty() const;
331 inline bool doneBackgroundFinalize(AllocKind kind
) const;
332 inline bool needBackgroundFinalizeWait(AllocKind kind
) const;
334 /* Clear the free lists so we won't try to allocate from swept arenas. */
335 inline void clearFreeLists();
337 inline void unmarkPreMarkedFreeCells();
339 MOZ_ALWAYS_INLINE TenuredCell
* allocateFromFreeList(AllocKind thingKind
);
341 inline void checkEmptyFreeLists();
342 inline void checkEmptyArenaLists();
343 inline void checkEmptyFreeList(AllocKind kind
);
345 void checkEmptyArenaList(AllocKind kind
);
347 bool relocateArenas(Arena
*& relocatedListOut
, JS::GCReason reason
,
348 JS::SliceBudget
& sliceBudget
, gcstats::Statistics
& stats
);
350 void queueForegroundObjectsForSweep(JS::GCContext
* gcx
);
351 void queueForegroundThingsForSweep();
353 Arena
* takeSweptEmptyArenas();
355 void mergeFinalizedArenas(AllocKind thingKind
,
356 SortedArenaList
& finalizedArenas
);
358 void moveArenasToCollectingLists();
359 void mergeArenasFromCollectingLists();
361 void checkGCStateNotInUse();
362 void checkSweepStateNotInUse();
363 void checkNoArenasToUpdate();
364 void checkNoArenasToUpdateForKind(AllocKind kind
);
367 ArenaList
& arenaList(AllocKind i
) { return arenaLists_
.ref()[i
]; }
368 const ArenaList
& arenaList(AllocKind i
) const { return arenaLists_
.ref()[i
]; }
370 ArenaList
& collectingArenaList(AllocKind i
) {
371 return collectingArenaLists_
.ref()[i
];
373 const ArenaList
& collectingArenaList(AllocKind i
) const {
374 return collectingArenaLists_
.ref()[i
];
377 ConcurrentUseState
& concurrentUse(AllocKind i
) {
378 return concurrentUseState_
.ref()[i
];
380 ConcurrentUse
concurrentUse(AllocKind i
) const {
381 return concurrentUseState_
.ref()[i
];
384 inline JSRuntime
* runtime();
385 inline JSRuntime
* runtimeFromAnyThread();
387 void initBackgroundSweep(AllocKind thingKind
);
389 void* refillFreeListAndAllocate(AllocKind thingKind
,
390 ShouldCheckThresholds checkThresholds
);
392 friend class BackgroundUnmarkTask
;
393 friend class GCRuntime
;
394 friend class js::Nursery
;
395 friend class TenuringTracer
;
401 #endif /* gc_ArenaList_h */