1 /** 2 * Copyright (c) 2021-2024 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 PANDA_MEM_GC_G1_REM_SET_H 17 #define PANDA_MEM_GC_G1_REM_SET_H 18 19 #include <limits> 20 #include <runtime/include/mem/panda_containers.h> 21 22 namespace ark::mem { 23 24 namespace test { 25 class RemSetTest; 26 } // namespace test 27 28 class RemSetLockConfig { 29 public: 30 using CommonLock = os::memory::RecursiveMutex; 31 using DummyLock = os::memory::DummyLock; 32 }; 33 34 class Region; 35 36 /// @brief Set in the Region. To record the regions and cards reference to this region. 37 template <typename LockConfigT = RemSetLockConfig::CommonLock> 38 class RemSet { 39 public: 40 RemSet() = default; 41 ~RemSet(); 42 43 NO_COPY_SEMANTIC(RemSet); 44 NO_MOVE_SEMANTIC(RemSet); 45 46 template <bool NEED_LOCK = true> 47 void AddRef(const ObjectHeader *fromObjAddr, size_t offset); 48 template <bool NEED_LOCK = true> 49 void AddRef(const void *fromAddr); 50 51 template <typename RegionPred, typename MemVisitor> 52 void Iterate(const RegionPred ®ionPred, const MemVisitor &visitor); 53 template <typename Visitor> 54 void IterateOverObjects(const Visitor &visitor); 55 56 void Clear(); 57 58 template <bool NEED_LOCK = true> 59 static void InvalidateRegion(Region *invalidRegion); 60 61 template <bool NEED_LOCK = true> 62 static void InvalidateRefsFromRegion(Region *invalidRegion); 63 Size()64 size_t Size() const 65 { 66 return bitmaps_.size(); 67 } 68 69 void Merge(RemSet<> *other); 70 PandaUnorderedSet<Region *> GetDirtyRegions(); 71 72 /** 73 * Used in the barrier. Record the reference from the region of objAddr to the region of valueAddr. 74 * @param objAddr - address of the object 75 * @param offset - offset in the object where value is stored 76 * @param valueAddr - address of the reference in the field 77 */ 78 template <bool NEED_LOCK = true> 79 static void AddRefWithAddr(const ObjectHeader *objAddr, size_t offset, const ObjectHeader *valueAddr); 80 81 /** 82 * Used in the barrier. Record the reference from the region of fromAddr to the region of valueAddr. 83 * @param fromRemset - pointer to remset of region which contains fromAddr object (avoid region resolving on each 84 * call) 85 * @param fromAddr - pointer to the reference in the object where value is stored 86 * @param valueAddr - address of the reference in the field 87 */ 88 template <bool NEED_LOCK = true> 89 static void AddRefWithAddr(RemSet<> *fromRemset, const void *fromAddr, const ObjectHeader *valueAddr); 90 91 void Dump(std::ostream &out); 92 93 template <typename Visitor> 94 void VisitBitmaps(const Visitor &visitor) const; 95 96 static size_t GetIdxInBitmap(uintptr_t addr, uintptr_t bitmapBeginAddr); 97 98 class Bitmap { 99 public: GetBitmapSizeInBytes()100 static constexpr size_t GetBitmapSizeInBytes() 101 { 102 return sizeof(bitmap_); 103 } 104 GetNumBits()105 static constexpr size_t GetNumBits() 106 { 107 return GetBitmapSizeInBytes() * BITS_PER_BYTE; 108 } 109 Merge(Bitmap other)110 void Merge(Bitmap other) 111 { 112 for (size_t i = 0; i < SIZE; i++) { 113 bitmap_[i] |= other.bitmap_[i]; 114 } 115 } 116 Set(size_t idx)117 void Set(size_t idx) 118 { 119 size_t elemIdx = idx / ELEM_BITS; 120 ASSERT(elemIdx < SIZE); 121 size_t bitOffset = idx - elemIdx * ELEM_BITS; 122 bitmap_[elemIdx] |= 1ULL << bitOffset; 123 } 124 Check(size_t idx)125 bool Check(size_t idx) const 126 { 127 size_t elemIdx = idx / ELEM_BITS; 128 ASSERT(elemIdx < SIZE); 129 size_t bitOffset = idx - elemIdx * ELEM_BITS; 130 return (bitmap_[elemIdx] & (1ULL << bitOffset)) != 0; 131 } 132 AddBits(const Bitmap & other)133 void AddBits(const Bitmap &other) 134 { 135 for (size_t i = 0; i < SIZE; ++i) { 136 bitmap_[i] |= other.bitmap_[i]; 137 } 138 } 139 140 template <typename Visitor> Iterate(const MemRange & range,const Visitor & visitor)141 void Iterate(const MemRange &range, const Visitor &visitor) const 142 { 143 size_t memSize = (range.GetEndAddress() - range.GetStartAddress()) / GetNumBits(); 144 uintptr_t startAddr = range.GetStartAddress(); 145 for (size_t i = 0; i < SIZE; ++i) { 146 uintptr_t addr = startAddr + i * memSize * ELEM_BITS; 147 uint64_t elem = bitmap_[i]; 148 while (elem > 0) { 149 if (elem & 1ULL) { 150 visitor(MemRange(addr, addr + memSize)); 151 } 152 elem >>= 1ULL; 153 addr += memSize; 154 } 155 } 156 } 157 158 private: 159 static constexpr size_t SIZE = 8U; 160 static constexpr size_t ELEM_BITS = std::numeric_limits<uint64_t>::digits; 161 std::array<uint64_t, SIZE> bitmap_ {0}; 162 }; 163 164 private: 165 template <bool NEED_LOCK> 166 PandaUnorderedSet<Region *> *GetRefRegions(); 167 template <bool NEED_LOCK> 168 void AddRefRegion(Region *region); 169 template <bool NEED_LOCK> 170 void RemoveFromRegion(Region *region); 171 template <bool NEED_LOCK> 172 void RemoveRefRegion(Region *region); 173 174 LockConfigT remSetLock_; 175 // NOTE(alovkov): make value a Set? 176 PandaUnorderedMap<uintptr_t, Bitmap> bitmaps_; 177 PandaUnorderedSet<Region *> refRegions_; 178 179 friend class test::RemSetTest; 180 }; 181 182 class GlobalRemSet { 183 public: 184 template <typename RegionContainer, typename RegionPred, typename MemVisitor> 185 void ProcessRemSets(const RegionContainer &cont, const RegionPred ®ionPred, const MemVisitor &visitor); 186 187 template <typename MemVisitor> 188 bool IterateOverUniqueRange(Region *region, MemRange range, const MemVisitor &visitor); 189 190 private: 191 template <typename RegionPred> 192 void FillBitmap(const RemSet<> &remSet, const RegionPred ®ionPred); 193 194 template <typename MemVisitor> 195 void IterateOverBits(const MemVisitor &visitor) const; 196 197 PandaUnorderedMap<uintptr_t, RemSet<>::Bitmap> bitmaps_; 198 }; 199 200 } // namespace ark::mem 201 #endif // PANDA_MEM_GC_G1_REM_SET_H 202