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 
23 #include <memory>
24 #include <set>
25 #include <vector>
26 
27 #include "base/bit_utils.h"
28 #include "base/locks.h"
29 #include "base/mem_map.h"
30 #include "runtime_globals.h"
31 
32 namespace art HIDDEN {
33 
34 namespace gc {
35 namespace accounting {
36 
37 // TODO: Use this code to implement SpaceBitmap.
38 class Bitmap {
39  public:
40   // Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap.
41   static Bitmap* Create(const std::string& name, size_t num_bits);
42 
43   // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
44   // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
45   // Objects are kAlignement-aligned.
46   static Bitmap* CreateFromMemMap(MemMap&& mem_map, size_t num_bits);
47 
48   // offset is the difference from base to a index.
BitIndexToWordIndex(uintptr_t offset)49   static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) {
50     return offset / kBitsPerBitmapWord;
51   }
52 
53   template<typename T>
WordIndexToBitIndex(T word_index)54   static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) {
55     return static_cast<T>(word_index * kBitsPerBitmapWord);
56   }
57 
BitIndexToMask(uintptr_t bit_index)58   static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) {
59     return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord);
60   }
61 
SetBit(size_t bit_index)62   ALWAYS_INLINE bool SetBit(size_t bit_index) {
63     return ModifyBit<true>(bit_index);
64   }
65 
ClearBit(size_t bit_index)66   ALWAYS_INLINE bool ClearBit(size_t bit_index) {
67     return ModifyBit<false>(bit_index);
68   }
69 
70   ALWAYS_INLINE bool TestBit(size_t bit_index) const;
71 
72   // Returns true if the bit_index was previously set.
73   ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index);
74 
75   // Fill the bitmap with zeroes.  Returns the bitmap's memory to the system as a side-effect.
76   void Clear();
77 
78   // Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are
79   // bit indices visitor is called with the index of each set bit.
80   template <typename Visitor>
81   void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const;
82 
83   void CopyFrom(Bitmap* source_bitmap);
84 
85   // Starting address of our internal storage.
Begin()86   uintptr_t* Begin() const {
87     return bitmap_begin_;
88   }
89 
90   // Size of our bitmap in bits.
BitmapSize()91   size_t BitmapSize() const { return bitmap_numbits_; }
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 = kBitsPerIntPtrT;
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. This is interpreted as an array of
113   // kBitsPerBitmapWord-sized integers, with bits assigned in each word little
114   // endian first.
115   MemMap mem_map_;
116 
117   // This bitmap itself, word sized for efficiency in scanning.
118   uintptr_t* const bitmap_begin_;
119 
120   // Number of bits in the bitmap.
121   size_t bitmap_numbits_;
122 
123  private:
124   DISALLOW_IMPLICIT_CONSTRUCTORS(Bitmap);
125 };
126 
127 // One bit per kAlignment in range [start, end)
128 template<size_t kAlignment>
129 class MemoryRangeBitmap : public Bitmap {
130  public:
131   static MemoryRangeBitmap* Create(
132       const std::string& name, uintptr_t cover_begin, uintptr_t cover_end);
133   static MemoryRangeBitmap* CreateFromMemMap(
134       MemMap&& mem_map, uintptr_t cover_begin, size_t num_bits);
135 
SetBitmapSize(size_t bytes)136   void SetBitmapSize(size_t bytes) {
137     CHECK_ALIGNED(bytes, kAlignment);
138     bitmap_numbits_ = bytes / kAlignment;
139     size_t rounded_size =
140         RoundUp(bitmap_numbits_, kBitsPerBitmapWord) / kBitsPerBitmapWord * sizeof(uintptr_t);
141     mem_map_.SetSize(rounded_size);
142   }
143 
144   // Beginning of the memory range that the bitmap covers.
CoverBegin()145   ALWAYS_INLINE uintptr_t CoverBegin() const {
146     return cover_begin_;
147   }
148 
149   // End of the memory range that the bitmap covers.
CoverEnd()150   ALWAYS_INLINE uintptr_t CoverEnd() const {
151     return cover_begin_ + kAlignment * BitmapSize();
152   }
153 
154   // Return the address associated with a bit index.
AddrFromBitIndex(size_t bit_index)155   ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const {
156     const uintptr_t addr = CoverBegin() + bit_index * kAlignment;
157     DCHECK_EQ(BitIndexFromAddr(addr), bit_index);
158     return addr;
159   }
160 
161   // Return the bit index associated with an address .
BitIndexFromAddr(uintptr_t addr)162   ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const {
163     uintptr_t result = (addr - CoverBegin()) / kAlignment;
164     DCHECK(result < BitmapSize()) << CoverBegin() << " <= " <<  addr << " < " << CoverEnd();
165     return result;
166   }
167 
HasAddress(const uintptr_t addr)168   ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const {
169     // Don't use BitIndexFromAddr() here as the addr passed to this function
170     // could be outside the range. If addr < cover_begin_, then the result
171     // underflows to some very large value past the end of the bitmap.
172     // Therefore, all operations are unsigned here.
173     bool ret = (addr - CoverBegin()) / kAlignment < BitmapSize();
174     if (ret) {
175       DCHECK(CoverBegin() <= addr && addr < CoverEnd())
176           << CoverBegin() << " <= " <<  addr << " < " << CoverEnd();
177     }
178     return ret;
179   }
180 
Set(uintptr_t addr)181   ALWAYS_INLINE bool Set(uintptr_t addr) {
182     return SetBit(BitIndexFromAddr(addr));
183   }
184 
Clear(uintptr_t addr)185   ALWAYS_INLINE bool Clear(uintptr_t addr) {
186     return ClearBit(BitIndexFromAddr(addr));
187   }
188 
Test(uintptr_t addr)189   ALWAYS_INLINE bool Test(uintptr_t addr) const {
190     return TestBit(BitIndexFromAddr(addr));
191   }
192 
193   // Returns true if the object was previously set.
AtomicTestAndSet(uintptr_t addr)194   ALWAYS_INLINE bool AtomicTestAndSet(uintptr_t addr) {
195     return AtomicTestAndSetBit(BitIndexFromAddr(addr));
196   }
197 
198  private:
MemoryRangeBitmap(MemMap && mem_map,uintptr_t begin,size_t num_bits)199   MemoryRangeBitmap(MemMap&& mem_map, uintptr_t begin, size_t num_bits)
200       : Bitmap(std::move(mem_map), num_bits),
201         cover_begin_(begin) {}
202 
203   uintptr_t const cover_begin_;
204 
205   DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryRangeBitmap);
206 };
207 
208 }  // namespace accounting
209 }  // namespace gc
210 }  // namespace art
211 
212 #endif  // ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
213