CSE2410 Fall 2014 Bounce

// Copyright 2012 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 "accessors.h"

#include "api.h"

#include "bootstrapper.h"

#include "codegen.h"

#include "compilation-cache.h"

#include "cpu-profiler.h"

#include "debug.h"

#include "deoptimizer.h"

#include "global-handles.h"

#include "heap-profiler.h"

#include "incremental-marking.h"

#include "isolate-inl.h"

#include "mark-compact.h"

#include "natives.h"

#include "objects-visiting.h"

#include "objects-visiting-inl.h"

#include "once.h"

#include "runtime-profiler.h"

#include "scopeinfo.h"

#include "snapshot.h"

#include "store-buffer.h"

#include "utils/random-number-generator.h"

#include "v8threads.h"

#include "v8utils.h"

#include "vm-state-inl.h"

#if V8_TARGET_ARCH_ARM && !V8_INTERPRETED_REGEXP

#include "regexp-macro-assembler.h"

#include "arm/regexp-macro-assembler-arm.h"

#endif

#if V8_TARGET_ARCH_MIPS && !V8_INTERPRETED_REGEXP

#include "regexp-macro-assembler.h"

#include "mips/regexp-macro-assembler-mips.h"

#endif

namespace v8 {

namespace internal {

Heap::Heap()

    : isolate_(NULL),

      code_range_size_(kIs64BitArch ? 512 * MB : 0),

// semispace_size_ should be a power of 2 and old_generation_size_ should be

// a multiple of Page::kPageSize.

      reserved_semispace_size_(8 * (kPointerSize / 4) * MB),

      max_semispace_size_(8 * (kPointerSize / 4)  * MB),

      initial_semispace_size_(Page::kPageSize),

      max_old_generation_size_(700ul * (kPointerSize / 4) * MB),

      max_executable_size_(256ul * (kPointerSize / 4) * MB),

// Variables set based on semispace_size_ and old_generation_size_ in

// ConfigureHeap (survived_since_last_expansion_, external_allocation_limit_)

// Will be 4 * reserved_semispace_size_ to ensure that young

// generation can be aligned to its size.

      survived_since_last_expansion_(0),

      sweep_generation_(0),

      always_allocate_scope_depth_(0),

      linear_allocation_scope_depth_(0),

      contexts_disposed_(0),

      global_ic_age_(0),

      flush_monomorphic_ics_(false),

      allocation_mementos_found_(0),

      scan_on_scavenge_pages_(0),

      new_space_(this),

      old_pointer_space_(NULL),

      old_data_space_(NULL),

      code_space_(NULL),

      map_space_(NULL),

      cell_space_(NULL),

      property_cell_space_(NULL),

      lo_space_(NULL),

      gc_state_(NOT_IN_GC),

      gc_post_processing_depth_(0),

      ms_count_(0),

      gc_count_(0),

      remembered_unmapped_pages_index_(0),

      unflattened_strings_length_(0),

#ifdef DEBUG

      allocation_timeout_(0),

      disallow_allocation_failure_(false),

#endif  // DEBUG

      new_space_high_promotion_mode_active_(false),

      old_generation_allocation_limit_(kMinimumOldGenerationAllocationLimit),

      size_of_old_gen_at_last_old_space_gc_(0),

      external_allocation_limit_(0),

      amount_of_external_allocated_memory_(0),

      amount_of_external_allocated_memory_at_last_global_gc_(0),

      old_gen_exhausted_(false),

      store_buffer_rebuilder_(store_buffer()),

      hidden_string_(NULL),

      gc_safe_size_of_old_object_(NULL),

      total_regexp_code_generated_(0),

      tracer_(NULL),

      young_survivors_after_last_gc_(0),

      high_survival_rate_period_length_(0),

      low_survival_rate_period_length_(0),

      survival_rate_(0),

      previous_survival_rate_trend_(Heap::STABLE),

      survival_rate_trend_(Heap::STABLE),

      max_gc_pause_(0.0),

      total_gc_time_ms_(0.0),

      max_alive_after_gc_(0),

      min_in_mutator_(kMaxInt),

      alive_after_last_gc_(0),

      last_gc_end_timestamp_(0.0),

      marking_time_(0.0),

      sweeping_time_(0.0),

      store_buffer_(this),

      marking_(this),

      incremental_marking_(this),

      number_idle_notifications_(0),

      last_idle_notification_gc_count_(0),

      last_idle_notification_gc_count_init_(false),

      mark_sweeps_since_idle_round_started_(0),

      gc_count_at_last_idle_gc_(0),

      scavenges_since_last_idle_round_(kIdleScavengeThreshold),

      full_codegen_bytes_generated_(0),

      crankshaft_codegen_bytes_generated_(0),

      gcs_since_last_deopt_(0),

#ifdef VERIFY_HEAP

      no_weak_object_verification_scope_depth_(0),

#endif

      promotion_queue_(this),

      configured_(false),

      chunks_queued_for_free_(NULL),

      relocation_mutex_(NULL) {

  // Allow build-time customization of the max semispace size. Building

  // V8 with snapshots and a non-default max semispace size is much

  // easier if you can define it as part of the build environment.

#if defined(V8_MAX_SEMISPACE_SIZE)

  max_semispace_size_ = reserved_semispace_size_ = V8_MAX_SEMISPACE_SIZE;

#endif

  // Ensure old_generation_size_ is a multiple of kPageSize.

  ASSERT(MB >= Page::kPageSize);

  intptr_t max_virtual = OS::MaxVirtualMemory();

  if (max_virtual > 0) {

    if (code_range_size_ > 0) {

      // Reserve no more than 1/8 of the memory for the code range.

      code_range_size_ = Min(code_range_size_, max_virtual >> 3);

    }

  }

  memset(roots_, 0, sizeof(roots_[0]) * kRootListLength);

  native_contexts_list_ = NULL;

  array_buffers_list_ = Smi::FromInt(0);

  allocation_sites_list_ = Smi::FromInt(0);

  mark_compact_collector_.heap_ = this;

  external_string_table_.heap_ = this;

  // Put a dummy entry in the remembered pages so we can find the list the

  // minidump even if there are no real unmapped pages.

  RememberUnmappedPage(NULL, false);

  ClearObjectStats(true);

}

intptr_t Heap::Capacity() {

  if (!HasBeenSetUp()) return 0;

  return new_space_.Capacity() +

      old_pointer_space_->Capacity() +

      old_data_space_->Capacity() +

      code_space_->Capacity() +

      map_space_->Capacity() +

      cell_space_->Capacity() +

      property_cell_space_->Capacity();

}

intptr_t Heap::CommittedMemory() {

  if (!HasBeenSetUp()) return 0;

  return new_space_.CommittedMemory() +

      old_pointer_space_->CommittedMemory() +

      old_data_space_->CommittedMemory() +

      code_space_->CommittedMemory() +

      map_space_->CommittedMemory() +

      cell_space_->CommittedMemory() +

      property_cell_space_->CommittedMemory() +

      lo_space_->Size();

}

size_t Heap::CommittedPhysicalMemory() {

  if (!HasBeenSetUp()) return 0;

  return new_space_.CommittedPhysicalMemory() +

      old_pointer_space_->CommittedPhysicalMemory() +

      old_data_space_->CommittedPhysicalMemory() +

      code_space_->CommittedPhysicalMemory() +

      map_space_->CommittedPhysicalMemory() +

      cell_space_->CommittedPhysicalMemory() +

      property_cell_space_->CommittedPhysicalMemory() +

      lo_space_->CommittedPhysicalMemory();

}

intptr_t Heap::CommittedMemoryExecutable() {

  if (!HasBeenSetUp()) return 0;

  return isolate()->memory_allocator()->SizeExecutable();

}

intptr_t Heap::Available() {

  if (!HasBeenSetUp()) return 0;

  return new_space_.Available() +

      old_pointer_space_->Available() +

      old_data_space_->Available() +

      code_space_->Available() +

      map_space_->Available() +

      cell_space_->Available() +

      property_cell_space_->Available();

}

bool Heap::HasBeenSetUp() {

  return old_pointer_space_ != NULL &&

         old_data_space_ != NULL &&

         code_space_ != NULL &&

         map_space_ != NULL &&

         cell_space_ != NULL &&

         property_cell_space_ != NULL &&

         lo_space_ != NULL;

}

int Heap::GcSafeSizeOfOldObject(HeapObject* object) {

  if (IntrusiveMarking::IsMarked(object)) {

    return IntrusiveMarking::SizeOfMarkedObject(object);

  }

  return object->SizeFromMap(object->map());

}

GarbageCollector Heap::SelectGarbageCollector(AllocationSpace space,

                                              const char** reason) {

  // Is global GC requested?

  if (space != NEW_SPACE) {

    isolate_->counters()->gc_compactor_caused_by_request()->Increment();

    *reason = "GC in old space requested";

    return MARK_COMPACTOR;

  }

  if (FLAG_gc_global || (FLAG_stress_compaction && (gc_count_ & 1) != 0)) {

    *reason = "GC in old space forced by flags";

    return MARK_COMPACTOR;

  }

  // Is enough data promoted to justify a global GC?

  if (OldGenerationAllocationLimitReached()) {

    isolate_->counters()->gc_compactor_caused_by_promoted_data()->Increment();

    *reason = "promotion limit reached";

    return MARK_COMPACTOR;

  }

  // Have allocation in OLD and LO failed?

  if (old_gen_exhausted_) {

    isolate_->counters()->

        gc_compactor_caused_by_oldspace_exhaustion()->Increment();

    *reason = "old generations exhausted";

    return MARK_COMPACTOR;

  }

  // Is there enough space left in OLD to guarantee that a scavenge can

  // succeed?

  //

  // Note that MemoryAllocator->MaxAvailable() undercounts the memory available

  // for object promotion. It counts only the bytes that the memory

  // allocator has not yet allocated from the OS and assigned to any space,

  // and does not count available bytes already in the old space or code

  // space.  Undercounting is safe---we may get an unrequested full GC when

  // a scavenge would have succeeded.

  if (isolate_->memory_allocator()->MaxAvailable() <= new_space_.Size()) {

    isolate_->counters()->

        gc_compactor_caused_by_oldspace_exhaustion()->Increment();

    *reason = "scavenge might not succeed";

    return MARK_COMPACTOR;

  }

  // Default

  *reason = NULL;

  return SCAVENGER;

}

// TODO(1238405): Combine the infrastructure for --heap-stats and

// --log-gc to avoid the complicated preprocessor and flag testing.

void Heap::ReportStatisticsBeforeGC() {

  // Heap::ReportHeapStatistics will also log NewSpace statistics when

  // compiled --log-gc is set.  The following logic is used to avoid

  // double logging.

#ifdef DEBUG

  if (FLAG_heap_stats || FLAG_log_gc) new_space_.CollectStatistics();

  if (FLAG_heap_stats) {

    ReportHeapStatistics("Before GC");

  } else if (FLAG_log_gc) {

    new_space_.ReportStatistics();

  }

  if (FLAG_heap_stats || FLAG_log_gc) new_space_.ClearHistograms();

#else

  if (FLAG_log_gc) {

    new_space_.CollectStatistics();

    new_space_.ReportStatistics();

    new_space_.ClearHistograms();

  }

#endif  // DEBUG

}

void Heap::PrintShortHeapStatistics() {

  if (!FLAG_trace_gc_verbose) return;

  PrintPID("Memory allocator,   used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB\n",

           isolate_->memory_allocator()->Size() / KB,

           isolate_->memory_allocator()->Available() / KB);

  PrintPID("New space,          used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           new_space_.Size() / KB,

           new_space_.Available() / KB,

           new_space_.CommittedMemory() / KB);

  PrintPID("Old pointers,       used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           old_pointer_space_->SizeOfObjects() / KB,

           old_pointer_space_->Available() / KB,

           old_pointer_space_->CommittedMemory() / KB);

  PrintPID("Old data space,     used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           old_data_space_->SizeOfObjects() / KB,

           old_data_space_->Available() / KB,

           old_data_space_->CommittedMemory() / KB);

  PrintPID("Code space,         used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           code_space_->SizeOfObjects() / KB,

           code_space_->Available() / KB,

           code_space_->CommittedMemory() / KB);

  PrintPID("Map space,          used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           map_space_->SizeOfObjects() / KB,

           map_space_->Available() / KB,

           map_space_->CommittedMemory() / KB);

  PrintPID("Cell space,         used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           cell_space_->SizeOfObjects() / KB,

           cell_space_->Available() / KB,

           cell_space_->CommittedMemory() / KB);

  PrintPID("PropertyCell space, used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           property_cell_space_->SizeOfObjects() / KB,

           property_cell_space_->Available() / KB,

           property_cell_space_->CommittedMemory() / KB);

  PrintPID("Large object space, used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           lo_space_->SizeOfObjects() / KB,

           lo_space_->Available() / KB,

           lo_space_->CommittedMemory() / KB);

  PrintPID("All spaces,         used: %6" V8_PTR_PREFIX "d KB"

               ", available: %6" V8_PTR_PREFIX "d KB"

               ", committed: %6" V8_PTR_PREFIX "d KB\n",

           this->SizeOfObjects() / KB,

           this->Available() / KB,

           this->CommittedMemory() / KB);

  PrintPID("External memory reported: %6" V8_PTR_PREFIX "d KB\n",

           amount_of_external_allocated_memory_ / KB);

  PrintPID("Total time spent in GC  : %.1f ms\n", total_gc_time_ms_);

}

// TODO(1238405): Combine the infrastructure for --heap-stats and

// --log-gc to avoid the complicated preprocessor and flag testing.

void Heap::ReportStatisticsAfterGC() {

  // Similar to the before GC, we use some complicated logic to ensure that

  // NewSpace statistics are logged exactly once when --log-gc is turned on.

#if defined(DEBUG)

  if (FLAG_heap_stats) {

    new_space_.CollectStatistics();

    ReportHeapStatistics("After GC");

  } else if (FLAG_log_gc) {

    new_space_.ReportStatistics();

  }

#else

  if (FLAG_log_gc) new_space_.ReportStatistics();

#endif  // DEBUG

}

void Heap::GarbageCollectionPrologue() {

  {  AllowHeapAllocation for_the_first_part_of_prologue;

    isolate_->transcendental_cache()->Clear();

    ClearJSFunctionResultCaches();

    gc_count_++;

    unflattened_strings_length_ = 0;

    if (FLAG_flush_code && FLAG_flush_code_incrementally) {

      mark_compact_collector()->EnableCodeFlushing(true);

    }

#ifdef VERIFY_HEAP

    if (FLAG_verify_heap) {

      Verify();

    }

#endif

  }

#ifdef DEBUG

  ASSERT(!AllowHeapAllocation::IsAllowed() && gc_state_ == NOT_IN_GC);

  if (FLAG_gc_verbose) Print();

  ReportStatisticsBeforeGC();

#endif  // DEBUG

  store_buffer()->GCPrologue();

  if (FLAG_concurrent_osr) {

    isolate()->optimizing_compiler_thread()->AgeBufferedOsrJobs();

  }

}

intptr_t Heap::SizeOfObjects() {

  intptr_t total = 0;

  AllSpaces spaces(this);

  for (Space* space = spaces.next(); space != NULL; space = spaces.next()) {

    total += space->SizeOfObjects();

  }

  return total;

}

void Heap::RepairFreeListsAfterBoot() {

  PagedSpaces spaces(this);

  for (PagedSpace* space = spaces.next();

       space != NULL;

       space = spaces.next()) {

    space->RepairFreeListsAfterBoot();

  }

}

void Heap::GarbageCollectionEpilogue() {

  store_buffer()->GCEpilogue();

  // In release mode, we only zap the from space under heap verification.

  if (Heap::ShouldZapGarbage()) {

    ZapFromSpace();

  }

#ifdef VERIFY_HEAP

  if (FLAG_verify_heap) {

    Verify();

  }

#endif

  AllowHeapAllocation for_the_rest_of_the_epilogue;

#ifdef DEBUG

  if (FLAG_print_global_handles) isolate_->global_handles()->Print();

  if (FLAG_print_handles) PrintHandles();

  if (FLAG_gc_verbose) Print();

  if (FLAG_code_stats) ReportCodeStatistics("After GC");

#endif

  if (FLAG_deopt_every_n_garbage_collections > 0) {

    if (++gcs_since_last_deopt_ == FLAG_deopt_every_n_garbage_collections) {

      Deoptimizer::DeoptimizeAll(isolate());

      gcs_since_last_deopt_ = 0;

    }

  }

  isolate_->counters()->alive_after_last_gc()->Set(

      static_cast<int>(SizeOfObjects()));

  isolate_->counters()->string_table_capacity()->Set(

      string_table()->Capacity());

  isolate_->counters()->number_of_symbols()->Set(

      string_table()->NumberOfElements());

  if (full_codegen_bytes_generated_ + crankshaft_codegen_bytes_generated_ > 0) {

    isolate_->counters()->codegen_fraction_crankshaft()->AddSample(

        static_cast<int>((crankshaft_codegen_bytes_generated_ * 100.0) /

            (crankshaft_codegen_bytes_generated_

            + full_codegen_bytes_generated_)));

  }

  if (CommittedMemory() > 0) {

    isolate_->counters()->external_fragmentation_total()->AddSample(

        static_cast<int>(100 - (SizeOfObjects() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_fraction_new_space()->

        AddSample(static_cast<int>(

            (new_space()->CommittedMemory() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_fraction_old_pointer_space()->AddSample(

        static_cast<int>(

            (old_pointer_space()->CommittedMemory() * 100.0) /

            CommittedMemory()));

    isolate_->counters()->heap_fraction_old_data_space()->AddSample(

        static_cast<int>(

            (old_data_space()->CommittedMemory() * 100.0) /

            CommittedMemory()));

    isolate_->counters()->heap_fraction_code_space()->

        AddSample(static_cast<int>(

            (code_space()->CommittedMemory() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_fraction_map_space()->AddSample(

        static_cast<int>(

            (map_space()->CommittedMemory() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_fraction_cell_space()->AddSample(

        static_cast<int>(

            (cell_space()->CommittedMemory() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_fraction_property_cell_space()->

        AddSample(static_cast<int>(

            (property_cell_space()->CommittedMemory() * 100.0) /

            CommittedMemory()));

    isolate_->counters()->heap_fraction_lo_space()->

        AddSample(static_cast<int>(

            (lo_space()->CommittedMemory() * 100.0) / CommittedMemory()));

    isolate_->counters()->heap_sample_total_committed()->AddSample(

        static_cast<int>(CommittedMemory() / KB));

    isolate_->counters()->heap_sample_total_used()->AddSample(

        static_cast<int>(SizeOfObjects() / KB));

    isolate_->counters()->heap_sample_map_space_committed()->AddSample(

        static_cast<int>(map_space()->CommittedMemory() / KB));

    isolate_->counters()->heap_sample_cell_space_committed()->AddSample(

        static_cast<int>(cell_space()->CommittedMemory() / KB));

    isolate_->counters()->

        heap_sample_property_cell_space_committed()->

            AddSample(static_cast<int>(

                property_cell_space()->CommittedMemory() / KB));

    isolate_->counters()->heap_sample_code_space_committed()->AddSample(

        static_cast<int>(code_space()->CommittedMemory() / KB));

  }

#define UPDATE_COUNTERS_FOR_SPACE(space)                                       \

  isolate_->counters()->space##_bytes_available()->Set(                        \

      static_cast<int>(space()->Available()));                                 \

  isolate_->counters()->space##_bytes_committed()->Set(                        \

      static_cast<int>(space()->CommittedMemory()));                           \

  isolate_->counters()->space##_bytes_used()->Set(                             \

      static_cast<int>(space()->SizeOfObjects()));

#define UPDATE_FRAGMENTATION_FOR_SPACE(space)                                  \

  if (space()->CommittedMemory() > 0) {                                        \

    isolate_->counters()->external_fragmentation_##space()->AddSample(         \

        static_cast<int>(100 -                                                 \

            (space()->SizeOfObjects() * 100.0) / space()->CommittedMemory())); \

  }

#define UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(space)                     \

  UPDATE_COUNTERS_FOR_SPACE(space)                                             \

  UPDATE_FRAGMENTATION_FOR_SPACE(space)

  UPDATE_COUNTERS_FOR_SPACE(new_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(old_pointer_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(old_data_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(code_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(map_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(cell_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(property_cell_space)

  UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE(lo_space)

#undef UPDATE_COUNTERS_FOR_SPACE

#undef UPDATE_FRAGMENTATION_FOR_SPACE

#undef UPDATE_COUNTERS_AND_FRAGMENTATION_FOR_SPACE

#if defined(DEBUG)

  ReportStatisticsAfterGC();

#endif  // DEBUG

#ifdef ENABLE_DEBUGGER_SUPPORT

  isolate_->debug()->AfterGarbageCollection();

#endif  // ENABLE_DEBUGGER_SUPPORT

}

void Heap::CollectAllGarbage(int flags, const char* gc_reason) {

  // Since we are ignoring the return value, the exact choice of space does

  // not matter, so long as we do not specify NEW_SPACE, which would not

  // cause a full GC.

  mark_compact_collector_.SetFlags(flags);

  CollectGarbage(OLD_POINTER_SPACE, gc_reason);

  mark_compact_collector_.SetFlags(kNoGCFlags);

}

void Heap::CollectAllAvailableGarbage(const char* gc_reason) {

  // Since we are ignoring the return value, the exact choice of space does

  // not matter, so long as we do not specify NEW_SPACE, which would not

  // cause a full GC.

  // Major GC would invoke weak handle callbacks on weakly reachable

  // handles, but won't collect weakly reachable objects until next

  // major GC.  Therefore if we collect aggressively and weak handle callback

  // has been invoked, we rerun major GC to release objects which become

  // garbage.

  // Note: as weak callbacks can execute arbitrary code, we cannot

  // hope that eventually there will be no weak callbacks invocations.

  // Therefore stop recollecting after several attempts.

  if (FLAG_concurrent_recompilation) {

    // The optimizing compiler may be unnecessarily holding on to memory.

    DisallowHeapAllocation no_recursive_gc;

    isolate()->optimizing_compiler_thread()->Flush();

  }

  mark_compact_collector()->SetFlags(kMakeHeapIterableMask |

                                     kReduceMemoryFootprintMask);

  isolate_->compilation_cache()->Clear();

  const int kMaxNumberOfAttempts = 7;

  const int kMinNumberOfAttempts = 2;

  for (int attempt = 0; attempt < kMaxNumberOfAttempts; attempt++) {

    if (!CollectGarbage(OLD_POINTER_SPACE, MARK_COMPACTOR, gc_reason, NULL) &&

        attempt + 1 >= kMinNumberOfAttempts) {

      break;

    }

  }

  mark_compact_collector()->SetFlags(kNoGCFlags);

  new_space_.Shrink();

  UncommitFromSpace();

  incremental_marking()->UncommitMarkingDeque();

}

bool Heap::CollectGarbage(AllocationSpace space,

                          GarbageCollector collector,

                          const char* gc_reason,

                          const char* collector_reason) {

  // The VM is in the GC state until exiting this function.

  VMState<GC> state(isolate_);

#ifdef DEBUG

  // Reset the allocation timeout to the GC interval, but make sure to

  // allow at least a few allocations after a collection. The reason

  // for this is that we have a lot of allocation sequences and we

  // assume that a garbage collection will allow the subsequent

  // allocation attempts to go through.

  allocation_timeout_ = Max(6, FLAG_gc_interval);

#endif

  if (collector == SCAVENGER && !incremental_marking()->IsStopped()) {

    if (FLAG_trace_incremental_marking) {

      PrintF("[IncrementalMarking] Scavenge during marking.\n");

    }

  }

  if (collector == MARK_COMPACTOR &&

      !mark_compact_collector()->abort_incremental_marking() &&

      !incremental_marking()->IsStopped() &&

      !incremental_marking()->should_hurry() &&

      FLAG_incremental_marking_steps) {

    // Make progress in incremental marking.

    const intptr_t kStepSizeWhenDelayedByScavenge = 1 * MB;

    incremental_marking()->Step(kStepSizeWhenDelayedByScavenge,

                                IncrementalMarking::NO_GC_VIA_STACK_GUARD);

    if (!incremental_marking()->IsComplete()) {

      if (FLAG_trace_incremental_marking) {

        PrintF("[IncrementalMarking] Delaying MarkSweep.\n");

      }

      collector = SCAVENGER;

      collector_reason = "incremental marking delaying mark-sweep";

    }

  }

  bool next_gc_likely_to_collect_more = false;

  { GCTracer tracer(this, gc_reason, collector_reason);

    ASSERT(AllowHeapAllocation::IsAllowed());

    DisallowHeapAllocation no_allocation_during_gc;

    GarbageCollectionPrologue();

    // The GC count was incremented in the prologue.  Tell the tracer about

    // it.

    tracer.set_gc_count(gc_count_);

    // Tell the tracer which collector we've selected.

    tracer.set_collector(collector);

    {

      HistogramTimerScope histogram_timer_scope(

          (collector == SCAVENGER) ? isolate_->counters()->gc_scavenger()

                                   : isolate_->counters()->gc_compactor());

      next_gc_likely_to_collect_more =

          PerformGarbageCollection(collector, &tracer);

    }

    GarbageCollectionEpilogue();

  }

  // Start incremental marking for the next cycle. The heap snapshot

  // generator needs incremental marking to stay off after it aborted.

  if (!mark_compact_collector()->abort_incremental_marking() &&

      incremental_marking()->IsStopped() &&

      incremental_marking()->WorthActivating() &&

      NextGCIsLikelyToBeFull()) {

    incremental_marking()->Start();

  }

  return next_gc_likely_to_collect_more;

}

int Heap::NotifyContextDisposed() {

  if (FLAG_concurrent_recompilation) {

    // Flush the queued recompilation tasks.

    isolate()->optimizing_compiler_thread()->Flush();

  }

  flush_monomorphic_ics_ = true;

  return ++contexts_disposed_;

}

void Heap::PerformScavenge() {

  GCTracer tracer(this, NULL, NULL);

  if (incremental_marking()->IsStopped()) {

    PerformGarbageCollection(SCAVENGER, &tracer);

  } else {

    PerformGarbageCollection(MARK_COMPACTOR, &tracer);

  }

}

void Heap::MoveElements(FixedArray* array,

                        int dst_index,

                        int src_index,

                        int len) {

  if (len == 0) return;

  ASSERT(array->map() != fixed_cow_array_map());

  Object** dst_objects = array->data_start() + dst_index;

  OS::MemMove(dst_objects,

              array->data_start() + src_index,

              len * kPointerSize);

  if (!InNewSpace(array)) {

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

      // TODO(hpayer): check store buffer for entries

      if (InNewSpace(dst_objects[i])) {

        RecordWrite(array->address(), array->OffsetOfElementAt(dst_index + i));

      }

    }

  }

  incremental_marking()->RecordWrites(array);

}

#ifdef VERIFY_HEAP

// Helper class for verifying the string table.

class StringTableVerifier : public ObjectVisitor {

 public:

  void VisitPointers(Object** start, Object** end) {

    // Visit all HeapObject pointers in [start, end).

    for (Object** p = start; p < end; p++) {

      if ((*p)->IsHeapObject()) {

        // Check that the string is actually internalized.

        CHECK((*p)->IsTheHole() || (*p)->IsUndefined() ||

              (*p)->IsInternalizedString());

      }

    }

  }

};

static void VerifyStringTable(Heap* heap) {

  StringTableVerifier verifier;

  heap->string_table()->IterateElements(&verifier);

}

#endif  // VERIFY_HEAP

static bool AbortIncrementalMarkingAndCollectGarbage(

    Heap* heap,

    AllocationSpace space,

    const char* gc_reason = NULL) {

  heap->mark_compact_collector()->SetFlags(Heap::kAbortIncrementalMarkingMask);

  bool result = heap->CollectGarbage(space, gc_reason);

  heap->mark_compact_collector()->SetFlags(Heap::kNoGCFlags);

  return result;

}

void Heap::ReserveSpace(

    int *sizes,

    Address *locations_out) {

  bool gc_performed = true;

  int counter = 0;

  static const int kThreshold = 20;

  while (gc_performed && counter++ < kThreshold) {

    gc_performed = false;

    ASSERT(NEW_SPACE == FIRST_PAGED_SPACE - 1);

    for (int space = NEW_SPACE; space <= LAST_PAGED_SPACE; space++) {

      if (sizes[space] != 0) {

        MaybeObject* allocation;

        if (space == NEW_SPACE) {

          allocation = new_space()->AllocateRaw(sizes[space]);

        } else {

          allocation = paged_space(space)->AllocateRaw(sizes[space]);

        }

        FreeListNode* node;

        if (!allocation->To<FreeListNode>(&node)) {

          if (space == NEW_SPACE) {

            Heap::CollectGarbage(NEW_SPACE,

                                 "failed to reserve space in the new space");

          } else {

            AbortIncrementalMarkingAndCollectGarbage(

                this,

                static_cast<AllocationSpace>(space),

                "failed to reserve space in paged space");

          }

          gc_performed = true;

          break;

        } else {

          // Mark with a free list node, in case we have a GC before

          // deserializing.

          node->set_size(this, sizes[space]);

          locations_out[space] = node->address();

        }

      }

    }

  }

  if (gc_performed) {

    // Failed to reserve the space after several attempts.

    V8::FatalProcessOutOfMemory("Heap::ReserveSpace");

  }

}

void Heap::EnsureFromSpaceIsCommitted() {

  if (new_space_.CommitFromSpaceIfNeeded()) return;

  // Committing memory to from space failed.

  // Memory is exhausted and we will die.

  V8::FatalProcessOutOfMemory("Committing semi space failed.");

}

void Heap::ClearJSFunctionResultCaches() {

  if (isolate_->bootstrapper()->IsActive()) return;

  Object* context = native_contexts_list_;

  while (!context->IsUndefined()) {

    // Get the caches for this context. GC can happen when the context

    // is not fully initialized, so the caches can be undefined.

    Object* caches_or_undefined =

        Context::cast(context)->get(Context::JSFUNCTION_RESULT_CACHES_INDEX);

    if (!caches_or_undefined->IsUndefined()) {

      FixedArray* caches = FixedArray::cast(caches_or_undefined);

      // Clear the caches:

      int length = caches->length();

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

        JSFunctionResultCache::cast(caches->get(i))->Clear();

      }

    }

    // Get the next context:

    context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);

  }

}

void Heap::ClearNormalizedMapCaches() {

  if (isolate_->bootstrapper()->IsActive() &&

      !incremental_marking()->IsMarking()) {

    return;

  }

  Object* context = native_contexts_list_;

  while (!context->IsUndefined()) {

    // GC can happen when the context is not fully initialized,

    // so the cache can be undefined.

    Object* cache =

        Context::cast(context)->get(Context::NORMALIZED_MAP_CACHE_INDEX);

    if (!cache->IsUndefined()) {

      NormalizedMapCache::cast(cache)->Clear();

    }

    context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);

  }

}

void Heap::UpdateSurvivalRateTrend(int start_new_space_size) {

  double survival_rate =

      (static_cast<double>(young_survivors_after_last_gc_) * 100) /

      start_new_space_size;

  if (survival_rate > kYoungSurvivalRateHighThreshold) {

    high_survival_rate_period_length_++;

  } else {

    high_survival_rate_period_length_ = 0;

  }

  if (survival_rate < kYoungSurvivalRateLowThreshold) {

    low_survival_rate_period_length_++;

  } else {

    low_survival_rate_period_length_ = 0;

  }

  double survival_rate_diff = survival_rate_ - survival_rate;

  if (survival_rate_diff > kYoungSurvivalRateAllowedDeviation) {

    set_survival_rate_trend(DECREASING);

  } else if (survival_rate_diff < -kYoungSurvivalRateAllowedDeviation) {

    set_survival_rate_trend(INCREASING);

  } else {

    set_survival_rate_trend(STABLE);

  }

  survival_rate_ = survival_rate;

}

bool Heap::PerformGarbageCollection(GarbageCollector collector,

                                    GCTracer* tracer) {

  bool next_gc_likely_to_collect_more = false;

  if (collector != SCAVENGER) {

    PROFILE(isolate_, CodeMovingGCEvent());

  }

#ifdef VERIFY_HEAP

  if (FLAG_verify_heap) {

    VerifyStringTable(this);

  }

#endif

  GCType gc_type =

      collector == MARK_COMPACTOR ? kGCTypeMarkSweepCompact : kGCTypeScavenge;

  {

    GCTracer::Scope scope(tracer, GCTracer::Scope::EXTERNAL);

    VMState<EXTERNAL> state(isolate_);

    HandleScope handle_scope(isolate_);

    CallGCPrologueCallbacks(gc_type, kNoGCCallbackFlags);

  }

  EnsureFromSpaceIsCommitted();

  int start_new_space_size = Heap::new_space()->SizeAsInt();

  if (IsHighSurvivalRate()) {

    // We speed up the incremental marker if it is running so that it

    // does not fall behind the rate of promotion, which would cause a

    // constantly growing old space.

    incremental_marking()->NotifyOfHighPromotionRate();

  }

  if (collector == MARK_COMPACTOR) {

    // Perform mark-sweep with optional compaction.

    MarkCompact(tracer);

    sweep_generation_++;

    UpdateSurvivalRateTrend(start_new_space_size);

    size_of_old_gen_at_last_old_space_gc_ = PromotedSpaceSizeOfObjects();

    old_generation_allocation_limit_ =

        OldGenerationAllocationLimit(size_of_old_gen_at_last_old_space_gc_);

    old_gen_exhausted_ = false;

  } else {

    tracer_ = tracer;

    Scavenge();

    tracer_ = NULL;

    UpdateSurvivalRateTrend(start_new_space_size);

  }

  if (!new_space_high_promotion_mode_active_ &&

      new_space_.Capacity() == new_space_.MaximumCapacity() &&

      IsStableOrIncreasingSurvivalTrend() &&

      IsHighSurvivalRate()) {

    // Stable high survival rates even though young generation is at

    // maximum capacity indicates that most objects will be promoted.

    // To decrease scavenger pauses and final mark-sweep pauses, we

    // have to limit maximal capacity of the young generation.

    SetNewSpaceHighPromotionModeActive(true);

    if (FLAG_trace_gc) {

      PrintPID("Limited new space size due to high promotion rate: %d MB\n",

               new_space_.InitialCapacity() / MB);

    }

    // Support for global pre-tenuring uses the high promotion mode as a

    // heuristic indicator of whether to pretenure or not, we trigger

    // deoptimization here to take advantage of pre-tenuring as soon as

    // possible.

    if (FLAG_pretenuring) {

      isolate_->stack_guard()->FullDeopt();

    }

  } else if (new_space_high_promotion_mode_active_ &&

      IsStableOrDecreasingSurvivalTrend() &&

      IsLowSurvivalRate()) {

    // Decreasing low survival rates might indicate that the above high

    // promotion mode is over and we should allow the young generation

    // to grow again.

    SetNewSpaceHighPromotionModeActive(false);

    if (FLAG_trace_gc) {

      PrintPID("Unlimited new space size due to low promotion rate: %d MB\n",

               new_space_.MaximumCapacity() / MB);

    }

    // Trigger deoptimization here to turn off pre-tenuring as soon as

    // possible.

    if (FLAG_pretenuring) {

      isolate_->stack_guard()->FullDeopt();

    }

  }

  if (new_space_high_promotion_mode_active_ &&

      new_space_.Capacity() > new_space_.InitialCapacity()) {

    new_space_.Shrink();

  }

  isolate_->counters()->objs_since_last_young()->Set(0);

  // Callbacks that fire after this point might trigger nested GCs and

  // restart incremental marking, the assertion can't be moved down.

  ASSERT(collector == SCAVENGER || incremental_marking()->IsStopped());

  gc_post_processing_depth_++;

  { AllowHeapAllocation allow_allocation;

    GCTracer::Scope scope(tracer, GCTracer::Scope::EXTERNAL);

    next_gc_likely_to_collect_more =

        isolate_->global_handles()->PostGarbageCollectionProcessing(

            collector, tracer);

  }

  gc_post_processing_depth_--;

  isolate_->eternal_handles()->PostGarbageCollectionProcessing(this);

  // Update relocatables.

  Relocatable::PostGarbageCollectionProcessing(isolate_);

  if (collector == MARK_COMPACTOR) {

    // Register the amount of external allocated memory.

    amount_of_external_allocated_memory_at_last_global_gc_ =

        amount_of_external_allocated_memory_;

  }

  {

    GCTracer::Scope scope(tracer, GCTracer::Scope::EXTERNAL);

    VMState<EXTERNAL> state(isolate_);

    HandleScope handle_scope(isolate_);

    CallGCEpilogueCallbacks(gc_type);

  }

#ifdef VERIFY_HEAP

  if (FLAG_verify_heap) {

    VerifyStringTable(this);

  }

#endif

  return next_gc_likely_to_collect_more;

}

void Heap::CallGCPrologueCallbacks(GCType gc_type, GCCallbackFlags flags) {

  for (int i = 0; i < gc_prologue_callbacks_.length(); ++i) {

    if (gc_type & gc_prologue_callbacks_[i].gc_type) {

      if (!gc_prologue_callbacks_[i].pass_isolate_) {

        v8::GCPrologueCallback callback =

            reinterpret_cast<v8::GCPrologueCallback>(

                gc_prologue_callbacks_[i].callback);

        callback(gc_type, flags);

      } else {

        v8::Isolate* isolate = reinterpret_cast<v8::Isolate*>(this->isolate());

        gc_prologue_callbacks_[i].callback(isolate, gc_type, flags);

      }

    }

  }

}

void Heap::CallGCEpilogueCallbacks(GCType gc_type) {

  for (int i = 0; i < gc_epilogue_callbacks_.length(); ++i) {

    if (gc_type & gc_epilogue_callbacks_[i].gc_type) {

      if (!gc_epilogue_callbacks_[i].pass_isolate_) {

        v8::GCPrologueCallback callback =

            reinterpret_cast<v8::GCPrologueCallback>(

                gc_epilogue_callbacks_[i].callback);

        callback(gc_type, kNoGCCallbackFlags);

      } else {

        v8::Isolate* isolate = reinterpret_cast<v8::Isolate*>(this->isolate());

        gc_epilogue_callbacks_[i].callback(

            isolate, gc_type, kNoGCCallbackFlags);

      }

    }

  }

}

void Heap::MarkCompact(GCTracer* tracer) {

  gc_state_ = MARK_COMPACT;

  LOG(isolate_, ResourceEvent("markcompact", "begin"));

  mark_compact_collector_.Prepare(tracer);

  ms_count_++;

  tracer->set_full_gc_count(ms_count_);

  MarkCompactPrologue();

  mark_compact_collector_.CollectGarbage();

  LOG(isolate_, ResourceEvent("markcompact", "end"));

  gc_state_ = NOT_IN_GC;

  isolate_->counters()->objs_since_last_full()->Set(0);

  contexts_disposed_ = 0;

  flush_monomorphic_ics_ = false;

}

void Heap::MarkCompactPrologue() {

  // At any old GC clear the keyed lookup cache to enable collection of unused

  // maps.

  isolate_->keyed_lookup_cache()->Clear();

  isolate_->context_slot_cache()->Clear();

  isolate_->descriptor_lookup_cache()->Clear();

  RegExpResultsCache::Clear(string_split_cache());

  RegExpResultsCache::Clear(regexp_multiple_cache());

  isolate_->compilation_cache()->MarkCompactPrologue();

  CompletelyClearInstanceofCache();

  FlushNumberStringCache();

  if (FLAG_cleanup_code_caches_at_gc) {

    polymorphic_code_cache()->set_cache(undefined_value());

  }

  ClearNormalizedMapCaches();

}

// Helper class for copying HeapObjects

class ScavengeVisitor: public ObjectVisitor {

 public:

  explicit ScavengeVisitor(Heap* heap) : heap_(heap) {}

  void VisitPointer(Object** p) { ScavengePointer(p); }

  void VisitPointers(Object** start, Object** end) {

    // Copy all HeapObject pointers in [start, end)

    for (Object** p = start; p < end; p++) ScavengePointer(p);

  }

 private:

  void ScavengePointer(Object** p) {

    Object* object = *p;

    if (!heap_->InNewSpace(object)) return;

    Heap::ScavengeObject(reinterpret_cast<HeapObject**>(p),

                         reinterpret_cast<HeapObject*>(object));

  }

  Heap* heap_;

};

#ifdef VERIFY_HEAP

// Visitor class to verify pointers in code or data space do not point into

// new space.

class VerifyNonPointerSpacePointersVisitor: public ObjectVisitor {

 public:

  explicit VerifyNonPointerSpacePointersVisitor(Heap* heap) : heap_(heap) {}

  void VisitPointers(Object** start, Object**end) {

    for (Object** current = start; current < end; current++) {

      if ((*current)->IsHeapObject()) {

        CHECK(!heap_->InNewSpace(HeapObject::cast(*current)));

      }

    }

  }

 private:

  Heap* heap_;

};

static void VerifyNonPointerSpacePointers(Heap* heap) {

  // Verify that there are no pointers to new space in spaces where we

  // do not expect them.

  VerifyNonPointerSpacePointersVisitor v(heap);

  HeapObjectIterator code_it(heap->code_space());

  for (HeapObject* object = code_it.Next();

       object != NULL; object = code_it.Next())

    object->Iterate(&v);

  // The old data space was normally swept conservatively so that the iterator

  // doesn't work, so we normally skip the next bit.

  if (!heap->old_data_space()->was_swept_conservatively()) {

    HeapObjectIterator data_it(heap->old_data_space());

    for (HeapObject* object = data_it.Next();

         object != NULL; object = data_it.Next())

      object->Iterate(&v);

  }

}

#endif  // VERIFY_HEAP

void Heap::CheckNewSpaceExpansionCriteria() {

  if (new_space_.Capacity() < new_space_.MaximumCapacity() &&

      survived_since_last_expansion_ > new_space_.Capacity() &&

      !new_space_high_promotion_mode_active_) {

    // Grow the size of new space if there is room to grow, enough data

    // has survived scavenge since the last expansion and we are not in

    // high promotion mode.

    new_space_.Grow();

    survived_since_last_expansion_ = 0;

  }

}

static bool IsUnscavengedHeapObject(Heap* heap, Object** p) {

  return heap->InNewSpace(*p) &&

      !HeapObject::cast(*p)->map_word().IsForwardingAddress();

}

void Heap::ScavengeStoreBufferCallback(

    Heap* heap,

    MemoryChunk* page,

    StoreBufferEvent event) {

  heap->store_buffer_rebuilder_.Callback(page, event);

}

void StoreBufferRebuilder::Callback(MemoryChunk* page, StoreBufferEvent event) {

  if (event == kStoreBufferStartScanningPagesEvent) {

    start_of_current_page_ = NULL;

    current_page_ = NULL;

  } else if (event == kStoreBufferScanningPageEvent) {

    if (current_page_ != NULL) {

      // If this page already overflowed the store buffer during this iteration.

      if (current_page_->scan_on_scavenge()) {

        // Then we should wipe out the entries that have been added for it.

        store_buffer_->SetTop(start_of_current_page_);

      } else if (store_buffer_->Top() - start_of_current_page_ >=

                 (store_buffer_->Limit() - store_buffer_->Top()) >> 2) {

        // Did we find too many pointers in the previous page?  The heuristic is

        // that no page can take more then 1/5 the remaining slots in the store

        // buffer.

        current_page_->set_scan_on_scavenge(true);

        store_buffer_->SetTop(start_of_current_page_);

      } else {

        // In this case the page we scanned took a reasonable number of slots in

        // the store buffer.  It has now been rehabilitated and is no longer

        // marked scan_on_scavenge.

        ASSERT(!current_page_->scan_on_scavenge());

      }

    }

    start_of_current_page_ = store_buffer_->Top();

    current_page_ = page;

  } else if (event == kStoreBufferFullEvent) {

    // The current page overflowed the store buffer again.  Wipe out its entries

    // in the store buffer and mark it scan-on-scavenge again.  This may happen

    // several times while scanning.

    if (current_page_ == NULL) {

      // Store Buffer overflowed while scanning promoted objects.  These are not

      // in any particular page, though they are likely to be clustered by the

      // allocation routines.

      store_buffer_->EnsureSpace(StoreBuffer::kStoreBufferSize / 2);

    } else {

      // Store Buffer overflowed while scanning a particular old space page for

      // pointers to new space.

      ASSERT(current_page_ == page);

      ASSERT(page != NULL);

      current_page_->set_scan_on_scavenge(true);

      ASSERT(start_of_current_page_ != store_buffer_->Top());

      store_buffer_->SetTop(start_of_current_page_);

    }

  } else {

    UNREACHABLE();

  }

}

void PromotionQueue::Initialize() {

  // Assumes that a NewSpacePage exactly fits a number of promotion queue

  // entries (where each is a pair of intptr_t). This allows us to simplify

  // the test fpr when to switch pages.

  ASSERT((Page::kPageSize - MemoryChunk::kBodyOffset) % (2 * kPointerSize)

         == 0);

  limit_ = reinterpret_cast<intptr_t*>(heap_->new_space()->ToSpaceStart());

  front_ = rear_ =

      reinterpret_cast<intptr_t*>(heap_->new_space()->ToSpaceEnd());

  emergency_stack_ = NULL;

  guard_ = false;

}

void PromotionQueue::RelocateQueueHead() {

  ASSERT(emergency_stack_ == NULL);

  Page* p = Page::FromAllocationTop(reinterpret_cast<Address>(rear_));

  intptr_t* head_start = rear_;

  intptr_t* head_end =

      Min(front_, reinterpret_cast<intptr_t*>(p->area_end()));

  int entries_count =

      static_cast<int>(head_end - head_start) / kEntrySizeInWords;

  emergency_stack_ = new List<Entry>(2 * entries_count);

  while (head_start != head_end) {

    int size = static_cast<int>(*(head_start++));

    HeapObject* obj = reinterpret_cast<HeapObject*>(*(head_start++));

    emergency_stack_->Add(Entry(obj, size));

  }

  rear_ = head_end;

}

class ScavengeWeakObjectRetainer : public WeakObjectRetainer {

 public:

  explicit ScavengeWeakObjectRetainer(Heap* heap) : heap_(heap) { }

  virtual Object* RetainAs(Object* object) {

    if (!heap_->InFromSpace(object)) {

      return object;

    }