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