blob: 0fee24fd53e14a21bda11c9b48eb1ac8a2f34dea [file] [log] [blame]
/*
* Copyright (C) 2011 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_SRC_MARK_SWEEP_H_
#define ART_SRC_MARK_SWEEP_H_
#include "atomic_stack.h"
#include "macros.h"
#include "heap_bitmap.h"
#include "object.h"
#include "offsets.h"
namespace art {
class Barrier;
class CheckObjectVisitor;
class Class;
class Heap;
class MarkIfReachesAllocspaceVisitor;
class ModUnionClearCardVisitor;
class ModUnionVisitor;
class ModUnionTableBitmap;
class Object;
class TimingLogger;
class MarkStackChunk;
class MarkSweep {
public:
explicit MarkSweep(ObjectStack* mark_stack);
~MarkSweep();
// Initializes internal structures.
void Init();
// Find the default mark bitmap.
void FindDefaultMarkBitmap();
// Marks the root set at the start of a garbage collection.
void MarkRoots()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void MarkNonThreadRoots()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void MarkConcurrentRoots();
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void MarkRootsCheckpoint();
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Verify that image roots point to only marked objects within the alloc space.
void VerifyImageRoots() EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Builds a mark stack and recursively mark until it empties.
void RecursiveMark(bool partial, TimingLogger& timings)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
// Copies mark bits from live bitmap of ZygoteSpace to mark bitmap for partial GCs.
void CopyMarkBits(ContinuousSpace* space);
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void BindLiveToMarkBitmap(ContinuousSpace* space)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void UnBindBitmaps()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Builds a mark stack with objects on dirty cards and recursively mark until it empties.
void RecursiveMarkDirtyObjects(byte minimum_age = CardTable::kCardDirty)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
// Recursive mark objects on specified cards. Updates finger.
void RecursiveMarkCards(CardTable* card_table, const std::vector<byte*>& cards,
TimingLogger& timings)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);;
// Remarks the root set after completing the concurrent mark.
void ReMarkRoots()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
Heap* GetHeap() {
return heap_;
}
void ProcessReferences(bool clear_soft_references)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
ProcessReferences(&soft_reference_list_, clear_soft_references,
&weak_reference_list_,
&finalizer_reference_list_,
&phantom_reference_list_);
}
// Sweeps unmarked objects to complete the garbage collection.
void Sweep(TimingLogger& timings, bool partial, bool swap_bitmaps)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Sweeps unmarked objects to complete the garbage collection.
void SweepLargeObjects(bool swap_bitmaps)
EXCLUSIVE_LOCKS_REQUIRED(GlobalSynchronization::heap_bitmap_lock_);
// Sweep only pointers within an array. WARNING: Trashes objects.
void SweepArray(TimingLogger& logger, ObjectStack* allocation_stack_, bool swap_bitmaps)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
Object* GetClearedReferences() {
return cleared_reference_list_;
}
// Proxy for external access to ScanObject.
void ScanRoot(const Object* obj)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
// Blackens an object.
void ScanObject(const Object* obj)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
template <typename MarkVisitor>
void ScanObjectVisit(const Object* obj, const MarkVisitor& visitor)
NO_THREAD_SAFETY_ANALYSIS {
DCHECK(obj != NULL);
if (kIsDebugBuild && !IsMarked(obj)) {
heap_->DumpSpaces();
LOG(FATAL) << "Scanning unmarked object " << obj;
}
Class* klass = obj->GetClass();
DCHECK(klass != NULL);
if (klass == java_lang_Class_) {
DCHECK_EQ(klass->GetClass(), java_lang_Class_);
if (kCountScannedTypes) {
++class_count_;
}
VisitClassReferences(klass, obj, visitor);
} else if (klass->IsArrayClass()) {
if (kCountScannedTypes) {
++array_count_;
}
visitor(obj, klass, Object::ClassOffset(), false);
if (klass->IsObjectArrayClass()) {
VisitObjectArrayReferences(obj->AsObjectArray<Object>(), visitor);
}
} else {
if (kCountScannedTypes) {
++other_count_;
}
VisitOtherReferences(klass, obj, visitor);
if (UNLIKELY(klass->IsReferenceClass())) {
DelayReferenceReferent(const_cast<Object*>(obj));
}
}
}
void SetFinger(Object* new_finger) {
finger_ = new_finger;
}
void DisableFinger() {
SetFinger(reinterpret_cast<Object*>(~static_cast<uintptr_t>(0)));
}
size_t GetFreedBytes() const {
return freed_bytes_;
}
size_t GetFreedObjects() const {
return freed_objects_;
}
// Everything inside the immune range is marked.
void SetImmuneRange(Object* begin, Object* end) {
immune_begin_ = begin;
immune_end_ = end;
}
void SweepSystemWeaks()
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Only sweep the weaks which are inside of an allocation stack.
void SweepSystemWeaksArray(ObjectStack* allocations)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
static bool VerifyIsLiveCallback(const Object* obj, void* arg)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void VerifySystemWeaks()
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Verify that an object is live, either in a live bitmap or in the allocation stack.
void VerifyIsLive(const Object* obj)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
template <typename Visitor>
static void VisitObjectReferences(const Object* obj, const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
Locks::mutator_lock_) {
DCHECK(obj != NULL);
DCHECK(obj->GetClass() != NULL);
Class* klass = obj->GetClass();
DCHECK(klass != NULL);
if (klass == Class::GetJavaLangClass()) {
DCHECK_EQ(klass->GetClass(), Class::GetJavaLangClass());
VisitClassReferences(klass, obj, visitor);
} else {
if (klass->IsArrayClass()) {
visitor(obj, klass, Object::ClassOffset(), false);
if (klass->IsObjectArrayClass()) {
VisitObjectArrayReferences(obj->AsObjectArray<Object>(), visitor);
}
} else {
VisitOtherReferences(klass, obj, visitor);
}
}
}
static void MarkObjectCallback(const Object* root, void* arg)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
static void MarkRootParallelCallback(const Object* root, void* arg);
// Marks an object.
void MarkObject(const Object* obj)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
Barrier& GetBarrier();
private:
// Returns true if the object has its bit set in the mark bitmap.
bool IsMarked(const Object* object) const;
static bool IsMarkedCallback(const Object* object, void* arg)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
static bool IsMarkedArrayCallback(const Object* object, void* arg)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
static void ReMarkObjectVisitor(const Object* root, void* arg)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
static void VerifyImageRootVisitor(Object* root, void* arg)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
Locks::mutator_lock_);
void MarkObjectNonNull(const Object* obj, bool check_finger)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void MarkObjectNonNullParallel(const Object* obj, bool check_finger);
bool MarkLargeObject(const Object* obj)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Returns true if we need to add obj to a mark stack.
bool MarkObjectParallel(const Object* obj) NO_THREAD_SAFETY_ANALYSIS;
static void SweepCallback(size_t num_ptrs, Object** ptrs, void* arg)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Special sweep for zygote that just marks objects / dirties cards.
static void ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
void CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
void CheckObject(const Object* obj)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
// Verify the roots of the heap and print out information related to any invalid roots.
// Called in MarkObject, so may we may not hold the mutator lock.
void VerifyRoots()
NO_THREAD_SAFETY_ANALYSIS;
// Expand mark stack to 2x its current size. Thread safe.
void ExpandMarkStack();
static void VerifyRootCallback(const Object* root, void* arg, size_t vreg,
const StackVisitor *visitor);
void VerifyRoot(const Object* root, size_t vreg, const StackVisitor* visitor)
NO_THREAD_SAFETY_ANALYSIS;
template <typename Visitor>
static void VisitInstanceFieldsReferences(const Class* klass, const Object* obj,
const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
DCHECK(obj != NULL);
DCHECK(klass != NULL);
VisitFieldsReferences(obj, klass->GetReferenceInstanceOffsets(), false, visitor);
}
// Visit the header, static field references, and interface pointers of a class object.
template <typename Visitor>
static void VisitClassReferences(const Class* klass, const Object* obj,
const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
VisitInstanceFieldsReferences(klass, obj, visitor);
VisitStaticFieldsReferences(obj->AsClass(), visitor);
}
template <typename Visitor>
static void VisitStaticFieldsReferences(const Class* klass, const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
DCHECK(klass != NULL);
VisitFieldsReferences(klass, klass->GetReferenceStaticOffsets(), true, visitor);
}
template <typename Visitor>
static void VisitFieldsReferences(const Object* obj, uint32_t ref_offsets, bool is_static,
const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
if (LIKELY(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);
MemberOffset field_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
visitor(obj, ref, field_offset, is_static);
ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift);
}
} else {
// There is no reference offset bitmap. In the non-static case,
// walk up the class inheritance hierarchy and find reference
// offsets the hard way. In the static case, just consider this
// class.
for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
klass != NULL;
klass = is_static ? NULL : klass->GetSuperClass()) {
size_t num_reference_fields = (is_static
? klass->NumReferenceStaticFields()
: klass->NumReferenceInstanceFields());
for (size_t i = 0; i < num_reference_fields; ++i) {
Field* field = (is_static
? klass->GetStaticField(i)
: klass->GetInstanceField(i));
MemberOffset field_offset = field->GetOffset();
const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
visitor(obj, ref, field_offset, is_static);
}
}
}
}
// Visit all of the references in an object array.
template <typename Visitor>
static void VisitObjectArrayReferences(const ObjectArray<Object>* array,
const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
const int32_t length = array->GetLength();
for (int32_t i = 0; i < length; ++i) {
const Object* element = array->GetWithoutChecks(i);
const size_t width = sizeof(Object*);
MemberOffset offset = MemberOffset(i * width + Array::DataOffset(width).Int32Value());
visitor(array, element, offset, false);
}
}
// Visits the header and field references of a data object.
template <typename Visitor>
static void VisitOtherReferences(const Class* klass, const Object* obj,
const Visitor& visitor)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
return VisitInstanceFieldsReferences(klass, obj, visitor);
}
// Blackens objects grayed during a garbage collection.
void ScanGrayObjects(byte minimum_age)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
// Schedules an unmarked object for reference processing.
void DelayReferenceReferent(Object* reference)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
// Recursively blackens objects on the mark stack.
void ProcessMarkStack()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void ProcessMarkStackParallel()
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void EnqueueFinalizerReferences(Object** ref)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void PreserveSomeSoftReferences(Object** ref)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void ClearWhiteReferences(Object** list)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
void ProcessReferences(Object** soft_references, bool clear_soft_references,
Object** weak_references,
Object** finalizer_references,
Object** phantom_references)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
void SweepJniWeakGlobals(Heap::IsMarkedTester is_marked, void* arg)
SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
// Whether or not we count how many of each type of object were scanned.
static const bool kCountScannedTypes = false;
// Current space, we check this space first to avoid searching for the appropriate space for an object.
SpaceBitmap* current_mark_bitmap_;
// Cache java.lang.Class for optimization.
Class* java_lang_Class_;
ObjectStack* mark_stack_;
Heap* heap_;
Object* finger_;
// Immune range, every object inside the immune range is assumed to be marked.
Object* immune_begin_;
Object* immune_end_;
Object* soft_reference_list_;
Object* weak_reference_list_;
Object* finalizer_reference_list_;
Object* phantom_reference_list_;
Object* cleared_reference_list_;
AtomicInteger freed_bytes_;
AtomicInteger freed_objects_;
AtomicInteger class_count_;
AtomicInteger array_count_;
AtomicInteger other_count_;
AtomicInteger large_object_test_;
AtomicInteger large_object_mark_;
AtomicInteger classes_marked_;
AtomicInteger overhead_time_;
AtomicInteger work_chunks_created_;
AtomicInteger work_chunks_deleted_;
AtomicInteger reference_count_;
UniquePtr<Barrier> gc_barrier_;
Mutex large_object_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
Mutex mark_stack_expand_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table.
friend class CheckBitmapVisitor;
friend class CheckObjectVisitor;
friend class CheckReferenceVisitor;
friend class InternTableEntryIsUnmarked;
friend class MarkIfReachesAllocspaceVisitor;
friend class ModUnionCheckReferences;
friend class ModUnionClearCardVisitor;
friend class ModUnionReferenceVisitor;
friend class ModUnionVisitor;
friend class ModUnionTableBitmap;
friend class ModUnionTableReferenceCache;
friend class ModUnionScanImageRootVisitor;
friend class ScanBitmapVisitor;
friend class ScanImageRootVisitor;
friend class MarkStackChunk;
friend class FifoMarkStackChunk;
DISALLOW_COPY_AND_ASSIGN(MarkSweep);
};
} // namespace art
#endif // ART_SRC_MARK_SWEEP_H_