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

src/mark-compact.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 1037 matching lines @@
 }
 
 
 template<MarkCompactCollector::AllocationFunction Alloc,
          MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive>
 void MarkCompactCollector::EncodeForwardingAddressesInPagedSpace(
     PagedSpace* space) {
   PageIterator it(space, PageIterator::PAGES_IN_USE);
   while (it.has_next()) {
     Page* p = it.next();
-    // The offset of each live object in the page from the first live object
-    // in the page.
-    int offset = 0;
-    EncodeForwardingAddressesInRange<Alloc,
-                                     EncodeForwardingAddressInPagedSpace,
-                                     ProcessNonLive>(
-        p->ObjectAreaStart(),
-        p->AllocationTop(),
-        &offset);
+
+    if (p->WasInUseBeforeMC()) {
+      // The offset of each live object in the page from the first live object
+      // in the page.
+      int offset = 0;
+      EncodeForwardingAddressesInRange<Alloc,
+                                       EncodeForwardingAddressInPagedSpace,
+                                       ProcessNonLive>(
+          p->ObjectAreaStart(),
+          p->AllocationTop(),
+          &offset);
+    } else {
+      // Mark whole unused page as a free region.
+      EncodeFreeRegion(p->ObjectAreaStart(),
+                       p->AllocationTop() - p->ObjectAreaStart());
+    }
   }
 }
 
 
 // We scavange new space simultaneously with sweeping. This is done in two
 // passes.
 // The first pass migrates all alive objects from one semispace to another or
 // promotes them to old space. Forwading address is written directly into
 // first word of object without any encoding. If object is dead we are writing
 // NULL as a forwarding address.
@@ skipping 193 matching lines @@
       &UpdateNewSpaceReferenceInExternalStringTableEntry);
 
   // All pointers were updated. Update auxiliary allocation info.
   Heap::IncrementYoungSurvivorsCounter(survivors_size);
   space->set_age_mark(space->top());
 }
 
 
 static void SweepSpace(PagedSpace* space, DeallocateFunction dealloc) {
   PageIterator it(space, PageIterator::PAGES_IN_USE);
+
+  // During sweeping of paged space we are trying to find longest sequences
+  // of pages without live objects and free them (instead of putting them on
+  // the free list).
+  Page* prev = NULL;  // Page preceding current.
+  Page* first_empty_page = NULL;  // First empty page in a sequence.
+  Page* prec_first_empty_page = NULL;  // Page preceding first empty page.
+
+  // If last used page of space ends with a sequence of dead objects
+  // we can adjust allocation top instead of puting this free area into
+  // the free list. Thus during sweeping we keep track of such areas
+  // and defer their deallocation until the sweeping of the next page
+  // is done: if one of the next pages contains live objects we have
+  // to put such area into the free list.
+  Address last_free_start = NULL;
+  int last_free_size = 0;
+
   while (it.has_next()) {
     Page* p = it.next();
 
     bool is_previous_alive = true;
     Address free_start = NULL;
     HeapObject* object;
 
     for (Address current = p->ObjectAreaStart();
          current < p->AllocationTop();
          current += object->Size()) {
       object = HeapObject::FromAddress(current);
       if (object->IsMarked()) {
         object->ClearMark();
         MarkCompactCollector::tracer()->decrement_marked_count();
+
         if (!is_previous_alive) {  // Transition from free to live.
-          dealloc(free_start, static_cast<int>(current - free_start));
+          dealloc(free_start, static_cast<int>(current - free_start), true);
           is_previous_alive = true;
         }
       } else {
         MarkCompactCollector::ReportDeleteIfNeeded(object);
         if (is_previous_alive) {  // Transition from live to free.
           free_start = current;
           is_previous_alive = false;
         }
       }
       // The object is now unmarked for the call to Size() at the top of the
       // loop.
     }
 
-    // If the last region was not live we need to deallocate from
-    // free_start to the allocation top in the page.
-    if (!is_previous_alive) {
-      int free_size = static_cast<int>(p->AllocationTop() - free_start);
-      if (free_size > 0) {
-        dealloc(free_start, free_size);
+    bool page_is_empty = (p->ObjectAreaStart() == p->AllocationTop())
+        || (!is_previous_alive && free_start == p->ObjectAreaStart());
+
+    if (page_is_empty) {
+      // This page is empty. Check whether we are in the middle of
+      // sequence of empty pages and start one if not.
+      if (first_empty_page == NULL) {
+        first_empty_page = p;
+        prec_first_empty_page = prev;
+      }
+
+      if (!is_previous_alive) {
+        // There are dead objects on this page. Update space accounting stats
+        // without putting anything into free list.
+        int size_in_bytes = static_cast<int>(p->AllocationTop() - free_start);
+        if (size_in_bytes > 0) {
+          dealloc(free_start, size_in_bytes, false);
+        }
+      }
+    } else {
+      // This page is not empty. Sequence of empty pages ended on the previous
+      // one.
+      if (first_empty_page != NULL) {
+        space->FreePages(prec_first_empty_page, prev);
+        prec_first_empty_page = first_empty_page = NULL;
+      }
+
+      // If there is a free ending area on one of the previous pages we have
+      // deallocate that area and put it on the free list.
+      if (last_free_size > 0) {
+        dealloc(last_free_start, last_free_size, true);
+        last_free_start = NULL;
+        last_free_size  = 0;
+      }
+
+      // If the last region of this page was not live we remember it.
+      if (!is_previous_alive) {
+        ASSERT(last_free_size == 0);
+        last_free_size = static_cast<int>(p->AllocationTop() - free_start);
+        last_free_start = free_start;
       }
     }
+
+    prev = p;
+  }
+
+  // We reached end of space. See if we need to adjust allocation top.
+  Address new_allocation_top = NULL;
+
+  if (first_empty_page != NULL) {
+    // Last used pages in space are empty. We can move allocation top backwards
+    // to the beginning of first empty page.
+    ASSERT(prev == space->AllocationTopPage());
+
+    new_allocation_top = first_empty_page->ObjectAreaStart();
+  }
+
+  if (last_free_size > 0) {
+    // There was a free ending area on the previous page.
+    // Deallocate it without putting it into freelist and move allocation
+    // top to the beginning of this free area.
+    dealloc(last_free_start, last_free_size, false);
+    new_allocation_top = last_free_start;
+  }
+
+  if (new_allocation_top != NULL) {
+    Page* new_allocation_top_page = Page::FromAllocationTop(new_allocation_top);
+
+    ASSERT(((first_empty_page == NULL) &&
+            (new_allocation_top_page == space->AllocationTopPage())) ||
+           ((first_empty_page != NULL) && (last_free_size > 0) &&
+            (new_allocation_top_page == prec_first_empty_page)) ||
+           ((first_empty_page != NULL) && (last_free_size == 0) &&
+            (new_allocation_top_page == first_empty_page)));
+
+    space->SetTop(new_allocation_top,
+                  new_allocation_top_page->ObjectAreaEnd());
   }
 }
 
 
 void MarkCompactCollector::DeallocateOldPointerBlock(Address start,
-                                                     int size_in_bytes) {
+                                                     int size_in_bytes,
+                                                     bool add_to_freelist) {
   Heap::ClearRSetRange(start, size_in_bytes);
-  Heap::old_pointer_space()->Free(start, size_in_bytes);
+  Heap::old_pointer_space()->Free(start, size_in_bytes, add_to_freelist);
 }
 
 
 void MarkCompactCollector::DeallocateOldDataBlock(Address start,
-                                                  int size_in_bytes) {
-  Heap::old_data_space()->Free(start, size_in_bytes);
+                                                  int size_in_bytes,
+                                                  bool add_to_freelist) {
+  Heap::old_data_space()->Free(start, size_in_bytes, add_to_freelist);
 }
 
 
 void MarkCompactCollector::DeallocateCodeBlock(Address start,
-                                               int size_in_bytes) {
-  Heap::code_space()->Free(start, size_in_bytes);
+                                               int size_in_bytes,
+                                               bool add_to_freelist) {
+  Heap::code_space()->Free(start, size_in_bytes, add_to_freelist);
 }
 
 
 void MarkCompactCollector::DeallocateMapBlock(Address start,
-                                              int size_in_bytes) {
+                                              int size_in_bytes,
+                                              bool add_to_freelist) {
   // Objects in map space are assumed to have size Map::kSize and a
   // valid map in their first word.  Thus, we break the free block up into
   // chunks and free them separately.
   ASSERT(size_in_bytes % Map::kSize == 0);
   Heap::ClearRSetRange(start, size_in_bytes);
   Address end = start + size_in_bytes;
   for (Address a = start; a < end; a += Map::kSize) {
-    Heap::map_space()->Free(a);
+    Heap::map_space()->Free(a, add_to_freelist);
   }
 }
 
 
 void MarkCompactCollector::DeallocateCellBlock(Address start,
-                                               int size_in_bytes) {
+                                               int size_in_bytes,
+                                               bool add_to_freelist) {
   // Free-list elements in cell space are assumed to have a fixed size.
   // We break the free block into chunks and add them to the free list
   // individually.
   int size = Heap::cell_space()->object_size_in_bytes();
   ASSERT(size_in_bytes % size == 0);
   Heap::ClearRSetRange(start, size_in_bytes);
   Address end = start + size_in_bytes;
   for (Address a = start; a < end; a += size) {
-    Heap::cell_space()->Free(a);
+    Heap::cell_space()->Free(a, add_to_freelist);
   }
 }
 
 
 void MarkCompactCollector::EncodeForwardingAddresses() {
   ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES);
   // Objects in the active semispace of the young generation may be
   // relocated to the inactive semispace (if not promoted).  Set the
   // relocation info to the beginning of the inactive semispace.
   Heap::new_space()->MCResetRelocationInfo();
@@ skipping 835 matching lines @@
 #ifdef ENABLE_LOGGING_AND_PROFILING
   if (obj->IsCode()) {
     PROFILE(CodeDeleteEvent(obj->address()));
   } else if (obj->IsJSFunction()) {
     PROFILE(FunctionDeleteEvent(obj->address()));
   }
 #endif
 }
 
 } }  // namespace v8::internal