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