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