xref: /aosp_15_r20/external/pigweed/pw_multibuf/chunk_test.cc (revision 61c4878ac05f98d0ceed94b57d316916de578985)

// Copyright 2023 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

#include "pw_multibuf/chunk.h"

#include <memory>

#if __cplusplus >= 202002L
#include <ranges>
#endif  // __cplusplus >= 202002L

#include "pw_allocator/testing.h"
#include "pw_multibuf/header_chunk_region_tracker.h"
#include "pw_unit_test/framework.h"

namespace pw::multibuf {
namespace {

using ::pw::allocator::test::AllocatorForTest;

/// Returns literal with ``_size`` suffix as a ``size_t``.
///
/// This is useful for writing size-related test assertions without
/// explicit (verbose) casts.
constexpr size_t operator""_size(unsigned long long n) { return n; }

const size_t kArbitraryAllocatorSize = 1024;
const size_t kArbitraryChunkSize = 32;

#if __cplusplus >= 202002L
static_assert(std::ranges::contiguous_range<Chunk>);
#endif  // __cplusplus >= 202002L

void TakesSpan([[maybe_unused]] ByteSpan span) {}

TEST(Chunk, IsImplicitlyConvertibleToSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk.has_value());
  // ``Chunk`` should convert to ``ByteSpan``.
  TakesSpan(**chunk);
}

TEST(OwnedChunk, ReleaseDestroysChunkRegion) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  const auto& metrics = allocator.metrics();
  auto tracker =
      HeaderChunkRegionTracker::AllocateRegion(allocator, kArbitraryChunkSize);
  ASSERT_NE(tracker, nullptr);
  EXPECT_EQ(metrics.num_allocations.value(), 1_size);

  std::optional<OwnedChunk> chunk_opt = tracker->CreateFirstChunk();
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  EXPECT_EQ(metrics.num_allocations.value(), 2_size);
  EXPECT_EQ(chunk.size(), kArbitraryChunkSize);

  chunk.Release();
  EXPECT_EQ(chunk.size(), 0_size);
  EXPECT_EQ(metrics.num_deallocations.value(), 2_size);
  EXPECT_EQ(metrics.allocated_bytes.value(), 0_size);
}

TEST(OwnedChunk, DestructorDestroysChunkRegion) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  const auto& metrics = allocator.metrics();
  auto tracker =
      HeaderChunkRegionTracker::AllocateRegion(allocator, kArbitraryChunkSize);
  ASSERT_NE(tracker, nullptr);
  EXPECT_EQ(metrics.num_allocations.value(), 1_size);

  {
    std::optional<OwnedChunk> chunk = tracker->CreateFirstChunk();
    ASSERT_TRUE(chunk.has_value());
    EXPECT_EQ(metrics.num_allocations.value(), 2_size);
    EXPECT_EQ(chunk->size(), kArbitraryChunkSize);
  }

  EXPECT_EQ(metrics.num_deallocations.value(), 2_size);
  EXPECT_EQ(metrics.allocated_bytes.value(), 0_size);
}

TEST(Chunk, DiscardPrefixDiscardsPrefixOfSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kDiscarded = 4;
  chunk->DiscardPrefix(kDiscarded);
  EXPECT_EQ(chunk.size(), old_span.size() - kDiscarded);
  EXPECT_EQ(chunk.data(), old_span.data() + kDiscarded);
}

TEST(Chunk, TakePrefixTakesPrefixOfSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kTaken = 4;
  std::optional<OwnedChunk> front_opt = chunk->TakePrefix(kTaken);
  ASSERT_TRUE(front_opt.has_value());
  auto& front = *front_opt;
  EXPECT_EQ(front->size(), kTaken);
  EXPECT_EQ(front->data(), old_span.data());
  EXPECT_EQ(chunk.size(), old_span.size() - kTaken);
  EXPECT_EQ(chunk.data(), old_span.data() + kTaken);
}

TEST(Chunk, TruncateDiscardsEndOfSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kShorter = 5;
  chunk->Truncate(old_span.size() - kShorter);
  EXPECT_EQ(chunk.size(), old_span.size() - kShorter);
  EXPECT_EQ(chunk.data(), old_span.data());
}

TEST(Chunk, TakeSuffixTakesEndOfSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kTaken = 5;
  std::optional<OwnedChunk> tail_opt = chunk->TakeSuffix(kTaken);
  ASSERT_TRUE(tail_opt.has_value());
  auto& tail = *tail_opt;
  EXPECT_EQ(tail.size(), kTaken);
  EXPECT_EQ(tail.data(), old_span.data() + old_span.size() - kTaken);
  EXPECT_EQ(chunk.size(), old_span.size() - kTaken);
  EXPECT_EQ(chunk.data(), old_span.data());
}

TEST(Chunk, SliceRemovesSidesOfSpan) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kBegin = 4;
  const size_t kEnd = 9;
  chunk->Slice(kBegin, kEnd);
  EXPECT_EQ(chunk.data(), old_span.data() + kBegin);
  EXPECT_EQ(chunk.size(), kEnd - kBegin);
}

TEST(Chunk, RegionPersistsUntilAllChunksReleased) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  const auto& metrics = allocator.metrics();
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  // One allocation for the region tracker, one for the chunk.
  EXPECT_EQ(metrics.num_allocations.value(), 2_size);
  const size_t kSplitPoint = 13;
  auto split_opt = chunk->TakePrefix(kSplitPoint);
  ASSERT_TRUE(split_opt.has_value());
  auto& split = *split_opt;
  // One allocation for the region tracker, one for each of two chunks.
  EXPECT_EQ(metrics.num_allocations.value(), 3_size);
  chunk.Release();
  EXPECT_EQ(metrics.num_deallocations.value(), 1_size);
  split.Release();
  EXPECT_EQ(metrics.num_deallocations.value(), 3_size);
}

TEST(Chunk, ClaimPrefixReclaimsDiscardedPrefix) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = chunk;
  const size_t kDiscarded = 4;
  chunk->DiscardPrefix(kDiscarded);
  EXPECT_TRUE(chunk->ClaimPrefix(kDiscarded));
  EXPECT_EQ(chunk.size(), old_span.size());
  EXPECT_EQ(chunk.data(), old_span.data());
}

TEST(Chunk, ClaimPrefixFailsOnFullRegionChunk) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  EXPECT_FALSE(chunk->ClaimPrefix(1));
}

TEST(Chunk, ClaimPrefixFailsOnNeighboringChunk) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kSplitPoint = 22;
  auto front = chunk->TakePrefix(kSplitPoint);
  ASSERT_TRUE(front.has_value());
  EXPECT_FALSE(chunk->ClaimPrefix(1));
}

TEST(Chunk,
     ClaimPrefixFailsAtStartOfRegionEvenAfterReleasingChunkAtEndOfRegion) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kTaken = 13;
  auto split = chunk->TakeSuffix(kTaken);
  ASSERT_TRUE(split.has_value());
  split->Release();
  EXPECT_FALSE(chunk->ClaimPrefix(1));
}

TEST(Chunk, ClaimPrefixReclaimsPrecedingChunksDiscardedSuffix) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kSplitPoint = 13;
  auto split_opt = chunk->TakePrefix(kSplitPoint);
  ASSERT_TRUE(split_opt.has_value());
  auto& split = *split_opt;
  const size_t kDiscard = 3;
  split->Truncate(split.size() - kDiscard);
  EXPECT_TRUE(chunk->ClaimPrefix(kDiscard));
  EXPECT_FALSE(chunk->ClaimPrefix(1));
}

TEST(Chunk, ClaimSuffixReclaimsTruncatedEnd) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  ConstByteSpan old_span = *chunk;
  const size_t kDiscarded = 4;
  chunk->Truncate(old_span.size() - kDiscarded);
  EXPECT_TRUE(chunk->ClaimSuffix(kDiscarded));
  EXPECT_EQ(chunk->size(), old_span.size());
  EXPECT_EQ(chunk->data(), old_span.data());
}

TEST(Chunk, ClaimSuffixFailsOnFullRegionChunk) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  EXPECT_FALSE(chunk->ClaimSuffix(1));
}

TEST(Chunk, ClaimSuffixFailsWithNeighboringChunk) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kSplitPoint = 22;
  auto split_opt = chunk->TakePrefix(kSplitPoint);
  ASSERT_TRUE(split_opt.has_value());
  auto& split = *split_opt;
  EXPECT_FALSE(split->ClaimSuffix(1));
}

TEST(Chunk, ClaimSuffixFailsAtEndOfRegionEvenAfterReleasingFirstChunkInRegion) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kTaken = 22;
  auto split_opt = chunk->TakeSuffix(kTaken);
  ASSERT_TRUE(split_opt.has_value());
  auto& split = *split_opt;
  EXPECT_FALSE(split->ClaimSuffix(1));
}

TEST(Chunk, ClaimSuffixReclaimsFollowingChunksDiscardedPrefix) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_opt.has_value());
  auto& chunk = *chunk_opt;
  const size_t kSplitPoint = 22;
  auto split_opt = chunk->TakePrefix(kSplitPoint);
  ASSERT_TRUE(split_opt.has_value());
  auto& split = *split_opt;
  const size_t kDiscarded = 3;
  chunk->DiscardPrefix(kDiscarded);
  EXPECT_TRUE(split->ClaimSuffix(kDiscarded));
  EXPECT_FALSE(split->ClaimSuffix(1));
}

TEST(Chunk, MergeReturnsFalseForChunksFromDifferentRegions) {
  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_1_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_1_opt.has_value());
  OwnedChunk& chunk_1 = *chunk_1_opt;
  std::optional<OwnedChunk> chunk_2_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_2_opt.has_value());
  OwnedChunk& chunk_2 = *chunk_2_opt;
  EXPECT_FALSE(chunk_1->CanMerge(*chunk_2));
  EXPECT_FALSE(chunk_1->Merge(chunk_2));
  // Ensure that neither chunk was modified
  EXPECT_EQ(chunk_1.size(), kArbitraryChunkSize);
  EXPECT_EQ(chunk_2.size(), kArbitraryChunkSize);
}

TEST(Chunk, MergeReturnsFalseForNonAdjacentChunksFromSameRegion) {
  const size_t kTakenFromOne = 8;
  const size_t kTakenFromTwo = 4;

  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_1_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_1_opt.has_value());
  OwnedChunk& chunk_1 = *chunk_1_opt;

  std::optional<OwnedChunk> chunk_2_opt = chunk_1->TakeSuffix(kTakenFromOne);
  ASSERT_TRUE(chunk_2_opt.has_value());
  OwnedChunk& chunk_2 = *chunk_2_opt;

  std::optional<OwnedChunk> chunk_3_opt = chunk_2->TakeSuffix(kTakenFromTwo);
  ASSERT_TRUE(chunk_3_opt.has_value());
  OwnedChunk& chunk_3 = *chunk_3_opt;

  EXPECT_FALSE(chunk_1->CanMerge(*chunk_3));
  EXPECT_FALSE(chunk_1->Merge(chunk_3));
  EXPECT_EQ(chunk_1.size(), kArbitraryChunkSize - kTakenFromOne);
  EXPECT_EQ(chunk_2.size(), kTakenFromOne - kTakenFromTwo);
  EXPECT_EQ(chunk_3.size(), kTakenFromTwo);
}

TEST(Chunk, MergeJoinsMultipleAdjacentChunksFromSameRegion) {
  const size_t kTakenFromOne = 8;
  const size_t kTakenFromTwo = 4;

  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_1_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_1_opt.has_value());
  OwnedChunk& chunk_1 = *chunk_1_opt;

  std::optional<OwnedChunk> chunk_2_opt = chunk_1->TakeSuffix(kTakenFromOne);
  ASSERT_TRUE(chunk_2_opt.has_value());
  OwnedChunk& chunk_2 = *chunk_2_opt;

  std::optional<OwnedChunk> chunk_3_opt = chunk_2->TakeSuffix(kTakenFromTwo);
  ASSERT_TRUE(chunk_3_opt.has_value());
  OwnedChunk& chunk_3 = *chunk_3_opt;

  EXPECT_TRUE(chunk_1->CanMerge(*chunk_2));
  EXPECT_TRUE(chunk_1->Merge(chunk_2));
  EXPECT_TRUE(chunk_1->CanMerge(*chunk_3));
  EXPECT_TRUE(chunk_1->Merge(chunk_3));

  EXPECT_EQ(chunk_1.size(), kArbitraryChunkSize);
  EXPECT_EQ(chunk_2.size(), 0_size);
  EXPECT_EQ(chunk_3.size(), 0_size);
}

TEST(Chunk, MergeJoinsAdjacentChunksFromSameRegion) {
  const size_t kTaken = 4;

  AllocatorForTest<kArbitraryAllocatorSize> allocator;
  std::optional<OwnedChunk> chunk_1_opt =
      HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator,
                                                      kArbitraryChunkSize);
  ASSERT_TRUE(chunk_1_opt.has_value());
  OwnedChunk& chunk_1 = *chunk_1_opt;
  std::optional<OwnedChunk> chunk_2_opt = chunk_1->TakeSuffix(kTaken);
  ASSERT_TRUE(chunk_2_opt.has_value());
  OwnedChunk& chunk_2 = *chunk_2_opt;
  EXPECT_EQ(chunk_1.size(), kArbitraryChunkSize - kTaken);
  EXPECT_EQ(chunk_2.size(), kTaken);

  EXPECT_TRUE(chunk_1->CanMerge(*chunk_2));
  EXPECT_TRUE(chunk_1->Merge(chunk_2));
  EXPECT_EQ(chunk_1.size(), kArbitraryChunkSize);
  EXPECT_EQ(chunk_2.size(), 0_size);
}

}  // namespace
}  // namespace pw::multibuf