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_RUNTIME_MEM_RUNSLOTS_H 16 #define PANDA_RUNTIME_MEM_RUNSLOTS_H 17 18 #include <array> 19 #include <cstddef> 20 21 #include "libpandabase/macros.h" 22 #include "libpandabase/mem/mem.h" 23 #include "libpandabase/utils/asan_interface.h" 24 #include "libpandabase/utils/logger.h" 25 26 namespace panda::mem { 27 28 // If the OS has this macro, do not redefine it. 29 #ifndef PAGE_SIZE 30 static constexpr size_t PAGE_SIZE = SIZE_1K * 4; 31 #endif 32 static constexpr size_t PAGES_IN_RUNSLOTS = 1; 33 static constexpr size_t RUNSLOTS_SIZE = PAGES_IN_RUNSLOTS * PAGE_SIZE; 34 static constexpr size_t RUNSLOTS_ALIGNMENT_IN_BYTES = PAGE_SIZE; 35 static constexpr size_t RUNSLOTS_ALIGNMENT = 10 + 2; // Alignment for shift 36 static constexpr size_t RUNSLOTS_ALIGNMENT_MASK = (1UL << RUNSLOTS_ALIGNMENT) - 1; 37 static_assert((1UL << RUNSLOTS_ALIGNMENT) == RUNSLOTS_ALIGNMENT_IN_BYTES); 38 39 class RunSlotsLockConfig { 40 public: 41 using CommonLock = os::memory::Mutex; 42 using DummyLock = os::memory::DummyLock; 43 }; 44 45 /** 46 * A class for free slots inside RunSlots object. 47 * Each free slot has a link to the next slot in RunSlots. 48 * If the link is equal to nullptr, then it is the last free slot. 49 */ 50 class FreeSlot { 51 public: GetNext()52 FreeSlot *GetNext() 53 { 54 return next_free_; 55 } SetNext(FreeSlot * next)56 void SetNext(FreeSlot *next) 57 { 58 next_free_ = next; 59 } 60 61 private: 62 FreeSlot *next_free_ {nullptr}; 63 }; 64 /** 65 * The main class for RunSlots. 66 * Each RunSlots consumes RUNSLOTS_SIZE bytes of memory. 67 * RunSlots is divided into equal size slots which will be used for allocation. 68 * The RunSlots header is stored inside the first slot (or slots) of this RunSlots instance. 69 */ 70 template <typename LockTypeT = RunSlotsLockConfig::CommonLock> 71 class RunSlots { 72 public: 73 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 74 ATTRIBUTE_NO_SANITIZE_ADDRESS 75 void Initialize(size_t slot_size, uintptr_t pool_pointer, bool initialize_lock); 76 MaxSlotSize()77 static constexpr size_t MaxSlotSize() 78 { 79 return SlotToSize(SlotsSizes::SLOT_MAX_SIZE_BYTES); 80 } 81 MinSlotSize()82 static constexpr size_t MinSlotSize() 83 { 84 return SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES); 85 } 86 SlotSizesVariants()87 static constexpr size_t SlotSizesVariants() 88 { 89 return SlotToSize(SlotsSizes::SLOT_MAX_SIZE_BYTES_POWER_OF_TWO); 90 } 91 92 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 93 ATTRIBUTE_NO_SANITIZE_ADDRESS 94 FreeSlot *PopFreeSlot(); 95 96 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 97 ATTRIBUTE_NO_SANITIZE_ADDRESS 98 void PushFreeSlot(FreeSlot *mem_slot); 99 100 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 101 ATTRIBUTE_NO_SANITIZE_ADDRESS GetPoolPointer()102 uintptr_t GetPoolPointer() 103 { 104 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 105 uintptr_t pool_pointer = pool_pointer_; 106 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 107 return pool_pointer; 108 } 109 110 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 111 ATTRIBUTE_NO_SANITIZE_ADDRESS IsEmpty()112 bool IsEmpty() 113 { 114 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 115 bool is_empty = (used_slots_ == 0); 116 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 117 return is_empty; 118 } 119 120 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 121 ATTRIBUTE_NO_SANITIZE_ADDRESS IsFull()122 bool IsFull() 123 { 124 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 125 bool is_full = (next_free_ == nullptr) && (first_uninitialized_slot_offset_ == 0); 126 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 127 return is_full; 128 } 129 130 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 131 ATTRIBUTE_NO_SANITIZE_ADDRESS SetNextRunSlots(RunSlots * runslots)132 void SetNextRunSlots(RunSlots *runslots) 133 { 134 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 135 next_runslot_ = runslots; 136 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 137 } 138 139 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 140 ATTRIBUTE_NO_SANITIZE_ADDRESS GetNextRunSlots()141 RunSlots *GetNextRunSlots() 142 { 143 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 144 RunSlots *next = next_runslot_; 145 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 146 return next; 147 } 148 149 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 150 ATTRIBUTE_NO_SANITIZE_ADDRESS SetPrevRunSlots(RunSlots * runslots)151 void SetPrevRunSlots(RunSlots *runslots) 152 { 153 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 154 prev_runslot_ = runslots; 155 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 156 } 157 158 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 159 ATTRIBUTE_NO_SANITIZE_ADDRESS GetPrevRunSlots()160 RunSlots *GetPrevRunSlots() 161 { 162 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 163 RunSlots *prev = prev_runslot_; 164 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 165 return prev; 166 } 167 168 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 169 ATTRIBUTE_NO_SANITIZE_ADDRESS GetSlotsSize()170 size_t GetSlotsSize() 171 { 172 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 173 size_t size = slot_size_; 174 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 175 return size; 176 } 177 ConvertToPowerOfTwoUnsafe(size_t size)178 static constexpr size_t ConvertToPowerOfTwoUnsafe(size_t size) 179 { 180 size_t i = SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES_POWER_OF_TWO); 181 size_t val = SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES); 182 while (size > val) { 183 i++; 184 val = val << 1UL; 185 } 186 return i; 187 } 188 189 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 190 template <typename ObjectVisitor> IterateOverOccupiedSlots(const ObjectVisitor & object_visitor)191 ATTRIBUTE_NO_SANITIZE_ADDRESS void IterateOverOccupiedSlots(const ObjectVisitor &object_visitor) 192 { 193 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 194 // TODO(aemelenko): We can increase execution speed of this loops and do not count BitMapToSlot each time 195 for (size_t array_index = 0; array_index < BITMAP_ARRAY_SIZE; array_index++) { 196 uint8_t byte = bitmap_[array_index]; 197 if (byte == 0x0) { 198 continue; 199 } 200 for (size_t bit = 0; bit < (1U << BITS_IN_BYTE_POWER_OF_TWO); bit++) { 201 if (byte & 0x1U) { 202 object_visitor(static_cast<ObjectHeader *>(static_cast<void *>(BitMapToSlot(array_index, bit)))); 203 } 204 byte = byte >> 1U; 205 } 206 // We must unpoison again, because we can poison header somewhere inside a visitor 207 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 208 } 209 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 210 } 211 212 /** 213 * \brief Check integraty of ROS allocator, return failure count. 214 */ VerifyRun()215 size_t VerifyRun() 216 { 217 return RunVerifier()(this); 218 } 219 220 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 221 ATTRIBUTE_NO_SANITIZE_ADDRESS 222 bool IsLive(const ObjectHeader *obj) const; 223 224 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 225 ATTRIBUTE_NO_SANITIZE_ADDRESS GetLock()226 LockTypeT *GetLock() 227 { 228 ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize()); 229 LockTypeT *lock = &lock_; 230 ASAN_POISON_MEMORY_REGION(this, GetHeaderSize()); 231 return lock; 232 } 233 234 private: 235 enum SlotsSizes : size_t { 236 SLOT_8_BYTES_POWER_OF_TWO = 3, 237 SLOT_16_BYTES_POWER_OF_TWO = 4, 238 SLOT_32_BYTES_POWER_OF_TWO = 5, 239 SLOT_64_BYTES_POWER_OF_TWO = 6, 240 SLOT_128_BYTES_POWER_OF_TWO = 7, 241 SLOT_256_BYTES_POWER_OF_TWO = 8, 242 SLOT_MAX_SIZE_BYTES_POWER_OF_TWO = SLOT_256_BYTES_POWER_OF_TWO, 243 SLOT_MIN_SIZE_BYTES_POWER_OF_TWO = SLOT_8_BYTES_POWER_OF_TWO, 244 SLOT_MAX_SIZE_BYTES = 1UL << SLOT_MAX_SIZE_BYTES_POWER_OF_TWO, 245 SLOT_MIN_SIZE_BYTES = 1UL << SLOT_MIN_SIZE_BYTES_POWER_OF_TWO, 246 }; 247 SlotToSize(SlotsSizes val)248 static constexpr size_t SlotToSize(SlotsSizes val) 249 { 250 return static_cast<size_t>(val); 251 } 252 253 static constexpr size_t BITS_IN_BYTE_POWER_OF_TWO = 3U; 254 static constexpr size_t BITMAP_ARRAY_SIZE = 255 (RUNSLOTS_SIZE >> (SlotsSizes::SLOT_MIN_SIZE_BYTES_POWER_OF_TWO)) >> BITS_IN_BYTE_POWER_OF_TWO; 256 GetHeaderSize()257 static size_t GetHeaderSize() 258 { 259 return sizeof(RunSlots); 260 } 261 262 size_t ComputeFirstSlotOffset(size_t slot_size); 263 264 void SetupSlots(); 265 266 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 267 ATTRIBUTE_NO_SANITIZE_ADDRESS 268 void MarkAsOccupied(const FreeSlot *slot_mem); 269 270 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 271 ATTRIBUTE_NO_SANITIZE_ADDRESS 272 void MarkAsFree(const FreeSlot *slot_mem); 273 274 FreeSlot *BitMapToSlot(size_t array_index, size_t bit); 275 276 class RunVerifier { 277 public: 278 RunVerifier() = default; 279 ~RunVerifier() = default; 280 NO_COPY_SEMANTIC(RunVerifier); 281 NO_MOVE_SEMANTIC(RunVerifier); 282 283 size_t operator()(RunSlots *run); 284 285 private: 286 size_t fail_cnt_ {0}; 287 }; 288 289 // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON 290 ATTRIBUTE_NO_SANITIZE_ADDRESS 291 void *PopUninitializedSlot(); 292 293 static_assert((RUNSLOTS_SIZE / SlotsSizes::SLOT_MIN_SIZE_BYTES) <= 294 std::numeric_limits<uint16_t>::max()); // used_slots_ 295 static_assert(SlotsSizes::SLOT_MAX_SIZE_BYTES <= std::numeric_limits<uint16_t>::max()); // slot_size_ 296 static_assert(RUNSLOTS_SIZE <= std::numeric_limits<uint16_t>::max()); // first_uninitialized_slot_offset_ 297 uint16_t used_slots_ {0}; 298 uint16_t slot_size_ {0}; 299 uint16_t first_uninitialized_slot_offset_ {0}; // If equal to zero - we don't have uninitialized slots 300 uintptr_t pool_pointer_ {0}; 301 FreeSlot *next_free_ {nullptr}; 302 RunSlots *next_runslot_ {nullptr}; 303 RunSlots *prev_runslot_ {nullptr}; 304 LockTypeT lock_; 305 306 // Bitmap for identifying live objects in this RunSlot 307 std::array<uint8_t, BITMAP_ARRAY_SIZE> bitmap_ {}; 308 }; 309 310 static_assert(RunSlots<>::MinSlotSize() >= sizeof(uintptr_t)); 311 312 } // namespace panda::mem 313 314 #endif // PANDA_RUNTIME_MEM_RUNSLOTS_H 315