CSE2410 Fall 2014 Bounce

// Copyright 2006-2008 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "macro-assembler.h"

#include "mark-compact.h"

#include "platform.h"

namespace v8 { namespace internal {

// For contiguous spaces, top should be in the space (or at the end) and limit

// should be the end of the space.

#define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \

  ASSERT((space).low() <= (info).top                 \

         && (info).top <= (space).high()             \

         && (info).limit == (space).high())

// ----------------------------------------------------------------------------

// HeapObjectIterator

HeapObjectIterator::HeapObjectIterator(PagedSpace* space) {

  Initialize(space->bottom(), space->top(), NULL);

}

HeapObjectIterator::HeapObjectIterator(PagedSpace* space,

                                       HeapObjectCallback size_func) {

  Initialize(space->bottom(), space->top(), size_func);

}

HeapObjectIterator::HeapObjectIterator(PagedSpace* space, Address start) {

  Initialize(start, space->top(), NULL);

}

HeapObjectIterator::HeapObjectIterator(PagedSpace* space, Address start,

                                       HeapObjectCallback size_func) {

  Initialize(start, space->top(), size_func);

}

void HeapObjectIterator::Initialize(Address cur, Address end,

                                    HeapObjectCallback size_f) {

  cur_addr_ = cur;

  end_addr_ = end;

  end_page_ = Page::FromAllocationTop(end);

  size_func_ = size_f;

  Page* p = Page::FromAllocationTop(cur_addr_);

  cur_limit_ = (p == end_page_) ? end_addr_ : p->AllocationTop();

#ifdef DEBUG

  Verify();

#endif

}

bool HeapObjectIterator::HasNextInNextPage() {

  if (cur_addr_ == end_addr_) return false;

  Page* cur_page = Page::FromAllocationTop(cur_addr_);

  cur_page = cur_page->next_page();

  ASSERT(cur_page->is_valid());

  cur_addr_ = cur_page->ObjectAreaStart();

  cur_limit_ = (cur_page == end_page_) ? end_addr_ : cur_page->AllocationTop();

  ASSERT(cur_addr_ < cur_limit_);

#ifdef DEBUG

  Verify();

#endif

  return true;

}

#ifdef DEBUG

void HeapObjectIterator::Verify() {

  Page* p = Page::FromAllocationTop(cur_addr_);

  ASSERT(p == Page::FromAllocationTop(cur_limit_));

  ASSERT(p->Offset(cur_addr_) <= p->Offset(cur_limit_));

}

#endif

// -----------------------------------------------------------------------------

// PageIterator

PageIterator::PageIterator(PagedSpace* space, Mode mode) {

  cur_page_ = space->first_page_;

  switch (mode) {

    case PAGES_IN_USE:

      stop_page_ = space->AllocationTopPage()->next_page();

      break;

    case PAGES_USED_BY_MC:

      stop_page_ = space->MCRelocationTopPage()->next_page();

      break;

    case ALL_PAGES:

      stop_page_ = Page::FromAddress(NULL);

      break;

    default:

      UNREACHABLE();

  }

}

// -----------------------------------------------------------------------------

// Page

#ifdef DEBUG

Page::RSetState Page::rset_state_ = Page::IN_USE;

#endif

// -----------------------------------------------------------------------------

// MemoryAllocator

//

int MemoryAllocator::capacity_   = 0;

int MemoryAllocator::size_       = 0;

VirtualMemory* MemoryAllocator::initial_chunk_ = NULL;

// 270 is an estimate based on the static default heap size of a pair of 256K

// semispaces and a 64M old generation.

const int kEstimatedNumberOfChunks = 270;

List<MemoryAllocator::ChunkInfo> MemoryAllocator::chunks_(

    kEstimatedNumberOfChunks);

List<int> MemoryAllocator::free_chunk_ids_(kEstimatedNumberOfChunks);

int MemoryAllocator::max_nof_chunks_ = 0;

int MemoryAllocator::top_ = 0;

void MemoryAllocator::Push(int free_chunk_id) {

  ASSERT(max_nof_chunks_ > 0);

  ASSERT(top_ < max_nof_chunks_);

  free_chunk_ids_[top_++] = free_chunk_id;

}

int MemoryAllocator::Pop() {

  ASSERT(top_ > 0);

  return free_chunk_ids_[--top_];

}

bool MemoryAllocator::Setup(int capacity) {

  capacity_ = RoundUp(capacity, Page::kPageSize);

  // Over-estimate the size of chunks_ array.  It assumes the expansion of old

  // space is always in the unit of a chunk (kChunkSize) except the last

  // expansion.

  //

  // Due to alignment, allocated space might be one page less than required

  // number (kPagesPerChunk) of pages for old spaces.

  //

  // Reserve two chunk ids for semispaces, one for map space, one for old

  // space, and one for code space.

  max_nof_chunks_ = (capacity_ / (kChunkSize - Page::kPageSize)) + 5;

  if (max_nof_chunks_ > kMaxNofChunks) return false;

  size_ = 0;

  ChunkInfo info;  // uninitialized element.

  for (int i = max_nof_chunks_ - 1; i >= 0; i--) {

    chunks_.Add(info);

    free_chunk_ids_.Add(i);

  }

  top_ = max_nof_chunks_;

  return true;

}

void MemoryAllocator::TearDown() {

  for (int i = 0; i < max_nof_chunks_; i++) {

    if (chunks_[i].address() != NULL) DeleteChunk(i);

  }

  chunks_.Clear();

  free_chunk_ids_.Clear();

  if (initial_chunk_ != NULL) {

    LOG(DeleteEvent("InitialChunk", initial_chunk_->address()));

    delete initial_chunk_;

    initial_chunk_ = NULL;

  }

  ASSERT(top_ == max_nof_chunks_);  // all chunks are free

  top_ = 0;

  capacity_ = 0;

  size_ = 0;

  max_nof_chunks_ = 0;

}

void* MemoryAllocator::AllocateRawMemory(const size_t requested,

                                         size_t* allocated,

                                         Executability executable) {

  if (size_ + static_cast<int>(requested) > capacity_) return NULL;

  void* mem = OS::Allocate(requested, allocated, executable == EXECUTABLE);

  int alloced = *allocated;

  size_ += alloced;

  Counters::memory_allocated.Increment(alloced);

  return mem;

}

void MemoryAllocator::FreeRawMemory(void* mem, size_t length) {

  OS::Free(mem, length);

  Counters::memory_allocated.Decrement(length);

  size_ -= length;

  ASSERT(size_ >= 0);

}

void* MemoryAllocator::ReserveInitialChunk(const size_t requested) {

  ASSERT(initial_chunk_ == NULL);

  initial_chunk_ = new VirtualMemory(requested);

  CHECK(initial_chunk_ != NULL);

  if (!initial_chunk_->IsReserved()) {

    delete initial_chunk_;

    initial_chunk_ = NULL;

    return NULL;

  }

  // We are sure that we have mapped a block of requested addresses.

  ASSERT(initial_chunk_->size() == requested);

  LOG(NewEvent("InitialChunk", initial_chunk_->address(), requested));

  size_ += requested;

  return initial_chunk_->address();

}

static int PagesInChunk(Address start, size_t size) {

  // The first page starts on the first page-aligned address from start onward

  // and the last page ends on the last page-aligned address before

  // start+size.  Page::kPageSize is a power of two so we can divide by

  // shifting.

  return (RoundDown(start + size, Page::kPageSize)

          - RoundUp(start, Page::kPageSize)) >> Page::kPageSizeBits;

}

Page* MemoryAllocator::AllocatePages(int requested_pages, int* allocated_pages,

                                     PagedSpace* owner) {

  if (requested_pages <= 0) return Page::FromAddress(NULL);

  size_t chunk_size = requested_pages * Page::kPageSize;

  // There is not enough space to guarantee the desired number pages can be

  // allocated.

  if (size_ + static_cast<int>(chunk_size) > capacity_) {

    // Request as many pages as we can.

    chunk_size = capacity_ - size_;

    requested_pages = chunk_size >> Page::kPageSizeBits;

    if (requested_pages <= 0) return Page::FromAddress(NULL);

  }

  void* chunk = AllocateRawMemory(chunk_size, &chunk_size, owner->executable());

  if (chunk == NULL) return Page::FromAddress(NULL);

  LOG(NewEvent("PagedChunk", chunk, chunk_size));

  *allocated_pages = PagesInChunk(static_cast<Address>(chunk), chunk_size);

  if (*allocated_pages == 0) {

    FreeRawMemory(chunk, chunk_size);

    LOG(DeleteEvent("PagedChunk", chunk));

    return Page::FromAddress(NULL);

  }

  int chunk_id = Pop();

  chunks_[chunk_id].init(static_cast<Address>(chunk), chunk_size, owner);

  return InitializePagesInChunk(chunk_id, *allocated_pages, owner);

}

Page* MemoryAllocator::CommitPages(Address start, size_t size,

                                   PagedSpace* owner, int* num_pages) {

  ASSERT(start != NULL);

  *num_pages = PagesInChunk(start, size);

  ASSERT(*num_pages > 0);

  ASSERT(initial_chunk_ != NULL);

  ASSERT(InInitialChunk(start));

  ASSERT(InInitialChunk(start + size - 1));

  if (!initial_chunk_->Commit(start, size, owner->executable() == EXECUTABLE)) {

    return Page::FromAddress(NULL);

  }

  Counters::memory_allocated.Increment(size);

  // So long as we correctly overestimated the number of chunks we should not

  // run out of chunk ids.

  CHECK(!OutOfChunkIds());

  int chunk_id = Pop();

  chunks_[chunk_id].init(start, size, owner);

  return InitializePagesInChunk(chunk_id, *num_pages, owner);

}

bool MemoryAllocator::CommitBlock(Address start,

                                  size_t size,

                                  Executability executable) {

  ASSERT(start != NULL);

  ASSERT(size > 0);

  ASSERT(initial_chunk_ != NULL);

  ASSERT(InInitialChunk(start));

  ASSERT(InInitialChunk(start + size - 1));

  if (!initial_chunk_->Commit(start, size, executable)) return false;

  Counters::memory_allocated.Increment(size);

  return true;

}

Page* MemoryAllocator::InitializePagesInChunk(int chunk_id, int pages_in_chunk,

                                              PagedSpace* owner) {

  ASSERT(IsValidChunk(chunk_id));

  ASSERT(pages_in_chunk > 0);

  Address chunk_start = chunks_[chunk_id].address();

  Address low = RoundUp(chunk_start, Page::kPageSize);

#ifdef DEBUG

  size_t chunk_size = chunks_[chunk_id].size();

  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);

  ASSERT(pages_in_chunk <=

        ((OffsetFrom(high) - OffsetFrom(low)) / Page::kPageSize));

#endif

  Address page_addr = low;

  for (int i = 0; i < pages_in_chunk; i++) {

    Page* p = Page::FromAddress(page_addr);

    p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;

    p->is_normal_page = 1;

    page_addr += Page::kPageSize;

  }

  // Set the next page of the last page to 0.

  Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);

  last_page->opaque_header = OffsetFrom(0) | chunk_id;

  return Page::FromAddress(low);

}

Page* MemoryAllocator::FreePages(Page* p) {

  if (!p->is_valid()) return p;

  // Find the first page in the same chunk as 'p'

  Page* first_page = FindFirstPageInSameChunk(p);

  Page* page_to_return = Page::FromAddress(NULL);

  if (p != first_page) {

    // Find the last page in the same chunk as 'prev'.

    Page* last_page = FindLastPageInSameChunk(p);

    first_page = GetNextPage(last_page);  // first page in next chunk

    // set the next_page of last_page to NULL

    SetNextPage(last_page, Page::FromAddress(NULL));

    page_to_return = p;  // return 'p' when exiting

  }

  while (first_page->is_valid()) {

    int chunk_id = GetChunkId(first_page);

    ASSERT(IsValidChunk(chunk_id));

    // Find the first page of the next chunk before deleting this chunk.

    first_page = GetNextPage(FindLastPageInSameChunk(first_page));

    // Free the current chunk.

    DeleteChunk(chunk_id);

  }

  return page_to_return;

}

void MemoryAllocator::DeleteChunk(int chunk_id) {

  ASSERT(IsValidChunk(chunk_id));

  ChunkInfo& c = chunks_[chunk_id];

  // We cannot free a chunk contained in the initial chunk because it was not

  // allocated with AllocateRawMemory.  Instead we uncommit the virtual

  // memory.

  if (InInitialChunk(c.address())) {

    // TODO(1240712): VirtualMemory::Uncommit has a return value which

    // is ignored here.

    initial_chunk_->Uncommit(c.address(), c.size());

    Counters::memory_allocated.Decrement(c.size());

  } else {

    LOG(DeleteEvent("PagedChunk", c.address()));

    FreeRawMemory(c.address(), c.size());

  }

  c.init(NULL, 0, NULL);

  Push(chunk_id);

}

Page* MemoryAllocator::FindFirstPageInSameChunk(Page* p) {

  int chunk_id = GetChunkId(p);

  ASSERT(IsValidChunk(chunk_id));

  Address low = RoundUp(chunks_[chunk_id].address(), Page::kPageSize);

  return Page::FromAddress(low);

}

Page* MemoryAllocator::FindLastPageInSameChunk(Page* p) {

  int chunk_id = GetChunkId(p);

  ASSERT(IsValidChunk(chunk_id));

  Address chunk_start = chunks_[chunk_id].address();

  size_t chunk_size = chunks_[chunk_id].size();

  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);

  ASSERT(chunk_start <= p->address() && p->address() < high);

  return Page::FromAddress(high - Page::kPageSize);

}

#ifdef DEBUG

void MemoryAllocator::ReportStatistics() {

  float pct = static_cast<float>(capacity_ - size_) / capacity_;

  PrintF("  capacity: %d, used: %d, available: %%%d\n\n",

         capacity_, size_, static_cast<int>(pct*100));

}

#endif

// -----------------------------------------------------------------------------

// PagedSpace implementation

PagedSpace::PagedSpace(int max_capacity,

                       AllocationSpace id,

                       Executability executable)

    : Space(id, executable) {

  max_capacity_ = (RoundDown(max_capacity, Page::kPageSize) / Page::kPageSize)

                  * Page::kObjectAreaSize;

  accounting_stats_.Clear();

  allocation_info_.top = NULL;

  allocation_info_.limit = NULL;

  mc_forwarding_info_.top = NULL;

  mc_forwarding_info_.limit = NULL;

}

bool PagedSpace::Setup(Address start, size_t size) {

  if (HasBeenSetup()) return false;

  int num_pages = 0;

  // Try to use the virtual memory range passed to us.  If it is too small to

  // contain at least one page, ignore it and allocate instead.

  int pages_in_chunk = PagesInChunk(start, size);

  if (pages_in_chunk > 0) {

    first_page_ = MemoryAllocator::CommitPages(RoundUp(start, Page::kPageSize),

                                               Page::kPageSize * pages_in_chunk,

                                               this, &num_pages);

  } else {

    int requested_pages = Min(MemoryAllocator::kPagesPerChunk,

                              max_capacity_ / Page::kObjectAreaSize);

    first_page_ =

        MemoryAllocator::AllocatePages(requested_pages, &num_pages, this);

    if (!first_page_->is_valid()) return false;

  }

  // We are sure that the first page is valid and that we have at least one

  // page.

  ASSERT(first_page_->is_valid());

  ASSERT(num_pages > 0);

  accounting_stats_.ExpandSpace(num_pages * Page::kObjectAreaSize);

  ASSERT(Capacity() <= max_capacity_);

  for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {

    p->ClearRSet();

  }

  // Use first_page_ for allocation.

  SetAllocationInfo(&allocation_info_, first_page_);

  return true;

}

bool PagedSpace::HasBeenSetup() {

  return (Capacity() > 0);

}

void PagedSpace::TearDown() {

  first_page_ = MemoryAllocator::FreePages(first_page_);

  ASSERT(!first_page_->is_valid());

  accounting_stats_.Clear();

}

#ifdef ENABLE_HEAP_PROTECTION

void PagedSpace::Protect() {

  Page* page = first_page_;

  while (page->is_valid()) {

    MemoryAllocator::ProtectChunkFromPage(page);

    page = MemoryAllocator::FindLastPageInSameChunk(page)->next_page();

  }

}

void PagedSpace::Unprotect() {

  Page* page = first_page_;

  while (page->is_valid()) {

    MemoryAllocator::UnprotectChunkFromPage(page);

    page = MemoryAllocator::FindLastPageInSameChunk(page)->next_page();

  }

}

#endif

void PagedSpace::ClearRSet() {

  PageIterator it(this, PageIterator::ALL_PAGES);

  while (it.has_next()) {

    it.next()->ClearRSet();

  }

}

Object* PagedSpace::FindObject(Address addr) {

  // Note: this function can only be called before or after mark-compact GC

  // because it accesses map pointers.

  ASSERT(!MarkCompactCollector::in_use());

  if (!Contains(addr)) return Failure::Exception();

  Page* p = Page::FromAddress(addr);

  ASSERT(IsUsed(p));

  Address cur = p->ObjectAreaStart();

  Address end = p->AllocationTop();

  while (cur < end) {

    HeapObject* obj = HeapObject::FromAddress(cur);

    Address next = cur + obj->Size();

    if ((cur <= addr) && (addr < next)) return obj;

    cur = next;

  }

  UNREACHABLE();

  return Failure::Exception();

}

bool PagedSpace::IsUsed(Page* page) {

  PageIterator it(this, PageIterator::PAGES_IN_USE);

  while (it.has_next()) {

    if (page == it.next()) return true;

  }

  return false;

}

void PagedSpace::SetAllocationInfo(AllocationInfo* alloc_info, Page* p) {

  alloc_info->top = p->ObjectAreaStart();

  alloc_info->limit = p->ObjectAreaEnd();

  ASSERT(alloc_info->VerifyPagedAllocation());

}

void PagedSpace::MCResetRelocationInfo() {

  // Set page indexes.

  int i = 0;

  PageIterator it(this, PageIterator::ALL_PAGES);

  while (it.has_next()) {

    Page* p = it.next();

    p->mc_page_index = i++;

  }

  // Set mc_forwarding_info_ to the first page in the space.

  SetAllocationInfo(&mc_forwarding_info_, first_page_);

  // All the bytes in the space are 'available'.  We will rediscover

  // allocated and wasted bytes during GC.

  accounting_stats_.Reset();

}

int PagedSpace::MCSpaceOffsetForAddress(Address addr) {

#ifdef DEBUG

  // The Contains function considers the address at the beginning of a

  // page in the page, MCSpaceOffsetForAddress considers it is in the

  // previous page.

  if (Page::IsAlignedToPageSize(addr)) {

    ASSERT(Contains(addr - kPointerSize));

  } else {

    ASSERT(Contains(addr));

  }

#endif

  // If addr is at the end of a page, it belongs to previous page

  Page* p = Page::IsAlignedToPageSize(addr)

            ? Page::FromAllocationTop(addr)

            : Page::FromAddress(addr);

  int index = p->mc_page_index;

  return (index * Page::kPageSize) + p->Offset(addr);

}

// Slow case for reallocating and promoting objects during a compacting

// collection.  This function is not space-specific.

HeapObject* PagedSpace::SlowMCAllocateRaw(int size_in_bytes) {

  Page* current_page = TopPageOf(mc_forwarding_info_);

  if (!current_page->next_page()->is_valid()) {

    if (!Expand(current_page)) {

      return NULL;

    }

  }

  // There are surely more pages in the space now.

  ASSERT(current_page->next_page()->is_valid());

  // We do not add the top of page block for current page to the space's

  // free list---the block may contain live objects so we cannot write

  // bookkeeping information to it.  Instead, we will recover top of page

  // blocks when we move objects to their new locations.

  //

  // We do however write the allocation pointer to the page.  The encoding

  // of forwarding addresses is as an offset in terms of live bytes, so we

  // need quick access to the allocation top of each page to decode

  // forwarding addresses.

  current_page->mc_relocation_top = mc_forwarding_info_.top;

  SetAllocationInfo(&mc_forwarding_info_, current_page->next_page());

  return AllocateLinearly(&mc_forwarding_info_, size_in_bytes);

}

bool PagedSpace::Expand(Page* last_page) {

  ASSERT(max_capacity_ % Page::kObjectAreaSize == 0);

  ASSERT(Capacity() % Page::kObjectAreaSize == 0);

  if (Capacity() == max_capacity_) return false;

  ASSERT(Capacity() < max_capacity_);

  // Last page must be valid and its next page is invalid.

  ASSERT(last_page->is_valid() && !last_page->next_page()->is_valid());

  int available_pages = (max_capacity_ - Capacity()) / Page::kObjectAreaSize;

  if (available_pages <= 0) return false;

  int desired_pages = Min(available_pages, MemoryAllocator::kPagesPerChunk);

  Page* p = MemoryAllocator::AllocatePages(desired_pages, &desired_pages, this);

  if (!p->is_valid()) return false;

  accounting_stats_.ExpandSpace(desired_pages * Page::kObjectAreaSize);

  ASSERT(Capacity() <= max_capacity_);

  MemoryAllocator::SetNextPage(last_page, p);

  // Clear remembered set of new pages.

  while (p->is_valid()) {

    p->ClearRSet();

    p = p->next_page();

  }

  return true;

}

#ifdef DEBUG

int PagedSpace::CountTotalPages() {

  int count = 0;

  for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {

    count++;

  }

  return count;

}

#endif

void PagedSpace::Shrink() {

  // Release half of free pages.

  Page* top_page = AllocationTopPage();

  ASSERT(top_page->is_valid());

  // Loop over the pages from the top page to the end of the space to count

  // the number of pages to keep and find the last page to keep.

  int free_pages = 0;

  int pages_to_keep = 0;  // Of the free pages.

  Page* last_page_to_keep = top_page;

  Page* current_page = top_page->next_page();

  // Loop over the pages to the end of the space.

  while (current_page->is_valid()) {

    // Advance last_page_to_keep every other step to end up at the midpoint.

    if ((free_pages & 0x1) == 1) {

      pages_to_keep++;

      last_page_to_keep = last_page_to_keep->next_page();

    }

    free_pages++;

    current_page = current_page->next_page();

  }

  // Free pages after last_page_to_keep, and adjust the next_page link.

  Page* p = MemoryAllocator::FreePages(last_page_to_keep->next_page());

  MemoryAllocator::SetNextPage(last_page_to_keep, p);

  // Since pages are only freed in whole chunks, we may have kept more than

  // pages_to_keep.

  while (p->is_valid()) {

    pages_to_keep++;

    p = p->next_page();

  }

  // The difference between free_pages and pages_to_keep is the number of

  // pages actually freed.

  ASSERT(pages_to_keep <= free_pages);

  int bytes_freed = (free_pages - pages_to_keep) * Page::kObjectAreaSize;

  accounting_stats_.ShrinkSpace(bytes_freed);

  ASSERT(Capacity() == CountTotalPages() * Page::kObjectAreaSize);

}

bool PagedSpace::EnsureCapacity(int capacity) {

  if (Capacity() >= capacity) return true;

  // Start from the allocation top and loop to the last page in the space.

  Page* last_page = AllocationTopPage();

  Page* next_page = last_page->next_page();

  while (next_page->is_valid()) {

    last_page = MemoryAllocator::FindLastPageInSameChunk(next_page);

    next_page = last_page->next_page();

  }

  // Expand the space until it has the required capacity or expansion fails.

  do {

    if (!Expand(last_page)) return false;

    ASSERT(last_page->next_page()->is_valid());

    last_page =

        MemoryAllocator::FindLastPageInSameChunk(last_page->next_page());

  } while (Capacity() < capacity);

  return true;

}

#ifdef DEBUG

void PagedSpace::Print() { }

#endif

// -----------------------------------------------------------------------------

// NewSpace implementation

bool NewSpace::Setup(Address start, int size) {

  // Setup new space based on the preallocated memory block defined by

  // start and size. The provided space is divided into two semi-spaces.

  // To support fast containment testing in the new space, the size of

  // this chunk must be a power of two and it must be aligned to its size.

  int initial_semispace_capacity = Heap::InitialSemiSpaceSize();

  int maximum_semispace_capacity = Heap::SemiSpaceSize();

  ASSERT(initial_semispace_capacity <= maximum_semispace_capacity);

  ASSERT(IsPowerOf2(maximum_semispace_capacity));

  maximum_capacity_ = maximum_semispace_capacity;

  capacity_ = initial_semispace_capacity;

  // Allocate and setup the histogram arrays if necessary.

#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)

  allocated_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);

  promoted_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);

#define SET_NAME(name) allocated_histogram_[name].set_name(#name); \

                       promoted_histogram_[name].set_name(#name);

  INSTANCE_TYPE_LIST(SET_NAME)

#undef SET_NAME

#endif

  ASSERT(size == 2 * maximum_capacity_);

  ASSERT(IsAddressAligned(start, size, 0));

  if (!to_space_.Setup(start, capacity_, maximum_capacity_)) {

    return false;

  }

  if (!from_space_.Setup(start + maximum_capacity_,

                         capacity_,

                         maximum_capacity_)) {

    return false;

  }

  start_ = start;

  address_mask_ = ~(size - 1);

  object_mask_ = address_mask_ | kHeapObjectTag;

  object_expected_ = reinterpret_cast<uint32_t>(start) | kHeapObjectTag;

  allocation_info_.top = to_space_.low();

  allocation_info_.limit = to_space_.high();

  mc_forwarding_info_.top = NULL;

  mc_forwarding_info_.limit = NULL;

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

  return true;

}

void NewSpace::TearDown() {

#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)

  if (allocated_histogram_) {

    DeleteArray(allocated_histogram_);

    allocated_histogram_ = NULL;

  }

  if (promoted_histogram_) {

    DeleteArray(promoted_histogram_);

    promoted_histogram_ = NULL;

  }

#endif

  start_ = NULL;

  capacity_ = 0;

  allocation_info_.top = NULL;

  allocation_info_.limit = NULL;

  mc_forwarding_info_.top = NULL;

  mc_forwarding_info_.limit = NULL;

  to_space_.TearDown();

  from_space_.TearDown();

}

#ifdef ENABLE_HEAP_PROTECTION

void NewSpace::Protect() {

  MemoryAllocator::Protect(ToSpaceLow(), Capacity());

  MemoryAllocator::Protect(FromSpaceLow(), Capacity());

}

void NewSpace::Unprotect() {

  MemoryAllocator::Unprotect(ToSpaceLow(), Capacity(),

                             to_space_.executable());

  MemoryAllocator::Unprotect(FromSpaceLow(), Capacity(),

                             from_space_.executable());

}

#endif

void NewSpace::Flip() {

  SemiSpace tmp = from_space_;

  from_space_ = to_space_;

  to_space_ = tmp;

}

bool NewSpace::Double() {

  ASSERT(capacity_ <= maximum_capacity_ / 2);

  // TODO(1240712): Failure to double the from space can result in

  // semispaces of different sizes.  In the event of that failure, the

  // to space doubling should be rolled back before returning false.

  if (!to_space_.Double() || !from_space_.Double()) return false;

  capacity_ *= 2;

  allocation_info_.limit = to_space_.high();

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

  return true;

}

void NewSpace::ResetAllocationInfo() {

  allocation_info_.top = to_space_.low();

  allocation_info_.limit = to_space_.high();

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

}

void NewSpace::MCResetRelocationInfo() {

  mc_forwarding_info_.top = from_space_.low();

  mc_forwarding_info_.limit = from_space_.high();

  ASSERT_SEMISPACE_ALLOCATION_INFO(mc_forwarding_info_, from_space_);

}

void NewSpace::MCCommitRelocationInfo() {

  // Assumes that the spaces have been flipped so that mc_forwarding_info_ is

  // valid allocation info for the to space.

  allocation_info_.top = mc_forwarding_info_.top;

  allocation_info_.limit = to_space_.high();

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

}

#ifdef DEBUG

// We do not use the SemispaceIterator because verification doesn't assume

// that it works (it depends on the invariants we are checking).

void NewSpace::Verify() {

  // The allocation pointer should be in the space or at the very end.

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

  // There should be objects packed in from the low address up to the

  // allocation pointer.

  Address current = to_space_.low();

  while (current < top()) {

    HeapObject* object = HeapObject::FromAddress(current);

    // The first word should be a map, and we expect all map pointers to

    // be in map space.

    Map* map = object->map();

    ASSERT(map->IsMap());

    ASSERT(Heap::map_space()->Contains(map));

    // The object should not be code or a map.

    ASSERT(!object->IsMap());

    ASSERT(!object->IsCode());

    // The object itself should look OK.

    object->Verify();

    // All the interior pointers should be contained in the heap.

    VerifyPointersVisitor visitor;

    int size = object->Size();

    object->IterateBody(map->instance_type(), size, &visitor);

    current += size;

  }

  // The allocation pointer should not be in the middle of an object.

  ASSERT(current == top());

}

#endif

// -----------------------------------------------------------------------------

// SemiSpace implementation

bool SemiSpace::Setup(Address start,

                      int initial_capacity,

                      int maximum_capacity) {

  // Creates a space in the young generation. The constructor does not

  // allocate memory from the OS.  A SemiSpace is given a contiguous chunk of

  // memory of size 'capacity' when set up, and does not grow or shrink

  // otherwise.  In the mark-compact collector, the memory region of the from

  // space is used as the marking stack. It requires contiguous memory

  // addresses.

  capacity_ = initial_capacity;

  maximum_capacity_ = maximum_capacity;

  if (!MemoryAllocator::CommitBlock(start, capacity_, executable())) {

    return false;

  }

  start_ = start;

  address_mask_ = ~(maximum_capacity - 1);

  object_mask_ = address_mask_ | kHeapObjectTag;

  object_expected_ = reinterpret_cast<uint32_t>(start) | kHeapObjectTag;

  age_mark_ = start_;

  return true;

}

void SemiSpace::TearDown() {

  start_ = NULL;

  capacity_ = 0;

}

bool SemiSpace::Double() {

  if (!MemoryAllocator::CommitBlock(high(), capacity_, executable())) {

    return false;

  }

  capacity_ *= 2;

  return true;

}

#ifdef DEBUG

void SemiSpace::Print() { }

void SemiSpace::Verify() { }

#endif

// -----------------------------------------------------------------------------

// SemiSpaceIterator implementation.

SemiSpaceIterator::SemiSpaceIterator(NewSpace* space) {

  Initialize(space, space->bottom(), space->top(), NULL);

}

SemiSpaceIterator::SemiSpaceIterator(NewSpace* space,

                                     HeapObjectCallback size_func) {

  Initialize(space, space->bottom(), space->top(), size_func);

}

SemiSpaceIterator::SemiSpaceIterator(NewSpace* space, Address start) {

  Initialize(space, start, space->top(), NULL);

}

void SemiSpaceIterator::Initialize(NewSpace* space, Address start,

                                   Address end,

                                   HeapObjectCallback size_func) {

  ASSERT(space->ToSpaceContains(start));

  ASSERT(space->ToSpaceLow() <= end

         && end <= space->ToSpaceHigh());

  space_ = &space->to_space_;

  current_ = start;

  limit_ = end;

  size_func_ = size_func;

}

#ifdef DEBUG

// A static array of histogram info for each type.

static HistogramInfo heap_histograms[LAST_TYPE+1];

static JSObject::SpillInformation js_spill_information;

// heap_histograms is shared, always clear it before using it.

static void ClearHistograms() {

  // We reset the name each time, though it hasn't changed.

#define DEF_TYPE_NAME(name) heap_histograms[name].set_name(#name);

  INSTANCE_TYPE_LIST(DEF_TYPE_NAME)

#undef DEF_TYPE_NAME

#define CLEAR_HISTOGRAM(name) heap_histograms[name].clear();

  INSTANCE_TYPE_LIST(CLEAR_HISTOGRAM)

#undef CLEAR_HISTOGRAM

  js_spill_information.Clear();

}

static int code_kind_statistics[Code::NUMBER_OF_KINDS];

static void ClearCodeKindStatistics() {

  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {

    code_kind_statistics[i] = 0;

  }

}

static void ReportCodeKindStatistics() {

  const char* table[Code::NUMBER_OF_KINDS];

#define CASE(name)                            \

  case Code::name: table[Code::name] = #name; \

  break

  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {

    switch (static_cast<Code::Kind>(i)) {

      CASE(FUNCTION);

      CASE(STUB);

      CASE(BUILTIN);

      CASE(LOAD_IC);

      CASE(KEYED_LOAD_IC);

      CASE(STORE_IC);

      CASE(KEYED_STORE_IC);

      CASE(CALL_IC);

    }

  }

#undef CASE

  PrintF("\n   Code kind histograms: \n");

  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {

    if (code_kind_statistics[i] > 0) {

      PrintF("     %-20s: %10d bytes\n", table[i], code_kind_statistics[i]);

    }

  }

  PrintF("\n");

}

static int CollectHistogramInfo(HeapObject* obj) {

  InstanceType type = obj->map()->instance_type();

  ASSERT(0 <= type && type <= LAST_TYPE);

  ASSERT(heap_histograms[type].name() != NULL);

  heap_histograms[type].increment_number(1);

  heap_histograms[type].increment_bytes(obj->Size());

  if (FLAG_collect_heap_spill_statistics && obj->IsJSObject()) {

    JSObject::cast(obj)->IncrementSpillStatistics(&js_spill_information);

  }

  return obj->Size();

}

static void ReportHistogram(bool print_spill) {

  PrintF("\n  Object Histogram:\n");

  for (int i = 0; i <= LAST_TYPE; i++) {

    if (heap_histograms[i].number() > 0) {

      PrintF("    %-33s%10d (%10d bytes)\n",

             heap_histograms[i].name(),

             heap_histograms[i].number(),

             heap_histograms[i].bytes());

    }

  }

  PrintF("\n");

  // Summarize string types.

  int string_number = 0;

  int string_bytes = 0;

#define INCREMENT(type, size, name)                  \

    string_number += heap_histograms[type].number(); \

    string_bytes += heap_histograms[type].bytes();

  STRING_TYPE_LIST(INCREMENT)

#undef INCREMENT

  if (string_number > 0) {

    PrintF("    %-33s%10d (%10d bytes)\n\n", "STRING_TYPE", string_number,

           string_bytes);

  }

  if (FLAG_collect_heap_spill_statistics && print_spill) {

    js_spill_information.Print();

  }

}

#endif  // DEBUG

// Support for statistics gathering for --heap-stats and --log-gc.

#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)

void NewSpace::ClearHistograms() {

  for (int i = 0; i <= LAST_TYPE; i++) {

    allocated_histogram_[i].clear();

    promoted_histogram_[i].clear();

  }

}

// Because the copying collector does not touch garbage objects, we iterate

// the new space before a collection to get a histogram of allocated objects.

// This only happens (1) when compiled with DEBUG and the --heap-stats flag is

// set, or when compiled with ENABLE_LOGGING_AND_PROFILING and the --log-gc

// flag is set.

void NewSpace::CollectStatistics() {

  ClearHistograms();

  SemiSpaceIterator it(this);

  while (it.has_next()) RecordAllocation(it.next());

}

#ifdef ENABLE_LOGGING_AND_PROFILING

static void DoReportStatistics(HistogramInfo* info, const char* description) {

  LOG(HeapSampleBeginEvent("NewSpace", description));

  // Lump all the string types together.

  int string_number = 0;

  int string_bytes = 0;

#define INCREMENT(type, size, name)       \

    string_number += info[type].number(); \

    string_bytes += info[type].bytes();

  STRING_TYPE_LIST(INCREMENT)

#undef INCREMENT

  if (string_number > 0) {

    LOG(HeapSampleItemEvent("STRING_TYPE", string_number, string_bytes));

  }

  // Then do the other types.

  for (int i = FIRST_NONSTRING_TYPE; i <= LAST_TYPE; ++i) {

    if (info[i].number() > 0) {

      LOG(HeapSampleItemEvent(info[i].name(), info[i].number(),

                              info[i].bytes()));

    }

  }

  LOG(HeapSampleEndEvent("NewSpace", description));

}

#endif  // ENABLE_LOGGING_AND_PROFILING

void NewSpace::ReportStatistics() {

#ifdef DEBUG

  if (FLAG_heap_stats) {

    float pct = static_cast<float>(Available()) / Capacity();

    PrintF("  capacity: %d, available: %d, %%%d\n",

           Capacity(), Available(), static_cast<int>(pct*100));

    PrintF("\n  Object Histogram:\n");

    for (int i = 0; i <= LAST_TYPE; i++) {

      if (allocated_histogram_[i].number() > 0) {

        PrintF("    %-33s%10d (%10d bytes)\n",

               allocated_histogram_[i].name(),

               allocated_histogram_[i].number(),

               allocated_histogram_[i].bytes());

      }

    }

    PrintF("\n");

  }

#endif  // DEBUG

#ifdef ENABLE_LOGGING_AND_PROFILING

  if (FLAG_log_gc) {

    DoReportStatistics(allocated_histogram_, "allocated");

    DoReportStatistics(promoted_histogram_, "promoted");

  }

#endif  // ENABLE_LOGGING_AND_PROFILING

}

void NewSpace::RecordAllocation(HeapObject* obj) {

  InstanceType type = obj->map()->instance_type();

  ASSERT(0 <= type && type <= LAST_TYPE);

  allocated_histogram_[type].increment_number(1);

  allocated_histogram_[type].increment_bytes(obj->Size());

}

void NewSpace::RecordPromotion(HeapObject* obj) {

  InstanceType type = obj->map()->instance_type();

  ASSERT(0 <= type && type <= LAST_TYPE);

  promoted_histogram_[type].increment_number(1);

  promoted_histogram_[type].increment_bytes(obj->Size());

}

#endif  // defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)

// -----------------------------------------------------------------------------

// Free lists for old object spaces implementation

void FreeListNode::set_size(int size_in_bytes) {

  ASSERT(size_in_bytes > 0);

  ASSERT(IsAligned(size_in_bytes, kPointerSize));

  // We write a map and possibly size information to the block.  If the block

  // is big enough to be a ByteArray with at least one extra word (the next

  // pointer), we set its map to be the byte array map and its size to an

  // appropriate array length for the desired size from HeapObject::Size().

  // If the block is too small (eg, one or two words), to hold both a size

  // field and a next pointer, we give it a filler map that gives it the

  // correct size.

  if (size_in_bytes > Array::kHeaderSize) {

    set_map(Heap::byte_array_map());

    ByteArray::cast(this)->set_length(ByteArray::LengthFor(size_in_bytes));

  } else if (size_in_bytes == kPointerSize) {

    set_map(Heap::one_word_filler_map());

  } else if (size_in_bytes == 2 * kPointerSize) {

    set_map(Heap::two_word_filler_map());

  } else {

    UNREACHABLE();

  }

  ASSERT(Size() == size_in_bytes);

}

Address FreeListNode::next() {

  ASSERT(map() == Heap::byte_array_map());

  ASSERT(Size() >= kNextOffset + kPointerSize);

  return Memory::Address_at(address() + kNextOffset);

}

void FreeListNode::set_next(Address next) {

  ASSERT(map() == Heap::byte_array_map());

  ASSERT(Size() >= kNextOffset + kPointerSize);

  Memory::Address_at(address() + kNextOffset) = next;

}

OldSpaceFreeList::OldSpaceFreeList(AllocationSpace owner) : owner_(owner) {

  Reset();

}

void OldSpaceFreeList::Reset() {

  available_ = 0;

  for (int i = 0; i < kFreeListsLength; i++) {

    free_[i].head_node_ = NULL;

  }

  needs_rebuild_ = false;

  finger_ = kHead;

  free_[kHead].next_size_ = kEnd;

}

void OldSpaceFreeList::RebuildSizeList() {

  ASSERT(needs_rebuild_);

  int cur = kHead;

  for (int i = cur + 1; i < kFreeListsLength; i++) {

    if (free_[i].head_node_ != NULL) {

      free_[cur].next_size_ = i;

      cur = i;

    }

  }

  free_[cur].next_size_ = kEnd;

  needs_rebuild_ = false;

}

int OldSpaceFreeList::Free(Address start, int size_in_bytes) {

#ifdef DEBUG

  for (int i = 0; i < size_in_bytes; i += kPointerSize) {

    Memory::Address_at(start + i) = kZapValue;

  }

#endif

  FreeListNode* node = FreeListNode::FromAddress(start);

  node->set_size(size_in_bytes);

  // Early return to drop too-small blocks on the floor (one or two word

  // blocks cannot hold a map pointer, a size field, and a pointer to the

  // next block in the free list).

  if (size_in_bytes < kMinBlockSize) {

    return size_in_bytes;

  }

  // Insert other blocks at the head of an exact free list.

  int index = size_in_bytes >> kPointerSizeLog2;

  node->set_next(free_[index].head_node_);

  free_[index].head_node_ = node->address();

  available_ += size_in_bytes;

  needs_rebuild_ = true;

  return 0;

}

Object* OldSpaceFreeList::Allocate(int size_in_bytes, int* wasted_bytes) {

  ASSERT(0 < size_in_bytes);

  ASSERT(size_in_bytes <= kMaxBlockSize);

  ASSERT(IsAligned(size_in_bytes, kPointerSize));

  if (needs_rebuild_) RebuildSizeList();

  int index = size_in_bytes >> kPointerSizeLog2;

  // Check for a perfect fit.

  if (free_[index].head_node_ != NULL) {

    FreeListNode* node = FreeListNode::FromAddress(free_[index].head_node_);

    // If this was the last block of its size, remove the size.

    if ((free_[index].head_node_ = node->next()) == NULL) RemoveSize(index);

    available_ -= size_in_bytes;

    *wasted_bytes = 0;

    return node;

  }

  // Search the size list for the best fit.

  int prev = finger_ < index ? finger_ : kHead;

  int cur = FindSize(index, &prev);

  ASSERT(index < cur);

  if (cur == kEnd) {

    // No large enough size in list.

    *wasted_bytes = 0;

    return Failure::RetryAfterGC(size_in_bytes, owner_);

  }

  int rem = cur - index;

  int rem_bytes = rem << kPointerSizeLog2;

  FreeListNode* cur_node = FreeListNode::FromAddress(free_[cur].head_node_);

  ASSERT(cur_node->Size() == (cur << kPointerSizeLog2));

  FreeListNode* rem_node = FreeListNode::FromAddress(free_[cur].head_node_ +

                                                     size_in_bytes);

  // Distinguish the cases prev < rem < cur and rem <= prev < cur

  // to avoid many redundant tests and calls to Insert/RemoveSize.

  if (prev < rem) {

    // Simple case: insert rem between prev and cur.

    finger_ = prev;

    free_[prev].next_size_ = rem;

    // If this was the last block of size cur, remove the size.

    if ((free_[cur].head_node_ = cur_node->next()) == NULL) {

      free_[rem].next_size_ = free_[cur].next_size_;

    } else {

      free_[rem].next_size_ = cur;

    }

    // Add the remainder block.

    rem_node->set_size(rem_bytes);

    rem_node->set_next(free_[rem].head_node_);

    free_[rem].head_node_ = rem_node->address();

  } else {

    // If this was the last block of size cur, remove the size.

    if ((free_[cur].head_node_ = cur_node->next()) == NULL) {

      finger_ = prev;

      free_[prev].next_size_ = free_[cur].next_size_;

    }

    if (rem_bytes < kMinBlockSize) {

      // Too-small remainder is wasted.

      rem_node->set_size(rem_bytes);

      available_ -= size_in_bytes + rem_bytes;

      *wasted_bytes = rem_bytes;

      return cur_node;

    }

    // Add the remainder block and, if needed, insert its size.

    rem_node->set_size(rem_bytes);

    rem_node->set_next(free_[rem].head_node_);

    free_[rem].head_node_ = rem_node->address();

    if (rem_node->next() == NULL) InsertSize(rem);

  }

  available_ -= size_in_bytes;

  *wasted_bytes = 0;

  return cur_node;

}

#ifdef DEBUG