1 /*
2  * Copyright (C) 2011 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_CARD_TABLE_H_
18 #define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_
19 
20 #include <memory>
21 
22 #include "base/mutex.h"
23 #include "globals.h"
24 
25 namespace art {
26 
27 class MemMap;
28 
29 namespace mirror {
30   class Object;
31 }  // namespace mirror
32 
33 namespace gc {
34 
35 namespace space {
36   class ContinuousSpace;
37 }  // namespace space
38 
39 class Heap;
40 
41 namespace accounting {
42 
43 template<size_t kAlignment> class SpaceBitmap;
44 
45 // Maintain a card table from the the write barrier. All writes of
46 // non-null values to heap addresses should go through an entry in
47 // WriteBarrier, and from there to here.
48 class CardTable {
49  public:
50   static constexpr size_t kCardShift = 7;
51   static constexpr size_t kCardSize = 1 << kCardShift;
52   static constexpr uint8_t kCardClean = 0x0;
53   static constexpr uint8_t kCardDirty = 0x70;
54 
55   static CardTable* Create(const uint8_t* heap_begin, size_t heap_capacity);
56   ~CardTable();
57 
58   // Set the card associated with the given address to GC_CARD_DIRTY.
MarkCard(const void * addr)59   ALWAYS_INLINE void MarkCard(const void *addr) {
60     *CardFromAddr(addr) = kCardDirty;
61   }
62 
63   // Is the object on a dirty card?
IsDirty(const mirror::Object * obj)64   bool IsDirty(const mirror::Object* obj) const {
65     return GetCard(obj) == kCardDirty;
66   }
67 
68   // Return the state of the card at an address.
GetCard(const mirror::Object * obj)69   uint8_t GetCard(const mirror::Object* obj) const {
70     return *CardFromAddr(obj);
71   }
72 
73   // Visit and clear cards within memory range, only visits dirty cards.
74   template <typename Visitor>
VisitClear(const void * start,const void * end,const Visitor & visitor)75   void VisitClear(const void* start, const void* end, const Visitor& visitor) {
76     uint8_t* card_start = CardFromAddr(start);
77     uint8_t* card_end = CardFromAddr(end);
78     for (uint8_t* it = card_start; it != card_end; ++it) {
79       if (*it == kCardDirty) {
80         *it = kCardClean;
81         visitor(it);
82       }
83     }
84   }
85 
86   // Returns a value that when added to a heap address >> GC_CARD_SHIFT will address the appropriate
87   // card table byte. For convenience this value is cached in every Thread
GetBiasedBegin()88   uint8_t* GetBiasedBegin() const {
89     return biased_begin_;
90   }
91 
92   /*
93    * Visitor is expected to take in a card and return the new value. When a value is modified, the
94    * modify visitor is called.
95    * visitor: The visitor which modifies the cards. Returns the new value for a card given an old
96    * value.
97    * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables
98    * us to know which cards got cleared.
99    */
100   template <typename Visitor, typename ModifiedVisitor>
101   void ModifyCardsAtomic(uint8_t* scan_begin, uint8_t* scan_end, const Visitor& visitor,
102                          const ModifiedVisitor& modified);
103 
104   // For every dirty at least minumum age between begin and end invoke the visitor with the
105   // specified argument. Returns how many cards the visitor was run on.
106   template <bool kClearCard, typename Visitor>
107   size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap, uint8_t* scan_begin, uint8_t* scan_end,
108               const Visitor& visitor,
109               const uint8_t minimum_age = kCardDirty) const
110       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
111       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
112 
113   // Assertion used to check the given address is covered by the card table
114   void CheckAddrIsInCardTable(const uint8_t* addr) const;
115 
116   // Resets all of the bytes in the card table to clean.
117   void ClearCardTable();
118   void ClearCardRange(uint8_t* start, uint8_t* end);
119 
120   // Resets all of the bytes in the card table which do not map to the image space.
121   void ClearSpaceCards(space::ContinuousSpace* space);
122 
123   // Returns the first address in the heap which maps to this card.
124   void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE;
125 
126   // Returns the address of the relevant byte in the card table, given an address on the heap.
127   uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE;
128 
129   bool AddrIsInCardTable(const void* addr) const;
130 
131  private:
132   CardTable(MemMap* begin, uint8_t* biased_begin, size_t offset);
133 
134   // Returns true iff the card table address is within the bounds of the card table.
135   bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE;
136 
137   void CheckCardValid(uint8_t* card) const ALWAYS_INLINE;
138 
139   // Verifies that all gray objects are on a dirty card.
140   void VerifyCardTable();
141 
142   // Mmapped pages for the card table
143   std::unique_ptr<MemMap> mem_map_;
144   // Value used to compute card table addresses from object addresses, see GetBiasedBegin
145   uint8_t* const biased_begin_;
146   // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset
147   // to allow the byte value of biased_begin_ to equal GC_CARD_DIRTY
148   const size_t offset_;
149 
150   DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable);
151 };
152 
153 }  // namespace accounting
154 }  // namespace gc
155 }  // namespace art
156 
157 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_
158