1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
/*
* Copyright (C) 2010 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* Needed for PROT_* definitions.
*/
#include <sys/mman.h>
#include "Dalvik.h"
#include "alloc/HeapSource.h"
#include "alloc/Visit.h"
/*
* Maintain a card table from the the write barrier. All writes of
* non-NULL values to heap addresses should go through an entry in
* WriteBarrier, and from there to here.
*
* The heap is divided into "cards" of GC_CARD_SIZE bytes, as
* determined by GC_CARD_SHIFT. The card table contains one byte of
* data per card, to be used by the GC. The value of the byte will be
* one of GC_CARD_CLEAN or GC_CARD_DIRTY.
*
* After any store of a non-NULL object pointer into a heap object,
* code is obliged to mark the card dirty. The setters in
* ObjectInlines.h [such as dvmSetFieldObject] do this for you. The
* JIT and fast interpreters also contain code to mark cards as dirty.
*
* [TODO: Concurrent collection will have to expand on this, as it
* uses the card table as well.]
*
* The card table is used to support partial collection, which at the
* moment means "treat the zygote's heap as permanent, and only GC
* objects in the application heap". In order to do this efficiently,
* the GC need to find quickly references to objects in the
* application heap from the zygote heap. When an application creates
* an object and stores it into an object on the zygote heap, it will
* mark the corresponding card in the zygote heap as "dirty". When the
* GC does a partial collection, it can efficiently find all the
* cross-heap objects, since they are all on dirty cards. The GC also
* takes the opportunity to mark as "clean" any cards which are dirty,
* but no longer contain cross-heap pointers.
*
* The card table's base [the "biased card table"] gets set to a
* rather strange value. In order to keep the JIT from having to
* fabricate or load GC_DIRTY_CARD to store into the card table,
* biased base is within the mmap allocation at a point where it's low
* byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details.
*/
/*
* Initializes the card table; must be called before any other
* dvmCardTable*() functions.
*/
bool dvmCardTableStartup(GcHeap *gcHeap, void *heapBase)
{
size_t length;
void *allocBase;
u1 *biasedBase;
/* Set up the card table */
length = gDvm.heapSizeMax / GC_CARD_SIZE;
/* Allocate an extra 256 bytes to allow fixed low-byte of base */
allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE,
"dalvik-card-table");
if (allocBase == NULL) {
return false;
}
gcHeap->cardTableBase = allocBase;
gcHeap->cardTableLength = length;
/* All zeros is the correct initial value; all clean. */
assert(GC_CARD_CLEAN == 0);
biasedBase = (u1 *)((uintptr_t)allocBase -
((uintptr_t)heapBase >> GC_CARD_SHIFT));
if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) {
int offset;
offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff);
biasedBase += offset + (offset < 0 ? 0x100 : 0);
}
assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY);
gDvm.biasedCardTableBase = biasedBase;
return true;
}
/*
* Tears down the entire CardTable.
*/
void dvmCardTableShutdown()
{
munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
}
/*
* Returns true iff the address is within the bounds of the card table.
*/
bool dvmIsValidCard(const u1 *cardAddr)
{
GcHeap *h = gDvm.gcHeap;
return cardAddr >= h->cardTableBase &&
cardAddr < &h->cardTableBase[h->cardTableLength];
}
/*
* Returns the address of the relevent byte in the card table, given
* an address on the heap.
*/
u1 *dvmCardFromAddr(const void *addr)
{
u1 *biasedBase = gDvm.biasedCardTableBase;
u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT);
assert(dvmIsValidCard(cardAddr));
return cardAddr;
}
/*
* Returns the first address in the heap which maps to this card.
*/
void *dvmAddrFromCard(const u1 *cardAddr)
{
assert(dvmIsValidCard(cardAddr));
uintptr_t offset = cardAddr - gDvm.biasedCardTableBase;
return (void *)(offset << GC_CARD_SHIFT);
}
/*
* Dirties the card for the given address.
*/
void dvmMarkCard(const void *addr)
{
u1 *cardAddr = dvmCardFromAddr(addr);
*cardAddr = GC_CARD_DIRTY;
}
/*
* Returns true iff all address within the Object are on unmarked cards.
*/
static bool objectIsClean(const Object *obj)
{
assert(dvmIsValidObject(obj));
size_t size = dvmHeapSourceChunkSize(obj);
u1 *start = dvmCardFromAddr(obj);
u1 *end = dvmCardFromAddr((char *)obj + size-1);
u1 *index;
for (index = start; index <= end; index++) {
if (*index != GC_CARD_CLEAN) {
return false;
}
}
return true;
}
/*
* A Visitor callback in support of checkCleanObjects. "arg" is
* expected to be the immuneLimit.
*/
static void crossGenCheckVisitor(void *ptr, void *arg)
{
Object *ref = *(Object **)ptr;
Object *immuneLimit = (Object *)arg;
if (ref >= immuneLimit) {
LOGE("Clean obj contains threatened ref %p: %p", ptr, ref);
dvmAbort();
}
}
/*
* A HeapBitmap callback in support of checkCleanObjects.
*/
static bool crossGenCheckCallback(size_t numPtrs, void **ptrs,
const void *finger, void *arg)
{
size_t i;
for (i = 0; i < numPtrs; i++) {
Object *obj = ptrs[i];
if (objectIsClean(obj)) {
dvmVisitObject(crossGenCheckVisitor, obj, arg);
}
}
return true;
}
/*
* dvmAbort if a clean, immune Object in the bitmap contains a pointer
* to a threatened Object.
*/
void dvmVerifyCardTable(HeapBitmap *bitmap, const char *immuneLimit)
{
dvmHeapBitmapWalk(bitmap, crossGenCheckCallback, (void *)immuneLimit);
}
|
