pw_allocator/test_harness.cc

// 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_allocator/test_harness.h"

#include <algorithm>
#include <climits>
#include <cstdint>
#include <type_traits>

#include "lib/stdcompat/bit.h"
#include "pw_assert/check.h"

namespace pw::allocator::test {
namespace {

// Helper to allow static_assert'ing in constexpr-if branches, e.g. that a
// visitor for a std::variant are exhaustive.
template <typename T>
constexpr bool not_reached(T&) {
  return false;
}

AllocationRequest GenerateAllocationRequest(random::RandomGenerator& prng,
                                            size_t max_size) {
  AllocationRequest request;
  if (max_size != 0) {
    prng.GetInt(request.size);
    request.size %= max_size;
  }
  uint8_t lshift;
  prng.GetInt(lshift);
  request.alignment = AlignmentFromLShift(lshift, request.size);
  return request;
}

DeallocationRequest GenerateDeallocationRequest(random::RandomGenerator& prng) {
  DeallocationRequest request;
  prng.GetInt(request.index);
  return request;
}

ReallocationRequest GenerateReallocationRequest(random::RandomGenerator& prng,
                                                size_t max_size) {
  ReallocationRequest request;
  prng.GetInt(request.index);
  if (max_size != 0) {
    prng.GetInt(request.new_size);
    request.new_size %= max_size;
  }
  return request;
}

}  // namespace

size_t AlignmentFromLShift(size_t lshift, size_t size) {
  constexpr size_t max_bits = (sizeof(size) * CHAR_BIT) - 1;
  size_t num_bits =
      size == 0 ? 1 : std::min(size_t(cpp20::bit_width(size)), max_bits);
  return 1U << (lshift % num_bits);
}

void AllocatorTestHarnessGeneric::GenerateRequests(
    random::RandomGenerator& prng, size_t max_size, size_t num_requests) {
  for (size_t i = 0; i < num_requests; ++i) {
    GenerateRequest(prng, max_size);
  }
  Reset();
}

void AllocatorTestHarnessGeneric::GenerateRequest(random::RandomGenerator& prng,
                                                  size_t max_size) {
  AllocatorRequest request;
  size_t request_type;
  prng.GetInt(request_type);
  switch (request_type % 3) {
    case 0:
      request = GenerateAllocationRequest(prng, max_size);
      break;
    case 1:
      request = GenerateDeallocationRequest(prng);
      break;
    case 2:
      request = GenerateReallocationRequest(prng, max_size);
      break;
  }
  HandleRequest(request);
}

void AllocatorTestHarnessGeneric::HandleRequests(
    const Vector<AllocatorRequest>& requests) {
  for (const auto& request : requests) {
    HandleRequest(request);
  }
  Reset();
}

void AllocatorTestHarnessGeneric::HandleRequest(
    const AllocatorRequest& request) {
  if (allocator_ == nullptr) {
    allocator_ = Init();
    PW_DCHECK_NOTNULL(allocator_);
  }
  std::visit(
      [this](auto&& r) {
        using T = std::decay_t<decltype(r)>;

        if constexpr (std::is_same_v<T, AllocationRequest>) {
          if (allocations_.size() < allocations_.max_size()) {
            Layout layout(r.size, r.alignment);
            void* ptr = allocator_->Allocate(layout);
            if (ptr != nullptr) {
              AddAllocation(ptr, layout);
            }
          }

        } else if constexpr (std::is_same_v<T, DeallocationRequest>) {
          if (!allocations_.empty()) {
            Allocation old = RemoveAllocation(r.index);
            allocator_->Deallocate(old.ptr);
          }

        } else if constexpr (std::is_same_v<T, ReallocationRequest>) {
          if (!allocations_.empty()) {
            Allocation old = RemoveAllocation(r.index);
            Layout new_layout = Layout(r.new_size, old.layout.alignment());
            void* new_ptr = allocator_->Reallocate(old.ptr, new_layout);
            if (new_ptr == nullptr) {
              AddAllocation(old.ptr, old.layout);
            } else {
              AddAllocation(new_ptr, new_layout);
            }
          }
        } else {
          static_assert(not_reached(r), "unsupported request type!");
        }
      },
      request);
}

void AllocatorTestHarnessGeneric::Reset() {
  if (allocator_ == nullptr) {
    return;
  }
  for (const Allocation& old : allocations_) {
    allocator_->Deallocate(old.ptr);
  }
  allocations_.clear();
}

void AllocatorTestHarnessGeneric::AddAllocation(void* ptr, Layout layout) {
  auto* bytes = static_cast<std::byte*>(ptr);
  size_t left = layout.size();

  // Record the request number in the allocated memory to aid in debugging.
  ++num_requests_;
  if (left >= sizeof(num_requests_)) {
    std::memcpy(bytes, &num_requests_, sizeof(num_requests_));
    left -= sizeof(num_requests_);
  }

  // Record the allocation size in the allocated memory to aid in debugging.
  size_t size = layout.size();
  if (left >= sizeof(size)) {
    std::memcpy(bytes, &size, sizeof(size));
    left -= sizeof(size);
  }

  // Fill the remaining memory with data.
  if (left > 0) {
    std::memset(bytes, 0x5A, left);
  }

  allocations_.emplace_back(Allocation{ptr, layout});
}

AllocatorTestHarnessGeneric::Allocation
AllocatorTestHarnessGeneric::RemoveAllocation(size_t index) {
  // Move the target allocation to the back of the list.
  index %= allocations_.size();
  std::swap(allocations_.at(index), allocations_.back());

  // Copy and remove the targeted allocation.
  Allocation old(allocations_.back());
  allocations_.pop_back();
  return old;
}

}  // namespace pw::allocator::test