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_H_ 18 #define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_ 19 20 #include <memory> 21 22 #include "base/locks.h" 23 #include "base/mem_map.h" 24 #include "base/utils.h" 25 #include "runtime_globals.h" 26 27 namespace art HIDDEN { 28 29 namespace mirror { 30 class Object; 31 } // namespace mirror 32 33 namespace gc { 34 35 namespace space { 36 class ContinuousSpace; 37 } // namespace space 38 39 class Heap; 40 41 namespace accounting { 42 43 template<size_t kAlignment> class SpaceBitmap; 44 45 // Maintain a card table from the the write barrier. All writes of 46 // non-null values to heap addresses should go through an entry in 47 // WriteBarrier, and from there to here. 48 class CardTable { 49 public: 50 static constexpr size_t kCardShift = 10; 51 static constexpr size_t kCardSize = 1 << kCardShift; 52 static constexpr uint8_t kCardClean = 0x0; 53 // Value written into the card by the write-barrier to indicate that 54 // reference(s) to some object starting in this card has been modified. 55 static constexpr uint8_t kCardDirty = 0x70; 56 // Value to indicate that a dirty card is 'aged' now in the sense that it has 57 // been noticed by the GC and will be visited. 58 static constexpr uint8_t kCardAged = kCardDirty - 1; 59 // Further ageing an aged card usually means clearing the card as we have 60 // already visited it when ageing it the first time. This value is used to 61 // avoid re-visiting (in the second pass of CMC marking phase) cards which 62 // contain old-to-young references and have not been dirtied since the first 63 // pass of marking. We can't simply clean these cards as they are needed later 64 // in compaction phase to update the old-to-young references. 65 static constexpr uint8_t kCardAged2 = kCardAged - 1; 66 67 static CardTable* Create(const uint8_t* heap_begin, size_t heap_capacity); 68 ~CardTable(); 69 70 // Set the card associated with the given address to `kCardDirty`. MarkCard(const void * addr)71 ALWAYS_INLINE void MarkCard(const void *addr) { 72 *CardFromAddr(addr) = kCardDirty; 73 } 74 75 // Is the object on a dirty card? IsDirty(const mirror::Object * obj)76 bool IsDirty(const mirror::Object* obj) const { 77 return GetCard(obj) == kCardDirty; 78 } 79 80 // Is the object on a clean card? IsClean(const mirror::Object * obj)81 bool IsClean(const mirror::Object* obj) const { 82 return GetCard(obj) == kCardClean; 83 } 84 85 // Return the state of the card at an address. GetCard(const mirror::Object * obj)86 uint8_t GetCard(const mirror::Object* obj) const { 87 return *CardFromAddr(obj); 88 } 89 90 // Visit and clear cards within memory range, only visits dirty cards. 91 template <typename Visitor> VisitClear(const void * start,const void * end,const Visitor & visitor)92 void VisitClear(const void* start, const void* end, const Visitor& visitor) { 93 uint8_t* card_start = CardFromAddr(start); 94 uint8_t* card_end = CardFromAddr(end); 95 for (uint8_t* it = card_start; it != card_end; ++it) { 96 if (*it == kCardDirty) { 97 *it = kCardClean; 98 visitor(it); 99 } 100 } 101 } 102 103 // Returns a value that when added to a heap address >> `kCardShift` will address the appropriate 104 // card table byte. For convenience this value is cached in every Thread. GetBiasedBegin()105 uint8_t* GetBiasedBegin() const { 106 return biased_begin_; 107 } 108 MemMapBegin()109 void* MemMapBegin() const { 110 return mem_map_.BaseBegin(); 111 } 112 MemMapSize()113 size_t MemMapSize() const { 114 return mem_map_.BaseSize(); 115 } 116 117 /* 118 * Modify cards in the range from scan_begin (inclusive) to scan_end (exclusive). Each card 119 * value v is replaced by visitor(v). Visitor() should not have side-effects. 120 * Whenever a card value is changed, modified(card_address, old_value, new_value) is invoked. 121 * For opportunistic performance reasons, this assumes that visitor(kCardClean) is kCardClean! 122 */ 123 template <typename Visitor, typename ModifiedVisitor> 124 void ModifyCardsAtomic(uint8_t* scan_begin, 125 uint8_t* scan_end, 126 const Visitor& visitor, 127 const ModifiedVisitor& modified); 128 129 // For every dirty (at least minimum age) card between begin and end invoke 130 // bitmap's VisitMarkedRange() to invoke 'visitor' on every object in the 131 // card. Calls 'mod_visitor' for each such card in case the caller wants to 132 // modify the value. Returns how many cards the visitor was run on. 133 // NOTE: 'visitor' is called on one whole card at a time. Therefore, 134 // 'scan_begin' and 'scan_end' are aligned to card-size before visitor is 135 // called. Therefore visitor may get called on objects before 'scan_begin' 136 // and/or after 'scan_end'. Visitor shall detect that and act appropriately. 137 template <bool kClearCard, typename Visitor, typename ModifyVisitor> 138 size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap, 139 uint8_t* scan_begin, 140 uint8_t* scan_end, 141 const Visitor& visitor, 142 const ModifyVisitor& mod_visitor, 143 const uint8_t minimum_age) REQUIRES(Locks::heap_bitmap_lock_) 144 REQUIRES_SHARED(Locks::mutator_lock_); 145 146 template <bool kClearCard, typename Visitor> 147 size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap, 148 uint8_t* scan_begin, 149 uint8_t* scan_end, 150 const Visitor& visitor, REQUIRES(Locks::heap_bitmap_lock_)151 const uint8_t minimum_age = kCardDirty) REQUIRES(Locks::heap_bitmap_lock_) 152 REQUIRES_SHARED(Locks::mutator_lock_) { 153 return Scan<kClearCard>(bitmap, scan_begin, scan_end, visitor, VoidFunctor(), minimum_age); 154 } 155 156 // Assertion used to check the given address is covered by the card table 157 void CheckAddrIsInCardTable(const uint8_t* addr) const; 158 159 // Resets all of the bytes in the card table to clean. 160 void ClearCardTable(); 161 162 // Clear a range of cards that covers start to end, start and end must be aligned to kCardSize. 163 void ClearCardRange(uint8_t* start, uint8_t* end); 164 165 // Returns the first address in the heap which maps to this card. 166 void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE; 167 168 // Returns the address of the relevant byte in the card table, given an address on the heap. 169 uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE; 170 171 bool AddrIsInCardTable(const void* addr) const; 172 173 private: 174 CardTable(MemMap&& mem_map, uint8_t* biased_begin, size_t offset); 175 176 // Returns true iff the card table address is within the bounds of the card table. 177 bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE; 178 179 void CheckCardValid(uint8_t* card) const ALWAYS_INLINE; 180 181 // Verifies that all gray objects are on a dirty card. 182 void VerifyCardTable(); 183 184 // Mmapped pages for the card table 185 MemMap mem_map_; 186 // Value used to compute card table addresses from object addresses, see GetBiasedBegin 187 uint8_t* const biased_begin_; 188 // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset 189 // to allow the byte value of `biased_begin_` to equal `kCardDirty`. 190 const size_t offset_; 191 192 DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable); 193 }; 194 195 } // namespace accounting 196 197 class AgeCardVisitor { 198 public: operator()199 uint8_t operator()(uint8_t card) const { 200 return (card == accounting::CardTable::kCardDirty) ? accounting::CardTable::kCardAged 201 : accounting::CardTable::kCardClean; 202 } 203 }; 204 205 } // namespace gc 206 } // namespace art 207 208 #endif // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_ 209