1 /* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 18 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 19 20 #include "base/logging.h" 21 #include "cutils/atomic-inline.h" 22 #include "utils.h" 23 24 namespace art { 25 namespace gc { 26 namespace accounting { 27 28 inline bool SpaceBitmap::AtomicTestAndSet(const mirror::Object* obj) { 29 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 30 DCHECK_GE(addr, heap_begin_); 31 const uintptr_t offset = addr - heap_begin_; 32 const size_t index = OffsetToIndex(offset); 33 const word mask = OffsetToMask(offset); 34 word* const address = &bitmap_begin_[index]; 35 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_; 36 word old_word; 37 do { 38 old_word = *address; 39 // Fast path: The bit is already set. 40 if ((old_word & mask) != 0) { 41 return true; 42 } 43 } while (UNLIKELY(android_atomic_cas(old_word, old_word | mask, address) != 0)); 44 return false; 45 } 46 47 inline bool SpaceBitmap::Test(const mirror::Object* obj) const { 48 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 49 DCHECK(HasAddress(obj)) << obj; 50 DCHECK(bitmap_begin_ != NULL); 51 DCHECK_GE(addr, heap_begin_); 52 const uintptr_t offset = addr - heap_begin_; 53 return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0; 54 } 55 56 template <typename Visitor> 57 void SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, 58 const Visitor& visitor) const { 59 DCHECK_LT(visit_begin, visit_end); 60 const size_t bit_index_start = (visit_begin - heap_begin_) / kAlignment; 61 const size_t bit_index_end = (visit_end - heap_begin_ - 1) / kAlignment; 62 63 size_t word_start = bit_index_start / kBitsPerWord; 64 size_t word_end = bit_index_end / kBitsPerWord; 65 DCHECK_LT(word_end * kWordSize, Size()); 66 67 // Trim off left_bits of left bits. 68 size_t edge_word = bitmap_begin_[word_start]; 69 70 // Handle bits on the left first as a special case 71 size_t left_bits = bit_index_start & (kBitsPerWord - 1); 72 if (left_bits != 0) { 73 edge_word &= (1 << (kBitsPerWord - left_bits)) - 1; 74 } 75 76 // If word_start == word_end then handle this case at the same place we handle the right edge. 77 if (edge_word != 0 && word_start < word_end) { 78 uintptr_t ptr_base = IndexToOffset(word_start) + heap_begin_; 79 do { 80 const size_t shift = CLZ(edge_word); 81 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 82 visitor(obj); 83 edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift; 84 } while (edge_word != 0); 85 } 86 word_start++; 87 88 for (size_t i = word_start; i < word_end; i++) { 89 size_t w = bitmap_begin_[i]; 90 if (w != 0) { 91 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 92 do { 93 const size_t shift = CLZ(w); 94 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 95 visitor(obj); 96 w ^= static_cast<size_t>(kWordHighBitMask) >> shift; 97 } while (w != 0); 98 } 99 } 100 101 // Handle the right edge, and also the left edge if both edges are on the same word. 102 size_t right_bits = bit_index_end & (kBitsPerWord - 1); 103 104 // If word_start == word_end then we need to use the word which we removed the left bits. 105 if (word_start <= word_end) { 106 edge_word = bitmap_begin_[word_end]; 107 } 108 109 // Bits that we trim off the right. 110 edge_word &= ~((static_cast<size_t>(kWordHighBitMask) >> right_bits) - 1); 111 uintptr_t ptr_base = IndexToOffset(word_end) + heap_begin_; 112 while (edge_word != 0) { 113 const size_t shift = CLZ(edge_word); 114 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 115 visitor(obj); 116 edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift; 117 } 118 } 119 120 inline bool SpaceBitmap::Modify(const mirror::Object* obj, bool do_set) { 121 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 122 DCHECK_GE(addr, heap_begin_); 123 const uintptr_t offset = addr - heap_begin_; 124 const size_t index = OffsetToIndex(offset); 125 const word mask = OffsetToMask(offset); 126 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_; 127 word* address = &bitmap_begin_[index]; 128 word old_word = *address; 129 if (do_set) { 130 *address = old_word | mask; 131 } else { 132 *address = old_word & ~mask; 133 } 134 return (old_word & mask) != 0; 135 } 136 137 } // namespace accounting 138 } // namespace gc 139 } // namespace art 140 141 #endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 142
