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 class RegType;
48 
49 // Verification dependencies collector class used by the MethodVerifier to record
50 // resolution outcomes and type assignability tests of classes/methods/fields
51 // not present in the set of compiled DEX files, that is classes/methods/fields
52 // defined in the classpath.
53 // The compilation driver initializes the class and registers all DEX files
54 // which are being compiled. Classes defined in DEX files outside of this set
55 // (or synthesized classes without associated DEX files) are considered being
56 // in the classpath.
57 // During code-flow verification, the MethodVerifier informs VerifierDeps
58 // about the outcome of every resolution and assignability test, and
59 // the VerifierDeps object records them if their outcome may change with
60 // changes in the classpath.
61 class VerifierDeps {
62  public:
63   explicit VerifierDeps(const std::vector<const DexFile*>& dex_files, bool output_only = true);
64 
65   // Marker to know whether a class is verified. A non-verified class will have
66   // this marker as its offset entry in the encoded data.
67   static uint32_t constexpr kNotVerifiedMarker = std::numeric_limits<uint32_t>::max();
68 
69   // Fill dependencies from stored data. Returns true on success, false on failure.
70   bool ParseStoredData(const std::vector<const DexFile*>& dex_files, ArrayRef<const uint8_t> data);
71 
72   // Merge `other` into this `VerifierDeps`'. `other` and `this` must be for the
73   // same set of dex files.
74   void MergeWith(std::unique_ptr<VerifierDeps> other, const std::vector<const DexFile*>& dex_files);
75 
76   // Record information that a class was verified.
77   // Note that this function is different from MaybeRecordVerificationStatus() which
78   // looks up thread-local VerifierDeps first.
79   void RecordClassVerified(const DexFile& dex_file, const dex::ClassDef& class_def)
80       REQUIRES(!Locks::verifier_deps_lock_);
81 
82   // Record the verification status of the class defined in `class_def`.
83   static void MaybeRecordVerificationStatus(VerifierDeps* verifier_deps,
84                                             const DexFile& dex_file,
85                                             const dex::ClassDef& class_def,
86                                             FailureKind failure_kind)
87       REQUIRES(!Locks::verifier_deps_lock_);
88 
89   // Record the outcome `is_assignable` of type assignability test from `source`
90   // to `destination` as defined by RegType::AssignableFrom. `dex_file` is the
91   // owner of the method for which MethodVerifier performed the assignability test.
92   static void MaybeRecordAssignability(VerifierDeps* verifier_deps,
93                                        const DexFile& dex_file,
94                                        const dex::ClassDef& class_def,
95                                        ObjPtr<mirror::Class> destination,
96                                        ObjPtr<mirror::Class> source)
97       REQUIRES_SHARED(Locks::mutator_lock_)
98       REQUIRES(!Locks::verifier_deps_lock_);
99 
100   // Record that `source` is assignable to `destination`. `dex_file` is the
101   // owner of the method for which MethodVerifier performed the assignability test.
102   static void MaybeRecordAssignability(VerifierDeps* verifier_deps,
103                                        const DexFile& dex_file,
104                                        const dex::ClassDef& class_def,
105                                        const RegType& destination,
106                                        const RegType& source)
107       REQUIRES_SHARED(Locks::mutator_lock_)
108       REQUIRES(!Locks::verifier_deps_lock_);
109 
110   // Serialize the recorded dependencies and store the data into `buffer`.
111   // `dex_files` provides the order of the dex files in which the dependencies
112   // should be emitted.
113   void Encode(const std::vector<const DexFile*>& dex_files, std::vector<uint8_t>* buffer) const;
114 
115   void Dump(VariableIndentationOutputStream* vios) const;
116 
117   // Verify the encoded dependencies of this `VerifierDeps` are still valid.
118   bool ValidateDependencies(Thread* self,
119                             Handle<mirror::ClassLoader> class_loader,
120                             /* out */ std::string* error_msg) const
121       REQUIRES_SHARED(Locks::mutator_lock_);
122 
GetVerifiedClasses(const DexFile & dex_file)123   const std::vector<bool>& GetVerifiedClasses(const DexFile& dex_file) const {
124     return GetDexFileDeps(dex_file)->verified_classes_;
125   }
126 
127   // Whether this `verifier_deps` has recorded that the given class is verified.
128   bool HasRecordedVerifiedStatus(const DexFile& dex_file, const dex::ClassDef& class_def)
129       REQUIRES(!Locks::verifier_deps_lock_);
130 
OutputOnly()131   bool OutputOnly() const {
132     return output_only_;
133   }
134 
ContainsDexFile(const DexFile & dex_file)135   bool ContainsDexFile(const DexFile& dex_file) const {
136     return GetDexFileDeps(dex_file) != nullptr;
137   }
138 
139   // Parses raw VerifierDeps data to extract bitvectors of which class def indices
140   // were verified or not. The given `dex_files` must match the order and count of
141   // dex files used to create the VerifierDeps.
142   static bool ParseVerifiedClasses(
143       const std::vector<const DexFile*>& dex_files,
144       ArrayRef<const uint8_t> data,
145       /*out*/std::vector<std::vector<bool>>* verified_classes_per_dex);
146 
147   using TypeAssignabilityBase = std::tuple<dex::StringIndex, dex::StringIndex>;
148   struct TypeAssignability : public TypeAssignabilityBase {
149     TypeAssignability() = default;
150     TypeAssignability(const TypeAssignability&) = default;
TypeAssignabilityTypeAssignability151     TypeAssignability(dex::StringIndex destination_idx, dex::StringIndex source_idx)
152         : TypeAssignabilityBase(destination_idx, source_idx) {}
153 
GetDestinationTypeAssignability154     dex::StringIndex GetDestination() const { return std::get<0>(*this); }
GetSourceTypeAssignability155     dex::StringIndex GetSource() const { return std::get<1>(*this); }
156   };
157 
158  private:
159   // Data structure representing dependencies collected during verification of
160   // methods inside one DexFile.
161   struct DexFileDeps {
DexFileDepsDexFileDeps162     explicit DexFileDeps(size_t num_class_defs)
163         : assignable_types_(num_class_defs),
164           verified_classes_(num_class_defs) {}
165 
166     // Vector of strings which are not present in the corresponding DEX file.
167     // These are referred to with ids starting with `NumStringIds()` of that DexFile.
168     std::vector<std::string> strings_;
169 
170     // Vector that contains for each class def defined in a dex file, a set of class pairs recording
171     // the outcome of assignability test from one of the two types to the other.
172     std::vector<std::set<TypeAssignability>> assignable_types_;
173 
174     // Bit vector indexed by class def indices indicating whether the corresponding
175     // class was successfully verified.
176     std::vector<bool> verified_classes_;
177 
178     bool Equals(const DexFileDeps& rhs) const;
179   };
180 
181   // Helper function to share DexFileDeps decoding code.
182   // Returns true on success, false on failure.
183   template <bool kOnlyVerifiedClasses>
184   static bool DecodeDexFileDeps(DexFileDeps& deps,
185                                 const uint8_t** cursor,
186                                 const uint8_t* data_start,
187                                 const uint8_t* data_end,
188                                 size_t num_class_defs);
189 
190   // Finds the DexFileDep instance associated with `dex_file`, or nullptr if
191   // `dex_file` is not reported as being compiled.
192   DexFileDeps* GetDexFileDeps(const DexFile& dex_file);
193 
194   const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const;
195 
196   // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex
197   // string ID. If not, an ID is assigned to the string and cached in `strings_`
198   // of the corresponding DexFileDeps structure (either provided or inferred from
199   // `dex_file`).
200   dex::StringIndex GetIdFromString(const DexFile& dex_file, const std::string& str)
201       REQUIRES(!Locks::verifier_deps_lock_);
202 
203   // Returns the string represented by `id`.
204   std::string GetStringFromId(const DexFile& dex_file, dex::StringIndex string_id) const;
205 
206   // Returns a string ID of the descriptor of the class.
207   dex::StringIndex GetClassDescriptorStringId(const DexFile& dex_file, ObjPtr<mirror::Class> klass)
208       REQUIRES_SHARED(Locks::mutator_lock_)
209       REQUIRES(!Locks::verifier_deps_lock_);
210 
211   void AddAssignability(const DexFile& dex_file,
212                         const dex::ClassDef& class_def,
213                         ObjPtr<mirror::Class> destination,
214                         ObjPtr<mirror::Class> source)
215       REQUIRES_SHARED(Locks::mutator_lock_);
216 
217   void AddAssignability(const DexFile& dex_file,
218                         const dex::ClassDef& class_def,
219                         const RegType& destination,
220                         const RegType& source)
221       REQUIRES_SHARED(Locks::mutator_lock_);
222 
223   bool Equals(const VerifierDeps& rhs) const;
224 
225   // Verify `dex_file` according to the `deps`, that is going over each
226   // `DexFileDeps` field, and checking that the recorded information still
227   // holds.
228   bool VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
229                      const DexFile& dex_file,
230                      const DexFileDeps& deps,
231                      Thread* self,
232                      /* out */ std::string* error_msg) const
233       REQUIRES_SHARED(Locks::mutator_lock_);
234 
235   // Iterates over `dex_files` and tries to find a class def matching `descriptor`.
236   // Returns true if such class def is found.
237   bool IsInDexFiles(const char* descriptor,
238                     size_t hash,
239                     const std::vector<const DexFile*>& dex_files,
240                     /* out */ const DexFile** cp_dex_file) const;
241 
242   bool VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
243                            const DexFile& dex_file,
244                            const std::vector<std::set<TypeAssignability>>& assignables,
245                            Thread* self,
246                            /* out */ std::string* error_msg) const
247       REQUIRES_SHARED(Locks::mutator_lock_);
248 
249   // Map from DexFiles into dependencies collected from verification of their methods.
250   std::map<const DexFile*, std::unique_ptr<DexFileDeps>> dex_deps_;
251 
252   // Output only signifies if we are using the verifier deps to verify or just to generate them.
253   const bool output_only_;
254 
255   friend class VerifierDepsTest;
256   ART_FRIEND_TEST(VerifierDepsTest, StringToId);
257   ART_FRIEND_TEST(VerifierDepsTest, EncodeDecode);
258   ART_FRIEND_TEST(VerifierDepsTest, EncodeDecodeMulti);
259   ART_FRIEND_TEST(VerifierDepsTest, VerifyDeps);
260   ART_FRIEND_TEST(VerifierDepsTest, CompilerDriver);
261 };
262 
263 }  // namespace verifier
264 }  // namespace art
265 
266 #endif  // ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_
267