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 432 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 1460 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(
+                                               this, this->free_list(), 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 13 matching lines @@
     heap()->CreateFillerObjectAt(allocation_info_.top, remaining);
 
     allocation_info_.top = NULL;
     allocation_info_.limit = NULL;
   }
 }
 
 
 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);
-
-    // Retry the free list allocation.
+  if (heap()->IsConcurrentSweepingActivated()) {

[Michael Starzinger, 2013/01/24 17:15:54]

The SlowAllocateRaw() function is getting too complicated. Would it be possible
to move all the sweeper-related code into a separate EnsureSweeperProgress()
function and basically keep the original implementation of SlowAllocateRaw()
almost untouched?

[Hannes Payer (out of office), 2013/01/25 10:46:49]

Done.

+    heap()->StealMemoryFromSweeperThreads(this);
     HeapObject* object = free_list_.Allocate(size_in_bytes);
     if (object != NULL) return object;
+
+    if (heap()->IsConcurrentSweepingPending()) {
+      heap()->WaitUntilParallelSweepingCompleted();
+    }
+
+    heap()->StealMemoryFromSweeperThreads(this);
+
+    object = free_list_.Allocate(size_in_bytes);
+    if (object != NULL) return object;
+  } else {
+    // 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);
+
+      // Retry the free list allocation.
+      HeapObject* object = free_list_.Allocate(size_in_bytes);
+      if (object != NULL) return object;
+    }
+
+    // Last ditch, sweep all the remaining pages to try to find space.  This may
+    // cause a pause.
+    if (!IsSweepingComplete()) {
+      AdvanceSweeper(kMaxInt);
+
+      // 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);
-
-    // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
-    if (object != NULL) return object;
-  }
-
   // Finally, fail.
   return NULL;
 }
 
 
 #ifdef DEBUG
 void PagedSpace::ReportCodeStatistics() {
   Isolate* isolate = Isolate::Current();
   CommentStatistic* comments_statistics =
       isolate->paged_space_comments_statistics();
@@ skipping 510 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal