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_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 775212497 : inline MarkBit Next() {
29 775232634 : CellType new_mask = mask_ << 1;
30 775232634 : if (new_mask == 0) {
31 24808881 : return MarkBit(cell_ + 1, 1);
32 : } else {
33 750404245 : 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 379236 : inline bool MarkBit::Set<AccessMode::NON_ATOMIC>() {
60 379236 : CellType old_value = *cell_;
61 379236 : *cell_ = old_value | mask_;
62 379236 : return (old_value & mask_) == 0;
63 : }
64 :
65 : template <>
66 7740986723 : inline bool MarkBit::Set<AccessMode::ATOMIC>() {
67 7741006860 : return base::AsAtomic32::SetBits(cell_, mask_, mask_);
68 : }
69 :
70 : template <>
71 245622931 : inline bool MarkBit::Get<AccessMode::NON_ATOMIC>() {
72 245622931 : return (*cell_ & mask_) != 0;
73 : }
74 :
75 : template <>
76 948554224 : inline bool MarkBit::Get<AccessMode::ATOMIC>() {
77 1897108448 : return (base::AsAtomic32::Acquire_Load(cell_) & mask_) != 0;
78 : }
79 :
80 : template <>
81 162316 : inline bool MarkBit::Clear<AccessMode::NON_ATOMIC>() {
82 162316 : CellType old_value = *cell_;
83 162316 : *cell_ = old_value & ~mask_;
84 162316 : 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 :
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 2240292 : return index >> kBitsPerCellLog2;
114 : }
115 :
116 : V8_INLINE static uint32_t IndexInCell(uint32_t index) {
117 8821640741 : 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 1120146 : 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 8156438476 : inline MarkBit MarkBitFromIndex(uint32_t index) {
134 8156438482 : MarkBit::CellType mask = 1u << IndexInCell(index);
135 8156438482 : MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
136 8156438476 : 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 322586 : 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 191540 : 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 21 : 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 5 : bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
216 5 : if (is_impossible) {
217 5 : 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 55294553 : 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 205544489 : 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 8110420 : 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 153734867 : 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 81158 : markbit.Clear<mode>();
255 81158 : 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 7067426232 : return markbit.Set<mode>();
270 : }
271 :
272 : template <AccessMode mode = AccessMode::NON_ATOMIC>
273 : V8_INLINE static bool WhiteToBlack(MarkBit markbit) {
274 8 : 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 725288338 : 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 0 : static ObjectColor Color(MarkBit mark_bit) {
304 0 : if (IsBlack(mark_bit)) return BLACK_OBJECT;
305 0 : if (IsWhite(mark_bit)) return WHITE_OBJECT;
306 0 : if (IsGrey(mark_bit)) return GREY_OBJECT;
307 0 : 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_
|
