12dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers/* 22dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * Copyright (C) 2008 The Android Open Source Project 32dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * 42dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * Licensed under the Apache License, Version 2.0 (the "License"); 52dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * you may not use this file except in compliance with the License. 62dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * You may obtain a copy of the License at 72dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * 82dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * http://www.apache.org/licenses/LICENSE-2.0 92dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * 102dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * Unless required by applicable law or agreed to in writing, software 112dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * distributed under the License is distributed on an "AS IS" BASIS, 122dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * See the License for the specific language governing permissions and 142dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers * limitations under the License. 152dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers */ 162dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 192dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 20a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier#include "space_bitmap.h" 21a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier 22700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers#include <memory> 23700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers 24be2a1df15a31a5223ee9af3015a00c31d2ad2e10Ian Rogers#include "atomic.h" 2580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include "base/bit_utils.h" 262dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "base/logging.h" 272dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 282dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersnamespace art { 291d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 301d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 312dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 32a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 33a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartierinline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) { 342dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 352dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 362dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 372dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t index = OffsetToIndex(offset); 3813735955f39b3b304c37d2b2840663c131262c18Ian Rogers const uintptr_t mask = OffsetToMask(offset); 3913735955f39b3b304c37d2b2840663c131262c18Ian Rogers Atomic<uintptr_t>* atomic_entry = reinterpret_cast<Atomic<uintptr_t>*>(&bitmap_begin_[index]); 4013735955f39b3b304c37d2b2840663c131262c18Ian Rogers DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_; 4113735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t old_word; 422dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers do { 43be2a1df15a31a5223ee9af3015a00c31d2ad2e10Ian Rogers old_word = atomic_entry->LoadRelaxed(); 442dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Fast path: The bit is already set. 452dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if ((old_word & mask) != 0) { 46ef7d42fca18c16fbaf103822ad16f23246e2905dIan Rogers DCHECK(Test(obj)); 472dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return true; 482dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 49fed3e2fd4919b58f8e4f8cbc317ee101f3b9af49Hiroshi Yamauchi } while (!atomic_entry->CompareExchangeWeakRelaxed(old_word, old_word | mask)); 50ef7d42fca18c16fbaf103822ad16f23246e2905dIan Rogers DCHECK(Test(obj)); 512dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return false; 522dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 532dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 54a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 55a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartierinline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const { 562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 572dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK(HasAddress(obj)) << obj; 582cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier DCHECK(bitmap_begin_ != nullptr); 592dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 602dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 612dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0; 622dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 632dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 64a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> template<typename Visitor> 65e9ea70bb806f7c1dcd57efb6f48f1d6329d5f103Mathieu Chartierinline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, 66e9ea70bb806f7c1dcd57efb6f48f1d6329d5f103Mathieu Chartier const Visitor& visitor) const { 676f365cc033654a5a3b45eaa1379d4b5f156b0ceeMathieu Chartier DCHECK_LE(visit_begin, visit_end); 68be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe#if 0 69be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) { 70be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe mirror::Object* obj = reinterpret_cast<mirror::Object*>(i); 71be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe if (Test(obj)) { 72be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe visitor(obj); 73be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 74be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 75be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe#else 76cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe DCHECK_LE(heap_begin_, visit_begin); 77cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe DCHECK_LE(visit_end, HeapLimit()); 782dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 79cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t offset_start = visit_begin - heap_begin_; 80cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t offset_end = visit_end - heap_begin_; 812dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 82cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t index_start = OffsetToIndex(offset_start); 83cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t index_end = OffsetToIndex(offset_end); 842dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 8513735955f39b3b304c37d2b2840663c131262c18Ian Rogers const size_t bit_start = (offset_start / kAlignment) % kBitsPerIntPtrT; 8613735955f39b3b304c37d2b2840663c131262c18Ian Rogers const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT; 872dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 88cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Index(begin) ... Index(end) 89cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // [xxxxx???][........][????yyyy] 90cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // ^ ^ 91cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // | #---- Bit of visit_end 92cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // #---- Bit of visit_begin 93cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // 94cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe 95cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Left edge. 9613735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t left_edge = bitmap_begin_[index_start]; 97cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Mark of lower bits that are not in range. 9813735955f39b3b304c37d2b2840663c131262c18Ian Rogers left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1); 992dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 100cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Right edge. Either unique, or left_edge. 10113735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t right_edge; 102cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe 103cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe if (index_start < index_end) { 104cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Left edge != right edge. 105cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe 106cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Traverse left edge. 107cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe if (left_edge != 0) { 108cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_; 1092dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers do { 110cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(left_edge); 1112dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 1122dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers visitor(obj); 11313735955f39b3b304c37d2b2840663c131262c18Ian Rogers left_edge ^= (static_cast<uintptr_t>(1)) << shift; 114cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } while (left_edge != 0); 1152dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1162dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 117cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Traverse the middle, full part. 118cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe for (size_t i = index_start + 1; i < index_end; ++i) { 11913735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t w = bitmap_begin_[i]; 120cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe if (w != 0) { 121cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 122cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe do { 123cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(w); 124cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 125cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe visitor(obj); 12613735955f39b3b304c37d2b2840663c131262c18Ian Rogers w ^= (static_cast<uintptr_t>(1)) << shift; 127cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } while (w != 0); 128cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } 129cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } 1302dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 131cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Right edge is unique. 132be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe // But maybe we don't have anything to do: visit_end starts in a new word... 133be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe if (bit_end == 0) { 134be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe // Do not read memory, as it could be after the end of the bitmap. 135be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe right_edge = 0; 136be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } else { 137be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe right_edge = bitmap_begin_[index_end]; 138be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 139cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } else { 140cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Right edge = left edge. 141cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe right_edge = left_edge; 1422dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1432dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 144cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe // Right edge handling. 14513735955f39b3b304c37d2b2840663c131262c18Ian Rogers right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1); 146cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe if (right_edge != 0) { 147cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_; 148cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe do { 149cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe const size_t shift = CTZ(right_edge); 150cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 151cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe visitor(obj); 15213735955f39b3b304c37d2b2840663c131262c18Ian Rogers right_edge ^= (static_cast<uintptr_t>(1)) << shift; 153cb8aea4bd5e77857c713edeb62bffcb1f7f06a39Andreas Gampe } while (right_edge != 0); 1542dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 155be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe#endif 1562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 1572dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 158a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> template<bool kSetBit> 159a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartierinline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) { 1602dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 1612dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 162d39645e22b8db1767cf64dc1200a9e4b2f939ed2Mathieu Chartier DCHECK(HasAddress(obj)) << obj; 1632dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 1642dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t index = OffsetToIndex(offset); 16513735955f39b3b304c37d2b2840663c131262c18Ian Rogers const uintptr_t mask = OffsetToMask(offset); 16613735955f39b3b304c37d2b2840663c131262c18Ian Rogers DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_; 16713735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t* address = &bitmap_begin_[index]; 16813735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t old_word = *address; 169a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier if (kSetBit) { 170fbc31087932a65e036a153afab3049dc5298656aMathieu Chartier // Check the bit before setting the word incase we are trying to mark a read only bitmap 171fbc31087932a65e036a153afab3049dc5298656aMathieu Chartier // like an image space bitmap. This bitmap is mapped as read only and will fault if we 172fbc31087932a65e036a153afab3049dc5298656aMathieu Chartier // attempt to change any words. Since all of the objects are marked, this will never 173fbc31087932a65e036a153afab3049dc5298656aMathieu Chartier // occur if we check before setting the bit. This also prevents dirty pages that would 174fbc31087932a65e036a153afab3049dc5298656aMathieu Chartier // occur if the bitmap was read write and we did not check the bit. 175dcdc85bbd569f0ee66c331b4219c19304a616214Jeff Hao if ((old_word & mask) == 0) { 176dcdc85bbd569f0ee66c331b4219c19304a616214Jeff Hao *address = old_word | mask; 177dcdc85bbd569f0ee66c331b4219c19304a616214Jeff Hao } 1782dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } else { 1792dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *address = old_word & ~mask; 1802dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 181a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier DCHECK_EQ(Test(obj), kSetBit); 1822dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return (old_word & mask) != 0; 1832dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 1841d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 185a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartiertemplate<size_t kAlignment> 186a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartierinline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) { 187a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier return stream 188a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier << bitmap.GetName() << "[" 189a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 190a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 191a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier << "]"; 192a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier} 193a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier 1941d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 1951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 1962dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} // namespace art 1972dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 198fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 199