Remove conservative sweeping.

src/heap/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/base/bits.h"
 #include "src/code-stubs.h"
 #include "src/compilation-cache.h"
@@ skipping 182 matching lines @@
     while (current < limit) {
       HeapObject* object = HeapObject::FromAddress(current);
       object->Iterate(&visitor);
       current += object->Size();
     }
   }
 }
 
 
 static void VerifyEvacuation(Heap* heap, PagedSpace* space) {
-  if (!space->swept_precisely()) return;
   if (FLAG_use_allocation_folding &&
       (space == heap->old_pointer_space() || space == heap->old_data_space())) {
     return;
   }
   PageIterator it(space);
 
   while (it.has_next()) {
     Page* p = it.next();
     if (p->IsEvacuationCandidate()) continue;
     VerifyEvacuation(p);
@@ skipping 2905 matching lines @@
 
   heap_->IncrementYoungSurvivorsCounter(survivors_size);
   new_space->set_age_mark(new_space->top());
 }
 
 
 void MarkCompactCollector::EvacuateLiveObjectsFromPage(Page* p) {
   AlwaysAllocateScope always_allocate(isolate());
   PagedSpace* space = static_cast<PagedSpace*>(p->owner());
   DCHECK(p->IsEvacuationCandidate() && !p->WasSwept());
-  p->MarkSweptPrecisely();
+  p->SetWasSwept();
 
   int offsets[16];
 
   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
     Address cell_base = it.CurrentCellBase();
     MarkBit::CellType* cell = it.CurrentCell();
 
     if (*cell == 0) continue;
 
     int live_objects = MarkWordToObjectStarts(*cell, offsets);
@@ skipping 154 matching lines @@
 // 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.
 // Returns the size of the biggest continuous freed memory chunk in bytes.
 template <SweepingMode sweeping_mode,
           MarkCompactCollector::SweepingParallelism parallelism,
           SkipListRebuildingMode skip_list_mode,
           FreeSpaceTreatmentMode free_space_mode>
 static int SweepPrecisely(PagedSpace* space, FreeList* free_list, Page* p,

[Jarin, 2014/08/21 08:29:12]

How about renaming to just "Sweep"?

[Hannes Payer (out of office), 2014/08/21 09:03:17]

Done.

                           ObjectVisitor* v) {
   DCHECK(!p->IsEvacuationCandidate() && !p->WasSwept());
   DCHECK_EQ(skip_list_mode == REBUILD_SKIP_LIST,
             space->identity() == CODE_SPACE);
   DCHECK((p->skip_list() == NULL) || (skip_list_mode == REBUILD_SKIP_LIST));
   DCHECK(parallelism == MarkCompactCollector::SWEEP_ON_MAIN_THREAD ||
          sweeping_mode == SWEEP_ONLY);
 
   Address free_start = p->area_start();
   DCHECK(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
@@ skipping 62 matching lines @@
     }
 #endif
   }
   p->ResetLiveBytes();
 
   if (parallelism == MarkCompactCollector::SWEEP_IN_PARALLEL) {
     // When concurrent sweeping is active, the page will be marked after
     // sweeping by the main thread.
     p->set_parallel_sweeping(MemoryChunk::SWEEPING_FINALIZE);
   } else {
-    p->MarkSweptPrecisely();
+    p->SetWasSwept();
   }
   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 216 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<SWEEP_ON_MAIN_THREAD>(space, NULL, p);
+            SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, SWEEP_ON_MAIN_THREAD,
+                           IGNORE_SKIP_LIST, IGNORE_FREE_SPACE>(
+                space, NULL, p, &updating_visitor);
             break;
           case OLD_POINTER_SPACE:
             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS, SWEEP_ON_MAIN_THREAD,
                            IGNORE_SKIP_LIST, IGNORE_FREE_SPACE>(
                 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>(
@@ skipping 477 matching lines @@
       for (int i = 0; i < objects_in_these_8_words; i++) {
         starts[objects++] = offset + table[1 + i];
       }
     }
     offset += 8;
   }
   return objects;
 }
 
 
-static inline Address DigestFreeStart(Address approximate_free_start,
-                                      uint32_t free_start_cell) {
-  DCHECK(free_start_cell != 0);
-
-  // No consecutive 1 bits.
-  DCHECK((free_start_cell & (free_start_cell << 1)) == 0);
-
-  int offsets[16];
-  uint32_t cell = free_start_cell;
-  int offset_of_last_live;
-  if ((cell & 0x80000000u) != 0) {
-    // This case would overflow below.
-    offset_of_last_live = 31;
-  } else {
-    // Remove all but one bit, the most significant.  This is an optimization
-    // that may or may not be worthwhile.
-    cell |= cell >> 16;
-    cell |= cell >> 8;
-    cell |= cell >> 4;
-    cell |= cell >> 2;
-    cell |= cell >> 1;
-    cell = (cell + 1) >> 1;
-    int live_objects = MarkWordToObjectStarts(cell, offsets);
-    DCHECK(live_objects == 1);
-    offset_of_last_live = offsets[live_objects - 1];
-  }
-  Address last_live_start =
-      approximate_free_start + offset_of_last_live * kPointerSize;
-  HeapObject* last_live = HeapObject::FromAddress(last_live_start);
-  Address free_start = last_live_start + last_live->Size();
-  return free_start;
-}
-
-
-static inline Address StartOfLiveObject(Address block_address, uint32_t cell) {
-  DCHECK(cell != 0);
-
-  // No consecutive 1 bits.
-  DCHECK((cell & (cell << 1)) == 0);
-
-  int offsets[16];
-  if (cell == 0x80000000u) {  // Avoid overflow below.
-    return block_address + 31 * kPointerSize;
-  }
-  uint32_t first_set_bit = ((cell ^ (cell - 1)) + 1) >> 1;
-  DCHECK((first_set_bit & cell) == first_set_bit);
-  int live_objects = MarkWordToObjectStarts(first_set_bit, offsets);
-  DCHECK(live_objects == 1);
-  USE(live_objects);
-  return block_address + offsets[0] * kPointerSize;
-}
-
-
-// Force instantiation of templatized SweepConservatively method for
-// SWEEP_ON_MAIN_THREAD mode.
-template int MarkCompactCollector::SweepConservatively<
-    MarkCompactCollector::SWEEP_ON_MAIN_THREAD>(PagedSpace*, FreeList*, Page*);
-
-
-// Force instantiation of templatized SweepConservatively method for
-// SWEEP_IN_PARALLEL mode.
-template int 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>
-int MarkCompactCollector::SweepConservatively(PagedSpace* space,
-                                              FreeList* free_list, Page* p) {
-  DCHECK(!p->IsEvacuationCandidate() && !p->WasSwept());
-  DCHECK(
-      (mode == MarkCompactCollector::SWEEP_IN_PARALLEL && free_list != NULL) ||
-      (mode == MarkCompactCollector::SWEEP_ON_MAIN_THREAD &&
-       free_list == NULL));
-
-  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;
-  MarkBit::CellType* cell = NULL;
-  MarkBitCellIterator it(p);
-  for (; !it.Done(); it.Advance()) {
-    cell_base = it.CurrentCellBase();
-    cell = it.CurrentCell();
-    if (*cell != 0) break;
-  }
-
-  if (it.Done()) {
-    size = p->area_end() - p->area_start();
-    freed_bytes =
-        Free<mode>(space, free_list, p->area_start(), static_cast<int>(size));
-    max_freed_bytes = Max(freed_bytes, max_freed_bytes);
-    DCHECK_EQ(0, p->LiveBytes());
-    if (mode == MarkCompactCollector::SWEEP_IN_PARALLEL) {
-      // When concurrent sweeping is active, the page will be marked after
-      // sweeping by the main thread.
-      p->set_parallel_sweeping(MemoryChunk::SWEEPING_FINALIZE);
-    } else {
-      p->MarkSweptConservatively();
-    }
-    return FreeList::GuaranteedAllocatable(static_cast<int>(max_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(cell_base, *cell);
-  // Free the first free space.
-  size = free_end - p->area_start();
-  freed_bytes =
-      Free<mode>(space, free_list, p->area_start(), static_cast<int>(size));
-  max_freed_bytes = Max(freed_bytes, max_freed_bytes);
-
-  // 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 = cell_base;
-  MarkBit::CellType free_start_cell = *cell;
-
-  for (; !it.Done(); it.Advance()) {
-    cell_base = it.CurrentCellBase();
-    cell = it.CurrentCell();
-    if (*cell != 0) {
-      // We have a live object.  Check approximately whether it is more than 32
-      // words since the last live object.
-      if (cell_base - free_start > 32 * kPointerSize) {
-        free_start = DigestFreeStart(free_start, free_start_cell);
-        if (cell_base - 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(cell_base, *cell);
-          freed_bytes = Free<mode>(space, free_list, free_start,
-                                   static_cast<int>(free_end - free_start));
-          max_freed_bytes = Max(freed_bytes, max_freed_bytes);
-        }
-      }
-      // Update our undigested record of where the current free area started.
-      free_start = cell_base;
-      free_start_cell = *cell;
-      // Clear marking bits for current cell.
-      *cell = 0;
-    }
-  }
-
-  // Handle the free space at the end of the page.
-  if (cell_base - free_start > 32 * kPointerSize) {
-    free_start = DigestFreeStart(free_start, free_start_cell);
-    freed_bytes = Free<mode>(space, free_list, free_start,
-                             static_cast<int>(p->area_end() - free_start));
-    max_freed_bytes = Max(freed_bytes, max_freed_bytes);
-  }
-
-  p->ResetLiveBytes();
-  if (mode == MarkCompactCollector::SWEEP_IN_PARALLEL) {
-    // When concurrent sweeping is active, the page will be marked after
-    // sweeping by the main thread.
-    p->set_parallel_sweeping(MemoryChunk::SWEEPING_FINALIZE);
-  } else {
-    p->MarkSweptConservatively();
-  }
-  return FreeList::GuaranteedAllocatable(static_cast<int>(max_freed_bytes));
-}
-
-
 int MarkCompactCollector::SweepInParallel(PagedSpace* space,
                                           int required_freed_bytes) {
   int max_freed = 0;
   int max_freed_overall = 0;
   PageIterator it(space);
   while (it.has_next()) {
     Page* p = it.next();
     max_freed = SweepInParallel(p, space);
     DCHECK(max_freed >= 0);
     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;
 }
 
 
 int MarkCompactCollector::SweepInParallel(Page* page, PagedSpace* space) {
   int max_freed = 0;
   if (page->TryParallelSweeping()) {
     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);
-    if (space->swept_precisely()) {
-      max_freed = SweepPrecisely<SWEEP_ONLY, SWEEP_IN_PARALLEL,
-                                 IGNORE_SKIP_LIST, IGNORE_FREE_SPACE>(
-          space, &private_free_list, page, NULL);
-    } else {
-      max_freed = SweepConservatively<SWEEP_IN_PARALLEL>(
-          space, &private_free_list, page);
-    }
+    max_freed = SweepPrecisely<SWEEP_ONLY, SWEEP_IN_PARALLEL, IGNORE_SKIP_LIST,
+                               IGNORE_FREE_SPACE>(space, &private_free_list,
+                                                  page, NULL);
     free_list->Concatenate(&private_free_list);
   }
   return max_freed;
 }
 
 
 void MarkCompactCollector::SweepSpace(PagedSpace* space, SweeperType sweeper) {
-  space->set_swept_precisely(sweeper == PRECISE ||
-                             sweeper == CONCURRENT_PRECISE ||
-                             sweeper == PARALLEL_PRECISE);
   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();
     DCHECK(p->parallel_sweeping() == MemoryChunk::SWEEPING_DONE);
 
     // Clear sweeping flags indicating that marking bits are still intact.
-    p->ClearSweptPrecisely();
-    p->ClearSweptConservatively();
+    p->ClearWasSwept();
 
     if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION) ||
         p->IsEvacuationCandidate()) {
       // Will be processed in EvacuateNewSpaceAndCandidates.
       DCHECK(evacuation_candidates_.length() > 0);
       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;
     }
 
     switch (sweeper) {
-      case CONCURRENT_CONSERVATIVE:
-      case PARALLEL_CONSERVATIVE: {
-        if (!parallel_sweeping_active) {
-          if (FLAG_gc_verbose) {
-            PrintF("Sweeping 0x%" V8PRIxPTR " conservatively.\n",
-                   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::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",
+            PrintF("Sweeping 0x%" V8PRIxPTR " precisely 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",
@@ skipping 20 matching lines @@
     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 ||
+  return type == MarkCompactCollector::PARALLEL_PRECISE ||
          type == MarkCompactCollector::CONCURRENT_PRECISE;
 }
 
 
 static bool ShouldWaitForSweeperThreads(
     MarkCompactCollector::SweeperType type) {
-  return type == MarkCompactCollector::PARALLEL_CONSERVATIVE ||
-         type == MarkCompactCollector::PARALLEL_PRECISE;
+  return type == MarkCompactCollector::PARALLEL_PRECISE;
 }
 
 
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(heap()->tracer(), GCTracer::Scope::MC_SWEEP);
   double start_time = 0.0;
   if (FLAG_print_cumulative_gc_stat) {
     start_time = base::OS::TimeCurrentMillis();
   }
 
 #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;
-  }
+  SweeperType how_to_sweep = CONCURRENT_PRECISE;
+  if (FLAG_parallel_sweeping) how_to_sweep = PARALLEL_PRECISE;
+  if (FLAG_concurrent_sweeping) how_to_sweep = CONCURRENT_PRECISE;
   if (sweep_precisely_) how_to_sweep = PRECISE;
 
   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.
   {
@@ skipping 51 matching lines @@
   }
 }
 
 
 void MarkCompactCollector::ParallelSweepSpaceComplete(PagedSpace* space) {
   PageIterator it(space);
   while (it.has_next()) {
     Page* p = it.next();
     if (p->parallel_sweeping() == MemoryChunk::SWEEPING_FINALIZE) {
       p->set_parallel_sweeping(MemoryChunk::SWEEPING_DONE);
-      if (space->swept_precisely()) {
-        p->MarkSweptPrecisely();
-      } else {
-        p->MarkSweptConservatively();
-      }
+      p->SetWasSwept();
     }
     DCHECK(p->parallel_sweeping() == MemoryChunk::SWEEPING_DONE);
   }
 }
 
 
 void MarkCompactCollector::ParallelSweepSpacesComplete() {
   ParallelSweepSpaceComplete(heap()->old_pointer_space());
   ParallelSweepSpaceComplete(heap()->old_data_space());
 }
@@ skipping 199 matching lines @@
   SlotsBuffer* buffer = *buffer_address;
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 }
 }  // namespace v8::internal