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
Clear()10 void Bitmap::Clear() {
11 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
12 for (int i = 0; i < CellsCount(); i++) {
13 base::Relaxed_Store(cell_base + i, 0);
14 }
15 // This fence prevents re-ordering of publishing stores with the mark-bit
16 // clearing stores.
17 base::SeqCst_MemoryFence();
18 }
19
MarkAllBits()20 void Bitmap::MarkAllBits() {
21 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
22 for (int i = 0; i < CellsCount(); i++) {
23 base::Relaxed_Store(cell_base + i, 0xffffffff);
24 }
25 // This fence prevents re-ordering of publishing stores with the mark-bit
26 // clearing stores.
27 base::SeqCst_MemoryFence();
28 }
29
SetRange(uint32_t start_index,uint32_t end_index)30 void Bitmap::SetRange(uint32_t start_index, uint32_t end_index) {
31 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
32 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
33 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
34 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
35 if (start_cell_index != end_cell_index) {
36 // Firstly, fill all bits from the start address to the end of the first
37 // cell with 1s.
38 SetBitsInCell<AccessMode::ATOMIC>(start_cell_index,
39 ~(start_index_mask - 1));
40 // Then fill all in between cells with 1s.
41 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
42 for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
43 base::Relaxed_Store(cell_base + i, ~0u);
44 }
45 // Finally, fill all bits until the end address in the last cell with 1s.
46 SetBitsInCell<AccessMode::ATOMIC>(end_cell_index, (end_index_mask - 1));
47 } else {
48 SetBitsInCell<AccessMode::ATOMIC>(start_cell_index,
49 end_index_mask - start_index_mask);
50 }
51 // This fence prevents re-ordering of publishing stores with the mark-
52 // bit setting stores.
53 base::SeqCst_MemoryFence();
54 }
55
ClearRange(uint32_t start_index,uint32_t end_index)56 void Bitmap::ClearRange(uint32_t start_index, uint32_t end_index) {
57 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
58 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
59
60 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
61 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
62
63 if (start_cell_index != end_cell_index) {
64 // Firstly, fill all bits from the start address to the end of the first
65 // cell with 0s.
66 ClearBitsInCell<AccessMode::ATOMIC>(start_cell_index,
67 ~(start_index_mask - 1));
68 // Then fill all in between cells with 0s.
69 base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
70 for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
71 base::Relaxed_Store(cell_base + i, 0);
72 }
73 // Finally, set all bits until the end address in the last cell with 0s.
74 ClearBitsInCell<AccessMode::ATOMIC>(end_cell_index, (end_index_mask - 1));
75 } else {
76 ClearBitsInCell<AccessMode::ATOMIC>(start_cell_index,
77 (end_index_mask - start_index_mask));
78 }
79 // This fence prevents re-ordering of publishing stores with the mark-
80 // bit clearing stores.
81 base::SeqCst_MemoryFence();
82 }
83
AllBitsSetInRange(uint32_t start_index,uint32_t end_index)84 bool Bitmap::AllBitsSetInRange(uint32_t start_index, uint32_t end_index) {
85 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
86 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
87
88 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
89 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
90
91 MarkBit::CellType matching_mask;
92 if (start_cell_index != end_cell_index) {
93 matching_mask = ~(start_index_mask - 1);
94 if ((cells()[start_cell_index] & matching_mask) != matching_mask) {
95 return false;
96 }
97 for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
98 if (cells()[i] != ~0u) return false;
99 }
100 matching_mask = (end_index_mask - 1);
101 // Check against a mask of 0 to avoid dereferencing the cell after the
102 // end of the bitmap.
103 return (matching_mask == 0) ||
104 ((cells()[end_cell_index] & matching_mask) == matching_mask);
105 } else {
106 matching_mask = end_index_mask - start_index_mask;
107 // Check against a mask of 0 to avoid dereferencing the cell after the
108 // end of the bitmap.
109 return (matching_mask == 0) ||
110 (cells()[end_cell_index] & matching_mask) == matching_mask;
111 }
112 }
113
AllBitsClearInRange(uint32_t start_index,uint32_t end_index)114 bool Bitmap::AllBitsClearInRange(uint32_t start_index, uint32_t end_index) {
115 unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
116 MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
117
118 unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
119 MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
120
121 MarkBit::CellType matching_mask;
122 if (start_cell_index != end_cell_index) {
123 matching_mask = ~(start_index_mask - 1);
124 if ((cells()[start_cell_index] & matching_mask)) return false;
125 for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
126 if (cells()[i]) return false;
127 }
128 matching_mask = (end_index_mask - 1);
129 // Check against a mask of 0 to avoid dereferencing the cell after the
130 // end of the bitmap.
131 return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
132 } else {
133 matching_mask = end_index_mask - start_index_mask;
134 // Check against a mask of 0 to avoid dereferencing the cell after the
135 // end of the bitmap.
136 return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
137 }
138 }
139
140 namespace {
141
PrintWord(uint32_t word,uint32_t himask=0)142 void PrintWord(uint32_t word, uint32_t himask = 0) {
143 for (uint32_t mask = 1; mask != 0; mask <<= 1) {
144 if ((mask & himask) != 0) PrintF("[");
145 PrintF((mask & word) ? "1" : "0");
146 if ((mask & himask) != 0) PrintF("]");
147 }
148 }
149
150 class CellPrinter {
151 public:
CellPrinter()152 CellPrinter() : seq_start(0), seq_type(0), seq_length(0) {}
153
Print(uint32_t pos,uint32_t cell)154 void Print(uint32_t pos, uint32_t cell) {
155 if (cell == seq_type) {
156 seq_length++;
157 return;
158 }
159
160 Flush();
161
162 if (IsSeq(cell)) {
163 seq_start = pos;
164 seq_length = 0;
165 seq_type = cell;
166 return;
167 }
168
169 PrintF("%d: ", pos);
170 PrintWord(cell);
171 PrintF("\n");
172 }
173
Flush()174 void Flush() {
175 if (seq_length > 0) {
176 PrintF("%d: %dx%d\n", seq_start, seq_type == 0 ? 0 : 1,
177 seq_length * Bitmap::kBitsPerCell);
178 seq_length = 0;
179 }
180 }
181
IsSeq(uint32_t cell)182 static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
183
184 private:
185 uint32_t seq_start;
186 uint32_t seq_type;
187 uint32_t seq_length;
188 };
189
190 } // anonymous namespace
191
Print()192 void Bitmap::Print() {
193 CellPrinter printer;
194 for (int i = 0; i < CellsCount(); i++) {
195 printer.Print(i, cells()[i]);
196 }
197 printer.Flush();
198 PrintF("\n");
199 }
200
IsClean()201 bool Bitmap::IsClean() {
202 for (int i = 0; i < CellsCount(); i++) {
203 if (cells()[i] != 0) {
204 return false;
205 }
206 }
207 return true;
208 }
209
210 } // namespace internal
211 } // namespace v8
212