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) const; 53 template <typename Visitor> 54 void IterateOverObjects(const Visitor &visitor) const; 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 Set(size_t idx)110 void Set(size_t idx) 111 { 112 size_t elemIdx = idx / ELEM_BITS; 113 ASSERT(elemIdx < SIZE); 114 size_t bitOffset = idx - elemIdx * ELEM_BITS; 115 bitmap_[elemIdx] |= 1ULL << bitOffset; 116 } 117 Check(size_t idx)118 bool Check(size_t idx) const 119 { 120 size_t elemIdx = idx / ELEM_BITS; 121 ASSERT(elemIdx < SIZE); 122 size_t bitOffset = idx - elemIdx * ELEM_BITS; 123 return (bitmap_[elemIdx] & (1ULL << bitOffset)) != 0; 124 } 125 AddBits(const Bitmap & other)126 void AddBits(const Bitmap &other) 127 { 128 for (size_t i = 0; i < SIZE; ++i) { 129 bitmap_[i] |= other.bitmap_[i]; 130 } 131 } 132 133 template <typename Visitor> Iterate(const MemRange & range,const Visitor & visitor)134 void Iterate(const MemRange &range, const Visitor &visitor) const 135 { 136 size_t memSize = (range.GetEndAddress() - range.GetStartAddress()) / GetNumBits(); 137 uintptr_t startAddr = range.GetStartAddress(); 138 for (size_t i = 0; i < SIZE; ++i) { 139 uintptr_t addr = startAddr + i * memSize * ELEM_BITS; 140 uint64_t elem = bitmap_[i]; 141 while (elem > 0) { 142 if (elem & 1ULL) { 143 visitor(MemRange(addr, addr + memSize)); 144 } 145 elem >>= 1ULL; 146 addr += memSize; 147 } 148 } 149 } 150 151 private: 152 static constexpr size_t SIZE = 8U; 153 static constexpr size_t ELEM_BITS = std::numeric_limits<uint64_t>::digits; 154 std::array<uint64_t, SIZE> bitmap_ {0}; 155 }; 156 157 private: 158 template <bool NEED_LOCK> 159 PandaUnorderedSet<Region *> *GetRefRegions(); 160 template <bool NEED_LOCK> 161 void AddRefRegion(Region *region); 162 template <bool NEED_LOCK> 163 void RemoveFromRegion(Region *region); 164 template <bool NEED_LOCK> 165 void RemoveRefRegion(Region *region); 166 167 LockConfigT remSetLock_; 168 // NOTE(alovkov): make value a Set? 169 PandaUnorderedMap<uintptr_t, Bitmap> bitmaps_; 170 PandaUnorderedSet<Region *> refRegions_; 171 172 friend class test::RemSetTest; 173 }; 174 175 class GlobalRemSet { 176 public: 177 template <typename RegionContainer, typename RegionPred, typename MemVisitor> 178 void ProcessRemSets(const RegionContainer &cont, const RegionPred ®ionPred, const MemVisitor &visitor); 179 180 template <typename MemVisitor> 181 bool IterateOverUniqueRange(Region *region, MemRange range, const MemVisitor &visitor); 182 183 private: 184 template <typename RegionPred> 185 void FillBitmap(const RemSet<> &remSet, const RegionPred ®ionPred); 186 187 template <typename MemVisitor> 188 void IterateOverBits(const MemVisitor &visitor) const; 189 190 PandaUnorderedMap<uintptr_t, RemSet<>::Bitmap> bitmaps_; 191 }; 192 193 } // namespace ark::mem 194 #endif // PANDA_MEM_GC_G1_REM_SET_H 195