mark_sweep.cc revision 35883cc623fdf475a4ead1dafcba9e9becc1ed11
12faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes/* 22faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Copyright (C) 2011 The Android Open Source Project 32faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 42faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 52faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * you may not use this file except in compliance with the License. 62faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * You may obtain a copy of the License at 72faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 82faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 92faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 102faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Unless required by applicable law or agreed to in writing, software 112faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 122faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * See the License for the specific language governing permissions and 142faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * limitations under the License. 152faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes */ 1669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 17578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "mark_sweep.h" 1869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <climits> 2058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <vector> 2158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 22858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier#include "barrier.h" 23357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#include "card_table.h" 24410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "class_loader.h" 25693267ad474039981e9be20a592ac2e4e3bd742eBrian Carlstrom#include "dex_cache.h" 2658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include "heap.h" 27410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "indirect_reference_table.h" 28410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "intern_table.h" 2981d425b0b232962441616f8b14f73620bffef5e5Ian Rogers#include "jni_internal.h" 301c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier#include "large_object_space.h" 31578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "logging.h" 32578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "macros.h" 33c33a32bccc4c66ed82ce3a580b16636399385cb4Elliott Hughes#include "monitor.h" 34578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "object.h" 351f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom#include "runtime.h" 3658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include "space.h" 37307f75d6bcf7c32db7e1b43124dead628cc7ce96Elliott Hughes#include "timing_logger.h" 38578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "thread.h" 396f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier#include "thread_list.h" 4008254278f290c2541cecd24ce6b7015427f4eae5Ian Rogers#include "verifier/method_verifier.h" 4169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 4269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapironamespace art { 4369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 4402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Performance options. 4502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kParallelMarkStack = true; 4602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kDisableFinger = true; 47858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartierstatic const bool kUseMarkStackPrefetch = true; 48858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 4902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Profiling and information flags. 5002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kCountClassesMarked = false; 5102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kProfileLargeObjects = false; 5202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kMeasureOverhead = false; 5302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kCountTasks = false; 54d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartierstatic const bool kCountJavaLangRefs = false; 5502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 56357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierclass SetFingerVisitor { 57357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier public: 58357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 59357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 60357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 61357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 62357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier void operator ()(void* finger) const { 63357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep_->SetFinger(reinterpret_cast<Object*>(finger)); 64357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 65357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 66357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier private: 67357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* const mark_sweep_; 68357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier}; 69357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 70d8195f19840911a73b1491dfc8e7c18139753731Mathieu ChartierMarkSweep::MarkSweep(ObjectStack* mark_stack) 71b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier : current_mark_bitmap_(NULL), 72b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier mark_stack_(mark_stack), 735301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier heap_(NULL), 745301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier finger_(NULL), 75e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier immune_begin_(NULL), 76e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier immune_end_(NULL), 775301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier soft_reference_list_(NULL), 785301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier weak_reference_list_(NULL), 795301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier finalizer_reference_list_(NULL), 805301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier phantom_reference_list_(NULL), 815301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier cleared_reference_list_(NULL), 82357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier freed_bytes_(0), freed_objects_(0), 83858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier class_count_(0), array_count_(0), other_count_(0), 8402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier large_object_test_(0), large_object_mark_(0), 8502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier classes_marked_(0), overhead_time_(0), 8602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier work_chunks_created_(0), work_chunks_deleted_(0), 87d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier reference_count_(0), 8835883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier gc_barrier_(new Barrier(0)), 89ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier large_object_lock_("large object lock"), 90ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_stack_expand_lock_("mark stack expand lock") { 915301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier DCHECK(mark_stack_ != NULL); 925301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier} 93b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 945301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartiervoid MarkSweep::Init() { 9502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier java_lang_Class_ = Class::GetJavaLangClass(); 9602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK(java_lang_Class_ != NULL); 97b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_ = Runtime::Current()->GetHeap(); 985301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier mark_stack_->Reset(); 997469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier FindDefaultMarkBitmap(); 1009ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier // Mark any concurrent roots as dirty since we need to scan them at least once during this GC. 1019ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier Runtime::Current()->DirtyRoots(); 1027469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 10358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 1047469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::FindDefaultMarkBitmap() { 105b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 1067469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 1077469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if ((*it)->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect) { 1087469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier current_mark_bitmap_ = (*it)->GetMarkBitmap(); 1097469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier CHECK(current_mark_bitmap_ != NULL); 1107469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return; 111b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 112b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 1137469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->DumpSpaces(); 1147469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier LOG(FATAL) << "Could not find a default mark bitmap"; 11558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 11658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 117ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartiervoid MarkSweep::ExpandMarkStack() { 118ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Rare case, no need to have Thread::Current be a parameter. 119ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier MutexLock mu(Thread::Current(), mark_stack_expand_lock_); 120ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (UNLIKELY(mark_stack_->Size() < mark_stack_->Capacity())) { 121ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Someone else acquired the lock and expanded the mark stack before us. 122ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier return; 123ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 124ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier std::vector<Object*> temp; 125ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier temp.insert(temp.begin(), mark_stack_->Begin(), mark_stack_->End()); 126ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_stack_->Resize(mark_stack_->Capacity() * 2); 127ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier for (size_t i = 0; i < temp.size(); ++i) { 128ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_stack_->PushBack(temp[i]); 129ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 130ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 131ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 132ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartierinline void MarkSweep::MarkObjectNonNullParallel(const Object* obj, bool check_finger) { 133ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(obj != NULL); 134ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (MarkObjectParallel(obj)) { 135ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (kDisableFinger || (check_finger && obj < finger_)) { 136ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier while (UNLIKELY(!mark_stack_->AtomicPushBack(const_cast<Object*>(obj)))) { 137ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Only reason a push can fail is that the mark stack is full. 138ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier ExpandMarkStack(); 139ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 140ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 141ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 142ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 143ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 14402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierinline void MarkSweep::MarkObjectNonNull(const Object* obj, bool check_finger) { 14569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 146b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 147e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (obj >= immune_begin_ && obj < immune_end_) { 148e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier DCHECK(IsMarked(obj)); 149357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return; 150357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 151357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 152b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Try to take advantage of locality of references within a space, failing this find the space 153b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // the hard way. 15402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier SpaceBitmap* object_bitmap = current_mark_bitmap_; 15502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 156e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj); 157e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (new_bitmap != NULL) { 15802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap = new_bitmap; 159e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else { 16002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkLargeObject(obj); 161e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier return; 162357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 163b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 164b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 16569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // This object was not previously marked. 16602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (!object_bitmap->Test(obj)) { 16702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap->Set(obj); 16802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kDisableFinger || (check_finger && obj < finger_)) { 169d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Do we need to expand the mark stack? 170d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 171ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier ExpandMarkStack(); 172d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 17369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // The object must be pushed on to the mark stack. 174d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack_->PushBack(const_cast<Object*>(obj)); 17569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 17669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 17769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 17869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 17902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Rare case, probably not worth inlining since it will increase instruction cache miss rate. 18002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierbool MarkSweep::MarkLargeObject(const Object* obj) { 18102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 18202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier SpaceSetMap* large_objects = large_object_space->GetMarkObjects(); 18302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 18402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++large_object_test_; 18502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 18602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!large_objects->Test(obj))) { 18702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (!large_object_space->Contains(obj)) { 18802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces"; 18902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(ERROR) << "Attempting see if it's a bad root"; 19002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier VerifyRoots(); 19102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(FATAL) << "Can't mark bad root"; 19202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 19302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 19402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++large_object_mark_; 19502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 19602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier large_objects->Set(obj); 19702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Don't need to check finger since large objects never have any object references. 19802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return true; 19902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 20002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return false; 20102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 20202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierinline bool MarkSweep::MarkObjectParallel(const Object* obj) { 20402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(obj != NULL); 20502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (obj >= immune_begin_ && obj < immune_end_) { 20702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(IsMarked(obj)); 20802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return false; 20902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 21002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 21102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Try to take advantage of locality of references within a space, failing this find the space 21202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // the hard way. 21302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier SpaceBitmap* object_bitmap = current_mark_bitmap_; 21402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 21502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj); 21602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (new_bitmap != NULL) { 21702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap = new_bitmap; 21802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 21902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Remove the Thread::Current here? 22002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Convert this to some kind of atomic marking? 22102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(Thread::Current(), large_object_lock_); 22202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return MarkLargeObject(obj); 22302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 22402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 22502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 22602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Return true if the object was not previously marked. 22702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return !object_bitmap->AtomicTestAndSet(obj); 22802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 22902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 23069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Used to mark objects when recursing. Recursion is done by moving 23169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger across the bitmaps in address order and marking child 23269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// objects. Any newly-marked objects whose addresses are lower than 23369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger won't be visited by the bitmap scan, so those objects 23469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// need to be added to the mark stack. 235b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::MarkObject(const Object* obj) { 23669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj != NULL) { 23702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectNonNull(obj, true); 23869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 23969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 24069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 241ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartiervoid MarkSweep::MarkRootParallelCallback(const Object* root, void* arg) { 242ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(root != NULL); 243ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(arg != NULL); 244ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 245ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_sweep->MarkObjectNonNullParallel(root, false); 246ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 247ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 24802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid MarkSweep::MarkObjectCallback(const Object* root, void* arg) { 2491f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(root != NULL); 2501f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(arg != NULL); 2511f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 25202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep->MarkObjectNonNull(root, false); 2531f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom} 2541f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 255262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) { 256262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(root != NULL); 257262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(arg != NULL); 258262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 25902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep->MarkObjectNonNull(root, true); 260262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 261262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 2626f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartiervoid MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg, 2636f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier const AbstractMethod* method) { 2646f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier reinterpret_cast<MarkSweep*>(arg)->VerifyRoot(root, vreg, method); 2656f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 2666f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 2676f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartiervoid MarkSweep::VerifyRoot(const Object* root, size_t vreg, const AbstractMethod* method) { 2686f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier // See if the root is on any space bitmap. 269128c52c3f97e6726a77cf2f704100915cf6bb9d3Mathieu Chartier if (GetHeap()->GetLiveBitmap()->GetSpaceBitmap(root) == NULL) { 2706f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 2714202b7484dab71ca4dfc2109ebb3fd04b87badfbMathieu Chartier if (!large_object_space->Contains(root)) { 2726f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier LOG(ERROR) << "Found invalid root: " << root; 27308254278f290c2541cecd24ce6b7015427f4eae5Ian Rogers LOG(ERROR) << "VReg: " << vreg; 2746f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier if (method != NULL) { 27508254278f290c2541cecd24ce6b7015427f4eae5Ian Rogers LOG(ERROR) << "In method " << PrettyMethod(method, true) << "\nVerifier output:\n"; 27608254278f290c2541cecd24ce6b7015427f4eae5Ian Rogers verifier::MethodVerifier::VerifyMethodAndDump(const_cast<AbstractMethod*>(method)); 2776f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 2786f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 2796f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 2806f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 2816f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 2826f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartiervoid MarkSweep::VerifyRoots() { 2836f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier Runtime::Current()->GetThreadList()->VerifyRoots(VerifyRootCallback, this); 2846f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 2856f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 28669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Marks all objects in the root set. 28769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkRoots() { 28802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Runtime::Current()->VisitNonConcurrentRoots(MarkObjectCallback, this); 2899ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier} 2909ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier 291858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartiervoid MarkSweep::MarkNonThreadRoots() { 29202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Runtime::Current()->VisitNonThreadRoots(MarkObjectCallback, this); 293858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier} 294858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 2959ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartiervoid MarkSweep::MarkConcurrentRoots() { 29602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Runtime::Current()->VisitConcurrentRoots(MarkObjectCallback, this); 29769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 29869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 299b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartierclass CheckObjectVisitor { 300b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier public: 301b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier CheckObjectVisitor(MarkSweep* const mark_sweep) 302b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier : mark_sweep_(mark_sweep) { 303b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 304b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier } 305b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 30600f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const 307d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier NO_THREAD_SAFETY_ANALYSIS { 308b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep_->CheckReference(obj, ref, offset, is_static); 309b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier } 310b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 311b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier private: 312b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* const mark_sweep_; 313b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier}; 314b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 315b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckObject(const Object* obj) { 316b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(obj != NULL); 317b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier CheckObjectVisitor visitor(this); 318b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier VisitObjectReferences(obj, visitor); 319b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 320b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 321b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) { 322b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(root != NULL); 323b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(arg != NULL); 324b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 325b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root)); 326b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep->CheckObject(root); 327b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 328b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 3292fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartiervoid MarkSweep::CopyMarkBits(ContinuousSpace* space) { 330357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 331357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 332357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_bitmap->CopyFrom(live_bitmap); 3335d76c435082332ef79a22962386fa92a0870e378Ian Rogers} 3345d76c435082332ef79a22962386fa92a0870e378Ian Rogers 3357469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::BindLiveToMarkBitmap(ContinuousSpace* space) { 3367469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier CHECK(space->IsAllocSpace()); 3371c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier DlMallocSpace* alloc_space = space->AsAllocSpace(); 3387469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 3397469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SpaceBitmap* mark_bitmap = alloc_space->mark_bitmap_.release(); 3407469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->GetMarkBitmap()->ReplaceBitmap(mark_bitmap, live_bitmap); 3417469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->temp_bitmap_.reset(mark_bitmap); 3427469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->mark_bitmap_.reset(live_bitmap); 3437469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 3447469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 34502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass ScanObjectVisitor { 346cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 34702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 34802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 349cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 350cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 35102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void operator ()(const Object* obj) const 352b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 353b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 35402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->ScanObject(obj); 355cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 356cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 357cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 358cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* const mark_sweep_; 359cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 360cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 361d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartiervoid MarkSweep::ScanGrayObjects(byte minimum_age) { 362357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 363262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier CardTable* card_table = heap_->GetCardTable(); 36402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisitor visitor(this); 365357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor finger_visitor(this); 366e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // TODO: C++ 0x auto 367357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 3682fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 369357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* begin = space->Begin(); 370357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* end = space->End(); 371b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Image spaces are handled properly since live == marked for them. 372357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 373d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier card_table->Scan(mark_bitmap, begin, end, visitor, VoidFunctor(), minimum_age); 374262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 375262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 376262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 377cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartierclass CheckBitmapVisitor { 378cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 379cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier CheckBitmapVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) { 380cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 381cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 382cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 38300f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* obj) const 384b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, 385b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers Locks::mutator_lock_) { 386cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier DCHECK(obj != NULL); 387cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier mark_sweep_->CheckObject(obj); 388cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 389cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 390cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 391cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* mark_sweep_; 392cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 393cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 394262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::VerifyImageRoots() { 395262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // Verify roots ensures that all the references inside the image space point 396262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // objects which are either in the image space or marked objects in the alloc 397262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // space 398cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier CheckBitmapVisitor visitor(this); 399cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 400cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 4012fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier if ((*it)->IsImageSpace()) { 4022fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ImageSpace* space = (*it)->AsImageSpace(); 403cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 404cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 405cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 406b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(live_bitmap != NULL); 407d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier live_bitmap->VisitMarkedRange(begin, end, visitor, VoidFunctor()); 408262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 409262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 410262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 411262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 41258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Populates the mark stack based on the set of marked objects and 41358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// recursively marks until the mark stack is emptied. 414357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::RecursiveMark(bool partial, TimingLogger& timings) { 4151f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // RecursiveMark will build the lists of known instances of the Reference classes. 4161f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // See DelayReferenceReferent for details. 4171f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(soft_reference_list_ == NULL); 4181f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(weak_reference_list_ == NULL); 4191f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(finalizer_reference_list_ == NULL); 4201f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(phantom_reference_list_ == NULL); 4211f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(cleared_reference_list_ == NULL); 4221f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 423cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 424357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor set_finger_visitor(this); 425357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObjectVisitor scan_visitor(this); 426357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 4272fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 42802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if ((!kDisableFinger && space->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect) || 4297469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier (!partial && space->GetGcRetentionPolicy() == kGcRetentionPolicyFullCollect) 430cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ) { 431357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_ = space->GetMarkBitmap(); 432357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL) { 433357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier GetHeap()->DumpSpaces(); 434e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LOG(FATAL) << "invalid bitmap"; 435357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 436357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // This function does not handle heap end increasing, so we must use the space end. 437cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 438cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 439357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor, set_finger_visitor); 4407664f5cd118b355a5fe0c7536cb48ac991ed2b62Mathieu Chartier } 44158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 44258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro finger_ = reinterpret_cast<Object*>(~0); 443357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("RecursiveMark"); 4445d76c435082332ef79a22962386fa92a0870e378Ian Rogers // TODO: tune the frequency of emptying the mark stack 44558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ProcessMarkStack(); 446357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("ProcessMarkStack"); 447357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 448357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 449357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::RecursiveMarkCards(CardTable* card_table, const std::vector<byte*>& cards, 450357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier TimingLogger& timings) { 45102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisitor image_root_visitor(this); 452357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor finger_visitor(this); 4537469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier const size_t card_count = cards.size(); 4547469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SpaceBitmap* active_bitmap = NULL; 4557469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier for (size_t i = 0;i < card_count;) { 456357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object* start_obj = reinterpret_cast<Object*>(card_table->AddrFromCard(cards[i])); 457357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(start_obj); 4587469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier uintptr_t end = begin + CardTable::kCardSize; 4597469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier for (++i; reinterpret_cast<uintptr_t>(cards[i]) == end && i < card_count; ++i) { 4607469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier end += CardTable::kCardSize; 461357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 4627469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (active_bitmap == NULL || !active_bitmap->HasAddress(start_obj)) { 4637469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier active_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(start_obj); 46402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kIsDebugBuild && active_bitmap == NULL) { 465357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier GetHeap()->DumpSpaces(); 466e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LOG(FATAL) << "Object " << reinterpret_cast<const void*>(start_obj); 467357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 468357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 46902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kDisableFinger) { 470d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, VoidFunctor()); 47102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 47202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor); 47302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 474357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 475357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("RecursiveMarkCards"); 476357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ProcessMarkStack(); 477357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("ProcessMarkStack"); 47858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 47958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 480357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierbool MarkSweep::IsMarkedCallback(const Object* object, void* arg) { 481357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return 482357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier reinterpret_cast<MarkSweep*>(arg)->IsMarked(object) || 483357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object); 484357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 485357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 486d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartiervoid MarkSweep::RecursiveMarkDirtyObjects(byte minimum_age) { 487d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier ScanGrayObjects(minimum_age); 488262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier ProcessMarkStack(); 489262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 490262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 49158551df3c2646ed507feec9e9eb3768085a76059Carl Shapirovoid MarkSweep::ReMarkRoots() { 492262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier Runtime::Current()->VisitRoots(ReMarkObjectVisitor, this); 49358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 49458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 4957469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::SweepJniWeakGlobals(Heap::IsMarkedTester is_marked, void* arg) { 496410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes JavaVMExt* vm = Runtime::Current()->GetJavaVM(); 49750b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 498410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes IndirectReferenceTable* table = &vm->weak_globals; 499654d3a217faf46310895a1825354d610c2f3d6c2Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 500410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes for (It it = table->begin(), end = table->end(); it != end; ++it) { 501410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes const Object** entry = *it; 5027469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (!is_marked(*entry, arg)) { 503410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes *entry = kClearedJniWeakGlobal; 504410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 505410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 506410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes} 507410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes 5087469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierstruct ArrayMarkedCheck { 5097469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ObjectStack* live_stack; 5107469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier MarkSweep* mark_sweep; 5117469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier}; 5127469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 5137469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier// Either marked or not live. 5147469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierbool MarkSweep::IsMarkedArrayCallback(const Object* object, void* arg) { 5157469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ArrayMarkedCheck* array_check = reinterpret_cast<ArrayMarkedCheck*>(arg); 5167469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (array_check->mark_sweep->IsMarked(object)) { 5177469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return true; 5187469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 5197469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ObjectStack* live_stack = array_check->live_stack; 5207469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return std::find(live_stack->Begin(), live_stack->End(), object) == live_stack->End(); 5217469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 5227469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 5237469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::SweepSystemWeaksArray(ObjectStack* allocations) { 52446a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier Runtime* runtime = Runtime::Current(); 525357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // The callbacks check 526357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !is_marked where is_marked is the callback but we want 527357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !IsMarked && IsLive 528357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive). 529357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Or for swapped (IsLive || !IsMarked). 5307469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 5317469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ArrayMarkedCheck visitor; 5327469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier visitor.live_stack = allocations; 5337469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier visitor.mark_sweep = this; 5347469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(IsMarkedArrayCallback, &visitor); 5357469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetMonitorList()->SweepMonitorList(IsMarkedArrayCallback, &visitor); 5367469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepJniWeakGlobals(IsMarkedArrayCallback, &visitor); 5377469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 5387469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 5397469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::SweepSystemWeaks() { 5407469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier Runtime* runtime = Runtime::Current(); 5417469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // The callbacks check 5427469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // !is_marked where is_marked is the callback but we want 5437469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // !IsMarked && IsLive 5447469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive). 5457469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // Or for swapped (IsLive || !IsMarked). 5467469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(IsMarkedCallback, this); 5477469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetMonitorList()->SweepMonitorList(IsMarkedCallback, this); 5487469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepJniWeakGlobals(IsMarkedCallback, this); 54969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 55069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 551c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartierbool MarkSweep::VerifyIsLiveCallback(const Object* obj, void* arg) { 552c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 553c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // We don't actually want to sweep the object, so lets return "marked" 554c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier return true; 555c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 556c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 557c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifyIsLive(const Object* obj) { 558c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Heap* heap = GetHeap(); 559c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier if (!heap->GetLiveBitmap()->Test(obj)) { 5607469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 5617469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (!large_object_space->GetLiveObjects()->Test(obj)) { 5627469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 5637469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier heap->allocation_stack_->End()) { 5647469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // Object not found! 5657469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier heap->DumpSpaces(); 5667469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier LOG(FATAL) << "Found dead object " << obj; 5677469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 568c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 569c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 570c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 571c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 572c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifySystemWeaks() { 573c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Runtime* runtime = Runtime::Current(); 574c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // Verify system weaks, uses a special IsMarked callback which always returns true. 575c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(VerifyIsLiveCallback, this); 576c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetMonitorList()->SweepMonitorList(VerifyIsLiveCallback, this); 577c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 578c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier JavaVMExt* vm = runtime->GetJavaVM(); 57950b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 580c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier IndirectReferenceTable* table = &vm->weak_globals; 581c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 582c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier for (It it = table->begin(), end = table->end(); it != end; ++it) { 583c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier const Object** entry = *it; 584c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier VerifyIsLive(*entry); 585c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 586c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 587c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 588b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughesstruct SweepCallbackContext { 589357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep; 590b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes AllocSpace* space; 59150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self; 592b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes}; 593b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 5940e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartierclass CheckpointMarkThreadRoots : public Closure { 595858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier public: 596858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier CheckpointMarkThreadRoots(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) { 597858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 598858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier } 599858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 600858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS { 601858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier // Note: self is not necessarily equal to thread since thread may be suspended. 602858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier Thread* self = Thread::Current(); 603d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 604d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier << thread->GetState() << " thread " << thread << " self " << self; 605ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier thread->VisitRoots(MarkSweep::MarkRootParallelCallback, mark_sweep_); 606858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier mark_sweep_->GetBarrier().Pass(self); 607858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier } 608858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 609858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier private: 610858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier MarkSweep* mark_sweep_; 611858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier}; 612858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 613858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu ChartierBarrier& MarkSweep::GetBarrier() { 614858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier return *gc_barrier_; 615858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier} 616858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 617858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartiervoid MarkSweep::MarkRootsCheckpoint() { 618d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier CheckpointMarkThreadRoots check_point(this); 619858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier ThreadList* thread_list = Runtime::Current()->GetThreadList(); 620858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier // Increment the count of the barrier. If all of the checkpoints have already been finished then 621858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier // will hit 0 and continue. Otherwise we are still waiting for some checkpoints, so the counter 622858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier // will go positive and we will unblock when it hits zero. 623d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier gc_barrier_->Increment(Thread::Current(), thread_list->RunCheckpoint(&check_point)); 624858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier} 625858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 62630fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogersvoid MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 627b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 628357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep = context->mark_sweep; 629357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = mark_sweep->GetHeap(); 630b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes AllocSpace* space = context->space; 63150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = context->self; 63250b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(self); 6335d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Use a bulk free, that merges consecutive objects before freeing or free per object? 6345d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Documentation suggests better free performance with merging, but this may be at the expensive 6355d76c435082332ef79a22962386fa92a0870e378Ian Rogers // of allocation. 63602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t freed_objects = num_ptrs; 63702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit 63802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t freed_bytes = space->FreeList(self, num_ptrs, ptrs); 63900f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers heap->RecordFree(freed_objects, freed_bytes); 640357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_objects_ += freed_objects; 641357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_bytes_ += freed_bytes; 64258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 64358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 644cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 645cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 64650b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(context->self); 647357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = context->mark_sweep->GetHeap(); 648cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // We don't free any actual memory to avoid dirtying the shared zygote pages. 649cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (size_t i = 0; i < num_ptrs; ++i) { 650cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier Object* obj = static_cast<Object*>(ptrs[i]); 651cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetLiveBitmap()->Clear(obj); 652cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetCardTable()->MarkCard(obj); 653cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 654cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 655cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 656d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartiervoid MarkSweep::SweepArray(TimingLogger& logger, ObjectStack* allocations, bool swap_bitmaps) { 657357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_bytes = 0; 6581c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier DlMallocSpace* space = heap_->GetAllocSpace(); 659357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 660357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 661357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 6627469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepSystemWeaksArray(allocations); 6637469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier logger.AddSplit("SweepSystemWeaks"); 664357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 665357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Newly allocated objects MUST be in the alloc space and those are the only objects which we are 666357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // going to free. 667357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 668357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 669e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 670e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 671e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 672357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (swap_bitmaps) { 673357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::swap(live_bitmap, mark_bitmap); 674e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 675357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 676357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 677e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_large_objects = 0; 678357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t count = allocations->Size(); 679d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier Object** objects = const_cast<Object**>(allocations->Begin()); 680357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object** out = objects; 681357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 682357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Empty the allocation stack. 68350b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 684357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (size_t i = 0;i < count;++i) { 685357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object* obj = objects[i]; 686e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // There should only be objects in the AllocSpace/LargeObjectSpace in the allocation stack. 687e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (LIKELY(mark_bitmap->HasAddress(obj))) { 688e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!mark_bitmap->Test(obj)) { 689e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Don't bother un-marking since we clear the mark bitmap anyways. 690e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier *(out++) = obj; 691e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 692e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else if (!large_mark_objects->Test(obj)) { 693e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_large_objects; 6941c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += large_object_space->Free(self, obj); 695357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 696357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 697357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier logger.AddSplit("Process allocation stack"); 698357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 699357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_objects = out - objects; 7001c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += space->FreeList(self, freed_objects, objects); 70140e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier VLOG(heap) << "Freed " << freed_objects << "/" << count 702e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier << " objects with size " << PrettySize(freed_bytes); 703e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes); 70440e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_objects_ += freed_objects; 70540e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_bytes_ += freed_bytes; 70640e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier logger.AddSplit("FreeList"); 707357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier allocations->Reset(); 708d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier logger.AddSplit("ResetStack"); 709357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 710357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 71102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid MarkSweep::Sweep(TimingLogger& timings, bool partial, bool swap_bitmaps) { 712b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 713b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 714357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 715357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 7167469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepSystemWeaks(); 71702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier timings.AddSplit("SweepSystemWeaks"); 718357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 71946a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 720b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext scc; 721357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier scc.mark_sweep = this; 72250b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers scc.self = Thread::Current(); 723357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // TODO: C++0x auto 724357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 7252fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 726cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if ( 7277469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier space->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect || 7287469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier (!partial && space->GetGcRetentionPolicy() == kGcRetentionPolicyFullCollect) 729cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ) { 730cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 731cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 732cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier scc.space = space->AsAllocSpace(); 733cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 734cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 735fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier if (swap_bitmaps) { 736fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier std::swap(live_bitmap, mark_bitmap); 737fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier } 7387469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (space->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect) { 739cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked. 740357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 741357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier &SweepCallback, reinterpret_cast<void*>(&scc)); 742cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } else { 743cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual memory. 744357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 745357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier &ZygoteSweepCallback, reinterpret_cast<void*>(&scc)); 746cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 74758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 74858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 74902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier timings.AddSplit("Sweep"); 75058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 75158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 752e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 753e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Sweep large objects 754e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 755e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 756e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 757e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (swap_bitmaps) { 758e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 759e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 760e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap::Objects& live_objects = large_live_objects->GetObjects(); 761e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // O(n*log(n)) but hopefully there are not too many large objects. 762e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_objects = 0; 7632fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier size_t freed_bytes = 0; 764e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // TODO: C++0x 76550b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 766e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier for (SpaceSetMap::Objects::iterator it = live_objects.begin(); it != live_objects.end(); ++it) { 767e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!large_mark_objects->Test(*it)) { 7681c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += large_object_space->Free(self, const_cast<Object*>(*it)); 769e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_objects; 770e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 771e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 772e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier freed_objects_ += freed_objects; 7732fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier freed_bytes_ += freed_bytes; 774e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Large objects don't count towards bytes_allocated. 7752fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier GetHeap()->RecordFree(freed_objects, freed_bytes); 776e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 777e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 778b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) { 779b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 780b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // TODO: C++0x auto 781b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) { 782b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) { 783b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(IsMarked(obj)); 784b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 785b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool is_marked = IsMarked(ref); 786b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!is_marked) { 787b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(INFO) << **cur; 788b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref) 789b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj) 790b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(obj) << ") at offset " 791b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked"; 792b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 793b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Class* klass = is_static ? obj->AsClass() : obj->GetClass(); 794b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(klass != NULL); 795b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields(); 796b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(fields != NULL); 797b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool found = false; 798b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); ++i) { 799b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Field* cur = fields->Get(i); 800b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (cur->GetOffset().Int32Value() == offset.Int32Value()) { 801b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur); 802b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier found = true; 803b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 804b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 805b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 806b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!found) { 807b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value(); 808262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 809262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 810b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool obj_marked = heap_->GetCardTable()->IsDirty(obj); 811b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!obj_marked) { 812b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' " 813b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "(" << reinterpret_cast<const void*>(obj) << ") contains references to " 814b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "the alloc space, but wasn't card marked"; 815b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 8165d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 8175d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 818b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 8195d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 8205d76c435082332ef79a22962386fa92a0870e378Ian Rogers} 8215d76c435082332ef79a22962386fa92a0870e378Ian Rogers 82269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Process the "referent" field in a java.lang.ref.Reference. If the 82369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent has not yet been marked, put it on the appropriate list in 82469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the gcHeap for later processing. 82569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::DelayReferenceReferent(Object* obj) { 82669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 8271f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom Class* klass = obj->GetClass(); 8281f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(klass != NULL); 8290cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers DCHECK(klass->IsReferenceClass()); 830b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false); 831b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(obj); 832d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountJavaLangRefs) { 833d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier ++reference_count_; 834d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier } 83569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (pending == NULL && referent != NULL && !IsMarked(referent)) { 8364873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom Object** list = NULL; 8370cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers if (klass->IsSoftReferenceClass()) { 83869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &soft_reference_list_; 8390cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsWeakReferenceClass()) { 84069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &weak_reference_list_; 8410cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsFinalizerReferenceClass()) { 84269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &finalizer_reference_list_; 8430cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsPhantomReferenceClass()) { 84469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &phantom_reference_list_; 84569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 8460796af03edc06d92bb8d631f1c0c23befdae2315Brian Carlstrom DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags(); 84702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: One lock per list? 848b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(obj, list); 84969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 85069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 85169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 852357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::ScanRoot(const Object* obj) { 853357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObject(obj); 854357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 855357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 85602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass MarkObjectVisitor { 85702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier public: 85802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 85902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 86002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 86102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void operator ()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, 862d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier bool /* is_static */) const EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 86302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->MarkObject(ref); 86402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 86502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 86602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier private: 86702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkSweep* const mark_sweep_; 86802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier}; 86902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 87069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans an object reference. Determines the type of the reference 87169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// and dispatches to a specialized scanning routine. 872cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ScanObject(const Object* obj) { 87302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectVisitor visitor(this); 87402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisit(obj, visitor); 87502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 87602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 87702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass MarkStackChunk : public Task { 87802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierpublic: 87902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk(ThreadPool* thread_pool, MarkSweep* mark_sweep, Object** begin, Object** end) 88002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier : mark_sweep_(mark_sweep), 88102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool_(thread_pool), 88202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier index_(0), 88302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier length_(0), 88402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_(NULL) { 88502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier length_ = end - begin; 88602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (begin != end) { 88702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Cost not significant since we only do this for the initial set of mark stack chunks. 88802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier memcpy(data_, begin, length_ * sizeof(*begin)); 88902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 89002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 89102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++mark_sweep_->work_chunks_created_; 89202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 89302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 89402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 89502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ~MarkStackChunk() { 89602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(output_ == NULL || output_->length_ == 0); 89702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK_GE(index_, length_); 89802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier delete output_; 89902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 90002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++mark_sweep_->work_chunks_deleted_; 90102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 90202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 90302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 90402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkSweep* const mark_sweep_; 90502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* const thread_pool_; 90602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier static const size_t max_size = 1 * KB; 90702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Index of which object we are scanning. Only needs to be atomic if we are doing work stealing. 90802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t index_; 90902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Input / output mark stack. We add newly marked references to data_ until length reaches 91002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // max_size. This is an optimization so that less tasks are created. 91102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Investigate using a bounded buffer FIFO. 91202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object* data_[max_size]; 91302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // How many elements in data_ we need to scan. 91402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t length_; 91502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Output block, newly marked references get added to the ouput block so that another thread can 91602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // scan them. 91702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk* output_; 91802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 91902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier class MarkObjectParallelVisitor { 92002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier public: 92102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectParallelVisitor(MarkStackChunk* chunk_task) : chunk_task_(chunk_task) { 92202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 92302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 92402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 92502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void operator ()(const Object* /* obj */, const Object* ref, 92602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const MemberOffset& /* offset */, bool /* is_static */) const { 92702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (ref != NULL && chunk_task_->mark_sweep_->MarkObjectParallel(ref)) { 92802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier chunk_task_->MarkStackPush(ref); 92902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 93002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 93102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 93202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier private: 93302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk* const chunk_task_; 93402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier }; 93502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 93602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Push an object into the block. 93702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Don't need to use atomic ++ since we only one thread is writing to an output block at any 93802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // given time. 93902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void Push(Object* obj) { 94002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier data_[length_++] = obj; 94169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 94202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 94302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void MarkStackPush(const Object* obj) { 94402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (static_cast<size_t>(length_) < max_size) { 94502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Push(const_cast<Object*>(obj)); 94602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 94702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Internal buffer is full, push to a new buffer instead. 94802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(output_ == NULL)) { 94902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier AllocateOutputChunk(); 95002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else if (UNLIKELY(static_cast<size_t>(output_->length_) == max_size)) { 95102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Output block is full, queue it up for processing and obtain a new block. 95202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier EnqueueOutput(); 95302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier AllocateOutputChunk(); 95402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 95502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_->Push(const_cast<Object*>(obj)); 95602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 95702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 95802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 95902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void ScanObject(Object* obj) { 96002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->ScanObjectVisit(obj, MarkObjectParallelVisitor(this)); 96102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 96202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 96302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void EnqueueOutput() { 96402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (output_ != NULL) { 96502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier uint64_t start = 0; 96602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 96702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start = NanoTime(); 96802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 96902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool_->AddTask(Thread::Current(), output_); 97002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_ = NULL; 97102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 97202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->overhead_time_ += NanoTime() - start; 97302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 97402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 97502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 97602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 97702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void AllocateOutputChunk() { 97802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier uint64_t start = 0; 97902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 98002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start = NanoTime(); 98102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 98202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_ = new MarkStackChunk(thread_pool_, mark_sweep_, NULL, NULL); 98302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 98402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->overhead_time_ += NanoTime() - start; 98502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 98602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 98702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 98802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void Finalize() { 98902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier EnqueueOutput(); 99002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier delete this; 99102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 99202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 99302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Scans all of the objects 99402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier virtual void Run(Thread* self) { 99502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier int index; 99602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while ((index = index_++) < length_) { 99702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kUseMarkStackPrefetch) { 998d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier static const size_t prefetch_look_ahead = 1; 999d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier __builtin_prefetch(data_[std::min(index + prefetch_look_ahead, length_ - 1)]); 100002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 100102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object* obj = data_[index]; 100202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(obj != NULL); 100302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObject(obj); 100402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 100502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 100602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier}; 100702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 100802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid MarkSweep::ProcessMarkStackParallel() { 100902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK(kDisableFinger) << "parallel mark stack processing cannot work when finger is enabled"; 101002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Thread* self = Thread::Current(); 101102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 101202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Split the current mark stack up into work tasks. 101302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t num_threads = thread_pool->GetThreadCount(); 101402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t stack_size = mark_stack_->Size(); 101502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t chunk_size = 101602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier std::min((stack_size + num_threads - 1) / num_threads, 101702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier static_cast<size_t>(MarkStackChunk::max_size)); 101802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t index = 0; 101902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier for (size_t i = 0; i < num_threads || index < stack_size; ++i) { 102002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object** begin = &mark_stack_->Begin()[std::min(stack_size, index)]; 102102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object** end = &mark_stack_->Begin()[std::min(stack_size, index + chunk_size)]; 102202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier index += chunk_size; 102302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool->AddTask(self, new MarkStackChunk(thread_pool, this, begin, end)); 102402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 102502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool->StartWorkers(self); 102602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_stack_->Reset(); 102702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool->Wait(self, true); 102802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier //LOG(INFO) << "Idle wait time " << PrettyDuration(thread_pool->GetWaitTime()); 102902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked"; 103069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 103169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 10325d76c435082332ef79a22962386fa92a0870e378Ian Rogers// Scan anything that's on the mark stack. 103369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessMarkStack() { 103402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 103502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kParallelMarkStack && thread_pool != NULL && thread_pool->GetThreadCount() > 0) { 103602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ProcessMarkStackParallel(); 103702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return; 103802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 103902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1040d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (kUseMarkStackPrefetch) { 1041d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_size = 4; 1042d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_mask = fifo_size - 1; 1043d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* fifo[fifo_size]; 1044d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (size_t i = 0;i < fifo_size;++i) { 1045d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[i] = NULL; 1046357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 1047d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_pos = 0; 1048d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_count = 0; 1049d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (;;) { 1050d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = fifo[fifo_pos & fifo_mask]; 1051d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (obj != NULL) { 1052d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 1053d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = NULL; 1054d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier --fifo_count; 1055d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1056357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1057d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!mark_stack_->IsEmpty()) { 1058d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 1059d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 1060d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = obj; 1061d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier __builtin_prefetch(obj); 1062d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_count++; 1063d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1064d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_pos++; 1065357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1066d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!fifo_count) { 1067d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier CHECK(mark_stack_->IsEmpty()) << mark_stack_->Size(); 1068d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier break; 1069d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1070d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1071d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } else { 1072d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier while (!mark_stack_->IsEmpty()) { 1073d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 1074d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 1075d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 1076357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 1077357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 107869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 107969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 108069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Walks the reference list marking any references subject to the 108169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// reference clearing policy. References with a black referent are 108269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// removed from the list. References with white referents biased 108369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// toward saving are blackened and also removed from the list. 108469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::PreserveSomeSoftReferences(Object** list) { 108569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 108669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* clear = NULL; 108769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t counter = 0; 1088b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 1089b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 1090b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 109169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1092b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1093b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 109469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent == NULL) { 109569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent was cleared by the user during marking. 109669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro continue; 109769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 109869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool is_marked = IsMarked(referent); 109969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked && ((++counter) & 1)) { 110069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white and biased toward saving, mark it. 110169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 110269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro is_marked = true; 110369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 110469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked) { 110569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, queue it for clearing. 1106b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(ref, &clear); 110769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 110869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 110969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = clear; 111069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Restart the mark with the newly black references added to the 111169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // root set. 111269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 111369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 111469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 11157469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierinline bool MarkSweep::IsMarked(const Object* object) const 11167469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 11177469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (object >= immune_begin_ && object < immune_end_) { 11187469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return true; 11197469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 11207469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier DCHECK(current_mark_bitmap_ != NULL); 11217469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (current_mark_bitmap_->HasAddress(object)) { 11227469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return current_mark_bitmap_->Test(object); 11237469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 11247469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return heap_->GetMarkBitmap()->Test(object); 11257469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 11267469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 11277469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 112869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Unlink the reference list clearing references objects with white 112969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents. Cleared references registered to a reference queue are 113069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scheduled for appending by the heap worker thread. 113169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ClearWhiteReferences(Object** list) { 113269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 113369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1134b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1135b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 113669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 113769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, clear it. 1138b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 1139b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes if (heap_->IsEnqueuable(ref)) { 1140b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 114169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 114269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 114369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 114469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 114569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 114669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 114769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Enqueues finalizer references with white referents. White 114869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents are blackened, moved to the zombie field, and the 114969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent field is cleared. 115069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueFinalizerReferences(Object** list) { 115169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 1152b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes MemberOffset zombie_offset = heap_->GetFinalizerReferenceZombieOffset(); 115369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool has_enqueued = false; 115469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1155b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1156b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 115769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 115869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 115969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // If the referent is non-null the reference must queuable. 1160b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes DCHECK(heap_->IsEnqueuable(ref)); 11610cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers ref->SetFieldObject(zombie_offset, referent, false); 1162b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 1163b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 116469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro has_enqueued = true; 116569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 116669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 116769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (has_enqueued) { 116869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 116969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 117069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 117169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 117269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 117358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Process reference class instances and schedule finalizations. 117469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft, 117569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** weak_references, 117669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** finalizer_references, 117769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** phantom_references) { 117869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(soft_references != NULL); 117969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(weak_references != NULL); 118069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(finalizer_references != NULL); 118169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(phantom_references != NULL); 118269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 118369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Unless we are in the zygote or required to clear soft references 118469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // with white references, preserve some white referents. 11852945e2455ba87e15b65f4a6a737bcdc8c0f2f31bIan Rogers if (!clear_soft && !Runtime::Current()->IsZygote()) { 118669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro PreserveSomeSoftReferences(soft_references); 118769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 118869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 118969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all remaining soft and weak references with white 119069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 119169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 119269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 119369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 119469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Preserve all white objects with finalize methods and schedule 119569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // them for finalization. 119669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueFinalizerReferences(finalizer_references); 119769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 119869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all f-reachable soft and weak references with white 119969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 120069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 120169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 120269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 120369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all phantom references with white referents. 120469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(phantom_references); 120569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 120669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // At this point all reference lists should be empty. 120769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*soft_references == NULL); 120869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*weak_references == NULL); 120969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*finalizer_references == NULL); 121069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*phantom_references == NULL); 121169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 121269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 12137469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::UnBindBitmaps() { 12147469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 12157469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // TODO: C++0x auto 12167469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 12177469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier Space* space = *it; 12187469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (space->IsAllocSpace()) { 12191c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier DlMallocSpace* alloc_space = space->AsAllocSpace(); 12207469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (alloc_space->temp_bitmap_.get() != NULL) { 12217469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // At this point, the temp_bitmap holds our old mark bitmap. 12227469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SpaceBitmap* new_bitmap = alloc_space->temp_bitmap_.release(); 12237469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->GetMarkBitmap()->ReplaceBitmap(alloc_space->mark_bitmap_.get(), new_bitmap); 12247469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier CHECK_EQ(alloc_space->mark_bitmap_.release(), alloc_space->live_bitmap_.get()); 12257469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->mark_bitmap_.reset(new_bitmap); 12267469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier DCHECK(alloc_space->temp_bitmap_.get() == NULL); 12277469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 12287469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 12297469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 12307469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 12317469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 123269759eaa6fd4386f1e6d8748052ad221087b3476Carl ShapiroMarkSweep::~MarkSweep() { 1233d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountScannedTypes) { 1234d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ 1235d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier << " other=" << other_count_; 123602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 123702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 123802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 1239d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_; 124002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 124102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 124202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 1243d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_); 124402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 124502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 124602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 1247d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_; 124802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 124902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 125002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountClassesMarked) { 1251d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Classes marked " << classes_marked_; 1252d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier } 1253d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier 1254d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountJavaLangRefs) { 1255d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "References scanned " << reference_count_; 125602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 125702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1258357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Ensure that the mark stack is empty. 1259357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK(mark_stack_->IsEmpty()); 1260357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 126102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Clear all of the spaces' mark bitmaps. 1262b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 1263b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // TODO: C++0x auto 1264357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 12657469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ContinuousSpace* space = *it; 12667469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (space->GetGcRetentionPolicy() != kGcRetentionPolicyNeverCollect) { 12677469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier space->GetMarkBitmap()->Clear(); 1268b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 1269b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 12705301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier mark_stack_->Reset(); 1271e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 1272e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Reset the marked large objects. 1273e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 1274e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier large_objects->GetMarkObjects()->Clear(); 127569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 127669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 127769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} // namespace art 1278