| // Copyright 2011 Google Inc. All Rights Reserved. |
| // Author: cshapiro@google.com (Carl Shapiro) |
| |
| #include "src/mark_sweep.h" |
| |
| #include "src/logging.h" |
| #include "src/macros.h" |
| #include "src/mark_stack.h" |
| #include "src/object.h" |
| #include "src/thread.h" |
| |
| #define CLZ(x) __builtin_clz(x) |
| |
| namespace art { |
| |
| size_t MarkSweep::reference_referent_offset_ = 0; // TODO |
| size_t MarkSweep::reference_queue_offset_ = 0; // TODO |
| size_t MarkSweep::reference_queueNext_offset_ = 0; // TODO |
| size_t MarkSweep::reference_pendingNext_offset_ = 0; // TODO |
| size_t MarkSweep::finalizer_reference_zombie_offset_ = 0; // TODO |
| |
| void MarkSweep::MarkObject0(const Object* obj, bool check_finger) { |
| DCHECK(obj != NULL); |
| if (obj < condemned_) { |
| DCHECK(IsMarked(obj)); |
| return; |
| } |
| bool is_marked = mark_bitmap_->Test(obj); |
| // This object was not previously marked. |
| if (!is_marked) { |
| mark_bitmap_->Set(obj); |
| if (check_finger && obj < finger_) { |
| // The object must be pushed on to the mark stack. |
| mark_stack_->Push(obj); |
| } |
| } |
| } |
| |
| // Used to mark objects when recursing. Recursion is done by moving |
| // the finger across the bitmaps in address order and marking child |
| // objects. Any newly-marked objects whose addresses are lower than |
| // the finger won't be visited by the bitmap scan, so those objects |
| // need to be added to the mark stack. |
| void MarkSweep::MarkObject(const Object* obj) { |
| if (obj != NULL) { |
| MarkObject0(obj, true); |
| } |
| } |
| |
| // Marks all objects in the root set. |
| void MarkSweep::MarkRoots() { |
| LOG(FATAL) << "Unimplemented"; |
| } |
| |
| void MarkSweep::ReMarkRoots() |
| { |
| LOG(FATAL) << "Unimplemented"; |
| } |
| |
| // Scans instance fields. |
| void MarkSweep::ScanInstanceFields(const Object* obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->GetClass() != NULL); |
| uint32_t ref_offsets = obj->GetClass()->GetReferenceOffsets(); |
| if (ref_offsets != CLASS_WALK_SUPER) { |
| // Found a reference offset bitmap. Mark the specified offsets. |
| while (ref_offsets != 0) { |
| size_t right_shift = CLZ(ref_offsets); |
| size_t byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift); |
| const Object* ref = obj->GetFieldObject(byte_offset); |
| MarkObject(ref); |
| ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift); |
| } |
| } else { |
| // There is no reference offset bitmap for this class. Walk up |
| // the class inheritance hierarchy and find reference offsets the |
| // hard way. |
| for (Class *klass = obj->GetClass(); |
| klass != NULL; |
| klass = klass->GetSuperClass()) { |
| for (size_t i = 0; i < klass->NumReferenceInstanceFields(); ++i) { |
| size_t field_offset = klass->GetInstanceField(i)->GetOffset(); |
| const Object* ref = obj->GetFieldObject(field_offset); |
| MarkObject(ref); |
| } |
| } |
| } |
| } |
| |
| // Scans the static fields of a class object. |
| void MarkSweep::ScanStaticFields(const Class* klass) { |
| DCHECK(klass != NULL); |
| for (size_t i = 0; i < klass->NumStaticFields(); ++i) { |
| // char ch = clazz->sfields[i].signature[0]; |
| const StaticField* static_field = klass->GetStaticField(i); |
| char ch = static_field->GetType(); |
| if (ch == '[' || ch == 'L') { |
| // Object *obj = clazz->sfields[i].value.l; |
| // markObject(obj, ctx); |
| const Object* obj = static_field->GetObject(); |
| MarkObject(obj); |
| } |
| } |
| } |
| |
| void MarkSweep::ScanInterfaces(const Class* klass) { |
| DCHECK(klass != NULL); |
| for (size_t i = 0; i < klass->NumInterfaces(); ++i) { |
| MarkObject(klass->GetInterface(i)); |
| } |
| } |
| |
| // Scans the header, static field references, and interface pointers |
| // of a class object. |
| void MarkSweep::ScanClass(const Object* obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->IsClass()); |
| const Class* klass = obj->AsClass(); |
| MarkObject(klass->GetClass()); |
| if (klass->IsArray()) { |
| MarkObject(klass->GetComponentType()); |
| } |
| if (klass->IsLoaded()) { |
| MarkObject(klass->GetSuperClass()); |
| } |
| MarkObject(klass->GetClassLoader()); |
| ScanInstanceFields(obj); |
| ScanStaticFields(klass); |
| // TODO: scan methods |
| // TODO: scan instance fields |
| if (klass->IsLoaded()) { |
| ScanInterfaces(klass); |
| } |
| } |
| |
| // Scans the header of all array objects. If the array object is |
| // specialized to a reference type, scans the array data as well. |
| void MarkSweep::ScanArray(const Object *obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->GetClass() != NULL); |
| MarkObject(obj->GetClass()); |
| if (obj->IsObjectArray()) { |
| const ObjectArray* array = obj->AsObjectArray(); |
| for (size_t i = 0; i < array->GetLength(); ++i) { |
| const Object* element = array->Get(i); |
| MarkObject(element); |
| } |
| } |
| } |
| |
| void MarkSweep::EnqueuePendingReference(Object* ref, Object** list) { |
| DCHECK(ref != NULL); |
| DCHECK(list != NULL); |
| size_t offset = reference_pendingNext_offset_; |
| if (*list == NULL) { |
| ref->SetFieldObject(offset, ref); |
| *list = ref; |
| } else { |
| Object *head = (*list)->GetFieldObject(offset); |
| ref->SetFieldObject(offset, head); |
| (*list)->SetFieldObject(offset, ref); |
| } |
| } |
| |
| Object* MarkSweep::DequeuePendingReference(Object** list) { |
| DCHECK(list != NULL); |
| DCHECK(*list != NULL); |
| size_t offset = reference_pendingNext_offset_; |
| Object* head = (*list)->GetFieldObject(offset); |
| Object* ref; |
| if (*list == head) { |
| ref = *list; |
| *list = NULL; |
| } else { |
| Object *next = head->GetFieldObject(offset); |
| (*list)->SetFieldObject(offset, next); |
| ref = head; |
| } |
| ref->SetFieldObject(offset, NULL); |
| return ref; |
| } |
| |
| // Process the "referent" field in a java.lang.ref.Reference. If the |
| // referent has not yet been marked, put it on the appropriate list in |
| // the gcHeap for later processing. |
| void MarkSweep::DelayReferenceReferent(Object* obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->GetClass() != NULL); |
| //DCHECK(IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)); |
| Object* pending = obj->GetFieldObject(reference_pendingNext_offset_); |
| Object* referent = obj->GetFieldObject(reference_referent_offset_); |
| if (pending == NULL && referent != NULL && !IsMarked(referent)) { |
| Object **list = NULL; |
| if (obj->IsSoftReference()) { |
| list = &soft_reference_list_; |
| } else if (obj->IsWeakReference()) { |
| list = &weak_reference_list_; |
| } else if (obj->IsFinalizerReference()) { |
| list = &finalizer_reference_list_; |
| } else if (obj->IsPhantomReference()) { |
| list = &phantom_reference_list_; |
| } |
| DCHECK(list != NULL); |
| EnqueuePendingReference(obj, list); |
| } |
| } |
| |
| // Scans the header and field references of a data object. If the |
| // scanned object is a reference subclass, it is scheduled for later |
| // processing |
| void MarkSweep::ScanDataObject(const Object *obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->GetClass() != NULL); |
| MarkObject(obj->GetClass()); |
| ScanInstanceFields(obj); |
| if (obj->IsReference()) { |
| DelayReferenceReferent(const_cast<Object*>(obj)); |
| } |
| } |
| |
| // Scans an object reference. Determines the type of the reference |
| // and dispatches to a specialized scanning routine. |
| void MarkSweep::ScanObject(const Object* obj) { |
| DCHECK(obj != NULL); |
| DCHECK(obj->GetClass() != NULL); |
| DCHECK(IsMarked(obj)); |
| if (obj->IsClass()) { |
| ScanClass(obj); |
| } else if (obj->IsArray()) { |
| ScanArray(obj); |
| } else { |
| ScanDataObject(obj); |
| } |
| } |
| |
| // Scan anything that's on the mark stack. We can't use the bitmaps |
| // anymore, so use a finger that points past the end of them. |
| void MarkSweep::ProcessMarkStack() { |
| while (!mark_stack_->IsEmpty()) { |
| const Object *obj = mark_stack_->Pop(); |
| ScanObject(obj); |
| } |
| } |
| |
| void MarkSweep::ScanDirtyObjects() { |
| ProcessMarkStack(); |
| } |
| |
| void MarkSweep::ClearReference(Object* ref) { |
| DCHECK(ref != NULL); |
| ref->SetFieldObject(reference_referent_offset_, NULL); |
| } |
| |
| bool MarkSweep::IsEnqueuable(const Object* ref) { |
| DCHECK(ref != NULL); |
| const Object* queue = ref->GetFieldObject(reference_queue_offset_); |
| const Object* queue_next = ref->GetFieldObject(reference_queueNext_offset_); |
| return (queue != NULL) && (queue_next == NULL); |
| } |
| |
| void MarkSweep::EnqueueReference(Object* ref) { |
| DCHECK(ref != NULL); |
| CHECK(ref->GetFieldObject(reference_queue_offset_) != NULL); |
| CHECK(ref->GetFieldObject(reference_queueNext_offset_) == NULL); |
| EnqueuePendingReference(ref, &cleared_reference_list_); |
| } |
| |
| // Walks the reference list marking any references subject to the |
| // reference clearing policy. References with a black referent are |
| // removed from the list. References with white referents biased |
| // toward saving are blackened and also removed from the list. |
| void MarkSweep::PreserveSomeSoftReferences(Object** list) { |
| DCHECK(list != NULL); |
| Object* clear = NULL; |
| size_t counter = 0; |
| while (*list != NULL) { |
| Object* ref = DequeuePendingReference(list); |
| Object* referent = ref->GetFieldObject(reference_referent_offset_); |
| if (referent == NULL) { |
| // Referent was cleared by the user during marking. |
| continue; |
| } |
| bool is_marked = IsMarked(referent); |
| if (!is_marked && ((++counter) & 1)) { |
| // Referent is white and biased toward saving, mark it. |
| MarkObject(referent); |
| is_marked = true; |
| } |
| if (!is_marked) { |
| // Referent is white, queue it for clearing. |
| EnqueuePendingReference(ref, &clear); |
| } |
| } |
| *list = clear; |
| // Restart the mark with the newly black references added to the |
| // root set. |
| ProcessMarkStack(); |
| } |
| |
| // Unlink the reference list clearing references objects with white |
| // referents. Cleared references registered to a reference queue are |
| // scheduled for appending by the heap worker thread. |
| void MarkSweep::ClearWhiteReferences(Object** list) { |
| DCHECK(list != NULL); |
| size_t offset = reference_referent_offset_; |
| while (*list != NULL) { |
| Object *ref = DequeuePendingReference(list); |
| Object *referent = ref->GetFieldObject(offset); |
| if (referent != NULL && !IsMarked(referent)) { |
| // Referent is white, clear it. |
| ClearReference(ref); |
| if (IsEnqueuable(ref)) { |
| EnqueueReference(ref); |
| } |
| } |
| } |
| DCHECK(*list == NULL); |
| } |
| |
| // Enqueues finalizer references with white referents. White |
| // referents are blackened, moved to the zombie field, and the |
| // referent field is cleared. |
| void MarkSweep::EnqueueFinalizerReferences(Object** list) { |
| DCHECK(list != NULL); |
| size_t referent_offset = reference_referent_offset_; |
| size_t zombie_offset = finalizer_reference_zombie_offset_; |
| bool has_enqueued = false; |
| while (*list != NULL) { |
| Object* ref = DequeuePendingReference(list); |
| Object* referent = ref->GetFieldObject(referent_offset); |
| if (referent != NULL && !IsMarked(referent)) { |
| MarkObject(referent); |
| // If the referent is non-null the reference must queuable. |
| DCHECK(IsEnqueuable(ref)); |
| ref->SetFieldObject(zombie_offset, referent); |
| ClearReference(ref); |
| EnqueueReference(ref); |
| has_enqueued = true; |
| } |
| } |
| if (has_enqueued) { |
| ProcessMarkStack(); |
| } |
| DCHECK(*list == NULL); |
| } |
| |
| /* |
| * Process reference class instances and schedule finalizations. |
| */ |
| void MarkSweep::ProcessReferences(Object** soft_references, bool clear_soft, |
| Object** weak_references, |
| Object** finalizer_references, |
| Object** phantom_references) { |
| DCHECK(soft_references != NULL); |
| DCHECK(weak_references != NULL); |
| DCHECK(finalizer_references != NULL); |
| DCHECK(phantom_references != NULL); |
| |
| // Unless we are in the zygote or required to clear soft references |
| // with white references, preserve some white referents. |
| if (clear_soft) { |
| PreserveSomeSoftReferences(soft_references); |
| } |
| |
| // Clear all remaining soft and weak references with white |
| // referents. |
| ClearWhiteReferences(soft_references); |
| ClearWhiteReferences(weak_references); |
| |
| // Preserve all white objects with finalize methods and schedule |
| // them for finalization. |
| EnqueueFinalizerReferences(finalizer_references); |
| |
| // Clear all f-reachable soft and weak references with white |
| // referents. |
| ClearWhiteReferences(soft_references); |
| ClearWhiteReferences(weak_references); |
| |
| // Clear all phantom references with white referents. |
| ClearWhiteReferences(phantom_references); |
| |
| // At this point all reference lists should be empty. |
| DCHECK(*soft_references == NULL); |
| DCHECK(*weak_references == NULL); |
| DCHECK(*finalizer_references == NULL); |
| DCHECK(*phantom_references == NULL); |
| } |
| |
| // Pushes a list of cleared references out to the managed heap. |
| void MarkSweep::EnqueueClearedReferences(Object** cleared) { |
| DCHECK(cleared != NULL); |
| if (*cleared != NULL) { |
| Thread* self = Thread::Current(); |
| DCHECK(self != NULL); |
| // TODO: Method *meth = gDvm.methJavaLangRefReferenceQueueAdd; |
| // DCHECK(meth != NULL); |
| // JValue unused; |
| // Object *reference = *cleared; |
| // TODO: dvmCallMethod(self, meth, NULL, &unused, reference); |
| LOG(FATAL) << "Unimplemented"; |
| *cleared = NULL; |
| } |
| } |
| |
| MarkSweep::~MarkSweep() { |
| mark_bitmap_->Clear(); |
| } |
| |
| } // namespace art |