space_bitmap.cc revision ef7d42fca18c16fbaf103822ad16f23246e2905d
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 47db7f37d57b6ac83abe6815d0cd5c50701b6be821Mathieu Chartiervoid ObjectSet::Walk(SpaceBitmap::Callback* callback, void* arg) { 4831e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier for (const mirror::Object* obj : contained_) { 4931e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier callback(const_cast<mirror::Object*>(obj), arg); 50e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 51e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 52e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 5331e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu ChartierSpaceBitmap* SpaceBitmap::CreateFromMemMap(const std::string& name, MemMap* mem_map, 5431e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier byte* heap_begin, size_t heap_capacity) { 5531e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier CHECK(mem_map != nullptr); 5631e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin()); 5731e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 5831e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin); 5931e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier} 6031e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier 61b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu ChartierSpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) { 62b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(heap_begin != NULL); 63b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 64b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 658d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers std::string error_msg; 668d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, 67ef7d42fca18c16fbaf103822ad16f23246e2905dIan Rogers PROT_READ | PROT_WRITE, false, &error_msg)); 688d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers if (UNLIKELY(mem_map.get() == nullptr)) { 698d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg; 70b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return NULL; 71b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 7231e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity); 73b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 74b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 75b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Clean up any resources associated with the bitmap. 760cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromSpaceBitmap::~SpaceBitmap() {} 77b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 78dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartiervoid SpaceBitmap::SetHeapLimit(uintptr_t new_end) { 79dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 80dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 81cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (new_size < bitmap_size_) { 82cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier bitmap_size_ = new_size; 83cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 84cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 85cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // should be marked. 86cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 87cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 88b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Clear() { 89b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (bitmap_begin_ != NULL) { 9031e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier // This returns the memory to the system. Successive page faults will return zeroed memory. 91b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 92b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (result == -1) { 937469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier PLOG(FATAL) << "madvise failed"; 94b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 95b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 96b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 97b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 98357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid SpaceBitmap::CopyFrom(SpaceBitmap* source_bitmap) { 99357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK_EQ(Size(), source_bitmap->Size()); 100357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 101357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 102357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 103b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits in address order. The callback is not permitted to 104b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// change the bitmap bits or max during the traversal. 105b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) { 106b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 107b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 108357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 109357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 110357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word* bitmap_begin = bitmap_begin_; 111b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (uintptr_t i = 0; i <= end; ++i) { 112357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word w = bitmap_begin[i]; 113357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (w != 0) { 114b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 115357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 116dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 1172dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 118b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 119dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 120357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (w != 0); 121b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 122b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 123b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 124b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 125b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk through the bitmaps in increasing address order, and find the 126b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// object pointers that correspond to garbage objects. Call 127b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// <callback> zero or more times with lists of these object pointers. 128b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// 129b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// The callback is not permitted to increase the max of either bitmap. 130b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap, 131a1602f28c0e3127ad511712d4b08db89737ae901Mathieu Chartier const SpaceBitmap& mark_bitmap, 132a1602f28c0e3127ad511712d4b08db89737ae901Mathieu Chartier uintptr_t sweep_begin, uintptr_t sweep_end, 133a1602f28c0e3127ad511712d4b08db89737ae901Mathieu Chartier SpaceBitmap::SweepCallback* callback, void* arg) { 134b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(live_bitmap.bitmap_begin_ != NULL); 135b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(mark_bitmap.bitmap_begin_ != NULL); 136b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 137b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 138b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 139b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_LE(sweep_begin, sweep_end); 140b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 141357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 142357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (sweep_end <= sweep_begin) { 143b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 144b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 145357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1462dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 147357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const size_t buffer_size = kWordSize * kBitsPerWord; 1482dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* pointer_buf[buffer_size]; 1492dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object** pb = &pointer_buf[0]; 150b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 151357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 152357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK_LT(end, live_bitmap.Size() / kWordSize); 153b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* live = live_bitmap.bitmap_begin_; 154b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* mark = mark_bitmap.bitmap_begin_; 155b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (size_t i = start; i <= end; i++) { 156b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word garbage = live[i] & ~mark[i]; 157b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(garbage != 0)) { 158b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 159357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 160dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(garbage); 161dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift; 1622dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 163357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (garbage != 0); 164b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Make sure that there are always enough slots available for an 165b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // entire word of one bits. 166357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 167b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 168b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier pb = &pointer_buf[0]; 169b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 170b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 171b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 172b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (pb > &pointer_buf[0]) { 173b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 174b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 175b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 176b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 1772dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 178b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier void* arg); 179b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 180b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk instance fields of the given Class. Separate function to allow recursion on the super 181b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// class. 1822dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 1832dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass, void* arg) 184b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 185b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Visit fields of parent classes first. 1862dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* super = klass->GetSuperClass(); 187b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (super != NULL) { 188b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, super, arg); 189b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 190b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields 191ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetIFields(); 192b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 193b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 194ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 195b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 19666f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 1972dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(obj); 198b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 199b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 200b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 201b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 202b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 203b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 204b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 205b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 206b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// For an unvisited object, visit it then all its children found via fields. 2072dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 20800f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void* arg) 209b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 210b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (visited->Test(obj)) { 211b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 212b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 213b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // visit the object itself 214b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 215b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier visited->Set(obj); 216b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields of all objects 2172dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass = obj->GetClass(); 218b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, klass, arg); 219b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk static fields of a Class 220b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (obj->IsClass()) { 221ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetSFields(); 222b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 223b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 224ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 225b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 22666f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 2272dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(NULL); 228b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 229b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 230b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 231b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 232b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 233b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 234b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } else if (obj->IsObjectArray()) { 235b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk elements of an object array 2362dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 237b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int32_t length = obj_array->GetLength(); 238b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < length; i++) { 2392dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = obj_array->Get(i); 240b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 241b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 242b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 243b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 244b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 245b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 246b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 247b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap 248b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// bits or max during the traversal. 249b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) { 250b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk", 251b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier reinterpret_cast<byte*>(heap_begin_), 252b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier IndexToOffset(bitmap_size_ / kWordSize))); 253b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 254b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 255357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = Size() / kWordSize; 256357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (uintptr_t i = 0; i < end; ++i) { 257b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word w = bitmap_begin_[i]; 258b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(w != 0)) { 259b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 260b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier while (w != 0) { 261dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 2622dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 263b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited.get(), callback, obj, arg); 264dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 265b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 266b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 267b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 268b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 269b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 270357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierstd::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap) { 271357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return stream 272357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << bitmap.GetName() << "[" 273357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 274357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 275357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "]"; 2761d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} 277357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 2781d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 2791d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 280b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 281