/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * 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
 *
 *      http://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 "base/logging.h"
#include "base/stl_util.h"
#include "large_object_space.h"
#include "UniquePtr.h"
#include "dlmalloc.h"
#include "image.h"
#include "os.h"
#include "space_bitmap.h"
#include "utils.h"

namespace art {

void LargeObjectSpace::SwapBitmaps() {
  live_objects_.swap(mark_objects_);
  // Swap names to get more descriptive diagnostics.
  std::string temp_name = live_objects_->GetName();
  live_objects_->SetName(mark_objects_->GetName());
  mark_objects_->SetName(temp_name);
}

LargeObjectSpace::LargeObjectSpace(const std::string& name)
    : DiscontinuousSpace(name, kGcRetentionPolicyAlwaysCollect),
      num_bytes_allocated_(0), num_objects_allocated_(0), total_bytes_allocated_(0),
      total_objects_allocated_(0) {
  live_objects_.reset(new SpaceSetMap("large live objects"));
  mark_objects_.reset(new SpaceSetMap("large marked objects"));
}


void LargeObjectSpace::CopyLiveToMarked() {
  mark_objects_->CopyFrom(*live_objects_.get());
}

LargeObjectMapSpace::LargeObjectMapSpace(const std::string& name)
    : LargeObjectSpace(name),
      lock_("large object space lock", kAllocSpaceLock)
{

}

LargeObjectMapSpace* LargeObjectMapSpace::Create(const std::string& name) {
  return new LargeObjectMapSpace(name);
}

Object* LargeObjectMapSpace::Alloc(Thread* self, size_t num_bytes) {
  MemMap* mem_map = MemMap::MapAnonymous("allocation", NULL, num_bytes, PROT_READ | PROT_WRITE);
  if (mem_map == NULL) {
    return NULL;
  }
  MutexLock mu(self, lock_);
  Object* obj = reinterpret_cast<Object*>(mem_map->Begin());
  large_objects_.push_back(obj);
  mem_maps_.Put(obj, mem_map);
  size_t allocation_size = mem_map->Size();
  num_bytes_allocated_ += allocation_size;
  total_bytes_allocated_ += allocation_size;
  ++num_objects_allocated_;
  ++total_objects_allocated_;
  return obj;
}

size_t LargeObjectMapSpace::Free(Thread* self, Object* ptr) {
  MutexLock mu(self, lock_);
  MemMaps::iterator found = mem_maps_.find(ptr);
  CHECK(found != mem_maps_.end()) << "Attempted to free large object which was not live";
  DCHECK_GE(num_bytes_allocated_, found->second->Size());
  size_t allocation_size = found->second->Size();
  num_bytes_allocated_ -= allocation_size;
  --num_objects_allocated_;
  delete found->second;
  mem_maps_.erase(found);
  return allocation_size;
}

size_t LargeObjectMapSpace::AllocationSize(const Object* obj) {
  MutexLock mu(Thread::Current(), lock_);
  MemMaps::iterator found = mem_maps_.find(const_cast<Object*>(obj));
  CHECK(found != mem_maps_.end()) << "Attempted to get size of a large object which is not live";
  return found->second->Size();
}

size_t LargeObjectSpace::FreeList(Thread* self, size_t num_ptrs, Object** ptrs) {
  size_t total = 0;
  for (size_t i = 0; i < num_ptrs; ++i) {
    if (kDebugSpaces) {
      CHECK(Contains(ptrs[i]));
    }
    total += Free(self, ptrs[i]);
  }
  return total;
}

void LargeObjectMapSpace::Walk(DlMallocSpace::WalkCallback callback, void* arg) {
  MutexLock mu(Thread::Current(), lock_);
  for (MemMaps::iterator it = mem_maps_.begin(); it != mem_maps_.end(); ++it) {
    MemMap* mem_map = it->second;
    callback(mem_map->Begin(), mem_map->End(), mem_map->Size(), arg);
    callback(NULL, NULL, 0, arg);
  }
}

bool LargeObjectMapSpace::Contains(const Object* obj) const {
  MutexLock mu(Thread::Current(), lock_);
  return mem_maps_.find(const_cast<Object*>(obj)) != mem_maps_.end();
}

FreeListSpace* FreeListSpace::Create(const std::string& name, byte* requested_begin, size_t size) {
  CHECK(size % kAlignment == 0);
  MemMap* mem_map = MemMap::MapAnonymous(name.c_str(), requested_begin, size,
                                         PROT_READ | PROT_WRITE);
  CHECK(mem_map != NULL) << "Failed to allocate large object space mem map";
  return new FreeListSpace(name, mem_map, mem_map->Begin(), mem_map->End());
}

FreeListSpace::FreeListSpace(const std::string& name, MemMap* mem_map, byte* begin, byte* end)
    : LargeObjectSpace(name),
      begin_(begin),
      end_(end),
      mem_map_(mem_map),
      lock_("free list space lock", kAllocSpaceLock) {
  chunks_.resize(Size() / kAlignment + 1);
  // Add a dummy chunk so we don't need to handle chunks having no next chunk.
  chunks_.back().SetSize(kAlignment, false);
  // Start out with one large free chunk.
  AddFreeChunk(begin_, end_ - begin_, NULL);
}

FreeListSpace::~FreeListSpace() {

}

void FreeListSpace::AddFreeChunk(void* address, size_t size, Chunk* previous) {
  Chunk* chunk = ChunkFromAddr(address);
  chunk->SetSize(size, true);
  chunk->SetPrevious(previous);
  Chunk* next_chunk = GetNextChunk(chunk);
  next_chunk->SetPrevious(chunk);
  free_chunks_.insert(chunk);
}

FreeListSpace::Chunk* FreeListSpace::ChunkFromAddr(void* address) {
  size_t offset = reinterpret_cast<byte*>(address) - Begin();
  DCHECK(IsAligned<kAlignment>(offset));
  DCHECK_LT(offset, Size());
  return &chunks_[offset / kAlignment];
}

void* FreeListSpace::AddrFromChunk(Chunk* chunk) {
  return reinterpret_cast<void*>(Begin() + (chunk - &chunks_.front()) * kAlignment);
}

void FreeListSpace::RemoveFreeChunk(Chunk* chunk) {
  // TODO: C++0x
  // TODO: Improve performance, this might be slow.
  std::pair<FreeChunks::iterator, FreeChunks::iterator> range = free_chunks_.equal_range(chunk);
  for (FreeChunks::iterator it = range.first; it != range.second; ++it) {
    if (*it == chunk) {
      free_chunks_.erase(it);
      return;
    }
  }
}

void FreeListSpace::Walk(DlMallocSpace::WalkCallback callback, void* arg) {
  MutexLock mu(Thread::Current(), lock_);
  for (Chunk* chunk = &chunks_.front(); chunk < &chunks_.back(); ) {
    if (!chunk->IsFree()) {
      size_t size = chunk->GetSize();
      void* begin = AddrFromChunk(chunk);
      void* end = reinterpret_cast<void*>(reinterpret_cast<byte*>(begin) + size);
      callback(begin, end, size, arg);
      callback(NULL, NULL, 0, arg);
    }
    chunk = GetNextChunk(chunk);
  }
}

size_t FreeListSpace::Free(Thread* self, Object* obj) {
  MutexLock mu(self, lock_);
  CHECK(Contains(obj));
  // Check adjacent chunks to see if we need to combine.
  Chunk* chunk = ChunkFromAddr(obj);
  CHECK(!chunk->IsFree());

  size_t allocation_size = chunk->GetSize();
  madvise(obj, allocation_size, MADV_DONTNEED);
  num_objects_allocated_--;
  num_bytes_allocated_ -= allocation_size;
  Chunk* prev = chunk->GetPrevious();
  Chunk* next = GetNextChunk(chunk);

  // Combine any adjacent free chunks
  size_t extra_size = chunk->GetSize();
  if (next->IsFree()) {
    extra_size += next->GetSize();
    RemoveFreeChunk(next);
  }
  if (prev != NULL && prev->IsFree()) {
    RemoveFreeChunk(prev);
    AddFreeChunk(AddrFromChunk(prev), prev->GetSize() + extra_size, prev->GetPrevious());
  } else {
    AddFreeChunk(AddrFromChunk(chunk), extra_size, prev);
  }
  return allocation_size;
}

bool FreeListSpace::Contains(const Object* obj) const {
  return mem_map_->HasAddress(obj);
}

FreeListSpace::Chunk* FreeListSpace::GetNextChunk(Chunk* chunk) {
  return chunk + chunk->GetSize() / kAlignment;
}

size_t FreeListSpace::AllocationSize(const Object* obj) {
  Chunk* chunk = ChunkFromAddr(const_cast<Object*>(obj));
  CHECK(!chunk->IsFree());
  return chunk->GetSize();
}

Object* FreeListSpace::Alloc(Thread* self, size_t num_bytes) {
  MutexLock mu(self, lock_);
  num_bytes = RoundUp(num_bytes, kAlignment);
  Chunk temp;
  temp.SetSize(num_bytes);
  // Find the smallest chunk at least num_bytes in size.
  FreeChunks::iterator found = free_chunks_.lower_bound(&temp);
  if (found == free_chunks_.end()) {
    // Out of memory, or too much fragmentation.
    return NULL;
  }
  Chunk* chunk = *found;
  free_chunks_.erase(found);
  CHECK(chunk->IsFree());
  void* addr = AddrFromChunk(chunk);
  size_t chunk_size = chunk->GetSize();
  chunk->SetSize(num_bytes);
  if (chunk_size > num_bytes) {
    // Split the chunk into two chunks.
    Chunk* new_chunk = GetNextChunk(chunk);
    AddFreeChunk(AddrFromChunk(new_chunk), chunk_size - num_bytes, chunk);
  }

  num_objects_allocated_++;
  total_objects_allocated_++;
  num_bytes_allocated_ += num_bytes;
  total_bytes_allocated_ += num_bytes;
  return reinterpret_cast<Object*>(addr);
}

void FreeListSpace::Dump(std::ostream& os) const{
  os << GetName() << " -"
     << " begin: " << reinterpret_cast<void*>(Begin())
     << " end: " << reinterpret_cast<void*>(End());
}

}