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