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 476 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(SweeperType sweeper_type) {
+  SweeperThread::set_sweeping_pending(true);
+  for (int i = 0; i < FLAG_sweeper_threads; i++) {
+    heap()->isolate()->sweeper_threads()[i]->StartSweeping(sweeper_type);
+  }
+}
+
+
+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) {

[Michael Starzinger, 2013/01/28 16:30:18]

Needs a comment that for now we wait, but it might make sense to abandon work in
the future.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+    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 1912 matching lines @@
 
 
 // Sweep a space precisely.  After this has been done the space can
 // be iterated precisely, hitting only the live objects.  Code space
 // is always swept precisely because we want to be able to iterate
 // over it.  Map space is swept precisely, because it is not compacted.
 // Slots in live objects pointing into evacuation candidates are updated
 // if requested.
 template<SweepingMode sweeping_mode, SkipListRebuildingMode skip_list_mode>
 static void SweepPrecisely(PagedSpace* space,
+                           FreeList* free_list,

[Michael Starzinger, 2013/01/28 16:30:18]

No need to pass the free-list, will not be called from a sweeper thread.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

                            Page* p,
                            ObjectVisitor* v) {
   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
   ASSERT_EQ(skip_list_mode == REBUILD_SKIP_LIST,
             space->identity() == CODE_SPACE);
   ASSERT((p->skip_list() == NULL) || (skip_list_mode == REBUILD_SKIP_LIST));
 
   MarkBit::CellType* cells = p->markbits()->cells();
   p->MarkSweptPrecisely();
 
@@ skipping 23 matching lines @@
        cell_index++, object_address += 32 * kPointerSize) {
     ASSERT((unsigned)cell_index ==
         Bitmap::IndexToCell(
             Bitmap::CellAlignIndex(
                 p->AddressToMarkbitIndex(object_address))));
     int live_objects = MarkWordToObjectStarts(cells[cell_index], offsets);
     int live_index = 0;
     for ( ; live_objects != 0; live_objects--) {
       Address free_end = object_address + offsets[live_index++] * kPointerSize;
       if (free_end != free_start) {
-        space->Free(free_start, static_cast<int>(free_end - free_start));
+        MarkCompactCollector::Free(space, free_list, free_start,
+             static_cast<int>(free_end - free_start));
       }
       HeapObject* live_object = HeapObject::FromAddress(free_end);
       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(live_object)));
       Map* map = live_object->map();
       int size = live_object->SizeFromMap(map);
       if (sweeping_mode == SWEEP_AND_VISIT_LIVE_OBJECTS) {
         live_object->IterateBody(map->instance_type(), size, v);
       }
       if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list != NULL) {
         int new_region_start =
             SkipList::RegionNumber(free_end);
         int new_region_end =
             SkipList::RegionNumber(free_end + size - kPointerSize);
         if (new_region_start != curr_region ||
             new_region_end != curr_region) {
           skip_list->AddObject(free_end, size);
           curr_region = new_region_end;
         }
       }
       free_start = free_end + size;
     }
     // Clear marking bits for current cell.
     cells[cell_index] = 0;
   }
   if (free_start != p->area_end()) {
-    space->Free(free_start, static_cast<int>(p->area_end() - free_start));
+    MarkCompactCollector::Free(space, free_list, free_start,
+         static_cast<int>(p->area_end() - free_start));
   }
   p->ResetLiveBytes();
 }
 
 
 static bool SetMarkBitsUnderInvalidatedCode(Code* code, bool value) {
   Page* p = Page::FromAddress(code->address());
 
   if (p->IsEvacuationCandidate() ||
       p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
@@ skipping 209 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(space, space->free_list(), p);

[Michael Starzinger, 2013/01/28 16:30:18]

This call-path leads to a mismatch in the accounting stats, because the space's
free-list is used directly, but the non-space specific freeing function is used.
This proves that having the PagedSpace::free_list() accessor is dangerous. See
comments about templatizing SweepConservatively below on how to fix this.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

             break;
           case OLD_POINTER_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, IGNORE_SKIP_LIST>(
-                space, p, &updating_visitor);
+                space, space->free_list(), p, &updating_visitor);
             break;
           case CODE_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, REBUILD_SKIP_LIST>(
-                space, p, &updating_visitor);
+                space, space->free_list(), p, &updating_visitor);
             break;
           default:
             UNREACHABLE();
             break;
         }
       }
     }
   }
 
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_UPDATE_MISC_POINTERS);
@@ skipping 327 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;
 }
 
 
+intptr_t MarkCompactCollector::Free(PagedSpace* space,

[Michael Starzinger, 2013/01/28 16:30:18]

Make this a static helper ... this should never ever be used by someone else
besides the sweeper below.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+                                    FreeList* free_list,
+                                    Address start,
+                                    int size) {
+  if (space->heap()->mark_compact_collector()->AreSweeperThreadsActivated()) {
+    intptr_t wasted = free_list->Free(start, size);
+    return size - wasted;
+  } else {
+    return space->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) {
+intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space,

[Michael Starzinger, 2013/01/28 16:30:18]

There are basically two different sweepers at work here, one for parallel and
one for non-parallel sweeping. We should templatize this function accordingly.
Something like ...

enum SweepingParallelism {
  SWEEP_ON_MAIN_THREAD,
  SWEEP_IN_PARALLEL
}

For parallel sweeping the free_list parameter will contain the target free-list,
whereas for on the main-thread it will always be NULL (and we should actually
assert that).

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+                                                   FreeList* free_list,
+                                                   Page* p) {
   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
   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)));
+    freed_bytes += Free(space, 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));
+  freed_bytes += Free(space, 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));
+          freed_bytes += Free(space, free_list, free_start,

[Michael Starzinger, 2013/01/28 16:30:18]

This looks like it will tank non-parallel sweeping. The templatization will
resolve this problem.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+                              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));
+    freed_bytes += Free(space, free_list, free_start,
+                        static_cast<int>(block_address - free_start));
   }
 
   p->ResetLiveBytes();
   return freed_bytes;
 }
 
 
+void MarkCompactCollector::PrepareParallelSweeping(PagedSpace* space) {

[Michael Starzinger, 2013/01/28 16:30:18]

Please merge all of this into SweepSpace() and introduce a fourth SweeperType
(i.e. PARALLEL_CONSERVATIVE) that indicates that a "1" should be put into some
pages that are eligible for parallel sweeping.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+  bool unused_page_present = false;
+
+  space->set_was_swept_conservatively(true);
+
+  space->ClearStats();
+
+  PageIterator it(space);
+  while (it.has_next()) {
+    Page* p = it.next();
+
+    // Clear sweeping flags indicating that marking bits are still intact.
+    p->ClearSweptPrecisely();
+    p->ClearSweptConservatively();
+    p->set_parallel_sweeping(0);
+
+    if (p->IsEvacuationCandidate()) {
+      ASSERT(evacuation_candidates_.length() > 0);
+      continue;
+    }
+
+    if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
+      // Will be processed in EvacuateNewSpaceAndCandidates.
+      continue;
+    }
+
+    // One unused page is kept, all further are released before sweeping them.
+    if (p->LiveBytes() == 0) {
+      if (unused_page_present) {
+        if (FLAG_gc_verbose) {
+          PrintF("Sweeping 0x%" V8PRIxPTR " released page.\n",
+                 reinterpret_cast<intptr_t>(p));
+        }
+        // Adjust unswept free bytes because releasing a page expects said
+        // counter to be accurate for unswept pages.
+        space->IncreaseUnsweptFreeBytes(p);
+        space->ReleasePage(p);
+        continue;
+      }
+      unused_page_present = true;
+    }
+  }
+}
+
+
+void MarkCompactCollector::SweepInParallel(PagedSpace* space,
+                                           SweeperType sweeper_type,
+                                           FreeList* private_free_list,
+                                           FreeList* free_list) {
+  PageIterator it(space);
+  while (it.has_next()) {
+    Page* p = it.next();
+
+    if (p->IsEvacuationCandidate()) {
+      ASSERT(evacuation_candidates_.length() > 0);
+      continue;

[Michael Starzinger, 2013/01/28 16:30:18]

In concurrent mode we have a race here, because the main thread is evacuating
while the sweeper threads are sweeping. So you might end up with a case where
the page is no longer and evacuation candidate but was swept already.

The wayt to solve this is to get rid of this check and instead solely rely on
the TryParallelSweeping to pick the pages that should be swept in parallel. This
will require the sweeper thread to basically steal a "1" out of the page header
instead of stealing the "0".

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+    }
+
+    if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
+      // Will be processed in EvacuateNewSpaceAndCandidates.
+      continue;
+    }
+
+    if (p->TryParallelSweeping()) {
+      if (sweeper_type == CONSERVATIVE || sweeper_type == LAZY_CONSERVATIVE) {

[Michael Starzinger, 2013/01/28 16:30:18]

This logic is no longer needed, we always sweep conservatively.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+        SweepConservatively(space, private_free_list, p);
+      } else {
+        SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST>(
+            space, private_free_list, p, NULL);
+      }
+      free_list->Concatenate(private_free_list);
+    }
+  }
+}
+
+
 void MarkCompactCollector::SweepSpace(PagedSpace* space, SweeperType sweeper) {
   space->set_was_swept_conservatively(sweeper == CONSERVATIVE ||
                                       sweeper == LAZY_CONSERVATIVE);
-
+  ASSERT(!(space->identity() == OLD_DATA_SPACE &&
+         FLAG_parallel_sweeping &&
+         FLAG_concurrent_sweeping));
+  ASSERT(!(space->identity() == OLD_POINTER_SPACE &&
+         FLAG_parallel_sweeping &&
+         FLAG_concurrent_sweeping));

[Michael Starzinger, 2013/01/28 16:30:18]

These assertions are bogus, they will always be false, because the two flags are
exclusive. Boolean algebra at its best.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

   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()) {
@@ skipping 37 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(space, space->free_list(), 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(space, space->free_list(), p);
         pages_swept++;
         space->SetPagesToSweep(p->next_page());
         lazy_sweeping_active = true;
         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);
+          SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST>(
+              space, space->free_list(), p, NULL);
         } else {
-          SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST>(space, p, NULL);
+          SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST>(
+              space, space->free_list(), p, NULL);
         }
         pages_swept++;
         break;
       }
       default: {
         UNREACHABLE();
       }
     }
   }
 
@@ skipping 15 matching lines @@
 #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;
   // 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);
+
+  if (AreSweeperThreadsActivated()) {
+    PrepareParallelSweeping(heap()->old_pointer_space());

[Michael Starzinger, 2013/01/28 16:30:18]

See the comment in PrepareParallelSweeping about this, better use SweepSpace
with a new SweeperType here.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+    PrepareParallelSweeping(heap()->old_data_space());
+    StartSweeperThreads(how_to_sweep);

[Michael Starzinger, 2013/01/28 16:30:18]

Move the StartSweeperThreads to below EvacuateNewSpaceAndCandidates for now to
prevent races. AFAICT it should be possible to start the threads here, but let's
play it safe for now and move it down.

[Hannes Payer (out of office), 2013/01/30 10:11:27]

Done.

+    if (FLAG_parallel_sweeping && !FLAG_concurrent_sweeping) {
+      WaitUntilSweepingCompleted();
+    }
+  } else {
+    SweepSpace(heap()->old_pointer_space(), how_to_sweep);
+    SweepSpace(heap()->old_data_space(), how_to_sweep);
+  }
 
   RemoveDeadInvalidatedCode();
   SweepSpace(heap()->code_space(), PRECISE);
 
   SweepSpace(heap()->cell_space(), PRECISE);
 
   EvacuateNewSpaceAndCandidates();
 
   // ClearNonLiveTransitions depends on precise sweeping of map space to
   // detect whether unmarked map became dead in this collection or in one
@@ skipping 195 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal