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