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 202dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "base/logging.h" 21693ff61274cd2c9b8eb7e68c370f84a911b8ca52Ian Rogers#include "cutils/atomic-inline.h" 221d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "utils.h" 232dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersnamespace art { 251d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 261d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 272dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 282dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersinline bool SpaceBitmap::AtomicTestAndSet(const mirror::Object* obj) { 292dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 302dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 312dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 322dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t index = OffsetToIndex(offset); 332dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const word mask = OffsetToMask(offset); 342dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers word* const address = &bitmap_begin_[index]; 352dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_; 362dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers word old_word; 372dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers do { 382dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers old_word = *address; 392dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Fast path: The bit is already set. 402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if ((old_word & mask) != 0) { 412dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return true; 422dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 432dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } while (UNLIKELY(android_atomic_cas(old_word, old_word | mask, address) != 0)); 442dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return false; 452dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 462dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 472dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersinline bool SpaceBitmap::Test(const mirror::Object* obj) const { 482dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 492dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK(HasAddress(obj)) << obj; 502dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK(bitmap_begin_ != NULL); 512dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 522dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 532dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0; 542dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 552dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 56184e322fe8ddd75c844a1eb2eb1ca32bc02f2d45Mathieu Chartiertemplate <typename Visitor> 572dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersvoid SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, 58184e322fe8ddd75c844a1eb2eb1ca32bc02f2d45Mathieu Chartier const Visitor& visitor) const { 592dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_LT(visit_begin, visit_end); 602dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t bit_index_start = (visit_begin - heap_begin_) / kAlignment; 612dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t bit_index_end = (visit_end - heap_begin_ - 1) / kAlignment; 622dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 632dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t word_start = bit_index_start / kBitsPerWord; 642dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t word_end = bit_index_end / kBitsPerWord; 652dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_LT(word_end * kWordSize, Size()); 662dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 672dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Trim off left_bits of left bits. 682dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t edge_word = bitmap_begin_[word_start]; 692dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 702dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Handle bits on the left first as a special case 712dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t left_bits = bit_index_start & (kBitsPerWord - 1); 722dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if (left_bits != 0) { 732dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers edge_word &= (1 << (kBitsPerWord - left_bits)) - 1; 742dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 752dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 762dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // If word_start == word_end then handle this case at the same place we handle the right edge. 772dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if (edge_word != 0 && word_start < word_end) { 782dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t ptr_base = IndexToOffset(word_start) + heap_begin_; 792dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers do { 802dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t shift = CLZ(edge_word); 812dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 822dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers visitor(obj); 832dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift; 842dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } while (edge_word != 0); 852dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 862dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers word_start++; 872dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 882dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers for (size_t i = word_start; i < word_end; i++) { 892dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t w = bitmap_begin_[i]; 902dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if (w != 0) { 912dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 922dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers do { 932dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t shift = CLZ(w); 942dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 952dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers visitor(obj); 962dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 972dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } while (w != 0); 982dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 992dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1002dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 1012dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Handle the right edge, and also the left edge if both edges are on the same word. 1022dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers size_t right_bits = bit_index_end & (kBitsPerWord - 1); 1032dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 1042dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // If word_start == word_end then we need to use the word which we removed the left bits. 1052dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if (word_start <= word_end) { 1062dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers edge_word = bitmap_begin_[word_end]; 1072dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1082dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 1092dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // Bits that we trim off the right. 1102dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers edge_word &= ~((static_cast<size_t>(kWordHighBitMask) >> right_bits) - 1); 1112dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t ptr_base = IndexToOffset(word_end) + heap_begin_; 1122dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers while (edge_word != 0) { 1132dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t shift = CLZ(edge_word); 1142dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 1152dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers visitor(obj); 1162dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift; 1172dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1182dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 1192dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 1202dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersinline bool SpaceBitmap::Modify(const mirror::Object* obj, bool do_set) { 1212dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 1222dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_GE(addr, heap_begin_); 1232dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const uintptr_t offset = addr - heap_begin_; 1242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const size_t index = OffsetToIndex(offset); 1252dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const word mask = OffsetToMask(offset); 1262dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_; 1272dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers word* address = &bitmap_begin_[index]; 1282dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers word old_word = *address; 1292dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers if (do_set) { 1302dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *address = old_word | mask; 1312dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } else { 1322dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers *address = old_word & ~mask; 1332dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 1342dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers return (old_word & mask) != 0; 1352dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} 1361d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 1371d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 1381d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 1392dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers} // namespace art 1402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 141fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 142