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