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