New GC related APIs: Implicit references.

src/mark-compact.cc

 // 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
@@ skipping 1913 matching lines @@
 
   // There may be overflowed objects in the heap.  Visit them now.
   while (marking_deque_.overflowed()) {
     RefillMarkingDeque();
     EmptyMarkingDeque();
   }
 }
 
 
 void MarkCompactCollector::MarkImplicitRefGroups() {
-  List<ImplicitRefGroup*>* ref_groups =
-      isolate()->global_handles()->implicit_ref_groups();
+  Isolate* isolate = Isolate::Current();
+  List<ObjectGroupConnection>* ref_groups =
+      isolate->global_handles()->implicit_ref_groups();
+  List<ObjectGroupRepresentativeObject>* representative_objects =
+      isolate->global_handles()->representative_objects();
 
-  int last = 0;
-  for (int i = 0; i < ref_groups->length(); i++) {
-    ImplicitRefGroup* entry = ref_groups->at(i);
-    ASSERT(entry != NULL);
+  if (ref_groups->length() == 0)
+    return;
 
-    if (!IsMarked(*entry->parent_)) {
-      (*ref_groups)[last++] = entry;
-      continue;
-    }
+  ref_groups->Sort();
+  representative_objects->Sort();
 
-    Object*** children = entry->children_;
-    // A parent object is marked, so mark all child heap objects.
-    for (size_t j = 0; j < entry->length_; ++j) {
-      if ((*children[j])->IsHeapObject()) {
-        HeapObject* child = HeapObject::cast(*children[j]);
-        MarkBit mark = Marking::MarkBitFrom(child);
-        MarkObject(child, mark);
+  int surviving_ref_group_index = 0;
+  int surviving_representative_object_index = 0;
+
+  int representative_objects_index = 0;
+  UniqueId current_group_id(0);
+  size_t current_group_start = 0;
+  for (int i = 0; i <= ref_groups->length(); ++i) {
+    if (i == 0)
+      current_group_id = ref_groups->at(i).id;
+    if (i == ref_groups->length() || current_group_id != ref_groups->at(i).id) {
+      // Group detected: objects in indices [current_group_start, i[.
+
+      // Find the representative object for this group.
+      while (representative_objects_index < representative_objects->length() &&
+             representative_objects->at(representative_objects_index).id <
+             current_group_id)
+        ++representative_objects_index;
+
+      if (representative_objects_index < representative_objects->length() &&
+          representative_objects->at(representative_objects_index).id ==
+              current_group_id) {
+        HeapObject* parent =
+            *(representative_objects->at(representative_objects_index).object);
+
+        if (!IsMarked(parent)) {
+          // Nothing tbd, copy the reference group so that it can be iterated
+          // during the next call.
+          for (int j = current_group_start; j < i; ++j)
+            ref_groups->at(surviving_ref_group_index++) = ref_groups->at(j);
+          representative_objects->at(surviving_representative_object_index++) =
+              representative_objects->at(representative_objects_index);
+        } else {
+          // A parent object is marked, so mark all child heap objects.
+          for (int j = current_group_start; j < i; ++j) {
+            if ((*ref_groups->at(j).object)->IsHeapObject()) {
+              HeapObject* child = HeapObject::cast(*ref_groups->at(j).object);
+              MarkBit mark = Marking::MarkBitFrom(child);
+              MarkObject(child, mark);
+            }
+          }
+        }
+      } else {
+        // This should not happen: representative object for a group was not

[Michael Starzinger, 2013/04/16 10:42:16]

Add an "UNREACHABLE();" here.

[marja, 2013/04/16 12:28:37]

Done.

+        // set!
+      }
+      if (i < ref_groups->length()) {
+        current_group_id = ref_groups->at(i).id;
+        current_group_start = i;
       }
     }
-
-    // Once the entire group has been marked, dispose it because it's
-    // not needed anymore.
-    entry->Dispose();
   }
-  ref_groups->Rewind(last);
+  ref_groups->Rewind(surviving_ref_group_index);
+  representative_objects->Rewind(surviving_representative_object_index);
 }
 
 
 // Mark all objects reachable from the objects on the marking stack.
 // Before: the marking stack contains zero or more heap object pointers.
 // After: the marking stack is empty, and all objects reachable from the
 // marking stack have been marked, or are overflowed in the heap.
 void MarkCompactCollector::EmptyMarkingDeque() {
   while (!marking_deque_.IsEmpty()) {
     while (!marking_deque_.IsEmpty()) {
@@ skipping 2161 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal