Concurrent/parallel precise sweeping.

src/mark-compact.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/v8.h"
 
 #include "src/base/atomicops.h"
 #include "src/code-stubs.h"
 #include "src/compilation-cache.h"
 #include "src/cpu-profiler.h"
@@ skipping 190 matching lines @@
       current += object->Size();
     }
   }
 }
 
 
 static void VerifyEvacuation(PagedSpace* space) {
   // TODO(hpayer): Bring back VerifyEvacuation for parallel-concurrently
   // swept pages.
   if ((FLAG_concurrent_sweeping || FLAG_parallel_sweeping) &&
-      !space->is_iterable()) return;
+      !space->swept_precisely()) return;
   PageIterator it(space);
 
   while (it.has_next()) {
     Page* p = it.next();
     if (p->IsEvacuationCandidate()) continue;
     VerifyEvacuation(p->area_start(), p->area_end());
   }
 }
 
 
@@ skipping 1822 matching lines @@
     }
     *cells = 0;
   }
   return survivors_size;
 }
 
 
 static void DiscoverGreyObjectsInSpace(Heap* heap,
                                        MarkingDeque* marking_deque,
                                        PagedSpace* space) {
-  if (space->is_iterable()) {
+  if (space->swept_precisely()) {
     HeapObjectIterator it(space);
     DiscoverGreyObjectsWithIterator(heap, marking_deque, &it);
   } else {
     PageIterator it(space);
     while (it.has_next()) {
       Page* p = it.next();
       DiscoverGreyObjectsOnPage(marking_deque, p);
       if (marking_deque->IsFull()) return;
     }
   }
@@ skipping 1060 matching lines @@
 }
 
 
 void MarkCompactCollector::EvacuatePages() {
   int npages = evacuation_candidates_.length();
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     ASSERT(p->IsEvacuationCandidate() ||
            p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
     ASSERT(static_cast<int>(p->parallel_sweeping()) ==
-           MemoryChunk::PARALLEL_SWEEPING_DONE);
+           MemoryChunk::SWEEPING_DONE);
     if (p->IsEvacuationCandidate()) {
       // During compaction we might have to request a new page.
       // Check that space still have room for that.
       if (static_cast<PagedSpace*>(p->owner())->CanExpand()) {
         EvacuateLiveObjectsFromPage(p);
       } else {
         // Without room for expansion evacuation is not guaranteed to succeed.
         // Pessimistically abandon unevacuated pages.
         for (int j = i; j < npages; j++) {
           Page* page = evacuation_candidates_[j];
@@ skipping 75 matching lines @@
   IGNORE_SKIP_LIST
 };
 
 
 enum FreeSpaceTreatmentMode {
   IGNORE_FREE_SPACE,
   ZAP_FREE_SPACE
 };
 
 
+template<MarkCompactCollector::SweepingParallelism mode>
+static intptr_t Free(PagedSpace* space,
+                     FreeList* free_list,
+                     Address start,
+                     int size) {
+  if (mode == MarkCompactCollector::SWEEP_ON_MAIN_THREAD) {
+    return space->Free(start, size);

[Jarin, 2014/07/18 08:31:29]

Could we ASSERT(free_list == NULL) here?

[Hannes Payer (out of office), 2014/07/18 10:47:20]

Done.

+  } else {
+    return size - free_list->Free(start, size);
+  }
+}
+
+
 // 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,
+         MarkCompactCollector::SweepingParallelism parallelism,
          SkipListRebuildingMode skip_list_mode,
          FreeSpaceTreatmentMode free_space_mode>
-static void SweepPrecisely(PagedSpace* space,
+static int SweepPrecisely(PagedSpace* space,
+                           FreeList* free_list,
                            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));
+  ASSERT(parallelism == MarkCompactCollector::SWEEP_ON_MAIN_THREAD ||
+         sweeping_mode == SWEEP_ONLY);
 
   double start_time = 0.0;
   if (FLAG_print_cumulative_gc_stat) {
     start_time = base::OS::TimeCurrentMillis();
   }
 
-  p->MarkSweptPrecisely();
+  if (parallelism == MarkCompactCollector::SWEEP_IN_PARALLEL) {
+    p->set_parallel_sweeping(MemoryChunk::SWEEPING_FINALIZE);
+  } else {
+    p->MarkSweptPrecisely();
+  }
 
   Address free_start = p->area_start();
   ASSERT(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
   int offsets[16];
 
   SkipList* skip_list = p->skip_list();
   int curr_region = -1;
   if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list) {
     skip_list->Clear();
   }
 
+  intptr_t freed_bytes = 0;
+  intptr_t max_freed_bytes = 0;
+
   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
     Address cell_base = it.CurrentCellBase();
     MarkBit::CellType* cell = it.CurrentCell();
     int live_objects = MarkWordToObjectStarts(*cell, offsets);
     int live_index = 0;
     for ( ; live_objects != 0; live_objects--) {
       Address free_end = cell_base + offsets[live_index++] * kPointerSize;
       if (free_end != free_start) {
+        int size = static_cast<int>(free_end - free_start);
         if (free_space_mode == ZAP_FREE_SPACE) {
-          memset(free_start, 0xcc, static_cast<int>(free_end - free_start));
+          memset(free_start, 0xcc, size);
         }
-        space->Free(free_start, static_cast<int>(free_end - free_start));
+        freed_bytes = Free<parallelism>(space, free_list, free_start, size);
+        max_freed_bytes = Max(freed_bytes, max_freed_bytes);
 #ifdef ENABLE_GDB_JIT_INTERFACE
         if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
           GDBJITInterface::RemoveCodeRange(free_start, free_end);
         }
 #endif
       }
       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);
@@ skipping 10 matching lines @@
           skip_list->AddObject(free_end, size);
           curr_region = new_region_end;
         }
       }
       free_start = free_end + size;
     }
     // Clear marking bits for current cell.
     *cell = 0;
   }
   if (free_start != p->area_end()) {
+    int size = static_cast<int>(p->area_end() - free_start);
     if (free_space_mode == ZAP_FREE_SPACE) {
-      memset(free_start, 0xcc, static_cast<int>(p->area_end() - free_start));
+      memset(free_start, 0xcc, size);
     }
-    space->Free(free_start, static_cast<int>(p->area_end() - free_start));
+    freed_bytes = Free<parallelism>(space, free_list, free_start, size);
+    max_freed_bytes = Max(freed_bytes, max_freed_bytes);
 #ifdef ENABLE_GDB_JIT_INTERFACE
     if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
       GDBJITInterface::RemoveCodeRange(free_start, p->area_end());
     }
 #endif
   }
   p->ResetLiveBytes();
   if (FLAG_print_cumulative_gc_stat) {
     space->heap()->AddSweepingTime(base::OS::TimeCurrentMillis() - start_time);
   }
+  return FreeList::GuaranteedAllocatable(static_cast<int>(max_freed_bytes));
 }
 
 
 static bool SetMarkBitsUnderInvalidatedCode(Code* code, bool value) {
   Page* p = Page::FromAddress(code->address());
 
   if (p->IsEvacuationCandidate() ||
       p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
     return false;
   }
@@ skipping 215 matching lines @@
         }
         PagedSpace* space = static_cast<PagedSpace*>(p->owner());
         p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
 
         switch (space->identity()) {
           case OLD_DATA_SPACE:
             SweepConservatively<SWEEP_ON_MAIN_THREAD>(space, NULL, p);
             break;
           case OLD_POINTER_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
+                           SWEEP_ON_MAIN_THREAD,
                            IGNORE_SKIP_LIST,
                            IGNORE_FREE_SPACE>(
-                space, p, &updating_visitor);
+                space, NULL, p, &updating_visitor);
             break;
           case CODE_SPACE:
             if (FLAG_zap_code_space) {
               SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
+                             SWEEP_ON_MAIN_THREAD,
                              REBUILD_SKIP_LIST,
                              ZAP_FREE_SPACE>(
-                  space, p, &updating_visitor);
+                  space, NULL, p, &updating_visitor);
             } else {
               SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
+                             SWEEP_ON_MAIN_THREAD,
                              REBUILD_SKIP_LIST,
                              IGNORE_FREE_SPACE>(
-                  space, p, &updating_visitor);
+                  space, NULL, p, &updating_visitor);
             }
             break;
           default:
             UNREACHABLE();
             break;
         }
       }
     }
   }
 
@@ skipping 351 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;
 }
 
 
-template<MarkCompactCollector::SweepingParallelism mode>
-static intptr_t Free(PagedSpace* space,
-                     FreeList* free_list,
-                     Address start,
-                     int size) {
-  if (mode == MarkCompactCollector::SWEEP_ON_MAIN_THREAD) {
-    return space->Free(start, size);
-  } else {
-    return size - free_list->Free(start, size);
-  }
-}
-
-
 // Force instantiation of templatized SweepConservatively method for
 // SWEEP_ON_MAIN_THREAD mode.
 template intptr_t MarkCompactCollector::
     SweepConservatively<MarkCompactCollector::SWEEP_ON_MAIN_THREAD>(
         PagedSpace*, FreeList*, Page*);
 
 
 // Force instantiation of templatized SweepConservatively method for
 // SWEEP_IN_PARALLEL mode.
 template intptr_t MarkCompactCollector::
     SweepConservatively<MarkCompactCollector::SWEEP_IN_PARALLEL>(
         PagedSpace*, FreeList*, Page*);
 
 
 // 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.
 template<MarkCompactCollector::SweepingParallelism mode>
-intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space,
-                                                   FreeList* free_list,
-                                                   Page* p) {
+int 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_ON_MAIN_THREAD &&
          free_list == NULL));
 
   // When parallel sweeping is active, the page will be marked after
   // sweeping by the main thread.
   if (mode == MarkCompactCollector::SWEEP_IN_PARALLEL) {
-    p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_FINALIZE);
+    p->set_parallel_sweeping(MemoryChunk::SWEEPING_FINALIZE);
   } else {
     p->MarkSweptConservatively();
   }
 
   intptr_t freed_bytes = 0;
   intptr_t max_freed_bytes = 0;
   size_t size = 0;
 
   // Skip over all the dead objects at the start of the page and mark them free.
   Address cell_base = 0;
@@ skipping 76 matching lines @@
                                           int required_freed_bytes) {
   PageIterator it(space);
   FreeList* free_list = space == heap()->old_pointer_space()
                             ? free_list_old_pointer_space_.get()
                             : free_list_old_data_space_.get();
   FreeList private_free_list(space);
   int max_freed = 0;
   int max_freed_overall = 0;
   while (it.has_next()) {
     Page* p = it.next();
-
     if (p->TryParallelSweeping()) {
-      max_freed = static_cast<int>(SweepConservatively<SWEEP_IN_PARALLEL>(
-          space, &private_free_list, p));
+      if (space->swept_precisely()) {
+        max_freed = SweepPrecisely<SWEEP_ONLY,
+                                   SWEEP_IN_PARALLEL,
+                                   IGNORE_SKIP_LIST,
+                                   IGNORE_FREE_SPACE>(
+                                       space, &private_free_list, p, NULL);
+      } else {
+        max_freed = SweepConservatively<SWEEP_IN_PARALLEL>(
+            space, &private_free_list, p);
+      }
       ASSERT(max_freed >= 0);
       free_list->Concatenate(&private_free_list);
       if (required_freed_bytes > 0 && max_freed >= required_freed_bytes) {
         return max_freed;
       }
       max_freed_overall = Max(max_freed, max_freed_overall);
     }
     if (p == space->end_of_unswept_pages()) break;
   }
   return max_freed_overall;
 }
 
 
 void MarkCompactCollector::SweepSpace(PagedSpace* space, SweeperType sweeper) {
-  space->set_is_iterable(sweeper == PRECISE);
+  space->set_swept_precisely(sweeper == PRECISE);

[Jarin, 2014/07/18 08:31:29]

I think the flag should be also set if sweeper is CONCURRENT_PRECISE or
PARALLEL_PRECISE.

[Hannes Payer (out of office), 2014/07/18 10:47:20]

Good catch! Done.

   space->ClearStats();
 
   // We defensively initialize end_of_unswept_pages_ here with the first page
   // of the pages list.
   space->set_end_of_unswept_pages(space->FirstPage());
 
   PageIterator it(space);
 
   int pages_swept = 0;
   bool unused_page_present = false;
   bool parallel_sweeping_active = false;
 
   while (it.has_next()) {
     Page* p = it.next();
-    ASSERT(p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_DONE);
+    ASSERT(p->parallel_sweeping() == MemoryChunk::SWEEPING_DONE);
 
     // Clear sweeping flags indicating that marking bits are still intact.
     p->ClearSweptPrecisely();
     p->ClearSweptConservatively();
 
     if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION) ||
         p->IsEvacuationCandidate()) {
       // Will be processed in EvacuateNewSpaceAndCandidates.
       ASSERT(evacuation_candidates_.length() > 0);
       continue;
@@ skipping 24 matching lines @@
                    reinterpret_cast<intptr_t>(p));
           }
           SweepConservatively<SWEEP_ON_MAIN_THREAD>(space, NULL, p);
           pages_swept++;
           parallel_sweeping_active = true;
         } else {
           if (FLAG_gc_verbose) {
             PrintF("Sweeping 0x%" V8PRIxPTR " conservatively in parallel.\n",
                    reinterpret_cast<intptr_t>(p));
           }
-          p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_PENDING);
+          p->set_parallel_sweeping(MemoryChunk::SWEEPING_PENDING);
           space->IncreaseUnsweptFreeBytes(p);
         }
         space->set_end_of_unswept_pages(p);
         break;
       }
+      case CONCURRENT_PRECISE:
+      case PARALLEL_PRECISE:
+        if (!parallel_sweeping_active) {
+          if (FLAG_gc_verbose) {
+            PrintF("Sweeping 0x%" V8PRIxPTR " precisely.\n",
+                   reinterpret_cast<intptr_t>(p));
+          }
+          SweepPrecisely<SWEEP_ONLY,
+                         SWEEP_ON_MAIN_THREAD,
+                         IGNORE_SKIP_LIST,
+                         IGNORE_FREE_SPACE>(space, NULL, p, NULL);
+          pages_swept++;
+          parallel_sweeping_active = true;
+        } else {
+          if (FLAG_gc_verbose) {
+            PrintF("Sweeping 0x%" V8PRIxPTR " conservatively in parallel.\n",
+                   reinterpret_cast<intptr_t>(p));
+          }
+          p->set_parallel_sweeping(MemoryChunk::SWEEPING_PENDING);
+          space->IncreaseUnsweptFreeBytes(p);
+        }
+        space->set_end_of_unswept_pages(p);
+        break;
       case PRECISE: {
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " precisely.\n",
                  reinterpret_cast<intptr_t>(p));
         }
         if (space->identity() == CODE_SPACE && FLAG_zap_code_space) {
-          SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST, ZAP_FREE_SPACE>(
-              space, p, NULL);
+          SweepPrecisely<SWEEP_ONLY,
+                         SWEEP_ON_MAIN_THREAD,
+                         REBUILD_SKIP_LIST,
+                         ZAP_FREE_SPACE>(space, NULL, p, NULL);
         } else if (space->identity() == CODE_SPACE) {
-          SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST, IGNORE_FREE_SPACE>(
-              space, p, NULL);
+          SweepPrecisely<SWEEP_ONLY,
+                         SWEEP_ON_MAIN_THREAD,
+                         REBUILD_SKIP_LIST,
+                         IGNORE_FREE_SPACE>(space, NULL, p, NULL);
         } else {
-          SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST, IGNORE_FREE_SPACE>(
-              space, p, NULL);
+          SweepPrecisely<SWEEP_ONLY,
+                         SWEEP_ON_MAIN_THREAD,
+                         IGNORE_SKIP_LIST,
+                         IGNORE_FREE_SPACE>(space, NULL, p, NULL);
         }
         pages_swept++;
         break;
       }
       default: {
         UNREACHABLE();
       }
     }
   }
 
   if (FLAG_gc_verbose) {
     PrintF("SweepSpace: %s (%d pages swept)\n",
            AllocationSpaceName(space->identity()),
            pages_swept);
   }
 
   // Give pages that are queued to be freed back to the OS.
   heap()->FreeQueuedChunks();
 }
 
 
+static bool ShouldStartSweeperThreads(MarkCompactCollector::SweeperType type) {
+  return type == MarkCompactCollector::PARALLEL_CONSERVATIVE ||
+         type == MarkCompactCollector::CONCURRENT_CONSERVATIVE ||
+         type == MarkCompactCollector::PARALLEL_PRECISE ||
+         type == MarkCompactCollector::CONCURRENT_PRECISE;
+}
+
+
+static bool ShouldWaitForSweeperThreads(
+    MarkCompactCollector::SweeperType type) {
+  return type == MarkCompactCollector::PARALLEL_CONSERVATIVE ||
+         type == MarkCompactCollector::PARALLEL_PRECISE;
+}
+
+
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 #ifdef DEBUG
   state_ = SWEEP_SPACES;
 #endif
   SweeperType how_to_sweep = CONCURRENT_CONSERVATIVE;
   if (FLAG_parallel_sweeping) how_to_sweep = PARALLEL_CONSERVATIVE;
   if (FLAG_concurrent_sweeping) how_to_sweep = CONCURRENT_CONSERVATIVE;
-
+  if (FLAG_always_precise_sweeping && FLAG_parallel_sweeping) {
+    how_to_sweep = PARALLEL_PRECISE;
+  }
+  if (FLAG_always_precise_sweeping && FLAG_concurrent_sweeping) {
+    how_to_sweep = CONCURRENT_PRECISE;
+  }
   if (sweep_precisely_) how_to_sweep = PRECISE;

[Jarin, 2014/07/18 08:31:29]

I am wondering whether we want sweep in parallel here (and also in the spaces
below).

[Hannes Payer (out of office), 2014/07/18 10:47:20]

I will address this comment in a separate cl.

 
   MoveEvacuationCandidatesToEndOfPagesList();
 
   // 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.
   { GCTracer::Scope sweep_scope(tracer_, GCTracer::Scope::MC_SWEEP_OLDSPACE);
     { SequentialSweepingScope scope(this);
       SweepSpace(heap()->old_pointer_space(), how_to_sweep);
       SweepSpace(heap()->old_data_space(), how_to_sweep);
     }
 
-    if (how_to_sweep == PARALLEL_CONSERVATIVE ||
-        how_to_sweep == CONCURRENT_CONSERVATIVE) {
+    if (ShouldStartSweeperThreads(how_to_sweep)) {
       StartSweeperThreads();
     }
 
-    if (how_to_sweep == PARALLEL_CONSERVATIVE) {
+    if (ShouldWaitForSweeperThreads(how_to_sweep)) {
       EnsureSweepingCompleted();
     }
   }
   RemoveDeadInvalidatedCode();
 
   { GCTracer::Scope sweep_scope(tracer_, GCTracer::Scope::MC_SWEEP_CODE);
     SweepSpace(heap()->code_space(), PRECISE);
   }
 
   { GCTracer::Scope sweep_scope(tracer_, GCTracer::Scope::MC_SWEEP_CELL);
@@ skipping 15 matching lines @@
 
   // Deallocate evacuated candidate pages.
   ReleaseEvacuationCandidates();
 }
 
 
 void MarkCompactCollector::ParallelSweepSpaceComplete(PagedSpace* space) {
   PageIterator it(space);
   while (it.has_next()) {
     Page* p = it.next();
-    if (p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_FINALIZE) {
-      p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_DONE);
-      p->MarkSweptConservatively();
+    if (p->parallel_sweeping() == MemoryChunk::SWEEPING_FINALIZE) {
+      p->set_parallel_sweeping(MemoryChunk::SWEEPING_DONE);
+      if (space->swept_precisely()) {
+        p->MarkSweptPrecisely();
+      } else {
+        p->MarkSweptConservatively();
+      }
     }
-    ASSERT(p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_DONE);
+    ASSERT(p->parallel_sweeping() == MemoryChunk::SWEEPING_DONE);
   }
 }
 
 
 void MarkCompactCollector::ParallelSweepSpacesComplete() {
   ParallelSweepSpaceComplete(heap()->old_pointer_space());
   ParallelSweepSpaceComplete(heap()->old_data_space());
 }
 
 
@@ skipping 210 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal