Add allocation and garbage collection infrastructure.
Change-Id: I4b04cdfdf18afb75a7b0df87b509e8156b4a932b
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
new file mode 100644
index 0000000..5ab9e3e
--- /dev/null
+++ b/src/mark_sweep.cc
@@ -0,0 +1,409 @@
+// 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