Parallel and concurrent sweeping.

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 23 matching lines @@
 #include "gdb-jit.h"
 #include "global-handles.h"
 #include "heap-profiler.h"
 #include "ic-inl.h"
 #include "incremental-marking.h"
 #include "liveobjectlist-inl.h"
 #include "mark-compact.h"
 #include "objects-visiting.h"
 #include "objects-visiting-inl.h"
 #include "stub-cache.h"
+#include "sweeper-thread.h"
 
 namespace v8 {
 namespace internal {
 
 
 const char* Marking::kWhiteBitPattern = "00";
 const char* Marking::kBlackBitPattern = "10";
 const char* Marking::kGreyBitPattern = "11";
 const char* Marking::kImpossibleBitPattern = "01";
 
@@ skipping 433 matching lines @@
   for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
     MarkBit mark_bit = Marking::MarkBitFrom(obj);
     mark_bit.Clear();
     mark_bit.Next().Clear();
     Page::FromAddress(obj->address())->ResetProgressBar();
     Page::FromAddress(obj->address())->ResetLiveBytes();
   }
 }
 
 
+void MarkCompactCollector::StartSweeperThreads() {
+  SweeperThread::set_sweeping_pending(true);
+  for (int i = 0; i < FLAG_sweeper_threads; i++) {
+    heap()->isolate()->sweeper_threads()[i]->StartSweeping();
+  }
+}
+
+
+void MarkCompactCollector::WaitUntilSweepingCompleted() {
+  if (SweeperThread::sweeping_pending()) {
+    for (int i = 0; i < FLAG_sweeper_threads; i++) {
+      heap()->isolate()->sweeper_threads()[i]->WaitForSweeperThread();
+    }
+    SweeperThread::set_sweeping_pending(false);
+    StealMemoryFromSweeperThreads(heap()->paged_space(OLD_DATA_SPACE));
+    StealMemoryFromSweeperThreads(heap()->paged_space(OLD_POINTER_SPACE));
+    heap()->FreeQueuedChunks();
+  }
+}
+
+
+intptr_t MarkCompactCollector::
+             StealMemoryFromSweeperThreads(PagedSpace* space) {
+  intptr_t freed_bytes = 0;
+  for (int i = 0; i < FLAG_sweeper_threads; i++) {
+    freed_bytes += heap()->isolate()->sweeper_threads()[i]->StealMemory(space);
+  }
+  return freed_bytes;
+}
+
+
+bool MarkCompactCollector::AreSweeperThreadsActivated() {
+  return heap()->isolate()->sweeper_threads() != NULL;
+}
+
+
 bool Marking::TransferMark(Address old_start, Address new_start) {
   // This is only used when resizing an object.
   ASSERT(MemoryChunk::FromAddress(old_start) ==
          MemoryChunk::FromAddress(new_start));
 
   // If the mark doesn't move, we don't check the color of the object.
   // It doesn't matter whether the object is black, since it hasn't changed
   // size, so the adjustment to the live data count will be zero anyway.
   if (old_start == new_start) return false;
 
@@ skipping 282 matching lines @@
   // variable.
   tracer_ = tracer;
 
 #ifdef DEBUG
   ASSERT(state_ == IDLE);
   state_ = PREPARE_GC;
 #endif
 
   ASSERT(!FLAG_never_compact || !FLAG_always_compact);
 
+  if (AreSweeperThreadsActivated() && FLAG_concurrent_sweeping) {
+    // Instead of waiting we could also abort the sweeper threads here.
+    WaitUntilSweepingCompleted();
+  }
+
   // Clear marking bits if incremental marking is aborted.
   if (was_marked_incrementally_ && abort_incremental_marking_) {
     heap()->incremental_marking()->Abort();
     ClearMarkbits();
     AbortCompaction();
     was_marked_incrementally_ = false;
   }
 
   // Don't start compaction if we are in the middle of incremental
   // marking cycle. We did not collect any slots.
@@ skipping 2211 matching lines @@
       } else {
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " during evacuation.\n",
                  reinterpret_cast<intptr_t>(p));
         }
         PagedSpace* space = static_cast<PagedSpace*>(p->owner());
         p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
 
         switch (space->identity()) {
           case OLD_DATA_SPACE:
-            SweepConservatively(space, p);
+            SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
             break;
           case OLD_POINTER_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, IGNORE_SKIP_LIST>(
                 space, p, &updating_visitor);
             break;
           case CODE_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, REBUILD_SKIP_LIST>(
                 space, p, &updating_visitor);
             break;
           default:
@@ skipping 335 matching lines @@
   }
   uint32_t first_set_bit = ((cell ^ (cell - 1)) + 1) >> 1;
   ASSERT((first_set_bit & cell) == first_set_bit);
   int live_objects = MarkWordToObjectStarts(first_set_bit, offsets);
   ASSERT(live_objects == 1);
   USE(live_objects);
   return block_address + offsets[0] * kPointerSize;
 }
 
 
+static intptr_t Free(FreeList* free_list,
+                     Address start,
+                     int size) {
+  return size - free_list->Free(start, size);
+}
+
+
 // Sweeps a space conservatively.  After this has been done the larger free
 // spaces have been put on the free list and the smaller ones have been
 // ignored and left untouched.  A free space is always either ignored or put
 // on the free list, never split up into two parts.  This is important
 // because it means that any FreeSpace maps left actually describe a region of
 // memory that can be ignored when scanning.  Dead objects other than free
 // spaces will not contain the free space map.
-intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space, Page* p) {
+template<MarkCompactCollector::SweepingParallelism mode>
+intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space,
+                                                   FreeList* free_list,
+                                                   Page* p) {
   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
+  ASSERT((mode == MarkCompactCollector::SWEEP_IN_PARALLEL &&
+         free_list != NULL) ||
+         (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY &&
+         free_list == NULL));
+
   MarkBit::CellType* cells = p->markbits()->cells();
   p->MarkSweptConservatively();
 
   int last_cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->area_end())));
 
   int cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->area_start())));
 
   intptr_t freed_bytes = 0;
 
   // This is the start of the 32 word block that we are currently looking at.
   Address block_address = p->area_start();
 
   // Skip over all the dead objects at the start of the page and mark them free.
   for (;
        cell_index < last_cell_index;
        cell_index++, block_address += 32 * kPointerSize) {
     if (cells[cell_index] != 0) break;
   }
   size_t size = block_address - p->area_start();
   if (cell_index == last_cell_index) {
-    freed_bytes += static_cast<int>(space->Free(p->area_start(),
-                                                static_cast<int>(size)));
+    if (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY) {

[Michael Starzinger, 2013/01/30 11:01:19]

You could factor out this logic and move it into the static Free() helper,
templatize the helper and hope that GCC inlines it. Would make the source
cleaner and produce the same code. I would prefer that over the current
implementation, but I'll leave the decision whether to do that or not up to you.

[Hannes Payer (out of office), 2013/01/30 12:07:32]

I templatized Free, the code looks cleaner.

On 2013/01/30 11:01:19, Michael Starzinger wrote:

+      freed_bytes += static_cast<int>(space->Free(p->area_start(),
+                                      static_cast<int>(size)));
+    } else {
+      freed_bytes += Free(free_list, p->area_start(), static_cast<int>(size));
+    }
     ASSERT_EQ(0, p->LiveBytes());
     return freed_bytes;
   }
   // Grow the size of the start-of-page free space a little to get up to the
   // first live object.
   Address free_end = StartOfLiveObject(block_address, cells[cell_index]);
   // Free the first free space.
   size = free_end - p->area_start();
-  freed_bytes += space->Free(p->area_start(),
-                             static_cast<int>(size));
+  if (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY) {
+    freed_bytes += space->Free(p->area_start(), static_cast<int>(size));
+  } else {
+    freed_bytes += Free(free_list, p->area_start(), static_cast<int>(size));
+  }
   // The start of the current free area is represented in undigested form by
   // the address of the last 32-word section that contained a live object and
   // the marking bitmap for that cell, which describes where the live object
   // started.  Unless we find a large free space in the bitmap we will not
   // digest this pair into a real address.  We start the iteration here at the
   // first word in the marking bit map that indicates a live object.
   Address free_start = block_address;
   uint32_t free_start_cell = cells[cell_index];
 
   for ( ;
        cell_index < last_cell_index;
        cell_index++, block_address += 32 * kPointerSize) {
     ASSERT((unsigned)cell_index ==
         Bitmap::IndexToCell(
             Bitmap::CellAlignIndex(
                 p->AddressToMarkbitIndex(block_address))));
     uint32_t cell = cells[cell_index];
     if (cell != 0) {
       // We have a live object.  Check approximately whether it is more than 32
       // words since the last live object.
       if (block_address - free_start > 32 * kPointerSize) {
         free_start = DigestFreeStart(free_start, free_start_cell);
         if (block_address - free_start > 32 * kPointerSize) {
           // Now that we know the exact start of the free space it still looks
           // like we have a large enough free space to be worth bothering with.
           // so now we need to find the start of the first live object at the
           // end of the free space.
           free_end = StartOfLiveObject(block_address, cell);
-          freed_bytes += space->Free(free_start,
-                                     static_cast<int>(free_end - free_start));
+          if (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY) {
+            freed_bytes += space->Free(free_start,
+                                       static_cast<int>(free_end - free_start));
+          } else {
+            freed_bytes += Free(free_list, free_start,
+                                static_cast<int>(free_end - free_start));
+          }
         }
       }
       // Update our undigested record of where the current free area started.
       free_start = block_address;
       free_start_cell = cell;
       // Clear marking bits for current cell.
       cells[cell_index] = 0;
     }
   }
 
   // Handle the free space at the end of the page.
   if (block_address - free_start > 32 * kPointerSize) {
     free_start = DigestFreeStart(free_start, free_start_cell);
-    freed_bytes += space->Free(free_start,
-                               static_cast<int>(block_address - free_start));
+    if (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY) {
+      freed_bytes += space->Free(free_start,
+          static_cast<int>(block_address - free_start));
+    } else {
+      freed_bytes += Free(free_list, free_start,
+                          static_cast<int>(block_address - free_start));
+    }
   }
 
   p->ResetLiveBytes();
   return freed_bytes;
 }
 
 
+void MarkCompactCollector::SweepInParallel(PagedSpace* space,
+                                           FreeList* private_free_list,
+                                           FreeList* free_list) {
+  PageIterator it(space);
+  while (it.has_next()) {
+    Page* p = it.next();
+
+    if (p->TryParallelSweeping()) {
+      SweepConservatively<SWEEP_IN_PARALLEL>(space, private_free_list, p);
+      free_list->Concatenate(private_free_list);
+    }
+  }
+}
+
+
 void MarkCompactCollector::SweepSpace(PagedSpace* space, SweeperType sweeper) {
   space->set_was_swept_conservatively(sweeper == CONSERVATIVE ||
                                       sweeper == LAZY_CONSERVATIVE);
-
   space->ClearStats();
 
   PageIterator it(space);
 
   intptr_t freed_bytes = 0;
   int pages_swept = 0;
   bool lazy_sweeping_active = false;
   bool unused_page_present = false;
 
   while (it.has_next()) {
     Page* p = it.next();
 
+    ASSERT(p->parallel_sweeping() == 0);
     // Clear sweeping flags indicating that marking bits are still intact.
     p->ClearSweptPrecisely();
     p->ClearSweptConservatively();
 
     if (p->IsEvacuationCandidate()) {
       ASSERT(evacuation_candidates_.length() > 0);
       continue;
     }
 
     if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
@@ skipping 25 matching lines @@
       space->IncreaseUnsweptFreeBytes(p);
       continue;
     }
 
     switch (sweeper) {
       case CONSERVATIVE: {
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " conservatively.\n",
                  reinterpret_cast<intptr_t>(p));
         }
-        SweepConservatively(space, p);
+        SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
         pages_swept++;
         break;
       }
       case LAZY_CONSERVATIVE: {
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " conservatively as needed.\n",
                  reinterpret_cast<intptr_t>(p));
         }
-        freed_bytes += SweepConservatively(space, p);
+        freed_bytes += SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
         pages_swept++;
         space->SetPagesToSweep(p->next_page());
         lazy_sweeping_active = true;
         break;
       }
+      case PARALLEL_CONSERVATIVE: {
+        if (FLAG_gc_verbose) {
+          PrintF("Prepare conservatively parallel sweeping 0x%" V8PRIxPTR ".\n",

[Michael Starzinger, 2013/01/30 11:01:19]

Let's rephrase this log line to "Sweeping 0x??? conservatively in parallel.", I
think that's easier to understand.

[Hannes Payer (out of office), 2013/01/30 12:07:32]

Done.

+                 reinterpret_cast<intptr_t>(p));
+        }
+        p->set_parallel_sweeping(1);
+        break;
+      }
       case PRECISE: {
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " precisely.\n",
                  reinterpret_cast<intptr_t>(p));
         }
         if (space->identity() == CODE_SPACE) {
           SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST>(space, p, NULL);
         } else {
           SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST>(space, p, NULL);
         }
@@ skipping 19 matching lines @@
 
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 #ifdef DEBUG
   state_ = SWEEP_SPACES;
 #endif
   SweeperType how_to_sweep =
       FLAG_lazy_sweeping ? LAZY_CONSERVATIVE : CONSERVATIVE;
   if (FLAG_expose_gc) how_to_sweep = CONSERVATIVE;
   if (sweep_precisely_) how_to_sweep = PRECISE;
+  if (AreSweeperThreadsActivated()) how_to_sweep = PARALLEL_CONSERVATIVE;
   // 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(), how_to_sweep);
   SweepSpace(heap()->old_data_space(), how_to_sweep);
-
+  

[Michael Starzinger, 2013/01/30 11:01:19]

I think you have white-space on that empty line. Should trip a presubmit
failure.

[Hannes Payer (out of office), 2013/01/30 12:07:32]

Done.

   RemoveDeadInvalidatedCode();
   SweepSpace(heap()->code_space(), PRECISE);
 
   SweepSpace(heap()->cell_space(), PRECISE);
 
   EvacuateNewSpaceAndCandidates();
 
+  if (AreSweeperThreadsActivated()) {
+    // The starting of the sweeper threads should be after SweepSpace

[Michael Starzinger, 2013/01/30 11:01:19]

Let's turn this comment into a TODO().

[Hannes Payer (out of office), 2013/01/30 12:07:32]

Done.

+    // old data space.
+    StartSweeperThreads();
+    if (FLAG_parallel_sweeping && !FLAG_concurrent_sweeping) {
+      WaitUntilSweepingCompleted();
+    }
+  }
+
   // ClearNonLiveTransitions depends on precise sweeping of map space to
   // detect whether unmarked map became dead in this collection or in one
   // of the previous ones.
   SweepSpace(heap()->map_space(), PRECISE);
 
   // Deallocate unmarked objects and clear marked bits for marked objects.
   heap_->lo_space()->FreeUnmarkedObjects();
 }
 
 
@@ skipping 187 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal