[heap] Add atomics to mark bit operations.

src/heap/marking.h

Index: src/heap/marking.h
diff --git a/src/heap/marking.h b/src/heap/marking.h
index b8396b7f0b243f9036956761446571a2166dd727..f1e738f58885a2e7727f0d1de0ab55611164808e 100644
--- a/src/heap/marking.h
+++ b/src/heap/marking.h
@@ -5,6 +5,7 @@
 #ifndef V8_MARKING_H
 #define V8_MARKING_H
 
+#include "src/base/atomic-utils.h"
 #include "src/utils.h"
 
 namespace v8 {
@@ -14,7 +15,11 @@ class MarkBit {
  public:
   typedef uint32_t CellType;

[Michael Lippautz, 2017/03/06 13:52:54]

nit: Can we have a static_assert that sizeof(CellType) == sizeof(Atomic32)?

[Hannes Payer (out of office), 2017/03/08 14:12:57]

Done.

 
-  inline MarkBit(CellType* cell, CellType mask) : cell_(cell), mask_(mask) {}
+  enum ModificationMode { ATOMIC, NON_ATOMIC };

[Michael Lippautz, 2017/03/06 13:52:54]

You could make an 
  enum class ModicationMode
outside of MarkBit. We often had problems with enums nested in classes.

[Hannes Payer (out of office), 2017/03/08 14:12:57]

I kind of like it to keep it in the MarkBit class for that particular case. I do
not see any problems with that.

+
+  inline MarkBit(base::Atomic32* cell, CellType mask) : cell_(cell) {
+    mask_ = static_cast<base::Atomic32>(mask);
+  }
 
 #ifdef DEBUG
   bool operator==(const MarkBit& other) {
@@ -23,9 +28,6 @@ class MarkBit {
 #endif
 
  private:
-  inline CellType* cell() { return cell_; }
-  inline CellType mask() { return mask_; }
-
   inline MarkBit Next() {
     CellType new_mask = mask_ << 1;
     if (new_mask == 0) {
@@ -35,12 +37,51 @@ class MarkBit {
     }
   }
 
-  inline void Set() { *cell_ |= mask_; }
-  inline bool Get() { return (*cell_ & mask_) != 0; }
-  inline void Clear() { *cell_ &= ~mask_; }
+  template <ModificationMode mode>
+  inline bool Set() {
+    if (mode == ATOMIC) {
+      base::Atomic32 old_value;
+      base::Atomic32 new_value;
+      do {
+        old_value = base::NoBarrier_Load(cell_);
+        if (old_value & mask_) return false;
+        new_value = old_value | mask_;
+      } while (base::Release_CompareAndSwap(cell_, old_value, new_value) !=
+               old_value);
+    } else {
+      *cell_ |= mask_;
+    }
+    return true;
+  }
+
+  template <ModificationMode mode>
+  inline bool Get() {
+    if (mode == ATOMIC) {
+      return (base::Acquire_Load(cell_) & mask_) != 0;
+    } else {
+      return (base::NoBarrier_Load(cell_) & mask_) != 0;
+    }
+  }
+
+  template <ModificationMode mode>
+  inline bool Clear() {
+    if (mode == ATOMIC) {
+      base::Atomic32 old_value;
+      base::Atomic32 new_value;
+      do {
+        old_value = base::NoBarrier_Load(cell_);
+        if (!(old_value & mask_)) return false;
+        new_value = old_value & ~mask_;
+      } while (base::Release_CompareAndSwap(cell_, old_value, new_value) !=
+               old_value);
+    } else {
+      *cell_ &= ~mask_;
+    }
+    return true;
+  }
 
-  CellType* cell_;
-  CellType mask_;
+  base::Atomic32* cell_;
+  base::Atomic32 mask_;
 
   friend class IncrementalMarking;
   friend class Marking;
@@ -99,7 +140,7 @@ class Bitmap {
   inline MarkBit MarkBitFromIndex(uint32_t index) {
     MarkBit::CellType mask = 1u << IndexInCell(index);
     MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
-    return MarkBit(cell, mask);
+    return MarkBit(reinterpret_cast<base::Atomic32*>(cell), mask);
   }
 
   void Clear() {
@@ -269,59 +310,75 @@ class Bitmap {
 
 class Marking : public AllStatic {
  public:
+  // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC
+  // mode for access. We should remove the default value or switch it with
+  // ATOMIC as soon we add concurrency.
+
   // Impossible markbits: 01
   static const char* kImpossibleBitPattern;
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
   INLINE(static bool IsImpossible(MarkBit mark_bit)) {
-    return !mark_bit.Get() && mark_bit.Next().Get();
+    return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();

[ulan, 2017/03/06 14:51:33]

Atomic version can return false positive if between the first bit read and the
second bit read the object goes from white to black in concurrent thread.

Can we get rid of this function?

[Hannes Payer (out of office), 2017/03/08 14:12:57]

This function is still useful. I made it safe for concurrent usage.

   }
 
   // Black markbits: 11
   static const char* kBlackBitPattern;
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
   INLINE(static bool IsBlack(MarkBit mark_bit)) {
-    return mark_bit.Get() && mark_bit.Next().Get();
+    return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
   }
 
   // White markbits: 00 - this is required by the mark bit clearer.
   static const char* kWhiteBitPattern;
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
   INLINE(static bool IsWhite(MarkBit mark_bit)) {
     DCHECK(!IsImpossible(mark_bit));
-    return !mark_bit.Get();
+    return !mark_bit.Get<mode>();
   }
 
   // Grey markbits: 10
   static const char* kGreyBitPattern;
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
   INLINE(static bool IsGrey(MarkBit mark_bit)) {
-    return mark_bit.Get() && !mark_bit.Next().Get();
+    return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>();
   }
 
   // IsBlackOrGrey assumes that the first bit is set for black or grey
   // objects.
-  INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) { return mark_bit.Get(); }
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) {
+    return mark_bit.Get<mode>();
+  }
 
-  INLINE(static void MarkWhite(MarkBit markbit)) {
-    markbit.Clear();
-    markbit.Next().Clear();
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool MarkWhite(MarkBit markbit)) {

[ulan, 2017/03/06 14:51:33]

All functions that move the color in black -> grey -> white direction are not
safe for concurrent usage (e.g. concurrent MarkWhite() and GreyToBlack() on a
grey color can make impossible color).

Should we disallow atomic versions of MarkWhite and BlackToGrey?

[Hannes Payer (out of office), 2017/03/08 14:12:57]

Done.

Why is BlackToGrey a problem?

+    if (!markbit.Clear<mode>()) return false;
+    return markbit.Next().Clear<mode>();
   }
 
-  INLINE(static void BlackToGrey(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool BlackToGrey(MarkBit markbit)) {
     DCHECK(IsBlack(markbit));
-    markbit.Next().Clear();
+    return markbit.Next().Clear<mode>();
   }
 
-  INLINE(static void WhiteToGrey(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool WhiteToGrey(MarkBit markbit)) {
     DCHECK(IsWhite(markbit));
-    markbit.Set();
+    return markbit.Set<mode>();
   }
 
-  INLINE(static void WhiteToBlack(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool WhiteToBlack(MarkBit markbit)) {
     DCHECK(IsWhite(markbit));
-    markbit.Set();
-    markbit.Next().Set();
+    if (!markbit.Set<mode>()) return false;
+    return markbit.Next().Set<mode>();
   }
 
-  INLINE(static void GreyToBlack(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool GreyToBlack(MarkBit markbit)) {
     DCHECK(IsGrey(markbit));
-    markbit.Next().Set();
+    return markbit.Next().Set<mode>();
   }
 
   enum ObjectColor {