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 /* 8 * GC-internal definitions of ArenaList and associated heap data structures. 9 */ 10 11 #ifndef gc_ArenaList_h 12 #define gc_ArenaList_h 13 14 #include "gc/AllocKind.h" 15 #include "js/GCAPI.h" 16 #include "js/HeapAPI.h" 17 #include "js/SliceBudget.h" 18 #include "js/TypeDecls.h" 19 #include "threading/ProtectedData.h" 20 21 namespace js { 22 23 class Nursery; 24 class TenuringTracer; 25 26 namespace gcstats { 27 struct Statistics; 28 } 29 30 namespace gc { 31 32 class Arena; 33 struct FinalizePhase; 34 class FreeSpan; 35 class TenuredCell; 36 37 /* 38 * A single segment of a SortedArenaList. Each segment has a head and a tail, 39 * which track the start and end of a segment for O(1) append and concatenation. 40 */ 41 struct SortedArenaListSegment { 42 Arena* head; 43 Arena** tailp; 44 clearSortedArenaListSegment45 void clear() { 46 head = nullptr; 47 tailp = &head; 48 } 49 isEmptySortedArenaListSegment50 bool isEmpty() const { return tailp == &head; } 51 52 // Appends |arena| to this segment. 53 inline void append(Arena* arena); 54 55 // Points the tail of this segment at |arena|, which may be null. Note 56 // that this does not change the tail itself, but merely which arena 57 // follows it. This essentially turns the tail into a cursor (see also the 58 // description of ArenaList), but from the perspective of a SortedArenaList 59 // this makes no difference. linkToSortedArenaListSegment60 void linkTo(Arena* arena) { *tailp = arena; } 61 }; 62 63 /* 64 * Arena lists have a head and a cursor. The cursor conceptually lies on arena 65 * boundaries, i.e. before the first arena, between two arenas, or after the 66 * last arena. 67 * 68 * Arenas are usually sorted in order of increasing free space, with the cursor 69 * following the Arena currently being allocated from. This ordering should not 70 * be treated as an invariant, however, as the free lists may be cleared, 71 * leaving arenas previously used for allocation partially full. Sorting order 72 * is restored during sweeping. 73 74 * Arenas following the cursor should not be full. 75 */ 76 class ArenaList { 77 // The cursor is implemented via an indirect pointer, |cursorp_|, to allow 78 // for efficient list insertion at the cursor point and other list 79 // manipulations. 80 // 81 // - If the list is empty: |head| is null, |cursorp_| points to |head|, and 82 // therefore |*cursorp_| is null. 83 // 84 // - If the list is not empty: |head| is non-null, and... 85 // 86 // - If the cursor is at the start of the list: |cursorp_| points to 87 // |head|, and therefore |*cursorp_| points to the first arena. 88 // 89 // - If cursor is at the end of the list: |cursorp_| points to the |next| 90 // field of the last arena, and therefore |*cursorp_| is null. 91 // 92 // - If the cursor is at neither the start nor the end of the list: 93 // |cursorp_| points to the |next| field of the arena preceding the 94 // cursor, and therefore |*cursorp_| points to the arena following the 95 // cursor. 96 // 97 // |cursorp_| is never null. 98 // 99 Arena* head_; 100 Arena** cursorp_; 101 102 inline void copy(const ArenaList& other); 103 104 public: 105 inline ArenaList(); 106 inline ArenaList(const ArenaList& other); 107 108 inline ArenaList& operator=(const ArenaList& other); 109 110 inline explicit ArenaList(const SortedArenaListSegment& segment); 111 112 inline void check() const; 113 114 inline void clear(); 115 inline ArenaList copyAndClear(); 116 inline bool isEmpty() const; 117 118 // This returns nullptr if the list is empty. 119 inline Arena* head() const; 120 121 inline bool isCursorAtHead() const; 122 inline bool isCursorAtEnd() const; 123 124 inline void moveCursorToEnd(); 125 126 // This can return nullptr. 127 inline Arena* arenaAfterCursor() const; 128 129 // This returns the arena after the cursor and moves the cursor past it. 130 inline Arena* takeNextArena(); 131 132 // This does two things. 133 // - Inserts |a| at the cursor. 134 // - Leaves the cursor sitting just before |a|, if |a| is not full, or just 135 // after |a|, if |a| is full. 136 inline void insertAtCursor(Arena* a); 137 138 // Inserts |a| at the cursor, then moves the cursor past it. 139 inline void insertBeforeCursor(Arena* a); 140 141 // This inserts |other|, which must be full, at the cursor of |this|. 142 inline ArenaList& insertListWithCursorAtEnd(const ArenaList& other); 143 144 Arena* removeRemainingArenas(Arena** arenap); 145 Arena** pickArenasToRelocate(size_t& arenaTotalOut, size_t& relocTotalOut); 146 Arena* relocateArenas(Arena* toRelocate, Arena* relocated, 147 js::SliceBudget& sliceBudget, 148 gcstats::Statistics& stats); 149 }; 150 151 /* 152 * A class that holds arenas in sorted order by appending arenas to specific 153 * segments. Each segment has a head and a tail, which can be linked up to 154 * other segments to create a contiguous ArenaList. 155 */ 156 class SortedArenaList { 157 public: 158 // The minimum size, in bytes, of a GC thing. 159 static const size_t MinThingSize = 16; 160 161 static_assert(ArenaSize <= 4096, 162 "When increasing the Arena size, please consider how" 163 " this will affect the size of a SortedArenaList."); 164 165 static_assert(MinThingSize >= 16, 166 "When decreasing the minimum thing size, please consider" 167 " how this will affect the size of a SortedArenaList."); 168 169 private: 170 // The maximum number of GC things that an arena can hold. 171 static const size_t MaxThingsPerArena = 172 (ArenaSize - ArenaHeaderSize) / MinThingSize; 173 174 size_t thingsPerArena_; 175 SortedArenaListSegment segments[MaxThingsPerArena + 1]; 176 177 // Convenience functions to get the nth head and tail. headAt(size_t n)178 Arena* headAt(size_t n) { return segments[n].head; } tailAt(size_t n)179 Arena** tailAt(size_t n) { return segments[n].tailp; } 180 181 public: 182 inline explicit SortedArenaList(size_t thingsPerArena = MaxThingsPerArena); 183 184 inline void setThingsPerArena(size_t thingsPerArena); 185 186 // Resets the first |thingsPerArena| segments of this list for further use. 187 inline void reset(size_t thingsPerArena = MaxThingsPerArena); 188 189 // Inserts an arena, which has room for |nfree| more things, in its segment. 190 inline void insertAt(Arena* arena, size_t nfree); 191 192 // Remove all empty arenas, inserting them as a linked list. 193 inline void extractEmpty(Arena** empty); 194 195 // Links up the tail of each non-empty segment to the head of the next 196 // non-empty segment, creating a contiguous list that is returned as an 197 // ArenaList. This is not a destructive operation: neither the head nor tail 198 // of any segment is modified. However, note that the Arenas in the 199 // resulting ArenaList should be treated as read-only unless the 200 // SortedArenaList is no longer needed: inserting or removing arenas would 201 // invalidate the SortedArenaList. 202 inline ArenaList toArenaList(); 203 }; 204 205 enum class ShouldCheckThresholds { 206 DontCheckThresholds = 0, 207 CheckThresholds = 1 208 }; 209 210 // For each arena kind its free list is represented as the first span with free 211 // things. Initially all the spans are initialized as empty. After we find a new 212 // arena with available things we move its first free span into the list and set 213 // the arena as fully allocated. That way we do not need to update the arena 214 // after the initial allocation. When starting the GC we only move the head of 215 // the of the list of spans back to the arena only for the arena that was not 216 // fully allocated. 217 class FreeLists { 218 AllAllocKindArray<FreeSpan*> freeLists_; 219 220 public: 221 // Because the JITs can allocate from the free lists, they cannot be null. 222 // We use a placeholder FreeSpan that is empty (and wihout an associated 223 // Arena) so the JITs can fall back gracefully. 224 static FreeSpan emptySentinel; 225 226 FreeLists(); 227 228 #ifdef DEBUG 229 inline bool allEmpty() const; 230 inline bool isEmpty(AllocKind kind) const; 231 #endif 232 233 inline void clear(); 234 235 MOZ_ALWAYS_INLINE TenuredCell* allocate(AllocKind kind); 236 237 inline TenuredCell* setArenaAndAllocate(Arena* arena, AllocKind kind); 238 239 inline void unmarkPreMarkedFreeCells(AllocKind kind); 240 addressOfFreeList(AllocKind thingKind)241 FreeSpan** addressOfFreeList(AllocKind thingKind) { 242 return &freeLists_[thingKind]; 243 } 244 }; 245 246 class ArenaLists { 247 enum class ConcurrentUse : uint32_t { 248 None, 249 BackgroundFinalize, 250 ParallelAlloc 251 }; 252 253 using ConcurrentUseState = 254 mozilla::Atomic<ConcurrentUse, mozilla::SequentiallyConsistent>; 255 256 JS::Zone* zone_; 257 258 // Whether this structure can be accessed by other threads. 259 UnprotectedData<AllAllocKindArray<ConcurrentUseState>> concurrentUseState_; 260 261 ZoneData<FreeLists> freeLists_; 262 263 ArenaListData<AllAllocKindArray<ArenaList>> arenaLists_; 264 265 /* For each arena kind, a list of arenas remaining to be swept. */ 266 MainThreadOrGCTaskData<AllAllocKindArray<Arena*>> arenasToSweep_; 267 268 /* During incremental sweeping, a list of the arenas already swept. */ 269 ZoneOrGCTaskData<AllocKind> incrementalSweptArenaKind; 270 ZoneOrGCTaskData<ArenaList> incrementalSweptArenas; 271 272 // Arena lists which have yet to be swept, but need additional foreground 273 // processing before they are swept. 274 ZoneData<Arena*> gcShapeArenasToUpdate; 275 ZoneData<Arena*> gcAccessorShapeArenasToUpdate; 276 ZoneData<Arena*> gcScriptArenasToUpdate; 277 ZoneData<Arena*> gcObjectGroupArenasToUpdate; 278 279 // The list of empty arenas which are collected during the sweep phase and 280 // released at the end of sweeping every sweep group. 281 ZoneData<Arena*> savedEmptyArenas; 282 283 public: 284 explicit ArenaLists(JS::Zone* zone); 285 ~ArenaLists(); 286 freeLists()287 FreeLists& freeLists() { return freeLists_.ref(); } freeLists()288 const FreeLists& freeLists() const { return freeLists_.ref(); } 289 addressOfFreeList(AllocKind thingKind)290 FreeSpan** addressOfFreeList(AllocKind thingKind) { 291 return freeLists_.refNoCheck().addressOfFreeList(thingKind); 292 } 293 294 inline Arena* getFirstArena(AllocKind thingKind) const; 295 inline Arena* getFirstArenaToSweep(AllocKind thingKind) const; 296 inline Arena* getFirstSweptArena(AllocKind thingKind) const; 297 inline Arena* getArenaAfterCursor(AllocKind thingKind) const; 298 299 inline bool arenaListsAreEmpty() const; 300 301 inline void unmarkAll(); 302 303 inline bool doneBackgroundFinalize(AllocKind kind) const; 304 inline bool needBackgroundFinalizeWait(AllocKind kind) const; 305 306 /* Clear the free lists so we won't try to allocate from swept arenas. */ 307 inline void clearFreeLists(); 308 309 inline void unmarkPreMarkedFreeCells(); 310 311 MOZ_ALWAYS_INLINE TenuredCell* allocateFromFreeList(AllocKind thingKind); 312 313 /* Moves all arenas from |fromArenaLists| into |this|. */ 314 void adoptArenas(ArenaLists* fromArenaLists, bool targetZoneIsCollecting); 315 316 inline void checkEmptyFreeLists(); 317 inline void checkEmptyArenaLists(); 318 inline void checkEmptyFreeList(AllocKind kind); 319 320 void checkEmptyArenaList(AllocKind kind); 321 322 bool relocateArenas(Arena*& relocatedListOut, JS::GCReason reason, 323 js::SliceBudget& sliceBudget, gcstats::Statistics& stats); 324 325 void queueForegroundObjectsForSweep(JSFreeOp* fop); 326 void queueForegroundThingsForSweep(); 327 328 void releaseForegroundSweptEmptyArenas(); 329 330 bool foregroundFinalize(JSFreeOp* fop, AllocKind thingKind, 331 js::SliceBudget& sliceBudget, 332 SortedArenaList& sweepList); 333 static void backgroundFinalize(JSFreeOp* fop, Arena* listHead, Arena** empty); 334 335 void setParallelAllocEnabled(bool enabled); 336 337 void checkSweepStateNotInUse(); 338 void checkNoArenasToUpdate(); 339 void checkNoArenasToUpdateForKind(AllocKind kind); 340 341 private: arenaList(AllocKind i)342 ArenaList& arenaList(AllocKind i) { return arenaLists_.ref()[i]; } arenaList(AllocKind i)343 const ArenaList& arenaList(AllocKind i) const { return arenaLists_.ref()[i]; } 344 concurrentUse(AllocKind i)345 ConcurrentUseState& concurrentUse(AllocKind i) { 346 return concurrentUseState_.ref()[i]; 347 } concurrentUse(AllocKind i)348 ConcurrentUse concurrentUse(AllocKind i) const { 349 return concurrentUseState_.ref()[i]; 350 } 351 arenasToSweep(AllocKind i)352 Arena*& arenasToSweep(AllocKind i) { return arenasToSweep_.ref()[i]; } arenasToSweep(AllocKind i)353 Arena* arenasToSweep(AllocKind i) const { return arenasToSweep_.ref()[i]; } 354 355 inline JSRuntime* runtime(); 356 inline JSRuntime* runtimeFromAnyThread(); 357 358 inline void queueForForegroundSweep(JSFreeOp* fop, 359 const FinalizePhase& phase); 360 inline void queueForBackgroundSweep(JSFreeOp* fop, 361 const FinalizePhase& phase); 362 inline void queueForForegroundSweep(AllocKind thingKind); 363 inline void queueForBackgroundSweep(AllocKind thingKind); 364 365 TenuredCell* refillFreeListAndAllocate(FreeLists& freeLists, 366 AllocKind thingKind, 367 ShouldCheckThresholds checkThresholds); 368 369 friend class GCRuntime; 370 friend class js::Nursery; 371 friend class js::TenuringTracer; 372 }; 373 374 } /* namespace gc */ 375 } /* namespace js */ 376 377 #endif /* gc_ArenaList_h */ 378