• 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 <deque>
21 #include <vector>
22 
23 #include "dex_instruction.h"
24 #include "reg_type.h"
25 #include "safe_map.h"
26 #include "UniquePtr.h"
27 
28 namespace art {
29 namespace verifier {
30 
31 class MethodVerifier;
32 
33 /*
34  * Register type categories, for type checking.
35  *
36  * The spec says category 1 includes boolean, byte, char, short, int, float, reference, and
37  * returnAddress. Category 2 includes long and double.
38  *
39  * We treat object references separately, so we have "category1nr". We don't support jsr/ret, so
40  * there is no "returnAddress" type.
41  */
42 enum TypeCategory {
43   kTypeCategoryUnknown = 0,
44   kTypeCategory1nr = 1,         // boolean, byte, char, short, int, float
45   kTypeCategory2 = 2,           // long, double
46   kTypeCategoryRef = 3,         // object reference
47 };
48 
49 // During verification, we associate one of these with every "interesting" instruction. We track
50 // the status of all registers, and (if the method has any monitor-enter instructions) maintain a
51 // stack of entered monitors (identified by code unit offset).
52 class RegisterLine {
53  public:
RegisterLine(size_t num_regs,MethodVerifier * verifier)54   RegisterLine(size_t num_regs, MethodVerifier* verifier)
55       : line_(new uint16_t[num_regs]),
56         verifier_(verifier),
57         num_regs_(num_regs) {
58     memset(line_.get(), 0, num_regs_ * sizeof(uint16_t));
59     SetResultTypeToUnknown();
60   }
61 
62   // Implement category-1 "move" instructions. Copy a 32-bit value from "vsrc" to "vdst".
63   void CopyRegister1(uint32_t vdst, uint32_t vsrc, TypeCategory cat)
64       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
65 
66   // Implement category-2 "move" instructions. Copy a 64-bit value from "vsrc" to "vdst". This
67   // copies both halves of the register.
68   void CopyRegister2(uint32_t vdst, uint32_t vsrc)
69       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
70 
71   // Implement "move-result". Copy the category-1 value from the result register to another
72   // register, and reset the result register.
73   void CopyResultRegister1(uint32_t vdst, bool is_reference)
74       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
75 
76   // Implement "move-result-wide". Copy the category-2 value from the result register to another
77   // register, and reset the result register.
78   void CopyResultRegister2(uint32_t vdst)
79       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
80 
81   // Set the invisible result register to unknown
82   void SetResultTypeToUnknown() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
83 
84   // Set the type of register N, verifying that the register is valid.  If "newType" is the "Lo"
85   // part of a 64-bit value, register N+1 will be set to "newType+1".
86   // The register index was validated during the static pass, so we don't need to check it here.
87   bool SetRegisterType(uint32_t vdst, const RegType& new_type)
88       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
89 
90   bool SetRegisterTypeWide(uint32_t vdst, const RegType& new_type1, const RegType& new_type2)
91       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
92 
93   /* Set the type of the "result" register. */
94   void SetResultRegisterType(const RegType& new_type)
95       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
96 
97   void SetResultRegisterTypeWide(const RegType& new_type1, const RegType& new_type2)
98       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
99 
100   // Get the type of register vsrc.
101   const RegType& GetRegisterType(uint32_t vsrc) const;
102 
103   bool VerifyRegisterType(uint32_t vsrc, const RegType& check_type)
104       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
105 
106   bool VerifyRegisterTypeWide(uint32_t vsrc, const RegType& check_type1, const RegType& check_type2)
107       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
108 
CopyFromLine(const RegisterLine * src)109   void CopyFromLine(const RegisterLine* src) {
110     DCHECK_EQ(num_regs_, src->num_regs_);
111     memcpy(line_.get(), src->line_.get(), num_regs_ * sizeof(uint16_t));
112     monitors_ = src->monitors_;
113     reg_to_lock_depths_ = src->reg_to_lock_depths_;
114   }
115 
116   std::string Dump() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
117 
FillWithGarbage()118   void FillWithGarbage() {
119     memset(line_.get(), 0xf1, num_regs_ * sizeof(uint16_t));
120     while (!monitors_.empty()) {
121       monitors_.pop_back();
122     }
123     reg_to_lock_depths_.clear();
124   }
125 
126   /*
127    * We're creating a new instance of class C at address A. Any registers holding instances
128    * previously created at address A must be initialized by now. If not, we mark them as "conflict"
129    * to prevent them from being used (otherwise, MarkRefsAsInitialized would mark the old ones and
130    * the new ones at the same time).
131    */
132   void MarkUninitRefsAsInvalid(const RegType& uninit_type)
133       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
134 
135   /*
136    * Update all registers holding "uninit_type" to instead hold the corresponding initialized
137    * reference type. This is called when an appropriate constructor is invoked -- all copies of
138    * the reference must be marked as initialized.
139    */
140   void MarkRefsAsInitialized(const RegType& uninit_type)
141       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
142 
143   /*
144    * Update all registers to be Conflict except vsrc.
145    */
146   void MarkAllRegistersAsConflicts();
147   void MarkAllRegistersAsConflictsExcept(uint32_t vsrc);
148   void MarkAllRegistersAsConflictsExceptWide(uint32_t vsrc);
149 
150   /*
151    * Check constraints on constructor return. Specifically, make sure that the "this" argument got
152    * initialized.
153    * The "this" argument to <init> uses code offset kUninitThisArgAddr, which puts it at the start
154    * of the list in slot 0. If we see a register with an uninitialized slot 0 reference, we know it
155    * somehow didn't get initialized.
156    */
157   bool CheckConstructorReturn() const;
158 
159   // Compare two register lines. Returns 0 if they match.
160   // Using this for a sort is unwise, since the value can change based on machine endianness.
CompareLine(const RegisterLine * line2)161   int CompareLine(const RegisterLine* line2) const {
162     DCHECK(monitors_ == line2->monitors_);
163     // TODO: DCHECK(reg_to_lock_depths_ == line2->reg_to_lock_depths_);
164     return memcmp(line_.get(), line2->line_.get(), num_regs_ * sizeof(uint16_t));
165   }
166 
NumRegs()167   size_t NumRegs() const {
168     return num_regs_;
169   }
170 
171   /*
172    * Get the "this" pointer from a non-static method invocation. This returns the RegType so the
173    * caller can decide whether it needs the reference to be initialized or not. (Can also return
174    * kRegTypeZero if the reference can only be zero at this point.)
175    *
176    * The argument count is in vA, and the first argument is in vC, for both "simple" and "range"
177    * versions. We just need to make sure vA is >= 1 and then return vC.
178    */
179   const RegType& GetInvocationThis(const Instruction* inst, bool is_range)
180       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
181 
182   /*
183    * Verify types for a simple two-register instruction (e.g. "neg-int").
184    * "dst_type" is stored into vA, and "src_type" is verified against vB.
185    */
186   void CheckUnaryOp(const Instruction* inst, const RegType& dst_type,
187                     const RegType& src_type)
188       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
189 
190   void CheckUnaryOpWide(const Instruction* inst,
191                         const RegType& dst_type1, const RegType& dst_type2,
192                         const RegType& src_type1, const RegType& src_type2)
193       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
194 
195   void CheckUnaryOpToWide(const Instruction* inst,
196                           const RegType& dst_type1, const RegType& dst_type2,
197                           const RegType& src_type)
198       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
199 
200   void CheckUnaryOpFromWide(const Instruction* inst,
201                             const RegType& dst_type,
202                             const RegType& src_type1, const RegType& src_type2)
203       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
204 
205   /*
206    * Verify types for a simple three-register instruction (e.g. "add-int").
207    * "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified
208    * against vB/vC.
209    */
210   void CheckBinaryOp(const Instruction* inst,
211                      const RegType& dst_type, const RegType& src_type1, const RegType& src_type2,
212                      bool check_boolean_op)
213       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
214 
215   void CheckBinaryOpWide(const Instruction* inst,
216                          const RegType& dst_type1, const RegType& dst_type2,
217                          const RegType& src_type1_1, const RegType& src_type1_2,
218                          const RegType& src_type2_1, const RegType& src_type2_2)
219       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
220 
221   void CheckBinaryOpWideShift(const Instruction* inst,
222                               const RegType& long_lo_type, const RegType& long_hi_type,
223                               const RegType& int_type)
224       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
225 
226   /*
227    * Verify types for a binary "2addr" operation. "src_type1"/"src_type2"
228    * are verified against vA/vB, then "dst_type" is stored into vA.
229    */
230   void CheckBinaryOp2addr(const Instruction* inst,
231                           const RegType& dst_type,
232                           const RegType& src_type1, const RegType& src_type2,
233                           bool check_boolean_op)
234       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
235 
236   void CheckBinaryOp2addrWide(const Instruction* inst,
237                               const RegType& dst_type1, const RegType& dst_type2,
238                               const RegType& src_type1_1, const RegType& src_type1_2,
239                               const RegType& src_type2_1, const RegType& src_type2_2)
240       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
241 
242   void CheckBinaryOp2addrWideShift(const Instruction* inst,
243                                    const RegType& long_lo_type, const RegType& long_hi_type,
244                                    const RegType& int_type)
245       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
246 
247   /*
248    * Verify types for A two-register instruction with a literal constant (e.g. "add-int/lit8").
249    * "dst_type" is stored into vA, and "src_type" is verified against vB.
250    *
251    * If "check_boolean_op" is set, we use the constant value in vC.
252    */
253   void CheckLiteralOp(const Instruction* inst,
254                       const RegType& dst_type, const RegType& src_type,
255                       bool check_boolean_op, bool is_lit16)
256       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
257 
258   // Verify/push monitor onto the monitor stack, locking the value in reg_idx at location insn_idx.
259   void PushMonitor(uint32_t reg_idx, int32_t insn_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
260 
261   // Verify/pop monitor from monitor stack ensuring that we believe the monitor is locked
262   void PopMonitor(uint32_t reg_idx) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
263 
264   // Stack of currently held monitors and where they were locked
MonitorStackDepth()265   size_t MonitorStackDepth() const {
266     return monitors_.size();
267   }
268 
269   // We expect no monitors to be held at certain points, such a method returns. Verify the stack
270   // is empty, failing and returning false if not.
271   bool VerifyMonitorStackEmpty() const;
272 
273   bool MergeRegisters(const RegisterLine* incoming_line)
274       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
275 
GetMaxNonZeroReferenceReg(size_t max_ref_reg)276   size_t GetMaxNonZeroReferenceReg(size_t max_ref_reg) {
277     size_t i = static_cast<int>(max_ref_reg) < 0 ? 0 : max_ref_reg;
278     for (; i < num_regs_; i++) {
279       if (GetRegisterType(i).IsNonZeroReferenceTypes()) {
280         max_ref_reg = i;
281       }
282     }
283     return max_ref_reg;
284   }
285 
286   // Write a bit at each register location that holds a reference
287   void WriteReferenceBitMap(std::vector<uint8_t>& data, size_t max_bytes);
288 
GetMonitorEnterCount()289   size_t GetMonitorEnterCount() {
290     return monitors_.size();
291   }
292 
GetMonitorEnterDexPc(size_t i)293   uint32_t GetMonitorEnterDexPc(size_t i) {
294     return monitors_[i];
295   }
296 
297  private:
CopyRegToLockDepth(size_t dst,size_t src)298   void CopyRegToLockDepth(size_t dst, size_t src) {
299     SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(src);
300     if (it != reg_to_lock_depths_.end()) {
301       reg_to_lock_depths_.Put(dst, it->second);
302     }
303   }
304 
IsSetLockDepth(size_t reg,size_t depth)305   bool IsSetLockDepth(size_t reg, size_t depth) {
306     SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
307     if (it != reg_to_lock_depths_.end()) {
308       return (it->second & (1 << depth)) != 0;
309     } else {
310       return false;
311     }
312   }
313 
SetRegToLockDepth(size_t reg,size_t depth)314   void SetRegToLockDepth(size_t reg, size_t depth) {
315     CHECK_LT(depth, 32u);
316     DCHECK(!IsSetLockDepth(reg, depth));
317     SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
318     if (it == reg_to_lock_depths_.end()) {
319       reg_to_lock_depths_.Put(reg, 1 << depth);
320     } else {
321       it->second |= (1 << depth);
322     }
323   }
324 
ClearRegToLockDepth(size_t reg,size_t depth)325   void ClearRegToLockDepth(size_t reg, size_t depth) {
326     CHECK_LT(depth, 32u);
327     DCHECK(IsSetLockDepth(reg, depth));
328     SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
329     DCHECK(it != reg_to_lock_depths_.end());
330     uint32_t depths = it->second ^ (1 << depth);
331     if (depths != 0) {
332       it->second = depths;
333     } else {
334       reg_to_lock_depths_.erase(it);
335     }
336   }
337 
ClearAllRegToLockDepths(size_t reg)338   void ClearAllRegToLockDepths(size_t reg) {
339     reg_to_lock_depths_.erase(reg);
340   }
341 
342   // Storage for the result register's type, valid after an invocation
343   uint16_t result_[2];
344 
345   // An array of RegType Ids associated with each dex register
346   UniquePtr<uint16_t[]> line_;
347 
348   // Back link to the verifier
349   MethodVerifier* verifier_;
350 
351   // Length of reg_types_
352   const uint32_t num_regs_;
353   // A stack of monitor enter locations
354   std::deque<uint32_t> monitors_;
355   // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor
356   // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a
357   // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5
358   SafeMap<uint32_t, uint32_t> reg_to_lock_depths_;
359 };
360 std::ostream& operator<<(std::ostream& os, const RegisterLine& rhs);
361 
362 }  // namespace verifier
363 }  // namespace art
364 
365 #endif  // ART_RUNTIME_VERIFIER_REGISTER_LINE_H_
366