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