110 lines · cpp
1//===-- Unittests for a freestore -------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include <stddef.h>10 11#include "src/__support/freestore.h"12#include "test/UnitTest/Test.h"13 14using LIBC_NAMESPACE::Block;15using LIBC_NAMESPACE::FreeList;16using LIBC_NAMESPACE::FreeStore;17using LIBC_NAMESPACE::FreeTrie;18using LIBC_NAMESPACE::cpp::byte;19using LIBC_NAMESPACE::cpp::optional;20 21// Inserting or removing blocks too small to be tracked does nothing.22TEST(LlvmLibcFreeStore, TooSmall) {23 byte mem[1024];24 optional<Block *> maybeBlock = Block::init(mem);25 ASSERT_TRUE(maybeBlock.has_value());26 Block *too_small = *maybeBlock;27 maybeBlock = too_small->split(Block::PREV_FIELD_SIZE);28 ASSERT_TRUE(maybeBlock.has_value());29 // On platforms with high alignment the smallest legal block may be large30 // enough for a node.31 if (too_small->outer_size() >= sizeof(Block) + sizeof(FreeList::Node))32 return;33 Block *remainder = *maybeBlock;34 35 FreeStore store;36 store.set_range({0, 4096});37 store.insert(too_small);38 store.insert(remainder);39 40 EXPECT_EQ(store.remove_best_fit(too_small->inner_size()), remainder);41 store.remove(too_small);42}43 44TEST(LlvmLibcFreeStore, RemoveBestFit) {45 byte mem[1024];46 optional<Block *> maybeBlock = Block::init(mem);47 ASSERT_TRUE(maybeBlock.has_value());48 49 Block *smallest = *maybeBlock;50 maybeBlock = smallest->split(sizeof(FreeList::Node) + Block::PREV_FIELD_SIZE);51 ASSERT_TRUE(maybeBlock.has_value());52 53 Block *largest_small = *maybeBlock;54 maybeBlock = largest_small->split(55 sizeof(FreeTrie::Node) + Block::PREV_FIELD_SIZE - alignof(max_align_t));56 ASSERT_TRUE(maybeBlock.has_value());57 if (largest_small->inner_size() == smallest->inner_size())58 largest_small = smallest;59 ASSERT_GE(largest_small->inner_size(), smallest->inner_size());60 61 Block *remainder = *maybeBlock;62 63 FreeStore store;64 store.set_range({0, 4096});65 store.insert(smallest);66 if (largest_small != smallest)67 store.insert(largest_small);68 store.insert(remainder);69 70 // Find exact match for smallest.71 ASSERT_EQ(store.remove_best_fit(smallest->inner_size()), smallest);72 store.insert(smallest);73 74 // Find exact match for largest.75 ASSERT_EQ(store.remove_best_fit(largest_small->inner_size()), largest_small);76 store.insert(largest_small);77 78 // Search small list for best fit.79 Block *next_smallest = largest_small == smallest ? remainder : largest_small;80 ASSERT_EQ(store.remove_best_fit(smallest->inner_size() + 1), next_smallest);81 store.insert(next_smallest);82 83 // Continue search for best fit to large blocks.84 EXPECT_EQ(store.remove_best_fit(largest_small->inner_size() + 1), remainder);85}86 87TEST(LlvmLibcFreeStore, Remove) {88 byte mem[1024];89 optional<Block *> maybeBlock = Block::init(mem);90 ASSERT_TRUE(maybeBlock.has_value());91 92 Block *small = *maybeBlock;93 maybeBlock = small->split(sizeof(FreeList::Node) + Block::PREV_FIELD_SIZE);94 ASSERT_TRUE(maybeBlock.has_value());95 96 Block *remainder = *maybeBlock;97 98 FreeStore store;99 store.set_range({0, 4096});100 store.insert(small);101 store.insert(remainder);102 103 store.remove(remainder);104 ASSERT_EQ(store.remove_best_fit(remainder->inner_size()),105 static_cast<Block *>(nullptr));106 store.remove(small);107 ASSERT_EQ(store.remove_best_fit(small->inner_size()),108 static_cast<Block *>(nullptr));109}110