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