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/utils.h"
10
11 namespace v8 {
12 namespace internal {
13
14 class MarkBit {
15 public:
16 using CellType = uint32_t;
17 STATIC_ASSERT(sizeof(CellType) == sizeof(base::Atomic32));
18
MarkBit(CellType * cell,CellType mask)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:
Next()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) >> (kTaggedSizeLog2);
102
103 static const size_t kSize = (1 << kPageSizeBits) >>
104 (kTaggedSizeLog2 + kBitsPerByteLog2);
105
CellsForLength(int length)106 static int CellsForLength(int length) {
107 return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;
108 }
109
CellsCount()110 int CellsCount() { return CellsForLength(kLength); }
111
IndexToCell(uint32_t index)112 V8_INLINE static uint32_t IndexToCell(uint32_t index) {
113 return index >> kBitsPerCellLog2;
114 }
115
IndexInCell(uint32_t index)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.
CellAlignIndex(uint32_t index)121 V8_INLINE static uint32_t CellAlignIndex(uint32_t index) {
122 return index & ~kBitIndexMask;
123 }
124
cells()125 V8_INLINE MarkBit::CellType* cells() {
126 return reinterpret_cast<MarkBit::CellType*>(this);
127 }
128
FromAddress(Address addr)129 V8_INLINE static Bitmap* FromAddress(Address addr) {
130 return reinterpret_cast<Bitmap*>(addr);
131 }
132
MarkBitFromIndex(uint32_t index)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
140 template <AccessMode mode>
141 class ConcurrentBitmap : public Bitmap {
142 public:
143 void Clear();
144
145 void MarkAllBits();
146
147 // Clears bits in the given cell. The mask specifies bits to clear: if a
148 // bit is set in the mask then the corresponding bit is cleared in the cell.
149 void ClearBitsInCell(uint32_t cell_index, uint32_t mask);
150
151 // Sets bits in the given cell. The mask specifies bits to set: if a
152 // bit is set in the mask then the corresponding bit is set in the cell.
153 void SetBitsInCell(uint32_t cell_index, uint32_t mask);
154
155 // Sets all bits in the range [start_index, end_index). If the access is
156 // atomic, the cells at the boundary of the range are updated with atomic
157 // compare and swap operation. The inner cells are updated with relaxed write.
158 void SetRange(uint32_t start_index, uint32_t end_index);
159
160 // Clears all bits in the range [start_index, end_index). If the access is
161 // atomic, the cells at the boundary of the range are updated with atomic
162 // compare and swap operation. The inner cells are updated with relaxed write.
163 void ClearRange(uint32_t start_index, uint32_t end_index);
164
165 // The following methods are *not* safe to use in a concurrent context so they
166 // are not implemented for `AccessMode::ATOMIC`.
167
168 // Returns true if all bits in the range [start_index, end_index) are set.
169 bool AllBitsSetInRange(uint32_t start_index, uint32_t end_index);
170
171 // Returns true if all bits in the range [start_index, end_index) are cleared.
172 bool AllBitsClearInRange(uint32_t start_index, uint32_t end_index);
173
174 void Print();
175
176 bool IsClean();
177
178 private:
179 // Clear all bits in the cell range [start_cell_index, end_cell_index). If the
180 // access is atomic then *still* use a relaxed memory ordering.
181 void ClearCellRangeRelaxed(uint32_t start_cell_index,
182 uint32_t end_cell_index);
183
184 // Set all bits in the cell range [start_cell_index, end_cell_index). If the
185 // access is atomic then *still* use a relaxed memory ordering.
186 void SetCellRangeRelaxed(uint32_t start_cell_index, uint32_t end_cell_index);
187 };
188
189 template <>
ClearCellRangeRelaxed(uint32_t start_cell_index,uint32_t end_cell_index)190 inline void ConcurrentBitmap<AccessMode::ATOMIC>::ClearCellRangeRelaxed(
191 uint32_t start_cell_index, uint32_t end_cell_index) {
192 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
193 for (uint32_t i = start_cell_index; i < end_cell_index; i++) {
194 base::Relaxed_Store(cell_base + i, 0);
195 }
196 }
197
198 template <>
ClearCellRangeRelaxed(uint32_t start_cell_index,uint32_t end_cell_index)199 inline void ConcurrentBitmap<AccessMode::NON_ATOMIC>::ClearCellRangeRelaxed(
200 uint32_t start_cell_index, uint32_t end_cell_index) {
201 for (uint32_t i = start_cell_index; i < end_cell_index; i++) {
202 cells()[i] = 0;
203 }
204 }
205
206 template <>
SetCellRangeRelaxed(uint32_t start_cell_index,uint32_t end_cell_index)207 inline void ConcurrentBitmap<AccessMode::ATOMIC>::SetCellRangeRelaxed(
208 uint32_t start_cell_index, uint32_t end_cell_index) {
209 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
210 for (uint32_t i = start_cell_index; i < end_cell_index; i++) {
211 base::Relaxed_Store(cell_base + i, 0xffffffff);
212 }
213 }
214
215 template <>
SetCellRangeRelaxed(uint32_t start_cell_index,uint32_t end_cell_index)216 inline void ConcurrentBitmap<AccessMode::NON_ATOMIC>::SetCellRangeRelaxed(
217 uint32_t start_cell_index, uint32_t end_cell_index) {
218 for (uint32_t i = start_cell_index; i < end_cell_index; i++) {
219 cells()[i] = 0xffffffff;
220 }
221 }
222
223 template <AccessMode mode>
Clear()224 inline void ConcurrentBitmap<mode>::Clear() {
225 ClearCellRangeRelaxed(0, CellsCount());
226 if (mode == AccessMode::ATOMIC) {
227 // This fence prevents re-ordering of publishing stores with the mark-bit
228 // setting stores.
229 base::SeqCst_MemoryFence();
230 }
231 }
232
233 template <AccessMode mode>
MarkAllBits()234 inline void ConcurrentBitmap<mode>::MarkAllBits() {
235 SetCellRangeRelaxed(0, CellsCount());
236 if (mode == AccessMode::ATOMIC) {
237 // This fence prevents re-ordering of publishing stores with the mark-bit
238 // setting stores.
239 base::SeqCst_MemoryFence();
240 }
241 }
242
243 template <>
SetBitsInCell(uint32_t cell_index,uint32_t mask)244 inline void ConcurrentBitmap<AccessMode::NON_ATOMIC>::SetBitsInCell(
245 uint32_t cell_index, uint32_t mask) {
246 cells()[cell_index] |= mask;
247 }
248
249 template <>
SetBitsInCell(uint32_t cell_index,uint32_t mask)250 inline void ConcurrentBitmap<AccessMode::ATOMIC>::SetBitsInCell(
251 uint32_t cell_index, uint32_t mask) {
252 base::AsAtomic32::SetBits(cells() + cell_index, mask, mask);
253 }
254
255 template <>
ClearBitsInCell(uint32_t cell_index,uint32_t mask)256 inline void ConcurrentBitmap<AccessMode::NON_ATOMIC>::ClearBitsInCell(
257 uint32_t cell_index, uint32_t mask) {
258 cells()[cell_index] &= ~mask;
259 }
260
261 template <>
ClearBitsInCell(uint32_t cell_index,uint32_t mask)262 inline void ConcurrentBitmap<AccessMode::ATOMIC>::ClearBitsInCell(
263 uint32_t cell_index, uint32_t mask) {
264 base::AsAtomic32::SetBits(cells() + cell_index, 0u, mask);
265 }
266
267 template <AccessMode mode>
SetRange(uint32_t start_index,uint32_t end_index)268 void ConcurrentBitmap<mode>::SetRange(uint32_t start_index,
269 uint32_t end_index) {
270 if (start_index >= end_index) return;
271 end_index--;
272
273 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
274 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
275
276 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
277 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
278
279 if (start_cell_index != end_cell_index) {
280 // Firstly, fill all bits from the start address to the end of the first
281 // cell with 1s.
282 SetBitsInCell(start_cell_index, ~(start_index_mask - 1));
283 // Then fill all in between cells with 1s.
284 SetCellRangeRelaxed(start_cell_index + 1, end_cell_index);
285 // Finally, fill all bits until the end address in the last cell with 1s.
286 SetBitsInCell(end_cell_index, end_index_mask | (end_index_mask - 1));
287 } else {
288 SetBitsInCell(start_cell_index,
289 end_index_mask | (end_index_mask - start_index_mask));
290 }
291 if (mode == AccessMode::ATOMIC) {
292 // This fence prevents re-ordering of publishing stores with the mark-bit
293 // setting stores.
294 base::SeqCst_MemoryFence();
295 }
296 }
297
298 template <AccessMode mode>
ClearRange(uint32_t start_index,uint32_t end_index)299 void ConcurrentBitmap<mode>::ClearRange(uint32_t start_index,
300 uint32_t end_index) {
301 if (start_index >= end_index) return;
302 end_index--;
303
304 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
305 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
306
307 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
308 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
309
310 if (start_cell_index != end_cell_index) {
311 // Firstly, fill all bits from the start address to the end of the first
312 // cell with 0s.
313 ClearBitsInCell(start_cell_index, ~(start_index_mask - 1));
314 // Then fill all in between cells with 0s.
315 ClearCellRangeRelaxed(start_cell_index + 1, end_cell_index);
316 // Finally, set all bits until the end address in the last cell with 0s.
317 ClearBitsInCell(end_cell_index, end_index_mask | (end_index_mask - 1));
318 } else {
319 ClearBitsInCell(start_cell_index,
320 end_index_mask | (end_index_mask - start_index_mask));
321 }
322 if (mode == AccessMode::ATOMIC) {
323 // This fence prevents re-ordering of publishing stores with the mark-bit
324 // clearing stores.
325 base::SeqCst_MemoryFence();
326 }
327 }
328
329 template <>
330 V8_EXPORT_PRIVATE bool
331 ConcurrentBitmap<AccessMode::NON_ATOMIC>::AllBitsSetInRange(
332 uint32_t start_index, uint32_t end_index);
333
334 template <>
335 V8_EXPORT_PRIVATE bool
336 ConcurrentBitmap<AccessMode::NON_ATOMIC>::AllBitsClearInRange(
337 uint32_t start_index, uint32_t end_index);
338
339 template <>
340 void ConcurrentBitmap<AccessMode::NON_ATOMIC>::Print();
341
342 template <>
343 V8_EXPORT_PRIVATE bool ConcurrentBitmap<AccessMode::NON_ATOMIC>::IsClean();
344
345 class Marking : public AllStatic {
346 public:
347 // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC
348 // mode for access. We should remove the default value or switch it with
349 // ATOMIC as soon we add concurrency.
350
351 // Impossible markbits: 01
352 static const char* kImpossibleBitPattern;
353 template <AccessMode mode = AccessMode::NON_ATOMIC>
IsImpossible(MarkBit mark_bit)354 V8_INLINE static bool IsImpossible(MarkBit mark_bit) {
355 if (mode == AccessMode::NON_ATOMIC) {
356 return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
357 }
358 // If we are in concurrent mode we can only tell if an object has the
359 // impossible bit pattern if we read the first bit again after reading
360 // the first and the second bit. If the first bit is till zero and the
361 // second bit is one then the object has the impossible bit pattern.
362 bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
363 if (is_impossible) {
364 return !mark_bit.Get<mode>();
365 }
366 return false;
367 }
368
369 // Black markbits: 11
370 static const char* kBlackBitPattern;
371 template <AccessMode mode = AccessMode::NON_ATOMIC>
IsBlack(MarkBit mark_bit)372 V8_INLINE static bool IsBlack(MarkBit mark_bit) {
373 return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
374 }
375
376 // White markbits: 00 - this is required by the mark bit clearer.
377 static const char* kWhiteBitPattern;
378 template <AccessMode mode = AccessMode::NON_ATOMIC>
IsWhite(MarkBit mark_bit)379 V8_INLINE static bool IsWhite(MarkBit mark_bit) {
380 DCHECK(!IsImpossible<mode>(mark_bit));
381 return !mark_bit.Get<mode>();
382 }
383
384 // Grey markbits: 10
385 static const char* kGreyBitPattern;
386 template <AccessMode mode = AccessMode::NON_ATOMIC>
IsGrey(MarkBit mark_bit)387 V8_INLINE static bool IsGrey(MarkBit mark_bit) {
388 return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>();
389 }
390
391 // IsBlackOrGrey assumes that the first bit is set for black or grey
392 // objects.
393 template <AccessMode mode = AccessMode::NON_ATOMIC>
IsBlackOrGrey(MarkBit mark_bit)394 V8_INLINE static bool IsBlackOrGrey(MarkBit mark_bit) {
395 return mark_bit.Get<mode>();
396 }
397
398 template <AccessMode mode = AccessMode::NON_ATOMIC>
MarkWhite(MarkBit markbit)399 V8_INLINE static void MarkWhite(MarkBit markbit) {
400 STATIC_ASSERT(mode == AccessMode::NON_ATOMIC);
401 markbit.Clear<mode>();
402 markbit.Next().Clear<mode>();
403 }
404
405 // Warning: this method is not safe in general in concurrent scenarios.
406 // If you know that nobody else will change the bits on the given location
407 // then you may use it.
408 template <AccessMode mode = AccessMode::NON_ATOMIC>
MarkBlack(MarkBit markbit)409 V8_INLINE static void MarkBlack(MarkBit markbit) {
410 markbit.Set<mode>();
411 markbit.Next().Set<mode>();
412 }
413
414 template <AccessMode mode = AccessMode::NON_ATOMIC>
WhiteToGrey(MarkBit markbit)415 V8_INLINE static bool WhiteToGrey(MarkBit markbit) {
416 return markbit.Set<mode>();
417 }
418
419 template <AccessMode mode = AccessMode::NON_ATOMIC>
WhiteToBlack(MarkBit markbit)420 V8_INLINE static bool WhiteToBlack(MarkBit markbit) {
421 return markbit.Set<mode>() && markbit.Next().Set<mode>();
422 }
423
424 template <AccessMode mode = AccessMode::NON_ATOMIC>
GreyToBlack(MarkBit markbit)425 V8_INLINE static bool GreyToBlack(MarkBit markbit) {
426 return markbit.Get<mode>() && markbit.Next().Set<mode>();
427 }
428
429 enum ObjectColor {
430 BLACK_OBJECT,
431 WHITE_OBJECT,
432 GREY_OBJECT,
433 IMPOSSIBLE_COLOR
434 };
435
ColorName(ObjectColor color)436 static const char* ColorName(ObjectColor color) {
437 switch (color) {
438 case BLACK_OBJECT:
439 return "black";
440 case WHITE_OBJECT:
441 return "white";
442 case GREY_OBJECT:
443 return "grey";
444 case IMPOSSIBLE_COLOR:
445 return "impossible";
446 }
447 return "error";
448 }
449
Color(MarkBit mark_bit)450 static ObjectColor Color(MarkBit mark_bit) {
451 if (IsBlack(mark_bit)) return BLACK_OBJECT;
452 if (IsWhite(mark_bit)) return WHITE_OBJECT;
453 if (IsGrey(mark_bit)) return GREY_OBJECT;
454 UNREACHABLE();
455 }
456
457 private:
458 DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
459 };
460
461 } // namespace internal
462 } // namespace v8
463
464 #endif // V8_HEAP_MARKING_H_
465