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
26namespace panda::ecmascript {
27class JitFort;
28template <typename T>
29class FreeObjectList {
30public:
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
61    size_t GetFreeObjectSize() const
62    {
63        return available_;
64    }
65    size_t GetWastedSize() const
66    {
67        return wasted_;
68    }
69    void DecreaseWastedSize(size_t size)
70    {
71        wasted_ -= size;
72    }
73    void IncreaseWastedSize(size_t size)
74    {
75        wasted_ += size;
76    }
77
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
86private:
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
100    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    }
121    inline void SetNoneEmptyBit(SetType type)
122    {
123        noneEmptySetBitMap_ |= 1ULL << static_cast<uint32_t>(type);
124    }
125    inline void ClearNoneEmptyBit(SetType type)
126    {
127        noneEmptySetBitMap_ &= ~(1ULL << static_cast<uint32_t>(type));
128    }
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