Add support for eagerly calculating conflict tables
Will be used to put them in the image by having the compiler eagerly
calculate them.
Enabled for debug builds (non compiler). Support for having conflict
tables written in the image will come in the next CL.
(cherry picked from commit 49b5cede15d69930a8c156a3aea240164ca7af80)
Bug: 27906566
Change-Id: I03d1671a4b49317aaab5a741bbeaed7957cd6229
diff --git a/runtime/art_method.h b/runtime/art_method.h
index fe88238..d65dbd5 100644
--- a/runtime/art_method.h
+++ b/runtime/art_method.h
@@ -68,6 +68,29 @@
entries_[index + 1].implementation_method = nullptr;
}
+ // num_entries excludes the header.
+ explicit ImtConflictTable(size_t num_entries) {
+ entries_[num_entries].interface_method = nullptr;
+ entries_[num_entries].implementation_method = nullptr;
+ }
+
+ // Set an entry at an index.
+ void SetInterfaceMethod(size_t index, ArtMethod* method) {
+ entries_[index].interface_method = method;
+ }
+
+ void SetImplementationMethod(size_t index, ArtMethod* method) {
+ entries_[index].implementation_method = method;
+ }
+
+ ArtMethod* GetInterfaceMethod(size_t index) const {
+ return entries_[index].interface_method;
+ }
+
+ ArtMethod* GetImplementationMethod(size_t index) const {
+ return entries_[index].implementation_method;
+ }
+
// Lookup the implementation ArtMethod associated to `interface_method`. Return null
// if not found.
ArtMethod* Lookup(ArtMethod* interface_method) const {
@@ -82,16 +105,19 @@
return nullptr;
}
- // Compute the size in bytes taken by this table.
- size_t ComputeSize() const {
+ // Compute the number of entries in this table.
+ size_t NumEntries() const {
uint32_t table_index = 0;
- size_t total_size = 0;
- while ((entries_[table_index].interface_method) != nullptr) {
- total_size += sizeof(Entry);
+ while (entries_[table_index].interface_method != nullptr) {
table_index++;
}
+ return table_index;
+ }
+
+ // Compute the size in bytes taken by this table.
+ size_t ComputeSize() const {
// Add the end marker.
- return total_size + sizeof(Entry);
+ return ComputeSize(NumEntries());
}
// Compute the size in bytes needed for copying the given `table` and add
@@ -100,6 +126,11 @@
return table->ComputeSize() + sizeof(Entry);
}
+ // Compute size with a fixed number of entries.
+ static size_t ComputeSize(size_t num_entries) {
+ return (num_entries + 1) * sizeof(Entry); // Add one for null terminator.
+ }
+
struct Entry {
ArtMethod* interface_method;
ArtMethod* implementation_method;
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 0b6aad0..8fa78d1 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -5971,16 +5971,47 @@
}
}
-// Sets imt_ref appropriately for LinkInterfaceMethods.
-// If there is no method in the imt location of imt_ref it will store the given method there.
-// Otherwise it will set the conflict method which will figure out which method to use during
-// runtime.
-static void SetIMTRef(ArtMethod* unimplemented_method,
- ArtMethod* imt_conflict_method,
- size_t image_pointer_size,
- ArtMethod* current_method,
- /*out*/ArtMethod** imt_ref)
- SHARED_REQUIRES(Locks::mutator_lock_) {
+ArtMethod* ClassLinker::AddMethodToConflictTable(mirror::Class* klass,
+ ArtMethod* conflict_method,
+ ArtMethod* interface_method,
+ ArtMethod* method,
+ bool force_new_conflict_method) {
+ ImtConflictTable* current_table = conflict_method->GetImtConflictTable(sizeof(void*));
+ Runtime* const runtime = Runtime::Current();
+ LinearAlloc* linear_alloc = GetAllocatorForClassLoader(klass->GetClassLoader());
+ bool new_entry = conflict_method == runtime->GetImtConflictMethod() || force_new_conflict_method;
+
+ // Create a new entry if the existing one is the shared conflict method.
+ ArtMethod* new_conflict_method = new_entry
+ ? runtime->CreateImtConflictMethod(linear_alloc)
+ : conflict_method;
+
+ // Allocate a new table. Note that we will leak this table at the next conflict,
+ // but that's a tradeoff compared to making the table fixed size.
+ void* data = linear_alloc->Alloc(
+ Thread::Current(), ImtConflictTable::ComputeSizeWithOneMoreEntry(current_table));
+ if (data == nullptr) {
+ LOG(ERROR) << "Failed to allocate conflict table";
+ return conflict_method;
+ }
+ ImtConflictTable* new_table = new (data) ImtConflictTable(current_table,
+ interface_method,
+ method);
+
+ // Do a fence to ensure threads see the data in the table before it is assigned
+ // to the conflict method.
+ // Note that there is a race in the presence of multiple threads and we may leak
+ // memory from the LinearAlloc, but that's a tradeoff compared to using
+ // atomic operations.
+ QuasiAtomic::ThreadFenceRelease();
+ new_conflict_method->SetImtConflictTable(new_table);
+ return new_conflict_method;
+}
+
+void ClassLinker::SetIMTRef(ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ ArtMethod* current_method,
+ /*out*/ArtMethod** imt_ref) {
// Place method in imt if entry is empty, place conflict otherwise.
if (*imt_ref == unimplemented_method) {
*imt_ref = current_method;
@@ -5990,9 +6021,9 @@
// Note that we have checked IsRuntimeMethod, as there may be multiple different
// conflict methods.
MethodNameAndSignatureComparator imt_comparator(
- (*imt_ref)->GetInterfaceMethodIfProxy(image_pointer_size));
+ (*imt_ref)->GetInterfaceMethodIfProxy(image_pointer_size_));
if (imt_comparator.HasSameNameAndSignature(
- current_method->GetInterfaceMethodIfProxy(image_pointer_size))) {
+ current_method->GetInterfaceMethodIfProxy(image_pointer_size_))) {
*imt_ref = current_method;
} else {
*imt_ref = imt_conflict_method;
@@ -6005,6 +6036,121 @@
}
}
+static inline uint32_t GetIMTIndex(ArtMethod* interface_method)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
+ return interface_method->GetDexMethodIndex() % mirror::Class::kImtSize;
+}
+
+void ClassLinker::ConstructIMTFromIfTable(mirror::IfTable* if_table,
+ ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ mirror::Class* klass,
+ bool create_conflict_tables,
+ bool ignore_copied_methods,
+ ArtMethod** out_imt) {
+ uint32_t conflict_counts[mirror::Class::kImtSize] = {};
+ for (size_t i = 0, length = if_table->Count(); i < length; ++i) {
+ mirror::Class* interface = if_table->GetInterface(i);
+ const size_t num_virtuals = interface->NumVirtualMethods();
+ const size_t method_array_count = if_table->GetMethodArrayCount(i);
+ // Virtual methods can be larger than the if table methods if there are default methods.
+ DCHECK_GE(num_virtuals, method_array_count);
+ if (kIsDebugBuild) {
+ if (klass->IsInterface()) {
+ DCHECK_EQ(method_array_count, 0u);
+ } else {
+ DCHECK_EQ(interface->NumDeclaredVirtualMethods(), method_array_count);
+ }
+ }
+ if (method_array_count == 0) {
+ continue;
+ }
+ auto* method_array = if_table->GetMethodArray(i);
+ for (size_t j = 0; j < method_array_count; ++j) {
+ ArtMethod* implementation_method =
+ method_array->GetElementPtrSize<ArtMethod*>(j, image_pointer_size_);
+ if (ignore_copied_methods && implementation_method->IsCopied()) {
+ continue;
+ }
+ DCHECK(implementation_method != nullptr);
+ // Miranda methods cannot be used to implement an interface method, but they are safe to put
+ // in the IMT since their entrypoint is the interface trampoline. If we put any copied methods
+ // or interface methods in the IMT here they will not create extra conflicts since we compare
+ // names and signatures in SetIMTRef.
+ ArtMethod* interface_method = interface->GetVirtualMethod(j, image_pointer_size_);
+ const uint32_t imt_index = GetIMTIndex(interface_method);
+
+ // There is only any conflicts if all of the interface methods for an IMT slot don't have
+ // the same implementation method, keep track of this to avoid creating a conflict table in
+ // this case.
+
+ // Conflict table size for each IMT slot.
+ ++conflict_counts[imt_index];
+
+ SetIMTRef(unimplemented_method,
+ imt_conflict_method,
+ implementation_method,
+ /*out*/&out_imt[imt_index]);
+ }
+ }
+
+ if (create_conflict_tables) {
+ // Create the conflict tables.
+ LinearAlloc* linear_alloc = GetAllocatorForClassLoader(klass->GetClassLoader());
+ for (size_t i = 0; i < mirror::Class::kImtSize; ++i) {
+ size_t conflicts = conflict_counts[i];
+ if (conflicts > 1) {
+ void* data = linear_alloc->Alloc(Thread::Current(),
+ ImtConflictTable::ComputeSize(conflicts));
+ if (data != nullptr) {
+ ImtConflictTable* new_table = new (data) ImtConflictTable(conflicts);
+ ArtMethod* new_conflict_method = Runtime::Current()->CreateImtConflictMethod(linear_alloc);
+ new_conflict_method->SetImtConflictTable(new_table);
+ out_imt[i] = new_conflict_method;
+ } else {
+ LOG(ERROR) << "Failed to allocate conflict table";
+ out_imt[i] = imt_conflict_method;
+ }
+ } else {
+ DCHECK_NE(out_imt[i], imt_conflict_method);
+ }
+ }
+
+ // No imt in the super class, need to reconstruct from the iftable.
+ for (size_t i = 0, length = if_table->Count(); i < length; ++i) {
+ mirror::Class* interface = if_table->GetInterface(i);
+ const size_t method_array_count = if_table->GetMethodArrayCount(i);
+ // Virtual methods can be larger than the if table methods if there are default methods.
+ if (method_array_count == 0) {
+ continue;
+ }
+ auto* method_array = if_table->GetMethodArray(i);
+ for (size_t j = 0; j < method_array_count; ++j) {
+ ArtMethod* implementation_method =
+ method_array->GetElementPtrSize<ArtMethod*>(j, image_pointer_size_);
+ if (ignore_copied_methods && implementation_method->IsCopied()) {
+ continue;
+ }
+ DCHECK(implementation_method != nullptr);
+ ArtMethod* interface_method = interface->GetVirtualMethod(j, image_pointer_size_);
+ const uint32_t imt_index = GetIMTIndex(interface_method);
+ if (conflict_counts[imt_index] <= 1) {
+ continue; // Only care about the conflicts.
+ }
+ DCHECK_NE(out_imt[imt_index], unimplemented_method) << PrettyMethod(out_imt[imt_index]);
+ DCHECK_NE(out_imt[imt_index], imt_conflict_method) << PrettyMethod(out_imt[imt_index]);
+ DCHECK(out_imt[imt_index]->IsRuntimeMethod()) << PrettyMethod(out_imt[imt_index]);
+ ImtConflictTable* table = out_imt[imt_index]->GetImtConflictTable(image_pointer_size_);
+ // Add to the end of the conflict table.
+ const size_t current_count = table->NumEntries();
+ CHECK_LT(current_count, conflict_counts[imt_index]);
+ table->SetInterfaceMethod(current_count, interface_method);
+ table->SetImplementationMethod(current_count, implementation_method);
+ }
+ }
+ }
+}
+
// Simple helper function that checks that no subtypes of 'val' are contained within the 'classes'
// set.
static bool NotSubinterfaceOfAny(const std::unordered_set<mirror::Class*>& classes,
@@ -6240,48 +6386,28 @@
}
}
-static void FillImtFromSuperClass(Handle<mirror::Class> klass,
- Handle<mirror::IfTable> iftable,
- ArtMethod* unimplemented_method,
- ArtMethod* imt_conflict_method,
- ArtMethod** out_imt,
- size_t pointer_size) SHARED_REQUIRES(Locks::mutator_lock_) {
+void ClassLinker::FillImtFromSuperClass(Handle<mirror::Class> klass,
+ ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ ArtMethod** out_imt) {
DCHECK(klass->HasSuperClass());
mirror::Class* super_class = klass->GetSuperClass();
if (super_class->ShouldHaveEmbeddedImtAndVTable()) {
for (size_t i = 0; i < mirror::Class::kImtSize; ++i) {
- out_imt[i] = super_class->GetEmbeddedImTableEntry(i, pointer_size);
+ out_imt[i] = super_class->GetEmbeddedImTableEntry(i, image_pointer_size_);
}
} else {
// No imt in the super class, need to reconstruct from the iftable.
mirror::IfTable* if_table = super_class->GetIfTable();
- const size_t length = super_class->GetIfTableCount();
- for (size_t i = 0; i < length; ++i) {
- mirror::Class* interface = iftable->GetInterface(i);
- const size_t num_virtuals = interface->NumDeclaredVirtualMethods();
- const size_t method_array_count = if_table->GetMethodArrayCount(i);
- DCHECK_EQ(num_virtuals, method_array_count);
- if (method_array_count == 0) {
- continue;
- }
- auto* method_array = if_table->GetMethodArray(i);
- for (size_t j = 0; j < num_virtuals; ++j) {
- auto method = method_array->GetElementPtrSize<ArtMethod*>(j, pointer_size);
- DCHECK(method != nullptr) << PrettyClass(super_class);
- // Miranda methods cannot be used to implement an interface method and defaults should be
- // skipped in case we override it.
- if (method->IsDefault() || method->IsMiranda()) {
- continue;
- }
- ArtMethod* interface_method = interface->GetVirtualMethod(j, pointer_size);
- uint32_t imt_index = interface_method->GetDexMethodIndex() % mirror::Class::kImtSize;
- auto** imt_ref = &out_imt[imt_index];
- if (*imt_ref == unimplemented_method) {
- *imt_ref = method;
- } else if (*imt_ref != imt_conflict_method) {
- *imt_ref = imt_conflict_method;
- }
- }
+ if (if_table != nullptr) {
+ // Ignore copied methods since we will handle these in LinkInterfaceMethods.
+ ConstructIMTFromIfTable(if_table,
+ unimplemented_method,
+ imt_conflict_method,
+ klass.Get(),
+ /*create_conflict_table*/false,
+ /*ignore_copied_methods*/true,
+ out_imt);
}
}
}
@@ -6324,13 +6450,10 @@
const bool extend_super_iftable = has_superclass;
if (has_superclass && fill_tables) {
FillImtFromSuperClass(klass,
- iftable,
unimplemented_method,
imt_conflict_method,
- out_imt,
- image_pointer_size_);
+ out_imt);
}
-
// Allocate method arrays before since we don't want miss visiting miranda method roots due to
// thread suspension.
if (fill_tables) {
@@ -6414,7 +6537,7 @@
auto* interface_method = iftable->GetInterface(i)->GetVirtualMethod(j, image_pointer_size_);
MethodNameAndSignatureComparator interface_name_comparator(
interface_method->GetInterfaceMethodIfProxy(image_pointer_size_));
- uint32_t imt_index = interface_method->GetDexMethodIndex() % mirror::Class::kImtSize;
+ uint32_t imt_index = GetIMTIndex(interface_method);
ArtMethod** imt_ptr = &out_imt[imt_index];
// For each method listed in the interface's method list, find the
// matching method in our class's method list. We want to favor the
@@ -6459,7 +6582,6 @@
// Place method in imt if entry is empty, place conflict otherwise.
SetIMTRef(unimplemented_method,
imt_conflict_method,
- image_pointer_size_,
vtable_method,
/*out*/imt_ptr);
}
@@ -6602,7 +6724,6 @@
method_array->SetElementPtrSize(j, current_method, image_pointer_size_);
SetIMTRef(unimplemented_method,
imt_conflict_method,
- image_pointer_size_,
current_method,
/*out*/imt_ptr);
}
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index 6dacb75..c880f4c 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -612,6 +612,12 @@
static bool IsBootClassLoader(ScopedObjectAccessAlreadyRunnable& soa,
mirror::ClassLoader* class_loader)
+
+ ArtMethod* AddMethodToConflictTable(mirror::Class* klass,
+ ArtMethod* conflict_method,
+ ArtMethod* interface_method,
+ ArtMethod* method,
+ bool force_new_conflict_method)
SHARED_REQUIRES(Locks::mutator_lock_);
struct DexCacheData {
@@ -1061,6 +1067,28 @@
REQUIRES(!dex_lock_)
SHARED_REQUIRES(Locks::mutator_lock_);
+ // Sets imt_ref appropriately for LinkInterfaceMethods.
+ // If there is no method in the imt location of imt_ref it will store the given method there.
+ // Otherwise it will set the conflict method which will figure out which method to use during
+ // runtime.
+ void SetIMTRef(ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ ArtMethod* current_method,
+ /*out*/ArtMethod** imt_ref) SHARED_REQUIRES(Locks::mutator_lock_);
+
+ void ConstructIMTFromIfTable(mirror::IfTable* if_table,
+ ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ mirror::Class* klass,
+ bool create_conflict_tables,
+ bool ignore_copied_methods,
+ ArtMethod** out_imt) SHARED_REQUIRES(Locks::mutator_lock_);
+
+ void FillImtFromSuperClass(Handle<mirror::Class> klass,
+ ArtMethod* unimplemented_method,
+ ArtMethod* imt_conflict_method,
+ ArtMethod** out_imt) SHARED_REQUIRES(Locks::mutator_lock_);
+
std::vector<const DexFile*> boot_class_path_;
std::vector<std::unique_ptr<const DexFile>> boot_dex_files_;
diff --git a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
index da6af72..278c4a3 100644
--- a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
+++ b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
@@ -2225,34 +2225,13 @@
ArtMethod* conflict_method = cls->GetEmbeddedImTableEntry(
imt_index % mirror::Class::kImtSize, sizeof(void*));
if (conflict_method->IsRuntimeMethod()) {
- ImtConflictTable* current_table = conflict_method->GetImtConflictTable(sizeof(void*));
- Runtime* runtime = Runtime::Current();
- LinearAlloc* linear_alloc = (cls->GetClassLoader() == nullptr)
- ? runtime->GetLinearAlloc()
- : cls->GetClassLoader()->GetAllocator();
- bool is_new_entry = (conflict_method == runtime->GetImtConflictMethod());
-
- // Create a new entry if the existing one is the shared conflict method.
- ArtMethod* new_conflict_method = is_new_entry
- ? runtime->CreateImtConflictMethod(linear_alloc)
- : conflict_method;
-
- // Allocate a new table. Note that we will leak this table at the next conflict,
- // but that's a tradeoff compared to making the table fixed size.
- void* data = linear_alloc->Alloc(
- self, ImtConflictTable::ComputeSizeWithOneMoreEntry(current_table));
- CHECK(data != nullptr) << "Out of memory";
- ImtConflictTable* new_table = new (data) ImtConflictTable(
- current_table, interface_method, method);
-
- // Do a fence to ensure threads see the data in the table before it is assigned
- // to the conlict method.
- // Note that there is a race in the presence of multiple threads and we may leak
- // memory from the LinearAlloc, but that's a tradeoff compared to using
- // atomic operations.
- QuasiAtomic::ThreadFenceRelease();
- new_conflict_method->SetImtConflictTable(new_table);
- if (is_new_entry) {
+ ArtMethod* new_conflict_method = Runtime::Current()->GetClassLinker()->AddMethodToConflictTable(
+ cls.Get(),
+ conflict_method,
+ interface_method,
+ method,
+ /*force_new_conflict_method*/false);
+ if (new_conflict_method != conflict_method) {
// Update the IMT if we create a new conflict method. No fence needed here, as the
// data is consistent.
cls->SetEmbeddedImTableEntry(imt_index % mirror::Class::kImtSize,
