1/*
2 * Copyright (c) 2022 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_GC_BITSET__H
17#define ECMASCRIPT_MEM_GC_BITSET__H
18
19#include <atomic>
20#include <bitset>
21
22#include "ecmascript/base/math_helper.h"
23#include "ecmascript/mem/mem.h"
24
25// |----word(32 bit)----|----word(32 bit)----|----...----|----word(32 bit)----|----word(32 bit)----|
26// |---------------------------------------GCBitset(4 kb)------------------------------------------|
27
28namespace panda::ecmascript {
29enum class AccessType { ATOMIC, NON_ATOMIC };
30
31class GCBitset {
32public:
33    using GCBitsetWord = uint32_t;
34    using GCBitsetTwoWords = uint64_t;
35    static constexpr uint32_t BYTE_PER_WORD = sizeof(GCBitsetWord);
36    static constexpr uint32_t BYTE_PER_WORD_LOG2 = base::MathHelper::GetIntLog2(BYTE_PER_WORD);
37    static constexpr uint32_t BIT_PER_BYTE = 8;
38    static constexpr uint32_t BIT_PER_BYTE_LOG2 = base::MathHelper::GetIntLog2(BIT_PER_BYTE);
39    static constexpr uint32_t BIT_PER_WORD = BYTE_PER_WORD * BIT_PER_BYTE;
40    static constexpr uint32_t BIT_PER_WORD_LOG2 = base::MathHelper::GetIntLog2(BIT_PER_WORD);
41    static constexpr uint32_t BIT_PER_WORD_MASK = BIT_PER_WORD - 1;
42
43    GCBitset() = default;
44    ~GCBitset() = default;
45
46    NO_COPY_SEMANTIC(GCBitset);
47    NO_MOVE_SEMANTIC(GCBitset);
48
49    static size_t SizeOfGCBitset(size_t heapSize)
50    {
51        size_t bitSize = AlignUp(heapSize, TAGGED_TYPE_SIZE) >> TAGGED_TYPE_SIZE_LOG;
52        return AlignUp(AlignUp(bitSize, BIT_PER_BYTE) >> BIT_PER_BYTE_LOG2, BYTE_PER_WORD);
53    }
54
55    GCBitsetWord *Words()
56    {
57        return reinterpret_cast<GCBitsetWord *>(this);
58    }
59
60    GCBitsetTwoWords *TwoWords()
61    {
62        return reinterpret_cast<GCBitsetTwoWords *>(this);
63    }
64
65    const GCBitsetWord *Words() const
66    {
67        return reinterpret_cast<const GCBitsetWord *>(this);
68    }
69
70    void SetGCWords(uint32_t index) // Only used for snapshot to record region index
71    {
72        *reinterpret_cast<GCBitsetWord *>(this) = index;
73    }
74
75    void Clear(size_t bitSize)
76    {
77        GCBitsetWord *words = Words();
78        uint32_t wordCount = static_cast<uint32_t>(WordCount(bitSize));
79        for (uint32_t i = 0; i < wordCount; i++) {
80            words[i] = 0;
81        }
82    }
83
84    void SetAllBits(size_t bitSize)
85    {
86        GCBitsetWord *words = Words();
87        uint32_t wordCount = static_cast<uint32_t>(WordCount(bitSize));
88        GCBitsetWord mask = 0;
89        for (uint32_t i = 0; i < wordCount; i++) {
90            words[i] = ~mask;
91        }
92    }
93
94    template <AccessType mode = AccessType::NON_ATOMIC>
95    bool SetBit(uintptr_t offset);
96
97    bool SetBitRange(uintptr_t offset, uint32_t mask);
98
99    void ClearBit(uintptr_t offset)
100    {
101        Words()[Index(offset)] &= ~Mask(IndexInWord(offset));
102    }
103
104    template <AccessType mode = AccessType::NON_ATOMIC>
105    void ClearBitRange(uintptr_t offsetBegin, uintptr_t offsetEnd)
106    {
107        GCBitsetWord *words = Words();
108        uint32_t startIndex = Index(offsetBegin);
109        uint32_t startIndexMask = Mask(IndexInWord(offsetBegin));
110        ASSERT(offsetEnd > 0);
111        uint32_t endIndex = Index(offsetEnd - 1);
112        uint32_t endIndexMask = Mask(IndexInWord(offsetEnd - 1));
113        ASSERT(startIndex <= endIndex);
114        if (startIndex != endIndex) {
115            ClearWord<mode>(startIndex, ~(startIndexMask - 1));
116            ClearWord<mode>(endIndex, endIndexMask | (endIndexMask - 1));
117            while (++startIndex < endIndex) {
118                words[startIndex] = 0;
119            }
120        } else {
121            ClearWord<mode>(endIndex, endIndexMask | (endIndexMask - startIndexMask));
122        }
123    }
124
125    bool TestBit(uintptr_t offset) const
126    {
127        return Words()[Index(offset)] & Mask(IndexInWord(offset));
128    }
129
130    template <typename Visitor, AccessType mode = AccessType::NON_ATOMIC>
131    void IterateMarkedBits(uintptr_t begin, size_t bitSize, Visitor visitor)
132    {
133        auto words = Words();
134        uint32_t wordCount = WordCount(bitSize);
135        uint32_t index = BIT_PER_WORD;
136        for (uint32_t i = 0; i < wordCount; i++) {
137            uint32_t word = words[i];
138            while (word != 0) {
139                index = static_cast<uint32_t>(__builtin_ctz(word));
140                ASSERT(index < BIT_PER_WORD);
141                if (!visitor(reinterpret_cast<void *>(begin + (index << TAGGED_TYPE_SIZE_LOG)))) {
142                    ClearWord<mode>(i, Mask(index));
143                }
144                word &= ~(1u << index);
145            }
146            begin += TAGGED_TYPE_SIZE * BIT_PER_WORD;
147        }
148    }
149
150    template <typename Visitor>
151    void IterateMarkedBitsConst(uintptr_t begin, size_t bitSize, Visitor visitor) const
152    {
153        auto words = Words();
154        uint32_t wordCount = WordCount(bitSize);
155        uint32_t index = BIT_PER_WORD;
156        for (uint32_t i = 0; i < wordCount; i++) {
157            uint32_t word = words[i];
158            while (word != 0) {
159                index = static_cast<uint32_t>(__builtin_ctz(word));
160                ASSERT(index < BIT_PER_WORD);
161                visitor(reinterpret_cast<void *>(begin + (index << TAGGED_TYPE_SIZE_LOG)));
162                word &= ~(1u << index);
163            }
164            begin += TAGGED_TYPE_SIZE * BIT_PER_WORD;
165        }
166    }
167
168    void Merge(GCBitset *bitset, size_t bitSize)
169    {
170        ASSERT(bitSize % sizeof(GCBitsetTwoWords) == 0);
171        auto words = TwoWords();
172        uint32_t wordCount = TwoWordsCount(bitSize);
173        for (uint32_t i = 0; i < wordCount; i++) {
174            words[i] |= bitset->TwoWords()[i];
175        }
176    }
177
178private:
179    GCBitsetWord Mask(size_t index) const
180    {
181        return 1 << index;
182    }
183
184    size_t IndexInWord(uintptr_t offset) const
185    {
186        return offset & BIT_PER_WORD_MASK;
187    }
188
189    size_t Index(uintptr_t offset) const
190    {
191        return offset >> BIT_PER_WORD_LOG2;
192    }
193
194    size_t WordCount(size_t size) const
195    {
196        return size >> BYTE_PER_WORD_LOG2;
197    }
198
199    size_t TwoWordsCount(size_t size) const
200    {
201        return size >> (BYTE_PER_WORD_LOG2 + 1);
202    }
203
204    template <AccessType mode = AccessType::NON_ATOMIC>
205    bool ClearWord(uint32_t index, uint32_t mask);
206
207    template <>
208    bool ClearWord<AccessType::NON_ATOMIC>(uint32_t index, uint32_t mask)
209    {
210        if ((Words()[index] & mask) == 0) {
211            return false;
212        }
213        Words()[index] &= ~mask;
214        return true;
215    }
216
217    template <>
218    bool ClearWord<AccessType::ATOMIC>(uint32_t index, uint32_t mask)
219    {
220        volatile auto word = reinterpret_cast<volatile std::atomic<GCBitsetWord> *>(&Words()[index]);
221        auto oldValue = word->load(std::memory_order_relaxed);
222        GCBitsetWord oldValueBeforeCAS;
223        do {
224            if ((oldValue & mask) == 0) {
225                return false;
226            }
227            oldValueBeforeCAS = oldValue;
228            std::atomic_compare_exchange_strong_explicit(word, &oldValue, oldValue & (~mask),
229                std::memory_order_release, std::memory_order_relaxed);
230        } while (oldValue != oldValueBeforeCAS);
231        return true;
232    }
233};
234
235inline bool GCBitset::SetBitRange(uintptr_t offset, uint32_t mask)
236{
237    size_t index = Index(offset);
238    Words()[index] |= mask;
239    return true;
240}
241
242template <>
243inline bool GCBitset::SetBit<AccessType::NON_ATOMIC>(uintptr_t offset)
244{
245    size_t index = Index(offset);
246    GCBitsetWord mask = Mask(IndexInWord(offset));
247    if (Words()[index] & mask) {
248        return false;
249    }
250    Words()[index] |= mask;
251    return true;
252}
253
254template <>
255inline bool GCBitset::SetBit<AccessType::ATOMIC>(uintptr_t offset)
256{
257    volatile auto word = reinterpret_cast<volatile std::atomic<GCBitsetWord> *>(&Words()[Index(offset)]);
258    auto mask = Mask(IndexInWord(offset));
259    auto oldValue = word->load(std::memory_order_relaxed);
260    GCBitsetWord oldValueBeforeCAS;
261    do {
262        if (oldValue & mask) {
263            return false;
264        }
265        oldValueBeforeCAS = oldValue;
266        std::atomic_compare_exchange_strong_explicit(word, &oldValue, oldValue | mask,
267            std::memory_order_release, std::memory_order_relaxed);
268    } while (oldValue != oldValueBeforeCAS);
269    return true;
270}
271
272template <size_t BitSetNum, typename Enable = std::enable_if_t<(BitSetNum >= 1), int>>
273class GCBitSetUpdater {
274public:
275    GCBitSetUpdater() = delete;
276
277    explicit GCBitSetUpdater(uintptr_t updateAddress)
278        : updateAddress_(updateAddress),
279          cursor_((updateAddress >> TAGGED_TYPE_SIZE_LOG) & GCBitset::BIT_PER_WORD_MASK)
280    {
281    }
282
283    NO_COPY_SEMANTIC(GCBitSetUpdater);
284
285    ARK_INLINE void Update(size_t setIdx)
286    {
287        ASSERT(setIdx < BitSetNum);
288        bitsets_[setIdx].set(cursor_);
289    }
290
291    ARK_INLINE bool Next()
292    {
293        cursor_++;
294        ASSERT(cursor_ <= GCBitset::BIT_PER_WORD);
295        return cursor_ == GCBitset::BIT_PER_WORD;
296    }
297
298    ARK_INLINE std::array<std::bitset<GCBitset::BIT_PER_WORD>, BitSetNum> GetAndResetAll(uintptr_t& updateAddress)
299    {
300        std::array<std::bitset<GCBitset::BIT_PER_WORD>, BitSetNum> retBitsets;
301        std::swap(retBitsets, bitsets_);
302        updateAddress = updateAddress_;
303
304        cursor_ = 0;
305        constexpr size_t ConsumeRange = GCBitset::BIT_PER_WORD * GCBitset::BIT_PER_BYTE;
306        updateAddress_ = AlignDown(updateAddress_ + ConsumeRange, ConsumeRange);
307        return retBitsets;
308    }
309
310private:
311    uintptr_t updateAddress_ = 0;
312    std::array<std::bitset<GCBitset::BIT_PER_WORD>, BitSetNum> bitsets_;
313    size_t cursor_ = 0;
314};
315} // namespace panda::ecmascript
316#endif  // ECMASCRIPT_MEM_GC_BITSET__H
317