14858a935868162266ead90ef2f7802108711371dMathieu Chartier/* 24858a935868162266ead90ef2f7802108711371dMathieu Chartier * Copyright (C) 2015 The Android Open Source Project 34858a935868162266ead90ef2f7802108711371dMathieu Chartier * 44858a935868162266ead90ef2f7802108711371dMathieu Chartier * Licensed under the Apache License, Version 2.0 (the "License"); 54858a935868162266ead90ef2f7802108711371dMathieu Chartier * you may not use this file except in compliance with the License. 64858a935868162266ead90ef2f7802108711371dMathieu Chartier * You may obtain a copy of the License at 74858a935868162266ead90ef2f7802108711371dMathieu Chartier * 84858a935868162266ead90ef2f7802108711371dMathieu Chartier * http://www.apache.org/licenses/LICENSE-2.0 94858a935868162266ead90ef2f7802108711371dMathieu Chartier * 104858a935868162266ead90ef2f7802108711371dMathieu Chartier * Unless required by applicable law or agreed to in writing, software 114858a935868162266ead90ef2f7802108711371dMathieu Chartier * distributed under the License is distributed on an "AS IS" BASIS, 124858a935868162266ead90ef2f7802108711371dMathieu Chartier * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 134858a935868162266ead90ef2f7802108711371dMathieu Chartier * See the License for the specific language governing permissions and 144858a935868162266ead90ef2f7802108711371dMathieu Chartier * limitations under the License. 154858a935868162266ead90ef2f7802108711371dMathieu Chartier */ 164858a935868162266ead90ef2f7802108711371dMathieu Chartier 174858a935868162266ead90ef2f7802108711371dMathieu Chartier#ifndef ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_ 184858a935868162266ead90ef2f7802108711371dMathieu Chartier#define ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_ 194858a935868162266ead90ef2f7802108711371dMathieu Chartier 204858a935868162266ead90ef2f7802108711371dMathieu Chartier#include <limits.h> 214858a935868162266ead90ef2f7802108711371dMathieu Chartier#include <stdint.h> 224858a935868162266ead90ef2f7802108711371dMathieu Chartier#include <memory> 234858a935868162266ead90ef2f7802108711371dMathieu Chartier#include <set> 244858a935868162266ead90ef2f7802108711371dMathieu Chartier#include <vector> 254858a935868162266ead90ef2f7802108711371dMathieu Chartier 264858a935868162266ead90ef2f7802108711371dMathieu Chartier#include "base/mutex.h" 274858a935868162266ead90ef2f7802108711371dMathieu Chartier#include "globals.h" 284858a935868162266ead90ef2f7802108711371dMathieu Chartier#include "object_callbacks.h" 294858a935868162266ead90ef2f7802108711371dMathieu Chartier 304858a935868162266ead90ef2f7802108711371dMathieu Chartiernamespace art { 314858a935868162266ead90ef2f7802108711371dMathieu Chartier 324858a935868162266ead90ef2f7802108711371dMathieu Chartierclass MemMap; 334858a935868162266ead90ef2f7802108711371dMathieu Chartier 344858a935868162266ead90ef2f7802108711371dMathieu Chartiernamespace gc { 354858a935868162266ead90ef2f7802108711371dMathieu Chartiernamespace accounting { 364858a935868162266ead90ef2f7802108711371dMathieu Chartier 374858a935868162266ead90ef2f7802108711371dMathieu Chartier// TODO: Use this code to implement SpaceBitmap. 384858a935868162266ead90ef2f7802108711371dMathieu Chartierclass Bitmap { 394858a935868162266ead90ef2f7802108711371dMathieu Chartier public: 404858a935868162266ead90ef2f7802108711371dMathieu Chartier // Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap. 414858a935868162266ead90ef2f7802108711371dMathieu Chartier static Bitmap* Create(const std::string& name, size_t num_bits); 424858a935868162266ead90ef2f7802108711371dMathieu Chartier 434858a935868162266ead90ef2f7802108711371dMathieu Chartier // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the 444858a935868162266ead90ef2f7802108711371dMathieu Chartier // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity. 454858a935868162266ead90ef2f7802108711371dMathieu Chartier // Objects are kAlignement-aligned. 464858a935868162266ead90ef2f7802108711371dMathieu Chartier static Bitmap* CreateFromMemMap(MemMap* mem_map, size_t num_bits); 474858a935868162266ead90ef2f7802108711371dMathieu Chartier 484858a935868162266ead90ef2f7802108711371dMathieu Chartier // offset is the difference from base to a index. 494858a935868162266ead90ef2f7802108711371dMathieu Chartier static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) { 504858a935868162266ead90ef2f7802108711371dMathieu Chartier return offset / kBitsPerBitmapWord; 514858a935868162266ead90ef2f7802108711371dMathieu Chartier } 524858a935868162266ead90ef2f7802108711371dMathieu Chartier 534858a935868162266ead90ef2f7802108711371dMathieu Chartier template<typename T> 544858a935868162266ead90ef2f7802108711371dMathieu Chartier static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) { 554858a935868162266ead90ef2f7802108711371dMathieu Chartier return static_cast<T>(word_index * kBitsPerBitmapWord); 564858a935868162266ead90ef2f7802108711371dMathieu Chartier } 574858a935868162266ead90ef2f7802108711371dMathieu Chartier 584858a935868162266ead90ef2f7802108711371dMathieu Chartier static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) { 594858a935868162266ead90ef2f7802108711371dMathieu Chartier return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord); 604858a935868162266ead90ef2f7802108711371dMathieu Chartier } 614858a935868162266ead90ef2f7802108711371dMathieu Chartier 624858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool SetBit(size_t bit_index) { 634858a935868162266ead90ef2f7802108711371dMathieu Chartier return ModifyBit<true>(bit_index); 644858a935868162266ead90ef2f7802108711371dMathieu Chartier } 654858a935868162266ead90ef2f7802108711371dMathieu Chartier 664858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool ClearBit(size_t bit_index) { 674858a935868162266ead90ef2f7802108711371dMathieu Chartier return ModifyBit<false>(bit_index); 684858a935868162266ead90ef2f7802108711371dMathieu Chartier } 694858a935868162266ead90ef2f7802108711371dMathieu Chartier 704858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool TestBit(size_t bit_index) const; 714858a935868162266ead90ef2f7802108711371dMathieu Chartier 724858a935868162266ead90ef2f7802108711371dMathieu Chartier // Returns true if the bit_index was previously set. 734858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index); 744858a935868162266ead90ef2f7802108711371dMathieu Chartier 754858a935868162266ead90ef2f7802108711371dMathieu Chartier // Fill the bitmap with zeroes. Returns the bitmap's memory to the system as a side-effect. 764858a935868162266ead90ef2f7802108711371dMathieu Chartier void Clear(); 774858a935868162266ead90ef2f7802108711371dMathieu Chartier 784858a935868162266ead90ef2f7802108711371dMathieu Chartier // Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are 794858a935868162266ead90ef2f7802108711371dMathieu Chartier // bit indices visitor is called with the index of each set bit. 804858a935868162266ead90ef2f7802108711371dMathieu Chartier template <typename Visitor> 814858a935868162266ead90ef2f7802108711371dMathieu Chartier void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const; 824858a935868162266ead90ef2f7802108711371dMathieu Chartier 834858a935868162266ead90ef2f7802108711371dMathieu Chartier void CopyFrom(Bitmap* source_bitmap); 844858a935868162266ead90ef2f7802108711371dMathieu Chartier 854858a935868162266ead90ef2f7802108711371dMathieu Chartier // Starting address of our internal storage. 864858a935868162266ead90ef2f7802108711371dMathieu Chartier uintptr_t* Begin() { 874858a935868162266ead90ef2f7802108711371dMathieu Chartier return bitmap_begin_; 884858a935868162266ead90ef2f7802108711371dMathieu Chartier } 894858a935868162266ead90ef2f7802108711371dMathieu Chartier 904858a935868162266ead90ef2f7802108711371dMathieu Chartier // Size of our bitmap in bits. 914858a935868162266ead90ef2f7802108711371dMathieu Chartier size_t BitmapSize() const { 924858a935868162266ead90ef2f7802108711371dMathieu Chartier return bitmap_size_; 934858a935868162266ead90ef2f7802108711371dMathieu Chartier } 944858a935868162266ead90ef2f7802108711371dMathieu Chartier 954858a935868162266ead90ef2f7802108711371dMathieu Chartier // Check that a bit index is valid with a DCHECK. 964858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE void CheckValidBitIndex(size_t bit_index) const { 974858a935868162266ead90ef2f7802108711371dMathieu Chartier DCHECK_LT(bit_index, BitmapSize()); 984858a935868162266ead90ef2f7802108711371dMathieu Chartier } 994858a935868162266ead90ef2f7802108711371dMathieu Chartier 1004858a935868162266ead90ef2f7802108711371dMathieu Chartier std::string Dump() const; 1014858a935868162266ead90ef2f7802108711371dMathieu Chartier 1024858a935868162266ead90ef2f7802108711371dMathieu Chartier protected: 1034858a935868162266ead90ef2f7802108711371dMathieu Chartier static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte; 1044858a935868162266ead90ef2f7802108711371dMathieu Chartier 1054858a935868162266ead90ef2f7802108711371dMathieu Chartier Bitmap(MemMap* mem_map, size_t bitmap_size); 1063481ba2c4e4f3aa80d8c6d50a9f85dacb56b508bVladimir Marko ~Bitmap(); 1074858a935868162266ead90ef2f7802108711371dMathieu Chartier 1084858a935868162266ead90ef2f7802108711371dMathieu Chartier // Allocate the mem-map for a bitmap based on how many bits are required. 1094858a935868162266ead90ef2f7802108711371dMathieu Chartier static MemMap* AllocateMemMap(const std::string& name, size_t num_bits); 1104858a935868162266ead90ef2f7802108711371dMathieu Chartier 1114858a935868162266ead90ef2f7802108711371dMathieu Chartier template<bool kSetBit> 1124858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool ModifyBit(uintptr_t bit_index); 1134858a935868162266ead90ef2f7802108711371dMathieu Chartier 1144858a935868162266ead90ef2f7802108711371dMathieu Chartier // Backing storage for bitmap. 1154858a935868162266ead90ef2f7802108711371dMathieu Chartier std::unique_ptr<MemMap> mem_map_; 1164858a935868162266ead90ef2f7802108711371dMathieu Chartier 1174858a935868162266ead90ef2f7802108711371dMathieu Chartier // This bitmap itself, word sized for efficiency in scanning. 1184858a935868162266ead90ef2f7802108711371dMathieu Chartier uintptr_t* const bitmap_begin_; 1194858a935868162266ead90ef2f7802108711371dMathieu Chartier 1204858a935868162266ead90ef2f7802108711371dMathieu Chartier // Number of bits in the bitmap. 1214858a935868162266ead90ef2f7802108711371dMathieu Chartier const size_t bitmap_size_; 1224858a935868162266ead90ef2f7802108711371dMathieu Chartier 1234858a935868162266ead90ef2f7802108711371dMathieu Chartier private: 124414369a2e3f23e1408fc1cbf4f623014bd95cb8fMathieu Chartier DISALLOW_IMPLICIT_CONSTRUCTORS(Bitmap); 1254858a935868162266ead90ef2f7802108711371dMathieu Chartier}; 1264858a935868162266ead90ef2f7802108711371dMathieu Chartier 1274858a935868162266ead90ef2f7802108711371dMathieu Chartier// One bit per kAlignment in range (start, end] 1284858a935868162266ead90ef2f7802108711371dMathieu Chartiertemplate<size_t kAlignment> 1294858a935868162266ead90ef2f7802108711371dMathieu Chartierclass MemoryRangeBitmap : public Bitmap { 1304858a935868162266ead90ef2f7802108711371dMathieu Chartier public: 1314858a935868162266ead90ef2f7802108711371dMathieu Chartier static MemoryRangeBitmap* Create(const std::string& name, uintptr_t cover_begin, 1324858a935868162266ead90ef2f7802108711371dMathieu Chartier uintptr_t cover_end); 1334858a935868162266ead90ef2f7802108711371dMathieu Chartier static MemoryRangeBitmap* CreateFromMemMap(MemMap* mem_map, uintptr_t cover_begin, 1344858a935868162266ead90ef2f7802108711371dMathieu Chartier size_t num_bits); 1354858a935868162266ead90ef2f7802108711371dMathieu Chartier 1364858a935868162266ead90ef2f7802108711371dMathieu Chartier // Beginning of the memory range that the bitmap covers. 1374858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE uintptr_t CoverBegin() const { 1384858a935868162266ead90ef2f7802108711371dMathieu Chartier return cover_begin_; 1394858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1404858a935868162266ead90ef2f7802108711371dMathieu Chartier 1414858a935868162266ead90ef2f7802108711371dMathieu Chartier // End of the memory range that the bitmap covers. 1424858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE uintptr_t CoverEnd() const { 1434858a935868162266ead90ef2f7802108711371dMathieu Chartier return cover_end_; 1444858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1454858a935868162266ead90ef2f7802108711371dMathieu Chartier 1464858a935868162266ead90ef2f7802108711371dMathieu Chartier // Return the address associated with a bit index. 1474858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const { 1484858a935868162266ead90ef2f7802108711371dMathieu Chartier const uintptr_t addr = CoverBegin() + bit_index * kAlignment; 1494858a935868162266ead90ef2f7802108711371dMathieu Chartier DCHECK_EQ(BitIndexFromAddr(addr), bit_index); 1504858a935868162266ead90ef2f7802108711371dMathieu Chartier return addr; 1514858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1524858a935868162266ead90ef2f7802108711371dMathieu Chartier 1534858a935868162266ead90ef2f7802108711371dMathieu Chartier // Return the bit index associated with an address . 1544858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const { 1554858a935868162266ead90ef2f7802108711371dMathieu Chartier DCHECK(HasAddress(addr)) << CoverBegin() << " <= " << addr << " < " << CoverEnd(); 1564858a935868162266ead90ef2f7802108711371dMathieu Chartier return (addr - CoverBegin()) / kAlignment; 1574858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1584858a935868162266ead90ef2f7802108711371dMathieu Chartier 1594858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const { 1604858a935868162266ead90ef2f7802108711371dMathieu Chartier return cover_begin_ <= addr && addr < cover_end_; 1614858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1624858a935868162266ead90ef2f7802108711371dMathieu Chartier 1634858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool Set(uintptr_t addr) { 1644858a935868162266ead90ef2f7802108711371dMathieu Chartier return SetBit(BitIndexFromAddr(addr)); 1654858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1664858a935868162266ead90ef2f7802108711371dMathieu Chartier 1674858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool Clear(size_t addr) { 1684858a935868162266ead90ef2f7802108711371dMathieu Chartier return ClearBit(BitIndexFromAddr(addr)); 1694858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1704858a935868162266ead90ef2f7802108711371dMathieu Chartier 1714858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool Test(size_t addr) const { 1724858a935868162266ead90ef2f7802108711371dMathieu Chartier return TestBit(BitIndexFromAddr(addr)); 1734858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1744858a935868162266ead90ef2f7802108711371dMathieu Chartier 1754858a935868162266ead90ef2f7802108711371dMathieu Chartier // Returns true if the object was previously set. 1764858a935868162266ead90ef2f7802108711371dMathieu Chartier ALWAYS_INLINE bool AtomicTestAndSet(size_t addr) { 1774858a935868162266ead90ef2f7802108711371dMathieu Chartier return AtomicTestAndSetBit(BitIndexFromAddr(addr)); 1784858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1794858a935868162266ead90ef2f7802108711371dMathieu Chartier 1804858a935868162266ead90ef2f7802108711371dMathieu Chartier private: 1814858a935868162266ead90ef2f7802108711371dMathieu Chartier MemoryRangeBitmap(MemMap* mem_map, uintptr_t begin, size_t num_bits) 1824858a935868162266ead90ef2f7802108711371dMathieu Chartier : Bitmap(mem_map, num_bits), cover_begin_(begin), cover_end_(begin + kAlignment * num_bits) { 1834858a935868162266ead90ef2f7802108711371dMathieu Chartier } 1844858a935868162266ead90ef2f7802108711371dMathieu Chartier 1854858a935868162266ead90ef2f7802108711371dMathieu Chartier uintptr_t const cover_begin_; 1864858a935868162266ead90ef2f7802108711371dMathieu Chartier uintptr_t const cover_end_; 187414369a2e3f23e1408fc1cbf4f623014bd95cb8fMathieu Chartier 188414369a2e3f23e1408fc1cbf4f623014bd95cb8fMathieu Chartier DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryRangeBitmap); 1894858a935868162266ead90ef2f7802108711371dMathieu Chartier}; 1904858a935868162266ead90ef2f7802108711371dMathieu Chartier 1914858a935868162266ead90ef2f7802108711371dMathieu Chartier} // namespace accounting 1924858a935868162266ead90ef2f7802108711371dMathieu Chartier} // namespace gc 1934858a935868162266ead90ef2f7802108711371dMathieu Chartier} // namespace art 1944858a935868162266ead90ef2f7802108711371dMathieu Chartier 1954858a935868162266ead90ef2f7802108711371dMathieu Chartier#endif // ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_ 196