Parallel and concurrent sweeping.

src/spaces.cc

 // Copyright 2011 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 448 matching lines @@
   chunk->area_start_ = area_start;
   chunk->area_end_ = area_end;
   chunk->flags_ = 0;
   chunk->set_owner(owner);
   chunk->InitializeReservedMemory();
   chunk->slots_buffer_ = NULL;
   chunk->skip_list_ = NULL;
   chunk->write_barrier_counter_ = kWriteBarrierCounterGranularity;
   chunk->progress_bar_ = 0;
   chunk->high_water_mark_ = static_cast<int>(area_start - base);
+  chunk->parallel_sweeping_ = 0;
   chunk->ResetLiveBytes();
   Bitmap::Clear(chunk);
   chunk->initialize_scan_on_scavenge(false);
   chunk->SetFlag(WAS_SWEPT_PRECISELY);
 
   ASSERT(OFFSET_OF(MemoryChunk, flags_) == kFlagsOffset);
   ASSERT(OFFSET_OF(MemoryChunk, live_byte_count_) == kLiveBytesOffset);
 
   if (executable == EXECUTABLE) {
     chunk->SetFlag(IS_EXECUTABLE);
@@ skipping 1555 matching lines @@
     ASSERT(map() == NULL || Size() >= kNextOffset + kPointerSize);
     Memory::Address_at(address() + kNextOffset) =
         reinterpret_cast<Address>(next);
   } else {
     Memory::Address_at(address() + kPointerSize) =
         reinterpret_cast<Address>(next);
   }
 }
 
 
+intptr_t FreeListCategory::Concatenate(FreeListCategory* category) {
+  intptr_t free_bytes = 0;
+  if (category->top_ != NULL) {
+    ASSERT(category->end_ != NULL);
+    // This is safe (not going to deadlock) since Concatenate operations
+    // are never performed on the same free lists at the same time in
+    // reverse order.
+    ScopedLock lock_target(mutex_);
+    ScopedLock lock_source(category->mutex());
+    free_bytes = category->available();
+    if (end_ == NULL) {
+      end_ = category->end();
+    } else {
+      category->end()->set_next(top_);
+    }
+    top_ = category->top();
+    available_ += category->available();
+    category->Reset();
+  }
+  return free_bytes;
+}
+
+
 void FreeListCategory::Reset() {
   top_ = NULL;
   end_ = NULL;
   available_ = 0;
 }
 
 
 intptr_t FreeListCategory::CountFreeListItemsInList(Page* p) {
   int sum = 0;
   FreeListNode* n = top_;
@@ skipping 78 matching lines @@
   }
 }
 
 
 FreeList::FreeList(PagedSpace* owner)
     : owner_(owner), heap_(owner->heap()) {
   Reset();
 }
 
 
+intptr_t FreeList::Concatenate(FreeList* free_list) {
+  intptr_t free_bytes = 0;
+  free_bytes += small_list_.Concatenate(free_list->small_list());
+  free_bytes += medium_list_.Concatenate(free_list->medium_list());
+  free_bytes += large_list_.Concatenate(free_list->large_list());
+  free_bytes += huge_list_.Concatenate(free_list->huge_list());
+  return free_bytes;
+}
+
+
 void FreeList::Reset() {
   small_list_.Reset();
   medium_list_.Reset();
   large_list_.Reset();
   huge_list_.Reset();
 }
 
 
 int FreeList::Free(Address start, int size_in_bytes) {
   if (size_in_bytes == 0) return 0;
@@ skipping 344 matching lines @@
   intptr_t freed_bytes = 0;
   Page* p = first_unswept_page_;
   do {
     Page* next_page = p->next_page();
     if (ShouldBeSweptLazily(p)) {
       if (FLAG_gc_verbose) {
         PrintF("Sweeping 0x%" V8PRIxPTR " lazily advanced.\n",
                reinterpret_cast<intptr_t>(p));
       }
       DecreaseUnsweptFreeBytes(p);
-      freed_bytes += MarkCompactCollector::SweepConservatively(this, p);
+      freed_bytes +=
+          MarkCompactCollector::
+              SweepConservatively<MarkCompactCollector::SWEEP_SEQUENTIALLY>(
+                  this, NULL, p);
     }
     p = next_page;
   } while (p != anchor() && freed_bytes < bytes_to_sweep);
 
   if (p == anchor()) {
     first_unswept_page_ = Page::FromAddress(NULL);
   } else {
     first_unswept_page_ = p;
   }
 
@@ skipping 11 matching lines @@
     int remaining =
         static_cast<int>(allocation_info_.limit - allocation_info_.top);
     heap()->CreateFillerObjectAt(allocation_info_.top, remaining);
 
     allocation_info_.top = NULL;
     allocation_info_.limit = NULL;
   }
 }
 
 
+bool PagedSpace::EnsureSweeperProgress(intptr_t size_in_bytes) {
+  MarkCompactCollector* collector = heap()->mark_compact_collector();
+  if (collector->AreSweeperThreadsActivated()) {
+    if (FLAG_concurrent_sweeping &&
+        collector->StealMemoryFromSweeperThreads(this) < size_in_bytes) {
+      collector->WaitUntilSweepingCompleted();
+      return true;
+    }
+    return false;
+  } else {
+    return AdvanceSweeper(size_in_bytes);
+  }
+}
+
+
 HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   // Allocation in this space has failed.
 
   // If there are unswept pages advance lazy sweeper a bounded number of times
   // until we find a size_in_bytes contiguous piece of memory
   const int kMaxSweepingTries = 5;
   bool sweeping_complete = false;
 
   for (int i = 0; i < kMaxSweepingTries && !sweeping_complete; i++) {
-    sweeping_complete = AdvanceSweeper(size_in_bytes);
+    sweeping_complete = EnsureSweeperProgress(size_in_bytes);
 
     // Retry the free list allocation.
     HeapObject* object = free_list_.Allocate(size_in_bytes);
     if (object != NULL) return object;
   }
 
   // Free list allocation failed and there is no next page.  Fail if we have
   // hit the old generation size limit that should cause a garbage
   // collection.
   if (!heap()->always_allocate() &&
       heap()->OldGenerationAllocationLimitReached()) {
     return NULL;
   }
 
   // Try to expand the space and allocate in the new next page.
   if (Expand()) {
     return free_list_.Allocate(size_in_bytes);
   }
 
   // Last ditch, sweep all the remaining pages to try to find space.  This may
   // cause a pause.
   if (!IsSweepingComplete()) {
-    AdvanceSweeper(kMaxInt);
+    EnsureSweeperProgress(kMaxInt);
 
     // Retry the free list allocation.
     HeapObject* object = free_list_.Allocate(size_in_bytes);
     if (object != NULL) return object;
   }
 
   // Finally, fail.
   return NULL;
 }
 
@@ skipping 516 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal