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