1 /* 2 * Copyright (C) 2011 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_CARD_TABLE_INL_H_ 18 #define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_ 19 20 #include "card_table.h" 21 22 #include <android-base/logging.h> 23 24 #include "base/atomic.h" 25 #include "base/bit_utils.h" 26 #include "base/mem_map.h" 27 #include "space_bitmap.h" 28 29 namespace art { 30 namespace gc { 31 namespace accounting { 32 33 static inline bool byte_cas(uint8_t old_value, uint8_t new_value, uint8_t* address) { 34 #if defined(__i386__) || defined(__x86_64__) 35 Atomic<uint8_t>* byte_atomic = reinterpret_cast<Atomic<uint8_t>*>(address); 36 return byte_atomic->CompareAndSetWeakRelaxed(old_value, new_value); 37 #else 38 // Little endian means most significant byte is on the left. 39 const size_t shift_in_bytes = reinterpret_cast<uintptr_t>(address) % sizeof(uintptr_t); 40 // Align the address down. 41 address -= shift_in_bytes; 42 const size_t shift_in_bits = shift_in_bytes * kBitsPerByte; 43 Atomic<uintptr_t>* word_atomic = reinterpret_cast<Atomic<uintptr_t>*>(address); 44 45 // Word with the byte we are trying to cas cleared. 46 const uintptr_t cur_word = word_atomic->load(std::memory_order_relaxed) & 47 ~(static_cast<uintptr_t>(0xFF) << shift_in_bits); 48 const uintptr_t old_word = cur_word | (static_cast<uintptr_t>(old_value) << shift_in_bits); 49 const uintptr_t new_word = cur_word | (static_cast<uintptr_t>(new_value) << shift_in_bits); 50 return word_atomic->CompareAndSetWeakRelaxed(old_word, new_word); 51 #endif 52 } 53 54 template <bool kClearCard, typename Visitor> 55 inline size_t CardTable::Scan(ContinuousSpaceBitmap* bitmap, 56 uint8_t* const scan_begin, 57 uint8_t* const scan_end, 58 const Visitor& visitor, 59 const uint8_t minimum_age) { 60 DCHECK_GE(scan_begin, reinterpret_cast<uint8_t*>(bitmap->HeapBegin())); 61 // scan_end is the byte after the last byte we scan. 62 DCHECK_LE(scan_end, reinterpret_cast<uint8_t*>(bitmap->HeapLimit())); 63 uint8_t* const card_begin = CardFromAddr(scan_begin); 64 uint8_t* const card_end = CardFromAddr(AlignUp(scan_end, kCardSize)); 65 uint8_t* card_cur = card_begin; 66 CheckCardValid(card_cur); 67 CheckCardValid(card_end); 68 size_t cards_scanned = 0; 69 70 // Handle any unaligned cards at the start. 71 while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) { 72 if (*card_cur >= minimum_age) { 73 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur)); 74 bitmap->VisitMarkedRange(start, start + kCardSize, visitor); 75 ++cards_scanned; 76 } 77 ++card_cur; 78 } 79 80 uint8_t* aligned_end = card_end - 81 (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1)); 82 83 uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end); 84 for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end; 85 ++word_cur) { 86 while (LIKELY(*word_cur == 0)) { 87 ++word_cur; 88 if (UNLIKELY(word_cur >= word_end)) { 89 goto exit_for; 90 } 91 } 92 93 // Find the first dirty card. 94 uintptr_t start_word = *word_cur; 95 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<uint8_t*>(word_cur))); 96 // TODO: Investigate if processing continuous runs of dirty cards with a single bitmap visit is 97 // more efficient. 98 for (size_t i = 0; i < sizeof(uintptr_t); ++i) { 99 if (static_cast<uint8_t>(start_word) >= minimum_age) { 100 auto* card = reinterpret_cast<uint8_t*>(word_cur) + i; 101 DCHECK(*card == static_cast<uint8_t>(start_word) || *card == kCardDirty) 102 << "card " << static_cast<size_t>(*card) << " intptr_t " << (start_word & 0xFF); 103 bitmap->VisitMarkedRange(start, start + kCardSize, visitor); 104 ++cards_scanned; 105 } 106 start_word >>= 8; 107 start += kCardSize; 108 } 109 } 110 exit_for: 111 112 // Handle any unaligned cards at the end. 113 card_cur = reinterpret_cast<uint8_t*>(word_end); 114 while (card_cur < card_end) { 115 if (*card_cur >= minimum_age) { 116 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur)); 117 bitmap->VisitMarkedRange(start, start + kCardSize, visitor); 118 ++cards_scanned; 119 } 120 ++card_cur; 121 } 122 123 if (kClearCard) { 124 ClearCardRange(scan_begin, scan_end); 125 } 126 127 return cards_scanned; 128 } 129 130 template <typename Visitor, typename ModifiedVisitor> 131 inline void CardTable::ModifyCardsAtomic(uint8_t* scan_begin, 132 uint8_t* scan_end, 133 const Visitor& visitor, 134 const ModifiedVisitor& modified) { 135 uint8_t* card_cur = CardFromAddr(scan_begin); 136 uint8_t* card_end = CardFromAddr(AlignUp(scan_end, kCardSize)); 137 CheckCardValid(card_cur); 138 CheckCardValid(card_end); 139 DCHECK(visitor(kCardClean) == kCardClean); 140 141 // Handle any unaligned cards at the start. 142 while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) { 143 uint8_t expected, new_value; 144 do { 145 expected = *card_cur; 146 new_value = visitor(expected); 147 } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_cur))); 148 if (expected != new_value) { 149 modified(card_cur, expected, new_value); 150 } 151 ++card_cur; 152 } 153 154 // Handle unaligned cards at the end. 155 while (!IsAligned<sizeof(intptr_t)>(card_end) && card_end > card_cur) { 156 --card_end; 157 uint8_t expected, new_value; 158 do { 159 expected = *card_end; 160 new_value = visitor(expected); 161 } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_end))); 162 if (expected != new_value) { 163 modified(card_end, expected, new_value); 164 } 165 } 166 167 // Now we have the words, we can process words in parallel. 168 uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); 169 uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end); 170 // TODO: This is not big endian safe. 171 union { 172 uintptr_t expected_word; 173 uint8_t expected_bytes[sizeof(uintptr_t)]; 174 }; 175 union { 176 uintptr_t new_word; 177 uint8_t new_bytes[sizeof(uintptr_t)]; 178 }; 179 180 // TODO: Parallelize. 181 while (word_cur < word_end) { 182 while (true) { 183 expected_word = *word_cur; 184 static_assert(kCardClean == 0); 185 if (LIKELY(expected_word == 0 /* All kCardClean */ )) { 186 break; 187 } 188 for (size_t i = 0; i < sizeof(uintptr_t); ++i) { 189 new_bytes[i] = visitor(expected_bytes[i]); 190 } 191 Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur); 192 if (LIKELY(atomic_word->CompareAndSetWeakRelaxed(expected_word, new_word))) { 193 for (size_t i = 0; i < sizeof(uintptr_t); ++i) { 194 const uint8_t expected_byte = expected_bytes[i]; 195 const uint8_t new_byte = new_bytes[i]; 196 if (expected_byte != new_byte) { 197 modified(reinterpret_cast<uint8_t*>(word_cur) + i, expected_byte, new_byte); 198 } 199 } 200 break; 201 } 202 } 203 ++word_cur; 204 } 205 } 206 207 inline void* CardTable::AddrFromCard(const uint8_t *card_addr) const { 208 DCHECK(IsValidCard(card_addr)) 209 << " card_addr: " << reinterpret_cast<const void*>(card_addr) 210 << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_) 211 << " end: " << reinterpret_cast<void*>(mem_map_.End()); 212 uintptr_t offset = card_addr - biased_begin_; 213 return reinterpret_cast<void*>(offset << kCardShift); 214 } 215 216 inline uint8_t* CardTable::CardFromAddr(const void *addr) const { 217 uint8_t *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift); 218 // Sanity check the caller was asking for address covered by the card table 219 DCHECK(IsValidCard(card_addr)) << "addr: " << addr 220 << " card_addr: " << reinterpret_cast<void*>(card_addr); 221 return card_addr; 222 } 223 224 inline bool CardTable::IsValidCard(const uint8_t* card_addr) const { 225 uint8_t* begin = mem_map_.Begin() + offset_; 226 uint8_t* end = mem_map_.End(); 227 return card_addr >= begin && card_addr < end; 228 } 229 230 inline void CardTable::CheckCardValid(uint8_t* card) const { 231 DCHECK(IsValidCard(card)) 232 << " card_addr: " << reinterpret_cast<const void*>(card) 233 << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_) 234 << " end: " << reinterpret_cast<void*>(mem_map_.End()); 235 } 236 237 } // namespace accounting 238 } // namespace gc 239 } // namespace art 240 241 #endif // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_ 242