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 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 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 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 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 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 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 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: 152 CellPrinter() : seq_start(0), seq_type(0), seq_length(0) {} 153 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 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 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 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 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
