/*
 * Copyright © 2021 The Fuchsia Authors
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 */

#include "simple_allocator.h"

#include <stdint.h>
#include <stdio.h>
#include <memory>

#define LOG_VERBOSE(msg, ...) do { \
    if (true) \
        fprintf(stderr, "%s:%d " msg "\n", __FILE__, __LINE__, ##__VA_ARGS__); \
        fflush(stderr); \
} while (0)

bool SimpleAllocator::CheckGap(SimpleAllocator::Region* prev, SimpleAllocator::Region* next,
                               uint64_t align, size_t size, uint64_t* addr_out,
                               bool* continue_search_out) {
  assert(addr_out);
  assert(continue_search_out);

  uint64_t gap_begin = prev ? (prev->base + prev->size) : base();
  uint64_t gap_end;  // last byte of a gap

  if (next) {
    if (gap_begin == next->base) {
      *continue_search_out = true;
      return false;
    }
    gap_end = next->base - 1;
  } else {
    if (gap_begin == base() + this->size()) {
      *continue_search_out = false;
      return false;
    }
    gap_end = base() + this->size() - 1;
  }

  *addr_out = RoundUp(gap_begin, align);

  if (*addr_out < gap_begin) {
    *continue_search_out = false;
    return false;
  }

  if (*addr_out < gap_end && ((gap_end - *addr_out + 1) >= size))
    return true;

  *continue_search_out = true;
  return false;
}

//////////////////////////////////////////////////////////////////////////////

SimpleAllocator::Region::Region(uint64_t base_in, size_t size_in) : base(base_in), size(size_in) {
  assert(size > 0);
  assert(base + size - 1 >= base);
}

std::unique_ptr<SimpleAllocator> SimpleAllocator::Create(uint64_t base, size_t size) {
  return std::unique_ptr<SimpleAllocator>(new SimpleAllocator(base, size));
}

SimpleAllocator::SimpleAllocator(uint64_t base, size_t size) : AddressSpaceAllocator(base, size) {}

bool SimpleAllocator::Alloc(size_t size, uint8_t align_pow2, uint64_t* addr_out) {
  assert(addr_out);

  size = RoundUp(size, size_t{GetPageSize()});
  if (size == 0) {
    LOG_VERBOSE("Can't allocate size zero");
    return false;
  }

  assert(IsPageAligned(size));

  uint32_t local_align_pow = align_pow2;
  const uint32_t page_shift = PageShift();
  if (align_pow2 < page_shift) {
    local_align_pow = page_shift;
  }

  uint64_t align = 1UL << local_align_pow;
  uint64_t addr;
  bool continue_search;

  // try to pick spot at the beginning of address space
  if (CheckGap(nullptr, regions_.empty() ? nullptr : &regions_.front(), align, size, &addr,
               &continue_search)) {
    *addr_out = addr;
    regions_.emplace_front(addr, size);
    return true;
  }

  // search the middle of the list
  for (auto iter = regions_.begin(); continue_search && iter != regions_.end();) {
    auto prev = &(*iter);
    auto next = (++iter == regions_.end()) ? nullptr : &(*iter);
    if (CheckGap(prev, next, align, size, &addr, &continue_search)) {
      *addr_out = addr;
      regions_.insert(iter, Region(addr, size));
      return true;
    }
  }

  LOG_VERBOSE("Failed to allocate");
  return false;
}

bool SimpleAllocator::Free(uint64_t addr) {
  auto iter = FindRegion(addr);
  if (iter == regions_.end()) {
      LOG_VERBOSE("Couldn't find region to free");
      return false;
  }

  regions_.erase(iter);

  return true;
}

bool SimpleAllocator::GetSize(uint64_t addr, size_t* size_out) {
  auto iter = FindRegion(addr);
  if (iter == regions_.end()) {
      LOG_VERBOSE("Couldn't find region");
      return false;
  }

  *size_out = iter->size;
  return true;
}

std::list<SimpleAllocator::Region>::iterator SimpleAllocator::FindRegion(uint64_t addr) {
  for (auto iter = regions_.begin(); iter != regions_.end(); iter++) {
    auto region = *iter;
    if ((addr >= region.base) && (addr <= region.base + region.size - 1))
      return iter;
  }

  return regions_.end();
}