1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <cstddef> 17 #include <limits> 18 19 #include "pw_allocator/buffer.h" 20 #include "pw_allocator/bump_allocator.h" 21 #include "pw_unit_test/framework.h" 22 23 namespace pw::allocator::test { 24 25 /// Test fixture for testing Buckets. 26 /// 27 /// This class contains code both to set up a bucket and a number of free 28 /// blocks that can be stored in it, as well as unit test methods that apply to 29 /// all buckets. 30 template <typename BucketType> 31 class BucketTest : public ::testing::Test { 32 protected: 33 using BlockType = typename BucketType::BlockType; 34 using ItemType = typename BucketType::ItemType; 35 36 constexpr static size_t kMaxBlocks = 4; 37 static constexpr Layout kLayout1 = Layout(0x040, 1); 38 static constexpr Layout kLayout2 = Layout(0x080, 2); 39 static constexpr Layout kLayout3 = Layout(0x100, 4); 40 static constexpr Layout kLayout4 = Layout(0x200, 8); 41 constexpr static size_t kCapacity = kLayout4.size() * 4; 42 bucket()43 BucketType& bucket() { return bucket_; } 44 45 // Test fixtures. 46 SetUp()47 void SetUp() override { 48 auto result = BlockType::Init(bytes_); 49 PW_ASSERT(result.status() == pw::OkStatus()); 50 available_ = *result; 51 } 52 53 /// Returns a layout with the same alignment as the given `layout`, and a size 54 /// that is one less. ShrinkByOne(Layout layout)55 static constexpr Layout ShrinkByOne(Layout layout) { 56 return Layout(layout.size() - 1, layout.alignment()); 57 } 58 59 /// Creates a free block of the given inner size. 60 /// 61 /// This creates a free block that can be added to a bucket, and a guard 62 /// block that remains allocated to prevent the free blocks from merging. 63 /// It avoids using any block allocator, and the buckets those type may use. 64 /// Instead, it manages the blocks directly from a block representing the 65 /// remaining available memory. CreateBlock(Layout layout)66 BlockType& CreateBlock(Layout layout) { 67 auto result = BlockType::AllocFirst(std::move(available_), layout); 68 PW_ASSERT(result.status() == pw::OkStatus()); 69 BlockType* block = result.block(); 70 available_ = block->Next(); 71 72 result = BlockType::AllocFirst(std::move(available_), Layout(1, 1)); 73 PW_ASSERT(result.status() == pw::OkStatus()); 74 BlockType* guard = result.block(); 75 available_ = guard->Next(); 76 77 result = BlockType::Free(std::move(block)); 78 PW_ASSERT(result.ok()); 79 return *(result.block()); 80 } 81 82 /// Creates a free block of the given inner size, and adds it to the test 83 /// bucket. CreateBlockAndAddToBucket(Layout layout)84 BlockType& CreateBlockAndAddToBucket(Layout layout) { 85 BlockType& block = CreateBlock(layout); 86 PW_ASSERT(bucket_.Add(block)); 87 return block; 88 } 89 90 // Unit tests. SetsAndGetsMaxInnerSize()91 void SetsAndGetsMaxInnerSize() { 92 EXPECT_EQ(bucket_.max_inner_size(), std::numeric_limits<size_t>::max()); 93 bucket_.set_max_inner_size(kLayout1.size()); 94 EXPECT_EQ(bucket_.max_inner_size(), kLayout1.size()); 95 } 96 AddsAndRemovesBlocks()97 void AddsAndRemovesBlocks() { 98 BlockType& block1 = CreateBlockAndAddToBucket(kLayout1); 99 BlockType& block2 = CreateBlockAndAddToBucket(kLayout2); 100 BlockType& block3 = CreateBlockAndAddToBucket(kLayout3); 101 BlockType& block4 = CreateBlockAndAddToBucket(kLayout4); 102 EXPECT_TRUE(bucket_.Remove(block1)); 103 EXPECT_TRUE(bucket_.Remove(block2)); 104 EXPECT_TRUE(bucket_.Remove(block3)); 105 EXPECT_TRUE(bucket_.Remove(block4)); 106 EXPECT_TRUE(bucket_.empty()); 107 } 108 FailsToAddWhenBlockIsTooSmall()109 void FailsToAddWhenBlockIsTooSmall() { 110 // Create the smallest block possible. 111 BlockType& block = CreateBlock(Layout(1, 1)); 112 113 // Some allocators may not be able to create blocks with inner sizes smaller 114 // than the bucket's intrusive item type. 115 if (block.InnerSize() < sizeof(ItemType)) { 116 EXPECT_FALSE(bucket_.Add(block)); 117 } 118 } 119 FailsToRemoveBlockWhenNotFound()120 void FailsToRemoveBlockWhenNotFound() { 121 BlockType& block1 = CreateBlockAndAddToBucket(kLayout1); 122 BlockType& block2 = CreateBlockAndAddToBucket(kLayout2); 123 BlockType& block3 = CreateBlockAndAddToBucket(kLayout3); 124 BlockType& block4 = CreateBlockAndAddToBucket(kLayout4); 125 bucket_.Clear(); 126 EXPECT_FALSE(bucket_.Remove(block1)); 127 EXPECT_FALSE(bucket_.Remove(block2)); 128 EXPECT_FALSE(bucket_.Remove(block3)); 129 EXPECT_FALSE(bucket_.Remove(block4)); 130 } 131 RemovesUnspecifiedBlock()132 void RemovesUnspecifiedBlock() { 133 std::ignore = CreateBlockAndAddToBucket(kLayout1); 134 std::ignore = CreateBlockAndAddToBucket(kLayout2); 135 for (size_t i = 1; i <= 2; ++i) { 136 EXPECT_FALSE(bucket_.empty()); 137 EXPECT_NE(bucket_.RemoveAny(), nullptr); 138 } 139 EXPECT_TRUE(bucket_.empty()); 140 EXPECT_EQ(bucket_.RemoveAny(), nullptr); 141 } 142 RemovesByLayout()143 void RemovesByLayout() { 144 BlockType& block1 = CreateBlockAndAddToBucket(kLayout1); 145 BlockType& block2 = CreateBlockAndAddToBucket(kLayout2); 146 EXPECT_EQ(bucket_.RemoveCompatible(ShrinkByOne(kLayout2)), &block2); 147 EXPECT_FALSE(bucket_.empty()); 148 EXPECT_EQ(bucket_.RemoveCompatible(ShrinkByOne(kLayout1)), &block1); 149 EXPECT_TRUE(bucket_.empty()); 150 } 151 FailsToRemoveByExcessiveSize()152 void FailsToRemoveByExcessiveSize() { 153 std::ignore = CreateBlockAndAddToBucket(kLayout1); 154 std::ignore = CreateBlockAndAddToBucket(kLayout2); 155 EXPECT_EQ(bucket_.RemoveCompatible(kLayout3), nullptr); 156 EXPECT_FALSE(bucket_.empty()); 157 bucket_.Clear(); 158 } 159 160 private: 161 BucketType bucket_; 162 std::array<std::byte, kCapacity> bytes_; 163 std::array<BlockType*, kMaxBlocks> blocks_; 164 BlockType* available_ = nullptr; 165 }; 166 167 } // namespace pw::allocator::test 168