Put empty pages discovered during sweeping to the end of the list of pages...

src/spaces.cc

 // Copyright 2006-2008 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 506 matching lines @@
   size_t chunk_size = chunks_[chunk_id].size();
   Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);
   ASSERT(pages_in_chunk <=
         ((OffsetFrom(high) - OffsetFrom(low)) / Page::kPageSize));
 #endif
 
   Address page_addr = low;
   for (int i = 0; i < pages_in_chunk; i++) {
     Page* p = Page::FromAddress(page_addr);
     p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;
-    p->is_normal_page = 1;
+    p->SetIsLargeObjectPage(false);
     page_addr += Page::kPageSize;
   }
 
   // Set the next page of the last page to 0.
   Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);
   last_page->opaque_header = OffsetFrom(0) | chunk_id;
 
   return Page::FromAddress(low);
 }
 
@@ skipping 23 matching lines @@
     first_page = GetNextPage(FindLastPageInSameChunk(first_page));
 
     // Free the current chunk.
     DeleteChunk(chunk_id);
   }
 
   return page_to_return;
 }
 
 
+void MemoryAllocator::FreeAllPages(PagedSpace* space) {
+  for (int i = 0, length = chunks_.length(); i < length; i++) {
+    if (chunks_[i].owner() == space) {
+      DeleteChunk(i);
+    }
+  }
+}
+
+
 void MemoryAllocator::DeleteChunk(int chunk_id) {
   ASSERT(IsValidChunk(chunk_id));
 
   ChunkInfo& c = chunks_[chunk_id];
 
   // We cannot free a chunk contained in the initial chunk because it was not
   // allocated with AllocateRawMemory.  Instead we uncommit the virtual
   // memory.
   if (InInitialChunk(c.address())) {
     // TODO(1240712): VirtualMemory::Uncommit has a return value which
@@ skipping 34 matching lines @@
 
 #ifdef DEBUG
 void MemoryAllocator::ReportStatistics() {
   float pct = static_cast<float>(capacity_ - size_) / capacity_;
   PrintF("  capacity: %d, used: %d, available: %%%d\n\n",
          capacity_, size_, static_cast<int>(pct*100));
 }
 #endif
 
 
+void MemoryAllocator::RelinkPageListInChunkOrder(PagedSpace* space,
+                                                 Page** first_page,
+                                                 Page** last_page,
+                                                 Page** last_page_in_use) {
+  Page* first = NULL;
+  Page* last = NULL;
+
+  for (int i = 0, length = chunks_.length(); i < length; i++) {
+    ChunkInfo& chunk = chunks_[i];
+
+    if (chunk.owner() == space) {
+      if (first == NULL) {
+        Address low = RoundUp(chunk.address(), Page::kPageSize);
+        first = Page::FromAddress(low);
+      }
+      last = RelinkPagesInChunk(i,
+                                chunk.address(),
+                                chunk.size(),
+                                last,
+                                last_page_in_use);
+    }
+  }
+
+  if (first_page != NULL) {
+    *first_page = first;
+  }
+
+  if (last_page != NULL) {
+    *last_page = last;
+  }
+}
+
+
+Page* MemoryAllocator::RelinkPagesInChunk(int chunk_id,
+                                          Address chunk_start,
+                                          int chunk_size,
+                                          Page* prev,
+                                          Page** last_page_in_use) {
+  Address page_addr = RoundUp(chunk_start, Page::kPageSize);
+  int pages_in_chunk = PagesInChunk(chunk_start, chunk_size);
+
+  if (prev->is_valid()) {
+    SetNextPage(prev, Page::FromAddress(page_addr));
+  }
+
+  for (int i = 0; i < pages_in_chunk; i++) {
+    Page* p = Page::FromAddress(page_addr);
+    p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;
+    page_addr += Page::kPageSize;
+
+    if (p->WasInUseBeforeMC()) {
+      *last_page_in_use = p;
+    }
+  }
+
+  // Set the next page of the last page to 0.
+  Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);
+  last_page->opaque_header = OffsetFrom(0) | chunk_id;
+
+  if (last_page->WasInUseBeforeMC()) {
+    *last_page_in_use = last_page;
+  }
+
+  return last_page;
+}
+
+
+
 // -----------------------------------------------------------------------------
 // PagedSpace implementation
 
 PagedSpace::PagedSpace(int max_capacity,
                        AllocationSpace id,
                        Executability executable)
     : Space(id, executable) {
   max_capacity_ = (RoundDown(max_capacity, Page::kPageSize) / Page::kPageSize)
                   * Page::kObjectAreaSize;
   accounting_stats_.Clear();
@@ skipping 35 matching lines @@
   // Sequentially initialize remembered sets in the newly allocated
   // pages and cache the current last page in the space.
   for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {
     p->ClearRSet();
     last_page_ = p;
   }
 
   // Use first_page_ for allocation.
   SetAllocationInfo(&allocation_info_, first_page_);
 
+  page_list_is_chunk_ordered_ = true;
+
   return true;
 }
 
 
 bool PagedSpace::HasBeenSetup() {
   return (Capacity() > 0);
 }
 
 
 void PagedSpace::TearDown() {
-  first_page_ = MemoryAllocator::FreePages(first_page_);
-  ASSERT(!first_page_->is_valid());
-
+  MemoryAllocator::FreeAllPages(this);
+  first_page_ = NULL;
   accounting_stats_.Clear();
 }
 
 
 #ifdef ENABLE_HEAP_PROTECTION
 
 void PagedSpace::Protect() {
   Page* page = first_page_;
   while (page->is_valid()) {
     MemoryAllocator::ProtectChunkFromPage(page);
@@ skipping 164 matching lines @@
   int count = 0;
   for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {
     count++;
   }
   return count;
 }
 #endif
 
 
 void PagedSpace::Shrink() {
+  if (!page_list_is_chunk_ordered_) {
+    // We can't shrink space if pages is not chunk-ordered
+    // (see comment for class MemoryAllocator for definition).
+    return;
+  }
+
   // Release half of free pages.
   Page* top_page = AllocationTopPage();
   ASSERT(top_page->is_valid());
 
   // Count the number of pages we would like to free.
   int pages_to_free = 0;
   for (Page* p = top_page->next_page(); p->is_valid(); p = p->next_page()) {
     pages_to_free++;
   }
 
@@ skipping 888 matching lines @@
   head_ = node->next();
   available_ -= object_size_;
   return node;
 }
 
 
 // -----------------------------------------------------------------------------
 // OldSpace implementation
 
 void OldSpace::PrepareForMarkCompact(bool will_compact) {
+  // Call prepare of the super class.
+  PagedSpace::PrepareForMarkCompact(will_compact);
+
   if (will_compact) {
     // Reset relocation info.  During a compacting collection, everything in
     // the space is considered 'available' and we will rediscover live data
     // and waste during the collection.
     MCResetRelocationInfo();
     ASSERT(Available() == Capacity());
   } else {
     // During a non-compacting collection, everything below the linear
     // allocation pointer is considered allocated (everything above is
     // available) and we will rediscover available and wasted bytes during
@@ skipping 50 matching lines @@
 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::FreePages(Page* prev, Page* last) {
+  if (last == AllocationTopPage()) {
+    // Pages are already at the end of used pages.
+    return;
+  }
+
+  Page* first = NULL;
+
+  // Remove pages from the list.
+  if (prev == NULL) {
+    first = first_page_;
+    first_page_ = last->next_page();
+  } else {
+    first = prev->next_page();
+    MemoryAllocator::SetNextPage(prev, last->next_page());
+  }
+
+  // Attach it after the last page.
+  MemoryAllocator::SetNextPage(last_page_, first);
+  last_page_ = last;
+  MemoryAllocator::SetNextPage(last, NULL);
+
+  // Clean them up.
+  do {
+    first->ClearRSet();
+    first = first->next_page();
+  } while (first != NULL);
+
+  // Order of pages in this space might no longer be consistent with
+  // order of pages in chunks.
+  page_list_is_chunk_ordered_ = false;
+}
+
+
+void PagedSpace::PrepareForMarkCompact(bool will_compact) {
+  if (will_compact) {
+    // MarkCompact collector relies on WAS_IN_USE_BEFORE_MC page flag
+    // to skip unused pages. Update flag value for all pages in space.
+    PageIterator it(this, PageIterator::ALL_PAGES);
+    Page* last_in_use = AllocationTopPage();
+    bool in_use = true;
+
+    while (it.has_next()) {
+      Page* p = it.next();
+      p->SetWasInUseBeforeMC(in_use);
+      if (p == last_in_use) {
+        // We passed a page containing allocation top. All consequent
+        // pages are not used.
+        in_use = false;
+      }
+    }
+
+    if (!page_list_is_chunk_ordered_) {
+      Page* new_last_in_use = NULL;
+      MemoryAllocator::RelinkPageListInChunkOrder(this,
+                                                  &first_page_,
+                                                  &last_page_,
+                                                  &new_last_in_use);
+      ASSERT(new_last_in_use != NULL);
+
+      if (new_last_in_use != last_in_use) {
+        // Current allocation top points to a page which is now in the middle
+        // of page list. We should move allocation top forward to the new last
+        // used page so various object iterators will continue to work properly.
+
+        int size_in_bytes =
+            last_in_use->ObjectAreaEnd() - last_in_use->AllocationTop();
+
+        if (size_in_bytes > 0) {
+          // There is still some space left on this page. Create a fake
+          // object which will occupy all free space on this page.
+          // Otherwise iterators would not be able to scan this page
+          // correctly.
+
+          FreeListNode* node =
+              FreeListNode::FromAddress(last_in_use->AllocationTop());
+          node->set_size(last_in_use->ObjectAreaEnd() -
+                         last_in_use->AllocationTop());
+        }
+
+        // New last in use page was in the middle of the list before
+        // sorting so it full.
+        SetTop(new_last_in_use->AllocationTop(),
+               new_last_in_use->AllocationTop());
+
+        ASSERT(AllocationTopPage() == new_last_in_use);
+      }
+
+      page_list_is_chunk_ordered_ = true;
+    }
+  }
+}
+
+
 bool PagedSpace::ReserveSpace(int bytes) {
   Address limit = allocation_info_.limit;
   Address top = allocation_info_.top;
   if (limit - top >= bytes) return true;
 
   // There wasn't enough space in the current page.  Lets put the rest
   // of the page on the free list and start a fresh page.
   PutRestOfCurrentPageOnFreeList(TopPageOf(allocation_info_));
 
   Page* reserved_page = TopPageOf(allocation_info_);
@@ skipping 391 matching lines @@
 }
 
 
 void OldSpace::PrintRSet() { DoPrintRSet("old"); }
 #endif
 
 // -----------------------------------------------------------------------------
 // FixedSpace implementation
 
 void FixedSpace::PrepareForMarkCompact(bool will_compact) {
+  // Call prepare of the super class.
+  PagedSpace::PrepareForMarkCompact(will_compact);
+
   if (will_compact) {
     // Reset relocation info.
     MCResetRelocationInfo();
 
     // During a compacting collection, everything in the space is considered
     // 'available' (set by the call to MCResetRelocationInfo) and we will
     // rediscover live and wasted bytes during the collection.
     ASSERT(Available() == Capacity());
   } else {
     // During a non-compacting collection, everything below the linear
@@ skipping 322 matching lines @@
   first_chunk_ = chunk;
 
   // Set the object address and size in the page header and clear its
   // remembered set.
   Page* page = Page::FromAddress(RoundUp(chunk->address(), Page::kPageSize));
   Address object_address = page->ObjectAreaStart();
   // Clear the low order bit of the second word in the page to flag it as a
   // large object page.  If the chunk_size happened to be written there, its
   // low order bit should already be clear.
   ASSERT((chunk_size & 0x1) == 0);
-  page->is_normal_page &= ~0x1;
+  page->SetIsLargeObjectPage(true);
   page->ClearRSet();
   int extra_bytes = requested_size - object_size;
   if (extra_bytes > 0) {
     // The extra memory for the remembered set should be cleared.
     memset(object_address + object_size, 0, extra_bytes);
   }
 
   return HeapObject::FromAddress(object_address);
 }
 
@@ skipping 254 matching lines @@
                      reinterpret_cast<Object**>(object->address()
                                                 + Page::kObjectAreaSize),
                      allocation_top);
       PrintF("\n");
     }
   }
 }
 #endif  // DEBUG
 
 } }  // namespace v8::internal