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/. */
12 #include "mozilla/DebugOnly.h"
13 #include "mozilla/Maybe.h"
15 #include "gc/IteratorUtils.h"
16 #include "gc/Marking.h"
18 #include "vm/Runtime.h"
20 #include "gc/ArenaList-inl.h"
24 class AutoAssertEmptyNursery
;
30 explicit ArenaListIter(Arena
* head
) : arena(head
) {}
31 bool done() const { return !arena
; }
41 operator Arena
*() const { return get(); }
42 Arena
* operator->() const { return get(); }
45 // Iterate all arenas in a zone of the specified kind, for use by the GC.
47 // Since the GC never iterates arenas during foreground sweeping we can skip
48 // traversing foreground swept arenas.
49 class ArenaIterInGC
: public ChainedIterator
<ArenaListIter
, 2> {
51 ArenaIterInGC(JS::Zone
* zone
, AllocKind kind
)
52 : ChainedIterator(zone
->arenas
.getFirstArena(kind
),
53 zone
->arenas
.getFirstCollectingArena(kind
)) {
55 MOZ_ASSERT(JS::RuntimeHeapIsMajorCollecting());
56 GCRuntime
& gc
= zone
->runtimeFromMainThread()->gc
;
57 MOZ_ASSERT(!gc
.maybeGetForegroundFinalizedArenas(zone
, kind
));
62 // Iterate all arenas in a zone of the specified kind. May be called at any
65 // Most uses of this happen when we are not in incremental GC but the debugger
66 // can iterate scripts at any time.
67 class ArenaIter
: public AutoGatherSweptArenas
,
68 public ChainedIterator
<ArenaListIter
, 3> {
70 ArenaIter(JS::Zone
* zone
, AllocKind kind
)
71 : AutoGatherSweptArenas(zone
, kind
),
72 ChainedIterator(zone
->arenas
.getFirstArena(kind
),
73 zone
->arenas
.getFirstCollectingArena(kind
),
78 size_t firstThingOffset
;
83 mozilla::DebugOnly
<JS::TraceKind
> traceKind
;
85 // Upon entry, |thing| points to any thing (free or used) and finds the
86 // first used thing, which may be |thing|.
90 // Note: if |span| is empty, this test will fail, which is what we want
91 // -- |span| being empty means that we're past the end of the last free
92 // thing, all the remaining things in the arena are used, and we'll
93 // never need to move forward.
94 if (thing
== span
.first
) {
95 thing
= span
.last
+ thingSize
;
96 span
= *span
.nextSpan(arenaAddr
);
101 explicit ArenaCellIter(Arena
* arena
) {
103 AllocKind kind
= arena
->getAllocKind();
104 firstThingOffset
= Arena::firstThingOffset(kind
);
105 thingSize
= Arena::thingSize(kind
);
106 traceKind
= MapAllocToTraceKind(kind
);
108 span
= *arena
->getFirstFreeSpan();
109 thing
= firstThingOffset
;
114 MOZ_ASSERT(thing
<= ArenaSize
);
115 return thing
== ArenaSize
;
118 TenuredCell
* get() const {
120 return reinterpret_cast<TenuredCell
*>(uintptr_t(arenaAddr
) + thing
);
123 template <typename T
>
126 MOZ_ASSERT(JS::MapTypeToTraceKind
<T
>::kind
== traceKind
);
127 return reinterpret_cast<T
*>(get());
133 if (thing
< ArenaSize
) {
138 operator TenuredCell
*() const { return get(); }
139 TenuredCell
* operator->() const { return get(); }
142 template <typename T
>
143 class ZoneAllCellIter
;
146 class ZoneAllCellIter
<TenuredCell
> {
147 mozilla::Maybe
<NestedIterator
<ArenaIter
, ArenaCellIter
>> iter
;
148 mozilla::Maybe
<JS::AutoAssertNoGC
> nogc
;
151 // For use when a subclass wants to insert some setup before init().
152 ZoneAllCellIter() = default;
154 void init(JS::Zone
* zone
, AllocKind kind
) {
155 MOZ_ASSERT_IF(IsNurseryAllocable(kind
),
156 (zone
->isAtomsZone() ||
157 zone
->runtimeFromMainThread()->gc
.nursery().isEmpty()));
158 initForTenuredIteration(zone
, kind
);
161 void initForTenuredIteration(JS::Zone
* zone
, AllocKind kind
) {
162 JSRuntime
* rt
= zone
->runtimeFromAnyThread();
164 // If called from outside a GC, ensure that the heap is in a state
165 // that allows us to iterate.
166 if (!JS::RuntimeHeapIsBusy()) {
167 // Assert that no GCs can occur while a ZoneAllCellIter is live.
171 // We have a single-threaded runtime, so there's no need to protect
172 // against other threads iterating or allocating. However, we do have
173 // background finalization; we may have to wait for this to finish if
174 // it's currently active.
175 if (IsBackgroundFinalized(kind
) &&
176 zone
->arenas
.needBackgroundFinalizeWait(kind
)) {
177 rt
->gc
.waitBackgroundSweepEnd();
179 iter
.emplace(zone
, kind
);
183 ZoneAllCellIter(JS::Zone
* zone
, AllocKind kind
) {
184 // If we are iterating a nursery-allocated kind then we need to
185 // evict first so that we can see all things.
186 if (IsNurseryAllocable(kind
)) {
187 zone
->runtimeFromMainThread()->gc
.evictNursery();
193 ZoneAllCellIter(JS::Zone
* zone
, AllocKind kind
,
194 const js::gc::AutoAssertEmptyNursery
&) {
195 // No need to evict the nursery. (This constructor is known statically
200 bool done() const { return iter
->done(); }
202 template <typename T
>
204 return iter
->ref().as
<T
>();
207 TenuredCell
* getCell() const { return iter
->get(); }
209 void next() { iter
->next(); }
212 /* clang-format off */
214 // Iterator over the cells in a Zone, where the GC type (JSString, JSObject) is
215 // known, for a single AllocKind. Example usages:
217 // for (auto obj = zone->cellIter<JSObject>(AllocKind::OBJECT0); !obj.done(); obj.next()) {
221 // for (auto script = zone->cellIter<JSScript>(); !script.done(); script.next()) {
222 // f(script->code());
225 // As this code demonstrates, you can use 'script' as if it were a JSScript*.
226 // Its actual type is ZoneAllCellIter<JSScript>, but for most purposes it will
227 // autoconvert to JSScript*.
229 // Note that in the JSScript case, ZoneAllCellIter is able to infer the AllocKind
230 // from the type 'JSScript', whereas in the JSObject case, the kind must be
231 // given (because there are multiple AllocKinds for objects).
233 // Also, the static rooting hazard analysis knows that the JSScript case will
234 // not GC during construction. The JSObject case needs to GC, or more precisely
235 // to empty the nursery and clear out the store buffer, so that it can see all
236 // objects to iterate over (the nursery is not iterable) and remove the
237 // possibility of having pointers from the store buffer to data hanging off
238 // stuff we're iterating over that we are going to delete. (The latter should
239 // not be a problem, since such instances should be using RelocatablePtr do
240 // remove themselves from the store buffer on deletion, but currently for
241 // subtle reasons that isn't good enough.)
243 // If the iterator is used within a GC, then there is no need to evict the
244 // nursery (again). You may select a variant that will skip the eviction either
245 // by specializing on a GCType that is never allocated in the nursery, or
246 // explicitly by passing in a trailing AutoAssertEmptyNursery argument.
248 // NOTE: This class can return items that are about to be swept/finalized.
249 // You must not keep pointers to such items across GCs. Use
250 // ZoneCellIter below to filter these out.
252 // NOTE: This class also does not read barrier returned items, so may return
253 // gray cells. You must not store such items anywhere on the heap without
254 // gray-unmarking them. Use ZoneCellIter to automatically unmark them.
256 /* clang-format on */
257 template <typename GCType
>
258 class ZoneAllCellIter
: public ZoneAllCellIter
<TenuredCell
> {
260 // Non-nursery allocated (equivalent to having an entry in
261 // MapTypeToAllocKind). The template declaration here is to discard this
262 // constructor overload if MapTypeToAllocKind<GCType>::kind does not
263 // exist. Note that there will be no remaining overloads that will work, which
264 // makes sense given that you haven't specified which of the AllocKinds to use
267 // If we later add a nursery allocable GCType with a single AllocKind, we will
268 // want to add an overload of this constructor that does the right thing (ie,
269 // it empties the nursery before iterating.)
270 explicit ZoneAllCellIter(JS::Zone
* zone
) : ZoneAllCellIter
<TenuredCell
>() {
271 init(zone
, MapTypeToAllocKind
<GCType
>::kind
);
274 // Non-nursery allocated, nursery is known to be empty: same behavior as
276 ZoneAllCellIter(JS::Zone
* zone
, const js::gc::AutoAssertEmptyNursery
&)
277 : ZoneAllCellIter(zone
) {}
279 // Arbitrary kind, which will be assumed to be nursery allocable (and
280 // therefore the nursery will be emptied before iterating.)
281 ZoneAllCellIter(JS::Zone
* zone
, AllocKind kind
)
282 : ZoneAllCellIter
<TenuredCell
>(zone
, kind
) {}
284 // Arbitrary kind, which will be assumed to be nursery allocable, but the
285 // nursery is known to be empty already: same behavior as non-nursery types.
286 ZoneAllCellIter(JS::Zone
* zone
, AllocKind kind
,
287 const js::gc::AutoAssertEmptyNursery
& empty
)
288 : ZoneAllCellIter
<TenuredCell
>(zone
, kind
, empty
) {}
290 GCType
* get() const { return ZoneAllCellIter
<TenuredCell
>::get
<GCType
>(); }
291 operator GCType
*() const { return get(); }
292 GCType
* operator->() const { return get(); }
295 // Like the above class but filter out cells that are about to be finalized.
296 // Also, read barrier all cells returned (unless the Unbarriered variants are
297 // used) to prevent gray cells from escaping.
298 template <typename T
>
299 class ZoneCellIter
: protected ZoneAllCellIter
<T
> {
300 using Base
= ZoneAllCellIter
<T
>;
304 * The same constructors as above.
306 explicit ZoneCellIter(JS::Zone
* zone
) : ZoneAllCellIter
<T
>(zone
) {
309 ZoneCellIter(JS::Zone
* zone
, const js::gc::AutoAssertEmptyNursery
& empty
)
310 : ZoneAllCellIter
<T
>(zone
, empty
) {
313 ZoneCellIter(JS::Zone
* zone
, AllocKind kind
)
314 : ZoneAllCellIter
<T
>(zone
, kind
) {
317 ZoneCellIter(JS::Zone
* zone
, AllocKind kind
,
318 const js::gc::AutoAssertEmptyNursery
& empty
)
319 : ZoneAllCellIter
<T
>(zone
, kind
, empty
) {
326 ZoneAllCellIter
<T
>::next();
330 TenuredCell
* getCell() const {
331 TenuredCell
* cell
= Base::getCell();
333 // This can result in a new reference being created to an object that an
334 // ongoing incremental GC may find to be unreachable, so we may need a
336 JSRuntime
* rt
= cell
->runtimeFromAnyThread();
337 if (!JS::RuntimeHeapIsCollecting(rt
->heapState())) {
338 JS::TraceKind traceKind
= JS::MapTypeToTraceKind
<T
>::kind
;
339 ExposeGCThingToActiveJS(JS::GCCellPtr(cell
, traceKind
));
345 T
* get() const { return reinterpret_cast<T
*>(getCell()); }
347 TenuredCell
* unbarrieredGetCell() const { return Base::getCell(); }
348 T
* unbarrieredGet() const { return Base::get(); }
349 operator T
*() const { return get(); }
350 T
* operator->() const { return get(); }
354 while (!ZoneAllCellIter
<T
>::done()) {
355 T
* current
= ZoneAllCellIter
<T
>::get();
356 if (!IsAboutToBeFinalizedUnbarriered(current
)) {
359 ZoneAllCellIter
<T
>::next();
364 } // namespace js::gc
366 #endif /* gc_GC_inl_h */