space_bitmap.cc revision 7940e44f4517de5e2634a7e07d58d0fb26160513
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#include "base/logging.h" 18#include "dex_file-inl.h" 19#include "heap_bitmap.h" 20#include "mirror/class-inl.h" 21#include "mirror/field-inl.h" 22#include "mirror/object-inl.h" 23#include "mirror/object_array-inl.h" 24#include "object_utils.h" 25#include "space_bitmap-inl.h" 26#include "UniquePtr.h" 27#include "utils.h" 28 29namespace art { 30namespace gc { 31namespace accounting { 32 33std::string SpaceBitmap::GetName() const { 34 return name_; 35} 36 37void SpaceBitmap::SetName(const std::string& name) { 38 name_ = name; 39} 40 41std::string SpaceBitmap::Dump() const { 42 return StringPrintf("%s: %p-%p", name_.c_str(), 43 reinterpret_cast<void*>(HeapBegin()), 44 reinterpret_cast<void*>(HeapLimit())); 45} 46 47void SpaceSetMap::Walk(SpaceBitmap::Callback* callback, void* arg) { 48 for (Objects::iterator it = contained_.begin(); it != contained_.end(); ++it) { 49 callback(const_cast<mirror::Object*>(*it), arg); 50 } 51} 52 53SpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) { 54 CHECK(heap_begin != NULL); 55 // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 56 size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 57 UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE)); 58 if (mem_map.get() == NULL) { 59 LOG(ERROR) << "Failed to allocate bitmap " << name; 60 return NULL; 61 } 62 word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin()); 63 return new SpaceBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin); 64} 65 66// Clean up any resources associated with the bitmap. 67SpaceBitmap::~SpaceBitmap() { 68 69} 70 71void SpaceBitmap::SetHeapLimit(uintptr_t new_end) { 72 DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 73 size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 74 if (new_size < bitmap_size_) { 75 bitmap_size_ = new_size; 76 } 77 // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 78 // should be marked. 79 // TODO: Fix this code is, it broken and causes rare heap corruption! 80 // mem_map_->Trim(reinterpret_cast<byte*>(heap_begin_ + bitmap_size_)); 81} 82 83void SpaceBitmap::Clear() { 84 if (bitmap_begin_ != NULL) { 85 // This returns the memory to the system. Successive page faults 86 // will return zeroed memory. 87 int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 88 if (result == -1) { 89 PLOG(FATAL) << "madvise failed"; 90 } 91 } 92} 93 94void SpaceBitmap::CopyFrom(SpaceBitmap* source_bitmap) { 95 DCHECK_EQ(Size(), source_bitmap->Size()); 96 std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 97} 98 99// Visits set bits in address order. The callback is not permitted to 100// change the bitmap bits or max during the traversal. 101void SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) { 102 CHECK(bitmap_begin_ != NULL); 103 CHECK(callback != NULL); 104 105 uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 106 word* bitmap_begin = bitmap_begin_; 107 for (uintptr_t i = 0; i <= end; ++i) { 108 word w = bitmap_begin[i]; 109 if (w != 0) { 110 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 111 do { 112 const size_t shift = CLZ(w); 113 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 114 (*callback)(obj, arg); 115 w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 116 } while (w != 0); 117 } 118 } 119} 120 121// Walk through the bitmaps in increasing address order, and find the 122// object pointers that correspond to garbage objects. Call 123// <callback> zero or more times with lists of these object pointers. 124// 125// The callback is not permitted to increase the max of either bitmap. 126void SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap, 127 const SpaceBitmap& mark_bitmap, 128 uintptr_t sweep_begin, uintptr_t sweep_end, 129 SpaceBitmap::SweepCallback* callback, void* arg) { 130 CHECK(live_bitmap.bitmap_begin_ != NULL); 131 CHECK(mark_bitmap.bitmap_begin_ != NULL); 132 CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 133 CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 134 CHECK(callback != NULL); 135 CHECK_LE(sweep_begin, sweep_end); 136 CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 137 138 if (sweep_end <= sweep_begin) { 139 return; 140 } 141 142 // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 143 const size_t buffer_size = kWordSize * kBitsPerWord; 144 mirror::Object* pointer_buf[buffer_size]; 145 mirror::Object** pb = &pointer_buf[0]; 146 size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 147 size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 148 CHECK_LT(end, live_bitmap.Size() / kWordSize); 149 word* live = live_bitmap.bitmap_begin_; 150 word* mark = mark_bitmap.bitmap_begin_; 151 for (size_t i = start; i <= end; i++) { 152 word garbage = live[i] & ~mark[i]; 153 if (UNLIKELY(garbage != 0)) { 154 uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 155 do { 156 const size_t shift = CLZ(garbage); 157 garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift; 158 *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 159 } while (garbage != 0); 160 // Make sure that there are always enough slots available for an 161 // entire word of one bits. 162 if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 163 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 164 pb = &pointer_buf[0]; 165 } 166 } 167 } 168 if (pb > &pointer_buf[0]) { 169 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 170 } 171} 172 173static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 174 void* arg); 175 176// Walk instance fields of the given Class. Separate function to allow recursion on the super 177// class. 178static void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 179 mirror::Class* klass, void* arg) 180 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 181 // Visit fields of parent classes first. 182 mirror::Class* super = klass->GetSuperClass(); 183 if (super != NULL) { 184 WalkInstanceFields(visited, callback, obj, super, arg); 185 } 186 // Walk instance fields 187 mirror::ObjectArray<mirror::Field>* fields = klass->GetIFields(); 188 if (fields != NULL) { 189 for (int32_t i = 0; i < fields->GetLength(); i++) { 190 mirror::Field* field = fields->Get(i); 191 FieldHelper fh(field); 192 if (!fh.IsPrimitiveType()) { 193 mirror::Object* value = field->GetObj(obj); 194 if (value != NULL) { 195 WalkFieldsInOrder(visited, callback, value, arg); 196 } 197 } 198 } 199 } 200} 201 202// For an unvisited object, visit it then all its children found via fields. 203static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 204 void* arg) 205 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 206 if (visited->Test(obj)) { 207 return; 208 } 209 // visit the object itself 210 (*callback)(obj, arg); 211 visited->Set(obj); 212 // Walk instance fields of all objects 213 mirror::Class* klass = obj->GetClass(); 214 WalkInstanceFields(visited, callback, obj, klass, arg); 215 // Walk static fields of a Class 216 if (obj->IsClass()) { 217 mirror::ObjectArray<mirror::Field>* fields = klass->GetSFields(); 218 if (fields != NULL) { 219 for (int32_t i = 0; i < fields->GetLength(); i++) { 220 mirror::Field* field = fields->Get(i); 221 FieldHelper fh(field); 222 if (!fh.IsPrimitiveType()) { 223 mirror::Object* value = field->GetObj(NULL); 224 if (value != NULL) { 225 WalkFieldsInOrder(visited, callback, value, arg); 226 } 227 } 228 } 229 } 230 } else if (obj->IsObjectArray()) { 231 // Walk elements of an object array 232 mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 233 int32_t length = obj_array->GetLength(); 234 for (int32_t i = 0; i < length; i++) { 235 mirror::Object* value = obj_array->Get(i); 236 if (value != NULL) { 237 WalkFieldsInOrder(visited, callback, value, arg); 238 } 239 } 240 } 241} 242 243// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap 244// bits or max during the traversal. 245void SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) { 246 UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk", 247 reinterpret_cast<byte*>(heap_begin_), 248 IndexToOffset(bitmap_size_ / kWordSize))); 249 CHECK(bitmap_begin_ != NULL); 250 CHECK(callback != NULL); 251 uintptr_t end = Size() / kWordSize; 252 for (uintptr_t i = 0; i < end; ++i) { 253 word w = bitmap_begin_[i]; 254 if (UNLIKELY(w != 0)) { 255 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 256 while (w != 0) { 257 const size_t shift = CLZ(w); 258 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 259 WalkFieldsInOrder(visited.get(), callback, obj, arg); 260 w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 261 } 262 } 263 } 264} 265 266std::string SpaceSetMap::GetName() const { 267 return name_; 268} 269 270void SpaceSetMap::SetName(const std::string& name) { 271 name_ = name; 272} 273 274void SpaceSetMap::CopyFrom(const SpaceSetMap& space_set) { 275 contained_ = space_set.contained_; 276} 277 278std::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap) { 279 return stream 280 << bitmap.GetName() << "[" 281 << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 282 << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 283 << "]"; 284} 285 286} // namespace accounting 287} // namespace gc 288} // namespace art 289