[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..6301cf5e177079d041bb830dc78cc9e0df603999 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)) {

[ulan, 2016/01/05 14:45:23]

Let's assert that the color of the _to_ is white.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

Done.

     MarkBit from_mark_bit = MarkBitFrom(from);
     MarkBit to_mark_bit = MarkBitFrom(to);
-    bool is_black = false;
     if (from_mark_bit.Get()) {
       to_mark_bit.Set();
-      is_black = true;  // Looks black so far.
+      // Looks black so far.

[ulan, 2016/01/05 14:45:23]

This comment doesn't help anymore. Let's just remove it.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

Done.

+      if (from_mark_bit.Next().Get()) {
+        to_mark_bit.Next().Set();
+        return true;  // Is black.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

I also removed "// Is black." comment.

+      }
     }
-    if (from_mark_bit.Next().Get()) {
-      to_mark_bit.Next().Set();
-      is_black = false;  // Was actually gray.
-    }
-    return is_black;
+    return false;
   }
 
  private:
@@ -854,6 +854,73 @@ class MarkBitCellIterator BASE_EMBEDDED {
 };
 
 
+class LiveObjectIterator BASE_EMBEDDED {
+ public:
+  enum LiveObjectIterationMode { kBlackObjects, kGreyObjects, kAllLiveObjects };
+
+  LiveObjectIterator(MemoryChunk* chunk, LiveObjectIterationMode mode)
+      : chunk_(chunk),
+        mode_(mode),
+        it_(chunk_),
+        cell_base_(it_.CurrentCellBase()),
+        current_cell_(*it_.CurrentCell()),
+        clear_overlapping_bit_(false) {}
+
+  inline HeapObject* Next() {
+    while (!it_.Done()) {

[ulan, 2016/01/05 14:45:23]

IUC, this condition will cause early return for the last cell, i.e. not all
objects of the last cell will be found.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

Nope, last cell index is already invalid, so this should be fine.

+      HeapObject* object = NULL;
+      if (clear_overlapping_bit_) {
+        DCHECK(current_cell_ & 0x1);
+        current_cell_ &= 0xFFFFFFFE;
+        clear_overlapping_bit_ = false;
+      }
+
+      while (current_cell_ != 0) {
+        int trailing_zeros = base::bits::CountTrailingZeros32(current_cell_);
+        Address addr = cell_base_ + trailing_zeros * kPointerSize;
+        MarkBit mark_bit = Marking::MarkBitFrom(addr);
+
+        if (IsValidLiveObject(mark_bit)) {
+          object = HeapObject::FromAddress(addr);
+        }
+
+        current_cell_ &= ~(1u << trailing_zeros);
+        if (trailing_zeros < Bitmap::kBitIndexMask) {
+          current_cell_ &= ~(1u << (trailing_zeros + 1));
+        } else if (Marking::IsBlack(mark_bit)) {
+          clear_overlapping_bit_ = true;

[ulan, 2016/01/05 14:45:23]

We would need to fetch the next cell here anyway.

After fetching and checking the LSB, we could clear it immediately instead of
setting clear_overlapping_bit_.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

Done.

+        }
+
+        // We found a live object.
+        break;
+      }
+      if (current_cell_ == 0) {
+        it_.Advance();
+        cell_base_ = it_.CurrentCellBase();
+        current_cell_ = *it_.CurrentCell();
+      }
+      if (object != NULL) return object;
+    }
+    return NULL;
+  }
+
+
+ private:
+  bool IsValidLiveObject(MarkBit mark_bit) {
+    return mode_ == kAllLiveObjects ||

[ulan, 2016/01/05 14:45:23]

As discussed we can templatize this.

[Hannes Payer (out of office), 2016/01/07 10:30:32]

Done.

+           (mode_ == kBlackObjects && Marking::IsBlack(mark_bit)) ||
+           (mode_ == kGreyObjects && Marking::IsGrey(mark_bit));
+  }
+
+  MemoryChunk* chunk_;
+  LiveObjectIterationMode mode_;
+  MarkBitCellIterator it_;
+  Address cell_base_;
+  MarkBit::CellType current_cell_;
+  bool clear_overlapping_bit_;
+};
+
+
 class EvacuationScope BASE_EMBEDDED {
  public:
   explicit EvacuationScope(MarkCompactCollector* collector)