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_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 panda::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 MTMode>
52 using ParameterizedLock = typename LockConfigHelper<RunSlotsAllocatorLockConfig, MTMode>::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 *mem_stats, SpaceType type_allocation = 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 arr_length);
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 &death_checker_fn);
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 &object_visitor);
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 &mem_visitor);
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 &mem_visitor);
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 &mem_visitor, void *left_border, void *right_border);
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 slots_size);
258
259 bool AddNewMemoryPool(void *mem, size_t size);
260
261 template <typename ObjectVisitor>
262 void IterateOverObjects(const ObjectVisitor &object_visitor);
263
264 template <typename MemVisitor>
265 void VisitAllPools(const MemVisitor &mem_visitor);
266
267 template <typename MemVisitor>
268 void VisitAllPoolsWithOccupiedSize(const MemVisitor &mem_visitor);
269
270 template <typename MemVisitor>
271 void VisitAndRemoveFreePools(const MemVisitor &mem_visitor);
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 *pool_mem, uintptr_t unoccupied_mem, 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 new_element = new (mem) PoolListElement();
297 uintptr_t unoccupied_mem = AlignUp(ToUintPtr(mem) + sizeof(PoolListElement), RUNSLOTS_SIZE);
298 ASSERT(unoccupied_mem < ToUintPtr(mem) + size);
299 new_element->Initialize(mem, unoccupied_mem, size, prev);
300 return new_element;
301 }
302
303 bool HasMemoryForRunSlots();
304
IsInitialized()305 bool IsInitialized()
306 {
307 return start_mem_ != 0;
308 }
309
310 RunSlotsType *GetMemoryForRunSlots(size_t slots_size);
311
312 template <typename RunSlotsVisitor>
313 void IterateOverRunSlots(const RunSlotsVisitor &runslots_visitor);
314
315 bool HasUsedMemory();
316
317 size_t GetOccupiedSize();
318
319 bool IsInUsedMemory(void *object);
320
GetPoolMemory()321 void *GetPoolMemory()
322 {
323 return ToVoidPtr(pool_mem_);
324 }
325
GetSize()326 size_t GetSize()
327 {
328 return size_;
329 }
330
GetNext()331 PoolListElement *GetNext() const
332 {
333 return next_pool_;
334 }
335
GetPrev()336 PoolListElement *GetPrev() const
337 {
338 return prev_pool_;
339 }
340
SetPrev(PoolListElement * prev)341 void SetPrev(PoolListElement *prev)
342 {
343 prev_pool_ = prev;
344 }
345
SetNext(PoolListElement * next)346 void SetNext(PoolListElement *next)
347 {
348 next_pool_ = next;
349 }
350
351 void PopFromList();
352
AddFreedRunSlots(RunSlotsType * slots)353 void AddFreedRunSlots(RunSlotsType *slots)
354 {
355 [[maybe_unused]] bool old_val = freed_runslots_bitmap_.AtomicTestAndSet(slots);
356 ASSERT(!old_val);
357 freeded_runslots_count_++;
358 ASAN_POISON_MEMORY_REGION(slots, RUNSLOTS_SIZE);
359 }
360
IsInFreedRunSlots(void * addr)361 bool IsInFreedRunSlots(void *addr)
362 {
363 void *align_addr = ToVoidPtr((ToUintPtr(addr) >> RUNSLOTS_ALIGNMENT) << RUNSLOTS_ALIGNMENT);
364 return freed_runslots_bitmap_.TestIfAddrValid(align_addr);
365 }
366
GetFreedRunSlotsCount()367 size_t GetFreedRunSlotsCount()
368 {
369 return freeded_runslots_count_;
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 slots_size);
384
385 uintptr_t pool_mem_;
386 uintptr_t start_mem_;
387 std::atomic<uintptr_t> free_ptr_;
388 size_t size_;
389 PoolListElement *next_pool_;
390 PoolListElement *prev_pool_;
391 size_t freeded_runslots_count_;
392 BitMapStorageType storage_for_bitmap_;
393 MemBitmapClass freed_runslots_bitmap_ {nullptr, MIN_POOL_SIZE, storage_for_bitmap_.data()};
394 };
395
396 PoolListElement *free_tail_;
397 PoolListElement *partially_occupied_head_;
398 PoolListElement *occupied_tail_;
399 typename LockConfigT::PoolLock lock_;
400 };
401
402 void ReleaseEmptyRunSlotsPagesUnsafe();
403
404 template <bool LockRunSlots>
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 slots_size);
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 free_runslots_;
427
428 MemPoolManager memory_pool_;
429 SpaceType type_allocation_;
430
431 MemStatsType *mem_stats_;
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 arr_length)442 T *RunSlotsAllocator<AllocConfigT, LockConfigT>::AllocArray(size_t arr_length)
443 {
444 // TODO(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) * arr_length));
446 }
447
448 #undef LOG_RUNSLOTS_ALLOCATOR
449
450 } // namespace panda::mem
451
452 #endif // PANDA_RUNTIME_MEM_RUNSLOTS_ALLOCATOR_H
453