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