mark_sweep.cc revision 69759eaa6fd4386f1e6d8748052ad221087b3476
169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Copyright 2011 Google Inc. All Rights Reserved. 269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Author: cshapiro@google.com (Carl Shapiro) 369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/mark_sweep.h" 569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/logging.h" 769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/macros.h" 869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/mark_stack.h" 969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/object.h" 1069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#include "src/thread.h" 1169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro#define CLZ(x) __builtin_clz(x) 1369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapironamespace art { 1569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 1669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirosize_t MarkSweep::reference_referent_offset_ = 0; // TODO 1769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirosize_t MarkSweep::reference_queue_offset_ = 0; // TODO 1869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirosize_t MarkSweep::reference_queueNext_offset_ = 0; // TODO 1969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirosize_t MarkSweep::reference_pendingNext_offset_ = 0; // TODO 2069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirosize_t MarkSweep::finalizer_reference_zombie_offset_ = 0; // TODO 2169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 2269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkObject0(const Object* obj, bool check_finger) { 2369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 2469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj < condemned_) { 2569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(IsMarked(obj)); 2669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro return; 2769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 2869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool is_marked = mark_bitmap_->Test(obj); 2969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // This object was not previously marked. 3069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked) { 3169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro mark_bitmap_->Set(obj); 3269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (check_finger && obj < finger_) { 3369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // The object must be pushed on to the mark stack. 3469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro mark_stack_->Push(obj); 3569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 3669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 3769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 3869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 3969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Used to mark objects when recursing. Recursion is done by moving 4069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger across the bitmaps in address order and marking child 4169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// objects. Any newly-marked objects whose addresses are lower than 4269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the finger won't be visited by the bitmap scan, so those objects 4369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// need to be added to the mark stack. 4469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkObject(const Object* obj) { 4569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj != NULL) { 4669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject0(obj, true); 4769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 4869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 4969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 5069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Marks all objects in the root set. 5169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::MarkRoots() { 5269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro LOG(FATAL) << "Unimplemented"; 5369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 5469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 5569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ReMarkRoots() 5669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro{ 5769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro LOG(FATAL) << "Unimplemented"; 5869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 5969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 6069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans instance fields. 6169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanInstanceFields(const Object* obj) { 6269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 6369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 6469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro uint32_t ref_offsets = obj->GetClass()->GetReferenceOffsets(); 6569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (ref_offsets != CLASS_WALK_SUPER) { 6669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Found a reference offset bitmap. Mark the specified offsets. 6769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (ref_offsets != 0) { 6869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t right_shift = CLZ(ref_offsets); 6969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift); 7069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* ref = obj->GetFieldObject(byte_offset); 7169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(ref); 7269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift); 7369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 7469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 7569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // There is no reference offset bitmap for this class. Walk up 7669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // the class inheritance hierarchy and find reference offsets the 7769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // hard way. 7869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro for (Class *klass = obj->GetClass(); 7969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro klass != NULL; 8069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro klass = klass->GetSuperClass()) { 8169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro for (size_t i = 0; i < klass->NumReferenceInstanceFields(); ++i) { 8269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t field_offset = klass->GetInstanceField(i)->GetOffset(); 8369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* ref = obj->GetFieldObject(field_offset); 8469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(ref); 8569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 8669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 8769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 8869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 8969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 9069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the static fields of a class object. 9169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanStaticFields(const Class* klass) { 9269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(klass != NULL); 9369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro for (size_t i = 0; i < klass->NumStaticFields(); ++i) { 9469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // char ch = clazz->sfields[i].signature[0]; 9569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const StaticField* static_field = klass->GetStaticField(i); 9669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro char ch = static_field->GetType(); 9769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (ch == '[' || ch == 'L') { 9869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Object *obj = clazz->sfields[i].value.l; 9969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // markObject(obj, ctx); 10069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* obj = static_field->GetObject(); 10169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(obj); 10269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 10369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 10469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 10569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 10669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanInterfaces(const Class* klass) { 10769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(klass != NULL); 10869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro for (size_t i = 0; i < klass->NumInterfaces(); ++i) { 10969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(klass->GetInterface(i)); 11069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 11169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 11269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 11369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header, static field references, and interface pointers 11469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// of a class object. 11569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanClass(const Object* obj) { 11669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 11769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->IsClass()); 11869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Class* klass = obj->AsClass(); 11969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(klass->GetClass()); 12069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (klass->IsArray()) { 12169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(klass->GetComponentType()); 12269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 12369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (klass->IsLoaded()) { 12469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(klass->GetSuperClass()); 12569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 12669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(klass->GetClassLoader()); 12769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanInstanceFields(obj); 12869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanStaticFields(klass); 12969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // TODO: scan methods 13069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // TODO: scan instance fields 13169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (klass->IsLoaded()) { 13269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanInterfaces(klass); 13369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 13469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 13569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 13669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header of all array objects. If the array object is 13769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// specialized to a reference type, scans the array data as well. 13869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanArray(const Object *obj) { 13969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 14069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 14169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(obj->GetClass()); 14269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsObjectArray()) { 14369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const ObjectArray* array = obj->AsObjectArray(); 14469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro for (size_t i = 0; i < array->GetLength(); ++i) { 14569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* element = array->Get(i); 14669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(element); 14769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 14869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 14969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 15069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 15169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueuePendingReference(Object* ref, Object** list) { 15269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(ref != NULL); 15369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 15469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t offset = reference_pendingNext_offset_; 15569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (*list == NULL) { 15669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref->SetFieldObject(offset, ref); 15769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = ref; 15869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 15969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object *head = (*list)->GetFieldObject(offset); 16069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref->SetFieldObject(offset, head); 16169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro (*list)->SetFieldObject(offset, ref); 16269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 16369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 16469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 16569759eaa6fd4386f1e6d8748052ad221087b3476Carl ShapiroObject* MarkSweep::DequeuePendingReference(Object** list) { 16669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 16769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list != NULL); 16869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t offset = reference_pendingNext_offset_; 16969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* head = (*list)->GetFieldObject(offset); 17069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* ref; 17169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (*list == head) { 17269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref = *list; 17369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = NULL; 17469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 17569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object *next = head->GetFieldObject(offset); 17669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro (*list)->SetFieldObject(offset, next); 17769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref = head; 17869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 17969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref->SetFieldObject(offset, NULL); 18069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro return ref; 18169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 18269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 18369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Process the "referent" field in a java.lang.ref.Reference. If the 18469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent has not yet been marked, put it on the appropriate list in 18569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// the gcHeap for later processing. 18669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::DelayReferenceReferent(Object* obj) { 18769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 18869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 18969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro //DCHECK(IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)); 19069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* pending = obj->GetFieldObject(reference_pendingNext_offset_); 19169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* referent = obj->GetFieldObject(reference_referent_offset_); 19269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (pending == NULL && referent != NULL && !IsMarked(referent)) { 19369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object **list = NULL; 19469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsSoftReference()) { 19569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &soft_reference_list_; 19669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else if (obj->IsWeakReference()) { 19769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &weak_reference_list_; 19869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else if (obj->IsFinalizerReference()) { 19969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &finalizer_reference_list_; 20069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else if (obj->IsPhantomReference()) { 20169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro list = &phantom_reference_list_; 20269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 20369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 20469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueuePendingReference(obj, list); 20569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 20669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 20769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 20869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans the header and field references of a data object. If the 20969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scanned object is a reference subclass, it is scheduled for later 21069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// processing 21169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanDataObject(const Object *obj) { 21269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 21369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 21469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(obj->GetClass()); 21569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanInstanceFields(obj); 21669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsReference()) { 21769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DelayReferenceReferent(const_cast<Object*>(obj)); 21869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 21969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 22069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 22169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scans an object reference. Determines the type of the reference 22269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// and dispatches to a specialized scanning routine. 22369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanObject(const Object* obj) { 22469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj != NULL); 22569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(obj->GetClass() != NULL); 22669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(IsMarked(obj)); 22769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (obj->IsClass()) { 22869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanClass(obj); 22969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else if (obj->IsArray()) { 23069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanArray(obj); 23169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } else { 23269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanDataObject(obj); 23369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 23469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 23569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 23669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Scan anything that's on the mark stack. We can't use the bitmaps 23769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// anymore, so use a finger that points past the end of them. 23869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessMarkStack() { 23969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (!mark_stack_->IsEmpty()) { 24069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object *obj = mark_stack_->Pop(); 24169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ScanObject(obj); 24269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 24369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 24469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 24569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ScanDirtyObjects() { 24669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 24769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 24869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 24969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ClearReference(Object* ref) { 25069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(ref != NULL); 25169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref->SetFieldObject(reference_referent_offset_, NULL); 25269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 25369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 25469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirobool MarkSweep::IsEnqueuable(const Object* ref) { 25569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(ref != NULL); 25669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* queue = ref->GetFieldObject(reference_queue_offset_); 25769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro const Object* queue_next = ref->GetFieldObject(reference_queueNext_offset_); 25869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro return (queue != NULL) && (queue_next == NULL); 25969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 26069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 26169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueReference(Object* ref) { 26269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(ref != NULL); 26369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro CHECK(ref->GetFieldObject(reference_queue_offset_) != NULL); 26469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro CHECK(ref->GetFieldObject(reference_queueNext_offset_) == NULL); 26569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueuePendingReference(ref, &cleared_reference_list_); 26669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 26769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 26869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Walks the reference list marking any references subject to the 26969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// reference clearing policy. References with a black referent are 27069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// removed from the list. References with white referents biased 27169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// toward saving are blackened and also removed from the list. 27269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::PreserveSomeSoftReferences(Object** list) { 27369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 27469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* clear = NULL; 27569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t counter = 0; 27669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 27769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* ref = DequeuePendingReference(list); 27869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* referent = ref->GetFieldObject(reference_referent_offset_); 27969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent == NULL) { 28069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent was cleared by the user during marking. 28169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro continue; 28269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 28369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool is_marked = IsMarked(referent); 28469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked && ((++counter) & 1)) { 28569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white and biased toward saving, mark it. 28669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 28769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro is_marked = true; 28869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 28969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (!is_marked) { 29069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, queue it for clearing. 29169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueuePendingReference(ref, &clear); 29269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 29369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 29469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *list = clear; 29569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Restart the mark with the newly black references added to the 29669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // root set. 29769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 29869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 29969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 30069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Unlink the reference list clearing references objects with white 30169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents. Cleared references registered to a reference queue are 30269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// scheduled for appending by the heap worker thread. 30369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ClearWhiteReferences(Object** list) { 30469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 30569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t offset = reference_referent_offset_; 30669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 30769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object *ref = DequeuePendingReference(list); 30869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object *referent = ref->GetFieldObject(offset); 30969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 31069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Referent is white, clear it. 31169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearReference(ref); 31269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (IsEnqueuable(ref)) { 31369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueReference(ref); 31469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 31569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 31669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 31769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 31869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 31969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 32069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Enqueues finalizer references with white referents. White 32169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referents are blackened, moved to the zombie field, and the 32269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// referent field is cleared. 32369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueFinalizerReferences(Object** list) { 32469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(list != NULL); 32569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t referent_offset = reference_referent_offset_; 32669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro size_t zombie_offset = finalizer_reference_zombie_offset_; 32769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro bool has_enqueued = false; 32869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro while (*list != NULL) { 32969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* ref = DequeuePendingReference(list); 33069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object* referent = ref->GetFieldObject(referent_offset); 33169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (referent != NULL && !IsMarked(referent)) { 33269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro MarkObject(referent); 33369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // If the referent is non-null the reference must queuable. 33469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(IsEnqueuable(ref)); 33569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ref->SetFieldObject(zombie_offset, referent); 33669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearReference(ref); 33769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueReference(ref); 33869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro has_enqueued = true; 33969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 34069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 34169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (has_enqueued) { 34269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ProcessMarkStack(); 34369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 34469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*list == NULL); 34569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 34669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 34769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro/* 34869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro * Process reference class instances and schedule finalizations. 34969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro */ 35069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft, 35169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** weak_references, 35269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** finalizer_references, 35369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Object** phantom_references) { 35469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(soft_references != NULL); 35569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(weak_references != NULL); 35669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(finalizer_references != NULL); 35769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(phantom_references != NULL); 35869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 35969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Unless we are in the zygote or required to clear soft references 36069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // with white references, preserve some white referents. 36169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (clear_soft) { 36269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro PreserveSomeSoftReferences(soft_references); 36369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 36469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 36569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all remaining soft and weak references with white 36669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 36769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 36869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 36969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 37069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Preserve all white objects with finalize methods and schedule 37169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // them for finalization. 37269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro EnqueueFinalizerReferences(finalizer_references); 37369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 37469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all f-reachable soft and weak references with white 37569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // referents. 37669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(soft_references); 37769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(weak_references); 37869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 37969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Clear all phantom references with white referents. 38069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro ClearWhiteReferences(phantom_references); 38169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 38269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // At this point all reference lists should be empty. 38369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*soft_references == NULL); 38469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*weak_references == NULL); 38569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*finalizer_references == NULL); 38669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(*phantom_references == NULL); 38769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 38869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 38969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro// Pushes a list of cleared references out to the managed heap. 39069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapirovoid MarkSweep::EnqueueClearedReferences(Object** cleared) { 39169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(cleared != NULL); 39269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro if (*cleared != NULL) { 39369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro Thread* self = Thread::Current(); 39469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro DCHECK(self != NULL); 39569759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // TODO: Method *meth = gDvm.methJavaLangRefReferenceQueueAdd; 39669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // DCHECK(meth != NULL); 39769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // JValue unused; 39869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // Object *reference = *cleared; 39969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro // TODO: dvmCallMethod(self, meth, NULL, &unused, reference); 40069759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro LOG(FATAL) << "Unimplemented"; 40169759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro *cleared = NULL; 40269759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro } 40369759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 40469759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 40569759eaa6fd4386f1e6d8748052ad221087b3476Carl ShapiroMarkSweep::~MarkSweep() { 40669759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro mark_bitmap_->Clear(); 40769759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} 40869759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro 40969759eaa6fd4386f1e6d8748052ad221087b3476Carl Shapiro} // namespace art 410