• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2012 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_REGISTER_LINE_H_
18 #define ART_RUNTIME_VERIFIER_REGISTER_LINE_H_
19 
20 #include <limits>
21 #include <memory>
22 #include <vector>
23 
24 #include <android-base/logging.h>
25 
26 #include "base/locks.h"
27 #include "base/safe_map.h"
28 #include "base/scoped_arena_containers.h"
29 
30 namespace art {
31 
32 class Instruction;
33 
34 namespace verifier {
35 
36 class MethodVerifier;
37 class RegType;
38 class RegTypeCache;
39 
40 /*
41  * Register type categories, for type checking.
42  *
43  * The spec says category 1 includes boolean, byte, char, short, int, float, reference, and
44  * returnAddress. Category 2 includes long and double.
45  *
46  * We treat object references separately, so we have "category1nr". We don't support jsr/ret, so
47  * there is no "returnAddress" type.
48  */
49 enum TypeCategory {
50   kTypeCategoryUnknown = 0,
51   kTypeCategory1nr = 1,         // boolean, byte, char, short, int, float
52   kTypeCategory2 = 2,           // long, double
53   kTypeCategoryRef = 3,         // object reference
54 };
55 
56 // What to do with the lock levels when setting the register type.
57 enum class LockOp {
58   kClear,                       // Clear the lock levels recorded.
59   kKeep                         // Leave the lock levels alone.
60 };
61 
62 // During verification, we associate one of these with every "interesting" instruction. We track
63 // the status of all registers, and (if the method has any monitor-enter instructions) maintain a
64 // stack of entered monitors (identified by code unit offset).
65 class RegisterLine {
66  public:
67   using RegisterStackMask = uint32_t;
68   // A map from register to a bit vector of indices into the monitors_ stack.
69   using RegToLockDepthsMap = ScopedArenaSafeMap<uint32_t, RegisterStackMask>;
70 
71   // Maximum number of nested monitors to track before giving up and
72   // taking the slow path.
73   static constexpr size_t kMaxMonitorStackDepth =
74       std::numeric_limits<RegisterStackMask>::digits;
75 
76   // Create a register line of num_regs registers.
77   static RegisterLine* Create(size_t num_regs,
78                               ScopedArenaAllocator& allocator,
79                               RegTypeCache* reg_types);
80 
81   // Implement category-1 "move" instructions. Copy a 32-bit value from "vsrc" to "vdst".
82   void CopyRegister1(MethodVerifier* verifier, uint32_t vdst, uint32_t vsrc, TypeCategory cat)
83       REQUIRES_SHARED(Locks::mutator_lock_);
84 
85   // Implement category-2 "move" instructions. Copy a 64-bit value from "vsrc" to "vdst". This
86   // copies both halves of the register.
87   void CopyRegister2(MethodVerifier* verifier, uint32_t vdst, uint32_t vsrc)
88       REQUIRES_SHARED(Locks::mutator_lock_);
89 
90   // Implement "move-result". Copy the category-1 value from the result register to another
91   // register, and reset the result register.
92   void CopyResultRegister1(MethodVerifier* verifier, uint32_t vdst, bool is_reference)
93       REQUIRES_SHARED(Locks::mutator_lock_);
94 
95   // Implement "move-result-wide". Copy the category-2 value from the result register to another
96   // register, and reset the result register.
97   void CopyResultRegister2(MethodVerifier* verifier, uint32_t vdst)
98       REQUIRES_SHARED(Locks::mutator_lock_);
99 
100   // Set the invisible result register to unknown
101   void SetResultTypeToUnknown(RegTypeCache* reg_types) REQUIRES_SHARED(Locks::mutator_lock_);
102 
103   // Set the type of register N, verifying that the register is valid.  If "newType" is the "Lo"
104   // part of a 64-bit value, register N+1 will be set to "newType+1".
105   // The register index was validated during the static pass, so we don't need to check it here.
106   //
107   // LockOp::kClear should be used by default; it will clear the lock levels associated with the
108   // register. An example is setting the register type because an instruction writes to the
109   // register.
110   // LockOp::kKeep keeps the lock levels of the register and only changes the register type. This
111   // is typical when the underlying value did not change, but we have "different" type information
112   // available now. An example is sharpening types after a check-cast. Note that when given kKeep,
113   // the new_type is dchecked to be a reference type.
114   template <LockOp kLockOp>
115   ALWAYS_INLINE bool SetRegisterType(MethodVerifier* verifier,
116                                      uint32_t vdst,
117                                      const RegType& new_type)
118       REQUIRES_SHARED(Locks::mutator_lock_);
119 
120   bool SetRegisterTypeWide(MethodVerifier* verifier,
121                            uint32_t vdst,
122                            const RegType& new_type1,
123                            const RegType& new_type2)
124       REQUIRES_SHARED(Locks::mutator_lock_);
125 
126   /* Set the type of the "result" register. */
127   void SetResultRegisterType(MethodVerifier* verifier, const RegType& new_type)
128       REQUIRES_SHARED(Locks::mutator_lock_);
129 
130   void SetResultRegisterTypeWide(const RegType& new_type1, const RegType& new_type2)
131       REQUIRES_SHARED(Locks::mutator_lock_);
132 
133   // Get the type of register vsrc.
134   const RegType& GetRegisterType(MethodVerifier* verifier, uint32_t vsrc) const;
135 
136   ALWAYS_INLINE bool VerifyRegisterType(MethodVerifier* verifier,
137                                         uint32_t vsrc,
138                                         const RegType& check_type)
139       REQUIRES_SHARED(Locks::mutator_lock_);
140 
141   bool VerifyRegisterTypeWide(MethodVerifier* verifier,
142                               uint32_t vsrc,
143                               const RegType& check_type1,
144                               const RegType& check_type2)
145       REQUIRES_SHARED(Locks::mutator_lock_);
146 
CopyFromLine(const RegisterLine * src)147   void CopyFromLine(const RegisterLine* src) {
148     DCHECK_EQ(num_regs_, src->num_regs_);
149     memcpy(&line_, &src->line_, num_regs_ * sizeof(uint16_t));
150     monitors_ = src->monitors_;
151     reg_to_lock_depths_ = src->reg_to_lock_depths_;
152     this_initialized_ = src->this_initialized_;
153   }
154 
155   std::string Dump(MethodVerifier* verifier) const REQUIRES_SHARED(Locks::mutator_lock_);
156 
FillWithGarbage()157   void FillWithGarbage() {
158     memset(&line_, 0xf1, num_regs_ * sizeof(uint16_t));
159     monitors_.clear();
160     reg_to_lock_depths_.clear();
161   }
162 
163   /*
164    * We're creating a new instance of class C at address A. Any registers holding instances
165    * previously created at address A must be initialized by now. If not, we mark them as "conflict"
166    * to prevent them from being used (otherwise, MarkRefsAsInitialized would mark the old ones and
167    * the new ones at the same time).
168    */
169   void MarkUninitRefsAsInvalid(MethodVerifier* verifier, const RegType& uninit_type)
170       REQUIRES_SHARED(Locks::mutator_lock_);
171 
172   /*
173    * Update all registers holding "uninit_type" to instead hold the corresponding initialized
174    * reference type. This is called when an appropriate constructor is invoked -- all copies of
175    * the reference must be marked as initialized.
176    */
177   void MarkRefsAsInitialized(MethodVerifier* verifier, const RegType& uninit_type)
178       REQUIRES_SHARED(Locks::mutator_lock_);
179 
180   /*
181    * Update all registers to be Conflict except vsrc.
182    */
183   void MarkAllRegistersAsConflicts(MethodVerifier* verifier);
184   void MarkAllRegistersAsConflictsExcept(MethodVerifier* verifier, uint32_t vsrc);
185   void MarkAllRegistersAsConflictsExceptWide(MethodVerifier* verifier, uint32_t vsrc);
186 
SetThisInitialized()187   void SetThisInitialized() {
188     this_initialized_ = true;
189   }
190 
CopyThisInitialized(const RegisterLine & src)191   void CopyThisInitialized(const RegisterLine& src) {
192     this_initialized_ = src.this_initialized_;
193   }
194 
195   /*
196    * Check constraints on constructor return. Specifically, make sure that the "this" argument got
197    * initialized.
198    * The "this" argument to <init> uses code offset kUninitThisArgAddr, which puts it at the start
199    * of the list in slot 0. If we see a register with an uninitialized slot 0 reference, we know it
200    * somehow didn't get initialized.
201    */
202   bool CheckConstructorReturn(MethodVerifier* verifier) const;
203 
204   // Compare two register lines. Returns 0 if they match.
205   // Using this for a sort is unwise, since the value can change based on machine endianness.
CompareLine(const RegisterLine * line2)206   int CompareLine(const RegisterLine* line2) const {
207     if (monitors_ != line2->monitors_) {
208       return 1;
209     }
210     // TODO: DCHECK(reg_to_lock_depths_ == line2->reg_to_lock_depths_);
211     return memcmp(&line_, &line2->line_, num_regs_ * sizeof(uint16_t));
212   }
213 
NumRegs()214   size_t NumRegs() const {
215     return num_regs_;
216   }
217 
218   // Return how many bytes of memory a register line uses.
219   ALWAYS_INLINE static size_t ComputeSize(size_t num_regs);
220 
221   /*
222    * Get the "this" pointer from a non-static method invocation. This returns the RegType so the
223    * caller can decide whether it needs the reference to be initialized or not. (Can also return
224    * kRegTypeZero if the reference can only be zero at this point.)
225    *
226    * The argument count is in vA, and the first argument is in vC, for both "simple" and "range"
227    * versions. We just need to make sure vA is >= 1 and then return vC.
228    * allow_failure will return Conflict() instead of causing a verification failure if there is an
229    * error.
230    */
231   const RegType& GetInvocationThis(MethodVerifier* verifier,
232                                    const Instruction* inst,
233                                    bool allow_failure = false)
234       REQUIRES_SHARED(Locks::mutator_lock_);
235 
236   /*
237    * Verify types for a simple two-register instruction (e.g. "neg-int").
238    * "dst_type" is stored into vA, and "src_type" is verified against vB.
239    */
240   void CheckUnaryOp(MethodVerifier* verifier,
241                     const Instruction* inst,
242                     const RegType& dst_type,
243                     const RegType& src_type)
244       REQUIRES_SHARED(Locks::mutator_lock_);
245 
246   void CheckUnaryOpWide(MethodVerifier* verifier,
247                         const Instruction* inst,
248                         const RegType& dst_type1,
249                         const RegType& dst_type2,
250                         const RegType& src_type1,
251                         const RegType& src_type2)
252       REQUIRES_SHARED(Locks::mutator_lock_);
253 
254   void CheckUnaryOpToWide(MethodVerifier* verifier,
255                           const Instruction* inst,
256                           const RegType& dst_type1,
257                           const RegType& dst_type2,
258                           const RegType& src_type)
259       REQUIRES_SHARED(Locks::mutator_lock_);
260 
261   void CheckUnaryOpFromWide(MethodVerifier* verifier,
262                             const Instruction* inst,
263                             const RegType& dst_type,
264                             const RegType& src_type1,
265                             const RegType& src_type2)
266       REQUIRES_SHARED(Locks::mutator_lock_);
267 
268   /*
269    * Verify types for a simple three-register instruction (e.g. "add-int").
270    * "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified
271    * against vB/vC.
272    */
273   void CheckBinaryOp(MethodVerifier* verifier,
274                      const Instruction* inst,
275                      const RegType& dst_type,
276                      const RegType& src_type1,
277                      const RegType& src_type2,
278                      bool check_boolean_op)
279       REQUIRES_SHARED(Locks::mutator_lock_);
280 
281   void CheckBinaryOpWide(MethodVerifier* verifier,
282                          const Instruction* inst,
283                          const RegType& dst_type1,
284                          const RegType& dst_type2,
285                          const RegType& src_type1_1,
286                          const RegType& src_type1_2,
287                          const RegType& src_type2_1,
288                          const RegType& src_type2_2)
289       REQUIRES_SHARED(Locks::mutator_lock_);
290 
291   void CheckBinaryOpWideShift(MethodVerifier* verifier,
292                               const Instruction* inst,
293                               const RegType& long_lo_type,
294                               const RegType& long_hi_type,
295                               const RegType& int_type)
296       REQUIRES_SHARED(Locks::mutator_lock_);
297 
298   /*
299    * Verify types for a binary "2addr" operation. "src_type1"/"src_type2"
300    * are verified against vA/vB, then "dst_type" is stored into vA.
301    */
302   void CheckBinaryOp2addr(MethodVerifier* verifier,
303                           const Instruction* inst,
304                           const RegType& dst_type,
305                           const RegType& src_type1,
306                           const RegType& src_type2,
307                           bool check_boolean_op)
308       REQUIRES_SHARED(Locks::mutator_lock_);
309 
310   void CheckBinaryOp2addrWide(MethodVerifier* verifier,
311                               const Instruction* inst,
312                               const RegType& dst_type1,
313                               const RegType& dst_type2,
314                               const RegType& src_type1_1,
315                               const RegType& src_type1_2,
316                               const RegType& src_type2_1,
317                               const RegType& src_type2_2)
318       REQUIRES_SHARED(Locks::mutator_lock_);
319 
320   void CheckBinaryOp2addrWideShift(MethodVerifier* verifier,
321                                    const Instruction* inst,
322                                    const RegType& long_lo_type,
323                                    const RegType& long_hi_type,
324                                    const RegType& int_type)
325       REQUIRES_SHARED(Locks::mutator_lock_);
326 
327   /*
328    * Verify types for A two-register instruction with a literal constant (e.g. "add-int/lit8").
329    * "dst_type" is stored into vA, and "src_type" is verified against vB.
330    *
331    * If "check_boolean_op" is set, we use the constant value in vC.
332    */
333   void CheckLiteralOp(MethodVerifier* verifier,
334                       const Instruction* inst,
335                       const RegType& dst_type,
336                       const RegType& src_type,
337                       bool check_boolean_op,
338                       bool is_lit16)
339       REQUIRES_SHARED(Locks::mutator_lock_);
340 
341   // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx.
342   void PushMonitor(MethodVerifier* verifier, uint32_t reg_idx, int32_t insn_idx)
343       REQUIRES_SHARED(Locks::mutator_lock_);
344 
345   // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked
346   void PopMonitor(MethodVerifier* verifier, uint32_t reg_idx)
347       REQUIRES_SHARED(Locks::mutator_lock_);
348 
349   // Stack of currently held monitors and where they were locked
MonitorStackDepth()350   size_t MonitorStackDepth() const {
351     return monitors_.size();
352   }
353 
354   // We expect no monitors to be held at certain points, such a method returns. Verify the stack
355   // is empty, queueing a LOCKING error else.
356   void VerifyMonitorStackEmpty(MethodVerifier* verifier) const;
357 
358   bool MergeRegisters(MethodVerifier* verifier, const RegisterLine* incoming_line)
359       REQUIRES_SHARED(Locks::mutator_lock_);
360 
GetMonitorEnterCount()361   size_t GetMonitorEnterCount() const {
362     return monitors_.size();
363   }
364 
GetMonitorEnterDexPc(size_t i)365   uint32_t GetMonitorEnterDexPc(size_t i) const {
366     return monitors_[i];
367   }
368 
369   // We give access to the lock depth map to avoid an expensive poll loop for FindLocksAtDexPC.
370   template <typename T>
IterateRegToLockDepths(T fn)371   void IterateRegToLockDepths(T fn) const {
372     for (const auto& pair : reg_to_lock_depths_) {
373       const uint32_t reg = pair.first;
374       uint32_t depths = pair.second;
375       uint32_t depth = 0;
376       while (depths != 0) {
377         if ((depths & 1) != 0) {
378           fn(reg, depth);
379         }
380         depths >>= 1;
381         depth++;
382       }
383     }
384   }
385 
386  private:
CopyRegToLockDepth(size_t dst,size_t src)387   void CopyRegToLockDepth(size_t dst, size_t src) {
388     auto it = reg_to_lock_depths_.find(src);
389     if (it != reg_to_lock_depths_.end()) {
390       reg_to_lock_depths_.Put(dst, it->second);
391     }
392   }
393 
IsSetLockDepth(size_t reg,size_t depth)394   bool IsSetLockDepth(size_t reg, size_t depth) {
395     auto it = reg_to_lock_depths_.find(reg);
396     if (it != reg_to_lock_depths_.end()) {
397       return (it->second & (1 << depth)) != 0;
398     } else {
399       return false;
400     }
401   }
402 
SetRegToLockDepth(size_t reg,size_t depth)403   bool SetRegToLockDepth(size_t reg, size_t depth) {
404     CHECK_LT(depth, kMaxMonitorStackDepth);
405     if (IsSetLockDepth(reg, depth)) {
406       return false;  // Register already holds lock so locking twice is erroneous.
407     }
408     auto it = reg_to_lock_depths_.find(reg);
409     if (it == reg_to_lock_depths_.end()) {
410       reg_to_lock_depths_.Put(reg, 1 << depth);
411     } else {
412       it->second |= (1 << depth);
413     }
414     return true;
415   }
416 
417   void ClearRegToLockDepth(size_t reg, size_t depth);
418 
ClearAllRegToLockDepths(size_t reg)419   void ClearAllRegToLockDepths(size_t reg) {
420     reg_to_lock_depths_.erase(reg);
421   }
422 
423   RegisterLine(size_t num_regs, ScopedArenaAllocator& allocator, RegTypeCache* reg_types);
424 
425   // Storage for the result register's type, valid after an invocation.
426   uint16_t result_[2];
427 
428   // Length of reg_types_
429   const uint32_t num_regs_;
430 
431   // A stack of monitor enter locations.
432   ScopedArenaVector<uint32_t> monitors_;
433 
434   // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor
435   // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a
436   // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5.
437   RegToLockDepthsMap reg_to_lock_depths_;
438 
439   // Whether "this" initialization (a constructor supercall) has happened.
440   bool this_initialized_;
441 
442   // An array of RegType Ids associated with each dex register.
443   uint16_t line_[1];
444 
445   DISALLOW_COPY_AND_ASSIGN(RegisterLine);
446 };
447 
448 class RegisterLineArenaDelete : public ArenaDelete<RegisterLine> {
449  public:
450   void operator()(RegisterLine* ptr) const;
451 };
452 
453 }  // namespace verifier
454 }  // namespace art
455 
456 #endif  // ART_RUNTIME_VERIFIER_REGISTER_LINE_H_
457