1 /* 2 * Copyright (C) 2012 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_MOD_UNION_TABLE_H_ 18 #define ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_ 19 20 #include "bitmap.h" 21 #include "base/allocator.h" 22 #include "card_table.h" 23 #include "globals.h" 24 #include "mirror/object_reference.h" 25 #include "safe_map.h" 26 27 #include <set> 28 #include <vector> 29 30 namespace art { 31 32 namespace mirror { 33 class Object; 34 } // namespace mirror 35 36 class MarkObjectVisitor; 37 38 namespace gc { 39 namespace space { 40 class ContinuousSpace; 41 } // namespace space 42 43 class Heap; 44 45 namespace accounting { 46 47 // The mod-union table is the union of modified cards. It is used to allow the card table to be 48 // cleared between GC phases, reducing the number of dirty cards that need to be scanned. 49 class ModUnionTable { 50 public: 51 // A callback for visiting an object in the heap. 52 using ObjectCallback = void (*)(mirror::Object*, void*); 53 54 typedef std::set<uint8_t*, std::less<uint8_t*>, 55 TrackingAllocator<uint8_t*, kAllocatorTagModUnionCardSet>> CardSet; 56 typedef MemoryRangeBitmap<CardTable::kCardSize> CardBitmap; 57 58 explicit ModUnionTable(const std::string& name, Heap* heap, space::ContinuousSpace* space) 59 : name_(name), 60 heap_(heap), 61 space_(space) {} 62 63 virtual ~ModUnionTable() {} 64 65 // Process cards for a memory range of a space. This doesn't immediately update the mod-union 66 // table, as updating the mod-union table may have an associated cost, such as determining 67 // references to track. 68 virtual void ProcessCards() = 0; 69 70 // Set all the cards. 71 virtual void SetCards() = 0; 72 73 // Clear all of the table. 74 virtual void ClearTable() = 0; 75 76 // Update the mod-union table using data stored by ProcessCards. There may be multiple 77 // ProcessCards before a call to update, for example, back-to-back sticky GCs. Also mark 78 // references to other spaces which are stored in the mod-union table. 79 virtual void UpdateAndMarkReferences(MarkObjectVisitor* visitor) = 0; 80 81 // Visit all of the objects that may contain references to other spaces. 82 virtual void VisitObjects(ObjectCallback callback, void* arg) = 0; 83 84 // Verification, sanity checks that we don't have clean cards which conflict with out cached data 85 // for said cards. Exclusive lock is required since verify sometimes uses 86 // SpaceBitmap::VisitMarkedRange and VisitMarkedRange can't know if the callback will modify the 87 // bitmap or not. 88 virtual void Verify() REQUIRES(Locks::heap_bitmap_lock_) = 0; 89 90 // Returns true if a card is marked inside the mod union table. Used for testing. The address 91 // doesn't need to be aligned. 92 virtual bool ContainsCardFor(uintptr_t addr) = 0; 93 94 // Filter out cards that don't need to be marked. Automatically done with UpdateAndMarkReferences. 95 void FilterCards(); 96 97 virtual void Dump(std::ostream& os) = 0; 98 99 space::ContinuousSpace* GetSpace() { 100 return space_; 101 } 102 103 Heap* GetHeap() const { 104 return heap_; 105 } 106 107 const std::string& GetName() const { 108 return name_; 109 } 110 111 protected: 112 const std::string name_; 113 Heap* const heap_; 114 space::ContinuousSpace* const space_; 115 }; 116 117 // Reference caching implementation. Caches references pointing to alloc space(s) for each card. 118 class ModUnionTableReferenceCache : public ModUnionTable { 119 public: 120 explicit ModUnionTableReferenceCache(const std::string& name, Heap* heap, 121 space::ContinuousSpace* space) 122 : ModUnionTable(name, heap, space) {} 123 124 virtual ~ModUnionTableReferenceCache() {} 125 126 // Clear and store cards for a space. 127 void ProcessCards() OVERRIDE; 128 129 // Update table based on cleared cards and mark all references to the other spaces. 130 void UpdateAndMarkReferences(MarkObjectVisitor* visitor) OVERRIDE 131 REQUIRES_SHARED(Locks::mutator_lock_) 132 REQUIRES(Locks::heap_bitmap_lock_); 133 134 virtual void VisitObjects(ObjectCallback callback, void* arg) OVERRIDE 135 REQUIRES(Locks::heap_bitmap_lock_) 136 REQUIRES_SHARED(Locks::mutator_lock_); 137 138 // Exclusive lock is required since verify uses SpaceBitmap::VisitMarkedRange and 139 // VisitMarkedRange can't know if the callback will modify the bitmap or not. 140 void Verify() OVERRIDE 141 REQUIRES_SHARED(Locks::mutator_lock_) 142 REQUIRES(Locks::heap_bitmap_lock_); 143 144 // Function that tells whether or not to add a reference to the table. 145 virtual bool ShouldAddReference(const mirror::Object* ref) const = 0; 146 147 virtual bool ContainsCardFor(uintptr_t addr) OVERRIDE; 148 149 virtual void Dump(std::ostream& os) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_); 150 151 virtual void SetCards() OVERRIDE; 152 153 virtual void ClearTable() OVERRIDE; 154 155 protected: 156 // Cleared card array, used to update the mod-union table. 157 ModUnionTable::CardSet cleared_cards_; 158 159 // Maps from dirty cards to their corresponding alloc space references. 160 AllocationTrackingSafeMap<const uint8_t*, std::vector<mirror::HeapReference<mirror::Object>*>, 161 kAllocatorTagModUnionReferenceArray> references_; 162 }; 163 164 // Card caching implementation. Keeps track of which cards we cleared and only this information. 165 class ModUnionTableCardCache : public ModUnionTable { 166 public: 167 // Note: There is assumption that the space End() doesn't change. 168 explicit ModUnionTableCardCache(const std::string& name, Heap* heap, 169 space::ContinuousSpace* space); 170 171 virtual ~ModUnionTableCardCache() {} 172 173 // Clear and store cards for a space. 174 virtual void ProcessCards() OVERRIDE; 175 176 // Mark all references to the alloc space(s). 177 virtual void UpdateAndMarkReferences(MarkObjectVisitor* visitor) OVERRIDE 178 REQUIRES(Locks::heap_bitmap_lock_) 179 REQUIRES_SHARED(Locks::mutator_lock_); 180 181 virtual void VisitObjects(ObjectCallback callback, void* arg) OVERRIDE 182 REQUIRES(Locks::heap_bitmap_lock_) 183 REQUIRES_SHARED(Locks::mutator_lock_); 184 185 // Nothing to verify. 186 virtual void Verify() OVERRIDE {} 187 188 virtual void Dump(std::ostream& os) OVERRIDE; 189 190 virtual bool ContainsCardFor(uintptr_t addr) OVERRIDE; 191 192 virtual void SetCards() OVERRIDE; 193 194 virtual void ClearTable() OVERRIDE; 195 196 protected: 197 // Cleared card bitmap, used to update the mod-union table. 198 std::unique_ptr<CardBitmap> card_bitmap_; 199 }; 200 201 } // namespace accounting 202 } // namespace gc 203 } // namespace art 204 205 #endif // ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_ 206