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