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