1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://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, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_allocator/freelist_heap.h"
16
17 #include "gtest/gtest.h"
18 #include "pw_span/span.h"
19
20 namespace pw::allocator {
21
TEST(FreeListHeap,CanAllocate)22 TEST(FreeListHeap, CanAllocate) {
23 constexpr size_t N = 2048;
24 constexpr size_t kAllocSize = 512;
25 alignas(Block) std::byte buf[N] = {std::byte(0)};
26
27 FreeListHeapBuffer allocator(buf);
28
29 void* ptr = allocator.Allocate(kAllocSize);
30
31 ASSERT_NE(ptr, nullptr);
32 // In this case, the allocator should be returning us the start of the chunk.
33 EXPECT_EQ(ptr, &buf[0] + sizeof(Block) + PW_ALLOCATOR_POISON_OFFSET);
34 }
35
TEST(FreeListHeap,AllocationsDontOverlap)36 TEST(FreeListHeap, AllocationsDontOverlap) {
37 constexpr size_t N = 2048;
38 constexpr size_t kAllocSize = 512;
39 alignas(Block) std::byte buf[N] = {std::byte(0)};
40
41 FreeListHeapBuffer allocator(buf);
42
43 void* ptr1 = allocator.Allocate(kAllocSize);
44 void* ptr2 = allocator.Allocate(kAllocSize);
45
46 ASSERT_NE(ptr1, nullptr);
47 ASSERT_NE(ptr2, nullptr);
48
49 uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
50 uintptr_t ptr1_end = ptr1_start + kAllocSize;
51 uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
52
53 EXPECT_GT(ptr2_start, ptr1_end);
54 }
55
TEST(FreeListHeap,CanFreeAndRealloc)56 TEST(FreeListHeap, CanFreeAndRealloc) {
57 // There's not really a nice way to test that Free works, apart from to try
58 // and get that value back again.
59 constexpr size_t N = 2048;
60 constexpr size_t kAllocSize = 512;
61 alignas(Block) std::byte buf[N] = {std::byte(0)};
62
63 FreeListHeapBuffer allocator(buf);
64
65 void* ptr1 = allocator.Allocate(kAllocSize);
66 allocator.Free(ptr1);
67 void* ptr2 = allocator.Allocate(kAllocSize);
68
69 EXPECT_EQ(ptr1, ptr2);
70 }
71
TEST(FreeListHeap,ReturnsNullWhenAllocationTooLarge)72 TEST(FreeListHeap, ReturnsNullWhenAllocationTooLarge) {
73 constexpr size_t N = 2048;
74 alignas(Block) std::byte buf[N] = {std::byte(0)};
75
76 FreeListHeapBuffer allocator(buf);
77
78 EXPECT_EQ(allocator.Allocate(N), nullptr);
79 }
80
TEST(FreeListHeap,ReturnsNullWhenFull)81 TEST(FreeListHeap, ReturnsNullWhenFull) {
82 constexpr size_t N = 2048;
83 alignas(Block) std::byte buf[N] = {std::byte(0)};
84
85 FreeListHeapBuffer allocator(buf);
86
87 EXPECT_NE(
88 allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET),
89 nullptr);
90 EXPECT_EQ(allocator.Allocate(1), nullptr);
91 }
92
TEST(FreeListHeap,ReturnedPointersAreAligned)93 TEST(FreeListHeap, ReturnedPointersAreAligned) {
94 constexpr size_t N = 2048;
95 alignas(Block) std::byte buf[N] = {std::byte(0)};
96
97 FreeListHeapBuffer allocator(buf);
98
99 void* ptr1 = allocator.Allocate(1);
100
101 // Should be aligned to native pointer alignment
102 uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
103 size_t alignment = alignof(void*);
104
105 EXPECT_EQ(ptr1_start % alignment, static_cast<size_t>(0));
106
107 void* ptr2 = allocator.Allocate(1);
108 uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
109
110 EXPECT_EQ(ptr2_start % alignment, static_cast<size_t>(0));
111 }
112
113 #if defined(CHECK_TEST_CRASHES) && CHECK_TEST_CRASHES
114
115 // TODO(amontanez): Ensure that this test triggers an assert.
TEST(FreeListHeap,CannotFreeNonOwnedPointer)116 TEST(FreeListHeap, CannotFreeNonOwnedPointer) {
117 // This is a nasty one to test without looking at the internals of FreeList.
118 // We can cheat; create a heap, allocate it all, and try and return something
119 // random to it. Try allocating again, and check that we get nullptr back.
120 constexpr size_t N = 2048;
121 alignas(Block) std::byte buf[N] = {std::byte(0)};
122
123 FreeListHeapBuffer allocator(buf);
124
125 void* ptr =
126 allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
127
128 ASSERT_NE(ptr, nullptr);
129
130 // Free some random address past the end
131 allocator.Free(static_cast<std::byte*>(ptr) + N * 2);
132
133 void* ptr_ahead = allocator.Allocate(1);
134 EXPECT_EQ(ptr_ahead, nullptr);
135
136 // And try before
137 allocator.Free(static_cast<std::byte*>(ptr) - N);
138
139 void* ptr_before = allocator.Allocate(1);
140 EXPECT_EQ(ptr_before, nullptr);
141 }
142 #endif // CHECK_TEST_CRASHES
143
TEST(FreeListHeap,CanRealloc)144 TEST(FreeListHeap, CanRealloc) {
145 constexpr size_t N = 2048;
146 constexpr size_t kAllocSize = 512;
147 constexpr size_t kNewAllocSize = 768;
148 alignas(Block) std::byte buf[N] = {std::byte(1)};
149
150 FreeListHeapBuffer allocator(buf);
151
152 void* ptr1 = allocator.Allocate(kAllocSize);
153 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
154
155 ASSERT_NE(ptr1, nullptr);
156 ASSERT_NE(ptr2, nullptr);
157 }
158
TEST(FreeListHeap,ReallocHasSameContent)159 TEST(FreeListHeap, ReallocHasSameContent) {
160 constexpr size_t N = 2048;
161 constexpr size_t kAllocSize = sizeof(int);
162 constexpr size_t kNewAllocSize = sizeof(int) * 2;
163 alignas(Block) std::byte buf[N] = {std::byte(1)};
164 // Data inside the allocated block.
165 std::byte data1[kAllocSize];
166 // Data inside the reallocated block.
167 std::byte data2[kAllocSize];
168
169 FreeListHeapBuffer allocator(buf);
170
171 int* ptr1 = reinterpret_cast<int*>(allocator.Allocate(kAllocSize));
172 *ptr1 = 42;
173 memcpy(data1, ptr1, kAllocSize);
174 int* ptr2 = reinterpret_cast<int*>(allocator.Realloc(ptr1, kNewAllocSize));
175 memcpy(data2, ptr2, kAllocSize);
176
177 ASSERT_NE(ptr1, nullptr);
178 ASSERT_NE(ptr2, nullptr);
179 // Verify that data inside the allocated and reallocated chunks are the same.
180 EXPECT_EQ(std::memcmp(data1, data2, kAllocSize), 0);
181 }
182
TEST(FreeListHeap,ReturnsNullReallocFreedPointer)183 TEST(FreeListHeap, ReturnsNullReallocFreedPointer) {
184 constexpr size_t N = 2048;
185 constexpr size_t kAllocSize = 512;
186 constexpr size_t kNewAllocSize = 256;
187 alignas(Block) std::byte buf[N] = {std::byte(0)};
188
189 FreeListHeapBuffer allocator(buf);
190
191 void* ptr1 = allocator.Allocate(kAllocSize);
192 allocator.Free(ptr1);
193 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
194
195 EXPECT_EQ(nullptr, ptr2);
196 }
197
TEST(FreeListHeap,ReallocSmallerSize)198 TEST(FreeListHeap, ReallocSmallerSize) {
199 constexpr size_t N = 2048;
200 constexpr size_t kAllocSize = 512;
201 constexpr size_t kNewAllocSize = 256;
202 alignas(Block) std::byte buf[N] = {std::byte(0)};
203
204 FreeListHeapBuffer allocator(buf);
205
206 void* ptr1 = allocator.Allocate(kAllocSize);
207 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
208
209 // For smaller sizes, Realloc will not shrink the block.
210 EXPECT_EQ(ptr1, ptr2);
211 }
212
TEST(FreeListHeap,ReallocTooLarge)213 TEST(FreeListHeap, ReallocTooLarge) {
214 constexpr size_t N = 2048;
215 constexpr size_t kAllocSize = 512;
216 constexpr size_t kNewAllocSize = 4096;
217 alignas(Block) std::byte buf[N] = {std::byte(0)};
218
219 FreeListHeapBuffer allocator(buf);
220
221 void* ptr1 = allocator.Allocate(kAllocSize);
222 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
223
224 // Realloc() will not invalidate the original pointer if Reallc() fails
225 EXPECT_NE(nullptr, ptr1);
226 EXPECT_EQ(nullptr, ptr2);
227 }
228
TEST(FreeListHeap,CanCalloc)229 TEST(FreeListHeap, CanCalloc) {
230 constexpr size_t N = 2048;
231 constexpr size_t kAllocSize = 128;
232 constexpr size_t kNum = 4;
233 constexpr int size = kNum * kAllocSize;
234 alignas(Block) std::byte buf[N] = {std::byte(1)};
235 constexpr std::byte zero{0};
236
237 FreeListHeapBuffer allocator(buf);
238
239 std::byte* ptr1 =
240 reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
241
242 // Calloc'd content is zero.
243 for (int i = 0; i < size; i++) {
244 EXPECT_EQ(ptr1[i], zero);
245 }
246 }
247
TEST(FreeListHeap,CanCallocWeirdSize)248 TEST(FreeListHeap, CanCallocWeirdSize) {
249 constexpr size_t N = 2048;
250 constexpr size_t kAllocSize = 143;
251 constexpr size_t kNum = 3;
252 constexpr int size = kNum * kAllocSize;
253 alignas(Block) std::byte buf[N] = {std::byte(132)};
254 constexpr std::byte zero{0};
255
256 FreeListHeapBuffer allocator(buf);
257
258 std::byte* ptr1 =
259 reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
260
261 // Calloc'd content is zero.
262 for (int i = 0; i < size; i++) {
263 EXPECT_EQ(ptr1[i], zero);
264 }
265 }
266
TEST(FreeListHeap,CallocTooLarge)267 TEST(FreeListHeap, CallocTooLarge) {
268 constexpr size_t N = 2048;
269 constexpr size_t kAllocSize = 2049;
270 alignas(Block) std::byte buf[N] = {std::byte(1)};
271
272 FreeListHeapBuffer allocator(buf);
273
274 EXPECT_EQ(allocator.Calloc(1, kAllocSize), nullptr);
275 }
276 } // namespace pw::allocator
277