// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <lib/trivial-allocator/basic-leaky-allocator.h>
#include <lib/trivial-allocator/single-heap-allocator.h>

#include <gtest/gtest.h>

namespace {

// Hide the pointer's value from the compiler so it doesn't think it knows any
// special invariants about it.  For example, the [[gnu::malloc]] attribute on
// the allocate() function lets the compiler assume that the returned pointer
// does not overlap with any other pointer known to the compiler.
template <typename T>
T* Launder(T* ptr) {
  __asm__("" : "=r"(ptr) : "0"(ptr));
  return ptr;
}

TEST(TrivialAllocatorTests, BasicLeakyAllocator) {
  alignas(16) std::byte backing_data[128];
  trivial_allocator::SingleHeapAllocator backing_allocator({backing_data});
  trivial_allocator::BasicLeakyAllocator allocator(backing_allocator);

  void* ptr = allocator.allocate(16);
  ASSERT_TRUE(ptr);

  // We should be able to return the one chunk and recover the space each time.
  for (int i = 0; i < 100; ++i) {
    allocator.deallocate(ptr);
    ptr = allocator.allocate(16);
    ASSERT_TRUE(ptr) << "attempt " << i;
  }
  allocator.deallocate(ptr);

  ptr = allocator.allocate(32, 16);
  EXPECT_TRUE(ptr);
  EXPECT_EQ(0u, reinterpret_cast<uintptr_t>(ptr) % 16);
  allocator.deallocate(ptr);

  for (int i = 0; i < 128 / 32; ++i) {
    ptr = allocator.allocate(32);
    EXPECT_TRUE(ptr) << "attempt " << i;
  }
  ptr = allocator.allocate(32);
  EXPECT_FALSE(ptr);

  // No-op.
  allocator.deallocate(nullptr);

  // Since backing_data is aligned to 16, 1 element into it is definitely
  // misaligned.
  cpp20::span misaligned_backing_data = cpp20::span(backing_data).subspan(1);
  trivial_allocator::SingleHeapAllocator misaligned_backing_allocator(misaligned_backing_data);
  trivial_allocator::BasicLeakyAllocator misaligned_allocator(misaligned_backing_allocator);

  // Allocating with no alignment requirement should be happy with the first
  // possible chunk.
  ptr = misaligned_allocator.allocate(1, 1);
  EXPECT_TRUE(ptr);
  ptr = Launder(ptr);  // Don't let the compiler assume anything.
  EXPECT_EQ(ptr, misaligned_backing_data.data());

  auto expect_aligned_to = [&backing_data](void* ptr, size_t alignment) {
    ptr = Launder(ptr);  // Don't let the compiler assume anything.
    void* align_check = ptr;
    size_t align_avail = &backing_data[sizeof(backing_data)] - static_cast<std::byte*>(ptr);
    EXPECT_EQ(std::align(alignment, alignment, align_check, align_avail), ptr);
  };

  // Allocating with a large required alignment should still work.
  ptr = misaligned_allocator.allocate(32, 32);
  EXPECT_TRUE(ptr);
  expect_aligned_to(ptr, 32);

  const std::array align_test_chunks = {
      // First, a well-aligned chunk only big enough for the first allocation.
      cpp20::span(backing_data).subspan(0, 16),
      // Second, a misaligned chunk big enough for the second allocation.
      cpp20::span(backing_data).subspan(17, 31),
      // Third, a misaligned chunk big enough for the third allocation but not
      // big enough to make it aligned.
      cpp20::span(backing_data).subspan(49, 16),
      // Finally, an aligned chunk that's just big enough for pessimistic
      // overalignment.
      cpp20::span(backing_data).subspan(80, 31),
  };
  auto align_test_heap = [chunks = cpp20::span<const cpp20::span<std::byte>>(align_test_chunks)](
                             size_t& size, size_t alignment) mutable {
    cpp20::span<std::byte> chunk;
    if (!chunks.empty()) {
      chunk = chunks.front();
      chunks = chunks.subspan(1);
    }
    return trivial_allocator::SingleHeapAllocator(chunk)(size, alignment);
  };
  trivial_allocator::BasicLeakyAllocator align_test_allocator(align_test_heap);

  // First allocation consumes first chunk.
  ptr = align_test_allocator.allocate(16, 16);
  EXPECT_TRUE(ptr);
  expect_aligned_to(ptr, 16);

  // Second allocation consumes second chunk.
  ptr = align_test_allocator.allocate(16, 16);
  EXPECT_TRUE(ptr);
  expect_aligned_to(ptr, 16);

  // Third allocation skips remainder of third chunk and uses fourth.
  ptr = align_test_allocator.allocate(16, 16);
  EXPECT_TRUE(ptr);
  expect_aligned_to(ptr, 16);

  // Fourth allocation consumes remainder of third chunk.
  ptr = align_test_allocator.allocate(15, 1);
  EXPECT_TRUE(ptr);

  // Should now be fresh out of chunks.
  ptr = align_test_allocator.allocate(1, 1);
  EXPECT_FALSE(ptr);
}

}  // namespace