1 /* 2 * Copyright (C) 2016 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 #ifndef ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_ 18 #define ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_ 19 20 #include <map> 21 #include <set> 22 #include <vector> 23 24 #include "base/array_ref.h" 25 #include "base/locks.h" 26 #include "dex/dex_file_structs.h" 27 #include "dex/dex_file_types.h" 28 #include "handle.h" 29 #include "obj_ptr.h" 30 #include "thread.h" 31 #include "verifier_enums.h" // For MethodVerifier::FailureKind. 32 33 namespace art { 34 35 class ArtField; 36 class ArtMethod; 37 class DexFile; 38 class VariableIndentationOutputStream; 39 40 namespace mirror { 41 class Class; 42 class ClassLoader; 43 } // namespace mirror 44 45 namespace verifier { 46 47 // Verification dependencies collector class used by the MethodVerifier to record 48 // resolution outcomes and type assignability tests of classes/methods/fields 49 // not present in the set of compiled DEX files, that is classes/methods/fields 50 // defined in the classpath. 51 // The compilation driver initializes the class and registers all DEX files 52 // which are being compiled. Classes defined in DEX files outside of this set 53 // (or synthesized classes without associated DEX files) are considered being 54 // in the classpath. 55 // During code-flow verification, the MethodVerifier informs VerifierDeps 56 // about the outcome of every resolution and assignability test, and 57 // the VerifierDeps object records them if their outcome may change with 58 // changes in the classpath. 59 class VerifierDeps { 60 public: 61 explicit VerifierDeps(const std::vector<const DexFile*>& dex_files); 62 63 VerifierDeps(const std::vector<const DexFile*>& dex_files, ArrayRef<const uint8_t> data); 64 65 // Merge `other` into this `VerifierDeps`'. `other` and `this` must be for the 66 // same set of dex files. 67 void MergeWith(std::unique_ptr<VerifierDeps> other, const std::vector<const DexFile*>& dex_files); 68 69 // Record information that a class was verified. 70 // Note that this function is different from MaybeRecordVerificationStatus() which 71 // looks up thread-local VerifierDeps first. 72 void RecordClassVerified(const DexFile& dex_file, const dex::ClassDef& class_def) 73 REQUIRES(!Locks::verifier_deps_lock_); 74 75 // Record the verification status of the class defined in `class_def`. 76 static void MaybeRecordVerificationStatus(const DexFile& dex_file, 77 const dex::ClassDef& class_def, 78 FailureKind failure_kind) 79 REQUIRES(!Locks::verifier_deps_lock_); 80 81 // Record that class defined in `class_def` was not verified because it redefines 82 // a class with the same descriptor which takes precedence in class resolution. 83 static void MaybeRecordClassRedefinition(const DexFile& dex_file, const dex::ClassDef& class_def) 84 REQUIRES(!Locks::verifier_deps_lock_); 85 86 // Record the outcome `klass` of resolving type `type_idx` from `dex_file`. 87 // If `klass` is null, the class is assumed unresolved. 88 static void MaybeRecordClassResolution(const DexFile& dex_file, 89 dex::TypeIndex type_idx, 90 ObjPtr<mirror::Class> klass) 91 REQUIRES_SHARED(Locks::mutator_lock_) 92 REQUIRES(!Locks::verifier_deps_lock_); 93 94 // Record the outcome `field` of resolving field `field_idx` from `dex_file`. 95 // If `field` is null, the field is assumed unresolved. 96 static void MaybeRecordFieldResolution(const DexFile& dex_file, 97 uint32_t field_idx, 98 ArtField* field) 99 REQUIRES_SHARED(Locks::mutator_lock_) 100 REQUIRES(!Locks::verifier_deps_lock_); 101 102 // Record the outcome `method` of resolving method `method_idx` from `dex_file`. 103 // If `method` is null, the method is assumed unresolved. 104 static void MaybeRecordMethodResolution(const DexFile& dex_file, 105 uint32_t method_idx, 106 ArtMethod* method) 107 REQUIRES_SHARED(Locks::mutator_lock_) 108 REQUIRES(!Locks::verifier_deps_lock_); 109 110 // Record the outcome `is_assignable` of type assignability test from `source` 111 // to `destination` as defined by RegType::AssignableFrom. `dex_file` is the 112 // owner of the method for which MethodVerifier performed the assignability test. 113 static void MaybeRecordAssignability(const DexFile& dex_file, 114 ObjPtr<mirror::Class> destination, 115 ObjPtr<mirror::Class> source, 116 bool is_strict, 117 bool is_assignable) 118 REQUIRES_SHARED(Locks::mutator_lock_) 119 REQUIRES(!Locks::verifier_deps_lock_); 120 121 // Serialize the recorded dependencies and store the data into `buffer`. 122 // `dex_files` provides the order of the dex files in which the dependencies 123 // should be emitted. 124 void Encode(const std::vector<const DexFile*>& dex_files, std::vector<uint8_t>* buffer) const; 125 126 void Dump(VariableIndentationOutputStream* vios) const; 127 128 // Verify the encoded dependencies of this `VerifierDeps` are still valid. 129 bool ValidateDependencies(Thread* self, 130 Handle<mirror::ClassLoader> class_loader, 131 const std::vector<const DexFile*>& classpath, 132 /* out */ std::string* error_msg) const 133 REQUIRES_SHARED(Locks::mutator_lock_); 134 GetVerifiedClasses(const DexFile & dex_file)135 const std::vector<bool>& GetVerifiedClasses(const DexFile& dex_file) const { 136 return GetDexFileDeps(dex_file)->verified_classes_; 137 } 138 GetRedefinedClasses(const DexFile & dex_file)139 const std::vector<bool>& GetRedefinedClasses(const DexFile& dex_file) const { 140 return GetDexFileDeps(dex_file)->redefined_classes_; 141 } 142 OutputOnly()143 bool OutputOnly() const { 144 return output_only_; 145 } 146 147 // Parses raw VerifierDeps data to extract bitvectors of which class def indices 148 // were verified or not. The given `dex_files` must match the order and count of 149 // dex files used to create the VerifierDeps. 150 static std::vector<std::vector<bool>> ParseVerifiedClasses( 151 const std::vector<const DexFile*>& dex_files, 152 ArrayRef<const uint8_t> data); 153 154 private: 155 static constexpr uint16_t kUnresolvedMarker = static_cast<uint16_t>(-1); 156 157 using ClassResolutionBase = std::tuple<dex::TypeIndex, uint16_t>; 158 struct ClassResolution : public ClassResolutionBase { 159 ClassResolution() = default; 160 ClassResolution(const ClassResolution&) = default; ClassResolutionClassResolution161 ClassResolution(dex::TypeIndex type_idx, uint16_t access_flags) 162 : ClassResolutionBase(type_idx, access_flags) {} 163 IsResolvedClassResolution164 bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; } GetDexTypeIndexClassResolution165 dex::TypeIndex GetDexTypeIndex() const { return std::get<0>(*this); } GetAccessFlagsClassResolution166 uint16_t GetAccessFlags() const { return std::get<1>(*this); } 167 }; 168 169 using FieldResolutionBase = std::tuple<uint32_t, uint16_t, dex::StringIndex>; 170 struct FieldResolution : public FieldResolutionBase { 171 FieldResolution() = default; 172 FieldResolution(const FieldResolution&) = default; FieldResolutionFieldResolution173 FieldResolution(uint32_t field_idx, uint16_t access_flags, dex::StringIndex declaring_class_idx) 174 : FieldResolutionBase(field_idx, access_flags, declaring_class_idx) {} 175 IsResolvedFieldResolution176 bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; } GetDexFieldIndexFieldResolution177 uint32_t GetDexFieldIndex() const { return std::get<0>(*this); } GetAccessFlagsFieldResolution178 uint16_t GetAccessFlags() const { return std::get<1>(*this); } GetDeclaringClassIndexFieldResolution179 dex::StringIndex GetDeclaringClassIndex() const { return std::get<2>(*this); } 180 }; 181 182 using MethodResolutionBase = std::tuple<uint32_t, uint16_t, dex::StringIndex>; 183 struct MethodResolution : public MethodResolutionBase { 184 MethodResolution() = default; 185 MethodResolution(const MethodResolution&) = default; MethodResolutionMethodResolution186 MethodResolution(uint32_t method_idx, 187 uint16_t access_flags, 188 dex::StringIndex declaring_class_idx) 189 : MethodResolutionBase(method_idx, access_flags, declaring_class_idx) {} 190 IsResolvedMethodResolution191 bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; } GetDexMethodIndexMethodResolution192 uint32_t GetDexMethodIndex() const { return std::get<0>(*this); } GetAccessFlagsMethodResolution193 uint16_t GetAccessFlags() const { return std::get<1>(*this); } GetDeclaringClassIndexMethodResolution194 dex::StringIndex GetDeclaringClassIndex() const { return std::get<2>(*this); } 195 }; 196 197 using TypeAssignabilityBase = std::tuple<dex::StringIndex, dex::StringIndex>; 198 struct TypeAssignability : public TypeAssignabilityBase { 199 TypeAssignability() = default; 200 TypeAssignability(const TypeAssignability&) = default; TypeAssignabilityTypeAssignability201 TypeAssignability(dex::StringIndex destination_idx, dex::StringIndex source_idx) 202 : TypeAssignabilityBase(destination_idx, source_idx) {} 203 GetDestinationTypeAssignability204 dex::StringIndex GetDestination() const { return std::get<0>(*this); } GetSourceTypeAssignability205 dex::StringIndex GetSource() const { return std::get<1>(*this); } 206 }; 207 208 // Data structure representing dependencies collected during verification of 209 // methods inside one DexFile. 210 struct DexFileDeps { DexFileDepsDexFileDeps211 explicit DexFileDeps(size_t num_class_defs) 212 : verified_classes_(num_class_defs), 213 redefined_classes_(num_class_defs) {} 214 215 // Vector of strings which are not present in the corresponding DEX file. 216 // These are referred to with ids starting with `NumStringIds()` of that DexFile. 217 std::vector<std::string> strings_; 218 219 // Set of class pairs recording the outcome of assignability test from one 220 // of the two types to the other. 221 std::set<TypeAssignability> assignable_types_; 222 std::set<TypeAssignability> unassignable_types_; 223 224 // Sets of recorded class/field/method resolutions. 225 std::set<ClassResolution> classes_; 226 std::set<FieldResolution> fields_; 227 std::set<MethodResolution> methods_; 228 229 // Bit vector indexed by class def indices indicating whether the corresponding 230 // class was successfully verified. 231 std::vector<bool> verified_classes_; 232 233 // Bit vector indexed by class def indices indicating whether the corresponding 234 // class resolved into a different class with the same descriptor (was eclipsed). 235 // The other class might have been both external (not covered by these VerifierDeps) 236 // and internal (same VerifierDeps, different DexFileDeps). 237 std::vector<bool> redefined_classes_; 238 239 bool Equals(const DexFileDeps& rhs) const; 240 }; 241 242 VerifierDeps(const std::vector<const DexFile*>& dex_files, bool output_only); 243 244 // Helper function to share DexFileDeps decoding code. 245 static void DecodeDexFileDeps(DexFileDeps& deps, 246 const uint8_t** data_start, 247 const uint8_t* data_end); 248 249 // Finds the DexFileDep instance associated with `dex_file`, or nullptr if 250 // `dex_file` is not reported as being compiled. 251 DexFileDeps* GetDexFileDeps(const DexFile& dex_file); 252 253 const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const; 254 255 // Returns true if `klass` is null or not defined in any of dex files which 256 // were reported as being compiled. 257 bool IsInClassPath(ObjPtr<mirror::Class> klass) const 258 REQUIRES_SHARED(Locks::mutator_lock_); 259 260 // Finds the class in the classpath that makes `source` inherit` from `destination`. 261 // Returns null if a class defined in the compiled DEX files, and assignable to 262 // `source`, direclty inherits from `destination`. 263 ObjPtr<mirror::Class> FindOneClassPathBoundaryForInterface(ObjPtr<mirror::Class> destination, 264 ObjPtr<mirror::Class> source) const 265 REQUIRES_SHARED(Locks::mutator_lock_); 266 267 // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex 268 // string ID. If not, an ID is assigned to the string and cached in `strings_` 269 // of the corresponding DexFileDeps structure (either provided or inferred from 270 // `dex_file`). 271 dex::StringIndex GetIdFromString(const DexFile& dex_file, const std::string& str) 272 REQUIRES(!Locks::verifier_deps_lock_); 273 274 // Returns the string represented by `id`. 275 std::string GetStringFromId(const DexFile& dex_file, dex::StringIndex string_id) const; 276 277 // Returns the bytecode access flags of `element` (bottom 16 bits), or 278 // `kUnresolvedMarker` if `element` is null. 279 template <typename Ptr> 280 static uint16_t GetAccessFlags(Ptr element) 281 REQUIRES_SHARED(Locks::mutator_lock_); 282 283 // Returns a string ID of the descriptor of the declaring class of `element`, 284 // or `kUnresolvedMarker` if `element` is null. 285 dex::StringIndex GetMethodDeclaringClassStringId(const DexFile& dex_file, 286 uint32_t dex_method_idx, 287 ArtMethod* method) 288 REQUIRES_SHARED(Locks::mutator_lock_); 289 dex::StringIndex GetFieldDeclaringClassStringId(const DexFile& dex_file, 290 uint32_t dex_field_idx, 291 ArtField* field) 292 REQUIRES_SHARED(Locks::mutator_lock_); 293 294 // Returns a string ID of the descriptor of the class. 295 dex::StringIndex GetClassDescriptorStringId(const DexFile& dex_file, ObjPtr<mirror::Class> klass) 296 REQUIRES_SHARED(Locks::mutator_lock_) 297 REQUIRES(!Locks::verifier_deps_lock_); 298 299 void AddClassResolution(const DexFile& dex_file, 300 dex::TypeIndex type_idx, 301 ObjPtr<mirror::Class> klass) 302 REQUIRES_SHARED(Locks::mutator_lock_) 303 REQUIRES(!Locks::verifier_deps_lock_); 304 305 void AddFieldResolution(const DexFile& dex_file, 306 uint32_t field_idx, 307 ArtField* field) 308 REQUIRES_SHARED(Locks::mutator_lock_) 309 REQUIRES(!Locks::verifier_deps_lock_); 310 311 void AddMethodResolution(const DexFile& dex_file, 312 uint32_t method_idx, 313 ArtMethod* method) 314 REQUIRES_SHARED(Locks::mutator_lock_) 315 REQUIRES(!Locks::verifier_deps_lock_); 316 317 void AddAssignability(const DexFile& dex_file, 318 ObjPtr<mirror::Class> destination, 319 ObjPtr<mirror::Class> source, 320 bool is_strict, 321 bool is_assignable) 322 REQUIRES_SHARED(Locks::mutator_lock_); 323 324 bool Equals(const VerifierDeps& rhs) const; 325 326 // Verify `dex_file` according to the `deps`, that is going over each 327 // `DexFileDeps` field, and checking that the recorded information still 328 // holds. 329 bool VerifyDexFile(Handle<mirror::ClassLoader> class_loader, 330 const DexFile& dex_file, 331 const DexFileDeps& deps, 332 const std::vector<const DexFile*>& classpath, 333 Thread* self, 334 /* out */ std::string* error_msg) const 335 REQUIRES_SHARED(Locks::mutator_lock_); 336 337 // Iterates over `dex_files` and tries to find a class def matching `descriptor`. 338 // Returns true if such class def is found. 339 bool IsInDexFiles(const char* descriptor, 340 size_t hash, 341 const std::vector<const DexFile*>& dex_files, 342 /* out */ const DexFile** cp_dex_file) const; 343 344 // Check that classes which are to be verified using these dependencies 345 // are not eclipsed by classes in parent class loaders, e.g. when vdex was 346 // created against SDK stubs and the app redefines a non-public class on 347 // boot classpath, or simply if a class is added during an OTA. In such cases, 348 // dependencies do not include the dependencies on the presumed-internal class 349 // and verification must fail unless the class was recorded to have been 350 // redefined during dependencies' generation too. 351 bool VerifyInternalClasses(const DexFile& dex_file, 352 const std::vector<const DexFile*>& classpath, 353 const std::vector<bool>& verified_classes, 354 const std::vector<bool>& redefined_classes, 355 /* out */ std::string* error_msg) const 356 REQUIRES_SHARED(Locks::mutator_lock_); 357 358 bool VerifyAssignability(Handle<mirror::ClassLoader> class_loader, 359 const DexFile& dex_file, 360 const std::set<TypeAssignability>& assignables, 361 bool expected_assignability, 362 Thread* self, 363 /* out */ std::string* error_msg) const 364 REQUIRES_SHARED(Locks::mutator_lock_); 365 366 // Verify that the set of resolved classes at the point of creation 367 // of this `VerifierDeps` is still the same. 368 bool VerifyClasses(Handle<mirror::ClassLoader> class_loader, 369 const DexFile& dex_file, 370 const std::set<ClassResolution>& classes, 371 Thread* self, 372 /* out */ std::string* error_msg) const 373 REQUIRES_SHARED(Locks::mutator_lock_); 374 375 // Verify that the set of resolved fields at the point of creation 376 // of this `VerifierDeps` is still the same, and each field resolves to the 377 // same field holder and access flags. 378 bool VerifyFields(Handle<mirror::ClassLoader> class_loader, 379 const DexFile& dex_file, 380 const std::set<FieldResolution>& classes, 381 Thread* self, 382 /* out */ std::string* error_msg) const 383 REQUIRES_SHARED(Locks::mutator_lock_) 384 REQUIRES(!Locks::verifier_deps_lock_); 385 386 // Verify that the set of resolved methods at the point of creation 387 // of this `VerifierDeps` is still the same, and each method resolves to the 388 // same method holder, access flags, and invocation kind. 389 bool VerifyMethods(Handle<mirror::ClassLoader> class_loader, 390 const DexFile& dex_file, 391 const std::set<MethodResolution>& methods, 392 Thread* self, 393 /* out */ std::string* error_msg) const 394 REQUIRES_SHARED(Locks::mutator_lock_); 395 396 // Map from DexFiles into dependencies collected from verification of their methods. 397 std::map<const DexFile*, std::unique_ptr<DexFileDeps>> dex_deps_; 398 399 // Output only signifies if we are using the verifier deps to verify or just to generate them. 400 const bool output_only_; 401 402 friend class VerifierDepsTest; 403 ART_FRIEND_TEST(VerifierDepsTest, StringToId); 404 ART_FRIEND_TEST(VerifierDepsTest, EncodeDecode); 405 ART_FRIEND_TEST(VerifierDepsTest, EncodeDecodeMulti); 406 ART_FRIEND_TEST(VerifierDepsTest, VerifyDeps); 407 ART_FRIEND_TEST(VerifierDepsTest, CompilerDriver); 408 }; 409 410 } // namespace verifier 411 } // namespace art 412 413 #endif // ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_ 414