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