Use worst-fit allocation in old space for prentured objects.

src/spaces.cc

Index: src/spaces.cc
diff --git a/src/spaces.cc b/src/spaces.cc
index 7202e1bbc07556ce31efc1d758418064d2a393f0..9cc8304aad0908078f85e56c72463eb2aadc2ab4 100644
--- a/src/spaces.cc
+++ b/src/spaces.cc
@@ -2215,36 +2215,8 @@ int FreeList::Free(Address start, int size_in_bytes) {
 }
 
 
-FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
+FreeListNode* FreeList::FindNodeInHugeList(int size_in_bytes, int* node_size) {
   FreeListNode* node = NULL;
-  Page* page = NULL;
-
-  if (size_in_bytes <= kSmallAllocationMax) {
-    node = small_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_small_free_list(-(*node_size));
-      return node;
-    }
-  }
-
-  if (size_in_bytes <= kMediumAllocationMax) {
-    node = medium_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_medium_free_list(-(*node_size));
-      return node;
-    }
-  }
-
-  if (size_in_bytes <= kLargeAllocationMax) {
-    node = large_list_.PickNodeFromList(node_size);
-    if (node != NULL) {
-      page = Page::FromAddress(node->address());
-      page->add_available_in_large_free_list(-(*node_size));
-      return node;
-    }
-  }
 
   int huge_list_available = huge_list_.available();
   for (FreeListNode** cur = huge_list_.GetTopAddress();
@@ -2255,7 +2227,7 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
            Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
       int size = reinterpret_cast<FreeSpace*>(cur_node)->Size();
       huge_list_available -= size;
-      page = Page::FromAddress(cur_node->address());
+      Page* page = Page::FromAddress(cur_node->address());
       page->add_available_in_huge_free_list(-size);
       cur_node = cur_node->next();
     }
@@ -2275,7 +2247,7 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
       *cur = node->next();
       *node_size = size;
       huge_list_available -= size;
-      page = Page::FromAddress(node->address());
+      Page* page = Page::FromAddress(node->address());
       page->add_available_in_huge_free_list(-size);
       break;
     }
@@ -2292,10 +2264,80 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
 }
 
 
+FreeListNode* FreeList::FindNodeForWorstFit(int size_in_bytes, int* node_size) {
+  FreeListNode* node = FindNodeInHugeList(size_in_bytes, node_size);
+  if (node != NULL) {
+    return node;
+  }
+
+  if (size_in_bytes <= kLargeAllocationMax) {
+    node = large_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      Page* page = Page::FromAddress(node->address());
+      page->add_available_in_large_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  if (size_in_bytes <= kMediumAllocationMax) {
+    node = medium_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      Page* page = Page::FromAddress(node->address());
+      page->add_available_in_medium_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  return node;
+}
+
+
+FreeListNode* FreeList::FindNodeForBestFit(int size_in_bytes, int* node_size) {
+  FreeListNode* node = NULL;
+
+  if (size_in_bytes <= kSmallAllocationMax) {
+    node = small_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      Page* page = Page::FromAddress(node->address());
+      page->add_available_in_small_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  if (size_in_bytes <= kMediumAllocationMax) {
+    node = medium_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      Page* page = Page::FromAddress(node->address());
+      page->add_available_in_medium_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  if (size_in_bytes <= kLargeAllocationMax) {
+    node = large_list_.PickNodeFromList(node_size);
+    if (node != NULL) {
+      Page* page = Page::FromAddress(node->address());
+      page->add_available_in_large_free_list(-(*node_size));
+      return node;
+    }
+  }
+
+  node = FindNodeInHugeList(size_in_bytes, node_size);
+  return node;
+}
+
+
+template HeapObject* FreeList::Allocate<FreeList::BEST_FIT>(int size_in_bytes);
+
+
+template HeapObject* FreeList::Allocate<FreeList::WORST_FIT>(int size_in_bytes);
+
+
 // 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.
+template<FreeList::AllocationStrategy strategy>
 HeapObject* FreeList::Allocate(int size_in_bytes) {
   ASSERT(0 < size_in_bytes);
   ASSERT(size_in_bytes <= kMaxBlockSize);
@@ -2304,7 +2346,12 @@ HeapObject* FreeList::Allocate(int size_in_bytes) {
   ASSERT(owner_->limit() - owner_->top() < size_in_bytes);
 
   int new_node_size = 0;
-  FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
+  FreeListNode* new_node;
+  if (FreeList::BEST_FIT == strategy) {
+    new_node = FindNodeForBestFit(size_in_bytes, &new_node_size);
+  } else {
+    new_node = FindNodeForWorstFit(size_in_bytes, &new_node_size);
+  }
   if (new_node == NULL) return NULL;
 
 
@@ -2335,10 +2382,17 @@ HeapObject* FreeList::Allocate(int size_in_bytes) {
   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.
+  // a little of this again immediately - see below. We try to create large
+  // bump pointer ranges when we use worst-fit, therefore we do not give
+  // memory back to the free-list.
   owner_->Allocate(new_node_size);
 
-  if (bytes_left > kThreshold &&
+  if (FreeList::WORST_FIT == strategy) {
+    owner_->AllocatePretenure(new_node_size);
+  }
+
+  if (FreeList::BEST_FIT == strategy &&
+      bytes_left > kThreshold &&
       owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
       FLAG_incremental_marking_steps) {
     int linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
@@ -2507,8 +2561,10 @@ bool PagedSpace::ReserveSpace(int size_in_bytes) {
   Address new_top = current_top + size_in_bytes;
   if (new_top <= allocation_info_.limit) return true;
 
-  HeapObject* new_area = free_list_.Allocate(size_in_bytes);
-  if (new_area == NULL) new_area = SlowAllocateRaw(size_in_bytes);
+  HeapObject* new_area = free_list_.Allocate<FreeList::BEST_FIT>(size_in_bytes);
+  if (new_area == NULL) {
+    new_area = SlowAllocateRaw<FreeList::BEST_FIT>(size_in_bytes);
+  }
   if (new_area == NULL) return false;
 
   int old_linear_size = static_cast<int>(limit() - top());
@@ -2613,6 +2669,15 @@ bool PagedSpace::EnsureSweeperProgress(intptr_t size_in_bytes) {
 }
 
 
+template HeapObject* PagedSpace::
+    SlowAllocateRaw<FreeList::BEST_FIT>(int size_in_bytes);
+
+
+template HeapObject* PagedSpace::
+    SlowAllocateRaw<FreeList::WORST_FIT>(int size_in_bytes);
+
+
+template<FreeList::AllocationStrategy strategy>
 HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   // Allocation in this space has failed.
 
@@ -2625,7 +2690,7 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
     sweeping_complete = EnsureSweeperProgress(size_in_bytes);
 
     // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
+    HeapObject* object = free_list_.Allocate<strategy>(size_in_bytes);
     if (object != NULL) return object;
   }
 
@@ -2633,13 +2698,14 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   // hit the old generation size limit that should cause a garbage
   // collection.
   if (!heap()->always_allocate() &&
+      !heap()->AggressivePromotionMode() &&
       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);
+     return free_list_.Allocate<strategy>(size_in_bytes);
   }
 
   // Last ditch, sweep all the remaining pages to try to find space.  This may
@@ -2648,7 +2714,7 @@ HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
     EnsureSweeperProgress(kMaxInt);
 
     // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
+    HeapObject* object = free_list_.Allocate<strategy>(size_in_bytes);
     if (object != NULL) return object;
   }