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 
28 namespace panda::ecmascript {
29 enum class AccessType { ATOMIC, NON_ATOMIC };
30 
31 class GCBitset {
32 public:
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 
SizeOfGCBitset(size_t heapSize)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 
Words()55     GCBitsetWord *Words()
56     {
57         return reinterpret_cast<GCBitsetWord *>(this);
58     }
59 
TwoWords()60     GCBitsetTwoWords *TwoWords()
61     {
62         return reinterpret_cast<GCBitsetTwoWords *>(this);
63     }
64 
Words() const65     const GCBitsetWord *Words() const
66     {
67         return reinterpret_cast<const GCBitsetWord *>(this);
68     }
69 
SetGCWords(uint32_t index)70     void SetGCWords(uint32_t index) // Only used for snapshot to record region index
71     {
72         *reinterpret_cast<GCBitsetWord *>(this) = index;
73     }
74 
Clear(size_t bitSize)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 
SetAllBits(size_t bitSize)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 
ClearBit(uintptr_t offset)99     void ClearBit(uintptr_t offset)
100     {
101         Words()[Index(offset)] &= ~Mask(IndexInWord(offset));
102     }
103 
104     template <AccessType mode = AccessType::NON_ATOMIC>
ClearBitRange(uintptr_t offsetBegin, uintptr_t offsetEnd)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 
TestBit(uintptr_t offset) const125     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>
IterateMarkedBits(uintptr_t begin, size_t bitSize, Visitor visitor)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 
178 private:
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 
235 inline 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 
242 template <>
243 inline 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 
254 template <>
255 inline 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 
272 template <size_t BitSetNum, typename Enable = std::enable_if_t<(BitSetNum >= 1), int>>
273 class GCBitSetUpdater {
274 public:
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 
310 private:
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