1 /*
2  * Copyright (c) 2021 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 #ifndef ECMASCRIPT_MEM_FREE_OBJECT_LIST_H
17 #define ECMASCRIPT_MEM_FREE_OBJECT_LIST_H
18 
19 #include <cstddef>
20 
21 #include "ecmascript/mem/free_object_set.h"
22 #include "ecmascript/mem/mem_common.h"
23 
24 #include "libpandabase/utils/span.h"
25 
26 namespace panda::ecmascript {
27 class JitFort;
28 template <typename T>
29 class FreeObjectList {
30 public:
31     FreeObjectList(JitFort* fort = nullptr);
32     ~FreeObjectList();
33 
34     T *Allocate(size_t size);
35 
36     T *LookupSuitableFreeObject(size_t size);
37 
38     void Free(uintptr_t start, size_t size, bool isAdd = true);
39 
40     void Rebuild();
41 
42     bool MatchFreeObjectInSet(FreeObjectSet<T> *set, size_t size);
43 
44     bool AddSet(FreeObjectSet<T> *set);
45 
46     void RemoveSet(FreeObjectSet<T> *set);
47     void Merge(FreeObjectList *list);
48 
49     template<class Callback>
50     void EnumerateSets(const Callback &cb) const;
51 
52     template<class Callback>
53     void EnumerateSets(SetType type, const Callback &cb) const;
54 
55     template<class Callback>
56     void EnumerateTopAndLastSets(const Callback &cb) const;
57 
58     NO_COPY_SEMANTIC(FreeObjectList);
59     NO_MOVE_SEMANTIC(FreeObjectList);
60 
GetFreeObjectSize() const61     size_t GetFreeObjectSize() const
62     {
63         return available_;
64     }
GetWastedSize() const65     size_t GetWastedSize() const
66     {
67         return wasted_;
68     }
DecreaseWastedSize(size_t size)69     void DecreaseWastedSize(size_t size)
70     {
71         wasted_ -= size;
72     }
IncreaseWastedSize(size_t size)73     void IncreaseWastedSize(size_t size)
74     {
75         wasted_ += size;
76     }
77 
NumberOfSets()78     static int NumberOfSets()
79     {
80         return NUMBER_OF_SETS;
81     }
82 
83     template<typename U>
84     void FreeImpl(U* region, uintptr_t start, size_t size, bool isAdd);
85 
86 private:
87     static constexpr int NUMBER_OF_SETS = 39;
88     static constexpr size_t MIN_SIZE = 16;
89     static constexpr size_t SMALL_SET_MAX_SIZE = 256;
90     static constexpr size_t LARGE_SET_MAX_SIZE = 65536;
91     static constexpr size_t HUGE_SET_MAX_SIZE = 255_KB;
92     static constexpr int SMALL_SET_MAX_INDEX = 29;
93     static constexpr int NUMBER_OF_LAST_LARGE = NUMBER_OF_SETS - 2;
94     static constexpr int NUMBER_OF_LAST_HUGE = NUMBER_OF_SETS - 1;
95     static constexpr size_t INTERVAL_OFFSET = 3;
96     static constexpr size_t LOG2_OFFSET = 21;
97     static constexpr size_t MAX_BIT_OF_SIZET = sizeof(size_t) << INTERVAL_OFFSET;
98     const int smallSetOffsetIndex = 2;
99 
SelectSetType(size_t size) const100     inline SetType SelectSetType(size_t size) const
101     {
102         if (size < SMALL_SET_MAX_SIZE) {
103             if (UNLIKELY(size < MIN_SIZE)) {
104                 return FreeObjectSet<T>::INVALID_SET_TYPE;
105             }
106             return (size >> INTERVAL_OFFSET) - smallSetOffsetIndex;
107         }
108         if (size < LARGE_SET_MAX_SIZE) {
109 #ifdef PANDA_TARGET_64
110             return MAX_BIT_OF_SIZET - __builtin_clzll(size) + LOG2_OFFSET;
111 #else
112             return MAX_BIT_OF_SIZET - __builtin_clzl(size) + LOG2_OFFSET;
113 #endif
114         }
115         if (size >= HUGE_SET_MAX_SIZE) {
116             return NUMBER_OF_LAST_HUGE;
117         }
118 
119         return NUMBER_OF_LAST_LARGE;
120     }
SetNoneEmptyBit(SetType type)121     inline void SetNoneEmptyBit(SetType type)
122     {
123         noneEmptySetBitMap_ |= 1ULL << static_cast<uint32_t>(type);
124     }
ClearNoneEmptyBit(SetType type)125     inline void ClearNoneEmptyBit(SetType type)
126     {
127         noneEmptySetBitMap_ &= ~(1ULL << static_cast<uint32_t>(type));
128     }
CalcNextNoneEmptyIndex(SetType start)129     inline size_t CalcNextNoneEmptyIndex(SetType start)
130     {
131         return __builtin_ffsll(noneEmptySetBitMap_ >> static_cast<uint32_t>(start)) + start - 1;
132     }
133 
134     size_t available_ = 0;
135     size_t wasted_ = 0;
136     uint64_t noneEmptySetBitMap_ = 0;
137     Span<FreeObjectSet<T> *> sets_ {};
138     Span<FreeObjectSet<T> *> lastSets_ {};
139     JitFort *jitFort_ {nullptr};
140 };
141 }  // namespace panda::ecmascript
142 #endif  // ECMASCRIPT_MEM_FREE_OBJECT_LIST_H
143