1 // Copyright 2023 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 #include <variant> 19 20 #include "pw_allocator/allocator.h" 21 #include "pw_containers/intrusive_list.h" 22 #include "pw_containers/vector.h" 23 #include "pw_random/xor_shift.h" 24 25 namespace pw::allocator::test { 26 27 /// Represents a request to allocate some memory. 28 struct AllocationRequest { 29 size_t size = 0; 30 size_t alignment = 1; 31 }; 32 33 /// Represents a request to free some allocated memory. 34 struct DeallocationRequest { 35 size_t index = 0; 36 }; 37 38 /// Represents a request to reallocate allocated memory with a new size. 39 struct ReallocationRequest { 40 size_t index = 0; 41 size_t new_size = 0; 42 }; 43 44 using Request = 45 std::variant<AllocationRequest, DeallocationRequest, ReallocationRequest>; 46 47 /// Helper function to produce a valid alignment for a given `size` from an 48 /// arbitrary left shift amount. 49 size_t AlignmentFromLShift(size_t lshift, size_t size); 50 51 /// Associates an `Allocator` with a list to store allocated pointers. 52 /// 53 /// This class facilitates performing allocations from generated 54 /// `Request`s, enabling the creation of performance, stress, and fuzz 55 /// tests for various allocators. 56 /// 57 /// This class does NOT implement `TestHarness::Init`. It must be extended 58 /// further with a method that provides an initialized allocator. 59 /// 60 /// For example, one can create a fuzzer for `MyAllocator` that verifies it 61 /// never crashes by adding the following class, function, and macro: 62 /// @code{.cpp} 63 /// constexpr size_t kMaxRequests = 256; 64 /// constexpr size_t kMaxAllocations = 128; 65 /// constexpr size_t kMaxSize = 2048; 66 /// 67 /// class MyAllocatorFuzzer : public TestHarness { 68 /// private: 69 /// Allocator* Init() override { return &allocator_; } 70 /// MyAllocator allocator_; 71 /// }; 72 /// 73 /// void MyAllocatorNeverCrashes(const Vector<Request>& requests) { 74 /// static MyAllocatorFuzzer fuzzer; 75 /// fuzzer.HandleRequests(requests); 76 /// } 77 /// 78 /// FUZZ_TEST(MyAllocator, MyAllocatorNeverCrashes) 79 /// .WithDomains(ArbitraryRequests<kMaxRequests, kMaxSize>()); 80 /// @endcode 81 class TestHarness { 82 public: 83 /// Associates a pointer to memory with the `Layout` used to allocate it. 84 struct Allocation : public IntrusiveList<Allocation>::Item { 85 Layout layout; 86 AllocationAllocation87 explicit Allocation(Layout layout_) : layout(layout_) {} 88 }; 89 90 virtual ~TestHarness() = default; 91 num_allocations()92 size_t num_allocations() const { return num_allocations_; } allocated()93 size_t allocated() const { return allocated_; } 94 set_prng_seed(uint64_t seed)95 void set_prng_seed(uint64_t seed) { prng_ = random::XorShiftStarRng64(seed); } set_available(size_t available)96 void set_available(size_t available) { available_ = available; } 97 98 /// Generates and handles a sequence of allocation requests. 99 /// 100 /// This method will use the given PRNG to generate `num_requests` allocation 101 /// requests and pass each in turn to `HandleRequest`. It will call `Reset` 102 /// before returning. 103 void GenerateRequests(size_t max_size, size_t num_requests); 104 105 /// Generate and handle an allocation requests. 106 /// 107 /// This method will use the given PRNG to generate an allocation request 108 /// and pass it to `HandleRequest`. Callers *MUST* call `Reset` when no more 109 /// requests remain to be generated. 110 void GenerateRequest(size_t max_size); 111 112 /// Handles a sequence of allocation requests. 113 /// 114 /// This method is useful for processing externally generated requests, e.g. 115 /// from FuzzTest. It will call `Reset` before returning. 116 void HandleRequests(const Vector<Request>& requests); 117 118 /// Handles an allocator request. 119 /// 120 /// This method is stateful, and modifies the vector of allocated pointers. 121 /// It will call `Init` if it has not yet been called. 122 /// 123 /// If the request is an allocation request: 124 /// * If the vector of previous allocations is full, ignores the request. 125 /// * Otherwise, allocates memory and stores the pointer in the vector. 126 /// 127 /// If the request is a deallocation request: 128 /// * If the vector of previous allocations is empty, ignores the request. 129 /// * Otherwise, removes a pointer from the vector and deallocates it. 130 /// 131 /// If the request is a reallocation request: 132 /// * If the vector of previous allocations is empty, reallocates a `nullptr`. 133 /// * Otherwise, removes a pointer from the vector and reallocates it. 134 /// 135 /// Returns whether the request was handled. This is different from whether 136 /// the request succeeded, e.g. a DeallocationRequest cannot be handled when 137 /// there are no current allocations and will return false. By contrast, an 138 /// AllocationRequest may be handled, but fail due to insufficient memory, and 139 /// will return true. 140 bool HandleRequest(const Request& request); 141 142 /// Deallocates any pointers stored in the vector of allocated pointers. 143 void Reset(); 144 145 private: 146 virtual Allocator* Init() = 0; 147 148 /// Generate requests. `set_prng_seed` must have been called first. 149 AllocationRequest GenerateAllocationRequest(size_t max_size); 150 DeallocationRequest GenerateDeallocationRequest(); 151 ReallocationRequest GenerateReallocationRequest(size_t max_size); 152 size_t GenerateSize(size_t max_size); 153 154 /// Derived classes may add callbacks that are invoked before and after each 155 /// de/re/allocation to record additional data about the allocator. BeforeAllocate(const Layout &)156 virtual void BeforeAllocate(const Layout&) {} AfterAllocate(const void *)157 virtual void AfterAllocate(const void*) {} BeforeReallocate(const Layout &)158 virtual void BeforeReallocate(const Layout&) {} AfterReallocate(const void *)159 virtual void AfterReallocate(const void*) {} BeforeDeallocate(const void *)160 virtual void BeforeDeallocate(const void*) {} AfterDeallocate()161 virtual void AfterDeallocate() {} 162 163 /// Adds a pointer to the vector of allocated pointers. 164 /// 165 /// The `ptr` must not be null, and the vector of allocated pointers must not 166 /// be full. To aid in detecting memory corruptions and in debugging, the 167 /// pointed-at memory will be filled with as much of the following sequence as 168 /// will fit: 169 /// * The request number.random::RandomGenerator& prng 170 /// * The request size. 171 /// * The byte "0x5a", repeating. 172 void AddAllocation(void* ptr, Layout layout); 173 174 /// Removes and returns a previously allocated pointer. 175 /// 176 /// The vector of allocated pointers must not be empty. 177 Allocation* RemoveAllocation(size_t index); 178 179 /// An allocator used to manage memory. 180 Allocator* allocator_ = nullptr; 181 182 /// A list of allocated pointers. 183 IntrusiveList<Allocation> allocations_; 184 185 /// The number of outstanding active allocation by this object. 186 size_t num_allocations_ = 0; 187 188 /// The total memory allocated. 189 size_t allocated_ = 0; 190 191 /// An optional amount of memory available. If set, this is used to adjust the 192 /// likelihood of what requests are generated based on how much of the 193 /// available memory has been used. 194 std::optional<size_t> available_; 195 196 /// Pseudorandom number generator. 197 std::optional<random::XorShiftStarRng64> prng_; 198 199 /// If an allocation fails, the next generated request is limited to half the 200 /// previous request's size. 201 std::optional<size_t> max_size_; 202 }; 203 204 } // namespace pw::allocator::test 205