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 "locks.h"
21#include "gc_allocator.h"
22#include "globals.h"
23#include "mem_map.h"
24#include "UniquePtr.h"
25
26#include <limits.h>
27#include <set>
28#include <stdint.h>
29#include <vector>
30
31namespace art {
32
33namespace mirror {
34  class Object;
35}  // namespace mirror
36
37namespace gc {
38namespace accounting {
39
40class SpaceBitmap {
41 public:
42  // Alignment of objects within spaces.
43  static const size_t kAlignment = 8;
44
45  typedef void Callback(mirror::Object* obj, void* arg);
46
47  typedef void ScanCallback(mirror::Object* obj, void* finger, void* arg);
48
49  typedef void SweepCallback(size_t ptr_count, mirror::Object** ptrs, void* arg);
50
51  // Initialize a space bitmap so that it points to a bitmap large enough to cover a heap at
52  // heap_begin of heap_capacity bytes, where objects are guaranteed to be kAlignment-aligned.
53  static SpaceBitmap* Create(const std::string& name, byte* heap_begin, size_t heap_capacity);
54
55  // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
56  // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
57  // Objects are kAlignement-aligned.
58  static SpaceBitmap* CreateFromMemMap(const std::string& name, MemMap* mem_map,
59                                       byte* heap_begin, size_t heap_capacity);
60
61  ~SpaceBitmap();
62
63  // <offset> is the difference from .base to a pointer address.
64  // <index> is the index of .bits that contains the bit representing
65  //         <offset>.
66  static size_t OffsetToIndex(size_t offset) {
67    return offset / kAlignment / kBitsPerWord;
68  }
69
70  static uintptr_t IndexToOffset(size_t index) {
71    return static_cast<uintptr_t>(index * kAlignment * kBitsPerWord);
72  }
73
74  // Pack the bits in backwards so they come out in address order when using CLZ.
75  static word OffsetToMask(uintptr_t offset_) {
76    return static_cast<uintptr_t>(kWordHighBitMask) >> ((offset_ / kAlignment) % kBitsPerWord);
77  }
78
79  inline bool Set(const mirror::Object* obj) {
80    return Modify(obj, true);
81  }
82
83  inline bool Clear(const mirror::Object* obj) {
84    return Modify(obj, false);
85  }
86
87  // Returns true if the object was previously marked.
88  bool AtomicTestAndSet(const mirror::Object* obj);
89
90  // Fill the bitmap with zeroes.  Returns the bitmap's memory to the system as a side-effect.
91  void Clear();
92
93  bool Test(const mirror::Object* obj) const;
94
95  // Return true iff <obj> is within the range of pointers that this bitmap could potentially cover,
96  // even if a bit has not been set for it.
97  bool HasAddress(const void* obj) const {
98    // If obj < heap_begin_ then offset underflows to some very large value past the end of the
99    // bitmap.
100    const uintptr_t offset = reinterpret_cast<uintptr_t>(obj) - heap_begin_;
101    const size_t index = OffsetToIndex(offset);
102    return index < bitmap_size_ / kWordSize;
103  }
104
105  void VisitRange(uintptr_t base, uintptr_t max, Callback* visitor, void* arg) const;
106
107  class ClearVisitor {
108   public:
109    explicit ClearVisitor(SpaceBitmap* const bitmap)
110        : bitmap_(bitmap) {
111    }
112
113    void operator()(mirror::Object* obj) const {
114      bitmap_->Clear(obj);
115    }
116   private:
117    SpaceBitmap* const bitmap_;
118  };
119
120  template <typename Visitor>
121  void VisitRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
122    for (; visit_begin < visit_end; visit_begin += kAlignment) {
123      visitor(reinterpret_cast<mirror::Object*>(visit_begin));
124    }
125  }
126
127  template <typename Visitor>
128  void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const
129      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
130      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
131
132  void Walk(Callback* callback, void* arg)
133      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
134
135  void InOrderWalk(Callback* callback, void* arg)
136      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
137
138  static void SweepWalk(const SpaceBitmap& live, const SpaceBitmap& mark, uintptr_t base,
139                        uintptr_t max, SweepCallback* thunk, void* arg);
140
141  void CopyFrom(SpaceBitmap* source_bitmap);
142
143  // Starting address of our internal storage.
144  word* Begin() {
145    return bitmap_begin_;
146  }
147
148  // Size of our internal storage
149  size_t Size() const {
150    return bitmap_size_;
151  }
152
153  // Size in bytes of the memory that the bitmaps spans.
154  size_t HeapSize() const {
155    return IndexToOffset(Size() / kWordSize);
156  }
157
158  uintptr_t HeapBegin() const {
159    return heap_begin_;
160  }
161
162  // The maximum address which the bitmap can span. (HeapBegin() <= object < HeapLimit()).
163  uintptr_t HeapLimit() const {
164    return HeapBegin() + static_cast<uintptr_t>(HeapSize());
165  }
166
167  // Set the max address which can covered by the bitmap.
168  void SetHeapLimit(uintptr_t new_end);
169
170  std::string GetName() const;
171  void SetName(const std::string& name);
172
173  std::string Dump() const;
174
175  const void* GetObjectWordAddress(const mirror::Object* obj) const {
176    uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
177    const uintptr_t offset = addr - heap_begin_;
178    const size_t index = OffsetToIndex(offset);
179    return &bitmap_begin_[index];
180  }
181
182 private:
183  // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
184  // however, we document that this is expected on heap_end_
185  SpaceBitmap(const std::string& name, MemMap* mem_map, word* bitmap_begin, size_t bitmap_size,
186              const void* heap_begin)
187      : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size),
188        heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
189        name_(name) {}
190
191  bool Modify(const mirror::Object* obj, bool do_set);
192
193  // Backing storage for bitmap.
194  UniquePtr<MemMap> mem_map_;
195
196  // This bitmap itself, word sized for efficiency in scanning.
197  word* const bitmap_begin_;
198
199  // Size of this bitmap.
200  size_t bitmap_size_;
201
202  // The base address of the heap, which corresponds to the word containing the first bit in the
203  // bitmap.
204  const uintptr_t heap_begin_;
205
206  // Name of this bitmap.
207  std::string name_;
208};
209
210// Like a bitmap except it keeps track of objects using sets.
211class SpaceSetMap {
212 public:
213  typedef std::set<
214      const mirror::Object*, std::less<const mirror::Object*>,
215      GCAllocator<const mirror::Object*> > Objects;
216
217  bool IsEmpty() const {
218    return contained_.empty();
219  }
220
221  inline void Set(const mirror::Object* obj) {
222    contained_.insert(obj);
223  }
224
225  inline void Clear(const mirror::Object* obj) {
226    Objects::iterator found = contained_.find(obj);
227    if (found != contained_.end()) {
228      contained_.erase(found);
229    }
230  }
231
232  void Clear() {
233    contained_.clear();
234  }
235
236  inline bool Test(const mirror::Object* obj) const {
237    return contained_.find(obj) != contained_.end();
238  }
239
240  std::string GetName() const;
241  void SetName(const std::string& name);
242
243  void Walk(SpaceBitmap::Callback* callback, void* arg)
244      SHARED_LOCKS_REQUIRED(GlobalSynchronization::heap_bitmap_lock_);
245
246  void CopyFrom(const SpaceSetMap& space_set);
247
248  template <typename Visitor>
249  void Visit(const Visitor& visitor) NO_THREAD_SAFETY_ANALYSIS {
250    for (Objects::iterator it = contained_.begin(); it != contained_.end(); ++it) {
251      visitor(*it);
252    }
253  }
254
255  explicit SpaceSetMap(const std::string& name) : name_(name) {}
256  ~SpaceSetMap() {}
257
258  Objects& GetObjects() {
259    return contained_;
260  }
261
262 private:
263  std::string name_;
264  Objects contained_;
265};
266
267std::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap);
268
269}  // namespace accounting
270}  // namespace gc
271}  // namespace art
272
273#endif  // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_H_
274