mod_union_table.h revision ef7d42fca18c16fbaf103822ad16f23246e2905d 
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 "gc_allocator.h"
21#include "globals.h"
22#include "root_visitor.h"
23#include "safe_map.h"
24
25#include <set>
26#include <vector>
27
28namespace art {
29namespace mirror {
30  class Object;
31}  // namespace mirror
32
33namespace gc {
34
35namespace collector {
36  class MarkSweep;
37}  // namespace collector
38namespace space {
39  class ContinuousSpace;
40  class Space;
41}  // namespace space
42
43class Heap;
44
45namespace accounting {
46
47class SpaceBitmap;
48class HeapBitmap;
49
50// The mod-union table is the union of modified cards. It is used to allow the card table to be
51// cleared between GC phases, reducing the number of dirty cards that need to be scanned.
52class ModUnionTable {
53 public:
54  typedef std::set<byte*, std::less<byte*>, GcAllocator<byte*> > CardSet;
55
56  explicit ModUnionTable(const std::string& name, Heap* heap, space::ContinuousSpace* space)
57      : name_(name),
58        heap_(heap),
59        space_(space) {
60  }
61
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(RootVisitor visitor, 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;
81  space::ContinuousSpace* GetSpace() {
82    return space_;
83  }
84  Heap* GetHeap() const {
85    return heap_;
86  }
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.
98class ModUnionTableReferenceCache : public ModUnionTable {
99 public:
100  explicit ModUnionTableReferenceCache(const std::string& name, Heap* heap,
101                                       space::ContinuousSpace* space)
102      : ModUnionTable(name, heap, space) {}
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(RootVisitor visitor, 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 AddReference(const mirror::Object* obj, const mirror::Object* ref) = 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  SafeMap<const byte*, std::vector<mirror::HeapReference<mirror::Object>*>, std::less<const byte*>,
130      GcAllocator<std::pair<const byte*, std::vector<mirror::HeapReference<mirror::Object>*> > > >
131      references_;
132};
133
134// Card caching implementation. Keeps track of which cards we cleared and only this information.
135class ModUnionTableCardCache : public ModUnionTable {
136 public:
137  explicit ModUnionTableCardCache(const std::string& name, Heap* heap, space::ContinuousSpace* space)
138      : ModUnionTable(name, heap, space) {}
139  virtual ~ModUnionTableCardCache() {}
140
141  // Clear and store cards for a space.
142  void ClearCards();
143
144  // Mark all references to the alloc space(s).
145  void UpdateAndMarkReferences(RootVisitor visitor, void* arg)
146      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
147      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
148
149  // Nothing to verify.
150  void Verify() {}
151
152  void Dump(std::ostream& os);
153
154 protected:
155  // Cleared card array, used to update the mod-union table.
156  CardSet cleared_cards_;
157};
158
159}  // namespace accounting
160}  // namespace gc
161}  // namespace art
162
163#endif  // ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
164