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 : 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 698079165 : inline MarkBit Next() {
29 698079165 : CellType new_mask = mask_ << 1;
30 698079165 : if (new_mask == 0) {
31 16983823 : return MarkBit(cell_ + 1, 1);
32 : } else {
33 681095342 : 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 186538 : inline bool MarkBit::Set<AccessMode::NON_ATOMIC>() {
60 186538 : CellType old_value = *cell_;
61 186538 : *cell_ = old_value | mask_;
62 186538 : return (old_value & mask_) == 0;
63 : }
64 :
65 : template <>
66 5356652151 : inline bool MarkBit::Set<AccessMode::ATOMIC>() {
67 5356652151 : return base::AsAtomic32::SetBits(cell_, mask_, mask_);
68 : }
69 :
70 : template <>
71 258260685 : inline bool MarkBit::Get<AccessMode::NON_ATOMIC>() {
72 258260685 : return (*cell_ & mask_) != 0;
73 : }
74 :
75 : template <>
76 876551133 : inline bool MarkBit::Get<AccessMode::ATOMIC>() {
77 1753102266 : return (base::AsAtomic32::Acquire_Load(cell_) & mask_) != 0;
78 : }
79 :
80 : template <>
81 8090 : inline bool MarkBit::Clear<AccessMode::NON_ATOMIC>() {
82 8090 : CellType old_value = *cell_;
83 8090 : *cell_ = old_value & ~mask_;
84 8090 : 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 2897364 : return index >> kBitsPerCellLog2;
114 : }
115 :
116 : V8_INLINE static uint32_t IndexInCell(uint32_t index) {
117 6395389395 : 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 965788 : return index & ~kBitIndexMask;
123 : }
124 :
125 : V8_INLINE static bool IsCellAligned(uint32_t index) {
126 : return (index & kBitIndexMask) == 0;
127 : }
128 :
129 : V8_INLINE MarkBit::CellType* cells() {
130 : return reinterpret_cast<MarkBit::CellType*>(this);
131 : }
132 :
133 : V8_INLINE static Bitmap* FromAddress(Address addr) {
134 : return reinterpret_cast<Bitmap*>(addr);
135 : }
136 :
137 5785293664 : inline MarkBit MarkBitFromIndex(uint32_t index) {
138 5785293670 : MarkBit::CellType mask = 1u << IndexInCell(index);
139 5785293670 : MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);
140 5785293664 : return MarkBit(cell, mask);
141 : }
142 :
143 : void Clear();
144 :
145 : // Clears bits in the given cell. The mask specifies bits to clear: if a
146 : // bit is set in the mask then the corresponding bit is cleared in the cell.
147 : template <AccessMode mode = AccessMode::NON_ATOMIC>
148 : void ClearBitsInCell(uint32_t cell_index, uint32_t mask);
149 :
150 : // Sets bits in the given cell. The mask specifies bits to set: if a
151 : // bit is set in the mask then the corresponding bit is set in the cell.
152 : template <AccessMode mode = AccessMode::NON_ATOMIC>
153 : void SetBitsInCell(uint32_t cell_index, uint32_t mask);
154 :
155 : // Sets all bits in the range [start_index, end_index). The cells at the
156 : // boundary of the range are updated with atomic compare and swap operation.
157 : // 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). The cells at the
161 : // boundary of the range are updated with atomic compare and swap operation.
162 : // The inner cells are updated with relaxed write.
163 : void ClearRange(uint32_t start_index, uint32_t end_index);
164 :
165 : // Returns true if all bits in the range [start_index, end_index) are set.
166 : bool AllBitsSetInRange(uint32_t start_index, uint32_t end_index);
167 :
168 : // Returns true if all bits in the range [start_index, end_index) are cleared.
169 : bool AllBitsClearInRange(uint32_t start_index, uint32_t end_index);
170 :
171 : void Print();
172 :
173 : bool IsClean();
174 : };
175 :
176 : template <>
177 : inline void Bitmap::SetBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index,
178 : uint32_t mask) {
179 : cells()[cell_index] |= mask;
180 : }
181 :
182 : template <>
183 : inline void Bitmap::SetBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index,
184 : uint32_t mask) {
185 287347 : base::AsAtomic32::SetBits(cells() + cell_index, mask, mask);
186 : }
187 :
188 : template <>
189 : inline void Bitmap::ClearBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index,
190 : uint32_t mask) {
191 : cells()[cell_index] &= ~mask;
192 : }
193 :
194 : template <>
195 : inline void Bitmap::ClearBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index,
196 : uint32_t mask) {
197 170730 : base::AsAtomic32::SetBits(cells() + cell_index, 0u, mask);
198 : }
199 :
200 : class Marking : public AllStatic {
201 : public:
202 : // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC
203 : // mode for access. We should remove the default value or switch it with
204 : // ATOMIC as soon we add concurrency.
205 :
206 : // Impossible markbits: 01
207 : static const char* kImpossibleBitPattern;
208 : template <AccessMode mode = AccessMode::NON_ATOMIC>
209 : INLINE(static bool IsImpossible(MarkBit mark_bit)) {
210 : if (mode == AccessMode::NON_ATOMIC) {
211 21 : return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
212 : }
213 : // If we are in concurrent mode we can only tell if an object has the
214 : // impossible bit pattern if we read the first bit again after reading
215 : // the first and the second bit. If the first bit is till zero and the
216 : // second bit is one then the object has the impossible bit pattern.
217 5 : bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
218 5 : if (is_impossible) {
219 5 : return !mark_bit.Get<mode>();
220 : }
221 : return false;
222 : }
223 :
224 : // Black markbits: 11
225 : static const char* kBlackBitPattern;
226 : template <AccessMode mode = AccessMode::NON_ATOMIC>
227 : INLINE(static bool IsBlack(MarkBit mark_bit)) {
228 76799553 : return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>();
229 : }
230 :
231 : // White markbits: 00 - this is required by the mark bit clearer.
232 : static const char* kWhiteBitPattern;
233 : template <AccessMode mode = AccessMode::NON_ATOMIC>
234 : INLINE(static bool IsWhite(MarkBit mark_bit)) {
235 : DCHECK(!IsImpossible<mode>(mark_bit));
236 244597930 : return !mark_bit.Get<mode>();
237 : }
238 :
239 : // Grey markbits: 10
240 : static const char* kGreyBitPattern;
241 : template <AccessMode mode = AccessMode::NON_ATOMIC>
242 : INLINE(static bool IsGrey(MarkBit mark_bit)) {
243 33440960 : return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>();
244 : }
245 :
246 : // IsBlackOrGrey assumes that the first bit is set for black or grey
247 : // objects.
248 : template <AccessMode mode = AccessMode::NON_ATOMIC>
249 : INLINE(static bool IsBlackOrGrey(MarkBit mark_bit)) {
250 85087810 : return mark_bit.Get<mode>();
251 : }
252 :
253 : template <AccessMode mode = AccessMode::NON_ATOMIC>
254 : INLINE(static void MarkWhite(MarkBit markbit)) {
255 : STATIC_ASSERT(mode == AccessMode::NON_ATOMIC);
256 4045 : markbit.Clear<mode>();
257 4045 : markbit.Next().Clear<mode>();
258 : }
259 :
260 : // Warning: this method is not safe in general in concurrent scenarios.
261 : // If you know that nobody else will change the bits on the given location
262 : // then you may use it.
263 : template <AccessMode mode = AccessMode::NON_ATOMIC>
264 : INLINE(static void MarkBlack(MarkBit markbit)) {
265 : markbit.Set<mode>();
266 : markbit.Next().Set<mode>();
267 : }
268 :
269 : template <AccessMode mode = AccessMode::NON_ATOMIC>
270 : INLINE(static bool WhiteToGrey(MarkBit markbit)) {
271 4722004226 : return markbit.Set<mode>();
272 : }
273 :
274 : template <AccessMode mode = AccessMode::NON_ATOMIC>
275 : INLINE(static bool WhiteToBlack(MarkBit markbit)) {
276 3 : return markbit.Set<mode>() && markbit.Next().Set<mode>();
277 : }
278 :
279 : template <AccessMode mode = AccessMode::NON_ATOMIC>
280 : INLINE(static bool GreyToBlack(MarkBit markbit)) {
281 621589586 : return markbit.Get<mode>() && markbit.Next().Set<mode>();
282 : }
283 :
284 : enum ObjectColor {
285 : BLACK_OBJECT,
286 : WHITE_OBJECT,
287 : GREY_OBJECT,
288 : IMPOSSIBLE_COLOR
289 : };
290 :
291 : static const char* ColorName(ObjectColor color) {
292 : switch (color) {
293 : case BLACK_OBJECT:
294 : return "black";
295 : case WHITE_OBJECT:
296 : return "white";
297 : case GREY_OBJECT:
298 : return "grey";
299 : case IMPOSSIBLE_COLOR:
300 : return "impossible";
301 : }
302 : return "error";
303 : }
304 :
305 0 : static ObjectColor Color(MarkBit mark_bit) {
306 0 : if (IsBlack(mark_bit)) return BLACK_OBJECT;
307 0 : if (IsWhite(mark_bit)) return WHITE_OBJECT;
308 0 : if (IsGrey(mark_bit)) return GREY_OBJECT;
309 0 : UNREACHABLE();
310 : }
311 :
312 : private:
313 : DISALLOW_IMPLICIT_CONSTRUCTORS(Marking);
314 : };
315 :
316 : } // namespace internal
317 : } // namespace v8
318 :
319 : #endif // V8_MARKING_H_
|
