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