blob: 77463830e9171085b94abdcb4728204417ea28cb [file] [log] [blame]
// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#include "pw_allocator/freelist_heap.h"
#include <span>
#include "gtest/gtest.h"
namespace pw::allocator {
TEST(FreeListHeap, CanAllocate) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr = allocator.Allocate(kAllocSize);
ASSERT_NE(ptr, nullptr);
// In this case, the allocator should be returning us the start of the chunk.
EXPECT_EQ(ptr, &buf[0] + sizeof(Block) + PW_ALLOCATOR_POISON_OFFSET);
}
TEST(FreeListHeap, AllocationsDontOverlap) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
void* ptr2 = allocator.Allocate(kAllocSize);
ASSERT_NE(ptr1, nullptr);
ASSERT_NE(ptr2, nullptr);
uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
uintptr_t ptr1_end = ptr1_start + kAllocSize;
uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
EXPECT_GT(ptr2_start, ptr1_end);
}
TEST(FreeListHeap, CanFreeAndRealloc) {
// There's not really a nice way to test that Free works, apart from to try
// and get that value back again.
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
allocator.Free(ptr1);
void* ptr2 = allocator.Allocate(kAllocSize);
EXPECT_EQ(ptr1, ptr2);
}
TEST(FreeListHeap, ReturnsNullWhenAllocationTooLarge) {
constexpr size_t N = 2048;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
EXPECT_EQ(allocator.Allocate(N), nullptr);
}
TEST(FreeListHeap, ReturnsNullWhenFull) {
constexpr size_t N = 2048;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
EXPECT_NE(
allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET),
nullptr);
EXPECT_EQ(allocator.Allocate(1), nullptr);
}
TEST(FreeListHeap, ReturnedPointersAreAligned) {
constexpr size_t N = 2048;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(1);
// Should be aligned to native pointer alignment
uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
size_t alignment = alignof(void*);
EXPECT_EQ(ptr1_start % alignment, static_cast<size_t>(0));
void* ptr2 = allocator.Allocate(1);
uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
EXPECT_EQ(ptr2_start % alignment, static_cast<size_t>(0));
}
#if defined(CHECK_TEST_CRASHES) && CHECK_TEST_CRASHES
// TODO(amontanez): Ensure that this test triggers an assert.
TEST(FreeListHeap, CannotFreeNonOwnedPointer) {
// This is a nasty one to test without looking at the internals of FreeList.
// We can cheat; create a heap, allocate it all, and try and return something
// random to it. Try allocating again, and check that we get nullptr back.
constexpr size_t N = 2048;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr =
allocator.Allocate(N - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
ASSERT_NE(ptr, nullptr);
// Free some random address past the end
allocator.Free(static_cast<std::byte*>(ptr) + N * 2);
void* ptr_ahead = allocator.Allocate(1);
EXPECT_EQ(ptr_ahead, nullptr);
// And try before
allocator.Free(static_cast<std::byte*>(ptr) - N);
void* ptr_before = allocator.Allocate(1);
EXPECT_EQ(ptr_before, nullptr);
}
#endif // CHECK_TEST_CRASHES
TEST(FreeListHeap, CanRealloc) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
constexpr size_t kNewAllocSize = 768;
std::byte buf[N] = {std::byte(1)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
ASSERT_NE(ptr1, nullptr);
ASSERT_NE(ptr2, nullptr);
}
TEST(FreeListHeap, ReallocHasSameContent) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = sizeof(int);
constexpr size_t kNewAllocSize = sizeof(int) * 2;
std::byte buf[N] = {std::byte(1)};
// Data inside the allocated block.
std::byte data1[kAllocSize];
// Data inside the reallocated block.
std::byte data2[kAllocSize];
FreeListHeapBuffer allocator(buf);
int* ptr1 = reinterpret_cast<int*>(allocator.Allocate(kAllocSize));
*ptr1 = 42;
memcpy(data1, ptr1, kAllocSize);
int* ptr2 = reinterpret_cast<int*>(allocator.Realloc(ptr1, kNewAllocSize));
memcpy(data2, ptr2, kAllocSize);
ASSERT_NE(ptr1, nullptr);
ASSERT_NE(ptr2, nullptr);
// Verify that data inside the allocated and reallocated chunks are the same.
EXPECT_EQ(std::memcmp(data1, data2, kAllocSize), 0);
}
TEST(FreeListHeap, ReturnsNullReallocFreedPointer) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
constexpr size_t kNewAllocSize = 256;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
allocator.Free(ptr1);
void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
EXPECT_EQ(nullptr, ptr2);
}
TEST(FreeListHeap, ReallocSmallerSize) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
constexpr size_t kNewAllocSize = 256;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
// For smaller sizes, Realloc will not shrink the block.
EXPECT_EQ(ptr1, ptr2);
}
TEST(FreeListHeap, ReallocTooLarge) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 512;
constexpr size_t kNewAllocSize = 4096;
std::byte buf[N] = {std::byte(0)};
FreeListHeapBuffer allocator(buf);
void* ptr1 = allocator.Allocate(kAllocSize);
void* ptr2 = allocator.Realloc(ptr1, kNewAllocSize);
// Realloc() will not invalidate the original pointer if Reallc() fails
EXPECT_NE(nullptr, ptr1);
EXPECT_EQ(nullptr, ptr2);
}
TEST(FreeListHeap, CanCalloc) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 128;
constexpr size_t kNum = 4;
constexpr int size = kNum * kAllocSize;
std::byte buf[N] = {std::byte(1)};
constexpr std::byte zero{0};
FreeListHeapBuffer allocator(buf);
std::byte* ptr1 =
reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
// Calloc'd content is zero.
for (int i = 0; i < size; i++) {
EXPECT_EQ(ptr1[i], zero);
}
}
TEST(FreeListHeap, CanCallocWeirdSize) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 143;
constexpr size_t kNum = 3;
constexpr int size = kNum * kAllocSize;
std::byte buf[N] = {std::byte(132)};
constexpr std::byte zero{0};
FreeListHeapBuffer allocator(buf);
std::byte* ptr1 =
reinterpret_cast<std::byte*>(allocator.Calloc(kNum, kAllocSize));
// Calloc'd content is zero.
for (int i = 0; i < size; i++) {
EXPECT_EQ(ptr1[i], zero);
}
}
TEST(FreeListHeap, CallocTooLarge) {
constexpr size_t N = 2048;
constexpr size_t kAllocSize = 2049;
std::byte buf[N] = {std::byte(1)};
FreeListHeapBuffer allocator(buf);
EXPECT_EQ(allocator.Calloc(1, kAllocSize), nullptr);
}
} // namespace pw::allocator