blob: a53d7e5b250fd877d34fc0198f9ec2a9f6b07479 [file] [log] [blame]
/*
* Copyright (C) 2016 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.
*/
#include "cha.h"
#include "art_method-inl.h"
#include "base/logging.h" // For VLOG
#include "jit/jit.h"
#include "jit/jit_code_cache.h"
#include "linear_alloc.h"
#include "runtime.h"
#include "scoped_thread_state_change-inl.h"
#include "stack.h"
#include "thread.h"
#include "thread_list.h"
#include "thread_pool.h"
namespace art {
void ClassHierarchyAnalysis::AddDependency(ArtMethod* method,
ArtMethod* dependent_method,
OatQuickMethodHeader* dependent_header) {
const auto it = cha_dependency_map_.insert(
decltype(cha_dependency_map_)::value_type(method, ListOfDependentPairs())).first;
it->second.push_back({dependent_method, dependent_header});
}
static const ClassHierarchyAnalysis::ListOfDependentPairs s_empty_vector;
const ClassHierarchyAnalysis::ListOfDependentPairs& ClassHierarchyAnalysis::GetDependents(
ArtMethod* method) {
auto it = cha_dependency_map_.find(method);
if (it != cha_dependency_map_.end()) {
return it->second;
}
return s_empty_vector;
}
void ClassHierarchyAnalysis::RemoveAllDependenciesFor(ArtMethod* method) {
cha_dependency_map_.erase(method);
}
void ClassHierarchyAnalysis::RemoveDependentsWithMethodHeaders(
const std::unordered_set<OatQuickMethodHeader*>& method_headers) {
// Iterate through all entries in the dependency map and remove any entry that
// contains one of those in method_headers.
for (auto map_it = cha_dependency_map_.begin(); map_it != cha_dependency_map_.end(); ) {
ListOfDependentPairs& dependents = map_it->second;
dependents.erase(
std::remove_if(
dependents.begin(),
dependents.end(),
[&method_headers](MethodAndMethodHeaderPair& dependent) {
return method_headers.find(dependent.second) != method_headers.end();
}),
dependents.end());
// Remove the map entry if there are no more dependents.
if (dependents.empty()) {
map_it = cha_dependency_map_.erase(map_it);
} else {
map_it++;
}
}
}
// This stack visitor walks the stack and for compiled code with certain method
// headers, sets the should_deoptimize flag on stack to 1.
// TODO: also set the register value to 1 when should_deoptimize is allocated in
// a register.
class CHAStackVisitor FINAL : public StackVisitor {
public:
CHAStackVisitor(Thread* thread_in,
Context* context,
const std::unordered_set<OatQuickMethodHeader*>& method_headers)
: StackVisitor(thread_in, context, StackVisitor::StackWalkKind::kSkipInlinedFrames),
method_headers_(method_headers) {
}
bool VisitFrame() OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
ArtMethod* method = GetMethod();
// Avoid types of methods that do not have an oat quick method header.
if (method == nullptr ||
method->IsRuntimeMethod() ||
method->IsNative() ||
method->IsProxyMethod()) {
return true;
}
if (GetCurrentQuickFrame() == nullptr) {
// Not compiled code.
return true;
}
// Method may have multiple versions of compiled code. Check
// the method header to see if it has should_deoptimize flag.
const OatQuickMethodHeader* method_header = GetCurrentOatQuickMethodHeader();
DCHECK(method_header != nullptr);
if (!method_header->HasShouldDeoptimizeFlag()) {
// This compiled version doesn't have should_deoptimize flag. Skip.
return true;
}
auto it = std::find(method_headers_.begin(), method_headers_.end(), method_header);
if (it == method_headers_.end()) {
// Not in the list of method headers that should be deoptimized.
return true;
}
// The compiled code on stack is not valid anymore. Need to deoptimize.
SetShouldDeoptimizeFlag();
return true;
}
private:
void SetShouldDeoptimizeFlag() REQUIRES_SHARED(Locks::mutator_lock_) {
QuickMethodFrameInfo frame_info = GetCurrentQuickFrameInfo();
size_t frame_size = frame_info.FrameSizeInBytes();
uint8_t* sp = reinterpret_cast<uint8_t*>(GetCurrentQuickFrame());
size_t core_spill_size = POPCOUNT(frame_info.CoreSpillMask()) *
GetBytesPerGprSpillLocation(kRuntimeISA);
size_t fpu_spill_size = POPCOUNT(frame_info.FpSpillMask()) *
GetBytesPerFprSpillLocation(kRuntimeISA);
size_t offset = frame_size - core_spill_size - fpu_spill_size - kShouldDeoptimizeFlagSize;
uint8_t* should_deoptimize_addr = sp + offset;
// Set deoptimization flag to 1.
DCHECK(*should_deoptimize_addr == 0 || *should_deoptimize_addr == 1);
*should_deoptimize_addr = 1;
}
// Set of method headers for compiled code that should be deoptimized.
const std::unordered_set<OatQuickMethodHeader*>& method_headers_;
DISALLOW_COPY_AND_ASSIGN(CHAStackVisitor);
};
class CHACheckpoint FINAL : public Closure {
public:
explicit CHACheckpoint(const std::unordered_set<OatQuickMethodHeader*>& method_headers)
: barrier_(0),
method_headers_(method_headers) {}
void Run(Thread* thread) OVERRIDE {
// Note thread and self may not be equal if thread was already suspended at
// the point of the request.
Thread* self = Thread::Current();
ScopedObjectAccess soa(self);
CHAStackVisitor visitor(thread, nullptr, method_headers_);
visitor.WalkStack();
barrier_.Pass(self);
}
void WaitForThreadsToRunThroughCheckpoint(size_t threads_running_checkpoint) {
Thread* self = Thread::Current();
ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun);
barrier_.Increment(self, threads_running_checkpoint);
}
private:
// The barrier to be passed through and for the requestor to wait upon.
Barrier barrier_;
// List of method headers for invalidated compiled code.
const std::unordered_set<OatQuickMethodHeader*>& method_headers_;
DISALLOW_COPY_AND_ASSIGN(CHACheckpoint);
};
static void VerifyNonSingleImplementation(mirror::Class* verify_class,
uint16_t verify_index,
ArtMethod* excluded_method)
REQUIRES_SHARED(Locks::mutator_lock_) {
if (!kIsDebugBuild) {
return;
}
// Grab cha_lock_ to make sure all single-implementation updates are seen.
MutexLock cha_mu(Thread::Current(), *Locks::cha_lock_);
PointerSize image_pointer_size =
Runtime::Current()->GetClassLinker()->GetImagePointerSize();
mirror::Class* input_verify_class = verify_class;
while (verify_class != nullptr) {
if (verify_index >= verify_class->GetVTableLength()) {
return;
}
ArtMethod* verify_method = verify_class->GetVTableEntry(verify_index, image_pointer_size);
if (verify_method != excluded_method) {
auto construct_parent_chain = [](mirror::Class* failed, mirror::Class* in)
REQUIRES_SHARED(Locks::mutator_lock_) {
std::string tmp = in->PrettyClass();
while (in != failed) {
in = in->GetSuperClass();
tmp = tmp + "->" + in->PrettyClass();
}
return tmp;
};
DCHECK(!verify_method->HasSingleImplementation())
<< "class: " << verify_class->PrettyClass()
<< " verify_method: " << verify_method->PrettyMethod(true)
<< " (" << construct_parent_chain(verify_class, input_verify_class) << ")"
<< " excluded_method: " << ArtMethod::PrettyMethod(excluded_method);
if (verify_method->IsAbstract()) {
DCHECK(verify_method->GetSingleImplementation(image_pointer_size) == nullptr);
}
}
verify_class = verify_class->GetSuperClass();
}
}
void ClassHierarchyAnalysis::CheckVirtualMethodSingleImplementationInfo(
Handle<mirror::Class> klass,
ArtMethod* virtual_method,
ArtMethod* method_in_super,
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
PointerSize pointer_size) {
// TODO: if klass is not instantiable, virtual_method isn't invocable yet so
// even if it overrides, it doesn't invalidate single-implementation
// assumption.
DCHECK((virtual_method != method_in_super) || virtual_method->IsAbstract());
DCHECK(method_in_super->GetDeclaringClass()->IsResolved()) << "class isn't resolved";
// If virtual_method doesn't come from a default interface method, it should
// be supplied by klass.
DCHECK(virtual_method == method_in_super ||
virtual_method->IsCopied() ||
virtual_method->GetDeclaringClass() == klass.Get());
// To make updating single-implementation flags simple, we always maintain the following
// invariant:
// Say all virtual methods in the same vtable slot, starting from the bottom child class
// to super classes, is a sequence of unique methods m3, m2, m1, ... (after removing duplicate
// methods for inherited methods).
// For example for the following class hierarchy,
// class A { void m() { ... } }
// class B extends A { void m() { ... } }
// class C extends B {}
// class D extends C { void m() { ... } }
// the sequence is D.m(), B.m(), A.m().
// The single-implementation status for that sequence of methods begin with one or two true's,
// then become all falses. The only case where two true's are possible is for one abstract
// method m and one non-abstract method mImpl that overrides method m.
// With the invariant, when linking in a new class, we only need to at most update one or
// two methods in the sequence for their single-implementation status, in order to maintain
// the invariant.
if (!method_in_super->HasSingleImplementation()) {
// method_in_super already has multiple implementations. All methods in the
// same vtable slots in its super classes should have
// non-single-implementation already.
VerifyNonSingleImplementation(klass->GetSuperClass()->GetSuperClass(),
method_in_super->GetMethodIndex(),
nullptr /* excluded_method */);
return;
}
uint16_t method_index = method_in_super->GetMethodIndex();
if (method_in_super->IsAbstract()) {
// An abstract method should have made all methods in the same vtable
// slot above it in the class hierarchy having non-single-implementation.
VerifyNonSingleImplementation(klass->GetSuperClass()->GetSuperClass(),
method_index,
method_in_super);
if (virtual_method->IsAbstract()) {
// SUPER: abstract, VIRTUAL: abstract.
if (method_in_super == virtual_method) {
DCHECK(klass->IsInstantiable());
// An instantiable subclass hasn't provided a concrete implementation of
// the abstract method. Invoking method_in_super may throw AbstractMethodError.
// This is an uncommon case, so we simply treat method_in_super as not
// having single-implementation.
invalidated_single_impl_methods.insert(method_in_super);
return;
} else {
// One abstract method overrides another abstract method. This is an uncommon
// case. We simply treat method_in_super as not having single-implementation.
invalidated_single_impl_methods.insert(method_in_super);
return;
}
} else {
// SUPER: abstract, VIRTUAL: non-abstract.
// A non-abstract method overrides an abstract method.
if (method_in_super->GetSingleImplementation(pointer_size) == nullptr) {
// Abstract method_in_super has no implementation yet.
// We need to grab cha_lock_ since there may be multiple class linking
// going on that can check/modify the single-implementation flag/method
// of method_in_super.
MutexLock cha_mu(Thread::Current(), *Locks::cha_lock_);
if (!method_in_super->HasSingleImplementation()) {
return;
}
if (method_in_super->GetSingleImplementation(pointer_size) == nullptr) {
// virtual_method becomes the first implementation for method_in_super.
method_in_super->SetSingleImplementation(virtual_method, pointer_size);
// Keep method_in_super's single-implementation status.
return;
}
// Fall through to invalidate method_in_super's single-implementation status.
}
// Abstract method_in_super already got one implementation.
// Invalidate method_in_super's single-implementation status.
invalidated_single_impl_methods.insert(method_in_super);
return;
}
} else {
if (virtual_method->IsAbstract()) {
// SUPER: non-abstract, VIRTUAL: abstract.
// An abstract method overrides a non-abstract method. This is an uncommon
// case, we simply treat both methods as not having single-implementation.
invalidated_single_impl_methods.insert(virtual_method);
// Fall-through to handle invalidating method_in_super of its
// single-implementation status.
}
// SUPER: non-abstract, VIRTUAL: non-abstract/abstract(fall-through from previous if).
// Invalidate method_in_super's single-implementation status.
invalidated_single_impl_methods.insert(method_in_super);
// method_in_super might be the single-implementation of another abstract method,
// which should be also invalidated of its single-implementation status.
mirror::Class* super_super = klass->GetSuperClass()->GetSuperClass();
while (super_super != nullptr &&
method_index < super_super->GetVTableLength()) {
ArtMethod* method_in_super_super = super_super->GetVTableEntry(method_index, pointer_size);
if (method_in_super_super != method_in_super) {
if (method_in_super_super->IsAbstract()) {
if (method_in_super_super->HasSingleImplementation()) {
// Invalidate method_in_super's single-implementation status.
invalidated_single_impl_methods.insert(method_in_super_super);
// No need to further traverse up the class hierarchy since if there
// are cases that one abstract method overrides another method, we
// should have made that method having non-single-implementation already.
} else {
// method_in_super_super is already non-single-implementation.
// No need to further traverse up the class hierarchy.
}
} else {
DCHECK(!method_in_super_super->HasSingleImplementation());
// No need to further traverse up the class hierarchy since two non-abstract
// methods (method_in_super and method_in_super_super) should have set all
// other methods (abstract or not) in the vtable slot to be non-single-implementation.
}
VerifyNonSingleImplementation(super_super->GetSuperClass(),
method_index,
method_in_super_super);
// No need to go any further.
return;
} else {
super_super = super_super->GetSuperClass();
}
}
}
}
void ClassHierarchyAnalysis::CheckInterfaceMethodSingleImplementationInfo(
Handle<mirror::Class> klass,
ArtMethod* interface_method,
ArtMethod* implementation_method,
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
PointerSize pointer_size) {
DCHECK(klass->IsInstantiable());
DCHECK(interface_method->IsAbstract() || interface_method->IsDefault());
if (!interface_method->HasSingleImplementation()) {
return;
}
if (implementation_method->IsAbstract()) {
// An instantiable class doesn't supply an implementation for
// interface_method. Invoking the interface method on the class will throw
// AbstractMethodError. This is an uncommon case, so we simply treat
// interface_method as not having single-implementation.
invalidated_single_impl_methods.insert(interface_method);
return;
}
// We need to grab cha_lock_ since there may be multiple class linking going
// on that can check/modify the single-implementation flag/method of
// interface_method.
MutexLock cha_mu(Thread::Current(), *Locks::cha_lock_);
// Do this check again after we grab cha_lock_.
if (!interface_method->HasSingleImplementation()) {
return;
}
ArtMethod* single_impl = interface_method->GetSingleImplementation(pointer_size);
if (single_impl == nullptr) {
// implementation_method becomes the first implementation for
// interface_method.
interface_method->SetSingleImplementation(implementation_method, pointer_size);
// Keep interface_method's single-implementation status.
return;
}
DCHECK(!single_impl->IsAbstract());
if (single_impl->GetDeclaringClass() == implementation_method->GetDeclaringClass()) {
// Same implementation. Since implementation_method may be a copy of a default
// method, we need to check the declaring class for equality.
return;
}
// Another implementation for interface_method.
invalidated_single_impl_methods.insert(interface_method);
}
void ClassHierarchyAnalysis::InitSingleImplementationFlag(Handle<mirror::Class> klass,
ArtMethod* method,
PointerSize pointer_size) {
DCHECK(method->IsCopied() || method->GetDeclaringClass() == klass.Get());
if (klass->IsFinal() || method->IsFinal()) {
// Final classes or methods do not need CHA for devirtualization.
// This frees up modifier bits for intrinsics which currently are only
// used for static methods or methods of final classes.
return;
}
if (method->IsAbstract()) {
// single-implementation of abstract method shares the same field
// that's used for JNI function of native method. It's fine since a method
// cannot be both abstract and native.
DCHECK(!method->IsNative()) << "Abstract method cannot be native";
if (method->GetDeclaringClass()->IsInstantiable()) {
// Rare case, but we do accept it (such as 800-smali/smali/b_26143249.smali).
// Do not attempt to devirtualize it.
method->SetHasSingleImplementation(false);
DCHECK(method->GetSingleImplementation(pointer_size) == nullptr);
} else {
// Abstract method starts with single-implementation flag set and null
// implementation method.
method->SetHasSingleImplementation(true);
DCHECK(method->GetSingleImplementation(pointer_size) == nullptr);
}
} else {
method->SetHasSingleImplementation(true);
// Single implementation of non-abstract method is itself.
DCHECK_EQ(method->GetSingleImplementation(pointer_size), method);
}
}
void ClassHierarchyAnalysis::UpdateAfterLoadingOf(Handle<mirror::Class> klass) {
PointerSize image_pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
if (klass->IsInterface()) {
for (ArtMethod& method : klass->GetDeclaredVirtualMethods(image_pointer_size)) {
DCHECK(method.IsAbstract() || method.IsDefault());
InitSingleImplementationFlag(klass, &method, image_pointer_size);
}
return;
}
mirror::Class* super_class = klass->GetSuperClass();
if (super_class == nullptr) {
return;
}
// Keeps track of all methods whose single-implementation assumption
// is invalidated by linking `klass`.
std::unordered_set<ArtMethod*> invalidated_single_impl_methods;
// Do an entry-by-entry comparison of vtable contents with super's vtable.
for (int32_t i = 0; i < super_class->GetVTableLength(); ++i) {
ArtMethod* method = klass->GetVTableEntry(i, image_pointer_size);
ArtMethod* method_in_super = super_class->GetVTableEntry(i, image_pointer_size);
if (method == method_in_super) {
// vtable slot entry is inherited from super class.
if (method->IsAbstract() && klass->IsInstantiable()) {
// An instantiable class that inherits an abstract method is treated as
// supplying an implementation that throws AbstractMethodError.
CheckVirtualMethodSingleImplementationInfo(klass,
method,
method_in_super,
invalidated_single_impl_methods,
image_pointer_size);
}
continue;
}
InitSingleImplementationFlag(klass, method, image_pointer_size);
CheckVirtualMethodSingleImplementationInfo(klass,
method,
method_in_super,
invalidated_single_impl_methods,
image_pointer_size);
}
// For new virtual methods that don't override.
for (int32_t i = super_class->GetVTableLength(); i < klass->GetVTableLength(); ++i) {
ArtMethod* method = klass->GetVTableEntry(i, image_pointer_size);
InitSingleImplementationFlag(klass, method, image_pointer_size);
}
if (klass->IsInstantiable()) {
auto* iftable = klass->GetIfTable();
const size_t ifcount = klass->GetIfTableCount();
for (size_t i = 0; i < ifcount; ++i) {
mirror::Class* interface = iftable->GetInterface(i);
for (size_t j = 0, count = iftable->GetMethodArrayCount(i); j < count; ++j) {
ArtMethod* interface_method = interface->GetVirtualMethod(j, image_pointer_size);
mirror::PointerArray* method_array = iftable->GetMethodArray(i);
ArtMethod* implementation_method =
method_array->GetElementPtrSize<ArtMethod*>(j, image_pointer_size);
DCHECK(implementation_method != nullptr) << klass->PrettyClass();
CheckInterfaceMethodSingleImplementationInfo(klass,
interface_method,
implementation_method,
invalidated_single_impl_methods,
image_pointer_size);
}
}
}
InvalidateSingleImplementationMethods(invalidated_single_impl_methods);
}
void ClassHierarchyAnalysis::InvalidateSingleImplementationMethods(
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods) {
if (!invalidated_single_impl_methods.empty()) {
Runtime* const runtime = Runtime::Current();
Thread *self = Thread::Current();
// Method headers for compiled code to be invalidated.
std::unordered_set<OatQuickMethodHeader*> dependent_method_headers;
PointerSize image_pointer_size =
Runtime::Current()->GetClassLinker()->GetImagePointerSize();
{
// We do this under cha_lock_. Committing code also grabs this lock to
// make sure the code is only committed when all single-implementation
// assumptions are still true.
MutexLock cha_mu(self, *Locks::cha_lock_);
// Invalidate compiled methods that assume some virtual calls have only
// single implementations.
for (ArtMethod* invalidated : invalidated_single_impl_methods) {
if (!invalidated->HasSingleImplementation()) {
// It might have been invalidated already when other class linking is
// going on.
continue;
}
invalidated->SetHasSingleImplementation(false);
if (invalidated->IsAbstract()) {
// Clear the single implementation method.
invalidated->SetSingleImplementation(nullptr, image_pointer_size);
}
if (runtime->IsAotCompiler()) {
// No need to invalidate any compiled code as the AotCompiler doesn't
// run any code.
continue;
}
// Invalidate all dependents.
for (const auto& dependent : GetDependents(invalidated)) {
ArtMethod* method = dependent.first;;
OatQuickMethodHeader* method_header = dependent.second;
VLOG(class_linker) << "CHA invalidated compiled code for " << method->PrettyMethod();
DCHECK(runtime->UseJitCompilation());
runtime->GetJit()->GetCodeCache()->InvalidateCompiledCodeFor(
method, method_header);
dependent_method_headers.insert(method_header);
}
RemoveAllDependenciesFor(invalidated);
}
}
if (dependent_method_headers.empty()) {
return;
}
// Deoptimze compiled code on stack that should have been invalidated.
CHACheckpoint checkpoint(dependent_method_headers);
size_t threads_running_checkpoint = runtime->GetThreadList()->RunCheckpoint(&checkpoint);
if (threads_running_checkpoint != 0) {
checkpoint.WaitForThreadsToRunThroughCheckpoint(threads_running_checkpoint);
}
}
}
void ClassHierarchyAnalysis::RemoveDependenciesForLinearAlloc(const LinearAlloc* linear_alloc) {
MutexLock mu(Thread::Current(), *Locks::cha_lock_);
for (auto it = cha_dependency_map_.begin(); it != cha_dependency_map_.end(); ) {
// Use unsafe to avoid locking since the allocator is going to be deleted.
if (linear_alloc->ContainsUnsafe(it->first)) {
// About to delete the ArtMethod, erase the entry from the map.
it = cha_dependency_map_.erase(it);
} else {
++it;
}
}
}
} // namespace art