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 <variant> 18 19 #include "pw_allocator/allocator.h" 20 #include "pw_containers/vector.h" 21 #include "pw_random/random.h" 22 23 namespace pw::allocator::test { 24 25 /// Represents a request to allocate some memory. 26 struct AllocationRequest { 27 size_t size = 0; 28 size_t alignment = 1; 29 }; 30 31 /// Represents a request to free some allocated memory. 32 struct DeallocationRequest { 33 size_t index = 0; 34 }; 35 36 /// Represents a request to reallocate allocated memory with a new size. 37 struct ReallocationRequest { 38 size_t index = 0; 39 size_t new_size = 0; 40 }; 41 42 using Request = 43 std::variant<AllocationRequest, DeallocationRequest, ReallocationRequest>; 44 45 /// Helper function to produce a valid alignment for a given `size` from an 46 /// arbitrary left shift amount. 47 size_t AlignmentFromLShift(size_t lshift, size_t size); 48 49 /// Associates an `Allocator` with a vector to store allocated pointers. 50 /// 51 /// This class facilitates performing allocations from generated 52 /// `Request`s, enabling the creation of performance, stress, and fuzz 53 /// tests for various allocators. 54 /// 55 /// This class lacks a public constructor, and so cannot be used directly. 56 /// Instead callers should use `WithAllocations`, which is templated on the 57 /// size of the vector used to store allocated pointers. 58 class TestHarnessGeneric { 59 public: 60 /// Since this object has references passed to it that are typically owned by 61 /// an object of a derived type, the destructor MUST NOT touch those 62 /// references. Instead, it is the callers and/or the derived classes 63 /// responsibility to call `Reset` before the object is destroyed, if desired. 64 virtual ~TestHarnessGeneric() = default; 65 66 /// Generates and handles a sequence of allocation requests. 67 /// 68 /// This method will use the given PRNG to generate `num_requests` allocation 69 /// requests and pass each in turn to `HandleRequest`. It will call `Reset` 70 /// before returning. 71 void GenerateRequests(random::RandomGenerator& prng, 72 size_t max_size, 73 size_t num_requests); 74 75 /// Generate and handle an allocation requests. 76 /// 77 /// This method will use the given PRNG to generate an allocation request 78 /// and pass it to `HandleRequest`. Callers *MUST* call `Reset` when no more 79 /// requests remain to be generated. 80 void GenerateRequest(random::RandomGenerator& prng, size_t max_size); 81 82 /// Handles a sequence of allocation requests. 83 /// 84 /// This method is useful for processing externally generated requests, e.g. 85 /// from FuzzTest. It will call `Reset` before returning. 86 void HandleRequests(const Vector<Request>& requests); 87 88 /// Handles an allocator request. 89 /// 90 /// This method is stateful, and modifies the vector of allocated pointers. 91 /// It will call `Init` if it has not yet been called. 92 /// 93 /// If the request is an allocation request: 94 /// * If the vector of previous allocations is full, ignores the request. 95 /// * Otherwise, allocates memory and stores the pointer in the vector. 96 /// 97 /// If the request is a deallocation request: 98 /// * If the vector of previous allocations is empty, ignores the request. 99 /// * Otherwise, removes a pointer from the vector and deallocates it. 100 /// 101 /// If the request is a reallocation request: 102 /// * If the vector of previous allocations is empty, reallocates a `nullptr`. 103 /// * Otherwise, removes a pointer from the vector and reallocates it. 104 void HandleRequest(const Request& request); 105 106 /// Deallocates any pointers stored in the vector of allocated pointers. 107 void Reset(); 108 109 protected: 110 /// Associates a pointer to memory with the `Layout` used to allocate it. 111 struct Allocation { 112 void* ptr; 113 Layout layout; 114 }; 115 TestHarnessGeneric(Vector<Allocation> & allocations)116 constexpr TestHarnessGeneric(Vector<Allocation>& allocations) 117 : allocations_(allocations) {} 118 119 private: 120 virtual Allocator* Init() = 0; 121 122 /// Adds a pointer to the vector of allocated pointers. 123 /// 124 /// The `ptr` must not be null, and the vector of allocated pointers must not 125 /// be full. To aid in detecting memory corruptions and in debugging, the 126 /// pointed-at memory will be filled with as much of the following sequence as 127 /// will fit: 128 /// * The request number. 129 /// * The request size. 130 /// * The byte "0x5a", repeating. 131 void AddAllocation(void* ptr, Layout layout); 132 133 /// Removes and returns a previously allocated pointer. 134 /// 135 /// The vector of allocated pointers must not be empty. 136 Allocation RemoveAllocation(size_t index); 137 138 /// An allocator used to manage memory. 139 Allocator* allocator_ = nullptr; 140 141 /// A vector of allocated pointers. 142 Vector<Allocation>& allocations_; 143 144 /// The number of requests this object has handled. 145 size_t num_requests_ = 0; 146 }; 147 148 /// Associates an `Allocator` with a vector to store allocated pointers. 149 /// 150 /// This class differes from its base class only in that it uses its template 151 /// parameter to explicitly size the vector used to store allocated pointers. 152 /// 153 /// This class does NOT implement `WithAllocationsGeneric::Init`. It must be 154 /// extended further with a method that provides an initialized allocator. 155 /// 156 /// For example, one create a fuzzer for `MyAllocator` that verifies it never 157 /// crashes by adding the following class, function, and macro: 158 /// @code{.cpp} 159 /// constexpr size_t kMaxRequests = 256; 160 /// constexpr size_t kMaxAllocations = 128; 161 /// constexpr size_t kMaxSize = 2048; 162 /// 163 /// class MyAllocatorFuzzer : public TestHarness<kMaxAllocations> { 164 /// private: 165 /// Allocator* Init() override { return &allocator_; } 166 /// MyAllocator allocator_; 167 /// }; 168 /// 169 /// void MyAllocatorNeverCrashes(const Vector<Request>& requests) { 170 /// static MyAllocatorFuzzer fuzzer; 171 /// fuzzer.HandleRequests(requests); 172 /// } 173 /// 174 /// FUZZ_TEST(MyAllocator, MyAllocatorNeverCrashes) 175 /// .WithDomains(ArbitraryRequests<kMaxRequests, kMaxSize>()); 176 /// @endcode 177 template <size_t kMaxConcurrentAllocations> 178 class TestHarness : public TestHarnessGeneric { 179 public: TestHarness()180 constexpr TestHarness() : TestHarnessGeneric(allocations_) {} 181 182 private: 183 Vector<Allocation, kMaxConcurrentAllocations> allocations_; 184 }; 185 186 } // namespace pw::allocator::test 187