1 /** 2 * Copyright (c) 2021-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 #ifndef PANDA_MEM_GC_CROSSING_MAP_H 16 #define PANDA_MEM_GC_CROSSING_MAP_H 17 18 #include <array> 19 #include <limits> 20 21 #include "libpandabase/mem/mem.h" 22 #include "libpandabase/utils/logger.h" 23 #include "runtime/include/mem/allocator.h" 24 #include "runtime/mem/runslots.h" 25 26 namespace panda::mem { 27 28 static constexpr uint64_t PANDA_CROSSING_MAP_COVERAGE = PANDA_MAX_HEAP_SIZE; 29 // If enabled - we will manage elements, which cross map borders. 30 // since now we dirty card by object header, so disable cross-border 31 static constexpr bool PANDA_CROSSING_MAP_MANAGE_CROSSED_BORDER = false; 32 static constexpr size_t PANDA_CROSSING_MAP_GRANULARITY = PAGE_SIZE; 33 // TODO(aemelenko): Now, we can't change the granularity parameter here 34 // because IteratingOverObjectsInRange is depended on it 35 static_assert(PANDA_CROSSING_MAP_GRANULARITY == PAGE_SIZE); 36 37 // CrossingMap structure is a double linked array: 38 // 39 // Each static array has a link to dynamic map 40 // which will be dynamically allocated/deallocated via internal allocator: 41 // |-------|-------|-------|-------|-------|-------| 42 // | | | | | | | 43 // |-------|-------|-------|-------|-------|-------| 44 // | | | | | | 45 // | | | | | | 46 // nullptr | nullptr nullptr nullptr nullptr 47 // | 48 // | 49 // | 50 // | 51 // |-----|-----|-----| 52 // | | | | 53 // |-----|-----|-----| 54 // dynamic map 55 // 56 57 // Each page from PANDA_CROSSING_MAP_COVERAGE heap space has its element in crossing map. 58 // This element (or map) can be used to get the first object address, which starts inside this page (if it exists) 59 // or an object address, which crosses the borders of this page. 60 class CrossingMap { 61 public: 62 /** 63 * \brief Create a new instance of a Crossing map. 64 * @param internal_allocator - pointer to the internal allocator. 65 * @param start_addr - first bit of the memory which must be covered by the Crossing Map. 66 * @param size - size of the memory which must be covered by the Crossing Map. 67 */ 68 explicit CrossingMap(InternalAllocatorPtr internal_allocator, uintptr_t start_addr, size_t size); 69 ~CrossingMap(); 70 NO_COPY_SEMANTIC(CrossingMap); 71 NO_MOVE_SEMANTIC(CrossingMap); 72 73 void Initialize(); 74 void Destroy(); 75 76 /** 77 * \brief Add object to the Crossing map. 78 * @param obj_addr - pointer to the object (object header). 79 * @param obj_size - size of the object. 80 */ 81 void AddObject(const void *obj_addr, size_t obj_size); 82 83 /** 84 * \brief Remove object from the Crossing map. 85 * Crossing map doesn't know about existed objects (it knows only about first). 86 * Therefore, during removing we need to send next and previous object parameters. 87 * @param obj_addr - pointer to the removing object (object header). 88 * @param obj_size - size of the removing object. 89 * @param next_obj_addr - pointer to the next object (object header). It can be nullptr. 90 * @param prev_obj_addr - pointer to the previous object (object header). It can be nullptr. 91 * @param prev_obj_size - size of the previous object. 92 * It is used check if previous object crosses the borders of the current map. 93 */ 94 void RemoveObject(const void *obj_addr, size_t obj_size, const void *next_obj_addr = nullptr, 95 const void *prev_obj_addr = nullptr, size_t prev_obj_size = 0); 96 97 /** 98 * \brief Find and return the first object, which starts in an interval inclusively 99 * or an object, which crosses the interval border. 100 * It is essential to check the previous object of the returned object to make sure that 101 * we find the first object, which crosses the border of this interval. 102 * @param start_addr - pointer to the first byte of the interval. 103 * @param end_addr - pointer to the last byte of the interval. 104 * @return Returns the first object which starts inside an interval, 105 * or an object which crosses a border of this interval 106 * or nullptr 107 */ 108 void *FindFirstObject(const void *start_addr, const void *end_addr); 109 110 /** 111 * \brief Initialize a Crossing map for the corresponding memory ranges. 112 * @param start_addr - pointer to the first byte of the interval. 113 * @param size - size of the interval. 114 */ 115 void InitializeCrossingMapForMemory(const void *start_addr, size_t size); 116 117 /** 118 * \brief Remove a Crossing map for the corresponding memory ranges. 119 * @param start_addr - pointer to the first byte of the interval. 120 * @param size - size of the interval. 121 */ 122 void RemoveCrossingMapForMemory(const void *start_addr, size_t size); 123 124 private: 125 static constexpr bool CROSSING_MAP_MANAGE_CROSSED_BORDER = PANDA_CROSSING_MAP_MANAGE_CROSSED_BORDER; 126 static constexpr size_t CROSSING_MAP_GRANULARITY = PANDA_CROSSING_MAP_GRANULARITY; 127 // How much memory we manage via one element of the static array. 128 static constexpr size_t CROSSING_MAP_STATIC_ARRAY_GRANULARITY = PANDA_POOL_ALIGNMENT_IN_BYTES; 129 static constexpr Alignment CROSSING_MAP_OBJ_ALIGNMENT = DEFAULT_ALIGNMENT; 130 using CROSSING_MAP_TYPE = uint16_t; 131 132 static_assert(CROSSING_MAP_STATIC_ARRAY_GRANULARITY % CROSSING_MAP_GRANULARITY == 0); 133 static constexpr size_t CROSSING_MAP_COUNT_IN_STATIC_ARRAY_ELEMENT = 134 CROSSING_MAP_STATIC_ARRAY_GRANULARITY / CROSSING_MAP_GRANULARITY; 135 136 // Each element of the crossing map consists of two fields: 137 // 138 // |.... Offset ....|.... Status ....| 139 // 140 // According Status bits, we can use the offset value in such a way: 141 // 142 // - if Status == Uninitialized, there is no element in this Page at all. 143 // 144 // - if Status == Initialized, the Offset value is an offset in words of the first element on this Page. 145 // We can start our range iteration from this element. 146 // 147 // - if Status == Crossed border, the Offset value is an offset in crossing map array to a page where the object, 148 // which crossed the Page border, is stored. 149 // 150 // - if Status == Initialized and Crossed border, the Offset value is an offset in words of the first element on 151 // this Page, and also we know what there is an object, which crossed the Page border. 152 class CrossingMapElement { 153 public: 154 enum STATE { 155 // This element of crossing map hasn't been initialized yet. 156 STATE_UNINITIALIZED, 157 // There are no objects which start in this page, 158 // but there is an object which starts before this page and crosses page border. 159 STATE_CROSSED_BORDER, 160 // We have some object that starts inside this page, 161 // but there are no objects which crosses page border. 162 STATE_INITIALIZED, 163 // We have some object that starts inside this page, 164 // and there is an object which crosses page border. 165 STATE_INITIALIZED_AND_CROSSED_BORDERS, 166 }; 167 GetMaxOffsetValue()168 static constexpr size_t GetMaxOffsetValue() 169 { 170 return MAX_OFFSET_VALUE; 171 } 172 GetState()173 STATE GetState() 174 { 175 switch (value_ & STATUS_MASK) { 176 case STATUS_UNINITIALIZED: 177 return (value_ | 0U) == 0U ? STATE_UNINITIALIZED : STATE_CROSSED_BORDER; 178 case STATUS_INITIALIZED: 179 return STATE_INITIALIZED; 180 case STATUS_INITIALIZED_AND_CROSSED_BORDERS: 181 return STATE_INITIALIZED_AND_CROSSED_BORDERS; 182 default: 183 LOG(FATAL, ALLOC) << "CrossingMapElement: Undefined map state"; 184 return STATE_UNINITIALIZED; 185 } 186 } 187 GetOffset()188 CROSSING_MAP_TYPE GetOffset() 189 { 190 return value_ >> STATUS_SIZE; 191 } 192 SetUninitialized()193 void SetUninitialized() 194 { 195 value_ = STATUS_UNINITIALIZED; 196 } 197 SetInitialized(CROSSING_MAP_TYPE offset)198 void SetInitialized(CROSSING_MAP_TYPE offset) 199 { 200 ASSERT(offset <= MAX_OFFSET_VALUE); 201 value_ = (offset << STATUS_SIZE); 202 value_ |= STATUS_INITIALIZED; 203 } 204 SetInitializedAndCrossedBorder(CROSSING_MAP_TYPE offset)205 void SetInitializedAndCrossedBorder(CROSSING_MAP_TYPE offset) 206 { 207 ASSERT(offset <= MAX_OFFSET_VALUE); 208 value_ = (offset << STATUS_SIZE); 209 value_ |= STATUS_INITIALIZED_AND_CROSSED_BORDERS; 210 } 211 SetCrossedBorder(CROSSING_MAP_TYPE offset)212 void SetCrossedBorder(CROSSING_MAP_TYPE offset) 213 { 214 ASSERT(offset <= MAX_OFFSET_VALUE); 215 value_ = (offset << STATUS_SIZE); 216 value_ |= STATUS_CROSSED_BORDER; 217 } 218 219 private: 220 enum MAP_REPRESENTATION : CROSSING_MAP_TYPE { 221 STATUS_UNINITIALIZED = 0U, 222 STATUS_CROSSED_BORDER = 0U, 223 STATUS_INITIALIZED = 1U, 224 STATUS_INITIALIZED_AND_CROSSED_BORDERS = 2U, 225 STATUS_SIZE = 2U, 226 STATUS_MASK = (1U << STATUS_SIZE) - 1U, 227 }; 228 229 static_assert(std::is_unsigned<CROSSING_MAP_TYPE>::value); 230 static constexpr size_t MAX_OFFSET_VALUE = std::numeric_limits<CROSSING_MAP_TYPE>::max() >> STATUS_SIZE; 231 232 // We must be sure that we can use such type for all possible obj offsets inside one page 233 static_assert((CROSSING_MAP_GRANULARITY >> CROSSING_MAP_OBJ_ALIGNMENT) <= MAX_OFFSET_VALUE); 234 235 CROSSING_MAP_TYPE value_ {STATUS_UNINITIALIZED}; 236 }; 237 // It is a pointer to an array of Crossing Map elements. 238 using StaticArrayPtr = CrossingMapElement **; 239 GetMapNumFromAddr(const void * addr)240 size_t GetMapNumFromAddr(const void *addr) 241 { 242 ASSERT(ToUintPtr(addr) >= start_addr_); 243 size_t map_num = (ToUintPtr(addr) - start_addr_) / CROSSING_MAP_GRANULARITY; 244 ASSERT(map_num < map_elements_count_); 245 return map_num; 246 } 247 GetAddrFromOffset(size_t map_num,size_t offset)248 void *GetAddrFromOffset(size_t map_num, size_t offset) 249 { 250 ASSERT(map_num < map_elements_count_); 251 return ToVoidPtr(start_addr_ + map_num * CROSSING_MAP_GRANULARITY + (offset << CROSSING_MAP_OBJ_ALIGNMENT)); 252 } 253 GetOffsetFromAddr(const void * addr)254 size_t GetOffsetFromAddr(const void *addr) 255 { 256 ASSERT(ToUintPtr(addr) >= start_addr_); 257 size_t offset = (ToUintPtr(addr) - start_addr_) % CROSSING_MAP_GRANULARITY; 258 ASSERT((offset & (GetAlignmentInBytes(CROSSING_MAP_OBJ_ALIGNMENT) - 1U)) == 0U); 259 return offset >> CROSSING_MAP_OBJ_ALIGNMENT; 260 } 261 262 void UpdateCrossedBorderOnAdding(size_t first_crossed_border_map, size_t last_crossed_border_map); 263 void UpdateCrossedBorderOnRemoving(size_t crossed_border_map); 264 void *FindObjInMap(size_t map_num); 265 GetMapElement(size_t map_num)266 CrossingMapElement *GetMapElement(size_t map_num) 267 { 268 ASSERT(map_num < map_elements_count_); 269 size_t static_array_num = map_num / CROSSING_MAP_COUNT_IN_STATIC_ARRAY_ELEMENT; 270 size_t relative_map_num = map_num % CROSSING_MAP_COUNT_IN_STATIC_ARRAY_ELEMENT; 271 ASSERT(GetStaticArrayElement(static_array_num) != nullptr); 272 return static_cast<CrossingMapElement *>(ToVoidPtr( 273 (ToUintPtr(GetStaticArrayElement(static_array_num)) + relative_map_num * sizeof(CrossingMapElement)))); 274 } 275 GetStaticArrayElement(size_t static_array_num)276 CrossingMapElement *GetStaticArrayElement(size_t static_array_num) 277 { 278 ASSERT(static_array_num < static_array_elements_count_); 279 auto element_pointer = static_cast<StaticArrayPtr>( 280 ToVoidPtr((ToUintPtr(static_array_) + static_array_num * sizeof(StaticArrayPtr)))); 281 return *element_pointer; 282 } 283 SetStaticArrayElement(size_t static_array_num,CrossingMapElement * value)284 void SetStaticArrayElement(size_t static_array_num, CrossingMapElement *value) 285 { 286 ASSERT(static_array_num < static_array_elements_count_); 287 void *element = ToVoidPtr(ToUintPtr(static_array_) + static_array_num * sizeof(StaticArrayPtr)); 288 *static_cast<StaticArrayPtr>(element) = value; 289 } 290 GetStaticArrayNumFromAddr(const void * addr)291 size_t GetStaticArrayNumFromAddr(const void *addr) 292 { 293 ASSERT(ToUintPtr(addr) >= start_addr_); 294 size_t static_array_num = (ToUintPtr(addr) - start_addr_) / CROSSING_MAP_STATIC_ARRAY_GRANULARITY; 295 ASSERT(static_array_num < static_array_elements_count_); 296 return static_array_num; 297 } 298 299 StaticArrayPtr static_array_ {nullptr}; 300 uintptr_t start_addr_ {0}; 301 size_t map_elements_count_ {0}; 302 size_t static_array_elements_count_ {0}; 303 InternalAllocatorPtr internal_allocator_ {nullptr}; 304 friend class CrossingMapTest; 305 }; 306 307 } // namespace panda::mem 308 309 #endif // PANDA_MEM_GC_CROSSING_MAP_H 310