Split single slots buffer into per page slots buffers.

src/mark-compact.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 42 matching lines @@
 // -------------------------------------------------------------------------
 // MarkCompactCollector
 
 MarkCompactCollector::MarkCompactCollector() :  // NOLINT
 #ifdef DEBUG
       state_(IDLE),
 #endif
       sweep_precisely_(false),
       compacting_(false),
       tracer_(NULL),
+      migration_slots_buffer_(NULL),
 #ifdef DEBUG
       live_young_objects_size_(0),
       live_old_pointer_objects_size_(0),
       live_old_data_objects_size_(0),
       live_code_objects_size_(0),
       live_map_objects_size_(0),
       live_cell_objects_size_(0),
       live_lo_objects_size_(0),
       live_bytes_(0),
 #endif
@@ skipping 152 matching lines @@
   evacuation_candidates_.Add(p);
 }
 
 
 bool MarkCompactCollector::StartCompaction() {
   // Don't start compaction if we are in the middle of incremental
   // marking cycle. We did not collect any slots.
   if (!compacting_ && !heap_->incremental_marking()->IsMarking()) {
     ASSERT(evacuation_candidates_.length() == 0);
 
-    // TODO(gc) Shrink slots buffer when we receive low memory notification.
-    slots_buffer_.Clear();
-
     CollectEvacuationCandidates(heap()->old_pointer_space());
     CollectEvacuationCandidates(heap()->old_data_space());
 
     heap()->old_pointer_space()->EvictEvacuationCandidatesFromFreeLists();
     heap()->old_data_space()->EvictEvacuationCandidatesFromFreeLists();
 
     compacting_ = evacuation_candidates_.length() > 0;
   }
 
   return compacting_;
@@ skipping 129 matching lines @@
   new_mark_bit.Set();
   return true;
 }
 
 
 void MarkCompactCollector::CollectEvacuationCandidates(PagedSpace* space) {
   ASSERT(space->identity() == OLD_POINTER_SPACE ||
          space->identity() == OLD_DATA_SPACE);
 
   PageIterator it(space);
+  if (it.has_next()) it.next();  // Never compact the first page.
   while (it.has_next()) {
     Page* p = it.next();
     if (space->IsFragmented(p)) {
       AddEvacuationCandidate(p);
     } else {
       p->ClearEvacuationCandidate();
     }
   }
 }
 
@@ skipping 1659 matching lines @@
 
     for (int remaining = size / kPointerSize; remaining > 0; remaining--) {
       Object* value = Memory::Object_at(src_slot);
 
       Memory::Object_at(dst_slot) = value;
 
       if (heap_->InNewSpace(value)) {
         heap_->store_buffer()->Mark(dst_slot);
       } else if (value->IsHeapObject() &&
                  MarkCompactCollector::IsOnEvacuationCandidate(value)) {
-        slots_buffer_.Add(reinterpret_cast<Object**>(dst_slot));
+        SlotsBuffer::AddTo(&slots_buffer_allocator_,
+                           &migration_slots_buffer_,
+                           reinterpret_cast<Object**>(dst_slot),
+                           SlotsBuffer::IGNORE_OVERFLOW);
       }
 
       src_slot += kPointerSize;
       dst_slot += kPointerSize;
     }
   } else {
     heap_->CopyBlock(dst, src, size);
   }
   Memory::Address_at(src) = dst;
 }
@@ skipping 184 matching lines @@
   }
 
   heap_->IncrementYoungSurvivorsCounter(survivors_size);
   new_space->set_age_mark(new_space->top());
 }
 
 
 void MarkCompactCollector::EvacuateLiveObjectsFromPage(Page* p) {
   AlwaysAllocateScope always_allocate;
 
-  ASSERT(p->IsEvacuationCandidate() && !p->WasEvacuated());
+  ASSERT(p->IsEvacuationCandidate() && !p->WasSwept());
 
   PagedSpace* space = static_cast<PagedSpace*>(p->owner());
 
   MarkBit::CellType* cells = p->markbits()->cells();
 
   int last_cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
 
@@ skipping 28 matching lines @@
       ASSERT(object->map_word().IsForwardingAddress());
     }
   }
 }
 
 
 void MarkCompactCollector::EvacuatePages() {
   int npages = evacuation_candidates_.length();
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
-    EvacuateLiveObjectsFromPage(p);
+    ASSERT(p->IsEvacuationCandidate() ||
+           p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
+    if (p->IsEvacuationCandidate()) {
+      EvacuateLiveObjectsFromPage(p);
+    }
   }
 }
 
 
 class EvacuationWeakObjectRetainer : public WeakObjectRetainer {
  public:
   virtual Object* RetainAs(Object* object) {
     if (object->IsHeapObject()) {
       HeapObject* heap_object = HeapObject::cast(object);
       MapWord map_word = heap_object->map_word();
       if (map_word.IsForwardingAddress()) {
         return map_word.ToForwardingAddress();
       }
     }
     return object;
   }
 };
 
 
+static inline void UpdateSlot(Object** slot) {
+  Object* obj = *slot;
+  if (!obj->IsHeapObject()) return;
+
+  HeapObject* heap_obj = HeapObject::cast(obj);
+
+  MapWord map_word = heap_obj->map_word();
+  if (map_word.IsForwardingAddress()) {
+    ASSERT(MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+    *slot = map_word.ToForwardingAddress();
+    ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+  }
+}
+
+
+static inline void UpdateSlotsInRange(Object** start, Object** end) {
+  for (Object** slot = start;
+       slot < end;
+       slot++) {
+    Object* obj = *slot;
+    if (obj->IsHeapObject() &&
+        MarkCompactCollector::IsOnEvacuationCandidate(obj)) {
+      MapWord map_word = HeapObject::cast(obj)->map_word();
+      if (map_word.IsForwardingAddress()) {
+        *slot = map_word.ToForwardingAddress();
+        ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+      }
+    }
+  }
+}
+
+
+static void UpdateSlotsOnPage(Page* p, ObjectVisitor* visitor) {
+  // TODO(gc) this is basically clone of SweepPrecisely
+  PagedSpace* space = static_cast<PagedSpace*>(p->owner());
+  MarkBit::CellType* cells = p->markbits()->cells();
+
+  p->ClearFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
+  p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
+  p->MarkSwept();
+
+  int last_cell_index =
+      Bitmap::IndexToCell(
+          Bitmap::CellAlignIndex(
+              p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
+
+  int cell_index = Page::kFirstUsedCell;
+  Address free_start = p->ObjectAreaStart();
+  ASSERT(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
+  Address object_address = p->ObjectAreaStart();
+  int offsets[16];
+
+  for (cell_index = Page::kFirstUsedCell;
+       cell_index < last_cell_index;
+       cell_index++, object_address += 32 * kPointerSize) {
+    ASSERT((unsigned)cell_index ==
+        Bitmap::IndexToCell(
+            Bitmap::CellAlignIndex(
+                p->AddressToMarkbitIndex(object_address))));
+    int live_objects = MarkWordToObjectStarts(cells[cell_index], offsets);
+    int live_index = 0;
+    for ( ; live_objects != 0; live_objects--) {
+      Address free_end = object_address + offsets[live_index++] * kPointerSize;
+      if (free_end != free_start) {
+        space->Free(free_start, free_end - free_start);
+      }
+      HeapObject* live_object = HeapObject::FromAddress(free_end);
+      ASSERT(Marking::IsBlack(Marking::MarkBitFrom(live_object)));
+      int size = live_object->Size();
+      UpdateSlotsInRange(HeapObject::RawField(live_object, kPointerSize),
+                         HeapObject::RawField(live_object, size));
+      free_start = free_end + size;
+    }
+  }
+  if (free_start != p->ObjectAreaEnd()) {
+    space->Free(free_start, p->ObjectAreaEnd() - free_start);
+  }
+}
+
+
 void MarkCompactCollector::EvacuateNewSpaceAndCandidates() {
   EvacuateNewSpace();
   EvacuatePages();
 
   // Second pass: find pointers to new space and update them.
   PointersUpdatingVisitor updating_visitor(heap());
 
   // Update pointers in to space.
   SemiSpaceIterator to_it(heap()->new_space()->bottom(),
                           heap()->new_space()->top());
   for (HeapObject* object = to_it.Next();
        object != NULL;
        object = to_it.Next()) {
     Map* map = object->map();
     object->IterateBody(map->instance_type(),
                         object->SizeFromMap(map),
                         &updating_visitor);
   }
 
   // Update roots.
   heap_->IterateRoots(&updating_visitor, VISIT_ALL_IN_SWEEP_NEWSPACE);
   LiveObjectList::IterateElements(&updating_visitor);
 
   {
     StoreBufferRebuildScope scope(heap_,
                                   heap_->store_buffer(),
                                   &Heap::ScavengeStoreBufferCallback);
     heap_->store_buffer()->IteratePointersToNewSpace(&UpdatePointer);
   }
-  slots_buffer_.Update();
+
+  SlotsBuffer::UpdateSlotsRecordedIn(migration_slots_buffer_);
+  if (FLAG_trace_fragmentation) {
+    PrintF("  migration slots buffer: %d\n",
+           SlotsBuffer::SizeOfChain(migration_slots_buffer_));
+  }
+
+  int npages = evacuation_candidates_.length();
+  for (int i = 0; i < npages; i++) {
+    Page* p = evacuation_candidates_[i];
+    ASSERT(p->IsEvacuationCandidate() ||
+           p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
+
+    if (p->IsEvacuationCandidate()) {
+      SlotsBuffer::UpdateSlotsRecordedIn(p->slots_buffer());
+      if (FLAG_trace_fragmentation) {
+        PrintF("  page %p slots buffer: %d\n",
+               reinterpret_cast<void*>(p),
+               SlotsBuffer::SizeOfChain(p->slots_buffer()));
+      }
+    } else {
+      UpdateSlotsOnPage(p, &updating_visitor);
+    }
+  }
 
   // Update pointers from cells.
   HeapObjectIterator cell_iterator(heap_->cell_space());
   for (HeapObject* cell = cell_iterator.Next();
        cell != NULL;
        cell = cell_iterator.Next()) {
     if (cell->IsJSGlobalPropertyCell()) {
       Address value_address =
           reinterpret_cast<Address>(cell) +
           (JSGlobalPropertyCell::kValueOffset - kHeapObjectTag);
@@ skipping 15 matching lines @@
 
   EvacuationWeakObjectRetainer evacuation_object_retainer;
   heap()->ProcessWeakReferences(&evacuation_object_retainer);
 
 #ifdef DEBUG
   if (FLAG_verify_heap) {
     VerifyEvacuation(heap_);
   }
 #endif
 
-  int npages = evacuation_candidates_.length();
-  ASSERT(compacting_ == (npages > 0));
+  slots_buffer_allocator_.DeallocateChain(&migration_slots_buffer_);
+  ASSERT(migration_slots_buffer_ == NULL);
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
-    ASSERT(p->IsEvacuationCandidate() && !p->WasEvacuated());
+    if (!p->IsEvacuationCandidate()) continue;
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
     space->Free(p->ObjectAreaStart(), Page::kObjectAreaSize);
     p->set_scan_on_scavenge(false);
+    slots_buffer_allocator_.DeallocateChain(p->slots_buffer_address());
     p->ClearEvacuationCandidate();
-    p->SetFlag(MemoryChunk::EVACUATED);
+    p->MarkSwept();
     p->ClearFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
   }
   evacuation_candidates_.Rewind(0);
   compacting_ = false;
 }
 
 
 INLINE(static uint32_t SweepFree(PagedSpace* space,
                                  Page* p,
                                  uint32_t free_start,
@@ skipping 311 matching lines @@
 
 
 // Sweeps a space conservatively.  After this has been done the larger free
 // spaces have been put on the free list and the smaller ones have been
 // ignored and left untouched.  A free space is always either ignored or put
 // on the free list, never split up into two parts.  This is important
 // because it means that any FreeSpace maps left actually describe a region of
 // memory that can be ignored when scanning.  Dead objects other than free
 // spaces will not contain the free space map.
 int MarkCompactCollector::SweepConservatively(PagedSpace* space, Page* p) {
-  ASSERT(!p->IsEvacuationCandidate() && !p->WasEvacuated());
+  ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
 
   int freed_bytes = 0;
 
   MarkBit::CellType* cells = p->markbits()->cells();
 
   p->SetFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
 
   // This is the start of the 32 word block that we are currently looking at.
   Address block_address = p->ObjectAreaStart();
 
@@ skipping 67 matching lines @@
   return freed_bytes;
 }
 
 
 // Sweep a space precisely.  After this has been done the space can
 // be iterated precisely, hitting only the live objects.  Code space
 // is always swept precisely because we want to be able to iterate
 // over it.  Map space is swept precisely, because it is not compacted.
 static void SweepPrecisely(PagedSpace* space,
                            Page* p) {
-  ASSERT(!p->IsEvacuationCandidate() && !p->WasEvacuated());
+  ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
   MarkBit::CellType* cells = p->markbits()->cells();
 
   p->ClearFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
 
   int last_cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
 
   int cell_index = Page::kFirstUsedCell;
@@ skipping 40 matching lines @@
   int newspace_size = space->heap()->new_space()->Size();
 
   while (it.has_next()) {
     Page* p = it.next();
 
     if (p->IsEvacuationCandidate()) {
       ASSERT(evacuation_candidates_.length() > 0);
       continue;
     }
 
+    if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
+      // Will be processed in EvacuateNewSpaceAndCandidates.
+      continue;
+    }
+
     switch (sweeper) {
       case CONSERVATIVE: {
         SweepConservatively(space, p);
         break;
       }
       case LAZY_CONSERVATIVE: {
         Page* next_page = p->next_page();
         freed_bytes += SweepConservatively(space, p);
         // TODO(gc): tweak the heuristic.
         if (freed_bytes >= newspace_size && p != space->LastPage()) {
@@ skipping 140 matching lines @@
   }
 #endif
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticMarkingVisitor::Initialize();
 }
 
 
-SlotsBuffer::SlotsBuffer()
-    : buffers_(0),
-      buffer_(NULL),
-      idx_(kBufferSize),
-      buffer_idx_(-1) {
-}
-
-
-SlotsBuffer::~SlotsBuffer() {
-  for (int buffer_index = 0; buffer_index < buffers_.length(); ++buffer_index) {
-    delete buffers_[buffer_index];
+void SlotsBuffer::UpdateSlots() {
+  ObjectSlot* slots = AsArray();
+  for (int slot_idx = 0; slot_idx < idx_; ++slot_idx) {
+    UpdateSlot(slots[slot_idx]);
   }
 }
 
 
-void SlotsBuffer::Clear() {
-  idx_ = kBufferSize;
-  buffer_idx_ = -1;
+SlotsBuffer* SlotsBufferAllocator::AllocateBuffer(SlotsBuffer* next_buffer) {
+  // TODO(gc) Consider maintaining local cache of buffers.
+  SlotsBuffer* buffer = reinterpret_cast<SlotsBuffer*>(

[Erik Corry, 2011/07/08 13:02:38]

This could just be new SlotsBuffer().

+      malloc(SlotsBuffer::kSizeWords * kPointerSize));
+  buffer->Initialize(next_buffer);
+  return buffer;
 }
 
 
-void SlotsBuffer::Add(Object** slot) {
-  if (idx_ == kBufferSize) {
-    idx_ = 0;
-    buffer_idx_++;
-    if (buffer_idx_ == buffers_.length()) {
-      buffers_.Add(new ObjectSlot[kBufferSize]);
-    }
-    buffer_ = buffers_[buffer_idx_];
-  }
-
-  buffer_[idx_++] = slot;
+void SlotsBufferAllocator::DeallocateBuffer(SlotsBuffer* buffer) {
+  free(buffer);
 }
 
 
-static inline void UpdateSlot(Object** slot) {
-  Object* obj = *slot;
-  if (!obj->IsHeapObject()) return;
-
-  HeapObject* heap_obj = HeapObject::cast(obj);
-
-  MapWord map_word = heap_obj->map_word();
-  if (map_word.IsForwardingAddress()) {
-    ASSERT(MarkCompactCollector::IsOnEvacuationCandidate(*slot));
-    *slot = map_word.ToForwardingAddress();
-    ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+void SlotsBufferAllocator::DeallocateChain(SlotsBuffer** buffer_address) {
+  SlotsBuffer* buffer = *buffer_address;
+  while (buffer != NULL) {
+    SlotsBuffer* next_buffer = buffer->next();
+    DeallocateBuffer(buffer);
+    buffer = next_buffer;
   }
+  *buffer_address = NULL;
 }
 
 
-void SlotsBuffer::Update() {
-  if (buffer_idx_ < 0) return;
-
-  for (int buffer_index = 0; buffer_index < buffer_idx_; ++buffer_index) {
-    ObjectSlot* buffer = buffers_[buffer_index];
-    for (int slot_idx = 0; slot_idx < kBufferSize; ++slot_idx) {
-      UpdateSlot(buffer[slot_idx]);
-    }
-  }
-
-  ObjectSlot* last_buffer = buffers_[buffer_idx_];
-  for (int slot_idx = 0; slot_idx < idx_; ++slot_idx) {
-    UpdateSlot(last_buffer[slot_idx]);
-  }
-}
-
-
-void SlotsBuffer::Report() {
-}
-
-
 } }  // namespace v8::internal