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