Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 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 | |
Wyatt Hepler | e2cbadf | 2020-06-22 11:21:45 -0700 | [diff] [blame] | 17 | #include <span> |
| 18 | |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 19 | #include "gtest/gtest.h" |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 20 | |
| 21 | namespace pw::allocator { |
| 22 | |
| 23 | TEST(FreeListHeap, CanAllocate) { |
| 24 | constexpr size_t N = 2048; |
| 25 | constexpr size_t kAllocSize = 512; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 26 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 27 | |
| 28 | FreeListHeapBuffer allocator(buf); |
| 29 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 30 | void* ptr = allocator.Allocate(kAllocSize); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 31 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 32 | ASSERT_NE(ptr, nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 33 | // In this case, the allocator should be returning us the start of the chunk. |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 34 | EXPECT_EQ(ptr, &buf[0] + sizeof(Block) + PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 35 | } |
| 36 | |
| 37 | TEST(FreeListHeap, AllocationsDontOverlap) { |
| 38 | constexpr size_t N = 2048; |
| 39 | constexpr size_t kAllocSize = 512; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 40 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 41 | |
| 42 | FreeListHeapBuffer allocator(buf); |
| 43 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 44 | void* ptr1 = allocator.Allocate(kAllocSize); |
| 45 | void* ptr2 = allocator.Allocate(kAllocSize); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 46 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 47 | ASSERT_NE(ptr1, nullptr); |
| 48 | ASSERT_NE(ptr2, nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 49 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 53 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 54 | EXPECT_GT(ptr2_start, ptr1_end); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 55 | } |
| 56 | |
| 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; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 62 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 63 | |
| 64 | FreeListHeapBuffer allocator(buf); |
| 65 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 66 | void* ptr1 = allocator.Allocate(kAllocSize); |
| 67 | allocator.Free(ptr1); |
| 68 | void* ptr2 = allocator.Allocate(kAllocSize); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 69 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 70 | EXPECT_EQ(ptr1, ptr2); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 71 | } |
| 72 | |
| 73 | TEST(FreeListHeap, ReturnsNullWhenAllocationTooLarge) { |
| 74 | constexpr size_t N = 2048; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 75 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 76 | |
| 77 | FreeListHeapBuffer allocator(buf); |
| 78 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 79 | EXPECT_EQ(allocator.Allocate(N), nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 80 | } |
| 81 | |
| 82 | TEST(FreeListHeap, ReturnsNullWhenFull) { |
| 83 | constexpr size_t N = 2048; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 84 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 85 | |
| 86 | FreeListHeapBuffer allocator(buf); |
| 87 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 88 | EXPECT_NE( |
| 89 | allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET), |
| 90 | nullptr); |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 91 | EXPECT_EQ(allocator.Allocate(1), nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 92 | } |
| 93 | |
| 94 | TEST(FreeListHeap, ReturnedPointersAreAligned) { |
| 95 | constexpr size_t N = 2048; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 96 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 97 | |
| 98 | FreeListHeapBuffer allocator(buf); |
| 99 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 100 | void* ptr1 = allocator.Allocate(1); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 101 | |
| 102 | // Should be aligned to native pointer alignment |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 103 | uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 104 | size_t alignment = alignof(void*); |
| 105 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 106 | EXPECT_EQ(ptr1_start % alignment, static_cast<size_t>(0)); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 107 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 108 | void* ptr2 = allocator.Allocate(1); |
| 109 | uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 110 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 111 | EXPECT_EQ(ptr2_start % alignment, static_cast<size_t>(0)); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 112 | } |
| 113 | |
Ewout van Bekkum | e4d7b69 | 2020-10-15 13:12:30 -0700 | [diff] [blame] | 114 | #if defined(CHECK_TEST_CRASHES) && CHECK_TEST_CRASHES |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 115 | |
| 116 | // TODO(amontanez): Ensure that this test triggers an assert. |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 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; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 122 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 123 | |
| 124 | FreeListHeapBuffer allocator(buf); |
| 125 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 126 | void* ptr = |
| 127 | allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 128 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 129 | ASSERT_NE(ptr, nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 130 | |
| 131 | // Free some random address past the end |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 132 | allocator.Free(static_cast<std::byte*>(ptr) + N * 2); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 133 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 134 | void* ptr_ahead = allocator.Allocate(1); |
| 135 | EXPECT_EQ(ptr_ahead, nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 136 | |
| 137 | // And try before |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 138 | allocator.Free(static_cast<std::byte*>(ptr) - N); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 139 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 140 | void* ptr_before = allocator.Allocate(1); |
| 141 | EXPECT_EQ(ptr_before, nullptr); |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 142 | } |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 143 | #endif // CHECK_TEST_CRASHES |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 144 | |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 145 | TEST(FreeListHeap, CanRealloc) { |
| 146 | constexpr size_t N = 2048; |
| 147 | constexpr size_t kAllocSize = 512; |
| 148 | constexpr size_t kNewAllocSize = 768; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 149 | alignas(Block) std::byte buf[N] = {std::byte(1)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 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; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 164 | alignas(Block) std::byte buf[N] = {std::byte(1)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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. |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 181 | EXPECT_EQ(std::memcmp(data1, data2, kAllocSize), 0); |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 182 | } |
| 183 | |
| 184 | TEST(FreeListHeap, ReturnsNullReallocFreedPointer) { |
| 185 | constexpr size_t N = 2048; |
| 186 | constexpr size_t kAllocSize = 512; |
| 187 | constexpr size_t kNewAllocSize = 256; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 188 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 199 | TEST(FreeListHeap, ReallocSmallerSize) { |
| 200 | constexpr size_t N = 2048; |
| 201 | constexpr size_t kAllocSize = 512; |
| 202 | constexpr size_t kNewAllocSize = 256; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 203 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 214 | TEST(FreeListHeap, ReallocTooLarge) { |
| 215 | constexpr size_t N = 2048; |
| 216 | constexpr size_t kAllocSize = 512; |
| 217 | constexpr size_t kNewAllocSize = 4096; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 218 | alignas(Block) std::byte buf[N] = {std::byte(0)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 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; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 235 | alignas(Block) std::byte buf[N] = {std::byte(1)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 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; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 254 | alignas(Block) std::byte buf[N] = {std::byte(132)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 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 | |
| 268 | TEST(FreeListHeap, CallocTooLarge) { |
| 269 | constexpr size_t N = 2048; |
| 270 | constexpr size_t kAllocSize = 2049; |
Armando Montanez | 28f8218 | 2021-02-05 17:10:43 -0800 | [diff] [blame] | 271 | alignas(Block) std::byte buf[N] = {std::byte(1)}; |
Chenghan | 0ac0275 | 2020-06-01 13:02:04 -0400 | [diff] [blame] | 272 | |
| 273 | FreeListHeapBuffer allocator(buf); |
| 274 | |
| 275 | EXPECT_EQ(allocator.Calloc(1, kAllocSize), nullptr); |
| 276 | } |
Jamie Garside | f65bb9c | 2020-04-02 11:17:20 +0100 | [diff] [blame] | 277 | } // namespace pw::allocator |