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