space_bitmap.cc revision ea46f950e7a51585db293cd7f047de190a482414
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 1707ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 184f6ad8ab428038129b2d0d6c40b7fd625cca15e1Ian Rogers#include "dex_file-inl.h" 191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "heap_bitmap.h" 20ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom#include "mirror/art_field-inl.h" 212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/class-inl.h" 222dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object-inl.h" 232dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object_array-inl.h" 241d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "object_utils.h" 252dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "space_bitmap-inl.h" 26b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier#include "UniquePtr.h" 27b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier#include "utils.h" 28b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 29b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiernamespace art { 301d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 311d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 32b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 33357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierstd::string SpaceBitmap::GetName() const { 34357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return name_; 35357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 36357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 37357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid SpaceBitmap::SetName(const std::string& name) { 38357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier name_ = name; 39357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 40357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 411d54e73444e017d3a65234e0f193846f3e27472bIan Rogersstd::string SpaceBitmap::Dump() const { 421d54e73444e017d3a65234e0f193846f3e27472bIan Rogers return StringPrintf("%s: %p-%p", name_.c_str(), 431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers reinterpret_cast<void*>(HeapBegin()), 441d54e73444e017d3a65234e0f193846f3e27472bIan Rogers reinterpret_cast<void*>(HeapLimit())); 451d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} 461d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 47e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::Walk(SpaceBitmap::Callback* callback, void* arg) { 48e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier for (Objects::iterator it = contained_.begin(); it != contained_.end(); ++it) { 492dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers callback(const_cast<mirror::Object*>(*it), arg); 50e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 51e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 52e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 53b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu ChartierSpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) { 54b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(heap_begin != NULL); 55b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 56b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 57b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE)); 58b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (mem_map.get() == NULL) { 59b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(ERROR) << "Failed to allocate bitmap " << name; 60b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return NULL; 61b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 62b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin()); 63b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return new SpaceBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin); 64b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 65b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 66b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Clean up any resources associated with the bitmap. 670cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromSpaceBitmap::~SpaceBitmap() {} 68b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 69dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartiervoid SpaceBitmap::SetHeapLimit(uintptr_t new_end) { 70dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 71dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 72cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (new_size < bitmap_size_) { 73cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier bitmap_size_ = new_size; 74cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 75cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 76cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // should be marked. 77cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // TODO: Fix this code is, it broken and causes rare heap corruption! 78cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // mem_map_->Trim(reinterpret_cast<byte*>(heap_begin_ + bitmap_size_)); 79cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 80cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 81b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Clear() { 82b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (bitmap_begin_ != NULL) { 83b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // This returns the memory to the system. Successive page faults 84b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // will return zeroed memory. 85b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 86b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (result == -1) { 877469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier PLOG(FATAL) << "madvise failed"; 88b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 89b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 90b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 91b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 92357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid SpaceBitmap::CopyFrom(SpaceBitmap* source_bitmap) { 93357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK_EQ(Size(), source_bitmap->Size()); 94357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 95357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 96357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 97b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits in address order. The callback is not permitted to 98b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// change the bitmap bits or max during the traversal. 99b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) { 100b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 101b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 102357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 103357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 104357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word* bitmap_begin = bitmap_begin_; 105b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (uintptr_t i = 0; i <= end; ++i) { 106357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word w = bitmap_begin[i]; 107357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (w != 0) { 108b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 109357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 110dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 1112dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 112b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 113dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 114357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (w != 0); 115b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 116b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 117b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 118b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 119b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk through the bitmaps in increasing address order, and find the 120b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// object pointers that correspond to garbage objects. Call 121b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// <callback> zero or more times with lists of these object pointers. 122b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// 123b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// The callback is not permitted to increase the max of either bitmap. 124b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap, 125b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const SpaceBitmap& mark_bitmap, 126b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t sweep_begin, uintptr_t sweep_end, 127b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier SpaceBitmap::SweepCallback* callback, void* arg) { 128b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(live_bitmap.bitmap_begin_ != NULL); 129b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(mark_bitmap.bitmap_begin_ != NULL); 130b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 131b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 132b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 133b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_LE(sweep_begin, sweep_end); 134b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 135357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 136357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (sweep_end <= sweep_begin) { 137b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 138b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 139357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 141357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const size_t buffer_size = kWordSize * kBitsPerWord; 1422dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* pointer_buf[buffer_size]; 1432dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object** pb = &pointer_buf[0]; 144b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 145357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 146357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK_LT(end, live_bitmap.Size() / kWordSize); 147b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* live = live_bitmap.bitmap_begin_; 148b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* mark = mark_bitmap.bitmap_begin_; 149b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (size_t i = start; i <= end; i++) { 150b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word garbage = live[i] & ~mark[i]; 151b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(garbage != 0)) { 152b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 153357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 154dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(garbage); 155dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift; 1562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 157357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (garbage != 0); 158b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Make sure that there are always enough slots available for an 159b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // entire word of one bits. 160357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 161b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 162b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier pb = &pointer_buf[0]; 163b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 164b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 165b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 166b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (pb > &pointer_buf[0]) { 167b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 168b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 169b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 170b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 1712dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 172b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier void* arg); 173b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 174b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk instance fields of the given Class. Separate function to allow recursion on the super 175b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// class. 1762dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 1772dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass, void* arg) 178b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 179b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Visit fields of parent classes first. 1802dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* super = klass->GetSuperClass(); 181b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (super != NULL) { 182b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, super, arg); 183b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 184b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields 185ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetIFields(); 186b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 187b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 188ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 189b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 19066f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 1912dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(obj); 192b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 193b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 194b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 195b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 196b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 197b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 198b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 199b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 200b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// For an unvisited object, visit it then all its children found via fields. 2012dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 20200f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void* arg) 203b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 204b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (visited->Test(obj)) { 205b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 206b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 207b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // visit the object itself 208b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 209b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier visited->Set(obj); 210b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields of all objects 2112dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass = obj->GetClass(); 212b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, klass, arg); 213b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk static fields of a Class 214b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (obj->IsClass()) { 215ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetSFields(); 216b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 217b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 218ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 219b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 22066f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 2212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(NULL); 222b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 223b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 224b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 225b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 226b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 227b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 228b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } else if (obj->IsObjectArray()) { 229b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk elements of an object array 2302dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 231b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int32_t length = obj_array->GetLength(); 232b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < length; i++) { 2332dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = obj_array->Get(i); 234b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 235b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 236b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 237b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 238b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 239b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 240b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 241b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap 242b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// bits or max during the traversal. 243b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) { 244b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk", 245b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier reinterpret_cast<byte*>(heap_begin_), 246b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier IndexToOffset(bitmap_size_ / kWordSize))); 247b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 248b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 249357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = Size() / kWordSize; 250357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (uintptr_t i = 0; i < end; ++i) { 251b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word w = bitmap_begin_[i]; 252b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(w != 0)) { 253b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 254b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier while (w != 0) { 255dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 2562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 257b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited.get(), callback, obj, arg); 258dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 259b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 260b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 261b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 262b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 263b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 264e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartierstd::string SpaceSetMap::GetName() const { 265e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier return name_; 266e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 267e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 268e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::SetName(const std::string& name) { 269e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier name_ = name; 270e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 271e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 272e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::CopyFrom(const SpaceSetMap& space_set) { 273e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier contained_ = space_set.contained_; 274e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 275e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 276357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierstd::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap) { 277357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return stream 278357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << bitmap.GetName() << "[" 279357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 280357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 281357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "]"; 2821d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} 283357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 2841d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 2851d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 286b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 287