space_bitmap.cc revision 2dd0e2cea360bc9206eb88ecc40d259e796c239d
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 1907ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 202dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/class-inl.h" 212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/field-inl.h" 222dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object-inl.h" 232dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object_array-inl.h" 242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "space_bitmap-inl.h" 25b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier#include "UniquePtr.h" 26b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier#include "utils.h" 27b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 28b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiernamespace art { 29b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 30357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierstd::string SpaceBitmap::GetName() const { 31357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return name_; 32357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 33357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 34357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid SpaceBitmap::SetName(const std::string& name) { 35357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier name_ = name; 36357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 37357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 38e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::Walk(SpaceBitmap::Callback* callback, void* arg) { 39e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier for (Objects::iterator it = contained_.begin(); it != contained_.end(); ++it) { 402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers callback(const_cast<mirror::Object*>(*it), arg); 41e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 42e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 43e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 44b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu ChartierSpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) { 45b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(heap_begin != NULL); 46b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 47b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize; 48b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE)); 49b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (mem_map.get() == NULL) { 50b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(ERROR) << "Failed to allocate bitmap " << name; 51b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return NULL; 52b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 53b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin()); 54b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return new SpaceBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin); 55b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 56b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 57b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Clean up any resources associated with the bitmap. 587469ebf3888b8037421cb6834f37f946646265ecMathieu ChartierSpaceBitmap::~SpaceBitmap() { 597469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 607469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 61b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 62dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartiervoid SpaceBitmap::SetHeapLimit(uintptr_t new_end) { 63dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 64dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 65cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (new_size < bitmap_size_) { 66cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier bitmap_size_ = new_size; 67cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 68cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 69cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // should be marked. 70cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // TODO: Fix this code is, it broken and causes rare heap corruption! 71cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // mem_map_->Trim(reinterpret_cast<byte*>(heap_begin_ + bitmap_size_)); 72cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 73cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 74b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Fill the bitmap with zeroes. Returns the bitmap's memory to the 75b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// system as a side-effect. 76b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Clear() { 77b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (bitmap_begin_ != NULL) { 78b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // This returns the memory to the system. Successive page faults 79b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // will return zeroed memory. 80b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED); 81b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (result == -1) { 827469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier PLOG(FATAL) << "madvise failed"; 83b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 84b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 85b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 86b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 87357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid SpaceBitmap::CopyFrom(SpaceBitmap* source_bitmap) { 88357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK_EQ(Size(), source_bitmap->Size()); 89357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 90357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 91357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 92b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits in address order. The callback is not permitted to 93b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// change the bitmap bits or max during the traversal. 94b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) { 95b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 96b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 97357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 98357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 99357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word* bitmap_begin = bitmap_begin_; 100b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (uintptr_t i = 0; i <= end; ++i) { 101357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier word w = bitmap_begin[i]; 102357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (w != 0) { 103b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 104357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 105dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 1062dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 107b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 108dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 109357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (w != 0); 110b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 111b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 112b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 113b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 114b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk through the bitmaps in increasing address order, and find the 115b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// object pointers that correspond to garbage objects. Call 116b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// <callback> zero or more times with lists of these object pointers. 117b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// 118b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// The callback is not permitted to increase the max of either bitmap. 119b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap, 120b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const SpaceBitmap& mark_bitmap, 121b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t sweep_begin, uintptr_t sweep_end, 122b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier SpaceBitmap::SweepCallback* callback, void* arg) { 123b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(live_bitmap.bitmap_begin_ != NULL); 124b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(mark_bitmap.bitmap_begin_ != NULL); 125b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 126b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 127b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 128b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_LE(sweep_begin, sweep_end); 129b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 130357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 131357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (sweep_end <= sweep_begin) { 132b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 133b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 134357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1352dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 136357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const size_t buffer_size = kWordSize * kBitsPerWord; 1372dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* pointer_buf[buffer_size]; 1382dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object** pb = &pointer_buf[0]; 139b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 140357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 141357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK_LT(end, live_bitmap.Size() / kWordSize); 142b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* live = live_bitmap.bitmap_begin_; 143b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word* mark = mark_bitmap.bitmap_begin_; 144b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (size_t i = start; i <= end; i++) { 145b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word garbage = live[i] & ~mark[i]; 146b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(garbage != 0)) { 147b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 148357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 149dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(garbage); 150dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift; 1512dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 152357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (garbage != 0); 153b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Make sure that there are always enough slots available for an 154b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // entire word of one bits. 155357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 156b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 157b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier pb = &pointer_buf[0]; 158b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 159b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 160b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 161b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (pb > &pointer_buf[0]) { 162b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 163b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 164b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 165b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 166b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 167b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 168b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Support needed for in order traversal 1692dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object.h" 170b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier#include "object_utils.h" 171b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 172b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiernamespace art { 173b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 1742dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 175b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier void* arg); 176b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 177b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Walk instance fields of the given Class. Separate function to allow recursion on the super 178b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// class. 1792dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 1802dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass, void* arg) 181b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 182b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Visit fields of parent classes first. 1832dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* super = klass->GetSuperClass(); 184b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (super != NULL) { 185b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, super, arg); 186b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 187b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields 1882dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Field>* fields = klass->GetIFields(); 189b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 190b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 1912dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Field* field = fields->Get(i); 192b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 19366f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 1942dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(obj); 195b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 196b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 197b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 198b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 199b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 200b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 201b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 202b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 203b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// For an unvisited object, visit it then all its children found via fields. 2042dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersstatic void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj, 20500f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void* arg) 206b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 207b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (visited->Test(obj)) { 208b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 209b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 210b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // visit the object itself 211b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 212b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier visited->Set(obj); 213b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields of all objects 2142dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass = obj->GetClass(); 215b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, klass, arg); 216b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk static fields of a Class 217b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (obj->IsClass()) { 2182dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Field>* fields = klass->GetSFields(); 219b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 220b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 2212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Field* field = fields->Get(i); 222b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier FieldHelper fh(field); 22366f19258f9728d4ffe026074d8fd429d639802faMathieu Chartier if (!fh.IsPrimitiveType()) { 2242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(NULL); 225b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 226b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 227b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 228b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 229b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 230b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 231b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } else if (obj->IsObjectArray()) { 232b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk elements of an object array 2332dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 234b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int32_t length = obj_array->GetLength(); 235b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < length; i++) { 2362dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = obj_array->Get(i); 237b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 238b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 239b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 240b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 241b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 242b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 243b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 244b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap 245b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier// bits or max during the traversal. 246b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiervoid SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) { 247b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk", 248b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier reinterpret_cast<byte*>(heap_begin_), 249b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier IndexToOffset(bitmap_size_ / kWordSize))); 250b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(bitmap_begin_ != NULL); 251b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 252357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = Size() / kWordSize; 253357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (uintptr_t i = 0; i < end; ++i) { 254b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier word w = bitmap_begin_[i]; 255b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(w != 0)) { 256b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 257b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier while (w != 0) { 258dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier const size_t shift = CLZ(w); 2592dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 260b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited.get(), callback, obj, arg); 261dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 262b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 263b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 264b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 265b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 266b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 267e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartierstd::string SpaceSetMap::GetName() const { 268e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier return name_; 269e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 270e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 271e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::SetName(const std::string& name) { 272e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier name_ = name; 273e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 274e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 275e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu ChartierSpaceSetMap::SpaceSetMap(const std::string& name) : name_(name) { 276e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 277e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 278e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 279e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid SpaceSetMap::CopyFrom(const SpaceSetMap& space_set) { 280e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier contained_ = space_set.contained_; 281e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 282e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 283357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierstd::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap) { 284357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return stream 285357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << bitmap.GetName() << "[" 286357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 287357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 288357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier << "]"; 289357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 290357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 291b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 292