1 /*
2 * Copyright (C) 2018-2021 Intel Corporation
3 *
4 * SPDX-License-Identifier: MIT
5 *
6 */
7
8 #include "shared/source/utilities/heap_allocator.h"
9 #include "shared/test/common/test_macros/test.h"
10
11 #include "gtest/gtest.h"
12
13 #include <iostream>
14 #include <random>
15
16 using namespace NEO;
17
18 const size_t sizeThreshold = 16 * 4096;
19 const size_t allocationAlignment = MemoryConstants::pageSize;
20
21 class HeapAllocatorUnderTest : public HeapAllocator {
22 public:
HeapAllocatorUnderTest(uint64_t address,uint64_t size,size_t alignment,size_t threshold)23 HeapAllocatorUnderTest(uint64_t address, uint64_t size, size_t alignment, size_t threshold) : HeapAllocator(address, size, alignment, threshold) {}
HeapAllocatorUnderTest(uint64_t address,uint64_t size,size_t alignment)24 HeapAllocatorUnderTest(uint64_t address, uint64_t size, size_t alignment) : HeapAllocator(address, size, alignment) {}
HeapAllocatorUnderTest(uint64_t address,uint64_t size)25 HeapAllocatorUnderTest(uint64_t address, uint64_t size) : HeapAllocator(address, size) {}
26
getLeftBound() const27 uint64_t getLeftBound() const { return this->pLeftBound; }
getRightBound() const28 uint64_t getRightBound() const { return this->pRightBound; }
getavailableSize() const29 uint64_t getavailableSize() const { return this->availableSize; }
getThresholdSize() const30 size_t getThresholdSize() const { return this->sizeThreshold; }
31 using HeapAllocator::defragment;
32
getFromFreedChunks(size_t size,std::vector<HeapChunk> & vec,size_t requiredAlignment)33 uint64_t getFromFreedChunks(size_t size, std::vector<HeapChunk> &vec, size_t requiredAlignment) {
34 size_t sizeOfFreedChunk;
35 return HeapAllocator::getFromFreedChunks(size, vec, sizeOfFreedChunk, requiredAlignment);
36 }
storeInFreedChunks(uint64_t ptr,size_t size,std::vector<HeapChunk> & vec)37 void storeInFreedChunks(uint64_t ptr, size_t size, std::vector<HeapChunk> &vec) { return HeapAllocator::storeInFreedChunks(ptr, size, vec); }
38
getFreedChunksSmall()39 std::vector<HeapChunk> &getFreedChunksSmall() { return this->freedChunksSmall; };
getFreedChunksBig()40 std::vector<HeapChunk> &getFreedChunksBig() { return this->freedChunksBig; };
41
42 using HeapAllocator::allocationAlignment;
43 };
44
TEST(HeapAllocatorTest,WhenHeapAllocatorIsCreatedWithAlignmentThenAlignmentIsSet)45 TEST(HeapAllocatorTest, WhenHeapAllocatorIsCreatedWithAlignmentThenAlignmentIsSet) {
46 uint64_t ptrBase = 0x100000llu;
47 size_t size = 1024 * 4096;
48 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment);
49 EXPECT_EQ(MemoryConstants::pageSize, heapAllocator->allocationAlignment);
50 }
51
TEST(HeapAllocatorTest,WhenHeapAllocatorIsCreatedThenThresholdAndAlignmentIsSet)52 TEST(HeapAllocatorTest, WhenHeapAllocatorIsCreatedThenThresholdAndAlignmentIsSet) {
53 uint64_t ptrBase = 0x100000llu;
54 size_t size = 1024 * 4096;
55 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size);
56 EXPECT_NE(0u, heapAllocator->getThresholdSize());
57 EXPECT_EQ(MemoryConstants::pageSize, heapAllocator->allocationAlignment);
58 }
59
TEST(HeapAllocatorTest,WhenAllocatingThenUsageStatisticsAreUpdated)60 TEST(HeapAllocatorTest, WhenAllocatingThenUsageStatisticsAreUpdated) {
61 uint64_t ptrBase = 0x100000llu;
62 size_t size = 1024 * 4096;
63 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size);
64 EXPECT_EQ(heapAllocator->getavailableSize(), heapAllocator->getLeftSize());
65 EXPECT_EQ(0u, heapAllocator->getUsedSize());
66 EXPECT_EQ((double)0.0, heapAllocator->getUsage());
67
68 size_t ptrSize = 4096;
69 auto ptr = heapAllocator->allocate(ptrSize);
70 EXPECT_EQ(4096u, heapAllocator->getUsedSize());
71 EXPECT_LT((double)0.0, heapAllocator->getUsage());
72
73 heapAllocator->free(ptr, ptrSize);
74 }
75
TEST(HeapAllocatorTest,GivenExactSizeChunkInFreedChunksWhenGetIsCalledThenChunkIsReturned)76 TEST(HeapAllocatorTest, GivenExactSizeChunkInFreedChunksWhenGetIsCalledThenChunkIsReturned) {
77 uint64_t ptrBase = 0x100000llu;
78 size_t size = 1024 * 4096;
79 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
80
81 std::vector<HeapChunk> freedChunks;
82 uint64_t ptrFreed = 0x101000llu;
83 size_t sizeFreed = MemoryConstants::pageSize * 2;
84 freedChunks.emplace_back(ptrFreed, sizeFreed);
85
86 auto ptrReturned = heapAllocator->getFromFreedChunks(sizeFreed, freedChunks, allocationAlignment);
87
88 EXPECT_EQ(ptrFreed, ptrReturned); // ptr returned is the one that was stored
89 EXPECT_EQ(0u, freedChunks.size()); // entry in freed container is removed
90 }
91
TEST(HeapAllocatorTest,GivenOnlySmallerSizeChunksInFreedChunksWhenGetIsCalledThenNullptrIsReturned)92 TEST(HeapAllocatorTest, GivenOnlySmallerSizeChunksInFreedChunksWhenGetIsCalledThenNullptrIsReturned) {
93 uint64_t ptrBase = 0x100000llu;
94 size_t size = 1024 * 4096;
95 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
96
97 std::vector<HeapChunk> freedChunks;
98
99 freedChunks.emplace_back(0x100000llu, 4096);
100 freedChunks.emplace_back(0x101000llu, 4096);
101 freedChunks.emplace_back(0x105000llu, 4096);
102 freedChunks.emplace_back(0x104000llu, 4096);
103 freedChunks.emplace_back(0x102000llu, 8192);
104 freedChunks.emplace_back(0x109000llu, 8192);
105 freedChunks.emplace_back(0x107000llu, 4096);
106
107 EXPECT_EQ(7u, freedChunks.size());
108
109 auto ptrReturned = heapAllocator->getFromFreedChunks(4 * 4096, freedChunks, allocationAlignment);
110
111 EXPECT_EQ(0llu, ptrReturned);
112 EXPECT_EQ(7u, freedChunks.size());
113 }
114
TEST(HeapAllocatorTest,GivenOnlyBiggerSizeChunksInFreedChunksWhenGetIsCalledThenBestFitChunkIsReturned)115 TEST(HeapAllocatorTest, GivenOnlyBiggerSizeChunksInFreedChunksWhenGetIsCalledThenBestFitChunkIsReturned) {
116 uint64_t ptrBase = 0x100000llu;
117 size_t size = 1024 * 4096;
118 auto pUpperBound = ptrBase + size;
119
120 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
121
122 std::vector<HeapChunk> freedChunks;
123 uint64_t ptrExpected = 0llu;
124
125 pUpperBound -= 4096;
126 freedChunks.emplace_back(pUpperBound, 4096);
127 pUpperBound -= 5 * 4096;
128 freedChunks.emplace_back(pUpperBound, 5 * 4096);
129 pUpperBound -= 4 * 4096;
130 freedChunks.emplace_back(pUpperBound, 4 * 4096);
131 ptrExpected = pUpperBound;
132
133 pUpperBound -= 5 * 4096;
134 freedChunks.emplace_back(pUpperBound, 5 * 4096);
135 pUpperBound -= 4 * 4096;
136 freedChunks.emplace_back(pUpperBound, 4 * 4096);
137
138 EXPECT_EQ(5u, freedChunks.size());
139
140 auto ptrReturned = heapAllocator->getFromFreedChunks(3 * 4096, freedChunks, allocationAlignment);
141
142 EXPECT_EQ(ptrExpected, ptrReturned);
143 EXPECT_EQ(4u, freedChunks.size());
144 }
145
TEST(HeapAllocatorTest,GivenOnlyMoreThanTwiceBiggerSizeChunksInFreedChunksWhenGetIsCalledThenSplittedChunkIsReturned)146 TEST(HeapAllocatorTest, GivenOnlyMoreThanTwiceBiggerSizeChunksInFreedChunksWhenGetIsCalledThenSplittedChunkIsReturned) {
147 uint64_t ptrBase = 0x100000llu;
148 size_t size = 1024 * 4096;
149 auto pLowerBound = ptrBase;
150
151 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
152
153 std::vector<HeapChunk> freedChunks;
154 uint64_t ptrExpected = 0llu;
155 size_t requestedSize = 3 * 4096;
156
157 freedChunks.emplace_back(pLowerBound, 4096);
158 pLowerBound += 4096;
159 freedChunks.emplace_back(pLowerBound, 9 * 4096);
160 pLowerBound += 9 * 4096;
161 freedChunks.emplace_back(pLowerBound, 7 * 4096);
162
163 size_t deltaSize = 7 * 4096 - requestedSize;
164 ptrExpected = pLowerBound + deltaSize;
165
166 EXPECT_EQ(3u, freedChunks.size());
167
168 auto ptrReturned = heapAllocator->getFromFreedChunks(requestedSize, freedChunks, allocationAlignment);
169
170 EXPECT_EQ(ptrExpected, ptrReturned);
171 EXPECT_EQ(3u, freedChunks.size());
172
173 EXPECT_EQ(pLowerBound, freedChunks[2].ptr);
174 EXPECT_EQ(deltaSize, freedChunks[2].size);
175 }
176
TEST(HeapAllocatorTest,GivenStoredChunkAdjacentToLeftBoundaryOfIncomingChunkWhenStoreIsCalledThenChunkIsMerged)177 TEST(HeapAllocatorTest, GivenStoredChunkAdjacentToLeftBoundaryOfIncomingChunkWhenStoreIsCalledThenChunkIsMerged) {
178 uint64_t ptrBase = 0x100000llu;
179 size_t size = 1024 * 4096;
180 auto pLowerBound = ptrBase;
181
182 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
183
184 std::vector<HeapChunk> freedChunks;
185 uint64_t ptrExpected = 0llu;
186 size_t expectedSize = 9 * 4096;
187
188 freedChunks.emplace_back(pLowerBound, 4096);
189 pLowerBound += 4096;
190 freedChunks.emplace_back(pLowerBound, 9 * 4096);
191 ptrExpected = pLowerBound;
192 pLowerBound += 9 * 4096;
193
194 EXPECT_EQ(ptrExpected, freedChunks[1].ptr);
195 EXPECT_EQ(expectedSize, freedChunks[1].size);
196
197 EXPECT_EQ(2u, freedChunks.size());
198
199 auto ptrToStore = pLowerBound;
200 size_t sizeToStore = 2 * 4096;
201
202 expectedSize += sizeToStore;
203
204 heapAllocator->storeInFreedChunks(ptrToStore, sizeToStore, freedChunks);
205
206 EXPECT_EQ(2u, freedChunks.size());
207
208 EXPECT_EQ(ptrExpected, freedChunks[1].ptr);
209 EXPECT_EQ(expectedSize, freedChunks[1].size);
210 }
211
TEST(HeapAllocatorTest,GivenStoredChunkAdjacentToRightBoundaryOfIncomingChunkWhenStoreIsCalledThenChunkIsMerged)212 TEST(HeapAllocatorTest, GivenStoredChunkAdjacentToRightBoundaryOfIncomingChunkWhenStoreIsCalledThenChunkIsMerged) {
213 uint64_t ptrBase = 0x100000llu;
214 size_t size = 1024 * 4096;
215 auto pLowerBound = ptrBase;
216
217 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
218
219 std::vector<HeapChunk> freedChunks;
220 uint64_t ptrExpected = 0llu;
221 size_t expectedSize = 9 * 4096;
222
223 freedChunks.emplace_back(pLowerBound, 4096);
224 pLowerBound += 4096;
225 pLowerBound += 4096; // space between stored chunk and chunk to store
226
227 auto ptrToStore = pLowerBound;
228 size_t sizeToStore = 2 * 4096;
229 pLowerBound += sizeToStore;
230
231 freedChunks.emplace_back(pLowerBound, 9 * 4096);
232 ptrExpected = pLowerBound;
233
234 EXPECT_EQ(ptrExpected, freedChunks[1].ptr);
235 EXPECT_EQ(expectedSize, freedChunks[1].size);
236
237 EXPECT_EQ(2u, freedChunks.size());
238
239 expectedSize += sizeToStore;
240 ptrExpected = ptrToStore;
241
242 heapAllocator->storeInFreedChunks(ptrToStore, sizeToStore, freedChunks);
243
244 EXPECT_EQ(2u, freedChunks.size());
245
246 EXPECT_EQ(ptrExpected, freedChunks[1].ptr);
247 EXPECT_EQ(expectedSize, freedChunks[1].size);
248 }
249
TEST(HeapAllocatorTest,GivenStoredChunkNotAdjacentToIncomingChunkWhenStoreIsCalledThenNewFreeChunkIsCreated)250 TEST(HeapAllocatorTest, GivenStoredChunkNotAdjacentToIncomingChunkWhenStoreIsCalledThenNewFreeChunkIsCreated) {
251 uint64_t ptrBase = 0x100000llu;
252 size_t size = 1024 * 4096;
253 auto pLowerBound = ptrBase;
254
255 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
256
257 std::vector<HeapChunk> freedChunks;
258
259 freedChunks.emplace_back(pLowerBound, 4096);
260 pLowerBound += 4096;
261 freedChunks.emplace_back(pLowerBound, 9 * 4096);
262 pLowerBound += 9 * 4096;
263
264 pLowerBound += 9 * 4096;
265
266 uint64_t ptrToStore = pLowerBound;
267 size_t sizeToStore = 4096;
268
269 EXPECT_EQ(2u, freedChunks.size());
270
271 heapAllocator->storeInFreedChunks(ptrToStore, sizeToStore, freedChunks);
272
273 EXPECT_EQ(3u, freedChunks.size());
274
275 EXPECT_EQ(ptrToStore, freedChunks[2].ptr);
276 EXPECT_EQ(sizeToStore, freedChunks[2].size);
277 }
278
TEST(HeapAllocatorTest,GivenStoredChunkExpandableByIncomingChunkWhenStoreIsCalledThenChunksAreMerged)279 TEST(HeapAllocatorTest, GivenStoredChunkExpandableByIncomingChunkWhenStoreIsCalledThenChunksAreMerged) {
280 uint64_t ptrBase = 0x100000llu;
281 size_t size = 1024 * 4096;
282 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
283
284 std::vector<HeapChunk> freedChunks;
285
286 freedChunks.emplace_back(0x100000llu, 4096);
287 freedChunks.emplace_back(0x103000llu, 4096);
288
289 EXPECT_EQ(2u, freedChunks.size());
290
291 uint64_t ptrToStore = 0x102000llu;
292 size_t sizeToStore = 2 * 4096;
293
294 heapAllocator->storeInFreedChunks(ptrToStore, sizeToStore, freedChunks);
295
296 EXPECT_EQ(2u, freedChunks.size());
297
298 auto ptrReturned = heapAllocator->getFromFreedChunks(2 * 4096, freedChunks, allocationAlignment);
299
300 EXPECT_EQ(0x102000llu, ptrReturned);
301 EXPECT_EQ(1u, freedChunks.size());
302 }
303
TEST(HeapAllocatorTest,WhenAllocatingThenEntryIsAddedToMap)304 TEST(HeapAllocatorTest, WhenAllocatingThenEntryIsAddedToMap) {
305 uint64_t ptrBase = 0x100000llu;
306 size_t size = 1024 * 4096;
307 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
308
309 size_t ptrSize = 4096;
310 uint64_t ptr = heapAllocator->allocate(ptrSize);
311
312 EXPECT_NE(0llu, ptr);
313 EXPECT_LE(ptrBase, ptr);
314
315 size_t ptrSize2 = sizeThreshold + 4096;
316 ptr = heapAllocator->allocate(ptrSize2);
317
318 EXPECT_NE(0llu, ptr);
319 EXPECT_LE(ptrBase, ptr);
320 }
321
TEST(HeapAllocatorTest,WhenFreeingThenEntryIsRemovedFromMapAndSpaceMadeAvailable)322 TEST(HeapAllocatorTest, WhenFreeingThenEntryIsRemovedFromMapAndSpaceMadeAvailable) {
323 uint64_t ptrBase = 0x100000llu;
324 size_t size = 1024u * 4096u;
325 auto pLeftBound = ptrBase;
326 auto pRightBound = pLeftBound + size;
327
328 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
329
330 size_t ptrSize = 4096;
331 uint64_t ptr = heapAllocator->allocate(ptrSize);
332
333 EXPECT_NE(0llu, ptr);
334 EXPECT_LE(ptrBase, ptr);
335
336 size_t ptrSize2 = sizeThreshold + 4096;
337 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
338
339 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound + sizeThreshold + 4096u);
340 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound - 4096u);
341
342 EXPECT_EQ(heapAllocator->getavailableSize(), size - (sizeThreshold + 4096u) - 4096u);
343
344 heapAllocator->free(ptr, ptrSize);
345 heapAllocator->free(ptr2, ptrSize2);
346
347 EXPECT_EQ(heapAllocator->getavailableSize(), size);
348
349 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound);
350 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound);
351 }
352
TEST(HeapAllocatorTest,WhenAllocatingMultipleThenEachAllocationIsDistinct)353 TEST(HeapAllocatorTest, WhenAllocatingMultipleThenEachAllocationIsDistinct) {
354 uint64_t ptrBase = 0x100000llu;
355 size_t size = 1024 * 4096;
356
357 size_t allocSize = 4096;
358 size_t doubleAllocSize = 4096 * 2;
359
360 for (uint32_t i = 0u; i < 2u; i++) {
361 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
362 doubleAllocSize = allocSize * 2;
363 auto pLeftBound = ptrBase;
364 auto pRightBound = pLeftBound + size;
365
366 uint64_t ptr1 = heapAllocator->allocate(allocSize);
367 EXPECT_NE(0llu, ptr1);
368 EXPECT_LE(ptrBase, ptr1);
369
370 uint64_t ptr2 = heapAllocator->allocate(allocSize);
371 EXPECT_NE(0llu, ptr2);
372
373 uint64_t ptr3 = heapAllocator->allocate(doubleAllocSize);
374 EXPECT_NE(0llu, ptr3);
375
376 uint64_t ptr4 = heapAllocator->allocate(allocSize);
377 EXPECT_NE(0llu, ptr4);
378
379 EXPECT_NE(ptr1, ptr2);
380 EXPECT_NE(ptr1, ptr3);
381 EXPECT_NE(ptr1, ptr4);
382 EXPECT_NE(ptr2, ptr3);
383 EXPECT_NE(ptr2, ptr4);
384 EXPECT_NE(ptr3, ptr4);
385
386 size_t totalAllocationSize = 3 * allocSize + 2 * allocSize;
387 EXPECT_LE(heapAllocator->getavailableSize(), size - totalAllocationSize);
388
389 if (i == 0u) {
390 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound - totalAllocationSize);
391 } else if (i == 1u) {
392 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound + totalAllocationSize);
393 }
394
395 allocSize += sizeThreshold;
396 }
397 }
398
TEST(HeapAllocatorTest,GivenNoSpaceLeftWhenAllocatingThenZeroIsReturned)399 TEST(HeapAllocatorTest, GivenNoSpaceLeftWhenAllocatingThenZeroIsReturned) {
400 uint64_t ptrBase = 0x100000llu;
401 size_t size = 1024 * 4096;
402 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
403
404 size_t ptrSize = 4096;
405 uint64_t ptr1 = heapAllocator->allocate(ptrSize);
406 EXPECT_NE(0llu, ptr1);
407 EXPECT_LE(ptrBase, ptr1);
408
409 size_t ptrSize2 = 1023 * 4096;
410 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
411 EXPECT_NE(0llu, ptr2);
412
413 EXPECT_EQ(heapAllocator->getLeftBound(), heapAllocator->getRightBound());
414 EXPECT_EQ(0u, heapAllocator->getavailableSize());
415
416 size_t ptrSize3 = 8192;
417 uint64_t ptr3 = heapAllocator->allocate(ptrSize3);
418 EXPECT_EQ(0llu, ptr3);
419 }
420
TEST(HeapAllocatorTest,GivenReverseOrderWhenFreeingThenHeapAllocatorStateIsCorrect)421 TEST(HeapAllocatorTest, GivenReverseOrderWhenFreeingThenHeapAllocatorStateIsCorrect) {
422 uint64_t ptrBase = 0x100000llu;
423 size_t size = 1024 * 4096;
424 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
425
426 auto pLeftBound = ptrBase;
427 auto pRightBound = pLeftBound + size;
428
429 size_t ptr1Size = 4096;
430 uint64_t ptr1 = heapAllocator->allocate(ptr1Size);
431 EXPECT_NE(0llu, ptr1);
432 EXPECT_LE(ptrBase, ptr1);
433
434 size_t ptrSize2 = sizeThreshold + 4096;
435 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
436 EXPECT_NE(0llu, ptr2);
437
438 size_t ptrSize3 = 8192;
439 uint64_t ptr3 = heapAllocator->allocate(ptrSize3);
440 EXPECT_NE(0llu, ptr3);
441
442 heapAllocator->free(ptr3, ptrSize3);
443 heapAllocator->free(ptr2, ptrSize2);
444 heapAllocator->free(ptr1, ptr1Size);
445
446 EXPECT_EQ(heapAllocator->getavailableSize(), size);
447
448 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
449 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
450
451 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound);
452 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound);
453 }
454
TEST(HeapAllocatorTest,GivenNoMemoryLeftWhenAllocatingThenZeroIsReturned)455 TEST(HeapAllocatorTest, GivenNoMemoryLeftWhenAllocatingThenZeroIsReturned) {
456 uint64_t ptrBase = 0x100000llu;
457 size_t size = 0;
458 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
459
460 size_t ptrSize = 4096;
461 uint64_t ptr = heapAllocator->allocate(ptrSize);
462
463 EXPECT_EQ(0llu, ptr);
464 EXPECT_EQ(0u, heapAllocator->getavailableSize());
465 }
466
TEST(HeapAllocatorTest,GivenSizeGreaterThanMemoryLeftWhenAllocatingThenZeroIsReturned)467 TEST(HeapAllocatorTest, GivenSizeGreaterThanMemoryLeftWhenAllocatingThenZeroIsReturned) {
468 uint64_t ptrBase = 0x100000llu;
469 size_t size = 11 * 4096;
470 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, 3 * 4096);
471 size_t remainingSize = size;
472
473 // first small succeeds
474 size_t ptrSize = 4096;
475 uint64_t ptr = heapAllocator->allocate(ptrSize);
476 EXPECT_NE(0llu, ptr);
477 // second small suceeds
478 size_t ptrSize1 = 4096;
479 uint64_t ptr1 = heapAllocator->allocate(ptrSize1);
480 // free first to store on free list
481 heapAllocator->free(ptr, ptrSize);
482 remainingSize -= 4096;
483
484 EXPECT_NE(0llu, ptr1);
485 EXPECT_EQ(remainingSize, heapAllocator->getavailableSize());
486
487 // first big succeeds
488 size_t ptrSize2 = 4 * 4096;
489 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
490 EXPECT_NE(0llu, ptr2);
491 // second big succeeds
492 size_t ptrSize3 = 4 * 4096;
493 uint64_t ptr3 = heapAllocator->allocate(ptrSize3);
494 EXPECT_NE(0llu, ptr3);
495 // free first big to store on free list
496 heapAllocator->free(ptr2, 4 * 4096);
497 remainingSize -= 4 * 4096;
498
499 EXPECT_EQ(remainingSize, heapAllocator->getavailableSize());
500
501 // third small fails
502 size_t ptrSize4 = 2 * 4096;
503 uint64_t ptr4 = heapAllocator->allocate(ptrSize4);
504 EXPECT_EQ(0llu, ptr4);
505 // third big fails
506 size_t ptrSize5 = 5 * 4096;
507 uint64_t ptr5 = heapAllocator->allocate(ptrSize5);
508 EXPECT_EQ(0llu, ptr5);
509 }
510
TEST(HeapAllocatorTest,GivenNullWhenFreeingThenNothingHappens)511 TEST(HeapAllocatorTest, GivenNullWhenFreeingThenNothingHappens) {
512 uint64_t ptrBase = 0x100000llu;
513 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, sizeThreshold, allocationAlignment, sizeThreshold);
514
515 heapAllocator->free(0llu, 0);
516
517 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
518 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
519 }
520
TEST(HeapAllocatorTest,WhenFreeingThenMemoryAvailableForAllocation)521 TEST(HeapAllocatorTest, WhenFreeingThenMemoryAvailableForAllocation) {
522 uint64_t ptrBase = 0x100000llu;
523 size_t size = 1024 * 4096;
524 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
525
526 auto pLeftBound = ptrBase;
527 auto pRightBound = pLeftBound + size;
528
529 size_t ptrSize = 8192;
530 uint64_t ptr = heapAllocator->allocate(ptrSize);
531 EXPECT_NE(0llu, ptr);
532 EXPECT_LE(ptrBase, ptr);
533
534 size_t ptrSize1 = 8192;
535 uint64_t ptr1 = heapAllocator->allocate(ptrSize1);
536 EXPECT_NE(0llu, ptr1);
537 EXPECT_LE(ptrBase, ptr1);
538
539 size_t ptrSize2 = 8192;
540 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
541 EXPECT_NE(0llu, ptr2);
542
543 heapAllocator->free(ptr1, ptrSize1);
544
545 EXPECT_EQ(1u, heapAllocator->getFreedChunksSmall().size());
546 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
547
548 size_t ptrSize3 = 8192;
549 uint64_t ptr3 = heapAllocator->allocate(ptrSize3);
550 EXPECT_NE(0llu, ptr3);
551
552 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
553 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
554
555 heapAllocator->free(ptr2, ptrSize2);
556
557 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
558 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
559
560 heapAllocator->free(ptr3, ptrSize3);
561
562 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
563 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
564
565 heapAllocator->free(ptr, ptrSize);
566
567 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound);
568 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound);
569 }
570
TEST(HeapAllocatorTest,WhenFreeingChunkThenMemoryAvailableForAllocation)571 TEST(HeapAllocatorTest, WhenFreeingChunkThenMemoryAvailableForAllocation) {
572 uint64_t ptrBase = 0x100000llu;
573 size_t size = 1024 * 4096;
574 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
575
576 auto pLeftBound = ptrBase;
577 auto pRightBound = pLeftBound + size;
578
579 size_t sizeAllocated = 0;
580
581 size_t ptrSize = 8192;
582 uint64_t ptr = heapAllocator->allocate(ptrSize);
583 EXPECT_NE(0llu, ptr);
584 EXPECT_LE(ptrBase, ptr);
585
586 sizeAllocated += 8192;
587
588 size_t ptrSize1 = 4 * 4096;
589 uint64_t ptr1 = heapAllocator->allocate(ptrSize1);
590 EXPECT_NE(0llu, ptr1);
591 EXPECT_LE(ptrBase, ptr1);
592
593 sizeAllocated += 4 * 4096;
594
595 size_t ptrSize2 = 8192;
596 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
597 EXPECT_NE(0llu, ptr2);
598
599 sizeAllocated += 8192;
600 EXPECT_EQ(size - sizeAllocated, heapAllocator->getavailableSize());
601
602 heapAllocator->free(ptr1, ptrSize1);
603
604 sizeAllocated -= 4 * 4096;
605 EXPECT_EQ(size - sizeAllocated, heapAllocator->getavailableSize());
606
607 EXPECT_EQ(1u, heapAllocator->getFreedChunksSmall().size());
608 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
609
610 size_t ptrSize3 = 3 * 4096;
611 uint64_t ptr3 = heapAllocator->allocate(ptrSize3);
612 EXPECT_NE(0llu, ptr3);
613
614 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
615 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
616
617 sizeAllocated += 4 * 4096; // 4*4096 because this was chunk that was stored on free list
618 EXPECT_EQ(size - sizeAllocated, heapAllocator->getavailableSize());
619
620 heapAllocator->free(ptr2, ptrSize2);
621
622 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
623 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
624
625 heapAllocator->free(ptr3, ptrSize3);
626
627 EXPECT_EQ(0u, heapAllocator->getFreedChunksSmall().size());
628 EXPECT_EQ(0u, heapAllocator->getFreedChunksBig().size());
629
630 heapAllocator->free(ptr, ptrSize);
631
632 EXPECT_EQ(heapAllocator->getLeftBound(), pLeftBound);
633 EXPECT_EQ(heapAllocator->getRightBound(), pRightBound);
634 EXPECT_EQ(size, heapAllocator->getavailableSize());
635 }
636
TEST(HeapAllocatorTest,GivenSmallAllocationGreaterThanAvailableSizeWhenAllocatingThenZeroIsReturned)637 TEST(HeapAllocatorTest, GivenSmallAllocationGreaterThanAvailableSizeWhenAllocatingThenZeroIsReturned) {
638 uint64_t ptrBase = 0x100000llu;
639 size_t size = 1024 * 4096;
640 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
641
642 size_t ptrSize1 = size - 4096;
643 uint64_t ptr1 = heapAllocator->allocate(ptrSize1);
644 EXPECT_NE(0llu, ptr1);
645 EXPECT_LE(ptrBase, ptr1);
646
647 EXPECT_EQ(4096u, heapAllocator->getavailableSize());
648
649 size_t ptrSize2 = 8192;
650 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
651 EXPECT_EQ(0llu, ptr2);
652 }
653
TEST(HeapAllocatorTest,GivenBigAllocationGreaterThanAvailableSizeWhenAllocatingThenZeroIsReturned)654 TEST(HeapAllocatorTest, GivenBigAllocationGreaterThanAvailableSizeWhenAllocatingThenZeroIsReturned) {
655 uint64_t ptrBase = 0x100000llu;
656 size_t size = 1024 * 4096;
657 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, sizeThreshold);
658
659 size_t ptrSize1 = 8192;
660 uint64_t ptr1 = heapAllocator->allocate(ptrSize1);
661 EXPECT_NE(0llu, ptr1);
662 EXPECT_LE(ptrBase, ptr1);
663
664 EXPECT_EQ(size - 8192u, heapAllocator->getavailableSize());
665
666 size_t ptrSize2 = size - 4096;
667 uint64_t ptr2 = heapAllocator->allocate(ptrSize2);
668 EXPECT_EQ(0llu, ptr2);
669 }
670
TEST(HeapAllocatorTest,WhenMemoryIsAllocatedThenAllocationsDoNotOverlap)671 TEST(HeapAllocatorTest, WhenMemoryIsAllocatedThenAllocationsDoNotOverlap) {
672 std::ranlux24 generator(1);
673
674 const uint32_t maxIndex = 2000;
675
676 std::unique_ptr<uint64_t[]> ptrs(new uint64_t[maxIndex]);
677 std::unique_ptr<size_t[]> sizes(new size_t[maxIndex]);
678
679 memset(ptrs.get(), 0, sizeof(uint64_t) * maxIndex);
680 memset(sizes.get(), 0, sizeof(size_t) * maxIndex);
681
682 uint16_t *freeIndexes = new uint16_t[maxIndex];
683 std::unique_ptr<uint16_t[]> indexes(new uint16_t[maxIndex]);
684 memset(freeIndexes, 0, sizeof(uint16_t) * maxIndex);
685 memset(indexes.get(), 0, sizeof(uint16_t) * maxIndex);
686
687 // Generate random unique indexes
688 for (uint32_t i = 0; i < maxIndex; i++) {
689 uint16_t index = (generator() + 1) % maxIndex;
690
691 if (freeIndexes[index] == 0) {
692 indexes[i] = index;
693 freeIndexes[index] = 1;
694 }
695 }
696
697 delete[] freeIndexes;
698 uint64_t allocatorSize = 1024llu * 1024llu; // 1 MB
699 void *pBasePtr = alignedMalloc(static_cast<size_t>(allocatorSize), 4096);
700 uint64_t basePtr = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(pBasePtr));
701 constexpr size_t reqAlignment = 4;
702 size_t bigAllocationThreshold = (512 + 256) * reqAlignment;
703
704 memset(pBasePtr, 0, static_cast<size_t>(allocatorSize));
705 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(basePtr, allocatorSize, allocationAlignment, bigAllocationThreshold);
706 heapAllocator->allocationAlignment = reqAlignment;
707
708 for (uint32_t i = 0; i < maxIndex; i++) {
709 if (indexes[i] != 0) {
710 size_t sizeToAllocate = (indexes[i] % 1024) * reqAlignment;
711 ASSERT_LT(sizeToAllocate, allocatorSize);
712 sizes[i] = sizeToAllocate;
713 ptrs[i] = heapAllocator->allocate(sizes[i]);
714
715 if (ptrs[i] == 0llu)
716 break;
717
718 uint8_t *pTemp = reinterpret_cast<uint8_t *>(ptrs[i]);
719 for (uint32_t j = 0; j < sizes[i] / 4096; j++) {
720 *pTemp += 1;
721 pTemp += 4096;
722 }
723
724 uint32_t indexToFree = indexes[i] % (i * 2 + 1);
725 if (ptrs[indexToFree]) {
726 memset(reinterpret_cast<void *>(ptrs[indexToFree]), 0, sizes[indexToFree]);
727 heapAllocator->free(ptrs[indexToFree], sizes[indexToFree]);
728 ptrs[indexToFree] = 0llu;
729 sizes[indexToFree] = 0;
730 }
731 }
732 }
733
734 uint8_t *pTemp = reinterpret_cast<uint8_t *>(pBasePtr);
735
736 for (uint32_t i = 0; i < allocatorSize / reqAlignment; i++) {
737 if (*pTemp > 1) {
738 EXPECT_TRUE(false) << "Heap from Allocator corrupted at page offset " << i << std::endl;
739 }
740 }
741
742 for (uint32_t i = 0; i < maxIndex; i++) {
743 if (ptrs[i] != 0) {
744 heapAllocator->free(ptrs[i], sizes[i]);
745 }
746 }
747
748 //at this point we should be able to allocate full size
749 size_t totalSize = (size_t)(allocatorSize - reqAlignment);
750 auto finalPtr = heapAllocator->allocate(totalSize);
751 EXPECT_NE(0llu, finalPtr);
752
753 heapAllocator->free(finalPtr, totalSize);
754
755 alignedFree(pBasePtr);
756 }
757
TEST(HeapAllocatorTest,GivenLargeAllocationsWhenFreeingThenSpaceIsDefragmented)758 TEST(HeapAllocatorTest, GivenLargeAllocationsWhenFreeingThenSpaceIsDefragmented) {
759 uint64_t ptrBase = 0x100000llu;
760 uint64_t basePtr = 0x100000llu;
761 size_t size = 1024 * 4096;
762
763 size_t threshold = 4096;
764 size_t allocSize = 2 * MemoryConstants::pageSize;
765 size_t doubleallocSize = 2 * allocSize;
766 size_t tripleallocSize = 3 * allocSize;
767
768 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, threshold);
769
770 std::vector<HeapChunk> &freedChunks = heapAllocator->getFreedChunksBig();
771
772 // 0, 1, 2 - can be merged to one
773 // 6,7,8,10 - can be merged to one
774
775 uint64_t ptrs[12];
776 ptrs[0] = heapAllocator->allocate(allocSize);
777 ptrs[1] = heapAllocator->allocate(allocSize);
778 ptrs[2] = heapAllocator->allocate(allocSize);
779 ptrs[3] = heapAllocator->allocate(tripleallocSize);
780 ptrs[4] = 0llu;
781 ptrs[5] = 0llu;
782 ptrs[6] = heapAllocator->allocate(allocSize);
783 ptrs[7] = heapAllocator->allocate(allocSize);
784 ptrs[8] = heapAllocator->allocate(doubleallocSize);
785 ptrs[9] = 0llu;
786 ptrs[10] = heapAllocator->allocate(allocSize);
787 ptrs[11] = heapAllocator->allocate(allocSize);
788
789 heapAllocator->free(ptrs[0], allocSize);
790 heapAllocator->free(ptrs[10], allocSize);
791 heapAllocator->free(ptrs[2], allocSize);
792 heapAllocator->free(ptrs[6], allocSize);
793 heapAllocator->free(ptrs[1], allocSize);
794 heapAllocator->free(ptrs[7], allocSize);
795 heapAllocator->free(ptrs[8], doubleallocSize);
796
797 // 0,1 merged on free,
798 // 2
799 // 6,7 - merged on free
800 // 8, 10 - merged on free
801 EXPECT_EQ(4u, freedChunks.size());
802
803 heapAllocator->defragment();
804
805 ASSERT_EQ(2u, freedChunks.size());
806
807 EXPECT_EQ(basePtr, freedChunks[0].ptr);
808 EXPECT_EQ(3 * allocSize, freedChunks[0].size);
809
810 EXPECT_EQ((basePtr + 6 * allocSize), freedChunks[1].ptr);
811 EXPECT_EQ(5 * allocSize, freedChunks[1].size);
812 }
813
TEST(HeapAllocatorTest,GivenSmallAllocationsWhenFreeingThenSpaceIsDefragmented)814 TEST(HeapAllocatorTest, GivenSmallAllocationsWhenFreeingThenSpaceIsDefragmented) {
815 uint64_t ptrBase = 0x100000llu;
816 uint64_t basePtr = 0x100000;
817
818 size_t size = 1024 * 4096;
819 uint64_t upperLimitPtr = basePtr + size;
820
821 size_t threshold = 2 * MemoryConstants::pageSize;
822 size_t allocSize = MemoryConstants::pageSize;
823 size_t doubleallocSize = 2 * allocSize;
824
825 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, threshold);
826
827 std::vector<HeapChunk> &freedChunks = heapAllocator->getFreedChunksSmall();
828
829 // 0, 1, 2 - can be merged to one
830 // 6,7,8,10 - can be merged to one
831
832 uint64_t ptrs[12];
833 ptrs[0] = heapAllocator->allocate(allocSize);
834 ptrs[1] = heapAllocator->allocate(allocSize);
835 ptrs[2] = heapAllocator->allocate(allocSize);
836 ptrs[3] = heapAllocator->allocate(doubleallocSize);
837 ptrs[4] = 0llu;
838 ptrs[5] = 0llu;
839 ptrs[6] = heapAllocator->allocate(allocSize);
840 ptrs[7] = heapAllocator->allocate(allocSize);
841 ptrs[8] = heapAllocator->allocate(doubleallocSize);
842 ptrs[9] = 0llu;
843 ptrs[10] = heapAllocator->allocate(allocSize);
844 ptrs[11] = heapAllocator->allocate(allocSize);
845
846 heapAllocator->free(ptrs[0], allocSize);
847 heapAllocator->free(ptrs[2], allocSize);
848 heapAllocator->free(ptrs[8], doubleallocSize);
849 heapAllocator->free(ptrs[1], allocSize);
850 heapAllocator->free(ptrs[6], allocSize);
851 heapAllocator->free(ptrs[7], allocSize);
852 heapAllocator->free(ptrs[10], allocSize);
853
854 // 0,1 merged on free,
855 // 2
856 // 6, - merged on free
857 // 7, 8, 10 - merged on free
858 EXPECT_EQ(4u, freedChunks.size());
859
860 heapAllocator->defragment();
861
862 ASSERT_EQ(2u, freedChunks.size());
863
864 EXPECT_EQ((upperLimitPtr - 3 * allocSize), freedChunks[0].ptr);
865 EXPECT_EQ(3 * allocSize, freedChunks[0].size);
866
867 EXPECT_EQ((upperLimitPtr - 10 * allocSize), freedChunks[1].ptr);
868 EXPECT_EQ(5 * allocSize, freedChunks[1].size);
869 }
870
TEST(HeapAllocatorTest,Given10SmallAllocationsWhenFreedInTheSameOrderThenLastChunkFreedReturnsWholeSpaceToFreeRange)871 TEST(HeapAllocatorTest, Given10SmallAllocationsWhenFreedInTheSameOrderThenLastChunkFreedReturnsWholeSpaceToFreeRange) {
872 uint64_t ptrBase = 0llu;
873 size_t size = 1024 * 4096;
874 size_t threshold = 2 * 4096;
875
876 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, threshold);
877
878 std::vector<HeapChunk> &freedChunks = heapAllocator->getFreedChunksSmall();
879
880 uint64_t ptrs[10];
881 size_t sizes[10];
882
883 for (uint32_t i = 0; i < 10; i++) {
884 sizes[i] = 4096;
885 ptrs[i] = heapAllocator->allocate(sizes[i]);
886 }
887
888 EXPECT_EQ(0u, freedChunks.size());
889
890 for (uint32_t i = 0; i < 10; i++) {
891 heapAllocator->free(ptrs[i], sizes[i]);
892 // After free chunk gets merged to existing one on freed list
893 if (i < 9) {
894 EXPECT_EQ(1u, freedChunks.size());
895 }
896 }
897
898 // Last chunk released merges freed chunk to free range
899 EXPECT_EQ(0u, freedChunks.size());
900 }
901
TEST(HeapAllocatorTest,Given10SmallAllocationsWhenMergedToBigAllocatedAsSmallSplittedAndReleasedThenItDoesNotGoToFreedBigChunksList)902 TEST(HeapAllocatorTest, Given10SmallAllocationsWhenMergedToBigAllocatedAsSmallSplittedAndReleasedThenItDoesNotGoToFreedBigChunksList) {
903 uint64_t ptrBase = 0llu;
904 uintptr_t basePtr = 0;
905
906 // Size for 10 small allocs plus one single 2 page plus some space
907 size_t size = (10 + 2 + 1) * 4096;
908 uintptr_t upperLimitPtr = basePtr + size;
909
910 size_t threshold = 4 * 4096;
911
912 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, threshold);
913
914 std::vector<HeapChunk> &freedChunksSmall = heapAllocator->getFreedChunksSmall();
915 std::vector<HeapChunk> &freedChunksBig = heapAllocator->getFreedChunksBig();
916
917 uint64_t ptrs[10];
918 size_t sizes[10];
919
920 // size smaller than threshold
921 size_t sizeOfSmallAlloc = 2 * 4096;
922 uint64_t smallAlloc = 0llu;
923
924 for (uint32_t i = 0; i < 10; i++) {
925 sizes[i] = 4096;
926 ptrs[i] = heapAllocator->allocate(sizes[i]);
927 }
928
929 EXPECT_EQ(0u, freedChunksSmall.size());
930 EXPECT_EQ(0u, freedChunksBig.size());
931
932 // Release 8 chunks
933 for (uint32_t i = 0; i < 8; i++) {
934 heapAllocator->free(ptrs[i], sizes[i]);
935 }
936
937 // Allocate small chunk, should be taken from freed list
938 smallAlloc = heapAllocator->allocate(sizeOfSmallAlloc);
939
940 EXPECT_NE(0llu, smallAlloc);
941 EXPECT_LE(upperLimitPtr - (8 * 4096), smallAlloc);
942
943 EXPECT_EQ(1u, freedChunksSmall.size());
944
945 heapAllocator->free(smallAlloc, sizeOfSmallAlloc);
946
947 // It should not go to freedBig list
948 EXPECT_EQ(0u, freedChunksBig.size());
949
950 // It should merge to freedSmall chunk
951 EXPECT_EQ(1u, freedChunksSmall.size());
952
953 // Release last 2 allocs
954 for (uint32_t i = 8; i < 10; i++) {
955 heapAllocator->free(ptrs[i], sizes[i]);
956 }
957
958 // In the end both lists should be empty
959 EXPECT_EQ(0u, freedChunksSmall.size());
960 EXPECT_EQ(0u, freedChunksBig.size());
961 }
962
TEST(HeapAllocatorTest,Given10SmallAllocationsWhenMergedToBigAllocatedAsSmallNotSplittedAndReleasedThenItDoesNotGoToFreedBigChunksList)963 TEST(HeapAllocatorTest, Given10SmallAllocationsWhenMergedToBigAllocatedAsSmallNotSplittedAndReleasedThenItDoesNotGoToFreedBigChunksList) {
964 uint64_t ptrBase = 0llu;
965 uintptr_t basePtr = 0;
966
967 // Size for 10 small allocs plus one single 3 page plus some space
968 size_t size = (10 + 3 + 1) * 4096;
969 uint64_t upperLimitPtr = basePtr + size;
970
971 size_t threshold = 4 * 4096;
972
973 auto heapAllocator = std::make_unique<HeapAllocatorUnderTest>(ptrBase, size, allocationAlignment, threshold);
974
975 std::vector<HeapChunk> &freedChunksSmall = heapAllocator->getFreedChunksSmall();
976 std::vector<HeapChunk> &freedChunksBig = heapAllocator->getFreedChunksBig();
977
978 uint64_t ptrs[10];
979 size_t sizes[10];
980
981 // size smaller than threshold
982 size_t sizeOfSmallAlloc = 3 * 4096;
983 uint64_t smallAlloc = 0llu;
984
985 for (uint32_t i = 0; i < 10; i++) {
986 sizes[i] = 4096;
987 ptrs[i] = heapAllocator->allocate(sizes[i]);
988 }
989
990 EXPECT_EQ(0u, freedChunksSmall.size());
991 EXPECT_EQ(0u, freedChunksBig.size());
992
993 // Release 8 chunks
994 for (uint32_t i = 0; i < 5; i++) {
995 heapAllocator->free(ptrs[i], sizes[i]);
996 }
997
998 // Allocate small chunk, should be taken from freed list
999 smallAlloc = heapAllocator->allocate(sizeOfSmallAlloc);
1000
1001 EXPECT_NE(0llu, smallAlloc);
1002 EXPECT_LE(upperLimitPtr - (5 * 4096), smallAlloc);
1003
1004 EXPECT_EQ(0u, freedChunksSmall.size());
1005
1006 heapAllocator->free(smallAlloc, sizeOfSmallAlloc);
1007
1008 // It should not go to freedBig list
1009 EXPECT_EQ(0u, freedChunksBig.size());
1010
1011 // It should go to freedSmall chunk
1012 EXPECT_EQ(1u, freedChunksSmall.size());
1013
1014 // Release remaining allocs
1015 for (uint32_t i = 5; i < 10; i++) {
1016 heapAllocator->free(ptrs[i], sizes[i]);
1017 if (i < 9) {
1018 // chunks should be merged to freedSmall chunk on list
1019 EXPECT_EQ(1u, freedChunksSmall.size());
1020 }
1021 }
1022
1023 // In the end both lists should be empty
1024 EXPECT_EQ(0u, freedChunksSmall.size());
1025 EXPECT_EQ(0u, freedChunksBig.size());
1026 }
1027
TEST(HeapAllocatorTest,givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentFromLeftThenReturnAllocations)1028 TEST(HeapAllocatorTest, givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentFromLeftThenReturnAllocations) {
1029 const uint64_t heapBase = 0x100000llu;
1030 const size_t heapSize = 1024u * 4096u;
1031 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1032
1033 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1034 size_t ptrSize = 32 * MemoryConstants::pageSize;
1035 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1036 EXPECT_EQ(heapBase + heapSize, heapAllocator.getRightBound());
1037 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1038 EXPECT_EQ(32 * MemoryConstants::pageSize, ptrSize);
1039 EXPECT_EQ(heapBase, ptr);
1040 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1041
1042 ptrSize = 32 * MemoryConstants::pageSize;
1043 ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1044 EXPECT_EQ(heapBase + heapSize, heapAllocator.getRightBound());
1045 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1046 EXPECT_EQ(32 * MemoryConstants::pageSize, ptrSize);
1047 EXPECT_EQ(heapBase + ptrSize, ptr);
1048 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1049 }
1050
TEST(HeapAllocatorTest,givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentFromRightThenReturnAllocations)1051 TEST(HeapAllocatorTest, givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentFromRightThenReturnAllocations) {
1052 const uint64_t heapBase = 0x100000llu;
1053 const size_t heapSize = 1024u * 4096u;
1054 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1055
1056 const size_t customAlignment = 8 * MemoryConstants::pageSize;
1057 size_t ptrSize = 8 * MemoryConstants::pageSize;
1058 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1059 EXPECT_EQ(heapBase + heapSize - ptrSize, heapAllocator.getRightBound());
1060 EXPECT_EQ(heapBase, heapAllocator.getLeftBound());
1061 EXPECT_EQ(8 * MemoryConstants::pageSize, ptrSize);
1062 EXPECT_EQ(heapBase + heapSize - ptrSize, ptr);
1063 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1064 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1065
1066 ptrSize = 8 * MemoryConstants::pageSize;
1067 ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1068 EXPECT_EQ(heapBase + heapSize - 2 * ptrSize, heapAllocator.getRightBound());
1069 EXPECT_EQ(heapBase, heapAllocator.getLeftBound());
1070 EXPECT_EQ(8 * MemoryConstants::pageSize, ptrSize);
1071 EXPECT_EQ(heapBase + heapSize - 2 * ptrSize, ptr);
1072 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1073 EXPECT_EQ(heapSize - 2 * ptrSize, heapAllocator.getavailableSize());
1074 }
1075
TEST(HeapAllocatorTest,givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentBiggerThanPtrSizeFromRightThenReturnAllocations)1076 TEST(HeapAllocatorTest, givenAlignedBoundWhenAllocatingMemoryWithCustomAlignmentBiggerThanPtrSizeFromRightThenReturnAllocations) {
1077 const uint64_t heapBase = 0x100000llu;
1078 const size_t heapSize = 1024u * 4096u;
1079 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1080
1081 size_t customAlignment = 8 * MemoryConstants::pageSize;
1082 size_t ptrSize = 8 * MemoryConstants::pageSize;
1083 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1084 EXPECT_EQ(heapBase + heapSize - ptrSize, heapAllocator.getRightBound());
1085 EXPECT_EQ(heapBase, heapAllocator.getLeftBound());
1086 EXPECT_EQ(8 * MemoryConstants::pageSize, ptrSize);
1087 EXPECT_EQ(heapBase + heapSize - ptrSize, ptr);
1088 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1089 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1090
1091 ptrSize = 8 * MemoryConstants::pageSize;
1092 customAlignment = 32 * MemoryConstants::pageSize;
1093 ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1094 EXPECT_EQ(heapBase + heapSize - customAlignment, heapAllocator.getRightBound());
1095 EXPECT_EQ(heapBase, heapAllocator.getLeftBound());
1096 EXPECT_EQ(8 * MemoryConstants::pageSize, ptrSize);
1097 EXPECT_EQ(heapBase + heapSize - customAlignment, ptr);
1098 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1099 EXPECT_EQ(heapSize - 2 * ptrSize, heapAllocator.getavailableSize());
1100 }
1101
TEST(HeapAllocatorTest,givenUnalignedBoundWhenAllocatingWithCustomAlignmentFromLeftThenAlignBoundBeforeAllocation)1102 TEST(HeapAllocatorTest, givenUnalignedBoundWhenAllocatingWithCustomAlignmentFromLeftThenAlignBoundBeforeAllocation) {
1103 const uint64_t heapBase = 0x100000llu;
1104 const size_t heapSize = 1024u * 4096u;
1105 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, 0);
1106
1107 // Misalign the left bound
1108 const size_t misaligningAllocationSize = 2 * MemoryConstants::pageSize;
1109 size_t ptrSize = misaligningAllocationSize;
1110 uint64_t ptr = heapAllocator.allocate(ptrSize);
1111 EXPECT_EQ(heapBase, ptr);
1112 EXPECT_EQ(misaligningAllocationSize, ptrSize);
1113 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1114 EXPECT_EQ(heapSize - misaligningAllocationSize, heapAllocator.getavailableSize());
1115 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1116
1117 // Allocate with alignment
1118 const size_t customAlignment = 8 * MemoryConstants::pageSize;
1119 const size_t alignedAllocationSize = 16 * MemoryConstants::pageSize;
1120 ptrSize = alignedAllocationSize;
1121 ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1122 EXPECT_EQ(alignedAllocationSize, ptrSize);
1123 EXPECT_EQ(heapBase + customAlignment, ptr);
1124 EXPECT_EQ(heapBase + customAlignment + alignedAllocationSize, heapAllocator.getLeftBound());
1125 EXPECT_EQ(heapSize - misaligningAllocationSize - alignedAllocationSize, heapAllocator.getavailableSize());
1126 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1127
1128 // Try to use w hole, we just created by aligning
1129 const size_t additionalAllocationSize = customAlignment - misaligningAllocationSize;
1130 ptrSize = additionalAllocationSize;
1131 ptr = heapAllocator.allocate(ptrSize);
1132 EXPECT_EQ(heapBase + misaligningAllocationSize, ptr);
1133 EXPECT_EQ(additionalAllocationSize, ptrSize);
1134 EXPECT_EQ(heapBase + customAlignment + alignedAllocationSize, heapAllocator.getLeftBound());
1135 EXPECT_EQ(heapSize - customAlignment - alignedAllocationSize, heapAllocator.getavailableSize());
1136 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1137 }
1138
TEST(HeapAllocatorTest,givenUnalignedBoundWhenAllocatingWithCustomAlignmentFromRightThenAlignBoundBeforeAllocation)1139 TEST(HeapAllocatorTest, givenUnalignedBoundWhenAllocatingWithCustomAlignmentFromRightThenAlignBoundBeforeAllocation) {
1140 const uint64_t heapBase = 0x100000llu;
1141 const size_t heapSize = 1024u * 4096u;
1142 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, std::numeric_limits<size_t>::max());
1143
1144 // Misalign the right bound
1145 const size_t misaligningAllocationSize = 2 * MemoryConstants::pageSize;
1146 size_t ptrSize = misaligningAllocationSize;
1147 uint64_t ptr = heapAllocator.allocate(ptrSize);
1148 EXPECT_EQ(misaligningAllocationSize, ptrSize);
1149 EXPECT_EQ(heapBase + heapSize - misaligningAllocationSize, ptr);
1150 EXPECT_EQ(heapBase + heapSize - misaligningAllocationSize, heapAllocator.getRightBound());
1151 EXPECT_EQ(heapSize - misaligningAllocationSize, heapAllocator.getavailableSize());
1152 EXPECT_EQ(0u, heapAllocator.getFreedChunksSmall().size());
1153
1154 // Allocate with alignment
1155 const size_t customAlignment = 8 * MemoryConstants::pageSize;
1156 const size_t alignedAllocationSize = 16 * MemoryConstants::pageSize;
1157 ptrSize = alignedAllocationSize;
1158 ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1159 EXPECT_EQ(alignedAllocationSize, ptrSize);
1160 EXPECT_EQ(heapBase + heapSize - customAlignment - alignedAllocationSize, ptr);
1161 EXPECT_EQ(heapBase + heapSize - customAlignment - alignedAllocationSize, heapAllocator.getRightBound());
1162 EXPECT_EQ(heapSize - misaligningAllocationSize - alignedAllocationSize, heapAllocator.getavailableSize());
1163 EXPECT_EQ(1u, heapAllocator.getFreedChunksSmall().size());
1164
1165 // Try to use w hole, we just created by aligning
1166 const size_t additionalAllocationSize = customAlignment - misaligningAllocationSize;
1167 ptrSize = additionalAllocationSize;
1168 ptr = heapAllocator.allocate(ptrSize);
1169 EXPECT_EQ(heapBase + heapSize - customAlignment, ptr);
1170 EXPECT_EQ(additionalAllocationSize, ptrSize);
1171 EXPECT_EQ(heapBase + heapSize - customAlignment - alignedAllocationSize, heapAllocator.getRightBound());
1172 EXPECT_EQ(heapSize - customAlignment - alignedAllocationSize, heapAllocator.getavailableSize());
1173 EXPECT_EQ(0u, heapAllocator.getFreedChunksSmall().size());
1174 }
1175
TEST(HeapAllocatorTest,givenNoSpaceLeftWhenAllocatingWithCustomAlignmentFromLeftThenReturnZero)1176 TEST(HeapAllocatorTest, givenNoSpaceLeftWhenAllocatingWithCustomAlignmentFromLeftThenReturnZero) {
1177 const uint64_t heapBase = 0x100000llu;
1178 const size_t heapSize = 1024u * 4096u;
1179 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, 0);
1180
1181 const size_t customAlignment = 256 * MemoryConstants::pageSize;
1182 const size_t alignedAllocationSize = 256 * MemoryConstants::pageSize;
1183 size_t ptrSize = alignedAllocationSize;
1184
1185 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1186 EXPECT_EQ(heapBase + alignedAllocationSize, heapAllocator.getLeftBound());
1187
1188 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1189 EXPECT_EQ(heapBase + 2 * alignedAllocationSize, heapAllocator.getLeftBound());
1190
1191 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1192 EXPECT_EQ(heapBase + 3 * alignedAllocationSize, heapAllocator.getLeftBound());
1193
1194 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1195 EXPECT_EQ(heapBase + 4 * alignedAllocationSize, heapAllocator.getLeftBound());
1196
1197 EXPECT_EQ(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1198 EXPECT_EQ(heapBase + 4 * alignedAllocationSize, heapAllocator.getLeftBound());
1199 }
1200
TEST(HeapAllocatorTest,givenNoSpaceLeftWhenAllocatingWithCustomAlignmentFromRightThenReturnZero)1201 TEST(HeapAllocatorTest, givenNoSpaceLeftWhenAllocatingWithCustomAlignmentFromRightThenReturnZero) {
1202 const uint64_t heapBase = 0x100000llu;
1203 const size_t heapSize = 1024u * 4096u;
1204 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, std::numeric_limits<size_t>::max());
1205
1206 const size_t customAlignment = 256 * MemoryConstants::pageSize;
1207 const size_t alignedAllocationSize = 256 * MemoryConstants::pageSize;
1208 size_t ptrSize = alignedAllocationSize;
1209 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1210 EXPECT_EQ(heapBase + heapSize - alignedAllocationSize, heapAllocator.getRightBound());
1211
1212 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1213 EXPECT_EQ(heapBase + heapSize - 2 * alignedAllocationSize, heapAllocator.getRightBound());
1214
1215 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1216 EXPECT_EQ(heapBase + heapSize - 3 * alignedAllocationSize, heapAllocator.getRightBound());
1217
1218 EXPECT_NE(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1219 EXPECT_EQ(heapBase + heapSize - 4 * alignedAllocationSize, heapAllocator.getRightBound());
1220
1221 EXPECT_EQ(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment));
1222 EXPECT_EQ(heapBase + heapSize - 4 * alignedAllocationSize, heapAllocator.getRightBound());
1223 }
1224
TEST(HeapAllocatorTest,givenNoSpaceLeftAfterAligningWhenAllocatingWithCustomAlignmentFromLeftThenReturnZero)1225 TEST(HeapAllocatorTest, givenNoSpaceLeftAfterAligningWhenAllocatingWithCustomAlignmentFromLeftThenReturnZero) {
1226 const uint64_t heapBase = 0x100000llu;
1227 const size_t heapSize = 1024u * 4096u;
1228 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1229 const size_t alignedAllocationSize = 64 * MemoryConstants::pageSize;
1230
1231 // First create a state, where we have desired size free, but not aligned
1232 size_t ptrSize = 16 * MemoryConstants::pageSize;
1233 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1234 EXPECT_EQ(heapBase + heapSize - 16 * MemoryConstants::pageSize, heapAllocator.getRightBound());
1235 ptrSize = heapSize - alignedAllocationSize - ptrSize;
1236 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1237 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1238 EXPECT_EQ(alignedAllocationSize, heapAllocator.getavailableSize());
1239
1240 // Aligned allocation should fail
1241 ptrSize = alignedAllocationSize;
1242 EXPECT_EQ(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, ptrSize));
1243 EXPECT_EQ(alignedAllocationSize, heapAllocator.getavailableSize());
1244
1245 // Unaligned allocation can be done
1246 ptrSize = alignedAllocationSize;
1247 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1248 EXPECT_EQ(0ull, heapAllocator.getavailableSize());
1249 }
1250
TEST(HeapAllocatorTest,givenNoSpaceLeftAfterAligningWhenAllocatingWithCustomAlignmentFromRightThenReturnZero)1251 TEST(HeapAllocatorTest, givenNoSpaceLeftAfterAligningWhenAllocatingWithCustomAlignmentFromRightThenReturnZero) {
1252 const uint64_t heapBase = 0x100000llu;
1253 const size_t heapSize = 1024u * 4096u;
1254 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1255 const size_t alignedAllocationSize = 8 * MemoryConstants::pageSize;
1256
1257 // First create a state, where we have desired size free, but not aligned
1258 size_t ptrSize = 4 * MemoryConstants::pageSize;
1259 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1260 EXPECT_EQ(heapBase + heapSize - 4 * MemoryConstants::pageSize, heapAllocator.getRightBound());
1261 ptrSize = heapSize - alignedAllocationSize - ptrSize;
1262 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1263 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1264 EXPECT_EQ(alignedAllocationSize, heapAllocator.getavailableSize());
1265
1266 // Aligned allocation should fail
1267 ptrSize = alignedAllocationSize;
1268 EXPECT_EQ(0ull, heapAllocator.allocateWithCustomAlignment(ptrSize, ptrSize));
1269 EXPECT_EQ(alignedAllocationSize, heapAllocator.getavailableSize());
1270
1271 // Unaligned allocation can be done
1272 ptrSize = alignedAllocationSize;
1273 EXPECT_NE(0ull, heapAllocator.allocate(ptrSize));
1274 EXPECT_EQ(0ull, heapAllocator.getavailableSize());
1275 }
1276
TEST(HeapAllocatorTest,givenSizeNotAlignedToCustomAlignmentWhenAllocatingMemoryWithCustomAlignmentThenDoNotAlignToCustomAlignment)1277 TEST(HeapAllocatorTest, givenSizeNotAlignedToCustomAlignmentWhenAllocatingMemoryWithCustomAlignmentThenDoNotAlignToCustomAlignment) {
1278 const uint64_t heapBase = 0x100000llu;
1279 const size_t heapSize = 1024u * 4096u;
1280 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1281
1282 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1283 size_t ptrSize = 49 * MemoryConstants::pageSize;
1284 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1285 EXPECT_EQ(heapBase + heapSize, heapAllocator.getRightBound());
1286 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1287 EXPECT_EQ(49 * MemoryConstants::pageSize, ptrSize);
1288 EXPECT_EQ(heapBase, ptr);
1289 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1290 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1291 }
1292
TEST(HeapAllocatorTest,givenSizeNotAlignedToBaseAllocatorAlignmentWhenAllocatingMemoryWithCustomAlignmentThenDoNotAlignToBaseAlignment)1293 TEST(HeapAllocatorTest, givenSizeNotAlignedToBaseAllocatorAlignmentWhenAllocatingMemoryWithCustomAlignmentThenDoNotAlignToBaseAlignment) {
1294 const uint64_t heapBase = 0x100000llu;
1295 const size_t heapSize = 1024u * 4096u;
1296 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, 0);
1297
1298 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1299 size_t ptrSize = 1;
1300 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1301 EXPECT_EQ(heapBase + heapSize, heapAllocator.getRightBound());
1302 EXPECT_EQ(heapBase + ptrSize, heapAllocator.getLeftBound());
1303 EXPECT_EQ(MemoryConstants::pageSize, ptrSize);
1304 EXPECT_EQ(heapBase, ptr);
1305 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1306 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1307 }
1308
TEST(HeapAllocatorTest,givenAlignedFreedChunkAvailableWhenAllocatingMemoryWithCustomAlignmentFromLeftThenReturnUseFreedChunk)1309 TEST(HeapAllocatorTest, givenAlignedFreedChunkAvailableWhenAllocatingMemoryWithCustomAlignmentFromLeftThenReturnUseFreedChunk) {
1310 const uint64_t heapBase = 0x100000llu;
1311 const size_t heapSize = 1024u * 4096u;
1312 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1313
1314 // First create an aligned freed chunk
1315 size_t ptrSize = 32 * MemoryConstants::pageSize;
1316 const uint64_t freeChunkAddress = heapAllocator.allocate(ptrSize);
1317 heapAllocator.allocate(ptrSize);
1318 heapAllocator.free(freeChunkAddress, ptrSize);
1319 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1320 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1321 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1322
1323 // Allocate with custom alignment using the freed chunk
1324 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1325 ptrSize = 32 * MemoryConstants::pageSize;
1326 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1327 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1328 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1329 EXPECT_EQ(freeChunkAddress, ptr);
1330 EXPECT_EQ(heapSize - 2 * ptrSize, heapAllocator.getavailableSize());
1331 }
1332
TEST(HeapAllocatorTest,givenAlignedFreedChunkSlightlyBiggerThanAllocationeWhenAllocatingMemoryWithCustomAlignmentFromLeftThenUseEntireFreedChunk)1333 TEST(HeapAllocatorTest, givenAlignedFreedChunkSlightlyBiggerThanAllocationeWhenAllocatingMemoryWithCustomAlignmentFromLeftThenUseEntireFreedChunk) {
1334 const uint64_t heapBase = 0x100000llu;
1335 const size_t heapSize = 1024u * 4096u;
1336 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1337
1338 // First create an aligned freed chunk
1339 size_t ptrSize = 48 * MemoryConstants::pageSize;
1340 const uint64_t freeChunkAddress = heapAllocator.allocate(ptrSize);
1341 heapAllocator.allocate(ptrSize);
1342 heapAllocator.free(freeChunkAddress, ptrSize);
1343 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1344 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1345 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1346
1347 // Allocate with custom alignment using the freed chunk
1348 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1349 size_t ptrSize2 = 32 * MemoryConstants::pageSize;
1350 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize2, customAlignment);
1351 EXPECT_EQ(ptrSize, ptrSize2);
1352 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1353 EXPECT_EQ(0u, heapAllocator.getFreedChunksBig().size());
1354 EXPECT_EQ(freeChunkAddress, ptr);
1355 EXPECT_EQ(heapSize - 2 * ptrSize, heapAllocator.getavailableSize());
1356 }
1357
TEST(HeapAllocatorTest,givenAlignedFreedChunkTwoTimesBiggerThanAllocationeWhenAllocatingMemoryWithCustomAlignmentFromLeftThenUseAPortionOfTheFreedChunk)1358 TEST(HeapAllocatorTest, givenAlignedFreedChunkTwoTimesBiggerThanAllocationeWhenAllocatingMemoryWithCustomAlignmentFromLeftThenUseAPortionOfTheFreedChunk) {
1359 const uint64_t heapBase = 0x100000llu;
1360 const size_t heapSize = 1024u * 4096u;
1361 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, sizeThreshold);
1362
1363 // First create an aligned freed chunk
1364 size_t ptrSize = 64 * MemoryConstants::pageSize;
1365 const uint64_t freeChunkAddress = heapAllocator.allocate(ptrSize);
1366 heapAllocator.allocate(ptrSize);
1367 heapAllocator.free(freeChunkAddress, ptrSize);
1368 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1369 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1370 EXPECT_EQ(heapSize - ptrSize, heapAllocator.getavailableSize());
1371
1372 // Allocate with custom alignment using the freed chunk
1373 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1374 size_t ptrSize2 = 32 * MemoryConstants::pageSize;
1375 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize2, customAlignment);
1376 EXPECT_EQ(32 * MemoryConstants::pageSize, ptrSize2);
1377 EXPECT_EQ(heapBase + 2 * ptrSize, heapAllocator.getLeftBound());
1378 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1379 EXPECT_EQ(freeChunkAddress + 32 * MemoryConstants::pageSize, ptr);
1380 EXPECT_EQ(heapSize - ptrSize - ptrSize2, heapAllocator.getavailableSize());
1381 }
1382
TEST(HeapAllocatorTest,givenUnalignedFreedChunkAvailableWhenAllocatingMemoryWithCustomAlignmentFromLeftThenDoNotUseFreedChunk)1383 TEST(HeapAllocatorTest, givenUnalignedFreedChunkAvailableWhenAllocatingMemoryWithCustomAlignmentFromLeftThenDoNotUseFreedChunk) {
1384 const uint64_t heapBase = 0x100000llu;
1385 const size_t heapSize = 1024u * 4096u;
1386 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, 1);
1387
1388 // First create an unaligned freed chunk
1389 size_t ptrSize = MemoryConstants::pageSize;
1390 heapAllocator.allocate(ptrSize);
1391 ptrSize = 32 * MemoryConstants::pageSize;
1392 const uint64_t freeChunkAddress = heapAllocator.allocate(ptrSize);
1393 heapAllocator.allocate(ptrSize);
1394 heapAllocator.free(freeChunkAddress, ptrSize);
1395 EXPECT_EQ(heapBase + 65 * MemoryConstants::pageSize, heapAllocator.getLeftBound());
1396 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1397 EXPECT_EQ(heapSize - ptrSize - MemoryConstants::pageSize, heapAllocator.getavailableSize());
1398
1399 // Allocate with custom alignment, the freed chunk cannot be used
1400 const size_t customAlignment = 32 * MemoryConstants::pageSize;
1401 ptrSize = 32 * MemoryConstants::pageSize;
1402 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, customAlignment);
1403 EXPECT_EQ(heapBase + 128 * MemoryConstants::pageSize, heapAllocator.getLeftBound());
1404 EXPECT_EQ(heapBase + 96 * MemoryConstants::pageSize, ptr);
1405 EXPECT_EQ(2u, heapAllocator.getFreedChunksBig().size());
1406 EXPECT_EQ(heapSize - 2 * ptrSize - MemoryConstants::pageSize, heapAllocator.getavailableSize());
1407
1408 // Allocate without custom alignment, the freed chunk can be used
1409 ptrSize = 32 * MemoryConstants::pageSize;
1410 ptr = heapAllocator.allocate(ptrSize);
1411 EXPECT_EQ(heapBase + 128 * MemoryConstants::pageSize, heapAllocator.getLeftBound());
1412 EXPECT_EQ(freeChunkAddress, ptr);
1413 EXPECT_EQ(1u, heapAllocator.getFreedChunksBig().size());
1414 EXPECT_EQ(heapSize - 3 * ptrSize - MemoryConstants::pageSize, heapAllocator.getavailableSize());
1415 }
1416
TEST(HeapAllocatorTest,givenZeroAlignmentPassedWhenAllocatingMemoryWithCustomAlignmentThenUseDefaultAllocatorAlignment)1417 TEST(HeapAllocatorTest, givenZeroAlignmentPassedWhenAllocatingMemoryWithCustomAlignmentThenUseDefaultAllocatorAlignment) {
1418 const uint64_t heapBase = 0x111111llu;
1419 const size_t heapSize = 1024u * 4096u;
1420 HeapAllocatorUnderTest heapAllocator(heapBase, heapSize, allocationAlignment, 0);
1421
1422 size_t ptrSize = 1;
1423 uint64_t ptr = heapAllocator.allocateWithCustomAlignment(ptrSize, 0u);
1424 EXPECT_EQ(alignUp(heapBase, allocationAlignment), ptr);
1425 }
1426