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/. */ 6 7 #ifndef gc_GC_inl_h 8 #define gc_GC_inl_h 9 10 #include "gc/GC.h" 11 12 #include "mozilla/DebugOnly.h" 13 #include "mozilla/Maybe.h" 14 15 #include "gc/IteratorUtils.h" 16 #include "gc/Zone.h" 17 #include "vm/Runtime.h" 18 19 #include "gc/ArenaList-inl.h" 20 21 namespace js { 22 namespace gc { 23 24 class AutoAssertEmptyNursery; 25 26 class ArenaListIter { 27 Arena* arena; 28 29 public: ArenaListIter(Arena * head)30 explicit ArenaListIter(Arena* head) : arena(head) {} done()31 bool done() const { return !arena; } get()32 Arena* get() const { 33 MOZ_ASSERT(!done()); 34 return arena; 35 } next()36 void next() { 37 MOZ_ASSERT(!done()); 38 arena = arena->next; 39 } 40 }; 41 42 class ArenaIter : public ChainedIterator<ArenaListIter, 4> { 43 public: ArenaIter(JS::Zone * zone,AllocKind kind)44 ArenaIter(JS::Zone* zone, AllocKind kind) 45 : ChainedIterator(zone->arenas.getFirstArena(kind), 46 zone->arenas.getFirstArenaToSweep(kind), 47 zone->arenas.getFirstSweptArena(kind), 48 zone->arenas.getFirstNewArenaInMarkPhase(kind)) {} 49 }; 50 51 class ArenaCellIter { 52 size_t firstThingOffset; 53 size_t thingSize; 54 Arena* arenaAddr; 55 FreeSpan span; 56 uint_fast16_t thing; 57 mozilla::DebugOnly<JS::TraceKind> traceKind; 58 59 // Upon entry, |thing| points to any thing (free or used) and finds the 60 // first used thing, which may be |thing|. settle()61 void settle() { 62 MOZ_ASSERT(!done()); 63 MOZ_ASSERT(thing); 64 // Note: if |span| is empty, this test will fail, which is what we want 65 // -- |span| being empty means that we're past the end of the last free 66 // thing, all the remaining things in the arena are used, and we'll 67 // never need to move forward. 68 if (thing == span.first) { 69 thing = span.last + thingSize; 70 span = *span.nextSpan(arenaAddr); 71 } 72 } 73 74 public: ArenaCellIter(Arena * arena)75 explicit ArenaCellIter(Arena* arena) { 76 MOZ_ASSERT(arena); 77 AllocKind kind = arena->getAllocKind(); 78 firstThingOffset = Arena::firstThingOffset(kind); 79 thingSize = Arena::thingSize(kind); 80 traceKind = MapAllocToTraceKind(kind); 81 arenaAddr = arena; 82 span = *arena->getFirstFreeSpan(); 83 thing = firstThingOffset; 84 settle(); 85 } 86 done()87 bool done() const { 88 MOZ_ASSERT(thing <= ArenaSize); 89 return thing == ArenaSize; 90 } 91 get()92 TenuredCell* get() const { 93 MOZ_ASSERT(!done()); 94 return reinterpret_cast<TenuredCell*>(uintptr_t(arenaAddr) + thing); 95 } 96 97 template <typename T> as()98 T* as() const { 99 MOZ_ASSERT(!done()); 100 MOZ_ASSERT(JS::MapTypeToTraceKind<T>::kind == traceKind); 101 return reinterpret_cast<T*>(get()); 102 } 103 next()104 void next() { 105 MOZ_ASSERT(!done()); 106 thing += thingSize; 107 if (thing < ArenaSize) { 108 settle(); 109 } 110 } 111 112 operator TenuredCell*() const { return get(); } 113 TenuredCell* operator->() const { return get(); } 114 }; 115 116 template <typename T> 117 class ZoneAllCellIter; 118 119 template <> 120 class ZoneAllCellIter<TenuredCell> { 121 mozilla::Maybe<NestedIterator<ArenaIter, ArenaCellIter>> iter; 122 mozilla::Maybe<JS::AutoAssertNoGC> nogc; 123 124 protected: 125 // For use when a subclass wants to insert some setup before init(). 126 ZoneAllCellIter() = default; 127 init(JS::Zone * zone,AllocKind kind)128 void init(JS::Zone* zone, AllocKind kind) { 129 MOZ_ASSERT_IF(IsNurseryAllocable(kind), 130 (zone->isAtomsZone() || 131 zone->runtimeFromMainThread()->gc.nursery().isEmpty())); 132 initForTenuredIteration(zone, kind); 133 } 134 initForTenuredIteration(JS::Zone * zone,AllocKind kind)135 void initForTenuredIteration(JS::Zone* zone, AllocKind kind) { 136 JSRuntime* rt = zone->runtimeFromAnyThread(); 137 138 // If called from outside a GC, ensure that the heap is in a state 139 // that allows us to iterate. 140 if (!JS::RuntimeHeapIsBusy()) { 141 // Assert that no GCs can occur while a ZoneAllCellIter is live. 142 nogc.emplace(); 143 } 144 145 // We have a single-threaded runtime, so there's no need to protect 146 // against other threads iterating or allocating. However, we do have 147 // background finalization; we may have to wait for this to finish if 148 // it's currently active. 149 if (IsBackgroundFinalized(kind) && 150 zone->arenas.needBackgroundFinalizeWait(kind)) { 151 rt->gc.waitBackgroundSweepEnd(); 152 } 153 iter.emplace(zone, kind); 154 } 155 156 public: ZoneAllCellIter(JS::Zone * zone,AllocKind kind)157 ZoneAllCellIter(JS::Zone* zone, AllocKind kind) { 158 // If we are iterating a nursery-allocated kind then we need to 159 // evict first so that we can see all things. 160 if (IsNurseryAllocable(kind)) { 161 zone->runtimeFromMainThread()->gc.evictNursery(); 162 } 163 164 init(zone, kind); 165 } 166 ZoneAllCellIter(JS::Zone * zone,AllocKind kind,const js::gc::AutoAssertEmptyNursery &)167 ZoneAllCellIter(JS::Zone* zone, AllocKind kind, 168 const js::gc::AutoAssertEmptyNursery&) { 169 // No need to evict the nursery. (This constructor is known statically 170 // to not GC.) 171 init(zone, kind); 172 } 173 done()174 bool done() const { return iter->done(); } 175 176 template <typename T> get()177 T* get() const { 178 return iter->ref().as<T>(); 179 } 180 getCell()181 TenuredCell* getCell() const { return iter->get(); } 182 next()183 void next() { iter->next(); } 184 }; 185 186 /* clang-format off */ 187 // 188 // Iterator over the cells in a Zone, where the GC type (JSString, JSObject) is 189 // known, for a single AllocKind. Example usages: 190 // 191 // for (auto obj = zone->cellIter<JSObject>(AllocKind::OBJECT0); !obj.done(); obj.next()) { 192 // ... 193 // } 194 // 195 // for (auto script = zone->cellIter<JSScript>(); !script.done(); script.next()) { 196 // f(script->code()); 197 // } 198 // 199 // As this code demonstrates, you can use 'script' as if it were a JSScript*. 200 // Its actual type is ZoneAllCellIter<JSScript>, but for most purposes it will 201 // autoconvert to JSScript*. 202 // 203 // Note that in the JSScript case, ZoneAllCellIter is able to infer the AllocKind 204 // from the type 'JSScript', whereas in the JSObject case, the kind must be 205 // given (because there are multiple AllocKinds for objects). 206 // 207 // Also, the static rooting hazard analysis knows that the JSScript case will 208 // not GC during construction. The JSObject case needs to GC, or more precisely 209 // to empty the nursery and clear out the store buffer, so that it can see all 210 // objects to iterate over (the nursery is not iterable) and remove the 211 // possibility of having pointers from the store buffer to data hanging off 212 // stuff we're iterating over that we are going to delete. (The latter should 213 // not be a problem, since such instances should be using RelocatablePtr do 214 // remove themselves from the store buffer on deletion, but currently for 215 // subtle reasons that isn't good enough.) 216 // 217 // If the iterator is used within a GC, then there is no need to evict the 218 // nursery (again). You may select a variant that will skip the eviction either 219 // by specializing on a GCType that is never allocated in the nursery, or 220 // explicitly by passing in a trailing AutoAssertEmptyNursery argument. 221 // 222 // NOTE: This class can return items that are about to be swept/finalized. 223 // You must not keep pointers to such items across GCs. Use 224 // ZoneCellIter below to filter these out. 225 // 226 // NOTE: This class also does not read barrier returned items, so may return 227 // gray cells. You must not store such items anywhere on the heap without 228 // gray-unmarking them. Use ZoneCellIter to automatically unmark them. 229 // 230 /* clang-format on */ 231 template <typename GCType> 232 class ZoneAllCellIter : public ZoneAllCellIter<TenuredCell> { 233 public: 234 // Non-nursery allocated (equivalent to having an entry in 235 // MapTypeToFinalizeKind). The template declaration here is to discard this 236 // constructor overload if MapTypeToFinalizeKind<GCType>::kind does not 237 // exist. Note that there will be no remaining overloads that will work, 238 // which makes sense given that you haven't specified which of the 239 // AllocKinds to use for GCType. 240 // 241 // If we later add a nursery allocable GCType with a single AllocKind, we 242 // will want to add an overload of this constructor that does the right 243 // thing (ie, it empties the nursery before iterating.) ZoneAllCellIter(JS::Zone * zone)244 explicit ZoneAllCellIter(JS::Zone* zone) : ZoneAllCellIter<TenuredCell>() { 245 init(zone, MapTypeToFinalizeKind<GCType>::kind); 246 } 247 248 // Non-nursery allocated, nursery is known to be empty: same behavior as 249 // above. ZoneAllCellIter(JS::Zone * zone,const js::gc::AutoAssertEmptyNursery &)250 ZoneAllCellIter(JS::Zone* zone, const js::gc::AutoAssertEmptyNursery&) 251 : ZoneAllCellIter(zone) {} 252 253 // Arbitrary kind, which will be assumed to be nursery allocable (and 254 // therefore the nursery will be emptied before iterating.) ZoneAllCellIter(JS::Zone * zone,AllocKind kind)255 ZoneAllCellIter(JS::Zone* zone, AllocKind kind) 256 : ZoneAllCellIter<TenuredCell>(zone, kind) {} 257 258 // Arbitrary kind, which will be assumed to be nursery allocable, but the 259 // nursery is known to be empty already: same behavior as non-nursery types. ZoneAllCellIter(JS::Zone * zone,AllocKind kind,const js::gc::AutoAssertEmptyNursery & empty)260 ZoneAllCellIter(JS::Zone* zone, AllocKind kind, 261 const js::gc::AutoAssertEmptyNursery& empty) 262 : ZoneAllCellIter<TenuredCell>(zone, kind, empty) {} 263 get()264 GCType* get() const { return ZoneAllCellIter<TenuredCell>::get<GCType>(); } 265 operator GCType*() const { return get(); } 266 GCType* operator->() const { return get(); } 267 }; 268 269 // Like the above class but filter out cells that are about to be finalized. 270 // Also, read barrier all cells returned (unless the Unbarriered variants are 271 // used) to prevent gray cells from escaping. 272 template <typename T> 273 class ZoneCellIter : protected ZoneAllCellIter<T> { 274 using Base = ZoneAllCellIter<T>; 275 276 public: 277 /* 278 * The same constructors as above. 279 */ ZoneCellIter(JS::Zone * zone)280 explicit ZoneCellIter(JS::Zone* zone) : ZoneAllCellIter<T>(zone) { 281 skipDying(); 282 } ZoneCellIter(JS::Zone * zone,const js::gc::AutoAssertEmptyNursery & empty)283 ZoneCellIter(JS::Zone* zone, const js::gc::AutoAssertEmptyNursery& empty) 284 : ZoneAllCellIter<T>(zone, empty) { 285 skipDying(); 286 } ZoneCellIter(JS::Zone * zone,AllocKind kind)287 ZoneCellIter(JS::Zone* zone, AllocKind kind) 288 : ZoneAllCellIter<T>(zone, kind) { 289 skipDying(); 290 } ZoneCellIter(JS::Zone * zone,AllocKind kind,const js::gc::AutoAssertEmptyNursery & empty)291 ZoneCellIter(JS::Zone* zone, AllocKind kind, 292 const js::gc::AutoAssertEmptyNursery& empty) 293 : ZoneAllCellIter<T>(zone, kind, empty) { 294 skipDying(); 295 } 296 297 using Base::done; 298 next()299 void next() { 300 ZoneAllCellIter<T>::next(); 301 skipDying(); 302 } 303 getCell()304 TenuredCell* getCell() const { 305 TenuredCell* cell = Base::getCell(); 306 307 // This can result in a new reference being created to an object that an 308 // ongoing incremental GC may find to be unreachable, so we may need a 309 // barrier here. 310 JSRuntime* rt = cell->runtimeFromAnyThread(); 311 if (!JS::RuntimeHeapIsCollecting(rt->heapState())) { 312 JS::TraceKind traceKind = JS::MapTypeToTraceKind<T>::kind; 313 ExposeGCThingToActiveJS(JS::GCCellPtr(cell, traceKind)); 314 } 315 316 return cell; 317 } 318 get()319 T* get() const { return reinterpret_cast<T*>(getCell()); } 320 unbarrieredGetCell()321 TenuredCell* unbarrieredGetCell() const { return Base::getCell(); } unbarrieredGet()322 T* unbarrieredGet() const { return Base::get(); } 323 operator T*() const { return get(); } 324 T* operator->() const { return get(); } 325 326 private: skipDying()327 void skipDying() { 328 while (!ZoneAllCellIter<T>::done()) { 329 T* current = ZoneAllCellIter<T>::get(); 330 if (!IsAboutToBeFinalizedUnbarriered(¤t)) { 331 return; 332 } 333 ZoneAllCellIter<T>::next(); 334 } 335 } 336 }; 337 338 } /* namespace gc */ 339 } /* namespace js */ 340 341 #endif /* gc_GC_inl_h */ 342