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 172dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "space_bitmap-inl.h" 18b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 19c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier#include "art_field-inl.h" 2022d5e735f403c57525fe868304c7123f0ce66399Ian Rogers#include "base/stringprintf.h" 21956af0f0cb05422e38c1d22cbef309d16b8a1a12Elliott Hughes#include "dex_file-inl.h" 2222d5e735f403c57525fe868304c7123f0ce66399Ian Rogers#include "mem_map.h" 2322d5e735f403c57525fe868304c7123f0ce66399Ian Rogers#include "mirror/object-inl.h" 243d21bdf8894e780d349c481e5c9e29fe1556051cMathieu Chartier#include "mirror/class-inl.h" 2522d5e735f403c57525fe868304c7123f0ce66399Ian Rogers#include "mirror/object_array.h" 2622d5e735f403c57525fe868304c7123f0ce66399Ian Rogers 27b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiernamespace art { 281d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 291d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 30b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 31a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 3273d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartiersize_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) { 3313735955f39b3b304c37d2b2840663c131262c18Ian Rogers const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT; 3413735955f39b3b304c37d2b2840663c131262c18Ian Rogers return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t); 3573d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier} 3673d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier 3773d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartiertemplate<size_t kAlignment> 38fac3a390a247fe33d4873773d742aad4cc100118Mathieu Chartiersize_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) { 39fac3a390a247fe33d4873773d742aad4cc100118Mathieu Chartier return bitmap_bytes * kBitsPerByte * kAlignment; 40fac3a390a247fe33d4873773d742aad4cc100118Mathieu Chartier} 41fac3a390a247fe33d4873773d742aad4cc100118Mathieu Chartier 42fac3a390a247fe33d4873773d742aad4cc100118Mathieu Chartiertemplate<size_t kAlignment> 43a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu ChartierSpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::CreateFromMemMap( 4413735955f39b3b304c37d2b2840663c131262c18Ian Rogers const std::string& name, MemMap* mem_map, uint8_t* heap_begin, size_t heap_capacity) { 4531e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier CHECK(mem_map != nullptr); 4613735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t* bitmap_begin = reinterpret_cast<uintptr_t*>(mem_map->Begin()); 4773d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 4831e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin); 4931e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier} 5031e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier 51a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 5213735955f39b3b304c37d2b2840663c131262c18Ian RogersSpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name, MemMap* mem_map, uintptr_t* bitmap_begin, 53bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier size_t bitmap_size, const void* heap_begin) 54bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size), 55bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)), 56bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier name_(name) { 57bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(bitmap_begin_ != nullptr); 58bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK_NE(bitmap_size, 0U); 59bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier} 60bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier 61bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiertemplate<size_t kAlignment> 6222d5e735f403c57525fe868304c7123f0ce66399Ian RogersSpaceBitmap<kAlignment>::~SpaceBitmap() {} 6322d5e735f403c57525fe868304c7123f0ce66399Ian Rogers 6422d5e735f403c57525fe868304c7123f0ce66399Ian Rogerstemplate<size_t kAlignment> 65a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu ChartierSpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::Create( 6613735955f39b3b304c37d2b2840663c131262c18Ian Rogers const std::string& name, uint8_t* heap_begin, size_t heap_capacity) { 67b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 6873d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 698d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers std::string error_msg; 70700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size, 715c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko PROT_READ | PROT_WRITE, false, false, 725c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko &error_msg)); 738d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers if (UNLIKELY(mem_map.get() == nullptr)) { 748d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg; 75bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier return nullptr; 76b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 7731e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity); 78b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 79b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 80a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 81a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) { 8213735955f39b3b304c37d2b2840663c131262c18Ian Rogers DCHECK(IsAligned<kBitsPerIntPtrT * kAlignment>(new_end)); 8313735955f39b3b304c37d2b2840663c131262c18Ian Rogers size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t); 84cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (new_size < bitmap_size_) { 85cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier bitmap_size_ = new_size; 86cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 87cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 88cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // should be marked. 89cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 90cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 91a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 92576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogersstd::string SpaceBitmap<kAlignment>::Dump() const { 93576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()), 94576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers reinterpret_cast<void*>(HeapLimit())); 95576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers} 96576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers 97576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogerstemplate<size_t kAlignment> 98a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::Clear() { 99c5f17732d8144491c642776b6b48c85dfadf4b52Ian Rogers if (bitmap_begin_ != nullptr) { 100c5f17732d8144491c642776b6b48c85dfadf4b52Ian Rogers mem_map_->MadviseDontNeedAndZero(); 101b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 102b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 103b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 104a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 105bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiervoid SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) { 106357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK_EQ(Size(), source_bitmap->Size()); 10713735955f39b3b304c37d2b2840663c131262c18Ian Rogers std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / sizeof(intptr_t), Begin()); 108357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 109357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 110a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 111bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiervoid SpaceBitmap<kAlignment>::Walk(ObjectCallback* callback, void* arg) { 1122cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier CHECK(bitmap_begin_ != nullptr); 1132cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier CHECK(callback != nullptr); 114357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 115357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 11613735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t* bitmap_begin = bitmap_begin_; 117b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (uintptr_t i = 0; i <= end; ++i) { 11813735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t w = bitmap_begin[i]; 119357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (w != 0) { 120b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 121357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 122cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(w); 1232dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 124b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 12513735955f39b3b304c37d2b2840663c131262c18Ian Rogers w ^= (static_cast<uintptr_t>(1)) << shift; 126357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (w != 0); 127b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 128b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 129b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 130b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 131a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 132a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap, 133bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier const SpaceBitmap<kAlignment>& mark_bitmap, 134bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier uintptr_t sweep_begin, uintptr_t sweep_end, 135bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier SpaceBitmap::SweepCallback* callback, void* arg) { 136bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(live_bitmap.bitmap_begin_ != nullptr); 137bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(mark_bitmap.bitmap_begin_ != nullptr); 138b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 139b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 1402cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier CHECK(callback != nullptr); 141b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_LE(sweep_begin, sweep_end); 142b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 143357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 144357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (sweep_end <= sweep_begin) { 145b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 146b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 147357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1482dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 14913735955f39b3b304c37d2b2840663c131262c18Ian Rogers constexpr size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT; 150262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#ifdef __LP64__ 151262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe // Heap-allocate for smaller stack frame. 152262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe std::unique_ptr<mirror::Object*[]> pointer_buf_ptr(new mirror::Object*[buffer_size]); 153262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe mirror::Object** pointer_buf = pointer_buf_ptr.get(); 154262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#else 155262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe // Stack-allocate buffer as it's small enough. 1562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* pointer_buf[buffer_size]; 157262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#endif 1582dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object** pb = &pointer_buf[0]; 159262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe 160b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 161357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 16213735955f39b3b304c37d2b2840663c131262c18Ian Rogers CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t)); 16313735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t* live = live_bitmap.bitmap_begin_; 16413735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t* mark = mark_bitmap.bitmap_begin_; 165b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (size_t i = start; i <= end; i++) { 16613735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t garbage = live[i] & ~mark[i]; 167b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(garbage != 0)) { 168b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 169357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 170cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(garbage); 17113735955f39b3b304c37d2b2840663c131262c18Ian Rogers garbage ^= (static_cast<uintptr_t>(1)) << shift; 1722dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 173357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (garbage != 0); 174b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Make sure that there are always enough slots available for an 175b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // entire word of one bits. 17613735955f39b3b304c37d2b2840663c131262c18Ian Rogers if (pb >= &pointer_buf[buffer_size - kBitsPerIntPtrT]) { 177b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 178b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier pb = &pointer_buf[0]; 179b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 180b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 181b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 182b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (pb > &pointer_buf[0]) { 183b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 184b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 185b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 186b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 187a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 188a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::WalkInstanceFields(SpaceBitmap<kAlignment>* visited, 189a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ObjectCallback* callback, mirror::Object* obj, 190a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier mirror::Class* klass, void* arg) 191b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 192b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Visit fields of parent classes first. 1932dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* super = klass->GetSuperClass(); 1942cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier if (super != nullptr) { 195b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, super, arg); 196b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 197b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields 198c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier auto* fields = klass->GetIFields(); 199c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier for (size_t i = 0, count = klass->NumInstanceFields(); i < count; ++i) { 200c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier ArtField* field = &fields[i]; 201c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier if (!field->IsPrimitiveType()) { 202c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier mirror::Object* value = field->GetObj(obj); 203c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier if (value != nullptr) { 204c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 205b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 206b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 207b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 208b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 209b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 210a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 211a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::WalkFieldsInOrder(SpaceBitmap<kAlignment>* visited, 212bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier ObjectCallback* callback, mirror::Object* obj, 213bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier void* arg) { 214b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (visited->Test(obj)) { 215b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 216b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 217b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // visit the object itself 218b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 219b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier visited->Set(obj); 220b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields of all objects 2212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass = obj->GetClass(); 222b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, klass, arg); 223b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk static fields of a Class 224b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (obj->IsClass()) { 225c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier auto* sfields = klass->GetSFields(); 226c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier for (size_t i = 0, count = klass->NumStaticFields(); i < count; ++i) { 227c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier ArtField* field = &sfields[i]; 228c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier if (!field->IsPrimitiveType()) { 229c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier mirror::Object* value = field->GetObj(nullptr); 230c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier if (value != nullptr) { 231c785344b87221f5e4e6473e5b762e4e61fe65dcfMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 232b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 233b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 234b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 235b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } else if (obj->IsObjectArray()) { 236b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk elements of an object array 2372dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 238b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int32_t length = obj_array->GetLength(); 239b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < length; i++) { 2402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = obj_array->Get(i); 2412cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier if (value != nullptr) { 242b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 243b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 244b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 245b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 246b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 247b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 248a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 249a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::InOrderWalk(ObjectCallback* callback, void* arg) { 250700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<SpaceBitmap<kAlignment>> visited( 25113735955f39b3b304c37d2b2840663c131262c18Ian Rogers Create("bitmap for in-order walk", reinterpret_cast<uint8_t*>(heap_begin_), 25213735955f39b3b304c37d2b2840663c131262c18Ian Rogers IndexToOffset(bitmap_size_ / sizeof(intptr_t)))); 253a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier CHECK(bitmap_begin_ != nullptr); 254a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier CHECK(callback != nullptr); 25513735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t end = Size() / sizeof(intptr_t); 256357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (uintptr_t i = 0; i < end; ++i) { 257cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Need uint for unsigned shift. 25813735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t w = bitmap_begin_[i]; 259b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(w != 0)) { 260b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 261b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier while (w != 0) { 262cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(w); 2632dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 264b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited.get(), callback, obj, arg); 26513735955f39b3b304c37d2b2840663c131262c18Ian Rogers w ^= (static_cast<uintptr_t>(1)) << shift; 266b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 267b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 268b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 269b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 270b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 271a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate class SpaceBitmap<kObjectAlignment>; 272a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate class SpaceBitmap<kPageSize>; 273a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier 2741d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 2751d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 276b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 277