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,
102                          uint8_t* scan_end,
103                          const Visitor& visitor,
104                          const ModifiedVisitor& modified);
105 
106   // For every dirty at least minumum age between begin and end invoke the visitor with the
107   // specified argument. Returns how many cards the visitor was run on.
108   template <bool kClearCard, typename Visitor>
109   size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap,
110               uint8_t* scan_begin,
111               uint8_t* scan_end,
112               const Visitor& visitor,
113               const uint8_t minimum_age = kCardDirty)
114       REQUIRES(Locks::heap_bitmap_lock_)
115       REQUIRES_SHARED(Locks::mutator_lock_);
116 
117   // Assertion used to check the given address is covered by the card table
118   void CheckAddrIsInCardTable(const uint8_t* addr) const;
119 
120   // Resets all of the bytes in the card table to clean.
121   void ClearCardTable();
122 
123   // Clear a range of cards that covers start to end, start and end must be aligned to kCardSize.
124   void ClearCardRange(uint8_t* start, uint8_t* end);
125 
126   // Returns the first address in the heap which maps to this card.
127   void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE;
128 
129   // Returns the address of the relevant byte in the card table, given an address on the heap.
130   uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE;
131 
132   bool AddrIsInCardTable(const void* addr) const;
133 
134  private:
135   CardTable(MemMap* begin, uint8_t* biased_begin, size_t offset);
136 
137   // Returns true iff the card table address is within the bounds of the card table.
138   bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE;
139 
140   void CheckCardValid(uint8_t* card) const ALWAYS_INLINE;
141 
142   // Verifies that all gray objects are on a dirty card.
143   void VerifyCardTable();
144 
145   // Mmapped pages for the card table
146   std::unique_ptr<MemMap> mem_map_;
147   // Value used to compute card table addresses from object addresses, see GetBiasedBegin
148   uint8_t* const biased_begin_;
149   // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset
150   // to allow the byte value of biased_begin_ to equal GC_CARD_DIRTY
151   const size_t offset_;
152 
153   DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable);
154 };
155 
156 }  // namespace accounting
157 }  // namespace gc
158 }  // namespace art
159 
160 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_
161