1 /**
2 * Copyright (c) 2021-2024 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 #include "runtime/mem/gc/gc_adaptive_stack.h"
17 #include "runtime/mem/gc/gc.h"
18 #include "runtime/mem/gc/workers/gc_workers_task_pool.h"
19
20 namespace ark::mem {
21
GCAdaptiveStack(GC * gc,size_t stackSizeLimit,size_t newTaskStackSizeLimit,GCWorkersTaskTypes task,uint64_t timeLimitForNewTaskCreation,PandaDeque<ObjectHeader * > * stackSrc)22 GCAdaptiveStack::GCAdaptiveStack(GC *gc, size_t stackSizeLimit, size_t newTaskStackSizeLimit, GCWorkersTaskTypes task,
23 uint64_t timeLimitForNewTaskCreation, PandaDeque<ObjectHeader *> *stackSrc)
24 : stackSizeLimit_(stackSizeLimit),
25 newTaskStackSizeLimit_(newTaskStackSizeLimit),
26 timeLimitForNewTaskCreation_(timeLimitForNewTaskCreation),
27 taskType_(task),
28 gc_(gc)
29 {
30 initialStackSizeLimit_ = stackSizeLimit_;
31 auto allocator = gc_->GetInternalAllocator();
32 ASSERT((stackSizeLimit == 0) || (gc->GetWorkersTaskPool() != nullptr));
33 if (stackSrc != nullptr) {
34 stackSrc_ = stackSrc;
35 } else {
36 stackSrc_ = allocator->template New<PandaDeque<ObjectHeader *>>(allocator->Adapter());
37 }
38 stackDst_ = allocator->template New<PandaDeque<ObjectHeader *>>(allocator->Adapter());
39 }
40
~GCAdaptiveStack()41 GCAdaptiveStack::~GCAdaptiveStack()
42 {
43 gc_->GetInternalAllocator()->Delete(stackSrc_);
44 gc_->GetInternalAllocator()->Delete(stackDst_);
45 }
46
Empty()47 bool GCAdaptiveStack::Empty()
48 {
49 return stackSrc_->empty() && stackDst_->empty();
50 }
51
Size()52 size_t GCAdaptiveStack::Size()
53 {
54 return stackSrc_->size() + stackDst_->size();
55 }
56
MoveStacksPointers()57 PandaDeque<ObjectHeader *> *GCAdaptiveStack::MoveStacksPointers()
58 {
59 ASSERT(stackSrc_ != nullptr);
60 PandaDeque<ObjectHeader *> *returnValue = stackSrc_;
61 stackSrc_ = nullptr;
62 return returnValue;
63 }
64
PushToStack(const ObjectHeader * fromObject,ObjectHeader * object)65 void GCAdaptiveStack::PushToStack(const ObjectHeader *fromObject, ObjectHeader *object)
66 {
67 LOG(DEBUG, GC) << "Add object to stack: " << GetDebugInfoAboutObject(object)
68 << " accessed from object: " << fromObject;
69 ValidateObject(fromObject, object);
70 PushToStack(object);
71 }
72
PushToStack(RootType rootType,ObjectHeader * object)73 void GCAdaptiveStack::PushToStack(RootType rootType, ObjectHeader *object)
74 {
75 LOG(DEBUG, GC) << "Add object to stack: " << GetDebugInfoAboutObject(object) << " accessed as a root: " << rootType;
76 ValidateObject(rootType, object);
77 PushToStack(object);
78 }
79
PushToStack(ObjectHeader * element)80 void GCAdaptiveStack::PushToStack(ObjectHeader *element)
81 {
82 ASSERT_PRINT(IsAddressInObjectsHeap(element), element);
83 if ((stackSizeLimit_ > 0) && ((stackDst_->size() + 1) == stackSizeLimit_)) {
84 // Try to create a new task only once
85 // Create a new stack and send a new task to GC
86 LOG(DEBUG, GC) << "GCAdaptiveStack: Try to add new task " << GCWorkersTaskTypesToString(taskType_)
87 << " for worker";
88 ASSERT(gc_->GetWorkersTaskPool() != nullptr);
89 ASSERT(taskType_ != GCWorkersTaskTypes::TASK_EMPTY);
90 auto allocator = gc_->GetInternalAllocator();
91 // New tasks will be created with the same new_task_stack_size_limit_ and stack_size_limit_
92 auto *newStack = allocator->New<GCAdaptiveStack>(gc_, newTaskStackSizeLimit_, newTaskStackSizeLimit_, taskType_,
93 timeLimitForNewTaskCreation_, stackDst_);
94 if (gc_->GetWorkersTaskPool()->AddTask(GCMarkWorkersTask(taskType_, newStack))) {
95 LOG(DEBUG, GC) << "GCAdaptiveStack: Successfully add new task " << GCWorkersTaskTypesToString(taskType_)
96 << " for worker";
97 stackDst_ = allocator->template New<PandaDeque<ObjectHeader *>>(allocator->Adapter());
98 } else {
99 // We will try to create a new task later
100 stackSizeLimit_ += stackSizeLimit_;
101 LOG(DEBUG, GC) << "GCAdaptiveStack: Failed to add new task " << GCWorkersTaskTypesToString(taskType_)
102 << " for worker";
103 [[maybe_unused]] auto srcStack = newStack->MoveStacksPointers();
104 ASSERT(srcStack == stackDst_);
105 allocator->Delete(newStack);
106 }
107 if (IsHighTaskCreationRate()) {
108 stackSizeLimit_ += stackSizeLimit_;
109 }
110 }
111 stackDst_->push_back(element);
112 }
113
IsHighTaskCreationRate()114 bool GCAdaptiveStack::IsHighTaskCreationRate()
115 {
116 if (createdTasks_ == 0) {
117 startTime_ = ark::os::time::GetClockTimeInThreadCpuTime();
118 }
119 createdTasks_++;
120 if (tasksForTimeCheck_ == createdTasks_) {
121 uint64_t curTime = ark::os::time::GetClockTimeInThreadCpuTime();
122 ASSERT(curTime >= startTime_);
123 uint64_t totalTimeConsumed = curTime - startTime_;
124 uint64_t oneTaskConsumed = totalTimeConsumed / createdTasks_;
125 LOG(DEBUG, GC) << "Created " << createdTasks_ << " tasks in " << Timing::PrettyTimeNs(totalTimeConsumed);
126 if (oneTaskConsumed < timeLimitForNewTaskCreation_) {
127 createdTasks_ = 0;
128 startTime_ = 0;
129 return true;
130 }
131 }
132 return false;
133 }
134
PopFromStack()135 ObjectHeader *GCAdaptiveStack::PopFromStack()
136 {
137 if (stackSrc_->empty()) {
138 ASSERT(!stackDst_->empty());
139 auto temp = stackSrc_;
140 stackSrc_ = stackDst_;
141 stackDst_ = temp;
142 if (stackSizeLimit_ != 0) {
143 // We may increase the current limit, so return it to the default value
144 stackSizeLimit_ = initialStackSizeLimit_;
145 }
146 }
147 ASSERT(!stackSrc_->empty());
148 ObjectHeader *element = stackSrc_->back();
149 stackSrc_->pop_back();
150 return element;
151 }
152
TraverseObjects(const GCAdaptiveStack::ObjectVisitor & visitor)153 GCAdaptiveStack::MarkedObjects GCAdaptiveStack::TraverseObjects(const GCAdaptiveStack::ObjectVisitor &visitor)
154 {
155 // We need this to avoid allocation of new stack and fragmentation
156 static constexpr size_t BUCKET_SIZE = 16;
157 auto allocator = gc_->GetInternalAllocator();
158 MarkedObjects markedObjects;
159 PandaDeque<ObjectHeader *> *tailMarkedObjects =
160 allocator->template New<PandaDeque<ObjectHeader *>>(allocator->Adapter());
161 if (stackSrc_->empty()) {
162 std::swap(stackSrc_, stackDst_);
163 }
164 while (!Empty()) {
165 [[maybe_unused]] auto stackSrcSize = stackSrc_->size();
166 for (auto *object : *stackSrc_) {
167 visitor(object);
168 // visitor mustn't pop from stack
169 ASSERT(stackSrcSize == stackSrc_->size());
170 }
171 if (LIKELY(stackSrc_->size() > BUCKET_SIZE)) {
172 markedObjects.push_back(stackSrc_);
173 stackSrc_ = allocator->template New<PandaDeque<ObjectHeader *>>(allocator->Adapter());
174 } else {
175 tailMarkedObjects->insert(tailMarkedObjects->end(), stackSrc_->begin(), stackSrc_->end());
176 stackSrc_->clear();
177 }
178 std::swap(stackSrc_, stackDst_);
179 }
180 if (!tailMarkedObjects->empty()) {
181 markedObjects.push_back(tailMarkedObjects);
182 } else {
183 allocator->Delete(tailMarkedObjects);
184 }
185 return markedObjects;
186 }
187
IsWorkersTaskSupported()188 bool GCAdaptiveStack::IsWorkersTaskSupported()
189 {
190 return taskType_ != GCWorkersTaskTypes::TASK_EMPTY;
191 }
192
Clear()193 void GCAdaptiveStack::Clear()
194 {
195 *stackSrc_ = PandaDeque<ObjectHeader *>();
196 *stackDst_ = PandaDeque<ObjectHeader *>();
197 }
198
199 } // namespace ark::mem
200