mark_sweep.cc revision d8195f19840911a73b1491dfc8e7c18139753731
12faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes/* 22faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Copyright (C) 2011 The Android Open Source Project 32faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 42faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 52faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * you may not use this file except in compliance with the License. 62faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * You may obtain a copy of the License at 72faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 82faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 92faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 102faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Unless required by applicable law or agreed to in writing, software 112faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 122faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * See the License for the specific language governing permissions and 142faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * limitations under the License. 152faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes */ 1669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 17578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "mark_sweep.h" 1869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <climits> 2058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include <vector> 2158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 22357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#include "card_table.h" 23410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "class_loader.h" 24693267ad474039981e9be20a592ac2e4e3bd742eBrian Carlstrom#include "dex_cache.h" 2558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include "heap.h" 26410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "indirect_reference_table.h" 27410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes#include "intern_table.h" 2881d425b0b232962441616f8b14f73620bffef5e5Ian Rogers#include "jni_internal.h" 29578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "logging.h" 30578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "macros.h" 31c33a32bccc4c66ed82ce3a580b16636399385cb4Elliott Hughes#include "monitor.h" 3281d425b0b232962441616f8b14f73620bffef5e5Ian Rogers#include "mutex.h" 33578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "object.h" 341f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom#include "runtime.h" 3558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro#include "space.h" 36307f75d6bcf7c32db7e1b43124dead628cc7ce96Elliott Hughes#include "timing_logger.h" 37578bbdc684db8ed68e9fedbc678669d27fa68b6eBrian Carlstrom#include "thread.h" 3869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 39d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartierstatic const bool kUseMarkStackPrefetch = true; 40357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 4169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapironamespace art { 4269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 43357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierclass SetFingerVisitor { 44357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier public: 45357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 46357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 47357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 48357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 49357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier void operator ()(void* finger) const { 50357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep_->SetFinger(reinterpret_cast<Object*>(finger)); 51357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 52357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 53357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier private: 54357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* const mark_sweep_; 55357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier}; 56357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 57d8195f19840911a73b1491dfc8e7c18139753731Mathieu ChartierMarkSweep::MarkSweep(ObjectStack* mark_stack) 58b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier : current_mark_bitmap_(NULL), 59b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier mark_stack_(mark_stack), 605301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier heap_(NULL), 615301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier finger_(NULL), 62e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier immune_begin_(NULL), 63e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier immune_end_(NULL), 645301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier soft_reference_list_(NULL), 655301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier weak_reference_list_(NULL), 665301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier finalizer_reference_list_(NULL), 675301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier phantom_reference_list_(NULL), 685301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier cleared_reference_list_(NULL), 69357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier freed_bytes_(0), freed_objects_(0), 705301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier class_count_(0), array_count_(0), other_count_(0) { 715301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier DCHECK(mark_stack_ != NULL); 725301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier} 73b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 745301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartiervoid MarkSweep::Init() { 75b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_ = Runtime::Current()->GetHeap(); 765301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier mark_stack_->Reset(); 7758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 78b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 79b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // TODO: C++0x auto 80b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) { 81357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL || (*cur)->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) { 82b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier current_mark_bitmap_ = (*cur)->GetMarkBitmap(); 83b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 84b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 85b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 86357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL) { 87357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier GetHeap()->DumpSpaces(); 88357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier DCHECK(false) << "current_mark_bitmap_ == NULL"; 89357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 900d966cff87464544a264efdbfba6c379474d5928buzbee // TODO: if concurrent, enable card marking in compiler 9158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro // TODO: check that the mark bitmap is entirely clear. 9258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 9358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 94357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierinline void MarkSweep::MarkObject0(const Object* obj, bool check_finger) { 9569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 96b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 97e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (obj >= immune_begin_ && obj < immune_end_) { 98e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier DCHECK(IsMarked(obj)); 99357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return; 100357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 101357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 102b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Try to take advantage of locality of references within a space, failing this find the space 103b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // the hard way. 104506de0cfe98c10b908d2ddb119bbb201542cbfcdIan Rogers if (UNLIKELY(!current_mark_bitmap_->HasAddress(obj))) { 105e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj); 106e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (new_bitmap != NULL) { 107e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier current_mark_bitmap_ = new_bitmap; 108e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else { 109e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 110e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_objects = large_object_space->GetMarkObjects(); 111e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!large_objects->Test(obj)) { 11283cf3280b70ae47e8f727eb1c0812f4eb04fb438Mathieu Chartier CHECK(large_object_space->Contains(obj)) << "Attempting to mark object " << obj << " not in large object space"; 113e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier large_objects->Set(obj); 114e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Don't need to check finger since large objects never have any object references. 115e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 116e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // TODO: Improve clarity of control flow in this function? 117e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier return; 118357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 119b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 120b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 12169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // This object was not previously marked. 122e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!current_mark_bitmap_->Test(obj)) { 123357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_->Set(obj); 12469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (check_finger && obj < finger_) { 125d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Do we need to expand the mark stack? 126d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 127d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier std::vector<Object*> temp; 128d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier temp.insert(temp.begin(), mark_stack_->Begin(), mark_stack_->End()); 129d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack_->Resize(mark_stack_->Capacity() * 2); 130d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (size_t i = 0; i < temp.size(); ++i) { 131d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack_->PushBack(temp[i]); 132d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 133d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 13469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // The object must be pushed on to the mark stack. 135d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack_->PushBack(const_cast<Object*>(obj)); 13669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 13769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 13869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 13969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 14069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Used to mark objects when recursing. Recursion is done by moving 14169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger across the bitmaps in address order and marking child 14269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// objects. Any newly-marked objects whose addresses are lower than 14369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger won't be visited by the bitmap scan, so those objects 14469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// need to be added to the mark stack. 145b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::MarkObject(const Object* obj) { 14669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj != NULL) { 14769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject0(obj, true); 14869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 14969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 15069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 151cf4c6c41b0084dc4567ff709fb8ce9ebd72b26acElliott Hughesvoid MarkSweep::MarkObjectVisitor(const Object* root, void* arg) { 1521f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(root != NULL); 1531f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(arg != NULL); 1541f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 1555d76c435082332ef79a22962386fa92a0870e378Ian Rogers mark_sweep->MarkObject0(root, false); 1561f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom} 1571f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 158262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) { 159262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(root != NULL); 160262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier DCHECK(arg != NULL); 161262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 162262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier mark_sweep->MarkObject0(root, true); 163262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 164262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 16569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Marks all objects in the root set. 16669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkRoots() { 1671f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom Runtime::Current()->VisitRoots(MarkObjectVisitor, this); 16869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 16969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 170b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartierclass CheckObjectVisitor { 171b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier public: 172b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier CheckObjectVisitor(MarkSweep* const mark_sweep) 173b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier : mark_sweep_(mark_sweep) { 174b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 175b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier } 176b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 17700f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const 178b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, 179b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers Locks::mutator_lock_) { 180b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep_->CheckReference(obj, ref, offset, is_static); 181b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier } 182b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 183b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier private: 184b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* const mark_sweep_; 185b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier}; 186b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 187b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckObject(const Object* obj) { 188b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(obj != NULL); 189b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier CheckObjectVisitor visitor(this); 190b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier VisitObjectReferences(obj, visitor); 191b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 192b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 193b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) { 194b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(root != NULL); 195b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(arg != NULL); 196b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 197b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root)); 198b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier mark_sweep->CheckObject(root); 199b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier} 200b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 2012fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartiervoid MarkSweep::CopyMarkBits(ContinuousSpace* space) { 202357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 203357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 204357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_bitmap->CopyFrom(live_bitmap); 2055d76c435082332ef79a22962386fa92a0870e378Ian Rogers} 2065d76c435082332ef79a22962386fa92a0870e378Ian Rogers 207cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartierclass ScanImageRootVisitor { 208cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 209cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ScanImageRootVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 210cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 211cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 21200f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* root) const 213b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 214b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 215cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier DCHECK(root != NULL); 216cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier mark_sweep_->ScanObject(root); 217cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 218cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 219cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 220cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* const mark_sweep_; 221cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 222cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 223357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::ScanGrayObjects(bool update_finger) { 224357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 225262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier CardTable* card_table = heap_->GetCardTable(); 226cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ScanImageRootVisitor image_root_visitor(this); 227357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor finger_visitor(this); 228e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // TODO: C++ 0x auto 229357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 2302fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 231357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* begin = space->Begin(); 232357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier byte* end = space->End(); 233b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Image spaces are handled properly since live == marked for them. 234357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 235357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (update_finger) { 236357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier card_table->Scan(mark_bitmap, begin, end, image_root_visitor, finger_visitor); 237357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } else { 238357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier card_table->Scan(mark_bitmap, begin, end, image_root_visitor, IdentityFunctor()); 239357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 240262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 241262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 242262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 243cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartierclass CheckBitmapVisitor { 244cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 245cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier CheckBitmapVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) { 246cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 247cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 248cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 24900f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers void operator ()(const Object* obj) const 250b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, 251b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers Locks::mutator_lock_) { 252cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier DCHECK(obj != NULL); 253cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier mark_sweep_->CheckObject(obj); 254cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 255cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 256cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier private: 257cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier MarkSweep* mark_sweep_; 258cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 259cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 260262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartiervoid MarkSweep::VerifyImageRoots() { 261262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // Verify roots ensures that all the references inside the image space point 262262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // objects which are either in the image space or marked objects in the alloc 263262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier // space 264cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier CheckBitmapVisitor visitor(this); 265cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 266cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 2672fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier if ((*it)->IsImageSpace()) { 2682fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ImageSpace* space = (*it)->AsImageSpace(); 269cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 270cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 271cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 272b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(live_bitmap != NULL); 273357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier live_bitmap->VisitMarkedRange(begin, end, visitor, IdentityFunctor()); 274262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 275262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 276262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 277262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 278357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierclass ScanObjectVisitor { 279357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier public: 280357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) { 281357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 282357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 283357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 284357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier void operator ()(const Object* obj) const 285b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 286b726dcb581bf72da46527378ccb6889020f0e6e9Ian Rogers SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 287357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep_->ScanObject(obj); 288357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 289357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 290357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier private: 291357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* const mark_sweep_; 292357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier}; 293357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 29458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Populates the mark stack based on the set of marked objects and 29558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// recursively marks until the mark stack is emptied. 296357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::RecursiveMark(bool partial, TimingLogger& timings) { 2971f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // RecursiveMark will build the lists of known instances of the Reference classes. 2981f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom // See DelayReferenceReferent for details. 2991f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(soft_reference_list_ == NULL); 3001f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(weak_reference_list_ == NULL); 3011f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(finalizer_reference_list_ == NULL); 3021f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(phantom_reference_list_ == NULL); 3031f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom CHECK(cleared_reference_list_ == NULL); 3041f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom 305cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 306cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 307357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor set_finger_visitor(this); 308357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObjectVisitor scan_visitor(this); 309357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 3102fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 311cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT || 312cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT) 313cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ) { 314357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_ = space->GetMarkBitmap(); 315357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL) { 316357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier GetHeap()->DumpSpaces(); 317e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LOG(FATAL) << "invalid bitmap"; 318357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 319357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // This function does not handle heap end increasing, so we must use the space end. 320cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 321cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 322357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor, set_finger_visitor); 3237664f5cd118b355a5fe0c7536cb48ac991ed2b62Mathieu Chartier } 32458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 32558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro finger_ = reinterpret_cast<Object*>(~0); 326357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("RecursiveMark"); 3275d76c435082332ef79a22962386fa92a0870e378Ian Rogers // TODO: tune the frequency of emptying the mark stack 32858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ProcessMarkStack(); 329357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("ProcessMarkStack"); 330357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 331357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 332357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::RecursiveMarkCards(CardTable* card_table, const std::vector<byte*>& cards, 333357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier TimingLogger& timings) { 334357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanImageRootVisitor image_root_visitor(this); 335357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SetFingerVisitor finger_visitor(this); 336357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (size_t i = 0;i < cards.size();) { 337357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object* start_obj = reinterpret_cast<Object*>(card_table->AddrFromCard(cards[i])); 338357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(start_obj); 339357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier uintptr_t end = begin + GC_CARD_SIZE; 340357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (++i; reinterpret_cast<uintptr_t>(cards[i]) == end && i < cards.size(); ++i) { 341357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier end += GC_CARD_SIZE; 342357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 343357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL || !current_mark_bitmap_->HasAddress(start_obj)) { 344357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_ = heap_->GetMarkBitmap()->GetSpaceBitmap(start_obj); 345357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#ifndef NDEBUG 346357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (current_mark_bitmap_ == NULL) { 347357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier GetHeap()->DumpSpaces(); 348e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LOG(FATAL) << "Object " << reinterpret_cast<const void*>(start_obj); 349357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 350357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#endif 351357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 352357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier current_mark_bitmap_->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor); 353357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 354357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("RecursiveMarkCards"); 355357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ProcessMarkStack(); 356357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier timings.AddSplit("ProcessMarkStack"); 35758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 35858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 359357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierbool MarkSweep::IsMarkedCallback(const Object* object, void* arg) { 360357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return 361357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier reinterpret_cast<MarkSweep*>(arg)->IsMarked(object) || 362357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object); 363357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 364357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 365357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartierbool MarkSweep::IsLiveCallback(const Object* object, void* arg) { 366357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier return 367357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object) || 368357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier !reinterpret_cast<MarkSweep*>(arg)->IsMarked(object); 369357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 370357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 371357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::RecursiveMarkDirtyObjects(bool update_finger) { 372357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanGrayObjects(update_finger); 373262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier ProcessMarkStack(); 374262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier} 375262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 37658551df3c2646ed507feec9e9eb3768085a76059Carl Shapirovoid MarkSweep::ReMarkRoots() { 377262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier Runtime::Current()->VisitRoots(ReMarkObjectVisitor, this); 37858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 37958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 380357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::SweepJniWeakGlobals(bool swap_bitmaps) { 381357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier HeapBitmap* live_bitmap = GetHeap()->GetLiveBitmap(); 382357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier HeapBitmap* mark_bitmap = GetHeap()->GetMarkBitmap(); 383357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 384357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (swap_bitmaps) { 385357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::swap(live_bitmap, mark_bitmap); 386357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 387357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 388410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes JavaVMExt* vm = Runtime::Current()->GetJavaVM(); 38950b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 390410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes IndirectReferenceTable* table = &vm->weak_globals; 391654d3a217faf46310895a1825354d610c2f3d6c2Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 392410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes for (It it = table->begin(), end = table->end(); it != end; ++it) { 393410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes const Object** entry = *it; 394357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (live_bitmap->Test(*entry) && !mark_bitmap->Test(*entry)) { 395410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes *entry = kClearedJniWeakGlobal; 396410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 397410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes } 398410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes} 399410c0c876f326e14c176a39ba21fc4dd3f7db8abElliott Hughes 40046a23638436afdf17330870ef150f5b8eb66410cMathieu Chartiervoid MarkSweep::SweepSystemWeaks(bool swap_bitmaps) { 40146a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier Runtime* runtime = Runtime::Current(); 402357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // The callbacks check 403357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !is_marked where is_marked is the callback but we want 404357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // !IsMarked && IsLive 405357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // So compute !(!IsMarked && IsLive) which is equal to (IsMarked || !IsLive). 406357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Or for swapped (IsLive || !IsMarked). 40746a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(swap_bitmaps ? IsLiveCallback : IsMarkedCallback, 40846a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier this); 40946a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier runtime->GetMonitorList()->SweepMonitorList(swap_bitmaps ? IsLiveCallback : IsMarkedCallback, 41046a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier this); 411357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SweepJniWeakGlobals(swap_bitmaps); 41269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 41369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 414c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartierbool MarkSweep::VerifyIsLiveCallback(const Object* obj, void* arg) { 415c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 416c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // We don't actually want to sweep the object, so lets return "marked" 417c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier return true; 418c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 419c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 420c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifyIsLive(const Object* obj) { 421c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Heap* heap = GetHeap(); 422c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier if (!heap->GetLiveBitmap()->Test(obj)) { 423c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 424c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier heap->allocation_stack_->End()) { 425c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // Object not found! 426c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier heap->DumpSpaces(); 427c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier LOG(FATAL) << "Found dead object " << obj; 428c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 429c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 430c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 431c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 432c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartiervoid MarkSweep::VerifySystemWeaks() { 433c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier Runtime* runtime = Runtime::Current(); 434c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier // Verify system weaks, uses a special IsMarked callback which always returns true. 435c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetInternTable()->SweepInternTableWeaks(VerifyIsLiveCallback, this); 436c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier runtime->GetMonitorList()->SweepMonitorList(VerifyIsLiveCallback, this); 437c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 438c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier JavaVMExt* vm = runtime->GetJavaVM(); 43950b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers MutexLock mu(Thread::Current(), vm->weak_globals_lock); 440c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier IndirectReferenceTable* table = &vm->weak_globals; 441c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto 442c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier for (It it = table->begin(), end = table->end(); it != end; ++it) { 443c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier const Object** entry = *it; 444c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier VerifyIsLive(*entry); 445c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier } 446c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier} 447c7b83a0d8ac73bdfff751619ae2a34948e3534b7Mathieu Chartier 448b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughesstruct SweepCallbackContext { 449357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep; 450b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes AllocSpace* space; 45150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self; 452b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes}; 453b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes 45430fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogersvoid MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 455307f75d6bcf7c32db7e1b43124dead628cc7ce96Elliott Hughes size_t freed_objects = num_ptrs; 456307f75d6bcf7c32db7e1b43124dead628cc7ce96Elliott Hughes size_t freed_bytes = 0; 457b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 458357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier MarkSweep* mark_sweep = context->mark_sweep; 459357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = mark_sweep->GetHeap(); 460b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes AllocSpace* space = context->space; 46150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = context->self; 46250b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(self); 4635d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Use a bulk free, that merges consecutive objects before freeing or free per object? 4645d76c435082332ef79a22962386fa92a0870e378Ian Rogers // Documentation suggests better free performance with merging, but this may be at the expensive 4655d76c435082332ef79a22962386fa92a0870e378Ian Rogers // of allocation. 4665d76c435082332ef79a22962386fa92a0870e378Ian Rogers // TODO: investigate performance 46730fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogers static const bool kUseFreeList = true; 46830fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogers if (kUseFreeList) { 4695d76c435082332ef79a22962386fa92a0870e378Ian Rogers for (size_t i = 0; i < num_ptrs; ++i) { 4705d76c435082332ef79a22962386fa92a0870e378Ian Rogers Object* obj = static_cast<Object*>(ptrs[i]); 47130fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogers freed_bytes += space->AllocationSize(obj); 4725d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 47330fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogers // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit 47450b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers space->FreeList(self, num_ptrs, ptrs); 4755d76c435082332ef79a22962386fa92a0870e378Ian Rogers } else { 4765d76c435082332ef79a22962386fa92a0870e378Ian Rogers for (size_t i = 0; i < num_ptrs; ++i) { 4775d76c435082332ef79a22962386fa92a0870e378Ian Rogers Object* obj = static_cast<Object*>(ptrs[i]); 47830fab40ee5a07af6b8c3b6b0e9438071695a57f4Ian Rogers freed_bytes += space->AllocationSize(obj); 47950b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers space->Free(self, obj); 4805d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 48158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 482357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 48300f7d0eaa6bd93d33bf0c1429bf4ba0b3f28abacIan Rogers heap->RecordFree(freed_objects, freed_bytes); 484357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_objects_ += freed_objects; 485357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier mark_sweep->freed_bytes_ += freed_bytes; 48658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 48758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 488cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 489cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 49050b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Locks::heap_bitmap_lock_->AssertExclusiveHeld(context->self); 491357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Heap* heap = context->mark_sweep->GetHeap(); 492cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // We don't free any actual memory to avoid dirtying the shared zygote pages. 493cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (size_t i = 0; i < num_ptrs; ++i) { 494cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier Object* obj = static_cast<Object*>(ptrs[i]); 495cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetLiveBitmap()->Clear(obj); 496cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier heap->GetCardTable()->MarkCard(obj); 497cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 498cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 499cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 500d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartiervoid MarkSweep::SweepArray(TimingLogger& logger, ObjectStack* allocations, bool swap_bitmaps) { 501357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_bytes = 0; 502357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier AllocSpace* space = heap_->GetAllocSpace(); 503357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 504357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 505357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 506357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // TODO: Fix when sweeping weaks works properly with mutators unpaused + allocation list. 507357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // SweepSystemWeaks(swap_bitmaps); 508357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 509357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Newly allocated objects MUST be in the alloc space and those are the only objects which we are 510357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // going to free. 511357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 512357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 513e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 514e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 515e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 516357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (swap_bitmaps) { 517357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier std::swap(live_bitmap, mark_bitmap); 518e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 519357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 520357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 521e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_large_objects = 0; 522357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t count = allocations->Size(); 523d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier Object** objects = const_cast<Object**>(allocations->Begin()); 524357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object** out = objects; 525357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 526357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Empty the allocation stack. 52750b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 528357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (size_t i = 0;i < count;++i) { 529357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier Object* obj = objects[i]; 530e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // There should only be objects in the AllocSpace/LargeObjectSpace in the allocation stack. 531e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (LIKELY(mark_bitmap->HasAddress(obj))) { 532e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!mark_bitmap->Test(obj)) { 533e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Don't bother un-marking since we clear the mark bitmap anyways. 534e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier *(out++) = obj; 535e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t size = space->AllocationSize(obj); 536e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier freed_bytes += size; 537e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 538e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } else if (!large_mark_objects->Test(obj)) { 539e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_large_objects; 540e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t size = large_object_space->AllocationSize(obj); 5412fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier freed_bytes += size; 54250b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers large_object_space->Free(self, obj); 543357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 544357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 545357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier logger.AddSplit("Process allocation stack"); 546357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 547357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier size_t freed_objects = out - objects; 54840e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier VLOG(heap) << "Freed " << freed_objects << "/" << count 549e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier << " objects with size " << PrettySize(freed_bytes); 55050b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers space->FreeList(self, freed_objects, objects); 551e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes); 55240e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_objects_ += freed_objects; 55340e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier freed_bytes_ += freed_bytes; 55440e978b0bb5e0011a69d7d1fb83a3e59f2df4f84Mathieu Chartier logger.AddSplit("FreeList"); 555357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier allocations->Reset(); 556357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier logger.AddSplit("Reset stack"); 557357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 558357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 559357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::Sweep(bool partial, bool swap_bitmaps) { 560b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 561b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 562357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark 563357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // bitmap, resulting in occasional frees of Weaks which are still in use. 564357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // SweepSystemWeaks(swap_bitmaps); 565357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 56646a23638436afdf17330870ef150f5b8eb66410cMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 567b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes SweepCallbackContext scc; 568357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier scc.mark_sweep = this; 56950b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers scc.self = Thread::Current(); 570357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // TODO: C++0x auto 571357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 5722fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier ContinuousSpace* space = *it; 573cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if ( 574cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT || 575cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT) 576cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier ) { 577cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 578cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 579cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier scc.space = space->AsAllocSpace(); 580cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 581cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 582fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier if (swap_bitmaps) { 583fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier std::swap(live_bitmap, mark_bitmap); 584fd678beb171a4686a4f2d53ca4188a4ade8fa54eMathieu Chartier } 585cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) { 586cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked. 587357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 588357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier &SweepCallback, reinterpret_cast<void*>(&scc)); 589cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } else { 590cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual memory. 591357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 592357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier &ZygoteSweepCallback, reinterpret_cast<void*>(&scc)); 593cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 59458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 59558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 59658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 59758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 598e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartiervoid MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 599e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Sweep large objects 600e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 601e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 602e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 603e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (swap_bitmaps) { 604e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier std::swap(large_live_objects, large_mark_objects); 605e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 606e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier SpaceSetMap::Objects& live_objects = large_live_objects->GetObjects(); 607e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // O(n*log(n)) but hopefully there are not too many large objects. 608e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier size_t freed_objects = 0; 6092fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier size_t freed_bytes = 0; 610e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // TODO: C++0x 61150b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers Thread* self = Thread::Current(); 612e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier for (SpaceSetMap::Objects::iterator it = live_objects.begin(); it != live_objects.end(); ++it) { 613e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier if (!large_mark_objects->Test(*it)) { 6142fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier freed_bytes += large_object_space->AllocationSize(*it); 61550b35e2fd1a68cd1240e4a9d9f363e11764957d1Ian Rogers large_object_space->Free(self, const_cast<Object*>(*it)); 616e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier ++freed_objects; 617e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 618e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier } 619e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier freed_objects_ += freed_objects; 6202fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier freed_bytes_ += freed_bytes; 621e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Large objects don't count towards bytes_allocated. 6222fde53367dbe721e5273c34b590e67112322cc9eMathieu Chartier GetHeap()->RecordFree(freed_objects, freed_bytes); 623e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier} 624e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 62569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans instance fields. 626b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanInstanceFields(const Object* obj) { 62769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 6284873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom Class* klass = obj->GetClass(); 6294873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom DCHECK(klass != NULL); 6302da50365eec2e77fca8925ba6b42edfecbdf6ad7Elliott Hughes ScanFields(obj, klass->GetReferenceInstanceOffsets(), false); 6314873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom} 6324873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom 6334873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom// Scans static storage on a Class. 634b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanStaticFields(const Class* klass) { 6354873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom DCHECK(klass != NULL); 636adb460d96702573de6e732ad58ca0380405cd928Elliott Hughes ScanFields(klass, klass->GetReferenceStaticOffsets(), true); 6374873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom} 6384873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom 639b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static) { 64069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (ref_offsets != CLASS_WALK_SUPER) { 64169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Found a reference offset bitmap. Mark the specified offsets. 64269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (ref_offsets != 0) { 643357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier const size_t right_shift = CLZ(ref_offsets); 6440cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers MemberOffset byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift); 6450cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers const Object* ref = obj->GetFieldObject<const Object*>(byte_offset, false); 64669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(ref); 647357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ref_offsets ^= CLASS_HIGH_BIT >> right_shift; 64869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 64969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 6504873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom // There is no reference offset bitmap. In the non-static case, 6514873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom // walk up the class inheritance hierarchy and find reference 6524873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom // offsets the hard way. In the static case, just consider this 6534873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom // class. 6544873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass(); 65569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro klass != NULL; 6564873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom klass = is_static ? NULL : klass->GetSuperClass()) { 6574873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom size_t num_reference_fields = (is_static 6584873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom ? klass->NumReferenceStaticFields() 6594873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom : klass->NumReferenceInstanceFields()); 6604873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom for (size_t i = 0; i < num_reference_fields; ++i) { 6614873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom Field* field = (is_static 6624873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom ? klass->GetStaticField(i) 6634873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom : klass->GetInstanceField(i)); 6640cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers MemberOffset field_offset = field->GetOffset(); 6650cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false); 66669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(ref); 66769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 66869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 66969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 67069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 67169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 672b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartiervoid MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) { 673b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 674b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // TODO: C++0x auto 675b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) { 676b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) { 677b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(IsMarked(obj)); 678b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 679b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool is_marked = IsMarked(ref); 680b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!is_marked) { 681b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(INFO) << **cur; 682b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref) 683b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj) 684b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "' (" << reinterpret_cast<const void*>(obj) << ") at offset " 685b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked"; 686b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier 687b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Class* klass = is_static ? obj->AsClass() : obj->GetClass(); 688b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(klass != NULL); 689b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields(); 690b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier DCHECK(fields != NULL); 691b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool found = false; 692b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier for (int32_t i = 0; i < fields->GetLength(); ++i) { 693b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Field* cur = fields->Get(i); 694b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (cur->GetOffset().Int32Value() == offset.Int32Value()) { 695b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur); 696b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier found = true; 697b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 698b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 699b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 700b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!found) { 701b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value(); 702262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier } 703262e5ffa1d4b23f23af3dea762a71a0af4bfd4a9Mathieu Chartier 704b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier bool obj_marked = heap_->GetCardTable()->IsDirty(obj); 705b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier if (!obj_marked) { 706b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' " 707b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "(" << reinterpret_cast<const void*>(obj) << ") contains references to " 708b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier << "the alloc space, but wasn't card marked"; 709b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 7105d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 7115d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 712b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier break; 7135d76c435082332ef79a22962386fa92a0870e378Ian Rogers } 7145d76c435082332ef79a22962386fa92a0870e378Ian Rogers} 7155d76c435082332ef79a22962386fa92a0870e378Ian Rogers 71669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header, static field references, and interface pointers 71769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// of a class object. 718b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanClass(const Object* obj) { 719352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#ifndef NDEBUG 720352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes ++class_count_; 721352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#endif 722693267ad474039981e9be20a592ac2e4e3bd742eBrian Carlstrom ScanInstanceFields(obj); 72340381fb9dc4b4cf274f1e58b2cdf4396202c6189Brian Carlstrom ScanStaticFields(obj->AsClass()); 72469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 72569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 72669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header of all array objects. If the array object is 72769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// specialized to a reference type, scans the array data as well. 728b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanArray(const Object* obj) { 729352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#ifndef NDEBUG 730352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes ++array_count_; 731352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#endif 73269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(obj->GetClass()); 73369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsObjectArray()) { 734db4d54081f09abcbe97ffdf615874f2809a9e777Brian Carlstrom const ObjectArray<Object>* array = obj->AsObjectArray<Object>(); 735d8ddfd5eadde1d5f53ef1419f529c799233eaa62Elliott Hughes for (int32_t i = 0; i < array->GetLength(); ++i) { 7365d76c435082332ef79a22962386fa92a0870e378Ian Rogers const Object* element = array->GetWithoutChecks(i); 73769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(element); 73869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 73969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 74069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 74169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 74269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Process the "referent" field in a java.lang.ref.Reference. If the 74369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent has not yet been marked, put it on the appropriate list in 74469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the gcHeap for later processing. 74569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::DelayReferenceReferent(Object* obj) { 74669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 7471f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom Class* klass = obj->GetClass(); 7481f87008b165d26541d832ff805250afdc89c253dBrian Carlstrom DCHECK(klass != NULL); 7490cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers DCHECK(klass->IsReferenceClass()); 750b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false); 751b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(obj); 75269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (pending == NULL && referent != NULL && !IsMarked(referent)) { 7534873d465a1eb6dfbdeddb085c81239d39db60c42Brian Carlstrom Object** list = NULL; 7540cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers if (klass->IsSoftReferenceClass()) { 75569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &soft_reference_list_; 7560cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsWeakReferenceClass()) { 75769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &weak_reference_list_; 7580cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsFinalizerReferenceClass()) { 75969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &finalizer_reference_list_; 7600cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers } else if (klass->IsPhantomReferenceClass()) { 76169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &phantom_reference_list_; 76269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 7630796af03edc06d92bb8d631f1c0c23befdae2315Brian Carlstrom DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags(); 764b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(obj, list); 76569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 76669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 76769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 76869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header and field references of a data object. If the 76969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scanned object is a reference subclass, it is scheduled for later 770adb460d96702573de6e732ad58ca0380405cd928Elliott Hughes// processing. 771b06631143b944388fc68bedf6679c006dde5f461Elliott Hughesinline void MarkSweep::ScanOther(const Object* obj) { 772352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#ifndef NDEBUG 773352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes ++other_count_; 774352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#endif 77569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanInstanceFields(obj); 776352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes if (obj->GetClass()->IsReferenceClass()) { 77769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DelayReferenceReferent(const_cast<Object*>(obj)); 77869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 77969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 78069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 781357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartiervoid MarkSweep::ScanRoot(const Object* obj) { 782357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier ScanObject(obj); 783357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier} 784357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 78569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans an object reference. Determines the type of the reference 78669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// and dispatches to a specialized scanning routine. 787cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiervoid MarkSweep::ScanObject(const Object* obj) { 78869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 78969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 790357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#ifndef NDEBUG 791357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if (!IsMarked(obj)) { 792357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier heap_->DumpSpaces(); 793357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier LOG(FATAL) << "Scanning unmarked object " << reinterpret_cast<const void*>(obj); 794357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 795357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier#endif 79669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsClass()) { 79769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanClass(obj); 798b63ec393a5c4ba2be1d34dd871cda811eaa803c7Brian Carlstrom } else if (obj->IsArrayInstance()) { 79969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanArray(obj); 80069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 80158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ScanOther(obj); 80269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 80369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 80469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 8055d76c435082332ef79a22962386fa92a0870e378Ian Rogers// Scan anything that's on the mark stack. 80669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessMarkStack() { 807d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (kUseMarkStackPrefetch) { 808d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_size = 4; 809d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const size_t fifo_mask = fifo_size - 1; 810d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* fifo[fifo_size]; 811d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (size_t i = 0;i < fifo_size;++i) { 812d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[i] = NULL; 813357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 814d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_pos = 0; 815d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t fifo_count = 0; 816d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier for (;;) { 817d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = fifo[fifo_pos & fifo_mask]; 818d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (obj != NULL) { 819d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 820d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = NULL; 821d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier --fifo_count; 822d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 823357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 824d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!mark_stack_->IsEmpty()) { 825d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 826d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 827d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo[fifo_pos & fifo_mask] = obj; 828d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier __builtin_prefetch(obj); 829d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_count++; 830d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 831d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier fifo_pos++; 832357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 833d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (!fifo_count) { 834d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier CHECK(mark_stack_->IsEmpty()) << mark_stack_->Size(); 835d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier break; 836d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 837d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 838d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } else { 839d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier while (!mark_stack_->IsEmpty()) { 840d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier const Object* obj = mark_stack_->PopBack(); 841d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(obj != NULL); 842d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier ScanObject(obj); 843357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 844357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier } 84569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 84669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 84769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Walks the reference list marking any references subject to the 84869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// reference clearing policy. References with a black referent are 84969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// removed from the list. References with white referents biased 85069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// toward saving are blackened and also removed from the list. 85169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::PreserveSomeSoftReferences(Object** list) { 85269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 85369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* clear = NULL; 85469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t counter = 0; 855b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 856b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier DCHECK(mark_stack_->IsEmpty()); 857b43b7d42b0c497333564e76be953157066c2b995Mathieu Chartier 85869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 859b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 860b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 86169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent == NULL) { 86269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent was cleared by the user during marking. 86369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro continue; 86469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 86569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool is_marked = IsMarked(referent); 86669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked && ((++counter) & 1)) { 86769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white and biased toward saving, mark it. 86869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 86969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro is_marked = true; 87069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 87169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked) { 87269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, queue it for clearing. 873b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueuePendingReference(ref, &clear); 87469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 87569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 87669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = clear; 87769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Restart the mark with the newly black references added to the 87869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // root set. 87969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 88069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 88169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 88269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Unlink the reference list clearing references objects with white 88369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents. Cleared references registered to a reference queue are 88469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scheduled for appending by the heap worker thread. 88569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ClearWhiteReferences(Object** list) { 88669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 88769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 888b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 889b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 89069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 89169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, clear it. 892b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 893b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes if (heap_->IsEnqueuable(ref)) { 894b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 89569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 89669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 89769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 89869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 89969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 90069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 90169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Enqueues finalizer references with white referents. White 90269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents are blackened, moved to the zombie field, and the 90369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent field is cleared. 90469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueFinalizerReferences(Object** list) { 90569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 906b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes MemberOffset zombie_offset = heap_->GetFinalizerReferenceZombieOffset(); 90769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool has_enqueued = false; 90869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 909b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* ref = heap_->DequeuePendingReference(list); 910b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes Object* referent = heap_->GetReferenceReferent(ref); 91169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 91269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 91369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // If the referent is non-null the reference must queuable. 914b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes DCHECK(heap_->IsEnqueuable(ref)); 9150cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers ref->SetFieldObject(zombie_offset, referent, false); 916b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->ClearReferenceReferent(ref); 917b3bd5f07884f5a1f2b84224363b1372d7c28d447Elliott Hughes heap_->EnqueueReference(ref, &cleared_reference_list_); 91869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro has_enqueued = true; 91969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 92069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 92169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (has_enqueued) { 92269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 92369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 92469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 92569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 92669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 92758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// Process reference class instances and schedule finalizations. 92869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft, 92969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** weak_references, 93069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** finalizer_references, 93169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** phantom_references) { 93269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(soft_references != NULL); 93369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(weak_references != NULL); 93469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(finalizer_references != NULL); 93569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(phantom_references != NULL); 93669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 93769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Unless we are in the zygote or required to clear soft references 93869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // with white references, preserve some white referents. 9392945e2455ba87e15b65f4a6a737bcdc8c0f2f31bIan Rogers if (!clear_soft && !Runtime::Current()->IsZygote()) { 94069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro PreserveSomeSoftReferences(soft_references); 94169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 94269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 94369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all remaining soft and weak references with white 94469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 94569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 94669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 94769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 94869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Preserve all white objects with finalize methods and schedule 94969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // them for finalization. 95069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueFinalizerReferences(finalizer_references); 95169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 95269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all f-reachable soft and weak references with white 95369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 95469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 95569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 95669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 95769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all phantom references with white referents. 95869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(phantom_references); 95969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 96069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // At this point all reference lists should be empty. 96169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*soft_references == NULL); 96269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*weak_references == NULL); 96369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*finalizer_references == NULL); 96469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*phantom_references == NULL); 96569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 96669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 96769759eaa6fd4386f1e6d8748052ad221087b3476Carl ShapiroMarkSweep::~MarkSweep() { 968352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#ifndef NDEBUG 9694dd9b4d95eec9db5338fb9bf132f9bb8facf6cf4Elliott Hughes VLOG(heap) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ << " other=" << other_count_; 970352a4244b62ad4a24eec6228dc4dd9983dfbf78eElliott Hughes#endif 971357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier // Ensure that the mark stack is empty. 972357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier CHECK(mark_stack_->IsEmpty()); 973357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier 974b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // Clear all of the alloc spaces' mark bitmaps. 975b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier const Spaces& spaces = heap_->GetSpaces(); 976b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier // TODO: C++0x auto 977357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) { 978357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier if ((*it)->GetGcRetentionPolicy() != GCRP_NEVER_COLLECT) { 979357e9be24c17a6bc2ae9fb53f25c73503116101dMathieu Chartier (*it)->GetMarkBitmap()->Clear(); 980b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 981b062fdd4cb097fbae69b4bcb479c34d83ecab8caMathieu Chartier } 9825301cd241b4d8afbfc1211e107c41f1b15c6bd48Mathieu Chartier mark_stack_->Reset(); 983e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier 984e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier // Reset the marked large objects. 985e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 986e0f0cb3d855cb5e926452b5e1ec8457adc4e454eMathieu Chartier large_objects->GetMarkObjects()->Clear(); 98769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 98869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 98969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} // namespace art 990