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 "pw_span/span.h"
18 #include "pw_unit_test/framework.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(FreeListHeap::BlockType) 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] + FreeListHeap::BlockType::kBlockOverhead);
34 }
35
TEST(FreeListHeap,AllocationsDontOverlap)36 TEST(FreeListHeap, AllocationsDontOverlap) {
37 constexpr size_t N = 2048;
38 constexpr size_t kAllocSize = 512;
39 alignas(FreeListHeap::BlockType) 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(FreeListHeap::BlockType) 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(FreeListHeap::BlockType) 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(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
84
85 FreeListHeapBuffer allocator(buf);
86
87 EXPECT_NE(allocator.Allocate(N - FreeListHeap::BlockType::kBlockOverhead),
88 nullptr);
89 EXPECT_EQ(allocator.Allocate(1), nullptr);
90 }
91
TEST(FreeListHeap,ReturnedPointersAreAligned)92 TEST(FreeListHeap, ReturnedPointersAreAligned) {
93 constexpr size_t N = 2048;
94 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
95
96 FreeListHeapBuffer allocator(buf);
97
98 void* ptr1 = allocator.Allocate(1);
99
100 // Should be aligned to native pointer alignment
101 uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
102 size_t alignment = alignof(void*);
103
104 EXPECT_EQ(ptr1_start % alignment, static_cast<size_t>(0));
105
106 void* ptr2 = allocator.Allocate(1);
107 uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
108
109 EXPECT_EQ(ptr2_start % alignment, static_cast<size_t>(0));
110 }
111
112 #if defined(CHECK_TEST_CRASHES) && CHECK_TEST_CRASHES
113
114 // TODO(amontanez): Ensure that this test triggers an assert.
TEST(FreeListHeap,CannotFreeNonOwnedPointer)115 TEST(FreeListHeap, CannotFreeNonOwnedPointer) {
116 // This is a nasty one to test without looking at the internals of FreeList.
117 // We can cheat; create a heap, allocate it all, and try and return something
118 // random to it. Try allocating again, and check that we get nullptr back.
119 constexpr size_t N = 2048;
120 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
121
122 FreeListHeapBuffer allocator(buf);
123
124 void* ptr =
125 allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
126
127 ASSERT_NE(ptr, nullptr);
128
129 // Free some random address past the end
130 allocator.Free(static_cast<std::byte*>(ptr) + N * 2);
131
132 void* ptr_ahead = allocator.Allocate(1);
133 EXPECT_EQ(ptr_ahead, nullptr);
134
135 // And try before
136 allocator.Free(static_cast<std::byte*>(ptr) - N);
137
138 void* ptr_before = allocator.Allocate(1);
139 EXPECT_EQ(ptr_before, nullptr);
140 }
141 #endif // CHECK_TEST_CRASHES
142
TEST(FreeListHeap,CanRealloc)143 TEST(FreeListHeap, CanRealloc) {
144 constexpr size_t N = 2048;
145 constexpr size_t kAllocSize = 512;
146 constexpr size_t kNewAllocSize = 768;
147 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(1)};
148
149 FreeListHeapBuffer allocator(buf);
150
151 void* ptr1 = allocator.Allocate(kAllocSize);
152 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
153
154 ASSERT_NE(ptr1, nullptr);
155 ASSERT_NE(ptr2, nullptr);
156 }
157
TEST(FreeListHeap,ReallocHasSameContent)158 TEST(FreeListHeap, ReallocHasSameContent) {
159 constexpr size_t N = 2048;
160 constexpr size_t kAllocSize = sizeof(int);
161 constexpr size_t kNewAllocSize = sizeof(int) * 2;
162 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(1)};
163 // Data inside the allocated block.
164 std::byte data1[kAllocSize];
165 // Data inside the reallocated block.
166 std::byte data2[kAllocSize];
167
168 FreeListHeapBuffer allocator(buf);
169
170 int* ptr1 = reinterpret_cast<int*>(allocator.Allocate(kAllocSize));
171 *ptr1 = 42;
172 memcpy(data1, ptr1, kAllocSize);
173 int* ptr2 = reinterpret_cast<int*>(allocator.Realloc(ptr1, kNewAllocSize));
174 memcpy(data2, ptr2, kAllocSize);
175
176 ASSERT_NE(ptr1, nullptr);
177 ASSERT_NE(ptr2, nullptr);
178 // Verify that data inside the allocated and reallocated chunks are the same.
179 EXPECT_EQ(std::memcmp(data1, data2, kAllocSize), 0);
180 }
181
TEST(FreeListHeap,ReturnsNullReallocFreedPointer)182 TEST(FreeListHeap, ReturnsNullReallocFreedPointer) {
183 constexpr size_t N = 2048;
184 constexpr size_t kAllocSize = 512;
185 constexpr size_t kNewAllocSize = 256;
186 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
187
188 FreeListHeapBuffer allocator(buf);
189
190 void* ptr1 = allocator.Allocate(kAllocSize);
191 allocator.Free(ptr1);
192 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
193
194 EXPECT_EQ(nullptr, ptr2);
195 }
196
TEST(FreeListHeap,ReallocSmallerSize)197 TEST(FreeListHeap, ReallocSmallerSize) {
198 constexpr size_t N = 2048;
199 constexpr size_t kAllocSize = 512;
200 constexpr size_t kNewAllocSize = 256;
201 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
202
203 FreeListHeapBuffer allocator(buf);
204
205 void* ptr1 = allocator.Allocate(kAllocSize);
206 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
207
208 // For smaller sizes, Realloc will not shrink the block.
209 EXPECT_EQ(ptr1, ptr2);
210 }
211
TEST(FreeListHeap,ReallocTooLarge)212 TEST(FreeListHeap, ReallocTooLarge) {
213 constexpr size_t N = 2048;
214 constexpr size_t kAllocSize = 512;
215 constexpr size_t kNewAllocSize = 4096;
216 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(0)};
217
218 FreeListHeapBuffer allocator(buf);
219
220 void* ptr1 = allocator.Allocate(kAllocSize);
221 void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
222
223 // Realloc() will not invalidate the original pointer if Reallc() fails
224 EXPECT_NE(nullptr, ptr1);
225 EXPECT_EQ(nullptr, ptr2);
226 }
227
TEST(FreeListHeap,CanCalloc)228 TEST(FreeListHeap, CanCalloc) {
229 constexpr size_t N = 2048;
230 constexpr size_t kAllocSize = 128;
231 constexpr size_t kNum = 4;
232 constexpr int size = kNum * kAllocSize;
233 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(1)};
234 constexpr std::byte zero{0};
235
236 FreeListHeapBuffer allocator(buf);
237
238 std::byte* ptr1 =
239 reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
240
241 // Calloc'd content is zero.
242 for (int i = 0; i < size; i++) {
243 EXPECT_EQ(ptr1[i], zero);
244 }
245 }
246
TEST(FreeListHeap,CanCallocWeirdSize)247 TEST(FreeListHeap, CanCallocWeirdSize) {
248 constexpr size_t N = 2048;
249 constexpr size_t kAllocSize = 143;
250 constexpr size_t kNum = 3;
251 constexpr int size = kNum * kAllocSize;
252 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(132)};
253 constexpr std::byte zero{0};
254
255 FreeListHeapBuffer allocator(buf);
256
257 std::byte* ptr1 =
258 reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
259
260 // Calloc'd content is zero.
261 for (int i = 0; i < size; i++) {
262 EXPECT_EQ(ptr1[i], zero);
263 }
264 }
265
TEST(FreeListHeap,CallocTooLarge)266 TEST(FreeListHeap, CallocTooLarge) {
267 constexpr size_t N = 2048;
268 constexpr size_t kAllocSize = 2049;
269 alignas(FreeListHeap::BlockType) std::byte buf[N] = {std::byte(1)};
270
271 FreeListHeapBuffer allocator(buf);
272
273 EXPECT_EQ(allocator.Calloc(1, kAllocSize), nullptr);
274 }
275 } // namespace pw::allocator
276