Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 1 | // Copyright 2020 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 | |
| 15 | #include "pw_allocator/block.h" |
| 16 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 17 | #include <cstring> |
Wyatt Hepler | e2cbadf | 2020-06-22 11:21:45 -0700 | [diff] [blame] | 18 | #include <span> |
| 19 | |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 20 | #include "gtest/gtest.h" |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 21 | |
| 22 | using std::byte; |
| 23 | |
| 24 | namespace pw::allocator { |
| 25 | |
| 26 | TEST(Block, CanCreateSingleBlock) { |
| 27 | constexpr size_t kN = 200; |
| 28 | alignas(Block*) byte bytes[kN]; |
| 29 | |
| 30 | Block* block = nullptr; |
Wyatt Hepler | e2cbadf | 2020-06-22 11:21:45 -0700 | [diff] [blame] | 31 | auto status = Block::Init(std::span(bytes, kN), &block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 32 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 33 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 34 | EXPECT_EQ(block->OuterSize(), kN); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 35 | EXPECT_EQ(block->InnerSize(), |
| 36 | kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
| 37 | EXPECT_EQ(block->Prev(), nullptr); |
| 38 | EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN)); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 39 | EXPECT_EQ(block->Used(), false); |
| 40 | EXPECT_EQ(block->Last(), true); |
| 41 | } |
| 42 | |
| 43 | TEST(Block, CannotCreateUnalignedSingleBlock) { |
| 44 | constexpr size_t kN = 1024; |
| 45 | |
| 46 | // Force alignment, so we can un-force it below |
| 47 | alignas(Block*) byte bytes[kN]; |
| 48 | byte* byte_ptr = bytes; |
| 49 | |
| 50 | Block* block = nullptr; |
Wyatt Hepler | e2cbadf | 2020-06-22 11:21:45 -0700 | [diff] [blame] | 51 | auto status = Block::Init(std::span(byte_ptr + 1, kN - 1), &block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 52 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 53 | EXPECT_EQ(status, Status::InvalidArgument()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 54 | } |
| 55 | |
| 56 | TEST(Block, CannotCreateTooSmallBlock) { |
| 57 | constexpr size_t kN = 2; |
| 58 | alignas(Block*) byte bytes[kN]; |
| 59 | Block* block = nullptr; |
Wyatt Hepler | e2cbadf | 2020-06-22 11:21:45 -0700 | [diff] [blame] | 60 | auto status = Block::Init(std::span(bytes, kN), &block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 61 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 62 | EXPECT_EQ(status, Status::InvalidArgument()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 63 | } |
| 64 | |
| 65 | TEST(Block, CanSplitBlock) { |
| 66 | constexpr size_t kN = 1024; |
| 67 | constexpr size_t kSplitN = 512; |
| 68 | alignas(Block*) byte bytes[kN]; |
| 69 | |
| 70 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 71 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 72 | |
| 73 | Block* next_block = nullptr; |
| 74 | auto status = block->Split(kSplitN, &next_block); |
| 75 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 76 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 77 | EXPECT_EQ(block->InnerSize(), kSplitN); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 78 | EXPECT_EQ(block->OuterSize(), |
| 79 | kSplitN + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 80 | EXPECT_EQ(block->Last(), false); |
| 81 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 82 | EXPECT_EQ(next_block->OuterSize(), |
| 83 | kN - kSplitN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 84 | EXPECT_EQ(next_block->Used(), false); |
| 85 | EXPECT_EQ(next_block->Last(), true); |
| 86 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 87 | EXPECT_EQ(block->Next(), next_block); |
| 88 | EXPECT_EQ(next_block->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 89 | } |
| 90 | |
| 91 | TEST(Block, CanSplitBlockUnaligned) { |
| 92 | constexpr size_t kN = 1024; |
| 93 | constexpr size_t kSplitN = 513; |
| 94 | |
| 95 | alignas(Block*) byte bytes[kN]; |
| 96 | |
| 97 | // We should split at sizeof(Block) + kSplitN bytes. Then |
| 98 | // we need to round that up to an alignof(Block*) boundary. |
| 99 | uintptr_t split_addr = ((uintptr_t)&bytes) + kSplitN; |
| 100 | split_addr += alignof(Block*) - (split_addr % alignof(Block*)); |
| 101 | uintptr_t split_len = split_addr - (uintptr_t)&bytes; |
| 102 | |
| 103 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 104 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 105 | |
| 106 | Block* next_block = nullptr; |
| 107 | auto status = block->Split(kSplitN, &next_block); |
| 108 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 109 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 110 | EXPECT_EQ(block->InnerSize(), split_len); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 111 | EXPECT_EQ(block->OuterSize(), |
| 112 | split_len + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET); |
| 113 | EXPECT_EQ(next_block->OuterSize(), |
| 114 | kN - split_len - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 115 | EXPECT_EQ(next_block->Used(), false); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 116 | EXPECT_EQ(block->Next(), next_block); |
| 117 | EXPECT_EQ(next_block->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 118 | } |
| 119 | |
| 120 | TEST(Block, CanSplitMidBlock) { |
| 121 | // Split once, then split the original block again to ensure that the |
| 122 | // pointers get rewired properly. |
| 123 | // I.e. |
| 124 | // [[ BLOCK 1 ]] |
| 125 | // block1->Split() |
| 126 | // [[ BLOCK1 ]][[ BLOCK2 ]] |
| 127 | // block1->Split() |
| 128 | // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]] |
| 129 | |
| 130 | constexpr size_t kN = 1024; |
| 131 | constexpr size_t kSplit1 = 512; |
| 132 | constexpr size_t kSplit2 = 256; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 133 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 134 | |
| 135 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 136 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 137 | |
| 138 | Block* block2 = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 139 | block->Split(kSplit1, &block2) |
| 140 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 141 | |
| 142 | Block* block3 = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 143 | block->Split(kSplit2, &block3) |
| 144 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 145 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 146 | EXPECT_EQ(block->Next(), block3); |
| 147 | EXPECT_EQ(block3->Next(), block2); |
| 148 | EXPECT_EQ(block2->Prev(), block3); |
| 149 | EXPECT_EQ(block3->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 150 | } |
| 151 | |
| 152 | TEST(Block, CannotSplitBlockWithoutHeaderSpace) { |
| 153 | constexpr size_t kN = 1024; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 154 | constexpr size_t kSplitN = |
| 155 | kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET - 1; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 156 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 157 | |
| 158 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 159 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 160 | |
| 161 | Block* next_block = nullptr; |
| 162 | auto status = block->Split(kSplitN, &next_block); |
| 163 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 164 | EXPECT_EQ(status, Status::ResourceExhausted()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 165 | EXPECT_EQ(next_block, nullptr); |
| 166 | } |
| 167 | |
| 168 | TEST(Block, MustProvideNextBlockPointer) { |
| 169 | constexpr size_t kN = 1024; |
| 170 | constexpr size_t kSplitN = kN - sizeof(Block) - 1; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 171 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 172 | |
| 173 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 174 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 175 | |
| 176 | auto status = block->Split(kSplitN, nullptr); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 177 | EXPECT_EQ(status, Status::InvalidArgument()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 178 | } |
| 179 | |
| 180 | TEST(Block, CannotMakeBlockLargerInSplit) { |
| 181 | // Ensure that we can't ask for more space than the block actually has... |
| 182 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 183 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 184 | |
| 185 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 186 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 187 | |
| 188 | Block* next_block = nullptr; |
| 189 | auto status = block->Split(block->InnerSize() + 1, &next_block); |
| 190 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 191 | EXPECT_EQ(status, Status::OutOfRange()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 192 | } |
| 193 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 194 | TEST(Block, CannotMakeSecondBlockLargerInSplit) { |
| 195 | // Ensure that the second block in split is at least of the size of header. |
| 196 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 197 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 198 | |
| 199 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 200 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 201 | |
| 202 | Block* next_block = nullptr; |
| 203 | auto status = block->Split( |
| 204 | block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET + 1, |
| 205 | &next_block); |
| 206 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 207 | ASSERT_EQ(status, Status::ResourceExhausted()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 208 | EXPECT_EQ(next_block, nullptr); |
| 209 | } |
| 210 | |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 211 | TEST(Block, CanMakeZeroSizeFirstBlock) { |
| 212 | // This block does support splitting with zero payload size. |
| 213 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 214 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 215 | |
| 216 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 217 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 218 | |
| 219 | Block* next_block = nullptr; |
| 220 | auto status = block->Split(0, &next_block); |
| 221 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 222 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 223 | EXPECT_EQ(block->InnerSize(), static_cast<size_t>(0)); |
| 224 | } |
| 225 | |
| 226 | TEST(Block, CanMakeZeroSizeSecondBlock) { |
| 227 | // Likewise, the split block can be zero-width. |
| 228 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 229 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 230 | |
| 231 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 232 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 233 | |
| 234 | Block* next_block = nullptr; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 235 | auto status = block->Split( |
| 236 | block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET, |
| 237 | &next_block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 238 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 239 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 240 | EXPECT_EQ(next_block->InnerSize(), static_cast<size_t>(0)); |
| 241 | } |
| 242 | |
| 243 | TEST(Block, CanMarkBlockUsed) { |
| 244 | constexpr size_t kN = 1024; |
| 245 | alignas(Block*) byte bytes[kN]; |
| 246 | |
| 247 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 248 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 249 | |
| 250 | block->MarkUsed(); |
| 251 | EXPECT_EQ(block->Used(), true); |
| 252 | |
| 253 | // Mark used packs that data into the next pointer. Check that it's still |
| 254 | // valid |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 255 | EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN)); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 256 | |
| 257 | block->MarkFree(); |
| 258 | EXPECT_EQ(block->Used(), false); |
| 259 | } |
| 260 | |
| 261 | TEST(Block, CannotSplitUsedBlock) { |
| 262 | constexpr size_t kN = 1024; |
| 263 | alignas(Block*) byte bytes[kN]; |
| 264 | |
| 265 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 266 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 267 | |
| 268 | block->MarkUsed(); |
| 269 | |
| 270 | Block* next_block = nullptr; |
| 271 | auto status = block->Split(512, &next_block); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 272 | EXPECT_EQ(status, Status::FailedPrecondition()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | TEST(Block, CanMergeWithNextBlock) { |
| 276 | // Do the three way merge from "CanSplitMidBlock", and let's |
| 277 | // merge block 3 and 2 |
| 278 | constexpr size_t kN = 1024; |
| 279 | constexpr size_t kSplit1 = 512; |
| 280 | constexpr size_t kSplit2 = 256; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 281 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 282 | |
| 283 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 284 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 285 | |
| 286 | Block* block2 = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 287 | block->Split(kSplit1, &block2) |
| 288 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 289 | |
| 290 | Block* block3 = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 291 | block->Split(kSplit2, &block3) |
| 292 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 293 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 294 | EXPECT_EQ(block3->MergeNext(), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 295 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 296 | EXPECT_EQ(block->Next(), block3); |
| 297 | EXPECT_EQ(block3->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 298 | EXPECT_EQ(block->InnerSize(), kSplit2); |
| 299 | |
| 300 | // The resulting "right hand" block should have an outer size of 1024 - 256 - |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 301 | // sizeof(Block) - 2*PW_ALLOCATOR_POISON_OFFSET, which accounts for the first |
| 302 | // block. |
| 303 | EXPECT_EQ(block3->OuterSize(), |
| 304 | kN - kSplit2 - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 305 | } |
| 306 | |
| 307 | TEST(Block, CannotMergeWithFirstOrLastBlock) { |
| 308 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 309 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 310 | |
Rob Mohr | de9cc1b | 2021-05-21 15:58:44 -0700 | [diff] [blame] | 311 | // Do a split, just to check that the checks on Next/Prev are |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 312 | // different... |
| 313 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 314 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 315 | |
| 316 | Block* next_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 317 | block->Split(512, &next_block) |
| 318 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 319 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 320 | EXPECT_EQ(next_block->MergeNext(), Status::OutOfRange()); |
| 321 | EXPECT_EQ(block->MergePrev(), Status::OutOfRange()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 322 | } |
| 323 | |
| 324 | TEST(Block, CannotMergeUsedBlock) { |
| 325 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 326 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 327 | |
Rob Mohr | de9cc1b | 2021-05-21 15:58:44 -0700 | [diff] [blame] | 328 | // Do a split, just to check that the checks on Next/Prev are |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 329 | // different... |
| 330 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 331 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 332 | |
| 333 | Block* next_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 334 | block->Split(512, &next_block) |
| 335 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 336 | |
| 337 | block->MarkUsed(); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 338 | EXPECT_EQ(block->MergeNext(), Status::FailedPrecondition()); |
| 339 | EXPECT_EQ(next_block->MergePrev(), Status::FailedPrecondition()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 340 | } |
| 341 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 342 | TEST(Block, CanCheckValidBlock) { |
| 343 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 344 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 345 | |
| 346 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 347 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 348 | |
| 349 | Block* second_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 350 | first_block->Split(512, &second_block) |
| 351 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 352 | |
| 353 | Block* third_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 354 | second_block->Split(256, &third_block) |
| 355 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 356 | |
| 357 | EXPECT_EQ(first_block->IsValid(), true); |
| 358 | EXPECT_EQ(second_block->IsValid(), true); |
| 359 | EXPECT_EQ(third_block->IsValid(), true); |
| 360 | } |
| 361 | |
| 362 | TEST(Block, CanCheckInalidBlock) { |
| 363 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 364 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 365 | |
| 366 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 367 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 368 | |
| 369 | Block* second_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 370 | first_block->Split(512, &second_block) |
| 371 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 372 | |
| 373 | Block* third_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 374 | second_block->Split(256, &third_block) |
| 375 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 376 | |
| 377 | Block* fourth_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 378 | third_block->Split(128, &fourth_block) |
| 379 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 380 | |
| 381 | std::byte* next_ptr = reinterpret_cast<std::byte*>(first_block); |
| 382 | memcpy(next_ptr, second_block, sizeof(void*)); |
| 383 | EXPECT_EQ(first_block->IsValid(), false); |
| 384 | EXPECT_EQ(second_block->IsValid(), false); |
| 385 | EXPECT_EQ(third_block->IsValid(), true); |
| 386 | EXPECT_EQ(fourth_block->IsValid(), true); |
| 387 | |
Ewout van Bekkum | e4d7b69 | 2020-10-15 13:12:30 -0700 | [diff] [blame] | 388 | #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 389 | std::byte fault_poison[PW_ALLOCATOR_POISON_OFFSET] = {std::byte(0)}; |
| 390 | std::byte* front_poison = |
| 391 | reinterpret_cast<std::byte*>(third_block) + sizeof(*third_block); |
| 392 | memcpy(front_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET); |
| 393 | EXPECT_EQ(third_block->IsValid(), false); |
| 394 | |
| 395 | std::byte* end_poison = |
| 396 | reinterpret_cast<std::byte*>(fourth_block) + sizeof(*fourth_block); |
| 397 | memcpy(end_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET); |
| 398 | EXPECT_EQ(fourth_block->IsValid(), false); |
| 399 | #endif // PW_ALLOCATOR_POISON_ENABLE |
| 400 | } |
| 401 | |
| 402 | TEST(Block, CanPoisonBlock) { |
Ewout van Bekkum | e4d7b69 | 2020-10-15 13:12:30 -0700 | [diff] [blame] | 403 | #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 404 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 405 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 406 | |
| 407 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 408 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 409 | |
| 410 | Block* second_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 411 | first_block->Split(512, &second_block) |
| 412 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 413 | |
| 414 | Block* third_block = nullptr; |
Adrien Larbanet | d1ca56c | 2021-06-10 14:20:45 +0000 | [diff] [blame] | 415 | second_block->Split(256, &third_block) |
| 416 | .IgnoreError(); // TODO(pwbug/387): Handle Status properly |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 417 | |
| 418 | EXPECT_EQ(first_block->IsValid(), true); |
| 419 | EXPECT_EQ(second_block->IsValid(), true); |
| 420 | EXPECT_EQ(third_block->IsValid(), true); |
| 421 | #endif // PW_ALLOCATOR_POISON_ENABLE |
| 422 | } |
| 423 | |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 424 | } // namespace pw::allocator |