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