• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2008 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_SPACE_BITMAP_H_
18 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_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 mirror {
33 class Class;
34 class Object;
35 }  // namespace mirror
36 
37 namespace gc {
38 namespace accounting {
39 
40 template<size_t kAlignment>
41 class SpaceBitmap {
42  public:
43   typedef void ScanCallback(mirror::Object* obj, void* finger, void* arg);
44   typedef void SweepCallback(size_t ptr_count, mirror::Object** ptrs, void* arg);
45 
46   // Initialize a space bitmap so that it points to a bitmap large enough to cover a heap at
47   // heap_begin of heap_capacity bytes, where objects are guaranteed to be kAlignment-aligned.
48   static SpaceBitmap* Create(const std::string& name, uint8_t* heap_begin, size_t heap_capacity);
49 
50   // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
51   // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
52   // Objects are kAlignement-aligned.
53   static SpaceBitmap* CreateFromMemMap(const std::string& name,
54                                        MemMap&& mem_map,
55                                        uint8_t* heap_begin,
56                                        size_t heap_capacity);
57 
58   ~SpaceBitmap();
59 
60   // Return the bitmap word index corresponding to memory offset (relative to
61   // `HeapBegin()`) `offset`.
62   // See also SpaceBitmap::OffsetBitIndex.
63   //
64   // <offset> is the difference from .base to a pointer address.
65   // <index> is the index of .bits that contains the bit representing
66   //         <offset>.
OffsetToIndex(size_t offset)67   static constexpr size_t OffsetToIndex(size_t offset) {
68     return offset / kAlignment / kBitsPerIntPtrT;
69   }
70 
71   // Return the memory offset (relative to `HeapBegin()`) corresponding to
72   // bitmap word index `index`.
73   template<typename T>
IndexToOffset(T index)74   static constexpr T IndexToOffset(T index) {
75     return static_cast<T>(index * kAlignment * kBitsPerIntPtrT);
76   }
77 
78   // Return the bit within the bitmap word index corresponding to
79   // memory offset (relative to `HeapBegin()`) `offset`.
80   // See also SpaceBitmap::OffsetToIndex.
OffsetBitIndex(uintptr_t offset)81   ALWAYS_INLINE static constexpr uintptr_t OffsetBitIndex(uintptr_t offset) {
82     return (offset / kAlignment) % kBitsPerIntPtrT;
83   }
84 
85   // Return the word-wide bit mask corresponding to `OffsetBitIndex(offset)`.
86   // Bits are packed in the obvious way.
OffsetToMask(uintptr_t offset)87   static constexpr uintptr_t OffsetToMask(uintptr_t offset) {
88     return static_cast<size_t>(1) << OffsetBitIndex(offset);
89   }
90 
91   // Set the bit corresponding to `obj` in the bitmap and return the previous value of that bit.
Set(const mirror::Object * obj)92   bool Set(const mirror::Object* obj) ALWAYS_INLINE {
93     return Modify<true>(obj);
94   }
95 
96   // Clear the bit corresponding to `obj` in the bitmap and return the previous value of that bit.
Clear(const mirror::Object * obj)97   bool Clear(const mirror::Object* obj) ALWAYS_INLINE {
98     return Modify<false>(obj);
99   }
100 
101   // Returns true if the object was previously marked.
102   bool AtomicTestAndSet(const mirror::Object* obj);
103 
104   // Fill the bitmap with zeroes.  Returns the bitmap's memory to the system as a side-effect.
105   void Clear();
106 
107   // Clear a range covered by the bitmap using madvise if possible.
108   void ClearRange(const mirror::Object* begin, const mirror::Object* end);
109 
110   // Test whether `obj` is part of the bitmap (i.e. return whether the bit
111   // corresponding to `obj` has been set in the bitmap).
112   //
113   // Precondition: `obj` is within the range of pointers that this bitmap could
114   // potentially cover (i.e. `this->HasAddress(obj)` is true)
115   bool Test(const mirror::Object* obj) const;
116 
117   // Return true iff <obj> is within the range of pointers that this bitmap could potentially cover,
118   // even if a bit has not been set for it.
HasAddress(const void * obj)119   bool HasAddress(const void* obj) const {
120     // If obj < heap_begin_ then offset underflows to some very large value past the end of the
121     // bitmap.
122     const uintptr_t offset = reinterpret_cast<uintptr_t>(obj) - heap_begin_;
123     const size_t index = OffsetToIndex(offset);
124     return index < bitmap_size_ / sizeof(intptr_t);
125   }
126 
127   class ClearVisitor {
128    public:
ClearVisitor(SpaceBitmap * const bitmap)129     explicit ClearVisitor(SpaceBitmap* const bitmap)
130         : bitmap_(bitmap) {
131     }
132 
operator()133     void operator()(mirror::Object* obj) const {
134       bitmap_->Clear(obj);
135     }
136    private:
137     SpaceBitmap* const bitmap_;
138   };
139 
140   template <typename Visitor>
VisitRange(uintptr_t visit_begin,uintptr_t visit_end,const Visitor & visitor)141   void VisitRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
142     for (; visit_begin < visit_end; visit_begin += kAlignment) {
143       visitor(reinterpret_cast<mirror::Object*>(visit_begin));
144     }
145   }
146 
147   // Visit the live objects in the range [visit_begin, visit_end).
148   // TODO: Use lock annotations when clang is fixed.
149   // REQUIRES(Locks::heap_bitmap_lock_) REQUIRES_SHARED(Locks::mutator_lock_);
150   template <typename Visitor>
151   void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, Visitor&& visitor) const
152       NO_THREAD_SAFETY_ANALYSIS;
153 
154   // Visit all of the set bits in HeapBegin(), HeapLimit().
155   template <typename Visitor>
VisitAllMarked(Visitor && visitor)156   void VisitAllMarked(Visitor&& visitor) const {
157     VisitMarkedRange(HeapBegin(), HeapLimit(), visitor);
158   }
159 
160   // Visits set bits in address order.  The callback is not permitted to change the bitmap bits or
161   // max during the traversal.
162   template <typename Visitor>
163   void Walk(Visitor&& visitor)
164       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
165 
166   // Walk through the bitmaps in increasing address order, and find the object pointers that
167   // correspond to garbage objects.  Call <callback> zero or more times with lists of these object
168   // pointers. The callback is not permitted to increase the max of either bitmap.
169   static void SweepWalk(const SpaceBitmap& live, const SpaceBitmap& mark, uintptr_t base,
170                         uintptr_t max, SweepCallback* thunk, void* arg);
171 
172   void CopyFrom(SpaceBitmap* source_bitmap);
173 
174   // Starting address of our internal storage.
Begin()175   Atomic<uintptr_t>* Begin() {
176     return bitmap_begin_;
177   }
178 
179   // Size of our internal storage
Size()180   size_t Size() const {
181     return bitmap_size_;
182   }
183 
184   // Size in bytes of the memory that the bitmaps spans.
HeapSize()185   uint64_t HeapSize() const {
186     return IndexToOffset<uint64_t>(Size() / sizeof(intptr_t));
187   }
188 
SetHeapSize(size_t bytes)189   void SetHeapSize(size_t bytes) {
190     // TODO: Un-map the end of the mem map.
191     heap_limit_ = heap_begin_ + bytes;
192     bitmap_size_ = OffsetToIndex(bytes) * sizeof(intptr_t);
193     CHECK_EQ(HeapSize(), bytes);
194   }
195 
HeapBegin()196   uintptr_t HeapBegin() const {
197     return heap_begin_;
198   }
199 
200   // The maximum address which the bitmap can span. (HeapBegin() <= object < HeapLimit()).
HeapLimit()201   uint64_t HeapLimit() const {
202     return heap_limit_;
203   }
204 
205   // Set the max address which can covered by the bitmap.
206   void SetHeapLimit(uintptr_t new_end);
207 
GetName()208   std::string GetName() const {
209     return name_;
210   }
211 
SetName(const std::string & name)212   void SetName(const std::string& name) {
213     name_ = name;
214   }
215 
216   std::string Dump() const;
217 
218   // Helper function for computing bitmap size based on a 64 bit capacity.
219   static size_t ComputeBitmapSize(uint64_t capacity);
220   static size_t ComputeHeapSize(uint64_t bitmap_bytes);
221 
222  private:
223   // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
224   // however, we document that this is expected on heap_end_
225   SpaceBitmap(const std::string& name,
226               MemMap&& mem_map,
227               uintptr_t* bitmap_begin,
228               size_t bitmap_size,
229               const void* heap_begin,
230               size_t heap_capacity);
231 
232   // Change the value of the bit corresponding to `obj` in the bitmap
233   // to `kSetBit` and return the previous value of that bit.
234   template<bool kSetBit>
235   bool Modify(const mirror::Object* obj);
236 
237   // Backing storage for bitmap.
238   MemMap mem_map_;
239 
240   // This bitmap itself, word sized for efficiency in scanning.
241   Atomic<uintptr_t>* const bitmap_begin_;
242 
243   // Size of this bitmap.
244   size_t bitmap_size_;
245 
246   // The start address of the memory covered by the bitmap, which corresponds to the word
247   // containing the first bit in the bitmap.
248   const uintptr_t heap_begin_;
249 
250   // The end address of the memory covered by the bitmap. This may not be on a word boundary.
251   uintptr_t heap_limit_;
252 
253   // Name of this bitmap.
254   std::string name_;
255 };
256 
257 typedef SpaceBitmap<kObjectAlignment> ContinuousSpaceBitmap;
258 typedef SpaceBitmap<kLargeObjectAlignment> LargeObjectBitmap;
259 
260 template<size_t kAlignment>
261 std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap);
262 
263 }  // namespace accounting
264 }  // namespace gc
265 }  // namespace art
266 
267 #endif  // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_H_
268