blob: a6284e3887de4d03cc079df337fe493391306f44 [file] [log] [blame]
Ian Rogers5d76c432011-10-31 21:42:49 -07001/*
Elliott Hughes2faa5f12012-01-30 14:42:07 -08002 * 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.
Ian Rogers5d76c432011-10-31 21:42:49 -070015 */
16
17#ifndef DALVIK_ALLOC_CARDTABLE_H_
18#define DALVIK_ALLOC_CARDTABLE_H_
19
20#include "globals.h"
21#include "logging.h"
22#include "mem_map.h"
Mathieu Chartiercc236d72012-07-20 10:29:05 -070023#include "space_bitmap.h"
Ian Rogers5d76c432011-10-31 21:42:49 -070024#include "UniquePtr.h"
25
26namespace art {
27
Mathieu Chartier262e5ff2012-06-01 17:35:38 -070028class Heap;
Mathieu Chartiercc236d72012-07-20 10:29:05 -070029class Space;
Mathieu Chartierb062fdd2012-07-03 09:51:48 -070030class SpaceBitmap;
Ian Rogers5d76c432011-10-31 21:42:49 -070031class Object;
32
33#define GC_CARD_SHIFT 7
34#define GC_CARD_SIZE (1 << GC_CARD_SHIFT)
35#define GC_CARD_CLEAN 0
36#define GC_CARD_DIRTY 0x70
37
Elliott Hughes2faa5f12012-01-30 14:42:07 -080038// Maintain a card table from the the write barrier. All writes of
39// non-NULL values to heap addresses should go through an entry in
40// WriteBarrier, and from there to here.
Ian Rogers5d76c432011-10-31 21:42:49 -070041class CardTable {
42 public:
Ian Rogers30fab402012-01-23 15:43:46 -080043 static CardTable* Create(const byte* heap_begin, size_t heap_capacity);
Ian Rogers5d76c432011-10-31 21:42:49 -070044
Ian Rogers30fab402012-01-23 15:43:46 -080045 // Set the card associated with the given address to GC_CARD_DIRTY.
Ian Rogers5d76c432011-10-31 21:42:49 -070046 void MarkCard(const void *addr) {
Elliott Hughes24edeb52012-06-18 15:29:46 -070047 byte* card_addr = CardFromAddr(addr);
48 *card_addr = GC_CARD_DIRTY;
Ian Rogers5d76c432011-10-31 21:42:49 -070049 }
50
Ian Rogers30fab402012-01-23 15:43:46 -080051 // Is the object on a dirty card?
Ian Rogers5d76c432011-10-31 21:42:49 -070052 bool IsDirty(const Object* obj) const {
53 return *CardFromAddr(obj) == GC_CARD_DIRTY;
54 }
55
Mathieu Chartierb43b7d42012-06-19 13:15:09 -070056 // Visit cards within memory range.
57 template <typename Visitor>
58 void VisitClear(const void* start, const void* end, const Visitor& visitor) {
59 byte* card_start = CardFromAddr(start);
60 byte* card_end = CardFromAddr(end);
61 for (byte* cur = card_start; cur != card_end; ++cur) {
62 if (*cur == GC_CARD_DIRTY) {
63 *cur = GC_CARD_CLEAN;
64 visitor(cur);
65 }
66 }
67 }
68
Ian Rogers30fab402012-01-23 15:43:46 -080069 // Returns a value that when added to a heap address >> GC_CARD_SHIFT will address the appropriate
70 // card table byte. For convenience this value is cached in every Thread
71 byte* GetBiasedBegin() const {
72 return biased_begin_;
jeffhao39da0352011-11-04 14:58:55 -070073 }
74
Mathieu Chartiercc236d72012-07-20 10:29:05 -070075 // For every dirty card between begin and end invoke the visitor with the specified argument.
Mathieu Chartier357e9be2012-08-01 11:00:14 -070076 template <typename Visitor, typename FingerVisitor>
77 void Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_end,
78 const Visitor& visitor, const FingerVisitor& finger_visitor) const
Ian Rogers00f7d0e2012-07-19 15:28:27 -070079 EXCLUSIVE_LOCKS_REQUIRED(GlobalSynchronization::heap_bitmap_lock_)
80 SHARED_LOCKS_REQUIRED(GlobalSynchronization::mutator_lock_) {
Mathieu Chartiercc236d72012-07-20 10:29:05 -070081 DCHECK(bitmap->HasAddress(scan_begin));
82 DCHECK(bitmap->HasAddress(scan_end - 1)); // scan_end is the byte after the last byte we scan.
83 byte* card_cur = CardFromAddr(scan_begin);
84 byte* card_end = CardFromAddr(scan_end);
85 while (card_cur < card_end) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -070086 // Find the first dirty card.
87 card_cur = reinterpret_cast<byte*>(memchr(card_cur, GC_CARD_DIRTY, card_end - card_cur));
88 if (card_cur == NULL) {
89 break;
Mathieu Chartiercc236d72012-07-20 10:29:05 -070090 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -070091 byte* run_start = card_cur++;
Mathieu Chartiercc236d72012-07-20 10:29:05 -070092
Mathieu Chartierfd678be2012-08-30 14:50:54 -070093 while (*card_cur == GC_CARD_DIRTY && card_cur < card_end) {
Mathieu Chartiercc236d72012-07-20 10:29:05 -070094 card_cur++;
95 }
96 byte* run_end = card_cur;
97
Mathieu Chartier357e9be2012-08-01 11:00:14 -070098 uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(run_start));
99 uintptr_t end = reinterpret_cast<uintptr_t>(AddrFromCard(run_end));
100 bitmap->VisitMarkedRange(start, end, visitor, finger_visitor);
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700101 }
102 }
Ian Rogers30fab402012-01-23 15:43:46 -0800103
Ian Rogers30fab402012-01-23 15:43:46 -0800104 // Assertion used to check the given address is covered by the card table
105 void CheckAddrIsInCardTable(const byte* addr) const;
106
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700107 // Resets all of the bytes in the card table to clean.
108 void ClearCardTable();
109
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700110 // Resets all of the bytes in the card table which do not map to the image space.
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700111 void ClearSpaceCards(Space* space);
Ian Rogers5d76c432011-10-31 21:42:49 -0700112
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700113 // Clean all the cards which map to a space.
114 void PreClearCards(Space* space, std::vector<byte*>& out_cards);
115
116 // Returns all of the dirty cards which map to a space.
117 void GetDirtyCards(Space* space, std::vector<byte*>& out_cards) const;
118
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700119 // Returns the first address in the heap which maps to this card.
120 void* AddrFromCard(const byte *card_addr) const {
121 DCHECK(IsValidCard(card_addr))
122 << " card_addr: " << reinterpret_cast<const void*>(card_addr)
123 << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
124 << " end: " << reinterpret_cast<void*>(mem_map_->End());
125 uintptr_t offset = card_addr - biased_begin_;
126 return reinterpret_cast<void*>(offset << GC_CARD_SHIFT);
127 }
Ian Rogers5d76c432011-10-31 21:42:49 -0700128
Ian Rogers30fab402012-01-23 15:43:46 -0800129 // Returns the address of the relevant byte in the card table, given an address on the heap.
Ian Rogers5d76c432011-10-31 21:42:49 -0700130 byte* CardFromAddr(const void *addr) const {
Elliott Hughes24edeb52012-06-18 15:29:46 -0700131 byte *card_addr = biased_begin_ + ((uintptr_t)addr >> GC_CARD_SHIFT);
Ian Rogers30fab402012-01-23 15:43:46 -0800132 // Sanity check the caller was asking for address covered by the card table
Elliott Hughes24edeb52012-06-18 15:29:46 -0700133 DCHECK(IsValidCard(card_addr)) << "addr: " << addr
134 << " card_addr: " << reinterpret_cast<void*>(card_addr);
135 return card_addr;
Ian Rogers5d76c432011-10-31 21:42:49 -0700136 }
137
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700138 private:
139 CardTable(MemMap* begin, byte* biased_begin, size_t offset);
140
Ian Rogers30fab402012-01-23 15:43:46 -0800141 // Returns true iff the card table address is within the bounds of the card table.
Elliott Hughes24edeb52012-06-18 15:29:46 -0700142 bool IsValidCard(const byte* card_addr) const {
Ian Rogers30fab402012-01-23 15:43:46 -0800143 byte* begin = mem_map_->Begin() + offset_;
144 byte* end = mem_map_->End();
Elliott Hughes24edeb52012-06-18 15:29:46 -0700145 return card_addr >= begin && card_addr < end;
Ian Rogers5d76c432011-10-31 21:42:49 -0700146 }
147
Ian Rogers30fab402012-01-23 15:43:46 -0800148 // Verifies that all gray objects are on a dirty card.
Ian Rogers5d76c432011-10-31 21:42:49 -0700149 void VerifyCardTable();
150
Ian Rogers30fab402012-01-23 15:43:46 -0800151 // Mmapped pages for the card table
Ian Rogers5d76c432011-10-31 21:42:49 -0700152 UniquePtr<MemMap> mem_map_;
Ian Rogers30fab402012-01-23 15:43:46 -0800153 // Value used to compute card table addresses from object addresses, see GetBiasedBegin
154 byte* const biased_begin_;
155 // Card table doesn't begin at the beginning of the mem_map_, instead it is displaced by offset
156 // to allow the byte value of biased_begin_ to equal GC_CARD_DIRTY
157 const size_t offset_;
Ian Rogers5d76c432011-10-31 21:42:49 -0700158};
159
160} // namespace art
161#endif // DALVIK_ALLOC_CARDTABLE_H_