1 /* 2 * Copyright (c) 2021 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_RUNTIME_MEM_FREELIST_ALLOCATOR_H_ 17 #define PANDA_RUNTIME_MEM_FREELIST_ALLOCATOR_H_ 18 19 #include <array> 20 21 #include "libpandabase/mem/mem.h" 22 #include "libpandabase/mem/space.h" 23 #include "libpandabase/os/mutex.h" 24 #include "runtime/mem/freelist.h" 25 #include "runtime/mem/runslots.h" 26 #include "runtime/mem/lock_config_helper.h" 27 28 namespace panda::mem { 29 30 // Minimal size of this allocator is a max size of RunSlots allocator. 31 static constexpr size_t PANDA_FREELIST_ALLOCATOR_MIN_SIZE = RunSlots<>::MaxSlotSize(); 32 static constexpr size_t PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_SIZE = 16; 33 static constexpr bool PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_FAST_INSERT = false; 34 static constexpr bool PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_FAST_EXTRACT = false; 35 36 static constexpr Alignment FREELIST_DEFAULT_ALIGNMENT = DEFAULT_ALIGNMENT; 37 38 static constexpr size_t FREELIST_ALLOCATOR_MIN_SIZE = PANDA_FREELIST_ALLOCATOR_MIN_SIZE; 39 static_assert(FREELIST_ALLOCATOR_MIN_SIZE >= (sizeof(freelist::FreeListHeader) - sizeof(freelist::MemoryBlockHeader))); 40 41 class FreeListAllocatorLockConfig { 42 public: 43 using CommonLock = os::memory::RWLock; 44 using DummyLock = os::memory::DummyLock; 45 46 template <MTModeT MTMode> 47 using ParameterizedLock = typename LockConfigHelper<FreeListAllocatorLockConfig, MTMode>::Value; 48 }; 49 50 template <typename T, typename AllocConfigT, typename LockConfigT> 51 class FreeListAllocatorAdapter; 52 enum class InternalAllocatorConfig; 53 template <InternalAllocatorConfig Config> 54 class InternalAllocator; 55 56 // FreeList Allocator layout: 57 // 58 // |..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|........|0000000000000000|..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|........|0000000000000000| 59 // |..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..Links.|0000000000000000|..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..Links.|0000000000000000| 60 // |..Memory..|xxxxxxxxxxOCCUPIEDxxxxxxxxxxxxx|..Memory..|...on...|000000FREE000000|..Memory..|xxxxxxxxxxOCCUPIEDxxxxxxxxxxxxx|..Memory..|...on...|000000FREE000000| 61 // |..Header..|xxxxxxxxxxxMEMORYxxxxxxxxxxxxxx|..Header..|..next/.|00000MEMORY00000|..Header..|xxxxxxxxxxxMEMORYxxxxxxxxxxxxxx|..Header..|..next/.|00000MEMORY00000| 62 // |..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..prev..|0000000000000000|..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..prev..|0000000000000000| 63 // |..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..free..|0000000000000000|..........|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|..........|..free..|0000000000000000| 64 // 65 // Blocks with alignments: 66 // 1) Padding header stored just after the main block header: 67 // |..........||..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 68 // |..........||..........||xxxxxxxxxxALIGNEDxxxxxxxxxxxxxx| 69 // |..Memory..||.Padding..||xxxxxxxxxxOCCUPIEDxxxxxxxxxxxxx| 70 // |..Header..||..Header..||xxxxxxxxxxxMEMORYxxxxxxxxxxxxxx| 71 // |..........||..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 72 // |..........||..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 73 // 74 // 2) We have padding size after the main block header: 75 // |..........|........|--------|..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 76 // |..........|........|--------|..........||xxxxxxxxxxALIGNEDxxxxxxxxxxxxxx| 77 // |..Memory..|.Padding|--------|.Padding..||xxxxxxxxxxOCCUPIEDxxxxxxxxxxxxx| 78 // |..Header..|..Size..|--------|..Header..||xxxxxxxxxxxMEMORYxxxxxxxxxxxxxx| 79 // |..........|........|--------|..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 80 // |..........|........|--------|..........||xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| 81 82 template <typename AllocConfigT, typename LockConfigT = FreeListAllocatorLockConfig::CommonLock> 83 class FreeListAllocator { 84 public: 85 explicit FreeListAllocator(MemStatsType *mem_stats, SpaceType type_allocation = SpaceType::SPACE_TYPE_OBJECT); 86 ~FreeListAllocator(); 87 NO_COPY_SEMANTIC(FreeListAllocator); 88 NO_MOVE_SEMANTIC(FreeListAllocator); 89 90 template <typename T, typename... Args> New(Args &&...args)91 [[nodiscard]] T *New(Args &&... args) 92 { 93 auto p = reinterpret_cast<void *>(Alloc(sizeof(T))); 94 new (p) T(std::forward<Args>(args)...); 95 return reinterpret_cast<T *>(p); 96 } 97 98 template <typename T> 99 [[nodiscard]] T *AllocArray(size_t arr_length); 100 101 [[nodiscard]] void *Alloc(size_t size, Alignment align = FREELIST_DEFAULT_ALIGNMENT); 102 103 void Free(void *mem); 104 105 void Collect(const GCObjectVisitor &death_checker_fn); 106 107 bool AddMemoryPool(void *mem, size_t size); 108 109 /** 110 * \brief Iterates over all objects allocated by this allocator. 111 * @tparam MemVisitor 112 * @param object_visitor - function pointer or functor 113 */ 114 template <typename ObjectVisitor> 115 void IterateOverObjects(const ObjectVisitor &object_visitor); 116 117 /** 118 * \brief Iterates over all memory pools used by this allocator 119 * and remove them from the allocator structure. 120 * NOTE: This method can't be used to clear all internal allocator 121 * information and reuse the allocator somewhere else. 122 * @tparam MemVisitor 123 * @param mem_visitor - function pointer or functor 124 */ 125 template <typename MemVisitor> 126 void VisitAndRemoveAllPools(const MemVisitor &mem_visitor); 127 128 /** 129 * \brief Visit memory pools that can be returned to the system in this allocator 130 * and remove them from the allocator structure. 131 * @tparam MemVisitor 132 * @param mem_visitor - function pointer or functor 133 */ 134 template <typename MemVisitor> 135 void VisitAndRemoveFreePools(const MemVisitor &mem_visitor); 136 137 /** 138 * \brief Iterates over objects in the range inclusively. 139 * @tparam MemVisitor 140 * @param mem_visitor - function pointer or functor 141 * @param left_border - a pointer to the first byte of the range 142 * @param right_border - a pointer to the last byte of the range 143 */ 144 template <typename MemVisitor> 145 void IterateOverObjectsInRange(const MemVisitor &mem_visitor, void *left_border, void *right_border); 146 147 FreeListAllocatorAdapter<void, AllocConfigT, LockConfigT> Adapter(); 148 149 /** 150 * \brief returns maximum size which can be allocated by this allocator 151 * @return 152 */ GetMaxSize()153 static constexpr size_t GetMaxSize() 154 { 155 return FREELIST_MAX_ALLOC_SIZE; 156 } 157 158 /** 159 * \brief returns minimum pool size which can be added to this allocator 160 * @return 161 */ GetMinPoolSize()162 static constexpr size_t GetMinPoolSize() 163 { 164 return FREELIST_DEFAULT_MEMORY_POOL_SIZE; 165 } 166 PoolAlign()167 static constexpr size_t PoolAlign() 168 { 169 return sizeof(MemoryBlockHeader); 170 } 171 172 bool ContainObject(const ObjectHeader *obj); 173 174 bool IsLive(const ObjectHeader *obj); 175 GetAllocatorType()176 static constexpr AllocatorType GetAllocatorType() 177 { 178 return AllocatorType::FREELIST_ALLOCATOR; 179 } 180 181 private: 182 using MemoryBlockHeader = panda::mem::freelist::MemoryBlockHeader; 183 using FreeListHeader = panda::mem::freelist::FreeListHeader; 184 185 class alignas(sizeof(MemoryBlockHeader)) MemoryPoolHeader { 186 public: 187 void Initialize(size_t size, MemoryPoolHeader *prev, MemoryPoolHeader *next); 188 189 ATTRIBUTE_NO_SANITIZE_ADDRESS GetPrev()190 MemoryPoolHeader *GetPrev() 191 { 192 ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 193 MemoryPoolHeader *prev = prev_; 194 ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 195 return prev; 196 } 197 198 ATTRIBUTE_NO_SANITIZE_ADDRESS GetNext()199 MemoryPoolHeader *GetNext() 200 { 201 ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 202 MemoryPoolHeader *next = next_; 203 ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 204 return next; 205 } 206 207 ATTRIBUTE_NO_SANITIZE_ADDRESS SetPrev(MemoryPoolHeader * prev)208 void SetPrev(MemoryPoolHeader *prev) 209 { 210 ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 211 prev_ = prev; 212 ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 213 } 214 215 ATTRIBUTE_NO_SANITIZE_ADDRESS SetNext(MemoryPoolHeader * next)216 void SetNext(MemoryPoolHeader *next) 217 { 218 ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 219 next_ = next; 220 ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 221 } 222 223 ATTRIBUTE_NO_SANITIZE_ADDRESS GetFirstMemoryHeader()224 MemoryBlockHeader *GetFirstMemoryHeader() 225 { 226 return static_cast<MemoryBlockHeader *>(ToVoidPtr(ToUintPtr(this) + sizeof(MemoryPoolHeader))); 227 } 228 229 ATTRIBUTE_NO_SANITIZE_ADDRESS GetSize()230 size_t GetSize() 231 { 232 ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 233 size_t size = size_; 234 ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryPoolHeader)); 235 return size; 236 } 237 238 private: 239 MemoryPoolHeader *prev_ {nullptr}; 240 MemoryPoolHeader *next_ {nullptr}; 241 size_t size_ {0}; 242 }; 243 244 static_assert((sizeof(MemoryPoolHeader) % sizeof(MemoryBlockHeader)) == 0); 245 static constexpr size_t FREELIST_DEFAULT_MEMORY_POOL_SIZE = PANDA_DEFAULT_ALLOCATOR_POOL_SIZE; 246 static constexpr size_t FREELIST_MAX_ALLOC_SIZE = 247 ((FREELIST_DEFAULT_MEMORY_POOL_SIZE - sizeof(MemoryPoolHeader)) / 2) - sizeof(MemoryBlockHeader); 248 249 class SegregatedList { 250 public: 251 void AddMemoryBlock(FreeListHeader *freelist_header); 252 FreeListHeader *FindMemoryBlock(size_t size); 253 void ReleaseFreeMemoryBlocks(); 254 255 private: 256 static constexpr size_t SEGREGATED_LIST_SIZE = PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_SIZE; 257 static constexpr size_t SEGREGATED_LIST_FREE_BLOCK_RANGE = 258 (FREELIST_MAX_ALLOC_SIZE - FREELIST_ALLOCATOR_MIN_SIZE) / SEGREGATED_LIST_SIZE; 259 // If it is off, we insert memory in the list in the descending order. 260 static constexpr bool SEGREGATED_LIST_FAST_INSERT = PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_FAST_INSERT; 261 // If it is off, we try to find the most suitable block in the list. 262 static constexpr bool SEGREGATED_LIST_FAST_EXTRACT = PANDA_FREELIST_ALLOCATOR_SEGREGATED_LIST_FAST_EXTRACT; 263 static_assert(((FREELIST_MAX_ALLOC_SIZE - FREELIST_ALLOCATOR_MIN_SIZE) % SEGREGATED_LIST_SIZE) == 0); 264 265 size_t GetIndex(size_t size); 266 GetFirstBlock(size_t index)267 FreeListHeader *GetFirstBlock(size_t index) 268 { 269 ASSERT(index < SEGREGATED_LIST_SIZE); 270 return free_memory_blocks_[index].GetNextFree(); 271 } 272 SetFirstBlock(size_t index,FreeListHeader * new_head)273 void SetFirstBlock(size_t index, FreeListHeader *new_head) 274 { 275 ASSERT(index < SEGREGATED_LIST_SIZE); 276 free_memory_blocks_[index].SetNextFree(new_head); 277 } 278 279 FreeListHeader *FindTheMostSuitableBlockInOrderedList(size_t index, size_t size); 280 281 // Each element of this array consists of memory blocks with size 282 // from (FREELIST_ALLOCATOR_MIN_SIZE + SEGREGATED_LIST_FREE_BLOCK_RANGE * (N)) 283 // to (FREELIST_ALLOCATOR_MIN_SIZE + SEGREGATED_LIST_FREE_BLOCK_RANGE * (N + 1)) (not inclusive) 284 // where N is the element number in this array. 285 std::array<FreeListHeader, SEGREGATED_LIST_SIZE> free_memory_blocks_; 286 }; 287 288 MemoryBlockHeader *GetFreeListMemoryHeader(void *mem); 289 290 bool AllocatedByFreeListAllocator(void *mem); 291 292 bool AllocatedByFreeListAllocatorUnsafe(void *mem); 293 294 // Try to coalesce a memory block with the next and previous blocks. 295 FreeListHeader *TryToCoalescing(MemoryBlockHeader *memory_header); 296 297 // Coalesce two neighboring memory blocks into one. 298 void CoalesceMemoryBlocks(MemoryBlockHeader *first_block, MemoryBlockHeader *second_block); 299 300 /** 301 * \brief Divide memory_block into two - the first with first_block_size. 302 * @param memory_block - a pointer to the divided block, first_block_size - size of the first part 303 * @return the second memory block header 304 */ 305 MemoryBlockHeader *SplitMemoryBlocks(MemoryBlockHeader *memory_block, size_t first_block_size); 306 307 void AddToSegregatedList(FreeListHeader *free_list_element); 308 309 MemoryBlockHeader *GetFromSegregatedList(size_t size, Alignment align); 310 CanCreateNewBlockFromRemainder(MemoryBlockHeader * memory,size_t alloc_size)311 bool CanCreateNewBlockFromRemainder(MemoryBlockHeader *memory, size_t alloc_size) 312 { 313 return (memory->GetSize() - alloc_size) >= (FREELIST_ALLOCATOR_MIN_SIZE + sizeof(FreeListHeader)); 314 } 315 316 void FreeUnsafe(void *mem); 317 318 SegregatedList segregated_list_; 319 320 // Links to head and tail of the memory pool headers 321 MemoryPoolHeader *mempool_head_ {nullptr}; 322 MemoryPoolHeader *mempool_tail_ {nullptr}; 323 SpaceType type_allocation_; 324 325 // RW lock which allows only one thread to change smth inside allocator 326 // NOTE: The MT support expects that we can't iterate 327 // and free (i.e. collect for an object scenario) simultaneously 328 LockConfigT alloc_free_lock_; 329 330 MemStatsType *mem_stats_; 331 332 friend class FreeListAllocatorTest; 333 friend class HybridObjectAllocatorTest; 334 template <InternalAllocatorConfig Config> 335 friend class InternalAllocator; 336 }; 337 338 } // namespace panda::mem 339 340 #endif // PANDA_RUNTIME_MEM_FREELIST_ALLOCATOR_H_ 341