blob: 68f2d049d09d79d231bb820a0ab9c07809d027fd [file] [log] [blame]
* Copyright (C) 2015 The Android Open Source Project
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* See the License for the specific language governing permissions and
* limitations under the License.
#include <limits.h>
#include <stdint.h>
#include <memory>
#include <set>
#include <vector>
#include "base/locks.h"
#include "base/mem_map.h"
#include "runtime_globals.h"
namespace art {
namespace gc {
namespace accounting {
// TODO: Use this code to implement SpaceBitmap.
class Bitmap {
// Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap.
static Bitmap* Create(const std::string& name, size_t num_bits);
// Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
// mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
// Objects are kAlignement-aligned.
static Bitmap* CreateFromMemMap(MemMap&& mem_map, size_t num_bits);
// offset is the difference from base to a index.
static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) {
return offset / kBitsPerBitmapWord;
template<typename T>
static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) {
return static_cast<T>(word_index * kBitsPerBitmapWord);
static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) {
return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord);
ALWAYS_INLINE bool SetBit(size_t bit_index) {
return ModifyBit<true>(bit_index);
ALWAYS_INLINE bool ClearBit(size_t bit_index) {
return ModifyBit<false>(bit_index);
ALWAYS_INLINE bool TestBit(size_t bit_index) const;
// Returns true if the bit_index was previously set.
ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index);
// Fill the bitmap with zeroes. Returns the bitmap's memory to the system as a side-effect.
void Clear();
// Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are
// bit indices visitor is called with the index of each set bit.
template <typename Visitor>
void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const;
void CopyFrom(Bitmap* source_bitmap);
// Starting address of our internal storage.
uintptr_t* Begin() {
return bitmap_begin_;
// Size of our bitmap in bits.
size_t BitmapSize() const {
return bitmap_size_;
// Check that a bit index is valid with a DCHECK.
ALWAYS_INLINE void CheckValidBitIndex(size_t bit_index) const {
DCHECK_LT(bit_index, BitmapSize());
std::string Dump() const;
static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte;
Bitmap(MemMap&& mem_map, size_t bitmap_size);
// Allocate the mem-map for a bitmap based on how many bits are required.
static MemMap AllocateMemMap(const std::string& name, size_t num_bits);
template<bool kSetBit>
ALWAYS_INLINE bool ModifyBit(uintptr_t bit_index);
// Backing storage for bitmap.
MemMap mem_map_;
// This bitmap itself, word sized for efficiency in scanning.
uintptr_t* const bitmap_begin_;
// Number of bits in the bitmap.
const size_t bitmap_size_;
// One bit per kAlignment in range (start, end]
template<size_t kAlignment>
class MemoryRangeBitmap : public Bitmap {
static MemoryRangeBitmap* Create(
const std::string& name, uintptr_t cover_begin, uintptr_t cover_end);
static MemoryRangeBitmap* CreateFromMemMap(
MemMap&& mem_map, uintptr_t cover_begin, size_t num_bits);
// Beginning of the memory range that the bitmap covers.
ALWAYS_INLINE uintptr_t CoverBegin() const {
return cover_begin_;
// End of the memory range that the bitmap covers.
ALWAYS_INLINE uintptr_t CoverEnd() const {
return cover_end_;
// Return the address associated with a bit index.
ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const {
const uintptr_t addr = CoverBegin() + bit_index * kAlignment;
DCHECK_EQ(BitIndexFromAddr(addr), bit_index);
return addr;
// Return the bit index associated with an address .
ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const {
DCHECK(HasAddress(addr)) << CoverBegin() << " <= " << addr << " < " << CoverEnd();
return (addr - CoverBegin()) / kAlignment;
ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const {
return cover_begin_ <= addr && addr < cover_end_;
ALWAYS_INLINE bool Set(uintptr_t addr) {
return SetBit(BitIndexFromAddr(addr));
ALWAYS_INLINE bool Clear(size_t addr) {
return ClearBit(BitIndexFromAddr(addr));
ALWAYS_INLINE bool Test(size_t addr) const {
return TestBit(BitIndexFromAddr(addr));
// Returns true if the object was previously set.
ALWAYS_INLINE bool AtomicTestAndSet(size_t addr) {
return AtomicTestAndSetBit(BitIndexFromAddr(addr));
MemoryRangeBitmap(MemMap&& mem_map, uintptr_t begin, size_t num_bits)
: Bitmap(std::move(mem_map), num_bits),
cover_end_(begin + kAlignment * num_bits) {}
uintptr_t const cover_begin_;
uintptr_t const cover_end_;
} // namespace accounting
} // namespace gc
} // namespace art