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