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 "ecmascript/mem/free_object_list.h"
17 #include "ecmascript/free_object.h"
18 #include "ecmascript/mem/jit_fort.h"
19
20 namespace panda::ecmascript {
21 template <typename T>
FreeObjectList()22 FreeObjectList<T>::FreeObjectList() : sets_(new FreeObjectSet<T> *[NUMBER_OF_SETS](), NUMBER_OF_SETS),
23 lastSets_(new FreeObjectSet<T> *[NUMBER_OF_SETS](), NUMBER_OF_SETS)
24 {
25 for (int i = 0; i < NUMBER_OF_SETS; i++) {
26 sets_[i] = nullptr;
27 lastSets_[i] = nullptr;
28 }
29 noneEmptySetBitMap_ = 0;
30 }
31 template FreeObjectList<FreeObject>::FreeObjectList();
32 template FreeObjectList<MemDesc>::FreeObjectList();
33
34 template <>
FreeObjectList(JitFort * fort)35 FreeObjectList<MemDesc>::FreeObjectList(JitFort *fort)
36 : sets_(new FreeObjectSet<MemDesc> *[NUMBER_OF_SETS](), NUMBER_OF_SETS),
37 lastSets_(new FreeObjectSet<MemDesc> *[NUMBER_OF_SETS](), NUMBER_OF_SETS),
38 jitFort_(fort)
39 {
40 for (int i = 0; i < NUMBER_OF_SETS; i++) {
41 sets_[i] = nullptr;
42 lastSets_[i] = nullptr;
43 }
44 noneEmptySetBitMap_ = 0;
45 }
46
47 template <typename T>
~FreeObjectList()48 FreeObjectList<T>::~FreeObjectList()
49 {
50 delete[] sets_.data();
51 delete[] lastSets_.data();
52 noneEmptySetBitMap_ = 0;
53 }
54 template FreeObjectList<FreeObject>::~FreeObjectList();
55 template FreeObjectList<MemDesc>::~FreeObjectList();
56
57 template <typename T>
Allocate(size_t size)58 T *FreeObjectList<T>::Allocate(size_t size)
59 {
60 if (noneEmptySetBitMap_ == 0) {
61 return nullptr;
62 }
63 // find from suitable
64 SetType type = SelectSetType(size);
65 if (type == FreeObjectSet<T>::INVALID_SET_TYPE) {
66 return nullptr;
67 }
68
69 SetType lastType = type - 1;
70 for (type = static_cast<int32_t>(CalcNextNoneEmptyIndex(type)); type > lastType && type < NUMBER_OF_SETS;
71 type = static_cast<int32_t>(CalcNextNoneEmptyIndex(type + 1))) {
72 lastType = type;
73 FreeObjectSet<T> *current = sets_[type];
74 while (current != nullptr) {
75 if (current->Available() < size || size > current->MaxAvailableFreeSize()) {
76 current = current->next_;
77 continue;
78 }
79 FreeObjectSet<T> *next = nullptr;
80 T *object = T::Cast(INVALID_OBJPTR);
81 if (type <= SMALL_SET_MAX_INDEX) {
82 object = current->ObtainSmallFreeObject(size);
83 } else {
84 next = current->next_;
85 object = current->ObtainLargeFreeObject(size);
86 }
87 if (current->Empty()) {
88 RemoveSet(current);
89 current->Rebuild();
90 }
91 if (object != T::Cast(INVALID_OBJPTR)) {
92 available_ -= object->Available();
93 return object;
94 }
95 current = next;
96 }
97 }
98 return nullptr;
99 }
100 template FreeObject *FreeObjectList<FreeObject>::Allocate(size_t size);
101 template MemDesc *FreeObjectList<MemDesc>::Allocate(size_t size);
102
103 template <typename T>
LookupSuitableFreeObject(size_t size)104 T *FreeObjectList<T>::LookupSuitableFreeObject(size_t size)
105 {
106 if (noneEmptySetBitMap_ == 0) {
107 return nullptr;
108 }
109 // find a suitable type
110 SetType type = SelectSetType(size);
111 if (type == FreeObjectSet<T>::INVALID_SET_TYPE) {
112 return nullptr;
113 }
114
115 SetType lastType = type - 1;
116 for (type = static_cast<int32_t>(CalcNextNoneEmptyIndex(type)); type > lastType && type < NUMBER_OF_SETS;
117 type = static_cast<int32_t>(CalcNextNoneEmptyIndex(type + 1))) {
118 lastType = type;
119 FreeObjectSet<T> *current = sets_[type];
120 while (current != nullptr) {
121 FreeObjectSet<T> *next = nullptr;
122 T *object = INVALID_OBJECT;
123 if (type <= SMALL_SET_MAX_INDEX) {
124 object = current->LookupSmallFreeObject(size);
125 } else {
126 next = current->next_;
127 object = current->LookupLargeFreeObject(size);
128 }
129 if (object != INVALID_OBJECT) {
130 return object;
131 }
132 current = next;
133 }
134 }
135 return nullptr;
136 }
137 template FreeObject *FreeObjectList<FreeObject>::LookupSuitableFreeObject(size_t);
138
139 template <typename T>
Free(uintptr_t start,size_t size,bool isAdd)140 void FreeObjectList<T>::Free(uintptr_t start, size_t size, bool isAdd)
141 {
142 if (UNLIKELY(start == 0)) { // LCOV_EXCL_BR_LINE
143 return;
144 }
145 if (UNLIKELY(size < MIN_SIZE)) { // LCOV_EXCL_BR_LINE
146 Region *region = Region::ObjectAddressToRange(reinterpret_cast<TaggedObject *>(start));
147 region->IncreaseWasted(size);
148 if (isAdd) {
149 wasted_ += size;
150 }
151 return;
152 }
153 SetType type = SelectSetType(size);
154 if (type == FreeObjectSet<T>::INVALID_SET_TYPE) {
155 return;
156 }
157
158 Region *region = Region::ObjectAddressToRange(reinterpret_cast<TaggedObject *>(start));
159 auto set = region->GetFreeObjectSet(type);
160 if (set == nullptr) { // LCOV_EXCL_BR_LINE
161 LOG_FULL(FATAL) << "The set of region is nullptr";
162 return;
163 }
164 set->Free(start, size);
165
166 if (isAdd) {
167 if (set->isAdded_ == 0) {
168 AddSet(set);
169 } else {
170 available_ += size;
171 }
172 }
173 }
174
175 // template class instance for non JitFort space uses FreeObject and Region.
176 template void FreeObjectList<FreeObject>::Free(uintptr_t, size_t, bool);
177 // template class instance for JitFort space uses MemDesc and JitFortRegion
178 template <>
Free(uintptr_t start,size_t size,bool isAdd)179 void FreeObjectList<MemDesc>::Free(uintptr_t start, size_t size, bool isAdd)
180 {
181 if (UNLIKELY(start == 0)) {
182 return;
183 }
184 if (UNLIKELY(size < MIN_SIZE)) {
185 JitFortRegion *region = jitFort_->ObjectAddressToRange(start);
186 region->IncreaseWasted(size);
187 if (isAdd) {
188 wasted_ += size;
189 }
190 return;
191 }
192 SetType type = SelectSetType(size);
193 if (type == FreeObjectSet<MemDesc>::INVALID_SET_TYPE) {
194 return;
195 }
196
197 JitFortRegion *region = jitFort_->ObjectAddressToRange(start);
198 auto set = region->GetFreeObjectSet(type);
199 if (set == nullptr) {
200 LOG_FULL(FATAL) << "The set of region is nullptr";
201 return;
202 }
203 set->Free(start, size);
204
205 if (isAdd) {
206 if (set->isAdded_ == 0) {
207 AddSet(set);
208 } else {
209 available_ += size;
210 }
211 }
212 }
213
214 template <typename T>
Rebuild()215 void FreeObjectList<T>::Rebuild()
216 {
217 EnumerateSets([](FreeObjectSet<T> *set) { set->Rebuild(); });
218 for (int i = 0; i < NUMBER_OF_SETS; i++) {
219 sets_[i] = nullptr;
220 lastSets_[i] = nullptr;
221 }
222 available_ = 0;
223 wasted_ = 0;
224 noneEmptySetBitMap_ = 0;
225 }
226 template void FreeObjectList<FreeObject>::Rebuild();
227 template void FreeObjectList<MemDesc>::Rebuild();
228
229 template <typename T>
MatchFreeObjectInSet(FreeObjectSet<T> * set,size_t size)230 bool FreeObjectList<T>::MatchFreeObjectInSet(FreeObjectSet<T> *set, size_t size)
231 {
232 if (set == nullptr || set->Empty()) {
233 return false;
234 }
235 // find a suitable type
236 SetType type = SelectSetType(size);
237 if (type == FreeObjectSet<T>::INVALID_SET_TYPE) {
238 return false;
239 }
240
241 T *object = nullptr;
242 if (type <= SMALL_SET_MAX_INDEX) {
243 object = set->LookupSmallFreeObject(size);
244 } else {
245 object = set->LookupLargeFreeObject(size);
246 }
247 return object != nullptr;
248 }
249 template bool FreeObjectList<FreeObject>::MatchFreeObjectInSet(FreeObjectSet<FreeObject> *, size_t);
250
251 template <typename T>
AddSet(FreeObjectSet<T> * set)252 bool FreeObjectList<T>::AddSet(FreeObjectSet<T> *set)
253 {
254 if (set == nullptr || set->Empty() || set->isAdded_ != 0) {
255 return false;
256 }
257 SetType type = set->setType_;
258 FreeObjectSet<T> *top = sets_[type];
259 if (set == top) {
260 return false;
261 }
262 if (top != nullptr) {
263 top->prev_ = set;
264 }
265 set->isAdded_ = 1; // 1: added
266 set->next_ = top;
267 set->prev_ = nullptr;
268 if (lastSets_[type] == nullptr) {
269 lastSets_[type] = set;
270 }
271 if (sets_[type] == nullptr) {
272 SetNoneEmptyBit(type);
273 }
274 sets_[type] = set;
275 available_ += set->Available();
276 return true;
277 }
278 template bool FreeObjectList<FreeObject>::AddSet(FreeObjectSet<FreeObject> *);
279 template bool FreeObjectList<MemDesc>::AddSet(FreeObjectSet<MemDesc> *);
280
281 template <typename T>
RemoveSet(FreeObjectSet<T> * set)282 void FreeObjectList<T>::RemoveSet(FreeObjectSet<T> *set)
283 {
284 if (set == nullptr) {
285 return;
286 }
287 SetType type = set->setType_;
288 FreeObjectSet<T> *top = sets_[type];
289 FreeObjectSet<T> *end = lastSets_[type];
290 if (top == set) {
291 sets_[type] = top->next_;
292 }
293 if (end == set) {
294 lastSets_[type] = end->prev_;
295 }
296 if (set->prev_ != nullptr) {
297 set->prev_->next_ = set->next_;
298 }
299 if (set->next_ != nullptr) {
300 set->next_->prev_ = set->prev_;
301 }
302 set->isAdded_ = 0;
303 set->prev_ = nullptr;
304 set->next_ = nullptr;
305 if (sets_[type] == nullptr) {
306 ClearNoneEmptyBit(type);
307 }
308 available_ -= set->Available();
309 }
310 template void FreeObjectList<FreeObject>::RemoveSet(FreeObjectSet<FreeObject> *);
311
312 template <typename T>
Merge(FreeObjectList<T> * list)313 void FreeObjectList<T>::Merge(FreeObjectList<T> *list)
314 {
315 list->EnumerateTopAndLastSets([this](FreeObjectSet<T> *set, FreeObjectSet<T> *end) {
316 if (set == nullptr || set->Empty()) {
317 return;
318 }
319 SetType type = set->setType_;
320 FreeObjectSet<T> *top = sets_[type];
321 if (top == nullptr) {
322 top = set;
323 } else {
324 lastSets_[type]->next_ = set;
325 set->prev_ = lastSets_[type];
326 }
327 lastSets_[type] = end;
328 SetNoneEmptyBit(type);
329 });
330 available_ += list->available_;
331 list->Rebuild();
332 }
333
334 template<typename T>
335 template<class Callback>
EnumerateSets(const Callback & cb) const336 void FreeObjectList<T>::EnumerateSets(const Callback &cb) const
337 {
338 for (SetType i = 0; i < NUMBER_OF_SETS; i++) {
339 EnumerateSets(i, cb);
340 }
341 }
342
343 template<typename T>
344 template<class Callback>
EnumerateSets(SetType type,const Callback & cb) const345 void FreeObjectList<T>::EnumerateSets(SetType type, const Callback &cb) const
346 {
347 FreeObjectSet<T> *current = sets_[type];
348 while (current != nullptr) {
349 // maybe reset
350 FreeObjectSet<T> *next = current->next_;
351 cb(current);
352 current = next;
353 }
354 }
355
356 template<typename T>
357 template<class Callback>
EnumerateTopAndLastSets(const Callback & cb) const358 void FreeObjectList<T>::EnumerateTopAndLastSets(const Callback &cb) const
359 {
360 for (SetType i = 0; i < NUMBER_OF_SETS; i++) {
361 cb(sets_[i], lastSets_[i]);
362 }
363 }
364 } // namespace panda::ecmascript
365