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