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
16 #include <sys/mman.h>
17
18 #include "libpandabase/mem/mem.h"
19 #include "libpandabase/os/mem.h"
20 #include "libpandabase/utils/asan_interface.h"
21 #include "libpandabase/utils/logger.h"
22 #include "libpandabase/utils/math_helpers.h"
23 #include "runtime/include/runtime.h"
24 #include "runtime/mem/alloc_config.h"
25 #include "runtime/mem/freelist_allocator-inl.h"
26 #include "runtime/tests/allocator_test_base.h"
27
28 namespace ark::mem {
29
30 using NonObjectFreeListAllocator = FreeListAllocator<EmptyAllocConfigWithCrossingMap>;
31
32 class FreeListAllocatorTest : public AllocatorTest<NonObjectFreeListAllocator> {
33 public:
34 NO_COPY_SEMANTIC(FreeListAllocatorTest);
35 NO_MOVE_SEMANTIC(FreeListAllocatorTest);
36
FreeListAllocatorTest()37 FreeListAllocatorTest()
38 {
39 // Logger::InitializeStdLogging(Logger::Level::DEBUG, Logger::Component::ALL);
40 // We need to create a runtime instance to be able to use CrossingMap.
41 options_.SetShouldLoadBootPandaFiles(false);
42 options_.SetShouldInitializeIntrinsics(false);
43 Runtime::Create(options_);
44 thread_ = ark::MTManagedThread::GetCurrent();
45 thread_->ManagedCodeBegin();
46 if (!CrossingMapSingleton::IsCreated()) {
47 CrossingMapSingleton::Create();
48 crossingmapManualHandling_ = true;
49 }
50 }
51
~FreeListAllocatorTest()52 ~FreeListAllocatorTest() override
53 {
54 thread_->ManagedCodeEnd();
55 ClearPoolManager();
56 if (crossingmapManualHandling_) {
57 CrossingMapSingleton::Destroy();
58 }
59 Runtime::Destroy();
60 // Logger::Destroy();
61 }
62
63 protected:
64 static constexpr size_t DEFAULT_POOL_SIZE_FOR_ALLOC = NonObjectFreeListAllocator::GetMinPoolSize();
65 static constexpr size_t DEFAULT_POOL_ALIGNMENT_FOR_ALLOC = FREELIST_DEFAULT_ALIGNMENT;
66 static constexpr size_t POOL_HEADER_SIZE = sizeof(NonObjectFreeListAllocator::MemoryPoolHeader);
67 static constexpr size_t MAX_ALLOC_SIZE = NonObjectFreeListAllocator::GetMaxSize();
68
AddMemoryPoolToAllocator(NonObjectFreeListAllocator & alloc)69 void AddMemoryPoolToAllocator(NonObjectFreeListAllocator &alloc) override
70 {
71 os::memory::LockHolder lock(poolLock_);
72 Pool pool = PoolManager::GetMmapMemPool()->AllocPool(DEFAULT_POOL_SIZE_FOR_ALLOC, SpaceType::SPACE_TYPE_OBJECT,
73 AllocatorType::FREELIST_ALLOCATOR, &alloc);
74 ASSERT(pool.GetSize() == DEFAULT_POOL_SIZE_FOR_ALLOC);
75 if (pool.GetMem() == nullptr) {
76 ASSERT_TRUE(0 && "Can't get a new pool from PoolManager");
77 }
78 allocatedPoolsByPoolManager_.push_back(pool);
79 if (!alloc.AddMemoryPool(pool.GetMem(), pool.GetSize())) {
80 ASSERT_TRUE(0 && "Can't add mem pool to allocator");
81 }
82 }
83
AddMemoryPoolToAllocatorProtected(NonObjectFreeListAllocator & alloc)84 void AddMemoryPoolToAllocatorProtected(NonObjectFreeListAllocator &alloc) override
85 {
86 // We use common PoolManager from Runtime. Therefore, we have the same pool allocation for both cases.
87 AddMemoryPoolToAllocator(alloc);
88 }
89
AllocatedByThisAllocator(NonObjectFreeListAllocator & allocator,void * mem)90 bool AllocatedByThisAllocator(NonObjectFreeListAllocator &allocator, void *mem) override
91 {
92 return allocator.AllocatedByFreeListAllocator(mem);
93 }
94
ClearPoolManager(bool clearCrossingMap=false)95 void ClearPoolManager(bool clearCrossingMap = false)
96 {
97 for (auto i : allocatedPoolsByPoolManager_) {
98 PoolManager::GetMmapMemPool()->FreePool(i.GetMem(), i.GetSize());
99 if (clearCrossingMap) {
100 // We need to remove corresponding Pools from the CrossingMap
101 CrossingMapSingleton::RemoveCrossingMapForMemory(i.GetMem(), i.GetSize());
102 }
103 }
104 allocatedPoolsByPoolManager_.clear();
105 }
106
107 private:
108 ark::MTManagedThread *thread_ {};
109 std::vector<Pool> allocatedPoolsByPoolManager_;
110 RuntimeOptions options_;
111 bool crossingmapManualHandling_ {false};
112 // Mutex, which allows only one thread to add pool to the pool vector
113 os::memory::Mutex poolLock_;
114 };
115
TEST_F(FreeListAllocatorTest,SimpleAllocateDifferentObjSizeTest)116 TEST_F(FreeListAllocatorTest, SimpleAllocateDifferentObjSizeTest)
117 {
118 LOG(DEBUG, ALLOC) << "SimpleAllocateDifferentObjSizeTest";
119 auto *memStats = new mem::MemStatsType();
120 NonObjectFreeListAllocator allocator(memStats);
121 AddMemoryPoolToAllocator(allocator);
122 // NOLINTNEXTLINE(readability-magic-numbers)
123 for (size_t i = 23U; i < 300U; i++) {
124 void *mem = allocator.Alloc(i);
125 (void)mem;
126 LOG(DEBUG, ALLOC) << "Allocate obj with size " << i << " at " << std::hex << mem;
127 }
128 delete memStats;
129 }
130
TEST_F(FreeListAllocatorTest,AllocateWriteFreeTest)131 TEST_F(FreeListAllocatorTest, AllocateWriteFreeTest)
132 {
133 // NOLINTNEXTLINE(readability-magic-numbers)
134 AllocateAndFree(FREELIST_ALLOCATOR_MIN_SIZE, 512U);
135 }
136
TEST_F(FreeListAllocatorTest,AllocateRandomFreeTest)137 TEST_F(FreeListAllocatorTest, AllocateRandomFreeTest)
138 {
139 static constexpr size_t ALLOC_SIZE = FREELIST_ALLOCATOR_MIN_SIZE;
140 static constexpr size_t ELEMENTS_COUNT = 512;
141 static constexpr size_t POOLS_COUNT = 1;
142 AllocateFreeDifferentSizesTest<ALLOC_SIZE, 2U * ALLOC_SIZE>(ELEMENTS_COUNT, POOLS_COUNT);
143 }
144
TEST_F(FreeListAllocatorTest,AllocateTooBigObjTest)145 TEST_F(FreeListAllocatorTest, AllocateTooBigObjTest)
146 {
147 AllocateTooBigObjectTest<MAX_ALLOC_SIZE + 1>();
148 }
149
TEST_F(FreeListAllocatorTest,AlignmentAllocTest)150 TEST_F(FreeListAllocatorTest, AlignmentAllocTest)
151 {
152 static constexpr size_t POOLS_COUNT = 2;
153 // NOLINTNEXTLINE(readability-magic-numbers)
154 AlignedAllocFreeTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_ALLOC_SIZE / 4096U>(POOLS_COUNT);
155 }
156
TEST_F(FreeListAllocatorTest,AllocateTooMuchTest)157 TEST_F(FreeListAllocatorTest, AllocateTooMuchTest)
158 {
159 static constexpr size_t ALLOC_SIZE = FREELIST_ALLOCATOR_MIN_SIZE;
160 AllocateTooMuchTest(ALLOC_SIZE, DEFAULT_POOL_SIZE_FOR_ALLOC / ALLOC_SIZE);
161 }
162
TEST_F(FreeListAllocatorTest,ObjectIteratorTest)163 TEST_F(FreeListAllocatorTest, ObjectIteratorTest)
164 {
165 ObjectIteratorTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_ALLOC_SIZE>();
166 }
167
TEST_F(FreeListAllocatorTest,ObjectCollectionTest)168 TEST_F(FreeListAllocatorTest, ObjectCollectionTest)
169 {
170 ObjectCollectionTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_ALLOC_SIZE>();
171 }
172
TEST_F(FreeListAllocatorTest,ObjectIteratorInRangeTest)173 TEST_F(FreeListAllocatorTest, ObjectIteratorInRangeTest)
174 {
175 ObjectIteratorInRangeTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_ALLOC_SIZE>(
176 CrossingMapSingleton::GetCrossingMapGranularity());
177 }
178
TEST_F(FreeListAllocatorTest,AsanTest)179 TEST_F(FreeListAllocatorTest, AsanTest)
180 {
181 AsanTest();
182 }
183
TEST_F(FreeListAllocatorTest,VisitAndRemoveFreePoolsTest)184 TEST_F(FreeListAllocatorTest, VisitAndRemoveFreePoolsTest)
185 {
186 static constexpr size_t POOLS_COUNT = 5;
187 VisitAndRemoveFreePools<POOLS_COUNT>(MAX_ALLOC_SIZE);
188 }
189
TEST_F(FreeListAllocatorTest,AllocatedByFreeListAllocatorTest)190 TEST_F(FreeListAllocatorTest, AllocatedByFreeListAllocatorTest)
191 {
192 AllocatedByThisAllocatorTest();
193 }
194
TEST_F(FreeListAllocatorTest,FailedLinksTest)195 TEST_F(FreeListAllocatorTest, FailedLinksTest)
196 {
197 static constexpr size_t MIN_ALLOC_SIZE = FREELIST_ALLOCATOR_MIN_SIZE;
198 auto *memStats = new mem::MemStatsType();
199 NonObjectFreeListAllocator allocator(memStats);
200 AddMemoryPoolToAllocator(allocator);
201 std::pair<void *, size_t> pair;
202
203 std::array<std::pair<void *, size_t>, 3U> memoryElements;
204 for (size_t i = 0; i < 3U; i++) {
205 void *mem = allocator.Alloc(MIN_ALLOC_SIZE);
206 ASSERT_TRUE(mem != nullptr);
207 size_t index = SetBytesFromByteArray(mem, MIN_ALLOC_SIZE);
208 memoryElements.at(i) = std::pair<void *, size_t> {mem, index};
209 }
210
211 pair = memoryElements[1];
212 ASSERT_TRUE(CompareBytesWithByteArray(std::get<0>(pair), MIN_ALLOC_SIZE, std::get<1>(pair)));
213 allocator.Free(std::get<0>(pair));
214
215 pair = memoryElements[0];
216 ASSERT_TRUE(CompareBytesWithByteArray(std::get<0>(pair), MIN_ALLOC_SIZE, std::get<1>(pair)));
217 allocator.Free(std::get<0>(pair));
218
219 {
220 void *mem = allocator.Alloc(MIN_ALLOC_SIZE * 2U);
221 ASSERT_TRUE(mem != nullptr);
222 size_t index = SetBytesFromByteArray(mem, MIN_ALLOC_SIZE * 2U);
223 memoryElements.at(0) = std::pair<void *, size_t> {mem, index};
224 }
225
226 {
227 void *mem = allocator.Alloc(MIN_ALLOC_SIZE);
228 ASSERT_TRUE(mem != nullptr);
229 size_t index = SetBytesFromByteArray(mem, MIN_ALLOC_SIZE);
230 memoryElements.at(1) = std::pair<void *, size_t> {mem, index};
231 }
232
233 {
234 pair = memoryElements[0];
235 ASSERT_TRUE(CompareBytesWithByteArray(std::get<0>(pair), MIN_ALLOC_SIZE * 2U, std::get<1>(pair)));
236 allocator.Free(std::get<0>(pair));
237 }
238
239 {
240 pair = memoryElements[1];
241 ASSERT_TRUE(CompareBytesWithByteArray(std::get<0>(pair), MIN_ALLOC_SIZE, std::get<1>(pair)));
242 allocator.Free(std::get<0>(pair));
243 }
244
245 {
246 pair = memoryElements[2U];
247 ASSERT_TRUE(CompareBytesWithByteArray(std::get<0>(pair), MIN_ALLOC_SIZE, std::get<1>(pair)));
248 allocator.Free(std::get<0>(pair));
249 }
250 delete memStats;
251 }
252
TEST_F(FreeListAllocatorTest,MaxAllocationSizeTest)253 TEST_F(FreeListAllocatorTest, MaxAllocationSizeTest)
254 {
255 static constexpr size_t ALLOC_SIZE = MAX_ALLOC_SIZE;
256 static constexpr size_t ALLOC_COUNT = 2;
257 auto *memStats = new mem::MemStatsType();
258 NonObjectFreeListAllocator allocator(memStats);
259 AddMemoryPoolToAllocator(allocator);
260 std::array<void *, ALLOC_COUNT> memoryElements {};
261 for (size_t i = 0; i < ALLOC_COUNT; i++) {
262 void *mem = allocator.Alloc(ALLOC_SIZE);
263 ASSERT_TRUE(mem != nullptr);
264 memoryElements.at(i) = mem;
265 }
266 for (size_t i = 0; i < ALLOC_COUNT; i++) {
267 allocator.Free(memoryElements.at(i));
268 }
269 delete memStats;
270 }
271
TEST_F(FreeListAllocatorTest,AllocateTheWholePoolFreeAndAllocateAgainTest)272 TEST_F(FreeListAllocatorTest, AllocateTheWholePoolFreeAndAllocateAgainTest)
273 {
274 size_t minSizePowerOfTwo;
275 if ((FREELIST_ALLOCATOR_MIN_SIZE & (FREELIST_ALLOCATOR_MIN_SIZE - 1)) == 0U) {
276 minSizePowerOfTwo = ark::helpers::math::GetIntLog2(FREELIST_ALLOCATOR_MIN_SIZE);
277 } else {
278 // NOLINTNEXTLINE(readability-magic-numbers)
279 minSizePowerOfTwo = ceil(std::log(FREELIST_ALLOCATOR_MIN_SIZE) / std::log(2.0F));
280 }
281 if (((1U << minSizePowerOfTwo) - sizeof(freelist::MemoryBlockHeader)) < FREELIST_ALLOCATOR_MIN_SIZE) {
282 minSizePowerOfTwo++;
283 }
284 size_t allocSize = (1U << minSizePowerOfTwo) - sizeof(freelist::MemoryBlockHeader);
285 // To cover all memory we need to consider pool header size at first bytes of pool memory.
286 size_t firstAllocSize = (1U << minSizePowerOfTwo) - sizeof(freelist::MemoryBlockHeader) - POOL_HEADER_SIZE;
287 if (firstAllocSize < FREELIST_ALLOCATOR_MIN_SIZE) {
288 firstAllocSize = (1U << (minSizePowerOfTwo + 1)) - sizeof(freelist::MemoryBlockHeader) - POOL_HEADER_SIZE;
289 }
290 auto *memStats = new mem::MemStatsType();
291 NonObjectFreeListAllocator allocator(memStats);
292 AddMemoryPoolToAllocator(allocator);
293 std::vector<void *> memoryElements;
294 size_t allocCount = 0;
295
296 // Allocate first element
297 void *firstAllocMem = allocator.Alloc(firstAllocSize);
298 ASSERT_TRUE(firstAllocMem != nullptr);
299
300 // Allocate and use the whole alloc pool
301 while (true) {
302 void *mem = allocator.Alloc(allocSize);
303 if (mem == nullptr) {
304 break;
305 }
306 allocCount++;
307 memoryElements.push_back(mem);
308 }
309
310 // Free all elements
311 allocator.Free(firstAllocMem);
312 for (size_t i = 0; i < allocCount; i++) {
313 allocator.Free(memoryElements.back());
314 memoryElements.pop_back();
315 }
316
317 // Allocate first element again
318 firstAllocMem = allocator.Alloc(firstAllocSize);
319 ASSERT_TRUE(firstAllocMem != nullptr);
320
321 // Allocate again
322 for (size_t i = 0; i < allocCount; i++) {
323 void *mem = allocator.Alloc(allocSize);
324 ASSERT_TRUE(mem != nullptr);
325 memoryElements.push_back(mem);
326 }
327
328 // Free all elements again
329 allocator.Free(firstAllocMem);
330 for (size_t i = 0; i < allocCount; i++) {
331 allocator.Free(memoryElements.back());
332 memoryElements.pop_back();
333 }
334 delete memStats;
335 }
336
TEST_F(FreeListAllocatorTest,MTAllocFreeTest)337 TEST_F(FreeListAllocatorTest, MTAllocFreeTest)
338 {
339 static constexpr size_t MIN_ELEMENTS_COUNT = 500;
340 static constexpr size_t MAX_ELEMENTS_COUNT = 1000;
341 #if defined(PANDA_TARGET_ARM64) || defined(PANDA_TARGET_32)
342 // We have an issue with QEMU during MT tests. Issue 2852
343 static constexpr size_t THREADS_COUNT = 1;
344 #else
345 static constexpr size_t THREADS_COUNT = 10;
346 #endif
347 static constexpr size_t MAX_MT_ALLOC_SIZE = MAX_ALLOC_SIZE / 128;
348 static constexpr size_t MT_TEST_RUN_COUNT = 5;
349 // Threads can concurrently add Pools to the allocator, therefore, we must make it into account
350 // And also we must take fragmentation into account
351 ASSERT_TRUE(mem::MemConfig::GetHeapSizeLimit() >
352 2U * (AlignUp(MAX_ELEMENTS_COUNT * MAX_MT_ALLOC_SIZE, DEFAULT_POOL_SIZE_FOR_ALLOC)) +
353 THREADS_COUNT * DEFAULT_POOL_SIZE_FOR_ALLOC);
354 for (size_t i = 0; i < MT_TEST_RUN_COUNT; i++) {
355 MtAllocFreeTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_MT_ALLOC_SIZE, THREADS_COUNT>(MIN_ELEMENTS_COUNT,
356 MAX_ELEMENTS_COUNT);
357 ClearPoolManager(true);
358 }
359 }
360
TEST_F(FreeListAllocatorTest,MTAllocIterateTest)361 TEST_F(FreeListAllocatorTest, MTAllocIterateTest)
362 {
363 static constexpr size_t MIN_ELEMENTS_COUNT = 500;
364 static constexpr size_t MAX_ELEMENTS_COUNT = 1000;
365 #if defined(PANDA_TARGET_ARM64) || defined(PANDA_TARGET_32)
366 // We have an issue with QEMU during MT tests. Issue 2852
367 static constexpr size_t THREADS_COUNT = 1;
368 #else
369 static constexpr size_t THREADS_COUNT = 10;
370 #endif
371 static constexpr size_t MAX_MT_ALLOC_SIZE = MAX_ALLOC_SIZE / 128;
372 static constexpr size_t MT_TEST_RUN_COUNT = 5;
373 // Threads can concurrently add Pools to the allocator, therefore, we must make it into account
374 // And also we must take fragmentation into account
375 ASSERT_TRUE(mem::MemConfig::GetHeapSizeLimit() >
376 2U * (AlignUp(MAX_ELEMENTS_COUNT * MAX_MT_ALLOC_SIZE, DEFAULT_POOL_SIZE_FOR_ALLOC)) +
377 THREADS_COUNT * DEFAULT_POOL_SIZE_FOR_ALLOC);
378 for (size_t i = 0; i < MT_TEST_RUN_COUNT; i++) {
379 MtAllocIterateTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_MT_ALLOC_SIZE, THREADS_COUNT>(
380 MIN_ELEMENTS_COUNT, MAX_ELEMENTS_COUNT, CrossingMapSingleton::GetCrossingMapGranularity());
381 ClearPoolManager(true);
382 }
383 }
384
TEST_F(FreeListAllocatorTest,MTAllocCollectTest)385 TEST_F(FreeListAllocatorTest, MTAllocCollectTest)
386 {
387 static constexpr size_t MIN_ELEMENTS_COUNT = 500;
388 static constexpr size_t MAX_ELEMENTS_COUNT = 1000;
389 #if defined(PANDA_TARGET_ARM64) || defined(PANDA_TARGET_32)
390 // We have an issue with QEMU during MT tests. Issue 2852
391 static constexpr size_t THREADS_COUNT = 1;
392 #else
393 static constexpr size_t THREADS_COUNT = 10;
394 #endif
395 static constexpr size_t MAX_MT_ALLOC_SIZE = MAX_ALLOC_SIZE / 128;
396 static constexpr size_t MT_TEST_RUN_COUNT = 5;
397 // Threads can concurrently add Pools to the allocator, therefore, we must make it into account
398 // And also we must take fragmentation into account
399 ASSERT_TRUE(mem::MemConfig::GetHeapSizeLimit() >
400 2U * (AlignUp(MAX_ELEMENTS_COUNT * MAX_MT_ALLOC_SIZE, DEFAULT_POOL_SIZE_FOR_ALLOC)) +
401 THREADS_COUNT * DEFAULT_POOL_SIZE_FOR_ALLOC);
402 for (size_t i = 0; i < MT_TEST_RUN_COUNT; i++) {
403 MtAllocCollectTest<FREELIST_ALLOCATOR_MIN_SIZE, MAX_MT_ALLOC_SIZE, THREADS_COUNT>(MIN_ELEMENTS_COUNT,
404 MAX_ELEMENTS_COUNT);
405 ClearPoolManager(true);
406 }
407 }
408
409 /*
410 * This test checks that `Free` clears padding status bits in MemoryBlockHeader.
411 * We allocate 4 consecutive blocks and free the 3rd and 1st ones. After it we
412 * allocate block that needs alignment that leads to padding size is saved after
413 * block header and PADDING_STATUS_COMMON_HEADER_WITH_PADDING_SIZE bit is set.
414 * We free this block and allocator overwrites padding size by pointer to the next
415 * free block. Allocator should clear padding status otherwise incorrect padding
416 * will be used and we got heap corruption.
417 */
TEST_F(FreeListAllocatorTest,AlignTest)418 TEST_F(FreeListAllocatorTest, AlignTest)
419 {
420 auto memStats = std::unique_ptr<mem::MemStatsType>();
421 NonObjectFreeListAllocator allocator(memStats.get());
422 AddMemoryPoolToAllocator(allocator);
423
424 // NOLINTNEXTLINE(readability-magic-numbers)
425 auto *ptr1 = allocator.Alloc(1678U);
426 // NOLINTNEXTLINE(readability-magic-numbers)
427 auto *ptr2 = allocator.Alloc(1678U);
428 // NOLINTNEXTLINE(readability-magic-numbers)
429 auto *ptr3 = allocator.Alloc(1678U);
430 // NOLINTNEXTLINE(readability-magic-numbers)
431 auto *ptr4 = allocator.Alloc(1678U);
432
433 allocator.Free(ptr3);
434 allocator.Free(ptr1);
435
436 // NOLINTNEXTLINE(readability-magic-numbers)
437 auto *ptr5 = allocator.Alloc(1536U, GetLogAlignment(128U));
438 ASSERT_FALSE(IsAligned(reinterpret_cast<uintptr_t>(ptr3), 128U));
439 ASSERT_TRUE(IsAligned(reinterpret_cast<uintptr_t>(ptr5), 128U));
440 allocator.Free(ptr5);
441
442 // NOLINTNEXTLINE(readability-magic-numbers)
443 auto *ptr6 = allocator.Alloc(1272U);
444 // allocations 5 and 6 should use the same memory block. But after free padding bits
445 // should be cleared so pointers will be not equal.
446 ASSERT_TRUE(ptr5 != ptr6);
447 allocator.Free(ptr6);
448
449 allocator.Free(ptr2);
450 allocator.Free(ptr4);
451 }
452
453 } // namespace ark::mem
454