diff options
Diffstat (limited to 'deps/v8/test/unittests/heap/cppgc/free-list-unittest.cc')
-rw-r--r-- | deps/v8/test/unittests/heap/cppgc/free-list-unittest.cc | 187 |
1 files changed, 187 insertions, 0 deletions
diff --git a/deps/v8/test/unittests/heap/cppgc/free-list-unittest.cc b/deps/v8/test/unittests/heap/cppgc/free-list-unittest.cc new file mode 100644 index 00000000000..e059734cf94 --- /dev/null +++ b/deps/v8/test/unittests/heap/cppgc/free-list-unittest.cc @@ -0,0 +1,187 @@ +// Copyright 2020 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/heap/cppgc/free-list.h" + +#include <memory> +#include <numeric> +#include <vector> + +#include "src/base/bits.h" +#include "src/heap/cppgc/globals.h" +#include "src/heap/cppgc/heap-object-header.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace cppgc { +namespace internal { +namespace { + +class Block { + public: + Block() = default; + explicit Block(size_t size) : address_(calloc(1, size)), size_(size) {} + + Block(Block&& other) V8_NOEXCEPT : address_(other.address_), + size_(other.size_) { + other.address_ = nullptr; + other.size_ = 0; + } + + Block& operator=(Block&& other) V8_NOEXCEPT { + address_ = other.address_; + size_ = other.size_; + other.address_ = nullptr; + other.size_ = 0; + return *this; + } + + ~Block() { free(address_); } + + void* Address() const { return address_; } + size_t Size() const { return size_; } + + private: + void* address_ = nullptr; + size_t size_ = 0; +}; + +std::vector<Block> CreateEntries() { + static constexpr size_t kFreeListEntrySizeLog2 = + v8::base::bits::WhichPowerOfTwo(kFreeListEntrySize); + std::vector<Block> vector; + vector.reserve(kPageSizeLog2); + for (size_t i = kFreeListEntrySizeLog2; i < kPageSizeLog2; ++i) { + vector.emplace_back(static_cast<size_t>(1u) << i); + } + return vector; +} + +FreeList CreatePopulatedFreeList(const std::vector<Block>& blocks) { + FreeList list; + for (const auto& block : blocks) { + list.Add({block.Address(), block.Size()}); + } + return list; +} + +} // namespace + +TEST(FreeListTest, Empty) { + FreeList list; + EXPECT_TRUE(list.IsEmpty()); + EXPECT_EQ(0u, list.Size()); + + auto block = list.Allocate(16); + EXPECT_EQ(nullptr, block.address); + EXPECT_EQ(0u, block.size); +} + +TEST(FreeListTest, Add) { + auto blocks = CreateEntries(); + FreeList list = CreatePopulatedFreeList(blocks); + EXPECT_FALSE(list.IsEmpty()); + const size_t allocated_size = std::accumulate( + blocks.cbegin(), blocks.cend(), 0u, + [](size_t acc, const Block& b) { return acc + b.Size(); }); + EXPECT_EQ(allocated_size, list.Size()); +} + +TEST(FreeListTest, AddWasted) { + FreeList list; + alignas(HeapObjectHeader) uint8_t buffer[sizeof(HeapObjectHeader)]; + list.Add({buffer, sizeof(buffer)}); + EXPECT_EQ(0u, list.Size()); + EXPECT_TRUE(list.IsEmpty()); +} + +TEST(FreeListTest, Clear) { + auto blocks = CreateEntries(); + FreeList list = CreatePopulatedFreeList(blocks); + list.Clear(); + EXPECT_EQ(0u, list.Size()); + EXPECT_TRUE(list.IsEmpty()); +} + +TEST(FreeListTest, Move) { + { + auto blocks = CreateEntries(); + FreeList list1 = CreatePopulatedFreeList(blocks); + const size_t expected_size = list1.Size(); + FreeList list2 = std::move(list1); + EXPECT_EQ(expected_size, list2.Size()); + EXPECT_FALSE(list2.IsEmpty()); + EXPECT_EQ(0u, list1.Size()); + EXPECT_TRUE(list1.IsEmpty()); + } + { + auto blocks1 = CreateEntries(); + FreeList list1 = CreatePopulatedFreeList(blocks1); + const size_t expected_size = list1.Size(); + + auto blocks2 = CreateEntries(); + FreeList list2 = CreatePopulatedFreeList(blocks2); + + list2 = std::move(list1); + EXPECT_EQ(expected_size, list2.Size()); + EXPECT_FALSE(list2.IsEmpty()); + EXPECT_EQ(0u, list1.Size()); + EXPECT_TRUE(list1.IsEmpty()); + } +} + +TEST(FreeListTest, Append) { + auto blocks1 = CreateEntries(); + FreeList list1 = CreatePopulatedFreeList(blocks1); + const size_t list1_size = list1.Size(); + + auto blocks2 = CreateEntries(); + FreeList list2 = CreatePopulatedFreeList(blocks2); + const size_t list2_size = list1.Size(); + + list2.Append(std::move(list1)); + EXPECT_EQ(list1_size + list2_size, list2.Size()); + EXPECT_FALSE(list2.IsEmpty()); + EXPECT_EQ(0u, list1.Size()); + EXPECT_TRUE(list1.IsEmpty()); +} + +TEST(FreeListTest, Contains) { + auto blocks = CreateEntries(); + FreeList list = CreatePopulatedFreeList(blocks); + + for (const auto& block : blocks) { + EXPECT_TRUE(list.Contains({block.Address(), block.Size()})); + } +} + +TEST(FreeListTest, Allocate) { + static constexpr size_t kFreeListEntrySizeLog2 = + v8::base::bits::WhichPowerOfTwo(kFreeListEntrySize); + + std::vector<Block> blocks; + blocks.reserve(kPageSizeLog2); + for (size_t i = kFreeListEntrySizeLog2; i < kPageSizeLog2; ++i) { + blocks.emplace_back(static_cast<size_t>(1u) << i); + } + + FreeList list = CreatePopulatedFreeList(blocks); + + // Try allocate from the biggest block. + for (auto it = blocks.rbegin(); it < blocks.rend(); ++it) { + const auto result = list.Allocate(it->Size()); + EXPECT_EQ(it->Address(), result.address); + EXPECT_EQ(it->Size(), result.size); + } + + EXPECT_EQ(0u, list.Size()); + EXPECT_TRUE(list.IsEmpty()); + + // Check that allocation fails for empty list: + const auto empty_block = list.Allocate(8); + EXPECT_EQ(nullptr, empty_block.address); + EXPECT_EQ(0u, empty_block.size); +} + +} // namespace internal +} // namespace cppgc |