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