V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
marking.h
1 // Copyright 2016 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_HEAP_MARKING_H_
6 #define V8_HEAP_MARKING_H_
7 
8 #include "src/base/atomic-utils.h"
9 #include "src/utils.h"
10 
11 namespace v8 {
12 namespace internal {
13 
14 class MarkBit {
15  public:
16  typedef uint32_t CellType;
17  STATIC_ASSERT(sizeof(CellType) == sizeof(base::Atomic32));
18 
19  inline MarkBit(CellType* cell, CellType mask) : cell_(cell), mask_(mask) {}
20 
21 #ifdef DEBUG
22  bool operator==(const MarkBit& other) {
23  return cell_ == other.cell_ && mask_ == other.mask_;
24  }
25 #endif
26 
27  private:
28  inline MarkBit Next() {
29  CellType new_mask = mask_ << 1;
30  if (new_mask == 0) {
31  return MarkBit(cell_ + 1, 1);
32  } else {
33  return MarkBit(cell_, new_mask);
34  }
35  }
36 
37  // The function returns true if it succeeded to
38  // transition the bit from 0 to 1.
39  template <AccessMode mode = AccessMode::NON_ATOMIC>
40  inline bool Set();
41 
42  template <AccessMode mode = AccessMode::NON_ATOMIC>
43  inline bool Get();
44 
45  // The function returns true if it succeeded to
46  // transition the bit from 1 to 0.
47  template <AccessMode mode = AccessMode::NON_ATOMIC>
48  inline bool Clear();
49 
50  CellType* cell_;
51  CellType mask_;
52 
53  friend class IncrementalMarking;
54  friend class ConcurrentMarkingMarkbits;
55  friend class Marking;
56 };
57 
58 template <>
59 inline bool MarkBit::Set<AccessMode::NON_ATOMIC>() {
60  CellType old_value = *cell_;
61  *cell_ = old_value | mask_;
62  return (old_value & mask_) == 0;
63 }
64 
65 template <>
66 inline bool MarkBit::Set<AccessMode::ATOMIC>() {
67  return base::AsAtomic32::SetBits(cell_, mask_, mask_);
68 }
69 
70 template <>
71 inline bool MarkBit::Get<AccessMode::NON_ATOMIC>() {
72  return (*cell_ & mask_) != 0;
73 }
74 
75 template <>
76 inline bool MarkBit::Get<AccessMode::ATOMIC>() {
77  return (base::AsAtomic32::Acquire_Load(cell_) & mask_) != 0;
78 }
79 
80 template <>
81 inline bool MarkBit::Clear<AccessMode::NON_ATOMIC>() {
82  CellType old_value = *cell_;
83  *cell_ = old_value & ~mask_;
84  return (old_value & mask_) == mask_;
85 }
86 
87 template <>
88 inline bool MarkBit::Clear<AccessMode::ATOMIC>() {
89  return base::AsAtomic32::SetBits(cell_, 0u, mask_);
90 }
91 
92 // Bitmap is a sequence of cells each containing fixed number of bits.
93 class V8_EXPORT_PRIVATE Bitmap {
94  public:
95  static const uint32_t kBitsPerCell = 32;
96  static const uint32_t kBitsPerCellLog2 = 5;
97  static const uint32_t kBitIndexMask = kBitsPerCell - 1;
98  static const uint32_t kBytesPerCell = kBitsPerCell / kBitsPerByte;
99  static const uint32_t kBytesPerCellLog2 = kBitsPerCellLog2 - kBitsPerByteLog2;
100 
101  static const size_t kLength = (1 << kPageSizeBits) >> (kPointerSizeLog2);
102 
103  static const size_t kSize = (1 << kPageSizeBits) >>
104  (kPointerSizeLog2 + kBitsPerByteLog2);
105 
106  static int CellsForLength(int length) {
107  return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;
108  }
109 
110  int CellsCount() { return CellsForLength(kLength); }
111 
112  V8_INLINE static uint32_t IndexToCell(uint32_t index) {
113  return index >> kBitsPerCellLog2;
114  }
115 
116  V8_INLINE static uint32_t IndexInCell(uint32_t index) {
117  return index & kBitIndexMask;
118  }
119 
120  // Retrieves the cell containing the provided markbit index.
121  V8_INLINE static uint32_t CellAlignIndex(uint32_t index) {
122  return index & ~kBitIndexMask;
123  }
124 
125  V8_INLINE MarkBit::CellType* cells() {
126  return reinterpret_cast<MarkBit::CellType*>(this);
127  }
128 
129  V8_INLINE static Bitmap* FromAddress(Address addr) {
130  return reinterpret_cast<Bitmap*>(addr);
131  }
132 
133  inline MarkBit MarkBitFromIndex(uint32_t index) {
134  MarkBit::CellType mask = 1u << IndexInCell(index);
135  MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
136  return MarkBit(cell, mask);
137  }
138 
139  void Clear();
140 
141  void MarkAllBits();
142 
143  // Clears bits in the given cell. The mask specifies bits to clear: if a
144  // bit is set in the mask then the corresponding bit is cleared in the cell.
145  template <AccessMode mode = AccessMode::NON_ATOMIC>
146  void ClearBitsInCell(uint32_t cell_index, uint32_t mask);
147 
148  // Sets bits in the given cell. The mask specifies bits to set: if a
149  // bit is set in the mask then the corresponding bit is set in the cell.
150  template <AccessMode mode = AccessMode::NON_ATOMIC>
151  void SetBitsInCell(uint32_t cell_index, uint32_t mask);
152 
153  // Sets all bits in the range [start_index, end_index). The cells at the
154  // boundary of the range are updated with atomic compare and swap operation.
155  // The inner cells are updated with relaxed write.
156  void SetRange(uint32_t start_index, uint32_t end_index);
157 
158  // Clears all bits in the range [start_index, end_index). The cells at the
159  // boundary of the range are updated with atomic compare and swap operation.
160  // The inner cells are updated with relaxed write.
161  void ClearRange(uint32_t start_index, uint32_t end_index);
162 
163  // Returns true if all bits in the range [start_index, end_index) are set.
164  bool AllBitsSetInRange(uint32_t start_index, uint32_t end_index);
165 
166  // Returns true if all bits in the range [start_index, end_index) are cleared.
167  bool AllBitsClearInRange(uint32_t start_index, uint32_t end_index);
168 
169  void Print();
170 
171  bool IsClean();
172 };
173 
174 template <>
175 inline void Bitmap::SetBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index,
176  uint32_t mask) {
177  cells()[cell_index] |= mask;
178 }
179 
180 template <>
181 inline void Bitmap::SetBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index,
182  uint32_t mask) {
183  base::AsAtomic32::SetBits(cells() + cell_index, mask, mask);
184 }
185 
186 template <>
187 inline void Bitmap::ClearBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index,
188  uint32_t mask) {
189  cells()[cell_index] &= ~mask;
190 }
191 
192 template <>
193 inline void Bitmap::ClearBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index,
194  uint32_t mask) {
195  base::AsAtomic32::SetBits(cells() + cell_index, 0u, mask);
196 }
197 
198 class Marking : public AllStatic {
199  public:
200  // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC
201  // mode for access. We should remove the default value or switch it with
202  // ATOMIC as soon we add concurrency.
203 
204  // Impossible markbits: 01
205  static const char* kImpossibleBitPattern;
206  template <AccessMode mode = AccessMode::NON_ATOMIC>
207  V8_INLINE static bool IsImpossible(MarkBit mark_bit) {
208  if (mode == AccessMode::NON_ATOMIC) {
209  return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
210  }
211  // If we are in concurrent mode we can only tell if an object has the
212  // impossible bit pattern if we read the first bit again after reading
213  // the first and the second bit. If the first bit is till zero and the
214  // second bit is one then the object has the impossible bit pattern.
215  bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
216  if (is_impossible) {
217  return !mark_bit.Get<mode>();
218  }
219  return false;
220  }
221 
222  // Black markbits: 11
223  static const char* kBlackBitPattern;
224  template <AccessMode mode = AccessMode::NON_ATOMIC>
225  V8_INLINE static bool IsBlack(MarkBit mark_bit) {
226  return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
227  }
228 
229  // White markbits: 00 - this is required by the mark bit clearer.
230  static const char* kWhiteBitPattern;
231  template <AccessMode mode = AccessMode::NON_ATOMIC>
232  V8_INLINE static bool IsWhite(MarkBit mark_bit) {
233  DCHECK(!IsImpossible<mode>(mark_bit));
234  return !mark_bit.Get<mode>();
235  }
236 
237  // Grey markbits: 10
238  static const char* kGreyBitPattern;
239  template <AccessMode mode = AccessMode::NON_ATOMIC>
240  V8_INLINE static bool IsGrey(MarkBit mark_bit) {
241  return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>();
242  }
243 
244  // IsBlackOrGrey assumes that the first bit is set for black or grey
245  // objects.
246  template <AccessMode mode = AccessMode::NON_ATOMIC>
247  V8_INLINE static bool IsBlackOrGrey(MarkBit mark_bit) {
248  return mark_bit.Get<mode>();
249  }
250 
251  template <AccessMode mode = AccessMode::NON_ATOMIC>
252  V8_INLINE static void MarkWhite(MarkBit markbit) {
253  STATIC_ASSERT(mode == AccessMode::NON_ATOMIC);
254  markbit.Clear<mode>();
255  markbit.Next().Clear<mode>();
256  }
257 
258  // Warning: this method is not safe in general in concurrent scenarios.
259  // If you know that nobody else will change the bits on the given location
260  // then you may use it.
261  template <AccessMode mode = AccessMode::NON_ATOMIC>
262  V8_INLINE static void MarkBlack(MarkBit markbit) {
263  markbit.Set<mode>();
264  markbit.Next().Set<mode>();
265  }
266 
267  template <AccessMode mode = AccessMode::NON_ATOMIC>
268  V8_INLINE static bool WhiteToGrey(MarkBit markbit) {
269  return markbit.Set<mode>();
270  }
271 
272  template <AccessMode mode = AccessMode::NON_ATOMIC>
273  V8_INLINE static bool WhiteToBlack(MarkBit markbit) {
274  return markbit.Set<mode>() && markbit.Next().Set<mode>();
275  }
276 
277  template <AccessMode mode = AccessMode::NON_ATOMIC>
278  V8_INLINE static bool GreyToBlack(MarkBit markbit) {
279  return markbit.Get<mode>() && markbit.Next().Set<mode>();
280  }
281 
282  enum ObjectColor {
283  BLACK_OBJECT,
284  WHITE_OBJECT,
285  GREY_OBJECT,
286  IMPOSSIBLE_COLOR
287  };
288 
289  static const char* ColorName(ObjectColor color) {
290  switch (color) {
291  case BLACK_OBJECT:
292  return "black";
293  case WHITE_OBJECT:
294  return "white";
295  case GREY_OBJECT:
296  return "grey";
297  case IMPOSSIBLE_COLOR:
298  return "impossible";
299  }
300  return "error";
301  }
302 
303  static ObjectColor Color(MarkBit mark_bit) {
304  if (IsBlack(mark_bit)) return BLACK_OBJECT;
305  if (IsWhite(mark_bit)) return WHITE_OBJECT;
306  if (IsGrey(mark_bit)) return GREY_OBJECT;
307  UNREACHABLE();
308  }
309 
310  private:
311  DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
312 };
313 
314 } // namespace internal
315 } // namespace v8
316 
317 #endif // V8_HEAP_MARKING_H_
Definition: libplatform.h:13
Definition: v8.h:3740