[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 23 matching lines @@
     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)) {
     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();
+        return true;
+      }
     }
-    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 };
+
+  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)
       : 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_