[heap] Sort sweep pages list by free memory.

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/heap/mark-compact.h"
 
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/sys-info.h"
 #include "src/code-stubs.h"
@@ skipping 3285 matching lines @@
            MemoryChunk::kSweepingDone);
     if (p->parallel_compaction_state().TrySetValue(
             MemoryChunk::kCompactingDone, MemoryChunk::kCompactingInProgress)) {
       if (p->IsEvacuationCandidate()) {
         DCHECK_EQ(p->parallel_compaction_state().Value(),
                   MemoryChunk::kCompactingInProgress);
         double start = heap()->MonotonicallyIncreasingTimeInMs();
         intptr_t live_bytes = p->LiveBytes();
         AlwaysAllocateScope always_allocate(isolate());
         if (VisitLiveObjects(p, &visitor, kClearMarkbits)) {
-          p->ResetLiveBytes();
           p->parallel_compaction_state().SetValue(
               MemoryChunk::kCompactingFinalize);
           compaction_spaces->ReportCompactionProgress(
               heap()->MonotonicallyIncreasingTimeInMs() - start, live_bytes);
         } else {
           p->parallel_compaction_state().SetValue(
               MemoryChunk::kCompactingAborted);
         }
       } else {
         // There could be popular pages in the list of evacuation candidates
@@ skipping 436 matching lines @@
     // Update pointers from external string table.
     heap_->UpdateReferencesInExternalStringTable(
         &UpdateReferenceInExternalStringTableEntry);
 
     EvacuationWeakObjectRetainer evacuation_object_retainer;
     heap()->ProcessAllWeakReferences(&evacuation_object_retainer);
   }
 }
 
 
-void MarkCompactCollector::MoveEvacuationCandidatesToEndOfPagesList() {
-  int npages = evacuation_candidates_.length();
-  for (int i = 0; i < npages; i++) {
-    Page* p = evacuation_candidates_[i];
-    if (!p->IsEvacuationCandidate()) continue;
-    p->Unlink();
-    PagedSpace* space = static_cast<PagedSpace*>(p->owner());
-    p->InsertAfter(space->LastPage());
-  }
-}
-
-
 void MarkCompactCollector::ReleaseEvacuationCandidates() {
   int npages = evacuation_candidates_.length();
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     if (!p->IsEvacuationCandidate()) continue;
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
     space->Free(p->area_start(), p->area_size());
     p->set_scan_on_scavenge(false);
     p->ResetLiveBytes();
     CHECK(p->WasSwept());
     space->ReleasePage(p);
   }
   evacuation_candidates_.Rewind(0);
   compacting_ = false;
   heap()->FilterStoreBufferEntriesOnAboutToBeFreedPages();
   heap()->FreeQueuedChunks();
 }
 
 
 int MarkCompactCollector::SweepInParallel(PagedSpace* space,
-                                          int required_freed_bytes) {
+                                          int required_freed_bytes,
+                                          int max_pages) {
   int max_freed = 0;
   int max_freed_overall = 0;
-  PageIterator it(space);
-  while (it.has_next()) {
-    Page* p = it.next();
+  int page_count = 0;
+  for (Page* p : sweeping_list(space)) {
     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;
+    page_count++;
+    if (max_pages > 0 && page_count >= max_pages) {
+      break;
+    }
   }
   return max_freed_overall;
 }
 
 
 int MarkCompactCollector::SweepInParallel(Page* page, PagedSpace* space) {
   int max_freed = 0;
   if (page->TryLock()) {
     // If this page was already swept in the meantime, we can return here.
     if (page->parallel_sweeping_state().Value() !=
@@ skipping 23 matching lines @@
     free_list->Concatenate(&private_free_list);
     page->mutex()->Unlock();
   }
   return max_freed;
 }
 
 
 void MarkCompactCollector::StartSweepSpace(PagedSpace* space) {
   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;
+  int will_be_swept = 0;
   bool unused_page_present = false;
-  bool parallel_sweeping_active = false;
 
   while (it.has_next()) {
     Page* p = it.next();
     DCHECK(p->parallel_sweeping_state().Value() == MemoryChunk::kSweepingDone);
 
     // Clear sweeping flags indicating that marking bits are still intact.
     p->ClearWasSwept();
 
     if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION) ||
         p->IsEvacuationCandidate()) {
@@ skipping 17 matching lines @@
       if (unused_page_present) {
         if (FLAG_gc_verbose) {
           PrintIsolate(isolate(), "sweeping: released page: %p", p);
         }
         space->ReleasePage(p);
         continue;
       }
       unused_page_present = true;
     }
 
-    if (!parallel_sweeping_active) {
-      if (FLAG_gc_verbose) {
-        PrintIsolate(isolate(), "sweeping: %p", p);
-      }
-      if (space->identity() == CODE_SPACE) {
-        if (FLAG_zap_code_space) {
-          Sweep<SWEEP_ONLY, SWEEP_ON_MAIN_THREAD, REBUILD_SKIP_LIST,
-                ZAP_FREE_SPACE>(space, NULL, p, NULL);
-        } else {
-          Sweep<SWEEP_ONLY, SWEEP_ON_MAIN_THREAD, REBUILD_SKIP_LIST,
-                IGNORE_FREE_SPACE>(space, NULL, p, NULL);
-        }
-      } else {
-        Sweep<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) {
-        PrintIsolate(isolate(), "sweeping: initialized for parallel: %p", p);
-      }
-      p->parallel_sweeping_state().SetValue(MemoryChunk::kSweepingPending);
-      int to_sweep = p->area_size() - p->LiveBytes();
-      space->accounting_stats_.ShrinkSpace(to_sweep);
-    }
-    space->set_end_of_unswept_pages(p);
+    sweeping_list(space).push_back(p);
+    p->parallel_sweeping_state().SetValue(MemoryChunk::kSweepingPending);
+    int to_sweep = p->area_size() - p->LiveBytes();
+    space->accounting_stats_.ShrinkSpace(to_sweep);
+    will_be_swept++;
   }
 
   if (FLAG_gc_verbose) {
-    PrintIsolate(isolate(), "sweeping: space=%s pages_swept=%d",
-                 AllocationSpaceName(space->identity()), pages_swept);
+    PrintIsolate(isolate(), "sweeping: space=%s initialized_for_sweeping=%d",
+                 AllocationSpaceName(space->identity()), will_be_swept);
   }
+  std::sort(sweeping_list(space).begin(), sweeping_list(space).end(),
+            [](Page* a, Page* b) { return a->LiveBytes() < b->LiveBytes(); });
 }
 
 
 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 = heap_->MonotonicallyIncreasingTimeInMs();
   }
 
 #ifdef DEBUG
   state_ = SWEEP_SPACES;
 #endif
 
-  MoveEvacuationCandidatesToEndOfPagesList();
-
   {
     sweeping_in_progress_ = true;
     {
       GCTracer::Scope sweep_scope(heap()->tracer(),
                                   GCTracer::Scope::MC_SWEEP_OLD);
       StartSweepSpace(heap()->old_space());
     }
     {
       GCTracer::Scope sweep_scope(heap()->tracer(),
                                   GCTracer::Scope::MC_SWEEP_CODE);
@@ skipping 17 matching lines @@
   heap()->FreeQueuedChunks();
 
   if (FLAG_print_cumulative_gc_stat) {
     heap_->tracer()->AddSweepingTime(heap_->MonotonicallyIncreasingTimeInMs() -
                                      start_time);
   }
 }
 
 
 void MarkCompactCollector::ParallelSweepSpaceComplete(PagedSpace* space) {
-  PageIterator it(space);
-  while (it.has_next()) {
-    Page* p = it.next();
+  for (Page* p : sweeping_list(space)) {
     if (p->parallel_sweeping_state().Value() ==
         MemoryChunk::kSweepingFinalize) {
       p->parallel_sweeping_state().SetValue(MemoryChunk::kSweepingDone);
       p->SetWasSwept();
     }
     DCHECK(p->parallel_sweeping_state().Value() == MemoryChunk::kSweepingDone);
   }
 }
 
 
 void MarkCompactCollector::ParallelSweepSpacesComplete() {
   ParallelSweepSpaceComplete(heap()->old_space());
   ParallelSweepSpaceComplete(heap()->code_space());
   ParallelSweepSpaceComplete(heap()->map_space());
+  sweeping_list(heap()->old_space()).clear();
+  sweeping_list(heap()->code_space()).clear();
+  sweeping_list(heap()->map_space()).clear();
 }
 
 
 // TODO(1466) ReportDeleteIfNeeded is not called currently.
 // Our profiling tools do not expect intersections between
 // code objects. We should either reenable it or change our tools.
 void MarkCompactCollector::ReportDeleteIfNeeded(HeapObject* obj,
                                                 Isolate* isolate) {
   if (obj->IsCode()) {
     PROFILE(isolate, CodeDeleteEvent(obj->address()));
@@ skipping 57 matching lines @@
     MarkBit mark_bit = Marking::MarkBitFrom(host);
     if (Marking::IsBlack(mark_bit)) {
       RelocInfo rinfo(isolate(), pc, RelocInfo::CODE_TARGET, 0, host);
       RecordRelocSlot(&rinfo, target);
     }
   }
 }
 
 }  // namespace internal
 }  // namespace v8