Filter invalid slots out from the SlotsBuffer after marking.

src/heap/mark-compact.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/v8.h"
 
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/code-stubs.h"
 #include "src/compilation-cache.h"
@@ skipping 269 matching lines @@
     heap()->old_data_space()->EvictEvacuationCandidatesFromFreeLists();
     heap()->code_space()->EvictEvacuationCandidatesFromFreeLists();
 
     compacting_ = evacuation_candidates_.length() > 0;
   }
 
   return compacting_;
 }
 
 
+void MarkCompactCollector::ClearInvalidSlotsBufferEntries(PagedSpace* space) {
+  PageIterator it(space);
+  while (it.has_next()) {
+    Page* p = it.next();
+    SlotsBuffer::RemoveInvalidSlots(heap_, p->slots_buffer());
+  }
+}
+
+
+void MarkCompactCollector::ClearInvalidStoreAndSlotsBufferEntries() {
+  heap_->store_buffer()->ClearInvalidStoreBufferEntries();
+
+  ClearInvalidSlotsBufferEntries(heap_->old_pointer_space());
+  ClearInvalidSlotsBufferEntries(heap_->old_data_space());
+  ClearInvalidSlotsBufferEntries(heap_->code_space());
+  ClearInvalidSlotsBufferEntries(heap_->cell_space());
+  ClearInvalidSlotsBufferEntries(heap_->map_space());
+
+  LargeObjectIterator it(heap_->lo_space());
+  for (HeapObject* object = it.Next(); object != NULL; object = it.Next()) {
+    MemoryChunk* chunk = MemoryChunk::FromAddress(object->address());
+    SlotsBuffer::RemoveInvalidSlots(heap_, chunk->slots_buffer());
+  }
+}
+
+
+#ifdef VERIFY_HEAP
+static void VerifyValidSlotsBufferEntries(Heap* heap, PagedSpace* space) {
+  PageIterator it(space);
+  while (it.has_next()) {
+    Page* p = it.next();
+    SlotsBuffer::VerifySlots(heap, p->slots_buffer());
+  }
+}
+
+
+static void VerifyValidStoreAndSlotsBufferEntries(Heap* heap) {
+  heap->store_buffer()->VerifyValidStoreBufferEntries();
+
+  VerifyValidSlotsBufferEntries(heap, heap->old_pointer_space());
+  VerifyValidSlotsBufferEntries(heap, heap->old_data_space());
+  VerifyValidSlotsBufferEntries(heap, heap->code_space());
+  VerifyValidSlotsBufferEntries(heap, heap->cell_space());
+  VerifyValidSlotsBufferEntries(heap, heap->map_space());
+
+  LargeObjectIterator it(heap->lo_space());
+  for (HeapObject* object = it.Next(); object != NULL; object = it.Next()) {
+    MemoryChunk* chunk = MemoryChunk::FromAddress(object->address());
+    SlotsBuffer::VerifySlots(heap, chunk->slots_buffer());
+  }
+}
+#endif
+
+
 void MarkCompactCollector::CollectGarbage() {
   // Make sure that Prepare() has been called. The individual steps below will
   // update the state as they proceed.
   DCHECK(state_ == PREPARE_GC);
 
   MarkLiveObjects();
   DCHECK(heap_->incremental_marking()->IsStopped());
 
   // ClearNonLiveReferences can deoptimize code in dependent code arrays.
   // Process weak cells before so that weak cells in dependent code
   // arrays are cleared or contain only live code objects.
   ProcessAndClearWeakCells();
 
   if (FLAG_collect_maps) ClearNonLiveReferences();
 
   ClearWeakCollections();
 
   heap_->set_encountered_weak_cells(Smi::FromInt(0));
 
 #ifdef VERIFY_HEAP
   if (FLAG_verify_heap) {
     VerifyMarking(heap_);
   }
 #endif
 
-  heap_->store_buffer()->ClearInvalidStoreBufferEntries();
+  ClearInvalidStoreAndSlotsBufferEntries();
 
 #ifdef VERIFY_HEAP
   if (FLAG_verify_heap) {
-    heap_->store_buffer()->VerifyValidStoreBufferEntries();
+    VerifyValidStoreAndSlotsBufferEntries(heap_);
   }
 #endif
 
   SweepSpaces();
 
 #ifdef VERIFY_HEAP
   VerifyWeakEmbeddedObjectsInCode();
   if (FLAG_collect_maps && FLAG_omit_map_checks_for_leaf_maps) {
     VerifyOmittedMapChecks();
   }
@@ skipping 377 matching lines @@
 
   intptr_t estimated_release = 0;
 
   Candidate candidates[kMaxMaxEvacuationCandidates];
 
   max_evacuation_candidates =
       Min(kMaxMaxEvacuationCandidates, max_evacuation_candidates);
 
   int count = 0;
   int fragmentation = 0;
+  int page_number = 0;
   Candidate* least = NULL;
 
   PageIterator it(space);
   while (it.has_next()) {
     Page* p = it.next();
     if (p->NeverEvacuate()) continue;
 
     // Invariant: Evacuation candidates are just created when marking is
     // started. At the end of a GC all evacuation candidates are cleared and
     // their slot buffers are released.
     CHECK(!p->IsEvacuationCandidate());
     CHECK(p->slots_buffer() == NULL);
 
     if (FLAG_stress_compaction) {
-      unsigned int counter = space->heap()->ms_count();
-      uintptr_t page_number = reinterpret_cast<uintptr_t>(p) >> kPageSizeBits;
-      if ((counter & 1) == (page_number & 1)) fragmentation = 1;
+      if (FLAG_manual_evacuation_candidates_selection) {
+        if (p->IsFlagSet(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING)) {
+          p->ClearFlag(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING);
+          fragmentation = 1;
+        }
+      } else {
+        unsigned int counter = space->heap()->ms_count();
+        if ((counter & 1) == (page_number & 1)) fragmentation = 1;
+        page_number++;
+      }
     } else if (mode == REDUCE_MEMORY_FOOTPRINT) {
       // Don't try to release too many pages.
       if (estimated_release >= over_reserved) {
         continue;
       }
 
       intptr_t free_bytes = 0;
 
       if (!p->WasSwept()) {
         free_bytes = (p->area_size() - p->LiveBytes());
@@ skipping 2275 matching lines @@
   if (allocation.To(&target)) {
     MigrateObject(target, object, object_size, target_space->identity());
     heap()->IncrementPromotedObjectsSize(object_size);
     return true;
   }
 
   return false;
 }
 
 
-bool MarkCompactCollector::IsSlotInBlackObject(Page* p, Address slot) {
+bool MarkCompactCollector::IsSlotInBlackObject(Page* p, Address slot,
+                                               HeapObject** out_object) {
   // This function does not support large objects right now.
   Space* owner = p->owner();
-  if (owner == heap_->lo_space() || owner == NULL) return true;
+  if (owner == heap_->lo_space() || owner == NULL) {
+    *out_object = NULL;
+    return true;
+  }
 
   uint32_t mark_bit_index = p->AddressToMarkbitIndex(slot);
   unsigned int start_index = mark_bit_index >> Bitmap::kBitsPerCellLog2;
   MarkBit::CellType index_in_cell = 1U
                                     << (mark_bit_index & Bitmap::kBitIndexMask);
   MarkBit::CellType* cells = p->markbits()->cells();
   Address cell_base = p->area_start();
   unsigned int cell_base_start_index = Bitmap::IndexToCell(
       Bitmap::CellAlignIndex(p->AddressToMarkbitIndex(cell_base)));
 
@@ skipping 33 matching lines @@
   unsigned int offset = Bitmap::kBitIndexMask - leading_zeros;
 
   cell_base += (start_index - cell_base_start_index) * 32 * kPointerSize;
   Address address = cell_base + offset * kPointerSize;
   HeapObject* object = HeapObject::FromAddress(address);
   DCHECK(object->address() < reinterpret_cast<Address>(slot));
   if (object->address() <= slot &&
       (object->address() + object->Size()) > slot) {
     // If the slot is within the last found object in the cell, the slot is
     // in a live object.
+    *out_object = object;
     return true;
   }
   return false;
 }
 
 
 bool MarkCompactCollector::IsSlotInBlackObjectSlow(Page* p, Address slot) {
   // This function does not support large objects right now.
   Space* owner = p->owner();
   if (owner == heap_->lo_space() || owner == NULL) return true;
@@ skipping 21 matching lines @@
       }
 
       offset++;
       current_cell >>= 1;
     }
   }
   return false;
 }
 
 
-bool MarkCompactCollector::IsSlotInLiveObject(HeapObject** address,
-                                              HeapObject* object) {
-  // If the target object is not black, the source slot must be part
-  // of a non-black (dead) object.
-  if (!Marking::IsBlack(Marking::MarkBitFrom(object))) {
+bool MarkCompactCollector::IsSlotInLiveObject(Address slot) {
+  HeapObject* object = NULL;
+  // The target object is black but we don't know if the source slot is black.
+  // The source object could have died and the slot could be part of a free
+  // space. Find out based on mark bits if the slot is part of a live object.
+  if (!IsSlotInBlackObject(Page::FromAddress(slot), slot, &object)) {
     return false;
   }
 
-  // The target object is black but we don't know if the source slot is black.
-  // The source object could have died and the slot could be part of a free
-  // space. Find out based on mark bits if the slot is part of a live object.
-  if (!IsSlotInBlackObject(
-          Page::FromAddress(reinterpret_cast<Address>(address)),
-          reinterpret_cast<Address>(address))) {
-    return false;
+#if V8_DOUBLE_FIELDS_UNBOXING
+  // |object| is NULL only when the slot belongs to large object space.
+  DCHECK(object != NULL ||
+         Page::FromAnyPointerAddress(heap_, slot)->owner() ==
+             heap_->lo_space());
+  // We don't need to check large objects' layout descriptor since it can't
+  // contain in-object fields anyway.
+  if (object != NULL) {
+    // Filter out slots that happens to point to unboxed double fields.
+    LayoutDescriptorHelper helper(object->map());
+    bool has_only_tagged_fields = helper.all_fields_tagged();
+    if (!has_only_tagged_fields &&
+        !helper.IsTagged(static_cast<int>(slot - object->address()))) {
+      return false;
+    }
   }
+#endif
 
   return true;
 }
 
 
-void MarkCompactCollector::VerifyIsSlotInLiveObject(HeapObject** address,
+void MarkCompactCollector::VerifyIsSlotInLiveObject(Address slot,
                                                     HeapObject* object) {
   // The target object has to be black.
   CHECK(Marking::IsBlack(Marking::MarkBitFrom(object)));
 
   // The target object is black but we don't know if the source slot is black.
   // The source object could have died and the slot could be part of a free
   // space. Use the mark bit iterator to find out about liveness of the slot.
-  CHECK(IsSlotInBlackObjectSlow(
-      Page::FromAddress(reinterpret_cast<Address>(address)),
-      reinterpret_cast<Address>(address)));
+  CHECK(IsSlotInBlackObjectSlow(Page::FromAddress(slot), slot));
 }
 
 
 void MarkCompactCollector::EvacuateNewSpace() {
   // There are soft limits in the allocation code, designed trigger a mark
   // sweep collection by failing allocations.  But since we are already in
   // a mark-sweep allocation, there is no sense in trying to trigger one.
   AlwaysAllocateScope scope(isolate());
 
   NewSpace* new_space = heap()->new_space();
@@ skipping 1286 matching lines @@
     buffer = allocator->AllocateBuffer(buffer);
     *buffer_address = buffer;
   }
   DCHECK(buffer->HasSpaceForTypedSlot());
   buffer->Add(reinterpret_cast<ObjectSlot>(type));
   buffer->Add(reinterpret_cast<ObjectSlot>(addr));
   return true;
 }
 
 
+static Object* g_smi_slot = NULL;
+
+
+void SlotsBuffer::RemoveInvalidSlots(Heap* heap, SlotsBuffer* buffer) {
+  DCHECK_EQ(Smi::FromInt(0), g_smi_slot);

[Hannes Payer (out of office), 2015/03/24 14:47:05]

SMI 0 will indicate an embedded object slot. Why don't we just shrink the slots
buffer here, similar to the store buffer code?

[Igor Sheludko, 2015/03/24 15:10:25]

We delete entries by replacing them with address of g_smi_slot but not with a
smi zero. So it would not look like a typed slot and they would be skipped
during slots updating phase. 
Since we don't expect the number of invalid slots to be high we agreed that it
would probably be more efficient to replace invalid entries than to right shift
the tail of the buffer.

Here we just ensure that this g_smi_slot was not modified and still contains smi
zero.

+
+  // Remove entries by replacing them with a dummy slot containing a smi.
+  const ObjectSlot kRemovedEntry = &g_smi_slot;
+
+  while (buffer != NULL) {
+    SlotsBuffer::ObjectSlot* slots = buffer->slots_;
+    intptr_t slots_count = buffer->idx_;
+
+    for (int slot_idx = 0; slot_idx < slots_count; ++slot_idx) {
+      ObjectSlot slot = slots[slot_idx];
+      if (!IsTypedSlot(slot)) {
+        Object* object = *slot;
+        if (object->IsHeapObject()) {
+          if (heap->InNewSpace(object) ||
+              !heap->mark_compact_collector()->IsSlotInLiveObject(
+                  reinterpret_cast<Address>(slot))) {
+            slots[slot_idx] = kRemovedEntry;
+          }
+        }
+      } else {
+        ++slot_idx;
+        DCHECK(slot_idx < slots_count);
+      }
+    }
+    buffer = buffer->next();
+  }
+}
+
+
+void SlotsBuffer::VerifySlots(Heap* heap, SlotsBuffer* buffer) {
+  DCHECK_EQ(Smi::FromInt(0), g_smi_slot);
+
+  while (buffer != NULL) {
+    SlotsBuffer::ObjectSlot* slots = buffer->slots_;
+    intptr_t slots_count = buffer->idx_;
+
+    for (int slot_idx = 0; slot_idx < slots_count; ++slot_idx) {
+      ObjectSlot slot = slots[slot_idx];
+      if (!IsTypedSlot(slot)) {
+        Object* object = *slot;
+        if (object->IsHeapObject()) {
+          CHECK(!heap->InNewSpace(object));
+          CHECK(heap->mark_compact_collector()->IsSlotInLiveObject(
+              reinterpret_cast<Address>(slot)));
+        }
+      } else {
+        ++slot_idx;
+        DCHECK(slot_idx < slots_count);
+      }
+    }
+    buffer = buffer->next();
+  }
+}
+
+
 static inline SlotsBuffer::SlotType SlotTypeForRMode(RelocInfo::Mode rmode) {
   if (RelocInfo::IsCodeTarget(rmode)) {
     return SlotsBuffer::CODE_TARGET_SLOT;
   } else if (RelocInfo::IsEmbeddedObject(rmode)) {
     return SlotsBuffer::EMBEDDED_OBJECT_SLOT;
   } else if (RelocInfo::IsDebugBreakSlot(rmode)) {
     return SlotsBuffer::DEBUG_TARGET_SLOT;
   } else if (RelocInfo::IsJSReturn(rmode)) {
     return SlotsBuffer::JS_RETURN_SLOT;
   }
@@ skipping 121 matching lines @@
   SlotsBuffer* buffer = *buffer_address;
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 }
 }  // namespace v8::internal