Fix Heap::Shrink to ensure that it does not free pages that are still in use.

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 640 matching lines @@
 // -----------------------------------------------------------------------------
 // PagedSpace implementation
 
 PagedSpace::PagedSpace(Heap* heap,
                        intptr_t max_capacity,
                        AllocationSpace id,
                        Executability executable)
     : Space(heap, id, executable),
       free_list_(this),
       was_swept_conservatively_(false),
-      first_unswept_page_(Page::FromAddress(NULL)),
-      last_unswept_page_(Page::FromAddress(NULL)) {
+      first_unswept_page_(Page::FromAddress(NULL)) {
   max_capacity_ = (RoundDown(max_capacity, Page::kPageSize) / Page::kPageSize)
                   * Page::kObjectAreaSize;
   accounting_stats_.Clear();
 
   allocation_info_.top = NULL;
   allocation_info_.limit = NULL;
 
   anchor_.InitializeAsAnchor(this);
 }
 
@@ skipping 74 matching lines @@
     it.next();
     count++;
   }
   return count;
 }
 #endif
 
 
 void PagedSpace::ReleasePage(Page* page) {
   ASSERT(page->LiveBytes() == 0);
+
+  // Adjust list of unswept pages if the page is it's head or tail.
+  if (first_unswept_page_ == page) {
+    first_unswept_page_ = page->next_page();
+    if (first_unswept_page_ == anchor()) {
+      first_unswept_page_ = Page::FromAddress(NULL);
+    }
+  }
+
+  if (page->WasSwept()) {
+    intptr_t size = free_list_.EvictFreeListItems(page);
+    accounting_stats_.AllocateBytes(size);
+    ASSERT_EQ(Page::kObjectAreaSize, static_cast<int>(size));
+  }
+
   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);
 }
 
 
 void PagedSpace::ReleaseAllUnusedPages() {
   PageIterator it(this);
   while (it.has_next()) {
     Page* page = it.next();
-    if (page->LiveBytes() == 0) {
-      ReleasePage(page);
+    if (!page->WasSwept()) {
+      if (page->LiveBytes() == 0) ReleasePage(page);
+    } else {
+      HeapObject* obj = HeapObject::FromAddress(page->body());
+      if (obj->IsFreeSpace() &&
+          FreeSpace::cast(obj)->size() == Page::kObjectAreaSize) {
+        // Sometimes we allocate memory from free list but don't
+        // immediately initialize it (e.g. see PagedSpace::ReserveSpace
+        // called from Heap::ReserveSpace that can cause GC before
+        // reserved space is actually initialized).
+        // Thus we can't simply assume that obj represents a valid
+        // node still owned by a free list
+        // Instead we should verify that the page is fully covered
+        // by free list items.

[Michael Starzinger, 2011/11/10 12:52:45]

Wow, that's tricky. Nice catch!

+        FreeList::SizeStats sizes;
+        free_list_.CountFreeListItems(page, &sizes);
+        if (sizes.Total() == Page::kObjectAreaSize) {
+          ReleasePage(page);
+        }
+      }
     }
   }
   heap()->FreeQueuedChunks();
 }
 
 
 #ifdef DEBUG
 void PagedSpace::Print() { }
 #endif
 
@@ skipping 1077 matching lines @@
     if (Page::FromAddress(n->address()) == p) {
       FreeSpace* free_space = reinterpret_cast<FreeSpace*>(n);
       sum += free_space->Size();
     }
     n = n->next();
   }
   return sum;
 }
 
 
-void FreeList::CountFreeListItems(Page* p, intptr_t* sizes) {
-  sizes[0] = CountFreeListItemsInList(small_list_, p);
-  sizes[1] = CountFreeListItemsInList(medium_list_, p);
-  sizes[2] = CountFreeListItemsInList(large_list_, p);
-  sizes[3] = CountFreeListItemsInList(huge_list_, p);
+void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
+  sizes->huge_size_ = CountFreeListItemsInList(huge_list_, p);
+  if (sizes->huge_size_ < Page::kObjectAreaSize) {
+    sizes->small_size_ = CountFreeListItemsInList(small_list_, p);
+    sizes->medium_size_ = CountFreeListItemsInList(medium_list_, p);
+    sizes->large_size_ = CountFreeListItemsInList(large_list_, p);
+  } else {
+    sizes->small_size_ = 0;
+    sizes->medium_size_ = 0;
+    sizes->large_size_ = 0;
+  }
 }
 
+
+static intptr_t EvictFreeListItemsInList(FreeListNode** n, Page* p) {
+  intptr_t sum = 0;
+  while (*n != NULL) {
+    if (Page::FromAddress((*n)->address()) == p) {
+      FreeSpace* free_space = reinterpret_cast<FreeSpace*>(*n);
+      sum += free_space->Size();
+      *n = (*n)->next();
+    } else {
+      n = (*n)->next_address();
+    }
+  }
+  return sum;
+}
+
+
+intptr_t FreeList::EvictFreeListItems(Page* p) {
+  intptr_t sum = EvictFreeListItemsInList(&huge_list_, p);
+
+  if (sum < Page::kObjectAreaSize) {
+    sum += EvictFreeListItemsInList(&small_list_, p) +
+        EvictFreeListItemsInList(&medium_list_, p) +
+        EvictFreeListItemsInList(&large_list_, p);
+  }
+
+  available_ -= sum;
+
+  return sum;
+}
+
+
 #ifdef DEBUG
 intptr_t FreeList::SumFreeList(FreeListNode* cur) {
   intptr_t sum = 0;
   while (cur != NULL) {
     ASSERT(cur->map() == HEAP->raw_unchecked_free_space_map());
     FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(cur);
     sum += cur_as_free_space->Size();
     cur = cur->next();
   }
   return sum;
@@ skipping 66 matching lines @@
   // 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);
   SetTop(NULL, NULL);
 
   // Stop lazy sweeping and clear marking bits for unswept pages.
   if (first_unswept_page_ != NULL) {
-    Page* last = last_unswept_page_;
     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()) {
         Bitmap::Clear(p);
         if (FLAG_gc_verbose) {
           PrintF("Sweeping 0x%" V8PRIxPTR " lazily abandoned.\n",
                  reinterpret_cast<intptr_t>(p));
         }
       }
       p = p->next_page();
-    } while (p != last);
+    } while (p != anchor());
   }
-  first_unswept_page_ = last_unswept_page_ = Page::FromAddress(NULL);
+  first_unswept_page_ = Page::FromAddress(NULL);
 
   // Clear the free list before a full GC---it will be rebuilt afterward.
   free_list_.Reset();
 }
 
 
 bool PagedSpace::ReserveSpace(int size_in_bytes) {
   ASSERT(size_in_bytes <= Page::kMaxHeapObjectSize);
   ASSERT(size_in_bytes == RoundSizeDownToObjectAlignment(size_in_bytes));
   Address current_top = allocation_info_.top;
@@ skipping 20 matching lines @@
 // doesn't know that memory was 'promised' to large object space.
 bool LargeObjectSpace::ReserveSpace(int bytes) {
   return heap()->OldGenerationSpaceAvailable() >= bytes;
 }
 
 
 bool PagedSpace::AdvanceSweeper(intptr_t bytes_to_sweep) {
   if (IsSweepingComplete()) return true;
 
   intptr_t freed_bytes = 0;
-  Page* last = last_unswept_page_;
   Page* p = first_unswept_page_;
   do {
     Page* next_page = p->next_page();
     if (ShouldBeSweptLazily(p)) {
       if (FLAG_gc_verbose) {
         PrintF("Sweeping 0x%" V8PRIxPTR " lazily advanced.\n",
                reinterpret_cast<intptr_t>(p));
       }
       freed_bytes += MarkCompactCollector::SweepConservatively(this, p);
     }
     p = next_page;
-  } while (p != last && freed_bytes < bytes_to_sweep);
+  } while (p != anchor() && freed_bytes < bytes_to_sweep);
 
-  if (p == last) {
-    last_unswept_page_ = first_unswept_page_ = Page::FromAddress(NULL);
+  if (p == anchor()) {
+    first_unswept_page_ = Page::FromAddress(NULL);
   } else {
     first_unswept_page_ = p;
   }
 
   heap()->LowerOldGenLimits(freed_bytes);
 
   heap()->FreeQueuedChunks();
 
   return IsSweepingComplete();
 }
@@ skipping 516 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal