[heap] Black is encoded with 11, grey with 10.

src/heap/mark-compact.h

Index: src/heap/mark-compact.h
diff --git a/src/heap/mark-compact.h b/src/heap/mark-compact.h
index 1ade4372f61d0909b1caad9b8d966935f06d0022..0bcd1d3b159f44bb9b44675813e6692c203d062f 100644
--- a/src/heap/mark-compact.h
+++ b/src/heap/mark-compact.h
@@ -45,10 +45,10 @@ class Marking : public AllStatic {
     return !mark_bit.Get() && mark_bit.Next().Get();
   }
 
-  // Black markbits: 10 - this is required by the sweeper.
+  // Black markbits: 11
   static const char* kBlackBitPattern;
   INLINE(static bool IsBlack(MarkBit mark_bit)) {
-    return mark_bit.Get() && !mark_bit.Next().Get();
+    return mark_bit.Get() && mark_bit.Next().Get();
   }
 
   // White markbits: 00 - this is required by the mark bit clearer.
@@ -58,10 +58,10 @@ class Marking : public AllStatic {
     return !mark_bit.Get();
   }
 
-  // Grey markbits: 11
+  // Grey markbits: 10
   static const char* kGreyBitPattern;
   INLINE(static bool IsGrey(MarkBit mark_bit)) {
-    return mark_bit.Get() && mark_bit.Next().Get();
+    return mark_bit.Get() && !mark_bit.Next().Get();
   }
 
   // IsBlackOrGrey assumes that the first bit is set for black or grey
@@ -70,7 +70,7 @@ class Marking : public AllStatic {
 
   INLINE(static void MarkBlack(MarkBit mark_bit)) {
     mark_bit.Set();
-    mark_bit.Next().Clear();
+    mark_bit.Next().Set();
   }
 
   INLINE(static void MarkWhite(MarkBit mark_bit)) {
@@ -81,6 +81,7 @@ class Marking : public AllStatic {
   INLINE(static void BlackToWhite(MarkBit markbit)) {
     DCHECK(IsBlack(markbit));
     markbit.Clear();
+    markbit.Next().Clear();
   }
 
   INLINE(static void GreyToWhite(MarkBit markbit)) {
@@ -91,23 +92,23 @@ class Marking : public AllStatic {
 
   INLINE(static void BlackToGrey(MarkBit markbit)) {
     DCHECK(IsBlack(markbit));
-    markbit.Next().Set();
+    markbit.Next().Clear();
   }
 
   INLINE(static void WhiteToGrey(MarkBit markbit)) {
     DCHECK(IsWhite(markbit));
     markbit.Set();
-    markbit.Next().Set();
   }
 
   INLINE(static void WhiteToBlack(MarkBit markbit)) {
     DCHECK(IsWhite(markbit));
     markbit.Set();
+    markbit.Next().Set();
   }
 
   INLINE(static void GreyToBlack(MarkBit markbit)) {
     DCHECK(IsGrey(markbit));
-    markbit.Next().Clear();
+    markbit.Next().Set();
   }
 
   INLINE(static void BlackToGrey(HeapObject* obj)) {
@@ -116,7 +117,7 @@ class Marking : public AllStatic {
 
   INLINE(static void AnyToGrey(MarkBit markbit)) {
     markbit.Set();
-    markbit.Next().Set();
+    markbit.Next().Clear();
   }
 
   static void TransferMark(Heap* heap, Address old_start, Address new_start);
@@ -160,16 +161,15 @@ class Marking : public AllStatic {
   INLINE(static bool TransferColor(HeapObject* from, HeapObject* to)) {
     MarkBit from_mark_bit = MarkBitFrom(from);
     MarkBit to_mark_bit = MarkBitFrom(to);
-    bool is_black = false;
+    DCHECK(Marking::IsWhite(to_mark_bit));
     if (from_mark_bit.Get()) {
       to_mark_bit.Set();
-      is_black = true;  // Looks black so far.
-    }
-    if (from_mark_bit.Next().Get()) {
-      to_mark_bit.Next().Set();
-      is_black = false;  // Was actually gray.
+      if (from_mark_bit.Next().Get()) {
+        to_mark_bit.Next().Set();
+        return true;
+      }
     }
-    return is_black;
+    return false;
   }
 
  private:
@@ -854,6 +854,78 @@ class MarkBitCellIterator BASE_EMBEDDED {
 };
 
 
+class LiveObjectIterator BASE_EMBEDDED {
+ public:
+  enum LiveObjectIterationMode { kBlackObjects, kGreyObjects, kAllLiveObjects };
+
+  explicit LiveObjectIterator(MemoryChunk* chunk)
+      : chunk_(chunk),
+        it_(chunk_),
+        cell_base_(it_.CurrentCellBase()),
+        current_cell_(*it_.CurrentCell()) {}
+
+  template <LiveObjectIterationMode mode>

[ulan, 2016/01/07 16:39:11]

The template parameter should be on the class, not method.

Otherwise, it allows to change the between calls.

[Hannes Payer (out of office), 2016/01/07 20:17:33]

Done.

+  inline HeapObject* Next() {

[Michael Lippautz, 2016/01/07 14:02:53]

Maybe move the implementation to to mark-compact-inl.h

[Hannes Payer (out of office), 2016/01/07 16:26:16]

Done.

+    while (!it_.Done()) {
+      HeapObject* object = NULL;

[Michael Lippautz, 2016/01/07 14:02:53]

nit:nullptr

[Hannes Payer (out of office), 2016/01/07 16:26:16]

Done.

+      while (current_cell_ != 0) {
+        int trailing_zeros = base::bits::CountTrailingZeros32(current_cell_);

[Michael Lippautz, 2016/01/07 14:02:53]

nit: Maybe add
  DCHECK_NE(trailing_zeros, 32);

[Hannes Payer (out of office), 2016/01/07 16:26:16]

This is implied by current_cell_ != 0 and by the implementation of
CountTrailingZeros32.

+        Address addr = cell_base_ + trailing_zeros * kPointerSize;
+
+        current_cell_ &= ~(1u << trailing_zeros);

[ulan, 2016/01/07 16:39:11]

unsigned color = 0;
if (trailing_zeros < Bitmap::kBitIndexMask) {
  color = (current_cell_ >> (trailing_zeros + 1)) & 1;
  current_cell_ = ~(3u << trailing_zeros);
} else {
  current_cell_ = ~(1u << trailing_zeros);
  DCHECK(!it_.Done());
  it_.Advance();
  cell_base_ = it_.CurrentCellBase();
  current_cell_ = *it_.CurrentCell();
  color = (current_cell_ & 1);
  current_cell_ &= 0xFFFFFFFE;
}

now use the color to check for object.

[Hannes Payer (out of office), 2016/01/07 20:17:33]

I refactored it the other way around.

+        if (trailing_zeros < Bitmap::kBitIndexMask) {

[Michael Lippautz, 2016/01/07 14:02:53]

You could do
  uint32_t bit_idx = 0;
  if (trailing_zeros < Bitmap::kBitIndexMask) {
    bit_idx = 1u << (trailing_zeros + 1);
    ...
  } else {
    bit_idx = 0x1;
    ...
  }
  current_cell_ &= ~bit_idx;

[Hannes Payer (out of office), 2016/01/07 16:26:16]

Done.

+          if (mode == kBlackObjects &&
+              (current_cell_ & 1u << (trailing_zeros + 1))) {
+            object = HeapObject::FromAddress(addr);
+          } else if (mode == kGreyObjects &&
+                     !(current_cell_ & 1u << (trailing_zeros + 1))) {
+            object = HeapObject::FromAddress(addr);
+          } else if (mode == kAllLiveObjects) {
+            object = HeapObject::FromAddress(addr);
+          }
+          current_cell_ &= ~(1u << (trailing_zeros + 1));
+        } else {
+          // The overlapping case; there has to exist a cell after the current
+          // cell.
+          DCHECK(!it_.Done());
+          it_.Advance();
+          cell_base_ = it_.CurrentCellBase();
+          current_cell_ = *it_.CurrentCell();
+          if (mode == kBlackObjects && (current_cell_ & 0x1)) {
+            object = HeapObject::FromAddress(addr);
+          } else if (mode == kGreyObjects && !(current_cell_ & 0x1)) {
+            object = HeapObject::FromAddress(addr);
+          } else if (mode == kAllLiveObjects) {
+            object = HeapObject::FromAddress(addr);
+          }
+          // Clear overlapping bit.
+          current_cell_ &= 0xFFFFFFFE;
+        }
+
+        // We found a live object.
+        if (object != NULL) break;

[Michael Lippautz, 2016/01/07 14:02:53]

nit: nullptr, likewise below

[Hannes Payer (out of office), 2016/01/07 16:26:16]

Done.

+      }
+      if (current_cell_ == 0) {
+        if (!it_.Done()) {
+          it_.Advance();
+          cell_base_ = it_.CurrentCellBase();
+          current_cell_ = *it_.CurrentCell();
+        }
+      }
+      if (object != NULL) return object;
+    }
+    return NULL;
+  }
+
+
+ private:
+  MemoryChunk* chunk_;
+  MarkBitCellIterator it_;
+  Address cell_base_;
+  MarkBit::CellType current_cell_;
+};
+
+
 class EvacuationScope BASE_EMBEDDED {
  public:
   explicit EvacuationScope(MarkCompactCollector* collector)