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 #ifndef PANDA_RUNTIME_MEM_RUNSLOTS_ALLOCATOR_H
16 #define PANDA_RUNTIME_MEM_RUNSLOTS_ALLOCATOR_H
17
18 #include <algorithm>
19 #include <array>
20 #include <cstddef>
21
22 #include "libpandabase/macros.h"
23 #include "libpandabase/mem/mem.h"
24 #include "libpandabase/mem/space.h"
25 #include "libpandabase/utils/logger.h"
26 #include "runtime/mem/runslots.h"
27 #include "runtime/mem/gc/bitmap.h"
28 #include "runtime/mem/lock_config_helper.h"
29
30 namespace ark::mem {
31
32 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
33 #define LOG_RUNSLOTS_ALLOCATOR(level) LOG(level, ALLOC) << "RunSlotsAllocator: "
34
35 class RunSlotsAllocatorLockConfig {
36 public:
37 class CommonLock {
38 public:
39 using PoolLock = os::memory::RWLock;
40 using ListLock = os::memory::Mutex;
41 using RunSlotsLock = RunSlotsLockConfig::CommonLock;
42 };
43
44 class DummyLock {
45 public:
46 using PoolLock = os::memory::DummyLock;
47 using ListLock = os::memory::DummyLock;
48 using RunSlotsLock = RunSlotsLockConfig::DummyLock;
49 };
50
51 template <MTModeT MT_MODE>
52 using ParameterizedLock = typename LockConfigHelper<RunSlotsAllocatorLockConfig, MT_MODE>::Value;
53 };
54
55 template <typename T, typename AllocConfigT, typename LockConfigT>
56 class RunSlotsAllocatorAdapter;
57 enum class InternalAllocatorConfig;
58 template <InternalAllocatorConfig CONFIG>
59 class InternalAllocator;
60
61 /**
62 * RunSlotsAllocator is an allocator based on RunSlots instance.
63 * It gets a big pool of memory from OS and uses it for creating RunSlots with different slot sizes.
64 */
65 template <typename AllocConfigT, typename LockConfigT = RunSlotsAllocatorLockConfig::CommonLock>
66 class RunSlotsAllocator {
67 public:
68 explicit RunSlotsAllocator(MemStatsType *memStats, SpaceType typeAllocation = SpaceType::SPACE_TYPE_OBJECT);
69 ~RunSlotsAllocator();
70 NO_COPY_SEMANTIC(RunSlotsAllocator);
71 NO_MOVE_SEMANTIC(RunSlotsAllocator);
72
73 template <typename T, typename... Args>
New(Args &&...args)74 [[nodiscard]] T *New(Args &&...args)
75 {
76 auto p = reinterpret_cast<void *>(Alloc(sizeof(T)));
77 new (p) T(std::forward<Args>(args)...);
78 return reinterpret_cast<T *>(p);
79 }
80
81 template <typename T>
82 [[nodiscard]] T *AllocArray(size_t arrLength);
83
84 template <bool NEED_LOCK = true, bool DISABLE_USE_FREE_RUNSLOTS = false>
85 [[nodiscard]] void *Alloc(size_t size, Alignment align = DEFAULT_ALIGNMENT);
86
87 void Free(void *mem);
88
89 void Collect(const GCObjectVisitor &deathCheckerFn);
90
91 bool AddMemoryPool(void *mem, size_t size);
92
93 /**
94 * @brief Iterates over all objects allocated by this allocator.
95 * @tparam MemVisitor
96 * @param mem_visitor - function pointer or functor
97 */
98 template <typename ObjectVisitor>
99 void IterateOverObjects(const ObjectVisitor &objectVisitor);
100
101 /**
102 * @brief Iterates over all memory pools used by this allocator
103 * and remove them from the allocator structure.
104 * NOTE: This method can't be used to clear all internal allocator
105 * information and reuse the allocator somewhere else.
106 * @tparam MemVisitor
107 * @param mem_visitor - function pointer or functor
108 */
109 template <typename MemVisitor>
110 void VisitAndRemoveAllPools(const MemVisitor &memVisitor);
111
112 /**
113 * @brief Visit memory pools that can be returned to the system in this allocator
114 * and remove them from the allocator structure.
115 * @tparam MemVisitor
116 * @param mem_visitor - function pointer or functor
117 */
118 template <typename MemVisitor>
119 void VisitAndRemoveFreePools(const MemVisitor &memVisitor);
120
121 /**
122 * @brief Iterates over objects in the range inclusively.
123 * @tparam MemVisitor
124 * @param mem_visitor - function pointer or functor
125 * @param left_border - a pointer to the first byte of the range
126 * @param right_border - a pointer to the last byte of the range
127 */
128 template <typename MemVisitor>
129 void IterateOverObjectsInRange(const MemVisitor &memVisitor, void *leftBorder, void *rightBorder);
130
131 RunSlotsAllocatorAdapter<void, AllocConfigT, LockConfigT> Adapter();
132
133 /**
134 * @brief returns maximum size which can be allocated by this allocator
135 * @return
136 */
GetMaxSize()137 static constexpr size_t GetMaxSize()
138 {
139 return RunSlotsType::MaxSlotSize();
140 }
141
142 /**
143 * @brief returns minimum pool size which can be added to this allocator
144 * @return
145 */
GetMinPoolSize()146 static constexpr size_t GetMinPoolSize()
147 {
148 return MIN_POOL_SIZE;
149 }
150
PoolAlign()151 static constexpr size_t PoolAlign()
152 {
153 return DEFAULT_ALIGNMENT_IN_BYTES;
154 }
155
156 size_t VerifyAllocator();
157
158 bool ContainObject(const ObjectHeader *obj);
159
160 bool IsLive(const ObjectHeader *obj);
161
GetAllocatorType()162 static constexpr AllocatorType GetAllocatorType()
163 {
164 return AllocatorType::RUNSLOTS_ALLOCATOR;
165 }
166
167 private:
168 using RunSlotsType = RunSlots<typename LockConfigT::RunSlotsLock>;
169
170 static constexpr size_t MIN_POOL_SIZE = PANDA_DEFAULT_ALLOCATOR_POOL_SIZE;
171
172 class RunSlotsList {
173 public:
RunSlotsList()174 RunSlotsList()
175 {
176 head_ = nullptr;
177 tail_ = nullptr;
178 }
179
GetLock()180 typename LockConfigT::ListLock *GetLock()
181 {
182 return &lock_;
183 }
184
GetHead()185 RunSlotsType *GetHead()
186 {
187 return head_;
188 }
189
GetTail()190 RunSlotsType *GetTail()
191 {
192 return tail_;
193 }
194
195 void PushToTail(RunSlotsType *runslots);
196
197 RunSlotsType *PopFromHead();
198
199 RunSlotsType *PopFromTail();
200
201 void PopFromList(RunSlotsType *runslots);
202
IsInThisList(RunSlotsType * runslots)203 bool IsInThisList(RunSlotsType *runslots)
204 {
205 RunSlotsType *current = head_;
206 while (current != nullptr) {
207 if (current == runslots) {
208 return true;
209 }
210 current = current->GetNextRunSlots();
211 }
212 return false;
213 }
214
215 ~RunSlotsList() = default;
216
217 NO_COPY_SEMANTIC(RunSlotsList);
218 NO_MOVE_SEMANTIC(RunSlotsList);
219
220 private:
221 RunSlotsType *head_;
222 RunSlotsType *tail_;
223 typename LockConfigT::ListLock lock_;
224 };
225
226 /**
227 * MemPoolManager class is used for manage memory which we get from OS.
228 * Current implementation limits the amount of memory pools which can be managed by this class.
229 */
230
231 // MemPoolManager structure:
232 //
233 // part_occupied_head_ - is a pointer to the first partially occupied pool in occupied list
234 // |
235 // | occupied_tail_ - is a pointer to the last occupied pool
236 // | |
237 // | part occupied |
238 // v pools v
239 // |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|
240 // ^ ^
241 // | occupied pools |
242 //
243 // free_tail_ - is a pointer to the last totally free pool.
244 // |
245 // |
246 // v
247 // |0|0|0|0|0|0|0|0|0|0|
248 // ^ ^
249 // | free pools |
250 //
251
252 class MemPoolManager {
253 public:
254 explicit MemPoolManager();
255
256 template <bool NEED_LOCK = true>
257 RunSlotsType *GetNewRunSlots(size_t slotsSize);
258
259 bool AddNewMemoryPool(void *mem, size_t size);
260
261 template <typename ObjectVisitor>
262 void IterateOverObjects(const ObjectVisitor &objectVisitor);
263
264 template <typename MemVisitor>
265 void VisitAllPools(const MemVisitor &memVisitor);
266
267 template <typename MemVisitor>
268 void VisitAllPoolsWithOccupiedSize(const MemVisitor &memVisitor);
269
270 template <typename MemVisitor>
271 void VisitAndRemoveFreePools(const MemVisitor &memVisitor);
272
273 void ReturnAndReleaseRunSlotsMemory(RunSlotsType *runslots);
274
275 bool IsInMemPools(void *object);
276
277 ~MemPoolManager() = default;
278
279 NO_COPY_SEMANTIC(MemPoolManager);
280 NO_MOVE_SEMANTIC(MemPoolManager);
281
282 private:
283 class PoolListElement {
284 public:
285 PoolListElement();
286
287 void Initialize(void *poolMem, uintptr_t unoccupiedMem, size_t size, PoolListElement *prev);
288
Create(void * mem,size_t size,PoolListElement * prev)289 static PoolListElement *Create(void *mem, size_t size, PoolListElement *prev)
290 {
291 LOG_RUNSLOTS_ALLOCATOR(DEBUG)
292 << "PoolMemory: Create new instance with size " << size << " bytes at addr " << std::hex << mem;
293 ASSERT(mem != nullptr);
294 ASSERT(sizeof(PoolListElement) <= RUNSLOTS_SIZE);
295 ASAN_UNPOISON_MEMORY_REGION(mem, sizeof(PoolListElement));
296 auto newElement = new (mem) PoolListElement();
297 uintptr_t unoccupiedMem = AlignUp(ToUintPtr(mem) + sizeof(PoolListElement), RUNSLOTS_SIZE);
298 ASSERT(unoccupiedMem < ToUintPtr(mem) + size);
299 newElement->Initialize(mem, unoccupiedMem, size, prev);
300 return newElement;
301 }
302
303 bool HasMemoryForRunSlots();
304
IsInitialized()305 bool IsInitialized()
306 {
307 return startMem_ != 0;
308 }
309
310 RunSlotsType *GetMemoryForRunSlots(size_t slotsSize);
311
312 template <typename RunSlotsVisitor>
313 void IterateOverRunSlots(const RunSlotsVisitor &runslotsVisitor);
314
315 bool HasUsedMemory();
316
317 size_t GetOccupiedSize();
318
319 bool IsInUsedMemory(void *object);
320
GetPoolMemory()321 void *GetPoolMemory()
322 {
323 return ToVoidPtr(poolMem_);
324 }
325
GetSize()326 size_t GetSize()
327 {
328 return size_;
329 }
330
GetNext()331 PoolListElement *GetNext() const
332 {
333 return nextPool_;
334 }
335
GetPrev()336 PoolListElement *GetPrev() const
337 {
338 return prevPool_;
339 }
340
SetPrev(PoolListElement * prev)341 void SetPrev(PoolListElement *prev)
342 {
343 prevPool_ = prev;
344 }
345
SetNext(PoolListElement * next)346 void SetNext(PoolListElement *next)
347 {
348 nextPool_ = next;
349 }
350
351 void PopFromList();
352
AddFreedRunSlots(RunSlotsType * slots)353 void AddFreedRunSlots(RunSlotsType *slots)
354 {
355 [[maybe_unused]] bool oldVal = freedRunslotsBitmap_.AtomicTestAndSet(slots);
356 ASSERT(!oldVal);
357 freededRunslotsCount_++;
358 ASAN_POISON_MEMORY_REGION(slots, RUNSLOTS_SIZE);
359 }
360
IsInFreedRunSlots(void * addr)361 bool IsInFreedRunSlots(void *addr)
362 {
363 void *alignAddr = ToVoidPtr((ToUintPtr(addr) >> RUNSLOTS_ALIGNMENT) << RUNSLOTS_ALIGNMENT);
364 return freedRunslotsBitmap_.TestIfAddrValid(alignAddr);
365 }
366
GetFreedRunSlotsCount()367 size_t GetFreedRunSlotsCount()
368 {
369 return freededRunslotsCount_;
370 }
371
372 ~PoolListElement() = default;
373
374 NO_COPY_SEMANTIC(PoolListElement);
375 NO_MOVE_SEMANTIC(PoolListElement);
376
377 private:
378 using MemBitmapClass = MemBitmap<RUNSLOTS_SIZE, uintptr_t>;
379 using BitMapStorageType = std::array<uint8_t, MemBitmapClass::GetBitMapSizeInByte(MIN_POOL_SIZE)>;
380
381 uintptr_t GetFirstRunSlotsBlock(uintptr_t mem);
382
383 RunSlotsType *GetFreedRunSlots(size_t slotsSize);
384
385 uintptr_t poolMem_;
386 uintptr_t startMem_;
387 std::atomic<uintptr_t> freePtr_;
388 size_t size_;
389 PoolListElement *nextPool_;
390 PoolListElement *prevPool_;
391 size_t freededRunslotsCount_;
392 BitMapStorageType storageForBitmap_;
393 MemBitmapClass freedRunslotsBitmap_ {nullptr, MIN_POOL_SIZE, storageForBitmap_.data()};
394 };
395
396 PoolListElement *freeTail_;
397 PoolListElement *partiallyOccupiedHead_;
398 PoolListElement *occupiedTail_;
399 typename LockConfigT::PoolLock lock_;
400 };
401
402 void ReleaseEmptyRunSlotsPagesUnsafe();
403
404 template <bool LOCK_RUN_SLOTS>
405 void FreeUnsafe(void *mem);
406
407 bool FreeUnsafeInternal(RunSlotsType *runslots, void *mem);
408
409 void TrimUnsafe();
410
411 // Return true if this object could be allocated by the RunSlots allocator.
412 // Does not check any live objects bitmap inside.
413 bool AllocatedByRunSlotsAllocator(void *object);
414
415 bool AllocatedByRunSlotsAllocatorUnsafe(void *object);
416
417 template <bool NEED_LOCK = true>
418 RunSlotsType *CreateNewRunSlotsFromMemory(size_t slotsSize);
419
420 // Add one to the array size to just use the size (power of two) for RunSlots list without any modifications
421 static constexpr size_t SLOTS_SIZES_VARIANTS = RunSlotsType::SlotSizesVariants() + 1;
422
423 std::array<RunSlotsList, SLOTS_SIZES_VARIANTS> runslots_;
424
425 // Add totally free RunSlots in this list for possibility to reuse them with different element sizes.
426 RunSlotsList freeRunslots_;
427
428 MemPoolManager memoryPool_;
429 SpaceType typeAllocation_;
430
431 MemStatsType *memStats_;
432
433 template <typename T>
434 friend class PygoteSpaceAllocator;
435 friend class RunSlotsAllocatorTest;
436 template <InternalAllocatorConfig CONFIG>
437 friend class InternalAllocator;
438 };
439
440 template <typename AllocConfigT, typename LockConfigT>
441 template <typename T>
AllocArray(size_t arrLength)442 T *RunSlotsAllocator<AllocConfigT, LockConfigT>::AllocArray(size_t arrLength)
443 {
444 // NOTE(aemelenko): Very dirty hack. If you want to fix it, you must change RunSlotsAllocatorAdapter::max_size() too
445 return static_cast<T *>(Alloc(sizeof(T) * arrLength));
446 }
447
448 #undef LOG_RUNSLOTS_ALLOCATOR
449
450 } // namespace ark::mem
451
452 #endif // PANDA_RUNTIME_MEM_RUNSLOTS_ALLOCATOR_H
453