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