1 // Copyright 2015 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_HEAP_SCAVENGER_H_ 6 #define V8_HEAP_SCAVENGER_H_ 7 8 #include "src/base/platform/condition-variable.h" 9 #include "src/heap/index-generator.h" 10 #include "src/heap/local-allocator.h" 11 #include "src/heap/objects-visiting.h" 12 #include "src/heap/parallel-work-item.h" 13 #include "src/heap/slot-set.h" 14 #include "src/heap/worklist.h" 15 16 namespace v8 { 17 namespace internal { 18 19 class OneshotBarrier; 20 class RootScavengeVisitor; 21 class Scavenger; 22 23 enum class CopyAndForwardResult { 24 SUCCESS_YOUNG_GENERATION, 25 SUCCESS_OLD_GENERATION, 26 FAILURE 27 }; 28 29 using ObjectAndSize = std::pair<HeapObject, int>; 30 using SurvivingNewLargeObjectsMap = 31 std::unordered_map<HeapObject, Map, Object::Hasher>; 32 using SurvivingNewLargeObjectMapEntry = std::pair<HeapObject, Map>; 33 34 constexpr int kEphemeronTableListSegmentSize = 128; 35 using EphemeronTableList = 36 Worklist<EphemeronHashTable, kEphemeronTableListSegmentSize>; 37 38 class ScavengerCollector; 39 40 class Scavenger { 41 public: 42 struct PromotionListEntry { 43 HeapObject heap_object; 44 Map map; 45 int size; 46 }; 47 48 class PromotionList { 49 public: 50 class View { 51 public: View(PromotionList * promotion_list,int task_id)52 View(PromotionList* promotion_list, int task_id) 53 : promotion_list_(promotion_list), task_id_(task_id) {} 54 55 inline void PushRegularObject(HeapObject object, int size); 56 inline void PushLargeObject(HeapObject object, Map map, int size); 57 inline bool IsEmpty(); 58 inline size_t LocalPushSegmentSize(); 59 inline bool Pop(struct PromotionListEntry* entry); 60 inline bool IsGlobalPoolEmpty(); 61 inline bool ShouldEagerlyProcessPromotionList(); 62 inline void FlushToGlobal(); 63 64 private: 65 PromotionList* promotion_list_; 66 int task_id_; 67 }; 68 PromotionList(int num_tasks)69 explicit PromotionList(int num_tasks) 70 : regular_object_promotion_list_(num_tasks), 71 large_object_promotion_list_(num_tasks) {} 72 73 inline void PushRegularObject(int task_id, HeapObject object, int size); 74 inline void PushLargeObject(int task_id, HeapObject object, Map map, 75 int size); 76 inline bool IsEmpty(); 77 inline size_t GlobalPoolSize() const; 78 inline size_t LocalPushSegmentSize(int task_id); 79 inline bool Pop(int task_id, struct PromotionListEntry* entry); 80 inline bool IsGlobalPoolEmpty(); 81 inline bool ShouldEagerlyProcessPromotionList(int task_id); 82 inline void FlushToGlobal(int task_id); 83 84 private: 85 static const int kRegularObjectPromotionListSegmentSize = 256; 86 static const int kLargeObjectPromotionListSegmentSize = 4; 87 88 using RegularObjectPromotionList = 89 Worklist<ObjectAndSize, kRegularObjectPromotionListSegmentSize>; 90 using LargeObjectPromotionList = 91 Worklist<PromotionListEntry, kLargeObjectPromotionListSegmentSize>; 92 93 RegularObjectPromotionList regular_object_promotion_list_; 94 LargeObjectPromotionList large_object_promotion_list_; 95 }; 96 97 static const int kCopiedListSegmentSize = 256; 98 99 using CopiedList = Worklist<ObjectAndSize, kCopiedListSegmentSize>; 100 Scavenger(ScavengerCollector* collector, Heap* heap, bool is_logging, 101 Worklist<MemoryChunk*, 64>* empty_chunks, CopiedList* copied_list, 102 PromotionList* promotion_list, 103 EphemeronTableList* ephemeron_table_list, int task_id); 104 105 // Entry point for scavenging an old generation page. For scavenging single 106 // objects see RootScavengingVisitor and ScavengeVisitor below. 107 void ScavengePage(MemoryChunk* page); 108 109 // Processes remaining work (=objects) after single objects have been 110 // manually scavenged using ScavengeObject or CheckAndScavengeObject. 111 void Process(JobDelegate* delegate = nullptr); 112 113 // Finalize the Scavenger. Needs to be called from the main thread. 114 void Finalize(); 115 void Flush(); 116 117 void AddEphemeronHashTable(EphemeronHashTable table); 118 bytes_copied()119 size_t bytes_copied() const { return copied_size_; } bytes_promoted()120 size_t bytes_promoted() const { return promoted_size_; } 121 122 private: 123 // Number of objects to process before interrupting for potentially waking 124 // up other tasks. 125 static const int kInterruptThreshold = 128; 126 static const int kInitialLocalPretenuringFeedbackCapacity = 256; 127 heap()128 inline Heap* heap() { return heap_; } 129 130 inline void PageMemoryFence(MaybeObject object); 131 132 void AddPageToSweeperIfNecessary(MemoryChunk* page); 133 134 // Potentially scavenges an object referenced from |slot| if it is 135 // indeed a HeapObject and resides in from space. 136 template <typename TSlot> 137 inline SlotCallbackResult CheckAndScavengeObject(Heap* heap, TSlot slot); 138 139 // Scavenges an object |object| referenced from slot |p|. |object| is required 140 // to be in from space. 141 template <typename THeapObjectSlot> 142 inline SlotCallbackResult ScavengeObject(THeapObjectSlot p, 143 HeapObject object); 144 145 // Copies |source| to |target| and sets the forwarding pointer in |source|. 146 V8_INLINE bool MigrateObject(Map map, HeapObject source, HeapObject target, 147 int size); 148 149 V8_INLINE SlotCallbackResult 150 RememberedSetEntryNeeded(CopyAndForwardResult result); 151 152 template <typename THeapObjectSlot> 153 V8_INLINE CopyAndForwardResult 154 SemiSpaceCopyObject(Map map, THeapObjectSlot slot, HeapObject object, 155 int object_size, ObjectFields object_fields); 156 157 template <typename THeapObjectSlot> 158 V8_INLINE CopyAndForwardResult PromoteObject(Map map, THeapObjectSlot slot, 159 HeapObject object, 160 int object_size, 161 ObjectFields object_fields); 162 163 template <typename THeapObjectSlot> 164 V8_INLINE SlotCallbackResult EvacuateObject(THeapObjectSlot slot, Map map, 165 HeapObject source); 166 167 V8_INLINE bool HandleLargeObject(Map map, HeapObject object, int object_size, 168 ObjectFields object_fields); 169 170 // Different cases for object evacuation. 171 template <typename THeapObjectSlot> 172 V8_INLINE SlotCallbackResult 173 EvacuateObjectDefault(Map map, THeapObjectSlot slot, HeapObject object, 174 int object_size, ObjectFields object_fields); 175 176 template <typename THeapObjectSlot> 177 inline SlotCallbackResult EvacuateThinString(Map map, THeapObjectSlot slot, 178 ThinString object, 179 int object_size); 180 181 template <typename THeapObjectSlot> 182 inline SlotCallbackResult EvacuateShortcutCandidate(Map map, 183 THeapObjectSlot slot, 184 ConsString object, 185 int object_size); 186 187 void IterateAndScavengePromotedObject(HeapObject target, Map map, int size); 188 void RememberPromotedEphemeron(EphemeronHashTable table, int index); 189 190 ScavengerCollector* const collector_; 191 Heap* const heap_; 192 Worklist<MemoryChunk*, 64>::View empty_chunks_; 193 PromotionList::View promotion_list_; 194 CopiedList::View copied_list_; 195 EphemeronTableList::View ephemeron_table_list_; 196 Heap::PretenuringFeedbackMap local_pretenuring_feedback_; 197 size_t copied_size_; 198 size_t promoted_size_; 199 EvacuationAllocator allocator_; 200 SurvivingNewLargeObjectsMap surviving_new_large_objects_; 201 202 EphemeronRememberedSet ephemeron_remembered_set_; 203 const bool is_logging_; 204 const bool is_incremental_marking_; 205 const bool is_compacting_; 206 207 friend class IterateAndScavengePromotedObjectsVisitor; 208 friend class RootScavengeVisitor; 209 friend class ScavengeVisitor; 210 }; 211 212 // Helper class for turning the scavenger into an object visitor that is also 213 // filtering out non-HeapObjects and objects which do not reside in new space. 214 class RootScavengeVisitor final : public RootVisitor { 215 public: 216 explicit RootScavengeVisitor(Scavenger* scavenger); 217 218 void VisitRootPointer(Root root, const char* description, 219 FullObjectSlot p) final; 220 void VisitRootPointers(Root root, const char* description, 221 FullObjectSlot start, FullObjectSlot end) final; 222 223 private: 224 void ScavengePointer(FullObjectSlot p); 225 226 Scavenger* const scavenger_; 227 }; 228 229 class ScavengeVisitor final : public NewSpaceVisitor<ScavengeVisitor> { 230 public: 231 explicit ScavengeVisitor(Scavenger* scavenger); 232 233 V8_INLINE void VisitPointers(HeapObject host, ObjectSlot start, 234 ObjectSlot end) final; 235 236 V8_INLINE void VisitPointers(HeapObject host, MaybeObjectSlot start, 237 MaybeObjectSlot end) final; 238 239 V8_INLINE void VisitCodeTarget(Code host, RelocInfo* rinfo) final; 240 V8_INLINE void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final; 241 V8_INLINE int VisitEphemeronHashTable(Map map, EphemeronHashTable object); 242 V8_INLINE int VisitJSArrayBuffer(Map map, JSArrayBuffer object); 243 244 private: 245 template <typename TSlot> 246 V8_INLINE void VisitHeapObjectImpl(TSlot slot, HeapObject heap_object); 247 248 template <typename TSlot> 249 V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end); 250 251 Scavenger* const scavenger_; 252 }; 253 254 class ScavengerCollector { 255 public: 256 static const int kMaxScavengerTasks = 8; 257 static const int kMainThreadId = 0; 258 259 explicit ScavengerCollector(Heap* heap); 260 261 void CollectGarbage(); 262 263 private: 264 class JobTask : public v8::JobTask { 265 public: 266 explicit JobTask( 267 ScavengerCollector* outer, 268 std::vector<std::unique_ptr<Scavenger>>* scavengers, 269 std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> memory_chunks, 270 Scavenger::CopiedList* copied_list, 271 Scavenger::PromotionList* promotion_list); 272 273 void Run(JobDelegate* delegate) override; 274 size_t GetMaxConcurrency(size_t worker_count) const override; 275 276 private: 277 void ProcessItems(JobDelegate* delegate, Scavenger* scavenger); 278 void ConcurrentScavengePages(Scavenger* scavenger); 279 280 ScavengerCollector* outer_; 281 282 std::vector<std::unique_ptr<Scavenger>>* scavengers_; 283 std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> memory_chunks_; 284 std::atomic<size_t> remaining_memory_chunks_{0}; 285 IndexGenerator generator_; 286 287 Scavenger::CopiedList* copied_list_; 288 Scavenger::PromotionList* promotion_list_; 289 }; 290 291 void MergeSurvivingNewLargeObjects( 292 const SurvivingNewLargeObjectsMap& objects); 293 294 int NumberOfScavengeTasks(); 295 296 void ProcessWeakReferences(EphemeronTableList* ephemeron_table_list); 297 void ClearYoungEphemerons(EphemeronTableList* ephemeron_table_list); 298 void ClearOldEphemerons(); 299 void HandleSurvivingNewLargeObjects(); 300 301 void SweepArrayBufferExtensions(); 302 303 void IterateStackAndScavenge( 304 RootScavengeVisitor* root_scavenge_visitor, 305 std::vector<std::unique_ptr<Scavenger>>* scavengers, int main_thread_id); 306 307 Isolate* const isolate_; 308 Heap* const heap_; 309 SurvivingNewLargeObjectsMap surviving_new_large_objects_; 310 311 friend class Scavenger; 312 }; 313 314 } // namespace internal 315 } // namespace v8 316 317 #endif // V8_HEAP_SCAVENGER_H_ 318