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 ACCOUNTING_CARD_TABLE_H 17 #define ACCOUNTING_CARD_TABLE_H 18 19 #include <atomic> 20 #include <cstddef> 21 #include <cstdint> 22 #include <type_traits> 23 24 #include "runtime/include/mem/panda_containers.h" 25 26 namespace ark::mem { 27 28 template <typename PtrType> 29 class CardPtrIterator { 30 public: 31 using Reference = PtrType &; 32 using ConstReference = typename std::add_const<PtrType &>::type; 33 using Pointer = PtrType *; 34 35 // NOLINTNEXTLINE(readability-identifier-naming) CardPtrIterator(PtrType c)36 explicit CardPtrIterator(PtrType c) : card_(c) {} 37 38 CardPtrIterator &operator++() 39 { 40 card_ += 1; 41 return *this; 42 } 43 44 // NOLINTNEXTLINE(cert-dcl21-cpp) 45 CardPtrIterator operator++(int) 46 { 47 CardPtrIterator retval = *this; 48 ++(*this); 49 return retval; 50 } 51 52 bool operator==(CardPtrIterator other) const 53 { 54 return card_ == other.card_; 55 } 56 57 bool operator!=(CardPtrIterator other) const 58 { 59 return !(*this == other); 60 } 61 62 ConstReference operator*() const 63 { 64 return card_; 65 } 66 67 Reference operator*() 68 { 69 return card_; 70 } 71 72 virtual ~CardPtrIterator() = default; 73 74 DEFAULT_COPY_SEMANTIC(CardPtrIterator); 75 NO_MOVE_SEMANTIC(CardPtrIterator); 76 77 private: 78 // NOLINTNEXTLINE(readability-identifier-naming) 79 PtrType card_; 80 }; 81 82 enum CardTableProcessedFlag : uint32_t { 83 VISIT_MARKED = 1U, // visit marked cards 84 VISIT_PROCESSED = 1U << 1U, // visit parocessed cards 85 SET_PROCESSED = 1U << 2U, // set the visited cards processed 86 }; 87 88 /** 89 * --------------------------------------------------------------------------------------- 90 * | Card | 91 * --------------------------------------------------------------------------------------- 92 * | | | | | | | | 93 * | 0 | | 0 | 0 | 0 | | 0 | 0 | | 0 | 0 | 94 * | | | | | | | | 95 * ----------- ----------------------------------------------------- --------------------- 96 * | | | | 97 * ---- hot flag ---- hotness value ---- unused bits ---- status bits 98 */ 99 class CardTable { 100 public: 101 class Card; 102 using CardPtr = Card *; 103 using CardAddress = uintptr_t; 104 using Iterator = CardPtrIterator<CardPtr>; 105 using ConstIterator = CardPtrIterator<const CardPtr>; 106 107 explicit CardTable(InternalAllocatorPtr internalAllocator, uintptr_t minAddress, size_t size); 108 ~CardTable(); 109 CardTable(const CardTable &other) = delete; 110 CardTable &operator=(const CardTable &other) = delete; 111 CardTable(CardTable &&other) = delete; 112 CardTable &operator=(CardTable &&other) = delete; 113 114 void Initialize(); 115 bool IsMarked(uintptr_t addr) const; // returns true if the card(for the addr) state is marked 116 void MarkCard(uintptr_t addr); // set card state to the marked 117 bool IsClear(uintptr_t addr) const; // returns true if the card(for the addr) state is clear 118 void ClearCard(uintptr_t addr); // set card state to the cleared 119 void ClearAll(); // set card state to the cleared for the all cards 120 void ClearCardRange(uintptr_t beginAddr, uintptr_t endAddr); GetCardSize()121 static constexpr uint32_t GetCardSize() 122 { 123 return CARD_SIZE; 124 } GetCardsCount()125 size_t GetCardsCount() const 126 { 127 return cardsCount_; 128 } 129 130 uintptr_t GetCardStartAddress(CardPtr card) const; // returns address of the first byte in the card 131 uintptr_t GetCardEndAddress(CardPtr card) const; // returns address of the last byte in the card 132 MemRange GetMemoryRange(CardPtr card) const; // returns memory range for the card 133 134 template <typename CardVisitor> 135 void VisitMarked(CardVisitor cardVisitor, uint32_t processedFlag); 136 137 template <typename CardVisitor> 138 void VisitMarkedCompact(CardVisitor cardVisitor); 139 140 // NOLINTNEXTLINE(readability-identifier-naming) begin()141 Iterator begin() 142 { 143 return Iterator(cards_); 144 } 145 146 // NOLINTNEXTLINE(readability-identifier-naming) end()147 Iterator end() 148 { 149 return Iterator(cards_ + cardsCount_); 150 } 151 152 // NOLINTNEXTLINE(readability-identifier-naming) begin()153 ConstIterator begin() const 154 { 155 return ConstIterator(cards_); 156 } 157 158 // NOLINTNEXTLINE(readability-identifier-naming) end()159 ConstIterator end() const 160 { 161 return ConstIterator(cards_ + cardsCount_); 162 } 163 GetCardBits()164 static constexpr uint8_t GetCardBits() 165 { 166 return LOG2_CARD_SIZE; 167 } 168 GetCardDirtyValue()169 static constexpr uint8_t GetCardDirtyValue() 170 { 171 return DIRTY_CARD; 172 } 173 174 #ifndef NDEBUG 175 bool IsClear(); 176 #endif 177 178 class Card { 179 public: 180 using Status = uint8_t; 181 182 Card() = default; 183 explicit Card(uint8_t val); 184 185 void Mark(); 186 void UnMark(); 187 void Clear(); 188 void SetProcessed(); 189 void SetYoung(); 190 uint8_t GetCard() const; 191 void SetCard(uint8_t newVal); 192 Status GetStatus() const; 193 194 bool IsMarked() const; 195 bool IsClear() const; 196 bool IsProcessed() const; 197 bool IsYoung() const; 198 199 static bool IsMarked(Status status); 200 static bool IsProcessed(Status status); 201 static bool IsYoung(Status status); 202 203 bool IsHot() const; 204 void SetHot(); 205 void ResetHot(); 206 void SetMaxHotValue(); 207 void IncrementHotValue(); 208 void DecrementHotValue(); 209 210 static bool IsMaxHotValue(uint8_t value); 211 static bool IsMinHotValue(uint8_t value); 212 static bool IsHot(uint8_t value); 213 214 static Status GetStatus(uint8_t value); 215 GetValueOffset()216 static constexpr uint32_t GetValueOffset() 217 { 218 return MEMBER_OFFSET(Card, value_); 219 } 220 GetClearValue()221 static constexpr auto GetClearValue() 222 { 223 return CLEAR_VALUE; 224 } 225 GetMarkedValue()226 static constexpr auto GetMarkedValue() 227 { 228 return MARKED_VALUE; 229 } 230 GetYoungValue()231 static constexpr auto GetYoungValue() 232 { 233 return YOUNG_VALUE; 234 } 235 GetMaxHotValue()236 static constexpr auto GetMaxHotValue() 237 { 238 return MAX_HOT_VALUE; 239 } 240 GetHotValue()241 static constexpr auto GetHotValue() 242 { 243 return HOT_VALUE; 244 } 245 GetHotFlag()246 static constexpr auto GetHotFlag() 247 { 248 return HOT_FLAG; 249 } 250 GetStatusMask()251 static constexpr auto GetStatusMask() 252 { 253 return STATUS_MASK; 254 } 255 256 ~Card() = default; 257 258 NO_COPY_SEMANTIC(Card); 259 NO_MOVE_SEMANTIC(Card); 260 261 private: 262 static constexpr uint8_t YOUNG_VALUE = 3U; 263 static constexpr uint8_t PROCESSED_VALUE = 2U; 264 static constexpr uint8_t MARKED_VALUE = 1U; 265 static constexpr uint8_t CLEAR_VALUE = 0U; 266 static constexpr uint8_t STATUS_MASK = 3U; 267 static constexpr uint8_t STATUS_BITS = 2U; 268 static constexpr uint8_t UNUSED_BITS = 2U; 269 static constexpr uint8_t HOT_VALUE = 1U << (uint8_t)(STATUS_BITS + UNUSED_BITS); 270 static constexpr uint8_t MAX_HOT_VALUE = 7U << (uint8_t)(STATUS_BITS + UNUSED_BITS); 271 static constexpr uint8_t HOT_FLAG = 1U << 7U; 272 273 std::atomic_uint8_t value_ = CLEAR_VALUE; 274 }; 275 276 CardPtr GetCardPtr(uintptr_t addr) const; // returns card address for the addr 277 GetMinAddress()278 ALWAYS_INLINE uintptr_t GetMinAddress() const 279 { 280 return minAddress_; 281 } 282 283 void MarkCardsAsYoung(const MemRange &memRange); 284 285 private: 286 void ClearCards(CardPtr start, size_t cardCount); 287 size_t GetSize() const; // returns size of card table array 288 inline void FillRanges(PandaVector<MemRange> *ranges, const Card *startCard, const Card *endCard); 289 290 static constexpr uint8_t LOG2_CARD_SIZE = 12; 291 static constexpr uint32_t CARD_SIZE = 1U << LOG2_CARD_SIZE; 292 static constexpr uint8_t DIRTY_CARD = 1U; 293 static constexpr size_t CHUNK_CARD_NUM = sizeof(std::atomic_size_t) / sizeof(Card); 294 295 CardPtr cards_ {nullptr}; 296 uintptr_t minAddress_ {0}; 297 size_t cardsCount_ {0}; 298 InternalAllocatorPtr internalAllocator_ {nullptr}; 299 }; 300 301 static_assert(sizeof(std::atomic_size_t) % sizeof(CardTable::Card) == 0); 302 303 using CardVisitor = std::function<void(CardTable::CardPtr)>; 304 305 } // namespace ark::mem 306 307 #endif // ACCOUNTING_CARD_TABLE_H 308