Eliminate invalid pointers in store buffer 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 296 matching lines @@
   ClearWeakCollections();
 
   heap_->set_encountered_weak_cells(Smi::FromInt(0));
 
 #ifdef VERIFY_HEAP
   if (FLAG_verify_heap) {
     VerifyMarking(heap_);
   }
 #endif
 
+  heap_->store_buffer()->ClearInvalidStoreBufferEntries();
+
+#ifdef VERIFY_HEAP
+  if (FLAG_verify_heap) {
+    heap_->store_buffer()->VerifyValidStoreBufferEntries();
+  }
+#endif
+
   SweepSpaces();
 
 #ifdef VERIFY_HEAP
   VerifyWeakEmbeddedObjectsInCode();
   if (FLAG_collect_maps && FLAG_omit_map_checks_for_leaf_maps) {
     VerifyOmittedMapChecks();
   }
 #endif
 
   Finish();
@@ skipping 2714 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) {
+  // This function does not support large objects right now.
+  if (p->owner() == 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();
+
+  // First check if the object is in the current cell.
+  MarkBit::CellType slot_mask;
+  if ((cells[start_index] == 0) ||
+      (base::bits::CountTrailingZeros32(cells[start_index]) >
+       base::bits::CountTrailingZeros32(cells[start_index] | index_in_cell))) {
+    // If not, find a cell in a preceding cell slot that has a mark bit set.
+    do {
+      start_index--;

[Erik Corry, 2015/03/09 10:39:17]

If start_index was zero, it goes negative here, which is going to cause chaos!

[Hannes Payer (out of office), 2015/03/09 11:50:12]

start_index will never be zero. It will always be larger or equal than 
Address cell_base = p->area_start();
unsigned int cell_base_start_index = Bitmap::IndexToCell(
       Bitmap::CellAlignIndex(p->AddressToMarkbitIndex(cell_base)));

However, we should not go until 0 but should stop at base_start_index. Changed.

+    } while (start_index > 0 && cells[start_index] == 0);
+
+    // The slot must be in a dead object if there are no preceding cells that
+    // have mark bits set.
+    if (cells[start_index] == 0) {
+      return false;
+    }
+
+    // The object is in a preceding cell. Set the mask to find any object.
+    slot_mask = 0xffffffff;
+  } else {
+    // We are interested in object mark bits right before the slot.
+    slot_mask = index_in_cell - 1;
+  }
+
+  MarkBit::CellType current_cell = cells[start_index];
+  DCHECK(current_cell != 0);
+
+  // Find the first live object in the cell.

[Erik Corry, 2015/03/09 10:46:26]

Shouldn't this be the _last_ live object in the cell?

[Hannes Payer (out of office), 2015/03/09 11:50:12]

Done. It depends on your point of view.

+  unsigned int leading_zeros =
+      base::bits::CountLeadingZeros32(current_cell & slot_mask);
+  DCHECK(leading_zeros != 32);
+  unsigned int offset = Bitmap::kBitIndexMask - leading_zeros;
+
+  Address cell_base = p->area_start();
+  unsigned int cell_base_start_index = Bitmap::IndexToCell(
+      Bitmap::CellAlignIndex(p->AddressToMarkbitIndex(cell_base)));
+  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 first found object in the cell, the slot is
+    // in a live object.
+    return true;
+  }
+  return false;
+}
+
+
+bool MarkCompactCollector::IsSlotInBlackObjectSlow(Page* p, Address slot) {
+  // This function does not support large objects right now.
+  if (p->owner() == NULL) return true;
+
+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    Address cell_base = it.CurrentCellBase();
+    MarkBit::CellType* cell = it.CurrentCell();
+
+    MarkBit::CellType current_cell = *cell;
+    if (current_cell == 0) continue;
+
+    int offset = 0;
+    while (current_cell != 0) {
+      int trailing_zeros = base::bits::CountTrailingZeros32(current_cell);
+      current_cell >>= trailing_zeros;
+      offset += trailing_zeros;
+      Address address = cell_base + offset * kPointerSize;
+
+      HeapObject* object = HeapObject::FromAddress(address);
+      int size = object->Size();
+
+      if (object->address() > slot) return false;
+      if (object->address() <= slot && slot < (object->address() + size)) {
+        return true;
+      }
+
+      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))) {
+    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;
+  }
+
+  return true;
+}
+
+
+void MarkCompactCollector::VerifyIsSlotInLiveObject(HeapObject** address,
+                                                    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)));
+}
+
+
 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();
 
   // Store allocation range before flipping semispaces.
   Address from_bottom = new_space->bottom();
@@ skipping 1435 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