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