Line data    Source code

       1             : // Copyright 2017 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             : #include "src/heap/marking.h"
       6             : 
       7             : namespace v8 {
       8             : namespace internal {
       9             : 
      10             : template <>
      11          15 : bool ConcurrentBitmap<AccessMode::NON_ATOMIC>::AllBitsSetInRange(
      12             :     uint32_t start_index, uint32_t end_index) {
      13          15 :   if (start_index >= end_index) return false;
      14          15 :   end_index--;
      15             : 
      16          15 :   unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
      17          15 :   MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
      18             : 
      19          15 :   unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
      20          15 :   MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
      21             : 
      22             :   MarkBit::CellType matching_mask;
      23          15 :   if (start_cell_index != end_cell_index) {
      24          10 :     matching_mask = ~(start_index_mask - 1);
      25          10 :     if ((cells()[start_cell_index] & matching_mask) != matching_mask) {
      26             :       return false;
      27             :     }
      28          30 :     for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
      29          20 :       if (cells()[i] != ~0u) return false;
      30             :     }
      31          10 :     matching_mask = end_index_mask | (end_index_mask - 1);
      32          10 :     return ((cells()[end_cell_index] & matching_mask) == matching_mask);
      33             :   } else {
      34           5 :     matching_mask = end_index_mask | (end_index_mask - start_index_mask);
      35           5 :     return (cells()[end_cell_index] & matching_mask) == matching_mask;
      36             :   }
      37             : }
      38             : 
      39             : template <>
      40           4 : bool ConcurrentBitmap<AccessMode::NON_ATOMIC>::AllBitsClearInRange(
      41             :     uint32_t start_index, uint32_t end_index) {
      42           4 :   if (start_index >= end_index) return true;
      43           4 :   end_index--;
      44             : 
      45           4 :   unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
      46           4 :   MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
      47             : 
      48           4 :   unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
      49           4 :   MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
      50             : 
      51             :   MarkBit::CellType matching_mask;
      52           4 :   if (start_cell_index != end_cell_index) {
      53           0 :     matching_mask = ~(start_index_mask - 1);
      54           0 :     if ((cells()[start_cell_index] & matching_mask)) return false;
      55           0 :     for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
      56           0 :       if (cells()[i]) return false;
      57             :     }
      58           0 :     matching_mask = end_index_mask | (end_index_mask - 1);
      59           0 :     return !(cells()[end_cell_index] & matching_mask);
      60             :   } else {
      61           4 :     matching_mask = end_index_mask | (end_index_mask - start_index_mask);
      62           4 :     return !(cells()[end_cell_index] & matching_mask);
      63             :   }
      64             : }
      65             : 
      66             : namespace {
      67             : 
      68           0 : void PrintWord(uint32_t word, uint32_t himask = 0) {
      69           0 :   for (uint32_t mask = 1; mask != 0; mask <<= 1) {
      70           0 :     if ((mask & himask) != 0) PrintF("[");
      71           0 :     PrintF((mask & word) ? "1" : "0");
      72           0 :     if ((mask & himask) != 0) PrintF("]");
      73             :   }
      74           0 : }
      75             : 
      76             : class CellPrinter {
      77             :  public:
      78           0 :   CellPrinter() : seq_start(0), seq_type(0), seq_length(0) {}
      79             : 
      80           0 :   void Print(uint32_t pos, uint32_t cell) {
      81           0 :     if (cell == seq_type) {
      82           0 :       seq_length++;
      83           0 :       return;
      84             :     }
      85             : 
      86           0 :     Flush();
      87             : 
      88           0 :     if (IsSeq(cell)) {
      89           0 :       seq_start = pos;
      90           0 :       seq_length = 0;
      91           0 :       seq_type = cell;
      92           0 :       return;
      93             :     }
      94             : 
      95           0 :     PrintF("%d: ", pos);
      96           0 :     PrintWord(cell);
      97           0 :     PrintF("\n");
      98             :   }
      99             : 
     100           0 :   void Flush() {
     101           0 :     if (seq_length > 0) {
     102           0 :       PrintF("%d: %dx%d\n", seq_start, seq_type == 0 ? 0 : 1,
     103           0 :              seq_length * Bitmap::kBitsPerCell);
     104           0 :       seq_length = 0;
     105             :     }
     106           0 :   }
     107             : 
     108           0 :   static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
     109             : 
     110             :  private:
     111             :   uint32_t seq_start;
     112             :   uint32_t seq_type;
     113             :   uint32_t seq_length;
     114             : };
     115             : 
     116             : }  // anonymous namespace
     117             : 
     118             : template <>
     119           0 : void ConcurrentBitmap<AccessMode::NON_ATOMIC>::Print() {
     120             :   CellPrinter printer;
     121           0 :   for (int i = 0; i < CellsCount(); i++) {
     122           0 :     printer.Print(i, cells()[i]);
     123             :   }
     124           0 :   printer.Flush();
     125           0 :   PrintF("\n");
     126           0 : }
     127             : 
     128             : template <>
     129          22 : bool ConcurrentBitmap<AccessMode::NON_ATOMIC>::IsClean() {
     130       43030 :   for (int i = 0; i < CellsCount(); i++) {
     131       21505 :     if (cells()[i] != 0) {
     132             :       return false;
     133             :     }
     134             :   }
     135             :   return true;
     136             : }
     137             : 
     138             : }  // namespace internal
     139      121996 : }  // namespace v8