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/locks.h"
23 #include "base/mem_map.h"
24 #include "runtime_globals.h"
25 
26 namespace art {
27 
28 namespace mirror {
29 class Object;
30 }  // namespace mirror
31 
32 namespace gc {
33 
34 namespace space {
35 class ContinuousSpace;
36 }  // namespace space
37 
38 class Heap;
39 
40 namespace accounting {
41 
42 template<size_t kAlignment> class SpaceBitmap;
43 
44 // Maintain a card table from the the write barrier. All writes of
45 // non-null values to heap addresses should go through an entry in
46 // WriteBarrier, and from there to here.
47 class CardTable {
48  public:
49   static constexpr size_t kCardShift = 10;
50   static constexpr size_t kCardSize = 1 << kCardShift;
51   static constexpr uint8_t kCardClean = 0x0;
52   static constexpr uint8_t kCardDirty = 0x70;
53   static constexpr uint8_t kCardAged = kCardDirty - 1;
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 `kCardDirty`.
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   // Is the object on a clean card?
IsClean(const mirror::Object * obj)69   bool IsClean(const mirror::Object* obj) const {
70     return GetCard(obj) == kCardClean;
71   }
72 
73   // Return the state of the card at an address.
GetCard(const mirror::Object * obj)74   uint8_t GetCard(const mirror::Object* obj) const {
75     return *CardFromAddr(obj);
76   }
77 
78   // Visit and clear cards within memory range, only visits dirty cards.
79   template <typename Visitor>
VisitClear(const void * start,const void * end,const Visitor & visitor)80   void VisitClear(const void* start, const void* end, const Visitor& visitor) {
81     uint8_t* card_start = CardFromAddr(start);
82     uint8_t* card_end = CardFromAddr(end);
83     for (uint8_t* it = card_start; it != card_end; ++it) {
84       if (*it == kCardDirty) {
85         *it = kCardClean;
86         visitor(it);
87       }
88     }
89   }
90 
91   // Returns a value that when added to a heap address >> `kCardShift` will address the appropriate
92   // card table byte. For convenience this value is cached in every Thread.
GetBiasedBegin()93   uint8_t* GetBiasedBegin() const {
94     return biased_begin_;
95   }
96 
MemMapBegin()97   void* MemMapBegin() const {
98     return mem_map_.BaseBegin();
99   }
100 
MemMapSize()101   size_t MemMapSize() const {
102     return mem_map_.BaseSize();
103   }
104 
105   /*
106    * Modify cards in the range from scan_begin (inclusive) to scan_end (exclusive). Each card
107    * value v is replaced by visitor(v). Visitor() should not have side-effects.
108    * Whenever a card value is changed, modified(card_address, old_value, new_value) is invoked.
109    * For opportunistic performance reasons, this assumes that visitor(kCardClean) is kCardClean!
110    */
111   template <typename Visitor, typename ModifiedVisitor>
112   void ModifyCardsAtomic(uint8_t* scan_begin,
113                          uint8_t* scan_end,
114                          const Visitor& visitor,
115                          const ModifiedVisitor& modified);
116 
117   // For every dirty at least minumum age between begin and end invoke the visitor with the
118   // specified argument. Returns how many cards the visitor was run on.
119   template <bool kClearCard, typename Visitor>
120   size_t Scan(SpaceBitmap<kObjectAlignment>* bitmap,
121               uint8_t* scan_begin,
122               uint8_t* scan_end,
123               const Visitor& visitor,
124               const uint8_t minimum_age = kCardDirty)
125       REQUIRES(Locks::heap_bitmap_lock_)
126       REQUIRES_SHARED(Locks::mutator_lock_);
127 
128   // Assertion used to check the given address is covered by the card table
129   void CheckAddrIsInCardTable(const uint8_t* addr) const;
130 
131   // Resets all of the bytes in the card table to clean.
132   void ClearCardTable();
133 
134   // Clear a range of cards that covers start to end, start and end must be aligned to kCardSize.
135   void ClearCardRange(uint8_t* start, uint8_t* end);
136 
137   // Returns the first address in the heap which maps to this card.
138   void* AddrFromCard(const uint8_t *card_addr) const ALWAYS_INLINE;
139 
140   // Returns the address of the relevant byte in the card table, given an address on the heap.
141   uint8_t* CardFromAddr(const void *addr) const ALWAYS_INLINE;
142 
143   bool AddrIsInCardTable(const void* addr) const;
144 
145  private:
146   CardTable(MemMap&& mem_map, uint8_t* biased_begin, size_t offset);
147 
148   // Returns true iff the card table address is within the bounds of the card table.
149   bool IsValidCard(const uint8_t* card_addr) const ALWAYS_INLINE;
150 
151   void CheckCardValid(uint8_t* card) const ALWAYS_INLINE;
152 
153   // Verifies that all gray objects are on a dirty card.
154   void VerifyCardTable();
155 
156   // Mmapped pages for the card table
157   MemMap mem_map_;
158   // Value used to compute card table addresses from object addresses, see GetBiasedBegin
159   uint8_t* const biased_begin_;
160   // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset
161   // to allow the byte value of `biased_begin_` to equal `kCardDirty`.
162   const size_t offset_;
163 
164   DISALLOW_IMPLICIT_CONSTRUCTORS(CardTable);
165 };
166 
167 }  // namespace accounting
168 
169 class AgeCardVisitor {
170  public:
operator()171   uint8_t operator()(uint8_t card) const {
172     return (card == accounting::CardTable::kCardDirty) ? card - 1 : 0;
173   }
174 };
175 
176 }  // namespace gc
177 }  // namespace art
178 
179 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_H_
180