blob: 23fbdd3465aee42906428363ebe74706ffbe8760 [file] [log] [blame]
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/heap/marking.h"
namespace v8 {
namespace internal {
void Bitmap::Clear() {
base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
for (int i = 0; i < CellsCount(); i++) {
base::Relaxed_Store(cell_base + i, 0);
}
// This fence prevents re-ordering of publishing stores with the mark-bit
// clearing stores.
base::SeqCst_MemoryFence();
}
void Bitmap::MarkAllBits() {
base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
for (int i = 0; i < CellsCount(); i++) {
base::Relaxed_Store(cell_base + i, 0xffffffff);
}
// This fence prevents re-ordering of publishing stores with the mark-bit
// clearing stores.
base::SeqCst_MemoryFence();
}
void Bitmap::SetRange(uint32_t start_index, uint32_t end_index) {
unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
if (start_cell_index != end_cell_index) {
// Firstly, fill all bits from the start address to the end of the first
// cell with 1s.
SetBitsInCell<AccessMode::ATOMIC>(start_cell_index,
~(start_index_mask - 1));
// Then fill all in between cells with 1s.
base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
base::Relaxed_Store(cell_base + i, ~0u);
}
// Finally, fill all bits until the end address in the last cell with 1s.
SetBitsInCell<AccessMode::ATOMIC>(end_cell_index, (end_index_mask - 1));
} else {
SetBitsInCell<AccessMode::ATOMIC>(start_cell_index,
end_index_mask - start_index_mask);
}
// This fence prevents re-ordering of publishing stores with the mark-
// bit setting stores.
base::SeqCst_MemoryFence();
}
void Bitmap::ClearRange(uint32_t start_index, uint32_t end_index) {
unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
if (start_cell_index != end_cell_index) {
// Firstly, fill all bits from the start address to the end of the first
// cell with 0s.
ClearBitsInCell<AccessMode::ATOMIC>(start_cell_index,
~(start_index_mask - 1));
// Then fill all in between cells with 0s.
base::Atomic32* cell_base = reinterpret_cast<base::Atomic32*>(cells());
for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
base::Relaxed_Store(cell_base + i, 0);
}
// Finally, set all bits until the end address in the last cell with 0s.
ClearBitsInCell<AccessMode::ATOMIC>(end_cell_index, (end_index_mask - 1));
} else {
ClearBitsInCell<AccessMode::ATOMIC>(start_cell_index,
(end_index_mask - start_index_mask));
}
// This fence prevents re-ordering of publishing stores with the mark-
// bit clearing stores.
base::SeqCst_MemoryFence();
}
bool Bitmap::AllBitsSetInRange(uint32_t start_index, uint32_t end_index) {
unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
MarkBit::CellType matching_mask;
if (start_cell_index != end_cell_index) {
matching_mask = ~(start_index_mask - 1);
if ((cells()[start_cell_index] & matching_mask) != matching_mask) {
return false;
}
for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
if (cells()[i] != ~0u) return false;
}
matching_mask = (end_index_mask - 1);
// Check against a mask of 0 to avoid dereferencing the cell after the
// end of the bitmap.
return (matching_mask == 0) ||
((cells()[end_cell_index] & matching_mask) == matching_mask);
} else {
matching_mask = end_index_mask - start_index_mask;
// Check against a mask of 0 to avoid dereferencing the cell after the
// end of the bitmap.
return (matching_mask == 0) ||
(cells()[end_cell_index] & matching_mask) == matching_mask;
}
}
bool Bitmap::AllBitsClearInRange(uint32_t start_index, uint32_t end_index) {
unsigned int start_cell_index = start_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType start_index_mask = 1u << Bitmap::IndexInCell(start_index);
unsigned int end_cell_index = end_index >> Bitmap::kBitsPerCellLog2;
MarkBit::CellType end_index_mask = 1u << Bitmap::IndexInCell(end_index);
MarkBit::CellType matching_mask;
if (start_cell_index != end_cell_index) {
matching_mask = ~(start_index_mask - 1);
if ((cells()[start_cell_index] & matching_mask)) return false;
for (unsigned int i = start_cell_index + 1; i < end_cell_index; i++) {
if (cells()[i]) return false;
}
matching_mask = (end_index_mask - 1);
// Check against a mask of 0 to avoid dereferencing the cell after the
// end of the bitmap.
return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
} else {
matching_mask = end_index_mask - start_index_mask;
// Check against a mask of 0 to avoid dereferencing the cell after the
// end of the bitmap.
return (matching_mask == 0) || !(cells()[end_cell_index] & matching_mask);
}
}
namespace {
void PrintWord(uint32_t word, uint32_t himask = 0) {
for (uint32_t mask = 1; mask != 0; mask <<= 1) {
if ((mask & himask) != 0) PrintF("[");
PrintF((mask & word) ? "1" : "0");
if ((mask & himask) != 0) PrintF("]");
}
}
class CellPrinter {
public:
CellPrinter() : seq_start(0), seq_type(0), seq_length(0) {}
void Print(uint32_t pos, uint32_t cell) {
if (cell == seq_type) {
seq_length++;
return;
}
Flush();
if (IsSeq(cell)) {
seq_start = pos;
seq_length = 0;
seq_type = cell;
return;
}
PrintF("%d: ", pos);
PrintWord(cell);
PrintF("\n");
}
void Flush() {
if (seq_length > 0) {
PrintF("%d: %dx%d\n", seq_start, seq_type == 0 ? 0 : 1,
seq_length * Bitmap::kBitsPerCell);
seq_length = 0;
}
}
static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
private:
uint32_t seq_start;
uint32_t seq_type;
uint32_t seq_length;
};
} // anonymous namespace
void Bitmap::Print() {
CellPrinter printer;
for (int i = 0; i < CellsCount(); i++) {
printer.Print(i, cells()[i]);
}
printer.Flush();
PrintF("\n");
}
bool Bitmap::IsClean() {
for (int i = 0; i < CellsCount(); i++) {
if (cells()[i] != 0) {
return false;
}
}
return true;
}
} // namespace internal
} // namespace v8