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 "space_bitmap.h" 21 22 #include <memory> 23 24 #include "atomic.h" 25 #include "base/bit_utils.h" 26 #include "base/logging.h" 27 28 namespace art { 29 namespace gc { 30 namespace accounting { 31 32 template<size_t kAlignment> 33 inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) { 34 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 35 DCHECK_GE(addr, heap_begin_); 36 const uintptr_t offset = addr - heap_begin_; 37 const size_t index = OffsetToIndex(offset); 38 const uintptr_t mask = OffsetToMask(offset); 39 Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index]; 40 DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_; 41 uintptr_t old_word; 42 do { 43 old_word = atomic_entry->LoadRelaxed(); 44 // Fast path: The bit is already set. 45 if ((old_word & mask) != 0) { 46 DCHECK(Test(obj)); 47 return true; 48 } 49 } while (!atomic_entry->CompareExchangeWeakRelaxed(old_word, old_word | mask)); 50 DCHECK(Test(obj)); 51 return false; 52 } 53 54 template<size_t kAlignment> 55 inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const { 56 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 57 DCHECK(HasAddress(obj)) << obj; 58 DCHECK(bitmap_begin_ != nullptr); 59 DCHECK_GE(addr, heap_begin_); 60 const uintptr_t offset = addr - heap_begin_; 61 return (bitmap_begin_[OffsetToIndex(offset)].LoadRelaxed() & OffsetToMask(offset)) != 0; 62 } 63 64 template<size_t kAlignment> template<typename Visitor> 65 inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, 66 uintptr_t visit_end, 67 Visitor&& visitor) const { 68 DCHECK_LE(visit_begin, visit_end); 69 #if 0 70 for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) { 71 mirror::Object* obj = reinterpret_cast<mirror::Object*>(i); 72 if (Test(obj)) { 73 visitor(obj); 74 } 75 } 76 #else 77 DCHECK_LE(heap_begin_, visit_begin); 78 DCHECK_LE(visit_end, HeapLimit()); 79 80 const uintptr_t offset_start = visit_begin - heap_begin_; 81 const uintptr_t offset_end = visit_end - heap_begin_; 82 83 const uintptr_t index_start = OffsetToIndex(offset_start); 84 const uintptr_t index_end = OffsetToIndex(offset_end); 85 86 const size_t bit_start = (offset_start / kAlignment) % kBitsPerIntPtrT; 87 const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT; 88 89 // Index(begin) ... Index(end) 90 // [xxxxx???][........][????yyyy] 91 // ^ ^ 92 // | #---- Bit of visit_end 93 // #---- Bit of visit_begin 94 // 95 96 // Left edge. 97 uintptr_t left_edge = bitmap_begin_[index_start]; 98 // Mark of lower bits that are not in range. 99 left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1); 100 101 // Right edge. Either unique, or left_edge. 102 uintptr_t right_edge; 103 104 if (index_start < index_end) { 105 // Left edge != right edge. 106 107 // Traverse left edge. 108 if (left_edge != 0) { 109 const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_; 110 do { 111 const size_t shift = CTZ(left_edge); 112 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 113 visitor(obj); 114 left_edge ^= (static_cast<uintptr_t>(1)) << shift; 115 } while (left_edge != 0); 116 } 117 118 // Traverse the middle, full part. 119 for (size_t i = index_start + 1; i < index_end; ++i) { 120 uintptr_t w = bitmap_begin_[i].LoadRelaxed(); 121 if (w != 0) { 122 const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 123 do { 124 const size_t shift = CTZ(w); 125 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 126 visitor(obj); 127 w ^= (static_cast<uintptr_t>(1)) << shift; 128 } while (w != 0); 129 } 130 } 131 132 // Right edge is unique. 133 // But maybe we don't have anything to do: visit_end starts in a new word... 134 if (bit_end == 0) { 135 // Do not read memory, as it could be after the end of the bitmap. 136 right_edge = 0; 137 } else { 138 right_edge = bitmap_begin_[index_end]; 139 } 140 } else { 141 // Right edge = left edge. 142 right_edge = left_edge; 143 } 144 145 // Right edge handling. 146 right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1); 147 if (right_edge != 0) { 148 const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_; 149 do { 150 const size_t shift = CTZ(right_edge); 151 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 152 visitor(obj); 153 right_edge ^= (static_cast<uintptr_t>(1)) << shift; 154 } while (right_edge != 0); 155 } 156 #endif 157 } 158 159 template<size_t kAlignment> template<typename Visitor> 160 void SpaceBitmap<kAlignment>::Walk(Visitor&& visitor) { 161 CHECK(bitmap_begin_ != nullptr); 162 163 uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1); 164 Atomic<uintptr_t>* bitmap_begin = bitmap_begin_; 165 for (uintptr_t i = 0; i <= end; ++i) { 166 uintptr_t w = bitmap_begin[i].LoadRelaxed(); 167 if (w != 0) { 168 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; 169 do { 170 const size_t shift = CTZ(w); 171 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); 172 visitor(obj); 173 w ^= (static_cast<uintptr_t>(1)) << shift; 174 } while (w != 0); 175 } 176 } 177 } 178 179 template<size_t kAlignment> template<bool kSetBit> 180 inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) { 181 uintptr_t addr = reinterpret_cast<uintptr_t>(obj); 182 DCHECK_GE(addr, heap_begin_); 183 DCHECK(HasAddress(obj)) << obj; 184 const uintptr_t offset = addr - heap_begin_; 185 const size_t index = OffsetToIndex(offset); 186 const uintptr_t mask = OffsetToMask(offset); 187 DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_; 188 Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index]; 189 uintptr_t old_word = atomic_entry->LoadRelaxed(); 190 if (kSetBit) { 191 // Check the bit before setting the word incase we are trying to mark a read only bitmap 192 // like an image space bitmap. This bitmap is mapped as read only and will fault if we 193 // attempt to change any words. Since all of the objects are marked, this will never 194 // occur if we check before setting the bit. This also prevents dirty pages that would 195 // occur if the bitmap was read write and we did not check the bit. 196 if ((old_word & mask) == 0) { 197 atomic_entry->StoreRelaxed(old_word | mask); 198 } 199 } else { 200 atomic_entry->StoreRelaxed(old_word & ~mask); 201 } 202 DCHECK_EQ(Test(obj), kSetBit); 203 return (old_word & mask) != 0; 204 } 205 206 template<size_t kAlignment> 207 inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) { 208 return stream 209 << bitmap.GetName() << "[" 210 << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin()) 211 << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit()) 212 << "]"; 213 } 214 215 } // namespace accounting 216 } // namespace gc 217 } // namespace art 218 219 #endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_ 220