Parallelize marking phase of mark-sweep/compact collection cycle.

src/heap.h

 // Copyright 2010 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 195 matching lines @@
 class GCTracer;
 class HeapStats;
 
 
 typedef String* (*ExternalStringTableUpdaterCallback)(Object** pointer);
 
 typedef bool (*DirtyRegionCallback)(Address start,
                                     Address end,
                                     ObjectSlotCallback copy_object_func);
 
+enum RootsPartition {
+  kStrongRootsList,
+  kBootstrapperRoots,
+  kTopRoots,
+  kRelocatableRoots,
+#ifdef ENABLE_DEBUGGER_SUPPORT
+  kDebugRoots,
+#endif
+  kCompilationCacheRoots,
+  kHandleScopeRoots,
+  kBuiltinsRoots,
+  kGlobalHandlesRoots,
+  kThreadManagerRoots,
+  kSerializerDeserializerRoots,
+  kNumberOfRootsPartitions
+};
+
+class RootsPartitioner : public AllStatic {
+ public:
+  static bool Claim(RootsPartition partition) {
+    return (partitions_state_[partition] == UNCLAIMED) &&
+        AtomicCompareAndSwap(&partitions_state_[partition], UNCLAIMED, CLAIMED);
+  }
+
+  static void Reset() {
+    for (int i = 0; i < kNumberOfRootsPartitions; i++) {
+      partitions_state_[i] = UNCLAIMED;
+    }
+  }
+
+ private:
+  static const Atomic32 CLAIMED = 0;
+  static const Atomic32 UNCLAIMED = 1;
+
+  static Atomic32 partitions_state_[kNumberOfRootsPartitions];
+};
+
 
 // The all static Heap captures the interface to the global object heap.
 // All JavaScript contexts by this process share the same object heap.
 
 class Heap : public AllStatic {
  public:
   // Configure heap size before setup. Return false if the heap has been
   // setup already.
   static bool ConfigureHeap(int max_semispace_size, int max_old_gen_size);
   static bool ConfigureHeapDefault();
@@ skipping 538 matching lines @@
 #undef SYMBOL_ACCESSOR
 
   // The hidden_symbol is special because it is the empty string, but does
   // not match the empty string.
   static String* hidden_symbol() { return hidden_symbol_; }
 
   // Iterates over all roots in the heap.
   static void IterateRoots(ObjectVisitor* v, VisitMode mode);
   // Iterates over all strong roots in the heap.
   static void IterateStrongRoots(ObjectVisitor* v, VisitMode mode);
+
+  static void ClaimAndIterateStrongRootsGroup(ObjectVisitor* v,
+                                              VisitMode mode,
+                                              RootsPartition partition);
+
   // Iterates over all the other roots in the heap.
   static 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.
@@ skipping 868 matching lines @@
   struct Key {
     DescriptorArray* array;
     String* name;
   };
 
   static Key keys_[kLength];
   static int results_[kLength];
 };
 
 
-// ----------------------------------------------------------------------------
-// Marking stack for tracing live objects.
-
-class MarkingStack {
- public:
-  void Initialize(Address low, Address high) {
-    top_ = low_ = reinterpret_cast<HeapObject**>(low);
-    high_ = reinterpret_cast<HeapObject**>(high);
-    overflowed_ = false;
-  }
-
-  bool is_full() { return top_ >= high_; }
-
-  bool is_empty() { return top_ <= low_; }
-
-  bool overflowed() { return overflowed_; }
-
-  void clear_overflowed() { overflowed_ = false; }
-
-  // Push the (marked) object on the marking stack if there is room,
-  // otherwise mark the object as overflowed and wait for a rescan of the
-  // heap.
-  void Push(HeapObject* object) {
-    CHECK(object->IsHeapObject());
-    if (is_full()) {
-      object->SetOverflow();
-      overflowed_ = true;
-    } else {
-      *(top_++) = object;
-    }
-  }
-
-  HeapObject* Pop() {
-    ASSERT(!is_empty());
-    HeapObject* object = *(--top_);
-    CHECK(object->IsHeapObject());
-    return object;
-  }
-
- private:
-  HeapObject** low_;
-  HeapObject** top_;
-  HeapObject** high_;
-  bool overflowed_;
-};
-
-
 // A helper class to document/test C++ scopes where we do not
 // expect a GC. Usage:
 //
 // /* Allocation not allowed: we cannot handle a GC in this scope. */
 // { AssertNoAllocation nogc;
 //   ...
 // }
 
 #ifdef DEBUG
 
@@ skipping 97 matching lines @@
   // Sets the GC count.
   void set_gc_count(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_; }
 
+#ifdef DEBUG
   // Increment and decrement the count of marked objects.
-  void increment_marked_count() { ++marked_count_; }
+  void increment_marked_count() { AtomicAdd(&marked_count_, 1); }
   void decrement_marked_count() { --marked_count_; }
 
   int marked_count() { return marked_count_; }
+#endif
 
   void increment_promoted_objects_size(int object_size) {
     promoted_objects_size_ += object_size;
   }
 
   // Returns maximum GC pause.
   static int get_max_gc_pause() { return max_gc_pause_; }
 
   // Returns maximum size of objects alive after GC.
   static intptr_t get_max_alive_after_gc() { return max_alive_after_gc_; }
@@ skipping 22 matching lines @@
   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_;
 
+#ifdef DEBUG
   // 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_;
+#endif
 
   // 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.
@@ skipping 148 matching lines @@
 
   // To speed up scavenge collections new space string are kept
   // separate from old space strings.
   static List<Object*> new_space_strings_;
   static List<Object*> old_space_strings_;
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_HEAP_H_