Reland "[heap] Introduce parallel compaction algorithm."

src/heap/spaces.cc

 // Copyright 2011 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/spaces.h"
 
 #include "src/base/bits.h"
 #include "src/base/platform/platform.h"
 #include "src/full-codegen/full-codegen.h"
 #include "src/heap/slots-buffer.h"
@@ skipping 62 matching lines @@
 
 // -----------------------------------------------------------------------------
 // CodeRange
 
 
 CodeRange::CodeRange(Isolate* isolate)
     : isolate_(isolate),
       code_range_(NULL),
       free_list_(0),
       allocation_list_(0),
-      current_allocation_block_index_(0),
-      emergency_block_() {}
+      current_allocation_block_index_(0) {}
 
 
 bool CodeRange::SetUp(size_t requested) {
   DCHECK(code_range_ == NULL);
 
   if (requested == 0) {
     // When a target requires the code range feature, we put all code objects
     // in a kMaximalCodeRangeSize range of virtual address space, so that
     // they can call each other with near calls.
     if (kRequiresCodeRange) {
@@ skipping 38 matching lines @@
     }
     base += kReservedCodeRangePages * base::OS::CommitPageSize();
   }
   Address aligned_base = RoundUp(base, MemoryChunk::kAlignment);
   size_t size = code_range_->size() - (aligned_base - base) -
                 kReservedCodeRangePages * base::OS::CommitPageSize();
   allocation_list_.Add(FreeBlock(aligned_base, size));
   current_allocation_block_index_ = 0;
 
   LOG(isolate_, NewEvent("CodeRange", code_range_->address(), requested));
-  ReserveEmergencyBlock();
   return true;
 }
 
 
 int CodeRange::CompareFreeBlockAddress(const FreeBlock* left,
                                        const FreeBlock* right) {
   // The entire point of CodeRange is that the difference between two
   // addresses in the range can be represented as a signed 32-bit int,
   // so the cast is semantically correct.
   return static_cast<int>(left->start - right->start);
@@ skipping 115 matching lines @@
   return true;
 }
 
 
 void CodeRange::ReleaseBlock(const FreeBlock* block) {
   base::LockGuard<base::Mutex> guard(&code_range_mutex_);
   free_list_.Add(*block);
 }
 
 
-void CodeRange::ReserveEmergencyBlock() {
-  const size_t requested_size = MemoryAllocator::CodePageAreaSize();
-  if (emergency_block_.size == 0) {
-    ReserveBlock(requested_size, &emergency_block_);
-  } else {
-    DCHECK(emergency_block_.size >= requested_size);
-  }
-}
-
-
-void CodeRange::ReleaseEmergencyBlock() {
-  if (emergency_block_.size != 0) {
-    ReleaseBlock(&emergency_block_);
-    emergency_block_.size = 0;
-  }
-}
-
-
 // -----------------------------------------------------------------------------
 // MemoryAllocator
 //
 
 MemoryAllocator::MemoryAllocator(Isolate* isolate)
     : isolate_(isolate),
       capacity_(0),
       capacity_executable_(0),
       size_(0),
       size_executable_(0),
@@ skipping 178 matching lines @@
   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_.SetValue(static_cast<intptr_t>(area_start - base));
   chunk->set_parallel_sweeping(SWEEPING_DONE);
+  chunk->parallel_compaction_state().SetValue(kCompactingDone);
   chunk->mutex_ = NULL;
   chunk->available_in_small_free_list_ = 0;
   chunk->available_in_medium_free_list_ = 0;
   chunk->available_in_large_free_list_ = 0;
   chunk->available_in_huge_free_list_ = 0;
   chunk->non_available_small_blocks_ = 0;
   chunk->ResetLiveBytes();
   Bitmap::Clear(chunk);
   chunk->initialize_scan_on_scavenge(false);
   chunk->SetFlag(WAS_SWEPT);
@@ skipping 462 matching lines @@
               ObjectSpace::kObjectSpaceCodeSpace);
 STATIC_ASSERT(static_cast<ObjectSpace>(1 << AllocationSpace::MAP_SPACE) ==
               ObjectSpace::kObjectSpaceMapSpace);
 
 
 PagedSpace::PagedSpace(Heap* heap, AllocationSpace space,
                        Executability executable)
     : Space(heap, space, executable),
       free_list_(this),
       unswept_free_bytes_(0),
-      end_of_unswept_pages_(NULL),
-      emergency_memory_(NULL) {
+      end_of_unswept_pages_(NULL) {
   area_size_ = MemoryAllocator::PageAreaSize(space);
   accounting_stats_.Clear();
 
   allocation_info_.set_top(NULL);
   allocation_info_.set_limit(NULL);
 
   anchor_.InitializeAsAnchor(this);
 }
 
 
 bool PagedSpace::SetUp() { return true; }
 
 
 bool PagedSpace::HasBeenSetUp() { return true; }
 
 
 void PagedSpace::TearDown() {
   PageIterator iterator(this);
   while (iterator.has_next()) {
     heap()->isolate()->memory_allocator()->Free(iterator.next());
   }
   anchor_.set_next_page(&anchor_);
   anchor_.set_prev_page(&anchor_);
   accounting_stats_.Clear();
 }
 
 
+void PagedSpace::MoveOverFreeMemory(PagedSpace* other, bool other_is_local) {

[Hannes Payer (out of office), 2015/09/17 09:09:46]

As discussed offline: let's solve this using a three state enum (for different
kinds of local spaces) or based on the space type.

[Michael Lippautz, 2015/09/17 09:27:15]

Type-based lock it is.

+  DCHECK(identity() == other->identity());
+  // Destroy the linear allocation space of {other}. This is needed to
+  //   (a) not waste the memory and
+  //   (b) keep the rest of the chunk in an iterable state (filler is needed).
+  other->EmptyAllocationInfo();
+
+  // Move over the free list. Concatenate makes sure that the source free list
+  // gets properly reset after moving over all nodes.
+  intptr_t freed_bytes =
+      free_list_.Concatenate(other->free_list(), other_is_local);
+  other->accounting_stats_.AllocateBytes(freed_bytes);
+  // We do not adjust accounting_stats_ for {this} as we treat the received
+  // memory as borrowed, i.e., the originating space keeps track of its
+  // capacity. Other stats, e.g. accounting_stats_.{size_,waste_} are properly
+  // maintained by allocating and freeing blocks.
+}
+
+
 void PagedSpace::MergeCompactionSpace(CompactionSpace* other) {
   // Unmerged fields:
   //   area_size_
   //   allocation_info_
-  //   emergency_memory_
   //   end_of_unswept_pages_
   //   unswept_free_bytes_
   //   anchor_
 
-  // It only makes sense to merge compatible spaces.
-  DCHECK(identity() == other->identity());
-
-  // Destroy the linear allocation space of {other}. This is needed to (a) not
-  // waste the memory and (b) keep the rest of the chunk in an iterable state
-  // (filler is needed).
-  int linear_size = static_cast<int>(other->limit() - other->top());
-  other->Free(other->top(), linear_size);
-
-  // Move over the free list.
-  free_list_.Concatenate(other->free_list());
+  // CompactionSpace is per definition a local space without concurrent access.
+  // Use this information to break the potential lock cycle in
+  // FreeList::Concatenate.
+  MoveOverFreeMemory(other, true);
 
   // Update and clear accounting statistics.
   accounting_stats_.Merge(other->accounting_stats_);
-  other->accounting_stats_.Clear();
+  other->accounting_stats_.Reset();
 
   // Move over pages.
   PageIterator it(other);
   Page* p = nullptr;
   while (it.has_next()) {
     p = it.next();
     p->Unlink();
     p->set_owner(this);
     p->InsertAfter(anchor_.prev_page());
   }
@@ skipping 63 matching lines @@
   if (!CanExpand(size)) return false;
 
   Page* p = heap()->isolate()->memory_allocator()->AllocatePage(size, this,
                                                                 executable());
   if (p == NULL) return false;
 
   // Pages created during bootstrapping may contain immortal immovable objects.
   if (!heap()->deserialization_complete()) p->MarkNeverEvacuate();
 
   DCHECK(Capacity() <= heap()->MaxOldGenerationSize());
-  DCHECK(heap()->CommittedOldGenerationMemory() <=
-         heap()->MaxOldGenerationSize() +
-             PagedSpace::MaxEmergencyMemoryAllocated());
 
   p->InsertAfter(anchor_.prev_page());
 
   return true;
 }
 
 
 int PagedSpace::CountTotalPages() {
   PageIterator it(this);
   int count = 0;
@@ skipping 49 matching lines @@
     page->Unlink();
   }
 
   heap()->QueueMemoryChunkForFree(page);
 
   DCHECK(Capacity() > 0);
   accounting_stats_.ShrinkSpace(AreaSize());
 }
 
 
-intptr_t PagedSpace::MaxEmergencyMemoryAllocated() {
-  // New space and large object space.
-  static const int spaces_without_emergency_memory = 2;
-  static const int spaces_with_emergency_memory =
-      LAST_SPACE - FIRST_SPACE + 1 - spaces_without_emergency_memory;
-  return Page::kPageSize * spaces_with_emergency_memory;
-}
-
-
-void PagedSpace::CreateEmergencyMemory() {
-  if (identity() == CODE_SPACE) {
-    // Make the emergency block available to the allocator.
-    CodeRange* code_range = heap()->isolate()->code_range();
-    if (code_range != NULL && code_range->valid()) {
-      code_range->ReleaseEmergencyBlock();
-    }
-    DCHECK(MemoryAllocator::CodePageAreaSize() == AreaSize());
-  }
-  emergency_memory_ = heap()->isolate()->memory_allocator()->AllocateChunk(
-      AreaSize(), AreaSize(), executable(), this);
-}
-
-
-void PagedSpace::FreeEmergencyMemory() {
-  Page* page = static_cast<Page*>(emergency_memory_);
-  DCHECK(page->LiveBytes() == 0);
-  DCHECK(AreaSize() == page->area_size());
-  DCHECK(!free_list_.ContainsPageFreeListItems(page));
-  heap()->isolate()->memory_allocator()->Free(page);
-  emergency_memory_ = NULL;
-}
-
-
-void PagedSpace::UseEmergencyMemory() {
-  // Page::Initialize makes the chunk into a real page and adds it to the
-  // accounting for this space.  Unlike PagedSpace::Expand, we don't check
-  // CanExpand first, so we can go over the limits a little here.  That's OK,
-  // because we are in the process of compacting which will free up at least as
-  // much memory as it allocates.
-  Page* page = Page::Initialize(heap(), emergency_memory_, executable(), this);
-  page->InsertAfter(anchor_.prev_page());
-  emergency_memory_ = NULL;
-}
-
-
 #ifdef DEBUG
 void PagedSpace::Print() {}
 #endif
 
 #ifdef VERIFY_HEAP
 void PagedSpace::Verify(ObjectVisitor* visitor) {
   bool allocation_pointer_found_in_space =
       (allocation_info_.top() == allocation_info_.limit());
   PageIterator page_iterator(this);
   while (page_iterator.has_next()) {
@@ skipping 881 matching lines @@
   if (from_space_.is_committed()) {
     size += from_space_.CommittedPhysicalMemory();
   }
   return size;
 }
 
 
 // -----------------------------------------------------------------------------
 // Free lists for old object spaces implementation
 
-intptr_t FreeListCategory::Concatenate(FreeListCategory* category) {
+intptr_t FreeListCategory::Concatenate(FreeListCategory* category,
+                                       bool category_is_local) {
   intptr_t free_bytes = 0;
   if (category->top() != 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.
     base::LockGuard<base::Mutex> target_lock_guard(mutex());
-    base::LockGuard<base::Mutex> source_lock_guard(category->mutex());
+    if (!category_is_local) category->mutex()->Lock();
     DCHECK(category->end_ != NULL);
     free_bytes = category->available();
     if (end_ == NULL) {
       end_ = category->end();
     } else {
       category->end()->set_next(top());
     }
     set_top(category->top());
     base::NoBarrier_Store(&top_, category->top_);
     available_ += category->available();
     category->Reset();
+    if (!category_is_local) category->mutex()->Unlock();
   }
   return free_bytes;
 }
 
 
 void FreeListCategory::Reset() {
   set_top(NULL);
   set_end(NULL);
   set_available(0);
 }
@@ skipping 92 matching lines @@
     n = n->next();
   }
 }
 
 
 FreeList::FreeList(PagedSpace* owner) : owner_(owner), heap_(owner->heap()) {
   Reset();
 }
 
 
-intptr_t FreeList::Concatenate(FreeList* free_list) {
+intptr_t FreeList::Concatenate(FreeList* free_list, bool free_list_is_local) {
   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());
+  free_bytes +=
+      small_list_.Concatenate(free_list->small_list(), free_list_is_local);
+  free_bytes +=
+      medium_list_.Concatenate(free_list->medium_list(), free_list_is_local);
+  free_bytes +=
+      large_list_.Concatenate(free_list->large_list(), free_list_is_local);
+  free_bytes +=
+      huge_list_.Concatenate(free_list->huge_list(), free_list_is_local);
   return free_bytes;
 }
 
 
 void FreeList::Reset() {
   small_list_.Reset();
   medium_list_.Reset();
   large_list_.Reset();
   huge_list_.Reset();
 }
@@ skipping 917 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8