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/mutex.h"
26 #include "dex/dex_file_types.h"
27 #include "handle.h"
28 #include "obj_ptr.h"
29 #include "thread.h"
30 #include "verifier_enums.h"  // For MethodVerifier::FailureKind.
31 
32 namespace art {
33 
34 class ArtField;
35 class ArtMethod;
36 class DexFile;
37 class VariableIndentationOutputStream;
38 
39 namespace mirror {
40 class Class;
41 class ClassLoader;
42 }  // namespace mirror
43 
44 namespace verifier {
45 
46 // Verification dependencies collector class used by the MethodVerifier to record
47 // resolution outcomes and type assignability tests of classes/methods/fields
48 // not present in the set of compiled DEX files, that is classes/methods/fields
49 // defined in the classpath.
50 // The compilation driver initializes the class and registers all DEX files
51 // which are being compiled. Classes defined in DEX files outside of this set
52 // (or synthesized classes without associated DEX files) are considered being
53 // in the classpath.
54 // During code-flow verification, the MethodVerifier informs VerifierDeps
55 // about the outcome of every resolution and assignability test, and
56 // the VerifierDeps object records them if their outcome may change with
57 // changes in the classpath.
58 class VerifierDeps {
59  public:
60   explicit VerifierDeps(const std::vector<const DexFile*>& dex_files);
61 
62   VerifierDeps(const std::vector<const DexFile*>& dex_files, ArrayRef<const uint8_t> data);
63 
64   // Merge `other` into this `VerifierDeps`'. `other` and `this` must be for the
65   // same set of dex files.
66   void MergeWith(const VerifierDeps& other, const std::vector<const DexFile*>& dex_files);
67 
68   // Record the verification status of the class at `type_idx`.
69   static void MaybeRecordVerificationStatus(const DexFile& dex_file,
70                                             dex::TypeIndex type_idx,
71                                             FailureKind failure_kind)
72       REQUIRES(!Locks::verifier_deps_lock_);
73 
74   // Record the outcome `klass` of resolving type `type_idx` from `dex_file`.
75   // If `klass` is null, the class is assumed unresolved.
76   static void MaybeRecordClassResolution(const DexFile& dex_file,
77                                          dex::TypeIndex type_idx,
78                                          mirror::Class* klass)
79       REQUIRES_SHARED(Locks::mutator_lock_)
80       REQUIRES(!Locks::verifier_deps_lock_);
81 
82   // Record the outcome `field` of resolving field `field_idx` from `dex_file`.
83   // If `field` is null, the field is assumed unresolved.
84   static void MaybeRecordFieldResolution(const DexFile& dex_file,
85                                          uint32_t field_idx,
86                                          ArtField* field)
87       REQUIRES_SHARED(Locks::mutator_lock_)
88       REQUIRES(!Locks::verifier_deps_lock_);
89 
90   // Record the outcome `method` of resolving method `method_idx` from `dex_file`.
91   // If `method` is null, the method is assumed unresolved.
92   static void MaybeRecordMethodResolution(const DexFile& dex_file,
93                                           uint32_t method_idx,
94                                           ArtMethod* method)
95       REQUIRES_SHARED(Locks::mutator_lock_)
96       REQUIRES(!Locks::verifier_deps_lock_);
97 
98   // Record the outcome `is_assignable` of type assignability test from `source`
99   // to `destination` as defined by RegType::AssignableFrom. `dex_file` is the
100   // owner of the method for which MethodVerifier performed the assignability test.
101   static void MaybeRecordAssignability(const DexFile& dex_file,
102                                        mirror::Class* destination,
103                                        mirror::Class* source,
104                                        bool is_strict,
105                                        bool is_assignable)
106       REQUIRES_SHARED(Locks::mutator_lock_)
107       REQUIRES(!Locks::verifier_deps_lock_);
108 
109   // Serialize the recorded dependencies and store the data into `buffer`.
110   // `dex_files` provides the order of the dex files in which the dependencies
111   // should be emitted.
112   void Encode(const std::vector<const DexFile*>& dex_files, std::vector<uint8_t>* buffer) const;
113 
114   void Dump(VariableIndentationOutputStream* vios) const;
115 
116   // Verify the encoded dependencies of this `VerifierDeps` are still valid.
117   bool ValidateDependencies(Handle<mirror::ClassLoader> class_loader, Thread* self) const
118       REQUIRES_SHARED(Locks::mutator_lock_);
119 
GetUnverifiedClasses(const DexFile & dex_file)120   const std::set<dex::TypeIndex>& GetUnverifiedClasses(const DexFile& dex_file) const {
121     return GetDexFileDeps(dex_file)->unverified_classes_;
122   }
123 
OutputOnly()124   bool OutputOnly() const {
125     return output_only_;
126   }
127 
128  private:
129   static constexpr uint16_t kUnresolvedMarker = static_cast<uint16_t>(-1);
130 
131   using ClassResolutionBase = std::tuple<dex::TypeIndex, uint16_t>;
132   struct ClassResolution : public ClassResolutionBase {
133     ClassResolution() = default;
134     ClassResolution(const ClassResolution&) = default;
ClassResolutionClassResolution135     ClassResolution(dex::TypeIndex type_idx, uint16_t access_flags)
136         : ClassResolutionBase(type_idx, access_flags) {}
137 
IsResolvedClassResolution138     bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
GetDexTypeIndexClassResolution139     dex::TypeIndex GetDexTypeIndex() const { return std::get<0>(*this); }
GetAccessFlagsClassResolution140     uint16_t GetAccessFlags() const { return std::get<1>(*this); }
141   };
142 
143   using FieldResolutionBase = std::tuple<uint32_t, uint16_t, dex::StringIndex>;
144   struct FieldResolution : public FieldResolutionBase {
145     FieldResolution() = default;
146     FieldResolution(const FieldResolution&) = default;
FieldResolutionFieldResolution147     FieldResolution(uint32_t field_idx, uint16_t access_flags, dex::StringIndex declaring_class_idx)
148         : FieldResolutionBase(field_idx, access_flags, declaring_class_idx) {}
149 
IsResolvedFieldResolution150     bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
GetDexFieldIndexFieldResolution151     uint32_t GetDexFieldIndex() const { return std::get<0>(*this); }
GetAccessFlagsFieldResolution152     uint16_t GetAccessFlags() const { return std::get<1>(*this); }
GetDeclaringClassIndexFieldResolution153     dex::StringIndex GetDeclaringClassIndex() const { return std::get<2>(*this); }
154   };
155 
156   using MethodResolutionBase = std::tuple<uint32_t, uint16_t, dex::StringIndex>;
157   struct MethodResolution : public MethodResolutionBase {
158     MethodResolution() = default;
159     MethodResolution(const MethodResolution&) = default;
MethodResolutionMethodResolution160     MethodResolution(uint32_t method_idx,
161                      uint16_t access_flags,
162                      dex::StringIndex declaring_class_idx)
163         : MethodResolutionBase(method_idx, access_flags, declaring_class_idx) {}
164 
IsResolvedMethodResolution165     bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
GetDexMethodIndexMethodResolution166     uint32_t GetDexMethodIndex() const { return std::get<0>(*this); }
GetAccessFlagsMethodResolution167     uint16_t GetAccessFlags() const { return std::get<1>(*this); }
GetDeclaringClassIndexMethodResolution168     dex::StringIndex GetDeclaringClassIndex() const { return std::get<2>(*this); }
169   };
170 
171   using TypeAssignabilityBase = std::tuple<dex::StringIndex, dex::StringIndex>;
172   struct TypeAssignability : public TypeAssignabilityBase {
173     TypeAssignability() = default;
174     TypeAssignability(const TypeAssignability&) = default;
TypeAssignabilityTypeAssignability175     TypeAssignability(dex::StringIndex destination_idx, dex::StringIndex source_idx)
176         : TypeAssignabilityBase(destination_idx, source_idx) {}
177 
GetDestinationTypeAssignability178     dex::StringIndex GetDestination() const { return std::get<0>(*this); }
GetSourceTypeAssignability179     dex::StringIndex GetSource() const { return std::get<1>(*this); }
180   };
181 
182   // Data structure representing dependencies collected during verification of
183   // methods inside one DexFile.
184   struct DexFileDeps {
185     // Vector of strings which are not present in the corresponding DEX file.
186     // These are referred to with ids starting with `NumStringIds()` of that DexFile.
187     std::vector<std::string> strings_;
188 
189     // Set of class pairs recording the outcome of assignability test from one
190     // of the two types to the other.
191     std::set<TypeAssignability> assignable_types_;
192     std::set<TypeAssignability> unassignable_types_;
193 
194     // Sets of recorded class/field/method resolutions.
195     std::set<ClassResolution> classes_;
196     std::set<FieldResolution> fields_;
197     std::set<MethodResolution> methods_;
198 
199     // List of classes that were not fully verified in that dex file.
200     std::set<dex::TypeIndex> unverified_classes_;
201 
202     bool Equals(const DexFileDeps& rhs) const;
203   };
204 
205   VerifierDeps(const std::vector<const DexFile*>& dex_files, bool output_only);
206 
207   // Finds the DexFileDep instance associated with `dex_file`, or nullptr if
208   // `dex_file` is not reported as being compiled.
209   DexFileDeps* GetDexFileDeps(const DexFile& dex_file);
210 
211   const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const;
212 
213   // Returns true if `klass` is null or not defined in any of dex files which
214   // were reported as being compiled.
215   bool IsInClassPath(ObjPtr<mirror::Class> klass) const
216       REQUIRES_SHARED(Locks::mutator_lock_);
217 
218   // Finds the class in the classpath that makes `source` inherit` from `destination`.
219   // Returns null if a class defined in the compiled DEX files, and assignable to
220   // `source`, direclty inherits from `destination`.
221   mirror::Class* FindOneClassPathBoundaryForInterface(mirror::Class* destination,
222                                                       mirror::Class* source) const
223       REQUIRES_SHARED(Locks::mutator_lock_);
224 
225   // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex
226   // string ID. If not, an ID is assigned to the string and cached in `strings_`
227   // of the corresponding DexFileDeps structure (either provided or inferred from
228   // `dex_file`).
229   dex::StringIndex GetIdFromString(const DexFile& dex_file, const std::string& str)
230       REQUIRES(!Locks::verifier_deps_lock_);
231 
232   // Returns the string represented by `id`.
233   std::string GetStringFromId(const DexFile& dex_file, dex::StringIndex string_id) const;
234 
235   // Returns the bytecode access flags of `element` (bottom 16 bits), or
236   // `kUnresolvedMarker` if `element` is null.
237   template <typename T>
238   static uint16_t GetAccessFlags(T* element)
239       REQUIRES_SHARED(Locks::mutator_lock_);
240 
241   // Returns a string ID of the descriptor of the declaring class of `element`,
242   // or `kUnresolvedMarker` if `element` is null.
243   dex::StringIndex GetMethodDeclaringClassStringId(const DexFile& dex_file,
244                                                    uint32_t dex_method_idx,
245                                                    ArtMethod* method)
246       REQUIRES_SHARED(Locks::mutator_lock_);
247   dex::StringIndex GetFieldDeclaringClassStringId(const DexFile& dex_file,
248                                                   uint32_t dex_field_idx,
249                                                   ArtField* field)
250       REQUIRES_SHARED(Locks::mutator_lock_);
251 
252   // Returns a string ID of the descriptor of the class.
253   dex::StringIndex GetClassDescriptorStringId(const DexFile& dex_file, ObjPtr<mirror::Class> klass)
254       REQUIRES_SHARED(Locks::mutator_lock_)
255       REQUIRES(!Locks::verifier_deps_lock_);
256 
257   void AddClassResolution(const DexFile& dex_file,
258                           dex::TypeIndex type_idx,
259                           mirror::Class* klass)
260       REQUIRES_SHARED(Locks::mutator_lock_)
261       REQUIRES(!Locks::verifier_deps_lock_);
262 
263   void AddFieldResolution(const DexFile& dex_file,
264                           uint32_t field_idx,
265                           ArtField* field)
266       REQUIRES_SHARED(Locks::mutator_lock_)
267       REQUIRES(!Locks::verifier_deps_lock_);
268 
269   void AddMethodResolution(const DexFile& dex_file,
270                            uint32_t method_idx,
271                            ArtMethod* method)
272       REQUIRES_SHARED(Locks::mutator_lock_)
273       REQUIRES(!Locks::verifier_deps_lock_);
274 
275   void AddAssignability(const DexFile& dex_file,
276                         mirror::Class* destination,
277                         mirror::Class* source,
278                         bool is_strict,
279                         bool is_assignable)
280       REQUIRES_SHARED(Locks::mutator_lock_);
281 
282   bool Equals(const VerifierDeps& rhs) const;
283 
284   // Verify `dex_file` according to the `deps`, that is going over each
285   // `DexFileDeps` field, and checking that the recorded information still
286   // holds.
287   bool VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
288                      const DexFile& dex_file,
289                      const DexFileDeps& deps,
290                      Thread* self) const
291       REQUIRES_SHARED(Locks::mutator_lock_);
292 
293   bool VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
294                            const DexFile& dex_file,
295                            const std::set<TypeAssignability>& assignables,
296                            bool expected_assignability,
297                            Thread* self) const
298       REQUIRES_SHARED(Locks::mutator_lock_);
299 
300   // Verify that the set of resolved classes at the point of creation
301   // of this `VerifierDeps` is still the same.
302   bool VerifyClasses(Handle<mirror::ClassLoader> class_loader,
303                      const DexFile& dex_file,
304                      const std::set<ClassResolution>& classes,
305                      Thread* self) const
306       REQUIRES_SHARED(Locks::mutator_lock_);
307 
308   // Verify that the set of resolved fields at the point of creation
309   // of this `VerifierDeps` is still the same, and each field resolves to the
310   // same field holder and access flags.
311   bool VerifyFields(Handle<mirror::ClassLoader> class_loader,
312                     const DexFile& dex_file,
313                     const std::set<FieldResolution>& classes,
314                     Thread* self) const
315       REQUIRES_SHARED(Locks::mutator_lock_)
316       REQUIRES(!Locks::verifier_deps_lock_);
317 
318   // Verify that the set of resolved methods at the point of creation
319   // of this `VerifierDeps` is still the same, and each method resolves to the
320   // same method holder, access flags, and invocation kind.
321   bool VerifyMethods(Handle<mirror::ClassLoader> class_loader,
322                      const DexFile& dex_file,
323                      const std::set<MethodResolution>& methods,
324                      Thread* self) const
325       REQUIRES_SHARED(Locks::mutator_lock_);
326 
327   // Map from DexFiles into dependencies collected from verification of their methods.
328   std::map<const DexFile*, std::unique_ptr<DexFileDeps>> dex_deps_;
329 
330   // Output only signifies if we are using the verifier deps to verify or just to generate them.
331   const bool output_only_;
332 
333   friend class VerifierDepsTest;
334   ART_FRIEND_TEST(VerifierDepsTest, StringToId);
335   ART_FRIEND_TEST(VerifierDepsTest, EncodeDecode);
336   ART_FRIEND_TEST(VerifierDepsTest, EncodeDecodeMulti);
337   ART_FRIEND_TEST(VerifierDepsTest, VerifyDeps);
338   ART_FRIEND_TEST(VerifierDepsTest, CompilerDriver);
339 };
340 
341 }  // namespace verifier
342 }  // namespace art
343 
344 #endif  // ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_
345