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
21namespace panda::ecmascript {
22template <typename T>
23FreeObjectList<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}
32template FreeObjectList<FreeObject>::FreeObjectList(JitFort* fort);
33template FreeObjectList<MemDesc>::FreeObjectList(JitFort* fort);
34
35template <typename T>
36FreeObjectList<T>::~FreeObjectList()
37{
38    delete[] sets_.data();
39    delete[] lastSets_.data();
40    noneEmptySetBitMap_ = 0;
41}
42template FreeObjectList<FreeObject>::~FreeObjectList();
43template FreeObjectList<MemDesc>::~FreeObjectList();
44
45template <typename T>
46T *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}
88template FreeObject *FreeObjectList<FreeObject>::Allocate(size_t size);
89template MemDesc *FreeObjectList<MemDesc>::Allocate(size_t size);
90
91template <typename T>
92T *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}
125template FreeObject *FreeObjectList<FreeObject>::LookupSuitableFreeObject(size_t);
126
127template <typename T>
128template <typename U>
129void 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}
162template void FreeObjectList<FreeObject>::FreeImpl<Region>(Region* region, uintptr_t start, size_t size, bool isAdd);
163template void FreeObjectList<MemDesc>::FreeImpl<JitFortRegion>(JitFortRegion* region,
164    uintptr_t start, size_t size, bool isAdd);
165
166template <typename T>
167void 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.
173template void FreeObjectList<FreeObject>::Free(uintptr_t, size_t, bool);
174// template class instance for JitFort space uses MemDesc and JitFortRegion
175template <>
176void FreeObjectList<MemDesc>::Free(uintptr_t start, size_t size, bool isAdd)
177{
178    return FreeImpl<JitFortRegion>(jitFort_->ObjectAddressToRange(start), start, size, isAdd);
179}
180
181template <typename T>
182void 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}
193template void FreeObjectList<FreeObject>::Rebuild();
194template void FreeObjectList<MemDesc>::Rebuild();
195
196template <typename T>
197bool 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}
216template bool FreeObjectList<FreeObject>::MatchFreeObjectInSet(FreeObjectSet<FreeObject> *, size_t);
217
218template <typename T>
219bool 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}
245template bool FreeObjectList<FreeObject>::AddSet(FreeObjectSet<FreeObject> *);
246template bool FreeObjectList<MemDesc>::AddSet(FreeObjectSet<MemDesc> *);
247
248template <typename T>
249void 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}
277template void FreeObjectList<FreeObject>::RemoveSet(FreeObjectSet<FreeObject> *);
278
279template <typename T>
280void 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
301template<typename T>
302template<class Callback>
303void 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
310template<typename T>
311template<class Callback>
312void 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
323template<typename T>
324template<class Callback>
325void 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