// Copyright 2014 The Chromium 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 "base/memory/discardable_memory_ashmem_allocator.h"

#include <sys/mman.h>
#include <unistd.h>

#include <algorithm>
#include <cmath>
#include <limits>
#include <set>
#include <utility>

#include "base/basictypes.h"
#include "base/containers/hash_tables.h"
#include "base/files/file_util.h"
#include "base/files/scoped_file.h"
#include "base/logging.h"
#include "base/memory/scoped_vector.h"
#include "third_party/ashmem/ashmem.h"

// The allocator consists of three parts (classes):
// - DiscardableMemoryAshmemAllocator: entry point of all allocations (through
// its Allocate() method) that are dispatched to the AshmemRegion instances
// (which it owns).
// - AshmemRegion: manages allocations and destructions inside a single large
// (e.g. 32 MBytes) ashmem region.
// - DiscardableAshmemChunk: class mimicking the DiscardableMemory interface
// whose instances are returned to the client.

namespace base {
namespace {

// Only tolerate fragmentation in used chunks *caused by the client* (as opposed
// to the allocator when a free chunk is reused). The client can cause such
// fragmentation by e.g. requesting 4097 bytes. This size would be rounded up to
// 8192 by the allocator which would cause 4095 bytes of fragmentation (which is
// currently the maximum allowed). If the client requests 4096 bytes and a free
// chunk of 8192 bytes is available then the free chunk gets splitted into two
// pieces to minimize fragmentation (since 8192 - 4096 = 4096 which is greater
// than 4095).
// TODO(pliard): tune this if splitting chunks too often leads to performance
// issues.
const size_t kMaxChunkFragmentationBytes = 4096 - 1;

const size_t kMinAshmemRegionSize = 32 * 1024 * 1024;

// Returns 0 if the provided size is too high to be aligned.
size_t AlignToNextPage(size_t size) {
  const size_t kPageSize = 4096;
  DCHECK_EQ(static_cast<int>(kPageSize), getpagesize());
  if (size > std::numeric_limits<size_t>::max() - kPageSize + 1)
    return 0;
  const size_t mask = ~(kPageSize - 1);
  return (size + kPageSize - 1) & mask;
}

bool CreateAshmemRegion(const char* name,
                        size_t size,
                        int* out_fd,
                        uintptr_t* out_address) {
  base::ScopedFD fd(ashmem_create_region(name, size));
  if (!fd.is_valid()) {
    DLOG(ERROR) << "ashmem_create_region() failed";
    return false;
  }

  const int err = ashmem_set_prot_region(fd.get(), PROT_READ | PROT_WRITE);
  if (err < 0) {
    DLOG(ERROR) << "Error " << err << " when setting protection of ashmem";
    return false;
  }

  // There is a problem using MAP_PRIVATE here. As we are constantly calling
  // Lock() and Unlock(), data could get lost if they are not written to the
  // underlying file when Unlock() gets called.
  void* const address = mmap(
      NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd.get(), 0);
  if (address == MAP_FAILED) {
    DPLOG(ERROR) << "Failed to map memory.";
    return false;
  }

  *out_fd = fd.release();
  *out_address = reinterpret_cast<uintptr_t>(address);
  return true;
}

bool CloseAshmemRegion(int fd, size_t size, void* address) {
  if (munmap(address, size) == -1) {
    DPLOG(ERROR) << "Failed to unmap memory.";
    close(fd);
    return false;
  }
  return close(fd) == 0;
}

bool LockAshmemRegion(int fd, size_t off, size_t size) {
  return ashmem_pin_region(fd, off, size) != ASHMEM_WAS_PURGED;
}

bool UnlockAshmemRegion(int fd, size_t off, size_t size) {
  const int failed = ashmem_unpin_region(fd, off, size);
  if (failed)
    DLOG(ERROR) << "Failed to unpin memory.";
  return !failed;
}

}  // namespace

namespace internal {

class AshmemRegion {
 public:
  // Note that |allocator| must outlive |this|.
  static scoped_ptr<AshmemRegion> Create(
      size_t size,
      const std::string& name,
      DiscardableMemoryAshmemAllocator* allocator) {
    DCHECK_EQ(size, AlignToNextPage(size));
    int fd;
    uintptr_t base;
    if (!CreateAshmemRegion(name.c_str(), size, &fd, &base))
      return scoped_ptr<AshmemRegion>();
    return make_scoped_ptr(new AshmemRegion(fd, size, base, allocator));
  }

  ~AshmemRegion() {
    const bool result = CloseAshmemRegion(
        fd_, size_, reinterpret_cast<void*>(base_));
    DCHECK(result);
    DCHECK(!highest_allocated_chunk_);
  }

  // Returns a new instance of DiscardableAshmemChunk whose size is greater or
  // equal than |actual_size| (which is expected to be greater or equal than
  // |client_requested_size|).
  // Allocation works as follows:
  // 1) Reuse a previously freed chunk and return it if it succeeded. See
  // ReuseFreeChunk_Locked() below for more information.
  // 2) If no free chunk could be reused and the region is not big enough for
  // the requested size then NULL is returned.
  // 3) If there is enough room in the ashmem region then a new chunk is
  // returned. This new chunk starts at |offset_| which is the end of the
  // previously highest chunk in the region.
  scoped_ptr<DiscardableAshmemChunk> Allocate_Locked(
      size_t client_requested_size,
      size_t actual_size) {
    DCHECK_LE(client_requested_size, actual_size);
    allocator_->lock_.AssertAcquired();

    // Check that the |highest_allocated_chunk_| field doesn't contain a stale
    // pointer. It should point to either a free chunk or a used chunk.
    DCHECK(!highest_allocated_chunk_ ||
           address_to_free_chunk_map_.find(highest_allocated_chunk_) !=
               address_to_free_chunk_map_.end() ||
           used_to_previous_chunk_map_.find(highest_allocated_chunk_) !=
               used_to_previous_chunk_map_.end());

    scoped_ptr<DiscardableAshmemChunk> memory = ReuseFreeChunk_Locked(
        client_requested_size, actual_size);
    if (memory)
      return memory.Pass();

    if (size_ - offset_ < actual_size) {
      // This region does not have enough space left to hold the requested size.
      return scoped_ptr<DiscardableAshmemChunk>();
    }

    uintptr_t const address = base_ + offset_;
    memory.reset(
        new DiscardableAshmemChunk(this, fd_, reinterpret_cast<void*>(address),
                                   offset_, actual_size));

    used_to_previous_chunk_map_.insert(
        std::make_pair(address, highest_allocated_chunk_));
    highest_allocated_chunk_ = reinterpret_cast<uintptr_t>(address);
    offset_ += actual_size;
    DCHECK_LE(offset_, size_);
    return memory.Pass();
  }

  void OnChunkDeletion(uintptr_t chunk, size_t size) {
    AutoLock auto_lock(allocator_->lock_);
    MergeAndAddFreeChunk_Locked(chunk, size);
    // Note that |this| might be deleted beyond this point.
  }

 private:
  struct FreeChunk {
    FreeChunk() : previous_chunk(0), start(0), size(0) {}

    explicit FreeChunk(size_t size)
        : previous_chunk(0),
          start(0),
          size(size) {
    }

    FreeChunk(uintptr_t previous_chunk, uintptr_t start, size_t size)
        : previous_chunk(previous_chunk),
          start(start),
          size(size) {
      DCHECK_LT(previous_chunk, start);
    }

    uintptr_t const previous_chunk;
    uintptr_t const start;
    const size_t size;

    bool is_null() const { return !start; }

    bool operator<(const FreeChunk& other) const {
      return size < other.size;
    }
  };

  // Note that |allocator| must outlive |this|.
  AshmemRegion(int fd,
               size_t size,
               uintptr_t base,
               DiscardableMemoryAshmemAllocator* allocator)
      : fd_(fd),
        size_(size),
        base_(base),
        allocator_(allocator),
        highest_allocated_chunk_(0),
        offset_(0) {
    DCHECK_GE(fd_, 0);
    DCHECK_GE(size, kMinAshmemRegionSize);
    DCHECK(base);
    DCHECK(allocator);
  }

  // Tries to reuse a previously freed chunk by doing a closest size match.
  scoped_ptr<DiscardableAshmemChunk> ReuseFreeChunk_Locked(
      size_t client_requested_size,
      size_t actual_size) {
    allocator_->lock_.AssertAcquired();
    const FreeChunk reused_chunk = RemoveFreeChunkFromIterator_Locked(
        free_chunks_.lower_bound(FreeChunk(actual_size)));
    if (reused_chunk.is_null())
      return scoped_ptr<DiscardableAshmemChunk>();

    used_to_previous_chunk_map_.insert(
        std::make_pair(reused_chunk.start, reused_chunk.previous_chunk));
    size_t reused_chunk_size = reused_chunk.size;
    // |client_requested_size| is used below rather than |actual_size| to
    // reflect the amount of bytes that would not be usable by the client (i.e.
    // wasted). Using |actual_size| instead would not allow us to detect
    // fragmentation caused by the client if he did misaligned allocations.
    DCHECK_GE(reused_chunk.size, client_requested_size);
    const size_t fragmentation_bytes =
        reused_chunk.size - client_requested_size;

    if (fragmentation_bytes > kMaxChunkFragmentationBytes) {
      // Split the free chunk being recycled so that its unused tail doesn't get
      // reused (i.e. locked) which would prevent it from being evicted under
      // memory pressure.
      reused_chunk_size = actual_size;
      uintptr_t const new_chunk_start = reused_chunk.start + actual_size;
      if (reused_chunk.start == highest_allocated_chunk_) {
        // We also need to update the pointer to the highest allocated chunk in
        // case we are splitting the highest chunk.
        highest_allocated_chunk_ = new_chunk_start;
      }
      DCHECK_GT(reused_chunk.size, actual_size);
      const size_t new_chunk_size = reused_chunk.size - actual_size;
      // Note that merging is not needed here since there can't be contiguous
      // free chunks at this point.
      AddFreeChunk_Locked(
          FreeChunk(reused_chunk.start, new_chunk_start, new_chunk_size));
    }

    const size_t offset = reused_chunk.start - base_;
    LockAshmemRegion(fd_, offset, reused_chunk_size);
    scoped_ptr<DiscardableAshmemChunk> memory(
        new DiscardableAshmemChunk(this, fd_,
                                   reinterpret_cast<void*>(reused_chunk.start),
                                   offset, reused_chunk_size));
    return memory.Pass();
  }

  // Makes the chunk identified with the provided arguments free and possibly
  // merges this chunk with the previous and next contiguous ones.
  // If the provided chunk is the only one used (and going to be freed) in the
  // region then the internal ashmem region is closed so that the underlying
  // physical pages are immediately released.
  // Note that free chunks are unlocked therefore they can be reclaimed by the
  // kernel if needed (under memory pressure) but they are not immediately
  // released unfortunately since madvise(MADV_REMOVE) and
  // fallocate(FALLOC_FL_PUNCH_HOLE) don't seem to work on ashmem. This might
  // change in versions of kernel >=3.5 though. The fact that free chunks are
  // not immediately released is the reason why we are trying to minimize
  // fragmentation in order not to cause "artificial" memory pressure.
  void MergeAndAddFreeChunk_Locked(uintptr_t chunk, size_t size) {
    allocator_->lock_.AssertAcquired();
    size_t new_free_chunk_size = size;
    // Merge with the previous chunk.
    uintptr_t first_free_chunk = chunk;
    DCHECK(!used_to_previous_chunk_map_.empty());
    const hash_map<uintptr_t, uintptr_t>::iterator previous_chunk_it =
        used_to_previous_chunk_map_.find(chunk);
    DCHECK(previous_chunk_it != used_to_previous_chunk_map_.end());
    uintptr_t previous_chunk = previous_chunk_it->second;
    used_to_previous_chunk_map_.erase(previous_chunk_it);

    if (previous_chunk) {
      const FreeChunk free_chunk = RemoveFreeChunk_Locked(previous_chunk);
      if (!free_chunk.is_null()) {
        new_free_chunk_size += free_chunk.size;
        first_free_chunk = previous_chunk;
        if (chunk == highest_allocated_chunk_)
          highest_allocated_chunk_ = previous_chunk;

        // There should not be more contiguous previous free chunks.
        previous_chunk = free_chunk.previous_chunk;
        DCHECK(!address_to_free_chunk_map_.count(previous_chunk));
      }
    }

    // Merge with the next chunk if free and present.
    uintptr_t next_chunk = chunk + size;
    const FreeChunk next_free_chunk = RemoveFreeChunk_Locked(next_chunk);
    if (!next_free_chunk.is_null()) {
      new_free_chunk_size += next_free_chunk.size;
      if (next_free_chunk.start == highest_allocated_chunk_)
        highest_allocated_chunk_ = first_free_chunk;

      // Same as above.
      DCHECK(
          !address_to_free_chunk_map_.count(next_chunk + next_free_chunk.size));
    }

    const bool whole_ashmem_region_is_free =
        used_to_previous_chunk_map_.empty();
    if (!whole_ashmem_region_is_free) {
      AddFreeChunk_Locked(
          FreeChunk(previous_chunk, first_free_chunk, new_free_chunk_size));
      return;
    }

    // The whole ashmem region is free thus it can be deleted.
    DCHECK_EQ(base_, first_free_chunk);
    DCHECK_EQ(base_, highest_allocated_chunk_);
    DCHECK(free_chunks_.empty());
    DCHECK(address_to_free_chunk_map_.empty());
    DCHECK(used_to_previous_chunk_map_.empty());
    highest_allocated_chunk_ = 0;
    allocator_->DeleteAshmemRegion_Locked(this);  // Deletes |this|.
  }

  void AddFreeChunk_Locked(const FreeChunk& free_chunk) {
    allocator_->lock_.AssertAcquired();
    const std::multiset<FreeChunk>::iterator it = free_chunks_.insert(
        free_chunk);
    address_to_free_chunk_map_.insert(std::make_pair(free_chunk.start, it));
    // Update the next used contiguous chunk, if any, since its previous chunk
    // may have changed due to free chunks merging/splitting.
    uintptr_t const next_used_contiguous_chunk =
        free_chunk.start + free_chunk.size;
    hash_map<uintptr_t, uintptr_t>::iterator previous_it =
        used_to_previous_chunk_map_.find(next_used_contiguous_chunk);
    if (previous_it != used_to_previous_chunk_map_.end())
      previous_it->second = free_chunk.start;
  }

  // Finds and removes the free chunk, if any, whose start address is
  // |chunk_start|. Returns a copy of the unlinked free chunk or a free chunk
  // whose content is null if it was not found.
  FreeChunk RemoveFreeChunk_Locked(uintptr_t chunk_start) {
    allocator_->lock_.AssertAcquired();
    const hash_map<
        uintptr_t, std::multiset<FreeChunk>::iterator>::iterator it =
            address_to_free_chunk_map_.find(chunk_start);
    if (it == address_to_free_chunk_map_.end())
      return FreeChunk();
    return RemoveFreeChunkFromIterator_Locked(it->second);
  }

  // Same as above but takes an iterator in.
  FreeChunk RemoveFreeChunkFromIterator_Locked(
      std::multiset<FreeChunk>::iterator free_chunk_it) {
    allocator_->lock_.AssertAcquired();
    if (free_chunk_it == free_chunks_.end())
      return FreeChunk();
    DCHECK(free_chunk_it != free_chunks_.end());
    const FreeChunk free_chunk(*free_chunk_it);
    address_to_free_chunk_map_.erase(free_chunk_it->start);
    free_chunks_.erase(free_chunk_it);
    return free_chunk;
  }

  const int fd_;
  const size_t size_;
  uintptr_t const base_;
  DiscardableMemoryAshmemAllocator* const allocator_;
  // Points to the chunk with the highest address in the region. This pointer
  // needs to be carefully updated when chunks are merged/split.
  uintptr_t highest_allocated_chunk_;
  // Points to the end of |highest_allocated_chunk_|.
  size_t offset_;
  // Allows free chunks recycling (lookup, insertion and removal) in O(log N).
  // Note that FreeChunk values are indexed by their size and also note that
  // multiple free chunks can have the same size (which is why multiset<> is
  // used instead of e.g. set<>).
  std::multiset<FreeChunk> free_chunks_;
  // Used while merging free contiguous chunks to erase free chunks (from their
  // start address) in constant time. Note that multiset<>::{insert,erase}()
  // don't invalidate iterators (except the one for the element being removed
  // obviously).
  hash_map<
      uintptr_t, std::multiset<FreeChunk>::iterator> address_to_free_chunk_map_;
  // Maps the address of *used* chunks to the address of their previous
  // contiguous chunk.
  hash_map<uintptr_t, uintptr_t> used_to_previous_chunk_map_;

  DISALLOW_COPY_AND_ASSIGN(AshmemRegion);
};

DiscardableAshmemChunk::~DiscardableAshmemChunk() {
  if (locked_)
    UnlockAshmemRegion(fd_, offset_, size_);
  ashmem_region_->OnChunkDeletion(reinterpret_cast<uintptr_t>(address_), size_);
}

bool DiscardableAshmemChunk::Lock() {
  DCHECK(!locked_);
  locked_ = true;
  return LockAshmemRegion(fd_, offset_, size_);
}

void DiscardableAshmemChunk::Unlock() {
  DCHECK(locked_);
  locked_ = false;
  UnlockAshmemRegion(fd_, offset_, size_);
}

void* DiscardableAshmemChunk::Memory() const {
  return address_;
}

// Note that |ashmem_region| must outlive |this|.
DiscardableAshmemChunk::DiscardableAshmemChunk(AshmemRegion* ashmem_region,
                                               int fd,
                                               void* address,
                                               size_t offset,
                                               size_t size)
    : ashmem_region_(ashmem_region),
      fd_(fd),
      address_(address),
      offset_(offset),
      size_(size),
      locked_(true) {
}

DiscardableMemoryAshmemAllocator::DiscardableMemoryAshmemAllocator(
    const std::string& name,
    size_t ashmem_region_size)
    : name_(name),
      ashmem_region_size_(
          std::max(kMinAshmemRegionSize, AlignToNextPage(ashmem_region_size))),
      last_ashmem_region_size_(0) {
  DCHECK_GE(ashmem_region_size_, kMinAshmemRegionSize);
}

DiscardableMemoryAshmemAllocator::~DiscardableMemoryAshmemAllocator() {
  DCHECK(ashmem_regions_.empty());
}

scoped_ptr<DiscardableAshmemChunk> DiscardableMemoryAshmemAllocator::Allocate(
    size_t size) {
  const size_t aligned_size = AlignToNextPage(size);
  if (!aligned_size)
    return scoped_ptr<DiscardableAshmemChunk>();
  // TODO(pliard): make this function less naive by e.g. moving the free chunks
  // multiset to the allocator itself in order to decrease even more
  // fragmentation/speedup allocation. Note that there should not be more than a
  // couple (=5) of AshmemRegion instances in practice though.
  AutoLock auto_lock(lock_);
  DCHECK_LE(ashmem_regions_.size(), 5U);
  for (ScopedVector<AshmemRegion>::iterator it = ashmem_regions_.begin();
       it != ashmem_regions_.end(); ++it) {
    scoped_ptr<DiscardableAshmemChunk> memory(
        (*it)->Allocate_Locked(size, aligned_size));
    if (memory)
      return memory.Pass();
  }
  // The creation of the (large) ashmem region might fail if the address space
  // is too fragmented. In case creation fails the allocator retries by
  // repetitively dividing the size by 2.
  const size_t min_region_size = std::max(kMinAshmemRegionSize, aligned_size);
  for (size_t region_size = std::max(ashmem_region_size_, aligned_size);
       region_size >= min_region_size;
       region_size = AlignToNextPage(region_size / 2)) {
    scoped_ptr<AshmemRegion> new_region(
        AshmemRegion::Create(region_size, name_.c_str(), this));
    if (!new_region)
      continue;
    last_ashmem_region_size_ = region_size;
    ashmem_regions_.push_back(new_region.release());
    return ashmem_regions_.back()->Allocate_Locked(size, aligned_size);
  }
  // TODO(pliard): consider adding an histogram to see how often this happens.
  return scoped_ptr<DiscardableAshmemChunk>();
}

size_t DiscardableMemoryAshmemAllocator::last_ashmem_region_size() const {
  AutoLock auto_lock(lock_);
  return last_ashmem_region_size_;
}

void DiscardableMemoryAshmemAllocator::DeleteAshmemRegion_Locked(
    AshmemRegion* region) {
  lock_.AssertAcquired();
  // Note that there should not be more than a couple of ashmem region instances
  // in |ashmem_regions_|.
  DCHECK_LE(ashmem_regions_.size(), 5U);
  const ScopedVector<AshmemRegion>::iterator it = std::find(
      ashmem_regions_.begin(), ashmem_regions_.end(), region);
  DCHECK(ashmem_regions_.end() != it);
  std::swap(*it, ashmem_regions_.back());
  ashmem_regions_.pop_back();
}

}  // namespace internal
}  // namespace base