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 "globals.h"
22#include "object_callbacks.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 HeapBitmap;
48
49// The mod-union table is the union of modified cards. It is used to allow the card table to be
50// cleared between GC phases, reducing the number of dirty cards that need to be scanned.
51class ModUnionTable {
52 public:
53  typedef std::set<byte*, std::less<byte*>,
54                   TrackingAllocator<byte*, kAllocatorTagModUnionCardSet>> 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(MarkHeapReferenceCallback* callback, 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(MarkHeapReferenceCallback* callback, 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 ShouldAddReference(const mirror::Object* ref) const = 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  AllocationTrackingSafeMap<const byte*, std::vector<mirror::HeapReference<mirror::Object>*>,
130                            kAllocatorTagModUnionReferenceArray> references_;
131};
132
133// Card caching implementation. Keeps track of which cards we cleared and only this information.
134class ModUnionTableCardCache : public ModUnionTable {
135 public:
136  explicit ModUnionTableCardCache(const std::string& name, Heap* heap, space::ContinuousSpace* space)
137      : ModUnionTable(name, heap, space) {}
138  virtual ~ModUnionTableCardCache() {}
139
140  // Clear and store cards for a space.
141  void ClearCards();
142
143  // Mark all references to the alloc space(s).
144  void UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg)
145      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
146      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
147
148  // Nothing to verify.
149  void Verify() {}
150
151  void Dump(std::ostream& os);
152
153 protected:
154  // Cleared card array, used to update the mod-union table.
155  CardSet cleared_cards_;
156};
157
158}  // namespace accounting
159}  // namespace gc
160}  // namespace art
161
162#endif  // ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
163