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 HIDDEN {
30 namespace gc {
31 namespace accounting {
32
byte_cas(uint8_t old_value,uint8_t new_value,uint8_t * address)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, typename ModifyVisitor>
Scan(ContinuousSpaceBitmap * bitmap,uint8_t * const scan_begin,uint8_t * const scan_end,const Visitor & visitor,const ModifyVisitor & mod_visitor,const uint8_t minimum_age)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 ModifyVisitor& mod_visitor,
60 const uint8_t minimum_age) {
61 DCHECK_GE(scan_begin, reinterpret_cast<uint8_t*>(bitmap->HeapBegin()));
62 // scan_end is the byte after the last byte we scan.
63 DCHECK_LE(scan_end, reinterpret_cast<uint8_t*>(bitmap->HeapLimit()));
64 uint8_t* const card_begin = CardFromAddr(scan_begin);
65 uint8_t* const card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
66 uint8_t* card_cur = card_begin;
67 CheckCardValid(card_cur);
68 CheckCardValid(card_end);
69 size_t cards_scanned = 0;
70
71 // Handle any unaligned cards at the start.
72 while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
73 uint8_t cur_val = *card_cur;
74 if (cur_val >= minimum_age) {
75 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
76 bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
77 mod_visitor(card_cur, cur_val);
78 ++cards_scanned;
79 }
80 ++card_cur;
81 }
82
83 if (card_cur < card_end) {
84 DCHECK_ALIGNED(card_cur, sizeof(intptr_t));
85 uint8_t* aligned_end = card_end -
86 (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
87 DCHECK_LE(card_cur, aligned_end);
88
89 uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
90 for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
91 ++word_cur) {
92 while (LIKELY(*word_cur == 0)) {
93 ++word_cur;
94 if (UNLIKELY(word_cur >= word_end)) {
95 goto exit_for;
96 }
97 }
98
99 // Find the first dirty card.
100 uintptr_t start_word = *word_cur;
101 uintptr_t start =
102 reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<uint8_t*>(word_cur)));
103 // TODO: Investigate if processing continuous runs of dirty cards with
104 // a single bitmap visit is more efficient.
105 for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
106 uint8_t cur_val = static_cast<uint8_t>(start_word);
107 if (cur_val >= minimum_age) {
108 auto* card = reinterpret_cast<uint8_t*>(word_cur) + i;
109 DCHECK(*card == static_cast<uint8_t>(start_word) || *card == kCardDirty)
110 << "card " << static_cast<size_t>(*card) << " intptr_t " << cur_val;
111 bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
112 mod_visitor(card, cur_val);
113 ++cards_scanned;
114 }
115 start_word >>= 8;
116 start += kCardSize;
117 }
118 }
119 exit_for:
120
121 // Handle any unaligned cards at the end.
122 card_cur = reinterpret_cast<uint8_t*>(word_end);
123 while (card_cur < card_end) {
124 uint8_t cur_val = *card_cur;
125 if (cur_val >= minimum_age) {
126 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
127 bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
128 mod_visitor(card_cur, cur_val);
129 ++cards_scanned;
130 }
131 ++card_cur;
132 }
133 }
134
135 if (kClearCard) {
136 ClearCardRange(scan_begin, scan_end);
137 }
138
139 return cards_scanned;
140 }
141
142 template <typename Visitor, typename ModifiedVisitor>
ModifyCardsAtomic(uint8_t * scan_begin,uint8_t * scan_end,const Visitor & visitor,const ModifiedVisitor & modified)143 inline void CardTable::ModifyCardsAtomic(uint8_t* scan_begin,
144 uint8_t* scan_end,
145 const Visitor& visitor,
146 const ModifiedVisitor& modified) {
147 uint8_t* card_cur = CardFromAddr(scan_begin);
148 uint8_t* card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
149 CheckCardValid(card_cur);
150 CheckCardValid(card_end);
151 DCHECK(visitor(kCardClean) == kCardClean);
152
153 // Handle any unaligned cards at the start.
154 while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
155 uint8_t expected, new_value;
156 do {
157 expected = *card_cur;
158 new_value = visitor(expected);
159 } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_cur)));
160 if (expected != new_value) {
161 modified(card_cur, expected, new_value);
162 }
163 ++card_cur;
164 }
165
166 // Handle unaligned cards at the end.
167 while (!IsAligned<sizeof(intptr_t)>(card_end) && card_end > card_cur) {
168 --card_end;
169 uint8_t expected, new_value;
170 do {
171 expected = *card_end;
172 new_value = visitor(expected);
173 } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_end)));
174 if (expected != new_value) {
175 modified(card_end, expected, new_value);
176 }
177 }
178
179 // Now we have the words, we can process words in parallel.
180 uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
181 uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end);
182 // TODO: This is not big endian safe.
183 union {
184 uintptr_t expected_word;
185 uint8_t expected_bytes[sizeof(uintptr_t)];
186 };
187 union {
188 uintptr_t new_word;
189 uint8_t new_bytes[sizeof(uintptr_t)];
190 };
191
192 // TODO: Parallelize.
193 while (word_cur < word_end) {
194 while (true) {
195 expected_word = *word_cur;
196 static_assert(kCardClean == 0);
197 if (LIKELY(expected_word == 0 /* All kCardClean */ )) {
198 break;
199 }
200 for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
201 new_bytes[i] = visitor(expected_bytes[i]);
202 }
203 Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur);
204 if (LIKELY(atomic_word->CompareAndSetWeakRelaxed(expected_word, new_word))) {
205 for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
206 const uint8_t expected_byte = expected_bytes[i];
207 const uint8_t new_byte = new_bytes[i];
208 if (expected_byte != new_byte) {
209 modified(reinterpret_cast<uint8_t*>(word_cur) + i, expected_byte, new_byte);
210 }
211 }
212 break;
213 }
214 }
215 ++word_cur;
216 }
217 }
218
AddrFromCard(const uint8_t * card_addr)219 inline void* CardTable::AddrFromCard(const uint8_t *card_addr) const {
220 DCHECK(IsValidCard(card_addr))
221 << " card_addr: " << reinterpret_cast<const void*>(card_addr)
222 << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_)
223 << " end: " << reinterpret_cast<void*>(mem_map_.End());
224 uintptr_t offset = card_addr - biased_begin_;
225 return reinterpret_cast<void*>(offset << kCardShift);
226 }
227
CardFromAddr(const void * addr)228 inline uint8_t* CardTable::CardFromAddr(const void *addr) const {
229 uint8_t *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift);
230 // Check that the caller was asking for an address covered by the card table.
231 DCHECK(IsValidCard(card_addr)) << "addr: " << addr
232 << " card_addr: " << reinterpret_cast<void*>(card_addr);
233 return card_addr;
234 }
235
IsValidCard(const uint8_t * card_addr)236 inline bool CardTable::IsValidCard(const uint8_t* card_addr) const {
237 uint8_t* begin = mem_map_.Begin() + offset_;
238 uint8_t* end = mem_map_.End();
239 return card_addr >= begin && card_addr < end;
240 }
241
CheckCardValid(uint8_t * card)242 inline void CardTable::CheckCardValid(uint8_t* card) const {
243 DCHECK(IsValidCard(card))
244 << " card_addr: " << reinterpret_cast<const void*>(card)
245 << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_)
246 << " end: " << reinterpret_cast<void*>(mem_map_.End());
247 }
248
249 } // namespace accounting
250 } // namespace gc
251 } // namespace art
252
253 #endif // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
254