1 // Copyright 2024 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 #pragma once
15
16 #include <cstddef>
17 #include <optional>
18
19 #include "pw_allocator/benchmarks/measurements.h"
20 #include "pw_allocator/fragmentation.h"
21 #include "pw_allocator/layout.h"
22 #include "pw_allocator/test_harness.h"
23 #include "pw_chrono/system_clock.h"
24 #include "pw_metric/metric.h"
25 #include "pw_tokenizer/tokenize.h"
26
27 namespace pw::allocator {
28 namespace internal {
29
30 /// Base class for benchmarking block allocators.
31 ///
32 /// This class extends the test harness to sample data relevant to benchmarking
33 /// the performance of a blockallocator before and after each request. It is not
34 /// templated and avoids any types related to the specific block allocator.
35 ///
36 /// Callers should not use this class directly, and instead using
37 /// `BlockAllocatorBenchmark`.
38 class GenericBlockAllocatorBenchmark : public pw::allocator::test::TestHarness {
39 public:
metrics()40 metric::Group& metrics() { return measurements_.metrics(); }
measurements()41 Measurements& measurements() { return measurements_; }
42
43 protected:
GenericBlockAllocatorBenchmark(Measurements & measurements)44 constexpr explicit GenericBlockAllocatorBenchmark(Measurements& measurements)
45 : measurements_(measurements) {}
46
47 private:
48 /// @copydoc test::TestHarness::BeforeAllocate
49 void BeforeAllocate(const Layout& layout) override;
50
51 /// @copydoc test::TestHarness::BeforeAllocate
52 void AfterAllocate(const void* ptr) override;
53
54 /// @copydoc test::TestHarness::BeforeAllocate
55 void BeforeDeallocate(const void* ptr) override;
56
57 /// @copydoc test::TestHarness::BeforeAllocate
58 void AfterDeallocate() override;
59
60 /// @copydoc test::TestHarness::BeforeAllocate
61 void BeforeReallocate(const Layout& layout) override;
62
63 /// @copydoc test::TestHarness::BeforeAllocate
64 void AfterReallocate(const void* new_ptr) override;
65
66 /// Preparse to benchmark an allocator request.
67 void DoBefore();
68
69 /// Finishes benchmarking an allocator request.
70 void DoAfter();
71
72 /// Updates the `measurements` with data from an allocator request.
73 void Update();
74
75 /// Returns the inner size of block from is usable space.
76 virtual size_t GetBlockInnerSize(const void* ptr) const = 0;
77
78 /// Iterates over an allocators blocks and collects benchmark data.
79 virtual void IterateOverBlocks(BenchmarkSample& data) const = 0;
80
81 /// Measures the current fragmentation of an allocator.
82 virtual Fragmentation GetBlockFragmentation() const = 0;
83
84 std::optional<chrono::SystemClock::time_point> start_;
85 size_t num_allocations_ = 0;
86 size_t size_ = 0;
87 BenchmarkSample data_;
88 Measurements& measurements_;
89 };
90
91 } // namespace internal
92
93 /// test harness used for benchmarking block allocators.
94 ///
95 /// This class records measurements aggregated from benchmarking samples of a
96 /// sequence of block allocator requests. The `Measurements` objects must
97 /// outlive the benchmark test harness.
98 ///
99 /// @tparam AllocatorType Type of the block allocator being benchmarked.
100 template <typename AllocatorType>
101 class BlockAllocatorBenchmark
102 : public internal::GenericBlockAllocatorBenchmark {
103 public:
BlockAllocatorBenchmark(Measurements & measurements,AllocatorType & allocator)104 BlockAllocatorBenchmark(Measurements& measurements, AllocatorType& allocator)
105 : internal::GenericBlockAllocatorBenchmark(measurements),
106 allocator_(allocator) {}
107
108 private:
109 using BlockType = typename AllocatorType::BlockType;
110
111 /// @copydoc test::TestHarness::Init
Init()112 Allocator* Init() override { return &allocator_; }
113
114 /// @copydoc GenericBlockAllocatorBenchmark::GetBlockInnerSize
115 size_t GetBlockInnerSize(const void* ptr) const override;
116
117 /// @copydoc GenericBlockAllocatorBenchmark::IterateOverBlocks
118 void IterateOverBlocks(internal::BenchmarkSample& data) const override;
119
120 /// @copydoc GenericBlockAllocatorBenchmark::GetBlockFragmentation
121 Fragmentation GetBlockFragmentation() const override;
122
123 AllocatorType& allocator_;
124 };
125
126 /// Block allocator benchmark that use a default set of measurements
127 ///
128 /// This class simplifies the set up of a block allocator benchmark by defining
129 /// a default set of metrics and linking all the relevant metrics together.
130 template <typename AllocatorType>
131 class DefaultBlockAllocatorBenchmark
132 : public BlockAllocatorBenchmark<AllocatorType> {
133 public:
DefaultBlockAllocatorBenchmark(metric::Token name,AllocatorType & allocator)134 DefaultBlockAllocatorBenchmark(metric::Token name, AllocatorType& allocator)
135 : BlockAllocatorBenchmark<AllocatorType>(measurements_, allocator),
136 measurements_(name) {}
137
138 private:
139 DefaultMeasurements measurements_;
140 };
141
142 // Template method implementations
143
144 template <typename AllocatorType>
GetBlockInnerSize(const void * ptr)145 size_t BlockAllocatorBenchmark<AllocatorType>::GetBlockInnerSize(
146 const void* ptr) const {
147 const auto* block = BlockType::FromUsableSpace(ptr);
148 return block->InnerSize();
149 }
150
151 template <typename AllocatorType>
IterateOverBlocks(internal::BenchmarkSample & data)152 void BlockAllocatorBenchmark<AllocatorType>::IterateOverBlocks(
153 internal::BenchmarkSample& data) const {
154 data.largest = 0;
155 for (const auto* block : allocator_.blocks()) {
156 if (block->IsFree()) {
157 data.largest = std::max(data.largest, block->InnerSize());
158 }
159 }
160 }
161
162 template <typename AllocatorType>
GetBlockFragmentation()163 Fragmentation BlockAllocatorBenchmark<AllocatorType>::GetBlockFragmentation()
164 const {
165 return allocator_.MeasureFragmentation();
166 }
167
168 } // namespace pw::allocator
169