[heap] Add atomics to mark bit operations.

src/heap/marking.h

 // Copyright 2016 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_MARKING_H
 #define V8_MARKING_H
 
+#include "src/base/atomic-utils.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
 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) {
     return cell_ == other.cell_ && mask_ == other.mask_;
   }
 #endif
 
  private:
-  inline CellType* cell() { return cell_; }
-  inline CellType mask() { return mask_; }
-
   inline MarkBit Next() {
     CellType new_mask = mask_ << 1;
     if (new_mask == 0) {
       return MarkBit(cell_ + 1, 1);
     } else {
       return MarkBit(cell_, new_mask);
     }
   }
 
-  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;
+  }
 
-  CellType* cell_;
-  CellType mask_;
+  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;
+  }
+
+  base::Atomic32* cell_;
+  base::Atomic32 mask_;
 
   friend class IncrementalMarking;
   friend class Marking;
 };
 
 // Bitmap is a sequence of cells each containing fixed number of bits.
 class Bitmap {
  public:
   static const uint32_t kBitsPerCell = 32;
   static const uint32_t kBitsPerCellLog2 = 5;
@@ skipping 38 matching lines @@
 
   INLINE(Address address()) { return reinterpret_cast<Address>(this); }
 
   INLINE(static Bitmap* FromAddress(Address addr)) {
     return reinterpret_cast<Bitmap*>(addr);
   }
 
   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() {
     for (int i = 0; i < CellsCount(); i++) cells()[i] = 0;
   }
 
   // Sets all bits in the range [start_index, end_index).
   void SetRange(uint32_t start_index, uint32_t end_index) {
     unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
     MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
@@ skipping 149 matching lines @@
       if (cells()[i] != 0) {
         return false;
       }
     }
     return true;
   }
 };
 
 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(); }
-
-  INLINE(static void MarkWhite(MarkBit markbit)) {
-    markbit.Clear();
-    markbit.Next().Clear();
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) {
+    return mark_bit.Get<mode>();
   }
 
-  INLINE(static void BlackToGrey(MarkBit markbit)) {
-    DCHECK(IsBlack(markbit));
-    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 WhiteToGrey(MarkBit markbit)) {
-    DCHECK(IsWhite(markbit));
-    markbit.Set();
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool BlackToGrey(MarkBit markbit)) {
+    DCHECK(IsBlack(markbit));
+    return markbit.Next().Clear<mode>();
   }
 
-  INLINE(static void WhiteToBlack(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool WhiteToGrey(MarkBit markbit)) {
     DCHECK(IsWhite(markbit));
-    markbit.Set();
-    markbit.Next().Set();
+    return markbit.Set<mode>();
   }
 
-  INLINE(static void GreyToBlack(MarkBit markbit)) {
+  template <MarkBit::ModificationMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool WhiteToBlack(MarkBit markbit)) {
+    DCHECK(IsWhite(markbit));
+    if (!markbit.Set<mode>()) return false;
+    return markbit.Next().Set<mode>();
+  }
+
+  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 {
     BLACK_OBJECT,
     WHITE_OBJECT,
     GREY_OBJECT,
     IMPOSSIBLE_COLOR
   };
 
   static const char* ColorName(ObjectColor color) {
@@ skipping 19 matching lines @@
   }
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_MARKING_H_