From 9be475af81ee36f1d360ad1d70b695c4b26c98fa Mon Sep 17 00:00:00 2001 From: Daniel Thornburgh Date: Wed, 20 Nov 2024 14:00:07 -0800 Subject: Revert "[libc] Use best-fit binary trie to make malloc logarithmic" (#117065) Reverts llvm/llvm-project#106259 Unit tests break on AArch64. --- libc/test/src/__support/freelist_test.cpp | 185 ++++++++++++++++++++++++------ 1 file changed, 150 insertions(+), 35 deletions(-) (limited to 'libc/test/src/__support/freelist_test.cpp') diff --git a/libc/test/src/__support/freelist_test.cpp b/libc/test/src/__support/freelist_test.cpp index f8bde941df09..cae0ed470315 100644 --- a/libc/test/src/__support/freelist_test.cpp +++ b/libc/test/src/__support/freelist_test.cpp @@ -8,44 +8,159 @@ #include +#include "src/__support/CPP/array.h" +#include "src/__support/CPP/span.h" #include "src/__support/freelist.h" #include "test/UnitTest/Test.h" -using LIBC_NAMESPACE::Block; using LIBC_NAMESPACE::FreeList; +using LIBC_NAMESPACE::cpp::array; using LIBC_NAMESPACE::cpp::byte; -using LIBC_NAMESPACE::cpp::optional; - -TEST(LlvmLibcFreeList, FreeList) { - byte mem1[1024]; - optional *> maybeBlock = Block<>::init(mem1); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *block1 = *maybeBlock; - - byte mem2[1024]; - maybeBlock = Block<>::init(mem2); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *block2 = *maybeBlock; - - FreeList list; - list.push(block1); - ASSERT_FALSE(list.empty()); - EXPECT_EQ(list.front(), block1); - - list.push(block2); - EXPECT_EQ(list.front(), block1); - - list.pop(); - ASSERT_FALSE(list.empty()); - EXPECT_EQ(list.front(), block2); - - list.pop(); - ASSERT_TRUE(list.empty()); - - list.push(block1); - list.push(block2); - list.remove(reinterpret_cast(block2->usable_space())); - EXPECT_EQ(list.front(), block1); - list.pop(); - ASSERT_TRUE(list.empty()); +using LIBC_NAMESPACE::cpp::span; + +static constexpr size_t SIZE = 8; +static constexpr array example_sizes = {64, 128, 256, 512, + 1024, 2048, 4096, 8192}; + +TEST(LlvmLibcFreeList, EmptyListHasNoMembers) { + FreeList list(example_sizes); + + auto item = list.find_chunk(4); + EXPECT_EQ(item.size(), static_cast(0)); + item = list.find_chunk(128); + EXPECT_EQ(item.size(), static_cast(0)); +} + +TEST(LlvmLibcFreeList, CanRetrieveAddedMember) { + FreeList list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + bool ok = list.add_chunk(span(data, N)); + EXPECT_TRUE(ok); + + auto item = list.find_chunk(N); + EXPECT_EQ(item.size(), N); + EXPECT_EQ(item.data(), data); +} + +TEST(LlvmLibcFreeList, CanRetrieveAddedMemberForSmallerSize) { + FreeList list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span(data, N))); + auto item = list.find_chunk(N / 2); + EXPECT_EQ(item.size(), N); + EXPECT_EQ(item.data(), data); +} + +TEST(LlvmLibcFreeList, CanRemoveItem) { + FreeList list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span(data, N))); + EXPECT_TRUE(list.remove_chunk(span(data, N))); + + auto item = list.find_chunk(N); + EXPECT_EQ(item.size(), static_cast(0)); +} + +TEST(LlvmLibcFreeList, FindReturnsSmallestChunk) { + FreeList list(example_sizes); + constexpr size_t kN1 = 512; + constexpr size_t kN2 = 1024; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span(data2, kN2))); + + auto chunk = list.find_chunk(kN1 / 2); + EXPECT_EQ(chunk.size(), kN1); + EXPECT_EQ(chunk.data(), data1); + + chunk = list.find_chunk(kN1); + EXPECT_EQ(chunk.size(), kN1); + EXPECT_EQ(chunk.data(), data1); + + chunk = list.find_chunk(kN1 + 1); + EXPECT_EQ(chunk.size(), kN2); + EXPECT_EQ(chunk.data(), data2); +} + +TEST(LlvmLibcFreeList, FindReturnsCorrectChunkInSameBucket) { + // If we have two values in the same bucket, ensure that the allocation will + // pick an appropriately sized one. + FreeList list(example_sizes); + constexpr size_t kN1 = 512; + constexpr size_t kN2 = 257; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + // List should now be 257 -> 512 -> NULL + ASSERT_TRUE(list.add_chunk(span(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span(data2, kN2))); + + auto chunk = list.find_chunk(kN2 + 1); + EXPECT_EQ(chunk.size(), kN1); +} + +TEST(LlvmLibcFreeList, FindCanMoveUpThroughBuckets) { + // Ensure that finding a chunk will move up through buckets if no appropriate + // chunks were found in a given bucket + FreeList list(example_sizes); + constexpr size_t kN1 = 257; + constexpr size_t kN2 = 513; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + // List should now be: + // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL + // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL + ASSERT_TRUE(list.add_chunk(span(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span(data2, kN2))); + + // Request a 300 byte chunk. This should return the 513 byte one + auto chunk = list.find_chunk(kN1 + 1); + EXPECT_EQ(chunk.size(), kN2); +} + +TEST(LlvmLibcFreeList, RemoveUnknownChunkReturnsNotFound) { + FreeList list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + byte data2[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span(data, N))); + EXPECT_FALSE(list.remove_chunk(span(data2, N))); +} + +TEST(LlvmLibcFreeList, CanStoreMultipleChunksPerBucket) { + FreeList list(example_sizes); + constexpr size_t N = 512; + + byte data1[N] = {byte(0)}; + byte data2[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span(data1, N))); + ASSERT_TRUE(list.add_chunk(span(data2, N))); + + auto chunk1 = list.find_chunk(N); + ASSERT_TRUE(list.remove_chunk(chunk1)); + auto chunk2 = list.find_chunk(N); + ASSERT_TRUE(list.remove_chunk(chunk2)); + + // Ordering of the chunks doesn't matter + EXPECT_TRUE(chunk1.data() != chunk2.data()); + EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2); + EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2); } -- cgit v1.2.3