diff options
Diffstat (limited to 'pw_multibuf')
-rw-r--r-- | pw_multibuf/Android.bp | 67 | ||||
-rw-r--r-- | pw_multibuf/BUILD.bazel | 54 | ||||
-rw-r--r-- | pw_multibuf/BUILD.gn | 66 | ||||
-rw-r--r-- | pw_multibuf/CMakeLists.txt | 61 | ||||
-rw-r--r-- | pw_multibuf/chunk.cc | 6 | ||||
-rw-r--r-- | pw_multibuf/chunk_region_tracker_test.cc | 70 | ||||
-rw-r--r-- | pw_multibuf/chunk_test.cc | 126 | ||||
-rw-r--r-- | pw_multibuf/docs.rst | 18 | ||||
-rw-r--r-- | pw_multibuf/multibuf_test.cc | 77 | ||||
-rw-r--r-- | pw_multibuf/public/pw_multibuf/chunk.h | 1 | ||||
-rw-r--r-- | pw_multibuf/public/pw_multibuf/chunk_region_tracker.h | 106 | ||||
-rw-r--r-- | pw_multibuf/public/pw_multibuf/internal/test_utils.h | 162 | ||||
-rw-r--r-- | pw_multibuf/public/pw_multibuf/single_chunk_region_tracker.h | 82 | ||||
-rw-r--r-- | pw_multibuf/single_chunk_region_tracker_test.cc | 77 |
14 files changed, 679 insertions, 294 deletions
diff --git a/pw_multibuf/Android.bp b/pw_multibuf/Android.bp new file mode 100644 index 000000000..6faec4c2a --- /dev/null +++ b/pw_multibuf/Android.bp @@ -0,0 +1,67 @@ +// Copyright 2024 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. + +package { + default_applicable_licenses: ["external_pigweed_license"], +} + +filegroup { + name: "pw_multibuf_src_files", + srcs: [ + "chunk.cc", + "multibuf.cc", + ], +} + +cc_library_headers { + name: "pw_multibuf_headers", + cpp_std: "c++20", + export_include_dirs: [ + "public", + ], + header_libs: [ + "pw_assert_headers", + "pw_log_headers", + "pw_span_headers", + "pw_sync_headers", + ], + export_header_lib_headers: [ + "pw_assert_headers", + "pw_log_headers", + "pw_span_headers", + "pw_sync_headers", + ], + vendor_available: true, + host_supported: true, +} + +cc_defaults { + name: "pw_multibuf_defaults", + cpp_std: "c++20", + srcs: [ + ":pw_multibuf_src_files", + ], + header_libs: [ + "pw_multibuf_headers", + ], + export_header_lib_headers: [ + "pw_multibuf_headers", + ], + static_libs: [ + "pw_bytes", + ], + export_static_lib_headers: [ + "pw_bytes", + ], +} diff --git a/pw_multibuf/BUILD.bazel b/pw_multibuf/BUILD.bazel index c078e6098..50700b856 100644 --- a/pw_multibuf/BUILD.bazel +++ b/pw_multibuf/BUILD.bazel @@ -14,7 +14,6 @@ load( "//pw_build:pigweed.bzl", - "pw_cc_library", "pw_cc_test", ) @@ -22,7 +21,7 @@ package(default_visibility = ["//visibility:public"]) licenses(["notice"]) -pw_cc_library( +cc_library( name = "chunk", srcs = ["chunk.cc"], hdrs = ["public/pw_multibuf/chunk.h"], @@ -36,15 +35,25 @@ pw_cc_library( ], ) -pw_cc_library( - name = "test_utils", - hdrs = ["public/pw_multibuf/internal/test_utils.h"], +cc_library( + name = "chunk_region_tracker", + hdrs = ["public/pw_multibuf/chunk_region_tracker.h"], includes = ["public"], - visibility = [":__subpackages__"], deps = [ ":chunk", - "//pw_allocator:allocator_metric_proxy", - "//pw_allocator:split_free_list_allocator", + "//pw_allocator:allocator", + "//pw_bytes", + ], +) + +cc_library( + name = "single_chunk_region_tracker", + hdrs = ["public/pw_multibuf/single_chunk_region_tracker.h"], + includes = ["public"], + deps = [ + ":chunk", + "//pw_assert", + "//pw_bytes", ], ) @@ -53,12 +62,33 @@ pw_cc_test( srcs = ["chunk_test.cc"], deps = [ ":chunk", - ":test_utils", + ":chunk_region_tracker", + "//pw_allocator:allocator_testing", "//pw_unit_test", ], ) -pw_cc_library( +pw_cc_test( + name = "chunk_region_tracker_test", + srcs = ["chunk_region_tracker_test.cc"], + deps = [ + ":chunk", + ":chunk_region_tracker", + "//pw_allocator:simple_allocator", + "//pw_status", + ], +) + +pw_cc_test( + name = "single_chunk_region_tracker_test", + srcs = ["single_chunk_region_tracker_test.cc"], + deps = [ + ":chunk", + ":single_chunk_region_tracker", + ], +) + +cc_library( name = "pw_multibuf", srcs = ["multibuf.cc"], hdrs = ["public/pw_multibuf/multibuf.h"], @@ -69,8 +99,10 @@ pw_cc_test( name = "multibuf_test", srcs = ["multibuf_test.cc"], deps = [ + ":chunk_region_tracker", ":pw_multibuf", - ":test_utils", + "//pw_allocator:allocator_testing", + "//pw_assert", "//pw_unit_test", ], ) diff --git a/pw_multibuf/BUILD.gn b/pw_multibuf/BUILD.gn index 41a9f20d9..d0a065391 100644 --- a/pw_multibuf/BUILD.gn +++ b/pw_multibuf/BUILD.gn @@ -37,22 +37,66 @@ pw_source_set("chunk") { deps = [ "$dir_pw_assert:check" ] } -pw_source_set("test_utils") { +pw_source_set("chunk_region_tracker") { public_configs = [ ":public_include_path" ] - public = [ "public/pw_multibuf/internal/test_utils.h" ] + public = [ "public/pw_multibuf/chunk_region_tracker.h" ] public_deps = [ ":chunk", - "$dir_pw_allocator:allocator_metric_proxy", - "$dir_pw_allocator:split_free_list_allocator", + dir_pw_allocator, + dir_pw_bytes, + ] +} + +pw_test("chunk_region_tracker_test") { + deps = [ + ":chunk", + ":chunk_region_tracker", + "$dir_pw_allocator:simple_allocator", + dir_pw_status, + ] + sources = [ "chunk_region_tracker_test.cc" ] + + # TODO: https://pwbug.dev/325509758 - Doesn't work on the Pico yet; hangs + # indefinitely. + if (pw_build_EXECUTABLE_TARGET_TYPE == "pico_executable") { + enable_if = false + } +} + +pw_source_set("single_chunk_region_tracker") { + public_configs = [ ":public_include_path" ] + public = [ "public/pw_multibuf/single_chunk_region_tracker.h" ] + public_deps = [ + ":chunk", + dir_pw_assert, + dir_pw_bytes, + ] +} + +pw_test("single_chunk_region_tracker_test") { + deps = [ + ":chunk", + ":single_chunk_region_tracker", ] + sources = [ "single_chunk_region_tracker_test.cc" ] + + # TODO: b/260624583 - Fix this for //targets/rp2040 + enable_if = pw_build_EXECUTABLE_TARGET_TYPE != "pico_executable" } pw_test("chunk_test") { deps = [ ":chunk", - ":test_utils", + ":chunk_region_tracker", + "$dir_pw_allocator:allocator_testing", ] sources = [ "chunk_test.cc" ] + + # TODO: https://pwbug.dev/325509758 - Doesn't work on the Pico yet; hangs + # indefinitely. + if (pw_build_EXECUTABLE_TARGET_TYPE == "pico_executable") { + enable_if = false + } } pw_source_set("pw_multibuf") { @@ -64,16 +108,26 @@ pw_source_set("pw_multibuf") { pw_test("multibuf_test") { deps = [ + ":chunk_region_tracker", ":pw_multibuf", - ":test_utils", + "$dir_pw_allocator:allocator_testing", + dir_pw_assert, ] sources = [ "multibuf_test.cc" ] + + # TODO: https://pwbug.dev/325509758 - Doesn't work on the Pico yet; hangs + # indefinitely. + if (pw_build_EXECUTABLE_TARGET_TYPE == "pico_executable") { + enable_if = false + } } pw_test_group("tests") { tests = [ ":chunk_test", + ":chunk_region_tracker_test", ":multibuf_test", + ":single_chunk_region_tracker_test", ] } diff --git a/pw_multibuf/CMakeLists.txt b/pw_multibuf/CMakeLists.txt index 217b70a60..39bc17b5c 100644 --- a/pw_multibuf/CMakeLists.txt +++ b/pw_multibuf/CMakeLists.txt @@ -31,28 +31,65 @@ pw_add_library(pw_multibuf.chunk STATIC chunk.cc ) -pw_add_library(pw_multibuf.test_utils STATIC - HEADERS - public/pw_multibuf/internal/test_utils.h +pw_add_library(pw_multibuf.chunk_region_tracker STATIC + SOURCES + public/pw_multibuf/chunk_region_tracker.h + PUBLIC_INCLUDES + public + PUBLIC_DEPS + pw_allocator.allocator + pw_bytes + pw_multibuf.chunk +) + +pw_add_library(pw_multibuf.single_chunk_region_tracker STATIC + SOURCES + public/pw_multibuf/single_chunk_region_tracker.h PUBLIC_INCLUDES public PUBLIC_DEPS + pw_assert + pw_bytes pw_multibuf.chunk - pw_allocator.allocator_metric_proxy - pw_allocator.split_free_list_allocator +) -pw_add_test(pw_multibuf.chunk_test STATIC +pw_add_test(pw_multibuf.chunk_test SOURCES chunk_test.cc PRIVATE_DEPS + pw_allocator.allocator_testing pw_multibuf.chunk - pw_multibuf.test_utils + pw_multibuf.chunk_region_tracker GROUPS modules pw_multibuf ) -pw_add_library(pw_multibuf.pw_multibuf STATIC +pw_add_test(pw_multibuf.chunk_region_tracker_test + SOURCES + chunk_region_tracker_test.cc + PRIVATE_DEPS + pw_allocator.simple_allocator + pw_multibuf.chunk + pw_multibuf.chunk_region_tracker + pw_status + GROUPS + modules + pw_multibuf +) + +pw_add_test(pw_multibuf.single_chunk_region_tracker_test + SOURCES + single_chunk_region_tracker_test.cc + PRIVATE_DEPS + pw_multibuf.chunk + pw_multibuf.single_chunk_region_tracker + GROUPS + modules + pw_multibuf +) + +pw_add_library(pw_multibuf STATIC HEADERS public/pw_multibuf/multibuf.h PUBLIC_INCLUDES @@ -63,12 +100,14 @@ pw_add_library(pw_multibuf.pw_multibuf STATIC multibuf.cc ) -pw_add_test(pw_multibuf.multibuf_test STATIC +pw_add_test(pw_multibuf.multibuf_test SOURCES multibuf_test.cc PRIVATE_DEPS - pw_multibuf.multibuf - pw_multibuf.test_utils + pw_assert + pw_multibuf + pw_multibuf.chunk_region_tracker + pw_allocator.allocator_testing GROUPS modules pw_multibuf diff --git a/pw_multibuf/chunk.cc b/pw_multibuf/chunk.cc index 628a9d30c..4a1e80514 100644 --- a/pw_multibuf/chunk.cc +++ b/pw_multibuf/chunk.cc @@ -67,7 +67,7 @@ bool Chunk::Merge(OwnedChunk& next_chunk_owned) { } void Chunk::InsertAfterInRegionList(Chunk* new_chunk) - PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_ -> lock_) { + PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_->lock_) { new_chunk->next_in_region_ = next_in_region_; new_chunk->prev_in_region_ = this; if (next_in_region_ != nullptr) { @@ -77,7 +77,7 @@ void Chunk::InsertAfterInRegionList(Chunk* new_chunk) } void Chunk::InsertBeforeInRegionList(Chunk* new_chunk) - PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_ -> lock_) { + PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_->lock_) { new_chunk->next_in_region_ = this; new_chunk->prev_in_region_ = prev_in_region_; if (prev_in_region_ != nullptr) { @@ -87,7 +87,7 @@ void Chunk::InsertBeforeInRegionList(Chunk* new_chunk) } void Chunk::RemoveFromRegionList() - PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_ -> lock_) { + PW_EXCLUSIVE_LOCKS_REQUIRED(region_tracker_->lock_) { if (prev_in_region_ != nullptr) { prev_in_region_->next_in_region_ = next_in_region_; } diff --git a/pw_multibuf/chunk_region_tracker_test.cc b/pw_multibuf/chunk_region_tracker_test.cc new file mode 100644 index 000000000..2af9c6ed2 --- /dev/null +++ b/pw_multibuf/chunk_region_tracker_test.cc @@ -0,0 +1,70 @@ +// 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_region_tracker.h" + +#include <cstddef> +#include <optional> + +#include "pw_allocator/simple_allocator.h" +#include "pw_multibuf/chunk.h" +#include "pw_status/status.h" +#include "pw_unit_test/framework.h" + +namespace pw::multibuf { +namespace { + +const size_t kArbitraryAllocatorSize = 1024; +const size_t kArbitraryChunkSize = 32; + +TEST(HeaderChunkRegionTracker, AllocatesRegionAsChunk) { + allocator::SimpleAllocator alloc{}; + std::array<std::byte, kArbitraryAllocatorSize> alloc_storage{}; + ASSERT_EQ(alloc.Init(alloc_storage), OkStatus()); + std::optional<OwnedChunk> chunk = + HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + kArbitraryChunkSize); + ASSERT_TRUE(chunk.has_value()); +} + +TEST(HeaderChunkRegionTracker, AllocatedRegionAsChunkTooLarge) { + allocator::SimpleAllocator alloc{}; + std::array<std::byte, kArbitraryAllocatorSize> alloc_storage{}; + ASSERT_EQ(alloc.Init(alloc_storage), OkStatus()); + std::optional<OwnedChunk> chunk = + HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + kArbitraryAllocatorSize); + ASSERT_FALSE(chunk.has_value()); +} + +TEST(HeaderChunkRegionTracker, AllocatesRegion) { + allocator::SimpleAllocator alloc{}; + std::array<std::byte, kArbitraryAllocatorSize> alloc_storage{}; + ASSERT_EQ(alloc.Init(alloc_storage), OkStatus()); + auto tracker = + HeaderChunkRegionTracker::AllocateRegion(&alloc, kArbitraryChunkSize); + ASSERT_NE(tracker, nullptr); +} + +TEST(HeaderChunkRegionTracker, AllocatedRegionTooLarge) { + allocator::SimpleAllocator alloc{}; + std::array<std::byte, kArbitraryAllocatorSize> alloc_storage{}; + ASSERT_EQ(alloc.Init(alloc_storage), OkStatus()); + auto tracker = + HeaderChunkRegionTracker::AllocateRegion(&alloc, kArbitraryAllocatorSize); + ASSERT_EQ(tracker, nullptr); +} + +} // namespace +} // namespace pw::multibuf diff --git a/pw_multibuf/chunk_test.cc b/pw_multibuf/chunk_test.cc index 23ff0e3f6..2a8a0d3d7 100644 --- a/pw_multibuf/chunk_test.cc +++ b/pw_multibuf/chunk_test.cc @@ -20,14 +20,14 @@ #include <ranges> #endif // __cplusplus >= 202002L -#include "gtest/gtest.h" -#include "pw_multibuf/internal/test_utils.h" +#include "pw_allocator/allocator_testing.h" +#include "pw_multibuf/chunk_region_tracker.h" +#include "pw_unit_test/framework.h" namespace pw::multibuf { namespace { -using ::pw::multibuf::internal::HeaderChunkRegionTracker; -using ::pw::multibuf::internal::TrackingAllocatorWithMemory; +using ::pw::allocator::test::AllocatorForTest; /// Returns literal with ``_size`` suffix as a ``size_t``. /// @@ -45,9 +45,9 @@ static_assert(std::ranges::contiguous_range<Chunk>); void TakesSpan([[maybe_unused]] ByteSpan span) {} TEST(Chunk, IsImplicitlyConvertibleToSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk.has_value()); // ``Chunk`` should convert to ``ByteSpan``. @@ -55,46 +55,46 @@ TEST(Chunk, IsImplicitlyConvertibleToSpan) { } TEST(OwnedChunk, ReleaseDestroysChunkRegion) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; auto tracker = - HeaderChunkRegionTracker::AllocateRegion(&alloc, kArbitraryChunkSize); + HeaderChunkRegionTracker::AllocateRegion(&allocator, kArbitraryChunkSize); ASSERT_NE(tracker, nullptr); - EXPECT_EQ(alloc.count(), 1_size); + EXPECT_EQ(allocator.num_allocations(), 1_size); std::optional<OwnedChunk> chunk_opt = Chunk::CreateFirstForRegion(*tracker); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; - EXPECT_EQ(alloc.count(), 2_size); + EXPECT_EQ(allocator.num_allocations(), 2_size); EXPECT_EQ(chunk.size(), kArbitraryChunkSize); chunk.Release(); EXPECT_EQ(chunk.size(), 0_size); - EXPECT_EQ(alloc.count(), 0_size); - EXPECT_EQ(alloc.used(), 0_size); + EXPECT_EQ(allocator.num_deallocations(), 2_size); + EXPECT_EQ(allocator.allocated_bytes(), 0_size); } TEST(OwnedChunk, DestructorDestroysChunkRegion) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; auto tracker = - HeaderChunkRegionTracker::AllocateRegion(&alloc, kArbitraryChunkSize); + HeaderChunkRegionTracker::AllocateRegion(&allocator, kArbitraryChunkSize); ASSERT_NE(tracker, nullptr); - EXPECT_EQ(alloc.count(), 1_size); + EXPECT_EQ(allocator.num_allocations(), 1_size); { std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*tracker); ASSERT_TRUE(chunk.has_value()); - EXPECT_EQ(alloc.count(), 2_size); + EXPECT_EQ(allocator.num_allocations(), 2_size); EXPECT_EQ(chunk->size(), kArbitraryChunkSize); } - EXPECT_EQ(alloc.count(), 0_size); - EXPECT_EQ(alloc.used(), 0_size); + EXPECT_EQ(allocator.num_deallocations(), 2_size); + EXPECT_EQ(allocator.allocated_bytes(), 0_size); } TEST(Chunk, DiscardFrontDiscardsFrontOfSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -106,9 +106,9 @@ TEST(Chunk, DiscardFrontDiscardsFrontOfSpan) { } TEST(Chunk, TakeFrontTakesFrontOfSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -124,9 +124,9 @@ TEST(Chunk, TakeFrontTakesFrontOfSpan) { } TEST(Chunk, TruncateDiscardsEndOfSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -138,9 +138,9 @@ TEST(Chunk, TruncateDiscardsEndOfSpan) { } TEST(Chunk, TakeTailTakesEndOfSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -156,9 +156,9 @@ TEST(Chunk, TakeTailTakesEndOfSpan) { } TEST(Chunk, SliceRemovesSidesOfSpan) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -171,30 +171,30 @@ TEST(Chunk, SliceRemovesSidesOfSpan) { } TEST(Chunk, RegionPersistsUntilAllChunksReleased) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + 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(alloc.count(), 2_size); + EXPECT_EQ(allocator.num_allocations(), 2_size); const size_t kSplitPoint = 13; auto split_opt = chunk->TakeFront(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(alloc.count(), 3_size); + EXPECT_EQ(allocator.num_allocations(), 3_size); chunk.Release(); - EXPECT_EQ(alloc.count(), 2_size); + EXPECT_EQ(allocator.num_deallocations(), 1_size); split.Release(); - EXPECT_EQ(alloc.count(), 0_size); + EXPECT_EQ(allocator.num_deallocations(), 3_size); } TEST(Chunk, ClaimPrefixReclaimsDiscardedFront) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -207,9 +207,9 @@ TEST(Chunk, ClaimPrefixReclaimsDiscardedFront) { } TEST(Chunk, ClaimPrefixFailsOnFullRegionChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -217,9 +217,9 @@ TEST(Chunk, ClaimPrefixFailsOnFullRegionChunk) { } TEST(Chunk, ClaimPrefixFailsOnNeighboringChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -231,9 +231,9 @@ TEST(Chunk, ClaimPrefixFailsOnNeighboringChunk) { TEST(Chunk, ClaimPrefixFailsAtStartOfRegionEvenAfterReleasingChunkAtEndOfRegion) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -245,9 +245,9 @@ TEST(Chunk, } TEST(Chunk, ClaimPrefixReclaimsPrecedingChunksDiscardedSuffix) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -262,9 +262,9 @@ TEST(Chunk, ClaimPrefixReclaimsPrecedingChunksDiscardedSuffix) { } TEST(Chunk, ClaimSuffixReclaimsTruncatedEnd) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -277,9 +277,9 @@ TEST(Chunk, ClaimSuffixReclaimsTruncatedEnd) { } TEST(Chunk, ClaimSuffixFailsOnFullRegionChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -287,9 +287,9 @@ TEST(Chunk, ClaimSuffixFailsOnFullRegionChunk) { } TEST(Chunk, ClaimSuffixFailsWithNeighboringChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -301,9 +301,9 @@ TEST(Chunk, ClaimSuffixFailsWithNeighboringChunk) { } TEST(Chunk, ClaimSuffixFailsAtEndOfRegionEvenAfterReleasingFirstChunkInRegion) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -315,9 +315,9 @@ TEST(Chunk, ClaimSuffixFailsAtEndOfRegionEvenAfterReleasingFirstChunkInRegion) { } TEST(Chunk, ClaimSuffixReclaimsFollowingChunksDiscardedPrefix) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_opt.has_value()); auto& chunk = *chunk_opt; @@ -332,14 +332,14 @@ TEST(Chunk, ClaimSuffixReclaimsFollowingChunksDiscardedPrefix) { } TEST(Chunk, MergeReturnsFalseForChunksFromDifferentRegions) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_1_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + 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(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_2_opt.has_value()); OwnedChunk& chunk_2 = *chunk_2_opt; @@ -354,9 +354,9 @@ TEST(Chunk, MergeReturnsFalseForNonAdjacentChunksFromSameRegion) { const size_t kTakenFromOne = 8; const size_t kTakenFromTwo = 4; - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_1_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_1_opt.has_value()); OwnedChunk& chunk_1 = *chunk_1_opt; @@ -380,9 +380,9 @@ TEST(Chunk, MergeJoinsMultipleAdjacentChunksFromSameRegion) { const size_t kTakenFromOne = 8; const size_t kTakenFromTwo = 4; - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_1_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_1_opt.has_value()); OwnedChunk& chunk_1 = *chunk_1_opt; @@ -408,9 +408,9 @@ TEST(Chunk, MergeJoinsMultipleAdjacentChunksFromSameRegion) { TEST(Chunk, MergeJoinsAdjacentChunksFromSameRegion) { const size_t kTaken = 4; - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; std::optional<OwnedChunk> chunk_1_opt = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, + HeaderChunkRegionTracker::AllocateRegionAsChunk(&allocator, kArbitraryChunkSize); ASSERT_TRUE(chunk_1_opt.has_value()); OwnedChunk& chunk_1 = *chunk_1_opt; diff --git a/pw_multibuf/docs.rst b/pw_multibuf/docs.rst index e19f8e7ce..8d3d22931 100644 --- a/pw_multibuf/docs.rst +++ b/pw_multibuf/docs.rst @@ -85,3 +85,21 @@ These users will also need to understand and implement the following APIs: .. doxygenclass:: pw::multibuf::ChunkRegionTracker :members: + +A simple implementation of a ``ChunkRegionTracker`` is provided, called +``HeaderChunkRegionTracker``. It stores its ``Chunk`` and region metadata in a +``Allocator`` allocation alongside the data. The allocation process is +synchronous, making this class suitable for testing. The allocated region or +``Chunk`` must not outlive the provided allocator. + +.. doxygenclass:: pw::multibuf::HeaderChunkRegionTracker + :members: + +Another ``ChunkRegionTracker`` specialization is the lightweight +``SingleChunkRegionTracker``, which does not rely on ``Allocator`` and uses the +provided memory view to create a single chunk. This is useful when a single +``Chunk`` is sufficient at no extra overhead. However, the user needs to own +the provided memory and know when a new ``Chunk`` can be requested. + +.. doxygenclass:: pw::multibuf::SingleChunkRegionTracker + :members: diff --git a/pw_multibuf/multibuf_test.cc b/pw_multibuf/multibuf_test.cc index d1bfe969d..717db71c8 100644 --- a/pw_multibuf/multibuf_test.cc +++ b/pw_multibuf/multibuf_test.cc @@ -14,15 +14,16 @@ #include "pw_multibuf/multibuf.h" -#include "gtest/gtest.h" +#include "pw_allocator/allocator_testing.h" +#include "pw_assert/check.h" #include "pw_bytes/suffix.h" -#include "pw_multibuf/internal/test_utils.h" +#include "pw_multibuf/chunk_region_tracker.h" +#include "pw_unit_test/framework.h" namespace pw::multibuf { namespace { -using ::pw::multibuf::internal::HeaderChunkRegionTracker; -using ::pw::multibuf::internal::TrackingAllocatorWithMemory; +using ::pw::allocator::test::AllocatorForTest; const size_t kArbitraryAllocatorSize = 1024; const size_t kArbitraryChunkSize = 32; @@ -34,61 +35,61 @@ static_assert(std::forward_iterator<MultiBuf::ChunkIterator>); static_assert(std::forward_iterator<MultiBuf::ConstChunkIterator>); #endif // __cplusplus >= 202002L -OwnedChunk MakeChunk(pw::allocator::Allocator& alloc, size_t size) { +OwnedChunk MakeChunk(pw::allocator::Allocator* allocator, size_t size) { std::optional<OwnedChunk> chunk = - HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, size); - assert(chunk.has_value()); + HeaderChunkRegionTracker::AllocateRegionAsChunk(allocator, size); + PW_CHECK(chunk.has_value()); return std::move(*chunk); } TEST(MultiBuf, IsDefaultConstructible) { [[maybe_unused]] MultiBuf buf; } TEST(MultiBuf, WithOneChunkReleases) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); - EXPECT_EQ(alloc.count(), 2U); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); + EXPECT_EQ(allocator.num_allocations(), 2U); buf.Release(); - EXPECT_EQ(alloc.count(), 0U); + EXPECT_EQ(allocator.num_deallocations(), 2U); } TEST(MultiBuf, WithOneChunkReleasesOnDestruction) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; { MultiBuf buf; - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); - EXPECT_EQ(alloc.count(), 2U); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); + EXPECT_EQ(allocator.num_allocations(), 2U); } - EXPECT_EQ(alloc.count(), 0U); + EXPECT_EQ(allocator.num_deallocations(), 2U); } TEST(MultiBuf, WithMultipleChunksReleasesAllOnDestruction) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; { MultiBuf buf; - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); - EXPECT_EQ(alloc.count(), 4U); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); + EXPECT_EQ(allocator.num_allocations(), 4U); } - EXPECT_EQ(alloc.count(), 0U); + EXPECT_EQ(allocator.num_deallocations(), 4U); } TEST(MultiBuf, SizeReturnsNumberOfBytes) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; EXPECT_EQ(buf.size(), 0U); - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); EXPECT_EQ(buf.size(), kArbitraryChunkSize); - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); EXPECT_EQ(buf.size(), kArbitraryChunkSize * 2); } TEST(MultiBuf, PushFrontChunkAddsBytesToFront) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; const std::array<std::byte, 3> kBytesOne = {0_b, 1_b, 2_b}; - auto chunk_one = MakeChunk(alloc, kBytesOne.size()); + auto chunk_one = MakeChunk(&allocator, kBytesOne.size()); std::copy(kBytesOne.begin(), kBytesOne.end(), chunk_one->begin()); buf.PushFrontChunk(std::move(chunk_one)); @@ -100,7 +101,7 @@ TEST(MultiBuf, PushFrontChunkAddsBytesToFront) { } const std::array<std::byte, 4> kBytesTwo = {9_b, 10_b, 11_b, 12_b}; - auto chunk_two = MakeChunk(alloc, kBytesTwo.size()); + auto chunk_two = MakeChunk(&allocator, kBytesTwo.size()); std::copy(kBytesTwo.begin(), kBytesTwo.end(), chunk_two->begin()); buf.PushFrontChunk(std::move(chunk_two)); @@ -122,11 +123,11 @@ TEST(MultiBuf, PushFrontChunkAddsBytesToFront) { } TEST(MultiBuf, InsertChunkOnEmptyBufAddsFirstChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; const std::array<std::byte, 3> kBytes = {0_b, 1_b, 2_b}; - auto chunk = MakeChunk(alloc, kBytes.size()); + auto chunk = MakeChunk(&allocator, kBytes.size()); std::copy(kBytes.begin(), kBytes.end(), chunk->begin()); auto inserted_iter = buf.InsertChunk(buf.Chunks().begin(), std::move(chunk)); EXPECT_EQ(inserted_iter, buf.Chunks().begin()); @@ -142,14 +143,14 @@ TEST(MultiBuf, InsertChunkOnEmptyBufAddsFirstChunk) { } TEST(MultiBuf, InsertChunkAtEndOfBufAddsLastChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; // Add a chunk to the beginning - buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize)); + buf.PushFrontChunk(MakeChunk(&allocator, kArbitraryChunkSize)); const std::array<std::byte, 3> kBytes = {0_b, 1_b, 2_b}; - auto chunk = MakeChunk(alloc, kBytes.size()); + auto chunk = MakeChunk(&allocator, kBytes.size()); std::copy(kBytes.begin(), kBytes.end(), chunk->begin()); auto inserted_iter = buf.InsertChunk(buf.Chunks().end(), std::move(chunk)); EXPECT_EQ(inserted_iter, ++buf.Chunks().begin()); @@ -166,11 +167,11 @@ TEST(MultiBuf, InsertChunkAtEndOfBufAddsLastChunk) { } TEST(MultiBuf, TakeChunkAtBeginRemovesAndReturnsFirstChunk) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; auto insert_iter = buf.Chunks().begin(); - insert_iter = buf.InsertChunk(insert_iter, MakeChunk(alloc, 2)); - insert_iter = buf.InsertChunk(++insert_iter, MakeChunk(alloc, 4)); + insert_iter = buf.InsertChunk(insert_iter, MakeChunk(&allocator, 2)); + insert_iter = buf.InsertChunk(++insert_iter, MakeChunk(&allocator, 4)); auto [chunk_iter, chunk] = buf.TakeChunk(buf.Chunks().begin()); EXPECT_EQ(chunk.size(), 2U); @@ -180,12 +181,12 @@ TEST(MultiBuf, TakeChunkAtBeginRemovesAndReturnsFirstChunk) { } TEST(MultiBuf, TakeChunkOnLastInsertedIterReturnsLastInserted) { - TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc; + AllocatorForTest<kArbitraryAllocatorSize> allocator; MultiBuf buf; auto iter = buf.Chunks().begin(); - iter = buf.InsertChunk(iter, MakeChunk(alloc, 42)); - iter = buf.InsertChunk(++iter, MakeChunk(alloc, 11)); - iter = buf.InsertChunk(++iter, MakeChunk(alloc, 65)); + iter = buf.InsertChunk(iter, MakeChunk(&allocator, 42)); + iter = buf.InsertChunk(++iter, MakeChunk(&allocator, 11)); + iter = buf.InsertChunk(++iter, MakeChunk(&allocator, 65)); OwnedChunk chunk; std::tie(iter, chunk) = buf.TakeChunk(iter); EXPECT_EQ(iter, buf.Chunks().end()); diff --git a/pw_multibuf/public/pw_multibuf/chunk.h b/pw_multibuf/public/pw_multibuf/chunk.h index 9747b944a..201f2d6ff 100644 --- a/pw_multibuf/public/pw_multibuf/chunk.h +++ b/pw_multibuf/public/pw_multibuf/chunk.h @@ -175,6 +175,7 @@ class Chunk { : region_tracker_(region_tracker), next_in_region_(nullptr), prev_in_region_(nullptr), + next_in_buf_(nullptr), span_(span) {} // NOTE: these functions are logically diff --git a/pw_multibuf/public/pw_multibuf/chunk_region_tracker.h b/pw_multibuf/public/pw_multibuf/chunk_region_tracker.h new file mode 100644 index 000000000..b741dc162 --- /dev/null +++ b/pw_multibuf/public/pw_multibuf/chunk_region_tracker.h @@ -0,0 +1,106 @@ +// 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. +#pragma once + +#include <cstddef> +#include <memory> +#include <optional> + +#include "pw_allocator/allocator.h" +#include "pw_bytes/span.h" +#include "pw_multibuf/chunk.h" + +namespace pw::multibuf { + +/// A ``ChunkRegionTracker`` which stores its ``Chunk`` and region metadata +/// in a ``allocator::Allocator`` allocation alongside the data. +/// +/// This is useful when testing and when there is no need for asynchronous +/// allocation. +class HeaderChunkRegionTracker final : public ChunkRegionTracker { + public: + /// Allocates a new ``Chunk`` region of ``size`` bytes in ``alloc``. + /// + /// The underlyiing allocation will also store the + /// ``HeaderChunkRegionTracker`` itself. The allocated memory must not outlive + /// the provided allocator ``alloc``. + /// + /// Returns the newly-created ``OwnedChunk`` if successful. + static std::optional<OwnedChunk> AllocateRegionAsChunk( + allocator::Allocator* alloc, size_t size) { + HeaderChunkRegionTracker* tracker = AllocateRegion(alloc, size); + if (tracker == nullptr) { + return std::nullopt; + } + std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*tracker); + if (!chunk.has_value()) { + tracker->Destroy(); + return std::nullopt; + } + return chunk; + } + + /// Allocates a new region of ``size`` bytes in ``alloc``. + /// + /// The underlyiing allocation will also store the + /// ``HeaderChunkRegionTracker`` itself. The allocated memory must not outlive + /// the provided allocator ``alloc``. + /// + /// Returns a pointer to the newly-created ``HeaderChunkRegionTracker`` + /// or ``nullptr`` if the allocation failed. + static HeaderChunkRegionTracker* AllocateRegion(allocator::Allocator* alloc, + size_t size) { + auto layout = + allocator::Layout::Of<HeaderChunkRegionTracker>().Extend(size); + void* ptr = alloc->Allocate(layout); + if (ptr == nullptr) { + return nullptr; + } + std::byte* data = + reinterpret_cast<std::byte*>(ptr) + sizeof(HeaderChunkRegionTracker); + return new (ptr) HeaderChunkRegionTracker(ByteSpan(data, size), alloc); + } + + ByteSpan Region() const final { return region_; } + ~HeaderChunkRegionTracker() final {} + + protected: + void Destroy() final { + std::byte* ptr = reinterpret_cast<std::byte*>(this); + auto layout = allocator::Layout::Of<HeaderChunkRegionTracker>().Extend( + region_.size()); + auto alloc = alloc_; + std::destroy_at(this); + alloc->Deallocate(ptr, layout); + } + + void* AllocateChunkClass() final { + return alloc_->Allocate(allocator::Layout::Of<Chunk>()); + } + + void DeallocateChunkClass(void* ptr) final { + alloc_->Deallocate(ptr, allocator::Layout::Of<Chunk>()); + } + + private: + ByteSpan region_; + allocator::Allocator* alloc_; + + // NOTE: `region` must directly follow this `FakeChunkRegionTracker` + // in memory allocated by allocated by `alloc`. + HeaderChunkRegionTracker(ByteSpan region, allocator::Allocator* alloc) + : region_(region), alloc_(alloc) {} +}; + +} // namespace pw::multibuf diff --git a/pw_multibuf/public/pw_multibuf/internal/test_utils.h b/pw_multibuf/public/pw_multibuf/internal/test_utils.h deleted file mode 100644 index 07e325016..000000000 --- a/pw_multibuf/public/pw_multibuf/internal/test_utils.h +++ /dev/null @@ -1,162 +0,0 @@ -// 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. - -#pragma once - -#include <memory> - -#include "pw_allocator/allocator_metric_proxy.h" -#include "pw_allocator/split_free_list_allocator.h" -#include "pw_multibuf/chunk.h" - -namespace pw::multibuf::internal { - -/// A basic ``Allocator`` implementation that reports the number and size of -/// allocations. -class TrackingAllocator : public pw::allocator::Allocator { - public: - /// Constructs a new ``TrackingAllocator`` which allocates from the provided - /// region of memory. - TrackingAllocator(ByteSpan span) : alloc_stats_(kFakeToken) { - Status status = alloc_.Init(span, kFakeThreshold); - EXPECT_EQ(status, OkStatus()); - alloc_stats_.Initialize(alloc_); - } - - /// Returns the number of current allocations. - size_t count() const { return alloc_stats_.count(); } - - /// Returns the combined size in bytes of all current allocations. - size_t used() const { return alloc_stats_.used(); } - - protected: - void* DoAllocate(allocator::Layout layout) override { - return alloc_stats_.Allocate(layout); - } - bool DoResize(void* ptr, - allocator::Layout old_layout, - size_t new_size) override { - return alloc_stats_.Resize(ptr, old_layout, new_size); - } - void DoDeallocate(void* ptr, allocator::Layout layout) override { - alloc_stats_.Deallocate(ptr, layout); - } - - private: - const size_t kFakeThreshold = 0; - const int32_t kFakeToken = 0; - - pw::allocator::SplitFreeListAllocator<> alloc_; - pw::allocator::AllocatorMetricProxy alloc_stats_; -}; - -/// A ``TrackingAllocator`` which holds an internal buffer of size `num_buffer` -/// for its allocations. -template <auto num_bytes> -class TrackingAllocatorWithMemory : public pw::allocator::Allocator { - public: - TrackingAllocatorWithMemory() : mem_(), alloc_(mem_) {} - size_t count() const { return alloc_.count(); } - size_t used() const { return alloc_.used(); } - void* DoAllocate(allocator::Layout layout) override { - return alloc_.Allocate(layout); - } - bool DoResize(void* ptr, - allocator::Layout old_layout, - size_t new_size) override { - return alloc_.Resize(ptr, old_layout, new_size); - } - void DoDeallocate(void* ptr, allocator::Layout layout) override { - alloc_.Deallocate(ptr, layout); - } - - private: - std::array<std::byte, num_bytes> mem_; - TrackingAllocator alloc_; -}; - -/// A ``ChunkRegionTracker`` which stores its ``Chunk`` and region metadata -/// in a ``pw::allocator::Allocator`` allocation alongside the data. -class HeaderChunkRegionTracker final : public ChunkRegionTracker { - public: - /// Allocates a new ``Chunk`` region of ``size`` bytes in ``alloc``. - /// - /// The underlyiing allocation will also store the - /// ``HeaderChunkRegionTracker`` itself. - /// - /// Returns the newly-created ``OwnedChunk`` if successful. - static std::optional<OwnedChunk> AllocateRegionAsChunk( - pw::allocator::Allocator* alloc, size_t size) { - HeaderChunkRegionTracker* tracker = AllocateRegion(alloc, size); - if (tracker == nullptr) { - return std::nullopt; - } - std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*tracker); - if (!chunk.has_value()) { - tracker->Destroy(); - return std::nullopt; - } - return chunk; - } - - /// Allocates a new ``Chunk`` region of ``size`` bytes in ``alloc``. - /// - /// The underlyiing allocation will also store the - /// ``HeaderChunkRegionTracker`` itself. - /// - /// Returns a pointer to the newly-created ``HeaderChunkRegionTracker`` - /// or ``nullptr`` if the allocation failed. - static HeaderChunkRegionTracker* AllocateRegion( - pw::allocator::Allocator* alloc, size_t size) { - auto layout = - allocator::Layout::Of<HeaderChunkRegionTracker>().Extend(size); - void* ptr = alloc->Allocate(layout); - if (ptr == nullptr) { - return nullptr; - } - std::byte* data = - reinterpret_cast<std::byte*>(ptr) + sizeof(HeaderChunkRegionTracker); - return new (ptr) HeaderChunkRegionTracker(ByteSpan(data, size), alloc); - } - - ByteSpan Region() const final { return region_; } - ~HeaderChunkRegionTracker() final {} - - protected: - void Destroy() final { - std::byte* ptr = reinterpret_cast<std::byte*>(this); - auto layout = allocator::Layout::Of<HeaderChunkRegionTracker>().Extend( - region_.size()); - auto alloc = alloc_; - std::destroy_at(this); - alloc->Deallocate(ptr, layout); - } - void* AllocateChunkClass() final { - return alloc_->Allocate(pw::allocator::Layout::Of<Chunk>()); - } - void DeallocateChunkClass(void* ptr) final { - alloc_->Deallocate(ptr, pw::allocator::Layout::Of<Chunk>()); - } - - private: - ByteSpan region_; - pw::allocator::Allocator* alloc_; - - // NOTE: `region` must directly follow this `FakeChunkRegionTracker` - // in memory allocated by allocated by `alloc`. - HeaderChunkRegionTracker(ByteSpan region, pw::allocator::Allocator* alloc) - : region_(region), alloc_(alloc) {} -}; - -} // namespace pw::multibuf::internal diff --git a/pw_multibuf/public/pw_multibuf/single_chunk_region_tracker.h b/pw_multibuf/public/pw_multibuf/single_chunk_region_tracker.h new file mode 100644 index 000000000..bde12c247 --- /dev/null +++ b/pw_multibuf/public/pw_multibuf/single_chunk_region_tracker.h @@ -0,0 +1,82 @@ +// Copyright 2024 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. +#pragma once + +#include <atomic> +#include <cstring> +#include <optional> + +#include "pw_assert/assert.h" +#include "pw_bytes/span.h" +#include "pw_multibuf/chunk.h" + +namespace pw::multibuf { + +/// A `ChunkRegionTracker` that uses inline memory to create a single `Chunk` +/// with the only caveat that the provided `Chunk` cannot be split. All attempts +/// will result in `std::nullopt`. +class SingleChunkRegionTracker : public ChunkRegionTracker { + public: + /// Constructs a region tracker with a single `Chunk` that maps to `region`, + /// which must outlive this tracker and any `OwnedChunk` it creates. + explicit SingleChunkRegionTracker(ByteSpan region) : region_(region) {} + ~SingleChunkRegionTracker() override { Destroy(); } + + /// Gets a `Chunk` of a given size, which must be less than or equal to the + /// provided region. + /// + /// Returns: + /// An `OwnedChunk` if the `Chunk` is free, otherwise `std::nullopt`, in + /// which case `GetChunk()` can be called again. + std::optional<OwnedChunk> GetChunk(size_t size) { + PW_DASSERT(size <= region_.size()); + // Since this is a single `Chunk` region, re-create the first `Chunk` is + // allowed if freed. + std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*this); + if (chunk.has_value() && size < region_.size()) { + (*chunk)->Truncate(size); + } + return chunk; + } + + void Destroy() final { + // Nothing to release here. + PW_ASSERT(!chunk_in_use_); + } + + ByteSpan Region() const final { return region_; } + + void* AllocateChunkClass() final { + bool in_use = false; + if (!chunk_in_use_.compare_exchange_strong(in_use, true)) { + return nullptr; + } + return &chunk_storage_; + } + + void DeallocateChunkClass(void* chunk) final { + PW_ASSERT(chunk == chunk_storage_.data()); + // Mark the `Chunk` as not in use and zero-out the region and chunk storage. + std::memset(chunk_storage_.data(), 0, chunk_storage_.size()); + std::memset(region_.data(), 0, region_.size()); + chunk_in_use_ = false; + } + + private: + ByteSpan region_; + std::atomic<bool> chunk_in_use_ = false; + alignas(Chunk) std::array<std::byte, sizeof(Chunk)> chunk_storage_; +}; + +} // namespace pw::multibuf diff --git a/pw_multibuf/single_chunk_region_tracker_test.cc b/pw_multibuf/single_chunk_region_tracker_test.cc new file mode 100644 index 000000000..d02163a45 --- /dev/null +++ b/pw_multibuf/single_chunk_region_tracker_test.cc @@ -0,0 +1,77 @@ +// 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/single_chunk_region_tracker.h" + +#include <cstddef> +#include <optional> + +#include "pw_multibuf/chunk.h" +#include "pw_unit_test/framework.h" + +namespace pw::multibuf { +namespace { + +const size_t kArbitraryRegionSize = 1024; +const size_t kArbitraryChunkSize = 32; + +TEST(SingleChunkRegionTrackerTest, GetChunkSmallerThanRegionSuccess) { + std::array<std::byte, kArbitraryRegionSize> chunk_storage{}; + SingleChunkRegionTracker chunk_tracker(chunk_storage); + std::optional<OwnedChunk> chunk = chunk_tracker.GetChunk(kArbitraryChunkSize); + EXPECT_TRUE(chunk.has_value()); + EXPECT_EQ(chunk->size(), kArbitraryChunkSize); +} + +TEST(SingleChunkRegionTrackerTest, GetChunkSameSizeAsRegionSuccess) { + std::array<std::byte, kArbitraryRegionSize> chunk_storage{}; + SingleChunkRegionTracker chunk_tracker(chunk_storage); + std::optional<OwnedChunk> chunk = + chunk_tracker.GetChunk(kArbitraryRegionSize); + EXPECT_TRUE(chunk.has_value()); + EXPECT_EQ(chunk->size(), kArbitraryRegionSize); +} + +TEST(SingleChunkRegionTrackerTest, GetChunkFailChunkInUse) { + std::array<std::byte, kArbitraryRegionSize> chunk_storage{}; + SingleChunkRegionTracker chunk_tracker(chunk_storage); + std::optional<OwnedChunk> chunk1 = + chunk_tracker.GetChunk(kArbitraryChunkSize); + ASSERT_TRUE(chunk1.has_value()); + + std::optional<OwnedChunk> chunk2 = + chunk_tracker.GetChunk(kArbitraryChunkSize); + EXPECT_FALSE(chunk2.has_value()); +} + +TEST(SingleChunkRegionTrackerTest, GetChunkAfterReleasedChunkSuccess) { + std::array<std::byte, kArbitraryRegionSize> chunk_storage{}; + SingleChunkRegionTracker chunk_tracker(chunk_storage); + std::optional<OwnedChunk> chunk1 = + chunk_tracker.GetChunk(kArbitraryChunkSize); + ASSERT_TRUE(chunk1.has_value()); + + std::optional<OwnedChunk> chunk2 = + chunk_tracker.GetChunk(kArbitraryChunkSize); + ASSERT_FALSE(chunk2.has_value()); + + chunk1->Release(); + + std::optional<OwnedChunk> chunk3 = + chunk_tracker.GetChunk(kArbitraryChunkSize); + EXPECT_TRUE(chunk3.has_value()); +} + +} // namespace +} // namespace pw::multibuf |