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