verified_method.cc revision c449e8b79aaaf156ce055524c41474cc1200ed5a
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "verified_method.h" 18 19#include <algorithm> 20#include <memory> 21#include <vector> 22 23#include "art_method-inl.h" 24#include "base/logging.h" 25#include "base/stl_util.h" 26#include "dex_file.h" 27#include "dex_instruction-inl.h" 28#include "dex_instruction_utils.h" 29#include "mirror/class-inl.h" 30#include "mirror/dex_cache-inl.h" 31#include "mirror/object-inl.h" 32#include "utils.h" 33#include "verifier/dex_gc_map.h" 34#include "verifier/method_verifier-inl.h" 35#include "verifier/reg_type-inl.h" 36#include "verifier/register_line-inl.h" 37 38namespace art { 39 40const VerifiedMethod* VerifiedMethod::Create(verifier::MethodVerifier* method_verifier, 41 bool compile) { 42 std::unique_ptr<VerifiedMethod> verified_method(new VerifiedMethod); 43 verified_method->has_verification_failures_ = method_verifier->HasFailures(); 44 if (compile) { 45 /* Generate a register map. */ 46 if (!verified_method->GenerateGcMap(method_verifier)) { 47 return nullptr; // Not a real failure, but a failure to encode. 48 } 49 if (kIsDebugBuild) { 50 VerifyGcMap(method_verifier, verified_method->dex_gc_map_); 51 } 52 53 // TODO: move this out when DEX-to-DEX supports devirtualization. 54 if (method_verifier->HasVirtualOrInterfaceInvokes()) { 55 verified_method->GenerateDevirtMap(method_verifier); 56 } 57 58 // Only need dequicken info for JIT so far. 59 if (Runtime::Current()->UseJit() && !verified_method->GenerateDequickenMap(method_verifier)) { 60 return nullptr; 61 } 62 } 63 64 if (method_verifier->HasCheckCasts()) { 65 verified_method->GenerateSafeCastSet(method_verifier); 66 } 67 68 verified_method->SetStringInitPcRegMap(method_verifier->GetStringInitPcRegMap()); 69 70 return verified_method.release(); 71} 72 73const MethodReference* VerifiedMethod::GetDevirtTarget(uint32_t dex_pc) const { 74 auto it = devirt_map_.find(dex_pc); 75 return (it != devirt_map_.end()) ? &it->second : nullptr; 76} 77 78const DexFileReference* VerifiedMethod::GetDequickenIndex(uint32_t dex_pc) const { 79 DCHECK(Runtime::Current()->UseJit()); 80 auto it = dequicken_map_.find(dex_pc); 81 return (it != dequicken_map_.end()) ? &it->second : nullptr; 82} 83 84bool VerifiedMethod::IsSafeCast(uint32_t pc) const { 85 return std::binary_search(safe_cast_set_.begin(), safe_cast_set_.end(), pc); 86} 87 88bool VerifiedMethod::GenerateGcMap(verifier::MethodVerifier* method_verifier) { 89 DCHECK(dex_gc_map_.empty()); 90 size_t num_entries, ref_bitmap_bits, pc_bits; 91 ComputeGcMapSizes(method_verifier, &num_entries, &ref_bitmap_bits, &pc_bits); 92 // There's a single byte to encode the size of each bitmap. 93 if (ref_bitmap_bits >= kBitsPerByte * 8192 /* 13-bit size */) { 94 LOG(WARNING) << "Cannot encode GC map for method with " << ref_bitmap_bits << " registers: " 95 << PrettyMethod(method_verifier->GetMethodReference().dex_method_index, 96 *method_verifier->GetMethodReference().dex_file); 97 return false; 98 } 99 size_t ref_bitmap_bytes = RoundUp(ref_bitmap_bits, kBitsPerByte) / kBitsPerByte; 100 // There are 2 bytes to encode the number of entries. 101 if (num_entries > std::numeric_limits<uint16_t>::max()) { 102 LOG(WARNING) << "Cannot encode GC map for method with " << num_entries << " entries: " 103 << PrettyMethod(method_verifier->GetMethodReference().dex_method_index, 104 *method_verifier->GetMethodReference().dex_file); 105 return false; 106 } 107 size_t pc_bytes; 108 verifier::RegisterMapFormat format; 109 if (pc_bits <= kBitsPerByte) { 110 format = verifier::kRegMapFormatCompact8; 111 pc_bytes = 1; 112 } else if (pc_bits <= kBitsPerByte * 2) { 113 format = verifier::kRegMapFormatCompact16; 114 pc_bytes = 2; 115 } else { 116 LOG(WARNING) << "Cannot encode GC map for method with " 117 << (1 << pc_bits) << " instructions (number is rounded up to nearest power of 2): " 118 << PrettyMethod(method_verifier->GetMethodReference().dex_method_index, 119 *method_verifier->GetMethodReference().dex_file); 120 return false; 121 } 122 size_t table_size = ((pc_bytes + ref_bitmap_bytes) * num_entries) + 4; 123 dex_gc_map_.reserve(table_size); 124 // Write table header. 125 dex_gc_map_.push_back(format | ((ref_bitmap_bytes & ~0xFF) >> 5)); 126 dex_gc_map_.push_back(ref_bitmap_bytes & 0xFF); 127 dex_gc_map_.push_back(num_entries & 0xFF); 128 dex_gc_map_.push_back((num_entries >> 8) & 0xFF); 129 // Write table data. 130 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 131 for (size_t i = 0; i < code_item->insns_size_in_code_units_; i++) { 132 if (method_verifier->GetInstructionFlags(i).IsCompileTimeInfoPoint()) { 133 dex_gc_map_.push_back(i & 0xFF); 134 if (pc_bytes == 2) { 135 dex_gc_map_.push_back((i >> 8) & 0xFF); 136 } 137 verifier::RegisterLine* line = method_verifier->GetRegLine(i); 138 line->WriteReferenceBitMap(method_verifier, &dex_gc_map_, ref_bitmap_bytes); 139 } 140 } 141 DCHECK_EQ(dex_gc_map_.size(), table_size); 142 return true; 143} 144 145void VerifiedMethod::VerifyGcMap(verifier::MethodVerifier* method_verifier, 146 const std::vector<uint8_t>& data) { 147 // Check that for every GC point there is a map entry, there aren't entries for non-GC points, 148 // that the table data is well formed and all references are marked (or not) in the bitmap. 149 verifier::DexPcToReferenceMap map(&data[0]); 150 DCHECK_EQ(data.size(), map.RawSize()); 151 size_t map_index = 0; 152 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 153 for (size_t i = 0; i < code_item->insns_size_in_code_units_; i++) { 154 const uint8_t* reg_bitmap = map.FindBitMap(i, false); 155 if (method_verifier->GetInstructionFlags(i).IsCompileTimeInfoPoint()) { 156 DCHECK_LT(map_index, map.NumEntries()); 157 DCHECK_EQ(map.GetDexPc(map_index), i); 158 DCHECK_EQ(map.GetBitMap(map_index), reg_bitmap); 159 map_index++; 160 verifier::RegisterLine* line = method_verifier->GetRegLine(i); 161 for (size_t j = 0; j < code_item->registers_size_; j++) { 162 if (line->GetRegisterType(method_verifier, j).IsNonZeroReferenceTypes()) { 163 DCHECK_LT(j / kBitsPerByte, map.RegWidth()); 164 DCHECK_EQ((reg_bitmap[j / kBitsPerByte] >> (j % kBitsPerByte)) & 1, 1); 165 } else if ((j / kBitsPerByte) < map.RegWidth()) { 166 DCHECK_EQ((reg_bitmap[j / kBitsPerByte] >> (j % kBitsPerByte)) & 1, 0); 167 } else { 168 // If a register doesn't contain a reference then the bitmap may be shorter than the line. 169 } 170 } 171 } else { 172 DCHECK(i >= 65536 || reg_bitmap == nullptr); 173 } 174 } 175} 176 177void VerifiedMethod::ComputeGcMapSizes(verifier::MethodVerifier* method_verifier, 178 size_t* gc_points, size_t* ref_bitmap_bits, 179 size_t* log2_max_gc_pc) { 180 size_t local_gc_points = 0; 181 size_t max_insn = 0; 182 size_t max_ref_reg = -1; 183 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 184 for (size_t i = 0; i < code_item->insns_size_in_code_units_; i++) { 185 if (method_verifier->GetInstructionFlags(i).IsCompileTimeInfoPoint()) { 186 local_gc_points++; 187 max_insn = i; 188 verifier::RegisterLine* line = method_verifier->GetRegLine(i); 189 max_ref_reg = line->GetMaxNonZeroReferenceReg(method_verifier, max_ref_reg); 190 } 191 } 192 *gc_points = local_gc_points; 193 *ref_bitmap_bits = max_ref_reg + 1; // If max register is 0 we need 1 bit to encode (ie +1). 194 size_t i = 0; 195 while ((1U << i) <= max_insn) { 196 i++; 197 } 198 *log2_max_gc_pc = i; 199} 200 201bool VerifiedMethod::GenerateDequickenMap(verifier::MethodVerifier* method_verifier) { 202 if (method_verifier->HasFailures()) { 203 return false; 204 } 205 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 206 const uint16_t* insns = code_item->insns_; 207 const Instruction* inst = Instruction::At(insns); 208 const Instruction* end = Instruction::At(insns + code_item->insns_size_in_code_units_); 209 for (; inst < end; inst = inst->Next()) { 210 const bool is_virtual_quick = inst->Opcode() == Instruction::INVOKE_VIRTUAL_QUICK; 211 const bool is_range_quick = inst->Opcode() == Instruction::INVOKE_VIRTUAL_RANGE_QUICK; 212 if (is_virtual_quick || is_range_quick) { 213 uint32_t dex_pc = inst->GetDexPc(insns); 214 verifier::RegisterLine* line = method_verifier->GetRegLine(dex_pc); 215 ArtMethod* method = 216 method_verifier->GetQuickInvokedMethod(inst, line, is_range_quick, true); 217 if (method == nullptr) { 218 // It can be null if the line wasn't verified since it was unreachable. 219 return false; 220 } 221 // The verifier must know what the type of the object was or else we would have gotten a 222 // failure. Put the dex method index in the dequicken map since we need this to get number of 223 // arguments in the compiler. 224 dequicken_map_.Put(dex_pc, DexFileReference(method->GetDexFile(), 225 method->GetDexMethodIndex())); 226 } else if (IsInstructionIGetQuickOrIPutQuick(inst->Opcode())) { 227 uint32_t dex_pc = inst->GetDexPc(insns); 228 verifier::RegisterLine* line = method_verifier->GetRegLine(dex_pc); 229 ArtField* field = method_verifier->GetQuickFieldAccess(inst, line); 230 if (field == nullptr) { 231 // It can be null if the line wasn't verified since it was unreachable. 232 return false; 233 } 234 // The verifier must know what the type of the field was or else we would have gotten a 235 // failure. Put the dex field index in the dequicken map since we need this for lowering 236 // in the compiler. 237 // TODO: Putting a field index in a method reference is gross. 238 dequicken_map_.Put(dex_pc, DexFileReference(field->GetDexFile(), field->GetDexFieldIndex())); 239 } 240 } 241 return true; 242} 243 244void VerifiedMethod::GenerateDevirtMap(verifier::MethodVerifier* method_verifier) { 245 // It is risky to rely on reg_types for sharpening in cases of soft 246 // verification, we might end up sharpening to a wrong implementation. Just abort. 247 if (method_verifier->HasFailures()) { 248 return; 249 } 250 251 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 252 const uint16_t* insns = code_item->insns_; 253 const Instruction* inst = Instruction::At(insns); 254 const Instruction* end = Instruction::At(insns + code_item->insns_size_in_code_units_); 255 256 for (; inst < end; inst = inst->Next()) { 257 const bool is_virtual = inst->Opcode() == Instruction::INVOKE_VIRTUAL || 258 inst->Opcode() == Instruction::INVOKE_VIRTUAL_RANGE; 259 const bool is_interface = inst->Opcode() == Instruction::INVOKE_INTERFACE || 260 inst->Opcode() == Instruction::INVOKE_INTERFACE_RANGE; 261 262 if (!is_interface && !is_virtual) { 263 continue; 264 } 265 // Get reg type for register holding the reference to the object that will be dispatched upon. 266 uint32_t dex_pc = inst->GetDexPc(insns); 267 verifier::RegisterLine* line = method_verifier->GetRegLine(dex_pc); 268 const bool is_range = inst->Opcode() == Instruction::INVOKE_VIRTUAL_RANGE || 269 inst->Opcode() == Instruction::INVOKE_INTERFACE_RANGE; 270 const verifier::RegType& 271 reg_type(line->GetRegisterType(method_verifier, 272 is_range ? inst->VRegC_3rc() : inst->VRegC_35c())); 273 274 if (!reg_type.HasClass()) { 275 // We will compute devirtualization information only when we know the Class of the reg type. 276 continue; 277 } 278 mirror::Class* reg_class = reg_type.GetClass(); 279 if (reg_class->IsInterface()) { 280 // We can't devirtualize when the known type of the register is an interface. 281 continue; 282 } 283 if (reg_class->IsAbstract() && !reg_class->IsArrayClass()) { 284 // We can't devirtualize abstract classes except on arrays of abstract classes. 285 continue; 286 } 287 auto* cl = Runtime::Current()->GetClassLinker(); 288 size_t pointer_size = cl->GetImagePointerSize(); 289 ArtMethod* abstract_method = method_verifier->GetDexCache()->GetResolvedMethod( 290 is_range ? inst->VRegB_3rc() : inst->VRegB_35c(), pointer_size); 291 if (abstract_method == nullptr) { 292 // If the method is not found in the cache this means that it was never found 293 // by ResolveMethodAndCheckAccess() called when verifying invoke_*. 294 continue; 295 } 296 // Find the concrete method. 297 ArtMethod* concrete_method = nullptr; 298 if (is_interface) { 299 concrete_method = reg_type.GetClass()->FindVirtualMethodForInterface( 300 abstract_method, pointer_size); 301 } 302 if (is_virtual) { 303 concrete_method = reg_type.GetClass()->FindVirtualMethodForVirtual( 304 abstract_method, pointer_size); 305 } 306 if (concrete_method == nullptr || concrete_method->IsAbstract()) { 307 // In cases where concrete_method is not found, or is abstract, continue to the next invoke. 308 continue; 309 } 310 if (reg_type.IsPreciseReference() || concrete_method->IsFinal() || 311 concrete_method->GetDeclaringClass()->IsFinal()) { 312 // If we knew exactly the class being dispatched upon, or if the target method cannot be 313 // overridden record the target to be used in the compiler driver. 314 devirt_map_.Put(dex_pc, concrete_method->ToMethodReference()); 315 } 316 } 317} 318 319void VerifiedMethod::GenerateSafeCastSet(verifier::MethodVerifier* method_verifier) { 320 /* 321 * Walks over the method code and adds any cast instructions in which 322 * the type cast is implicit to a set, which is used in the code generation 323 * to elide these casts. 324 */ 325 if (method_verifier->HasFailures()) { 326 return; 327 } 328 const DexFile::CodeItem* code_item = method_verifier->CodeItem(); 329 const Instruction* inst = Instruction::At(code_item->insns_); 330 const Instruction* end = Instruction::At(code_item->insns_ + 331 code_item->insns_size_in_code_units_); 332 333 for (; inst < end; inst = inst->Next()) { 334 Instruction::Code code = inst->Opcode(); 335 if ((code == Instruction::CHECK_CAST) || (code == Instruction::APUT_OBJECT)) { 336 uint32_t dex_pc = inst->GetDexPc(code_item->insns_); 337 if (!method_verifier->GetInstructionFlags(dex_pc).IsVisited()) { 338 // Do not attempt to quicken this instruction, it's unreachable anyway. 339 continue; 340 } 341 const verifier::RegisterLine* line = method_verifier->GetRegLine(dex_pc); 342 bool is_safe_cast = false; 343 if (code == Instruction::CHECK_CAST) { 344 const verifier::RegType& reg_type(line->GetRegisterType(method_verifier, 345 inst->VRegA_21c())); 346 const verifier::RegType& cast_type = 347 method_verifier->ResolveCheckedClass(inst->VRegB_21c()); 348 is_safe_cast = cast_type.IsStrictlyAssignableFrom(reg_type); 349 } else { 350 const verifier::RegType& array_type(line->GetRegisterType(method_verifier, 351 inst->VRegB_23x())); 352 // We only know its safe to assign to an array if the array type is precise. For example, 353 // an Object[] can have any type of object stored in it, but it may also be assigned a 354 // String[] in which case the stores need to be of Strings. 355 if (array_type.IsPreciseReference()) { 356 const verifier::RegType& value_type(line->GetRegisterType(method_verifier, 357 inst->VRegA_23x())); 358 const verifier::RegType& component_type = method_verifier->GetRegTypeCache() 359 ->GetComponentType(array_type, method_verifier->GetClassLoader()); 360 is_safe_cast = component_type.IsStrictlyAssignableFrom(value_type); 361 } 362 } 363 if (is_safe_cast) { 364 // Verify ordering for push_back() to the sorted vector. 365 DCHECK(safe_cast_set_.empty() || safe_cast_set_.back() < dex_pc); 366 safe_cast_set_.push_back(dex_pc); 367 } 368 } 369 } 370} 371 372} // namespace art 373