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