Merge experimental/gc branch to the bleeding_edge.

src/heap.h

 // Copyright 2011 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
@@ skipping 14 matching lines @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #ifndef V8_HEAP_H_
 #define V8_HEAP_H_
 
 #include <math.h>
 
 #include "allocation.h"
 #include "globals.h"
+#include "incremental-marking.h"
 #include "list.h"
 #include "mark-compact.h"
+#include "objects-visiting.h"
 #include "spaces.h"
 #include "splay-tree-inl.h"
+#include "store-buffer.h"
 #include "v8-counters.h"
+#include "v8globals.h"
 
 namespace v8 {
 namespace internal {
 
 // TODO(isolates): remove HEAP here
 #define HEAP (_inline_get_heap_())
 class Heap;
 inline Heap* _inline_get_heap_();
 
 
 // Defines all the roots in Heap.
 #define STRONG_ROOT_LIST(V)                                      \
-  /* Put the byte array map early.  We need it to be in place by the time   */ \
-  /* the deserializer hits the next page, since it wants to put a byte      */ \
-  /* array in the unused space at the end of the page.                      */ \
   V(Map, byte_array_map, ByteArrayMap)                                         \
+  V(Map, free_space_map, FreeSpaceMap)                                         \
   V(Map, one_pointer_filler_map, OnePointerFillerMap)                          \
   V(Map, two_pointer_filler_map, TwoPointerFillerMap)                          \
   /* Cluster the most popular ones in a few cache lines here at the top.    */ \
+  V(Smi, store_buffer_top, StoreBufferTop)                                     \
   V(Object, undefined_value, UndefinedValue)                                   \
   V(Object, the_hole_value, TheHoleValue)                                      \
   V(Object, null_value, NullValue)                                             \
   V(Object, true_value, TrueValue)                                             \
   V(Object, false_value, FalseValue)                                           \
   V(Object, arguments_marker, ArgumentsMarker)                                 \
   V(Map, heap_number_map, HeapNumberMap)                                       \
   V(Map, global_context_map, GlobalContextMap)                                 \
   V(Map, fixed_array_map, FixedArrayMap)                                       \
   V(Map, serialized_scope_info_map, SerializedScopeInfoMap)                    \
@@ skipping 162 matching lines @@
 // Forward declarations.
 class GCTracer;
 class HeapStats;
 class Isolate;
 class WeakObjectRetainer;
 
 
 typedef String* (*ExternalStringTableUpdaterCallback)(Heap* heap,
                                                       Object** pointer);
 
-typedef bool (*DirtyRegionCallback)(Heap* heap,
-                                    Address start,
-                                    Address end,
-                                    ObjectSlotCallback copy_object_func);
+class StoreBufferRebuilder {
+ public:
+  explicit StoreBufferRebuilder(StoreBuffer* store_buffer)
+      : store_buffer_(store_buffer) {
+  }
+
+  void Callback(MemoryChunk* page, StoreBufferEvent event);
+
+ private:
+  StoreBuffer* store_buffer_;
+
+  // We record in this variable how full the store buffer was when we started
+  // iterating over the current page, finding pointers to new space.  If the
+  // store buffer overflows again we can exempt the page from the store buffer
+  // by rewinding to this point instead of having to search the store buffer.
+  Object*** start_of_current_page_;
+  // The current page we are scanning in the store buffer iterator.
+  MemoryChunk* current_page_;
+};
+
 
 
 // The all static Heap captures the interface to the global object heap.
 // All JavaScript contexts by this process share the same object heap.
 
 #ifdef DEBUG
 class HeapDebugUtils;
 #endif
 
 
 // A queue of objects promoted during scavenge. Each object is accompanied
 // by it's size to avoid dereferencing a map pointer for scanning.
 class PromotionQueue {
  public:
   PromotionQueue() : front_(NULL), rear_(NULL) { }
 
   void Initialize(Address start_address) {
+    // 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);
+    ASSERT(NewSpacePage::IsAtEnd(start_address));
     front_ = rear_ = reinterpret_cast<intptr_t*>(start_address);
   }
 
-  bool is_empty() { return front_ <= rear_; }
+  bool is_empty() { return front_ == rear_; }
 
   inline void insert(HeapObject* target, int size);
 
   void remove(HeapObject** target, int* size) {
+    ASSERT(!is_empty());
+    if (NewSpacePage::IsAtStart(reinterpret_cast<Address>(front_))) {
+      NewSpacePage* front_page =
+          NewSpacePage::FromAddress(reinterpret_cast<Address>(front_));
+      ASSERT(!front_page->prev_page()->is_anchor());
+      front_ =
+          reinterpret_cast<intptr_t*>(front_page->prev_page()->body_limit());
+    }
     *target = reinterpret_cast<HeapObject*>(*(--front_));
     *size = static_cast<int>(*(--front_));
     // Assert no underflow.
-    ASSERT(front_ >= rear_);
+    SemiSpace::AssertValidRange(reinterpret_cast<Address>(rear_),
+                                reinterpret_cast<Address>(front_));
   }
 
  private:
-  // The front of the queue is higher in memory than the rear.
+  // The front of the queue is higher in the memory page chain than the rear.
   intptr_t* front_;
   intptr_t* rear_;
 
   DISALLOW_COPY_AND_ASSIGN(PromotionQueue);
 };
 
 
+typedef void (*ScavengingCallback)(Map* map,
+                                   HeapObject** slot,
+                                   HeapObject* object);
+
+
 // External strings table is a place where all external strings are
 // registered.  We need to keep track of such strings to properly
 // finalize them.
 class ExternalStringTable {
  public:
   // Registers an external string.
   inline void AddString(String* string);
 
   inline void Iterate(ObjectVisitor* v);
 
@@ skipping 25 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(ExternalStringTable);
 };
 
 
 class Heap {
  public:
   // Configure heap size before setup. Return false if the heap has been
   // setup already.
   bool ConfigureHeap(int max_semispace_size,
-                     int max_old_gen_size,
-                     int max_executable_size);
+                     intptr_t max_old_gen_size,
+                     intptr_t max_executable_size);
   bool ConfigureHeapDefault();
 
   // Initializes the global object heap. If create_heap_objects is true,
   // also creates the basic non-mutable objects.
   // Returns whether it succeeded.
   bool Setup(bool create_heap_objects);
 
   // Destroys all memory allocated by the heap.
   void TearDown();
 
@@ skipping 536 matching lines @@
   // Performs garbage collection operation.
   // Returns whether there is a chance that another major GC could
   // collect more garbage.
   bool CollectGarbage(AllocationSpace space, GarbageCollector collector);
 
   // Performs garbage collection operation.
   // Returns whether there is a chance that another major GC could
   // collect more garbage.
   inline bool CollectGarbage(AllocationSpace space);
 
-  // Performs a full garbage collection. Force compaction if the
-  // parameter is true.
-  void CollectAllGarbage(bool force_compaction);
+  static const int kNoGCFlags = 0;
+  static const int kMakeHeapIterableMask = 1;
+
+  // Performs a full garbage collection.  If (flags & kMakeHeapIterableMask) is
+  // non-zero, then the slower precise sweeper is used, which leaves the heap
+  // in a state where we can iterate over the heap visiting all objects.
+  void CollectAllGarbage(int flags);
 
   // Last hope GC, should try to squeeze as much as possible.
   void CollectAllAvailableGarbage();
 
+  // Check whether the heap is currently iterable.
+  bool IsHeapIterable();
+
+  // Ensure that we have swept all spaces in such a way that we can iterate
+  // over all objects.  May cause a GC.
+  void EnsureHeapIsIterable();
+
   // Notify the heap that a context has been disposed.
   int NotifyContextDisposed() { return ++contexts_disposed_; }
 
   // Utility to invoke the scavenger. This is needed in test code to
   // ensure correct callback for weak global handles.
   void PerformScavenge();
 
+  inline void increment_scan_on_scavenge_pages() {
+    scan_on_scavenge_pages_++;
+    if (FLAG_gc_verbose) {
+      PrintF("Scan-on-scavenge pages: %d\n", scan_on_scavenge_pages_);
+    }
+  }
+
+  inline void decrement_scan_on_scavenge_pages() {
+    scan_on_scavenge_pages_--;
+    if (FLAG_gc_verbose) {
+      PrintF("Scan-on-scavenge pages: %d\n", scan_on_scavenge_pages_);
+    }
+  }
+
   PromotionQueue* promotion_queue() { return &promotion_queue_; }
 
 #ifdef DEBUG
   // Utility used with flag gc-greedy.
   void GarbageCollectionGreedyCheck();
 #endif
 
   void AddGCPrologueCallback(
       GCEpilogueCallback callback, GCType gc_type_filter);
   void RemoveGCPrologueCallback(GCEpilogueCallback callback);
 
   void AddGCEpilogueCallback(
       GCEpilogueCallback callback, GCType gc_type_filter);
   void RemoveGCEpilogueCallback(GCEpilogueCallback callback);
 
   void SetGlobalGCPrologueCallback(GCCallback callback) {
     ASSERT((callback == NULL) ^ (global_gc_prologue_callback_ == NULL));
     global_gc_prologue_callback_ = callback;
   }
   void SetGlobalGCEpilogueCallback(GCCallback callback) {
     ASSERT((callback == NULL) ^ (global_gc_epilogue_callback_ == NULL));
     global_gc_epilogue_callback_ = callback;
   }
 
   // Heap root getters.  We have versions with and without type::cast() here.
   // You can't use type::cast during GC because the assert fails.
+  // TODO(1490): Try removing the unchecked accessors, now that GC marking does
+  // not corrupt the stack.
 #define ROOT_ACCESSOR(type, name, camel_name)                                  \
   type* name() {                                                               \
     return type::cast(roots_[k##camel_name##RootIndex]);                       \
   }                                                                            \
   type* raw_unchecked_##name() {                                               \
     return reinterpret_cast<type*>(roots_[k##camel_name##RootIndex]);          \
   }
   ROOT_LIST(ROOT_ACCESSOR)
 #undef ROOT_ACCESSOR
 
@@ skipping 20 matching lines @@
   }
   Object* global_contexts_list() { return global_contexts_list_; }
 
   // Iterates over all roots in the heap.
   void IterateRoots(ObjectVisitor* v, VisitMode mode);
   // Iterates over all strong roots in the heap.
   void IterateStrongRoots(ObjectVisitor* v, VisitMode mode);
   // Iterates over all the other roots in the heap.
   void IterateWeakRoots(ObjectVisitor* v, VisitMode mode);
 
-  enum ExpectedPageWatermarkState {
-    WATERMARK_SHOULD_BE_VALID,
-    WATERMARK_CAN_BE_INVALID
-  };
-
-  // For each dirty region on a page in use from an old space call
-  // visit_dirty_region callback.
-  // If either visit_dirty_region or callback can cause an allocation
-  // in old space and changes in allocation watermark then
-  // can_preallocate_during_iteration should be set to true.
-  // All pages will be marked as having invalid watermark upon
-  // iteration completion.
-  void IterateDirtyRegions(
-      PagedSpace* space,
-      DirtyRegionCallback visit_dirty_region,
-      ObjectSlotCallback callback,
-      ExpectedPageWatermarkState expected_page_watermark_state);
-
-  // Interpret marks as a bitvector of dirty marks for regions of size
-  // Page::kRegionSize aligned by Page::kRegionAlignmentMask and covering
-  // memory interval from start to top. For each dirty region call a
-  // visit_dirty_region callback. Return updated bitvector of dirty marks.
-  uint32_t IterateDirtyRegions(uint32_t marks,
-                               Address start,
-                               Address end,
-                               DirtyRegionCallback visit_dirty_region,
-                               ObjectSlotCallback callback);
-
   // Iterate pointers to from semispace of new space found in memory interval
   // from start to end.
-  // Update dirty marks for page containing start address.
   void IterateAndMarkPointersToFromSpace(Address start,
                                          Address end,
                                          ObjectSlotCallback callback);
 
   // Iterate pointers to new space found in memory interval from start to end.
-  // Return true if pointers to new space was found.
-  static bool IteratePointersInDirtyRegion(Heap* heap,
-                                           Address start,
-                                           Address end,
-                                           ObjectSlotCallback callback);
+  static void IteratePointersToNewSpace(Heap* heap,
+                                        Address start,
+                                        Address end,
+                                        ObjectSlotCallback callback);
 
 
   // Iterate pointers to new space found in memory interval from start to end.
   // This interval is considered to belong to the map space.
-  // Return true if pointers to new space was found.
-  static bool IteratePointersInDirtyMapsRegion(Heap* heap,
-                                               Address start,
-                                               Address end,
-                                               ObjectSlotCallback callback);
+  static void IteratePointersFromMapsToNewSpace(Heap* heap,
+                                                Address start,
+                                                Address end,
+                                                ObjectSlotCallback callback);
 
 
   // Returns whether the object resides in new space.
   inline bool InNewSpace(Object* object);
+  inline bool InNewSpace(Address addr);
+  inline bool InNewSpacePage(Address addr);
   inline bool InFromSpace(Object* object);
   inline bool InToSpace(Object* object);
 
   // Checks whether an address/object in the heap (including auxiliary
   // area and unused area).
   bool Contains(Address addr);
   bool Contains(HeapObject* value);
 
   // Checks whether an address/object in a space.
   // Currently used by tests, serialization and heap verification only.
@@ skipping 18 matching lines @@
 
   // Sets the non_monomorphic_cache_ (only used when expanding the dictionary).
   void public_set_non_monomorphic_cache(NumberDictionary* value) {
     roots_[kNonMonomorphicCacheRootIndex] = value;
   }
 
   void public_set_empty_script(Script* script) {
     roots_[kEmptyScriptRootIndex] = script;
   }
 
+  void public_set_store_buffer_top(Address* top) {
+    roots_[kStoreBufferTopRootIndex] = reinterpret_cast<Smi*>(top);
+  }
+
   // Update the next script id.
   inline void SetLastScriptId(Object* last_script_id);
 
   // Generated code can embed this address to get access to the roots.
   Object** roots_address() { return roots_; }
 
+  Address* store_buffer_top_address() {
+    return reinterpret_cast<Address*>(&roots_[kStoreBufferTopRootIndex]);
+  }
+
   // Get address of global contexts list for serialization support.
   Object** global_contexts_list_address() {
     return &global_contexts_list_;
   }
 
 #ifdef DEBUG
   void Print();
   void PrintHandles();
 
   // Verify the heap is in its normal state before or after a GC.
   void Verify();
 
+  void OldPointerSpaceCheckStoreBuffer();
+  void MapSpaceCheckStoreBuffer();
+  void LargeObjectSpaceCheckStoreBuffer();
+
   // Report heap statistics.
   void ReportHeapStatistics(const char* title);
   void ReportCodeStatistics(const char* title);
 
   // Fill in bogus values in from space
   void ZapFromSpace();
 #endif
 
   // Print short heap statistics.
   void PrintShortHeapStatistics();
@@ skipping 75 matching lines @@
 
   // Adjusts the amount of registered external memory.
   // Returns the adjusted value.
   inline int AdjustAmountOfExternalAllocatedMemory(int change_in_bytes);
 
   // Allocate uninitialized fixed array.
   MUST_USE_RESULT MaybeObject* AllocateRawFixedArray(int length);
   MUST_USE_RESULT MaybeObject* AllocateRawFixedArray(int length,
                                                      PretenureFlag pretenure);
 
-  // True if we have reached the allocation limit in the old generation that
-  // should force the next GC (caused normally) to be a full one.
-  bool OldGenerationPromotionLimitReached() {
-    return (PromotedSpaceSize() + PromotedExternalMemorySize())
-           > old_gen_promotion_limit_;
-  }
-
-  intptr_t OldGenerationSpaceAvailable() {
-    return old_gen_allocation_limit_ -
-           (PromotedSpaceSize() + PromotedExternalMemorySize());
+  inline intptr_t PromotedTotalSize() {
+    return PromotedSpaceSize() + PromotedExternalMemorySize();
   }
 
   // True if we have reached the allocation limit in the old generation that
-  // should artificially cause a GC right now.
-  bool OldGenerationAllocationLimitReached() {
-    return OldGenerationSpaceAvailable() < 0;
+  // should force the next GC (caused normally) to be a full one.
+  inline bool OldGenerationPromotionLimitReached() {
+    return PromotedTotalSize() > old_gen_promotion_limit_;
+  }
+
+  inline intptr_t OldGenerationSpaceAvailable() {
+    return old_gen_allocation_limit_ - PromotedTotalSize();
+  }
+
+  static const intptr_t kMinimumPromotionLimit = 5 * Page::kPageSize;
+  static const intptr_t kMinimumAllocationLimit =
+      8 * (Page::kPageSize > MB ? Page::kPageSize : MB);
+
+  // When we sweep lazily we initially guess that there is no garbage on the
+  // heap and set the limits for the next GC accordingly.  As we sweep we find
+  // out that some of the pages contained garbage and we have to adjust
+  // downwards the size of the heap.  This means the limits that control the
+  // timing of the next GC also need to be adjusted downwards.
+  void LowerOldGenLimits(intptr_t adjustment) {
+    size_of_old_gen_at_last_old_space_gc_ -= adjustment;
+    old_gen_promotion_limit_ =
+        OldGenPromotionLimit(size_of_old_gen_at_last_old_space_gc_);
+    old_gen_allocation_limit_ =
+        OldGenAllocationLimit(size_of_old_gen_at_last_old_space_gc_);
+  }
+
+  intptr_t OldGenPromotionLimit(intptr_t old_gen_size) {
+    intptr_t limit =
+        Max(old_gen_size + old_gen_size / 3, kMinimumPromotionLimit);
+    limit += new_space_.Capacity();
+    limit *= old_gen_limit_factor_;
+    return limit;
+  }
+
+  intptr_t OldGenAllocationLimit(intptr_t old_gen_size) {
+    intptr_t limit =
+        Max(old_gen_size + old_gen_size / 2, kMinimumAllocationLimit);
+    limit += new_space_.Capacity();
+    limit *= old_gen_limit_factor_;
+    return limit;
   }
 
   // Can be called when the embedding application is idle.
   bool IdleNotification();
 
   // Declare all the root indices.
   enum RootListIndex {
 #define ROOT_INDEX_DECLARATION(type, name, camel_name) k##camel_name##RootIndex,
     STRONG_ROOT_LIST(ROOT_INDEX_DECLARATION)
 #undef ROOT_INDEX_DECLARATION
@@ skipping 18 matching lines @@
   Map* MapForExternalArrayType(ExternalArrayType array_type);
   RootListIndex RootIndexForExternalArrayType(
       ExternalArrayType array_type);
 
   void RecordStats(HeapStats* stats, bool take_snapshot = false);
 
   // Copy block of memory from src to dst. Size of block should be aligned
   // by pointer size.
   static inline void CopyBlock(Address dst, Address src, int byte_size);
 
-  inline void CopyBlockToOldSpaceAndUpdateRegionMarks(Address dst,
-                                                      Address src,
-                                                      int byte_size);
-
   // Optimized version of memmove for blocks with pointer size aligned sizes and
   // pointer size aligned addresses.
   static inline void MoveBlock(Address dst, Address src, int byte_size);
 
-  inline void MoveBlockToOldSpaceAndUpdateRegionMarks(Address dst,
-                                                      Address src,
-                                                      int byte_size);
-
   // Check new space expansion criteria and expand semispaces if it was hit.
   void CheckNewSpaceExpansionCriteria();
 
   inline void IncrementYoungSurvivorsCounter(int survived) {
     young_survivors_after_last_gc_ = survived;
     survived_since_last_expansion_ += survived;
   }
 
+  inline bool NextGCIsLikelyToBeFull() {
+    if (FLAG_gc_global) return true;
+
+    intptr_t total_promoted = PromotedTotalSize();
+
+    intptr_t adjusted_promotion_limit =
+        old_gen_promotion_limit_ - new_space_.Capacity();
+
+    if (total_promoted >= adjusted_promotion_limit) return true;
+
+    intptr_t adjusted_allocation_limit =
+        old_gen_allocation_limit_ - new_space_.Capacity() / 5;
+
+    if (PromotedSpaceSize() >= adjusted_allocation_limit) return true;
+
+    return false;
+  }
+
+
   void UpdateNewSpaceReferencesInExternalStringTable(
       ExternalStringTableUpdaterCallback updater_func);
 
+  void UpdateReferencesInExternalStringTable(
+      ExternalStringTableUpdaterCallback updater_func);
+
   void ProcessWeakReferences(WeakObjectRetainer* retainer);
 
   // Helper function that governs the promotion policy from new space to
   // old.  If the object's old address lies below the new space's age
   // mark or if we've already filled the bottom 1/16th of the to space,
   // we try to promote this object.
   inline bool ShouldBePromoted(Address old_address, int object_size);
 
   int MaxObjectSizeInNewSpace() { return kMaxObjectSizeInNewSpace; }
 
   void ClearJSFunctionResultCaches();
 
   void ClearNormalizedMapCaches();
 
   GCTracer* tracer() { return tracer_; }
 
+  // Returns the size of objects residing in non new spaces.
+  intptr_t PromotedSpaceSize();
+
   double total_regexp_code_generated() { return total_regexp_code_generated_; }
   void IncreaseTotalRegexpCodeGenerated(int size) {
     total_regexp_code_generated_ += size;
   }
 
   // Returns maximum GC pause.
   int get_max_gc_pause() { return max_gc_pause_; }
 
   // Returns maximum size of objects alive after GC.
   intptr_t get_max_alive_after_gc() { return max_alive_after_gc_; }
 
   // Returns minimal interval between two subsequent collections.
   int get_min_in_mutator() { return min_in_mutator_; }
 
   MarkCompactCollector* mark_compact_collector() {
     return &mark_compact_collector_;
   }
 
+  StoreBuffer* store_buffer() {
+    return &store_buffer_;
+  }
+
+  Marking* marking() {
+    return &marking_;
+  }
+
+  IncrementalMarking* incremental_marking() {
+    return &incremental_marking_;
+  }
+
   ExternalStringTable* external_string_table() {
     return &external_string_table_;
   }
 
   // Returns the current sweep generation.
   int sweep_generation() {
     return sweep_generation_;
   }
 
   inline Isolate* isolate();
-  bool is_safe_to_read_maps() { return is_safe_to_read_maps_; }
 
-  void CallGlobalGCPrologueCallback() {
+  inline void CallGlobalGCPrologueCallback() {
     if (global_gc_prologue_callback_ != NULL) global_gc_prologue_callback_();
   }
 
-  void CallGlobalGCEpilogueCallback() {
+  inline void CallGlobalGCEpilogueCallback() {
     if (global_gc_epilogue_callback_ != NULL) global_gc_epilogue_callback_();
   }
 
+  inline bool OldGenerationAllocationLimitReached();
+
+  inline void DoScavengeObject(Map* map, HeapObject** slot, HeapObject* obj) {
+    scavenging_visitors_table_.GetVisitor(map)(map, slot, obj);
+  }
+
+  bool ShouldWeGiveBackAPageToTheOS() {
+    last_empty_page_was_given_back_to_the_os_ =
+        !last_empty_page_was_given_back_to_the_os_;
+    return last_empty_page_was_given_back_to_the_os_;
+  }
+
+  void QueueMemoryChunkForFree(MemoryChunk* chunk);
+  void FreeQueuedChunks();
+
+  // Completely clear the Instanceof cache (to stop it keeping objects alive
+  // around a GC).
+  inline void CompletelyClearInstanceofCache();
+
  private:
   Heap();
 
   // This can be calculated directly from a pointer to the heap; however, it is
   // more expedient to get at the isolate directly from within Heap methods.
   Isolate* isolate_;
 
+  intptr_t code_range_size_;
   int reserved_semispace_size_;
   int max_semispace_size_;
   int initial_semispace_size_;
   intptr_t max_old_generation_size_;
   intptr_t max_executable_size_;
-  intptr_t code_range_size_;
 
   // For keeping track of how much data has survived
   // scavenge since last new space expansion.
   int survived_since_last_expansion_;
 
   // For keeping track on when to flush RegExp code.
   int sweep_generation_;
 
   int always_allocate_scope_depth_;
   int linear_allocation_scope_depth_;
 
   // For keeping track of context disposals.
   int contexts_disposed_;
 
+  int scan_on_scavenge_pages_;
+
 #if defined(V8_TARGET_ARCH_X64)
   static const int kMaxObjectSizeInNewSpace = 1024*KB;
 #else
   static const int kMaxObjectSizeInNewSpace = 512*KB;
 #endif
 
   NewSpace new_space_;
   OldSpace* old_pointer_space_;
   OldSpace* old_data_space_;
   OldSpace* code_space_;
   MapSpace* map_space_;
   CellSpace* cell_space_;
   LargeObjectSpace* lo_space_;
   HeapState gc_state_;
   int gc_post_processing_depth_;
 
-  // Returns the size of object residing in non new spaces.
-  intptr_t PromotedSpaceSize();
-
   // Returns the amount of external memory registered since last global gc.
   int PromotedExternalMemorySize();
 
-  int mc_count_;  // how many mark-compact collections happened
   int ms_count_;  // how many mark-sweep collections happened
   unsigned int gc_count_;  // how many gc happened
 
   // Total length of the strings we failed to flatten since the last GC.
   int unflattened_strings_length_;
 
 #define ROOT_ACCESSOR(type, name, camel_name)                                  \
   inline void set_##name(type* value) {                                 \
     roots_[k##camel_name##RootIndex] = value;                                  \
   }
@@ skipping 18 matching lines @@
   // Limit that triggers a global GC on the next (normally caused) GC.  This
   // is checked when we have already decided to do a GC to help determine
   // which collector to invoke.
   intptr_t old_gen_promotion_limit_;
 
   // Limit that triggers a global GC as soon as is reasonable.  This is
   // checked before expanding a paged space in the old generation and on
   // every allocation in large object space.
   intptr_t old_gen_allocation_limit_;
 
+  // Sometimes the heuristics dictate that those limits are increased.  This
+  // variable records that fact.
+  int old_gen_limit_factor_;
+
+  // Used to adjust the limits that control the timing of the next GC.
+  intptr_t size_of_old_gen_at_last_old_space_gc_;
+
   // Limit on the amount of externally allocated memory allowed
   // between global GCs. If reached a global GC is forced.
   intptr_t external_allocation_limit_;
 
   // The amount of external memory registered through the API kept alive
   // by global handles
   int amount_of_external_allocated_memory_;
 
   // Caches the amount of external memory registered at the last global gc.
   int amount_of_external_allocated_memory_at_last_global_gc_;
 
   // Indicates that an allocation has failed in the old generation since the
   // last GC.
   int old_gen_exhausted_;
 
   Object* roots_[kRootListLength];
 
   Object* global_contexts_list_;
 
+  StoreBufferRebuilder store_buffer_rebuilder_;
+
   struct StringTypeTable {
     InstanceType type;
     int size;
     RootListIndex index;
   };
 
   struct ConstantSymbolTable {
     const char* contents;
     RootListIndex index;
   };
@@ skipping 37 matching lines @@
     GCType gc_type;
   };
   List<GCEpilogueCallbackPair> gc_epilogue_callbacks_;
 
   GCCallback global_gc_prologue_callback_;
   GCCallback global_gc_epilogue_callback_;
 
   // Support for computing object sizes during GC.
   HeapObjectCallback gc_safe_size_of_old_object_;
   static int GcSafeSizeOfOldObject(HeapObject* object);
-  static int GcSafeSizeOfOldObjectWithEncodedMap(HeapObject* object);
 
   // Update the GC state. Called from the mark-compact collector.
   void MarkMapPointersAsEncoded(bool encoded) {
-    gc_safe_size_of_old_object_ = encoded
-        ? &GcSafeSizeOfOldObjectWithEncodedMap
-        : &GcSafeSizeOfOldObject;
+    ASSERT(!encoded);
+    gc_safe_size_of_old_object_ = &GcSafeSizeOfOldObject;
   }
 
   // Checks whether a global GC is necessary
   GarbageCollector SelectGarbageCollector(AllocationSpace space);
 
   // Performs garbage collection
   // Returns whether there is a chance another major GC could
   // collect more garbage.
   bool PerformGarbageCollection(GarbageCollector collector,
                                 GCTracer* tracer);
 
-  static const intptr_t kMinimumPromotionLimit = 2 * MB;
-  static const intptr_t kMinimumAllocationLimit = 8 * MB;
 
   inline void UpdateOldSpaceLimits();
 
+
   // Allocate an uninitialized object in map space.  The behavior is identical
   // to Heap::AllocateRaw(size_in_bytes, MAP_SPACE), except that (a) it doesn't
   // have to test the allocation space argument and (b) can reduce code size
   // (since both AllocateRaw and AllocateRawMap are inlined).
   MUST_USE_RESULT inline MaybeObject* AllocateRawMap();
 
   // Allocate an uninitialized object in the global property cell space.
   MUST_USE_RESULT inline MaybeObject* AllocateRawCell();
 
   // Initializes a JSObject based on its map.
@@ skipping 14 matching lines @@
   MaybeObject* CreateOddball(const char* to_string,
                              Object* to_number,
                              byte kind);
 
   // Allocate empty fixed array.
   MUST_USE_RESULT MaybeObject* AllocateEmptyFixedArray();
 
   // Allocate empty fixed double array.
   MUST_USE_RESULT MaybeObject* AllocateEmptyFixedDoubleArray();
 
-  void SwitchScavengingVisitorsTableIfProfilingWasEnabled();
-
   // Performs a minor collection in new generation.
   void Scavenge();
 
   static String* UpdateNewSpaceReferenceInExternalStringTableEntry(
       Heap* heap,
       Object** pointer);
 
   Address DoScavenge(ObjectVisitor* scavenge_visitor, Address new_space_front);
+  static void ScavengeStoreBufferCallback(Heap* heap,
+                                          MemoryChunk* page,
+                                          StoreBufferEvent event);
 
   // Performs a major collection in the whole heap.
   void MarkCompact(GCTracer* tracer);
 
   // Code to be run before and after mark-compact.
-  void MarkCompactPrologue(bool is_compacting);
-
-  // Completely clear the Instanceof cache (to stop it keeping objects alive
-  // around a GC).
-  inline void CompletelyClearInstanceofCache();
+  void MarkCompactPrologue();
 
   // Record statistics before and after garbage collection.
   void ReportStatisticsBeforeGC();
   void ReportStatisticsAfterGC();
 
   // Slow part of scavenge object.
   static void ScavengeObjectSlow(HeapObject** p, HeapObject* object);
 
   // Initializes a function with a shared part and prototype.
   // Returns the function.
@@ skipping 59 matching lines @@
   }
 
   bool IsIncreasingSurvivalTrend() {
     return survival_rate_trend() == INCREASING;
   }
 
   bool IsHighSurvivalRate() {
     return high_survival_rate_period_length_ > 0;
   }
 
+  void SelectScavengingVisitorsTable();
+
   static const int kInitialSymbolTableSize = 2048;
   static const int kInitialEvalCacheSize = 64;
 
   // Maximum GC pause.
   int max_gc_pause_;
 
   // Maximum size of objects alive after GC.
   intptr_t max_alive_after_gc_;
 
   // Minimal interval between two subsequent collections.
   int min_in_mutator_;
 
   // Size of objects alive after last GC.
   intptr_t alive_after_last_gc_;
 
   double last_gc_end_timestamp_;
 
   MarkCompactCollector mark_compact_collector_;
 
-  // This field contains the meaning of the WATERMARK_INVALIDATED flag.
-  // Instead of clearing this flag from all pages we just flip
-  // its meaning at the beginning of a scavenge.
-  intptr_t page_watermark_invalidated_mark_;
+  StoreBuffer store_buffer_;
+
+  Marking marking_;
+
+  IncrementalMarking incremental_marking_;
 
   int number_idle_notifications_;
   unsigned int last_idle_notification_gc_count_;
   bool last_idle_notification_gc_count_init_;
 
   // Shared state read by the scavenge collector and set by ScavengeObject.
   PromotionQueue promotion_queue_;
 
   // Flag is set when the heap has been configured.  The heap can be repeatedly
   // configured through the API until it is setup.
   bool configured_;
 
   ExternalStringTable external_string_table_;
 
-  bool is_safe_to_read_maps_;
+  VisitorDispatchTable<ScavengingCallback> scavenging_visitors_table_;
+
+  bool last_empty_page_was_given_back_to_the_os_;
+  MemoryChunk* chunks_queued_for_free_;
 
   friend class Factory;
   friend class GCTracer;
   friend class DisallowAllocationFailure;
   friend class AlwaysAllocateScope;
   friend class LinearAllocationScope;
   friend class Page;
   friend class Isolate;
   friend class MarkCompactCollector;
   friend class StaticMarkingVisitor;
@@ skipping 78 matching lines @@
   void VisitPointers(Object** start, Object** end) {
     for (Object** current = start; current < end; current++) {
       if ((*current)->IsHeapObject()) {
         HeapObject* object = HeapObject::cast(*current);
         ASSERT(HEAP->Contains(object));
         ASSERT(object->map()->IsMap());
       }
     }
   }
 };
-
-
-// Visitor class to verify interior pointers in spaces that use region marks
-// to keep track of intergenerational references.
-// As VerifyPointersVisitor but also checks that dirty marks are set
-// for regions covering intergenerational references.
-class VerifyPointersAndDirtyRegionsVisitor: public ObjectVisitor {
- public:
-  void VisitPointers(Object** start, Object** end) {
-    for (Object** current = start; current < end; current++) {
-      if ((*current)->IsHeapObject()) {
-        HeapObject* object = HeapObject::cast(*current);
-        ASSERT(HEAP->Contains(object));
-        ASSERT(object->map()->IsMap());
-        if (HEAP->InNewSpace(object)) {
-          ASSERT(HEAP->InToSpace(object));
-          Address addr = reinterpret_cast<Address>(current);
-          ASSERT(Page::FromAddress(addr)->IsRegionDirty(addr));
-        }
-      }
-    }
-  }
-};
 #endif
 
 
 // Space iterator for iterating over all spaces of the heap.
 // Returns each space in turn, and null when it is done.
 class AllSpaces BASE_EMBEDDED {
  public:
   Space* next();
   AllSpaces() { counter_ = FIRST_SPACE; }
  private:
@@ skipping 312 matching lines @@
 
   // Sets the collector.
   void set_collector(GarbageCollector collector) { collector_ = collector; }
 
   // Sets the GC count.
   void set_gc_count(unsigned int count) { gc_count_ = count; }
 
   // Sets the full GC count.
   void set_full_gc_count(int count) { full_gc_count_ = count; }
 
-  // Sets the flag that this is a compacting full GC.
-  void set_is_compacting() { is_compacting_ = true; }
-  bool is_compacting() const { return is_compacting_; }
-
-  // Increment and decrement the count of marked objects.
-  void increment_marked_count() { ++marked_count_; }
-  void decrement_marked_count() { --marked_count_; }
-
-  int marked_count() { return marked_count_; }
-
   void increment_promoted_objects_size(int object_size) {
     promoted_objects_size_ += object_size;
   }
 
  private:
   // Returns a string matching the collector.
   const char* CollectorString();
 
   // Returns size of object in heap (in MB).
   double SizeOfHeapObjects() {
     return (static_cast<double>(HEAP->SizeOfObjects())) / MB;
   }
 
   double start_time_;  // Timestamp set in the constructor.
   intptr_t start_size_;  // Size of objects in heap set in constructor.
   GarbageCollector collector_;  // Type of collector.
 
   // A count (including this one, eg, the first collection is 1) of the
   // number of garbage collections.
   unsigned int gc_count_;
 
   // A count (including this one) of the number of full garbage collections.
   int full_gc_count_;
 
-  // True if the current GC is a compacting full collection, false
-  // otherwise.
-  bool is_compacting_;
-
-  // True if the *previous* full GC cwas a compacting collection (will be
-  // false if there has not been a previous full GC).
-  bool previous_has_compacted_;
-
-  // On a full GC, a count of the number of marked objects.  Incremented
-  // when an object is marked and decremented when an object's mark bit is
-  // cleared.  Will be zero on a scavenge collection.
-  int marked_count_;
-
-  // The count from the end of the previous full GC.  Will be zero if there
-  // was no previous full GC.
-  int previous_marked_count_;
-
   // Amounts of time spent in different scopes during GC.
   double scopes_[Scope::kNumberOfScopes];
 
   // Total amount of space either wasted or contained in one of free lists
   // before the current GC.
   intptr_t in_free_list_or_wasted_before_gc_;
 
   // Difference between space used in the heap at the beginning of the current
   // collection and the end of the previous collection.
   intptr_t allocated_since_last_gc_;
 
   // Amount of time spent in mutator that is time elapsed between end of the
   // previous collection and the beginning of the current one.
   double spent_in_mutator_;
 
   // Size of objects promoted during the current collection.
   intptr_t promoted_objects_size_;
 
+  // Incremental marking steps counters.
+  int steps_count_;
+  double steps_took_;
+  double longest_step_;
+  int steps_count_since_last_gc_;
+  double steps_took_since_last_gc_;
+
   Heap* heap_;
 };
 
 
 class StringSplitCache {
  public:
   static Object* Lookup(FixedArray* cache, String* string, String* pattern);
   static void Enter(Heap* heap,
                     FixedArray* cache,
                     String* string,
@@ skipping 91 matching lines @@
  public:
   virtual ~WeakObjectRetainer() {}
 
   // Return whether this object should be retained. If NULL is returned the
   // object has no references. Otherwise the address of the retained object
   // should be returned as in some GC situations the object has been moved.
   virtual Object* RetainAs(Object* object) = 0;
 };
 
 
+// Intrusive object marking uses least significant bit of
+// heap object's map word to mark objects.
+// Normally all map words have least significant bit set
+// because they contain tagged map pointer.
+// If the bit is not set object is marked.
+// All objects should be unmarked before resuming
+// JavaScript execution.
+class IntrusiveMarking {
+ public:
+  static bool IsMarked(HeapObject* object) {
+    return (object->map_word().ToRawValue() & kNotMarkedBit) == 0;
+  }
+
+  static void ClearMark(HeapObject* object) {
+    uintptr_t map_word = object->map_word().ToRawValue();
+    object->set_map_word(MapWord::FromRawValue(map_word | kNotMarkedBit));
+    ASSERT(!IsMarked(object));
+  }
+
+  static void SetMark(HeapObject* object) {
+    uintptr_t map_word = object->map_word().ToRawValue();
+    object->set_map_word(MapWord::FromRawValue(map_word & ~kNotMarkedBit));
+    ASSERT(IsMarked(object));
+  }
+
+  static Map* MapOfMarkedObject(HeapObject* object) {
+    uintptr_t map_word = object->map_word().ToRawValue();
+    return MapWord::FromRawValue(map_word | kNotMarkedBit).ToMap();
+  }
+
+  static int SizeOfMarkedObject(HeapObject* object) {
+    return object->SizeFromMap(MapOfMarkedObject(object));
+  }
+
+ private:
+  static const uintptr_t kNotMarkedBit = 0x1;
+  STATIC_ASSERT((kHeapObjectTag & kNotMarkedBit) != 0);
+};
+
+
 #if defined(DEBUG) || defined(LIVE_OBJECT_LIST)
 // Helper class for tracing paths to a search target Object from all roots.
 // The TracePathFrom() method can be used to trace paths from a specific
 // object to the search target object.
 class PathTracer : public ObjectVisitor {
  public:
   enum WhatToFind {
     FIND_ALL,   // Will find all matches.
     FIND_FIRST  // Will stop the search after first match.
   };
@@ skipping 38 matching lines @@
   WhatToFind what_to_find_;
   VisitMode visit_mode_;
   List<Object*> object_stack_;
 
   AssertNoAllocation no_alloc;  // i.e. no gc allowed.
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(PathTracer);
 };
 #endif  // DEBUG || LIVE_OBJECT_LIST
 
-
 } }  // namespace v8::internal
 
 #undef HEAP
 
 #endif  // V8_HEAP_H_