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/mutex.h" 23 #include "globals.h" 24 25 namespace art { 26 27 class MemMap; 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 static constexpr uint8_t kCardDirty = 0x70; 54 static constexpr uint8_t kCardAged = kCardDirty - 1; 55 56 static CardTable* Create(const uint8_t* heap_begin, size_t heap_capacity); 57 ~CardTable(); 58 59 // Set the card associated with the given address to GC_CARD_DIRTY. MarkCard(const void * addr)60 ALWAYS_INLINE void MarkCard(const void *addr) { 61 *CardFromAddr(addr) = kCardDirty; 62 } 63 64 // Is the object on a dirty card? IsDirty(const mirror::Object * obj)65 bool IsDirty(const mirror::Object* obj) const { 66 return GetCard(obj) == kCardDirty; 67 } 68 69 // Return the state of the card at an address. GetCard(const mirror::Object * obj)70 uint8_t GetCard(const mirror::Object* obj) const { 71 return *CardFromAddr(obj); 72 } 73 74 // Visit and clear cards within memory range, only visits dirty cards. 75 template <typename Visitor> VisitClear(const void * start,const void * end,const Visitor & visitor)76 void VisitClear(const void* start, const void* end, const Visitor& visitor) { 77 uint8_t* card_start = CardFromAddr(start); 78 uint8_t* card_end = CardFromAddr(end); 79 for (uint8_t* it = card_start; it != card_end; ++it) { 80 if (*it == kCardDirty) { 81 *it = kCardClean; 82 visitor(it); 83 } 84 } 85 } 86 87 // Returns a value that when added to a heap address >> GC_CARD_SHIFT will address the appropriate 88 // card table byte. For convenience this value is cached in every Thread GetBiasedBegin()89 uint8_t* GetBiasedBegin() const { 90 return biased_begin_; 91 } 92 93 /* 94 * Visitor is expected to take in a card and return the new value. When a value is modified, the 95 * modify visitor is called. 96 * visitor: The visitor which modifies the cards. Returns the new value for a card given an old 97 * value. 98 * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables 99 * us to know which cards got cleared. 100 */ 101 template <typename Visitor, typename ModifiedVisitor> 102 void ModifyCardsAtomic(uint8_t* scan_begin, 103 uint8_t* scan_end, 104 const Visitor& visitor, 105 const ModifiedVisitor& modified); 106 107 // For every dirty at least minumum age between begin and end invoke the visitor with the 108 // specified argument. Returns how many cards the visitor was run on. 109 template <bool kClearCard, typename Visitor> 110 size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap, 111 uint8_t* scan_begin, 112 uint8_t* scan_end, 113 const Visitor& visitor, 114 const uint8_t minimum_age = kCardDirty) 115 REQUIRES(Locks::heap_bitmap_lock_) 116 REQUIRES_SHARED(Locks::mutator_lock_); 117 118 // Assertion used to check the given address is covered by the card table 119 void CheckAddrIsInCardTable(const uint8_t* addr) const; 120 121 // Resets all of the bytes in the card table to clean. 122 void ClearCardTable(); 123 124 // Clear a range of cards that covers start to end, start and end must be aligned to kCardSize. 125 void ClearCardRange(uint8_t* start, uint8_t* end); 126 127 // Returns the first address in the heap which maps to this card. 128 void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE; 129 130 // Returns the address of the relevant byte in the card table, given an address on the heap. 131 uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE; 132 133 bool AddrIsInCardTable(const void* addr) const; 134 135 private: 136 CardTable(MemMap* begin, uint8_t* biased_begin, size_t offset); 137 138 // Returns true iff the card table address is within the bounds of the card table. 139 bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE; 140 141 void CheckCardValid(uint8_t* card) const ALWAYS_INLINE; 142 143 // Verifies that all gray objects are on a dirty card. 144 void VerifyCardTable(); 145 146 // Mmapped pages for the card table 147 std::unique_ptr<MemMap> mem_map_; 148 // Value used to compute card table addresses from object addresses, see GetBiasedBegin 149 uint8_t* const biased_begin_; 150 // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset 151 // to allow the byte value of biased_begin_ to equal GC_CARD_DIRTY 152 const size_t offset_; 153 154 DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable); 155 }; 156 157 } // namespace accounting 158 159 class AgeCardVisitor { 160 public: operator()161 uint8_t operator()(uint8_t card) const { 162 return (card == accounting::CardTable::kCardDirty) ? card - 1 : 0; 163 } 164 }; 165 166 } // namespace gc 167 } // namespace art 168 169 #endif // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_ 170