Avoid cases of deriving information from unresolved types giving conflict.
Previously non-trivial merges of unresolved types resulted in conflict
(bottom), introduce a new type to represent this case. Similarly
implement a type for unresolved super classes.
Change-Id: Ib84ba082cb9409ad3acaa49dafbc6b1dd1c7772d
diff --git a/src/class_linker.cc b/src/class_linker.cc
index 5bd69e8..df14a41 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -2045,6 +2045,11 @@
LOG(FATAL) << "Verification failed hard on class " << PrettyDescriptor(klass)
<< " at compile time, but succeeded at runtime! The verifier must be broken.";
}
+ if (!preverified && verifier_failure != verifier::MethodVerifier::kNoFailure) {
+ LOG(WARNING) << "Soft verification failure in class " << PrettyDescriptor(klass)
+ << " in " << klass->GetDexCache()->GetLocation()->ToModifiedUtf8()
+ << " because: " << error_msg;
+ }
DCHECK(!Thread::Current()->IsExceptionPending());
CHECK(verifier_failure == verifier::MethodVerifier::kNoFailure ||
Runtime::Current()->IsCompiler());
diff --git a/src/verifier/method_verifier.cc b/src/verifier/method_verifier.cc
index cc01224..5e98b1e 100644
--- a/src/verifier/method_verifier.cc
+++ b/src/verifier/method_verifier.cc
@@ -2627,7 +2627,7 @@
if (is_super) {
DCHECK(method_type == METHOD_VIRTUAL);
const RegType& super = GetDeclaringClass().GetSuperClass(®_types_);
- if (super.IsConflict()) { // unknown super class
+ if (super.IsUnresolvedTypes()) {
Fail(VERIFY_ERROR_NO_METHOD) << "unknown super class in invoke-super from "
<< PrettyMethod(method_idx_, *dex_file_)
<< " to super " << PrettyMethod(res_method);
diff --git a/src/verifier/reg_type.cc b/src/verifier/reg_type.cc
index dd54b5f..8d1df22 100644
--- a/src/verifier/reg_type.cc
+++ b/src/verifier/reg_type.cc
@@ -43,13 +43,41 @@
"Uninitialized This Reference",
"Unresolved And Uninitialized Reference",
"Unresolved And Uninitialized This Reference",
+ "Unresolved Merged References",
+ "Unresolved Super Class",
"Reference",
};
-std::string RegType::Dump() const {
+std::string RegType::Dump(const RegTypeCache* reg_types) const {
DCHECK(type_ >= kRegTypeUndefined && type_ <= kRegTypeReference);
+ DCHECK(arraysize(type_strings) == (kRegTypeReference + 1));
std::string result;
- if (IsConstant()) {
+ if (IsUnresolvedMergedReference()) {
+ if (reg_types == NULL) {
+ std::pair<uint16_t, uint16_t> refs = GetTopMergedTypes();
+ result += StringPrintf("UnresolvedMergedReferences(%d, %d)", refs.first, refs.second);
+ } else {
+ std::set<uint16_t> types = GetMergedTypes(reg_types);
+ result += "UnresolvedMergedReferences(";
+ typedef std::set<uint16_t>::const_iterator It; // TODO: C++0x auto
+ It it = types.begin();
+ result += reg_types->GetFromId(*it).Dump(reg_types);
+ for(++it; it != types.end(); ++it) {
+ result += ", ";
+ result += reg_types->GetFromId(*it).Dump(reg_types);
+ }
+ result += ")";
+ }
+ } else if (IsUnresolvedSuperClass()) {
+ uint16_t super_type_id = GetUnresolvedSuperClassChildId();
+ if (reg_types == NULL) {
+ result += StringPrintf("UnresolvedSuperClass(%d)", super_type_id);
+ } else {
+ result += "UnresolvedSuperClass(";
+ result += reg_types->GetFromId(super_type_id).Dump(reg_types);
+ result += ")";
+ }
+ } else if (IsConstant()) {
uint32_t val = ConstantValue();
if (val == 0) {
result = "Zero";
@@ -85,6 +113,31 @@
}
}
+std::set<uint16_t> RegType::GetMergedTypes(const RegTypeCache* cache) const {
+ std::pair<uint16_t, uint16_t> refs = GetTopMergedTypes();
+ const RegType& left = cache->GetFromId(refs.first);
+ const RegType& right = cache->GetFromId(refs.second);
+ std::set<uint16_t> types;
+ if (left.IsUnresolvedMergedReference()) {
+ types = left.GetMergedTypes(cache);
+ } else {
+ types.insert(refs.first);
+ }
+ if (right.IsUnresolvedMergedReference()) {
+ std::set<uint16_t> right_types = right.GetMergedTypes(cache);
+ types.insert(right_types.begin(), right_types.end());
+ } else {
+ types.insert(refs.second);
+ }
+#ifndef NDEBUG
+ typedef std::set<uint16_t>::const_iterator It; // TODO: C++0x auto
+ for(It it = types.begin(); it != types.end(); ++it) {
+ CHECK(!cache->GetFromId(*it).IsUnresolvedMergedReference());
+ }
+#endif
+ return types;
+}
+
const RegType& RegType::GetSuperClass(RegTypeCache* cache) const {
if (!IsUnresolvedTypes()) {
Class* super_klass = GetClass()->GetSuperClass();
@@ -94,8 +147,13 @@
return cache->Zero();
}
} else {
- // TODO: handle unresolved type cases better?
- return cache->Conflict();
+ if (!IsUnresolvedMergedReference() && !IsUnresolvedSuperClass() &&
+ GetDescriptor()->CharAt(0) == '[') {
+ // Super class of all arrays is Object.
+ return cache->JavaLangObject();
+ } else {
+ return cache->FromUnresolvedSuperClass(*this);
+ }
}
}
@@ -157,12 +215,8 @@
GetClass()->IsAssignableFrom(src.GetClass())) {
// We're assignable from the Class point-of-view
return true;
- } else if (IsUnresolvedTypes() && src.IsUnresolvedTypes() &&
- GetDescriptor() == src.GetDescriptor()) {
- // Two unresolved types (maybe one is uninitialized), we're clearly assignable if the
- // descriptor is the same.
- return true;
} else {
+ // TODO: unresolved types are only assignable for null, Object and equality currently.
return false;
}
}
@@ -248,10 +302,16 @@
return SelectNonConstant(*this, incoming_type); // 0 MERGE ref => ref
} else if (IsJavaLangObject() || incoming_type.IsJavaLangObject()) {
return reg_types->JavaLangObject(); // Object MERGE ref => Object
- } else if (IsUninitializedTypes() || incoming_type.IsUninitializedTypes() ||
- IsUnresolvedTypes() || incoming_type.IsUnresolvedTypes()) {
- // Can only merge an unresolved or uninitialized type with itself, 0 or Object, we've already
- // checked these so => Conflict
+ } else if (IsUnresolvedTypes() || incoming_type.IsUnresolvedTypes()) {
+ // We know how to merge an unresolved type with itself, 0 or Object. In this case we
+ // have two sub-classes and don't know how to merge. Create a new string-based unresolved
+ // type that reflects our lack of knowledge and that allows the rest of the unresolved
+ // mechanics to continue.
+ return reg_types->FromUnresolvedMerge(*this, incoming_type);
+ } else if (IsUninitializedTypes() || incoming_type.IsUninitializedTypes()) {
+ // Something that is uninitialized hasn't had its constructor called. Mark any merge
+ // of this type with something that is initialized as conflicting. The cases of a merge
+ // with itself, 0 or Object are handled above.
return reg_types->Conflict();
} else { // Two reference types, compute Join
Class* c1 = GetClass();
diff --git a/src/verifier/reg_type.h b/src/verifier/reg_type.h
index 41a9255..7e8fca1 100644
--- a/src/verifier/reg_type.h
+++ b/src/verifier/reg_type.h
@@ -62,6 +62,8 @@
kRegTypeUnresolvedAndUninitializedReference, // Freshly allocated unresolved reference type.
// Freshly allocated unresolved reference passed as "this".
kRegTypeUnresolvedAndUninitializedThisReference,
+ kRegTypeUnresolvedMergedReference, // Tree of merged references (at least 1 is unresolved).
+ kRegTypeUnresolvedSuperClass, // Super class of an unresolved type.
kRegTypeReference, // Reference type.
};
@@ -88,6 +90,8 @@
bool IsUnresolvedAndUninitializedThisReference() const {
return type_ == kRegTypeUnresolvedAndUninitializedThisReference;
}
+ bool IsUnresolvedMergedReference() const { return type_ == kRegTypeUnresolvedMergedReference; }
+ bool IsUnresolvedSuperClass() const { return type_ == kRegTypeUnresolvedSuperClass; }
bool IsReference() const { return type_ == kRegTypeReference; }
bool IsUninitializedTypes() const {
return IsUninitializedReference() || IsUninitializedThisReference() ||
@@ -95,7 +99,8 @@
}
bool IsUnresolvedTypes() const {
return IsUnresolvedReference() || IsUnresolvedAndUninitializedReference() ||
- IsUnresolvedAndUninitializedThisReference();
+ IsUnresolvedAndUninitializedThisReference() || IsUnresolvedMergedReference() ||
+ IsUnresolvedSuperClass();
}
bool IsLowHalf() const { return type_ == kRegTypeLongLo ||
type_ == kRegTypeDoubleLo ||
@@ -122,7 +127,7 @@
// approximate to the actual constant value by virtue of merging.
int32_t ConstantValue() const {
DCHECK(IsConstant());
- return allocation_pc_or_constant_;
+ return allocation_pc_or_constant_or_merged_types_;
}
bool IsZero() const { return IsConstant() && ConstantValue() == 0; }
@@ -146,14 +151,18 @@
bool IsReferenceTypes() const {
return IsNonZeroReferenceTypes() || IsZero();
}
+
bool IsNonZeroReferenceTypes() const {
return IsReference() || IsUnresolvedReference() ||
IsUninitializedReference() || IsUninitializedThisReference() ||
- IsUnresolvedAndUninitializedReference() || IsUnresolvedAndUninitializedThisReference();
+ IsUnresolvedAndUninitializedReference() || IsUnresolvedAndUninitializedThisReference() ||
+ IsUnresolvedMergedReference() || IsUnresolvedSuperClass();
}
+
bool IsCategory1Types() const {
return (type_ >= kRegType1nrSTART && type_ <= kRegType1nrEND) || IsConstant();
}
+
bool IsCategory2Types() const {
return IsLowHalf(); // Don't expect explicit testing of high halves
}
@@ -185,7 +194,7 @@
uint32_t GetAllocationPc() const {
DCHECK(IsUninitializedTypes());
- return allocation_pc_or_constant_;
+ return allocation_pc_or_constant_or_merged_types_;
}
Class* GetClass() const {
@@ -200,7 +209,7 @@
}
bool IsArrayTypes() const {
- if (IsUnresolvedTypes()) {
+ if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
return GetDescriptor()->CharAt(0) == '[';
} else if (IsReference()) {
return GetClass()->IsArrayClass();
@@ -210,7 +219,7 @@
}
bool IsObjectArrayTypes() const {
- if (IsUnresolvedTypes()) {
+ if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
// Primitive arrays will always resolve
DCHECK(GetDescriptor()->CharAt(1) == 'L' || GetDescriptor()->CharAt(1) == '[');
return GetDescriptor()->CharAt(0) == '[';
@@ -258,7 +267,7 @@
}
String* GetDescriptor() const {
- DCHECK(IsUnresolvedTypes());
+ DCHECK(IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass());
DCHECK(klass_or_descriptor_ != NULL);
DCHECK(klass_or_descriptor_->GetClass()->IsStringClass());
return down_cast<String*>(klass_or_descriptor_);
@@ -268,9 +277,25 @@
return cache_id_;
}
+ // The top of a tree of merged types.
+ std::pair<uint16_t, uint16_t> GetTopMergedTypes() const {
+ DCHECK(IsUnresolvedMergedReference());
+ uint16_t type1 = static_cast<uint16_t>(allocation_pc_or_constant_or_merged_types_ & 0xFFFF);
+ uint16_t type2 = static_cast<uint16_t>(allocation_pc_or_constant_or_merged_types_ >> 16);
+ return std::pair<uint16_t, uint16_t>(type1, type2);
+ }
+
+ // The complete set of merged types.
+ std::set<uint16_t> GetMergedTypes(const RegTypeCache* cache) const;
+
+ uint16_t GetUnresolvedSuperClassChildId() const {
+ DCHECK(IsUnresolvedSuperClass());
+ return static_cast<uint16_t>(allocation_pc_or_constant_or_merged_types_ & 0xFFFF);
+ }
+
const RegType& GetSuperClass(RegTypeCache* cache) const;
- std::string Dump() const;
+ std::string Dump(const RegTypeCache* reg_types = NULL) const;
// Can this type access other?
bool CanAccess(const RegType& other) const;
@@ -306,12 +331,15 @@
private:
friend class RegTypeCache;
- RegType(Type type, Object* klass_or_descriptor, uint32_t allocation_pc_or_constant, uint16_t cache_id)
+ RegType(Type type, Object* klass_or_descriptor,
+ uint32_t allocation_pc_or_constant_or_merged_types, uint16_t cache_id)
: type_(type), klass_or_descriptor_(klass_or_descriptor),
- allocation_pc_or_constant_(allocation_pc_or_constant), cache_id_(cache_id) {
- DCHECK(IsConstant() || IsUninitializedTypes() || allocation_pc_or_constant == 0);
+ allocation_pc_or_constant_or_merged_types_(allocation_pc_or_constant_or_merged_types),
+ cache_id_(cache_id) {
+ DCHECK(IsConstant() || IsUninitializedTypes() || IsUnresolvedMergedReference() ||
+ IsUnresolvedSuperClass() || allocation_pc_or_constant_or_merged_types == 0);
if (!IsConstant() && !IsLongConstant() && !IsLongConstantHigh() && !IsUndefined() &&
- !IsConflict()) {
+ !IsConflict() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
DCHECK(klass_or_descriptor != NULL);
DCHECK(IsUnresolvedTypes() || klass_or_descriptor_->IsClass());
DCHECK(!IsUnresolvedTypes() || klass_or_descriptor_->GetClass()->IsStringClass());
@@ -327,7 +355,7 @@
// - if IsConstant() holds a 32bit constant value
// - is IsReference() holds the allocation_pc or kInitArgAddr for an initialized reference or
// kUninitThisArgAddr for an uninitialized this ptr
- const uint32_t allocation_pc_or_constant_;
+ const uint32_t allocation_pc_or_constant_or_merged_types_;
// A RegType cache densely encodes types, this is the location in the cache for this type
const uint16_t cache_id_;
diff --git a/src/verifier/reg_type_cache.cc b/src/verifier/reg_type_cache.cc
index bb05e7e..37086c9 100644
--- a/src/verifier/reg_type_cache.cc
+++ b/src/verifier/reg_type_cache.cc
@@ -143,6 +143,60 @@
}
}
+const RegType& RegTypeCache::FromUnresolvedMerge(const RegType& left, const RegType& right) {
+ std::set<uint16_t> types;
+ if (left.IsUnresolvedMergedReference()) {
+ types = left.GetMergedTypes(this);
+ } else {
+ types.insert(left.GetId());
+ }
+ if (right.IsUnresolvedMergedReference()) {
+ std::set<uint16_t> right_types = right.GetMergedTypes(this);
+ types.insert(right_types.begin(), right_types.end());
+ } else {
+ types.insert(right.GetId());
+ }
+ // Check if entry already exists.
+ for (size_t i = RegType::kRegTypeLastFixedLocation + 1; i < entries_.size(); i++) {
+ RegType* cur_entry = entries_[i];
+ if (cur_entry->IsUnresolvedMergedReference()) {
+ std::set<uint16_t> cur_entry_types = cur_entry->GetMergedTypes(this);
+ if (cur_entry_types == types) {
+ return *cur_entry;
+ }
+ }
+ }
+ // Create entry.
+ uint32_t merged_ids = static_cast<uint32_t>(left.GetId()) << 16 |
+ static_cast<uint32_t>(right.GetId());
+ RegType* entry = new RegType(RegType::kRegTypeUnresolvedMergedReference, NULL, merged_ids,
+ entries_.size());
+ entries_.push_back(entry);
+#ifndef DEBUG
+ std::set<uint16_t> check_types = entry->GetMergedTypes(this);
+ CHECK(check_types == types);
+#endif
+ return *entry;
+}
+
+const RegType& RegTypeCache::FromUnresolvedSuperClass(const RegType& child) {
+ // Check if entry already exists.
+ for (size_t i = RegType::kRegTypeLastFixedLocation + 1; i < entries_.size(); i++) {
+ RegType* cur_entry = entries_[i];
+ if (cur_entry->IsUnresolvedSuperClass()) {
+ uint16_t unresolved_super_child_id = cur_entry->GetUnresolvedSuperClassChildId();
+ if (unresolved_super_child_id == child.GetId()) {
+ return *cur_entry;
+ }
+ }
+ }
+ // Create entry.
+ RegType* entry = new RegType(RegType::kRegTypeUnresolvedSuperClass, NULL, child.GetId(),
+ entries_.size());
+ entries_.push_back(entry);
+ return *entry;
+}
+
const RegType& RegTypeCache::Uninitialized(const RegType& type, uint32_t allocation_pc) {
RegType* entry;
if (type.IsUnresolvedTypes()) {
diff --git a/src/verifier/reg_type_cache.h b/src/verifier/reg_type_cache.h
index 765809c..4ba667b 100644
--- a/src/verifier/reg_type_cache.h
+++ b/src/verifier/reg_type_cache.h
@@ -33,7 +33,7 @@
STLDeleteElements(&entries_);
}
- const RegType& GetFromId(uint16_t id) {
+ const RegType& GetFromId(uint16_t id) const {
DCHECK_LT(id, entries_.size());
RegType* result = entries_[id];
DCHECK(result != NULL);
@@ -45,6 +45,8 @@
const RegType& FromCat1Const(int32_t value);
const RegType& FromDescriptor(ClassLoader* loader, const char* descriptor);
const RegType& FromType(RegType::Type);
+ const RegType& FromUnresolvedMerge(const RegType& left, const RegType& right);
+ const RegType& FromUnresolvedSuperClass(const RegType& child);
const RegType& Boolean() { return FromType(RegType::kRegTypeBoolean); }
const RegType& Byte() { return FromType(RegType::kRegTypeByte); }
diff --git a/src/verifier/register_line.cc b/src/verifier/register_line.cc
index d5477a3..d6aca98 100644
--- a/src/verifier/register_line.cc
+++ b/src/verifier/register_line.cc
@@ -130,6 +130,20 @@
DCHECK_GT(changed, 0u);
}
+std::string RegisterLine::Dump() const {
+ std::string result;
+ for (size_t i = 0; i < num_regs_; i++) {
+ result += StringPrintf("%zd:[", i);
+ result += GetRegisterType(i).Dump(verifier_->GetRegTypeCache());
+ result += "],";
+ }
+ typedef std::deque<uint32_t>::const_iterator It; // TODO: C++0x auto
+ for (It it = monitors_.begin(), end = monitors_.end(); it != end ; ++it) {
+ result += StringPrintf("{%d},", *it);
+ }
+ return result;
+}
+
void RegisterLine::MarkUninitRefsAsInvalid(const RegType& uninit_type) {
for (size_t i = 0; i < num_regs_; i++) {
if (GetRegisterType(i).Equals(uninit_type)) {
diff --git a/src/verifier/register_line.h b/src/verifier/register_line.h
index e406678..9664a5b 100644
--- a/src/verifier/register_line.h
+++ b/src/verifier/register_line.h
@@ -98,19 +98,7 @@
reg_to_lock_depths_ = src->reg_to_lock_depths_;
}
- std::string Dump() const {
- std::string result;
- for (size_t i = 0; i < num_regs_; i++) {
- result += StringPrintf("%zd:[", i);
- result += GetRegisterType(i).Dump();
- result += "],";
- }
- typedef std::deque<uint32_t>::const_iterator It; // TODO: C++0x auto
- for (It it = monitors_.begin(), end = monitors_.end(); it != end ; ++it) {
- result += StringPrintf("{%d},", *it);
- }
- return result;
- }
+ std::string Dump() const;
void FillWithGarbage() {
memset(line_.get(), 0xf1, num_regs_ * sizeof(uint16_t));