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