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; |
| 139 | block->Split(kSplit1, &block2); |
| 140 | |
| 141 | Block* block3 = nullptr; |
| 142 | block->Split(kSplit2, &block3); |
| 143 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 144 | EXPECT_EQ(block->Next(), block3); |
| 145 | EXPECT_EQ(block3->Next(), block2); |
| 146 | EXPECT_EQ(block2->Prev(), block3); |
| 147 | EXPECT_EQ(block3->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 148 | } |
| 149 | |
| 150 | TEST(Block, CannotSplitBlockWithoutHeaderSpace) { |
| 151 | constexpr size_t kN = 1024; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 152 | constexpr size_t kSplitN = |
| 153 | kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET - 1; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 154 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 155 | |
| 156 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 157 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 158 | |
| 159 | Block* next_block = nullptr; |
| 160 | auto status = block->Split(kSplitN, &next_block); |
| 161 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 162 | EXPECT_EQ(status, Status::ResourceExhausted()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 163 | EXPECT_EQ(next_block, nullptr); |
| 164 | } |
| 165 | |
| 166 | TEST(Block, MustProvideNextBlockPointer) { |
| 167 | constexpr size_t kN = 1024; |
| 168 | constexpr size_t kSplitN = kN - sizeof(Block) - 1; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 169 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 170 | |
| 171 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 172 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 173 | |
| 174 | auto status = block->Split(kSplitN, nullptr); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 175 | EXPECT_EQ(status, Status::InvalidArgument()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | TEST(Block, CannotMakeBlockLargerInSplit) { |
| 179 | // Ensure that we can't ask for more space than the block actually has... |
| 180 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 181 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 182 | |
| 183 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 184 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 185 | |
| 186 | Block* next_block = nullptr; |
| 187 | auto status = block->Split(block->InnerSize() + 1, &next_block); |
| 188 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 189 | EXPECT_EQ(status, Status::OutOfRange()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 190 | } |
| 191 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 192 | TEST(Block, CannotMakeSecondBlockLargerInSplit) { |
| 193 | // Ensure that the second block in split is at least of the size of header. |
| 194 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 195 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 196 | |
| 197 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 198 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 199 | |
| 200 | Block* next_block = nullptr; |
| 201 | auto status = block->Split( |
| 202 | block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET + 1, |
| 203 | &next_block); |
| 204 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 205 | ASSERT_EQ(status, Status::ResourceExhausted()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 206 | EXPECT_EQ(next_block, nullptr); |
| 207 | } |
| 208 | |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 209 | TEST(Block, CanMakeZeroSizeFirstBlock) { |
| 210 | // This block does support splitting with zero payload size. |
| 211 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 212 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 213 | |
| 214 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 215 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 216 | |
| 217 | Block* next_block = nullptr; |
| 218 | auto status = block->Split(0, &next_block); |
| 219 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 220 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 221 | EXPECT_EQ(block->InnerSize(), static_cast<size_t>(0)); |
| 222 | } |
| 223 | |
| 224 | TEST(Block, CanMakeZeroSizeSecondBlock) { |
| 225 | // Likewise, the split block can be zero-width. |
| 226 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 227 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 228 | |
| 229 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 230 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 231 | |
| 232 | Block* next_block = nullptr; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 233 | auto status = block->Split( |
| 234 | block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET, |
| 235 | &next_block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 236 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 237 | ASSERT_EQ(status, OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 238 | EXPECT_EQ(next_block->InnerSize(), static_cast<size_t>(0)); |
| 239 | } |
| 240 | |
| 241 | TEST(Block, CanMarkBlockUsed) { |
| 242 | constexpr size_t kN = 1024; |
| 243 | alignas(Block*) byte bytes[kN]; |
| 244 | |
| 245 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 246 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 247 | |
| 248 | block->MarkUsed(); |
| 249 | EXPECT_EQ(block->Used(), true); |
| 250 | |
| 251 | // Mark used packs that data into the next pointer. Check that it's still |
| 252 | // valid |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 253 | EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN)); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 254 | |
| 255 | block->MarkFree(); |
| 256 | EXPECT_EQ(block->Used(), false); |
| 257 | } |
| 258 | |
| 259 | TEST(Block, CannotSplitUsedBlock) { |
| 260 | constexpr size_t kN = 1024; |
| 261 | alignas(Block*) byte bytes[kN]; |
| 262 | |
| 263 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 264 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 265 | |
| 266 | block->MarkUsed(); |
| 267 | |
| 268 | Block* next_block = nullptr; |
| 269 | auto status = block->Split(512, &next_block); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 270 | EXPECT_EQ(status, Status::FailedPrecondition()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 271 | } |
| 272 | |
| 273 | TEST(Block, CanMergeWithNextBlock) { |
| 274 | // Do the three way merge from "CanSplitMidBlock", and let's |
| 275 | // merge block 3 and 2 |
| 276 | constexpr size_t kN = 1024; |
| 277 | constexpr size_t kSplit1 = 512; |
| 278 | constexpr size_t kSplit2 = 256; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 279 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 280 | |
| 281 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 282 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 283 | |
| 284 | Block* block2 = nullptr; |
| 285 | block->Split(kSplit1, &block2); |
| 286 | |
| 287 | Block* block3 = nullptr; |
| 288 | block->Split(kSplit2, &block3); |
| 289 | |
Wyatt Hepler | 1b3da3a | 2021-01-07 13:26:57 -0800 | [diff] [blame] | 290 | EXPECT_EQ(block3->MergeNext(), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 291 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 292 | EXPECT_EQ(block->Next(), block3); |
| 293 | EXPECT_EQ(block3->Prev(), block); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 294 | EXPECT_EQ(block->InnerSize(), kSplit2); |
| 295 | |
| 296 | // 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] | 297 | // sizeof(Block) - 2*PW_ALLOCATOR_POISON_OFFSET, which accounts for the first |
| 298 | // block. |
| 299 | EXPECT_EQ(block3->OuterSize(), |
| 300 | kN - kSplit2 - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 301 | } |
| 302 | |
| 303 | TEST(Block, CannotMergeWithFirstOrLastBlock) { |
| 304 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 305 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 306 | |
| 307 | // Do a split, just to sanity check that the checks on Next/Prev are |
| 308 | // different... |
| 309 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 310 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 311 | |
| 312 | Block* next_block = nullptr; |
| 313 | block->Split(512, &next_block); |
| 314 | |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 315 | EXPECT_EQ(next_block->MergeNext(), Status::OutOfRange()); |
| 316 | EXPECT_EQ(block->MergePrev(), Status::OutOfRange()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 317 | } |
| 318 | |
| 319 | TEST(Block, CannotMergeUsedBlock) { |
| 320 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 321 | alignas(Block*) byte bytes[kN]; |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 322 | |
| 323 | // Do a split, just to sanity check that the checks on Next/Prev are |
| 324 | // different... |
| 325 | Block* block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 326 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 327 | |
| 328 | Block* next_block = nullptr; |
| 329 | block->Split(512, &next_block); |
| 330 | |
| 331 | block->MarkUsed(); |
Wyatt Hepler | d78f7c6 | 2020-09-28 14:27:32 -0700 | [diff] [blame] | 332 | EXPECT_EQ(block->MergeNext(), Status::FailedPrecondition()); |
| 333 | EXPECT_EQ(next_block->MergePrev(), Status::FailedPrecondition()); |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 334 | } |
| 335 | |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 336 | TEST(Block, CanCheckValidBlock) { |
| 337 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 338 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 339 | |
| 340 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 341 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 342 | |
| 343 | Block* second_block = nullptr; |
| 344 | first_block->Split(512, &second_block); |
| 345 | |
| 346 | Block* third_block = nullptr; |
| 347 | second_block->Split(256, &third_block); |
| 348 | |
| 349 | EXPECT_EQ(first_block->IsValid(), true); |
| 350 | EXPECT_EQ(second_block->IsValid(), true); |
| 351 | EXPECT_EQ(third_block->IsValid(), true); |
| 352 | } |
| 353 | |
| 354 | TEST(Block, CanCheckInalidBlock) { |
| 355 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 356 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 357 | |
| 358 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 359 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 360 | |
| 361 | Block* second_block = nullptr; |
| 362 | first_block->Split(512, &second_block); |
| 363 | |
| 364 | Block* third_block = nullptr; |
| 365 | second_block->Split(256, &third_block); |
| 366 | |
| 367 | Block* fourth_block = nullptr; |
| 368 | third_block->Split(128, &fourth_block); |
| 369 | |
| 370 | std::byte* next_ptr = reinterpret_cast<std::byte*>(first_block); |
| 371 | memcpy(next_ptr, second_block, sizeof(void*)); |
| 372 | EXPECT_EQ(first_block->IsValid(), false); |
| 373 | EXPECT_EQ(second_block->IsValid(), false); |
| 374 | EXPECT_EQ(third_block->IsValid(), true); |
| 375 | EXPECT_EQ(fourth_block->IsValid(), true); |
| 376 | |
Ewout van Bekkum | e4d7b69 | 2020-10-15 13:12:30 -0700 | [diff] [blame] | 377 | #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 378 | std::byte fault_poison[PW_ALLOCATOR_POISON_OFFSET] = {std::byte(0)}; |
| 379 | std::byte* front_poison = |
| 380 | reinterpret_cast<std::byte*>(third_block) + sizeof(*third_block); |
| 381 | memcpy(front_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET); |
| 382 | EXPECT_EQ(third_block->IsValid(), false); |
| 383 | |
| 384 | std::byte* end_poison = |
| 385 | reinterpret_cast<std::byte*>(fourth_block) + sizeof(*fourth_block); |
| 386 | memcpy(end_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET); |
| 387 | EXPECT_EQ(fourth_block->IsValid(), false); |
| 388 | #endif // PW_ALLOCATOR_POISON_ENABLE |
| 389 | } |
| 390 | |
| 391 | TEST(Block, CanPoisonBlock) { |
Ewout van Bekkum | e4d7b69 | 2020-10-15 13:12:30 -0700 | [diff] [blame] | 392 | #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 393 | constexpr size_t kN = 1024; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 394 | alignas(Block*) byte bytes[kN]; |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 395 | |
| 396 | Block* first_block = nullptr; |
Armando Montanez | 1ee925c | 2020-06-29 13:15:28 -0700 | [diff] [blame] | 397 | EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus()); |
Chenghan Zhou | ea0f7ad | 2020-07-29 18:20:37 -0400 | [diff] [blame] | 398 | |
| 399 | Block* second_block = nullptr; |
| 400 | first_block->Split(512, &second_block); |
| 401 | |
| 402 | Block* third_block = nullptr; |
| 403 | second_block->Split(256, &third_block); |
| 404 | |
| 405 | EXPECT_EQ(first_block->IsValid(), true); |
| 406 | EXPECT_EQ(second_block->IsValid(), true); |
| 407 | EXPECT_EQ(third_block->IsValid(), true); |
| 408 | #endif // PW_ALLOCATOR_POISON_ENABLE |
| 409 | } |
| 410 | |
Jamie Garside | 558e144 | 2020-03-27 17:05:55 +0000 | [diff] [blame] | 411 | } // namespace pw::allocator |