third_party/pigweed/repo/pw_allocator/block_test.cc

   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
  17 #include <cstring>
  18 #include <span>
  19
  20 #include "gtest/gtest.h"
  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;
  31   auto status = Block::Init(std::span(bytes, kN), &block);
  32
  33   ASSERT_EQ(status, OkStatus());
  34   EXPECT_EQ(block->OuterSize(), kN);
  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));
  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;
  51   auto status = Block::Init(std::span(byte_ptr + 1, kN - 1), &block);
  52
  53   EXPECT_EQ(status, Status::InvalidArgument());
  54 }
  55
  56 TEST(Block, CannotCreateTooSmallBlock) {
  57   constexpr size_t kN = 2;
  58   alignas(Block*) byte bytes[kN];
  59   Block* block = nullptr;
  60   auto status = Block::Init(std::span(bytes, kN), &block);
  61
  62   EXPECT_EQ(status, Status::InvalidArgument());
  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;
  71   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
  72
  73   Block* next_block = nullptr;
  74   auto status = block->Split(kSplitN, &next_block);
  75
  76   ASSERT_EQ(status, OkStatus());
  77   EXPECT_EQ(block->InnerSize(), kSplitN);
  78   EXPECT_EQ(block->OuterSize(),
  79             kSplitN + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET);
  80   EXPECT_EQ(block->Last(), false);
  81
  82   EXPECT_EQ(next_block->OuterSize(),
  83             kN - kSplitN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
  84   EXPECT_EQ(next_block->Used(), false);
  85   EXPECT_EQ(next_block->Last(), true);
  86
  87   EXPECT_EQ(block->Next(), next_block);
  88   EXPECT_EQ(next_block->Prev(), block);
  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;
 104   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 105
 106   Block* next_block = nullptr;
 107   auto status = block->Split(kSplitN, &next_block);
 108
 109   ASSERT_EQ(status, OkStatus());
 110   EXPECT_EQ(block->InnerSize(), split_len);
 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);
 115   EXPECT_EQ(next_block->Used(), false);
 116   EXPECT_EQ(block->Next(), next_block);
 117   EXPECT_EQ(next_block->Prev(), block);
 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;
 133   alignas(Block*) byte bytes[kN];
 134
 135   Block* block = nullptr;
 136   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 137
 138   Block* block2 = nullptr;
 139   block->Split(kSplit1, &block2);
 140
 141   Block* block3 = nullptr;
 142   block->Split(kSplit2, &block3);
 143
 144   EXPECT_EQ(block->Next(), block3);
 145   EXPECT_EQ(block3->Next(), block2);
 146   EXPECT_EQ(block2->Prev(), block3);
 147   EXPECT_EQ(block3->Prev(), block);
 148 }
 149
 150 TEST(Block, CannotSplitBlockWithoutHeaderSpace) {
 151   constexpr size_t kN = 1024;
 152   constexpr size_t kSplitN =
 153       kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET - 1;
 154   alignas(Block*) byte bytes[kN];
 155
 156   Block* block = nullptr;
 157   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 158
 159   Block* next_block = nullptr;
 160   auto status = block->Split(kSplitN, &next_block);
 161
 162   EXPECT_EQ(status, Status::ResourceExhausted());
 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;
 169   alignas(Block*) byte bytes[kN];
 170
 171   Block* block = nullptr;
 172   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 173
 174   auto status = block->Split(kSplitN, nullptr);
 175   EXPECT_EQ(status, Status::InvalidArgument());
 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;
 181   alignas(Block*) byte bytes[kN];
 182
 183   Block* block = nullptr;
 184   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 185
 186   Block* next_block = nullptr;
 187   auto status = block->Split(block->InnerSize() + 1, &next_block);
 188
 189   EXPECT_EQ(status, Status::OutOfRange());
 190 }
 191
 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;
 195   alignas(Block*) byte bytes[kN];
 196
 197   Block* block = nullptr;
 198   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 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
 205   ASSERT_EQ(status, Status::ResourceExhausted());
 206   EXPECT_EQ(next_block, nullptr);
 207 }
 208
 209 TEST(Block, CanMakeZeroSizeFirstBlock) {
 210   // This block does support splitting with zero payload size.
 211   constexpr size_t kN = 1024;
 212   alignas(Block*) byte bytes[kN];
 213
 214   Block* block = nullptr;
 215   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 216
 217   Block* next_block = nullptr;
 218   auto status = block->Split(0, &next_block);
 219
 220   ASSERT_EQ(status, OkStatus());
 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;
 227   alignas(Block*) byte bytes[kN];
 228
 229   Block* block = nullptr;
 230   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 231
 232   Block* next_block = nullptr;
 233   auto status = block->Split(
 234       block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET,
 235       &next_block);
 236
 237   ASSERT_EQ(status, OkStatus());
 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;
 246   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 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
 253   EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN));
 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;
 264   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 265
 266   block->MarkUsed();
 267
 268   Block* next_block = nullptr;
 269   auto status = block->Split(512, &next_block);
 270   EXPECT_EQ(status, Status::FailedPrecondition());
 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;
 279   alignas(Block*) byte bytes[kN];
 280
 281   Block* block = nullptr;
 282   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 283
 284   Block* block2 = nullptr;
 285   block->Split(kSplit1, &block2);
 286
 287   Block* block3 = nullptr;
 288   block->Split(kSplit2, &block3);
 289
 290   EXPECT_EQ(block3->MergeNext(), OkStatus());
 291
 292   EXPECT_EQ(block->Next(), block3);
 293   EXPECT_EQ(block3->Prev(), block);
 294   EXPECT_EQ(block->InnerSize(), kSplit2);
 295
 296   // The resulting "right hand" block should have an outer size of 1024 - 256 -
 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);
 301 }
 302
 303 TEST(Block, CannotMergeWithFirstOrLastBlock) {
 304   constexpr size_t kN = 1024;
 305   alignas(Block*) byte bytes[kN];
 306
 307   // Do a split, just to sanity check that the checks on Next/Prev are
 308   // different...
 309   Block* block = nullptr;
 310   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 311
 312   Block* next_block = nullptr;
 313   block->Split(512, &next_block);
 314
 315   EXPECT_EQ(next_block->MergeNext(), Status::OutOfRange());
 316   EXPECT_EQ(block->MergePrev(), Status::OutOfRange());
 317 }
 318
 319 TEST(Block, CannotMergeUsedBlock) {
 320   constexpr size_t kN = 1024;
 321   alignas(Block*) byte bytes[kN];
 322
 323   // Do a split, just to sanity check that the checks on Next/Prev are
 324   // different...
 325   Block* block = nullptr;
 326   EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
 327
 328   Block* next_block = nullptr;
 329   block->Split(512, &next_block);
 330
 331   block->MarkUsed();
 332   EXPECT_EQ(block->MergeNext(), Status::FailedPrecondition());
 333   EXPECT_EQ(next_block->MergePrev(), Status::FailedPrecondition());
 334 }
 335
 336 TEST(Block, CanCheckValidBlock) {
 337   constexpr size_t kN = 1024;
 338   alignas(Block*) byte bytes[kN];
 339
 340   Block* first_block = nullptr;
 341   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
 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;
 356   alignas(Block*) byte bytes[kN];
 357
 358   Block* first_block = nullptr;
 359   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
 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
 377 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
 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) {
 392 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
 393   constexpr size_t kN = 1024;
 394   alignas(Block*) byte bytes[kN];
 395
 396   Block* first_block = nullptr;
 397   EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
 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
 411 }  // namespace pw::allocator