Introduce conservative sweeping.

src/mark-compact.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 92 matching lines @@
 
   SweepLargeObjectSpace();
 
   SweepSpaces();
   PcToCodeCache::FlushPcToCodeCache();
 
   Finish();
 
   // Check that swept all marked objects and
   // null out the GC tracer.
-  ASSERT(tracer_->marked_count() == 0);
+  // TODO(gc) does not work with conservative sweeping.
+  // ASSERT(tracer_->marked_count() == 0);
   tracer_ = NULL;
 }
 
 
 #ifdef DEBUG
 static void VerifyMarkbitsAreClean(PagedSpace* space) {
   PageIterator it(space, PageIterator::PAGES_IN_USE);
 
   while (it.has_next()) {
     Page* p = it.next();
     ASSERT(p->markbits()->IsClean());
   }
 }
 
 static void VerifyMarkbitsAreClean() {
   VerifyMarkbitsAreClean(Heap::old_pointer_space());
   VerifyMarkbitsAreClean(Heap::old_data_space());
   VerifyMarkbitsAreClean(Heap::code_space());
   VerifyMarkbitsAreClean(Heap::cell_space());
   VerifyMarkbitsAreClean(Heap::map_space());
 }
 #endif
 
 
+static void ClearMarkbits(PagedSpace* space) {
+  PageIterator it(space, PageIterator::PAGES_IN_USE);
+
+  while (it.has_next()) {
+    Page* p = it.next();
+    p->markbits()->Clear();
+  }
+}
+
+static void ClearMarkbits() {
+  // We are sweeping code and map spaces presisely so clearing is not required.

[Erik Corry, 2011/01/19 13:46:48]

presisely -> precisely,

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  ClearMarkbits(Heap::old_pointer_space());
+  ClearMarkbits(Heap::old_data_space());
+  ClearMarkbits(Heap::cell_space());
+}
+
+
 void MarkCompactCollector::Prepare(GCTracer* tracer) {
   FLAG_flush_code = false;
   FLAG_always_compact = false;
   FLAG_never_compact = true;
 
   // Rather than passing the tracer around we stash it in a static member
   // variable.
   tracer_ = tracer;
 
 #ifdef DEBUG
@@ skipping 16 matching lines @@
        space != NULL; space = spaces.next()) {
     space->PrepareForMarkCompact(compacting_collection_);
   }
 
   Address new_space_top = Heap::new_space()->top();
   Address new_space_bottom = Heap::new_space()->bottom();
 
   Marking::ClearRange(new_space_bottom,
                       static_cast<int>(new_space_top - new_space_bottom));
 
+  ClearMarkbits();
+
 #ifdef DEBUG
   VerifyMarkbitsAreClean();
 
   live_bytes_ = 0;
   live_young_objects_size_ = 0;
   live_old_pointer_objects_size_ = 0;
   live_old_data_objects_size_ = 0;
   live_code_objects_size_ = 0;
   live_map_objects_size_ = 0;
   live_cell_objects_size_ = 0;
@@ skipping 1527 matching lines @@
   // Update pointers from external string table.
   Heap::UpdateNewSpaceReferencesInExternalStringTable(
       &UpdateNewSpaceReferenceInExternalStringTableEntry);
 
   // All pointers were updated. Update auxiliary allocation info.
   Heap::IncrementYoungSurvivorsCounter(survivors_size);
   space->set_age_mark(space->top());
 }
 
 
-void MarkCompactCollector::SweepSpace(PagedSpace* space) {
+INLINE(static uint32_t SweepFree(PagedSpace* space,
+                                 Page* p,
+                                 uint32_t free_start,
+                                 uint32_t region_end,
+                                 uint32_t* cells));
+
+
+static uint32_t SweepFree(PagedSpace* space,
+                          Page* p,
+                          uint32_t free_start,
+                          uint32_t region_end,
+                          uint32_t* cells) {
+  uint32_t free_cell = Page::MarkbitsBitmap::Index2Cell(free_start);
+  ASSERT(cells[free_cell] == 0);
+  while (free_cell < region_end && cells[free_cell] == 0) {
+    free_cell++;
+  }
+
+  if (free_cell >= region_end) {
+    return free_cell;
+  }
+
+  uint32_t free_end = Page::MarkbitsBitmap::Cell2Index(free_cell);
+  space->DeallocateBlock(p->Markbit2Address(free_start),
+                         (free_end - free_start) << kPointerSizeLog2,
+                         true);
+
+  return free_cell;
+}
+
+
+INLINE(static uint32_t NextCandidate(uint32_t cell,
+                                     uint32_t last_cell,
+                                     uint32_t* cells));
+
+
+static uint32_t NextCandidate(uint32_t cell,
+                              uint32_t last_cell,
+                              uint32_t* cells) {
+  do {
+    cell++;
+  } while (cell < last_cell && cells[cell] != 0);
+  return cell;
+}
+
+
+INLINE(static int SizeOfPreviousObject(Page* p,
+                                       uint32_t cell,
+                                       uint32_t* cells));
+
+
+static int SizeOfPreviousObject(Page* p,
+                                uint32_t cell,
+                                uint32_t* cells) {
+  ASSERT(cells[cell] == 0);
+  if (cells[cell - 1] == 0) return 0;
+
+  int clz = __builtin_clz(cells[cell - 1]) + 1;

[Erik Corry, 2011/01/19 13:46:48]

Variable should be called leading_zeros

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  Address addr =
+      p->Markbit2Address(Page::MarkbitsBitmap::Cell2Index(cell) - clz);
+  HeapObject* obj = HeapObject::FromAddress(addr);
+  ASSERT(obj->map()->IsMap());
+  return (obj->Size() >> kPointerSizeLog2) - clz;
+}
+
+
+static void SweepConservatively(PagedSpace* space,
+                                Page* p,
+                                Address* last_free_start) {
+  typedef Page::MarkbitsBitmap::CellType CellType;
+  Page::MarkbitsBitmap* markbits = p->markbits();
+  CellType* cells = markbits->cells();
+
+  uint32_t last_cell =
+      Page::MarkbitsBitmap::Index2Cell(
+          Page::MarkbitsBitmap::CellAlignIndex(
+              p->Address2Markbit(p->AllocationTop())));
+
+  uint32_t cell = Page::kFirstUsedCell;

[Erik Corry, 2011/01/19 13:46:48]

See above.

+  uint32_t poluted_cell = Page::kFirstUsedCell;

[Erik Corry, 2011/01/19 13:46:48]

poluted -> polluted

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  if (cells[cell] == 0) {
+    poluted_cell = SweepFree(space,
+                             p,
+                             p->Address2Markbit(p->ObjectAreaStart()),
+                             last_cell,
+                             cells);
+
+    if (poluted_cell >= last_cell) {
+      // All cells are free.
+      *last_free_start = p->ObjectAreaStart();
+      return;
+    }
+  }
+
+  p->ClearFlag(Page::IS_CONTINIOUS);
+
+  ASSERT(cells[poluted_cell] != 0);
+  for (cell = NextCandidate(poluted_cell, last_cell, cells);
+       cell < last_cell;
+       cell = NextCandidate(poluted_cell, last_cell, cells)) {
+    ASSERT(cells[cell] == 0);
+
+    int size = SizeOfPreviousObject(p, cell, cells);
+    if (size <= 0) {
+      poluted_cell = SweepFree(space,
+                               p,
+                               Page::MarkbitsBitmap::Cell2Index(cell),
+                               last_cell,
+                               cells);
+      if (poluted_cell >= last_cell) {
+        // This free region is the last on the page.
+        *last_free_start = p->Markbit2Address(
+            Page::MarkbitsBitmap::Cell2Index(cell));
+        return;
+      }
+    } else {
+      // Skip cells covered by this object.
+      poluted_cell = cell +
+          Page::MarkbitsBitmap::Index2Cell(size - 1);
+    }
+  }
+}
+
+
+static void SweepPrecisely(PagedSpace* space, Page* p, Address* last_free_start) {

[Erik Corry, 2011/01/19 13:46:48]

Lint?

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  bool is_previous_alive = true;
+  Address free_start = NULL;
+  HeapObject* object;
+
+  for (Address current = p->ObjectAreaStart();
+       current < p->AllocationTop();
+       current += object->Size()) {
+    object = HeapObject::FromAddress(current);
+    if (Marking::IsMarked(object)) {
+      Marking::ClearMark(object);
+      MarkCompactCollector::tracer()->decrement_marked_count();
+
+      if (!is_previous_alive) {  // Transition from free to live.
+        space->DeallocateBlock(free_start,
+                               static_cast<int>(current - free_start),
+                               true);
+        is_previous_alive = true;
+      }
+    } else {
+      MarkCompactCollector::ReportDeleteIfNeeded(object);
+      if (is_previous_alive) {  // Transition from live to free.
+        free_start = current;
+        is_previous_alive = false;
+      }
+    }
+  }
+
+  if (!is_previous_alive) *last_free_start = free_start;
+}
+
+
+void MarkCompactCollector::SweepSpace(PagedSpace* space,
+                                      SweeperType sweeper) {
   PageIterator it(space, PageIterator::PAGES_IN_USE);
 
   // During sweeping of paged space we are trying to find longest sequences
   // of pages without live objects and free them (instead of putting them on
   // the free list).
 
   // Page preceding current.
   Page* prev = Page::FromAddress(NULL);
 
   // First empty page in a sequence.
   Page* first_empty_page = Page::FromAddress(NULL);
 
   // Page preceding first empty page.
   Page* prec_first_empty_page = Page::FromAddress(NULL);
 
   // If last used page of space ends with a sequence of dead objects
   // we can adjust allocation top instead of puting this free area into
   // the free list. Thus during sweeping we keep track of such areas
   // and defer their deallocation until the sweeping of the next page
   // is done: if one of the next pages contains live objects we have
   // to put such area into the free list.
   Address last_free_start = NULL;
   int last_free_size = 0;
 
   while (it.has_next()) {
     Page* p = it.next();
 
-    bool is_previous_alive = true;
-    Address free_start = NULL;
-    HeapObject* object;
+    Address free_start = p->AllocationTop();
 
-    for (Address current = p->ObjectAreaStart();
-         current < p->AllocationTop();
-         current += object->Size()) {
-      object = HeapObject::FromAddress(current);
-      if (Marking::IsMarked(object)) {
-        Marking::ClearMark(object);
-        MarkCompactCollector::tracer()->decrement_marked_count();
-
-        if (!is_previous_alive) {  // Transition from free to live.
-          space->DeallocateBlock(free_start,
-                                 static_cast<int>(current - free_start),
-                                 true);
-          is_previous_alive = true;
-        }
-      } else {
-        MarkCompactCollector::ReportDeleteIfNeeded(object);
-        if (is_previous_alive) {  // Transition from live to free.
-          free_start = current;
-          is_previous_alive = false;
-        }
-      }
-      // The object is now unmarked for the call to Size() at the top of the
-      // loop.
+    if (sweeper == CONSERVATIVE) {
+      SweepConservatively(space, p, &free_start);
+      p->set_linearity_boundary(free_start);
+    } else {
+      ASSERT(sweeper == PRECISE);
+      SweepPrecisely(space, p, &free_start);
     }
 
-    bool page_is_empty = (p->ObjectAreaStart() == p->AllocationTop())
-        || (!is_previous_alive && free_start == p->ObjectAreaStart());
+    bool page_is_empty = (p->ObjectAreaStart() == free_start);
+    bool is_previous_alive = (free_start == p->AllocationTop());
+
+    ASSERT(free_start <= p->AllocationTop());
 
     if (page_is_empty) {
       // This page is empty. Check whether we are in the middle of
       // sequence of empty pages and start one if not.
       if (!first_empty_page->is_valid()) {
         first_empty_page = p;
         prec_first_empty_page = prev;
       }
 
       if (!is_previous_alive) {
@@ skipping 33 matching lines @@
     prev = p;
   }
 
   // We reached end of space. See if we need to adjust allocation top.
   Address new_allocation_top = NULL;
 
   if (first_empty_page->is_valid()) {
     // Last used pages in space are empty. We can move allocation top backwards
     // to the beginning of first empty page.
     ASSERT(prev == space->AllocationTopPage());
-
+    space->FreePages(prec_first_empty_page, prev);
     new_allocation_top = first_empty_page->ObjectAreaStart();
   }
 
   if (last_free_size > 0) {
     // There was a free ending area on the previous page.
     // Deallocate it without putting it into freelist and move allocation
     // top to the beginning of this free area.
     space->DeallocateBlock(last_free_start, last_free_size, false);
     new_allocation_top = last_free_start;
   }
@@ skipping 18 matching lines @@
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 
   ASSERT(state_ == SWEEP_SPACES);
   ASSERT(!IsCompacting());
   // Noncompacting collections simply sweep the spaces to clear the mark
   // bits and free the nonlive blocks (for old and map spaces).  We sweep
   // the map space last because freeing non-live maps overwrites them and
   // the other spaces rely on possibly non-live maps to get the sizes for
   // non-live objects.
-  SweepSpace(Heap::old_pointer_space());
-  SweepSpace(Heap::old_data_space());
-  SweepSpace(Heap::code_space());
-  SweepSpace(Heap::cell_space());
+  SweepSpace(Heap::old_pointer_space(), CONSERVATIVE);
+  SweepSpace(Heap::old_data_space(), CONSERVATIVE);
+  SweepSpace(Heap::code_space(), PRECISE);
+  // TODO(gc): implement specialized sweeper for cell space.
+  SweepSpace(Heap::cell_space(), CONSERVATIVE);
   { GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP_NEWSPACE);
     SweepNewSpace(Heap::new_space());
   }
-  SweepSpace(Heap::map_space());
+  // TODO(gc): ClearNonLiveTransitions depends on precise sweeping of
+  // map space to detect whether unmarked map became dead in this
+  // collection on in one of the previous ones.

[Erik Corry, 2011/01/19 13:46:48]

on -> or

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  // Implement specialized sweeper for map space.

[Erik Corry, 2011/01/19 13:46:48]

Missing TODO?

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+  SweepSpace(Heap::map_space(), PRECISE);
 
   Heap::IterateDirtyRegions(Heap::map_space(),
                             &Heap::IteratePointersInDirtyMapsRegion,
                             &UpdatePointerToNewGen,
                             Heap::WATERMARK_SHOULD_BE_VALID);
 
-  ASSERT(live_map_objects_size_ == Heap::map_space()->Size());
+  ASSERT(live_map_objects_size_ <= Heap::map_space()->Size());
 }
 
 
 // Iterate the live objects in a range of addresses (eg, a page or a
 // semispace).  The live regions of the range have been linked into a list.
 // The first live region is [first_live_start, first_live_end), and the last
 // address in the range is top.  The callback function is used to get the
 // size of each live object.
 int MarkCompactCollector::IterateLiveObjectsInRange(
     Address start,
@@ skipping 37 matching lines @@
   }
   return total;
 }
 
 
 void MarkCompactCollector::ReportDeleteIfNeeded(HeapObject* obj) {
 #ifdef ENABLE_LOGGING_AND_PROFILING
   if (obj->IsCode()) {
     PROFILE(CodeDeleteEvent(obj->address()));
   } else if (obj->IsJSFunction()) {
+    // TODO(gc): we are sweeping old pointer space conservatively thus
+    // we can't notify attached profiler about death of functions.
+    // Consider disabling conservative sweeping when profiler
+    // is enabled.
     PROFILE(FunctionDeleteEvent(obj->address()));
   }
 #endif
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticPointersToNewGenUpdatingVisitor::Initialize();
   StaticMarkingVisitor::Initialize();
 }
 
 
 } }  // namespace v8::internal