Line data Source code
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_MARKING_H
6 : #define V8_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 : enum AccessMode { ATOMIC, NON_ATOMIC };
20 :
21 : inline MarkBit(base::Atomic32* cell, CellType mask) : cell_(cell) {
22 7961668344 : mask_ = static_cast<base::Atomic32>(mask);
23 : }
24 :
25 : #ifdef DEBUG
26 : bool operator==(const MarkBit& other) {
27 : return cell_ == other.cell_ && mask_ == other.mask_;
28 : }
29 : #endif
30 :
31 : private:
32 804617007 : inline MarkBit Next() {
33 804617007 : CellType new_mask = mask_ << 1;
34 804617007 : if (new_mask == 0) {
35 20985810 : return MarkBit(cell_ + 1, 1);
36 : } else {
37 783631197 : return MarkBit(cell_, new_mask);
38 : }
39 : }
40 :
41 : template <AccessMode mode = NON_ATOMIC>
42 : inline bool Set();
43 :
44 : template <AccessMode mode = NON_ATOMIC>
45 : inline bool Get();
46 :
47 : template <AccessMode mode = NON_ATOMIC>
48 : inline bool Clear();
49 :
50 : base::Atomic32* cell_;
51 : base::Atomic32 mask_;
52 :
53 : friend class IncrementalMarking;
54 : friend class ConcurrentMarkingMarkbits;
55 : friend class Marking;
56 : };
57 :
58 : template <>
59 1475105752 : inline bool MarkBit::Set<MarkBit::NON_ATOMIC>() {
60 1475105752 : *cell_ |= mask_;
61 1475105752 : return true;
62 : }
63 :
64 : template <>
65 : inline bool MarkBit::Set<MarkBit::ATOMIC>() {
66 : base::Atomic32 old_value;
67 : base::Atomic32 new_value;
68 : do {
69 : old_value = base::NoBarrier_Load(cell_);
70 : if (old_value & mask_) return false;
71 : new_value = old_value | mask_;
72 : } while (base::Release_CompareAndSwap(cell_, old_value, new_value) !=
73 : old_value);
74 : return true;
75 : }
76 :
77 : template <>
78 6610608817 : inline bool MarkBit::Get<MarkBit::NON_ATOMIC>() {
79 13221217634 : return (base::NoBarrier_Load(cell_) & mask_) != 0;
80 : }
81 :
82 : template <>
83 : inline bool MarkBit::Get<MarkBit::ATOMIC>() {
84 : return (base::Acquire_Load(cell_) & mask_) != 0;
85 : }
86 :
87 : template <>
88 838222 : inline bool MarkBit::Clear<MarkBit::NON_ATOMIC>() {
89 838222 : *cell_ &= ~mask_;
90 838222 : return true;
91 : }
92 :
93 : template <>
94 : inline bool MarkBit::Clear<MarkBit::ATOMIC>() {
95 : base::Atomic32 old_value;
96 : base::Atomic32 new_value;
97 : do {
98 : old_value = base::NoBarrier_Load(cell_);
99 : if (!(old_value & mask_)) return false;
100 : new_value = old_value & ~mask_;
101 : } while (base::Release_CompareAndSwap(cell_, old_value, new_value) !=
102 : old_value);
103 : return true;
104 : }
105 :
106 : // Bitmap is a sequence of cells each containing fixed number of bits.
107 : class Bitmap {
108 : public:
109 : static const uint32_t kBitsPerCell = 32;
110 : static const uint32_t kBitsPerCellLog2 = 5;
111 : static const uint32_t kBitIndexMask = kBitsPerCell - 1;
112 : static const uint32_t kBytesPerCell = kBitsPerCell / kBitsPerByte;
113 : static const uint32_t kBytesPerCellLog2 = kBitsPerCellLog2 - kBitsPerByteLog2;
114 :
115 : static const size_t kLength = (1 << kPageSizeBits) >> (kPointerSizeLog2);
116 :
117 : static const size_t kSize = (1 << kPageSizeBits) >>
118 : (kPointerSizeLog2 + kBitsPerByteLog2);
119 :
120 : static int CellsForLength(int length) {
121 : return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;
122 : }
123 :
124 : int CellsCount() { return CellsForLength(kLength); }
125 :
126 : static int SizeFor(int cells_count) {
127 : return sizeof(MarkBit::CellType) * cells_count;
128 : }
129 :
130 : INLINE(static uint32_t IndexToCell(uint32_t index)) {
131 1242422 : return index >> kBitsPerCellLog2;
132 : }
133 :
134 : V8_INLINE static uint32_t IndexInCell(uint32_t index) {
135 8703929593 : return index & kBitIndexMask;
136 : }
137 :
138 : INLINE(static uint32_t CellToIndex(uint32_t index)) {
139 : return index << kBitsPerCellLog2;
140 : }
141 :
142 : INLINE(static uint32_t CellAlignIndex(uint32_t index)) {
143 1242422 : return (index + kBitIndexMask) & ~kBitIndexMask;
144 : }
145 :
146 : INLINE(MarkBit::CellType* cells()) {
147 : return reinterpret_cast<MarkBit::CellType*>(this);
148 : }
149 :
150 : INLINE(Address address()) { return reinterpret_cast<Address>(this); }
151 :
152 : INLINE(static Bitmap* FromAddress(Address addr)) {
153 : return reinterpret_cast<Bitmap*>(addr);
154 : }
155 :
156 7961668344 : inline MarkBit MarkBitFromIndex(uint32_t index) {
157 7961668344 : MarkBit::CellType mask = 1u << IndexInCell(index);
158 7961668344 : MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
159 7961668344 : return MarkBit(reinterpret_cast<base::Atomic32*>(cell), mask);
160 : }
161 :
162 : void Clear() {
163 3986460672 : for (int i = 0; i < CellsCount(); i++) cells()[i] = 0;
164 : }
165 :
166 : // Sets all bits in the range [start_index, end_index).
167 4184 : void SetRange(uint32_t start_index, uint32_t end_index) {
168 4184 : unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
169 4184 : MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
170 :
171 4184 : unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
172 4184 : MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
173 :
174 4184 : if (start_cell_index != end_cell_index) {
175 : // Firstly, fill all bits from the start address to the end of the first
176 : // cell with 1s.
177 3557 : cells()[start_cell_index] |= ~(start_index_mask - 1);
178 : // Then fill all in between cells with 1s.
179 2154767 : for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
180 2151210 : cells()[i] = ~0u;
181 : }
182 : // Finally, fill all bits until the end address in the last cell with 1s.
183 3557 : cells()[end_cell_index] |= (end_index_mask - 1);
184 : } else {
185 627 : cells()[start_cell_index] |= end_index_mask - start_index_mask;
186 : }
187 4184 : }
188 :
189 : // Clears all bits in the range [start_index, end_index).
190 2901 : void ClearRange(uint32_t start_index, uint32_t end_index) {
191 2901 : unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
192 2901 : MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
193 :
194 2901 : unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
195 2901 : MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
196 :
197 2901 : if (start_cell_index != end_cell_index) {
198 : // Firstly, fill all bits from the start address to the end of the first
199 : // cell with 0s.
200 2478 : cells()[start_cell_index] &= (start_index_mask - 1);
201 : // Then fill all in between cells with 0s.
202 1950273 : for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
203 1947795 : cells()[i] = 0;
204 : }
205 : // Finally, set all bits until the end address in the last cell with 0s.
206 2478 : cells()[end_cell_index] &= ~(end_index_mask - 1);
207 : } else {
208 423 : cells()[start_cell_index] &= ~(end_index_mask - start_index_mask);
209 : }
210 2901 : }
211 :
212 : // Returns true if all bits in the range [start_index, end_index) are set.
213 : bool AllBitsSetInRange(uint32_t start_index, uint32_t end_index) {
214 : unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
215 : MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
216 :
217 : unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
218 : MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
219 :
220 : MarkBit::CellType matching_mask;
221 : if (start_cell_index != end_cell_index) {
222 : matching_mask = ~(start_index_mask - 1);
223 : if ((cells()[start_cell_index] & matching_mask) != matching_mask) {
224 : return false;
225 : }
226 : for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
227 : if (cells()[i] != ~0u) return false;
228 : }
229 : matching_mask = (end_index_mask - 1);
230 : // Check against a mask of 0 to avoid dereferencing the cell after the
231 : // end of the bitmap.
232 : return (matching_mask == 0) ||
233 : ((cells()[end_cell_index] & matching_mask) == matching_mask);
234 : } else {
235 : matching_mask = end_index_mask - start_index_mask;
236 : // Check against a mask of 0 to avoid dereferencing the cell after the
237 : // end of the bitmap.
238 : return (matching_mask == 0) ||
239 : (cells()[end_cell_index] & matching_mask) == matching_mask;
240 : }
241 : }
242 :
243 : // Returns true if all bits in the range [start_index, end_index) are cleared.
244 : bool AllBitsClearInRange(uint32_t start_index, uint32_t end_index) {
245 : unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
246 : MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
247 :
248 : unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
249 : MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
250 :
251 : MarkBit::CellType matching_mask;
252 : if (start_cell_index != end_cell_index) {
253 : matching_mask = ~(start_index_mask - 1);
254 : if ((cells()[start_cell_index] & matching_mask)) return false;
255 : for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
256 : if (cells()[i]) return false;
257 : }
258 : matching_mask = (end_index_mask - 1);
259 : // Check against a mask of 0 to avoid dereferencing the cell after the
260 : // end of the bitmap.
261 : return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
262 : } else {
263 : matching_mask = end_index_mask - start_index_mask;
264 : // Check against a mask of 0 to avoid dereferencing the cell after the
265 : // end of the bitmap.
266 : return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
267 : }
268 : }
269 :
270 : static void PrintWord(uint32_t word, uint32_t himask = 0) {
271 : for (uint32_t mask = 1; mask != 0; mask <<= 1) {
272 : if ((mask & himask) != 0) PrintF("[");
273 : PrintF((mask & word) ? "1" : "0");
274 : if ((mask & himask) != 0) PrintF("]");
275 : }
276 : }
277 :
278 : class CellPrinter {
279 : public:
280 : CellPrinter() : seq_start(0), seq_type(0), seq_length(0) {}
281 :
282 : void Print(uint32_t pos, uint32_t cell) {
283 : if (cell == seq_type) {
284 : seq_length++;
285 : return;
286 : }
287 :
288 : Flush();
289 :
290 : if (IsSeq(cell)) {
291 : seq_start = pos;
292 : seq_length = 0;
293 : seq_type = cell;
294 : return;
295 : }
296 :
297 : PrintF("%d: ", pos);
298 : PrintWord(cell);
299 : PrintF("\n");
300 : }
301 :
302 : void Flush() {
303 : if (seq_length > 0) {
304 : PrintF("%d: %dx%d\n", seq_start, seq_type == 0 ? 0 : 1,
305 : seq_length * kBitsPerCell);
306 : seq_length = 0;
307 : }
308 : }
309 :
310 : static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
311 :
312 : private:
313 : uint32_t seq_start;
314 : uint32_t seq_type;
315 : uint32_t seq_length;
316 : };
317 :
318 : void Print() {
319 : CellPrinter printer;
320 : for (int i = 0; i < CellsCount(); i++) {
321 : printer.Print(i, cells()[i]);
322 : }
323 : printer.Flush();
324 : PrintF("\n");
325 : }
326 :
327 : bool IsClean() {
328 : for (int i = 0; i < CellsCount(); i++) {
329 : if (cells()[i] != 0) {
330 : return false;
331 : }
332 : }
333 : return true;
334 : }
335 : };
336 :
337 : class Marking : public AllStatic {
338 : public:
339 : // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC
340 : // mode for access. We should remove the default value or switch it with
341 : // ATOMIC as soon we add concurrency.
342 :
343 : // Impossible markbits: 01
344 : static const char* kImpossibleBitPattern;
345 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
346 : INLINE(static bool IsImpossible(MarkBit mark_bit)) {
347 : if (mode == MarkBit::NON_ATOMIC) {
348 : return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
349 : }
350 : // If we are in concurrent mode we can only tell if an object has the
351 : // impossible bit pattern if we read the first bit again after reading
352 : // the first and the second bit. If the first bit is till zero and the
353 : // second bit is one then the object has the impossible bit pattern.
354 : bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
355 : if (is_impossible) {
356 : return !mark_bit.Get<mode>();
357 : }
358 : return false;
359 : }
360 :
361 : // Black markbits: 11
362 : static const char* kBlackBitPattern;
363 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
364 : INLINE(static bool IsBlack(MarkBit mark_bit)) {
365 287393018 : return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
366 : }
367 :
368 : // White markbits: 00 - this is required by the mark bit clearer.
369 : static const char* kWhiteBitPattern;
370 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
371 : INLINE(static bool IsWhite(MarkBit mark_bit)) {
372 : DCHECK(!IsImpossible(mark_bit));
373 4214632509 : return !mark_bit.Get<mode>();
374 : }
375 :
376 : // Grey markbits: 10
377 : static const char* kGreyBitPattern;
378 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
379 : INLINE(static bool IsGrey(MarkBit mark_bit)) {
380 2605503 : return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>();
381 : }
382 :
383 : // IsBlackOrGrey assumes that the first bit is set for black or grey
384 : // objects.
385 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
386 : INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) {
387 2040199887 : return mark_bit.Get<mode>();
388 : }
389 :
390 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
391 : INLINE(static void MarkWhite(MarkBit markbit)) {
392 : STATIC_ASSERT(mode == MarkBit::NON_ATOMIC);
393 1582 : markbit.Clear<mode>();
394 1582 : markbit.Next().Clear<mode>();
395 : }
396 :
397 : // Warning: this method is not safe in general in concurrent scenarios.
398 : // If you know that nobody else will change the bits on the given location
399 : // then you may use it.
400 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
401 : INLINE(static void MarkBlack(MarkBit markbit)) {
402 2 : markbit.Set<mode>();
403 2 : markbit.Next().Set<mode>();
404 : }
405 :
406 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
407 : INLINE(static bool BlackToGrey(MarkBit markbit)) {
408 : STATIC_ASSERT(mode == MarkBit::NON_ATOMIC);
409 : DCHECK(IsBlack(markbit));
410 835058 : return markbit.Next().Clear<mode>();
411 : }
412 :
413 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
414 : INLINE(static bool WhiteToGrey(MarkBit markbit)) {
415 : DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit));
416 707725746 : return markbit.Set<mode>();
417 : }
418 :
419 : // Warning: this method is not safe in general in concurrent scenarios.
420 : // If you know that nobody else will change the bits on the given location
421 : // then you may use it.
422 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
423 : INLINE(static void WhiteToBlack(MarkBit markbit)) {
424 : DCHECK(mode == MarkBit::ATOMIC || IsWhite(markbit));
425 29486137 : markbit.Set<mode>();
426 29486137 : markbit.Next().Set<mode>();
427 : }
428 :
429 : template <MarkBit::AccessMode mode = MarkBit::NON_ATOMIC>
430 : INLINE(static bool GreyToBlack(MarkBit markbit)) {
431 : DCHECK(mode == MarkBit::ATOMIC || IsGrey(markbit));
432 708416774 : return markbit.Next().Set<mode>();
433 : }
434 :
435 : enum ObjectColor {
436 : BLACK_OBJECT,
437 : WHITE_OBJECT,
438 : GREY_OBJECT,
439 : IMPOSSIBLE_COLOR
440 : };
441 :
442 : static const char* ColorName(ObjectColor color) {
443 : switch (color) {
444 : case BLACK_OBJECT:
445 : return "black";
446 : case WHITE_OBJECT:
447 : return "white";
448 : case GREY_OBJECT:
449 : return "grey";
450 : case IMPOSSIBLE_COLOR:
451 : return "impossible";
452 : }
453 : return "error";
454 : }
455 :
456 0 : static ObjectColor Color(MarkBit mark_bit) {
457 0 : if (IsBlack(mark_bit)) return BLACK_OBJECT;
458 0 : if (IsWhite(mark_bit)) return WHITE_OBJECT;
459 0 : if (IsGrey(mark_bit)) return GREY_OBJECT;
460 0 : UNREACHABLE();
461 : return IMPOSSIBLE_COLOR;
462 : }
463 :
464 : private:
465 : DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
466 : };
467 :
468 : } // namespace internal
469 : } // namespace v8
470 :
471 : #endif // V8_MARKING_H_
|
