in runtime/class_linker.cc [5730:5954]
bool ClassLinker::LinkVirtualMethods(
Thread* self,
Handle<mirror::Class> klass,
/*out*/std::unordered_map<size_t, ClassLinker::MethodTranslation>* default_translations) {
const size_t num_virtual_methods = klass->NumVirtualMethods();
if (klass->IsInterface()) {
// No vtable.
if (!IsUint<16>(num_virtual_methods)) {
ThrowClassFormatError(klass.Get(), "Too many methods on interface: %zu", num_virtual_methods);
return false;
}
bool has_defaults = false;
// Assign each method an IMT index and set the default flag.
for (size_t i = 0; i < num_virtual_methods; ++i) {
ArtMethod* m = klass->GetVirtualMethodDuringLinking(i, image_pointer_size_);
m->SetMethodIndex(i);
if (!m->IsAbstract()) {
m->SetAccessFlags(m->GetAccessFlags() | kAccDefault);
has_defaults = true;
}
}
// Mark that we have default methods so that we won't need to scan the virtual_methods_ array
// during initialization. This is a performance optimization. We could simply traverse the
// virtual_methods_ array again during initialization.
if (has_defaults) {
klass->SetHasDefaultMethods();
}
return true;
} else if (klass->HasSuperClass()) {
const size_t super_vtable_length = klass->GetSuperClass()->GetVTableLength();
const size_t max_count = num_virtual_methods + super_vtable_length;
StackHandleScope<2> hs(self);
Handle<mirror::Class> super_class(hs.NewHandle(klass->GetSuperClass()));
MutableHandle<mirror::PointerArray> vtable;
if (super_class->ShouldHaveEmbeddedVTable()) {
vtable = hs.NewHandle(AllocPointerArray(self, max_count));
if (UNLIKELY(vtable.Get() == nullptr)) {
self->AssertPendingOOMException();
return false;
}
for (size_t i = 0; i < super_vtable_length; i++) {
vtable->SetElementPtrSize(
i, super_class->GetEmbeddedVTableEntry(i, image_pointer_size_), image_pointer_size_);
}
// We might need to change vtable if we have new virtual methods or new interfaces (since that
// might give us new default methods). If no new interfaces then we can skip the rest since
// the class cannot override any of the super-class's methods. This is required for
// correctness since without it we might not update overridden default method vtable entries
// correctly.
if (num_virtual_methods == 0 && super_class->GetIfTableCount() == klass->GetIfTableCount()) {
klass->SetVTable(vtable.Get());
return true;
}
} else {
DCHECK(super_class->IsAbstract() && !super_class->IsArrayClass());
auto* super_vtable = super_class->GetVTable();
CHECK(super_vtable != nullptr) << PrettyClass(super_class.Get());
// We might need to change vtable if we have new virtual methods or new interfaces (since that
// might give us new default methods). See comment above.
if (num_virtual_methods == 0 && super_class->GetIfTableCount() == klass->GetIfTableCount()) {
klass->SetVTable(super_vtable);
return true;
}
vtable = hs.NewHandle(down_cast<mirror::PointerArray*>(
super_vtable->CopyOf(self, max_count)));
if (UNLIKELY(vtable.Get() == nullptr)) {
self->AssertPendingOOMException();
return false;
}
}
// How the algorithm works:
// 1. Populate hash table by adding num_virtual_methods from klass. The values in the hash
// table are: invalid_index for unused slots, index super_vtable_length + i for a virtual
// method which has not been matched to a vtable method, and j if the virtual method at the
// index overrode the super virtual method at index j.
// 2. Loop through super virtual methods, if they overwrite, update hash table to j
// (j < super_vtable_length) to avoid redundant checks. (TODO maybe use this info for reducing
// the need for the initial vtable which we later shrink back down).
// 3. Add non overridden methods to the end of the vtable.
static constexpr size_t kMaxStackHash = 250;
// + 1 so that even if we only have new default methods we will still be able to use this hash
// table (i.e. it will never have 0 size).
const size_t hash_table_size = num_virtual_methods * 3 + 1;
uint32_t* hash_table_ptr;
std::unique_ptr<uint32_t[]> hash_heap_storage;
if (hash_table_size <= kMaxStackHash) {
hash_table_ptr = reinterpret_cast<uint32_t*>(
alloca(hash_table_size * sizeof(*hash_table_ptr)));
} else {
hash_heap_storage.reset(new uint32_t[hash_table_size]);
hash_table_ptr = hash_heap_storage.get();
}
LinkVirtualHashTable hash_table(klass, hash_table_size, hash_table_ptr, image_pointer_size_);
// Add virtual methods to the hash table.
for (size_t i = 0; i < num_virtual_methods; ++i) {
DCHECK(klass->GetVirtualMethodDuringLinking(
i, image_pointer_size_)->GetDeclaringClass() != nullptr);
hash_table.Add(i);
}
// Loop through each super vtable method and see if they are overridden by a method we added to
// the hash table.
for (size_t j = 0; j < super_vtable_length; ++j) {
// Search the hash table to see if we are overridden by any method.
ArtMethod* super_method = vtable->GetElementPtrSize<ArtMethod*>(j, image_pointer_size_);
MethodNameAndSignatureComparator super_method_name_comparator(
super_method->GetInterfaceMethodIfProxy(image_pointer_size_));
uint32_t hash_index = hash_table.FindAndRemove(&super_method_name_comparator);
if (hash_index != hash_table.GetNotFoundIndex()) {
ArtMethod* virtual_method = klass->GetVirtualMethodDuringLinking(
hash_index, image_pointer_size_);
if (klass->CanAccessMember(super_method->GetDeclaringClass(),
super_method->GetAccessFlags())) {
if (super_method->IsFinal()) {
ThrowLinkageError(klass.Get(), "Method %s overrides final method in class %s",
PrettyMethod(virtual_method).c_str(),
super_method->GetDeclaringClassDescriptor());
return false;
}
vtable->SetElementPtrSize(j, virtual_method, image_pointer_size_);
virtual_method->SetMethodIndex(j);
} else {
LOG(WARNING) << "Before Android 4.1, method " << PrettyMethod(virtual_method)
<< " would have incorrectly overridden the package-private method in "
<< PrettyDescriptor(super_method->GetDeclaringClassDescriptor());
}
} else if (super_method->IsOverridableByDefaultMethod()) {
// We didn't directly override this method but we might through default methods...
// Check for default method update.
ArtMethod* default_method = nullptr;
switch (FindDefaultMethodImplementation(self,
super_method,
klass,
/*out*/&default_method)) {
case DefaultMethodSearchResult::kDefaultConflict: {
// A conflict was found looking for default methods. Note this (assuming it wasn't
// pre-existing) in the translations map.
if (UNLIKELY(!super_method->IsDefaultConflicting())) {
// Don't generate another conflict method to reduce memory use as an optimization.
default_translations->insert(
{j, ClassLinker::MethodTranslation::CreateConflictingMethod()});
}
break;
}
case DefaultMethodSearchResult::kAbstractFound: {
// No conflict but method is abstract.
// We note that this vtable entry must be made abstract.
if (UNLIKELY(!super_method->IsAbstract())) {
default_translations->insert(
{j, ClassLinker::MethodTranslation::CreateAbstractMethod()});
}
break;
}
case DefaultMethodSearchResult::kDefaultFound: {
if (UNLIKELY(super_method->IsDefaultConflicting() ||
default_method->GetDeclaringClass() != super_method->GetDeclaringClass())) {
// Found a default method implementation that is new.
// TODO Refactor this add default methods to virtuals here and not in
// LinkInterfaceMethods maybe.
// The problem is default methods might override previously present
// default-method or miranda-method vtable entries from the superclass.
// Unfortunately we need these to be entries in this class's virtuals. We do not
// give these entries there until LinkInterfaceMethods so we pass this map around
// to let it know which vtable entries need to be updated.
// Make a note that vtable entry j must be updated, store what it needs to be updated
// to. We will allocate a virtual method slot in LinkInterfaceMethods and fix it up
// then.
default_translations->insert(
{j, ClassLinker::MethodTranslation::CreateTranslatedMethod(default_method)});
VLOG(class_linker) << "Method " << PrettyMethod(super_method)
<< " overridden by default " << PrettyMethod(default_method)
<< " in " << PrettyClass(klass.Get());
}
break;
}
}
}
}
size_t actual_count = super_vtable_length;
// Add the non-overridden methods at the end.
for (size_t i = 0; i < num_virtual_methods; ++i) {
ArtMethod* local_method = klass->GetVirtualMethodDuringLinking(i, image_pointer_size_);
size_t method_idx = local_method->GetMethodIndexDuringLinking();
if (method_idx < super_vtable_length &&
local_method == vtable->GetElementPtrSize<ArtMethod*>(method_idx, image_pointer_size_)) {
continue;
}
vtable->SetElementPtrSize(actual_count, local_method, image_pointer_size_);
local_method->SetMethodIndex(actual_count);
++actual_count;
}
if (!IsUint<16>(actual_count)) {
ThrowClassFormatError(klass.Get(), "Too many methods defined on class: %zd", actual_count);
return false;
}
// Shrink vtable if possible
CHECK_LE(actual_count, max_count);
if (actual_count < max_count) {
vtable.Assign(down_cast<mirror::PointerArray*>(vtable->CopyOf(self, actual_count)));
if (UNLIKELY(vtable.Get() == nullptr)) {
self->AssertPendingOOMException();
return false;
}
}
klass->SetVTable(vtable.Get());
} else {
CHECK_EQ(klass.Get(), GetClassRoot(kJavaLangObject));
if (!IsUint<16>(num_virtual_methods)) {
ThrowClassFormatError(klass.Get(), "Too many methods: %d",
static_cast<int>(num_virtual_methods));
return false;
}
auto* vtable = AllocPointerArray(self, num_virtual_methods);
if (UNLIKELY(vtable == nullptr)) {
self->AssertPendingOOMException();
return false;
}
for (size_t i = 0; i < num_virtual_methods; ++i) {
ArtMethod* virtual_method = klass->GetVirtualMethodDuringLinking(i, image_pointer_size_);
vtable->SetElementPtrSize(i, virtual_method, image_pointer_size_);
virtual_method->SetMethodIndex(i & 0xFFFF);
}
klass->SetVTable(vtable);
}
return true;
}