space_bitmap.cc revision cc236d74772dda5a4161d9bc5f497fd3d956eb87
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 "logging.h" 20#include "UniquePtr.h" 21#include "utils.h" 22 23namespace art { 24 25SpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) { 26 CHECK(heap_begin != NULL); 27 // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 28 size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 29 UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE)); 30 if (mem_map.get() == NULL) { 31 LOG(ERROR) << "Failed to allocate bitmap " << name; 32 return NULL; 33 } 34 word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin()); 35 return new SpaceBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin); 36} 37 38// Clean up any resources associated with the bitmap. 39SpaceBitmap::~SpaceBitmap() {} 40 41void SpaceBitmap::Trim(size_t heap_capacity) { 42 size_t new_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 43 if (new_size < bitmap_size_) { 44 bitmap_size_ = new_size; 45 } 46 // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 47 // should be marked. 48 // TODO: Fix this code is, it broken and causes rare heap corruption! 49 // mem_map_->Trim(reinterpret_cast<byte*>(heap_begin_ + bitmap_size_)); 50} 51 52// Fill the bitmap with zeroes. Returns the bitmap's memory to the 53// system as a side-effect. 54void SpaceBitmap::Clear() { 55 if (bitmap_begin_ != NULL) { 56 // This returns the memory to the system. Successive page faults 57 // will return zeroed memory. 58 int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 59 if (result == -1) { 60 PLOG(WARNING) << "madvise failed"; 61 } 62 heap_end_ = heap_begin_ - 1; 63 } 64} 65 66// Return true iff <obj> is within the range of pointers that this bitmap could potentially cover, 67// even if a bit has not been set for it. 68bool SpaceBitmap::HasAddress(const void* obj) const { 69 // If obj < heap_begin_ then offset underflows to some very large value past the end of the bitmap. 70 const uintptr_t offset = (uintptr_t)obj - heap_begin_; 71 const size_t index = OffsetToIndex(offset); 72 return index < bitmap_size_ / kWordSize; 73} 74 75// Visits set bits in address order. The callback is not permitted to 76// change the bitmap bits or max during the traversal. 77void SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) { 78 CHECK(bitmap_begin_ != NULL); 79 CHECK(callback != NULL); 80 if (heap_end_ < heap_begin_) { 81 return; // Bitmap is empty. 82 } 83 uintptr_t end = OffsetToIndex(heap_end_ - heap_begin_); 84 for (uintptr_t i = 0; i <= end; ++i) { 85 word w = bitmap_begin_[i]; 86 if (UNLIKELY(w != 0)) { 87 word high_bit = 1 << (kBitsPerWord - 1); 88 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 89 while (w != 0) { 90 const int shift = CLZ(w); 91 Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment); 92 (*callback)(obj, arg); 93 w &= ~(high_bit >> shift); 94 } 95 } 96 } 97} 98 99// Similar to Walk but the callback routine is permitted to change the bitmap bits and end during 100// traversal. Used by the the root marking scan exclusively. 101// 102// The callback is invoked with a finger argument. The finger is a pointer to an address not yet 103// visited by the traversal. If the callback sets a bit for an address at or above the finger, this 104// address will be visited by the traversal. If the callback sets a bit for an address below the 105// finger, this address will not be visited (typiscally such an address would be placed on the 106// marking stack). 107void SpaceBitmap::ScanWalk(uintptr_t scan_begin, uintptr_t scan_end, ScanCallback* callback, void* arg) { 108 CHECK(bitmap_begin_ != NULL); 109 CHECK(callback != NULL); 110 CHECK_LE(scan_begin, scan_end); 111 CHECK_GE(scan_begin, heap_begin_); 112 113 // This function doesn't support unaligned boundaries yet. 114 size_t begin_offset = scan_begin - heap_begin_; 115 size_t end_offset = scan_end - heap_begin_; 116 DCHECK((begin_offset / kAlignment) % kBitsPerWord == 0) 117 << "scan begin " << reinterpret_cast<const void*>(scan_begin) 118 << " with offset " << begin_offset 119 << " not aligned to word boundary"; 120 DCHECK((end_offset / kAlignment) % kBitsPerWord == 0) 121 << "scan end " << reinterpret_cast<const void*>(scan_end) 122 << " with offset " << end_offset 123 << " not aligned to word boundary"; 124 125 size_t start = OffsetToIndex(begin_offset); 126 if (scan_end < heap_end_) { 127 // The end of the space we're looking at is before the current maximum bitmap PC, scan to that 128 // and don't recompute end on each iteration 129 size_t end = OffsetToIndex(end_offset - 1); 130 for (size_t i = start; i <= end; i++) { 131 word w = bitmap_begin_[i]; 132 if (UNLIKELY(w != 0)) { 133 word high_bit = 1 << (kBitsPerWord - 1); 134 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 135 void* finger = reinterpret_cast<void*>(IndexToOffset(i + 1) + heap_begin_); 136 while (w != 0) { 137 const int shift = CLZ(w); 138 Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment); 139 (*callback)(obj, finger, arg); 140 w &= ~(high_bit >> shift); 141 } 142 } 143 } 144 } else { 145 size_t end = OffsetToIndex(heap_end_ - heap_begin_); 146 for (size_t i = start; i <= end; i++) { 147 word w = bitmap_begin_[i]; 148 if (UNLIKELY(w != 0)) { 149 word high_bit = 1 << (kBitsPerWord - 1); 150 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 151 void* finger = reinterpret_cast<void*>(IndexToOffset(i + 1) + heap_begin_); 152 while (w != 0) { 153 const int shift = CLZ(w); 154 Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment); 155 (*callback)(obj, finger, arg); 156 w &= ~(high_bit >> shift); 157 } 158 } 159 // update 'end' in case callback modified bitmap 160 end = OffsetToIndex(heap_end_ - heap_begin_); 161 } 162 } 163} 164 165// Walk through the bitmaps in increasing address order, and find the 166// object pointers that correspond to garbage objects. Call 167// <callback> zero or more times with lists of these object pointers. 168// 169// The callback is not permitted to increase the max of either bitmap. 170void SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap, 171 const SpaceBitmap& mark_bitmap, 172 uintptr_t sweep_begin, uintptr_t sweep_end, 173 SpaceBitmap::SweepCallback* callback, void* arg) { 174 CHECK(live_bitmap.bitmap_begin_ != NULL); 175 CHECK(mark_bitmap.bitmap_begin_ != NULL); 176 CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 177 CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 178 CHECK(callback != NULL); 179 CHECK_LE(sweep_begin, sweep_end); 180 CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 181 sweep_end = std::min(sweep_end - 1, live_bitmap.heap_end_); 182 if (live_bitmap.heap_end_ < live_bitmap.heap_begin_) { 183 // Easy case; both are obviously empty. 184 // TODO: this should never happen 185 return; 186 } 187 // TODO: rewrite the callbacks to accept a std::vector<Object*> rather than a Object**? 188 std::vector<Object*> pointer_buf(4 * kBitsPerWord); 189 Object** pb = &pointer_buf[0]; 190 size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 191 size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_); 192 word* live = live_bitmap.bitmap_begin_; 193 word* mark = mark_bitmap.bitmap_begin_; 194 for (size_t i = start; i <= end; i++) { 195 word garbage = live[i] & ~mark[i]; 196 if (UNLIKELY(garbage != 0)) { 197 word high_bit = 1 << (kBitsPerWord - 1); 198 uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 199 while (garbage != 0) { 200 int shift = CLZ(garbage); 201 garbage &= ~(high_bit >> shift); 202 *pb++ = reinterpret_cast<Object*>(ptr_base + shift * kAlignment); 203 } 204 // Make sure that there are always enough slots available for an 205 // entire word of one bits. 206 if (pb >= &pointer_buf[pointer_buf.size() - kBitsPerWord]) { 207 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 208 pb = &pointer_buf[0]; 209 } 210 } 211 } 212 if (pb > &pointer_buf[0]) { 213 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 214 } 215} 216 217} // namespace art 218 219// Support needed for in order traversal 220#include "object.h" 221#include "object_utils.h" 222 223namespace art { 224 225static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj, 226 void* arg); 227 228// Walk instance fields of the given Class. Separate function to allow recursion on the super 229// class. 230static void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj, 231 Class* klass, void* arg) { 232 // Visit fields of parent classes first. 233 Class* super = klass->GetSuperClass(); 234 if (super != NULL) { 235 WalkInstanceFields(visited, callback, obj, super, arg); 236 } 237 // Walk instance fields 238 ObjectArray<Field>* fields = klass->GetIFields(); 239 if (fields != NULL) { 240 for (int32_t i = 0; i < fields->GetLength(); i++) { 241 Field* field = fields->Get(i); 242 FieldHelper fh(field); 243 if (!fh.GetType()->IsPrimitive()) { 244 Object* value = field->GetObj(obj); 245 if (value != NULL) { 246 WalkFieldsInOrder(visited, callback, value, arg); 247 } 248 } 249 } 250 } 251} 252 253// For an unvisited object, visit it then all its children found via fields. 254static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj, 255 void* arg) { 256 if (visited->Test(obj)) { 257 return; 258 } 259 // visit the object itself 260 (*callback)(obj, arg); 261 visited->Set(obj); 262 // Walk instance fields of all objects 263 Class* klass = obj->GetClass(); 264 WalkInstanceFields(visited, callback, obj, klass, arg); 265 // Walk static fields of a Class 266 if (obj->IsClass()) { 267 ObjectArray<Field>* fields = klass->GetSFields(); 268 if (fields != NULL) { 269 for (int32_t i = 0; i < fields->GetLength(); i++) { 270 Field* field = fields->Get(i); 271 FieldHelper fh(field); 272 if (!fh.GetType()->IsPrimitive()) { 273 Object* value = field->GetObj(NULL); 274 if (value != NULL) { 275 WalkFieldsInOrder(visited, callback, value, arg); 276 } 277 } 278 } 279 } 280 } else if (obj->IsObjectArray()) { 281 // Walk elements of an object array 282 ObjectArray<Object>* obj_array = obj->AsObjectArray<Object>(); 283 int32_t length = obj_array->GetLength(); 284 for (int32_t i = 0; i < length; i++) { 285 Object* value = obj_array->Get(i); 286 if (value != NULL) { 287 WalkFieldsInOrder(visited, callback, value, arg); 288 } 289 } 290 } 291} 292 293// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap 294// bits or max during the traversal. 295void SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) { 296 UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk", 297 reinterpret_cast<byte*>(heap_begin_), 298 IndexToOffset(bitmap_size_ / kWordSize))); 299 CHECK(bitmap_begin_ != NULL); 300 CHECK(callback != NULL); 301 uintptr_t end = OffsetToIndex(heap_end_ - heap_begin_); 302 for (uintptr_t i = 0; i <= end; ++i) { 303 word w = bitmap_begin_[i]; 304 if (UNLIKELY(w != 0)) { 305 word high_bit = 1 << (kBitsPerWord - 1); 306 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 307 while (w != 0) { 308 const int shift = CLZ(w); 309 Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment); 310 WalkFieldsInOrder(visited.get(), callback, obj, arg); 311 w &= ~(high_bit >> shift); 312 } 313 } 314 } 315} 316 317} // namespace art 318