Reduce boot-up memory use of V8.

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 13 matching lines @@
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include "v8.h"
 
 #include "liveobjectlist-inl.h"
 #include "macro-assembler.h"
 #include "mark-compact.h"
 #include "platform.h"
+#include "snapshot.h"
 
 namespace v8 {
 namespace internal {
 
 
 // ----------------------------------------------------------------------------
 // HeapObjectIterator
 
 HeapObjectIterator::HeapObjectIterator(PagedSpace* space) {
   // You can't actually iterate over the anchor page.  It is not a real page,
@@ skipping 212 matching lines @@
 
 
 // -----------------------------------------------------------------------------
 // MemoryAllocator
 //
 
 MemoryAllocator::MemoryAllocator(Isolate* isolate)
     : isolate_(isolate),
       capacity_(0),
       capacity_executable_(0),
-      size_(0),
+      memory_allocator_reserved_(0),
       size_executable_(0) {
 }
 
 
 bool MemoryAllocator::SetUp(intptr_t capacity, intptr_t capacity_executable) {
   capacity_ = RoundUp(capacity, Page::kPageSize);
   capacity_executable_ = RoundUp(capacity_executable, Page::kPageSize);
   ASSERT_GE(capacity_, capacity_executable_);
 
-  size_ = 0;
+  memory_allocator_reserved_ = 0;
   size_executable_ = 0;
 
   return true;
 }
 
 
 void MemoryAllocator::TearDown() {
   // Check that spaces were torn down before MemoryAllocator.
-  ASSERT(size_ == 0);
+  CHECK_EQ(memory_allocator_reserved_, 0);
   // TODO(gc) this will be true again when we fix FreeMemory.
   // ASSERT(size_executable_ == 0);
   capacity_ = 0;
   capacity_executable_ = 0;
 }
 
 
 void MemoryAllocator::FreeMemory(VirtualMemory* reservation,
                                  Executability executable) {
   // TODO(gc) make code_range part of memory allocator?
   ASSERT(reservation->IsReserved());
   size_t size = reservation->size();
-  ASSERT(size_ >= size);
-  size_ -= size;
+  ASSERT(memory_allocator_reserved_ >= size);
+  memory_allocator_reserved_ -= size;
 
   isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(size));
 
   if (executable == EXECUTABLE) {
     ASSERT(size_executable_ >= size);
     size_executable_ -= size;
   }
   // Code which is part of the code-range does not have its own VirtualMemory.
   ASSERT(!isolate_->code_range()->contains(
       static_cast<Address>(reservation->address())));
   ASSERT(executable == NOT_EXECUTABLE || !isolate_->code_range()->exists());
   reservation->Release();
 }
 
 
 void MemoryAllocator::FreeMemory(Address base,
                                  size_t size,
                                  Executability executable) {
   // TODO(gc) make code_range part of memory allocator?
-  ASSERT(size_ >= size);
-  size_ -= size;
+  ASSERT(memory_allocator_reserved_ >= size);
+  memory_allocator_reserved_ -= size;
 
   isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(size));
 
   if (executable == EXECUTABLE) {
     ASSERT(size_executable_ >= size);
     size_executable_ -= size;
   }
   if (isolate_->code_range()->contains(static_cast<Address>(base))) {
     ASSERT(executable == EXECUTABLE);
     isolate_->code_range()->FreeRawMemory(base, size);
   } else {
     ASSERT(executable == NOT_EXECUTABLE || !isolate_->code_range()->exists());
     bool result = VirtualMemory::ReleaseRegion(base, size);
     USE(result);
     ASSERT(result);
   }
 }
 
 
 Address MemoryAllocator::ReserveAlignedMemory(size_t size,
                                               size_t alignment,
                                               VirtualMemory* controller) {
   VirtualMemory reservation(size, alignment);
 
   if (!reservation.IsReserved()) return NULL;
-  size_ += reservation.size();
+  memory_allocator_reserved_ += reservation.size();
   Address base = RoundUp(static_cast<Address>(reservation.address()),
                          alignment);
   controller->TakeControl(&reservation);
   return base;
 }
 
 
 Address MemoryAllocator::AllocateAlignedMemory(size_t size,
+                                               size_t reserved_size,
                                                size_t alignment,
                                                Executability executable,
                                                VirtualMemory* controller) {
+  ASSERT(RoundUp(reserved_size, OS::CommitPageSize()) >=
+         RoundUp(size, OS::CommitPageSize()));
   VirtualMemory reservation;
-  Address base = ReserveAlignedMemory(size, alignment, &reservation);
+  Address base = ReserveAlignedMemory(reserved_size, alignment, &reservation);
   if (base == NULL) return NULL;
   if (!reservation.Commit(base,
                           size,
                           executable == EXECUTABLE)) {
     return NULL;
   }
   controller->TakeControl(&reservation);
   return base;
 }
 
 
 void Page::InitializeAsAnchor(PagedSpace* owner) {
   set_owner(owner);
   set_prev_page(this);
   set_next_page(this);
 }
 
 
+void Page::CommitMore(intptr_t space_needed) {
+  intptr_t reserved_page_size = reservation_.IsReserved() ?
+      reservation_.size() :
+      Page::kPageSize;
+  ASSERT(size() + space_needed <= reserved_page_size);
+  // At increase the page size by at least 64k (this also rounds to OS page
+  // size).
+  int expand = Min(reserved_page_size - size(),
+                   RoundUp(size() + space_needed, Page::kGrowthUnit) - size());
+  ASSERT(expand <= kPageSize - size());
+  ASSERT(expand <= reserved_page_size - size());
+  Executability executable =
+      IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;
+  Address old_end = ObjectAreaEnd();
+  if (!VirtualMemory::CommitRegion(old_end, expand, executable)) return;
+
+  set_size(size() + expand);
+
+  PagedSpace* paged_space = reinterpret_cast<PagedSpace*>(owner());
+  paged_space->heap()->isolate()->memory_allocator()->AllocationBookkeeping(
+      paged_space,
+      old_end,
+      0,  // No new memory was reserved.
+      expand,  // New memory committed.
+      executable);
+  paged_space->IncreaseCapacity(expand);
+
+  // In spaces with alignment requirements (e.g. map space) we have to align
+  // the expanded area with the correct object alignment.
+  uintptr_t object_area_size = old_end - ObjectAreaStart();
+  uintptr_t aligned_object_area_size =
+      object_area_size - object_area_size % paged_space->ObjectAlignment();
+  if (aligned_object_area_size != object_area_size) {
+    aligned_object_area_size += paged_space->ObjectAlignment();
+  }
+  Address new_area =
+      reinterpret_cast<Address>(ObjectAreaStart() + aligned_object_area_size);
+  // In spaces with alignment requirements, this will waste the space for one
+  // object per doubling of the page size until the next GC.
+  paged_space->AddToFreeLists(old_end, new_area - old_end);
+
+  expand -= (new_area - old_end);
+
+  paged_space->AddToFreeLists(new_area, expand);
+}
+
+
 NewSpacePage* NewSpacePage::Initialize(Heap* heap,
                                        Address start,
                                        SemiSpace* semi_space) {
   MemoryChunk* chunk = MemoryChunk::Initialize(heap,
                                                start,
                                                Page::kPageSize,
                                                NOT_EXECUTABLE,
                                                semi_space);
   chunk->set_next_chunk(NULL);
   chunk->set_prev_chunk(NULL);
@@ skipping 65 matching lines @@
     ClearFlag(SCAN_ON_SCAVENGE);
   }
   next_chunk_->prev_chunk_ = prev_chunk_;
   prev_chunk_->next_chunk_ = next_chunk_;
   prev_chunk_ = NULL;
   next_chunk_ = NULL;
 }
 
 
 MemoryChunk* MemoryAllocator::AllocateChunk(intptr_t body_size,
+                                            intptr_t committed_body_size,
                                             Executability executable,
                                             Space* owner) {
-  size_t chunk_size = MemoryChunk::kObjectStartOffset + body_size;
+  ASSERT(body_size >= committed_body_size);
+  size_t chunk_size = RoundUp(MemoryChunk::kObjectStartOffset + body_size,
+                              OS::CommitPageSize());
+  intptr_t committed_chunk_size =
+      committed_body_size + MemoryChunk::kObjectStartOffset;
+  committed_chunk_size = RoundUp(committed_chunk_size, OS::CommitPageSize());
   Heap* heap = isolate_->heap();
   Address base = NULL;
   VirtualMemory reservation;
   if (executable == EXECUTABLE) {
     // Check executable memory limit.
     if (size_executable_ + chunk_size > capacity_executable_) {
       LOG(isolate_,
           StringEvent("MemoryAllocator::AllocateRawMemory",
                       "V8 Executable Allocation capacity exceeded"));
       return NULL;
     }
 
     // Allocate executable memory either from code range or from the
     // OS.
     if (isolate_->code_range()->exists()) {
       base = isolate_->code_range()->AllocateRawMemory(chunk_size, &chunk_size);
       ASSERT(IsAligned(reinterpret_cast<intptr_t>(base),
                        MemoryChunk::kAlignment));
       if (base == NULL) return NULL;
-      size_ += chunk_size;
-      // Update executable memory size.
-      size_executable_ += chunk_size;
+      // The AllocateAlignedMemory method will update the memory allocator
+      // memory used, but we are not using that if we have a code range, so
+      // we update it here.
+      memory_allocator_reserved_ += chunk_size;
     } else {
-      base = AllocateAlignedMemory(chunk_size,
+      base = AllocateAlignedMemory(committed_chunk_size,
+                                   chunk_size,
                                    MemoryChunk::kAlignment,
                                    executable,
                                    &reservation);
       if (base == NULL) return NULL;
-      // Update executable memory size.
-      size_executable_ += reservation.size();
     }
   } else {
-    base = AllocateAlignedMemory(chunk_size,
+    base = AllocateAlignedMemory(committed_chunk_size,
+                                 chunk_size,
                                  MemoryChunk::kAlignment,
                                  executable,
                                  &reservation);
 
     if (base == NULL) return NULL;
   }
 
-#ifdef DEBUG
-  ZapBlock(base, chunk_size);
-#endif
-  isolate_->counters()->memory_allocated()->
-      Increment(static_cast<int>(chunk_size));
-
-  LOG(isolate_, NewEvent("MemoryChunk", base, chunk_size));
-  if (owner != NULL) {
-    ObjectSpace space = static_cast<ObjectSpace>(1 << owner->identity());
-    PerformAllocationCallback(space, kAllocationActionAllocate, chunk_size);
-  }
+  AllocationBookkeeping(
+      owner, base, chunk_size, committed_chunk_size, executable);
 
   MemoryChunk* result = MemoryChunk::Initialize(heap,
                                                 base,
-                                                chunk_size,
+                                                committed_chunk_size,
                                                 executable,
                                                 owner);
   result->set_reserved_memory(&reservation);
   return result;
 }
 
 
-Page* MemoryAllocator::AllocatePage(PagedSpace* owner,
+void MemoryAllocator::AllocationBookkeeping(Space* owner,
+                                            Address base,
+                                            intptr_t reserved_chunk_size,
+                                            intptr_t committed_chunk_size,
+                                            Executability executable) {
+  if (executable == EXECUTABLE) {
+    // Update executable memory size.
+    size_executable_ += reserved_chunk_size;
+  }
+
+#ifdef DEBUG
+  ZapBlock(base, committed_chunk_size);
+#endif
+  isolate_->counters()->memory_allocated()->
+      Increment(static_cast<int>(committed_chunk_size));
+
+  LOG(isolate_, NewEvent("MemoryChunk", base, committed_chunk_size));
+  if (owner != NULL) {
+    ObjectSpace space = static_cast<ObjectSpace>(1 << owner->identity());
+    PerformAllocationCallback(
+        space, kAllocationActionAllocate, committed_chunk_size);
+  }
+}
+
+
+Page* MemoryAllocator::AllocatePage(intptr_t committed_object_area_size,
+                                    PagedSpace* owner,
                                     Executability executable) {
-  MemoryChunk* chunk = AllocateChunk(Page::kObjectAreaSize, executable, owner);
+  ASSERT(committed_object_area_size <= Page::kObjectAreaSize);
+
+  MemoryChunk* chunk = AllocateChunk(Page::kObjectAreaSize,
+                                     committed_object_area_size,
+                                     executable,
+                                     owner);
 
   if (chunk == NULL) return NULL;
 
   return Page::Initialize(isolate_->heap(), chunk, executable, owner);
 }
 
 
 LargePage* MemoryAllocator::AllocateLargePage(intptr_t object_size,
                                               Executability executable,
                                               Space* owner) {
-  MemoryChunk* chunk = AllocateChunk(object_size, executable, owner);
+  MemoryChunk* chunk =
+      AllocateChunk(object_size, object_size, executable, owner);
   if (chunk == NULL) return NULL;
   return LargePage::Initialize(isolate_->heap(), chunk);
 }
 
 
 void MemoryAllocator::Free(MemoryChunk* chunk) {
   LOG(isolate_, DeleteEvent("MemoryChunk", chunk));
   if (chunk->owner() != NULL) {
     ObjectSpace space =
         static_cast<ObjectSpace>(1 << chunk->owner()->identity());
     PerformAllocationCallback(space, kAllocationActionFree, chunk->size());
   }
 
   delete chunk->slots_buffer();
   delete chunk->skip_list();
 
   VirtualMemory* reservation = chunk->reserved_memory();
   if (reservation->IsReserved()) {
     FreeMemory(reservation, chunk->executable());
   } else {
+    // When we do not have a reservation that is because this allocation
+    // is part of the huge reserved chunk of memory reserved for code on
+    // x64.  In that case the size was rounded up to the page size on
+    // allocation so we do the same now when freeing.
     FreeMemory(chunk->address(),
-               chunk->size(),
+               RoundUp(chunk->size(), Page::kPageSize),
                chunk->executable());
   }
 }
 
 
 bool MemoryAllocator::CommitBlock(Address start,
                                   size_t size,
                                   Executability executable) {
   if (!VirtualMemory::CommitRegion(start, size, executable)) return false;
 #ifdef DEBUG
@@ skipping 59 matching lines @@
       memory_allocation_callbacks_.Remove(i);
       return;
     }
   }
   UNREACHABLE();
 }
 
 
 #ifdef DEBUG
 void MemoryAllocator::ReportStatistics() {
-  float pct = static_cast<float>(capacity_ - size_) / capacity_;
+  float pct =
+      static_cast<float>(capacity_ - memory_allocator_reserved_) / capacity_;
   PrintF("  capacity: %" V8_PTR_PREFIX "d"
              ", used: %" V8_PTR_PREFIX "d"
              ", available: %%%d\n\n",
-         capacity_, size_, static_cast<int>(pct*100));
+         capacity_, memory_allocator_reserved_, static_cast<int>(pct*100));
 }
 #endif
 
 // -----------------------------------------------------------------------------
 // MemoryChunk implementation
 
 void MemoryChunk::IncrementLiveBytesFromMutator(Address address, int by) {
   MemoryChunk* chunk = MemoryChunk::FromAddress(address);
   if (!chunk->InNewSpace() && !static_cast<Page*>(chunk)->WasSwept()) {
     static_cast<PagedSpace*>(chunk->owner())->IncrementUnsweptFreeBytes(-by);
@@ skipping 58 matching lines @@
     Address next = cur + obj->Size();
     if ((cur <= addr) && (addr < next)) return obj;
   }
 
   UNREACHABLE();
   return Failure::Exception();
 }
 
 bool PagedSpace::CanExpand() {
   ASSERT(max_capacity_ % Page::kObjectAreaSize == 0);
-  ASSERT(Capacity() % Page::kObjectAreaSize == 0);
 
   if (Capacity() == max_capacity_) return false;
 
   ASSERT(Capacity() < max_capacity_);
 
   // Are we going to exceed capacity for this space?
   if ((Capacity() + Page::kPageSize) > max_capacity_) return false;
 
   return true;
 }
 
-bool PagedSpace::Expand() {
+bool PagedSpace::Expand(intptr_t size_in_bytes) {
   if (!CanExpand()) return false;
 
+  Page* last_page = anchor_.prev_page();
+  if (last_page != &anchor_) {
+    // We have run out of linear allocation space.  This may be  because the
+    // most recently allocated page (stored last in the list) is a small one,
+    // that starts on a page aligned boundary, but has not a full kPageSize of
+    // committed memory.  Let's commit more memory for the page.
+    intptr_t reserved_page_size = last_page->reserved_memory()->IsReserved() ?
+        last_page->reserved_memory()->size() :
+        Page::kPageSize;
+    if (last_page->size() < reserved_page_size &&
+        (reserved_page_size - last_page->size()) >= size_in_bytes &&
+        !last_page->IsEvacuationCandidate() &&
+        last_page->WasSwept()) {
+      last_page->CommitMore(size_in_bytes);
+      return true;
+    }
+  }
+
+  // We initially only commit a part of the page, but the deserialization
+  // of the initial snapshot makes the assumption that it can deserialize
+  // into linear memory of a certain size per space, so some of the spaces
+  // need to have a little more committed memory.
+  int initial =
+      Max(OS::CommitPageSize(), static_cast<intptr_t>(Page::kGrowthUnit));
+
+  ASSERT(Page::kPageSize - initial < Page::kObjectAreaSize);
+
+  intptr_t expansion_size =
+      Max(initial,
+          RoundUpToPowerOf2(MemoryChunk::kObjectStartOffset + size_in_bytes)) -
+      MemoryChunk::kObjectStartOffset;
+
   Page* p = heap()->isolate()->memory_allocator()->
-      AllocatePage(this, executable());
+      AllocatePage(expansion_size, this, executable());
   if (p == NULL) return false;
 
   ASSERT(Capacity() <= max_capacity_);
 
   p->InsertAfter(anchor_.prev_page());
 
   return true;
 }
 
 
@@ skipping 24 matching lines @@
     accounting_stats_.AllocateBytes(size);
     ASSERT_EQ(Page::kObjectAreaSize, static_cast<int>(size));
   } else {
     DecreaseUnsweptFreeBytes(page);
   }
 
   if (Page::FromAllocationTop(allocation_info_.top) == page) {
     allocation_info_.top = allocation_info_.limit = NULL;
   }
 
+  intptr_t size = page->ObjectAreaEnd() - page->ObjectAreaStart();
+
   page->Unlink();
   if (page->IsFlagSet(MemoryChunk::CONTAINS_ONLY_DATA)) {
     heap()->isolate()->memory_allocator()->Free(page);
   } else {
     heap()->QueueMemoryChunkForFree(page);
   }
 
   ASSERT(Capacity() > 0);
-  ASSERT(Capacity() % Page::kObjectAreaSize == 0);
-  accounting_stats_.ShrinkSpace(Page::kObjectAreaSize);
+  accounting_stats_.ShrinkSpace(size);
 }
 
 
 void PagedSpace::ReleaseAllUnusedPages() {
   PageIterator it(this);
   while (it.has_next()) {
     Page* page = it.next();
     if (!page->WasSwept()) {
       if (page->LiveBytes() == 0) ReleasePage(page);
     } else {
@@ skipping 857 matching lines @@
 // Free lists for old object spaces implementation
 
 void FreeListNode::set_size(Heap* heap, int size_in_bytes) {
   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
+  // If the block is too small (e.g. 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.
   if (size_in_bytes > FreeSpace::kHeaderSize) {
     set_map_no_write_barrier(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_no_write_barrier(heap->raw_unchecked_one_pointer_filler_map());
   } else if (size_in_bytes == 2 * kPointerSize) {
@@ skipping 83 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* FreeList::PickNodeFromList(FreeListNode** list,
+                                         int* node_size,
+                                         int minimum_size) {
   FreeListNode* node = *list;
 
   if (node == NULL) return NULL;
 
+  ASSERT(node->map() == node->GetHeap()->raw_unchecked_free_space_map());
+
   while (node != NULL &&
          Page::FromAddress(node->address())->IsEvacuationCandidate()) {
     available_ -= node->Size();
     node = node->next();
   }
 
-  if (node != NULL) {
-    *node_size = node->Size();
-    *list = node->next();
-  } else {
+  if (node == NULL) {
     *list = NULL;
+    return NULL;
   }
 
+  // Gets the size without checking the map.  When we are booting we have
+  // a FreeListNode before we have created its map.
+  intptr_t size = reinterpret_cast<FreeSpace*>(node)->Size();
+
+  // We don't search the list for one that fits, preferring to look in the
+  // list of larger nodes, but we do check the first in the list, because
+  // if we had to expand the space or page we may have placed an entry that
+  // was just long enough at the head of one of the lists.
+  if (size < minimum_size) return NULL;
+
+  *node_size = size;
+  available_ -= size;
+  *list = node->next();
+
   return node;
 }
 
 
-FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
+FreeListNode* FreeList::FindAbuttingNode(
+  int size_in_bytes, int* node_size, Address limit, FreeListNode** list_head) {
+  FreeListNode* first_node = *list_head;
+  if (first_node != NULL &&
+      first_node->address() == limit &&
+      reinterpret_cast<FreeSpace*>(first_node)->Size() >= size_in_bytes &&
+      !Page::FromAddress(first_node->address())->IsEvacuationCandidate()) {
+    FreeListNode* answer = first_node;
+    int size = reinterpret_cast<FreeSpace*>(first_node)->Size();
+    available_ -= size;
+    *node_size = size;
+    *list_head = first_node->next();
+    ASSERT(IsVeryLong() || available_ == SumFreeLists());
+    return answer;
+  }
+  return NULL;
+}
+
+
+FreeListNode* FreeList::FindNodeFor(int size_in_bytes,
+                                    int* node_size,
+                                    Address limit) {
   FreeListNode* node = NULL;
 
-  if (size_in_bytes <= kSmallAllocationMax) {
-    node = PickNodeFromList(&small_list_, node_size);
+  if (limit != NULL) {
+    // We may have a memory area at the head of the free list, which abuts the
+    // old linear allocation area.  This happens if the linear allocation area
+    // has been shortened to allow an incremental marking step to be performed.
+    // In that case we prefer to return the free memory area that is contiguous
+    // with the old linear allocation area.
+    node = FindAbuttingNode(size_in_bytes, node_size, limit, &large_list_);
+    if (node != NULL) return node;
+    node = FindAbuttingNode(size_in_bytes, node_size, limit, &huge_list_);
     if (node != NULL) return node;
   }
 
-  if (size_in_bytes <= kMediumAllocationMax) {
-    node = PickNodeFromList(&medium_list_, node_size);
+  node = PickNodeFromList(&small_list_, node_size, size_in_bytes);
+  ASSERT(IsVeryLong() || available_ == SumFreeLists());
+  if (node != NULL) return node;
+
+  node = PickNodeFromList(&medium_list_, node_size, size_in_bytes);
+  ASSERT(IsVeryLong() || available_ == SumFreeLists());
+  if (node != NULL) return node;
+
+  node = PickNodeFromList(&large_list_, node_size, size_in_bytes);
+  ASSERT(IsVeryLong() || available_ == SumFreeLists());
+  if (node != NULL) return node;
+
+  // The tricky third clause in this for statement is due to the fact that
+  // PickNodeFromList can cut pages out of the list if they are unavailable for
+  // new allocation (e.g. if they are on a page that has been scheduled for
+  // evacuation).
+  for (FreeListNode** cur = &huge_list_;
+       *cur != NULL;
+       cur = (*cur) == NULL ? cur : (*cur)->next_address()) {
+    node = PickNodeFromList(cur, node_size, size_in_bytes);
+    ASSERT(IsVeryLong() || available_ == SumFreeLists());
     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;
 }
 
 
 // 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);
 
   int new_node_size = 0;
-  FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
+  FreeListNode* new_node =
+      FindNodeFor(size_in_bytes, &new_node_size, owner_->limit());
   if (new_node == NULL) return NULL;
 
-  available_ -= new_node_size;
+  if (new_node->address() == owner_->limit()) {
+    // The new freelist node we were given is an extension of the one we had
+    // last.  This is a common thing to happen when we extend a small page by
+    // committing more memory.  In this case we just add the new node to the
+    // linear allocation area and recurse.
+    owner_->Allocate(new_node_size);
+    owner_->SetTop(owner_->top(), new_node->address() + new_node_size);
+    MaybeObject* allocation = owner_->AllocateRaw(size_in_bytes);
+    Object* answer;
+    if (!allocation->ToObject(&answer)) return NULL;
+    return HeapObject::cast(answer);
+  }
+
   ASSERT(IsVeryLong() || available_ == SumFreeLists());
 
   int bytes_left = new_node_size - size_in_bytes;
   ASSERT(bytes_left >= 0);
 
   int old_linear_size = static_cast<int>(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);
+  if (old_linear_size != 0) {
+    owner_->AddToFreeLists(owner_->top(), old_linear_size);
+  }
 
 #ifdef DEBUG
   for (int i = 0; i < size_in_bytes / kPointerSize; i++) {
     reinterpret_cast<Object**>(new_node->address())[i] = Smi::FromInt(0);
   }
 #endif
 
   owner_->heap()->incremental_marking()->OldSpaceStep(
       size_in_bytes - old_linear_size);
 
   // The old-space-step might have finished sweeping and restarted marking.
   // Verify that it did not turn the page of the new node into an evacuation
   // candidate.
   ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(new_node));
 
   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 (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_->AddToFreeLists(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 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);
   } else {
+    ASSERT(bytes_left == 0);
     // TODO(gc) Try not freeing linear allocation region when bytes_left
     // are zero.
     owner_->SetTop(NULL, NULL);
   }
 
   return new_node;
 }
 
 
 static intptr_t CountFreeListItemsInList(FreeListNode* n, Page* p) {
@@ skipping 112 matching lines @@
   // or because we have lowered the limit in order to get periodic incremental
   // marking.  The most reliable way to ensure that there is linear space is
   // to do the allocation, then rewind the limit.
   ASSERT(bytes <= InitialCapacity());
   MaybeObject* maybe = AllocateRaw(bytes);
   Object* object = NULL;
   if (!maybe->ToObject(&object)) return false;
   HeapObject* allocation = HeapObject::cast(object);
   Address top = allocation_info_.top;
   if ((top - bytes) == allocation->address()) {
-    allocation_info_.top = allocation->address();
+    Address new_top = allocation->address();
+    ASSERT(new_top >= Page::FromAddress(new_top - 1)->ObjectAreaStart());
+    allocation_info_.top = new_top;
     return true;
   }
   // There may be a borderline case here where the allocation succeeded, but
   // the limit and top have moved on to a new page.  In that case we try again.
   return ReserveSpace(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 = static_cast<int>(limit() - top());
-  Free(top(), old_linear_size);
+  AddToFreeLists(top(), old_linear_size);
   SetTop(NULL, NULL);
 
   // Stop lazy sweeping and clear marking bits for unswept pages.
   if (first_unswept_page_ != NULL) {
     Page* p = first_unswept_page_;
     do {
       // Do not use ShouldBeSweptLazily predicate here.
       // New evacuation candidates were selected but they still have
       // to be swept before collection starts.
       if (!p->WasSwept()) {
@@ skipping 22 matching lines @@
   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);
   if (new_area == NULL) return false;
 
   int old_linear_size = static_cast<int>(limit() - top());
   // Mark the old linear allocation area with a free space so it can be
   // skipped when scanning the heap.  This also puts it back in the free list
   // if it is big enough.
-  Free(top(), old_linear_size);
+  AddToFreeLists(top(), old_linear_size);
 
   SetTop(new_area->address(), new_area->address() + size_in_bytes);
-  Allocate(size_in_bytes);
+  // The AddToFreeLists call above will reduce the size of the space in the
+  // allocation stats.  We don't need to add this linear area to the size
+  // with an Allocate(size_in_bytes) call here, because the
+  // free_list_.Allocate() call above already accounted for this memory.
   return true;
 }
 
 
 // You have to call this last, since the implementation from PagedSpace
 // doesn't know that memory was 'promised' to large object space.
 bool LargeObjectSpace::ReserveSpace(int bytes) {
   return heap()->OldGenerationSpaceAvailable() >= bytes;
 }
 
@@ skipping 60 matching lines @@
 
   // 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()) {
+  if (Expand(size_in_bytes)) {
     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);
@@ skipping 340 matching lines @@
       if (previous == NULL) {
         first_page_ = current;
       } else {
         previous->set_next_page(current);
       }
 
       // Free the chunk.
       heap()->mark_compact_collector()->ReportDeleteIfNeeded(
           object, heap()->isolate());
       size_ -= static_cast<int>(page->size());
+      ASSERT(size_ >= 0);
       objects_size_ -= object->Size();
       page_count_--;
 
       if (is_pointer_object) {
         heap()->QueueMemoryChunkForFree(page);
       } else {
         heap()->isolate()->memory_allocator()->Free(page);
       }
     }
   }
@@ skipping 118 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal