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 "runtime_globals.h" 25 26 namespace art { 27 28 namespace mirror { 29 class Object; 30 } // namespace mirror 31 32 namespace gc { 33 34 namespace space { 35 class ContinuousSpace; 36 } // namespace space 37 38 class Heap; 39 40 namespace accounting { 41 42 template<size_t kAlignment> class SpaceBitmap; 43 44 // Maintain a card table from the the write barrier. All writes of 45 // non-null values to heap addresses should go through an entry in 46 // WriteBarrier, and from there to here. 47 class CardTable { 48 public: 49 static constexpr size_t kCardShift = 10; 50 static constexpr size_t kCardSize = 1 << kCardShift; 51 static constexpr uint8_t kCardClean = 0x0; 52 static constexpr uint8_t kCardDirty = 0x70; 53 static constexpr uint8_t kCardAged = kCardDirty - 1; 54 55 static CardTable* Create(const uint8_t* heap_begin, size_t heap_capacity); 56 ~CardTable(); 57 58 // Set the card associated with the given address to `kCardDirty`. MarkCard(const void * addr)59 ALWAYS_INLINE void MarkCard(const void *addr) { 60 *CardFromAddr(addr) = kCardDirty; 61 } 62 63 // Is the object on a dirty card? IsDirty(const mirror::Object * obj)64 bool IsDirty(const mirror::Object* obj) const { 65 return GetCard(obj) == kCardDirty; 66 } 67 68 // Is the object on a clean card? IsClean(const mirror::Object * obj)69 bool IsClean(const mirror::Object* obj) const { 70 return GetCard(obj) == kCardClean; 71 } 72 73 // Return the state of the card at an address. GetCard(const mirror::Object * obj)74 uint8_t GetCard(const mirror::Object* obj) const { 75 return *CardFromAddr(obj); 76 } 77 78 // Visit and clear cards within memory range, only visits dirty cards. 79 template <typename Visitor> VisitClear(const void * start,const void * end,const Visitor & visitor)80 void VisitClear(const void* start, const void* end, const Visitor& visitor) { 81 uint8_t* card_start = CardFromAddr(start); 82 uint8_t* card_end = CardFromAddr(end); 83 for (uint8_t* it = card_start; it != card_end; ++it) { 84 if (*it == kCardDirty) { 85 *it = kCardClean; 86 visitor(it); 87 } 88 } 89 } 90 91 // Returns a value that when added to a heap address >> `kCardShift` will address the appropriate 92 // card table byte. For convenience this value is cached in every Thread. GetBiasedBegin()93 uint8_t* GetBiasedBegin() const { 94 return biased_begin_; 95 } 96 MemMapBegin()97 void* MemMapBegin() const { 98 return mem_map_.BaseBegin(); 99 } 100 MemMapSize()101 size_t MemMapSize() const { 102 return mem_map_.BaseSize(); 103 } 104 105 /* 106 * Modify cards in the range from scan_begin (inclusive) to scan_end (exclusive). Each card 107 * value v is replaced by visitor(v). Visitor() should not have side-effects. 108 * Whenever a card value is changed, modified(card_address, old_value, new_value) is invoked. 109 * For opportunistic performance reasons, this assumes that visitor(kCardClean) is kCardClean! 110 */ 111 template <typename Visitor, typename ModifiedVisitor> 112 void ModifyCardsAtomic(uint8_t* scan_begin, 113 uint8_t* scan_end, 114 const Visitor& visitor, 115 const ModifiedVisitor& modified); 116 117 // For every dirty at least minumum age between begin and end invoke the visitor with the 118 // specified argument. Returns how many cards the visitor was run on. 119 template <bool kClearCard, typename Visitor> 120 size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap, 121 uint8_t* scan_begin, 122 uint8_t* scan_end, 123 const Visitor& visitor, 124 const uint8_t minimum_age = kCardDirty) 125 REQUIRES(Locks::heap_bitmap_lock_) 126 REQUIRES_SHARED(Locks::mutator_lock_); 127 128 // Assertion used to check the given address is covered by the card table 129 void CheckAddrIsInCardTable(const uint8_t* addr) const; 130 131 // Resets all of the bytes in the card table to clean. 132 void ClearCardTable(); 133 134 // Clear a range of cards that covers start to end, start and end must be aligned to kCardSize. 135 void ClearCardRange(uint8_t* start, uint8_t* end); 136 137 // Returns the first address in the heap which maps to this card. 138 void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE; 139 140 // Returns the address of the relevant byte in the card table, given an address on the heap. 141 uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE; 142 143 bool AddrIsInCardTable(const void* addr) const; 144 145 private: 146 CardTable(MemMap&& mem_map, uint8_t* biased_begin, size_t offset); 147 148 // Returns true iff the card table address is within the bounds of the card table. 149 bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE; 150 151 void CheckCardValid(uint8_t* card) const ALWAYS_INLINE; 152 153 // Verifies that all gray objects are on a dirty card. 154 void VerifyCardTable(); 155 156 // Mmapped pages for the card table 157 MemMap mem_map_; 158 // Value used to compute card table addresses from object addresses, see GetBiasedBegin 159 uint8_t* const biased_begin_; 160 // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset 161 // to allow the byte value of `biased_begin_` to equal `kCardDirty`. 162 const size_t offset_; 163 164 DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable); 165 }; 166 167 } // namespace accounting 168 169 class AgeCardVisitor { 170 public: operator()171 uint8_t operator()(uint8_t card) const { 172 return (card == accounting::CardTable::kCardDirty) ? card - 1 : 0; 173 } 174 }; 175 176 } // namespace gc 177 } // namespace art 178 179 #endif // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_ 180