blob: cf496059c27b38913b41d3ac4c3d725bd0960818 [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
Mathieu Chartier357e9be2012-08-01 11:00:14 -070022#include "card_table.h"
Elliott Hughes410c0c82011-09-01 17:58:25 -070023#include "class_loader.h"
Brian Carlstrom693267a2011-09-06 09:25:34 -070024#include "dex_cache.h"
Carl Shapiro58551df2011-07-24 03:09:51 -070025#include "heap.h"
Elliott Hughes410c0c82011-09-01 17:58:25 -070026#include "indirect_reference_table.h"
27#include "intern_table.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070028#include "logging.h"
29#include "macros.h"
30#include "mark_stack.h"
Elliott Hughesc33a32b2011-10-11 18:18:07 -070031#include "monitor.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070032#include "object.h"
Brian Carlstrom1f870082011-08-23 16:02:11 -070033#include "runtime.h"
Carl Shapiro58551df2011-07-24 03:09:51 -070034#include "space.h"
Elliott Hughes307f75d2011-10-12 18:04:40 -070035#include "timing_logger.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070036#include "thread.h"
Carl Shapiro69759ea2011-07-21 18:13:35 -070037
Mathieu Chartier357e9be2012-08-01 11:00:14 -070038#define MARK_STACK_PREFETCH 1
39
Carl Shapiro69759ea2011-07-21 18:13:35 -070040namespace art {
41
Mathieu Chartier357e9be2012-08-01 11:00:14 -070042class SetFingerVisitor {
43 public:
44 SetFingerVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
45
46 }
47
48 void operator ()(void* finger) const {
49 mark_sweep_->SetFinger(reinterpret_cast<Object*>(finger));
50 }
51
52 private:
53 MarkSweep* const mark_sweep_;
54};
55
Mathieu Chartier5301cd22012-05-31 12:11:36 -070056MarkSweep::MarkSweep(MarkStack* mark_stack)
Mathieu Chartierb062fdd2012-07-03 09:51:48 -070057 : current_mark_bitmap_(NULL),
58 mark_stack_(mark_stack),
Mathieu Chartier5301cd22012-05-31 12:11:36 -070059 heap_(NULL),
Mathieu Chartier5301cd22012-05-31 12:11:36 -070060 finger_(NULL),
61 condemned_(NULL),
62 soft_reference_list_(NULL),
63 weak_reference_list_(NULL),
64 finalizer_reference_list_(NULL),
65 phantom_reference_list_(NULL),
66 cleared_reference_list_(NULL),
Mathieu Chartier357e9be2012-08-01 11:00:14 -070067 freed_bytes_(0), freed_objects_(0),
Mathieu Chartier5301cd22012-05-31 12:11:36 -070068 class_count_(0), array_count_(0), other_count_(0) {
69 DCHECK(mark_stack_ != NULL);
70}
Elliott Hughesb3bd5f02012-03-08 21:05:27 -080071
Mathieu Chartier5301cd22012-05-31 12:11:36 -070072void MarkSweep::Init() {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -080073 heap_ = Runtime::Current()->GetHeap();
Mathieu Chartier5301cd22012-05-31 12:11:36 -070074 mark_stack_->Reset();
Carl Shapiro58551df2011-07-24 03:09:51 -070075
Mathieu Chartierb062fdd2012-07-03 09:51:48 -070076 const Spaces& spaces = heap_->GetSpaces();
77 // TODO: C++0x auto
78 for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -070079 if (current_mark_bitmap_ == NULL || (*cur)->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) {
Mathieu Chartierb062fdd2012-07-03 09:51:48 -070080 current_mark_bitmap_ = (*cur)->GetMarkBitmap();
81 break;
82 }
83 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -070084 if (current_mark_bitmap_ == NULL) {
85 GetHeap()->DumpSpaces();
86 DCHECK(false) << "current_mark_bitmap_ == NULL";
87 }
buzbee0d966cf2011-09-08 17:34:58 -070088 // TODO: if concurrent, enable card marking in compiler
Carl Shapiro58551df2011-07-24 03:09:51 -070089 // TODO: check that the mark bitmap is entirely clear.
Carl Shapiro58551df2011-07-24 03:09:51 -070090}
91
Mathieu Chartier357e9be2012-08-01 11:00:14 -070092inline void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
Carl Shapiro69759ea2011-07-21 18:13:35 -070093 DCHECK(obj != NULL);
Mathieu Chartierb062fdd2012-07-03 09:51:48 -070094
Carl Shapiro69759ea2011-07-21 18:13:35 -070095 if (obj < condemned_) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -070096 // May later use condemned for the NULL check.
97 DCHECK(obj == NULL || IsMarked(obj));
Carl Shapiro69759ea2011-07-21 18:13:35 -070098 return;
99 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700100
101 // Try to take advantage of locality of references within a space, failing this find the space
102 // the hard way.
Ian Rogers506de0c2012-09-17 15:39:06 -0700103 if (UNLIKELY(!current_mark_bitmap_->HasAddress(obj))) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700104 current_mark_bitmap_ = heap_->GetMarkBitmap()->GetSpaceBitmap(obj);
Ian Rogers506de0c2012-09-17 15:39:06 -0700105 if (UNLIKELY(current_mark_bitmap_ == NULL)) {
106 LOG(ERROR) << "Failed to find space bitmap for object: " << obj;
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700107 GetHeap()->DumpSpaces();
108 LOG(FATAL) << "space_bitmap == NULL";
109 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700110 }
111
112 bool is_marked = current_mark_bitmap_->Test(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700113 // This object was not previously marked.
114 if (!is_marked) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700115 current_mark_bitmap_->Set(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700116 if (check_finger && obj < finger_) {
117 // The object must be pushed on to the mark stack.
118 mark_stack_->Push(obj);
119 }
120 }
121}
122
123// Used to mark objects when recursing. Recursion is done by moving
124// the finger across the bitmaps in address order and marking child
125// objects. Any newly-marked objects whose addresses are lower than
126// the finger won't be visited by the bitmap scan, so those objects
127// need to be added to the mark stack.
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700128void MarkSweep::MarkObject(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700129 if (obj != NULL) {
130 MarkObject0(obj, true);
131 }
132}
133
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700134void MarkSweep::MarkObjectVisitor(const Object* root, void* arg) {
Brian Carlstrom1f870082011-08-23 16:02:11 -0700135 DCHECK(root != NULL);
136 DCHECK(arg != NULL);
137 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
Ian Rogers5d76c432011-10-31 21:42:49 -0700138 mark_sweep->MarkObject0(root, false);
Brian Carlstrom1f870082011-08-23 16:02:11 -0700139}
140
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700141void MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) {
142 DCHECK(root != NULL);
143 DCHECK(arg != NULL);
144 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
145 mark_sweep->MarkObject0(root, true);
146}
147
Carl Shapiro69759ea2011-07-21 18:13:35 -0700148// Marks all objects in the root set.
149void MarkSweep::MarkRoots() {
Brian Carlstrom1f870082011-08-23 16:02:11 -0700150 Runtime::Current()->VisitRoots(MarkObjectVisitor, this);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700151}
152
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700153class CheckObjectVisitor {
154 public:
155 CheckObjectVisitor(MarkSweep* const mark_sweep)
156 : mark_sweep_(mark_sweep) {
157
158 }
159
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700160 void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const
Ian Rogersb726dcb2012-09-05 08:57:23 -0700161 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
162 Locks::mutator_lock_) {
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700163 mark_sweep_->CheckReference(obj, ref, offset, is_static);
164 }
165
166 private:
167 MarkSweep* const mark_sweep_;
168};
169
170void MarkSweep::CheckObject(const Object* obj) {
171 DCHECK(obj != NULL);
172 CheckObjectVisitor visitor(this);
173 VisitObjectReferences(obj, visitor);
174}
175
176void MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) {
177 DCHECK(root != NULL);
178 DCHECK(arg != NULL);
179 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700180 DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root));
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700181 mark_sweep->CheckObject(root);
182}
183
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700184void MarkSweep::CopyMarkBits(Space* space) {
185 SpaceBitmap* live_bitmap = space->GetLiveBitmap();
186 SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
187 mark_bitmap->CopyFrom(live_bitmap);
Ian Rogers5d76c432011-10-31 21:42:49 -0700188}
189
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700190class ScanImageRootVisitor {
191 public:
192 ScanImageRootVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700193 }
194
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700195 void operator ()(const Object* root) const
Ian Rogersb726dcb2012-09-05 08:57:23 -0700196 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
197 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700198 DCHECK(root != NULL);
199 mark_sweep_->ScanObject(root);
200 }
201
202 private:
203 MarkSweep* const mark_sweep_;
204};
205
206// Marks all objects that are in images and have been touched by the mutator
207void MarkSweep::ScanDirtyImageRoots() {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700208 const Spaces& spaces = heap_->GetSpaces();
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700209 CardTable* card_table = heap_->GetCardTable();
210 ScanImageRootVisitor image_root_visitor(this);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700211 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
212 Space* space = *it;
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700213 if (space->IsImageSpace()) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700214 card_table->Scan(space->GetLiveBitmap(), space->Begin(), space->End(), image_root_visitor,
215 IdentityFunctor());
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700216 }
217 }
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700218}
219
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700220void MarkSweep::ScanGrayObjects(bool update_finger) {
221 const Spaces& spaces = heap_->GetSpaces();
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700222 CardTable* card_table = heap_->GetCardTable();
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700223 ScanImageRootVisitor image_root_visitor(this);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700224 SetFingerVisitor finger_visitor(this);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700225 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
226 Space* space = *it;
227 byte* begin = space->Begin();
228 byte* end = space->End();
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700229 // Image spaces are handled properly since live == marked for them.
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700230 SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
231 if (update_finger) {
232 card_table->Scan(mark_bitmap, begin, end, image_root_visitor, finger_visitor);
233 } else {
234 card_table->Scan(mark_bitmap, begin, end, image_root_visitor, IdentityFunctor());
235 }
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700236 }
237}
238
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700239class CheckBitmapVisitor {
240 public:
241 CheckBitmapVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {
242
243 }
244
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700245 void operator ()(const Object* obj) const
Ian Rogersb726dcb2012-09-05 08:57:23 -0700246 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
247 Locks::mutator_lock_) {
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700248 DCHECK(obj != NULL);
249 mark_sweep_->CheckObject(obj);
250 }
251
252 private:
253 MarkSweep* mark_sweep_;
254};
255
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700256void MarkSweep::VerifyImageRoots() {
257 // Verify roots ensures that all the references inside the image space point
258 // objects which are either in the image space or marked objects in the alloc
259 // space
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700260 CheckBitmapVisitor visitor(this);
261 const Spaces& spaces = heap_->GetSpaces();
262 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
263 const Space* space = *it;
264 if (space->IsImageSpace()) {
265 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
266 uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
267 SpaceBitmap* live_bitmap = space->GetLiveBitmap();
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700268 DCHECK(live_bitmap != NULL);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700269 live_bitmap->VisitMarkedRange(begin, end, visitor, IdentityFunctor());
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700270 }
271 }
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700272}
273
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700274class ScanObjectVisitor {
275 public:
276 ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
277
278 }
279
280 void operator ()(const Object* obj) const
Ian Rogersb726dcb2012-09-05 08:57:23 -0700281 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
282 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700283 mark_sweep_->ScanObject(obj);
284 }
285
286 private:
287 MarkSweep* const mark_sweep_;
288};
289
Carl Shapiro58551df2011-07-24 03:09:51 -0700290// Populates the mark stack based on the set of marked objects and
291// recursively marks until the mark stack is emptied.
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700292void MarkSweep::RecursiveMark(bool partial, TimingLogger& timings) {
Brian Carlstrom1f870082011-08-23 16:02:11 -0700293 // RecursiveMark will build the lists of known instances of the Reference classes.
294 // See DelayReferenceReferent for details.
295 CHECK(soft_reference_list_ == NULL);
296 CHECK(weak_reference_list_ == NULL);
297 CHECK(finalizer_reference_list_ == NULL);
298 CHECK(phantom_reference_list_ == NULL);
299 CHECK(cleared_reference_list_ == NULL);
300
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700301 const Spaces& spaces = heap_->GetSpaces();
302
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700303 SetFingerVisitor set_finger_visitor(this);
304 ScanObjectVisitor scan_visitor(this);
305 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
306 Space* space = *it;
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700307 if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT ||
308 (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT)
309 ) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700310 current_mark_bitmap_ = space->GetMarkBitmap();
311 if (current_mark_bitmap_ == NULL) {
312 GetHeap()->DumpSpaces();
313 DCHECK(false) << "invalid bitmap";
314 }
315 // This function does not handle heap end increasing, so we must use the space end.
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700316 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
317 uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700318 current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor, set_finger_visitor);
Mathieu Chartier7664f5c2012-06-08 18:15:32 -0700319 }
Carl Shapiro58551df2011-07-24 03:09:51 -0700320 }
321 finger_ = reinterpret_cast<Object*>(~0);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700322 timings.AddSplit("RecursiveMark");
Ian Rogers5d76c432011-10-31 21:42:49 -0700323 // TODO: tune the frequency of emptying the mark stack
Carl Shapiro58551df2011-07-24 03:09:51 -0700324 ProcessMarkStack();
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700325 timings.AddSplit("ProcessMarkStack");
Carl Shapiro58551df2011-07-24 03:09:51 -0700326}
327
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700328void MarkSweep::RecursiveMarkCards(CardTable* card_table, const std::vector<byte*>& cards,
329 TimingLogger& timings) {
330 ScanImageRootVisitor image_root_visitor(this);
331 SetFingerVisitor finger_visitor(this);
332 for (size_t i = 0;i < cards.size();) {
333 Object* start_obj = reinterpret_cast<Object*>(card_table->AddrFromCard(cards[i]));
334 uintptr_t begin = reinterpret_cast<uintptr_t>(start_obj);
335 uintptr_t end = begin + GC_CARD_SIZE;
336 for (++i; reinterpret_cast<uintptr_t>(cards[i]) == end && i < cards.size(); ++i) {
337 end += GC_CARD_SIZE;
338 }
339 if (current_mark_bitmap_ == NULL || !current_mark_bitmap_->HasAddress(start_obj)) {
340 current_mark_bitmap_ = heap_->GetMarkBitmap()->GetSpaceBitmap(start_obj);
341#ifndef NDEBUG
342 if (current_mark_bitmap_ == NULL) {
343 GetHeap()->DumpSpaces();
344 DCHECK(false) << "Object " << reinterpret_cast<const void*>(start_obj);
345 }
346#endif
347 }
348 current_mark_bitmap_->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor);
349 }
350 timings.AddSplit("RecursiveMarkCards");
351 ProcessMarkStack();
352 timings.AddSplit("ProcessMarkStack");
353}
354
355bool MarkSweep::IsMarkedCallback(const Object* object, void* arg) {
356 return
357 reinterpret_cast<MarkSweep*>(arg)->IsMarked(object) ||
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700358 !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object);
359}
360
361bool MarkSweep::IsLiveCallback(const Object* object, void* arg) {
362 return
363 reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object) ||
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700364 !reinterpret_cast<MarkSweep*>(arg)->IsMarked(object);
365}
366
367void MarkSweep::RecursiveMarkDirtyObjects(bool update_finger) {
368 ScanGrayObjects(update_finger);
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700369 ProcessMarkStack();
370}
371
Carl Shapiro58551df2011-07-24 03:09:51 -0700372void MarkSweep::ReMarkRoots() {
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700373 Runtime::Current()->VisitRoots(ReMarkObjectVisitor, this);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700374}
375
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700376void MarkSweep::SweepJniWeakGlobals(bool swap_bitmaps) {
377 HeapBitmap* live_bitmap = GetHeap()->GetLiveBitmap();
378 HeapBitmap* mark_bitmap = GetHeap()->GetMarkBitmap();
379
380 if (swap_bitmaps) {
381 std::swap(live_bitmap, mark_bitmap);
382 }
383
Elliott Hughes410c0c82011-09-01 17:58:25 -0700384 JavaVMExt* vm = Runtime::Current()->GetJavaVM();
385 MutexLock mu(vm->weak_globals_lock);
386 IndirectReferenceTable* table = &vm->weak_globals;
Mathieu Chartier654d3a22012-07-11 17:54:18 -0700387 typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto
Elliott Hughes410c0c82011-09-01 17:58:25 -0700388 for (It it = table->begin(), end = table->end(); it != end; ++it) {
389 const Object** entry = *it;
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700390 if (live_bitmap->Test(*entry) && !mark_bitmap->Test(*entry)) {
Elliott Hughes410c0c82011-09-01 17:58:25 -0700391 *entry = kClearedJniWeakGlobal;
392 }
393 }
394}
395
Mathieu Chartier46a23632012-08-07 18:44:40 -0700396void MarkSweep::SweepSystemWeaks(bool swap_bitmaps) {
397 Runtime* runtime = Runtime::Current();
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700398 // The callbacks check
399 // !is_marked where is_marked is the callback but we want
400 // !IsMarked && IsLive
401 // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive).
402 // Or for swapped (IsLive || !IsMarked).
Mathieu Chartier46a23632012-08-07 18:44:40 -0700403 runtime->GetInternTable()->SweepInternTableWeaks(swap_bitmaps ? IsLiveCallback : IsMarkedCallback,
404 this);
405 runtime->GetMonitorList()->SweepMonitorList(swap_bitmaps ? IsLiveCallback : IsMarkedCallback,
406 this);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700407 SweepJniWeakGlobals(swap_bitmaps);
Carl Shapiro58551df2011-07-24 03:09:51 -0700408}
409
Mathieu Chartierc7b83a02012-09-11 18:07:39 -0700410bool MarkSweep::VerifyIsLiveCallback(const Object* obj, void* arg) {
411 reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj);
412 // We don't actually want to sweep the object, so lets return "marked"
413 return true;
414}
415
416void MarkSweep::VerifyIsLive(const Object* obj) {
417 Heap* heap = GetHeap();
418 if (!heap->GetLiveBitmap()->Test(obj)) {
419 if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) ==
420 heap->allocation_stack_->End()) {
421 // Object not found!
422 heap->DumpSpaces();
423 LOG(FATAL) << "Found dead object " << obj;
424 }
425 }
426}
427
428void MarkSweep::VerifySystemWeaks() {
429 Runtime* runtime = Runtime::Current();
430 // Verify system weaks, uses a special IsMarked callback which always returns true.
431 runtime->GetInternTable()->SweepInternTableWeaks(VerifyIsLiveCallback, this);
432 runtime->GetMonitorList()->SweepMonitorList(VerifyIsLiveCallback, this);
433
434 JavaVMExt* vm = runtime->GetJavaVM();
435 MutexLock mu(vm->weak_globals_lock);
436 IndirectReferenceTable* table = &vm->weak_globals;
437 typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto
438 for (It it = table->begin(), end = table->end(); it != end; ++it) {
439 const Object** entry = *it;
440 VerifyIsLive(*entry);
441 }
442}
443
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800444struct SweepCallbackContext {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700445 MarkSweep* mark_sweep;
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800446 AllocSpace* space;
447};
448
Ian Rogers30fab402012-01-23 15:43:46 -0800449void MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
Ian Rogersb726dcb2012-09-05 08:57:23 -0700450 Locks::heap_bitmap_lock_->AssertExclusiveHeld();
Mathieu Chartier654d3a22012-07-11 17:54:18 -0700451
Elliott Hughes307f75d2011-10-12 18:04:40 -0700452 size_t freed_objects = num_ptrs;
453 size_t freed_bytes = 0;
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800454 SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700455 MarkSweep* mark_sweep = context->mark_sweep;
456 Heap* heap = mark_sweep->GetHeap();
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800457 AllocSpace* space = context->space;
Ian Rogers5d76c432011-10-31 21:42:49 -0700458 // Use a bulk free, that merges consecutive objects before freeing or free per object?
459 // Documentation suggests better free performance with merging, but this may be at the expensive
460 // of allocation.
461 // TODO: investigate performance
Ian Rogers30fab402012-01-23 15:43:46 -0800462 static const bool kUseFreeList = true;
463 if (kUseFreeList) {
Ian Rogers5d76c432011-10-31 21:42:49 -0700464 for (size_t i = 0; i < num_ptrs; ++i) {
465 Object* obj = static_cast<Object*>(ptrs[i]);
Ian Rogers30fab402012-01-23 15:43:46 -0800466 freed_bytes += space->AllocationSize(obj);
Ian Rogers5d76c432011-10-31 21:42:49 -0700467 }
Ian Rogers30fab402012-01-23 15:43:46 -0800468 // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
469 space->FreeList(num_ptrs, ptrs);
Ian Rogers5d76c432011-10-31 21:42:49 -0700470 } else {
471 for (size_t i = 0; i < num_ptrs; ++i) {
472 Object* obj = static_cast<Object*>(ptrs[i]);
Ian Rogers30fab402012-01-23 15:43:46 -0800473 freed_bytes += space->AllocationSize(obj);
Ian Rogers30fab402012-01-23 15:43:46 -0800474 space->Free(obj);
Ian Rogers5d76c432011-10-31 21:42:49 -0700475 }
Carl Shapiro58551df2011-07-24 03:09:51 -0700476 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700477
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700478 heap->RecordFree(freed_objects, freed_bytes);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700479 mark_sweep->freed_objects_ += freed_objects;
480 mark_sweep->freed_bytes_ += freed_bytes;
Carl Shapiro58551df2011-07-24 03:09:51 -0700481}
482
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700483void MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
Ian Rogersb726dcb2012-09-05 08:57:23 -0700484 Locks::heap_bitmap_lock_->AssertExclusiveHeld();
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700485
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700486 SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700487 Heap* heap = context->mark_sweep->GetHeap();
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700488 // We don't free any actual memory to avoid dirtying the shared zygote pages.
489 for (size_t i = 0; i < num_ptrs; ++i) {
490 Object* obj = static_cast<Object*>(ptrs[i]);
491 heap->GetLiveBitmap()->Clear(obj);
492 heap->GetCardTable()->MarkCard(obj);
493 }
494}
495
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700496void MarkSweep::SweepArray(TimingLogger& logger, MarkStack* allocations, bool swap_bitmaps) {
497 size_t freed_bytes = 0;
498 AllocSpace* space = heap_->GetAllocSpace();
Elliott Hughes2da50362011-10-10 16:57:08 -0700499
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700500 // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark
501 // bitmap, resulting in occasional frees of Weaks which are still in use.
502 // TODO: Fix when sweeping weaks works properly with mutators unpaused + allocation list.
503 // SweepSystemWeaks(swap_bitmaps);
504
505 // Newly allocated objects MUST be in the alloc space and those are the only objects which we are
506 // going to free.
507 SpaceBitmap* live_bitmap = space->GetLiveBitmap();
508 SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
509 if (swap_bitmaps) {
510 std::swap(live_bitmap, mark_bitmap);
511 }
512
513 size_t count = allocations->Size();
514 Object** objects = allocations->Begin();
515 Object** out = objects;
516
517 // Empty the allocation stack.
518 for (size_t i = 0;i < count;++i) {
519 Object* obj = objects[i];
520 // There should only be objects in the AllocSpace in the allocation stack.
521 DCHECK(space->Contains(obj));
522 DCHECK(mark_bitmap->HasAddress(obj));
523 // Mark as live in the live bitmap if and only if we are marked in the mark bitmap.
524 if (mark_bitmap->Test(obj)) {
525 live_bitmap->Set(obj);
526 } else {
527 // Due to bitmap swapping, a young object can end up being marked as live.
528 live_bitmap->Clear(obj);
529 // Don't bother un-marking since we clear the mark bitmap anyways.
530 *(out++) = obj;
531 size_t size = space->AllocationSize(obj);
532 freed_bytes += size;
533 }
534 }
535 logger.AddSplit("Process allocation stack");
536
537 size_t freed_objects = out - objects;
Mathieu Chartier40e978b2012-09-07 11:38:36 -0700538 VLOG(heap) << "Freed " << freed_objects << "/" << count
539 << " objects with size " << PrettySize(freed_bytes);
540 space->FreeList(freed_objects, objects);
541 heap_->RecordFree(freed_objects, freed_bytes);
542 freed_objects_ += freed_objects;
543 freed_bytes_ += freed_bytes;
544 logger.AddSplit("FreeList");
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700545
546 allocations->Reset();
547 logger.AddSplit("Reset stack");
548}
549
550void MarkSweep::Sweep(bool partial, bool swap_bitmaps) {
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700551 DCHECK(mark_stack_->IsEmpty());
552
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700553 // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark
554 // bitmap, resulting in occasional frees of Weaks which are still in use.
555 // SweepSystemWeaks(swap_bitmaps);
556
Mathieu Chartier46a23632012-08-07 18:44:40 -0700557 const Spaces& spaces = heap_->GetSpaces();
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800558 SweepCallbackContext scc;
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700559 scc.mark_sweep = this;
560 // TODO: C++0x auto
561 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
562 Space* space = *it;
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700563 if (
564 space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT ||
565 (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT)
566 ) {
567 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
568 uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
569 scc.space = space->AsAllocSpace();
570 SpaceBitmap* live_bitmap = space->GetLiveBitmap();
571 SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
Mathieu Chartierfd678be2012-08-30 14:50:54 -0700572 if (swap_bitmaps) {
573 std::swap(live_bitmap, mark_bitmap);
574 }
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700575 if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) {
576 // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked.
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700577 SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end,
578 &SweepCallback, reinterpret_cast<void*>(&scc));
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700579 } else {
580 // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual memory.
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700581 SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end,
582 &ZygoteSweepCallback, reinterpret_cast<void*>(&scc));
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700583 }
Carl Shapiro58551df2011-07-24 03:09:51 -0700584 }
585 }
586}
587
Carl Shapiro69759ea2011-07-21 18:13:35 -0700588// Scans instance fields.
Elliott Hughesb0663112011-10-19 18:16:37 -0700589inline void MarkSweep::ScanInstanceFields(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700590 DCHECK(obj != NULL);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700591 Class* klass = obj->GetClass();
592 DCHECK(klass != NULL);
Elliott Hughes2da50362011-10-10 16:57:08 -0700593 ScanFields(obj, klass->GetReferenceInstanceOffsets(), false);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700594}
595
596// Scans static storage on a Class.
Elliott Hughesb0663112011-10-19 18:16:37 -0700597inline void MarkSweep::ScanStaticFields(const Class* klass) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700598 DCHECK(klass != NULL);
Elliott Hughesadb460d2011-10-05 17:02:34 -0700599 ScanFields(klass, klass->GetReferenceStaticOffsets(), true);
Brian Carlstrom4873d462011-08-21 15:23:39 -0700600}
601
Elliott Hughesb0663112011-10-19 18:16:37 -0700602inline void MarkSweep::ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700603 if (ref_offsets != CLASS_WALK_SUPER) {
604 // Found a reference offset bitmap. Mark the specified offsets.
605 while (ref_offsets != 0) {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700606 const size_t right_shift = CLZ(ref_offsets);
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700607 MemberOffset byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
608 const Object* ref = obj->GetFieldObject<const Object*>(byte_offset, false);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700609 MarkObject(ref);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700610 ref_offsets ^= CLASS_HIGH_BIT >> right_shift;
Carl Shapiro69759ea2011-07-21 18:13:35 -0700611 }
612 } else {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700613 // There is no reference offset bitmap. In the non-static case,
614 // walk up the class inheritance hierarchy and find reference
615 // offsets the hard way. In the static case, just consider this
616 // class.
617 for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700618 klass != NULL;
Brian Carlstrom4873d462011-08-21 15:23:39 -0700619 klass = is_static ? NULL : klass->GetSuperClass()) {
620 size_t num_reference_fields = (is_static
621 ? klass->NumReferenceStaticFields()
622 : klass->NumReferenceInstanceFields());
623 for (size_t i = 0; i < num_reference_fields; ++i) {
624 Field* field = (is_static
625 ? klass->GetStaticField(i)
626 : klass->GetInstanceField(i));
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700627 MemberOffset field_offset = field->GetOffset();
628 const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700629 MarkObject(ref);
630 }
631 }
632 }
633}
634
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700635void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700636 const Spaces& spaces = heap_->GetSpaces();
637 // TODO: C++0x auto
638 for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
639 if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) {
640 DCHECK(IsMarked(obj));
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700641
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700642 bool is_marked = IsMarked(ref);
643 if (!is_marked) {
644 LOG(INFO) << **cur;
645 LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref)
646 << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj)
647 << "' (" << reinterpret_cast<const void*>(obj) << ") at offset "
648 << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked";
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700649
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700650 const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
651 DCHECK(klass != NULL);
652 const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields();
653 DCHECK(fields != NULL);
654 bool found = false;
655 for (int32_t i = 0; i < fields->GetLength(); ++i) {
656 const Field* cur = fields->Get(i);
657 if (cur->GetOffset().Int32Value() == offset.Int32Value()) {
658 LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur);
659 found = true;
660 break;
661 }
662 }
663 if (!found) {
664 LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value();
665 }
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700666
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700667 bool obj_marked = heap_->GetCardTable()->IsDirty(obj);
668 if (!obj_marked) {
669 LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' "
670 << "(" << reinterpret_cast<const void*>(obj) << ") contains references to "
671 << "the alloc space, but wasn't card marked";
Mathieu Chartier262e5ff2012-06-01 17:35:38 -0700672 }
673 }
Ian Rogers5d76c432011-10-31 21:42:49 -0700674 }
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700675 break;
Ian Rogers5d76c432011-10-31 21:42:49 -0700676 }
677}
678
Carl Shapiro69759ea2011-07-21 18:13:35 -0700679// Scans the header, static field references, and interface pointers
680// of a class object.
Elliott Hughesb0663112011-10-19 18:16:37 -0700681inline void MarkSweep::ScanClass(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700682#ifndef NDEBUG
683 ++class_count_;
684#endif
Brian Carlstrom693267a2011-09-06 09:25:34 -0700685 ScanInstanceFields(obj);
Brian Carlstrom40381fb2011-10-19 14:13:40 -0700686 ScanStaticFields(obj->AsClass());
Carl Shapiro69759ea2011-07-21 18:13:35 -0700687}
688
689// Scans the header of all array objects. If the array object is
690// specialized to a reference type, scans the array data as well.
Elliott Hughesb0663112011-10-19 18:16:37 -0700691inline void MarkSweep::ScanArray(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700692#ifndef NDEBUG
693 ++array_count_;
694#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700695 MarkObject(obj->GetClass());
696 if (obj->IsObjectArray()) {
Brian Carlstromdb4d5402011-08-09 12:18:28 -0700697 const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
Elliott Hughesd8ddfd52011-08-15 14:32:53 -0700698 for (int32_t i = 0; i < array->GetLength(); ++i) {
Ian Rogers5d76c432011-10-31 21:42:49 -0700699 const Object* element = array->GetWithoutChecks(i);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700700 MarkObject(element);
701 }
702 }
703}
704
Carl Shapiro69759ea2011-07-21 18:13:35 -0700705// Process the "referent" field in a java.lang.ref.Reference. If the
706// referent has not yet been marked, put it on the appropriate list in
707// the gcHeap for later processing.
708void MarkSweep::DelayReferenceReferent(Object* obj) {
709 DCHECK(obj != NULL);
Brian Carlstrom1f870082011-08-23 16:02:11 -0700710 Class* klass = obj->GetClass();
711 DCHECK(klass != NULL);
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700712 DCHECK(klass->IsReferenceClass());
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800713 Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false);
714 Object* referent = heap_->GetReferenceReferent(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700715 if (pending == NULL && referent != NULL && !IsMarked(referent)) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700716 Object** list = NULL;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700717 if (klass->IsSoftReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700718 list = &soft_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700719 } else if (klass->IsWeakReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700720 list = &weak_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700721 } else if (klass->IsFinalizerReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700722 list = &finalizer_reference_list_;
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700723 } else if (klass->IsPhantomReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700724 list = &phantom_reference_list_;
725 }
Brian Carlstrom0796af02011-10-12 14:31:45 -0700726 DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags();
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800727 heap_->EnqueuePendingReference(obj, list);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700728 }
729}
730
731// Scans the header and field references of a data object. If the
732// scanned object is a reference subclass, it is scheduled for later
Elliott Hughesadb460d2011-10-05 17:02:34 -0700733// processing.
Elliott Hughesb0663112011-10-19 18:16:37 -0700734inline void MarkSweep::ScanOther(const Object* obj) {
Elliott Hughes352a4242011-10-31 15:15:21 -0700735#ifndef NDEBUG
736 ++other_count_;
737#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700738 ScanInstanceFields(obj);
Elliott Hughes352a4242011-10-31 15:15:21 -0700739 if (obj->GetClass()->IsReferenceClass()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700740 DelayReferenceReferent(const_cast<Object*>(obj));
741 }
742}
743
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700744void MarkSweep::ScanRoot(const Object* obj) {
745 ScanObject(obj);
746}
747
Carl Shapiro69759ea2011-07-21 18:13:35 -0700748// Scans an object reference. Determines the type of the reference
749// and dispatches to a specialized scanning routine.
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700750void MarkSweep::ScanObject(const Object* obj) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700751 DCHECK(obj != NULL);
752 DCHECK(obj->GetClass() != NULL);
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700753#ifndef NDEBUG
754 if (!IsMarked(obj)) {
755 heap_->DumpSpaces();
756 LOG(FATAL) << "Scanning unmarked object " << reinterpret_cast<const void*>(obj);
757 }
758#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700759 if (obj->IsClass()) {
760 ScanClass(obj);
Brian Carlstromb63ec392011-08-27 17:38:27 -0700761 } else if (obj->IsArrayInstance()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700762 ScanArray(obj);
763 } else {
Carl Shapiro58551df2011-07-24 03:09:51 -0700764 ScanOther(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700765 }
766}
767
Ian Rogers5d76c432011-10-31 21:42:49 -0700768// Scan anything that's on the mark stack.
Carl Shapiro69759ea2011-07-21 18:13:35 -0700769void MarkSweep::ProcessMarkStack() {
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700770#if MARK_STACK_PREFETCH
771 const size_t fifo_size = 4;
772 const size_t fifo_mask = fifo_size - 1;
773 const Object* fifo[fifo_size];
774 for (size_t i = 0;i < fifo_size;++i) {
775 fifo[i] = NULL;
776 }
777 size_t fifo_pos = 0;
778 size_t fifo_count = 0;
779 for (;;) {
780 const Object* obj = fifo[fifo_pos & fifo_mask];
781 if (obj != NULL) {
782 ScanObject(obj);
783 fifo[fifo_pos & fifo_mask] = NULL;
784 --fifo_count;
785 }
786
787 if (!mark_stack_->IsEmpty()) {
788 const Object* obj = mark_stack_->Pop();
789 DCHECK(obj != NULL);
790 fifo[fifo_pos & fifo_mask] = obj;
791 __builtin_prefetch(obj);
792 fifo_count++;
793 }
794 fifo_pos++;
795
796 if (!fifo_count) {
797 CHECK(mark_stack_->IsEmpty()) << mark_stack_->Size();
798 break;
799 }
800 }
801#else
Carl Shapiro69759ea2011-07-21 18:13:35 -0700802 while (!mark_stack_->IsEmpty()) {
Brian Carlstrom4873d462011-08-21 15:23:39 -0700803 const Object* obj = mark_stack_->Pop();
Mathieu Chartiercc236d72012-07-20 10:29:05 -0700804 DCHECK(obj != NULL);
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700805 ScanObject(obj);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700806 }
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700807#endif
Carl Shapiro69759ea2011-07-21 18:13:35 -0700808}
809
Carl Shapiro69759ea2011-07-21 18:13:35 -0700810// Walks the reference list marking any references subject to the
811// reference clearing policy. References with a black referent are
812// removed from the list. References with white referents biased
813// toward saving are blackened and also removed from the list.
814void MarkSweep::PreserveSomeSoftReferences(Object** list) {
815 DCHECK(list != NULL);
816 Object* clear = NULL;
817 size_t counter = 0;
Mathieu Chartierb43b7d42012-06-19 13:15:09 -0700818
819 DCHECK(mark_stack_->IsEmpty());
820
Carl Shapiro69759ea2011-07-21 18:13:35 -0700821 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800822 Object* ref = heap_->DequeuePendingReference(list);
823 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700824 if (referent == NULL) {
825 // Referent was cleared by the user during marking.
826 continue;
827 }
828 bool is_marked = IsMarked(referent);
829 if (!is_marked && ((++counter) & 1)) {
830 // Referent is white and biased toward saving, mark it.
831 MarkObject(referent);
832 is_marked = true;
833 }
834 if (!is_marked) {
835 // Referent is white, queue it for clearing.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800836 heap_->EnqueuePendingReference(ref, &clear);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700837 }
838 }
839 *list = clear;
840 // Restart the mark with the newly black references added to the
841 // root set.
842 ProcessMarkStack();
843}
844
845// Unlink the reference list clearing references objects with white
846// referents. Cleared references registered to a reference queue are
847// scheduled for appending by the heap worker thread.
848void MarkSweep::ClearWhiteReferences(Object** list) {
849 DCHECK(list != NULL);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700850 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800851 Object* ref = heap_->DequeuePendingReference(list);
852 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700853 if (referent != NULL && !IsMarked(referent)) {
854 // Referent is white, clear it.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800855 heap_->ClearReferenceReferent(ref);
856 if (heap_->IsEnqueuable(ref)) {
857 heap_->EnqueueReference(ref, &cleared_reference_list_);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700858 }
859 }
860 }
861 DCHECK(*list == NULL);
862}
863
864// Enqueues finalizer references with white referents. White
865// referents are blackened, moved to the zombie field, and the
866// referent field is cleared.
867void MarkSweep::EnqueueFinalizerReferences(Object** list) {
868 DCHECK(list != NULL);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800869 MemberOffset zombie_offset = heap_->GetFinalizerReferenceZombieOffset();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700870 bool has_enqueued = false;
871 while (*list != NULL) {
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800872 Object* ref = heap_->DequeuePendingReference(list);
873 Object* referent = heap_->GetReferenceReferent(ref);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700874 if (referent != NULL && !IsMarked(referent)) {
875 MarkObject(referent);
876 // If the referent is non-null the reference must queuable.
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800877 DCHECK(heap_->IsEnqueuable(ref));
Ian Rogers0cfe1fb2011-08-26 03:29:44 -0700878 ref->SetFieldObject(zombie_offset, referent, false);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800879 heap_->ClearReferenceReferent(ref);
880 heap_->EnqueueReference(ref, &cleared_reference_list_);
Carl Shapiro69759ea2011-07-21 18:13:35 -0700881 has_enqueued = true;
882 }
883 }
884 if (has_enqueued) {
885 ProcessMarkStack();
886 }
887 DCHECK(*list == NULL);
888}
889
Carl Shapiro58551df2011-07-24 03:09:51 -0700890// Process reference class instances and schedule finalizations.
Carl Shapiro69759ea2011-07-21 18:13:35 -0700891void MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft,
892 Object** weak_references,
893 Object** finalizer_references,
894 Object** phantom_references) {
895 DCHECK(soft_references != NULL);
896 DCHECK(weak_references != NULL);
897 DCHECK(finalizer_references != NULL);
898 DCHECK(phantom_references != NULL);
899
900 // Unless we are in the zygote or required to clear soft references
901 // with white references, preserve some white referents.
Ian Rogers2945e242012-06-03 14:45:16 -0700902 if (!clear_soft && !Runtime::Current()->IsZygote()) {
Carl Shapiro69759ea2011-07-21 18:13:35 -0700903 PreserveSomeSoftReferences(soft_references);
904 }
905
906 // Clear all remaining soft and weak references with white
907 // referents.
908 ClearWhiteReferences(soft_references);
909 ClearWhiteReferences(weak_references);
910
911 // Preserve all white objects with finalize methods and schedule
912 // them for finalization.
913 EnqueueFinalizerReferences(finalizer_references);
914
915 // Clear all f-reachable soft and weak references with white
916 // referents.
917 ClearWhiteReferences(soft_references);
918 ClearWhiteReferences(weak_references);
919
920 // Clear all phantom references with white referents.
921 ClearWhiteReferences(phantom_references);
922
923 // At this point all reference lists should be empty.
924 DCHECK(*soft_references == NULL);
925 DCHECK(*weak_references == NULL);
926 DCHECK(*finalizer_references == NULL);
927 DCHECK(*phantom_references == NULL);
928}
929
Carl Shapiro69759ea2011-07-21 18:13:35 -0700930MarkSweep::~MarkSweep() {
Elliott Hughes352a4242011-10-31 15:15:21 -0700931#ifndef NDEBUG
Elliott Hughes4dd9b4d2011-12-12 18:29:24 -0800932 VLOG(heap) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ << " other=" << other_count_;
Elliott Hughes352a4242011-10-31 15:15:21 -0700933#endif
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700934 // Ensure that the mark stack is empty.
935 CHECK(mark_stack_->IsEmpty());
936
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700937 // Clear all of the alloc spaces' mark bitmaps.
938 const Spaces& spaces = heap_->GetSpaces();
939 // TODO: C++0x auto
Mathieu Chartier357e9be2012-08-01 11:00:14 -0700940 for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
941 if ((*it)->GetGcRetentionPolicy() != GCRP_NEVER_COLLECT) {
942 (*it)->GetMarkBitmap()->Clear();
Mathieu Chartierb062fdd2012-07-03 09:51:48 -0700943 }
944 }
Mathieu Chartier5301cd22012-05-31 12:11:36 -0700945 mark_stack_->Reset();
Carl Shapiro69759ea2011-07-21 18:13:35 -0700946}
947
948} // namespace art