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