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