mark_sweep.cc revision 93ba893c20532990a430741e0a97212900094e8c
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 192b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier#include <functional> 202b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier#include <numeric> 2158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <climits> 2258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <vector> 2358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 2407ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 25761600567d73b23324ae0251e871c15d6849ffd8Elliott Hughes#include "base/macros.h" 26693ff61274cd2c9b8eb7e68c370f84a911b8ca52Ian Rogers#include "base/mutex-inl.h" 27a84395489098e4531619b1cffd1afc282b14510eSameer Abu Asal#include "base/timing_logger.h" 281d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/accounting/card_table-inl.h" 291d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/accounting/heap_bitmap.h" 301d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/accounting/space_bitmap-inl.h" 311d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/heap.h" 321d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/space/image_space.h" 331d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/space/large_object_space.h" 341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "gc/space/space-inl.h" 35410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "indirect_reference_table.h" 36410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "intern_table.h" 3781d425b0b232962441616f8b14f73620bffef5e5Ian Rogers#include "jni_internal.h" 38c33a32bccc4c66ed82ce3a580b16636399385cb4Elliott Hughes#include "monitor.h" 392dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mark_sweep-inl.h" 402dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/class-inl.h" 412dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/class_loader.h" 422dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/dex_cache.h" 432dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/field.h" 442dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/field-inl.h" 452dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object-inl.h" 462dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object_array.h" 472dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "mirror/object_array-inl.h" 481f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom#include "runtime.h" 491d54e73444e017d3a65234e0f193846f3e27472bIan Rogers#include "thread-inl.h" 506f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier#include "thread_list.h" 5108254278f290c2541cecd24ce6b7015427f4eae5Ian Rogers#include "verifier/method_verifier.h" 5269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 532dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersusing namespace art::mirror; 542dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 5569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapironamespace art { 561d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 571d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace collector { 5869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 5902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Performance options. 6002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kParallelMarkStack = true; 61bdd0fb9bf5e3af9d2f0366652979ac04b05d3d1eMathieu Chartierstatic const bool kDisableFinger = true; // TODO: Fix, bit rotten. 62858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartierstatic const bool kUseMarkStackPrefetch = true; 63858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 6402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Profiling and information flags. 6502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kCountClassesMarked = false; 6602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kProfileLargeObjects = false; 6702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kMeasureOverhead = false; 6802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierstatic const bool kCountTasks = false; 69d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartierstatic const bool kCountJavaLangRefs = false; 7002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 71357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierclass SetFingerVisitor { 72357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier public: 7393ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit SetFingerVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {} 74357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 75357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier void operator ()(void* finger) const { 76357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep_->SetFinger(reinterpret_cast<Object*>(finger)); 77357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 78357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 79357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier private: 80357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* const mark_sweep_; 81357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier}; 82357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 831d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::ImmuneSpace(space::ContinuousSpace* space) { 842b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Bind live to mark bitmap if necessary. 852b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (space->GetLiveBitmap() != space->GetMarkBitmap()) { 862b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier BindLiveToMarkBitmap(space); 872b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 882b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 892b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Add the space to the immune region. 902b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (immune_begin_ == NULL) { 912b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier DCHECK(immune_end_ == NULL); 922b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier SetImmuneRange(reinterpret_cast<Object*>(space->Begin()), 932b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier reinterpret_cast<Object*>(space->End())); 942b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } else { 951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 961d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const space::ContinuousSpace* prev_space = NULL; 971d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Find out if the previous space is immune. 981d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 991d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 1001d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 1011d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (*it == space) { 1021d54e73444e017d3a65234e0f193846f3e27472bIan Rogers break; 1032b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 1041d54e73444e017d3a65234e0f193846f3e27472bIan Rogers prev_space = *it; 1051d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1062b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1071d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // If previous space was immune, then extend the immune region. Relies on continuous spaces 1081d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // being sorted by Heap::AddContinuousSpace. 1091d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (prev_space != NULL && 1101d54e73444e017d3a65234e0f193846f3e27472bIan Rogers immune_begin_ <= reinterpret_cast<Object*>(prev_space->Begin()) && 1111d54e73444e017d3a65234e0f193846f3e27472bIan Rogers immune_end_ >= reinterpret_cast<Object*>(prev_space->End())) { 1122b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier immune_begin_ = std::min(reinterpret_cast<Object*>(space->Begin()), immune_begin_); 1132b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier immune_end_ = std::max(reinterpret_cast<Object*>(space->End()), immune_end_); 1142b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 1152b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 1162b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 1172b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1182b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::BindBitmaps() { 1191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 1202b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_); 1212b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1222b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Mark all of the spaces we never collect as immune. 1231d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 1241d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 1251d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 1261d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect) { 1272b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ImmuneSpace(space); 1282b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 1292b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 1302b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 1312b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1321d54e73444e017d3a65234e0f193846f3e27472bIan RogersMarkSweep::MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix) 1331d54e73444e017d3a65234e0f193846f3e27472bIan Rogers : GarbageCollector(heap, 1341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers name_prefix + (name_prefix.empty() ? "" : " ") + 1351d54e73444e017d3a65234e0f193846f3e27472bIan Rogers (is_concurrent ? "concurrent mark sweep": "mark sweep")), 1361d54e73444e017d3a65234e0f193846f3e27472bIan Rogers current_mark_bitmap_(NULL), 1371d54e73444e017d3a65234e0f193846f3e27472bIan Rogers java_lang_Class_(NULL), 1381d54e73444e017d3a65234e0f193846f3e27472bIan Rogers mark_stack_(NULL), 1391d54e73444e017d3a65234e0f193846f3e27472bIan Rogers finger_(NULL), 1401d54e73444e017d3a65234e0f193846f3e27472bIan Rogers immune_begin_(NULL), 1411d54e73444e017d3a65234e0f193846f3e27472bIan Rogers immune_end_(NULL), 1421d54e73444e017d3a65234e0f193846f3e27472bIan Rogers soft_reference_list_(NULL), 1431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers weak_reference_list_(NULL), 1441d54e73444e017d3a65234e0f193846f3e27472bIan Rogers finalizer_reference_list_(NULL), 1451d54e73444e017d3a65234e0f193846f3e27472bIan Rogers phantom_reference_list_(NULL), 1461d54e73444e017d3a65234e0f193846f3e27472bIan Rogers cleared_reference_list_(NULL), 14735883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier gc_barrier_(new Barrier(0)), 14862d6c772205b8859f0ebf7ad105402ec4c3e2e01Ian Rogers large_object_lock_("mark sweep large object lock", kMarkSweepLargeObjectLock), 14962d6c772205b8859f0ebf7ad105402ec4c3e2e01Ian Rogers mark_stack_expand_lock_("mark sweep mark stack expand lock"), 1501bd4b4ca7f4f44c55ded050e5a6be09811e1b283Ian Rogers is_concurrent_(is_concurrent), 1511d54e73444e017d3a65234e0f193846f3e27472bIan Rogers clear_soft_references_(false) { 1525301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier} 153b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 1542b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::InitializePhase() { 1551d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.Reset(); 1561d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.StartSplit("InitializePhase"); 1572b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier mark_stack_ = GetHeap()->mark_stack_.get(); 1582b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier DCHECK(mark_stack_ != NULL); 1592b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier finger_ = NULL; 1602b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier SetImmuneRange(NULL, NULL); 1612b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier soft_reference_list_ = NULL; 1622b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier weak_reference_list_ = NULL; 1632b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier finalizer_reference_list_ = NULL; 1642b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier phantom_reference_list_ = NULL; 1652b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier cleared_reference_list_ = NULL; 1662b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier freed_bytes_ = 0; 1672b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier freed_objects_ = 0; 1682b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier class_count_ = 0; 1692b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier array_count_ = 0; 1702b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier other_count_ = 0; 1712b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier large_object_test_ = 0; 1722b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier large_object_mark_ = 0; 1732b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier classes_marked_ = 0; 1742b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier overhead_time_ = 0; 1752b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier work_chunks_created_ = 0; 1762b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier work_chunks_deleted_ = 0; 1772b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier reference_count_ = 0; 17802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier java_lang_Class_ = Class::GetJavaLangClass(); 17902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK(java_lang_Class_ != NULL); 1807469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier FindDefaultMarkBitmap(); 1812b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Do any pre GC verification. 1822b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap_->PreGcVerification(this); 1832b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 1842b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1852b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::ProcessReferences(Thread* self) { 1861d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ProcessReferences"); 1878e56c7e41cb37e2eaf553503968a01ff893b135bMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 1882b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ProcessReferences(&soft_reference_list_, clear_soft_references_, &weak_reference_list_, 1892b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier &finalizer_reference_list_, &phantom_reference_list_); 1902b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 1912b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1922b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartierbool MarkSweep::HandleDirtyObjectsPhase() { 1932b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Thread* self = Thread::Current(); 1941d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::ObjectStack* allocation_stack = GetHeap()->allocation_stack_.get(); 1952b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::mutator_lock_->AssertExclusiveHeld(self); 1962b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1972b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier { 1981d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ReMarkRoots"); 1992b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2002b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2012b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Re-mark root set. 2022b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ReMarkRoots(); 2032b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2042b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Scan dirty objects, this is only required if we are not doing concurrent GC. 2051d54e73444e017d3a65234e0f193846f3e27472bIan Rogers RecursiveMarkDirtyObjects(accounting::CardTable::kCardDirty); 2062b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 2072b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2082b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ProcessReferences(self); 2092b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2102b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Only need to do this if we have the card mark verification on, and only during concurrent GC. 2112b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (GetHeap()->verify_missing_card_marks_) { 2122b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2132b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // This second sweep makes sure that we don't have any objects in the live stack which point to 2142b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // freed objects. These cause problems since their references may be previously freed objects. 2151d54e73444e017d3a65234e0f193846f3e27472bIan Rogers SweepArray(allocation_stack, false); 2162b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } else { 2171d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("UnMarkAllocStack"); 2182b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // The allocation stack contains things allocated since the start of the GC. These may have been 2201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // marked during this GC meaning they won't be eligible for reclaiming in the next sticky GC. 2211d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Remove these objects from the mark bitmaps so that they will be eligible for sticky 2221d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // collection. 2232b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap_->UnMarkAllocStack(GetHeap()->alloc_space_->GetMarkBitmap(), 2241d54e73444e017d3a65234e0f193846f3e27472bIan Rogers GetHeap()->large_object_space_->GetMarkObjects(), 2251d54e73444e017d3a65234e0f193846f3e27472bIan Rogers allocation_stack); 2262b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 2272b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier return true; 2282b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 2292b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2302b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartierbool MarkSweep::IsConcurrent() const { 2312b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier return is_concurrent_; 2322b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 2332b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2342b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::MarkingPhase() { 2352b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Heap* heap = GetHeap(); 2362b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Thread* self = Thread::Current(); 2372b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2381d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("BindBitmaps"); 2392b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier BindBitmaps(); 2402b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier FindDefaultMarkBitmap(); 2412b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Process dirty cards and add dirty cards to mod union tables. 2422b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap->ProcessCards(timings_); 2432b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2442b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Need to do this before the checkpoint since we don't want any threads to add references to 2452b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // the live stack during the recursive mark. 2461d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SwapStacks"); 2472b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap->SwapStacks(); 2482b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2492b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2502b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (Locks::mutator_lock_->IsExclusiveHeld(self)) { 2512b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // If we exclusively hold the mutator lock, all threads must be suspended. 2521d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("MarkRoots"); 2532b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier MarkRoots(); 2542b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } else { 2551d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("MarkRootsCheckpoint"); 2561d54e73444e017d3a65234e0f193846f3e27472bIan Rogers MarkRootsCheckpoint(self); 2571d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("MarkNonThreadRoots"); 2582b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier MarkNonThreadRoots(); 2592b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 2601d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("MarkConcurrentRoots"); 2612b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier MarkConcurrentRoots(); 2622b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2632b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap->UpdateAndMarkModUnion(this, timings_, GetGcType()); 2642b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier MarkReachableObjects(); 2652b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 2662b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2672b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::MarkReachableObjects() { 2682b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Mark everything allocated since the last as GC live so that we can sweep concurrently, 2692b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // knowing that new allocations won't be marked as live. 2701d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("MarkStackAsLive"); 2711d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::ObjectStack* live_stack = heap_->GetLiveStack(); 2722b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap_->MarkAllocStack(heap_->alloc_space_->GetLiveBitmap(), 2732b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap_->large_object_space_->GetLiveObjects(), 2742b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier live_stack); 2752b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier live_stack->Reset(); 2762b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Recursively mark all the non-image bits set in the mark bitmap. 2772b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier RecursiveMark(); 2782b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier DisableFinger(); 2792b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 2802b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2812b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::ReclaimPhase() { 2822b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Thread* self = Thread::Current(); 2832b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2842b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (!IsConcurrent()) { 2852b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ProcessReferences(self); 2862b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 2872b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2882b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Before freeing anything, lets verify the heap. 2892b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (kIsDebugBuild) { 2902b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 2912b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier VerifyImageRoots(); 2922b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 2932b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier heap_->PreSweepingGcVerification(this); 2942b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2952b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier { 2962b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2972b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 2982b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Reclaim unmarked objects. 2991d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Sweep(false); 3002b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 3012b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Swap the live and mark bitmaps for each space which we modified space. This is an 3022b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound 3032b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // bitmaps. 3041d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SwapBitmaps"); 3052b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier SwapBitmaps(); 3062b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 3072b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Unbind the live and mark bitmaps. 3082b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier UnBindBitmaps(); 3092b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 3102b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 3112b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 3122b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::SetImmuneRange(Object* begin, Object* end) { 3132b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier immune_begin_ = begin; 3142b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier immune_end_ = end; 3157469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 31658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 3177469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::FindDefaultMarkBitmap() { 3181d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 3191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 3201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 3211d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 3221d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 3231d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) { 3247469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier current_mark_bitmap_ = (*it)->GetMarkBitmap(); 3257469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier CHECK(current_mark_bitmap_ != NULL); 3267469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return; 327b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 328b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 3297469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->DumpSpaces(); 3307469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier LOG(FATAL) << "Could not find a default mark bitmap"; 33158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 33258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 333ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartiervoid MarkSweep::ExpandMarkStack() { 334ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Rare case, no need to have Thread::Current be a parameter. 335ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier MutexLock mu(Thread::Current(), mark_stack_expand_lock_); 336ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (UNLIKELY(mark_stack_->Size() < mark_stack_->Capacity())) { 337ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Someone else acquired the lock and expanded the mark stack before us. 338ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier return; 339ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 340ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier std::vector<Object*> temp; 341ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier temp.insert(temp.begin(), mark_stack_->Begin(), mark_stack_->End()); 342ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_stack_->Resize(mark_stack_->Capacity() * 2); 343ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier for (size_t i = 0; i < temp.size(); ++i) { 344ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_stack_->PushBack(temp[i]); 345ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 346ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 347ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 348ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartierinline void MarkSweep::MarkObjectNonNullParallel(const Object* obj, bool check_finger) { 349ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(obj != NULL); 350ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (MarkObjectParallel(obj)) { 351ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier if (kDisableFinger || (check_finger && obj < finger_)) { 352ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier while (UNLIKELY(!mark_stack_->AtomicPushBack(const_cast<Object*>(obj)))) { 353ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier // Only reason a push can fail is that the mark stack is full. 354ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier ExpandMarkStack(); 355ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 356ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 357ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier } 358ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 359ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 36002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierinline void MarkSweep::MarkObjectNonNull(const Object* obj, bool check_finger) { 36169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 362b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 363e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (obj >= immune_begin_ && obj < immune_end_) { 364e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier DCHECK(IsMarked(obj)); 365357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return; 366357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 367357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 368b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Try to take advantage of locality of references within a space, failing this find the space 369b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // the hard way. 3701d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 37102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 3721d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 3731d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (LIKELY(new_bitmap != NULL)) { 37402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap = new_bitmap; 375e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else { 37602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkLargeObject(obj); 377e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier return; 378357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 379b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 380b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 38169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // This object was not previously marked. 38202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (!object_bitmap->Test(obj)) { 38302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap->Set(obj); 38402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kDisableFinger || (check_finger && obj < finger_)) { 385d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Do we need to expand the mark stack? 386d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 387ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier ExpandMarkStack(); 388d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 38969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // The object must be pushed on to the mark stack. 390d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack_->PushBack(const_cast<Object*>(obj)); 39169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 39269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 39369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 39469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 39502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier// Rare case, probably not worth inlining since it will increase instruction cache miss rate. 39602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierbool MarkSweep::MarkLargeObject(const Object* obj) { 3971d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: support >1 discontinuous space. 3981d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 3991d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap* large_objects = large_object_space->GetMarkObjects(); 40002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 40102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++large_object_test_; 40202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 40302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!large_objects->Test(obj))) { 4048afe6e0d8c4151ac74afc4ebe0dab85550821243Ian Rogers // TODO: mark may be called holding the JNI global references lock, Contains will hold the 4058afe6e0d8c4151ac74afc4ebe0dab85550821243Ian Rogers // large object space lock causing a lock level violation. Bug: 9414652; 4068afe6e0d8c4151ac74afc4ebe0dab85550821243Ian Rogers if (!kDebugLocking && !large_object_space->Contains(obj)) { 40702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces"; 40802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(ERROR) << "Attempting see if it's a bad root"; 40902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier VerifyRoots(); 41002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier LOG(FATAL) << "Can't mark bad root"; 41102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 41202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 41302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++large_object_mark_; 41402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 41502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier large_objects->Set(obj); 41602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Don't need to check finger since large objects never have any object references. 41702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return true; 41802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 41902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return false; 42002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 42102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 42202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierinline bool MarkSweep::MarkObjectParallel(const Object* obj) { 42302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(obj != NULL); 42402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 42502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (obj >= immune_begin_ && obj < immune_end_) { 42602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(IsMarked(obj)); 42702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return false; 42802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 42902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 43002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Try to take advantage of locality of references within a space, failing this find the space 43102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // the hard way. 4321d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 43302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 4341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 43502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (new_bitmap != NULL) { 43602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier object_bitmap = new_bitmap; 43702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 43802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Remove the Thread::Current here? 43902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Convert this to some kind of atomic marking? 44002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(Thread::Current(), large_object_lock_); 44102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return MarkLargeObject(obj); 44202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 44302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 44402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 44502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Return true if the object was not previously marked. 44602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return !object_bitmap->AtomicTestAndSet(obj); 44702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 44802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 44969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Used to mark objects when recursing. Recursion is done by moving 45069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger across the bitmaps in address order and marking child 45169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// objects. Any newly-marked objects whose addresses are lower than 45269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger won't be visited by the bitmap scan, so those objects 45369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// need to be added to the mark stack. 454b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::MarkObject(const Object* obj) { 45569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj != NULL) { 45602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectNonNull(obj, true); 45769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 45869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 45969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 4602b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::MarkRoot(const Object* obj) { 4612b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (obj != NULL) { 4622b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier MarkObjectNonNull(obj, false); 4632b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 4642b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier} 4652b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 466ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartiervoid MarkSweep::MarkRootParallelCallback(const Object* root, void* arg) { 467ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(root != NULL); 468ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier DCHECK(arg != NULL); 469ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 470ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier mark_sweep->MarkObjectNonNullParallel(root, false); 471ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier} 472ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier 47302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid MarkSweep::MarkObjectCallback(const Object* root, void* arg) { 4741f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(root != NULL); 4751f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(arg != NULL); 4761f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 47702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep->MarkObjectNonNull(root, false); 4781f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom} 4791f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 480262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) { 481262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(root != NULL); 482262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(arg != NULL); 483262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 48402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep->MarkObjectNonNull(root, true); 485262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 486262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 4876f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartiervoid MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg, 48840e3bacfd57bca2ca39c1caec64680bd0ed4a16dIan Rogers const StackVisitor* visitor) { 48940e3bacfd57bca2ca39c1caec64680bd0ed4a16dIan Rogers reinterpret_cast<MarkSweep*>(arg)->VerifyRoot(root, vreg, visitor); 4906f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 4916f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 49240e3bacfd57bca2ca39c1caec64680bd0ed4a16dIan Rogersvoid MarkSweep::VerifyRoot(const Object* root, size_t vreg, const StackVisitor* visitor) { 4936f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier // See if the root is on any space bitmap. 4941d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (GetHeap()->GetLiveBitmap()->GetContinuousSpaceBitmap(root) == NULL) { 4951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 4964202b7484dab71ca4dfc2109ebb3fd04b87badfbMathieu Chartier if (!large_object_space->Contains(root)) { 4976f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier LOG(ERROR) << "Found invalid root: " << root; 49840e3bacfd57bca2ca39c1caec64680bd0ed4a16dIan Rogers if (visitor != NULL) { 49940e3bacfd57bca2ca39c1caec64680bd0ed4a16dIan Rogers LOG(ERROR) << visitor->DescribeLocation() << " in VReg: " << vreg; 5006f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 5016f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 5026f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier } 5036f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 5046f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 5056f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartiervoid MarkSweep::VerifyRoots() { 5066f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier Runtime::Current()->GetThreadList()->VerifyRoots(VerifyRootCallback, this); 5076f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier} 5086f1c94968ada57da433debf8e2d1b38a80ceb510Mathieu Chartier 50969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Marks all objects in the root set. 51069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkRoots() { 51102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Runtime::Current()->VisitNonConcurrentRoots(MarkObjectCallback, this); 5129ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier} 5139ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartier 514858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartiervoid MarkSweep::MarkNonThreadRoots() { 51502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Runtime::Current()->VisitNonThreadRoots(MarkObjectCallback, this); 516858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier} 517858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 5189ebae1f30b84dfd8dab4144f80eebec4f8fc8851Mathieu Chartiervoid MarkSweep::MarkConcurrentRoots() { 5191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Visit all runtime roots and clear dirty flags. 5201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Runtime::Current()->VisitConcurrentRoots(MarkObjectCallback, this, false, true); 52169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 52269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 523b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartierclass CheckObjectVisitor { 524b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier public: 52593ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit CheckObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {} 526b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 52700f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const 528d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier NO_THREAD_SAFETY_ANALYSIS { 5292b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (kDebugLocking) { 5302b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::heap_bitmap_lock_->AssertSharedHeld(Thread::Current()); 5312b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 532b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep_->CheckReference(obj, ref, offset, is_static); 533b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier } 534b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 535b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier private: 536b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* const mark_sweep_; 537b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier}; 538b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 539b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckObject(const Object* obj) { 540b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(obj != NULL); 541b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier CheckObjectVisitor visitor(this); 542b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier VisitObjectReferences(obj, visitor); 543b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 544b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 545b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) { 546b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(root != NULL); 547b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(arg != NULL); 548b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 549b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root)); 550b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep->CheckObject(root); 551b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 552b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 5531d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::BindLiveToMarkBitmap(space::ContinuousSpace* space) { 5541d54e73444e017d3a65234e0f193846f3e27472bIan Rogers CHECK(space->IsDlMallocSpace()); 5551d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::DlMallocSpace* alloc_space = space->AsDlMallocSpace(); 5561d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 5571d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* mark_bitmap = alloc_space->mark_bitmap_.release(); 5587469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->GetMarkBitmap()->ReplaceBitmap(mark_bitmap, live_bitmap); 5597469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->temp_bitmap_.reset(mark_bitmap); 5607469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->mark_bitmap_.reset(live_bitmap); 5617469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 5627469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 56302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass ScanObjectVisitor { 564cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 56593ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {} 566cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 5672b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // TODO: Fixme when anotatalysis works with visitors. 5682b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier void operator ()(const Object* obj) const NO_THREAD_SAFETY_ANALYSIS { 5692b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (kDebugLocking) { 5702b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 5712b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 5722b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 57302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->ScanObject(obj); 574cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 575cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 576cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 577cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* const mark_sweep_; 578cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 579cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 580d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartiervoid MarkSweep::ScanGrayObjects(byte minimum_age) { 5811d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::CardTable* card_table = GetHeap()->GetCardTable(); 5821d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 58302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisitor visitor(this); 584357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor finger_visitor(this); 5851d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 5861d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 5871d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), space_end = spaces.end(); it != space_end; ++it) { 5881d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 5891d54e73444e017d3a65234e0f193846f3e27472bIan Rogers switch (space->GetGcRetentionPolicy()) { 5901d54e73444e017d3a65234e0f193846f3e27472bIan Rogers case space::kGcRetentionPolicyNeverCollect: 5911d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ScanGrayImageSpaceObjects"); 5921d54e73444e017d3a65234e0f193846f3e27472bIan Rogers break; 5931d54e73444e017d3a65234e0f193846f3e27472bIan Rogers case space::kGcRetentionPolicyFullCollect: 5941d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ScanGrayZygoteSpaceObjects"); 5951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers break; 5961d54e73444e017d3a65234e0f193846f3e27472bIan Rogers case space::kGcRetentionPolicyAlwaysCollect: 5971d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ScanGrayAllocSpaceObjects"); 5981d54e73444e017d3a65234e0f193846f3e27472bIan Rogers break; 5991d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 600357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* begin = space->Begin(); 601357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* end = space->End(); 602b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Image spaces are handled properly since live == marked for them. 6031d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 6041d54e73444e017d3a65234e0f193846f3e27472bIan Rogers card_table->Scan(mark_bitmap, begin, end, visitor, finger_visitor, minimum_age); 605262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 606262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 607262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 608cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartierclass CheckBitmapVisitor { 609cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 61093ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit CheckBitmapVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {} 611cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 6121d54e73444e017d3a65234e0f193846f3e27472bIan Rogers void operator ()(const Object* obj) const NO_THREAD_SAFETY_ANALYSIS { 6132b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (kDebugLocking) { 6142b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::heap_bitmap_lock_->AssertSharedHeld(Thread::Current()); 6152b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 616cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier DCHECK(obj != NULL); 617cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier mark_sweep_->CheckObject(obj); 618cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 619cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 620cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 621cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* mark_sweep_; 622cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 623cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 624262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::VerifyImageRoots() { 625262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // Verify roots ensures that all the references inside the image space point 626262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // objects which are either in the image space or marked objects in the alloc 627262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // space 628cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier CheckBitmapVisitor visitor(this); 6291d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 6301d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 6311d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 6321d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 6332fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier if ((*it)->IsImageSpace()) { 6341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ImageSpace* space = (*it)->AsImageSpace(); 635cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 636cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 6371d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 638b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(live_bitmap != NULL); 639d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier live_bitmap->VisitMarkedRange(begin, end, visitor, VoidFunctor()); 640262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 641262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 642262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 643262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 64458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Populates the mark stack based on the set of marked objects and 64558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// recursively marks until the mark stack is emptied. 6462b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::RecursiveMark() { 6471d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("RecursiveMark"); 6481f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // RecursiveMark will build the lists of known instances of the Reference classes. 6491f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // See DelayReferenceReferent for details. 6501f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(soft_reference_list_ == NULL); 6511f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(weak_reference_list_ == NULL); 6521f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(finalizer_reference_list_ == NULL); 6531f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(phantom_reference_list_ == NULL); 6541f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(cleared_reference_list_ == NULL); 6551f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 6562b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier const bool partial = GetGcType() == kGcTypePartial; 657357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor set_finger_visitor(this); 658357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObjectVisitor scan_visitor(this); 6592b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (!kDisableFinger) { 6602b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier finger_ = NULL; 6611d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 6621d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 6631d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 6641d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 6651d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 6661d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if ((space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) || 6671d54e73444e017d3a65234e0f193846f3e27472bIan Rogers (!partial && space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect)) { 6682b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier current_mark_bitmap_ = space->GetMarkBitmap(); 6692b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (current_mark_bitmap_ == NULL) { 6702b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier GetHeap()->DumpSpaces(); 6712b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier LOG(FATAL) << "invalid bitmap"; 6722b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 6732b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // This function does not handle heap end increasing, so we must use the space end. 6742b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 6752b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 6762b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor, set_finger_visitor); 677357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 678357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 679357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 6802b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier DisableFinger(); 6811d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ProcessMarkStack"); 682357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ProcessMarkStack(); 68358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 68458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 685357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierbool MarkSweep::IsMarkedCallback(const Object* object, void* arg) { 686357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return 687357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier reinterpret_cast<MarkSweep*>(arg)->IsMarked(object) || 688357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object); 689357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 690357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 691d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartiervoid MarkSweep::RecursiveMarkDirtyObjects(byte minimum_age) { 692d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier ScanGrayObjects(minimum_age); 6931d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ProcessMarkStack"); 694262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier ProcessMarkStack(); 695262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 696262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 69758551df3c2646ed507feec9e9eb3768085a76059Carl Shapirovoid MarkSweep::ReMarkRoots() { 6981d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Runtime::Current()->VisitRoots(ReMarkObjectVisitor, this, true, true); 69958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 70058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 7012dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogersvoid MarkSweep::SweepJniWeakGlobals(IsMarkedTester is_marked, void* arg) { 702410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes JavaVMExt* vm = Runtime::Current()->GetJavaVM(); 70350b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 704410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes IndirectReferenceTable* table = &vm->weak_globals; 705654d3a217faf46310895a1825354d610c2f3d6c2Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 706410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes for (It it = table->begin(), end = table->end(); it != end; ++it) { 707410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes const Object** entry = *it; 7087469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (!is_marked(*entry, arg)) { 709410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes *entry = kClearedJniWeakGlobal; 710410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 711410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 712410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes} 713410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes 7147469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierstruct ArrayMarkedCheck { 7151d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::ObjectStack* live_stack; 7167469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier MarkSweep* mark_sweep; 7177469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier}; 7187469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 7197469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier// Either marked or not live. 7207469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierbool MarkSweep::IsMarkedArrayCallback(const Object* object, void* arg) { 7217469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ArrayMarkedCheck* array_check = reinterpret_cast<ArrayMarkedCheck*>(arg); 7227469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (array_check->mark_sweep->IsMarked(object)) { 7237469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return true; 7247469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 7251d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::ObjectStack* live_stack = array_check->live_stack; 7267469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return std::find(live_stack->Begin(), live_stack->End(), object) == live_stack->End(); 7277469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 7287469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 7291d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::SweepSystemWeaksArray(accounting::ObjectStack* allocations) { 73046a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier Runtime* runtime = Runtime::Current(); 731357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // The callbacks check 732357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !is_marked where is_marked is the callback but we want 733357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !IsMarked && IsLive 734357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive). 735357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Or for swapped (IsLive || !IsMarked). 7367469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 7377469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier ArrayMarkedCheck visitor; 7387469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier visitor.live_stack = allocations; 7397469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier visitor.mark_sweep = this; 7407469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(IsMarkedArrayCallback, &visitor); 7417469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetMonitorList()->SweepMonitorList(IsMarkedArrayCallback, &visitor); 7427469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepJniWeakGlobals(IsMarkedArrayCallback, &visitor); 7437469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 7447469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 7457469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::SweepSystemWeaks() { 7467469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier Runtime* runtime = Runtime::Current(); 7477469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // The callbacks check 7487469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // !is_marked where is_marked is the callback but we want 7497469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // !IsMarked && IsLive 7507469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive). 7517469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // Or for swapped (IsLive || !IsMarked). 7527469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(IsMarkedCallback, this); 7537469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier runtime->GetMonitorList()->SweepMonitorList(IsMarkedCallback, this); 7547469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepJniWeakGlobals(IsMarkedCallback, this); 75569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 75669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 757c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartierbool MarkSweep::VerifyIsLiveCallback(const Object* obj, void* arg) { 758c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 759c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // We don't actually want to sweep the object, so lets return "marked" 760c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier return true; 761c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 762c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 763c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifyIsLive(const Object* obj) { 764c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Heap* heap = GetHeap(); 765c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier if (!heap->GetLiveBitmap()->Test(obj)) { 7661d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 7677469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (!large_object_space->GetLiveObjects()->Test(obj)) { 7687469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 7697469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier heap->allocation_stack_->End()) { 7707469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // Object not found! 7717469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier heap->DumpSpaces(); 7727469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier LOG(FATAL) << "Found dead object " << obj; 7737469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 774c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 775c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 776c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 777c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 778c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifySystemWeaks() { 779c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Runtime* runtime = Runtime::Current(); 780c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // Verify system weaks, uses a special IsMarked callback which always returns true. 781c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(VerifyIsLiveCallback, this); 782c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetMonitorList()->SweepMonitorList(VerifyIsLiveCallback, this); 783c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 784c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier JavaVMExt* vm = runtime->GetJavaVM(); 78550b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 786c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier IndirectReferenceTable* table = &vm->weak_globals; 787c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 788c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier for (It it = table->begin(), end = table->end(); it != end; ++it) { 789c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier const Object** entry = *it; 790c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier VerifyIsLive(*entry); 791c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 792c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 793c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 794b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughesstruct SweepCallbackContext { 795357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep; 7961d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::AllocSpace* space; 79750b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self; 798b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes}; 799b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 8000e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartierclass CheckpointMarkThreadRoots : public Closure { 801858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier public: 80293ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit CheckpointMarkThreadRoots(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {} 803858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 804858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS { 805858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier // Note: self is not necessarily equal to thread since thread may be suspended. 806858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier Thread* self = Thread::Current(); 807d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 808d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier << thread->GetState() << " thread " << thread << " self " << self; 809ac86a7cad60c20a131011338057887bb64cbfd38Mathieu Chartier thread->VisitRoots(MarkSweep::MarkRootParallelCallback, mark_sweep_); 810858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier mark_sweep_->GetBarrier().Pass(self); 811858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier } 812858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 813858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier private: 814858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier MarkSweep* mark_sweep_; 815858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier}; 816858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 8171d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::MarkRootsCheckpoint(Thread* self) { 818d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier CheckpointMarkThreadRoots check_point(this); 819858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier ThreadList* thread_list = Runtime::Current()->GetThreadList(); 8201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Request the check point is run on all threads returning a count of the threads that must 8211d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // run through the barrier including self. 8221d54e73444e017d3a65234e0f193846f3e27472bIan Rogers size_t barrier_count = thread_list->RunCheckpoint(&check_point); 8231d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Release locks then wait for all mutator threads to pass the barrier. 8241d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: optimize to not release locks when there are no threads to wait for. 8251d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Locks::heap_bitmap_lock_->ExclusiveUnlock(self); 8261d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Locks::mutator_lock_->SharedUnlock(self); 8271d54e73444e017d3a65234e0f193846f3e27472bIan Rogers ThreadState old_state = self->SetState(kWaitingForCheckPointsToRun); 8281d54e73444e017d3a65234e0f193846f3e27472bIan Rogers CHECK_EQ(old_state, kWaitingPerformingGc); 8291d54e73444e017d3a65234e0f193846f3e27472bIan Rogers gc_barrier_->Increment(self, barrier_count); 8301d54e73444e017d3a65234e0f193846f3e27472bIan Rogers self->SetState(kWaitingPerformingGc); 8311d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Locks::mutator_lock_->SharedLock(self); 8321d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Locks::heap_bitmap_lock_->ExclusiveLock(self); 833858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier} 834858f1c5fd5e528d0b16040ced74d4636046a42d8Mathieu Chartier 83530fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogersvoid MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 836b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 837357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep = context->mark_sweep; 838357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = mark_sweep->GetHeap(); 8391d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::AllocSpace* space = context->space; 84050b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = context->self; 84150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(self); 8425d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Use a bulk free, that merges consecutive objects before freeing or free per object? 8435d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Documentation suggests better free performance with merging, but this may be at the expensive 8445d76c435082332ef79a22962386fa92a0870e378Ian Rogers // of allocation. 84502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t freed_objects = num_ptrs; 84602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit 84702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t freed_bytes = space->FreeList(self, num_ptrs, ptrs); 84800f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers heap->RecordFree(freed_objects, freed_bytes); 849357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_objects_ += freed_objects; 850357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_bytes_ += freed_bytes; 85158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 85258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 853cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 854cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 85550b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(context->self); 856357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = context->mark_sweep->GetHeap(); 857cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // We don't free any actual memory to avoid dirtying the shared zygote pages. 858cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (size_t i = 0; i < num_ptrs; ++i) { 859cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier Object* obj = static_cast<Object*>(ptrs[i]); 860cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetLiveBitmap()->Clear(obj); 861cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetCardTable()->MarkCard(obj); 862cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 863cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 864cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 8651d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::SweepArray(accounting::ObjectStack* allocations, bool swap_bitmaps) { 866357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_bytes = 0; 8671d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::DlMallocSpace* space = heap_->GetAllocSpace(); 868357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 869357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 870357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 8711d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SweepSystemWeaks"); 8727469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepSystemWeaksArray(allocations); 873357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 8741d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("Process allocation stack"); 875357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Newly allocated objects MUST be in the alloc space and those are the only objects which we are 876357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // going to free. 8771d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 8781d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 8791d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 8801d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 8811d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 882357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (swap_bitmaps) { 883357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::swap(live_bitmap, mark_bitmap); 884e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 885357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 886357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 887e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_large_objects = 0; 888357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t count = allocations->Size(); 889d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier Object** objects = const_cast<Object**>(allocations->Begin()); 890357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object** out = objects; 891357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 892357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Empty the allocation stack. 89350b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 894357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (size_t i = 0;i < count;++i) { 895357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object* obj = objects[i]; 896e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // There should only be objects in the AllocSpace/LargeObjectSpace in the allocation stack. 897e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (LIKELY(mark_bitmap->HasAddress(obj))) { 898e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!mark_bitmap->Test(obj)) { 899e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Don't bother un-marking since we clear the mark bitmap anyways. 900e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier *(out++) = obj; 901e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 902e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else if (!large_mark_objects->Test(obj)) { 903e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_large_objects; 9041c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += large_object_space->Free(self, obj); 905357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 906357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 9071d54e73444e017d3a65234e0f193846f3e27472bIan Rogers CHECK_EQ(count, allocations->Size()); 9081d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("FreeList"); 909357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 910357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_objects = out - objects; 9111c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += space->FreeList(self, freed_objects, objects); 91240e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier VLOG(heap) << "Freed " << freed_objects << "/" << count 913e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier << " objects with size " << PrettySize(freed_bytes); 914e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes); 91540e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_objects_ += freed_objects; 91640e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_bytes_ += freed_bytes; 9171d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 9181d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("ResetStack"); 919357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier allocations->Reset(); 920357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 921357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 9221d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid MarkSweep::Sweep(bool swap_bitmaps) { 923b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 924b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 925357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 926357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 9271d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SweepSystemWeaks"); 9287469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SweepSystemWeaks(); 929357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 9301d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const bool partial = (GetGcType() == kGcTypePartial); 931b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext scc; 932357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier scc.mark_sweep = this; 93350b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers scc.self = Thread::Current(); 9341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 9351d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 9361d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 9371d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 9381d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 9391d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // We always sweep always collect spaces. 9401d54e73444e017d3a65234e0f193846f3e27472bIan Rogers bool sweep_space = (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect); 9411d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (!partial && !sweep_space) { 9421d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // We sweep full collect spaces when the GC isn't a partial GC (ie its full). 9431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers sweep_space = (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect); 9441d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 9451d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (sweep_space) { 946cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 947cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 9481d54e73444e017d3a65234e0f193846f3e27472bIan Rogers scc.space = space->AsDlMallocSpace(); 9491d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 9501d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 951fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier if (swap_bitmaps) { 952fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier std::swap(live_bitmap, mark_bitmap); 953fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier } 9541d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (!space->IsZygoteSpace()) { 9551d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SweepAllocSpace"); 956cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked. 9571d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 9581d54e73444e017d3a65234e0f193846f3e27472bIan Rogers &SweepCallback, reinterpret_cast<void*>(&scc)); 959cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } else { 9601d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SweepZygote"); 9611d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual 9621d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // memory. 9631d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 9641d54e73444e017d3a65234e0f193846f3e27472bIan Rogers &ZygoteSweepCallback, reinterpret_cast<void*>(&scc)); 965cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 96658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 96758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 9682b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 9691d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("SweepLargeObjects"); 9702b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier SweepLargeObjects(swap_bitmaps); 97158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 97258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 973e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 974e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Sweep large objects 9751d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 9761d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 9771d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 978e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (swap_bitmaps) { 979e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 980e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 9811d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceSetMap::Objects& live_objects = large_live_objects->GetObjects(); 982e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // O(n*log(n)) but hopefully there are not too many large objects. 983e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_objects = 0; 9842fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier size_t freed_bytes = 0; 98550b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 9861d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 9871d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef accounting::SpaceSetMap::Objects::iterator It; 9881d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = live_objects.begin(), end = live_objects.end(); it != end; ++it) { 989e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!large_mark_objects->Test(*it)) { 9901c23e1edb7361bbaec6e57fca86d8d3797960ad2Mathieu Chartier freed_bytes += large_object_space->Free(self, const_cast<Object*>(*it)); 991e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_objects; 992e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 993e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 994e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier freed_objects_ += freed_objects; 9952fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier freed_bytes_ += freed_bytes; 9962fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier GetHeap()->RecordFree(freed_objects, freed_bytes); 997e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 998e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 999b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) { 10001d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 10011d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 10021d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 10031d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 10041d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 10051d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (space->IsDlMallocSpace() && space->Contains(ref)) { 1006b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(IsMarked(obj)); 1007b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 1008b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool is_marked = IsMarked(ref); 1009b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!is_marked) { 10101d54e73444e017d3a65234e0f193846f3e27472bIan Rogers LOG(INFO) << *space; 1011b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref) 1012b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj) 1013b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(obj) << ") at offset " 1014b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked"; 1015b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 1016b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Class* klass = is_static ? obj->AsClass() : obj->GetClass(); 1017b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(klass != NULL); 1018b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields(); 1019b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(fields != NULL); 1020b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool found = false; 1021b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); ++i) { 1022b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Field* cur = fields->Get(i); 1023b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (cur->GetOffset().Int32Value() == offset.Int32Value()) { 1024b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur); 1025b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier found = true; 1026b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 1027b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 1028b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 1029b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!found) { 1030b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value(); 1031262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 1032262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 1033b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool obj_marked = heap_->GetCardTable()->IsDirty(obj); 1034b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!obj_marked) { 1035b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' " 1036b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "(" << reinterpret_cast<const void*>(obj) << ") contains references to " 1037b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "the alloc space, but wasn't card marked"; 1038b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 10395d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 10405d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 1041b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 10425d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 10435d76c435082332ef79a22962386fa92a0870e378Ian Rogers} 10445d76c435082332ef79a22962386fa92a0870e378Ian Rogers 104569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Process the "referent" field in a java.lang.ref.Reference. If the 104669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent has not yet been marked, put it on the appropriate list in 104769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the gcHeap for later processing. 104869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::DelayReferenceReferent(Object* obj) { 104969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 10501f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom Class* klass = obj->GetClass(); 10511f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(klass != NULL); 10520cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers DCHECK(klass->IsReferenceClass()); 1053b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false); 1054b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(obj); 1055d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountJavaLangRefs) { 1056d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier ++reference_count_; 1057d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier } 105869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (pending == NULL && referent != NULL && !IsMarked(referent)) { 10594873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom Object** list = NULL; 10600cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers if (klass->IsSoftReferenceClass()) { 106169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &soft_reference_list_; 10620cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsWeakReferenceClass()) { 106369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &weak_reference_list_; 10640cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsFinalizerReferenceClass()) { 106569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &finalizer_reference_list_; 10660cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsPhantomReferenceClass()) { 106769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &phantom_reference_list_; 106869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 10690796af03edc06d92bb8d631f1c0c23befdae2315Brian Carlstrom DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags(); 107002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: One lock per list? 1071b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(obj, list); 107269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 107369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 107469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1075357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::ScanRoot(const Object* obj) { 1076357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObject(obj); 1077357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 1078357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 107902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass MarkObjectVisitor { 108002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier public: 108193ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit MarkObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {} 108202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 10832b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // TODO: Fixme when anotatalysis works with visitors. 108402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void operator ()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, 10852b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier bool /* is_static */) const 10862b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier NO_THREAD_SAFETY_ANALYSIS { 10872b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier if (kDebugLocking) { 10882b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 10892b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 10902b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier } 109102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->MarkObject(ref); 109202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 109302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 109402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier private: 109502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkSweep* const mark_sweep_; 109602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier}; 109702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 109869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans an object reference. Determines the type of the reference 109969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// and dispatches to a specialized scanning routine. 1100cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ScanObject(const Object* obj) { 110102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkObjectVisitor visitor(this); 110202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObjectVisit(obj, visitor); 110302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 110402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 110502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartierclass MarkStackChunk : public Task { 11061d54e73444e017d3a65234e0f193846f3e27472bIan Rogers public: 110702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk(ThreadPool* thread_pool, MarkSweep* mark_sweep, Object** begin, Object** end) 110802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier : mark_sweep_(mark_sweep), 110902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool_(thread_pool), 111002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier index_(0), 111102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier length_(0), 111202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_(NULL) { 111302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier length_ = end - begin; 111402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (begin != end) { 111502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Cost not significant since we only do this for the initial set of mark stack chunks. 111602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier memcpy(data_, begin, length_ * sizeof(*begin)); 111702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 111802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 111902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++mark_sweep_->work_chunks_created_; 112002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 112102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 112202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 112302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ~MarkStackChunk() { 112402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(output_ == NULL || output_->length_ == 0); 112502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK_GE(index_, length_); 112602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier delete output_; 112702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 112802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++mark_sweep_->work_chunks_deleted_; 112902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 113002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 113102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 113202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkSweep* const mark_sweep_; 113302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* const thread_pool_; 113402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier static const size_t max_size = 1 * KB; 113502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Index of which object we are scanning. Only needs to be atomic if we are doing work stealing. 113602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t index_; 113702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Input / output mark stack. We add newly marked references to data_ until length reaches 113802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // max_size. This is an optimization so that less tasks are created. 113902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Investigate using a bounded buffer FIFO. 114002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object* data_[max_size]; 114102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // How many elements in data_ we need to scan. 114202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t length_; 114302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Output block, newly marked references get added to the ouput block so that another thread can 114402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // scan them. 114502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk* output_; 114602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 114702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier class MarkObjectParallelVisitor { 114802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier public: 114993ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit MarkObjectParallelVisitor(MarkStackChunk* chunk_task) : chunk_task_(chunk_task) {} 115002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 115102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void operator ()(const Object* /* obj */, const Object* ref, 115202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const MemberOffset& /* offset */, bool /* is_static */) const { 115302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (ref != NULL && chunk_task_->mark_sweep_->MarkObjectParallel(ref)) { 115402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier chunk_task_->MarkStackPush(ref); 115502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 115602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 115702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 115802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier private: 115902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MarkStackChunk* const chunk_task_; 116002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier }; 116102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 116202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Push an object into the block. 116302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Don't need to use atomic ++ since we only one thread is writing to an output block at any 116402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // given time. 116502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void Push(Object* obj) { 11661d54e73444e017d3a65234e0f193846f3e27472bIan Rogers CHECK(obj != NULL); 116702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier data_[length_++] = obj; 116869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 116902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 117002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void MarkStackPush(const Object* obj) { 117102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (static_cast<size_t>(length_) < max_size) { 117202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Push(const_cast<Object*>(obj)); 117302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 11741d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // Internal (thread-local) buffer is full, push to a new buffer instead. 117502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (UNLIKELY(output_ == NULL)) { 117602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier AllocateOutputChunk(); 117702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else if (UNLIKELY(static_cast<size_t>(output_->length_) == max_size)) { 117802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Output block is full, queue it up for processing and obtain a new block. 117902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier EnqueueOutput(); 118002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier AllocateOutputChunk(); 118102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 118202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_->Push(const_cast<Object*>(obj)); 118302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 118402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 118502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 118602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void ScanObject(Object* obj) { 118702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->ScanObjectVisit(obj, MarkObjectParallelVisitor(this)); 118802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 118902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 119002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void EnqueueOutput() { 119102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (output_ != NULL) { 119202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier uint64_t start = 0; 119302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 119402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start = NanoTime(); 119502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 119602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool_->AddTask(Thread::Current(), output_); 119702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_ = NULL; 119802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 119902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->overhead_time_ += NanoTime() - start; 120002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 120102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 120202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 120302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 120402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void AllocateOutputChunk() { 120502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier uint64_t start = 0; 120602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 120702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start = NanoTime(); 120802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 120902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier output_ = new MarkStackChunk(thread_pool_, mark_sweep_, NULL, NULL); 121002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 121102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_sweep_->overhead_time_ += NanoTime() - start; 121202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 121302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 121402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 121502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier void Finalize() { 121602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier EnqueueOutput(); 121702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier delete this; 121802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 121902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 122002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Scans all of the objects 122102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier virtual void Run(Thread* self) { 1222d74e41b1cce5373aa24fd2fbea735173f6113d5aBrian Carlstrom size_t index; 122302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while ((index = index_++) < length_) { 122402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kUseMarkStackPrefetch) { 1225d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier static const size_t prefetch_look_ahead = 1; 1226d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier __builtin_prefetch(data_[std::min(index + prefetch_look_ahead, length_ - 1)]); 122702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 122802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object* obj = data_[index]; 122902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier DCHECK(obj != NULL); 123002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ScanObject(obj); 123102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 123202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 123302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier}; 123402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 123502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid MarkSweep::ProcessMarkStackParallel() { 123602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK(kDisableFinger) << "parallel mark stack processing cannot work when finger is enabled"; 123702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Thread* self = Thread::Current(); 123802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 123902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Split the current mark stack up into work tasks. 124002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t num_threads = thread_pool->GetThreadCount(); 124102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t stack_size = mark_stack_->Size(); 124202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t chunk_size = 124302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier std::min((stack_size + num_threads - 1) / num_threads, 124402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier static_cast<size_t>(MarkStackChunk::max_size)); 124502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t index = 0; 124602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier for (size_t i = 0; i < num_threads || index < stack_size; ++i) { 124702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object** begin = &mark_stack_->Begin()[std::min(stack_size, index)]; 124802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Object** end = &mark_stack_->Begin()[std::min(stack_size, index + chunk_size)]; 124902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier index += chunk_size; 125002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool->AddTask(self, new MarkStackChunk(thread_pool, this, begin, end)); 125102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 125202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier thread_pool->StartWorkers(self); 12531d54e73444e017d3a65234e0f193846f3e27472bIan Rogers thread_pool->Wait(self, true, true); 125402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier mark_stack_->Reset(); 125502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier //LOG(INFO) << "Idle wait time " << PrettyDuration(thread_pool->GetWaitTime()); 125602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked"; 125769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 125869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 12595d76c435082332ef79a22962386fa92a0870e378Ian Rogers// Scan anything that's on the mark stack. 126069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessMarkStack() { 126102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 126202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kParallelMarkStack && thread_pool != NULL && thread_pool->GetThreadCount() > 0) { 126302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ProcessMarkStackParallel(); 126402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return; 126502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 126602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1267d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (kUseMarkStackPrefetch) { 1268d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_size = 4; 1269d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_mask = fifo_size - 1; 1270d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* fifo[fifo_size]; 1271d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (size_t i = 0;i < fifo_size;++i) { 1272d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[i] = NULL; 1273357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 1274d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_pos = 0; 1275d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_count = 0; 1276d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (;;) { 1277d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = fifo[fifo_pos & fifo_mask]; 1278d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (obj != NULL) { 1279d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 1280d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = NULL; 1281d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier --fifo_count; 1282d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1283357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1284d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!mark_stack_->IsEmpty()) { 1285d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 1286d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 1287d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = obj; 1288d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier __builtin_prefetch(obj); 1289d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_count++; 1290d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1291d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_pos++; 1292357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 1293d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!fifo_count) { 1294d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier CHECK(mark_stack_->IsEmpty()) << mark_stack_->Size(); 1295d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier break; 1296d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1297d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 1298d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } else { 1299d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier while (!mark_stack_->IsEmpty()) { 1300d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 1301d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 1302d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 1303357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 1304357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 130569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 130669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 130769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Walks the reference list marking any references subject to the 130869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// reference clearing policy. References with a black referent are 130969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// removed from the list. References with white referents biased 131069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// toward saving are blackened and also removed from the list. 131169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::PreserveSomeSoftReferences(Object** list) { 131269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 131369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* clear = NULL; 131469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t counter = 0; 1315b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 1316b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 1317b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 131869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1319b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1320b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 132169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent == NULL) { 132269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent was cleared by the user during marking. 132369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro continue; 132469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 132569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool is_marked = IsMarked(referent); 132669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked && ((++counter) & 1)) { 132769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white and biased toward saving, mark it. 132869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 132969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro is_marked = true; 133069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 133169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked) { 133269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, queue it for clearing. 1333b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(ref, &clear); 133469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 133569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 133669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = clear; 133769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Restart the mark with the newly black references added to the 133869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // root set. 133969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 134069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 134169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 13427469ebf3888b8037421cb6834f37f946646265ecMathieu Chartierinline bool MarkSweep::IsMarked(const Object* object) const 13437469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 13447469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (object >= immune_begin_ && object < immune_end_) { 13457469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return true; 13467469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 13477469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier DCHECK(current_mark_bitmap_ != NULL); 13487469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (current_mark_bitmap_->HasAddress(object)) { 13497469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return current_mark_bitmap_->Test(object); 13507469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 13517469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier return heap_->GetMarkBitmap()->Test(object); 13527469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 13537469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 13547469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 135569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Unlink the reference list clearing references objects with white 135669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents. Cleared references registered to a reference queue are 135769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scheduled for appending by the heap worker thread. 135869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ClearWhiteReferences(Object** list) { 135969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 136069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1361b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1362b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 136369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 136469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, clear it. 1365b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 1366b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes if (heap_->IsEnqueuable(ref)) { 1367b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 136869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 136969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 137069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 137169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 137269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 137369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 137469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Enqueues finalizer references with white referents. White 137569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents are blackened, moved to the zombie field, and the 137669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent field is cleared. 137769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueFinalizerReferences(Object** list) { 137869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 1379b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes MemberOffset zombie_offset = heap_->GetFinalizerReferenceZombieOffset(); 138069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool has_enqueued = false; 138169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 1382b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 1383b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 138469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 138569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 138669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // If the referent is non-null the reference must queuable. 1387b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes DCHECK(heap_->IsEnqueuable(ref)); 13880cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers ref->SetFieldObject(zombie_offset, referent, false); 1389b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 1390b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 139169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro has_enqueued = true; 139269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 139369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 139469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (has_enqueued) { 139569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 139669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 139769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 139869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 139969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 140058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Process reference class instances and schedule finalizations. 140169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft, 140269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** weak_references, 140369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** finalizer_references, 140469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** phantom_references) { 140569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(soft_references != NULL); 140669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(weak_references != NULL); 140769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(finalizer_references != NULL); 140869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(phantom_references != NULL); 140969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 141069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Unless we are in the zygote or required to clear soft references 141169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // with white references, preserve some white referents. 14122945e2455ba87e15b65f4a6a737bcdc8c0f2f31bIan Rogers if (!clear_soft && !Runtime::Current()->IsZygote()) { 141369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro PreserveSomeSoftReferences(soft_references); 141469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 141569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 141669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all remaining soft and weak references with white 141769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 141869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 141969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 142069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 142169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Preserve all white objects with finalize methods and schedule 142269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // them for finalization. 142369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueFinalizerReferences(finalizer_references); 142469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 142569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all f-reachable soft and weak references with white 142669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 142769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 142869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 142969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 143069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all phantom references with white referents. 143169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(phantom_references); 143269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 143369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // At this point all reference lists should be empty. 143469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*soft_references == NULL); 143569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*weak_references == NULL); 143669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*finalizer_references == NULL); 143769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*phantom_references == NULL); 143869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 143969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 14407469ebf3888b8037421cb6834f37f946646265ecMathieu Chartiervoid MarkSweep::UnBindBitmaps() { 14411d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 14421d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 14431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 14441d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 14451d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 14461d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (space->IsDlMallocSpace()) { 14471d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::DlMallocSpace* alloc_space = space->AsDlMallocSpace(); 14487469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier if (alloc_space->temp_bitmap_.get() != NULL) { 14497469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier // At this point, the temp_bitmap holds our old mark bitmap. 14501d54e73444e017d3a65234e0f193846f3e27472bIan Rogers accounting::SpaceBitmap* new_bitmap = alloc_space->temp_bitmap_.release(); 14517469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier GetHeap()->GetMarkBitmap()->ReplaceBitmap(alloc_space->mark_bitmap_.get(), new_bitmap); 14527469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier CHECK_EQ(alloc_space->mark_bitmap_.release(), alloc_space->live_bitmap_.get()); 14537469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier alloc_space->mark_bitmap_.reset(new_bitmap); 14547469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier DCHECK(alloc_space->temp_bitmap_.get() == NULL); 14557469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 14567469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 14577469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier } 14587469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier} 14597469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier 14602b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartiervoid MarkSweep::FinishPhase() { 14612b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Can't enqueue referneces if we hold the mutator lock. 14622b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier Object* cleared_references = GetClearedReferences(); 14631d54e73444e017d3a65234e0f193846f3e27472bIan Rogers Heap* heap = GetHeap(); 14641d54e73444e017d3a65234e0f193846f3e27472bIan Rogers heap->EnqueueClearedReferences(&cleared_references); 14652b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 14661d54e73444e017d3a65234e0f193846f3e27472bIan Rogers heap->PostGcVerification(this); 14672b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 14681d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("GrowForUtilization"); 1469bdd0fb9bf5e3af9d2f0366652979ac04b05d3d1eMathieu Chartier heap->GrowForUtilization(GetGcType(), GetDurationNs()); 147065db880c73718f89278dac8975d58d3a49ff1fdbMathieu Chartier 14711d54e73444e017d3a65234e0f193846f3e27472bIan Rogers timings_.NewSplit("RequestHeapTrim"); 14721d54e73444e017d3a65234e0f193846f3e27472bIan Rogers heap->RequestHeapTrim(); 147365db880c73718f89278dac8975d58d3a49ff1fdbMathieu Chartier 14742b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Update the cumulative statistics 14751d54e73444e017d3a65234e0f193846f3e27472bIan Rogers total_time_ns_ += GetDurationNs(); 14761d54e73444e017d3a65234e0f193846f3e27472bIan Rogers total_paused_time_ns_ += std::accumulate(GetPauseTimes().begin(), GetPauseTimes().end(), 0, 14771d54e73444e017d3a65234e0f193846f3e27472bIan Rogers std::plus<uint64_t>()); 14782b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier total_freed_objects_ += GetFreedObjects(); 14792b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier total_freed_bytes_ += GetFreedBytes(); 14802b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 14812b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Ensure that the mark stack is empty. 14822b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier CHECK(mark_stack_->IsEmpty()); 14832b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier 1484d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountScannedTypes) { 1485d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ 1486d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier << " other=" << other_count_; 148702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 148802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 148902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountTasks) { 1490d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_; 149102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 149202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 149302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kMeasureOverhead) { 1494d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_); 149502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 149602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 149702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kProfileLargeObjects) { 1498d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_; 149902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 150002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 150102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (kCountClassesMarked) { 1502d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "Classes marked " << classes_marked_; 1503d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier } 1504d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier 1505d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier if (kCountJavaLangRefs) { 1506d22d54849c96760aa1efa259d6dcfbace54da2afMathieu Chartier VLOG(gc) << "References scanned " << reference_count_; 150702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 150802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 15092b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier // Update the cumulative loggers. 15102b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier cumulative_timings_.Start(); 15111d54e73444e017d3a65234e0f193846f3e27472bIan Rogers cumulative_timings_.AddNewLogger(timings_); 15122b82db45c09450022199376c3a5420eacf2aa81eMathieu Chartier cumulative_timings_.End(); 1513357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 151402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Clear all of the spaces' mark bitmaps. 15151d54e73444e017d3a65234e0f193846f3e27472bIan Rogers const std::vector<space::ContinuousSpace*>& spaces = GetHeap()->GetContinuousSpaces(); 15161d54e73444e017d3a65234e0f193846f3e27472bIan Rogers // TODO: C++0x 15171d54e73444e017d3a65234e0f193846f3e27472bIan Rogers typedef std::vector<space::ContinuousSpace*>::const_iterator It; 15181d54e73444e017d3a65234e0f193846f3e27472bIan Rogers for (It it = spaces.begin(), end = spaces.end(); it != end; ++it) { 15191d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::ContinuousSpace* space = *it; 15201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (space->GetGcRetentionPolicy() != space::kGcRetentionPolicyNeverCollect) { 15217469ebf3888b8037421cb6834f37f946646265ecMathieu Chartier space->GetMarkBitmap()->Clear(); 1522b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 1523b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 15245301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier mark_stack_->Reset(); 1525e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 1526e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Reset the marked large objects. 15271d54e73444e017d3a65234e0f193846f3e27472bIan Rogers space::LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 1528e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier large_objects->GetMarkObjects()->Clear(); 152969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 153069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 15311d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace collector 15321d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 153369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} // namespace art 1534