Support slots recording for compaction during incremental marking.

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 1599 matching lines @@
   ASSERT(size_in_bytes > 0);
   ASSERT(IsAligned(size_in_bytes, kPointerSize));
 
   // We write a map and possibly size information to the block.  If the block
   // is big enough to be a FreeSpace with at least one extra word (the next
   // pointer), we set its map to be the free space map and its size to an
   // appropriate array length for the desired size from HeapObject::Size().
   // If the block is too small (eg, one or two words), to hold both a size
   // field and a next pointer, we give it a filler map that gives it the
   // correct size.
-  // TODO(gc) ISOLATES MERGE cleanup HEAP macro usage
   if (size_in_bytes > FreeSpace::kHeaderSize) {
     set_map(heap->raw_unchecked_free_space_map());
     // Can't use FreeSpace::cast because it fails during deserialization.
     FreeSpace* this_as_free_space = reinterpret_cast<FreeSpace*>(this);
     this_as_free_space->set_size(size_in_bytes);
   } else if (size_in_bytes == kPointerSize) {
     set_map(heap->raw_unchecked_one_pointer_filler_map());
   } else if (size_in_bytes == 2 * kPointerSize) {
     set_map(heap->raw_unchecked_two_pointer_filler_map());
   } else {
@@ skipping 100 matching lines @@
   } else {
     node->set_next(huge_list_);
     huge_list_ = node;
   }
   available_ += size_in_bytes;
   ASSERT(IsVeryLong() || available_ == SumFreeLists());
   return 0;
 }
 
 
+FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int* node_size) {
+  FreeListNode* node = *list;
+
+  if (node == NULL) return NULL;
+
+  while (node != NULL &&
+         Page::FromAddress(node->address())->IsEvacuationCandidate()) {

[Erik Corry, 2011/07/04 11:04:11]

It would be nicer to not put the free list entries in the list in the first
place.

[Vyacheslav Egorov (Chromium), 2011/08/05 12:50:28]

Evacuation decision is made late.

+    available_ -= node->Size();
+    node = node->next();
+  }
+
+  if (node != NULL) {
+    *node_size = node->Size();
+    *list = node->next();
+  } else {
+    *list = NULL;
+  }
+
+  return node;
+}
+
+
+FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
+  FreeListNode* node = NULL;
+
+  if (size_in_bytes <= kSmallAllocationMax) {
+    node = PickNodeFromList(&small_list_, node_size);
+    if (node != NULL) return node;
+  }
+
+  if (size_in_bytes <= kMediumAllocationMax) {
+    node = PickNodeFromList(&medium_list_, node_size);
+    if (node != NULL) return node;
+  }
+
+  if (size_in_bytes <= kLargeAllocationMax) {
+    node = PickNodeFromList(&large_list_, node_size);
+    if (node != NULL) return node;
+  }
+
+  for (FreeListNode** cur = &huge_list_;
+       *cur != NULL;
+       cur = (*cur)->next_address()) {
+
+    FreeListNode* cur_node = *cur;
+    while (cur_node != NULL &&
+           Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
+      available_ -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
+      cur_node = cur_node->next();
+    }
+
+    *cur = cur_node;
+    if (cur_node == NULL) break;
+
+    ASSERT((*cur)->map() == HEAP->raw_unchecked_free_space_map());
+    FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
+    int size = cur_as_free_space->Size();
+    if (size >= size_in_bytes) {
+      // Large enough node found.  Unlink it from the list.
+      node = *cur;
+      *node_size = size;
+      *cur = node->next();
+      break;
+    }
+  }
+
+  return node;
+}
+

[Erik Corry, 2011/07/04 11:04:11]

Missing blank line

[Vyacheslav Egorov (Chromium), 2011/08/05 12:50:28]

Done.

 // Allocation on the old space free list.  If it succeeds then a new linear
 // allocation space has been set up with the top and limit of the space.  If
 // the allocation fails then NULL is returned, and the caller can perform a GC
 // or allocate a new page before retrying.
 HeapObject* FreeList::Allocate(int size_in_bytes) {
   ASSERT(0 < size_in_bytes);
   ASSERT(size_in_bytes <= kMaxBlockSize);
   ASSERT(IsAligned(size_in_bytes, kPointerSize));
   // Don't free list allocate if there is linear space available.
   ASSERT(owner_->limit() - owner_->top() < size_in_bytes);
 
-  FreeListNode* new_node = NULL;
   int new_node_size = 0;
-
-  if (size_in_bytes <= kSmallAllocationMax && small_list_ != NULL) {
-    new_node = small_list_;
-    new_node_size = new_node->Size();
-    small_list_ = new_node->next();
-  } else if (size_in_bytes <= kMediumAllocationMax && medium_list_ != NULL) {
-    new_node = medium_list_;
-    new_node_size = new_node->Size();
-    medium_list_ = new_node->next();
-  } else if (size_in_bytes <= kLargeAllocationMax && large_list_ != NULL) {
-    new_node = large_list_;
-    new_node_size = new_node->Size();
-    large_list_ = new_node->next();
-  } else {
-    for (FreeListNode** cur = &huge_list_;
-         *cur != NULL;
-         cur = (*cur)->next_address()) {
-      ASSERT((*cur)->map() == HEAP->raw_unchecked_free_space_map());
-      FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
-      int size = cur_as_free_space->Size();
-      if (size >= size_in_bytes) {
-        // Large enough node found.  Unlink it from the list.
-        new_node = *cur;
-        new_node_size = size;
-        *cur = new_node->next();
-        break;
-      }
-    }
-    if (new_node == NULL) return NULL;
-  }
+  FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
+  if (new_node == NULL) return NULL;
 
   available_ -= new_node_size;
   ASSERT(IsVeryLong() || available_ == SumFreeLists());
 
   int old_linear_size = owner_->limit() - owner_->top();
   // Mark the old linear allocation area with a free space map so it can be
   // skipped when scanning the heap.  This also puts it back in the free list
   // if it is big enough.
   owner_->Free(owner_->top(), old_linear_size);
-  // TODO(gc) ISOLATES MERGE
-  HEAP->incremental_marking()->Step(size_in_bytes - old_linear_size);
+  owner_->heap()->incremental_marking()->Step(size_in_bytes - old_linear_size);
 
   ASSERT(new_node_size - size_in_bytes >= 0);  // New linear size.
 
   const int kThreshold = IncrementalMarking::kAllocatedThreshold;
 
   // Memory in the linear allocation area is counted as allocated.  We may free
   // a little of this again immediately - see below.
   owner_->Allocate(new_node_size);
 
-  if (new_node_size - size_in_bytes > kThreshold &&
-      HEAP->incremental_marking()->IsMarkingIncomplete() &&
+  int bytes_left = new_node_size - size_in_bytes;
+  if (bytes_left > kThreshold &&
+      owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
       FLAG_incremental_marking_steps) {
     int linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
     // We don't want to give too large linear areas to the allocator while
     // incremental marking is going on, because we won't check again whether
     // we want to do another increment until the linear area is used up.
     owner_->Free(new_node->address() + size_in_bytes + linear_size,
                  new_node_size - size_in_bytes - linear_size);
     owner_->SetTop(new_node->address() + size_in_bytes,
                    new_node->address() + size_in_bytes + linear_size);
-  } else {
+  } else if (bytes_left > 0) {
     // Normally we give the rest of the node to the allocator as its new
     // linear allocation area.
     owner_->SetTop(new_node->address() + size_in_bytes,
                    new_node->address() + new_node_size);
   }
 
   return new_node;
 }
 
 
@@ skipping 62 matching lines @@
   sum += SumFreeList(large_list_);
   sum += SumFreeList(huge_list_);
   return sum;
 }
 #endif
 
 
 // -----------------------------------------------------------------------------
 // OldSpace implementation
 
-void OldSpace::PrepareForMarkCompact() {
-  // Call prepare of the super class.
-  PagedSpace::PrepareForMarkCompact();
-
-  // Stop lazy sweeping for this space.
-  first_unswept_page_ = last_unswept_page_ = Page::FromAddress(NULL);
-
-  // Clear the free list before a full GC---it will be rebuilt afterward.
-  free_list_.Reset();
-}
-
-
 bool NewSpace::ReserveSpace(int bytes) {
   // We can't reliably unpack a partial snapshot that needs more new space
   // space than the minimum NewSpace size.
   ASSERT(bytes <= InitialCapacity());
   Address limit = allocation_info_.limit;
   Address top = allocation_info_.top;
   return limit - top >= bytes;
 }
 
 
 void PagedSpace::PrepareForMarkCompact() {
   // We don't have a linear allocation area while sweeping.  It will be restored
   // on the first allocation after the sweep.
   // Mark the old linear allocation area with a free space map so it can be
   // skipped when scanning the heap.
   int old_linear_size = limit() - top();
   Free(top(), old_linear_size);
   SetTop(NULL, NULL);
+
+  // Stop lazy sweeping for the space.
+  first_unswept_page_ = last_unswept_page_ = Page::FromAddress(NULL);
+
+  // Clear the free list before a full GC---it will be rebuilt afterward.
+  free_list_.Reset();
+
+  // Clear EVACUATED flag from all pages.
+  PageIterator it(this);
+  while (it.has_next()) {
+    Page* page = it.next();
+    page->ClearFlag(MemoryChunk::EVACUATED);
+  }
 }
 
 
 bool PagedSpace::ReserveSpace(int size_in_bytes) {
   ASSERT(size_in_bytes <= Page::kMaxHeapObjectSize);
   ASSERT(size_in_bytes == RoundSizeDownToObjectAlignment(size_in_bytes));
   Address current_top = allocation_info_.top;
   Address new_top = current_top + size_in_bytes;
   if (new_top <= allocation_info_.limit) return true;
 
@@ skipping 21 matching lines @@
 
 
 bool PagedSpace::AdvanceSweeper(intptr_t bytes_to_sweep) {
   if (IsSweepingComplete()) return true;
 
   int freed_bytes = 0;
   Page* last = last_unswept_page_->next_page();
   Page* p = first_unswept_page_;
   do {
     Page* next_page = p->next_page();
-    freed_bytes += MarkCompactCollector::SweepConservatively(this, p);
+    // Evacuation candidates were swept by evacuator.
+    if (!p->WasEvacuated()) {
+      freed_bytes += MarkCompactCollector::SweepConservatively(this, p);
+    }
     p = next_page;
   } while (p != last && freed_bytes < bytes_to_sweep);
 
   if (p == last) {
     last_unswept_page_ = first_unswept_page_ = Page::FromAddress(NULL);
   } else {
     first_unswept_page_ = p;
   }
 
   heap()->LowerOldGenLimits(freed_bytes);
 
   heap()->FreeQueuedChunks();
 
   return IsSweepingComplete();
 }
 
 
+void PagedSpace::EvictEvacuationCandidatesFromFreeLists() {
+  if (allocation_info_.top >= allocation_info_.limit) return;
+
+  if (Page::FromAddress(allocation_info_.top)->IsEvacuationCandidate()) {
+      allocation_info_.top = NULL;
+      allocation_info_.limit = NULL;
+  }
+}
+
+
 HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   // Allocation in this space has failed.
 
   // 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;
   }
@@ skipping 500 matching lines @@
   for (HeapObject* obj = obj_it.Next(); obj != NULL; obj = obj_it.Next()) {
     if (obj->IsCode()) {
       Code* code = Code::cast(obj);
       isolate->code_kind_statistics()[code->kind()] += code->Size();
     }
   }
 }
 #endif  // DEBUG
 
 } }  // namespace v8::internal