1 /* 2 * Copyright (c) 2025 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMMON_COMPONENTS_HEAP_COLLECTOR_MARKING_COLLECTOR_H 17 #define COMMON_COMPONENTS_HEAP_COLLECTOR_MARKING_COLLECTOR_H 18 19 #include <cstdint> 20 #include <map> 21 22 #include "common_components/heap/collector/collector.h" 23 #include "common_components/heap/collector/collector_resources.h" 24 #include "common_components/common/mark_work_stack.h" 25 #include "common_components/heap/allocator/region_space.h" 26 #include "common_components/heap/collector/copy_data_manager.h" 27 #include "common_components/mutator/mutator_manager.h" 28 29 namespace common { 30 31 template <typename T> 32 using CArrayList = std::vector<T>; 33 34 template <typename StackType> 35 class GlobalStackQueue; 36 37 // number of nanoseconds in a microsecond. 38 constexpr uint64_t NS_PER_US = 1000; 39 constexpr uint64_t NS_PER_S = 1000000000; 40 41 // prefetch distance for mark. 42 #define MACRO_MARK_PREFETCH_DISTANCE 16 // this macro is used for check when pre-compiling. 43 constexpr int MARK_PREFETCH_DISTANCE = 16; // when it is changed, remember to change MACRO_MARK_PREFETCH_DISTANCE. 44 45 // Small queue implementation, for prefetching. 46 #define COMMON_MAX_PREFETCH_QUEUE_SIZE_LOG 5UL 47 #define COMMON_MAX_PREFETCH_QUEUE_SIZE (1UL << COMMON_MAX_PREFETCH_QUEUE_SIZE_LOG) 48 #if COMMON_MAX_PREFETCH_QUEUE_SIZE <= MACRO_MARK_PREFETCH_DISTANCE 49 #error Prefetch queue size must be strictly greater than prefetch distance. 50 #endif 51 52 class PrefetchQueue { 53 public: PrefetchQueue(size_t d)54 explicit PrefetchQueue(size_t d) : elems_{ nullptr }, distance_(d), tail_(0), head_(0) {} ~PrefetchQueue()55 ~PrefetchQueue() {} Add(BaseObject * objaddr)56 inline void Add(BaseObject* objaddr) 57 { 58 size_t t = tail_; 59 elems_[t] = objaddr; 60 tail_ = (t + 1) & (COMMON_MAX_PREFETCH_QUEUE_SIZE - 1UL); 61 62 __builtin_prefetch(reinterpret_cast<void*>(objaddr), 0, PREFETCH_LOCALITY); 63 } 64 Remove()65 inline BaseObject* Remove() 66 { 67 size_t h = head_; 68 BaseObject* objaddr = elems_[h]; 69 head_ = (h + 1) & (COMMON_MAX_PREFETCH_QUEUE_SIZE - 1UL); 70 71 return objaddr; 72 } 73 Length()74 inline size_t Length() const { return (tail_ - head_) & (COMMON_MAX_PREFETCH_QUEUE_SIZE - 1UL); } 75 Empty()76 inline bool Empty() const { return head_ == tail_; } 77 Full()78 inline bool Full() const { return Length() == distance_; } 79 80 private: 81 static constexpr int PREFETCH_LOCALITY = 3; 82 BaseObject* elems_[COMMON_MAX_PREFETCH_QUEUE_SIZE]; 83 size_t distance_; 84 size_t tail_; 85 size_t head_; 86 }; // End of small queue implementation 87 88 // For managing gc roots 89 class StaticRootTable { 90 public: 91 struct StaticRootArray { 92 RefField<>* content[0]; 93 }; 94 StaticRootTable()95 StaticRootTable() { totalRootsCount_ = 0; } 96 ~StaticRootTable() = default; 97 void VisitRoots(const RefFieldVisitor& visitor); 98 99 private: 100 std::mutex gcRootsLock_; // lock gcRootsBuckets 101 std::map<StaticRootArray*, uint32_t> gcRootsBuckets_; // record gc roots entry of CFile 102 size_t totalRootsCount_; 103 }; 104 105 class MarkingWork; 106 class ConcurrentMarkingWork; 107 using RootSet = MarkStack<BaseObject*>; 108 using WorkStack = MarkStack<BaseObject*>; 109 using WorkStackBuf = MarkStackBuffer<BaseObject*>; 110 using WeakStack = MarkStack<std::shared_ptr<std::tuple<RefField<>*, size_t>>>; 111 using WeakStackBuf = MarkStackBuffer<std::shared_ptr<std::tuple<RefField<>*, size_t>>>; 112 using GlobalWorkStackQueue = GlobalStackQueue<WorkStack>; 113 using GlobalWeakStackQueue = GlobalStackQueue<WeakStack>; 114 115 class MarkingCollector : public Collector { 116 friend MarkingWork; 117 friend ConcurrentMarkingWork; 118 119 public: MarkingCollector(Allocator & allocator,CollectorResources & resources)120 explicit MarkingCollector(Allocator& allocator, CollectorResources& resources) 121 : Collector(), theAllocator_(allocator), collectorResources_(resources) 122 {} 123 124 ~MarkingCollector() override = default; 125 virtual void PreGarbageCollection(bool isConcurrent); 126 virtual void PostGarbageCollection(uint64_t gcIndex); 127 128 // Types, so that we don't confuse root sets and working stack. 129 // The policy is: we simply `push_back` into root set, 130 // but we use Enqueue to add into work stack. 131 132 void Init(const RuntimeParam& param) override; 133 void Fini() override; 134 135 #if defined(GCINFO_DEBUG) && GCINFO_DEBUG 136 void DumpRoots(LogType logType); 137 void DumpHeap(const CString& tag); DumpBeforeGC()138 void DumpBeforeGC() 139 { 140 if (ENABLE_LOG(FRAGMENT)) { 141 if (MutatorManager::Instance().WorldStopped()) { 142 DumpHeap("before_gc"); 143 } else { 144 STWParam stwParam{"dump-heap-before-gc"}; 145 ScopedStopTheWorld stw(stwParam); 146 DumpHeap("before_gc"); 147 } 148 } 149 } 150 DumpAfterGC()151 void DumpAfterGC() 152 { 153 if (ENABLE_LOG(FRAGMENT)) { 154 if (MutatorManager::Instance().WorldStopped()) { 155 DumpHeap("after_gc"); 156 } else { 157 STWParam stwParam{"dump-heap-after-gc"}; 158 ScopedStopTheWorld stw(stwParam); 159 DumpHeap("after_gc"); 160 } 161 } 162 } 163 #endif 164 ShouldIgnoreRequest(GCRequest & request)165 bool ShouldIgnoreRequest(GCRequest& request) override { return request.ShouldBeIgnored(); } 166 167 void ProcessMarkStack(uint32_t threadIndex, Taskpool *threadPool, WorkStack &workStack, 168 GlobalWorkStackQueue &globalQueue); 169 void ProcessWeakStack(WeakStack &weakStack); 170 171 void TryForkTask(Taskpool *threadPool, WorkStack &workStack, GlobalWorkStackQueue &globalQueue); 172 173 // live but not resurrected object. IsMarkedObject(const BaseObject * obj)174 bool IsMarkedObject(const BaseObject* obj) const { return RegionSpace::IsMarkedObject(obj); } 175 176 // live or resurrected object. IsSurvivedObject(const BaseObject * obj)177 inline bool IsSurvivedObject(const BaseObject* obj) const 178 { 179 return RegionSpace::IsMarkedObject(obj) || RegionSpace::IsResurrectedObject(obj); 180 } 181 IsToObject(const BaseObject * obj)182 inline bool IsToObject(const BaseObject* obj) const 183 { 184 return RegionDesc::GetAliveRegionDescAt(reinterpret_cast<HeapAddress>(obj))->IsToRegion(); 185 } 186 187 virtual bool MarkObject(BaseObject* obj) const = 0; 188 189 // avoid std::function allocation for each object marking 190 class MarkingRefFieldVisitor { 191 public: MarkingRefFieldVisitor()192 MarkingRefFieldVisitor() : closure_(std::make_shared<BaseObject *>(nullptr)) {} 193 194 template <typename Functor> SetVisitor(Functor && f)195 void SetVisitor(Functor &&f) 196 { 197 visitor_ = std::forward<Functor>(f); 198 } GetRefFieldVisitor()199 const auto &GetRefFieldVisitor() const { return visitor_; } SetMarkingRefFieldArgs(BaseObject * obj)200 void SetMarkingRefFieldArgs(BaseObject *obj) { *closure_ = obj; } GetClosure()201 const auto &GetClosure() const { return closure_; } 202 203 private: 204 common::RefFieldVisitor visitor_; 205 std::shared_ptr<BaseObject *> closure_; 206 }; 207 virtual MarkingRefFieldVisitor CreateMarkingObjectRefFieldsVisitor(WorkStack *workStack, WeakStack *weakStack) = 0; 208 virtual void MarkingObjectRefFields(BaseObject *obj, MarkingRefFieldVisitor *data) = 0; 209 IsResurrectedObject(const BaseObject * obj)210 inline bool IsResurrectedObject(const BaseObject* obj) const { return RegionSpace::IsResurrectedObject(obj); } 211 GetAllocator()212 Allocator& GetAllocator() const { return theAllocator_; } 213 IsHeapMarked()214 bool IsHeapMarked() const { return collectorResources_.IsHeapMarked(); } 215 SetHeapMarked(bool value)216 void SetHeapMarked(bool value) { collectorResources_.SetHeapMarked(value); } 217 SetGcStarted(bool val)218 void SetGcStarted(bool val) { collectorResources_.SetGcStarted(val); } 219 MarkGCStart()220 void MarkGCStart() { collectorResources_.MarkGCStart(); } MarkGCFinish(uint64_t gcIndex)221 void MarkGCFinish(uint64_t gcIndex) 222 { 223 collectorResources_.MarkGCFinish(gcIndex); 224 } 225 226 void RunGarbageCollection(uint64_t, GCReason, GCType) override; 227 228 void ReclaimGarbageMemory(GCReason reason); 229 TransitionToGCPhase(const GCPhase phase,const bool)230 void TransitionToGCPhase(const GCPhase phase, const bool) 231 { 232 MutatorManager::Instance().TransitionAllMutatorsToGCPhase(phase); 233 } 234 GetGCStats()235 GCStats& GetGCStats() override { return collectorResources_.GetGCStats(); } 236 237 virtual void UpdateGCStats(); 238 239 static const size_t MAX_MARKING_WORK_SIZE; 240 static const size_t MIN_MARKING_WORK_SIZE; 241 242 void CopyObject(const BaseObject& fromObj, BaseObject& toObj, size_t size) const; 243 244 protected: 245 virtual BaseObject* CopyObjectAfterExclusive(BaseObject* obj) = 0; 246 virtual void CopyFromSpace(); 247 virtual void ExemptFromSpace(); 248 249 virtual void DoGarbageCollection() = 0; 250 RequestGCInternal(GCReason reason,bool async,GCType gcType)251 void RequestGCInternal(GCReason reason, bool async, GCType gcType) override 252 { 253 collectorResources_.RequestGC(reason, async, gcType); 254 } 255 void MergeWeakStack(WeakStack& weakStack); 256 void UpdateNativeThreshold(GCParam& gcParam); 257 258 Allocator& theAllocator_; 259 260 // A collectorResources provides the resources that the tracing collector need, 261 // such as gc thread/threadPool, gc task queue. 262 // Also provides the resource access interfaces, such as invokeGC, waitGC. 263 // This resource should be singleton and shared for multi-collectors 264 CollectorResources& collectorResources_; 265 266 WeakStack globalWeakStack_; 267 std::mutex weakStackLock_; 268 269 uint32_t snapshotFinalizerNum_ = 0; 270 271 // reason for current GC. 272 GCReason gcReason_ = GC_REASON_USER; 273 274 GCType gcType_ = GC_TYPE_FULL; 275 276 // indicate whether to fix references (including global roots and reference fields). 277 // this member field is useful for optimizing concurrent copying gc. 278 bool fixReferences_ = false; 279 280 std::atomic<size_t> markedObjectCount_ = { 0 }; 281 ResetBitmap(bool heapMarked)282 void ResetBitmap(bool heapMarked) 283 { 284 // if heap is marked and tracing result will be used during next gc, we should not reset liveInfo_. 285 } 286 GetGCThreadCount(const bool isConcurrent)287 uint32_t GetGCThreadCount(const bool isConcurrent) const 288 { 289 return collectorResources_.GetGCThreadCount(isConcurrent); 290 } 291 NewWorkStack()292 inline WorkStack NewWorkStack() const 293 { 294 WorkStack workStack = WorkStack(); 295 return workStack; 296 } 297 SetGCReason(const GCReason reason)298 inline void SetGCReason(const GCReason reason) { gcReason_ = reason; } 299 GetThreadPool()300 Taskpool *GetThreadPool() const { return collectorResources_.GetThreadPool(); } 301 302 // let finalizerProcessor process finalizers, and mark resurrected if in stw gc 303 void ClearWeakStack(bool parallel); ProcessStringTable()304 virtual void ProcessStringTable() {} 305 ProcessFinalizers()306 virtual void ProcessFinalizers() {} RemarkAndPreforwardStaticRoots(WorkStack & workStack)307 virtual void RemarkAndPreforwardStaticRoots(WorkStack& workStack) 308 { 309 LOG_COMMON(FATAL) << "Unresolved fatal"; 310 UNREACHABLE_CC(); 311 } 312 313 void MergeAllocBufferRoots(WorkStack& workStack); 314 315 bool PushRootToWorkStack(RootSet *workStack, BaseObject *obj); 316 void PushRootsToWorkStack(RootSet *workStack, const CArrayList<BaseObject *> &collectedRoots); 317 void MarkingRoots(const CArrayList<BaseObject *> &collectedRoots); 318 void Remark(); 319 320 bool MarkSatbBuffer(WorkStack& workStack); 321 322 // concurrent marking. 323 void TracingImpl(WorkStack& workStack, bool parallel, bool Remark); 324 325 bool AddConcurrentTracingWork(WorkStack& workStack, GlobalWorkStackQueue &globalQueue, size_t threadCount); 326 bool AddWeakStackClearWork(WeakStack& workStack, GlobalWeakStackQueue &globalQueue, size_t threadCount); 327 private: 328 void MarkRememberSetImpl(BaseObject* object, WorkStack& workStack); 329 void ConcurrentRemark(WorkStack& remarkStack, bool parallel); 330 void MarkAwaitingJitFort(); 331 void EnumMutatorRoot(ObjectPtr& obj, RootSet& rootSet) const; 332 void EnumConcurrencyModelRoots(RootSet& rootSet) const; 333 }; 334 335 336 template <typename StackType> 337 class GlobalStackQueue { 338 public: 339 GlobalStackQueue() = default; 340 ~GlobalStackQueue() = default; 341 AddWorkStack(StackType && stack)342 void AddWorkStack(StackType &&stack) 343 { 344 DCHECK_CC(!stack.empty()); 345 std::lock_guard<std::mutex> guard(mtx_); 346 stacks_.push_back(std::move(stack)); 347 cv_.notify_one(); 348 } 349 PopWorkStack()350 StackType PopWorkStack() 351 { 352 std::unique_lock<std::mutex> lock(mtx_); 353 while (true) { 354 if (!stacks_.empty()) { 355 StackType stack(std::move(stacks_.back())); 356 stacks_.pop_back(); 357 return stack; 358 } 359 if (finished_) { 360 return StackType(); 361 } 362 cv_.wait(lock); 363 } 364 } 365 DrainAllWorkStack()366 StackType DrainAllWorkStack() 367 { 368 std::unique_lock<std::mutex> lock(mtx_); 369 while (!stacks_.empty()) { 370 StackType stack(std::move(stacks_.back())); 371 stacks_.pop_back(); 372 return stack; 373 } 374 return StackType(); 375 } 376 NotifyFinish()377 void NotifyFinish() 378 { 379 std::lock_guard<std::mutex> guard(mtx_); 380 DCHECK_CC(!finished_); 381 finished_ = true; 382 cv_.notify_all(); 383 } 384 private: 385 bool finished_ {false}; 386 std::condition_variable cv_; 387 std::mutex mtx_; 388 std::vector<StackType> stacks_; 389 }; 390 391 } // namespace common 392 393 #endif // COMMON_COMPONENTS_HEAP_COLLECTOR_MARKING_COLLECTOR_H 394