[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;
+  STATIC_ASSERT(sizeof(CellType) == sizeof(base::Atomic32));
 
-  inline MarkBit(CellType* cell, CellType mask) : cell_(cell), mask_(mask) {}
+  enum AccessMode { ATOMIC, NON_ATOMIC };
+
+  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 <AccessMode mode = NON_ATOMIC>
+  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 <AccessMode mode = NON_ATOMIC>
+  inline bool Get() {
+    if (mode == ATOMIC) {
+      return (base::Acquire_Load(cell_) & mask_) != 0;
+    } else {
+      return (base::NoBarrier_Load(cell_) & mask_) != 0;
+    }
+  }
+
+  template <AccessMode mode = NON_ATOMIC>
+  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 ConcurrentMarkingMarkbits;
   friend class Marking;
 };
 
 // Bitmap is a sequence of cells each containing fixed number of bits.
 class Bitmap {
  public:
   static const uint32_t kBitsPerCell = 32;
@@ skipping 39 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::AccessMode mode = MarkBit::NON_ATOMIC>
   INLINE(static bool IsImpossible(MarkBit mark_bit)) {
-    return !mark_bit.Get() && mark_bit.Next().Get();
+    if (mode == MarkBit::NON_ATOMIC) {
+      return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
+    }
+    // If we are in concurrent mode we can only tell if an object has the
+    // impossible bit pattern if we read the first bit again after reading
+    // the first and the second bit. If the first bit is till zero and the
+    // second bit is one then the object has the impossible bit pattern.
+    bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
+    if (is_impossible) {
+      return !mark_bit.Get<mode>();
+    }
+    return false;
   }
 
   // Black markbits: 11
   static const char* kBlackBitPattern;
+  template <MarkBit::AccessMode 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::AccessMode 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::AccessMode 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::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) {
+    return mark_bit.Get<mode>();
   }
 
-  INLINE(static void MarkGrey(MarkBit markbit)) { markbit.Set(); }
-
-  INLINE(static void MarkBlack(MarkBit markbit)) {
-    markbit.Set();
-    markbit.Next().Set();
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static void MarkWhite(MarkBit markbit)) {
+    STATIC_ASSERT(mode == MarkBit::NON_ATOMIC);
+    markbit.Clear<mode>();
+    markbit.Next().Clear<mode>();
   }
 
-  INLINE(static void BlackToGrey(MarkBit markbit)) {
-    DCHECK(IsBlack(markbit));
-    markbit.Next().Clear();
+  // Warning: this method is not safe in general in concurrent scenarios.
+  // If you know that nobody else will change the bits on the given location
+  // then you may use it.
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static void MarkBlack(MarkBit markbit)) {
+    markbit.Set<mode>();
+    markbit.Next().Set<mode>();
   }
 
-  INLINE(static void WhiteToGrey(MarkBit markbit)) {
-    DCHECK(IsWhite(markbit));
-    markbit.Set();
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool BlackToGrey(MarkBit markbit)) {
+    STATIC_ASSERT(mode == MarkBit::NON_ATOMIC);
+    DCHECK(IsBlack(markbit));
+    return markbit.Next().Clear<mode>();
   }
 
-  INLINE(static void WhiteToBlack(MarkBit markbit)) {
-    DCHECK(IsWhite(markbit));
-    markbit.Set();
-    markbit.Next().Set();
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool WhiteToGrey(MarkBit markbit)) {
+    DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit));
+    return markbit.Set<mode>();
   }
 
-  INLINE(static void GreyToBlack(MarkBit markbit)) {
-    DCHECK(IsGrey(markbit));
-    markbit.Next().Set();
+  // Warning: this method is not safe in general in concurrent scenarios.
+  // If you know that nobody else will change the bits on the given location
+  // then you may use it.
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static void WhiteToBlack(MarkBit markbit)) {
+    DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit));
+    markbit.Set<mode>();
+    markbit.Next().Set<mode>();
+  }
+
+  template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
+  INLINE(static bool GreyToBlack(MarkBit markbit)) {
+    DCHECK(mode == MarkBit::ATOMIC || IsGrey(markbit));
+    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_