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

src/heap/mark-compact.h

 // 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.
 
 #ifndef V8_HEAP_MARK_COMPACT_H_
 #define V8_HEAP_MARK_COMPACT_H_
 
 #include "src/base/bits.h"
 #include "src/heap/spaces.h"
 
@@ skipping 27 matching lines @@
   INLINE(static MarkBit MarkBitFrom(HeapObject* obj)) {
     return MarkBitFrom(reinterpret_cast<Address>(obj));
   }
 
   // Impossible markbits: 01
   static const char* kImpossibleBitPattern;
   INLINE(static bool IsImpossible(MarkBit mark_bit)) {
     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.
   static const char* kWhiteBitPattern;
   INLINE(static bool IsWhite(MarkBit mark_bit)) {
     DCHECK(!IsImpossible(mark_bit));
     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
   // objects.
   INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) { return mark_bit.Get(); }
 
   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)) {
     mark_bit.Clear();
     mark_bit.Next().Clear();
   }
 
   INLINE(static void BlackToWhite(MarkBit markbit)) {
     DCHECK(IsBlack(markbit));
     markbit.Clear();
+    markbit.Next().Clear();
   }
 
   INLINE(static void GreyToWhite(MarkBit markbit)) {
     DCHECK(IsGrey(markbit));
     markbit.Clear();
     markbit.Next().Clear();
   }
 
   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)) {
     BlackToGrey(MarkBitFrom(obj));
   }
 
   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);
 
 #ifdef DEBUG
   enum ObjectColor {
     BLACK_OBJECT,
     WHITE_OBJECT,
     GREY_OBJECT,
     IMPOSSIBLE_COLOR
@@ skipping 20 matching lines @@
   static ObjectColor Color(MarkBit mark_bit) {
     if (IsBlack(mark_bit)) return BLACK_OBJECT;
     if (IsWhite(mark_bit)) return WHITE_OBJECT;
     if (IsGrey(mark_bit)) return GREY_OBJECT;
     UNREACHABLE();
     return IMPOSSIBLE_COLOR;
   }
 #endif
 
   // Returns true if the transferred color is black.
   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:
   DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
 };
 
 // ----------------------------------------------------------------------------
 // Marking deque for tracing live objects.
 class MarkingDeque {
  public:
@@ skipping 664 matching lines @@
 
  private:
   MemoryChunk* chunk_;
   MarkBit::CellType* cells_;
   unsigned int last_cell_index_;
   unsigned int cell_index_;
   Address cell_base_;
 };
 
 
+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)
       : collector_(collector) {
     collector_->set_evacuation(true);
   }
 
   ~EvacuationScope() { collector_->set_evacuation(false); }
 
  private:
   MarkCompactCollector* collector_;
 };
 
 
 const char* AllocationSpaceName(AllocationSpace space);
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_HEAP_MARK_COMPACT_H_