OLD | NEW |
---|---|
1 // Copyright 2016 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_MARKING_H | 5 #ifndef V8_MARKING_H |
6 #define V8_MARKING_H | 6 #define V8_MARKING_H |
7 | 7 |
8 #include "src/base/atomic-utils.h" | |
8 #include "src/utils.h" | 9 #include "src/utils.h" |
9 | 10 |
10 namespace v8 { | 11 namespace v8 { |
11 namespace internal { | 12 namespace internal { |
12 | 13 |
13 class MarkBit { | 14 class MarkBit { |
14 public: | 15 public: |
15 typedef uint32_t CellType; | 16 typedef uint32_t CellType; |
17 STATIC_ASSERT(sizeof(CellType) == sizeof(base::Atomic32)); | |
16 | 18 |
17 inline MarkBit(CellType* cell, CellType mask) : cell_(cell), mask_(mask) {} | 19 enum AccessMode { ATOMIC, NON_ATOMIC }; |
20 | |
21 inline MarkBit(base::Atomic32* cell, CellType mask) : cell_(cell) { | |
22 mask_ = static_cast<base::Atomic32>(mask); | |
23 } | |
18 | 24 |
19 #ifdef DEBUG | 25 #ifdef DEBUG |
20 bool operator==(const MarkBit& other) { | 26 bool operator==(const MarkBit& other) { |
21 return cell_ == other.cell_ && mask_ == other.mask_; | 27 return cell_ == other.cell_ && mask_ == other.mask_; |
22 } | 28 } |
23 #endif | 29 #endif |
24 | 30 |
25 private: | 31 private: |
26 inline CellType* cell() { return cell_; } | |
27 inline CellType mask() { return mask_; } | |
28 | |
29 inline MarkBit Next() { | 32 inline MarkBit Next() { |
30 CellType new_mask = mask_ << 1; | 33 CellType new_mask = mask_ << 1; |
31 if (new_mask == 0) { | 34 if (new_mask == 0) { |
32 return MarkBit(cell_ + 1, 1); | 35 return MarkBit(cell_ + 1, 1); |
33 } else { | 36 } else { |
34 return MarkBit(cell_, new_mask); | 37 return MarkBit(cell_, new_mask); |
35 } | 38 } |
36 } | 39 } |
37 | 40 |
38 inline void Set() { *cell_ |= mask_; } | 41 template <AccessMode mode = NON_ATOMIC> |
39 inline bool Get() { return (*cell_ & mask_) != 0; } | 42 inline bool Set() { |
40 inline void Clear() { *cell_ &= ~mask_; } | 43 if (mode == ATOMIC) { |
44 base::Atomic32 old_value; | |
45 base::Atomic32 new_value; | |
46 do { | |
47 old_value = base::NoBarrier_Load(cell_); | |
48 if (old_value & mask_) return false; | |
49 new_value = old_value | mask_; | |
50 } while (base::Release_CompareAndSwap(cell_, old_value, new_value) != | |
51 old_value); | |
52 } else { | |
53 *cell_ |= mask_; | |
54 } | |
55 return true; | |
56 } | |
41 | 57 |
42 CellType* cell_; | 58 template <AccessMode mode = NON_ATOMIC> |
43 CellType mask_; | 59 inline bool Get() { |
60 if (mode == ATOMIC) { | |
61 return (base::Acquire_Load(cell_) & mask_) != 0; | |
62 } else { | |
63 return (base::NoBarrier_Load(cell_) & mask_) != 0; | |
64 } | |
65 } | |
66 | |
67 template <AccessMode mode = NON_ATOMIC> | |
68 inline bool Clear() { | |
69 if (mode == ATOMIC) { | |
70 base::Atomic32 old_value; | |
71 base::Atomic32 new_value; | |
72 do { | |
73 old_value = base::NoBarrier_Load(cell_); | |
74 if (!(old_value & mask_)) return false; | |
75 new_value = old_value & ~mask_; | |
76 } while (base::Release_CompareAndSwap(cell_, old_value, new_value) != | |
77 old_value); | |
78 } else { | |
79 *cell_ &= ~mask_; | |
80 } | |
81 return true; | |
82 } | |
83 | |
84 base::Atomic32* cell_; | |
85 base::Atomic32 mask_; | |
44 | 86 |
45 friend class IncrementalMarking; | 87 friend class IncrementalMarking; |
46 friend class ConcurrentMarkingMarkbits; | 88 friend class ConcurrentMarkingMarkbits; |
47 friend class Marking; | 89 friend class Marking; |
48 }; | 90 }; |
49 | 91 |
50 // Bitmap is a sequence of cells each containing fixed number of bits. | 92 // Bitmap is a sequence of cells each containing fixed number of bits. |
51 class Bitmap { | 93 class Bitmap { |
52 public: | 94 public: |
53 static const uint32_t kBitsPerCell = 32; | 95 static const uint32_t kBitsPerCell = 32; |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
93 | 135 |
94 INLINE(Address address()) { return reinterpret_cast<Address>(this); } | 136 INLINE(Address address()) { return reinterpret_cast<Address>(this); } |
95 | 137 |
96 INLINE(static Bitmap* FromAddress(Address addr)) { | 138 INLINE(static Bitmap* FromAddress(Address addr)) { |
97 return reinterpret_cast<Bitmap*>(addr); | 139 return reinterpret_cast<Bitmap*>(addr); |
98 } | 140 } |
99 | 141 |
100 inline MarkBit MarkBitFromIndex(uint32_t index) { | 142 inline MarkBit MarkBitFromIndex(uint32_t index) { |
101 MarkBit::CellType mask = 1u << IndexInCell(index); | 143 MarkBit::CellType mask = 1u << IndexInCell(index); |
102 MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2); | 144 MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2); |
103 return MarkBit(cell, mask); | 145 return MarkBit(reinterpret_cast<base::Atomic32*>(cell), mask); |
104 } | 146 } |
105 | 147 |
106 void Clear() { | 148 void Clear() { |
107 for (int i = 0; i < CellsCount(); i++) cells()[i] = 0; | 149 for (int i = 0; i < CellsCount(); i++) cells()[i] = 0; |
108 } | 150 } |
109 | 151 |
110 // Sets all bits in the range [start_index, end_index). | 152 // Sets all bits in the range [start_index, end_index). |
111 void SetRange(uint32_t start_index, uint32_t end_index) { | 153 void SetRange(uint32_t start_index, uint32_t end_index) { |
112 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2; | 154 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2; |
113 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index); | 155 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index); |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
263 if (cells()[i] != 0) { | 305 if (cells()[i] != 0) { |
264 return false; | 306 return false; |
265 } | 307 } |
266 } | 308 } |
267 return true; | 309 return true; |
268 } | 310 } |
269 }; | 311 }; |
270 | 312 |
271 class Marking : public AllStatic { | 313 class Marking : public AllStatic { |
272 public: | 314 public: |
315 // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC | |
316 // mode for access. We should remove the default value or switch it with | |
317 // ATOMIC as soon we add concurrency. | |
318 | |
273 // Impossible markbits: 01 | 319 // Impossible markbits: 01 |
274 static const char* kImpossibleBitPattern; | 320 static const char* kImpossibleBitPattern; |
321 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
275 INLINE(static bool IsImpossible(MarkBit mark_bit)) { | 322 INLINE(static bool IsImpossible(MarkBit mark_bit)) { |
276 return !mark_bit.Get() && mark_bit.Next().Get(); | 323 if (mode == MarkBit::NON_ATOMIC) { |
324 return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); | |
325 } | |
326 // If we are in concurrent mode we can only tell if an object has the | |
327 // impossible bit pattern if we read the first bit again after reading | |
328 // the first and the second bit. If the first bit is till zero and the | |
329 // second bit is one then the object has the impossible bit pattern. | |
330 bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); | |
331 if (is_impossible) { | |
332 return !mark_bit.Get<mode>(); | |
333 } | |
334 return false; | |
277 } | 335 } |
278 | 336 |
279 // Black markbits: 11 | 337 // Black markbits: 11 |
280 static const char* kBlackBitPattern; | 338 static const char* kBlackBitPattern; |
339 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
281 INLINE(static bool IsBlack(MarkBit mark_bit)) { | 340 INLINE(static bool IsBlack(MarkBit mark_bit)) { |
282 return mark_bit.Get() && mark_bit.Next().Get(); | 341 return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); |
283 } | 342 } |
284 | 343 |
285 // White markbits: 00 - this is required by the mark bit clearer. | 344 // White markbits: 00 - this is required by the mark bit clearer. |
286 static const char* kWhiteBitPattern; | 345 static const char* kWhiteBitPattern; |
346 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
287 INLINE(static bool IsWhite(MarkBit mark_bit)) { | 347 INLINE(static bool IsWhite(MarkBit mark_bit)) { |
288 DCHECK(!IsImpossible(mark_bit)); | 348 DCHECK(!IsImpossible(mark_bit)); |
289 return !mark_bit.Get(); | 349 return !mark_bit.Get<mode>(); |
290 } | 350 } |
291 | 351 |
292 // Grey markbits: 10 | 352 // Grey markbits: 10 |
293 static const char* kGreyBitPattern; | 353 static const char* kGreyBitPattern; |
354 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
294 INLINE(static bool IsGrey(MarkBit mark_bit)) { | 355 INLINE(static bool IsGrey(MarkBit mark_bit)) { |
295 return mark_bit.Get() && !mark_bit.Next().Get(); | 356 return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>(); |
296 } | 357 } |
297 | 358 |
298 // IsBlackOrGrey assumes that the first bit is set for black or grey | 359 // IsBlackOrGrey assumes that the first bit is set for black or grey |
299 // objects. | 360 // objects. |
300 INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) { return mark_bit.Get(); } | 361 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> |
301 | 362 INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) { |
302 INLINE(static void MarkWhite(MarkBit markbit)) { | 363 return mark_bit.Get<mode>(); |
303 markbit.Clear(); | |
304 markbit.Next().Clear(); | |
305 } | 364 } |
306 | 365 |
307 INLINE(static void MarkGrey(MarkBit markbit)) { markbit.Set(); } | 366 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> |
308 | 367 INLINE(static void MarkWhite(MarkBit markbit)) { |
309 INLINE(static void MarkBlack(MarkBit markbit)) { | 368 STATIC_ASSERT(mode == MarkBit::NON_ATOMIC); |
310 markbit.Set(); | 369 markbit.Clear<mode>(); |
311 markbit.Next().Set(); | 370 markbit.Next().Clear<mode>(); |
312 } | 371 } |
313 | 372 |
314 INLINE(static void BlackToGrey(MarkBit markbit)) { | 373 // Warning: this method is not safe in general in concurrent scenarios. |
315 DCHECK(IsBlack(markbit)); | 374 // If you know that nobody else will change the bits on the given location |
316 markbit.Next().Clear(); | 375 // then you may use it. |
376 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
377 INLINE(static void MarkBlack(MarkBit markbit)) { | |
378 markbit.Set<mode>(); | |
379 markbit.Next().Set<mode>(); | |
317 } | 380 } |
318 | 381 |
319 INLINE(static void WhiteToGrey(MarkBit markbit)) { | 382 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> |
320 DCHECK(IsWhite(markbit)); | 383 INLINE(static bool BlackToGrey(MarkBit markbit)) { |
321 markbit.Set(); | 384 DCHECK(mode == MarkBit::ATOMIC || IsBlack(markbit)); |
ulan
2017/03/08 14:42:01
STATIC_ASSERT(mode == MarkBit::NON_ATOMIC)
Hannes Payer (out of office)
2017/03/08 15:55:00
Done.
| |
385 return markbit.Next().Clear<mode>(); | |
322 } | 386 } |
323 | 387 |
324 INLINE(static void WhiteToBlack(MarkBit markbit)) { | 388 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> |
325 DCHECK(IsWhite(markbit)); | 389 INLINE(static bool WhiteToGrey(MarkBit markbit)) { |
326 markbit.Set(); | 390 DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit)); |
327 markbit.Next().Set(); | 391 return markbit.Set<mode>(); |
328 } | 392 } |
329 | 393 |
330 INLINE(static void GreyToBlack(MarkBit markbit)) { | 394 // Warning: this method is not safe in general in concurrent scenarios. |
331 DCHECK(IsGrey(markbit)); | 395 // If you know that nobody else will change the bits on the given location |
332 markbit.Next().Set(); | 396 // then you may use it. |
397 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
398 INLINE(static void WhiteToBlack(MarkBit markbit)) { | |
399 DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit)); | |
400 markbit.Set<mode>(); | |
401 markbit.Next().Set<mode>(); | |
402 } | |
403 | |
404 template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC> | |
405 INLINE(static bool GreyToBlack(MarkBit markbit)) { | |
406 DCHECK(mode == MarkBit::ATOMIC || IsGrey(markbit)); | |
407 return markbit.Next().Set<mode>(); | |
333 } | 408 } |
334 | 409 |
335 enum ObjectColor { | 410 enum ObjectColor { |
336 BLACK_OBJECT, | 411 BLACK_OBJECT, |
337 WHITE_OBJECT, | 412 WHITE_OBJECT, |
338 GREY_OBJECT, | 413 GREY_OBJECT, |
339 IMPOSSIBLE_COLOR | 414 IMPOSSIBLE_COLOR |
340 }; | 415 }; |
341 | 416 |
342 static const char* ColorName(ObjectColor color) { | 417 static const char* ColorName(ObjectColor color) { |
(...skipping 19 matching lines...) Expand all Loading... | |
362 } | 437 } |
363 | 438 |
364 private: | 439 private: |
365 DISALLOW_IMPLICIT_CONSTRUCTORS(Marking); | 440 DISALLOW_IMPLICIT_CONSTRUCTORS(Marking); |
366 }; | 441 }; |
367 | 442 |
368 } // namespace internal | 443 } // namespace internal |
369 } // namespace v8 | 444 } // namespace v8 |
370 | 445 |
371 #endif // V8_MARKING_H_ | 446 #endif // V8_MARKING_H_ |
OLD | NEW |