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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include <stddef.h> 10 11 #include "src/__support/freestore.h" 12 #include "test/UnitTest/Test.h" 13 14 using LIBC_NAMESPACE::Block; 15 using LIBC_NAMESPACE::FreeList; 16 using LIBC_NAMESPACE::FreeStore; 17 using LIBC_NAMESPACE::FreeTrie; 18 using LIBC_NAMESPACE::cpp::byte; 19 using LIBC_NAMESPACE::cpp::optional; 20 21 // Inserting or removing blocks too small to be tracked does nothing. 22 TEST(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 large 30 // 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 44 TEST(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 87 TEST(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