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