space_bitmap.cc revision c5f17732d8144491c642776b6b48c85dfadf4b52
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 19b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartiernamespace art { 201d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 211d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 22b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 23a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 2473d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartiersize_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) { 2573d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerWord; 2673d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * kWordSize; 2773d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier} 2873d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier 2973d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartiertemplate<size_t kAlignment> 30a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu ChartierSpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::CreateFromMemMap( 31a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier const std::string& name, MemMap* mem_map, byte* heap_begin, size_t heap_capacity) { 3231e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier CHECK(mem_map != nullptr); 33cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword* bitmap_begin = reinterpret_cast<uword*>(mem_map->Begin()); 3473d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 3531e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin); 3631e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier} 3731e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier 38a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 39bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu ChartierSpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name, MemMap* mem_map, uword* bitmap_begin, 40bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier size_t bitmap_size, const void* heap_begin) 41bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size), 42bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)), 43bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier name_(name) { 44bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(bitmap_begin_ != nullptr); 45bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK_NE(bitmap_size, 0U); 46bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier} 47bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier 48bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiertemplate<size_t kAlignment> 49a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu ChartierSpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::Create( 50a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier const std::string& name, byte* heap_begin, size_t heap_capacity) { 51b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. 5273d1e17b3afc7d5e56184f90bf819dc64956448aMathieu Chartier const size_t bitmap_size = ComputeBitmapSize(heap_capacity); 538d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers std::string error_msg; 54700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size, 55ef7d42fca18c16fbaf103822ad16f23246e2905dIan Rogers PROT_READ | PROT_WRITE, false, &error_msg)); 568d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers if (UNLIKELY(mem_map.get() == nullptr)) { 578d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg; 58bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier return nullptr; 59b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 6031e8925781c2302f1d1a9b39e216ba415bfe0d7eMathieu Chartier return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity); 61b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 62b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 63a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 64a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) { 65dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end)); 66dcf8d7283bd51714f3faa55b631ae4103dc98b51Mathieu Chartier size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize; 67cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (new_size < bitmap_size_) { 68cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier bitmap_size_ = new_size; 69cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 70cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity 71cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // should be marked. 72cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 73cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 74a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 75576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogersstd::string SpaceBitmap<kAlignment>::Dump() const { 76576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()), 77576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers reinterpret_cast<void*>(HeapLimit())); 78576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers} 79576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogers 80576ca0cd692c0b6ae70e776de91015b8ff000a08Ian Rogerstemplate<size_t kAlignment> 81a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::Clear() { 82c5f17732d8144491c642776b6b48c85dfadf4b52Ian Rogers if (bitmap_begin_ != nullptr) { 83c5f17732d8144491c642776b6b48c85dfadf4b52Ian Rogers mem_map_->MadviseDontNeedAndZero(); 84b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 85b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 86b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 87a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 88bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiervoid SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) { 89357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK_EQ(Size(), source_bitmap->Size()); 90357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin()); 91357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 92357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 93a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 94bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiervoid SpaceBitmap<kAlignment>::Walk(ObjectCallback* 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); 99cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword* bitmap_begin = bitmap_begin_; 100b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (uintptr_t i = 0; i <= end; ++i) { 101cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword w = bitmap_begin[i]; 102357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (w != 0) { 103b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 104357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 105cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(w); 1062dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 107b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 108cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe w ^= (static_cast<uword>(1)) << shift; 109357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (w != 0); 110b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 111b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 112b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 113b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 114a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 115a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap, 116bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier const SpaceBitmap<kAlignment>& mark_bitmap, 117bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier uintptr_t sweep_begin, uintptr_t sweep_end, 118bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier SpaceBitmap::SweepCallback* callback, void* arg) { 119bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(live_bitmap.bitmap_begin_ != nullptr); 120bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier CHECK(mark_bitmap.bitmap_begin_ != nullptr); 121b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_); 122b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_); 123b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK(callback != NULL); 124b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_LE(sweep_begin, sweep_end); 125b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier CHECK_GE(sweep_begin, live_bitmap.heap_begin_); 126357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 127357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (sweep_end <= sweep_begin) { 128b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 129b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 130357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1312dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**? 132262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe constexpr size_t buffer_size = kWordSize * kBitsPerWord; 133262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#ifdef __LP64__ 134262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe // Heap-allocate for smaller stack frame. 135262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe std::unique_ptr<mirror::Object*[]> pointer_buf_ptr(new mirror::Object*[buffer_size]); 136262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe mirror::Object** pointer_buf = pointer_buf_ptr.get(); 137262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#else 138262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe // Stack-allocate buffer as it's small enough. 1392dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* pointer_buf[buffer_size]; 140262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe#endif 1412dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object** pb = &pointer_buf[0]; 142262a0a36ee5f553880365fecf0be1a188526ca69Andreas Gampe 143b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_); 144357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1); 145357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK_LT(end, live_bitmap.Size() / kWordSize); 146cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword* live = live_bitmap.bitmap_begin_; 147cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword* mark = mark_bitmap.bitmap_begin_; 148b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (size_t i = start; i <= end; i++) { 149cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword garbage = live[i] & ~mark[i]; 150b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(garbage != 0)) { 151b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_; 152357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier do { 153cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(garbage); 154cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe garbage ^= (static_cast<uword>(1)) << shift; 1552dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 156357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } while (garbage != 0); 157b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Make sure that there are always enough slots available for an 158b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // entire word of one bits. 159357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) { 160b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 161b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier pb = &pointer_buf[0]; 162b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 163b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 164b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 165b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (pb > &pointer_buf[0]) { 166b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg); 167b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 168b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 169b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 170a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 171a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::WalkInstanceFields(SpaceBitmap<kAlignment>* visited, 172a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ObjectCallback* callback, mirror::Object* obj, 173a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier mirror::Class* klass, void* arg) 174b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 175b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Visit fields of parent classes first. 1762dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* super = klass->GetSuperClass(); 177b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (super != NULL) { 178b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, super, arg); 179b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 180b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields 181ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetIFields(); 182b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 183b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 184ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 18561c5ebc6aee2cac1c363de6fbdac25ada1697fdbMathieu Chartier if (!field->IsPrimitiveType()) { 1862dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(obj); 187b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 18861c5ebc6aee2cac1c363de6fbdac25ada1697fdbMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 189b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 190b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 191b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 192b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 193b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 194b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 195a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 196a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::WalkFieldsInOrder(SpaceBitmap<kAlignment>* visited, 197bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier ObjectCallback* callback, mirror::Object* obj, 198bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier void* arg) { 199b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (visited->Test(obj)) { 200b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier return; 201b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 202b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // visit the object itself 203b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier (*callback)(obj, arg); 204b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier visited->Set(obj); 205b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk instance fields of all objects 2062dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Class* klass = obj->GetClass(); 207b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkInstanceFields(visited, callback, obj, klass, arg); 208b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk static fields of a Class 209b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (obj->IsClass()) { 210ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ObjectArray<mirror::ArtField>* fields = klass->GetSFields(); 211b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (fields != NULL) { 212b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); i++) { 213ea46f950e7a51585db293cd7f047de190a482414Brian Carlstrom mirror::ArtField* field = fields->Get(i); 21461c5ebc6aee2cac1c363de6fbdac25ada1697fdbMathieu Chartier if (!field->IsPrimitiveType()) { 2152dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = field->GetObj(NULL); 216b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 217b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 218b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 219b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 220b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 221b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 222b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } else if (obj->IsObjectArray()) { 223b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Walk elements of an object array 2242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>(); 225b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier int32_t length = obj_array->GetLength(); 226b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < length; i++) { 2272dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* value = obj_array->Get(i); 228b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (value != NULL) { 229b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited, callback, value, arg); 230b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 231b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 232b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 233b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 234b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 235a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 236a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiervoid SpaceBitmap<kAlignment>::InOrderWalk(ObjectCallback* callback, void* arg) { 237700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<SpaceBitmap<kAlignment>> visited( 238a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier Create("bitmap for in-order walk", reinterpret_cast<byte*>(heap_begin_), 239a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier IndexToOffset(bitmap_size_ / kWordSize))); 240a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier CHECK(bitmap_begin_ != nullptr); 241a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier CHECK(callback != nullptr); 242357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = Size() / kWordSize; 243357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (uintptr_t i = 0; i < end; ++i) { 244cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Need uint for unsigned shift. 245cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe uword w = bitmap_begin_[i]; 246b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (UNLIKELY(w != 0)) { 247b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 248b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier while (w != 0) { 249cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(w); 2502dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 251b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier WalkFieldsInOrder(visited.get(), callback, obj, arg); 252cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe w ^= (static_cast<uword>(1)) << shift; 253b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 254b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 255b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 256b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} 257b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 258a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate class SpaceBitmap<kObjectAlignment>; 259a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate class SpaceBitmap<kPageSize>; 260a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier 2611d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 2621d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 263b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier} // namespace art 264