1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
18 #define ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
19 
20 #include <limits.h>
21 #include <stdint.h>
22 #include <memory>
23 #include <set>
24 #include <vector>
25 
26 #include "base/locks.h"
27 #include "base/mem_map.h"
28 #include "runtime_globals.h"
29 
30 namespace art {
31 
32 namespace gc {
33 namespace accounting {
34 
35 // TODO: Use this code to implement SpaceBitmap.
36 class Bitmap {
37  public:
38   // Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap.
39   static Bitmap* Create(const std::string& name, size_t num_bits);
40 
41   // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
42   // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
43   // Objects are kAlignement-aligned.
44   static Bitmap* CreateFromMemMap(MemMap&& mem_map, size_t num_bits);
45 
46   // offset is the difference from base to a index.
BitIndexToWordIndex(uintptr_t offset)47   static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) {
48     return offset / kBitsPerBitmapWord;
49   }
50 
51   template<typename T>
WordIndexToBitIndex(T word_index)52   static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) {
53     return static_cast<T>(word_index * kBitsPerBitmapWord);
54   }
55 
BitIndexToMask(uintptr_t bit_index)56   static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) {
57     return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord);
58   }
59 
SetBit(size_t bit_index)60   ALWAYS_INLINE bool SetBit(size_t bit_index) {
61     return ModifyBit<true>(bit_index);
62   }
63 
ClearBit(size_t bit_index)64   ALWAYS_INLINE bool ClearBit(size_t bit_index) {
65     return ModifyBit<false>(bit_index);
66   }
67 
68   ALWAYS_INLINE bool TestBit(size_t bit_index) const;
69 
70   // Returns true if the bit_index was previously set.
71   ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index);
72 
73   // Fill the bitmap with zeroes.  Returns the bitmap's memory to the system as a side-effect.
74   void Clear();
75 
76   // Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are
77   // bit indices visitor is called with the index of each set bit.
78   template <typename Visitor>
79   void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const;
80 
81   void CopyFrom(Bitmap* source_bitmap);
82 
83   // Starting address of our internal storage.
Begin()84   uintptr_t* Begin() {
85     return bitmap_begin_;
86   }
87 
88   // Size of our bitmap in bits.
BitmapSize()89   size_t BitmapSize() const {
90     return bitmap_size_;
91   }
92 
93   // Check that a bit index is valid with a DCHECK.
CheckValidBitIndex(size_t bit_index)94   ALWAYS_INLINE void CheckValidBitIndex(size_t bit_index) const {
95     DCHECK_LT(bit_index, BitmapSize());
96   }
97 
98   std::string Dump() const;
99 
100  protected:
101   static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte;
102 
103   Bitmap(MemMap&& mem_map, size_t bitmap_size);
104   ~Bitmap();
105 
106   // Allocate the mem-map for a bitmap based on how many bits are required.
107   static MemMap AllocateMemMap(const std::string& name, size_t num_bits);
108 
109   template<bool kSetBit>
110   ALWAYS_INLINE bool ModifyBit(uintptr_t bit_index);
111 
112   // Backing storage for bitmap.
113   MemMap mem_map_;
114 
115   // This bitmap itself, word sized for efficiency in scanning.
116   uintptr_t* const bitmap_begin_;
117 
118   // Number of bits in the bitmap.
119   const size_t bitmap_size_;
120 
121  private:
122   DISALLOW_IMPLICIT_CONSTRUCTORS(Bitmap);
123 };
124 
125 // One bit per kAlignment in range (start, end]
126 template<size_t kAlignment>
127 class MemoryRangeBitmap : public Bitmap {
128  public:
129   static MemoryRangeBitmap* Create(
130       const std::string& name, uintptr_t cover_begin, uintptr_t cover_end);
131   static MemoryRangeBitmap* CreateFromMemMap(
132       MemMap&& mem_map, uintptr_t cover_begin, size_t num_bits);
133 
134   // Beginning of the memory range that the bitmap covers.
CoverBegin()135   ALWAYS_INLINE uintptr_t CoverBegin() const {
136     return cover_begin_;
137   }
138 
139   // End of the memory range that the bitmap covers.
CoverEnd()140   ALWAYS_INLINE uintptr_t CoverEnd() const {
141     return cover_end_;
142   }
143 
144   // Return the address associated with a bit index.
AddrFromBitIndex(size_t bit_index)145   ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const {
146     const uintptr_t addr = CoverBegin() + bit_index * kAlignment;
147     DCHECK_EQ(BitIndexFromAddr(addr), bit_index);
148     return addr;
149   }
150 
151   // Return the bit index associated with an address .
BitIndexFromAddr(uintptr_t addr)152   ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const {
153     DCHECK(HasAddress(addr)) << CoverBegin() << " <= " <<  addr << " < " << CoverEnd();
154     return (addr - CoverBegin()) / kAlignment;
155   }
156 
HasAddress(const uintptr_t addr)157   ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const {
158     return cover_begin_ <= addr && addr < cover_end_;
159   }
160 
Set(uintptr_t addr)161   ALWAYS_INLINE bool Set(uintptr_t addr) {
162     return SetBit(BitIndexFromAddr(addr));
163   }
164 
Clear(size_t addr)165   ALWAYS_INLINE bool Clear(size_t addr) {
166     return ClearBit(BitIndexFromAddr(addr));
167   }
168 
Test(size_t addr)169   ALWAYS_INLINE bool Test(size_t addr) const {
170     return TestBit(BitIndexFromAddr(addr));
171   }
172 
173   // Returns true if the object was previously set.
AtomicTestAndSet(size_t addr)174   ALWAYS_INLINE bool AtomicTestAndSet(size_t addr) {
175     return AtomicTestAndSetBit(BitIndexFromAddr(addr));
176   }
177 
178  private:
MemoryRangeBitmap(MemMap && mem_map,uintptr_t begin,size_t num_bits)179   MemoryRangeBitmap(MemMap&& mem_map, uintptr_t begin, size_t num_bits)
180       : Bitmap(std::move(mem_map), num_bits),
181         cover_begin_(begin),
182         cover_end_(begin + kAlignment * num_bits) {}
183 
184   uintptr_t const cover_begin_;
185   uintptr_t const cover_end_;
186 
187   DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryRangeBitmap);
188 };
189 
190 }  // namespace accounting
191 }  // namespace gc
192 }  // namespace art
193 
194 #endif  // ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
195