space_bitmap.cc revision 700a402244a1a423da4f3ba8032459f4b65fa18f
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 "space_bitmap-inl.h" 18 19namespace art { 20namespace gc { 21namespace accounting { 22 23template<size_t kAlignment> 24size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) { 25 const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerWord; 26 return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * kWordSize; 27} 28 29template<size_t kAlignment> 30SpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::CreateFromMemMap( 31 const std::string& name, MemMap* mem_map, byte* heap_begin, size_t heap_capacity) { 32 CHECK(mem_map != nullptr); 33 uword* bitmap_begin = reinterpret_cast<uword*>(mem_map->Begin()); 34 const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 35 return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin); 36} 37 38template<size_t kAlignment> 39SpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name, MemMap* mem_map, uword* bitmap_begin, 40 size_t bitmap_size, const void* heap_begin) 41 : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size), 42 heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)), 43 name_(name) { 44 CHECK(bitmap_begin_ != nullptr); 45 CHECK_NE(bitmap_size, 0U); 46} 47 48template<size_t kAlignment> 49SpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::Create( 50 const std::string& name, byte* heap_begin, size_t heap_capacity) { 51 // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 52 const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 53 std::string error_msg; 54 std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size, 55 PROT_READ | PROT_WRITE, false, &error_msg)); 56 if (UNLIKELY(mem_map.get() == nullptr)) { 57 LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg; 58 return nullptr; 59 } 60 return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity); 61} 62 63template<size_t kAlignment> 64void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) { 65 DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 66 size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 67 if (new_size < bitmap_size_) { 68 bitmap_size_ = new_size; 69 } 70 // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 71 // should be marked. 72} 73 74template<size_t kAlignment> 75void SpaceBitmap<kAlignment>::Clear() { 76 if (bitmap_begin_ != NULL) { 77 // This returns the memory to the system. Successive page faults will return zeroed memory. 78 int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 79 if (result == -1) { 80 PLOG(FATAL) << "madvise failed"; 81 } 82 } 83} 84 85template<size_t kAlignment> 86void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) { 87 DCHECK_EQ(Size(), source_bitmap->Size()); 88 std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 89} 90 91template<size_t kAlignment> 92void SpaceBitmap<kAlignment>::Walk(ObjectCallback* callback, void* arg) { 93 CHECK(bitmap_begin_ != NULL); 94 CHECK(callback != NULL); 95 96 uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 97 uword* bitmap_begin = bitmap_begin_; 98 for (uintptr_t i = 0; i <= end; ++i) { 99 uword w = bitmap_begin[i]; 100 if (w != 0) { 101 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 102 do { 103 const size_t shift = CTZ(w); 104 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 105 (*callback)(obj, arg); 106 w ^= (static_cast<uword>(1)) << shift; 107 } while (w != 0); 108 } 109 } 110} 111 112template<size_t kAlignment> 113void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap, 114 const SpaceBitmap<kAlignment>& mark_bitmap, 115 uintptr_t sweep_begin, uintptr_t sweep_end, 116 SpaceBitmap::SweepCallback* callback, void* arg) { 117 CHECK(live_bitmap.bitmap_begin_ != nullptr); 118 CHECK(mark_bitmap.bitmap_begin_ != nullptr); 119 CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 120 CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 121 CHECK(callback != NULL); 122 CHECK_LE(sweep_begin, sweep_end); 123 CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 124 125 if (sweep_end <= sweep_begin) { 126 return; 127 } 128 129 // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 130 const size_t buffer_size = kWordSize * kBitsPerWord; 131 mirror::Object* pointer_buf[buffer_size]; 132 mirror::Object** pb = &pointer_buf[0]; 133 size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 134 size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 135 CHECK_LT(end, live_bitmap.Size() / kWordSize); 136 uword* live = live_bitmap.bitmap_begin_; 137 uword* mark = mark_bitmap.bitmap_begin_; 138 for (size_t i = start; i <= end; i++) { 139 uword garbage = live[i] & ~mark[i]; 140 if (UNLIKELY(garbage != 0)) { 141 uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 142 do { 143 const size_t shift = CTZ(garbage); 144 garbage ^= (static_cast<uword>(1)) << shift; 145 *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 146 } while (garbage != 0); 147 // Make sure that there are always enough slots available for an 148 // entire word of one bits. 149 if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 150 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 151 pb = &pointer_buf[0]; 152 } 153 } 154 } 155 if (pb > &pointer_buf[0]) { 156 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 157 } 158} 159 160template<size_t kAlignment> 161void SpaceBitmap<kAlignment>::WalkInstanceFields(SpaceBitmap<kAlignment>* visited, 162 ObjectCallback* callback, mirror::Object* obj, 163 mirror::Class* klass, void* arg) 164 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 165 // Visit fields of parent classes first. 166 mirror::Class* super = klass->GetSuperClass(); 167 if (super != NULL) { 168 WalkInstanceFields(visited, callback, obj, super, arg); 169 } 170 // Walk instance fields 171 mirror::ObjectArray<mirror::ArtField>* fields = klass->GetIFields(); 172 if (fields != NULL) { 173 for (int32_t i = 0; i < fields->GetLength(); i++) { 174 mirror::ArtField* field = fields->Get(i); 175 FieldHelper fh(field); 176 if (!fh.IsPrimitiveType()) { 177 mirror::Object* value = field->GetObj(obj); 178 if (value != NULL) { 179 WalkFieldsInOrder(visited, callback, value, arg); 180 } 181 } 182 } 183 } 184} 185 186template<size_t kAlignment> 187void SpaceBitmap<kAlignment>::WalkFieldsInOrder(SpaceBitmap<kAlignment>* visited, 188 ObjectCallback* callback, mirror::Object* obj, 189 void* arg) { 190 if (visited->Test(obj)) { 191 return; 192 } 193 // visit the object itself 194 (*callback)(obj, arg); 195 visited->Set(obj); 196 // Walk instance fields of all objects 197 mirror::Class* klass = obj->GetClass(); 198 WalkInstanceFields(visited, callback, obj, klass, arg); 199 // Walk static fields of a Class 200 if (obj->IsClass()) { 201 mirror::ObjectArray<mirror::ArtField>* fields = klass->GetSFields(); 202 if (fields != NULL) { 203 for (int32_t i = 0; i < fields->GetLength(); i++) { 204 mirror::ArtField* field = fields->Get(i); 205 FieldHelper fh(field); 206 if (!fh.IsPrimitiveType()) { 207 mirror::Object* value = field->GetObj(NULL); 208 if (value != NULL) { 209 WalkFieldsInOrder(visited, callback, value, arg); 210 } 211 } 212 } 213 } 214 } else if (obj->IsObjectArray()) { 215 // Walk elements of an object array 216 mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 217 int32_t length = obj_array->GetLength(); 218 for (int32_t i = 0; i < length; i++) { 219 mirror::Object* value = obj_array->Get(i); 220 if (value != NULL) { 221 WalkFieldsInOrder(visited, callback, value, arg); 222 } 223 } 224 } 225} 226 227template<size_t kAlignment> 228void SpaceBitmap<kAlignment>::InOrderWalk(ObjectCallback* callback, void* arg) { 229 std::unique_ptr<SpaceBitmap<kAlignment>> visited( 230 Create("bitmap for in-order walk", reinterpret_cast<byte*>(heap_begin_), 231 IndexToOffset(bitmap_size_ / kWordSize))); 232 CHECK(bitmap_begin_ != nullptr); 233 CHECK(callback != nullptr); 234 uintptr_t end = Size() / kWordSize; 235 for (uintptr_t i = 0; i < end; ++i) { 236 // Need uint for unsigned shift. 237 uword w = bitmap_begin_[i]; 238 if (UNLIKELY(w != 0)) { 239 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 240 while (w != 0) { 241 const size_t shift = CTZ(w); 242 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 243 WalkFieldsInOrder(visited.get(), callback, obj, arg); 244 w ^= (static_cast<uword>(1)) << shift; 245 } 246 } 247 } 248} 249 250template class SpaceBitmap<kObjectAlignment>; 251template class SpaceBitmap<kPageSize>; 252 253} // namespace accounting 254} // namespace gc 255} // namespace art 256