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