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 {
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>
Scan(ContinuousSpaceBitmap * bitmap,uint8_t * const scan_begin,uint8_t * const scan_end,const Visitor & 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 uint8_t minimum_age) {
60   DCHECK_GE(scan_begin, reinterpret_cast<uint8_t*>(bitmap->HeapBegin()));
61   // scan_end is the byte after the last byte we scan.
62   DCHECK_LE(scan_end, reinterpret_cast<uint8_t*>(bitmap->HeapLimit()));
63   uint8_t* const card_begin = CardFromAddr(scan_begin);
64   uint8_t* const card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
65   uint8_t* card_cur = card_begin;
66   CheckCardValid(card_cur);
67   CheckCardValid(card_end);
68   size_t cards_scanned = 0;
69 
70   // Handle any unaligned cards at the start.
71   while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
72     if (*card_cur >= minimum_age) {
73       uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
74       bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
75       ++cards_scanned;
76     }
77     ++card_cur;
78   }
79 
80   if (card_cur < card_end) {
81     DCHECK_ALIGNED(card_cur, sizeof(intptr_t));
82     uint8_t* aligned_end = card_end -
83         (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
84     DCHECK_LE(card_cur, aligned_end);
85 
86     uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
87     for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
88         ++word_cur) {
89       while (LIKELY(*word_cur == 0)) {
90         ++word_cur;
91         if (UNLIKELY(word_cur >= word_end)) {
92           goto exit_for;
93         }
94       }
95 
96       // Find the first dirty card.
97       uintptr_t start_word = *word_cur;
98       uintptr_t start =
99           reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<uint8_t*>(word_cur)));
100       // TODO: Investigate if processing continuous runs of dirty cards with
101       // a single bitmap visit is more efficient.
102       for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
103         if (static_cast<uint8_t>(start_word) >= minimum_age) {
104           auto* card = reinterpret_cast<uint8_t*>(word_cur) + i;
105           DCHECK(*card == static_cast<uint8_t>(start_word) || *card == kCardDirty)
106               << "card " << static_cast<size_t>(*card) << " intptr_t " << (start_word & 0xFF);
107           bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
108           ++cards_scanned;
109         }
110         start_word >>= 8;
111         start += kCardSize;
112       }
113     }
114     exit_for:
115 
116     // Handle any unaligned cards at the end.
117     card_cur = reinterpret_cast<uint8_t*>(word_end);
118     while (card_cur < card_end) {
119       if (*card_cur >= minimum_age) {
120         uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
121         bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
122         ++cards_scanned;
123       }
124       ++card_cur;
125     }
126   }
127 
128   if (kClearCard) {
129     ClearCardRange(scan_begin, scan_end);
130   }
131 
132   return cards_scanned;
133 }
134 
135 template <typename Visitor, typename ModifiedVisitor>
ModifyCardsAtomic(uint8_t * scan_begin,uint8_t * scan_end,const Visitor & visitor,const ModifiedVisitor & modified)136 inline void CardTable::ModifyCardsAtomic(uint8_t* scan_begin,
137                                          uint8_t* scan_end,
138                                          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   DCHECK(visitor(kCardClean) == kCardClean);
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       static_assert(kCardClean == 0);
190       if (LIKELY(expected_word == 0 /* All kCardClean */ )) {
191         break;
192       }
193       for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
194         new_bytes[i] = visitor(expected_bytes[i]);
195       }
196       Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur);
197       if (LIKELY(atomic_word->CompareAndSetWeakRelaxed(expected_word, new_word))) {
198         for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
199           const uint8_t expected_byte = expected_bytes[i];
200           const uint8_t new_byte = new_bytes[i];
201           if (expected_byte != new_byte) {
202             modified(reinterpret_cast<uint8_t*>(word_cur) + i, expected_byte, new_byte);
203           }
204         }
205         break;
206       }
207     }
208     ++word_cur;
209   }
210 }
211 
AddrFromCard(const uint8_t * card_addr)212 inline void* CardTable::AddrFromCard(const uint8_t *card_addr) const {
213   DCHECK(IsValidCard(card_addr))
214     << " card_addr: " << reinterpret_cast<const void*>(card_addr)
215     << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_)
216     << " end: " << reinterpret_cast<void*>(mem_map_.End());
217   uintptr_t offset = card_addr - biased_begin_;
218   return reinterpret_cast<void*>(offset << kCardShift);
219 }
220 
CardFromAddr(const void * addr)221 inline uint8_t* CardTable::CardFromAddr(const void *addr) const {
222   uint8_t *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift);
223   // Check that the caller was asking for an address covered by the card table.
224   DCHECK(IsValidCard(card_addr)) << "addr: " << addr
225       << " card_addr: " << reinterpret_cast<void*>(card_addr);
226   return card_addr;
227 }
228 
IsValidCard(const uint8_t * card_addr)229 inline bool CardTable::IsValidCard(const uint8_t* card_addr) const {
230   uint8_t* begin = mem_map_.Begin() + offset_;
231   uint8_t* end = mem_map_.End();
232   return card_addr >= begin && card_addr < end;
233 }
234 
CheckCardValid(uint8_t * card)235 inline void CardTable::CheckCardValid(uint8_t* card) const {
236   DCHECK(IsValidCard(card))
237       << " card_addr: " << reinterpret_cast<const void*>(card)
238       << " begin: " << reinterpret_cast<void*>(mem_map_.Begin() + offset_)
239       << " end: " << reinterpret_cast<void*>(mem_map_.End());
240 }
241 
242 }  // namespace accounting
243 }  // namespace gc
244 }  // namespace art
245 
246 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
247