blob: 1553dd8adfa459cc7e107ea4a08f3e7577ecf923 [file] [log] [blame]
Elliott Hughes2faa5f12012-01-30 14:42:07 -08001/*
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 */
Carl Shapiro69759ea2011-07-21 18:13:35 -070016
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070017#include "mark_sweep.h"
Carl Shapiro69759ea2011-07-21 18:13:35 -070018
Carl Shapiro58551df2011-07-24 03:09:51 -070019#include <climits>
20#include <vector>
21
Elliott Hughes410c0c82011-09-01 17:58:25 -070022#include "class_loader.h"
Brian Carlstrom693267a2011-09-06 09:25:34 -070023#include "dex_cache.h"
Carl Shapiro58551df2011-07-24 03:09:51 -070024#include "heap.h"
Elliott Hughes410c0c82011-09-01 17:58:25 -070025#include "indirect_reference_table.h"
26#include "intern_table.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070027#include "logging.h"
28#include "macros.h"
29#include "mark_stack.h"
Elliott Hughesc33a32b2011-10-11 18:18:07 -070030#include "monitor.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070031#include "object.h"
Brian Carlstrom1f870082011-08-23 16:02:11 -070032#include "runtime.h"
Carl Shapiro58551df2011-07-24 03:09:51 -070033#include "space.h"
Elliott Hughes307f75d2011-10-12 18:04:40 -070034#include "timing_logger.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070035#include "thread.h"
Carl Shapiro69759ea2011-07-21 18:13:35 -070036
Carl Shapiro69759ea2011-07-21 18:13:35 -070037namespace art {
38
Jesse Wilson078f9b02011-11-18 17:51:47 -050039void MarkSweep::Init() {
Brian Carlstrom4a289ed2011-08-16 17:17:49 -070040 mark_stack_ = MarkStack::Create();
Elliott Hughesb3bd5f02012-03-08 21:05:27 -080041
42 heap_ = Runtime::Current()->GetHeap();
43 mark_bitmap_ = heap_->GetMarkBits();
44 live_bitmap_ = heap_->GetLiveBits();
Carl Shapiro58551df2011-07-24 03:09:51 -070045
46 // TODO: if concurrent, clear the card table.
47
buzbee0d966cf2011-09-08 17:34:58 -070048 // TODO: if concurrent, enable card marking in compiler
49
Carl Shapiro58551df2011-07-24 03:09:51 -070050 // TODO: check that the mark bitmap is entirely clear.
Carl Shapiro58551df2011-07-24 03:09:51 -070051}
52
Elliott Hughesb0663112011-10-19 18:16:37 -070053inline void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
Carl Shapiro69759ea2011-07-21 18:13:35 -070054 DCHECK(obj != NULL);
55 if (obj < condemned_) {
56 DCHECK(IsMarked(obj));
57 return;
58 }
59 bool is_marked = mark_bitmap_->Test(obj);
60 // This object was not previously marked.
61 if (!is_marked) {
62 mark_bitmap_->Set(obj);
63 if (check_finger && obj < finger_) {
64 // The object must be pushed on to the mark stack.
65 mark_stack_->Push(obj);
66 }
67 }
68}
69
70// Used to mark objects when recursing. Recursion is done by moving
71// the finger across the bitmaps in address order and marking child
72// objects. Any newly-marked objects whose addresses are lower than
73// the finger won't be visited by the bitmap scan, so those objects
74// need to be added to the mark stack.
Elliott Hughesb0663112011-10-19 18:16:37 -070075inline void MarkSweep::MarkObject(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -070076 if (obj != NULL) {
77 MarkObject0(obj, true);
78 }
79}
80
Elliott Hughescf4c6c42011-09-01 15:16:42 -070081void MarkSweep::MarkObjectVisitor(const Object* root, void* arg) {
Brian Carlstrom1f870082011-08-23 16:02:11 -070082 DCHECK(root != NULL);
83 DCHECK(arg != NULL);
84 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
Ian Rogers5d76c432011-10-31 21:42:49 -070085 DCHECK(mark_sweep->finger_ == NULL); // no point to check finger if it is NULL
86 mark_sweep->MarkObject0(root, false);
Brian Carlstrom1f870082011-08-23 16:02:11 -070087}
88
Carl Shapiro69759ea2011-07-21 18:13:35 -070089// Marks all objects in the root set.
90void MarkSweep::MarkRoots() {
Brian Carlstrom1f870082011-08-23 16:02:11 -070091 Runtime::Current()->VisitRoots(MarkObjectVisitor, this);
Carl Shapiro69759ea2011-07-21 18:13:35 -070092}
93
Ian Rogers5d76c432011-10-31 21:42:49 -070094void MarkSweep::ScanImageRootVisitor(Object* root, void* arg) {
95 DCHECK(root != NULL);
96 DCHECK(arg != NULL);
97 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
98 DCHECK(mark_sweep->finger_ == NULL); // no point to check finger if it is NULL
99 mark_sweep->MarkObject0(root, false);
100 mark_sweep->ScanObject(root);
101}
102
103// Marks all objects that are in images and have been touched by the mutator
104void MarkSweep::ScanDirtyImageRoots() {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800105 const std::vector<Space*>& spaces = heap_->GetSpaces();
106 CardTable* card_table = heap_->GetCardTable();
Ian Rogers5d76c432011-10-31 21:42:49 -0700107 for (size_t i = 0; i < spaces.size(); ++i) {
108 if (spaces[i]->IsImageSpace()) {
Ian Rogers30fab402012-01-23 15:43:46 -0800109 byte* begin = spaces[i]->Begin();
110 byte* end = spaces[i]->End();
111 card_table->Scan(begin, end, ScanImageRootVisitor, this);
Ian Rogers5d76c432011-10-31 21:42:49 -0700112 }
113 }
114}
115
116void MarkSweep::CheckBitmapCallback(Object* obj, void* finger, void* arg) {
117 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
118 mark_sweep->finger_ = reinterpret_cast<Object*>(finger);
119 mark_sweep->CheckObject(obj);
120}
121
Carl Shapiro58551df2011-07-24 03:09:51 -0700122void MarkSweep::ScanBitmapCallback(Object* obj, void* finger, void* arg) {
123 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
124 mark_sweep->finger_ = reinterpret_cast<Object*>(finger);
125 mark_sweep->ScanObject(obj);
126}
127
128// Populates the mark stack based on the set of marked objects and
129// recursively marks until the mark stack is emptied.
130void MarkSweep::RecursiveMark() {
Brian Carlstrom1f870082011-08-23 16:02:11 -0700131 // RecursiveMark will build the lists of known instances of the Reference classes.
132 // See DelayReferenceReferent for details.
133 CHECK(soft_reference_list_ == NULL);
134 CHECK(weak_reference_list_ == NULL);
135 CHECK(finalizer_reference_list_ == NULL);
136 CHECK(phantom_reference_list_ == NULL);
137 CHECK(cleared_reference_list_ == NULL);
138
Carl Shapiro58551df2011-07-24 03:09:51 -0700139 void* arg = reinterpret_cast<void*>(this);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800140 const std::vector<Space*>& spaces = heap_->GetSpaces();
Carl Shapiro58551df2011-07-24 03:09:51 -0700141 for (size_t i = 0; i < spaces.size(); ++i) {
TDYa127540a5b72012-04-03 18:56:08 -0700142#if !defined(ART_USE_LLVM_COMPILER)
Ian Rogers5d76c432011-10-31 21:42:49 -0700143#ifndef NDEBUG
Ian Rogers30fab402012-01-23 15:43:46 -0800144 uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
145 uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
Ian Rogers5d76c432011-10-31 21:42:49 -0700146 if (!spaces[i]->IsImageSpace()) {
Ian Rogers30fab402012-01-23 15:43:46 -0800147 mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
Elliott Hughesb25c3f62012-03-26 16:35:06 -0700148 } else {
Ian Rogers30fab402012-01-23 15:43:46 -0800149 mark_bitmap_->ScanWalk(begin, end, &MarkSweep::CheckBitmapCallback, arg);
Ian Rogers5d76c432011-10-31 21:42:49 -0700150 }
151#else
Elliott Hughes307f75d2011-10-12 18:04:40 -0700152 if (!spaces[i]->IsImageSpace()) {
Ian Rogers30fab402012-01-23 15:43:46 -0800153 uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
154 uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
155 mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
Carl Shapiro58551df2011-07-24 03:09:51 -0700156 }
Ian Rogers5d76c432011-10-31 21:42:49 -0700157#endif
TDYa127540a5b72012-04-03 18:56:08 -0700158#else
159 // TODO: Implement card marking.
160 uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
161 uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
162 mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
163#endif
Carl Shapiro58551df2011-07-24 03:09:51 -0700164 }
165 finger_ = reinterpret_cast<Object*>(~0);
Ian Rogers5d76c432011-10-31 21:42:49 -0700166 // TODO: tune the frequency of emptying the mark stack
Carl Shapiro58551df2011-07-24 03:09:51 -0700167 ProcessMarkStack();
168}
169
170void MarkSweep::ReMarkRoots() {
Elliott Hughes53b61312011-08-12 18:28:20 -0700171 UNIMPLEMENTED(FATAL);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700172}
173
Elliott Hughes410c0c82011-09-01 17:58:25 -0700174void MarkSweep::SweepJniWeakGlobals() {
175 JavaVMExt* vm = Runtime::Current()->GetJavaVM();
176 MutexLock mu(vm->weak_globals_lock);
177 IndirectReferenceTable* table = &vm->weak_globals;
178 typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto
179 for (It it = table->begin(), end = table->end(); it != end; ++it) {
180 const Object** entry = *it;
181 if (!IsMarked(*entry)) {
182 *entry = kClearedJniWeakGlobal;
183 }
184 }
185}
186
Elliott Hughes410c0c82011-09-01 17:58:25 -0700187void MarkSweep::SweepSystemWeaks() {
Elliott Hughesc33a32b2011-10-11 18:18:07 -0700188 Runtime::Current()->GetInternTable()->SweepInternTableWeaks(IsMarked, this);
189 Runtime::Current()->GetMonitorList()->SweepMonitorList(IsMarked, this);
Elliott Hughes410c0c82011-09-01 17:58:25 -0700190 SweepJniWeakGlobals();
Carl Shapiro58551df2011-07-24 03:09:51 -0700191}
192
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800193struct SweepCallbackContext {
194 Heap* heap;
195 AllocSpace* space;
196};
197
Ian Rogers30fab402012-01-23 15:43:46 -0800198void MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
Elliott Hughes362f9bc2011-10-17 18:56:41 -0700199 // TODO: lock heap if concurrent
Elliott Hughes307f75d2011-10-12 18:04:40 -0700200 size_t freed_objects = num_ptrs;
201 size_t freed_bytes = 0;
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800202 SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
203 Heap* heap = context->heap;
204 AllocSpace* space = context->space;
Ian Rogers5d76c432011-10-31 21:42:49 -0700205 // Use a bulk free, that merges consecutive objects before freeing or free per object?
206 // Documentation suggests better free performance with merging, but this may be at the expensive
207 // of allocation.
208 // TODO: investigate performance
Ian Rogers30fab402012-01-23 15:43:46 -0800209 static const bool kUseFreeList = true;
210 if (kUseFreeList) {
Ian Rogers5d76c432011-10-31 21:42:49 -0700211 for (size_t i = 0; i < num_ptrs; ++i) {
212 Object* obj = static_cast<Object*>(ptrs[i]);
Ian Rogers30fab402012-01-23 15:43:46 -0800213 freed_bytes += space->AllocationSize(obj);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800214 heap->GetLiveBits()->Clear(obj);
Ian Rogers5d76c432011-10-31 21:42:49 -0700215 }
Ian Rogers30fab402012-01-23 15:43:46 -0800216 // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
217 space->FreeList(num_ptrs, ptrs);
Ian Rogers5d76c432011-10-31 21:42:49 -0700218 } else {
219 for (size_t i = 0; i < num_ptrs; ++i) {
220 Object* obj = static_cast<Object*>(ptrs[i]);
Ian Rogers30fab402012-01-23 15:43:46 -0800221 freed_bytes += space->AllocationSize(obj);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800222 heap->GetLiveBits()->Clear(obj);
Ian Rogers30fab402012-01-23 15:43:46 -0800223 space->Free(obj);
Ian Rogers5d76c432011-10-31 21:42:49 -0700224 }
Carl Shapiro58551df2011-07-24 03:09:51 -0700225 }
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800226 heap->RecordFreeLocked(freed_objects, freed_bytes);
Elliott Hughes362f9bc2011-10-17 18:56:41 -0700227 // TODO: unlock heap if concurrent
Carl Shapiro58551df2011-07-24 03:09:51 -0700228}
229
230void MarkSweep::Sweep() {
Elliott Hughes2da50362011-10-10 16:57:08 -0700231 SweepSystemWeaks();
232
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800233 const std::vector<Space*>& spaces = heap_->GetSpaces();
234 SweepCallbackContext scc;
235 scc.heap = heap_;
Carl Shapiro58551df2011-07-24 03:09:51 -0700236 for (size_t i = 0; i < spaces.size(); ++i) {
Elliott Hughes307f75d2011-10-12 18:04:40 -0700237 if (!spaces[i]->IsImageSpace()) {
Ian Rogers30fab402012-01-23 15:43:46 -0800238 uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
239 uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800240 scc.space = spaces[i]->AsAllocSpace();
Ian Rogers30fab402012-01-23 15:43:46 -0800241 HeapBitmap::SweepWalk(*live_bitmap_, *mark_bitmap_, begin, end,
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800242 &MarkSweep::SweepCallback, reinterpret_cast<void*>(&scc));
Carl Shapiro58551df2011-07-24 03:09:51 -0700243 }
244 }
245}
246
Carl Shapiro69759ea2011-07-21 18:13:35 -0700247// Scans instance fields.
Elliott Hughesb0663112011-10-19 18:16:37 -0700248inline void MarkSweep::ScanInstanceFields(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700249 DCHECK(obj != NULL);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700250 Class* klass = obj->GetClass();
251 DCHECK(klass != NULL);
Elliott Hughes2da50362011-10-10 16:57:08 -0700252 ScanFields(obj, klass->GetReferenceInstanceOffsets(), false);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700253}
254
Ian Rogers5d76c432011-10-31 21:42:49 -0700255inline void MarkSweep::CheckInstanceFields(const Object* obj) {
256 Class* klass = obj->GetClass();
257 CheckFields(obj, klass->GetReferenceInstanceOffsets(), false);
258}
259
Brian Carlstrom4873d462011-08-21 15:23:39 -0700260// Scans static storage on a Class.
Elliott Hughesb0663112011-10-19 18:16:37 -0700261inline void MarkSweep::ScanStaticFields(const Class* klass) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700262 DCHECK(klass != NULL);
Elliott Hughesadb460d2011-10-05 17:02:34 -0700263 ScanFields(klass, klass->GetReferenceStaticOffsets(), true);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700264}
265
Ian Rogers5d76c432011-10-31 21:42:49 -0700266inline void MarkSweep::CheckStaticFields(const Class* klass) {
267 CheckFields(klass, klass->GetReferenceStaticOffsets(), true);
268}
269
Elliott Hughesb0663112011-10-19 18:16:37 -0700270inline void MarkSweep::ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700271 if (ref_offsets != CLASS_WALK_SUPER) {
272 // Found a reference offset bitmap. Mark the specified offsets.
273 while (ref_offsets != 0) {
274 size_t right_shift = CLZ(ref_offsets);
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700275 MemberOffset byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
276 const Object* ref = obj->GetFieldObject<const Object*>(byte_offset, false);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700277 MarkObject(ref);
278 ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift);
279 }
280 } else {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700281 // There is no reference offset bitmap. In the non-static case,
282 // walk up the class inheritance hierarchy and find reference
283 // offsets the hard way. In the static case, just consider this
284 // class.
285 for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700286 klass != NULL;
Brian Carlstrom4873d462011-08-21 15:23:39 -0700287 klass = is_static ? NULL : klass->GetSuperClass()) {
288 size_t num_reference_fields = (is_static
289 ? klass->NumReferenceStaticFields()
290 : klass->NumReferenceInstanceFields());
291 for (size_t i = 0; i < num_reference_fields; ++i) {
292 Field* field = (is_static
293 ? klass->GetStaticField(i)
294 : klass->GetInstanceField(i));
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700295 MemberOffset field_offset = field->GetOffset();
296 const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700297 MarkObject(ref);
298 }
299 }
300 }
301}
302
Ian Rogers5d76c432011-10-31 21:42:49 -0700303inline void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800304 AllocSpace* alloc_space = heap_->GetAllocSpace();
Ian Rogers5d76c432011-10-31 21:42:49 -0700305 if (alloc_space->Contains(ref)) {
306 bool is_marked = mark_bitmap_->Test(ref);
Elliott Hughesb25c3f62012-03-26 16:35:06 -0700307 if (!is_marked) {
Ian Rogers30fab402012-01-23 15:43:46 -0800308 LOG(INFO) << *alloc_space;
309 LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref)
Elliott Hughes398f64b2012-03-26 18:05:48 -0700310 << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj)
311 << "' (" << reinterpret_cast<const void*>(obj) << ") at offset "
312 << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked";
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800313 bool obj_marked = heap_->GetCardTable()->IsDirty(obj);
Ian Rogers5d76c432011-10-31 21:42:49 -0700314 if (!obj_marked) {
Elliott Hughes398f64b2012-03-26 18:05:48 -0700315 LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' "
316 << "(" << reinterpret_cast<const void*>(obj) << ") contains references to "
317 << "the alloc space, but wasn't card marked";
Ian Rogers5d76c432011-10-31 21:42:49 -0700318 }
319 }
320 }
321}
322
323inline void MarkSweep::CheckFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
324 if (ref_offsets != CLASS_WALK_SUPER) {
325 // Found a reference offset bitmap. Mark the specified offsets.
326 while (ref_offsets != 0) {
327 size_t right_shift = CLZ(ref_offsets);
328 MemberOffset field_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
329 const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
330 CheckReference(obj, ref, field_offset, is_static);
331 ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift);
332 }
333 } else {
334 // There is no reference offset bitmap. In the non-static case,
335 // walk up the class inheritance hierarchy and find reference
336 // offsets the hard way. In the static case, just consider this
337 // class.
338 for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
339 klass != NULL;
340 klass = is_static ? NULL : klass->GetSuperClass()) {
341 size_t num_reference_fields = (is_static
342 ? klass->NumReferenceStaticFields()
343 : klass->NumReferenceInstanceFields());
344 for (size_t i = 0; i < num_reference_fields; ++i) {
345 Field* field = (is_static
346 ? klass->GetStaticField(i)
347 : klass->GetInstanceField(i));
348 MemberOffset field_offset = field->GetOffset();
349 const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
350 CheckReference(obj, ref, field_offset, is_static);
351 }
352 }
353 }
354}
355
Carl Shapiro69759ea2011-07-21 18:13:35 -0700356// Scans the header, static field references, and interface pointers
357// of a class object.
Elliott Hughesb0663112011-10-19 18:16:37 -0700358inline void MarkSweep::ScanClass(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700359#ifndef NDEBUG
360 ++class_count_;
361#endif
Brian Carlstrom693267a2011-09-06 09:25:34 -0700362 ScanInstanceFields(obj);
Brian Carlstrom40381fb2011-10-19 14:13:40 -0700363 ScanStaticFields(obj->AsClass());
Carl Shapiro69759ea2011-07-21 18:13:35 -0700364}
365
Ian Rogers5d76c432011-10-31 21:42:49 -0700366inline void MarkSweep::CheckClass(const Object* obj) {
367 CheckInstanceFields(obj);
368 CheckStaticFields(obj->AsClass());
369}
370
Carl Shapiro69759ea2011-07-21 18:13:35 -0700371// Scans the header of all array objects. If the array object is
372// specialized to a reference type, scans the array data as well.
Elliott Hughesb0663112011-10-19 18:16:37 -0700373inline void MarkSweep::ScanArray(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700374#ifndef NDEBUG
375 ++array_count_;
376#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700377 MarkObject(obj->GetClass());
378 if (obj->IsObjectArray()) {
Brian Carlstromdb4d5402011-08-09 12:18:28 -0700379 const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
Elliott Hughesd8ddfd52011-08-15 14:32:53 -0700380 for (int32_t i = 0; i < array->GetLength(); ++i) {
Ian Rogers5d76c432011-10-31 21:42:49 -0700381 const Object* element = array->GetWithoutChecks(i);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700382 MarkObject(element);
383 }
384 }
385}
386
Ian Rogers5d76c432011-10-31 21:42:49 -0700387inline void MarkSweep::CheckArray(const Object* obj) {
388 CheckReference(obj, obj->GetClass(), Object::ClassOffset(), false);
389 if (obj->IsObjectArray()) {
390 const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
391 for (int32_t i = 0; i < array->GetLength(); ++i) {
392 const Object* element = array->GetWithoutChecks(i);
Ian Rogersa15e67d2012-02-28 13:51:55 -0800393 size_t width = sizeof(Object*);
394 CheckReference(obj, element, MemberOffset(i * width +
395 Array::DataOffset(width).Int32Value()), false);
Ian Rogers5d76c432011-10-31 21:42:49 -0700396 }
397 }
398}
399
Carl Shapiro69759ea2011-07-21 18:13:35 -0700400// Process the "referent" field in a java.lang.ref.Reference. If the
401// referent has not yet been marked, put it on the appropriate list in
402// the gcHeap for later processing.
403void MarkSweep::DelayReferenceReferent(Object* obj) {
404 DCHECK(obj != NULL);
Brian Carlstrom1f870082011-08-23 16:02:11 -0700405 Class* klass = obj->GetClass();
406 DCHECK(klass != NULL);
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700407 DCHECK(klass->IsReferenceClass());
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800408 Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false);
409 Object* referent = heap_->GetReferenceReferent(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700410 if (pending == NULL && referent != NULL && !IsMarked(referent)) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700411 Object** list = NULL;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700412 if (klass->IsSoftReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700413 list = &soft_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700414 } else if (klass->IsWeakReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700415 list = &weak_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700416 } else if (klass->IsFinalizerReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700417 list = &finalizer_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700418 } else if (klass->IsPhantomReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700419 list = &phantom_reference_list_;
420 }
Brian Carlstrom0796af02011-10-12 14:31:45 -0700421 DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags();
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800422 heap_->EnqueuePendingReference(obj, list);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700423 }
424}
425
426// Scans the header and field references of a data object. If the
427// scanned object is a reference subclass, it is scheduled for later
Elliott Hughesadb460d2011-10-05 17:02:34 -0700428// processing.
Elliott Hughesb0663112011-10-19 18:16:37 -0700429inline void MarkSweep::ScanOther(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700430#ifndef NDEBUG
431 ++other_count_;
432#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700433 ScanInstanceFields(obj);
Elliott Hughes352a4242011-10-31 15:15:21 -0700434 if (obj->GetClass()->IsReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700435 DelayReferenceReferent(const_cast<Object*>(obj));
436 }
437}
438
Ian Rogers5d76c432011-10-31 21:42:49 -0700439inline void MarkSweep::CheckOther(const Object* obj) {
440 CheckInstanceFields(obj);
441}
442
Carl Shapiro69759ea2011-07-21 18:13:35 -0700443// Scans an object reference. Determines the type of the reference
444// and dispatches to a specialized scanning routine.
Elliott Hughesb0663112011-10-19 18:16:37 -0700445inline void MarkSweep::ScanObject(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700446 DCHECK(obj != NULL);
447 DCHECK(obj->GetClass() != NULL);
448 DCHECK(IsMarked(obj));
449 if (obj->IsClass()) {
450 ScanClass(obj);
Brian Carlstromb63ec392011-08-27 17:38:27 -0700451 } else if (obj->IsArrayInstance()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700452 ScanArray(obj);
453 } else {
Carl Shapiro58551df2011-07-24 03:09:51 -0700454 ScanOther(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700455 }
456}
457
Ian Rogers5d76c432011-10-31 21:42:49 -0700458// Check to see that all alloc space references are marked for the given object
459inline void MarkSweep::CheckObject(const Object* obj) {
460 DCHECK(obj != NULL);
461 DCHECK(obj->GetClass() != NULL);
462 DCHECK(IsMarked(obj));
463 if (obj->IsClass()) {
464 CheckClass(obj);
465 } else if (obj->IsArrayInstance()) {
466 CheckArray(obj);
467 } else {
468 CheckOther(obj);
469 }
470}
471
472// Scan anything that's on the mark stack.
Carl Shapiro69759ea2011-07-21 18:13:35 -0700473void MarkSweep::ProcessMarkStack() {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800474 Space* alloc_space = heap_->GetAllocSpace();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700475 while (!mark_stack_->IsEmpty()) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700476 const Object* obj = mark_stack_->Pop();
Ian Rogers5d76c432011-10-31 21:42:49 -0700477 if (alloc_space->Contains(obj)) {
478 ScanObject(obj);
479 }
Carl Shapiro69759ea2011-07-21 18:13:35 -0700480 }
481}
482
483void MarkSweep::ScanDirtyObjects() {
484 ProcessMarkStack();
485}
486
Carl Shapiro69759ea2011-07-21 18:13:35 -0700487// Walks the reference list marking any references subject to the
488// reference clearing policy. References with a black referent are
489// removed from the list. References with white referents biased
490// toward saving are blackened and also removed from the list.
491void MarkSweep::PreserveSomeSoftReferences(Object** list) {
492 DCHECK(list != NULL);
493 Object* clear = NULL;
494 size_t counter = 0;
495 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800496 Object* ref = heap_->DequeuePendingReference(list);
497 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700498 if (referent == NULL) {
499 // Referent was cleared by the user during marking.
500 continue;
501 }
502 bool is_marked = IsMarked(referent);
503 if (!is_marked && ((++counter) & 1)) {
504 // Referent is white and biased toward saving, mark it.
505 MarkObject(referent);
506 is_marked = true;
507 }
508 if (!is_marked) {
509 // Referent is white, queue it for clearing.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800510 heap_->EnqueuePendingReference(ref, &clear);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700511 }
512 }
513 *list = clear;
514 // Restart the mark with the newly black references added to the
515 // root set.
516 ProcessMarkStack();
517}
518
519// Unlink the reference list clearing references objects with white
520// referents. Cleared references registered to a reference queue are
521// scheduled for appending by the heap worker thread.
522void MarkSweep::ClearWhiteReferences(Object** list) {
523 DCHECK(list != NULL);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700524 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800525 Object* ref = heap_->DequeuePendingReference(list);
526 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700527 if (referent != NULL && !IsMarked(referent)) {
528 // Referent is white, clear it.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800529 heap_->ClearReferenceReferent(ref);
530 if (heap_->IsEnqueuable(ref)) {
531 heap_->EnqueueReference(ref, &cleared_reference_list_);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700532 }
533 }
534 }
535 DCHECK(*list == NULL);
536}
537
538// Enqueues finalizer references with white referents. White
539// referents are blackened, moved to the zombie field, and the
540// referent field is cleared.
541void MarkSweep::EnqueueFinalizerReferences(Object** list) {
542 DCHECK(list != NULL);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800543 MemberOffset zombie_offset = heap_->GetFinalizerReferenceZombieOffset();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700544 bool has_enqueued = false;
545 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800546 Object* ref = heap_->DequeuePendingReference(list);
547 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700548 if (referent != NULL && !IsMarked(referent)) {
549 MarkObject(referent);
550 // If the referent is non-null the reference must queuable.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800551 DCHECK(heap_->IsEnqueuable(ref));
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700552 ref->SetFieldObject(zombie_offset, referent, false);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800553 heap_->ClearReferenceReferent(ref);
554 heap_->EnqueueReference(ref, &cleared_reference_list_);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700555 has_enqueued = true;
556 }
557 }
558 if (has_enqueued) {
559 ProcessMarkStack();
560 }
561 DCHECK(*list == NULL);
562}
563
Carl Shapiro58551df2011-07-24 03:09:51 -0700564// Process reference class instances and schedule finalizations.
Carl Shapiro69759ea2011-07-21 18:13:35 -0700565void MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft,
566 Object** weak_references,
567 Object** finalizer_references,
568 Object** phantom_references) {
569 DCHECK(soft_references != NULL);
570 DCHECK(weak_references != NULL);
571 DCHECK(finalizer_references != NULL);
572 DCHECK(phantom_references != NULL);
573
574 // Unless we are in the zygote or required to clear soft references
575 // with white references, preserve some white referents.
576 if (clear_soft) {
577 PreserveSomeSoftReferences(soft_references);
578 }
579
580 // Clear all remaining soft and weak references with white
581 // referents.
582 ClearWhiteReferences(soft_references);
583 ClearWhiteReferences(weak_references);
584
585 // Preserve all white objects with finalize methods and schedule
586 // them for finalization.
587 EnqueueFinalizerReferences(finalizer_references);
588
589 // Clear all f-reachable soft and weak references with white
590 // referents.
591 ClearWhiteReferences(soft_references);
592 ClearWhiteReferences(weak_references);
593
594 // Clear all phantom references with white referents.
595 ClearWhiteReferences(phantom_references);
596
597 // At this point all reference lists should be empty.
598 DCHECK(*soft_references == NULL);
599 DCHECK(*weak_references == NULL);
600 DCHECK(*finalizer_references == NULL);
601 DCHECK(*phantom_references == NULL);
602}
603
Carl Shapiro69759ea2011-07-21 18:13:35 -0700604MarkSweep::~MarkSweep() {
Elliott Hughes352a4242011-10-31 15:15:21 -0700605#ifndef NDEBUG
Elliott Hughes4dd9b4d2011-12-12 18:29:24 -0800606 VLOG(heap) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ << " other=" << other_count_;
Elliott Hughes352a4242011-10-31 15:15:21 -0700607#endif
Carl Shapiro58551df2011-07-24 03:09:51 -0700608 delete mark_stack_;
Carl Shapiro69759ea2011-07-21 18:13:35 -0700609 mark_bitmap_->Clear();
610}
611
612} // namespace art