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