pw_allocator/public/pw_allocator/test_harness.h

// 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 <variant>

#include "pw_allocator/allocator.h"
#include "pw_containers/vector.h"
#include "pw_random/random.h"

namespace pw::allocator::test {

/// Represents a request to allocate some memory.
struct AllocationRequest {
  size_t size = 0;
  size_t alignment = 1;
};

/// Represents a request to free some allocated memory.
struct DeallocationRequest {
  size_t index = 0;
};

/// Represents a request to reallocate allocated memory with a new size.
struct ReallocationRequest {
  size_t index = 0;
  size_t new_size = 0;
};

using AllocatorRequest =
    std::variant<AllocationRequest, DeallocationRequest, ReallocationRequest>;

/// Helper function to produce a valid alignment for a given `size` from an
/// arbitrary left shift amount.
size_t AlignmentFromLShift(size_t lshift, size_t size);

/// Associates an `Allocator` with a vector to store allocated pointers.
///
/// This class facilitates performing allocations from generated
/// `AllocatorRequest`s, enabling the creation of performance, stress, and fuzz
/// tests for various allocators.
///
/// This class lacks a public constructor, and so cannot be used directly.
/// Instead callers should use `WithAllocations`, which is templated on the
/// size of the vector used to store allocated pointers.
class AllocatorTestHarnessGeneric {
 public:
  /// Since this object has references passed to it that are typically owned by
  /// an object of a derived type, the destructor MUST NOT touch those
  /// references. Instead, it is the callers and/or the derived classes
  /// responsibility to call `Reset` before the object is destroyed, if desired.
  virtual ~AllocatorTestHarnessGeneric() = default;

  /// Generates and handles a sequence of allocation requests.
  ///
  /// This method will use the given PRNG to generate `num_requests` allocation
  /// requests and pass each in turn to `HandleRequest`. It will call `Reset`
  /// before returning.
  void GenerateRequests(random::RandomGenerator& prng,
                        size_t max_size,
                        size_t num_requests);

  /// Generate and handle an allocation requests.
  ///
  /// This method will use the given PRNG to generate an allocation request
  /// and pass it to `HandleRequest`. Callers *MUST* call `Reset` when no more
  /// requests remain to be generated.
  void GenerateRequest(random::RandomGenerator& prng, size_t max_size);

  /// Handles a sequence of allocation requests.
  ///
  /// This method is useful for processing externally generated requests, e.g.
  /// from FuzzTest. It will call `Reset` before returning.
  void HandleRequests(const Vector<AllocatorRequest>& requests);

  /// Handles an allocator request.
  ///
  /// This method is stateful, and modifies the vector of allocated pointers.
  /// It will call `Init` if it has not yet been called.
  ///
  /// If the request is an allocation request:
  /// * If the vector of previous allocations is full, ignores the request.
  /// * Otherwise, allocates memory and stores the pointer in the vector.
  ///
  /// If the request is a deallocation request:
  /// * If the vector of previous allocations is empty, ignores the request.
  /// * Otherwise, removes a pointer from the vector and deallocates it.
  ///
  /// If the request is a reallocation request:
  /// * If the vector of previous allocations is empty, reallocates a `nullptr`.
  /// * Otherwise, removes a pointer from the vector and reallocates it.
  void HandleRequest(const AllocatorRequest& request);

  /// Deallocates any pointers stored in the vector of allocated pointers.
  void Reset();

 protected:
  /// Associates a pointer to memory with the `Layout` used to allocate it.
  struct Allocation {
    void* ptr;
    Layout layout;
  };

  constexpr AllocatorTestHarnessGeneric(Vector<Allocation>& allocations)
      : allocations_(allocations) {}

 private:
  virtual Allocator* Init() = 0;

  /// Adds a pointer to the vector of allocated pointers.
  ///
  /// The `ptr` must not be null, and the vector of allocated pointers must not
  /// be full. To aid in detecting memory corruptions and in debugging, the
  /// pointed-at memory will be filled with as much of the following sequence as
  /// will fit:
  /// * The request number.
  /// * The request size.
  /// * The byte "0x5a", repeating.
  void AddAllocation(void* ptr, Layout layout);

  /// Removes and returns a previously allocated pointer.
  ///
  /// The vector of allocated pointers must not be empty.
  Allocation RemoveAllocation(size_t index);

  /// An allocator used to manage memory.
  Allocator* allocator_ = nullptr;

  /// A vector of allocated pointers.
  Vector<Allocation>& allocations_;

  /// The number of requests this object has handled.
  size_t num_requests_ = 0;
};

/// Associates an `Allocator` with a vector to store allocated pointers.
///
/// This class differes from its base class only in that it uses its template
/// parameter to explicitly size the vector used to store allocated pointers.
///
/// This class does NOT implement `WithAllocationsGeneric::Init`. It must be
/// extended further with a method that provides an initialized allocator.
///
/// For example, one create a fuzzer for `MyAllocator` that verifies it never
/// crashes by adding the following class, function, and macro:
/// @code{.cpp}
///   constexpr size_t kMaxRequests = 256;
///   constexpr size_t kMaxAllocations = 128;
///   constexpr size_t kMaxSize = 2048;
///
///   class MyAllocatorFuzzer : public AllocatorTestHarness<kMaxAllocations> {
///    private:
///     Allocator* Init() override { return &allocator_; }
///     MyAllocator allocator_;
///   };
///
///   void MyAllocatorNeverCrashes(const Vector<AllocatorRequest>& requests) {
///     static MyAllocatorFuzzer fuzzer;
///     fuzzer.HandleRequests(requests);
///   }
///
///   FUZZ_TEST(MyAllocator, MyAllocatorNeverCrashes)
///     .WithDomains(ArbitraryAllocatorRequests<kMaxRequests, kMaxSize>());
/// @endcode
template <size_t kMaxConcurrentAllocations>
class AllocatorTestHarness : public AllocatorTestHarnessGeneric {
 public:
  constexpr AllocatorTestHarness()
      : AllocatorTestHarnessGeneric(allocations_) {}

 private:
  Vector<Allocation, kMaxConcurrentAllocations> allocations_;
};

}  // namespace pw::allocator::test