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