- Do not bump allocate in old-space pages. Always use

vm/pages.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/pages.h"
 
 #include "platform/assert.h"
 #include "vm/gc_marker.h"
 #include "vm/gc_sweeper.h"
 #include "vm/object.h"
@@ skipping 13 matching lines @@
             "Print free list statistics after a GC");
 
 HeapPage* HeapPage::Initialize(VirtualMemory* memory, bool is_executable) {
   ASSERT(memory->size() > VirtualMemory::PageSize());
   memory->Commit(is_executable);
 
   HeapPage* result = reinterpret_cast<HeapPage*>(memory->address());
   result->memory_ = memory;
   result->next_ = NULL;
   result->used_ = 0;
-  result->top_ = result->first_object_start();
   return result;
 }
 
 
 HeapPage* HeapPage::Allocate(intptr_t size, bool is_executable) {
   VirtualMemory* memory =
       VirtualMemory::ReserveAligned(size, PageSpace::kPageAlignment);
   return Initialize(memory, is_executable);
 }
 
 
 void HeapPage::Deallocate() {
   // The memory for this object will become unavailable after the delete below.
   delete memory_;
 }
 
 
 void HeapPage::VisitObjects(ObjectVisitor* visitor) const {
   uword obj_addr = first_object_start();
-  uword end_addr = top();
+  uword end_addr = end();
   while (obj_addr < end_addr) {
     RawObject* raw_obj = RawObject::FromAddr(obj_addr);
     visitor->VisitObject(raw_obj);
     obj_addr += raw_obj->Size();
   }
   ASSERT(obj_addr == end_addr);
 }
 
 
 void HeapPage::VisitObjectPointers(ObjectPointerVisitor* visitor) const {
   uword obj_addr = first_object_start();
-  uword end_addr = top();
+  uword end_addr = end();
   while (obj_addr < end_addr) {
     RawObject* raw_obj = RawObject::FromAddr(obj_addr);
     obj_addr += raw_obj->VisitPointers(visitor);
   }
   ASSERT(obj_addr == end_addr);
 }
 
 
 RawObject* HeapPage::FindObject(FindObjectVisitor* visitor) const {
   uword obj_addr = first_object_start();
-  uword end_addr = top();
+  uword end_addr = end();
   while (obj_addr < end_addr) {
     RawObject* raw_obj = RawObject::FromAddr(obj_addr);
     if (raw_obj->FindObject(visitor)) {
       return raw_obj;  // Found object, return it.
     }
     obj_addr += raw_obj->Size();
   }
   ASSERT(obj_addr == end_addr);
   return Object::null();
 }
 
 
 void HeapPage::WriteProtect(bool read_only) {
   memory_->Protect(
       read_only ? VirtualMemory::kReadOnly : VirtualMemory::kReadWrite);
 }
 
 
 PageSpace::PageSpace(Heap* heap, intptr_t max_capacity, bool is_executable)
     : freelist_(),
       heap_(heap),
       pages_(NULL),
       pages_tail_(NULL),
       large_pages_(NULL),
-      bump_page_(NULL),
       max_capacity_(max_capacity),
       capacity_(0),
       in_use_(0),
       count_(0),
       is_executable_(is_executable),
       sweeping_(false),
       page_space_controller_(FLAG_heap_growth_space_ratio,
                              FLAG_heap_growth_rate,
                              FLAG_heap_growth_time_ratio) {
 }
 
 
 PageSpace::~PageSpace() {
   FreePages(pages_);
   FreePages(large_pages_);
 }
 
 
 intptr_t PageSpace::LargePageSizeFor(intptr_t size) {
   intptr_t page_size = Utils::RoundUp(size + sizeof(HeapPage),
                                       VirtualMemory::PageSize());
   return page_size;
 }
 
 
-void PageSpace::AllocatePage() {
+HeapPage* PageSpace::AllocatePage() {
   HeapPage* page = HeapPage::Allocate(kPageSize, is_executable_);
   if (pages_ == NULL) {
     pages_ = page;
   } else {
     pages_tail_->set_next(page);
   }
   pages_tail_ = page;
-  bump_page_ = NULL;  // Reenable scanning of pages for bump allocation.
   capacity_ += kPageSize;
+  return page;
 }
 
 
 HeapPage* PageSpace::AllocateLargePage(intptr_t size) {
   intptr_t page_size = LargePageSizeFor(size);
   HeapPage* page = HeapPage::Allocate(page_size, is_executable_);
   page->set_next(large_pages_);
   large_pages_ = page;
   capacity_ += page_size;
   return page;
@@ skipping 31 matching lines @@
 void PageSpace::FreePages(HeapPage* pages) {
   HeapPage* page = pages;
   while (page != NULL) {
     HeapPage* next = page->next();
     page->Deallocate();
     page = next;
   }
 }
 
 
-uword PageSpace::TryBumpAllocate(intptr_t size) {
-  if (pages_tail_ == NULL) {
-    return 0;
-  }
-  uword result = pages_tail_->TryBumpAllocate(size);
-  if (result != 0) {
-    return result;
-  }
-  if (bump_page_ == NULL) {
-    // The bump page has not yet been used: Start at the beginning of the list.
-    bump_page_ = pages_;
-  }
-  // The last page has already been attempted above.
-  while (bump_page_ != pages_tail_) {
-    ASSERT(bump_page_->next() != NULL);
-    result = bump_page_->TryBumpAllocate(size);
-    if (result != 0) {
-      return result;
-    }
-    bump_page_ = bump_page_->next();
-  }
-  // Ran through all of the pages trying to bump allocate: Give up.
-  return 0;
-}
-
-
 uword PageSpace::TryAllocate(intptr_t size) {
   return TryAllocate(size, kControlGrowth);
 }
 
 
 uword PageSpace::TryAllocate(intptr_t size, GrowthPolicy growth_policy) {
   ASSERT(size >= kObjectAlignment);
   ASSERT(Utils::IsAligned(size, kObjectAlignment));
   uword result = 0;
   if (size < kAllocatablePageSize) {
     result = freelist_.TryAllocate(size);
-    if (result == 0) {
-      result = TryBumpAllocate(size);
-      if ((result == 0) &&
-          (page_space_controller_.CanGrowPageSpace(size) ||
-           growth_policy == kForceGrowth) &&
-          CanIncreaseCapacity(kPageSize)) {
-        AllocatePage();
-        result = TryBumpAllocate(size);
-        ASSERT(result != 0);
-      }
+    if ((result == 0) &&
+        (page_space_controller_.CanGrowPageSpace(size) ||
+         growth_policy == kForceGrowth) &&
+        CanIncreaseCapacity(kPageSize)) {
+      HeapPage* page = AllocatePage();
+      ASSERT(page != NULL);
+      // Start of the newly allocated page is the allocated object.
+      result = page->first_object_start();
+      // Enqueue the remainder in the free list.
+      uword free_start = result + size;
+      freelist_.Free(
+          free_start,
+          Utils::RoundDown(page->end() - free_start, kObjectAlignment));
     }
   } else {
     // Large page allocation.
     intptr_t page_size = LargePageSizeFor(size);
     if (page_size < size) {
       // On overflow we fail to allocate.
       return 0;
     }
     if (CanIncreaseCapacity(page_size)) {
       HeapPage* page = AllocateLargePage(size);
       if (page != NULL) {
-        result = page->top();
-        page->set_top(result + size);
+        result = page->first_object_start();
       }
     }
   }
   if (result != 0) {
     in_use_ += size;
   }
+  ASSERT((result & kObjectAlignmentMask) == kOldObjectAlignmentOffset);
   return result;
 }
 
 
 bool PageSpace::Contains(uword addr) const {
   HeapPage* page = pages_;
   while (page != NULL) {
     if (page->Contains(addr)) {
       return true;
     }
@@ skipping 30 matching lines @@
 
 void PageSpace::VisitObjects(ObjectVisitor* visitor) const {
   HeapPage* page = pages_;
   while (page != NULL) {
     page->VisitObjects(visitor);
     page = page->next();
   }
 
   page = large_pages_;
   while (page != NULL) {
-    page->VisitObjects(visitor);
+    uword obj_addr = page->first_object_start();

[cshapiro, 2012/10/17 02:53:22]

Why did this code have to change?  This was done in a few places.  I looked at
this code side by side with HeapPage::VisitObjects and it seems equivalent.

Anyhow, this expansion is repeated 2 times below.  For the sake of debugging and
test coverage, having one code path instead of 2 similar ones is strongly
preferable.

[Ivan Posva, 2012/10/18 17:34:21]

I did not like the expansion either. Now that I have introduced object_end I am
undoing these changes.

+    RawObject* raw_obj = RawObject::FromAddr(obj_addr);
+    visitor->VisitObject(raw_obj);
     page = page->next();
   }
 }
 
 
 void PageSpace::SetPeer(RawObject* raw_obj, void* peer) {
   if (peer == NULL) {
     peer_table_.erase(raw_obj);
   } else {
     peer_table_[raw_obj] = peer;
@@ skipping 14 matching lines @@
 
 void PageSpace::VisitObjectPointers(ObjectPointerVisitor* visitor) const {
   HeapPage* page = pages_;
   while (page != NULL) {
     page->VisitObjectPointers(visitor);
     page = page->next();
   }
 
   page = large_pages_;
   while (page != NULL) {
-    page->VisitObjectPointers(visitor);
+    uword obj_addr = page->first_object_start();

[cshapiro, 2012/10/17 02:53:22]

ditto

+    RawObject* raw_obj = RawObject::FromAddr(obj_addr);
+    raw_obj->VisitPointers(visitor);
     page = page->next();
   }
 }
 
 
 RawObject* PageSpace::FindObject(FindObjectVisitor* visitor) const {
   ASSERT(Isolate::Current()->no_gc_scope_depth() != 0);
   HeapPage* page = pages_;
   while (page != NULL) {
     RawObject* obj = page->FindObject(visitor);
     if (obj != Object::null()) {
       return obj;
     }
     page = page->next();
   }
 
   page = large_pages_;
   while (page != NULL) {
-    RawObject* obj = page->FindObject(visitor);
-    if (obj != Object::null()) {
-      return obj;
+    uword obj_addr = page->first_object_start();

[cshapiro, 2012/10/17 02:53:22]

ditto

+    RawObject* raw_obj = RawObject::FromAddr(obj_addr);
+    if (raw_obj->FindObject(visitor)) {
+      return raw_obj;
     }
     page = page->next();
   }
   return Object::null();
 }
 
 
 void PageSpace::WriteProtect(bool read_only) {
   HeapPage* page = pages_;
   while (page != NULL) {
@@ skipping 30 matching lines @@
   }
   Timer timer(true, "MarkSweep");
   timer.Start();
   int64_t start = OS::GetCurrentTimeMillis();
 
   // Mark all reachable old-gen objects.
   GCMarker marker(heap_);
   marker.MarkObjects(isolate, this, invoke_api_callbacks);
 
   // Reset the bump allocation page to unused.
-  bump_page_ = NULL;
   // Reset the freelists and setup sweeping.
   freelist_.Reset();
   GCSweeper sweeper(heap_);
   intptr_t in_use = 0;
 
   HeapPage* prev_page = NULL;
   HeapPage* page = pages_;
   while (page != NULL) {
     intptr_t page_in_use = sweeper.SweepPage(page, &freelist_);
     HeapPage* next_page = page->next();
@@ skipping 178 matching lines @@
     return 0;
   } else {
     ASSERT(total_time >= gc_time);
     int result= static_cast<int>((static_cast<double>(gc_time) /
                              static_cast<double>(total_time)) * 100);
     return result;
   }
 }
 
 }  // namespace dart