LCOV - code coverage report
Current view: top level - src/heap - marking.h (source / functions) Hit Total Coverage
Test: app.info Lines: 59 64 92.2 %
Date: 2017-04-26 Functions: 16 20 80.0 %

          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_

Generated by: LCOV version 1.10