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 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) >> (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 return index >> kBitsPerCellLog2; 114 } 115 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. 121 V8_INLINE static uint32_t CellAlignIndex(uint32_t index) { 122 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 inline MarkBit MarkBitFromIndex(uint32_t index) { 138 MarkBit::CellType mask = 1u << IndexInCell(index); 139 MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2); 140 return MarkBit(cell, mask); 141 } 142 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 template <AccessMode mode = AccessMode::NON_ATOMIC> 150 void ClearBitsInCell(uint32_t cell_index, uint32_t mask); 151 152 // Sets bits in the given cell. The mask specifies bits to set: if a 153 // bit is set in the mask then the corresponding bit is set in the cell. 154 template <AccessMode mode = AccessMode::NON_ATOMIC> 155 void SetBitsInCell(uint32_t cell_index, uint32_t mask); 156 157 // Sets all bits in the range [start_index, end_index). The cells at the 158 // boundary of the range are updated with atomic compare and swap operation. 159 // The inner cells are updated with relaxed write. 160 void SetRange(uint32_t start_index, uint32_t end_index); 161 162 // Clears all bits in the range [start_index, end_index). The cells at the 163 // boundary of the range are updated with atomic compare and swap operation. 164 // The inner cells are updated with relaxed write. 165 void ClearRange(uint32_t start_index, uint32_t end_index); 166 167 // Returns true if all bits in the range [start_index, end_index) are set. 168 bool AllBitsSetInRange(uint32_t start_index, uint32_t end_index); 169 170 // Returns true if all bits in the range [start_index, end_index) are cleared. 171 bool AllBitsClearInRange(uint32_t start_index, uint32_t end_index); 172 173 void Print(); 174 175 bool IsClean(); 176 }; 177 178 template <> 179 inline void Bitmap::SetBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index, 180 uint32_t mask) { 181 cells()[cell_index] |= mask; 182 } 183 184 template <> 185 inline void Bitmap::SetBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index, 186 uint32_t mask) { 187 base::AsAtomic32::SetBits(cells() + cell_index, mask, mask); 188 } 189 190 template <> 191 inline void Bitmap::ClearBitsInCell<AccessMode::NON_ATOMIC>(uint32_t cell_index, 192 uint32_t mask) { 193 cells()[cell_index] &= ~mask; 194 } 195 196 template <> 197 inline void Bitmap::ClearBitsInCell<AccessMode::ATOMIC>(uint32_t cell_index, 198 uint32_t mask) { 199 base::AsAtomic32::SetBits(cells() + cell_index, 0u, mask); 200 } 201 202 class Marking : public AllStatic { 203 public: 204 // TODO(hpayer): The current mark bit operations use as default NON_ATOMIC 205 // mode for access. We should remove the default value or switch it with 206 // ATOMIC as soon we add concurrency. 207 208 // Impossible markbits: 01 209 static const char* kImpossibleBitPattern; 210 template <AccessMode mode = AccessMode::NON_ATOMIC> 211 V8_INLINE static bool IsImpossible(MarkBit mark_bit) { 212 if (mode == AccessMode::NON_ATOMIC) { 213 return !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); 214 } 215 // If we are in concurrent mode we can only tell if an object has the 216 // impossible bit pattern if we read the first bit again after reading 217 // the first and the second bit. If the first bit is till zero and the 218 // second bit is one then the object has the impossible bit pattern. 219 bool is_impossible = !mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); 220 if (is_impossible) { 221 return !mark_bit.Get<mode>(); 222 } 223 return false; 224 } 225 226 // Black markbits: 11 227 static const char* kBlackBitPattern; 228 template <AccessMode mode = AccessMode::NON_ATOMIC> 229 V8_INLINE static bool IsBlack(MarkBit mark_bit) { 230 return mark_bit.Get<mode>() && mark_bit.Next().Get<mode>(); 231 } 232 233 // White markbits: 00 - this is required by the mark bit clearer. 234 static const char* kWhiteBitPattern; 235 template <AccessMode mode = AccessMode::NON_ATOMIC> 236 V8_INLINE static bool IsWhite(MarkBit mark_bit) { 237 DCHECK(!IsImpossible<mode>(mark_bit)); 238 return !mark_bit.Get<mode>(); 239 } 240 241 // Grey markbits: 10 242 static const char* kGreyBitPattern; 243 template <AccessMode mode = AccessMode::NON_ATOMIC> 244 V8_INLINE static bool IsGrey(MarkBit mark_bit) { 245 return mark_bit.Get<mode>() && !mark_bit.Next().Get<mode>(); 246 } 247 248 // IsBlackOrGrey assumes that the first bit is set for black or grey 249 // objects. 250 template <AccessMode mode = AccessMode::NON_ATOMIC> 251 V8_INLINE static bool IsBlackOrGrey(MarkBit mark_bit) { 252 return mark_bit.Get<mode>(); 253 } 254 255 template <AccessMode mode = AccessMode::NON_ATOMIC> 256 V8_INLINE static void MarkWhite(MarkBit markbit) { 257 STATIC_ASSERT(mode == AccessMode::NON_ATOMIC); 258 markbit.Clear<mode>(); 259 markbit.Next().Clear<mode>(); 260 } 261 262 // Warning: this method is not safe in general in concurrent scenarios. 263 // If you know that nobody else will change the bits on the given location 264 // then you may use it. 265 template <AccessMode mode = AccessMode::NON_ATOMIC> 266 V8_INLINE static void MarkBlack(MarkBit markbit) { 267 markbit.Set<mode>(); 268 markbit.Next().Set<mode>(); 269 } 270 271 template <AccessMode mode = AccessMode::NON_ATOMIC> 272 V8_INLINE static bool WhiteToGrey(MarkBit markbit) { 273 return markbit.Set<mode>(); 274 } 275 276 template <AccessMode mode = AccessMode::NON_ATOMIC> 277 V8_INLINE static bool WhiteToBlack(MarkBit markbit) { 278 return markbit.Set<mode>() && markbit.Next().Set<mode>(); 279 } 280 281 template <AccessMode mode = AccessMode::NON_ATOMIC> 282 V8_INLINE static bool GreyToBlack(MarkBit markbit) { 283 return markbit.Get<mode>() && markbit.Next().Set<mode>(); 284 } 285 286 enum ObjectColor { 287 BLACK_OBJECT, 288 WHITE_OBJECT, 289 GREY_OBJECT, 290 IMPOSSIBLE_COLOR 291 }; 292 293 static const char* ColorName(ObjectColor color) { 294 switch (color) { 295 case BLACK_OBJECT: 296 return "black"; 297 case WHITE_OBJECT: 298 return "white"; 299 case GREY_OBJECT: 300 return "grey"; 301 case IMPOSSIBLE_COLOR: 302 return "impossible"; 303 } 304 return "error"; 305 } 306 307 static ObjectColor Color(MarkBit mark_bit) { 308 if (IsBlack(mark_bit)) return BLACK_OBJECT; 309 if (IsWhite(mark_bit)) return WHITE_OBJECT; 310 if (IsGrey(mark_bit)) return GREY_OBJECT; 311 UNREACHABLE(); 312 } 313 314 private: 315 DISALLOW_IMPLICIT_CONSTRUCTORS(Marking); 316 }; 317 318 } // namespace internal 319 } // namespace v8 320 321 #endif // V8_HEAP_MARKING_H_ 322