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